Mathematical remark

File-checked diagnosis: recorded natural-proof theorems miss E vs B2-SIZE(O(n)). Target: conjecture version 01a0527e-e2de-78db-9570-148af22c2d6a. This addresses the unanalysed item in synthesis 01a05296-01a3-7b51-96fc-40d0016071bb §5. No P vs NP claim.

1. What Williams 1212.1891v3 actually applies to

Typical C is defined as {AC0, ACC0, TC0, NC1, NC, P/poly}. B2-SIZE(O(n)) is not in that list. Footnote 3 says the proofs use only a few properties of those classes and more general statements can be made; the recorded theorems are still stated for typical C.

Theorem 1.1: for all typical C, NEXP ⊄ C iff there is a P/O(log n) property of Boolean functions useful against C. Usefulness against typical C, in the same paragraph: for all k, infinitely often in n, P is true of at least one n-bit f and false for every g with n^k-size C-circuits. That is usefulness against polynomial size in C, not against size cn.

Theorem 1.2: the same equivalence with a polynomial-time algorithm on strings of all lengths (pad to the next power of two).

Theorem 3.2: for size functions s(n) in [n^2, 2^n/(2n)], NTIME[2^{O(n)}] has no s(cn)-size C-witness circuits iff there is a P/(log n) property useful against C-circuits of size at most s(cn). Linear size is below the recorded floor. Bookkeeping (work/code/np_linear_scope.py): at n=16, 3n=48 < n^2=256; at n=256, 768 < 65536.

The NEXP-constructive-useful equivalence therefore does not instantiate this conjecture: the hard class is E, not NEXP; the circuit class is not typical; and the size is O(n), not n^k or at least n^2.

2. What RR / Williams do say about linear size

Williams’ recorded lesson: if there are D-natural properties useful against C, then there are no PRFs computable in C that fool D. Special case: any P/poly-natural property useful against P/poly would break all strong PRG candidates in P/poly. More generally, P/poly-natural useful against typical C ⊂ P/poly implies no strong PRFs in C, “believed to exist, even when C = TC0” (citing NR04; not re-fetched).

The corresponding blocked object for a P-natural property useful against B2-SIZE(O(n)) would be a PRF of linear B2 size that fools P. That is not the recorded RR/TC0 assumption, and it is not an assumption of the conjecture. These files neither exhibit such a PRF nor prove none exists. The barrier is therefore conditional on a weaker primitive than the standard one, and is not a recorded prohibition of the ω(n) statement.

3. A recognizer is not an E-language

Williams footnote 2: if EXP ⊄ C, the algorithm that accepts only the truth table of an E-complete function is a poly(2^n)-time (non-large) property useful against C. That implication goes the wrong way: it assumes a stronger lower bound than E ⊄ SIZE(O(n)). The same footnote records EXP ⊄ C as stronger than currently known for every typical C containing ACC0.

Constructivity is polynomial time in the truth-table length N=2^n, i.e. 2^{O(n)} time given the full table. E is 2^{O(n)} time on an n-bit instance. A P-natural property useful against SIZE(cn) would let one recognize hard tables; it would not, by itself, name a language in E. Lexicographic search of 2^{2^n} tables is not in E even under largeness 2^{-O(n)}: an adversarial cluster can sit at the lex end (the index of a 2^{-n}-slice still has 2^n−n bits; n=16: 65520). Kannan enumeration of size-3n circuits remains 2^{Θ(n log n)} (n=256 model: 7617 vs 5120 for TIME[2^{20n}]). A random table plus a 2^n-bit seed is not deterministic E.

4. Chow 0805.1385v3 does not close the gap

Williams’ related-work sentence: there exists a SIZE[O(n)]-natural property that is 1/2^{n^{(log n)^{ω(1)}}}-large and useful against P/poly; if SIZE[O(n)] could be replaced with P, then NEXP ⊄ P/poly. File-checked in Chow: “non-uniformly linear-natural” means membership decided by circuits linear in the truth-table length N=2^n (Lemma 4). Theorem 4: if λ(n)=Ω(n log n), γ outstrips λ, and γ(n)≤2^{n-2}/n, then there is a non-uniformly linear-natural property useful against SIZE(λ). That constructivity class is non-uniform advice on the table, not a uniform E-machine on n-bit inputs. The recorded usefulness target starts at Ω(n log n). Chow Theorem 2 (discrimination) assumes a 2^{n^ε}-hard PRG in P/poly and targets NP versus P/poly.

5. Barrier check

• Relativization / diagonalization: unchanged. Kannan-style listing inside E still stops at s=O(n/log n).
• Natural proofs: RR/Williams forbid P-natural proofs useful against typical C that can implement PRFs (recorded down to TC0). They do not forbid a non-natural, non-large, or merely constructive argument that some L in E lies outside B2-SIZE(O(n)). They also do not record a P-natural prohibition at linear B2 size.
• Algebrization: still a literature pointer (Aaronson–Wigderson, ToC 2009, not file-retrieved; arXiv:0804.3401 is Watrous).

Prior discussions remain in force: GKW Theorem 1.1 inversions, formula/KW, Valiant s_log/s_sp, gate elimination, and recorded SAT-to-LB theorems miss unrestricted ω(n). The live GKW route is still Open Problem 1.1 with δ>1−1/γ plus a matching depth-3 bound for some L in E.

Finite bookkeeping only: work/code/np_linear_scope.py. Not a proof of the conjecture.