Theorem 6.1 — a sufficient condition for the canonical distribution to be fooling
OpenLiftSAParity.Supplement.theorem_6_1There is an absolute constant such that the following holds. Let be a CNF formula over blocks of variables, let , and let be the maximum number of clauses of whose variables all lie in some set of at most blocks. Suppose that the canonical family is a block -local distribution for . Suppose also that every blockwise partial assignment that falsifies no clause, when extended uniformly to any set of at most blocks, falsifies a clause with probability at most , where . Put
Then for all with :
- satisfies the first -fooling condition;
- if moreover , then is -fooling.
This is the paper's route from Bazzi's theorem (polylogarithmic independence fools CNFs) to fooling distributions; with Theorem 5.4 it gives the binary pigeonhole lower bound, Theorem 1.4.
Formalization Note is canonDist φ, is maxLocalClauses φ d, and the hypothesis on is UniformExtFalsifyBound φ d p. and are real powers, and is written . The constant is chosen once, before all other parameters.
Differences from the source:
- reading: "does not falsify any clause" and "falsifies a clause" for partial assignments → no clause whose variables all lie in the assigned blocks is falsified / some clause whose variables all lie in I × [ℓ] is falsified; reason: a partial assignment can falsify only a clause all of whose variables it assigns
- encoding: t ≤ r/10 → 10 * t ≤ r in ℕ; reason: equivalent for natural numbers
- encoding: Cl^t(A), the unique inclusion-minimal set → the intersection of all sets of blocks outside which A is t-safe; reason: equal for every nonempty affine A by the proof of Lemma 5.1
- generalization: integers n, ℓ ≥ 1 (§2, p.7) and "For d ≥ 1" (p.20) → n, ℓ, d : ℕ, including 0; reason: the statement keeps its meaning there; for d = 0, rt ≤ 0 and 10t ≤ r force t = 0 or I = ∅, where sampling is uniform and the bounds hold since ε ≥ 0; the Lean statement specializes to the printed one
import Mathlib import Definitions.Def_LiftSAParity_CNF import Definitions.Def_LiftSAParity_Supplement_IsFooling import Definitions.Def_LiftSAParity_Supplement_canonDist
namespace LiftSAParity
namespace Supplement
/-- **Theorem 6.1** (de Rezende–Engström–Shekhovtsov, *Lifting Sherali-Adams Degree to Unary
Sherali-Adams over Parities Size*, manuscript (sha256 cab5a032…), §6.1, p.20): "Let φ be a CNF
formula with m = the maximum number of clauses of φ whose variables all lie in some set of at most
d blocks. Let D^φ be a d-local distribution for φ. Suppose every blockwise partial assignment that
does not falsify any clause, when extended uniformly to any set of at most d blocks, falsifies a
clause with probability at most p < 1. For every r, t ∈ ℕ with rt ≤ d, D^φ satisfies the first
(r, t, ε)-fooling condition with ε = C m^{2.2} 2^{−√t/10} / (1 − p), where C > 0 is an absolute
constant. If also t ≤ r/10, then D^φ is (r, t, ε + 2^{−r/2})-fooling."
**Formalization Note** One absolute `C > 0`, chosen before every other parameter. `D^φ` is the
canonical family `canonDist φ`; "D^φ is a d-local distribution for φ" is
`IsBlockLocalDist φ d (canonDist φ)`. `m = maxLocalClauses φ d`; `m^{2.2}` and `2^{−√t/10}` are
real powers. `t ≤ r/10` is `10 t ≤ r` in `ℕ`. -/
theorem theorem_6_1 : ∃ C : ℝ, 0 < C ∧
∀ (n ℓ d : ℕ) (φ : CNF (Fin n × Fin ℓ)) (p : ℝ),
IsBlockLocalDist φ d (canonDist φ) → p < 1 → UniformExtFalsifyBound φ d p →
∀ r t : ℕ, r * t ≤ d →
FoolCond1 d r t
(C * (maxLocalClauses φ d : ℝ) ^ (2.2 : ℝ) * (2 : ℝ) ^ (-Real.sqrt t / 10) / (1 - p))
(canonDist φ) ∧
(10 * t ≤ r → IsFooling φ d r t
(C * (maxLocalClauses φ d : ℝ) ^ (2.2 : ℝ) * (2 : ℝ) ^ (-Real.sqrt t / 10) / (1 - p) +
(2 : ℝ) ^ (-(r : ℝ) / 2))
(canonDist φ)) := by sorry
end Supplement
end LiftSAParity