Theorem 1.4 — superpolynomial size bounds for depth-3.5 AC0[2]-Frege
ProvedAC02Frege.theorem_1_4_depth35_lower_boundLet 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 :
- the encoding length of is at most , and
- for every with , every depth-3.5 AC0[2]-Frege refutation of with bottom degree has total size 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:
- generalization: ℓ = Θ(log n) "chosen as in Corollary 4.21" (a sufficiently large constant times log n, rounded up to an odd integer) → for all 0 < λ₁ ≤ λ₂, every odd ℓ with λ₁ log n ≤ ℓ ≤ λ₂ log n, quantified before ∃ α; reason: Corollary 4.21 does not fix its constant; its choice ℓ = ⌈λ log n⌉_odd lies in the window [λ log n, 2λ log n] for large n, so the statement specializes to the source
- reading: "a constant α > 0, depending only on c", "for all sufficiently large n", F of constant width → ∃ α after c, λ₁, λ₂ and before the width bound w; ∃ k n₀ after w; reason: constant width fixes w before n; the proof of §5.4 makes α depend only on c and the constant of ℓ = Θ(log n), and n₀ on w
- generalization: c in (0, 1) (setting of §4.4); Definition 1.2 says c > 0 → every c > 0; reason: the hypothesis "no PC refutation of degree ⌊cn⌋" is monotone in c, so c ≥ 1 reduces to c = 1/2
- reading: "so that G has polynomial size" → a conjunct: ∃ k with encLength (lift F ℓ) ≤ n^k; reason: the sentence asserts that G has polynomial size
- encoding: "no PC refutation of degree cn" → ¬ PCDerivable F ⌊c n⌋₊ 1 (formal degree, Boolean axioms y_i² + y_i); reason: formal degrees are integers, so degree ≤ cn means degree ≤ ⌊cn⌋
- generalization: lines as disjunctions of terms with weakening and contraction → lines as finite sets of terms (contraction built in); reason: every refutation in the paper's form maps to a set-based one of no larger total size, so the bound specializes
- encoding: terms with order and repetition immaterial; polynomials of degree ≤ b; 1 ≤ b ≤ √ℓ; log → terms as finite sets of multilinear MvPolynomial (Fin n × Fin ℓ) (ZMod 2) of totalDegree ≤ b; 1 ≤ b, b² ≤ ℓ; Real.log; reason: same instances; the base of the logarithm is absorbed by α and λ
- reading: total size "counts all term occurrences as well as all monomial occurrences" → Σ over lines and their terms of (1 + Σ over the term's polynomials of the number of monomials); reason: one count per term occurrence plus one per monomial occurrence, with nothing else added
import Mathlib import Definitions.Def_LiftSAParity_CNF import Definitions.Def_AC02Frege_ML import Definitions.Def_AC02Frege_PC import Definitions.Def_AC02Frege_lift import Definitions.Def_AC02Frege_D35Refutation
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.