AFTD Auto-Formalizing Theoretical Domains

euclidean_avoids_ap_of_le

theoremverified

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

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.

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

    lines 4–5

      rcases h with ⟨c, hr1, hM1⟩
      refine ⟨c, ?_, ?_⟩
  2. 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₁.

    lines 6–7

    uses euclidean_has_mono_ap_of_le

      · intro h2
        exact hr1 (euclidean_has_mono_ap_of_le hr α false h2)
  3. 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₁.

    lines 8–9

    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

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