Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1: random logarithmic-width CNFs are unsatisfiable boundary expanders

Proved
SemAC02.Supplement.lemma_7_1_random_logwidth_expansion

by Henry Yuen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

expansionproof-complexityrandom-cnf

Put ℓ=⌈log⁡2n⌉\ell=\lceil\log_2 n\rceilℓ=⌈log2​n⌉ and m=n2ℓm=n2^\ellm=n2ℓ. Sample mmm clauses independently and uniformly, with repetition, from the clauses of width exactly ℓ\ellℓ on distinct variables among nnn Boolean variables. Let FnF_nFn​ be their conjunction. For a set JJJ of clause indices, write N(J)N(J)N(J) for its neighboring variables and ∂(J)\partial(J)∂(J) for the variables occurring in exactly one of the indexed clauses.

There is an absolute constant η>0\eta>0η>0 such that, with probability tending to one as n→∞n\to\inftyn→∞, FnF_nFn​ is unsatisfiable and simultaneously every nonempty set JJJ of at most ⌊ηn/ℓ⌋\lfloor\eta n/\ell\rfloor⌊ηn/ℓ⌋ clause indices satisfies

∣N(J)∣≥3ℓ4∣J∣,∣∂(J)∣≥ℓ2∣J∣.|N(J)|\ge\frac{3\ell}{4}|J|,\qquad |\partial(J)|\ge\frac{\ell}{2}|J|.∣N(J)∣≥43ℓ​∣J∣,∣∂(J)∣≥2ℓ​∣J∣.

This supplies the common expansion event used to prove the bounded-bottom-degree lower bounds for random logarithmic-width CNFs.

Formalization Note The graph keeps the sampled clause indices, so repeated clauses remain distinct left vertices. The CNF itself is the set of sampled clauses, which preserves satisfiability. Neighborhoods and boundaries are written directly as finite sets. The ceiling logarithm is Nat.clog, and probability is the mission's uniform counting probability.

Preamble
import Mathlib
import Definitions.Def_LiftSAParity_CNF
import Definitions.Def_SemAC02_Supplement_randCNF
open Filter Topology LiftSAParity SemAC02.Supplement
Formal statement
theorem SemAC02.Supplement.lemma_7_1_random_logwidth_expansion :
    ∃ η : ℝ, 0 < η ∧ Tendsto (fun n : ℕ => uprob
      (fun ω : Fin (n*2^Nat.clog 2 n) → WClause n (Nat.clog 2 n) =>
        ¬ Satisfiable (seqCNF ω) ∧ ∀ J : Finset (Fin (n*2^Nat.clog 2 n)),
          J.Nonempty → J.card ≤ ⌊η*n/(Nat.clog 2 n : ℝ)⌋₊ →
          (3 : ℝ)*(Nat.clog 2 n)*J.card/4 ≤
              ((J.biUnion (fun j => (ω j).1.image Prod.fst)).card : ℝ) ∧
          ((Nat.clog 2 n : ℝ)/2)*J.card ≤
              ((Finset.univ.filter (fun v : Fin n =>
                (J.filter (fun j => v∈(ω j).1.image Prod.fst)).card=1)).card : ℝ))) atTop (𝓝 1) := by sorry
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, Lemma 7.1, printed p.51 (PDF p.53), with proof in Appendix C, printed p.72 (PDF p.74), equations (55)–(56). https://www.doc.ic.ac.uk/~itzamere/Reslin_Simplification.pdf. Verified against the public manuscript saved in sources/Hard_Instances_Semantic.pdf; public and mission-pinned manuscript hashes differ as recorded in README.md.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me