euclidean_avoids_ap_of_le
For any dimension n, natural numbers r₁ ≤ r₂ and M₁ ≤ M₂, and spacings α, β : ℝ, if euclidean_avoids_ap n r₁ α M₁ β holds, then euclidean_avoids_ap n r₂ α M₂ β holds.
Statement
theorem euclidean_avoids_ap_of_le {n : ℕ} {r₁ r₂ M₁ M₂ : ℕ} (hr : r₁ ≤ r₂) (hM : M₁ ≤ M₂)
{α β : ℝ} (h : euclidean_avoids_ap n r₁ α M₁ β) : euclidean_avoids_ap n r₂ α M₂ β- Source
- folklore
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- euclidean_avoids_apThe Euclidean Ramsey avoidance property euclidean_avoids_ap n r α M β (commonly denoted E^n ↛ (α ℓ_r, β ℓ_M)) asserts that there exists a…
- euclidean_has_mono_ap_of_leFor any dimension n, coloring c : EuclideanSpace ℝ (Fin n) → Bool, spacings α, color b, and lengths m₁ ≤ m₂, if c contains a monochromatic…
- euclidean_has_mono_apFor a dimension n, a two-coloring c : EuclideanSpace ℝ (Fin n) → Bool, a term count m : ℕ, a spacing α : ℝ, and a color b : Bool,…
- Used by 1
- op_1482_avoidance_three_seventeen_dim_oneThere exists a two-coloring of 1-dimensional Euclidean space containing neither a monochromatic 3-term arithmetic progression with unit…
Read back from the Lean
For any dimension $n \in \mathbb{N}$, progression lengths $r_1, r_2, M_1, M_2 \in \mathbb{N}$ satisfying $r_1 \le r_2$ and $M_1 \le M_2$, and step sizes $\alpha, \beta \in \mathbb{R}$: if there exists a 2-coloring of $\mathbb{R}^n$ (EuclideanSpace ℝ (Fin n) → Bool) avoiding monochromatic arithmetic progressions of length $r_1$ with step norm $\alpha$ in color false and length $M_1$ with step norm $\beta$ in color true, then there also exists a 2-coloring of $\mathbb{R}^n$ avoiding monochromatic arithmetic progressions of length $r_2$ with step norm $\alpha$ in color false and length $M_2$ with step norm $\beta$ in color true.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The property of avoiding monochromatic arithmetic progressions is monotonic in the progression lengths: any 2-coloring of ℝⁿ that avoids progressions of lengths r₁ and M₁ also avoids longer progressions of lengths r₂ ≥ r₁ and M₂ ≥ M₁. Using the same coloring c that witnesses avoidance for (r₁, M₁), the proof proceeds by contraposition for each color. Any monochromatic progression of length r₂ or M₂ would contain an initial subprogression of length r₁ or M₁, contradicting the avoidance properties of c.
To show that an avoiding coloring exists for progressions of lengths r₂ and M₂, it suffices to show that the coloring c witnessing avoidance for lengths r₁ and M₁ also contains no monochromatic progressions of lengths r₂ and M₂.
Unpack the hypothesis h to obtain a 2-coloring c of ℝⁿ that contains no monochromatic progression of length r₁ with spacing α colored false, and no monochromatic progression of length M₁ with spacing β colored true. We use this same coloring c as the witness for avoidance at lengths r₂ and M₂.
rcases h with ⟨c, hr1, hM1⟩ refine ⟨c, ?_, ?_⟩
The coloring c contains no monochromatic arithmetic progression of length r₂ with step size α and color false.
Suppose for contradiction that c contains a monochromatic progression of length r₂ with step size α and color false (h2). Because r₁ ≤ r₂, the lemma euclidean_has_mono_ap_of_le implies that any such progression contains a subprogression of length r₁ with the same step size and color. This contradicts the assumption hr1 that c avoids progressions of length r₁.
uses
euclidean_has_mono_ap_of_le· intro h2 exact hr1 (euclidean_has_mono_ap_of_le hr α false h2)
The coloring c contains no monochromatic arithmetic progression of length M₂ with step size β and color true.
Suppose for contradiction that c contains a monochromatic progression of length M₂ with step size β and color true (h2). Because M₁ ≤ M₂, euclidean_has_mono_ap_of_le yields a monochromatic subprogression of length M₁, contradicting the assumption hM1 that c avoids progressions of length M₁.
uses
euclidean_has_mono_ap_of_le· intro h2 exact hM1 (euclidean_has_mono_ap_of_le hM β true h2)
euclidean_has_mono_ap_of_le- If a coloring of Euclidean space contains a monochromatic arithmetic progression of length m₂ with step size α and color b, and m₁ ≤ m₂, then it also contains a monochromatic arithmetic progression of length m₁ with the same step size and color.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity of Euclidean AP avoidance: avoiding shorter progressions implies avoiding longer progressions. -/theorem euclidean_avoids_ap_of_le {n : ℕ} {r₁ r₂ M₁ M₂ : ℕ} (hr : r₁ ≤ r₂) (hM : M₁ ≤ M₂) {α β : ℝ} (h : euclidean_avoids_ap n r₁ α M₁ β) : euclidean_avoids_ap n r₂ α M₂ β := by rcases h with ⟨c, hr1, hM1⟩ refine ⟨c, ?_, ?_⟩ · intro h2 exact hr1 (euclidean_has_mono_ap_of_le hr α false h2) · intro h2 exact hM1 (euclidean_has_mono_ap_of_le hM β true h2)