Research · Papers · Direct sums, wedges and the p14 frontier · ML-061

Model transfer barriers for finite-field multiplication complexity

Tensor rank does not transfer to unrestricted sequential XAG lower bounds; GF(4) cost is 3, GF(8) bilinear/depth-one ladder is 6,5,3

ML-061PROVEDSOLVER-CONFIRMEDDirect sums, wedges and the p14 frontier

Published 2026-09-04

For everyone

Plain summary

Multiplying elements in small finite fields takes a minimum number of non-linear multiplication steps. Researchers track this cost across different circuit models, including bilinear tensor rank, rational circuits, geometric models, and unrestricted sequential circuits (where one multiplication can feed into the next).

This work proves that lower bounds established for tensor rank do not transfer automatically to unrestricted sequential circuits. For GF(4), the unrestricted multiplication cost is 3, whereas geometric models achieve cost 2. For GF(8), the bilinear ladder gives exact costs of 6, 5, and 3 across different models, while sequential circuits follow separate bounds.

Two caveats apply to this record. First, the exact unrestricted cost of 3 for GF(4) is prior art from existing literature. Second, the unrestricted GF(8) cost interval [4,6] reported here was later resolved to an exact cost of 6 by entry MF-128.

Result

Tensor rank and bilinear rank lower bounds do not transfer as lower bounds for unrestricted sequential XOR-AND graphs (XAGs). Multiplicative complexity bounds separate across models as follows:

For GF(4):

Unrestricted exact cost: 3
Rational exact cost: 3
Rational border cost: 3
Geometric exact cost: 2
Geometric border cost: 2

For GF(8):

Bilinear / depth-one ladder: exact costs are 6, 5, and 3
Geometric XAG cost: 3
Rational XAG cost interval: [4,5]
Unrestricted XAG cost interval: [4,6] (superseded by MF-128 to exact cost 6)

A known bilinear or tensor rank lower bound does not bank an equivalent lower bound in the unrestricted sequential XAG model.

Setting and definitions

Let GF(2^k) denote the finite field of order 2^k over GF(2). Field multiplication is treated as a bilinear map or multi-output Boolean function f : GF(2)^k x GF(2)^k -> GF(2)^k.

The computational models are:

Unrestricted sequential XAG: Boolean circuits of two-input XOR gates (zero cost) and two-input AND gates (unit cost), where AND inputs may depend on prior AND outputs.
Bilinear / depth-one: Circuits where AND gate inputs are restricted to linear combinations of primary inputs.
Rational and border models: Arithmetic circuits over rational function fields and their topological/algebraic border closures.
Geometric models: Geometric tensor decompositions and projective varieties associated with field multiplication tensors.

Method

Model separations were verified through proof certificates and automated search:

Bilinear and depth-one ladders were verified via algebraic tensor decomposition checks in zkgolf-decomp/reports/VERIFY-STRASSEN.md and zkgolf-decomp/reports/COUNCIL-STRASSEN.md.
Unrestricted circuit bounds were evaluated with SAT encodings solved using CaDiCaL, tracked in zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md.
Verification receipts: zkgolf-decomp/verify-strassen-scratch/finite-checks-receipt.json (SHA-256 d5038c528fa125b3ee78e3a614db72d8d8f1582ea614ddf0941011059a00bc5c) and zkgolf-decomp/verify-strassen-scratch/cadical-receipt.json (SHA-256 5921cec7ad1f7e531882c568b4f45aea8ad81517f2295780204b32ba4c56fe6e).

Discussion

The primary contribution of ML-061 is establishing model-transfer barriers: a lower bound in a constrained algebraic model, such as bilinear tensor rank, cannot be transferred to unrestricted sequential multiplicative complexity without explicit verification.

Two updates attach to this entry:

GF(4) attribution: The exact unrestricted GF(4) multiplication cost of 3 is prior art. The three-term bilinear construction matches the quadratic-to-unrestricted transfer established by Mirwald and Schnorr (1992), with formulations in Find and Boyar (2014) and Ballet et al. (2011).
GF(8) interval supersession: The unrestricted GF(8) interval [4,6] recorded under ML-061 was superseded by MF-128, which proved an exact unrestricted cost of 6 via a solver-independent lower bound proof and complete-domain upper bound replay (documented in zkgolf-decomp/FREE-VERIFY.md and zkgolf-decomp/FREE-05.md).

The transfer barrier itself stands: resolving GF(8) in MF-128 required a dedicated proof, not a generic transfer theorem from tensor rank to unrestricted XAGs.

For everyone — the takeaway

What this means

Circuit models count multiplication steps under different rules. Some models let intermediate products feed into later multiplications, while others require every multiplication to run in parallel in a single layer.

This result shows that lower bounds do not carry over between models. Proving that a field requires a certain number of multiplications under structured tensor rules does not prove that general circuits need that many. Each circuit model requires its own explicit lower bound proof.

Attribution and prior art

Prior art: An unrestricted multiplication cost of 3 in GF(4) is prior art established by Mirwald–Schnorr (1992), Find–Boyar (2014), and Ballet et al. (2011). Sources: arXiv:1407.6169 · arXiv:1107.1184 · doi:10.1016/0304-3975(92)90235-8

Register references

Entry: ML-061 (related entries: MF-120, MF-128)
Reports: zkgolf-decomp/reports/VERIFY-STRASSEN.md, zkgolf-decomp/reports/COUNCIL-STRASSEN.md, zkgolf-decomp/reports/STATE-OF-PROGRAM-V2.md, zkgolf-decomp/reports/PRIOR-ART-S5.md
Artifact receipts:
zkgolf-decomp/verify-strassen-scratch/finite-checks-receipt.json (SHA-256 d5038c528fa125b3ee78e3a614db72d8d8f1582ea614ddf0941011059a00bc5c)
zkgolf-decomp/verify-strassen-scratch/cadical-receipt.json (SHA-256 5921cec7ad1f7e531882c568b4f45aea8ad81517f2295780204b32ba4c56fe6e)
zkgolf-decomp/PRIOR-ART-S5.md
zkgolf-decomp/FREE-VERIFY.md
zkgolf-decomp/FREE-05.md
Prior-art citations:
C. P. Mirwald and C. P. Schnorr, "The multiplicative complexity of quadratic Boolean forms," Theoretical Computer Science 102(2) (1992), 307–328, doi:10.1016/0304-3975(92)90235-8
M. Gausdal Find and J. Boyar, "Multiplicative Complexity of Vector Valued Boolean Functions," arXiv:1407.6169
S. Ballet et al., "On the Tensor Rank of Multiplication in Finite Fields," arXiv:1107.1184

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 3 of 8 receipt files bundled (32 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Changelog

Last reviewed 2026-09-04

2026-08-30Correction (2026-08-30): Model labels and numerical boundaries in ML-061 stand unchanged, but the exact unrestricted GF(4)-multiplication cost 3 is prior art credited to Mirwald and Schnorr (1992), Gausdal Find and Boyar, and Ballet et al.
2026-08-31As of 2026-08-31, MF-128 supersedes ML-061 by confirming the unrestricted GF(8) value is exactly six through an independent lower proof and verified replay. The model-transfer wall and every GF(4), rational, geometric, border, bilinear, and depth-one label in ML-061 still stand.
2026-09-04Published on this site.

Related in this programme

All papers The register The institute