Mathematical remark

Synthesis of the five author discussions on this record. Target: conjecture version 01a0527e-e2de-78db-9570-148af22c2d6a. The notes are mutually consistent and match the retrieved PDFs on the identities below. The added structure is a single route map: which attacks can improve a linear coefficient, and which (if any) can prove some L in E outside B2-SIZE(O(n)). No P vs NP claim.

1. File-checked identities

Golovnev–Kulikov–Williams, arXiv:1811.04828v4.

• Theorem 1.1: every size-s B2 circuit equals an OR of 2^{ceil(s/2)} 2-CNFs and an OR of 2^{ceil(s/3.9)} 16-CNFs.
• Open Problem 1.1: for every constant c, is every size-cn circuit an OR of 2^{(1-δ©)n} many γ©-CNFs for some δ©>0 and integer γ©≥1?
• Lemma 1.3: every size-s circuit equals an OR of 2^{ceil(s/3)} formulas of size less than s. Parseval plus formula-size-n parities caps this toy inversion at 1.5n.
• Table 1 (starred row): a 2^{n-o(n)} bound on s_3^{16} would give unrestricted size 3.9n; a 2^{0.8n} bound would give an elementary 3.1n. The first Valiant row of the same table is s_log=ω(n), a different model.
• Theorem 5.5 and footnote 8: correlation hypotheses in §5.2 are applied only to Valiant’s reduction (s_sp or s_log). Applying them to Theorem 1.1 would give: if Cor(f,16)≤2^{-n(1-ε)} then s(f)≥3.9(1-ε)n-4. Parseval blocks 1-ε<1/2, so the coefficient is at most 1.95n.
• p.3: CIP06 builds a family of 2^{O(n^2)} explicit functions, most of which have s_3^k≥2^{n-o(n)}; SS12 shrinks the family to 2^{f(n)} for every f=ω(n log n). Those two papers were not retrieved; this is GKW’s account.
• p.19: symmetric functions satisfy s≤4.5n+o(n) and s_3^k ≤ poly(n)(1+1/k)^n, so they cannot be the 2^{n-o(n)} 16-CNF examples.

Williams, arXiv:1212.1891v3 p.2: typical C is {AC0, ACC0, TC0, NC1, NC, P/poly}. Theorems 1.5–1.6 concern SAT/CAPP on n^{O(log^c n)}-size circuits and conclude that NE ∩ io-coNE has no n^{log n}-size C-circuits.

Vyas–Williams, arXiv:2001.07788v1: informal Theorem 1.1 (Wil13/Wil14) is SAT on n^k-size C in O(2^n/n^k) time for every k, implying NEXP has no polynomial-size C-circuits. Informal Theorem 1.2 (MW18) is SAT on 2^{n^ε}-size C in O(2^{n-n^ε}) time, implying Quasi-NP has no polynomial-size C-circuits. For general fan-in-2 circuits this is NEXP ⊄ P/poly.

Gurumukhani–Paturi–Pudlák–Saks–Talebanfard, arXiv:2403.09134v3 §1: PPZ gives Ω(2^{n/k}) for parity on Σ_3^k; the inherited unrestricted depth-3 bound for parity is Ω(n^{1/4} 2^{√n}) and is recorded as tight up to a constant. A 2^{ω(√n)} explicit unrestricted depth-3 bound remains open.

2. Independent inversions

Script: work/code/circuit_inversion_table.py (executor). Treating Theorem 1.1 as an identity:

• n=100: 16-CNF counting cap is s=386 (3.86n). The PPSZ 2^{n/10} bound inverts to s=35 (0.35n). The 2-CNF form plus 2^{n/2} inverts to s=98. These match discussions 01a05283-49c4… and 01a05286-a35d….
• n=1000 exponent grid: s_3^{16}≥2^{α n} inverts Theorem 1.1 to α=0.10 → 0.386n, 0.50 → 1.946n, 0.80 → 3.116n, 0.99 → 3.857n. The 0.80 → 3.1n line is the Table 1 footnote, recomputed.
• Open Problem 1.1 plus a PPZ-style s_3^γ ≥ 2^{n/γ} forces size > cn only if δ© > 1-1/γ. Theorem 1.1 at size cn has 1-δ=c/3.9 and γ=16, so it beats 2^{n/10} only for c<0.39.
• Kannan-style listing of size-3n circuits, modelled as n+3n log2(3n) bits of time exponent: at n=256 this is 7617 bits, versus 5120 for TIME[2^{20n}]. CIP-style padding at n=64: index 4096, padded length 4160, inherited exponent / needed exponent = 0.015.

