AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by Razborov and Smolensky in 1987, but no comparable lower bound is known for proofs. The best results concern restricted subsystems.
All polynomials are over and are identified with functions on the Boolean cube; products are multilinearized (). A CNF is encoded by the complements of its clauses and the Boolean axioms . Polynomial calculus (PC) derives new polynomials by linear combinations and by multiplication with a variable; its degree is the largest formal degree of a line. is the space of multilinear polynomials derivable in degree , and "no PC refutation of degree " means .
For odd , the majority lift replaces every variable by the majority of a block of fresh variables , rewrites each substituted clause as a CNF, and has variables.
A line of depth-3.5 AC0[2]-Frege with bottom degree is a disjunction of terms, each term a conjunction of equations with a multilinear polynomial of degree at most . The rules are weakening, projection, conjunction introduction, a cut on a term, the polynomial rules (linear combination and multiplication ), deletion of , the default axioms , and , and the input clauses. The total size counts every term occurrence and every monomial occurrence.
The paper presents three main results: the majority-lifted line lower bound for , refTheorem 4.20; the depth-3.5 AC0[2]-Frege lower bound, refTheorem 1.4; and the unrestricted-degree total-size lower bound, refTheorem 1.5. The platform allows one goal, so Theorem 1.4 is the goal and the other two are milestones of equal standing.
On 2026-11-15, five milestones from Sections 3, 4 and 6 and Appendix A were added so that the mission covers every theorem proved in the paper.
For every and there is such that for every width , all sufficiently large , every CNF on variables of width at most with no PC refutation of degree , and every odd : has polynomial size, and every depth-3.5 refutation of with bottom degree satisfies
The milestones follow the proof: Fact 2.5 (multiplication in ); the one-block algebra of the majority (Lemma 4.3) and the majority expansion (Lemma 4.5); the coefficient degree and the lifted space (Lemmas 4.8, 4.10, 4.11); Pang's matrix lemma (Theorem A.5); the one-factor gain and degree comparison with coefficient-degree losses (Lemmas 4.15, 4.16) and their iteration (Proposition 4.17); the counting estimates (eq. (49), Lemma 4.19, Lemma C.1); and the simulation and rank criterion for depth-3.5 proofs (Proposition 5.2, Corollary 5.3).
Since is polynomial in , the bound is superpolynomial in whenever , and is for constant . By the normal form of [BKZ15] and the equivalence Lemma D.2 of the manuscript, the same statement with would give superpolynomial lower bounds for depth- AC0[2]-Frege. The gap to that problem is thus a single parameter, the bottom degree. Already at the negation of the input CNF is a single line of the system, so the bound is necessarily about the rules rather than the expressible lines.
The result is new (an unpublished manuscript dated November 3, 2026) and has no machine-checked proof. A formalization would produce a reusable library of polynomial calculus, multilinear Boolean-ring algebra, Razborov–Smolensky approximation and the rank arguments of Pang's method, and would check a proof whose bookkeeping of two degrees, two levels of approximation and additive rank losses is easy to get wrong on paper.
The obvious route, Pang's argument applied directly, fails for degree beyond : each factor of a line approximator removes only a fraction of the error conditions, because the multiplier degree must stay a constant fraction below to remain inside the PC degree budget. The majority lift decouples the ordinary degree of the multiplier, which the counting sees, from its coefficient degree , which polynomial calculus sees. The multiplier can then have degree near , where binomial coefficients are flat and . The price is that is closed under multiplication only for known members of coefficient degree at most . Every step of the rank argument therefore loses dimensions to the restriction , and the counting has to show that these losses are exponentially smaller than the room . For depth 3.5 the term approximants are chosen independently of each other, and the simulation must recover that the approximant of a conjunction is the product of its parts.
Polynomials are MvPolynomial V (ZMod 2); multilinearity is a predicate and a linear map. CNFs reuse the published LiftSAParity.CNF; PC derivations reuse the published PCNonBool.IsDerivation with the identity reduction and the bound totalDegree ≤ D on every line (formal degree, Boolean axioms included). Original variables are Fin n, lifted variables Fin n × Fin ℓ, and . Terms are finite sets of polynomials and lines finite sets of terms; total size is . takes values in WithBot ℕ; dimensions are Module.finrank of spans. Logarithms are natural.
The bottom-degree bound applies to every polynomial of every line, conclusions of rules and default axioms included; only the multiplier of the multiplication rule is unrestricted. The approximants of Definition 5.1 have a fixed shape, so taking is not available. A soundness check, proved in the verification files, shows that a satisfiable CNF has no refutation, so the goal is not vacuous.
Needed infrastructure: multilinear algebra and evaluation, the majority basis, rank and kernel arguments over and over , a multiplicity Schwartz–Zippel lemma, a hypergeometric tail bound, and binomial-sum estimates. The polynomial-calculus and matrix-lemma parts are reusable beyond this mission. Contributions to any milestone, including the purely combinatorial ones (eq. (49), Lemma C.1), are welcome.
namespace AC02Frege
open MvPolynomial LiftSAParity
/-- Alekseev–Gryaznov–Pitassi–Robere–Shekhovtsov–Tzameret, *Progress on AC0[2]-Frege Lower Bounds*, manuscript (sha256 88d149fa…), Theorem 1.4, p.5 (restated p.29, (38); proof §5.4, pp.31–32): superpolynomial size
bounds for depth-3.5 AC0[2]-Frege. Let `F` be a constant-width CNF on `n` variables with no PC
refutation of degree `cn`, and let `G = F ∘ Maj_ℓ` with `ℓ = Θ(log n)`, so that `G` has
polynomial size. There is a constant `α > 0` such that for all sufficiently large `n` and all
`1 ≤ b ≤ √ℓ`, every depth-3.5 AC0[2]-Frege refutation of `G` with bottom degree `b` has total
size `T` with `log T ≥ α (log n)^{3/2} / b`.
**Formalization Note** `ℓ = Θ(log n)` is quantified as: for all `0 < λ₁ ≤ λ₂` and every odd `ℓ`
with `λ₁ log n ≤ ℓ ≤ λ₂ log n`; `α` is chosen after `c, λ₁, λ₂` and before the width bound `w`;
`k` (polynomial size) and `n₀` (sufficiently large) after `w`. "No PC refutation of degree
`cn`" is `¬ PCDerivable F ⌊cn⌋ 1` (formal degree, Boolean axioms). `b ≤ √ℓ` is `b² ≤ ℓ`.
`log` is the natural logarithm (the base is absorbed by `α` and `λ`). -/
theorem theorem_1_4_depth35_lower_bound :
∀ c : ℝ, 0 < c → ∀ lam₁ lam₂ : ℝ, 0 < lam₁ → lam₁ ≤ lam₂ →
∃ α : ℝ, 0 < α ∧ ∀ w : ℕ, ∃ k n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n →
∀ F : CNF (Fin n), (∀ C ∈ F, C.card ≤ w) → ¬ PCDerivable F ⌊c * n⌋₊ 1 →
∀ ℓ : ℕ, Odd ℓ → lam₁ * Real.log n ≤ ℓ → (ℓ : ℝ) ≤ lam₂ * Real.log n →
encLength (lift F ℓ) ≤ n ^ k ∧
∀ b : ℕ, 1 ≤ b → b ^ 2 ≤ ℓ → ∀ π : List (Line (Fin n × Fin ℓ)),
IsRefutation b (lift F ℓ) π →
α * Real.log n ^ ((3 : ℝ) / 2) / b ≤ Real.log (totalSize π) := by sorry
end AC02Frege
Let be a constant-width CNF on variables with no polynomial-calculus refutation over of degree , and let be its majority lift with block length odd. Then has polynomial size, and there is a constant such that for all sufficiently large and all , every depth-3.5 AC0[2]-Frege refutation of with bottom degree has total size with
Precisely: for every and every there is such that for every width bound there are and with the following property. For every , every CNF on variables of width at most with no PC refutation of degree , and every odd with :
Since is polynomial in , the bound is superpolynomial in for and equals for constant . By the normal form of Buss, Kołodziejczyk and Zdanowski, lower bounds for this system with would give superpolynomial lower bounds for depth- AC0[2]-Frege.
Formalization Note The degree hypothesis concerns in its own variables (formal PC degree, Boolean axioms included); the refutation is of in the lifted variables.
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.