Direct-sum theorems and lower bounds for unrestricted multiplicative complexity

Result

Let F(x) and G(y) be Boolean functions on disjoint sets of variables x and y. Let MC(H) denote the unrestricted multiplicative complexity of a function H over GF(2), and let V(H) denote the linear space of direction vectors along which H behaves affinely, with dimension dim V(H). Define the defect e(H) = MC(H) - dim V(H).

1. Rank floor:

dim V(F ⊕ G) = dim V(F) + dim V(G).

1. Restriction lower bound (Theorem A):

MC(F ⊕ G) ≥ dim V(F) + MC(G) and symmetrically MC(F ⊕ G) ≥ MC(F) + dim V(G).

1. Rank-tight additivity (Corollary A1):

If MC(F) = dim V(F), then MC(F ⊕ G) = MC(F) + MC(G) for every G. In particular, MC(F) = 1 implies MC(F ⊕ G) = 1 + MC(G).

1. Defect bound (Corollary A2):

MC(F) + MC(G) - MC(F ⊕ G) ≤ min(e(F), e(G)). A subadditive defect strictly requires both blocks to satisfy e(F) ≥ 1 and e(G) ≥ 1.

1. Complexity-two additivity (Theorem D):

If dim V(F) = dim V(G) = 1 and MC(F) = MC(G) = 2, then MC(F ⊕ G) = 4.

1. Defect normal form (Theorem E):

When Theorem A is tight on the F side, every optimal circuit for F ⊕ G has independent gate classes, satisfies ker(ρ_{x0}|U) = V(F) for every point x0, and the restricted-and-reduced circuit yields a minimal circuit for G.

The direct-sum additivity MC(F ⊕ G) = MC(F) + MC(G) holds whenever min(e(F), e(G)) = 0, and whenever both blocks satisfy (MC, dim V) = (2, 1).

Setting and definitions

Let H be a Boolean function on GF(2)ⁿ. The multiplicative complexity MC(H) is the minimal number of two-input AND gates in an unrestricted straight-line program (XAG) computing H over GF(2) with arbitrary XOR and NOT gates at zero cost.

The space V(H) is the linear subspace of directions v ∈ GF(2)ⁿ such that the second derivative D_u D_v H = 0 for all u ∈ GF(2)ⁿ (the linear structure space of H). The rank floor for multiplicative complexity is dim V(H) ≤ MC(H). The excess (or defect) of H is e(H) = MC(H) - dim V(H) ≥ 0.

For a combined function F(x) ⊕ G(y) on disjoint variable sets x and y, ρ_{x0} denotes the restriction map substituting x := x0, mapping an XAG U over (x, y) to a restricted circuit over y.

Method

Analytic and algebraic restriction proofs are documented in directsum/REPORT.md §§2–4 with candidate analysis in directsum/BANK-CANDIDATES.md DS-1..DS-5, DS-10, and DS-11:

1. Theorem A and Corollary A1–A2:

Substituting x := x0 restricts F(x) ⊕ G(y) to c ⊕ G(y) for a constant c, eliminating the linear space V(F) of dimension dim V(F). Deleting the gates whose classes become linear or linearly dependent under ρ_{x0} and applying rank-nullity to the gate space yields MC(F ⊕ G) ≥ dim V(F) + MC(G). Subtracting this inequality from MC(F) + MC(G) gives the defect bound.

1. Theorem D:

Every function with MC(H) = 2 admits the normal form A1 A2 + L1 L2 B + affine, where A1, A2, L1, L2 are linear forms and B is a Boolean function. When dim V(F) = dim V(G) = 1 and MC(F) = MC(G) = 2, decomposability of the leading degree-3 trivector forces the gate classes across the disjoint variable partition to remain linearly separated. Computing F ⊕ G in 3 gates is impossible, establishing MC(F ⊕ G) = 4.

1. Theorem E:

Analyzing ker(ρ_{x0}|U) over the gate space U shows that tightness in Theorem A forces gate independence across every restriction point x0, ensuring the restricted circuit is minimal for G.

Discussion

The rank floor and Theorem A relate to known results: an abstract by BPP (2000) noted restriction bounds, and Mirwald–Schnorr established additivity within the quadratic cost model. Tensor rank and bilinear complexity fail direct-sum additivity in general following Shitov's refutation of Strassen's additivity conjecture; related direct-sum frameworks include Feig (1984) for bilinear models and Karchmer–Raz–Wigderson (KRW) for formula depth. Theorem D is new: unrestricted Boolean multiplicative complexity lacked an explicit direct-sum theorem.

Scope and boundaries:

• Additivity MC(F ⊕ G) = MC(F) + MC(G) is established when min(e(F), e(G)) = 0, and on the stratum where both blocks satisfy (MC, dim V) = (2, 1).
• The remaining open cases require e(F) ≥ 1, e(G) ≥ 1, and at least one block with MC ≥ 3. Register entry MF-164 resolves the first cell in this stratum.

Attribution and prior art

Prior art: Theorem A and the rank floor are partly known or likely folklore (BPP 2000; Mirwald–Schnorr for the quadratic model). Theorem D appears new: no direct-sum theorem was found for unrestricted Boolean complexity, with the nearest precedents being Strassen additivity, Shitov's refutation, Feig 1984, and KRW for formula depth.

Register references

• Entry ID: MF-163
• Evidence tier: P
• Artifacts: directsum/REPORT.md §§2–4, directsum/BANK-CANDIDATES.md DS-1..DS-5, DS-10, DS-11
• Prior art: BPP (2000, abstract-only); Mirwald–Schnorr; Strassen; Shitov; Feig (1984); Karchmer–Raz–Wigderson (KRW); follow-up in register entry MF-164.

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 2 of 2 receipt files bundled (20 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-164
  Exact multiplicative complexity of direct sums of monomial Boolean functions
• MF-166
  Exact multiplicative complexity of a Fano 3-space at n = 8 and floor census at n = 4
• MF-149
  A lower bound on multiplicative complexity of 2x2 matrix multiplication over F2
• MF-148
  Exact unrestricted multiplicative complexity of 3-term binary polynomial multiplication