Acashic Research Institute · The papers
The Papers
Every listed result, written up in full. Each paper starts and ends in plain language anyone can follow; the middle is written for specialists. Pick any title that sounds interesting; the opening will tell you what it says and why it matters before any math shows up.
Adders, counters and the heap law
Exact multiplicative complexity bounds, carry-save recursions, and digit-sum laws for integer additions and compressor slices.
- MF-023Exact multiplicative complexity of two exposed-sum ripple chainsCERTIFIED PROOFPublished 2026-08-29
MC(I_L) = 2L MC(FullAdd(K,n)) = Kn − s₂(K(2ⁿ−1)); FullAdd(5,2) = 6 ≠ 8MC(J_m) = MC(A_{3,m+1}) − 1; J₃₂ = Add32x3Canon33 ∈ {61,62}- MF-114Exact restriction loss conservation law for multiplicative complexityCERTIFIED PROOFPublished 2026-09-04
MC(f) - MC(f|_R) = k_R + e_R with lifted potential k_R + ψ_R 1-Lipschitz; J_2 spectrum has four (1,0) and six (0,1). - MF-118Exact shear symmetry of multiplicative complexity in constant additionRECEIPTEDPublished 2026-09-04
MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}), with MC(F_{2,K}) = 2 and MC(F_{3,K}) = 5 for all constant offsets K - MF-131Classification of One-Word XOR-Mask Transports for Four-Word AdditionRECEIPTEDPublished 2026-09-04
Affine transport exists iff 2^(n-2)|M and 2^(n-2)|Δ; componentwise affine correction exists iff 2^(n-2)|M and Δ ≡ M (mod 2^(n-1)). - MF-136Exact multiplicative complexity of 5-by-3 addition and six addition floorsRECEIPTEDPublished 2026-09-04
MC(Add(5,3)) = 5, with Add(5,4) >= 8, Add(5,5) >= 10, Add(6,3) >= 6, Add(6,4) >= 9, Add(7,3) >= 7, Add(7,4) >= 11 - MF-138Exact multiplicative complexity of the two-column C7 carry transducerRECEIPTEDPublished 2026-09-04
MC(T) = 6 for the 11-input, 5-output two-column C7 carry transducer - MF-152Sharpness of the 5/8 law and multiplicative complexity of n-bit additionRECEIPTEDPublished 2026-09-04
delta = (5/8)^p attained at MC = p for disjoint ANDs, mod 2^n addition (MC = n - 1), and full addition (MC = n); Floor A <= 1.4747 mPrior art: While the value n - 1 was previously reported in BPP (2000, abstract only), the sharpness of this internal constant appears to be new.
MC(MAJ7) = MC(T^7_4) = 4Prior art: Boyar–Peralta (2008) established the published bounds `[3,4]`, where Thm 10 gives `<= 4` and Thm 8 / Schnorr degree give `>= 3`.
- MF-171Exact multiplicative complexity of carry-calculus and threshold functionsSOLVER-CONFIRMEDPublished 2026-09-04
59 exact MC values for small multi-bit threshold functions; D(m)=floor(log2 m)-[m!=2^b-1] proved for bridge; MCmax(S_m)=m-1 for m<=7Prior art: The symmetric cases and maximum MC bound are from BCSTP, correcting an earlier attribution to Boyar–Peralta (2008).
- MF-179Exact Multiplicative Complexity of Parallel Counters and Multi-Operand CompressorsRECEIPTEDPublished 2026-09-04
MC(3->2)=1, MC(4->3)=3, MC(5->3)=3, MC(6->3)=4, MC(7->3)=4, MC(4:2)=2, MC(5:2)=3, MC(6:2)=4 over F_2Prior art: This result establishes closed exact bounds that appear to be new, though the overall problem remains partially solved.
MC(K_m) = 2m+1 for every m ≥ 1Prior art: This result appears to be new as a general family statement: while Boyar–Peralta counted the redundant object, the exact count for the resolved object is not found in the known literature.
- MF-182Unification of Additive Line Multiplicative Complexity via Greedy Column-Heap RecursionRECEIPTEDPublished 2026-09-04
Heap recursion d_0=k+c0, d_{i+1}=k+⌈(d_i-1)/2⌉ with cost Σ⌈(d_i-1)/2⌉ matches all exact MC values for multi-operand addition and H_n.Prior art: While the recursion is based on standard carry-save and Dadda dot reduction, the observation that it matches every exact XAG value, including the boundary constants, appears to be new.
- ML-087Multiplicative complexity of cascaded k:2 carry-save compressor slicesRECEIPTEDPublished 2026-09-04
MC(k:2) = k - 2 for cascaded Full Adder compressor slices in the sequential XAG model (MC(4:2)=2, MC(5:2)=3, MC(6:2)=4) - MF-002An upper bound on the multiplicative complexity of a three-column interior adder tileRECEIPTEDPublished 2026-08-29
MC(g) ≤ 9Prior art: While the 2026 STACS MDFA/cirbo generator is used as the comparison point at twelve reported nonlinear gates, entry MF-077 clarifies that it does not represent the state-of-the-art baseline for AND count.
- MF-040An upper bound on the multiplicative complexity of the natural (S,S+R) componentEXHAUSTIVE CHECKPublished 2026-08-29
MC(component) ≤ 8 for the 13-input, 7-output natural (S,S+R) component - MF-053Refutation of stationary additive raw/state phases by a three-column divergent carry pathNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Natural edge quotient has 491,040 candidates across 245,520 classes with span rank 74; 40 elementary q_i(c)*u_j are linearly independent x+y+z+w+c₀+2c₁ = s+2c₀′+4c₁′ using 3 AND gates; full-precision sum of four n-bit integers uses 3n ANDsPrior art: The claimed 25% improvement is revised: standard carry-save baselines also achieve 3n AND gates, as the Cirbo/STACS generator’s 4n figure optimizes total gates instead.
- MF-083An eight-product circuit for the low four bits of four four-bit numbersEXHAUSTIVE CHECKPublished 2026-08-29
The low four bits of x₀ + x₁ + x₂ + x₃ are computed by an acyclic XAG with 8 products MC(A_{k,2}) = ⌊k/2⌋ for every k ≥ 22n−4 ≤ MC(A_{3,n}) ≤ 2n−3; the upper is exact at n = 2,3,4,5 and for prefix-causal circuitsMC(A_{k,n}) ≤ T(k,n) = (k−1)(n−1) − Σ_{r=1}^{n−1}⌊(k−1)/2ʳ⌋- MF-104Verified width-three constructions for nine and ten operandsEXHAUSTIVE CHECKPublished 2026-08-29
MC(A_{9,3}) ≤ 10 and MC(A_{10,3}) ≤ 12; both are replayed uppers, not exact values - MF-107Counterexamples to four former addition lawsNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
FullAdd (K−1)n, greedy truncated equality, U(k,n) tightness, and CS-base for k ≥ 9 are refuted CONJECTURE: MC(A_{k,n}) = T(k,n); the first sharp stable fork is A_{9,3} ∈ {9,10}MC(A_{5,3}) = 5; MC(A_{4,4}) ∈ [6,8], not exact 8 on retained evidence- MF-111Bounds on the multiplicative complexity of the injected-carry familyEXHAUSTIVE CHECKPublished 2026-09-04
2m-3 ≤ MC(J_m) ≤ 2m-2 for m ≥ 2; MC(J_2)=2, MC(J_3)=4, MC(J_4)=6, J_5 ∈ [7, 8] - MF-115Exact Kummer endpoint valuation and boundary-alias count for FullAddRECEIPTEDPublished 2026-09-04
MC(FullAdd(K,n)) = v_2((KB_n)! / (B_n!)^K) for K,n ≥ 1, B_n = 2^n - 1; eventual gap is (r-1)K - 2^r + 2 for r = ⌈log_2 K⌉ 18 ≤ E_9 ≤ 36H_n(K) = 4n - 6 - λ_n(K) for the canonical constant-heap classComplexity equals T(k,n) for the canonical heap-prefix class; transfer counterexample shows this does not prove unrestricted MC(A_{k,n})=T(k,n)Obtained J_3 witnesses partition into 7 unpointed gate-space orbits and 10 pointed restriction-comodule types; full census remains open.For c ∈ {2,3,4}, C7 c-column target requires 3 new gate-class dimensions beyond the 3(c-1)-gate prefix, giving exact cost 3c under prefix constraint- MF-140Exact multiplicative complexity of A_{4,3} and constant-added addition F_{3,K}RECEIPTEDPublished 2026-09-04
MC(A_{4,3}) = 5 = MC(F_{3,K}) for every K mod 8; MC(F_{2,K}) = 2 = MC(A_{4,2}) - MF-150Exact multiplicative complexity of 2×2 unsigned integer multiplierEXHAUSTIVE CHECKPublished 2026-09-04
MC(2×2 unsigned integer multiplier) = 4Prior art: This is a partial result, as small multipliers are well-studied and likely already known.
- MF-170Exhaustion of the t = 5 Two-Phase Route for 22-Variable Symmetric FunctionsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
C(22,5)=18 at state (1,1,1,2); max_{f∈S_22} min_{free} MC(g_f)=4 yielding bound 22; parity device has gain 0 at t=5 vs gain 1 at t=4Prior art: The H_1 cost and the 21-vs-22 statement are established results credited to BCSTP (§4.1.3, §5.1, Tables 3–4). Sources: ePrint 2019/708
- MF-183Discard-tax principle for heap optimality with discarded top digitsOPEN QUESTIONPublished 2026-09-04
MC(S⁻) = MC(S) − (heap ANDs exclusive to the dropped digits) - ML-049An eight-product acyclic XAG for the low four bits of x₀+x₁+x₂+x₃EXHAUSTIVE CHECKPublished 2026-08-29
An acyclic XAG computes the low four bits of x₀+x₁+x₂+x₃ in 8 products (target 4op_w4_p8, p = 8 is SAT) - ML-054Multiplicative complexity bounds for the injected-carry family J_mOPEN QUESTIONPublished 2026-09-04
2m-3 ≤ MC(J_m) ≤ 2m-2 with MC(J_2)=2, MC(J_3)=4, MC(J_4)=6, and J_5 ∈ [7,8] - ML-056Restriction conservation law for multiplicative complexity under exact restrictionCERTIFIED PROOFPublished 2026-09-04
MC(f) - MC(f|_R) = k_R + e_R under exact restriction, with 1-Lipschitz potential k_R + ψ_R; exhaustive J_2 spectrum is 4×(1,0), 6×(0,1) v_2((K(2^n-1))!/((2^n-1)!)^K) and P=∑_j min(h_j, 2^{n-j}-1) proved; gap is (r-1)K-2^r+2 with r=⌈log_2 K⌉; unrestricted MC=T is open18 ≤ E_9 ≤ 36- ML-060Symmetry and exact small-width complexity of constant-addition shearsRECEIPTEDPublished 2026-09-04
MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}), with MC(F_{2,K}) = 2 and MC(F_{3,K}) = 5 for every constant K - ML-065BLAKE3 and ARX redeployment limits from banked addition assetsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Direct redeployment of banked addition assets yields ≥ 10304 products on BLAKE3, exceeding the 10298-product conditional leader - ML-068Impossibility of Constant Absorption by Memoryless Scalar Carry CodesNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
No block with boundary state encoding scalar carry 0..4 beats 4 ANDs/col once carry 4 is reachable. τ_4 = MC(K_4) − MC(J_5) ∈ {1,2}; MC(K_4) = 9, MC(J_5) ∈ [7,8]
The SHA-256 record and exact synthesis
Gate optimization for SHA-256 round circuits, tracking the open 61-versus-62 injected-carry gap in three-operand addition.
∀x ∈ {0,1}^n, C(x) = f(x)- MF-048Quadratic-hull screens of two-column SHA-256 seed allocationsOPEN QUESTIONPublished 2026-08-29
All four K-pairs: 92,274,688 honest rows, degree-two rank 837 of 862, ideal dimension 25; JSC-13, JSC-12, JSC-11 fail instrument gate m_t xor m_(t+1) = (a_t xor b_t) * (a_t xor b_t xor c_t xor a_(t+1)) across all 16 local inputs- MF-062Exact fibre cardinality of the two-round SHA-256 edge-relaxed relationPAPER PROOFPublished 2026-08-29
p0 = b xor (U-P), p1 = p0 xor ((a xor b) and (a xor b xor c xor U)), P = T1 + Sigma0(a) mod 2^32 yields b_(t+2)=U and fibre cardinality 2^32 In F2[x]/((x+1)^{2^r}), every XOR sum of an odd number of cyclic rotations is invertible (s(1)=1), so SHA-256 Sigma0 has matrix rank 32verified rows = 22,215; authorized row change = 0; no row improvement is claimed- MF-141Full linear rank of multiplicative rows in the SHA-256 leader circuitNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Rank of 22,215 product equations modulo affine forms is 22,215/22,215 over GF(2); no linear product row elimination exists. - ML-010Affine rank of product-output functions and fixed-XOR optimization in the leaderNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
OPT_fixed-XOR = 274 p7 target 21,738: 2,018 dead_tail / 181,441 blockers across 768 rows, 0 unresolved tails, global closure = UNKNOWN, status = LIVE-PARKED- ML-025The p8 top-form obstruction for the exact three-column boundary tileNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Exact functional four-word tile T with output degrees [1,2,4,6,9] has no p8 circuit - ML-035Fixed-interface factor-component contraction on the 22,215-row leaderNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Fixed-interface factor-component contraction is closed on 22,215-row leader: 20,525 full-rank paths (18,837×(1,1), 1,686×(2,2), 2×(3,3)) - ML-040Piecewise cubic separation of JSC-12 cases in the flip-support subspaceRECEIPTEDPublished 2026-08-29
Piecewise pair (k0=0 principal, k0=1 companion) separates K10/K11; no square-free cubic meeting {middle1, middle2, final0} rejects witness - ML-042A polar rank 8 separator in the JSC-12 K1x even dual cosetNEGATIVE RESULTRECEIPTEDPublished 2026-08-29
JSC-12 K1x even dual coset separator middle2 * Q has polar rank 8, Hamming weight 37, satisfying K10=K11=0 and FALSE_CUBIC=1 K=4,n=2,p=1: UNSAT; K=3,n=3,p=2: UNSAT; K=3,n=3,p=3: SAT; K=2,n≤5,p=3: UNSAT- ML-063SHA-256 compilation record and status of conditional sub-22,215 alternativesRECEIPTEDPublished 2026-09-04
SHA-256 record = 22215 rows; hypothetical alternatives at 20612, 20531, and 22185 remain conditional without full witnesses - ML-067Limits of SHA-256 row reduction from banked component certificatesNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Banked certificates cover 20,248 of 22,215 SHA-256 rows but license 0 reductions due to non-additivity and a 1,967-row component deficit - ML-069Exact additivity of two-copy block sharing in leader pairsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Consecutive-round Ch and Maj pairs and schedule adder pairs are exactly additive at width 32; block sharing across real pairs yields 0 savings. Maj edge phase -1,024 candidate phase defect grows linearly at 32k bits for k=1..4, refuting the candidate with zero solver time.- ML-072Universal screen refutation of the JSC one-catalyst classNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
For JSC-11, degree-3 evaluation hull accepts a non-honest point, killing all acyclic one-catalyst lifts k ≤ 1. - ML-073Closure of redundant-carry seam route for natural prefixesNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Natural seam chains cost exactly 3c (gate-class rank equals gate count for c=2,3,4), exceeding the 2.875c leader schedule step threshold march_cu on c=3/p=8 yielded 4096 cubes timing out at 600 s; algebraic reduction enables 0.4-6 s decisions.
Cipher S-boxes, χ, and quantum gate counts
Exact AND depths for block-cipher S-boxes, Keccak permutations, Toffoli gates, and Kochen-Specker vector sets in C⁶.
- MF-080A lower bound on the Toffoli count of exact NCT networks implementing χ₅PAPER PROOFPublished 2026-08-29
For every exact NOT/CNOT/Toffoli network N implementing χ₅ with clean ancillas, #Toffoli(N) ≥ MC(χ₅⁻¹) = 6Prior art: No separate prior-art claims are made.
- MF-116Strict syntactic-equivariant inverse-χ costs at widths 3, 5, and 7CERTIFIED PROOFPublished 2026-09-04
E_3 = 3, E_5 = 10, E_7 = 21 for strict syntactic-equivariant inverse-χ; equivariance taxes are 0, 4, 12 over unrestricted costs 3, 6, 9 - MF-128Exact unrestricted multiplicative complexity of binary GF(8) multiplicationEXHAUSTIVE CHECKPublished 2026-09-04
MC_XAG,F_2(F_8 × F_8 → F_8) = 6 in basis F_2[r]/(r^3 + r + 1) MC(χ_n) = n for every n ≥ 3, with coordinate rule χ_i = Rule210_{i+1}- MF-130Exact multiplicative complexity of all powers of the width-four chi mapRECEIPTEDPublished 2026-09-04
MC(χ₄⁰)=0, MC(χ₄)=4, MC(χ₄²)=5, MC(χ₄³)=4; MC(χ₄^k)=5 for even k≥2, MC(χ₄^k)=4 for odd k≥1 MC(chi_n, chi_n^2) = 2n for all n >= 4- MF-135Three sound whole-function multiplicative complexity lower-bound floorsRECEIPTEDPublished 2026-09-04
MC(F) >= ceil(-log2 delta(F)/log2(8/5)), MC(F) >= max(ceil Lambda, ceil Sigma), MC(F) >= ceil(E_H MC(F|H) + alpha_{N,d}) - MF-147Basis-free lower bound on the multiplicative complexity of GF(2^k) multiplicationRECEIPTEDPublished 2026-09-04
MC(GF(2^k) multiplication) ≥ ⌈5k/2⌉ - 2 in the unrestricted XAG model, basis-freePrior art: This result appears to be new: existing bilinear and tensor-rank literature (Chudnovsky–Chudnovsky; Shparlinski–Tsfasman–Vlăduţ; Ballet et al.) bounds a different model, and NIST lists the multiplicative complexity (MC) of vectorial functions on `>= 5` bits as an open problem.
MC(chi_5^2) = 7, closing the [6,7] bracket at the top, with eps_5 = 10 - 7 = 3 = eps_4Prior art: This appears to be a new result.
- MF-156The k-window law for joint multiplicative complexity of Chi iteratesRECEIPTEDPublished 2026-09-04
MC(chi_n, ..., chi_n^k) = k n for 1 <= k <= floor(n/2), sharp in k; joint rank drops below k n at k = floor(n/2) + 1Prior art: Kriepke–Kyureghyan previously bounded Hadamard products for a single iterate using degree arguments, and the Schoone–Daemen order formula already established `chi_3^2 = id`.
- MF-167Exact quadratic multiplicative complexity of GF(2^4) multiplication and polymul_4RECEIPTEDPublished 2026-09-04
qMC(GF(2^4) mult) = 9, qMC(polymul_4) = 9, unrestricted MC(GF(16) mult) ∈ [8,9], MC(polymul_4) ∈ [8,9]Prior art: The value 9 is already known from Karatsuba and Winograd's bilinear theory.
- MF-168Exact multiplicative complexity of GF(16) inversion and bounds for GF(32)RECEIPTEDPublished 2026-09-04
MC(GF(2^4) inversion) = 5; MC(GF(2^5) inversion) ∈ [7, 14] with qMC(x^3) = qMC(x^5) = 7Prior art: GF(16) inversion is the core of tower-field AES S-boxes (Canright 2005; Boyar–Peralta 2010), with Stoffelen’s SAT study of 4-bit S-boxes (FSE 2016) confirming the inverter cost at 5.
- MF-176Exact multiplicative complexity of all 16 optimal 4-bit S-box classes and standard ciphersRECEIPTEDPublished 2026-09-04
MC=5 for G0,G1,G2,G5,G8,G9,G12,G15,G4,G10,G14; MC=4 for G3,G6,G7,G11,G13; MC(PRINCE)=5, MC(PRESENT,GIFT,RECTANGLE,Piccolo,SKINNY)=4 - ML-058Exact costs of strict syntactic equivariance for widths 3, 5, and 7CERTIFIED PROOFPublished 2026-09-04
E_3 = 3, E_5 = 10, E_7 = 21 with exact taxes 0, 4, 12 over unrestricted inverse-χ multiplicative complexity - MF-010An impossibility theorem for the χ₀₁ catalyst and the full-domain p7 tileEXHAUSTIVE CHECKPublished 2026-08-29
deg(f) = 9, 80 of 140 top monomials ∉ I = ⟨c₁c₂⟩ ⟹ χ₀₁ catalyst cannot realize full-domain p7 tile 6 ≤ MC(chi_5^2) ≤ 7Prior art: Prior bracket was [6,10].
- MF-155Multiplicative complexity lower bounds and brackets for chi_6^2 and chi_7^2RECEIPTEDPublished 2026-09-04
MC(chi_6^2) >= 8 (bracket [8, 12]) and MC(chi_7^2) >= 9 (bracket [9, 14])Prior art: This is an apparently new result cataloged as entry MF-154, achieved using fewer searches.
- MF-157Iterate structure, degree, and attributions for the Keccak chi mappingRECEIPTEDPublished 2026-09-04
deg chi_n^j = j+1 for j ≤ ⌊n/2⌋ (FC-verified n=3..13); |im(chi_n)| = 2^n - 2^{n/2} for even n; Ascon S-box is B ∘ chi_5 ∘ APrior art: Lemma A for odd n is due to Kriepke-Kyureghyan (CRYPTO 2024), while even n collisions match results from Schoone-Daemen (2024). Sources: ePrint 2024/801 · ePrint 2014/474
- MF-174Refutation of five candidate multiplicative complexity lower-bound conjecturesNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Five refutations: MC ≱ dim V + μ₁ + μ₂ - 2, plane parity bound fails, Lemma X fails at (4,3), linear catalysis fails, MC(χ,χ²,χ³) ≠ 3nPrior art: This result is supported by prior work, including the Mirwald–Schnorr <= 2-form import boundary, Boyar–Find’s open-problem statement, and the BCSTP redundant weight encoding.
- ML-017Universal wrong row-0 assignments in Toffoli-lift cyclic p6 modulesNEGATIVE RESULTLEGACY: NO RECEIPTPublished 2026-08-29
All 15 qdim-6 modules in the Toffoli-lift cyclic p6 family attain full rank and admit a universal wrong row-0 assignment - ML-018Exhaustion of the 3-gate full-domain start on the Toffoli acyclic p7 routeNEGATIVE RESULTLEGACY: NO RECEIPTPublished 2026-08-29
Real 3-gate full-domain start on Toffoli acyclic p7 route: EXHAUSTED after 786,430 factor checks; alternate prefixes: UNKNOWN - ML-064Infeasibility of K12 score reduction via banked rowwise chi5 replacementsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Rowwise chi5 in Keccak-p[1600,12] is optimal at 5 products per row (19,200 total); no banked rowwise replacement reduces the score. - ML-066Failure of Keccak-family score reduction via inverse-χ exactnessNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
Exact inverse-χ_5 and Ascon inverse circuits yield zero solver score reductions over forward-χ (MC(χ_n) = n). MC(GF(2^4) multiplication) ∈ [8, 9] in the unrestricted modelchi_6^2 ∈ [8, 12], chi_7^2 ∈ [9, 14]
Direct sums, wedges and the p14 frontier
Proving additivity of multiplicative complexity across disjoint monomial blocks and uncoupled matrix multiplications over GF(2).
- MF-084The separated-product theorem over any field under square closureCERTIFIED PROOFPublished 2026-08-29
If u ∈ U ⟹ u² ∈ U and v ∈ V ⟹ v² ∈ V, the separated-product theorem holds over any field kPrior art: This entry builds on predecessor MF-032; no position on external prior art is stated.
- MF-086Multiplicative complexity of independent copies of 2×2 matrix multiplication over GF(2)PAPER PROOFPublished 2026-08-29
rank_CP/bilinear(M₂^⊕s) = 7s, MC_formal-quadratic(M₂^⊕s) = 7s over GF(2)Prior art: The 7s value is credited to Alder-Strassen and Strassen under bilinear and formal-quadratic models, but this result has not been established for unrestricted Boolean settings.
- MF-148Exact unrestricted multiplicative complexity of 3-term binary polynomial multiplicationEXHAUSTIVE CHECKPublished 2026-09-04
MC(polymul_3 over F2) = 6 in the unrestricted modelPrior art: This is a known value obtained using classical Karatsuba multiplication for the NIST binary-polynomial category.
- MF-149A lower bound on multiplicative complexity of 2x2 matrix multiplication over F2RECEIPTEDPublished 2026-09-04
MC(M_2 over F2) >= 6, narrowing MC(M_2 over F2) to [6,7]Prior art: Winograd’s rank-7 optimality result applies specifically to bilinear algorithms; no unrestricted bound has been established.
- MF-163Direct-sum theorems and lower bounds for unrestricted multiplicative complexityRECEIPTEDPublished 2026-09-04
MC(F ⊕ G) ≥ dim V(F) + MC(G) with MC(F ⊕ G) = MC(F) + MC(G) if min(e(F), e(G)) = 0 or if dim V(F) = dim V(G) = 1 and MC(F) = MC(G) = 2Prior art: Theorem A and the rank floor are partly known or likely folklore (BPP 2000; Mirwald–Schnorr for the quadratic model).
- MF-164Exact multiplicative complexity of direct sums of monomial Boolean functionsOPEN QUESTIONPublished 2026-09-04
MC(x1x2x3 ⊕ y1y2y3y4) = 5, MC(x1x2x3 ⊕ y1y2y3) = 4, and additivity holds across all tested direct-sum cellsPrior art: Using standard methods from Calik–Turan–Peralta (ePrint 2015/848, 2018/002; arXiv 2005.01778), these specific direct-sum cells fall outside the n <= 6 census and appear to be new.
- MF-166Exact multiplicative complexity of a Fano 3-space at n = 8 and floor census at n = 4NEGATIVE RESULTRECEIPTEDPublished 2026-09-04
For explicit Fano W <= Λ^2(F2^8) with dim W = 3, m_2(W) = 6 and qMC(W) = MC(W) = 7 = dim W + 4.Prior art: This result is partial, and its novelty remains unverified because simplex-code packing is conceptually a standard technique in coding theory.
- MF-180Multiplicative complexity bounds for 2x2 matrix multiplication over GF(2)RECEIPTEDPublished 2026-09-04
6 ≤ MC(M_2(F_2)) ≤ 7 in sequential XAG over F_2, with qMC(W) ≥ 6 for an invariant 2-plane W ⊂ Λ^2(F_2^8)Prior art: This is a partial and apparently new result, establishing the first non-bilinear lower bound >= 6 for unrestricted XAG over F_2.
- ML-077Exact Multiplicative Complexity of x1x2x3 ⊕ y1y2y3y4NEGATIVE RESULTCERTIFIED PROOFPublished 2026-09-04
MC(x1x2x3 ⊕ y1y2y3y4) = 5 - MF-014Direct-sum additivity barrier for extension-field batching over F₂ᵐOPEN QUESTIONPublished 2026-08-29
Conjecture MF-014: batching over F₂ᵐ via Karatsuba or CRT cannot beat direct-sum additivity under the register's multiplicative cost model - MF-028A twelve-wedge prefix obstruction for the period-two carry law in p14 circuitsEXHAUSTIVE CHECKPublished 2026-08-29
Fixing gates 0–11 of a p14 circuit to 12 input-only quadratic wedge generators cannot realize the 26-input Cartesian period-two carry law - MF-032Copy-locality of target-bearing products at the rank-tight boundary over GF(2)EXHAUSTIVE CHECKPublished 2026-08-29
For affine combinations L and R of separated signals, if L*R is separated and target-bearing, then L*R is copy-local - MF-035A conjectured rank-two bilinear custom gate for the p14 bridgeOPEN QUESTIONPublished 2026-08-29
MF-035 is a conjecture. - MF-037A wedge-span obstruction for the exact Cartesian period-two carry lawEXHAUSTIVE CHECKPublished 2026-08-29
dim(T ∩ W)=4, dim(T/(T ∩ W))=6; every p14 realization requires ≥6 gate functions outside W, ruling out k≥9 gate functions in W Conditional on a verifier-legal p14 fusion, C(2r) ≤ 2 C(r) - Delta_r- MF-039A conjectural lower bound for the multiplicative complexity of T2OPEN QUESTIONPublished 2026-08-29
MC(T2) ≥ 15 - MF-044Exact scans of published p8 factors for three maximal mixed p14 skeletonsNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Zero 14-target spans across 1,920, 1,920, and 38,400 direct-fusion assignments over GF(2) on (7,15), (7,23), and (7,39) skeletons - MF-045The kernel of the Boolean product-residue map on separable signal cutsEXHAUSTIVE CHECKPublished 2026-08-29
ker(μ) = ker(μ_0) ⊕ ker(μ_1) - MF-047A lower bound on chained products for the period-two p14 targetEXHAUSTIVE CHECKPublished 2026-08-29
rank(T) = 10, rank(T≤2) = 4, dim(T ∩ W) = 4 ⇒ every p14 construction requires ≥ 6 chained or non-input-only product functions - MF-069A strict flag characterization of rank-tight acyclic full-domain XAGsRECEIPTEDPublished 2026-08-29
dim W = r admits acyclic full-domain XAG with r AND gates iff ∃ 0 = U0 < ... < Ur = W: Ui / U_{i-1} contains class of Li Ri, Li, Ri in A + U_{i-1} - MF-070Impossibility of p7 realizations for rank-tight q-rank-7 edges under G = WEXHAUSTIVE CHECKPublished 2026-08-29
In the rank-tight model G = W, every e ∈ E₇ is p7-impossible - MF-071A multiplicative complexity lower bound for 28 q-rank-6 edgesNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Every edge in E₆ is p6-impossible - MF-072Impossibility of rank-tight p5 realizations for q-rank-5 edgesNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
In the rank-tight model G = W, every e ∈ E₅ is p5-impossible For a p-gate acyclic XAG with W ⊆ G, dim G = p, dim W = r: catalyst dimension = p − dim W = p − r- MF-074A counterexample to the laminar multiplication-tree normal formNEGATIVE RESULTRECEIPTEDPublished 2026-08-29
Laminar multiplication-tree normal form does not hold on n=6: p4 circuit has q-rank 4, unrestricted [1,2,1,1,1] vs laminar [1,2,1,1,0] dim(residual separated target quotient) = r with r new product gates ⟹ every independent target-bearing gate is copy-local- MF-097Decomposability of the extremal top form in acyclic XOR–AND circuitsCERTIFIED PROOFPublished 2026-08-29
If C is an acyclic XOR–AND circuit with r AND gates and f is an output of degree r+1, then top_{r+1}(f) is decomposablePrior art: This result makes no separate prior-art claim.
p14 existence is LIVE/UNKNOWN; 817 named copy-swap cells survive; −477 rows requires p14 and rank(I+A)=3Exact exclusion is Γ_{m, 2m-3} = ∅; local-response theorem proved, but summation across sites and SBD remain unproved (OPEN).Full-carry sector injection into product-state space fails at J_2: degree-4 indicators not in two-gate span; general floor is refuted.- MF-123Necessary carrier sequence and connected-leakage bounds for hypothetical p14EXHAUSTIVE CHECKPublished 2026-09-04
0→H_6→E_10→C_4→0; rank Q_2(fg) ≤ 2r+2s+rs+2; first mixed catalyst connected rank ≤ 2 596 named p14 cells proved dead (327 s=0, 269 s=1); 68 s=1 timed out and 153 multi-catalyst remain, leaving 221 named surviving cellsPrior art: This result supersedes the 817-cell snapshot from MF-105; the general p14 SAT/UNSAT problem remains open.
- MF-133Finite classification of the primary-affine pairing-one localization componentRECEIPTEDPublished 2026-09-04
Primary-affine pairing-one kernel has 8 points (full kernel 15); reduced lex Gröbner basis has 69 polynomials; 5/3 with zero affine tail. - MF-178Domination of tensor slice rank floors for systems of quadratic formsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
srank(T) ≤ m for m-form tensors T, so ⌈srank(T)/3⌉ ≤ m ≤ MF-137 lower bound for all non-affine targets over F_2^n. - ML-007Multiplicative complexity of Pascal and averaging-algebra state-feature classesNEGATIVE RESULTRECEIPTEDPublished 2026-08-29
Exhaustive search across 2,097,152 Pascal / averaging-algebra state-feature classes yields 7 survivors at mixed-tensor-rank ≤2. - ML-043Closure of all 68 p7-eligible directed edges under the rank-tight affine-code modelEXHAUSTIVE CHECKPublished 2026-08-29
Zero-catalyst rank-tight affine-code model: 68 p7-eligible edges are closed: 32 rank-tight p7-dead, 28 p6-dead, 8 rank-tight p5-dead Functional direct-sum additivity for M₂ over GF(2) in unrestricted sequential Boolean XAGs is OPENPrior art: Alder-Strassen and Strassen establish 7s only within the bilinear and formal-quadratic models.
- ML-075The Mirwald–Schnorr 3-form transfer gap and n = 6 enumeration barrierOPEN QUESTIONPublished 2026-09-04
MC(W) = qMC(W) for dim W = 3 is proved only for n ≤ 5; closing it at n = 6 is an open bottleneck for packing filtration bounds at j ≥ 2 - ML-086Ineffectiveness of 3-tensor slice rank for multiplicative complexity boundsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
srank(T) ≤ m implies MC ≥ ⌈srank(T)/3⌉ ≤ ⌈m/3⌉ < m, which fails to improve upon the trivial linear dimension floor mPrior art: This result builds on tensor slice rank and partition rank techniques introduced by Tao (2016) and Naslund (2020).
- ML-088Search scale barrier for unrestricted 6-AND XAG decision of M_2(F_2)OPEN QUESTIONPublished 2026-09-04
Deciding 6-AND unrestricted XAG for M_2(F_2) requires refuting a CNF with 155,669 clauses and 33,345 variables; open at k=6.
The quadratic hull and its defects
Analysis of algebraic hull lifts, state-only coordinates, and proved limits on static preprocessing for SAT clauses.
- MF-031An impossibility theorem for deterministic state-only lifts of the c0c2 quadratic hullEXHAUSTIVE CHECKPublished 2026-08-29
No deterministic state-only feature set can repair the relation, as maximal lift replay retains 23,808 of 24,576 old wrong hull points - MF-090Exact quadratic cover number of an OR-chain lift of a width-k clause over F2PAPER PROOFPublished 2026-08-29
For the lifted relation of a positive width-k clause (k ≥ 3), κ2,cover = k − 1Prior art: This result uses well-established, classical techniques, and no claim of novelty is made without a targeted literature search for this encoding theorem.
- MF-144The packing filtration lower bound and master identity for multiplicative complexityRECEIPTEDPublished 2026-09-04
MC(F) = dim V + max_j (m_{j+1}(V) - j - 1) and MC(F) ≥ dim V' - j + m_{j+1}(V') - 1 for all V' ≤ VPrior art: The gate-span and rank arguments are credited to Schnorr (1989), Boyar–Peralta–Pochuev (2000), and Boyar–Find (2018).
- MF-145Packing floors on quadratic multiplicative complexity for linear spaces of quadraticsRECEIPTEDPublished 2026-09-04
qMC(W) ≥ ceil(sum_{w ≠ 0} mc(w) / 2^{d-1}) for d-dim space W; d=2 yields qMC(W) ≥ ceil((mc(q1)+mc(q2)+mc(q3))/2)Prior art: This is a partial result.
MC(F) ≥ dim V - 2 + ⌈3μ/2⌉ for all-quadratic V with every nonzero class of cost μPrior art: PARTIAL (composite of MF-144/MF-145).
- MF-151Exact characterization of additive quadruples destroyed by one AND gateRECEIPTEDPublished 2026-09-04
Quadruple survives e=uv iff {P(x1),P(x2),P(x3),P(x4)} ≠ GF(2)^2 for P=(u,v); uniform rainbow density killed is 24/64 = 3/8Prior art: The Fourier identity (-1)^{uv} = (1 + (-1)^u + (-1)^v - (-1)^{u+v})/2 is standard, but the additive-quadruple reformulation was not found in prior literature and appears to be new.
- MF-165Equality of multiplicative and quadratic complexity for 3-spaces on at most 5 variablesEXHAUSTIVE CHECKPublished 2026-09-04
MC(W) = qMC(W) for all 3-dimensional spaces W <= Quad(n) with n <= 5 in the general XAG model.Prior art: The result for dim W <= 2 is known from Mirwald–Schnorr (1992), while Boyar–Find record dim >= 3 as open.
- ML-052On the static quadratic hull as a general SAT preprocessorNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
If |F| < 2^(n-d), then I_≤d(R) = {0} and H_d(R) = F₂^nPrior art: The Reed-Muller minimum-distance property used here is a standard, classical mathematical result, and no novelty is claimed for this component.
- MF-009Quadratic hull closure of the Z-counter transition relationEXHAUSTIVE CHECKPublished 2026-08-29
|H₂(R_∂) ∩ W_same| = 24; exactly three canonical quadratic rows A·B=C are necessary and sufficient For affine forms ℓ_1,...,ℓ_m: 𝔽₂³ → 𝔽₂ and P = ∏_{j=1}^m ℓ_j, |Z(P)| ∈ {0,4,6,7,8}delta2^flip ≤ delta2^vert- MF-024Rank-one-target deficiency of stationary full covers on GF(2)⁵CERTIFIED PROOFPublished 2026-08-29
The condition of using all ten spare codewords holds if and only if delta ∈ {4, 20} - MF-025The false path 8 -> 0 -> 0 in the natural five-code Ghost-P5 quadratic hullCERTIFIED PROOFPublished 2026-08-29
No subset of H achieves soundness via repetition alone (two-column sequential composition admits exact false path 8 -> 0 -> 0) - MF-033A structural characterization of the c0c2 quadratic defectEXHAUSTIVE CHECKPublished 2026-08-29
On every one of the 8,192 public-input fibres, the nonzero in-hull output flips are `e1`, `u(x)`, and `e1+u(x)`, where `e1=32` flips `next_c1` and `u(x)=16 XOR next_c2(x)*128`. - MF-036A census of one-block affine data-split pins for c0c2 hull repairNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
The corrected census spans all 8,184 pointwise-distinct cases. - MF-049Linear fresh-defect growth in the strongest natural five-code relaxed SHA relationEXHAUSTIVE CHECKPublished 2026-08-29
For k=1..6, missing-C quotient ranks are k, raw state-flip ranks are 5k, interface ranks are 2k+3, and terminal repair tax cannot be o(1) - MF-052Closure of the ordered acyclic A*B=C catalyst class at p6NEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Ordered acyclic A*B=C catalyst class at p6 = ∅ (1,005 exact-UNSAT, 7,035 rank-dead across 67 deterministic state-feature subspaces) - MF-065Exact number of quadratic equations for a unique common zero in GF(2)^32PAPER PROOFPublished 2026-08-29
Forcing g₀=...=g₃₁=0 over GF(2) with degree ≤ 2 equations without auxiliary variables requires and is satisfied by exactly 16 equationsPrior art: The lower bound is based on the classical Chevalley-Warning theorem, and no separate prior-art position is claimed.
h₂=false-loop count, ρ₂=false-syndrome rank, δ_2,pin=nullity after deleting loops, κ_2,cover=Crapo–Rota critical exponentPrior art: Most concepts and terms used here follow established literature; only delta2^vert and delta2^flip represent original formulations introduced in this work.
For R_r = Graph(w = x₁...x_r) and a_r = (1^r, 0), σ_{R_r}(a_r) = r, and a_r ∈ H_d(R_r) if and only if d < rPrior art: This result generalizes MF-012; no external prior-art comparison is stated.
- MF-089The degree-(d) hull of Boolean relations with few forbidden pointsPAPER PROOFPublished 2026-08-29
If R ⊆ 𝔽_2^n, F = 𝔽_2^n \ R, 0 ≤ d ≤ n, and |F| < 2^{n-d}, then I_{≤d}(R) = {0} and H_d(R) = 𝔽_2^nPrior art: This step relies on standard minimum-distance properties of classical Reed-Muller codes; no original contribution or novelty is claimed.
- MF-132The Boolean ramification polytope common evaluation conjectureOPEN QUESTIONPublished 2026-09-04
MC(F) ≥ r+D-2-c(Q) survives, but unqualified polytope equality is undefined at V=0 and remains a CONJECTURE (GAP) - ML-016Wrong Fixed Points in Rank 5/5 Deterministic Quadratic-Atlas ChartsNEGATIVE RESULTRECEIPTEDPublished 2026-08-29
Two deterministic Quadratic-Atlas charts attain rank 5/5 with 14 and 21 wrong fixed points; all others terminate at rank ≤4 or qdim 6 - ML-022Unsoundness of the fixed Ghost-P5 ITER19 allocation and K0 trellis adapterOPEN QUESTIONPublished 2026-08-29
Ghost-P5 (18,801, ITER19): deg-2 hull spans 17-bit space, δvert=66, δflip=2; exact K0 adapter unsound on all 131,072 replayed assignments - ML-024On the quadratic hull of carry relations under state-only catalyst liftsNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Deterministic state-only lifts fail at every row budget: 8,040 acyclic-p6 models eliminated, 8,184 anchors yield no hull repairs - ML-028Quadratic hull closure for the canonical Z-difference counter interfaceNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
For the canonical Z-difference counter interface A*B=C, retaining garbage coordinate g0 or g1 closes the quadratic hull. - ML-034Elimination of stationary additive carry/raw phases with terminal syndrome-only checksNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
491,040 candidates across 245,520 classes yield rank 74 with 40 independent directions; span indicator(c=s)*{1,u0,...,u9} is 88-dimensional
What rank-one constraints can express
Rank-one constraint system geometry, witness-width classifications, and impossibility proofs for helper-free zero-knowledge gadgets.
- MF-059Complete witness-width classification of Boolean functions on F₂⁴EXHAUSTIVE CHECKPublished 2026-08-29
Every Boolean function `f: F₂⁴ → F₂` has a well-defined minimum witness width `ω(f)` in the finite arbitrary-affine-C rank-one model with an affine decoder and arbitrary nonempty f - MF-091A minimal three-row quadratic constraint system for the inverse-or-default gadgetPAPER PROOFPublished 2026-08-29
xy=1-z, xz=0, z(y-d)=0 uniquely defines z=[x=0], y=x⁻¹ (x≠0), y=d (x=0); 3 rows is minimal without auxiliary allocations over |F| ≥ 5 - MF-158Classification of relations implemented by single-row R1CS over F_pEXHAUSTIVE CHECKPublished 2026-09-04
A single row A·B = C over F_p with m witnesses implements one of 4 types: F^n, {q=0}, {L≠0}∪({L=0}∩{q=0}), or {x : Δ(x) is a square}.Prior art: This appears to be a new, partial result applying elementary algebraic geometry to a single quadratic equation.
- MF-160Exact R1CS Row Counts and Allocation-Independent Lower Bounds for Basic GadgetsRECEIPTEDPublished 2026-09-04
R1CS row counts: IsZero = 2, AND_n = OR_n = 2 for all n ≥ 3, XOR4 = 2 over F_p (p ≥ 7), with no 1-row systems possible.Prior art: This result is partial: the gadgets rely on standard implementations from circomlib, but no proofs were found showing that these R1CS row counts are optimal.
- MF-162Witness power, degree collapse, and allocation walls over large prime fieldsRECEIPTEDPublished 2026-09-04
{x : x != 0} needs 1 witness, XOR3/MAJ3 degree collapse breaks MF-013 over F_p, and primitive walls hold against arbitrary allocationsPrior art: PARTIAL / INTERNAL.
- ML-050Impossibility of helper-free IsZero over finite fields with |F| ≥ 4NEGATIVE RESULTPAPER PROOFPublished 2026-08-29
For |F| ≥ 4, no family of degree-at-most-two equations in (x,z) has solution relation Γ₀ = {(0,1)} ∪ {(x,0) : x ∈ F*} - MF-012An impossibility theorem for pinning the three-input AND under quadratic systemsEXHAUSTIVE CHECKPublished 2026-08-29
No quadratic system in (x1,x2,x3,w) can pin w=1 at x=(1,1,1) for R=Graph(w=x1x2x3)={(x1,x2,x3,w)∈F2^4:w=x1x2x3} - MF-051Impossibility of realizing AND4 with three witnesses and three product rowsCERTIFIED PROOFPublished 2026-08-29
The finite search space for an identity-C, affine-decoder, nonempty-even-fibre realization of AND4 with four public inputs, three witnesses, and three rank-one product rows contain In the affine-factor, affine-decoder, arbitrary-nonempty-fibre model with arbitrary affine-C: 1.- MF-060An impossibility theorem for the normalized two-witness selector for AND₄EXHAUSTIVE CHECKPublished 2026-08-29
Every normalized 2-witness selector separates 30 wrong witnesses over x ≠ 1111, and no selector separates both wrong witnesses over x = 1111 - MF-061Classification of the identity-C fixed-point consumer on toy Boolean graphsEXHAUSTIVE CHECKPublished 2026-08-29
1*(D⊕r)=r forces D=0; with m multiplication pins, affine parity compiles in m+1 rows (AND3 in 3 rows, AND4 in 4 rows) For a forest with N vertices and E edges over GF(2), gauge space dimension = apparent vertex-row savings = created gauges = N-En-bit range check takes n rows (lower n exact for n <= 2); u32 add takes [32,33] rows with carry-booleanity fusion ruled out by conic countsPrior art: This result is partial: the constructions follow standard practice, but the corresponding lower bounds have not yet been located.
- ML-020An impossibility result for two-witness AND4 in the affine-C modelEXHAUSTIVE CHECKPublished 2026-08-29
In the affine-C model, the two-witness AND4 route is unsatisfiable for every finite row count r. - ML-029Exact-UNSAT of Phase B in the natural P10 missing-plane modelNEGATIVE RESULTSOLVER-CONFIRMEDPublished 2026-08-29
Phase B is exact-UNSAT in the natural 30-coordinate P10 model; product image rank 423, quotient rank 393, rejection family empty - ML-041An impossibility result for affine third factors of the named JSC-12 witnessRECEIPTEDPublished 2026-08-29
For JSC-12 with q = current1 * middle2, no affine M makes qM vanish on honest {q=1} while rejecting the false point on K10, K11, K1x, all-K
Symmetry, state encodings and search gauges
Quantifying the exact gate penalty of syntactic symmetry, affine state relabeling, and XOR-mask transports.
- MF-092Exact nonlinear cost of an eight-state controller under affine relabelingEXHAUSTIVE CHECKPublished 2026-08-29
Affine maps over F₂ preserve XOR–AND count/depth: 40,320 3-bit encodings form 30 orbits with exact minimum ANDs: 1×2, 4×3, 15×4, 10×5 - MF-113Shortest-path and LP-dual formulation of multiplicative complexity via semantic gate statesCERTIFIED PROOFPublished 2026-09-04
MC equals shortest-path distance on the complete semantic gate-state graph; its LP dual is the 1-Lipschitz potential problem - MF-004Functional census and degree bounds for the two-row cyclic modelEXHAUSTIVE CHECKPublished 2026-08-29
|S₂| = 575,968, |{Φ(S) : S ∈ S₂}| = 32,768, and ∀S ∈ S₂, deg(Φ(S)) ≤ 3 - MF-008Affine equivalence classes of minimum-rank eight carry-state encodingsEXHAUSTIVE CHECKPublished 2026-08-29
{e ∈ E : e passes minimum-rank filter} / affine equivalence = {natural, orbit29 = [0,1,2,3,4,7,6,5]} Sparse exact CEGIS with 120× row-order symmetry reduction solved a 69,862-variable instance in 12 rounds (26 s); monolithic timed out- MF-018A soundness condition for subset-UNSAT certificates under symmetry breakingRECEIPTEDPublished 2026-08-29
A subset-UNSAT certificate is sound only when ∀g ∈ G, g(R) = R Sorting u, v, and u+v spanning an independent two-plane in S/<1> yields the exact GL(2,2) symmetry quotient for catalyst parameterization- MF-050Exact finite-horizon minimisation of natural SHA carry statesEXHAUSTIVE CHECKPublished 2026-08-29
For the 22 natural SHA carry states, exact finite-horizon minimisation produces the identical partition across all 64 round constants: 22 classes through bit 29, 16 at bit 30, four - MF-175Degree distribution of the two-column C7 transducer nonlinear quotientRECEIPTEDPublished 2026-09-04
For the two-column C7 transducer with dim V = 4, exactly 12 nonzero cosets in V have degree ≥ 3 and 3 cosets are quadratic. - ML-033Finite-horizon Nerode minimisation of the 22-state carry transducerNEGATIVE RESULTEXHAUSTIVE CHECKPublished 2026-08-29
Under finite-horizon Nerode minimisation, the natural 22-state carry transducer maintains 22 classes through bit 29, followed by 16, four, and one terminal class. - ML-055Exact gate-state duality and 1-Lipschitz potential bounds for multiplicative complexityCERTIFIED PROOFPublished 2026-09-04
Gate-state shortest path equals MC with LP dual as 1-Lipschitz potential; quotient certificates require complete edge sets. - ML-079Open Status of the NIST 21-vs-22 Question for Degree-22 Symmetric FunctionsOPEN QUESTIONPublished 2026-09-04
NIST 21-vs-22 question for deg-22 symmetric functions remains open; t = 5 two-phase route yields 22, while t = 6, 7 remain open.
Formal verification and machine-checked proof
Machine-checkable DRAT certificates and LP dual solvers ruling out circuit sizes below verified minimal bounds.
- MF-006Simultaneous and cyclic witness definitions in the Lean 4.28 kernelLEAN-VERIFIEDPublished 2026-08-29
Lean 4.28 accepts simultaneous and cyclic witness definitions with soundness, completeness, exact cost, computable witnesses, no sorryAx - MF-016Formal verification of large cryptographic circuits via cone-local proofsRECEIPTEDPublished 2026-08-29
Per-cone proofs composed via existing semantic theorems compile no-sorry in seconds to minutes when monolithic `bv_decide` is intractable Subset construction gives exact completeness/soundness checks for finite phase relations; natural sample & ITER19 K0 adapter fail soundness- MF-093Formal verification of end-to-end output equality for XAGs in LeanLEAN-VERIFIEDPublished 2026-08-29
Lean 4.28 proves equivalence between a 30,003-gate reference hierarchy and a 20,002-gate optimized hierarchy using zero axioms
Exact answers in open problems
Exact values and certified bounds on open cells in other fields: the minimal Kochen-Specker set in dimension six, Ramsey and Zarankiewicz numbers, median networks, constant-weight codes, circulant weighing matrices and universal tournaments.
- MF-184Non-existence of 18-vector Kochen-Specker sets in dimension 6CERTIFIED PROOFPublished 2026-09-06
No KS set in C^6 has 18 vectors, hence m_6 >= 19 and m_6 in [19, 21]Prior art: This result improves the universal lower bound m_d >= 18 from Xu-Chen-Guehne (2020) in dimension 6. Sources: Xu, Chen, Guehne 2020 (PRL 124, 230401) · Lisonek, Badziag, Portillo, Cabello 2014 (PRA 89, 042101)
n=7 median network exact size is 13 (UNSAT at 12 DRAT-verified); 6-channel lower-median exact size is 10 (UNSAT at 9 DRAT-verified).Prior art: Dobbelaere’s table lists 13 for n = 7 (unproven) and marks n = 9 as optimal (Smith 1996); Knuth TAOCP 5.3.4 remains unverified. Sources: Dobbelaere, median networks table
- MF-190Exact B2 circuit size and machine-checkable certificate for 5-input MOD3,1RECEIPTEDPublished 2026-09-06
size_B2(MOD3,1 on 5 inputs) = 9Prior art: Knuth (TAOCP 7.1.2, exercise 480) determined the values for n ≤ 5 using SAT solving without publishing certificates. Sources: Knuth, TAOCP vol. 4A, section 7.1.2 · Kulikov, Pechenev, Slezkin 2022 (MFCS) · Kojevnikov, Kulikov, Yaroslavtsev 2009
- MF-195Nonexistence of 19-vector Kochen-Specker sets in C^6 and the lower bound m_6 ≥ 20RECEIPTEDPublished 2026-09-06
No KS set in C^6 has 19 vectors, hence m_6 >= 20 and m_6 ∈ {20, 21} (conditional on cited lemma as in MF-184)Prior art: Searches across existing literature found no prior work excluding 19 in d = 6, though the novelty of this result remains unverified. Sources: Xu, Chen, Guehne 2020 · Lisonek, Badziag, Portillo, Cabello 2014
- MF-199Nonexistence of 20-vector Kochen-Specker sets in C^6 and minimality of m_6 = 21RECEIPTEDPublished 2026-09-06
No Kochen-Specker set in C^6 has 20 vectors; hence m_6 = 21 exactly, conditional on the Xu-Chen-Gühne lemma.Prior art: While prior work established 18 <= m_d for all d (XCG 2020) and m_6 <= 21 (LBPC 2014, "simplest KS set admitting a symmetric parity proof"), m_6 remained in [18, 21]. Sources: Xu, Chen, Guehne 2020 (PRL 124, 230401) · Lisonek, Badziag, Portillo, Cabello 2014 (PRA 89, 042101)
- MF-185Two necessary conditions on Kochen-Specker orthogonality graphsEXHAUSTIVE CHECKPublished 2026-09-06
For basis K in C^d: deg_K(v) ≤ d-2 for v ∉ K; and v ∦ w (v, w ∉ K) implies ∃u ∈ K with u ∦ v and u ∦ w.Prior art: This result was not found in the existing d = 3 SAT literature, which typically relies on C4-free or cross-product closure methods; its novelty remains unverified. Sources: Xu, Chen, Guehne 2020
- MF-186Maximum row degree bound for 16×17 Zarankiewicz extremal matricesRECEIPTEDPublished 2026-09-06
If A ∈ {0,1}^{16×17} has 133 ones and no 3×3 all-ones submatrix, then max row degree of A is ≤ 10Prior art: Two papers from August 2026 left the exact value of z(16,17;3) in {132, 133} unresolved. Sources: Afrasyab 2026 · Hou 2026
δ(G) ≥ 4 for every (J4,J8;30)-graph and δ(G) ≥ 5 for every (J4,J8;31)-graphPrior art: Wesley (arXiv:2606.17021) identifies R(J4,J8) in [30,32] as the next open case, building on the gluing framework from Goedgebeur-Van Overberghe (arXiv:2107.04460). Sources: Radziszowski, Small Ramsey Numbers (dynamic survey)
- MF-188Uniqueness of (J4,J7;26)-graphs with minimum degree at least 9NEGATIVE RESULTRECEIPTEDPublished 2026-09-06
(J4,J7;26)-graphs with δ >= 9 form a single isomorphism class: Schläfli complement minus one vertex (degrees 9^10 10^16, 125 edges)Prior art: MR91 proved uniqueness at order 27, but whether the 26-vertex statement appears in that paper remains unverified. Sources: Goedgebeur, Van Overberghe 2021
A(11,4,5) = 66Prior art: This machine-checkable certificate builds on Brouwer's table (Johnson bound from A(10,4,5) = 36, Ostergard 2010). Sources: Ostergard 2010, classification of binary constant weight codes
No 9-host for TT_6 and 12 6-tournaments; no 11-host for TT_7, QR_7, and 7 rare 7-tournaments (DRAT verified)Prior art: Zhang and Szeider (CP 2023) stated a lower bound of 11 and resolved the case n = 11 using four separate SAT instances. Sources: Zhang, Szeider 2023 (CP 2023)
- MF-193Contraction censuses and lifting obstructions for CW(112,36)NEGATIVE RESULTRECEIPTEDPublished 2026-09-06
CW(112,36) contractions: m=7 has 21 (2 orbits), m=8 has 96 (6), m=14 has 126 (3), m=16 has 1152 (24), m=28 has 420 vectors (4 orbits).Prior art: The orbit count 2 for m = 7 was previously reported in Arasu-Gordon-Zhang (2021, Table 9) under a multiplier assumption. Sources: Arasu, Gordon, Zhang 2021 (Cryptogr. Commun.) · Tan 2026 · Gordon, circulant weighing matrices table
ex(n) ≤ ⌊n·ex(n-1)/(n-3)⌋ for ex(n, K_4^(3)); given ex(13) = 174, ex(14) ≤ 221 leaving a gap of at most one triplePrior art: This result applies the standard Katona-Nemetz-Simonovits monotonicity argument to exact values. Sources: Katona, Nemetz, Simonovits 1964 · Turan 1941
For CW(n=2^e q, k) with q odd, e ≥ 1, k even: support S in F_2[Z_n] satisfies (x+1)^(2^(e-1)) | S, so S mod (x^(2^(e-1)) - 1) = 0Prior art: Prior work by Arasu, Leung, Ma, and Schmidt contains parity and 2-adic results for CW(2^e q, k). Sources: Arasu, Gordon, Zhang 2021 · Gordon, circulant weighing matrices table
t(7) > 12; no 12-vertex tournament is 7-universal (all 14 amalgam cubes UNSAT, drat-trim VERIFIED)Prior art: This value matches Zhang-Szeider (CP 2023), though the novelty of the amalgam-cube method and pattern-side symmetry breaking remains unverified against that paper, the Dec-2025 SMS survey, and the CP 2026 cubing paper. Sources: Zhang, Szeider 2023 (CP 2023)
- MF-198Automorphism group structure of 7-universal tournaments on 13 verticesRECEIPTEDPublished 2026-09-06
For every 7-universal tournament T on 13 vertices, |Aut(T)| ∈ {1, 3}Prior art: The novelty of this result has not been independently verified. Sources: Zhang, Szeider 2023 (CP 2023)
- ML-090Search wall for the smallest 7-universal tournament at order 13OPEN QUESTIONPublished 2026-09-06
13 ≤ t(7) ≤ 15; n = 13 undecided under SAT and lazy pattern-core CEGAR which exceeds 1800 s timeout at 32 enforced patternsPrior art: The bounds 13 <= t(7) <= 15 were established by Zhang and Szeider (CP 2023). Sources: Zhang, Szeider 2023 (CP 2023)
- ML-091Partial degree-cube search wall for Zarankiewicz number z(16,17;3)OPEN QUESTIONPublished 2026-09-06
z(16,17;3) ∈ {132, 133} undecided; d = 17..11 refuted with DRAT, 8 of 46 row-2 sub-cubes at d ∈ {9, 10} undecided at 7200 sSources: Afrasyab 2026 · Hou 2026
Optimal median network size undecided for n ≥ 8; SAT solver times out on n=8 at 15, n=9 at 18, n=10 at 21, and n=11 at 24 comparatorsPrior art: A verification check was unable to reproduce the published n = 9 optimality claim from Smith (1996). Sources: Dobbelaere, median networks table
- ML-093Proof-system mismatch for the circulant weighing matrix cell CW(112,36)NEGATIVE RESULTRECEIPTEDPublished 2026-09-06
DRAT resolution and RoundingSat cutting planes fail on CW(112,36) and known-nonexistent CW(n,36) for n ∈ {40, 44, 50, 56}.Sources: Arasu, Gordon, Zhang 2021 · Tan 2026
- ML-094Exact B2 circuit size of MOD3 on 6 inputs and solver scaling wallOPEN QUESTIONPublished 2026-09-06
C_B2(MOD3,0 on 6 inputs) conjectured 12; deciding 11 gates timed out at 5400 s with UNSAT cost growing 30-100x per gatePrior art: Knuth's conjecture predicts a circuit size of 12 for MOD3,0 on 6 inputs. Sources: Kulikov, Pechenev, Slezkin 2022 (MFCS)
- ML-095Open status and catalogue corrections for resolution hardness h_11OPEN QUESTIONPublished 2026-09-06
h_11 ≥ 28 remains undetermined; reproduced h_8 = 19, h_9 = 22; candidate census corrected to 626,973 with missing RSMU(8,10) identifiedPrior art: Prior work by Peitl-Szeider established the values of h_m for m ≤ 10 (including h_10 = 26) and proved that h_11 ≥ 28. Sources: Peitl, Szeider 2021 (JAIR) · Peitl, Szeider, short-proof code
- ML-096Bounds and search limits on the constant-weight code size A(13,4,5)OPEN QUESTIONPublished 2026-09-06
A(13,4,5) ∈ [123, 129] - ML-097Limits of plain CDCL with cardinality totalizers for Turán numbers ex(n, K_4^(3))NEGATIVE RESULTRECEIPTEDPublished 2026-09-06
ex(14, K_4^(3)) is undecided; CDCL with totalizers hits an empirical wall above n = 9, while degree-sequence cubing refutes cubes at n = 10Sources: Turan 1941
- ML-098Failure of SMS standalone LRAT certificate verification for Kochen-Specker n = 18NEGATIVE RESULTCERTIFIED PROOFPublished 2026-09-06
Standalone lrat-check of smsg -v 18 --lrat-output fails due to unintegrated --sym-break-clauses outside the LRAT chain. - ML-099Exclusion of 19- and 20-vector Kochen-Specker sets in C^6NEGATIVE RESULTRECEIPTEDPublished 2026-09-06
No 19- or 20-vector Kochen-Specker set exists in C^6 (both excluded via MF-195, MF-199)Sources: Xu, Chen, Guehne 2020 · Lisonek, Badziag, Portillo, Cabello 2014
Further results
Subspace packing lemmas, additive energy bounds, and exact gate counts for polynomial multipliers and carry transducers.
MC(F) ≥ dim(V) + μ(V) - 1, where V is nonlinear output span mod affine and μ(V) is min gate cost of any nonzero scalar class in V- MF-106The 37-wall atlas of failed proof routes and scope limitsNEGATIVE RESULTRECEIPTEDPublished 2026-08-29
W01–W37: MODEL, TECHNIQUE, SCOPE, and EVIDENCE walls with receipts R1–R46 - MF-143Refutation of three proposed multiplicative complexity lawsNEGATIVE RESULTRECEIPTEDPublished 2026-09-04
MC(11 x mod 128) = 6 ≠ 5, kappa_sq(7) ∈ {2,3} ≠ 1, and MC(I_9) = 6 ≠ 5, refuting three conjectured complexity laws. - MF-153Solver-Free Multiplicative Complexity Lower Bounds from Degree and Walsh FloorsRECEIPTEDPublished 2026-09-04
MC(3×3) ≥ 6, MC(4×4) ≥ 9, MC(clmul_4) ≥ 8, MC(clmul_5) ≥ 11, MC(Add(4,5)) ≥ 8 via degree and Walsh floor methodsPrior art: These bounds are previously established: the degree floor is credited to Schnorr, and the Walsh floor is documented under entry MF-135.
Papers are generated from the division's registers and curation records, then edited for style. Each paper carries its publication date, the date it was last reviewed, and a changelog of every amendment to the claim. Snapshot 2026-09-06.