The proof
Source
Main.lean · 3532 lines · 157.6 kB
Showing the first 500 of 3532 lines. The whole file is 157.6 kB; download it to read the rest.
/- Source module Erdos624.Statement. -/
namespace Erdos624
def Statement : Prop :=
Filter.Tendsto
(fun n : ℕ => (_root_.Erdos624.H n : ℝ) - Real.logb 2 (n : ℝ))
Filter.atTop Filter.atTop
end Erdos624
/- Source module Erdos624.Basic. -/
/-!
The covering predicate used by the construction and its connection to the
unchanged Erdős 624 declaration in Formal Conjectures.
-/
namespace Erdos624.Disproof
open Finset Filter
variable {X C D : Type*}
/-- Every sufficiently large source contains a witness for every color. -/
def Covers (f : Finset X → C) (h : ℕ) : Prop :=
∀ Y : Finset X, h ≤ Y.card → ∀ c : C, ∃ A : Finset X, A ⊆ Y ∧ f A = c
theorem covers_mono {f : Finset X → C} {h k : ℕ}
(hf : Covers f h) (hhk : h ≤ k) : Covers f k := by
intro Y hY c
exact hf Y (hhk.trans hY) c
theorem covers_of_exact_size {f : Finset X → C} {h : ℕ}
(hf : ∀ Y : Finset X, Y.card = h → ∀ c : C,
∃ A : Finset X, A ⊆ Y ∧ f A = c) : Covers f h := by
intro Y hY c
obtain ⟨Z, hZY, hZ⟩ := Finset.exists_subset_card_eq hY
obtain ⟨A, hAZ, hA⟩ := hf Z hZ c
exact ⟨A, hAZ.trans hZY, hA⟩
theorem covers_comp {f : Finset X → C} {h : ℕ} (hf : Covers f h)
{g : C → D} (hg : Function.Surjective g) : Covers (g ∘ f) h := by
intro Y hY d
obtain ⟨c, rfl⟩ := hg d
obtain ⟨A, hAY, hA⟩ := hf Y hY c
exact ⟨A, hAY, congrArg g hA⟩
theorem covers_restrict {X' : Type*} {f : Finset X → C} {h : ℕ}
(hf : Covers f h) (e : X' ↪ X) : Covers (fun A => f (A.map e)) h := by
classical
intro Y hY c
obtain ⟨A, hAY, hA⟩ := hf (Y.map e) (by simpa using hY) c
let A' := Y.filter fun x => e x ∈ A
have hmap : A'.map e = A := by
ext x
simp only [Finset.mem_map, A', Finset.mem_filter]
constructor
· rintro ⟨a, ⟨_, ha⟩, rfl⟩
exact ha
· intro hx
obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp (hAY hx)
exact ⟨a, ⟨ha, hx⟩, rfl⟩
exact ⟨A', Finset.filter_subset _ _, by simpa [hmap] using hA⟩
theorem existsEventuallySurjective_iff_covers (N h : ℕ) :
_root_.Erdos624.ExistsEventuallySurjective N h ↔
∃ f : Finset (Fin N) → Fin N, Covers f h := by
classical
unfold _root_.Erdos624.ExistsEventuallySurjective Covers
constructor
· rintro ⟨f, hf⟩
refine ⟨f, ?_⟩
intro Y hY c
have hc : c ∈ Y.powerset.image f := by rw [hf Y hY]; exact Finset.mem_univ c
obtain ⟨A, hA, hAc⟩ := Finset.mem_image.mp hc
exact ⟨A, Finset.mem_powerset.mp hA, hAc⟩
· rintro ⟨f, hf⟩
refine ⟨f, ?_⟩
intro Y hY
apply Finset.eq_univ_of_forall
intro c
obtain ⟨A, hAY, hAc⟩ := hf Y hY c
exact Finset.mem_image.mpr ⟨A, Finset.mem_powerset.mpr hAY, hAc⟩
theorem H_le_of_cover {N h : ℕ} (hN : 0 < N)
(hf : ∃ f : Finset (Fin N) → Fin N, Covers f h) : _root_.Erdos624.H N ≤ h := by
unfold _root_.Erdos624.H
simp only [hN, ↓reduceIte]
exact csInf_le (OrderBot.bddBelow _) ((existsEventuallySurjective_iff_covers N h).mpr hf)
/-- A constant upper gap on all sufficiently large multiples of 100 suffices. -/
theorem not_tendsto_of_eventual_power_cover (C : ℕ)
(hc : ∃ D : ℕ, ∀ d : ℕ, D ≤ d → 100 ∣ d →
∃ f : Finset (Fin (2 ^ d)) → Fin (2 ^ d), Covers f (d + C)) :
¬ Filter.Tendsto
(fun N : ℕ => (_root_.Erdos624.H N : ℝ) - Real.logb 2 (N : ℝ))
Filter.atTop Filter.atTop := by
intro hlim
obtain ⟨D, hD⟩ := hc
have hev : ∀ᶠ N : ℕ in Filter.atTop,
(C : ℝ) + 1 ≤ (_root_.Erdos624.H N : ℝ) - Real.logb 2 (N : ℝ) :=
hlim.eventually (Filter.eventually_ge_atTop ((C : ℝ) + 1))
obtain ⟨M, hM⟩ := Filter.eventually_atTop.mp hev
let d := 100 * (D + M + 1)
have hDd : D ≤ d := by dsimp [d]; omega
have hMd : M ≤ d := by dsimp [d]; omega
have hddiv : 100 ∣ d := ⟨D + M + 1, rfl⟩
have hN : 0 < (2 : ℕ) ^ d := by positivity
have hH := H_le_of_cover hN (hD d hDd hddiv)
have hlarge : M ≤ (2 : ℕ) ^ d := hMd.trans (Nat.le_of_lt (Nat.lt_two_pow_self))
have hlog : Real.logb 2 (((2 : ℕ) ^ d : ℕ) : ℝ) = (d : ℝ) := by
rw [Nat.cast_pow, Nat.cast_ofNat, Real.logb_pow]
norm_num [Real.logb_self_eq_one]
have hupper : (_root_.Erdos624.H (2 ^ d) : ℝ) ≤ (d : ℝ) + C := by exact_mod_cast hH
have hlower := hM (2 ^ d) hlarge
rw [hlog] at hlower
linarith
end Erdos624.Disproof
/- Source module Erdos624.Linear. -/
namespace Erdos624.Disproof
open Module
section Kernels
variable {F V A B : Type*} [Field F]
[AddCommGroup V] [Module F V]
[AddCommGroup A] [Module F A]
[AddCommGroup B] [Module F B]
/-- Two proper linear kernels cannot cover the whole domain. -/
theorem zero_or_zero_of_kernel_cover (u : V →ₗ[F] A) (v : V →ₗ[F] B)
(h : ∀ w : V, u w = 0 ∨ v w = 0) : u = 0 ∨ v = 0 := by
by_cases hu : u = 0
· exact Or.inl hu
right
apply LinearMap.ext
intro y
change v y = 0
by_contra hy
obtain ⟨x, hx⟩ : ∃ x : V, u x ≠ 0 := by
by_contra! hn
apply hu
ext x
exact hn x
have hvx : v x = 0 := (h x).resolve_left hx
have huy : u y = 0 := (h y).resolve_right hy
have hsum := h (x + y)
rw [map_add, huy, add_zero, map_add, hvx, zero_add] at hsum
exact hsum.elim hx hy
/-- The preceding dichotomy also holds after restricting to a subspace. -/
theorem vanishes_on_subspace_or (K : Submodule F V)
(u : V →ₗ[F] A) (v : V →ₗ[F] B)
(h : ∀ w ∈ K, u w = 0 ∨ v w = 0) :
(∀ w ∈ K, u w = 0) ∨ (∀ w ∈ K, v w = 0) := by
have h' := zero_or_zero_of_kernel_cover (u.comp K.subtype) (v.comp K.subtype)
(fun w => h w w.property)
rcases h' with hu | hv
· left
intro w hw
exact congrArg (fun f : K →ₗ[F] A => f ⟨w, hw⟩) hu
· right
intro w hw
exact congrArg (fun f : K →ₗ[F] B => f ⟨w, hw⟩) hv
variable [FiniteDimensional F V] [FiniteDimensional F A] [FiniteDimensional F B]
/-- Counting the parity equation and the two field-valued ratio equations. -/
theorem three_constraints_dimension (parity : V →ₗ[F] F)
(outer : V →ₗ[F] A) (inner : V →ₗ[F] B) :
finrank F V ≤ finrank F (LinearMap.ker (parity.prod (outer.prod inner))) +
1 + finrank F A + finrank F B := by
have hrank := (parity.prod (outer.prod inner)).finrank_range_add_finrank_ker
have hle := (LinearMap.range (parity.prod (outer.prod inner))).finrank_le
simp only [Module.finrank_prod, Module.finrank_self] at hle
omega
theorem sixteen_le_constraint_kernel (parity : V →ₗ[F] F)
(outer : V →ₗ[F] A) (inner : V →ₗ[F] B)
(hdim : 1 + finrank F A + finrank F B + 16 ≤ finrank F V) :
16 ≤ finrank F (LinearMap.ker (parity.prod (outer.prod inner))) := by
have := three_constraints_dimension parity outer inner
omega
omit [FiniteDimensional F V] [FiniteDimensional F A] in
theorem finrank_inf_ker (K : Submodule F V) (f : V →ₗ[F] A) :
finrank F (K ⊓ LinearMap.ker f : Submodule F V) =
finrank F (LinearMap.ker (f.comp K.subtype)) := by
let L := LinearMap.ker (f.comp K.subtype)
let g := K.subtype.comp L.subtype
have hg : Function.Injective g := K.subtype_injective.comp L.subtype_injective
have hrange : LinearMap.range g = K ⊓ LinearMap.ker f := by
ext v
constructor
· rintro ⟨w, rfl⟩
exact ⟨w.val.property, w.property⟩
· rintro ⟨hvK, hvf⟩
exact ⟨⟨⟨v, hvK⟩, hvf⟩, rfl⟩
rw [← hrange, LinearMap.finrank_range_of_inj hg]
/-- Imposing a linear equation costs at most the dimension of its target. -/
theorem finrank_le_inf_ker_add (K : Submodule F V) (f : V →ₗ[F] A) :
finrank F K ≤ finrank F (K ⊓ LinearMap.ker f : Submodule F V) + finrank F A := by
have hnull := (f.comp K.subtype).finrank_range_add_finrank_ker
have hrange := (LinearMap.range (f.comp K.subtype)).finrank_le
rw [finrank_inf_ker K f]
omega
end Kernels
section Labels
variable {I W : Type*} [Fintype I] [AddCommGroup W] [Module (ZMod 2) W]
/-- Point labels extend uniquely to binary linear sums. -/
noncomputable def labelMap (labels : I → W) : (I → ZMod 2) →ₗ[ZMod 2] W :=
Fintype.linearCombination (ZMod 2) labels
theorem labelMap_apply (labels : I → W) (w : I → ZMod 2) :
labelMap labels w = ∑ i, w i • labels i :=
Fintype.linearCombination_apply _ _ _
end Labels
end Erdos624.Disproof
/- Source module Erdos624.Counting. -/
namespace Erdos624.Disproof
open Finset
variable {I Ω : Type*} [Fintype I] [Fintype Ω] [DecidableEq Ω]
/-- A finite union bound, stated directly in cardinalities. -/
theorem exists_avoiding_events (bad : I → Finset Ω)
(h : ∑ i, (bad i).card < Fintype.card Ω) :
∃ x : Ω, ∀ i, x ∉ bad i := by
classical
by_contra! hn
have hcover : Finset.univ.biUnion bad = (Finset.univ : Finset Ω) := by
apply Finset.eq_univ_of_forall
intro x
obtain ⟨i, hi⟩ := hn x
exact Finset.mem_biUnion.mpr ⟨i, Finset.mem_univ _, hi⟩
have hcard := Finset.card_biUnion_le (s := (Finset.univ : Finset I)) (t := bad)
rw [hcover, Finset.card_univ] at hcard
exact (not_lt_of_ge hcard) h
/-- Independent coordinate constraints multiply their numbers of choices. -/
theorem card_coordinate_constraints [DecidableEq I] {A : I → Type*} [∀ i, Fintype (A i)]
(bad : ∀ i, Finset (A i)) :
(Fintype.piFinset bad).card = ∏ i, (bad i).card :=
Fintype.card_piFinset bad
/-- A small average cost on the whole space leaves a low-cost point outside a small bad set. -/
theorem exists_outside_with_small_value (bad : Finset Ω) (cost : Ω → ℕ) (a b : ℕ)
(h : a * (∑ x, cost x) < b * (Fintype.card Ω - bad.card)) :
∃ x, x ∉ bad ∧ a * cost x < b := by
classical
by_contra! hn
let good := (Finset.univ : Finset Ω) \ bad
have hpoint : ∀ x ∈ good, b ≤ a * cost x := by
intro x hx
exact hn x (Finset.mem_sdiff.mp hx).2
have hgood : good.card = Fintype.card Ω - bad.card := by
simp [good, Finset.card_sdiff_of_subset (Finset.subset_univ bad)]
have hle : b * (Fintype.card Ω - bad.card) ≤ a * (∑ x, cost x) := by
calc
b * (Fintype.card Ω - bad.card) = ∑ _x ∈ good, b := by simp [hgood, Nat.mul_comm]
_ ≤ ∑ x ∈ good, a * cost x := Finset.sum_le_sum hpoint
_ = a * (∑ x ∈ good, cost x) := (Finset.mul_sum _ _ _).symm
_ ≤ a * (∑ x, cost x) := Nat.mul_le_mul_left a
(Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _) (by simp))
exact (not_lt_of_ge hle) h
end Erdos624.Disproof
/- Source module Erdos624.Support. -/
namespace Erdos624.Disproof
open Finset
theorem binary_ne_zero_iff_eq_one (z : ZMod 2) : z ≠ 0 ↔ z = 1 := by
classical
fin_cases z
· change (0 : ZMod 2) ≠ 0 ↔ (0 : ZMod 2) = 1
simp
· change (1 : ZMod 2) ≠ 0 ↔ (1 : ZMod 2) = 1
simp
theorem binary_eq_zero_or_one (z : ZMod 2) : z = 0 ∨ z = 1 := by
by_cases hz : z = 0
· exact Or.inl hz
· exact Or.inr ((binary_ne_zero_iff_eq_one z).mp hz)
section CoordinateCount
variable {G : Type*} [AddCommGroup G] [Fintype G]
/-- Each binary linear coordinate is active on at most half the vectors. -/
theorem binary_hom_nonzero_card_le (f : G →+ ZMod 2) (q : ℕ)
(hcard : Fintype.card G ≤ 2 * q) :
(Finset.univ.filter fun x : G => f x ≠ 0).card ≤ q := by
classical
by_cases hf : ∀ x, f x = 0
· simp [hf]
obtain ⟨x, hx⟩ := not_forall.mp hf
have hx1 : f x = 1 := (binary_ne_zero_iff_eq_one _).mp hx
have heq := AddMonoidHom.card_fiber_eq_of_mem_range f
(show (0 : ZMod 2) ∈ Set.range f from ⟨0, map_zero f⟩)
(show (1 : ZMod 2) ∈ Set.range f from ⟨x, hx1⟩)
have hpartition := Finset.card_filter_add_card_filter_not
(s := (Finset.univ : Finset G)) (p := fun x => f x = 0)
have hfilter : (Finset.univ.filter fun x : G => f x ≠ 0) =
(Finset.univ.filter fun x : G => f x = 1) := by
ext x
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
exact binary_ne_zero_iff_eq_one _
rw [← hfilter] at heq
simp only [Finset.card_univ] at hpartition
change (Finset.univ.filter fun x : G => f x = 0).card +
(Finset.univ.filter fun x : G => f x ≠ 0).card = Fintype.card G at hpartition
omega
end CoordinateCount
section ShortVector
variable {I : Type*} [Fintype I]
def vectorSupport (v : I → ZMod 2) : Finset I :=
Finset.univ.filter fun i => v i ≠ 0
theorem mem_vectorSupport {v : I → ZMod 2} {i : I} :
i ∈ vectorSupport v ↔ v i ≠ 0 := by
simp [vectorSupport]
theorem vectorSupport_nonempty_iff (v : I → ZMod 2) : (vectorSupport v).Nonempty ↔ v ≠ 0 := by
classical
constructor
· rintro ⟨i, hi⟩ hv
have hne := mem_vectorSupport.mp hi
apply hne
simp [hv]
· intro hv
have hex : ∃ i, v i ≠ 0 := by
by_contra! h
exact hv (funext h)
obtain ⟨i, hi⟩ := hex
exact ⟨i, mem_vectorSupport.mpr hi⟩
noncomputable def subspaceSupport (K : Submodule (ZMod 2) (I → ZMod 2)) : Finset I := by
classical
exact Finset.univ.filter fun i => ∃ v ∈ K, v i ≠ 0
theorem mem_subspaceSupport {K : Submodule (ZMod 2) (I → ZMod 2)} {i : I} :
i ∈ subspaceSupport K ↔ ∃ v ∈ K, v i ≠ 0 := by
classical
simp [subspaceSupport]
theorem subspaceSupport_mono {K L : Submodule (ZMod 2) (I → ZMod 2)} (h : K ≤ L) :
subspaceSupport K ⊆ subspaceSupport L := by
classical
intro i hi
obtain ⟨_, v, hv, hvi⟩ := Finset.mem_filter.mp hi
exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, v, h hv, hvi⟩
/-- A five-dimensional binary subspace contains a short nonzero vector. -/
theorem short_vector_of_card_32 (K : Submodule (ZMod 2) (I → ZMod 2))
[Fintype K] (hK : Fintype.card K = 32) :
∃ v : K, v ≠ 0 ∧ 31 * (vectorSupport v.val).card ≤ 16 * Fintype.card I := by
letI : CommRing (ZMod 2) := ZMod.commRing 2
letI : Ring (ZMod 2) := (ZMod.commRing 2).toRing
letI : Semiring (ZMod 2) := (ZMod.commRing 2).toSemiring
letI : AddCommGroup (ZMod 2) := (ZMod.commRing 2).toAddCommGroup
letI : AddCommMonoid (ZMod 2) := (ZMod.commRing 2).toAddCommMonoid
classical
have hcoord (i : I) :
(Finset.univ.filter fun v : K => v.val i ≠ 0).card ≤ 16 := by
exact binary_hom_nonzero_card_le
(((LinearMap.proj i).comp K.subtype).toAddMonoidHom) 16 (by omega)
have hsum : ∑ v : K, (vectorSupport v.val).card ≤ 16 * Fintype.card I := by
calc
∑ v : K, (vectorSupport v.val).card =
∑ i : I, (Finset.univ.filter fun v : K => v.val i ≠ 0).card := by
simp only [vectorSupport, Finset.card_eq_sum_ones, Finset.sum_filter]
exact Finset.sum_comm
_ ≤ ∑ _ : I, 16 := Finset.sum_le_sum fun i _ => hcoord i
_ = 16 * Fintype.card I := by simp [Nat.mul_comm]
let S : Finset K := Finset.univ.erase 0
have hS : S.card = 31 := by simp [S, hK]
have hSne : S.Nonempty := Finset.card_pos.mp (by omega)
have hsumS : ∑ v ∈ S, (vectorSupport v.val).card ≤ 16 * Fintype.card I := by
apply le_trans _ hsum
exact Finset.sum_le_sum_of_subset_of_nonneg (Finset.erase_subset _ _) (by simp)
obtain ⟨v, hv, hsmall⟩ := Finset.exists_le_of_sum_le hSne
(show ∑ v ∈ S, 31 * (vectorSupport v.val).card ≤
∑ _v ∈ S, 16 * Fintype.card I by
rw [← Finset.mul_sum]
simp only [Finset.sum_const, hS, smul_eq_mul]
exact Nat.mul_le_mul_left 31 hsumS)
exact ⟨v, (Finset.mem_erase.mp hv).1, hsmall⟩
/-- The short vector estimate only needs a lower bound on the dimension. -/
theorem short_vector_of_finrank_ge_five (K : Submodule (ZMod 2) (I → ZMod 2))
(hK : 5 ≤ Module.finrank (ZMod 2) K) :
∃ v : K, v ≠ 0 ∧ 31 * (vectorSupport v.val).card ≤ 16 * Fintype.card I := by
letI : CommRing (ZMod 2) := ZMod.commRing 2
letI : Ring (ZMod 2) := (ZMod.commRing 2).toRing
letI : Semiring (ZMod 2) := (ZMod.commRing 2).toSemiring
letI : AddCommGroup (ZMod 2) := (ZMod.commRing 2).toAddCommGroup
letI : AddCommMonoid (ZMod 2) := (ZMod.commRing 2).toAddCommMonoid
classical
have hdim : Module.finrank (ZMod 2) (Fin 5 → ZMod 2) ≤
Module.finrank (ZMod 2) K := by simpa using hK
obtain ⟨e, he⟩ := finrank_le_iff_exists_linearMap.mp hdim
let f := K.subtype.comp e
have hf : Function.Injective f := K.subtype_injective.comp he
let L := LinearMap.range f
let : Fintype L := Fintype.ofFinite L
have hLdim : Module.finrank (ZMod 2) L = 5 := by
simpa [L] using LinearMap.finrank_range_of_inj hf
have hLcard : Fintype.card L = 32 := by
rw [Module.card_eq_pow_finrank (K := ZMod 2), hLdim]
norm_num
obtain ⟨v, hv, hsmall⟩ := short_vector_of_card_32 L hLcard
have hvK : v.val ∈ K := by
obtain ⟨w, hw⟩ := v.property
rw [← hw]
exact (e w).property
refine ⟨⟨v.val, hvK⟩, ?_, hsmall⟩
intro hz
apply hv
apply Subtype.ext
exact congrArg (fun z : K => z.val) hz
end ShortVector
end Erdos624.Disproof
/- Source module Erdos624.Probability. -/
namespace Erdos624.Disproof
open Finset
section UnionBound
variable {Ω R : Type*} [Fintype Ω] [Fintype R]
theorem weighted_union_bound (w : Ω → ℝ) (hw : ∀ x, 0 ≤ w x)
(event : Finset Ω) (bad : R → Finset Ω)
(hcover : ∀ x ∈ event, ∃ r, x ∈ bad r) :
∑ x ∈ event, w x ≤ ∑ r, ∑ x ∈ bad r, w x := by
classical
have hpoint (x : Ω) : (if x ∈ event then w x else 0) ≤
∑ r, if x ∈ bad r then w x else 0 := by
by_cases hx : x ∈ event
· obtain ⟨r, hr⟩ := hcover x hx
rw [ite_eq_left hx]
calc
w x = if x ∈ bad r then w x else 0 := by simp [hr]
_ ≤ ∑ s, if x ∈ bad s then w x else 0 :=
Finset.single_le_sum (f := fun s => if x ∈ bad s then w x else 0)
(fun s _ => by split <;> simp_all) (Finset.mem_univ r)
· rw [ite_eq_right hx]
exact Finset.sum_nonneg fun r _ => by split <;> simp_all
have hsum := Finset.sum_le_sum (fun x (_ : x ∈ Finset.univ) => hpoint x)
rw [Finset.sum_comm] at hsum
simpa only [← Finset.sum_filter, Finset.filter_univ_mem] using hsum
/-- The union bound for nonnegative weights on a finite sample space. -/
theorem exists_avoiding_weighted_events (w : Ω → ℝ) (hw : ∀ x, 0 ≤ w x)
(bad : R → Finset Ω)
(h : ∑ r, ∑ x ∈ bad r, w x < ∑ x, w x) :
∃ x, ∀ r, x ∉ bad r := by
classical
by_contra! hn
have hpoint (x : Ω) : w x ≤ ∑ r, if x ∈ bad r then w x else 0 := by
obtain ⟨r, hr⟩ := hn x
calc
w x = if x ∈ bad r then w x else 0 := by simp [hr]
_ ≤ ∑ s, if x ∈ bad s then w x else 0 :=
Finset.single_le_sum (f := fun s => if x ∈ bad s then w x else 0)
(fun s _ => by split <;> simp_all) (Finset.mem_univ r)
have hle : ∑ x, w x ≤ ∑ r, ∑ x ∈ bad r, w x := by
calc
∑ x, w x ≤ ∑ x, ∑ r, if x ∈ bad r then w x else 0 :=
Finset.sum_le_sum fun x _ => hpoint x
_ = ∑ r, ∑ x ∈ bad r, w x := by
rw [Finset.sum_comm]
congr 1 with rProvenance