Numerical bounds for Szemerédi Regularity Lemma

This file gathers the numerical facts required by the proof of Szemerédi's regularity lemma.

This entire file is internal to the proof of Szemerédi Regularity Lemma.

Main declarations

• SzemerediRegularity.stepBound: During the inductive step, a partition of size n is blown to size at most stepBound n.
• SzemerediRegularity.initialBound: The size of the partition we start the induction with.
• SzemerediRegularity.bound: The upper bound on the size of the partition produced by our version of Szemerédi's regularity lemma.

References

Yaël Dillies, Bhavik Mehta, Formalising Szemerédi’s Regularity Lemma in Lean

def SzemerediRegularity.stepBound (n : ℕ) : ℕ

Auxiliary function for Szemerédi's regularity lemma. Blowing up a partition of size n during the induction results in a partition of size at most stepBound n.

Equations

• SzemerediRegularity.stepBound n = n * 4 ^ n

theorem SzemerediRegularity.le_stepBound : id ≤ stepBound

theorem SzemerediRegularity.stepBound_mono : Monotone stepBound

theorem SzemerediRegularity.stepBound_pos_iff {n : ℕ} : 0 < stepBound n ↔ 0 < n

theorem SzemerediRegularity.stepBound_pos {n : ℕ} : 0 < n → 0 < stepBound n

Alias of the reverse direction of SzemerediRegularity.stepBound_pos_iff.

theorem SzemerediRegularity.coe_stepBound {α : Type u_1} [Semiring α] (n : ℕ) : ↑(stepBound n) = ↑n * 4 ^ n

def SzemerediRegularity.Positivity.tacticSz_positivity : Lean.ParserDescr

Local extension for the positivity tactic: A few facts that are needed many times for the proof of Szemerédi's regularity lemma.

Equations

