Research · Papers · Symmetry, state encodings and search gauges · ML-055
Exact gate-state duality and 1-Lipschitz potential bounds for multiplicative complexity
Gate-state shortest path equals MC with LP dual as 1-Lipschitz potential; quotient certificates require complete edge sets.
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of multiplication (AND) gates needed to compute a Boolean function when linear operations (XOR) are free. Computing multiplicative complexity is identical to finding the shortest path on a network of circuit states, where each step corresponds to an allowed multiplication. Through linear programming duality, this shortest path problem converts into assigning a numerical height to each state such that no single multiplication changes the height by more than one (a 1-Lipschitz potential).
When simplifying this network by grouping states together, leaving out even one possible transition produces false lower bounds. Valid lower bound certificates on grouped states must check every induced transition.
Result
In the GF(2) XOR-free multiplicative complexity model, MC(f) equals the exact shortest-path distance from the initial input state to the target state on the complete semantic gate-state graph.
The linear programming dual of this shortest-path formulation is the maximal 1-Lipschitz potential problem on the semantic gate-state space. A lower bound certificate evaluated over a quotient state space is sound if and only if the quotient edge set includes all induced semantic transitions. Omitting transitions produces spurious lower bounds.
Setting and definitions
Let G = (V, E) be the directed semantic gate-state graph. Vertices V represent linear subspaces of Boolean functions over GF(2) spanned by the inputs and previously computed intermediate products. A directed edge (u, v) ∈ E exists if and only if state v is reachable from state u by adjoining a single product of two affine functions available in u.
The shortest path from the initial state to any subspace containing f gives MC(f). Its linear programming dual assigns a real potential Φ(u) to each state u ∈ V satisfying:
- Φ(v) - Φ(u) ≤ 1 for all (u, v) ∈ E (the 1-Lipschitz condition).
- Φ(target) - Φ(start) bounds the shortest-path distance from below.
For a partition of V into quotient classes V_Q, the induced edge set E_Q contains ([u], [v]) whenever there exist u' ∈ [u] and v' ∈ [v] with (u', v') ∈ E.
Method
The exact gate-state shortest-path problem was formulated as an integer linear program whose continuous LP relaxation dualizes to the 1-Lipschitz potential problem. Duality and certificate validation were tested on small cell test cases using full certificate generation (tier P + FC).
Receipt artifacts:
j3-normal-form-dual.lp(SHA-2566c4d382908e80ca879c4b3f58b8ec7004b32cbe1f4c60b473a7093099aba15fe), containing the dual LP for the j3 normal form.dual-certificate.receipt.json(SHA-25601fe39f50fa66314c0356cda17480b94124c5ef496dca132a08ed7969cb695c4), recording dual potential values and edge completeness checks.- Synthesis and validation reports:
zkgolf-decomp/reports/CERT-DUAL.mdandzkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
Discussion
Exact duality holds on the complete semantic gate-state graph, where the maximal 1-Lipschitz potential difference equals MC(f) exactly. Aggregating states into quotient classes reduces graph size, but omitting any valid semantic transition allows the dual potential to assign height differences larger than 1 across the omitted transition, generating inflated lower bounds. Quotient certificates must verify every induced semantic transition across the partition.
For everyone — the takeaway
What this means
Proving lower bounds on multiplication counts is equivalent to setting up a height function on circuit states where each multiplication step climbs at most one unit. If states are grouped together to simplify the calculation, every valid transition between groups must be accounted for. Missing a single transition makes the function look harder to compute than it actually is.
Register references
- Register Entry: ML-055
- Cross-reference: MF-113
- Reports:
zkgolf-decomp/reports/CERT-DUAL.mdzkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md- Artifacts:
zkgolf-decomp/cert-dual-scratch/dual-certificate.receipt.json(SHA-25601fe39f50fa66314c0356cda17480b94124c5ef496dca132a08ed7969cb695c4)zkgolf-decomp/cert-dual-scratch/j3-normal-form-dual.lp(SHA-2566c4d382908e80ca879c4b3f58b8ec7004b32cbe1f4c60b473a7093099aba15fe)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 3 receipt files bundled (27 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.