euclidean_has_mono_ap_of_le
For any dimension n, coloring c : EuclideanSpace ℝ (Fin n) → Bool, spacings α, color b, and lengths m₁ ≤ m₂, if c contains a monochromatic m₂-term arithmetic progression of color b with spacing α, then it also contains a monochromatic m₁-term arithmetic progression of color b with spacing α.
Statement
theorem euclidean_has_mono_ap_of_le {n : ℕ} {c : EuclideanSpace ℝ (Fin n) → Bool}
{m₁ m₂ : ℕ} (hle : m₁ ≤ m₂) (α : ℝ) (b : Bool)
(h : euclidean_has_mono_ap c m₂ α b) : euclidean_has_mono_ap c m₁ α b- Source
- folklore
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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
- euclidean_avoids_ap_of_leFor any dimension n, natural numbers r₁ ≤ r₂ and M₁ ≤ M₂, and spacings α, β : ℝ, if euclidean_avoids_ap n r₁ α M₁ β holds, then…
Read back from the Lean
Given a dimension $n : ℕ$, a 2-coloring $c : \text{EuclideanSpace } \mathbb{R} (\text{Fin } n) \to \text{Bool}$, natural numbers $m_1, m_2$ such that $m_1 \le m_2$, a real number $\alpha$, and a boolean color $b$: if $c$ contains a monochromatic arithmetic progression of length $m_2$ with step size norm $\alpha$ and color $b$ (euclidean_has_mono_ap c m₂ α b), then $c$ contains a monochromatic arithmetic progression of length $m_1$ with step size norm $\alpha$ and color $b$ (euclidean_has_mono_ap c m₁ α b).
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
To show that a monochromatic arithmetic progression of length $m_2$ contains one of length $m_1$ when $m_1 \le m_2$, we unpack the base point $x_0$ and step vector $v$ of the given $m_2$-term progression. Since any index $k < m_1$ is strictly less than $m_2$ by transitivity with $m_1 \le m_2$, the first $m_1$ terms are a subset of the $m_2$ terms and therefore all have color $b$.
We obtain a base point $x_0$, a step vector $v$ of norm $\alpha$, and the property that the first $m_2$ terms of the progression have color $b$.
Unpacking the definition of `euclidean_has_mono_ap` for length $m_2$ yields a base point $x_0 \in \mathbb{R}^n$, a displacement vector $v$ satisfying $\|v\| = \alpha$, and a hypothesis $hc$ stating that $c(x_0 + k \cdot v) = b$ for all indices $k < m_2$.
rcases h with ⟨x₀, v, hv, hc⟩
The same base point $x_0$ and vector $v$ provide a monochromatic arithmetic progression of length $m_1$.
We exhibit $x_0$ and $v$ as witnesses for the $m_1$-term progression. Since $\|v\| = \alpha$, it remains to check the color at each index $k < m_1$. Because $m_1 \le m_2$, we have $k < m_2$ by transitivity, so the color at $x_0 + k \cdot v$ is indeed $b$ by the hypothesis $hc$ from the $m_2$-term progression.
exact ⟨x₀, v, hv, fun k => hc ⟨k.val, k.isLt.trans_le hle⟩⟩
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.
/-- If a coloring contains a monochromatic arithmetic progression of length m₂, it also contains one of length m₁ for m₁ ≤ m₂. -/theorem euclidean_has_mono_ap_of_le {n : ℕ} {c : EuclideanSpace ℝ (Fin n) → Bool} {m₁ m₂ : ℕ} (hle : m₁ ≤ m₂) (α : ℝ) (b : Bool) (h : euclidean_has_mono_ap c m₂ α b) : euclidean_has_mono_ap c m₁ α b := by rcases h with ⟨x₀, v, hv, hc⟩ exact ⟨x₀, v, hv, fun k => hc ⟨k.val, k.isLt.trans_le hle⟩⟩