Theorem 4.20 — majority extension with variable block length:
ProvedAC02Frege.Supplement.theorem_4_20Fix and a positive integer . There are constants , depending only on , with the following property. Let be an unsatisfiable polynomial-size CNF on variables of width at most with no PC refutation over of degree . Let be odd and an integer with . Then for all sufficiently large , every -line syntactic refutation of satisfies
The formula has variables, width at most , and . Hence the bound on lines, and a fortiori on total size, is superpolynomial in whenever
Precisely: for all and there are such that for all exponents there are such that for every , every unsatisfiable CNF on variables with , width at most and no PC refutation of degree , and every odd :
- and for ;
- for every integer with and every refutation of with lines and total size : (36) holds, and if then and .
Unlike Theorem 3.14, the decay is instead of , which allows degrees up to about .
Formalization Note is the base lift F ℓ and its encLength (literal occurrences plus one per clause).
Differences from the source:
- generalization: lines as disjunctions of equations, with weakening and contraction as rules → lines as finite sets of polynomials (RLine), contraction and reordering built in; reason: each line of a refutation in the paper's form maps to its set of polynomials, and every rule application maps to a rule application, so a paper refutation gives a set-based one with the same number of lines (and the same total size); the lower bound for set-based refutations specializes to the source
- encoding: "no PC refutation of degree D = ⌊cn⌋" → ¬ PCDerivable F ⌊c n⌋₊ 1 (base definition: formal degree, Boolean axioms y_i² + y_i); reason: formal degrees are integers, so degree ≤ cn means degree ≤ ⌊cn⌋; same instances
- reading: "Let F_n be a polynomial-size CNF" → for every exponent k, encLength F ≤ n^k, with n₀, C′, M chosen after k; reason: polynomial size means a fixed polynomial bound; ℓ₀, κ, c₁, C are chosen before k, as the theorem says they depend only on c, w
- reading: "Then for all sufficiently large n" → ∃ n₀ after c, w, k, k′ and before F, ℓ, r (one threshold for all ℓ, r with r + ℓ ≤ κn); reason: the stronger of the two readings; the proof's largeness conditions (D ≥ cn/2, 4n⁴e^{−11n} small, N ≤ n²) involve n only once r + ℓ ≤ κn
- encoding: G_n has N = nℓ variables and width at most w(ℓ+1)/2 → variables Fin n × Fin ℓ; 2 · width (lift F ℓ) ≤ w (ℓ + 1); reason: same instances
- reading: log |G_n| = O(ℓ + log n) → ∃ C′ (after k) with log encLength (lift F ℓ) ≤ C′ (ℓ + log n); reason: the O-constant may depend on the fixed data c, w and the size exponent k, as in the proof (|G_n| ≤ |F_n|·binom(ℓ, (ℓ+1)/2)^w)
- reading: the bound on lines, and on total size, is superpolynomial in |G_n| whenever (n/r)exp(−Cr/√ℓ) = ω(ℓ + log n) (37) → for every k′ there is M (after k) such that (n/r)exp(−Cr/√ℓ) ≥ M(ℓ + log n) implies encLength(G)^{k′} ≤ S and encLength(G)^{k′} ≤ T; reason: pins ω and 'superpolynomial' per n; along any sequence with ratio → ∞ it gives |G_n|^{k′} ≤ S, T eventually for every k′, which is the source's claim
- encoding: T, the number of monomial occurrences (Definition 2.7) → totalSize π = max 1 (monomial occurrences); reason: F has no empty clause (its complement 1 would be a degree-0 PC refutation), so every refutation of G contains a line with a monomial and the floor changes no instance
- encoding: log; S the number of lines → Real.log (natural logarithm); S = π.length; reason: the proof of (14)/(16) uses the natural logarithm (it compares S·e^{−ηt}); same instances
import Mathlib import Definitions.Def_LiftSAParity_CNF import Definitions.Def_AC02Frege_PC import Definitions.Def_AC02Frege_lift import Definitions.Def_AC02Frege_Supplement_ResPC
namespace AC02Frege.Supplement
open LiftSAParity
/-- Alekseev–Gryaznov–Pitassi–Robere–Shekhovtsov–Tzameret, *Progress on AC0[2]-Frege Lower
Bounds*, manuscript (sha256 88d149fa…), Theorem 4.20, p.27 (majority extension with variable block
length). Fix `0 < c < 1` and a positive integer `w`. There are constants `ℓ₀, κ, c₁, C > 0`,
depending only on `c, w`, such that: if `F_n` is an unsatisfiable polynomial-size CNF on `n`
variables of width at most `w` with no PC refutation over `𝔽₂` of degree `D = ⌊cn⌋`, `ℓ ≥ ℓ₀` is
odd and `r ≥ 1` is an integer with `r + ℓ ≤ κn`, then for all sufficiently large `n` every `S`-line
syntactic `Res(PC_r)` refutation of `G_n = F_n ∘ Maj_ℓ` satisfies
`log S ≥ c₁ (n/r) exp(−C r/√ℓ)` (36). `G_n` has `N = nℓ` variables, width at most `w(ℓ+1)/2`, and
`log |G_n| = O(ℓ + log n)`; hence the bound on lines, and a fortiori on total size, is
superpolynomial in `|G_n|` whenever `(n/r) exp(−C r/√ℓ) = ω(ℓ + log n)` (37).
**Formalization Note** "Polynomial-size" is `encLength F ≤ n^k` for a fixed exponent `k`;
`O(ℓ + log n)` is an explicit constant `C′`, and the `ω` of (37) is pinned uniformly: for every
exponent `k′` there is `M` such that `(n/r) exp(−C r/√ℓ) ≥ M (ℓ + log n)` forces
`|G_n|^{k′} ≤ S` and `|G_n|^{k′} ≤ T` (equivalent to the sequence form of `ω`). `ℓ₀, κ, c₁, C` are
chosen before `k, k′` and do not depend on `n, ℓ, r`; `n₀, C′, M` may depend on `c, w, k, k′`. `|G|`
is the base `encLength`, `N = nℓ` is the variable type `Fin n × Fin ℓ`, and the width bound is
`2 · width(G_n) ≤ w(ℓ + 1)`. `log` is natural. -/
theorem theorem_4_20 :
∀ c : ℝ, 0 < c → c < 1 → ∀ w : ℕ, 1 ≤ w →
∃ ℓ₀ : ℕ, ∃ κ c₁ C : ℝ, 0 < ℓ₀ ∧ 0 < κ ∧ 0 < c₁ ∧ 0 < C ∧
∀ k k' : ℕ, ∃ n₀ : ℕ, ∃ C' M : ℝ, ∀ n : ℕ, n₀ ≤ n →
∀ F : CNF (Fin n), ¬ Satisfiable F → AC02Frege.encLength F ≤ n ^ k →
(∀ J ∈ F, J.card ≤ w) → ¬ AC02Frege.PCDerivable F ⌊c * n⌋₊ 1 →
∀ ℓ : ℕ, Odd ℓ → ℓ₀ ≤ ℓ →
2 * AC02Frege.width (AC02Frege.lift F ℓ) ≤ w * (ℓ + 1) ∧
Real.log (AC02Frege.encLength (AC02Frege.lift F ℓ)) ≤ C' * (ℓ + Real.log n) ∧
∀ r : ℕ, 1 ≤ r → (r : ℝ) + ℓ ≤ κ * n →
∀ π : List (RLine (Fin n × Fin ℓ)), IsResRefutation (r : ℕ∞) (AC02Frege.lift F ℓ) π →
c₁ * ((n : ℝ) / r) * Real.exp (-C * r / Real.sqrt ℓ) ≤ Real.log π.length ∧
(M * (ℓ + Real.log n) ≤ (n : ℝ) / r * Real.exp (-C * r / Real.sqrt ℓ) →
((AC02Frege.encLength (AC02Frege.lift F ℓ) : ℝ) ^ k' ≤ π.length ∧
(AC02Frege.encLength (AC02Frege.lift F ℓ) : ℝ) ^ k' ≤ totalSize π)) := by sorry
end AC02Frege.Supplement