The two cover lemmas
Definitionsgl_cover_lemmasThe two cover lemmas — pure finite combinatorics on the Boolean cube, and the last mathematical content standing between the proven Lautemann bridge and .
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 points; if that is below , 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 precisely when every one of its translations sends outside the set, so the families failing at number out of . Summing over the points: if , 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 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.
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