op_1482_avoidance_three_seventeen_dim_one
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.
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.
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
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.
uses
op_1481_avoidance_three_twenty_one_dim_one_decide_evenhave 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
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.
uses
op_1481_avoidance_three_twenty_one_dim_one_norm_eq_abs_coordhave 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]
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.
uses
op_1481_avoidance_three_twenty_one_dim_one_floor_parity_ne_of_abs_onehave 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
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.
uses
euclidean_avoids_ap_of_leapply euclidean_avoids_ap_of_le (r₁ := 2) (M₁ := 2) (by norm_num) (by norm_num)
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.
uses
op_1482_avoidance_three_seventeen_dim_one_not_mono_twoexact ⟨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
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.
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⟩