• SzemerediRegularity.Positivity.tacticSz_positivity = Lean.ParserDescr.node `SzemerediRegularity.Positivity.tacticSz_positivity 1024 (Lean.ParserDescr.nonReservedSymbol "sz_positivity" false)

theorem SzemerediRegularity.m_pos {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} [Nonempty α] (hPα : P.parts.card * 16 ^ P.parts.card ≤ Fintype.card α) : 0 < Fintype.card α / stepBound P.parts.card

theorem SzemerediRegularity.coe_m_add_one_pos {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} : 0 < ↑(Fintype.card α / stepBound P.parts.card) + 1

theorem SzemerediRegularity.one_le_m_coe {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} [Nonempty α] (hPα : P.parts.card * 16 ^ P.parts.card ≤ Fintype.card α) : 1 ≤ ↑(Fintype.card α / stepBound P.parts.card)

theorem SzemerediRegularity.eps_pow_five_pos {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {ε : ℝ} (hPε : 100 ≤ 4 ^ P.parts.card * ε ^ 5) : 0 < ε ^ 5

theorem SzemerediRegularity.eps_pos {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {ε : ℝ} (hPε : 100 ≤ 4 ^ P.parts.card * ε ^ 5) : 0 < ε

theorem SzemerediRegularity.hundred_div_ε_pow_five_le_m {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {ε : ℝ} [Nonempty α] (hPα : P.parts.card * 16 ^ P.parts.card ≤ Fintype.card α) (hPε : 100 ≤ 4 ^ P.parts.card * ε ^ 5) : 100 / ε ^ 5 ≤ ↑(Fintype.card α / stepBound P.parts.card)

theorem SzemerediRegularity.hundred_le_m {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {ε : ℝ} [Nonempty α] (hPα : P.parts.card * 16 ^ P.parts.card ≤ Fintype.card α) (hPε : 100 ≤ 4 ^ P.parts.card * ε ^ 5) (hε : ε ≤ 1) : 100 ≤ Fintype.card α / stepBound P.parts.card

theorem SzemerediRegularity.a_add_one_le_four_pow_parts_card {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} : Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card + 1 ≤ 4 ^ P.parts.card

theorem SzemerediRegularity.card_aux₁ {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {u : Finset α} (hucard : u.card = Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card + (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card)) : (4 ^ P.parts.card - (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card)) * (Fintype.card α / stepBound P.parts.card) + (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card) * (Fintype.card α / stepBound P.parts.card + 1) = u.card

theorem SzemerediRegularity.card_aux₂ {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {u : Finset α} (hP : P.IsEquipartition) (hu : u ∈ P.parts) (hucard : u.card ≠ Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card + (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card)) : (4 ^ P.parts.card - (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card + 1)) * (Fintype.card α / stepBound P.parts.card) + (Fintype.card α / P.parts.card - Fintype.card α / stepBound P.parts.card * 4 ^ P.parts.card + 1) * (Fintype.card α / stepBound P.parts.card + 1) = u.card

theorem SzemerediRegularity.pow_mul_m_le_card_part {α : Type u_1} [DecidableEq α] [Fintype α] {P : Finpartition Finset.univ} {u : Finset α} (hP : P.IsEquipartition) (hu : u ∈ P.parts) : 4 ^ P.parts.card * ↑(Fintype.card α / stepBound P.parts.card) ≤ ↑u.card

noncomputable def SzemerediRegularity.initialBound (ε : ℝ) (l : ℕ) : ℕ

Auxiliary function for Szemerédi's regularity lemma. The size of the partition by which we start blowing.

Equations

• SzemerediRegularity.initialBound ε l = max 7 (max l (⌊Real.log (100 / ε ^ 5) / Real.log 4⌋₊ + 1))

theorem SzemerediRegularity.le_initialBound (ε : ℝ) (l : ℕ) : l ≤ initialBound ε l

theorem SzemerediRegularity.seven_le_initialBound (ε : ℝ) (l : ℕ) : 7 ≤ initialBound ε l

theorem SzemerediRegularity.initialBound_pos (ε : ℝ) (l : ℕ) : 0 < initialBound ε l

theorem SzemerediRegularity.hundred_lt_pow_initialBound_mul {ε : ℝ} (hε : 0 < ε) (l : ℕ) : 100 < 4 ^ initialBound ε l * ε ^ 5

noncomputable def SzemerediRegularity.bound (ε : ℝ) (l : ℕ) : ℕ

An explicit bound on the size of the equipartition whose existence is given by Szemerédi's regularity lemma.

Equations

• One or more equations did not get rendered due to their size.

theorem SzemerediRegularity.initialBound_le_bound (ε : ℝ) (l : ℕ) : initialBound ε l ≤ bound ε l

theorem SzemerediRegularity.le_bound (ε : ℝ) (l : ℕ) : l ≤ bound ε l

theorem SzemerediRegularity.bound_pos (ε : ℝ) (l : ℕ) : 0 < bound ε l

theorem SzemerediRegularity.mul_sq_le_sum_sq {ι : Type u_2} {𝕜 : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {s t : Finset ι} {x : 𝕜} (hst : s ⊆ t) (f : ι → 𝕜) (hs : x ^ 2 ≤ ((∑ i ∈ s, f i) / ↑s.card) ^ 2) (hs' : ↑s.card ≠ 0) : ↑s.card * x ^ 2 ≤ ∑ i ∈ t, f i ^ 2

theorem SzemerediRegularity.add_div_le_sum_sq_div_card {ι : Type u_2} {𝕜 : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {s t : Finset ι} {x : 𝕜} (hst : s ⊆ t) (f : ι → 𝕜) (d : 𝕜) (hx : 0 ≤ x) (hs : x ≤ |(∑ i ∈ s, f i) / ↑s.card - (∑ i ∈ t, f i) / ↑t.card|) (ht : d ≤ ((∑ i ∈ t, f i) / ↑t.card) ^ 2) : d + ↑s.card / ↑t.card * x ^ 2 ≤ (∑ i ∈ t, f i ^ 2) / ↑t.card

def Mathlib.Meta.Positivity.evalInitialBound : PositivityExt

Extension for the positivity tactic: SzemerediRegularity.initialBound is always positive.

def Mathlib.Meta.Positivity.evalBound : PositivityExt

Extension for the positivity tactic: SzemerediRegularity.bound is always positive.