AFTD Auto-Formalizing Theoretical Domains

op_1482_avoidance_three_seventeen_dim_one

theoremverifiedoriginal

There exists a two-coloring of 1-dimensional Euclidean space containing neither a monochromatic 3-term arithmetic progression with unit spacing of color false nor a monochromatic 17-term arithmetic progression with unit spacing of color true.

Statement

theorem op_1482_avoidance_three_seventeen_dim_one : euclidean_avoids_ap 1 3 1 17 1
Related work
arXiv:2611.12360
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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…
  • 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,…
  • op_1481_avoidance_three_twenty_one_dim_oneFor every real number $\alpha > 0$ such that $\alpha^2 \in \{1/4, 1/9, 2/15, 3/4\}$, euclidean_avoids_ap 1 3 1 21 α holds: there exists a…

Read back from the Lean

There exists a 2-coloring $c : \text{EuclideanSpace } \mathbb{R} (\text{Fin } 1) \to \text{Bool}$ of 1-dimensional Euclidean space such that: 1. There does not exist an arithmetic progression of length 3 with step size (norm of step vector) 1 colored entirely with false (i.e., there do not exist $x_0, v \in \text{EuclideanSpace } \mathbb{R} (\text{Fin } 1)$ such that $\|v\| = 1$ and $c(x_0 + k \cdot v) = \text{false}$ for all $k \in \{0, 1, 2\}$); and 2. There does not exist an arithmetic progression of length 17 with step size (norm of step vector) 1 colored entirely with true (i.e., there do not exist $x_0, v \in \text{EuclideanSpace } \mathbb{R} (\text{Fin } 1)$ such that $\|v\| = 1$ and $c(x_0 + k \cdot v) = \text{true}$ for all $k \in \{0, 1, \dots, 16\}$).

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 proof constructs a two-coloring of 1-dimensional Euclidean space according to the parity of the integer floor of the coordinate: c(x) = Even(⌊x⌋). It first proves a lemma showing that this coloring admits no monochromatic 2-term arithmetic progression with unit spacing of either color, because any unit displacement in dimension 1 shifts the coordinate by ±1, which toggles the parity of the floor. Finally, by monotonicity of progression avoidance (euclidean_avoids_ap_of_le), avoiding 2-term progressions of both colors implies avoiding 3-term progressions of color false and 17-term progressions of color true.

  1. Assume for contradiction that there exists a monochromatic 2-term arithmetic progression of unit spacing and color b, and evaluate the colors of its points.

    We introduce the progression with base point x₀ and unit direction vector v (‖v‖ = 1) whose terms both have color b. Evaluating the coloring function at indices 0 and 1 shows that decide(Even ⌊x₀⌋) = b and decide(Even ⌊x₀ + v⌋) = b.

    lines 7–12

      intro ⟨x₀, v, hv, hc⟩
      have h0 := hc 0
      have h1 := hc 1
      simp at h0 h1
      change decide (Even ⌊x₀.ofLp 0⌋) = b at h0
      change decide (Even ⌊x₀.ofLp 0 + v.ofLp 0⌋) = b at h1
  2. The integer floors ⌊x₀ + v⌋ and ⌊x₀⌋ have the same parity.

    Since the boolean decisions for both points equal b, they are equal to each other. By op_1481_avoidance_three_twenty_one_dim_one_decide_even, this equality of boolean decisions implies that ⌊x₀ + v⌋ is even if and only if ⌊x₀⌋ is even.

    lines 13–15

    uses op_1481_avoidance_three_twenty_one_dim_one_decide_even

      have heq : decide (Even ⌊x₀.ofLp 0 + v.ofLp 0⌋) = decide (Even ⌊x₀.ofLp 0⌋) := by
        rw [h1, h0]
      have hiff := op_1481_avoidance_three_twenty_one_dim_one_decide_even _ _ heq
  3. The coordinate component of the unit vector v has absolute value 1.

    By op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coord, the norm of a vector in 1-dimensional Euclidean space equals the absolute value of its coordinate. Since ‖v‖ = 1, its coordinate has absolute value 1.

    lines 16–17

    uses op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coord

      have hnorm : ‖v‖ = |v.ofLp 0| := op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coord v
      have habs : |v.ofLp 0| = 1 := by rw [← hnorm, hv]
  4. Shifting by a coordinate of absolute value 1 changes floor parity, yielding a contradiction.

    By op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_one, adding any displacement of absolute value 1 toggles the parity of the floor of a real number. This contradicts the established equivalence that both floors have the same parity, showing that no such 2-term progression can exist.

    lines 18–19

    uses op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_one

      have hne := op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_one (x₀.ofLp 0) (v.ofLp 0) habs
      exact hne hiff
  5. It suffices to find a two-coloring avoiding monochromatic 2-term arithmetic progressions of unit spacing for both colors.

    By euclidean_avoids_ap_of_le, avoiding progressions of lengths r₁ and M₁ implies avoiding progressions of any greater lengths r₂ ≥ r₁ and M₂ ≥ M₁. Since 2 ≤ 3 and 2 ≤ 17 (verified by norm_num), avoiding 2-term unit progressions of both colors suffices.

    line 23

    uses euclidean_avoids_ap_of_le

      apply euclidean_avoids_ap_of_le (r₁ := 2) (M₁ := 2) (by norm_num) (by norm_num)
  6. The floor-parity coloring avoids 2-term unit progressions of both colors, proving the theorem.

    We supply the floor-parity coloring op_1482_avoidance_three_seventeen_dim_one_c_parity, which avoids monochromatic 2-term unit progressions of color false and color true by applying op_1482_avoidance_three_seventeen_dim_one_not_mono_two to each boolean value.

    lines 24–26

    uses op_1482_avoidance_three_seventeen_dim_one_not_mono_two

      exact ⟨op_1482_avoidance_three_seventeen_dim_one_c_parity,
        op_1482_avoidance_three_seventeen_dim_one_not_mono_two false,
        op_1482_avoidance_three_seventeen_dim_one_not_mono_two true⟩
