Mathematical remark

Discussion note on gate elimination versus the conjecture. File-verified sources: Golovnev-Kulikov-Williams, arXiv:1811.04828v4, abstract and Section 1; Carmosino-Dang-Jackman, arXiv:2604.23958v1, abstract, Section 1, Lemma 1, Definition 2, Theorems 3, 5, 7, and Corollary 6. GHKK18 (JCSS 96:107-119, 2018), FGHK16, and Li-Yang STOC 2022 were not file-retrieved. export.arxiv.org title, author, and phrase searches for “On the limits of gate elimination” returned zero items. This fills the one-line GE item in synthesis 01a05296-01a3-7b51-96fc-40d0016071bb section 3 item 6.

GKW record that gate elimination is the only technique that has produced explicit unrestricted-size lower bounds; that the printed explicit record is (3+1/86)n-o(n) for affine dispersers (FGHK16 as cited); that no function in P, NP, or E^{NP} is known to require 3.1n binary gates; and that a formalization of gate elimination (GHKK18 as cited) cannot obtain a stronger than 5n bound. CDJ record the same 5n formalization and add that it does not cover every gate-elimination argument, in particular those that use the optimal structure of circuits for f or special properties of f. CDJ also record Li-Yang STOC 2022 as 3.1n-o(n) for affine dispersers in P (still not file-retrieved here).

Those statements do not yield some L in E outside B2-SIZE(O(n)). (1) A 5n ceiling is still O(n). The conjecture asks for C_n=omega(n) for infinitely many n, i.e. a coefficient that is not a fixed constant. (2) Even gate-elimination arguments that evade the recorded formalization have, in the printed record, only produced linear B2 bounds. CDJ’s 3.1n Li-Yang sentence is still linear. (3) CDJ constructivity is a different property. A Gamma-refuter, given 1^n and a circuit of size < s(n), prints an input on which the circuit errs. Theorem 3 is a P-refuter for MUX against DeMorgan-size 2N+log N-2. Theorem 5 is an affine refuter for dimension d against B2-size 3n-4d(n). Corollary 6 is a P^{NP}-constructive separation of an explicit affine disperser in P from B2-size 3n-o(n). Theorem 7 is a P-refuter for XOR against DeMorgan-size 3(n-1). Finding an error input efficiently does not raise s(n). (4) Wrong basis for XOR and MUX. CDJ distinguish DeMorgan (AND/OR/NOT) from B2. A DeMorgan lower bound does not lower-bound B2-SIZE: C_B2(f) <= C_DeMorgan(f). XOR has B2-size n-1. (5) MUX is linear in its input length. MUX_n is defined on L=n+2^n bits. The DeMorgan bound 2N+log N-2 with N=2^n satisfies LB/L -> 2. At address length 16, L=65552 and LB/L=1.9997. That is not omega(L). (6) Affine dispersers, XOR, and MUX lie in P subset E. Completing a 4.99n gate-elimination bound for an affine disperser would still be an E-versus-linear-size statement, not omega(n).

Finite bookkeeping: work/code/gate_elim_scope.py (executor). At n=256: 3.1n=793.6, (3+1/86)n approximately 771, 5n=1280, 20n=5120. Affine refuter at d=n/10: 668=2.61n.

Barriers: this is a comparison of recorded GE ceilings and CDJ constructivity, not oracle diagonalization. The GHKK18 formalization is used only through GKW and CDJ; its exact syntactic restriction was not re-read. Natural-proof usefulness of a property that holds of affine dispersers against SIZE(O(n)) is weaker than usefulness against P/poly and is not analysed here. Algebrization of gate elimination is not analysed here. No P versus NP claim. Affine-disperser linear bounds and the GKW combinatorial s_3^{16} / Open Problem 1.1 route are unchanged. Li-Yang remains ACM/DOI-only from this environment.