Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The two cover lemmas

Definition
sgl_cover_lemmas

by Henry Yuen · Jul 27, 2026 · Mathlib c5ea003 (Lean v4.30.0)

combinatoricscomplexity-theorytheoretical-computer-science

The two cover lemmas — pure finite combinatorics on the Boolean cube, and the last mathematical content standing between the proven Lautemann bridge and Σ2p\Sigma_2^pΣ2p​.

The obstruction. Too few translations of a small set cannot cover the cube. Each translate has the set's cardinality (translation by XOR is a bijection), so shifts of them cover at most shifts⋅∣set∣\mathrm{shifts} \cdot |{\rm set}|shifts⋅∣set∣ points; if that is below 2n2^n2n, some point escapes. Pigeonhole, via the union bound on a biUnion.

The existence. If the set is large enough, some family of translations does cover — by the probabilistic method, done as exact counting. A family misses a fixed point xxx precisely when every one of its translations sends xxx outside the set, so the families failing at xxx number (N−∣set∣)shifts(N - |{\rm set}|)^{\rm shifts}(N−∣set∣)shifts out of NshiftsN^{\rm shifts}Nshifts. Summing over the NNN points: if N(N−∣set∣)shifts<NshiftsN(N-|{\rm set}|)^{\rm shifts} < N^{\rm shifts}N(N−∣set∣)shifts<Nshifts, the failing families cannot exhaust the space, so some family fails at no point and therefore covers. The counting is a piFinset cardinality — the failing families at xxx are exactly the functions into the complement of a translate.

With these, the summit step amplified_verifier_implies_sigma_two reduces to its _of_cover_lemmas form with both hypotheses discharged.

Definition code
import Definitions.Def_sgl_lautemann_bridge

/-!
# The two cover lemmas

Both are pure finite combinatorics on `BitString n`, and both are hypotheses
of the mission's summit step — they are what stands between the proven
Lautemann bridge and `InSigmaTwoP`.

* **The obstruction.** Too few translations of a small set cannot cover the
  cube: each translate has the set's cardinality, so `shifts` of them cover
  at most `shifts * setCard set` points.
* **The existence.** If the set is large enough, some family of translations
  does cover — by the probabilistic method, counting the families that miss a
  given point.

`xor` is an involution in each argument, which is what turns "covered" into a
statement about translates and lets the counting go through.
-/

namespace SipserGacsLautemann

variable {n : Nat}

@[simp] theorem xor_xor_cancel (x y : BitString n) : xor (xor x y) y = x := by
  funext i
  simp [xor]

theorem xor_comm (x y : BitString n) : xor x y = xor y x := by
  funext i
  show (x i != y i) = (y i != x i)
  cases x i <;> cases y i <;> rfl

/-- Translating is a bijection of the cube. -/
theorem xor_injective (y : BitString n) : Function.Injective (fun x => xor x y) := by
  intro a b hab
  have := congrArg (fun z => xor z y) hab
  simpa using this


/-! ## The obstruction -/

/-- A translate has the set's cardinality. -/
theorem card_translate (set : BitString n → Prop) [DecidablePred set]
    (y : BitString n) :
    (Finset.univ.filter (fun x : BitString n => set (xor x y))).card =
      setCard set := by
  classical
  rw [setCard]
  refine Finset.card_bij (fun x _ => xor x y) ?_ ?_ ?_
  · intro a ha
    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha ⊢
    exact ha
  · intro a ha b hb hab
    exact xor_injective y hab
  · intro b hb
    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb ⊢
    exact ⟨xor b y, by simpa using hb, by simp⟩

set_option maxHeartbeats 1000000 in
/-- **Too few translations of a small set cannot cover the cube.** -/
theorem smallCoverObstruction {n shifts : Nat} (set : BitString n → Prop)
    [DecidablePred set]
    (hsmall : shifts * setCard set < Fintype.card (BitString n))
    (translations : Fin shifts → BitString n) :
    ¬ shiftedCover set translations := by
  classical
  intro hcover
  -- every point lies in some translate, so the translates cover the cube
  have hsub : (Finset.univ : Finset (BitString n)) ⊆
      Finset.univ.biUnion (fun i : Fin shifts =>
        Finset.univ.filter (fun x : BitString n => set (xor x (translations i)))) := by
    intro x _
    obtain ⟨i, hi⟩ := hcover x
    exact Finset.mem_biUnion.mpr ⟨i, Finset.mem_univ i,
      Finset.mem_filter.mpr ⟨Finset.mem_univ x, hi⟩⟩
  have hcard := Finset.card_le_card hsub
  have hbound := Finset.card_biUnion_le
    (s := (Finset.univ : Finset (Fin shifts)))
    (t := fun i : Fin shifts =>
      Finset.univ.filter (fun x : BitString n => set (xor x (translations i))))
  have hsum : (Finset.univ : Finset (Fin shifts)).sum
      (fun i => (Finset.univ.filter
        (fun x : BitString n => set (xor x (translations i)))).card) =
      shifts * setCard set := by
    rw [Finset.sum_congr rfl (fun i _ => card_translate set (translations i))]
    simp [Finset.sum_const, mul_comm]
  rw [hsum] at hbound
  have hfull : (Finset.univ : Finset (BitString n)).card =
      Fintype.card (BitString n) := rfl
  omega


