AFTD Auto-Formalizing Theoretical Domains

euclidean_has_mono_ap_of_le

theoremverified

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$.

  1. 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$.

    line 5

      rcases h with ⟨x₀, v, hv, hc⟩
  2. 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.

    line 6

      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

/-- 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⟩⟩
See it in the graphDiscuss this resultChallenge it