Open MathsAll courses

The lower bound

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

This lesson proves the theorem of Depth-three circuits and the square-root barrier: the language \(L\) of An explicit language needs depth-three circuits with more than \(2^{A\sqrt n}\) gates, for every constant \(A\) and every large \(n\). The restriction bound and the hard slices are combined first: a hard slice has small correlation with every CNF of width about \(\sqrt d\). Then a small circuit is shown to accept too few inputs.

The order of choices is: first \(A\); then constants \(B\) and \(b\) depending on \(A\); then \(n\) large. The language and its algorithm were fixed before all of them.

1. Parameters

Fix \(A>0\) and put \[ \begin{gathered} d=\lfloor n/5\rfloor,\qquad s=3A,\\ B=64(s+1),\qquad p=\frac B{\sqrt d},\\ m_0=B\sqrt d,\qquad k=\bigl\lceil3(s+1)\sqrt d\,\bigr\rceil . \end{gathered} \] All statements below hold for \(n\) large enough, how large depending on \(A\). In particular \(d\geq64\), \(0<p\leq\frac12\), and \(n\leq5d+4\leq9d\), so that \[ 2^{A\sqrt n}\leq2^{3A\sqrt d}=2^{s\sqrt d}. \tag{1.1} \] The numbers \(k\) and \(1/p\) are both of order \(\sqrt d\), so \(pk\) is bounded: \[ \begin{gathered} \frac{2pk}{1-p}\leq4pk\leq Q,\\ Q=4B\,[\,3(s+1)+1\,], \end{gathered} \] because \(k\leq3(s+1)\sqrt d+1\leq[3(s+1)+1]\sqrt d\).

Lemma 1.1. There is an integer \(b\geq1\), depending only on \(A\), such that the number \(\theta\) of the restriction bound, for these \(k\) and \(p\) and this \(b\), satisfies \(\theta\leq\frac12\).

Proof. The series \(\sum_\ell Q^\ell/\ell!\) converges (from \(\ell+1\geq2Q\) on, each term is at most half the previous one), so there is \(b\geq1\) with \(\sum_{\ell>b}Q^\ell/\ell!\leq\frac12\). With \(\binom k\ell\leq k^\ell/\ell!\) (Exercise 6.5 of Path weights and backward counting), \[ \begin{aligned} \theta&=\sum_{\ell=b+1}^{k}\binom k\ell\Bigl(\frac{2p}{1-p}\Bigr)^{\ell}\\ &\leq\sum_{\ell>b}\frac1{\ell!}\Bigl(\frac{2pk}{1-p}\Bigr)^{\ell}\\ &\leq\sum_{\ell>b}\frac{Q^\ell}{\ell!}\leq\frac12. \qquad\square \end{aligned} \]

This is the only place where \(A\) influences the width \(b\).

2. A hard slice against wide CNFs

Apply Proposition 1.1 of Hard slices with this \(b\) and \(B\): for large \(n\) there is a setting of the parameter bits whose slice has sign \(g:\{0,1\}^d\to\{-1,1\}\) with the following property. Call a restriction \((T,\rho)\) good if it is not exceptional, that is, if \(|T|\in[\frac{m_0}2,2m_0]\) and \(\operatorname{corr}_b(g_{T,\rho})\leq2^{-|T|/8}\). Then \[ \Pr[(T,\rho)\text{ is not good}]\leq4\cdot2^{-m_0/16}, \] and on a good restriction \(\operatorname{corr}_b(g_{T,\rho})\leq2^{-m_0/16}\). Fix this setting.

Proposition 2.1. For every CNF \(H\) of width at most \(k\) on the \(d\) data variables, \[ \bigl|\mathbb E_xg(x)H(x)\bigr|\leq6\cdot2^{-m_0/16}. \]

Proof. By Lemma 4.1 of the first lesson (averaging over restrictions), \[ \bigl|\mathbb E_xgH\bigr|\leq\mathbb E_{T,\rho}\bigl|\mathbb E_zg_{T,\rho}H_{T,\rho}\bigr| . \] By the restriction bound (Lemma 1.1 of A finite expansion of a restricted CNF) and Lemma 1.1 above, there are numbers \(W(H,T,\rho)\geq0\) with \(\mathbb EW\leq1/(1-\theta)\leq2\) and \[ \bigl|\mathbb E_zg_{T,\rho}H_{T,\rho}\bigr|\leq W(H,T,\rho)\operatorname{corr}_b(g_{T,\rho}) \] for every restriction. On a good restriction the right side is at most \(2^{-m_0/16}W\). On any restriction the left side is at most \(1\), because \(g\) is a sign and \(H\) an indicator. Therefore \[ \begin{aligned} \bigl|\mathbb E_xgH\bigr|&\leq2^{-m_0/16}\,\mathbb E\bigl[W\,\mathbf 1_{\text{good}}\bigr]\\ &\qquad+\Pr[\text{not good}]\\ &\leq2\cdot2^{-m_0/16}+4\cdot2^{-m_0/16}. \end{aligned} \] This is the claim. \(\square\)

