Proposition 8.3 — lifting preserves unsatisfiability
ProvedSemAC02.proposition_8_3_lift_unsatac0-2-fregeliftingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polynomial-calculusproof-complexitysemantic-proof-systems
Let be a gadget as in §8.1 and a CNF. If is unsatisfiable, then is unsatisfiable: no assignment to the lifted variables satisfies every circuit of .
Unsatisfiability of the lift is what makes refutations of exist at all.
Differences from the source:
- generalization: base CNF of §8.1 with clauses of 1 ≤ |I| ≤ w₀ literals → any CNF F (empty clauses and any width allowed); reason: an empty clause lifts to the empty OR, which no assignment satisfies, so the conclusion still holds; the source's CNFs are a special case
- encoding: the standing assumptions of §8.1 on d and g → 2 ≤ d and IsGadget d g (normal form included); reason: the paper's circuits are in normal form by definition
Preamble
import Mathlib import Definitions.Def_SemAC02_Circ import Definitions.Def_SemAC02_IsGadget import Definitions.Def_SemAC02_lift import Definitions.Def_LiftSAParity_CNF
Formal statement
namespace SemAC02
/-- **Proposition 8.3** (Alekseev–Gryaznov–Itsykson–Pitassi–Robere–Tzameret, *Hard Instances for Strong Semantic Proof
Systems*, manuscript (STOC 2027 submission), Proposition 8.3, p.63): for a gadget `g` as in §8.1,
if `F_n` is unsatisfiable, then `Lift_g(F_n)` is unsatisfiable: no assignment to the lifted
variables satisfies every circuit of `Lift_g(F_n)`.
**Formalization Note** The standing assumptions of §8.1 on `g` are `IsGadget d g` with
`d ≥ 2`. -/
theorem proposition_8_3_lift_unsat {d n m : ℕ} (hd : 2 ≤ d) (g : Circ (Fin m)) (hg : IsGadget d g)
(F : LiftSAParity.CNF (Fin n)) (hF : ¬ LiftSAParity.Satisfiable F) :
¬ ∃ X : Fin n × Fin m → Bool, ∀ A ∈ lift g F, A.eval X = true := 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), Proposition 8.3, p.63 (PDF p.65)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.