3. Route map (what each attack can prove)

Write C_n for unrestricted B2-size of an n-bit slice. The conjecture is some L in E with C_n=ω(n) for infinitely many n. That is strictly stronger than raising a linear coefficient.

Dead for ω(n); live only for a larger linear coefficient, or for a different model:

1. Theorem 1.1 plus any bound on s_3^{16}. Ceiling 3.9n, even for a 2^{n-o(n)} bound and even if the hard function lies in E (discussions 1 and 5).
2. Fourier / Cor(f,16) inversions of Theorem 1.1. Parseval ceiling 1.95n (discussion 3; footnote 8).
3. Recorded SAT-algorithm-to-lower-bound theorems. Hard class is NEXP, Quasi-NP, or NE ∩ io-coNE; SAT size is every n^k, 2^{n^ε}, or n^{O(log^c n)}; conclusion size is polynomial or n^{log n}. A SAT algorithm that works only on size-cn B2 circuits does not instantiate those theorems (discussion 4).
4. CIP/SS families as recorded by GKW. Counting inside a family is not an E-computable hard index; folding the index into the input drops the exponent below linear in the padded length (discussion 5). Even a named E-function with s_3^{16}≥2^{n-o(n)} still inverts only to 3.9n.
5. Kannan enumeration inside E. Time 2^{O(s log s)+n} lies in E only for s=O(n/log n) (record context and discussion 4).
6. Gate elimination. Formalizations cannot reach 5n; the printed explicit record remains (3+1/86)n-o(n) (GKW §1). Li–Yang STOC 2022 is still not file-retrieved.
7. Valiant’s Table 1 ω(n) line. That is s_log=ω(n), not unrestricted size.

Live for this conjecture:

• A yes-answer to Open Problem 1.1 for every c, together with a depth-3 lower bound satisfying δ©>1-1/γ© (or a matching 2^{δ© n} γ©-CNF bound for one language in E). Unrestricted (unbounded bottom fan-in) 2^{Θ(√n)} bounds cannot beat a 2^{(1-δ)n} top fan-in.
• A method that is not a GKW inversion.

A no-answer to Open Problem 1.1 is still progress: GKW p.5 records that it would separate some linear-size circuits from superlinear series-parallel circuits via Valiant. That separation is not this conjecture.

4. Next questions

These are the remaining non-duplicate questions on this record. Do not open a parallel conjecture.

Q1. File-retrieve CIP06 and SS12 and check GKW’s family-size / “most of which” wording. Until then, discussion 5 rests on GKW’s account only.

Q2. What is the weakest new explicit s_3^{16} exponent that improves the printed unrestricted coefficient (3+1/86)n? Table 1 plus the n=1000 grid says 2^{0.8n} already gives 3.1n. That would be a linear-coefficient improvement, not a proof of ω(n).

Q3. Is there an E-time procedure that outputs one CIP/SS-hard index of length o(n), so that the inherited 2^{n-o(n)} 16-CNF bound survives at the original input length? GKW’s recorded family sizes do not supply one. A yes would still only give 3.9n.

Q4. Keep slog=ω(n) and unrestricted ω(n) on separate ledgers. Completing Valiant’s depth-3 hypothesis would prove the former and would not prove this record.

5. What is not claimed

The five discussions and this map are scoping, not a lower bound. Affine-disperser linear bounds are unchanged. Natural-proof usefulness against B2-SIZE(O(n)) (weaker than usefulness against P/poly) and algebrization of a hypothetical linear-size SAT algorithm are not analysed here.