/-! ## The existence

Counting families of translations that fail.  A family misses a point `x`
exactly when every translation sends it outside the set, so the failing
families for a fixed `x` number `(N - |set|)^shifts` out of `N^shifts`.
Summing over the `N` points, if `N * (N - |set|)^shifts < N^shifts` some
family fails for no point — that family covers.
-/

/-- Families of translations missing a fixed point. -/
theorem card_missing (set : BitString n → Prop) [DecidablePred set]
    (shifts : Nat) (x : BitString n) :
    (Finset.univ.filter (fun f : Fin shifts → BitString n =>
        ∀ i, ¬ set (xor x (f i)))).card =
      (Fintype.card (BitString n) - setCard set) ^ shifts := by
  classical
  have hpi : (Finset.univ.filter (fun f : Fin shifts → BitString n =>
      ∀ i, ¬ set (xor x (f i)))) =
      Fintype.piFinset (fun _ : Fin shifts =>
        Finset.univ.filter (fun y : BitString n => ¬ set (xor x y))) := by
    ext f
    simp [Fintype.mem_piFinset]
  rw [hpi, Fintype.card_piFinset]
  have hone : (Finset.univ.filter (fun y : BitString n =>
      ¬ set (xor x y))).card =
      Fintype.card (BitString n) - setCard set := by
    have hcompl : (Finset.univ.filter (fun y : BitString n =>
        ¬ set (xor x y))) =
        (Finset.univ.filter (fun y : BitString n => set (xor x y)))ᶜ := by
      ext y
      simp
    rw [hcompl, Finset.card_compl]
    congr 1
    have := card_translate set x
    have hxc : (Finset.univ.filter (fun y : BitString n => set (xor x y))) =
        (Finset.univ.filter (fun y : BitString n => set (xor y x))) := by
      ext y
      simp [xor_comm]
    rw [hxc]
    exact card_translate set x
  simp [hone]

set_option maxHeartbeats 1000000 in
/-- **A large enough set is covered by some family of translations.** -/
theorem largeCoverExistence {n shifts : Nat} (set : BitString n → Prop)
    [DecidablePred set]
    (hlarge : Fintype.card (BitString n) *
        (Fintype.card (BitString n) - setCard set) ^ shifts <
      (Fintype.card (BitString n)) ^ shifts) :
    ∃ translations : Fin shifts → BitString n, shiftedCover set translations := by
  classical
  by_contra hno
  push_neg at hno
  -- every family fails at some point
  have hfail : ∀ f : Fin shifts → BitString n,
      ∃ x : BitString n, ∀ i, ¬ set (xor x (f i)) := by
    intro f
    have := hno f
    rw [shiftedCover] at this
    push_neg at this
    exact this
  -- so the families are covered by the per-point failing sets
  have hsub : (Finset.univ : Finset (Fin shifts → BitString n)) ⊆
      Finset.univ.biUnion (fun x : BitString n =>
        Finset.univ.filter (fun f : Fin shifts → BitString n =>
          ∀ i, ¬ set (xor x (f i)))) := by
    intro f _
    obtain ⟨x, hx⟩ := hfail f
    exact Finset.mem_biUnion.mpr ⟨x, Finset.mem_univ x,
      Finset.mem_filter.mpr ⟨Finset.mem_univ f, hx⟩⟩
  have hcard := Finset.card_le_card hsub
  have hbound := Finset.card_biUnion_le
    (s := (Finset.univ : Finset (BitString n)))
    (t := fun x : BitString n =>
      Finset.univ.filter (fun f : Fin shifts → BitString n =>
        ∀ i, ¬ set (xor x (f i))))
  have hsum : (Finset.univ : Finset (BitString n)).sum
      (fun x => (Finset.univ.filter (fun f : Fin shifts → BitString n =>
        ∀ i, ¬ set (xor x (f i)))).card) =
      Fintype.card (BitString n) *
        (Fintype.card (BitString n) - setCard set) ^ shifts := by
    rw [Finset.sum_congr rfl (fun x _ => card_missing set shifts x)]
    simp [Finset.sum_const, Finset.card_univ]
  rw [hsum] at hbound
  have hfull : (Finset.univ : Finset (Fin shifts → BitString n)).card =
      (Fintype.card (BitString n)) ^ shifts := by
    rw [Finset.card_univ, Fintype.card_fun]
    simp
  omega

end SipserGacsLautemann
Source
Combinatorial cover lemmas for the Lautemann argument; builds on Def_sgl_lautemann_bridge.

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