Research · Papers · The quadratic hull and its defects · MF-151
Exact characterization of additive quadruples destroyed by one AND gate
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/8
Published 2026-09-04
For everyone
Plain summary
In Boolean circuit analysis, researchers track intermediate calculations using transcript graphs. An additive quadruple is a group of four circuit inputs whose input values and intermediate values sum to zero. Appending an AND gate—a logical multiplication of two linear terms—can break this balance.
This result gives an exact rule for when an additive quadruple survives an added AND gate. The gate sorts inputs into four buckets based on its two input wires. A quadruple breaks if and only if its four inputs hit all four buckets, forming a rainbow quadruple. Out of 64 balanced four-point assignments across the buckets, exactly 24 hit every bucket. A single AND gate therefore destroys exactly 24/64 (or 3/8) of uniformly distributed quadruples. The underlying algebraic identity is classical, but this exact geometric characterization is new.
Result
Let A = {(x, T(x))} be a transcript graph in GF(2)^k, where x ∈ GF(2)^n and T: GF(2)^n -> GF(2)^(k-n) represents the transcript of intermediate gate evaluations. Let e(x) = u(x) v(x) be an appended AND gate with affine functions u, v: GF(2)^n -> GF(2), and define the affine map P = (u, v): GF(2)^n -> GF(2)^2.
An additive quadruple (x1, x2, x3, x4) of A—satisfying x1 + x2 + x3 + x4 = 0 and T(x1) + T(x2) + T(x3) + T(x4) = 0—survives appending e(x) to the transcript if and only if:
{P(x1), P(x2), P(x3), P(x4)} ≠ GF(2)^2.
The parity condition e(x1) + e(x2) + e(x3) + e(x4) = 0 holds if and only if the four points avoid forming a rainbow quadruple across the four affine fibers of P.
Among all 64 tuples (p1, p2, p3, p4) ∈ (GF(2)^2)^4 satisfying p1 + p2 + p3 + p4 = (0, 0), exactly 24 satisfy {p1, p2, p3, p4} = GF(2)^2. The uniform density of destroyed quadruples is therefore 24/64 = 3/8, leaving a survival density of 5/8.
Setting and definitions
Let GF(2) denote the two-element field. The transcript graph A = {(x, T(x))} records the joint input-intermediate state vector of a Boolean circuit. An additive quadruple of A is an element of A^4 whose four components sum to zero in GF(2)^k.
The four affine fibers of the AND gate e(x) = u(x) v(x) are the preimages P^(-1)(a, b) for (a, b) ∈ GF(2)^2 under P = (u, v). A quadruple (x1, x2, x3, x4) is a rainbow quadruple with respect to P if its image under P equals GF(2)^2.
Method
The characterization is proved via two routes:
- Exhaustive enumeration over all 64 patterns in (GF(2)^2)^4 satisfying p1 + p2 + p3 + p4 = (0, 0). Evaluating the parity e(x1) + e(x2) + e(x3) + e(x4) = u1 v1 + u2 v2 + u3 v3 + u4 v4 over GF(2) confirms that parity failure matches the rainbow condition in all 64 cases, isolating 24 destroyed patterns.
- An analytic hand proof via the symplectic form on GF(2)^2, using the character identity for the AND gate.
The verification script floors/energy58.py outputs parity-kill == rainbow-kill : True; killed patterns 24/64.
Discussion
This entry isolates the combinatorial mechanism of additive energy destruction for an individual AND gate, giving the exact origin of the 5/8 survival factor in the MF-135 floor (i) bounds.
Scope and limitations:
- The result is strictly local: it characterizes additive quadruple destruction after appending a single AND gate.
- The lemma does not bound multi-gate additive energy decay on its own.
- Prior art: The Fourier identity (-1)^(uv) = (1 + (-1)^u + (-1)^v - (-1)^(u+v))/2 is standard in Boolean function analysis; the explicit additive-quadruple and rainbow-fiber formulation is APPARENTLY-NEW.
For everyone — the takeaway
What this means
Proving lower bounds on the number of AND gates needed to compute Boolean functions is a central challenge in circuit complexity. One approach tracks how multiplication gates erode the linear balance—measured by additive energy—of intermediate values.
This result identifies the exact condition for that erosion at a single step. An AND gate destroys an additive relationship if and only if the four inputs hit all four of the gate's possible input states simultaneously. Because this rainbow configuration represents 3/8 of all balanced cases, a single gate destroys at most 3/8 of uniform quadruples, leaving a baseline survival rate of 5/8.
Attribution and prior art
Prior 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.
Register references
- Register entry: MF-151
- Receipt artifact:
floors/energy58.py - Related register entries: MF-135 (floor (i))
- Prior art: standard Fourier identity for (-1)^(uv)
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 1 of 1 receipt files bundled (3 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.