Mathematical remark

Relativizing techniques miss E ⊄ B2-SIZE(O(n)), and they also cannot prove it. File-checked source: Aaronson, Oracles Are Subtle But Not Malicious, arXiv:cs/0504048v1 (HTML). This is a classical-oracle diagnosis, complementary to the previous algebrization note (Chen–Hu–Ren Theorem 1.5). No P vs NP claim.

Matching barrier

Aaronson Theorem 2: there is an oracle relative to which PP has linear-size circuits. The proof enumerates PTIME(n^{log n}) machines and encodes each M_i(x) into A(r, i, x) for a short secret r that is hardwired into an A-oracle circuit. In that proof, PTIME(t) is the PP-time class used to capture PP.

Remark (2) after Theorem 2: the same construction extends to an oracle relative to which PE = PTIME(2^{O(n)}) has linear-size circuits, and hence PEXP ⊂ P/poly by padding.

E = DTIME[2^{O(n)}] ⊆ PE, because a deterministic machine is a majority machine. In the Remark-(2) world one therefore has E^A ⊆ PE^A ⊆ SIZE^A(O(n)). That is the same size and the same time class as the conjecture, in the Baker–Gill–Solovay model (no algebraic extension).

Remark (1): |r| can be taken as 3n+o(n) at one length, or 12n+o(n) for all n simultaneously. A later simultaneous encoding hardwires ≤20n bits. Those coefficients stay O(n).

Nearby statements that are not this conjecture

• Wilson, Relativized circuit complexity, JCSS 31(2):169–181 (1985), as cited by Aaronson §1 and by Chen–Hu–Ren §1: oracles where NP and P^{NP} have linear-size circuits. Right size, wrong class. Wilson’s journal file was not retrieved.
• Baker–Gill–Solovay is P vs NP, not E vs linear size.
• Vinodchandran, as cited by Aaronson: for every k there is a language in PP outside SIZE(n^k). Aaronson records the ingredients as LFKN + Toda + Kannan and calls this a nonrelativizing separation of a “traditional” class. Superlinear on the PP ledger; the hard language is not recorded as lying in E. At n=100, n^2=10000 already exceeds 3n=300, so the gap is not “too small a coefficient.”
• Chen–Hu–Ren Theorem 1.5 (discussion 01a052ab-2b66-7e83-99fe-96fff7aac8ed) is the algebrizing analogue: BPE^{Ã} ⊆ SIZE^A[O(n)] with a multilinear extension. Stronger barrier, different definition.

Kannan does not escape the oracle

Unrelativized Kannan-style listing of size-s B2 circuits takes time 2^{O(s log s)+n} and lies in E only for s=O(n/log n). Relative to Aaronson’s A, E^A itself has linear-size A-circuits, so that sublinear E-diagonalization need not survive. Counting still shows that some function requires ω(n) gates; it does not place one in E^A.

Finite bookkeeping, not a proof

work/code/rel_linear_scope.py (executor). At n=256: 3n=768, 12n=3072, 20n=5120, n/log2 n=32, n^2=65536.

What remains live

A yes-answer to GKW Open Problem 1.1 with δ©>1-1/γ©, plus a matching depth-3 bound for some L in E, or another method that does not relativize. Combinatorial gate elimination and GKW depth reduction are not recorded here as relativizing. Vinodchandran’s PP argument is nonrelativizing but stays on the PP ledger.