gpt 6 astra pro attempt on CS-16

Superlinear Circuit Lower Bounds for Explicit Boolean Functions

Definitions and mathematical statement

Let $\mathcal B_2$ be the set of all binary Boolean gates, with unrestricted circuit depth and fan-out. Denote by $C_{\mathcal B_2}(f_n)$ the minimum number of gates in a single-output circuit for $f_n$. Seek one uniformly polynomial-time computable family satisfying \[ \lim_{n\to\infty}\frac{C_{\mathcal B_2}(f_n)}{n}=\infty. \] Equivalently, every fixed linear bound is violated for all sufficiently large input lengths. A lower bound $cn-o(n)$ for one fixed $c$, no matter how large, is not superlinear in this sense.

Formulation and concept references: [S1].

Short English statement

Can an explicit polynomial-time Boolean function be proved to require more than every constant multiple of its input length in general circuit gates?

Research attempt

Current frontier.

Li--Yang prove a $3.1n-o(n)$ lower bound for explicit affine dispersers over the full binary basis. Their discussion of particular gate-elimination limitations is not a barrier against all lower-bound methods. A fixed constant cannot give the divergent ratio in this target. [S1] Restricted-model advances must remain separate: Rao's September 2026 manuscript gives exponential bounds for monotone matching circuits, not circuits with arbitrary binary gates. [E1]

Attack route.

Counting finds hard small truth tables but is too slow at the final input length. Padding restores polynomial-time uniformity while destroying the lower-bound ratio. We combine a slowly growing hard table with many disjoint input blocks and an XOR output. The missing step is a quantitative direct-sum estimate for unrestricted circuits, not the availability of hard tables at this small scale.

Attempt: construct a uniform hard-block family.

Allow free constants; this strengthens circuits and thus makes a lower bound in that model sufficient for the target. For $k\ge8$, set \[ s_k=\left\lfloor\frac{2^k}{16k}\right\rfloor. \] Topologically ordered circuits with $s_k$ gates have at most \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-63-6f-75-6e-74} (k+s_k+2)\left[16(k+s_k+2)^2\right]^{s_k} \end{equation} descriptions. Padding with projection gates includes all smaller circuits. Since $k+s_k+2\le2^k$, the base-two logarithm is at most \[ k+\frac{2^k}{16k}(4+2k)<2^k. \] Thus fewer than the $2^{2^k}$ truth tables are represented. Let $h_k$ be the lexicographically first missing table. This definition is effective: enumerate descriptions, evaluate their tables, mark them and select the first unmarked table. The running time and space are $2^{O(2^k)}$, and $C_{\mathcal B_2}(h_k)>s_k$. It is not advice hiding an unspecified hard function.

For sufficiently large $n$, choose \[ k(n)=\lfloor\log_2\log_2n\rfloor, \qquad t(n)=\lfloor n/k(n)\rfloor, \] and on disjoint $k$-bit blocks define \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-66-61-6d-69-6c-79} f_n(x)=\bigoplus_{i=1}^{t(n)}h_{k(n)}(x^{(i)}). \end{equation} Ignore the fewer than $k$ leftover bits and define the finitely many small lengths arbitrarily. Because $2^k\le\log_2n$, construction of $h_k$ takes $n^{O(1)}$ time with one fixed exponent; all subsequent table lookups and XOR operations are polynomial too. The logarithms defining $k$ are computed by integer bit lengths. Thus this is a genuinely uniform polynomial-time family meeting the explicitness requirement.

The precise amplification estimate that would suffice.

For these specific tables, suppose there is an absolute $\gamma>0$ such that \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-44-53} C_{\mathcal B_2}\left(\bigoplus_{i=1}^{t}h_k(x^{(i)})\right) \ge\gamma t C_{\mathcal B_2}(h_k) \end{equation} uniformly at the required $k,t$. Then \[ \frac{C_{\mathcal B_2}(f_n)}n \ge c\frac{2^{k(n)}}{k(n)^2} \ge c'\frac{\log n}{(\log\log n)^2}\longrightarrow\infty. \] Floors change only constants at sufficiently large lengths. Unused bits cannot lower this bound: fixing them in any circuit gives a circuit of no greater size for the active-block function. This conclusion holds at every sufficiently large $n$, not only a sparse subsequence.

Even $\gamma_k$ tending to zero would suffice if $\gamma_k2^k/k^2\to\infty$. This quantitative relaxation is a possible attack target. Neither version of (30006747:DS) is proved here. Its implication for the original problem is a warning about its depth, not a reason to infer it from disjointness of variables.

What separation of blocks actually proves.

Consider the restricted architecture where each block enters its own disjoint subcircuit producing one bit $g_i(x^{(i)})$, and every later gate sees only these bits. If the output is (30006747:family), fix all blocks except $i$. The final function is unary in $g_i$ but must equal $h_k$ or $1-h_k$. Since $h_k$ is nonconstant for large $k$, this unary function is nonconstant; hence $g_i=h_k$ or $1-h_k$. Complementing costs at most one binary gate, so the $i$th subcircuit has size at least $C(h_k)-1$. Summing disjoint gate sets proves \[ C\ge t(C(h_k)-1) \] in this architecture. This verifies amplification when early cross-block mixing is prohibited, not in the catalogue's unrestricted model.

Stress test: why separate restrictions do not add.

In an unrestricted circuit, fixing all but one block gives an individual lower bound, but repeating this for each block gives a maximum, not their sum. A gate can survive many different restrictions. For example, on $t$ two-bit blocks first compute the XOR of all first bits and the XOR of all second bits, then XOR those two results. The last gate remains a genuinely binary XOR under every restriction leaving only one block. Charging it once per block counts the same gate $t$ times. The companion script checks this overlap directly; it is not merely counting gates that become removable unary identities after restriction.

Replacing disjoint blocks by repeated identical inputs is worse: $h_k(x)\oplus h_k(x)=0$. Disjoint variables avoid this cancellation but do not force disjoint internal computations. Bare padding $\widetilde f_n(x)=h_{k(n)}(x_1,\ldots,x_k)$ has a truth-table circuit of size $O(2^k)=O(\log n)$, so cannot be the desired family. A proof must control shared computation, not tacitly replace circuits by the block-separated architecture.

Outcome.

Outcome: Conditional reduction. A fully uniform polynomial-time candidate family has been constructed, and a specified disjoint-block direct-sum estimate would give an explicit divergent lower-bound ratio. Amplification is proved only for the restricted architecture; unrestricted mixing is the remaining gap. The counting mechanism is standard and no new general circuit lower bound is claimed. A solution of this weak superlinear problem would not alone imply $\mathsf P\ne\mathsf{NP}$: the constructed family is in $\mathsf P$ and could still have larger polynomial-size circuits.

Sources

• S1 3.1n - o(n) Circuit Lower Bounds for Explicit Functions, ECCC TR21-023,20February2021. https://eccc.weizmann.ac.il/report/2021/023/download/. Catalogue formulation source.
• E1 A. Rao, Monotone circuit lower bounds from spread matchings, author's manuscript, 3 September 2026, Theorem 1 and Corollary 2. https://homes.cs.washington.edu/~anuprao/pubs/matchinglowerbound.pdf.