op_1481_avoidance_three_twenty_one_dim_one_decide_even
If the boolean parity tests of two integers are equal, then one is even if and only if the other is even.
op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coord
In 1-dimensional Euclidean space, the Euclidean norm of a vector equals the absolute value of its single coordinate.
op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_one
Shifting a real number by a value with absolute value 1 changes the parity of its integer floor.
euclidean_avoids_ap_of_le
If a coloring of Euclidean space avoids monochromatic arithmetic progressions of lengths r₁ and M₁, it also avoids monochromatic progressions of any greater lengths r₂ ≥ r₁ and M₂ ≥ M₁ with the same spacings.
op_1482_avoidance_three_seventeen_dim_one_not_mono_two
The floor-parity coloring contains no monochromatic 2-term arithmetic progression with unit spacing of color b.

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

noncomputable def op_1482_avoidance_three_seventeen_dim_one_c_parity    (x : EuclideanSpace ℝ (Fin 1)) : Bool :=  decide (Even ⌊x.ofLp 0⌋)lemma op_1482_avoidance_three_seventeen_dim_one_not_mono_two (b : Bool) :    ¬ euclidean_has_mono_ap op_1482_avoidance_three_seventeen_dim_one_c_parity 2 1 b := by  intro ⟨x₀, v, hv, hc⟩  have h0 := hc 0  have h1 := hc 1  simp at h0 h1  change decide (Even ⌊x₀.ofLp 0⌋) = b at h0  change decide (Even ⌊x₀.ofLp 0 + v.ofLp 0⌋) = b at h1  have heq : decide (Even ⌊x₀.ofLp 0 + v.ofLp 0⌋) = decide (Even ⌊x₀.ofLp 0⌋) := by    rw [h1, h0]  have hiff := op_1481_avoidance_three_twenty_one_dim_one_decide_even _ _ heq  have hnorm : ‖v‖ = |v.ofLp 0| := op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coord v  have habs : |v.ofLp 0| = 1 := by rw [← hnorm, hv]  have hne := op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_one (x₀.ofLp 0) (v.ofLp 0) habs  exact hne hiff/-- In dimension 1, there exists a two-coloring of Euclidean space avoiding monochromatic 3-APs and 17-APs with unit spacing. -/theorem op_1482_avoidance_three_seventeen_dim_one : euclidean_avoids_ap 1 3 1 17 1 := by  apply euclidean_avoids_ap_of_le (r₁ := 2) (M₁ := 2) (by norm_num) (by norm_num)  exact ⟨op_1482_avoidance_three_seventeen_dim_one_c_parity,    op_1482_avoidance_three_seventeen_dim_one_not_mono_two false,    op_1482_avoidance_three_seventeen_dim_one_not_mono_two true⟩
See it in the graphDiscuss this resultChallenge it