Lemma 8.4 — degree transfer and relative pseudo-reductions
ProvedSemAC02.lemma_8_4_degree_transferac0-2-fregeliftingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polynomial-calculusproof-complexitysemantic-proof-systems
Let be a gadget as in §8.1 on variables, , and the multiplier space (45) of (for any cutoff ). Let be an unsatisfiable CNF, and .
- If has a PC derivation from entirely in , then has a PC refutation of degree at most .
- Consequently, if every PC refutation of has degree at least and , the naïve relative pseudo-reduction for is non-zero.
Taking supplies the operators that Theorem 4.16 requires.
Differences from the source:
- generalization: the base CNF of §8.1 (clauses with 1 ≤ |I| ≤ w₀) → any unsatisfiable CNF F; reason: if F has an empty clause, its clause polynomial 1 is a degree-0 refutation, so the first conclusion holds and the second is vacuous; the source's CNFs are a special case
- encoding: the gadget assumptions of §8.1 → 2 ≤ d and IsGadget d g; reason: the paper's circuits are in normal form by definition
- encoding: PC derivation and refutation in B_n; "a derivation of f" → PCNonBool.IsDerivation / PCNonBool.IsRefutation with reduction AC02Frege.ML; f (resp. 1) occurs as a line; reason: lines are the multilinear representatives; the extra axiom multiple 0·a only adds zero lines, which can be deleted without changing any other line or degree
- encoding: "every base refutation has degree at least Δ_n"; R_{f,ℓ} the quotient map (9) → PCDegreeAtLeast F Δ; naiveRelPR (quotient by the span of the derivable polynomials); reason: the derivable polynomials form a subspace (p.36), so the span adds nothing
Preamble
import Mathlib import Definitions.Def_SemAC02_Circ import Definitions.Def_SemAC02_arith import Definitions.Def_SemAC02_Ble import Definitions.Def_SemAC02_IsGadget import Definitions.Def_SemAC02_lift import Definitions.Def_SemAC02_multiplierSpace import Definitions.Def_SemAC02_PCDegreeAtLeast import Definitions.Def_SemAC02_naiveRelPR import Definitions.Def_LiftSAParity_CNF import Definitions.Def_PCNonBool_IsDerivation import Definitions.Def_PCNonBool_IsRefutation import Definitions.Def_AC02Frege_ML
Formal statement
namespace SemAC02
/-- **Lemma 8.4 (Degree transfer and relative pseudo-reductions)** (Alekseev–Gryaznov–Itsykson–Pitassi–Robere–Tzameret, *Hard Instances for Strong Semantic Proof
Systems*, manuscript (STOC 2027 submission), Lemma 8.4,
p.64): let `g` satisfy the assumptions of §8.1, `v = nm`, `S = {⟦A⟧ : A ∈ Lift_g(F_n)}` and `U` as
in (45). Let `F_n` be an unsatisfiable CNF, let `0 ≠ f ∈ U`, and let `ℓ ≥ 0` be an integer. If `f`
has a PC derivation from `fS` entirely in `f B_v^{≤ℓ}`, then `F_n` has a PC refutation of degree
at most `ℓ + 1`. Consequently, if every base refutation has degree at least `Δ_n` and
`ℓ + 1 < Δ_n`, the naïve relative pseudo-reduction `R_{f,ℓ}` for `S` is non-zero.
**Formalization Note** `U` is `multiplierSpace` of `g` for an arbitrary cutoff `k`. PC
refutations of `F_n` are the published `PCNonBool.IsRefutation` with reduction `AC02Frege.ML`
from the clause polynomials `⟦C⟧`, degree being total degree in `B_n`. "Every
base refutation has degree at least `Δ_n`" is `PCDegreeAtLeast F Δ`. `R_{f,ℓ}` is the quotient map
`naiveRelPR` (9). -/
theorem lemma_8_4_degree_transfer {d n m : ℕ} (hd : 2 ≤ d) (g : Circ (Fin m)) (hg : IsGadget d g)
(F : LiftSAParity.CNF (Fin n)) (hF : ¬ LiftSAParity.Satisfiable F) (k : ℕ)
(f : MvPolynomial (Fin n × Fin m) (ZMod 2))
(hfU : f ∈ multiplierSpace (fun X => g.eval X) n k) (hf : f ≠ 0) (ℓ : ℕ) :
(RelDerivable (arith '' (lift g F : Set (Circ (Fin n × Fin m)))) f ℓ f →
∃ π : List (MvPolynomial (Fin n) (ZMod 2)),
PCNonBool.IsRefutation AC02Frege.ML (pcAxioms F) π ∧ ∀ p ∈ π, p.totalDegree ≤ ℓ + 1) ∧
(∀ Δ : ℕ, PCDegreeAtLeast F Δ → ℓ + 1 < Δ →
naiveRelPR (arith '' (lift g F : Set (Circ (Fin n × Fin m)))) f ℓ ≠ 0) := by sorry
end SemAC02
Source
Alekseev, Gryaznov, Itsykson, Pitassi, Robere, Tzameret, Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]-Frege, manuscript (STOC 2027 submission, sha256 c228d68b89b45b5c6c547aa994f7d1799441bb22b2a85e36c6cd400bea8cdb6a), Lemma 8.4, p.64 (PDF p.66)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.