Two remarks on the logic. The weight \(W\) and the event that the restriction is good may depend on each other in any way; the proof bounds \(W\mathbf 1_{\text{good}}\leq W\) and uses only \(\mathbb EW\leq2\). And the slice was fixed before \(H\): goodness of a restriction controls all CNFs of width \(b\) at once, and the restriction bound is applied to each \(H\) separately, so one slice serves for every \(H\).

Corollary 2.2. For \(n\) large, the slice accepts at least a quarter of the inputs: \(\Pr_x[g(x)=1]\geq\frac14\).

Proof. The constant true function is a CNF of width at most \(k\) (with no clauses). So \(|\mathbb Eg|\leq6\cdot2^{-m_0/16}\), which is less than \(\frac12\) for large \(n\), and \(\Pr[g=1]=\frac12(1+\mathbb Eg)\geq\frac14\). \(\square\)

3. A small circuit accepts too little

Proposition 3.1. Let an OR–AND–OR circuit with \(S\) gates compute the slice of Section 2 exactly, as a function of the \(d\) data variables. Then \[ \Pr_x[g(x)=1]\leq6S\cdot2^{-m_0/16}+S^2\,2^{-k}. \]

Proof. Remove the gates from which no path leads to the output; then every middle gate feeds the top gate. There are at most \(S\) middle gates, and each computes a CNF with at most \(S\) clauses, one for each bottom gate wired to it (Exercise 6.5 of the first lesson). Normalize the clauses: drop clauses that are always true, and drop a middle gate that has a false clause, since it computes \(0\).

Let \(H\) be the CNF of a remaining middle gate, and let \(H'\) be \(H\) without its clauses of width greater than \(k\). Then \(H'\geq H\), and \(H'\) has width at most \(k\). A clause of width \(\ell>k\) is violated on a fraction \(2^{-\ell}\leq2^{-k}\) of the cube, and \(H'-H\) is \(1\) only where a deleted clause is violated, so \[ \mathbb E(H'-H)\leq S\,2^{-k}. \] Every input accepted by \(H\) is accepted by the top gate, which computes the slice. So \(H=1\) implies \(g=1\), that is, \(gH=H\) pointwise. With Proposition 2.1 applied to \(H'\), \[ \begin{aligned} \mathbb EH&=\mathbb E(gH)\\ &=\mathbb E(gH')-\mathbb E\bigl(g(H'-H)\bigr)\\ &\leq6\cdot2^{-m_0/16}+S\,2^{-k}. \end{aligned} \] The accepted set of the circuit is the union of the accepted sets of its middle gates. Summing over at most \(S\) gates gives the claim. \(\square\)

The proof counts all gates: the number of middle gates bounds the number of CNFs, and the number of bottom gates bounds the clauses of each CNF, hence the cost of deleting the wide ones. A CNF with few clauses but large width, and an OR of many narrow CNFs, are both expensive in this count.

4. Proof of the theorem

Theorem 4.1 (OpenAI, 2026). Let \(f_n\) be the membership function of \(L\) on \(\{0,1\}^n\). For every \(A>0\) there is \(N_A\) such that \(S_3(f_n)>2^{A\sqrt n}\) for all \(n\geq N_A\). The language \(L\) is decided in polynomial time.

Proof. Polynomial time is Proposition 3.1 of An explicit language. Fix \(A\) and let \(n\) be large. Suppose an OR–AND–OR circuit with \(S\leq2^{A\sqrt n}\) gates computes \(f_n\). Substitute the parameter bits fixed in Section 2, and arbitrary constants for the unused bits, into its inputs: bottom gates then read data literals and constants, the number of gates does not grow, and the circuit computes the slice. By Corollary 2.2, Proposition 3.1 and (1.1), \[ \begin{aligned} \frac14\leq\Pr[g=1]&\leq6\cdot2^{s\sqrt d-m_0/16}\\ &\qquad+2^{2s\sqrt d-k}. \end{aligned} \] Now \(m_0/16=4(s+1)\sqrt d\) and \(k\geq3(s+1)\sqrt d\), so the right side is at most \[ 6\cdot2^{-(3s+4)\sqrt d}+2^{-(s+3)\sqrt d}, \] which tends to \(0\) as \(n\to\infty\). This is a contradiction for large \(n\). \(\square\)

This is Theorem 2.1 of the first lesson: \(\log_2S_3(f_n)/\sqrt n\) exceeds every constant \(A\) from \(N_A\) on, so it tends to infinity.

5. What the proof gives and what it does not

Where the square root sits. The restriction leaves about \(m_0=B\sqrt d\) variables live, and CNFs are truncated at width \(k\approx3(s+1)\sqrt d\). The two scales are tied together: the restriction bound needs \(pk\) bounded, so \(p\) is of order \(1/k\), and then the number of live variables \(pd\) is of order \(d/k\). The gain \(2^{-m_0/16}\) from the hard slice and the truncation loss \(2^{-k}\) are balanced when \(k\) and \(d/k\) are both of order \(\sqrt d\). Raising the constant \(A\) is paid for by a larger constant \(B\) and a larger width \(b\), and by a larger threshold \(N_A\); nothing else changes. The constants are large: for \(A=1\) the proof takes \(B=256\) and \(Q=13312\), a width \(b\) of about \(36{,}000\) is needed in Lemma 1.1, and the constant \(M(b,\frac18)\) of the sparse partition for such a width is far larger still. The proof makes no attempt to keep \(N_A\) small.

