Research · Papers · Adders, counters and the heap law · MF-169
Exact multiplicative complexity of 7-variable majority
MC(MAJ7) = MC(T^7_4) = 4
Published 2026-09-04
For everyone
Plain summary
The seven-variable majority function takes seven binary inputs and returns 1 when four or more inputs are 1. Multiplicative complexity measures the minimum number of nonlinear AND gates needed to build a circuit when linear XOR and NOT gates are free.
Boyar and Peralta (2008) showed that seven-variable majority requires either 3 or 4 AND gates. This result closes the bracket: the exact complexity is 4. An explicit bit-heap counter computes the function in 4 AND gates, and an exhaustive computer search proves that no 3-AND circuit exists. Novelty is not claimed; the exact value may already exist in the unexamined NIST Circuits data set.
Result
MC(MAJ7) = MC(T^7_4) = 4
The multiplicative complexity of the 7-variable Boolean majority function MAJ7 (equivalently the threshold function T^7_4) over the basis (AND, XOR, NOT) in GF(2) is exactly 4.
Setting and definitions
Let GF(2) denote the two-element finite field. Let f: GF(2)^n → GF(2) be a Boolean function.
- Multiplicative complexity MC(f): minimum number of AND gates needed to compute f in a straight-line program over GF(2) using (AND, XOR, NOT), with XOR and NOT gates treated as free.
- Threshold function T^n_k: symmetric Boolean function on n variables defined by T^n_k(x) = 1 if and only if Hamming weight hw(x) ≥ k. Here MAJ7 = T^7_4.
- Hamming weight vector: for x ∈ GF(2)^7, the integer sum of inputs represented as a 3-bit binary vector (w_2, w_1, w_0), where w_2 corresponds to hw(x) ≥ 4.
- Invertible affine substitution: transformation x ↦ A x + b with A invertible over GF(2), preserving multiplicative complexity.
- S_6-symmetry reduction: partition of the first-gate search space into orbit representatives under S_6 permutations of the remaining 6 variables.
Method
- Upper bound (MC(MAJ7) ≤ 4):
MAJ7 equals w_2, the most significant bit of (w_2, w_1, w_0). A bit-heap counter computes the full weight vector in 7 - hw(7) = 7 - 3 = 4 AND gates. The circuit was verified across all 128 input assignments in GF(2)^7 (128/128).
- Structural reduction:
MAJ7 satisfies the identity: MAJ7(x_1, …, x_7) = x_7 ⊕ T^6_4(x_1 + x_7, …, x_6 + x_7) This invertible affine map was verified on all 128 inputs (128/128). Because affine equivalence preserves multiplicative complexity, MC(MAJ7) = MC(T^6_4).
- Lower bound refutation (MC(T^6_4) > 3):
The decision problem MC(T^6_4) ≤ 3 was encoded into SAT and solved with solver.py. S_6-symmetry reduction yielded 59 first-gate orbit representatives. The solver refuted all 59 instances (UNSAT) in 1,115 seconds with per-representative checkpoints.
The verified 4-AND circuit and the exhaustive refutation establish Evidence Tier P.
Discussion
This entry closes the [3, 4] multiplicative complexity bracket for 7-variable majority. Boyar–Peralta (2008) established MC(MAJ7) ≤ 4 in Theorem 10 and MC(MAJ7) ≥ 3 in Theorem 8 via the Schnorr degree bound.
Novelty is not claimed. The exact count may already reside in the NIST Circuits data set for symmetric functions up to 25 variables, which was not searched. The register records the result as exact based on local verification receipts under the AGL(n.
The result applies strictly to the single-output majority function over GF(2) with free linear operations.
For everyone — the takeaway
What this means
Deciding whether at least four out of seven bits are true requires four nonlinear AND steps when XOR additions are free. Boyar and Peralta showed that either three or four multiplications were needed; this refutation proves three are never enough. An algebraic substitution reduces the seven-input problem to a six-input threshold function, which automated SAT solvers check across all 59 symmetry classes in under twenty minutes.
Attribution and prior art
Prior art: Boyar–Peralta (2008) established the published bounds `[3,4]`, where Thm 10 gives `<= 4` and Thm 8 / Schnorr degree give `>= 3`. The exact value is verified by an internal check without claiming novelty, as it may already appear in the NIST `Circuits` dataset of symmetric functions up to 25 variables.
Register references
- Register entry: MF-169
- Receipt script:
wave1-symmetric/unit_e2_maj7.py - Receipt output:
out/unit_e2_maj7.json - Log:
PROGRESS.log - Prior art: Boyar–Peralta (2008), Theorems 8 and 10
- Prior art: NIST Circuits data set (symmetric functions up to 25 variables)
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 4 of 4 receipt files bundled (10 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.