Refutation of three proposed multiplicative complexity laws

Result

Three candidate multiplicative complexity laws in the GF(2) XAG cost model are disproved:

1. The general odd-multiplier valuation law MC(a x mod 2^n) = max(0, N - s - 1) is false. The lexicographically minimal counterexample is MC(11 x mod 128) = 6, refuting the predicted complexity of 5. The proven shear subfamily MC((1+2^s) x mod 2^n) = max(0, n-s-1) is unaffected and stands.
2. The square catalyst law kappa_sq(n) = 1 for n >= 5 is false at n = 7. Both complexity 5 (rank-tight) and the conjectured complexity 6 are impossible; a verified eight-gate circuit gives MC(S_7) in [7,8], proving kappa_sq(7) in {2,3} ≠ 1.
3. The odd reciprocal law MC(I_n) = max(0, n-4) is false: MC(I_9) = 6 ≠ 5.

Setting and definitions

Let MC(f) denote the multiplicative complexity of a Boolean or bit-vector function f over GF(2), defined as the minimum number of two-input AND gates in an XOR-AND graph (XAG) computing f.

• MC(a x mod 2^n) denotes the multiplicative complexity of modular constant multiplication by an odd integer a.
• S_n denotes the modular squaring operator over n-bit inputs, and kappa_sq(n) denotes the associated square catalyst overhead.
• I_n denotes the n-bit odd modular reciprocal operation.

Method

Each refutation is established at evidence tier FC+FR (full certification and full replay):

• For MC(11 x mod 128), complete truth-space ordered-flag exhaustion establishes MC ≥ 6. An exact six-gate circuit replayed on all 128 input states establishes MC ≤ 6.
• For S_7, lower-bound certification proves that 5-gate and 6-gate circuits are impossible. An eight-gate circuit replayed on all inputs bounds MC(S_7) to [7,8], yielding kappa_sq(7) in {2,3}.
• For I_9, exact evaluation demonstrates MC(I_9) = 6, refuting the conjectured value of 5.

Verification receipts and circuit artifacts are recorded in CONST-MULT-LAW.md and SQUARE-CATALYST.md.

Discussion

These refutations eliminate three candidate general laws so downstream lower bounds and circuit synthesis routines do not build on false assumptions.

The scope of the results is specific:

• The failure of the general odd-multiplier law does not affect the proven shear subfamily formula MC((1+2^s) x mod 2^n) = max(0, n-s-1).
• The failure of kappa_sq(7) = 1 bounds the true catalyst overhead at n = 7 to {2,3}.
• No prior-art claims are recognized for these candidate laws beyond the refuted formulations.

Register references

• MF-143
• CONST-MULT-LAW.md
• SQUARE-CATALYST.md

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

Download evidence.zip

Related in this programme

• MF-137
  The packing lemma lower bound for multiplicative complexity
• MF-153
  Solver-Free Multiplicative Complexity Lower Bounds from Degree and Walsh Floors
• MF-106
  The 37-wall atlas of failed proof routes and scope limits