No fixed larger exponent. The proof does not give a bound \(2^{n^{1/2+\varepsilon}}\) for a fixed \(\varepsilon>0\). In the proof of the hard slices the constants \(b\) and \(B\) must be fixed before \(d\) grows: the amount of independence \(t\approx d^{1/6}\) has to beat the number \(2^{O(m\log m)}\) of sparse tests with a constant \(M(b,\frac18)\), and \(M\) grows quickly with \(b\). Whether an explicit function needs depth-three circuits of size \(2^{n^{1/2+\varepsilon}}\) is not settled by this theorem.

Formal verification. OpenAI's release contains a Lean formalization of the theorem in the form stated here: one polynomial-time language, a Turing machine with an explicit time bound, total gate count with unrestricted fan-in and sharing, and the bound for every \(A\) at all large lengths.

6. Exercises

6.1. Check the arithmetic at the end of the proof of Theorem 4.1: with \(S\leq2^{s\sqrt d}\), show \(6S2^{-m_0/16}\leq6\cdot2^{-(3s+4)\sqrt d}\) and \(S^22^{-k}\leq2^{-(s+3)\sqrt d}\).

6.2. Why is the truncation at width \(k\) needed at all? What goes wrong if Proposition 2.1 is applied to a CNF of unbounded width?

6.3. Proposition 3.1 uses that the circuit computes the slice exactly. Where? Show that the argument still works if the circuit only computes a function \(f'\) with \(f'\leq f\) and \(\Pr[f'=1]\geq\frac18\).

6.4. The parity function on \(d\) variables has depth-three circuits of size \(2^{O(\sqrt d)}\). Which step of the proof must therefore fail for parity in place of the slice?

6.5. Show that the theorem implies: for every \(A\), every OR–AND–OR circuit for \(f_n\) with \(n\geq N_A\) has more than \(2^{A\sqrt n}\) bottom or middle gates, up to one gate.

7. Solutions

6.1. \(m_0/16=64(s+1)\sqrt d/16\), which is \(4(s+1)\sqrt d\), so \(S2^{-m_0/16}\leq2^{(s-4s-4)\sqrt d}=2^{-(3s+4)\sqrt d}\). And \(k\geq3(s+1)\sqrt d\) gives \(S^22^{-k}\leq2^{(2s-3s-3)\sqrt d}=2^{-(s+3)\sqrt d}\).

6.2. The restriction bound needs \(\theta<1\), and \(\theta\) contains the terms \(\binom k\ell(2p/(1-p))^\ell\) up to \(\ell=k\). With \(p\) of order \(1/\sqrt d\), this requires \(k\) of order at most \(\sqrt d\). For wider CNFs the expected weight \(W\) is not bounded. The truncation trades width for the error \(S2^{-k}\) per gate.

6.3. It is used for \(gH=H\) (every input accepted by a middle gate is accepted by the slice) and for the accepted set of the slice being the union over the middle gates. If the circuit computes \(f'\leq f\), then \(gH=H\) still holds for its middle gates, and summing gives \(\Pr[f'=1]\leq6S2^{-m_0/16}+S^22^{-k}\), which contradicts \(\Pr[f'=1]\geq\frac18\) for large \(n\) in the same way.

6.4. The hard-slice property (Proposition 1.1 of Hard slices) fails for parity. After a restriction, the sign of parity is, up to a constant sign, the parity of the \(m\) live variables. Split the live variables into \(\lceil m/b\rceil\) blocks of at most \(b\) variables, and let \(J\) say that every block has even parity. Each block condition is a CNF of width at most \(b\) (one clause for each odd assignment of the block), so \(J\in\mathcal C_b(T)\); it accepts a fraction \(2^{-\lceil m/b\rceil}\) of the cube, and the parity is constant on the accepted set. So \(\operatorname{corr}_b\geq2^{-\lceil m/b\rceil}\), which is larger than \(2^{-m/8}\) when \(b\geq9\) and \(m>72\). The width \(b\) of Lemma 1.1 is much larger than \(9\): since \(Q^\ell/\ell!\geq1\) for \(\ell\leq Q\), the condition \(\sum_{\ell>b}Q^\ell/\ell!\leq\frac12\) forces \(b\geq Q\geq1024\). The other steps (the restriction bound and Proposition 3.1) hold for every function.

6.5. The top gate is one gate, so a circuit with \(S\) gates has \(S-1\) bottom and middle gates. If these numbered at most \(2^{A\sqrt n}-1\), the circuit would have at most \(2^{A\sqrt n}\) gates, contradicting the theorem.

References