euclidean_radial_ap_avoidance_transfer_from_plane
For a coloring determined solely by the squared distance from the origin, avoiding a monochromatic r-term arithmetic progression of spacing α and color b in the Euclidean plane implies avoidance of the same progression in every finite dimension. The same radial function is used in all dimensions.
Statement
theorem euclidean_radial_ap_avoidance_transfer_from_plane (f : ℝ → Bool) (r n : ℕ) (α : ℝ) (b : Bool) (h : ¬ euclidean_has_mono_ap (fun x : EuclideanSpace ℝ (Fin 2) => f (‖x‖ ^ 2)) r α b) : ¬ euclidean_has_mono_ap (fun x : EuclideanSpace ℝ (Fin n) => f (‖x‖ ^ 2)) r α b
- Source
- arXiv:2611.12360, Lemma 2.1, together with the Gram-matrix realization in the Euclidean plane
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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,…
- norm_sq_ap_quadraticFor any initial point x₀ and difference vector v in n-dimensional Euclidean space, and any real coefficient k, the squared norm of x₀ + k…
The proof, explained
The proof proceeds by contraposition. The squared distance from the origin along an arithmetic progression x₀ + k • v expands quadratically as ‖v‖² k² + 2 ⟨x₀, v⟩ k + ‖x₀‖², which depends only on the three scalar invariants ‖v‖, ⟨x₀, v⟩, and ‖x₀‖. By the Cauchy–Schwarz inequality, one can always construct a 2D configuration (x₂, v₂) in the Euclidean plane having precisely these same three scalar values and step length ‖v₂‖ = α. Since the coloring is a radial function of the squared distance from the origin, this planar pair forms an identical monochromatic progression in ℝ², contradicting the planar avoidance hypothesis.
Assume for contradiction that there exists a monochromatic r-term arithmetic progression of step length α and color b in ℝⁿ.
We unpack the assumed progression into an initial point x₀ ∈ ℝⁿ and a step vector v ∈ ℝⁿ with ‖v‖ = α such that for every step k ∈ {0, …, r - 1}, the point x₀ + k • v has color f(‖x₀ + k • v‖²) = b.
rintro ⟨x₀, v, hvα, hcol⟩
In the degenerate case v = 0, the progression transfers directly to a monochromatic progression in ℝ², contradicting avoidance in the plane.
When v = 0, the step length is α = ‖v‖ = 0. We define planar vectors x₂ = (‖x₀‖, 0) and v₂ = 0 in ℝ². Then ‖v₂‖ = 0 = α, and ‖x₂‖² = ‖x₀‖² + 0² = ‖x₀‖². Since v₂ = 0 and v = 0, every step point x₂ + k • v₂ equals x₂ and x₀ + k • v equals x₀, giving f(‖x₂ + k • v₂‖²) = f(‖x₀‖²) = b. This produces a monochromatic progression in ℝ², contradicting the hypothesis h.
uses
EuclideanSpace.norm_sq_eq,Fin.sum_univ_twoby_cases hv0 : v = 0 · have ha0 : ‖v‖ = 0 := by rw [hv0]; simp let x₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![‖x₀‖, 0] let v₂ : EuclideanSpace ℝ (Fin 2) := 0 refine h ⟨x₂, v₂, ?_, ?_⟩ · rw [show ‖v₂‖ = 0 from by simp [v₂], show α = 0 from hvα ▸ ha0] · intro k have hx₂ : ‖x₂‖ ^ 2 = ‖x₀‖ ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [x₂, Fin.sum_univ_two] show f (‖x₂ + (k:ℝ) • v₂‖ ^ 2) = b rw [show x₂ + (k:ℝ) • v₂ = x₂ from by simp [v₂]] rw [hx₂] simpa [hv0] using hcol k
In the non-degenerate case v ≠ 0, the invariants a = ‖v‖ > 0, d = ‖x₀‖, and c = ⟨x₀, v⟩ satisfy the Cauchy–Schwarz inequality c² ≤ d² a².
We set a = ‖v‖, d = ‖x₀‖, and c = ⟨x₀, v⟩. Because v ≠ 0, its norm is strictly positive (a > 0). By the Cauchy–Schwarz inequality (|c| ≤ d * a), squaring both sides and using |c|² = c² and (d * a)² = d² * a² yields c² ≤ d² a².
uses
norm_nonneg,norm_ne_zero_iff.mpr,Ne.symm,lt_of_le_of_ne,abs_real_inner_le_norm,pow_le_pow_left₀,abs_nonneg,sq_abs· set a : ℝ := ‖v‖ with ha_eq set d : ℝ := ‖x₀‖ with hd_eq set c : ℝ := inner ℝ x₀ v with hc_eq have ha_pos : 0 < a := by rw [ha_eq] exact lt_of_le_of_ne (norm_nonneg v) (Ne.symm (norm_ne_zero_iff.mpr hv0)) have hcs : c ^ 2 ≤ d ^ 2 * a ^ 2 := by have h1 : |c| ≤ d * a := by have := abs_real_inner_le_norm x₀ v rw [← hc_eq, ← hd_eq, ← ha_eq] at this exact this have h2 : |c| ^ 2 ≤ (d * a) ^ 2 := pow_le_pow_left₀ (abs_nonneg c) h1 2 have h3 : (d * a) ^ 2 = d ^ 2 * a ^ 2 := by ring nlinarith [sq_abs c]
The planar coordinate t = c / a satisfies d² - t² ≥ 0, which allows defining s = √(d² - t²) with s² = d² - t².
With t = c / a, we have t² a² = c². Since a > 0, a² > 0. From c² ≤ d² a², dividing by a² gives t² ≤ d², so d² - t² ≥ 0. Hence s = √(d² - t²) is well-defined and satisfies s² = d² - t².
uses
Real.sq_sqrtset t : ℝ := c / a with ht_eq have ht_sq : t ^ 2 = c ^ 2 / a ^ 2 := by rw [ht_eq]; field_simp have hnonneg : 0 ≤ d ^ 2 - t ^ 2 := by have ha2 : (0:ℝ) < a ^ 2 := by positivity have ht2 : t ^ 2 * a ^ 2 = c ^ 2 := by rw [ht_sq]; field_simp nlinarith set s : ℝ := Real.sqrt (d ^ 2 - t ^ 2) with hs_eq have hs : s ^ 2 = d ^ 2 - t ^ 2 := by rw [hs_eq]; exact Real.sq_sqrt hnonneg
The planar vectors x₂ = (t, s) and v₂ = (a, 0) match the invariants: ‖v₂‖² = a², ‖x₂‖² = d², and ⟨x₂, v₂⟩ = c.
We set x₂ = (t, s) and v₂ = (a, 0) in ℝ². Summing the squared components yields ‖v₂‖² = a² + 0² = a² and ‖x₂‖² = t² + s² = t² + (d² - t²) = d². Evaluating the inner product in ℝ² gives ⟨x₂, v₂⟩ = t * a + s * 0 = a * (c / a) = c.
uses
EuclideanSpace.norm_sq_eq,Fin.sum_univ_two,PiLp.inner_applylet x₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![t, s] let v₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![a, 0] have hv₂_sq : ‖v₂‖ ^ 2 = a ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [v₂, Fin.sum_univ_two] have hx₂_sq : ‖x₂‖ ^ 2 = d ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [x₂, Fin.sum_univ_two] nlinarith [hs] have hin : inner ℝ x₂ v₂ = c := by rw [PiLp.inner_apply] simp [x₂, v₂, Fin.sum_univ_two] rw [ht_eq]; field_simp
The planar progression (x₂, v₂) has step length α and matches the colors of the original progression, contradicting h.
Taking positive square roots of ‖v₂‖² = a² gives ‖v₂‖ = a = ‖v‖ = α. For each index k, expanding the squared distance via norm_sq_ap_quadratic shows that ‖x₂ + k • v₂‖² = ‖v₂‖² k² + 2 ⟨x₂, v₂⟩ k + ‖x₂‖² = a² k² + 2 c k + d² = ‖x₀ + k • v‖². Because the coloring f depends solely on the squared Euclidean distance from the origin, f(‖x₂ + k • v₂‖²) = f(‖x₀ + k • v‖²) = b. This establishes an r-term monochromatic progression in ℝ², contradicting the avoidance hypothesis h.
uses
sq_eq_sq₀,norm_nonneg,le_of_lt,norm_sq_ap_quadratichave hv2_norm : ‖v₂‖ = α := by have ha : ‖v₂‖ = a := by apply (sq_eq_sq₀ (norm_nonneg _) (le_of_lt ha_pos)).mp rw [hv₂_sq, ha_eq] rw [ha]; exact hvα refine h ⟨x₂, v₂, hv2_norm, ?_⟩ intro k have heq : ‖x₂ + (k:ℝ) • v₂‖ ^ 2 = ‖x₀ + (k:ℝ) • v‖ ^ 2 := by rw [norm_sq_ap_quadratic x₂ v₂ (k:ℝ), norm_sq_ap_quadratic x₀ v (k:ℝ)] rw [hv₂_sq, hin, hx₂_sq, ← ha_eq, ← hc_eq, ← hd_eq] show f (‖x₂ + (k:ℝ) • v₂‖ ^ 2) = b rw [heq] exact hcol k
abs_real_inner_le_norm- The Cauchy–Schwarz inequality in a real inner product space: |⟨x, y⟩| ≤ ‖x‖ ‖y‖.
abs_nonneg- The absolute value of any real number is non-negative: 0 ≤ |a|.
EuclideanSpace.norm_sq_eq- The squared norm of a vector in Euclidean space equals the sum of the squared norms of its components.
Fin.sum_univ_two- A sum over the two-element type Fin 2 is the sum of the value at 0 and the value at 1.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
lt_of_le_of_ne- In a partial order, a ≤ b and a ≠ b together imply a < b.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
norm_nonneg- The norm of any vector in a seminormed group is non-negative.
norm_ne_zero_iff.mpr- If a vector is non-zero, then its norm is non-zero.
norm_sq_ap_quadratic- The squared norm of an arithmetic progression term x₀ + k • v expands quadratically as ‖v‖² k² + 2 ⟨x₀, v⟩ k + ‖x₀‖².
PiLp.inner_apply- The inner product in an L² direct sum (Euclidean space) is the sum of the inner products of the corresponding components.
pow_le_pow_left₀- For non-negative elements, a ≤ b implies aⁿ ≤ bⁿ for every natural exponent n.
Real.sq_sqrt- For any non-negative real number x, the square of its square root equals x.
sq_abs- The square of the absolute value of a real number equals the square of the number: |a|² = a².
sq_eq_sq₀- For non-negative real numbers a and b, a² = b² if and only if a = b.
- In Lean, Euclidean space is represented as `EuclideanSpace ℝ (Fin n)`. Planar vectors are constructed via `(WithLp.equiv 2 (Fin 2 → ℝ)).symm ![x, y]` to explicitly embed 2D coordinates into this type.
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.
theorem euclidean_radial_ap_avoidance_transfer_from_plane (f : ℝ → Bool) (r n : ℕ) (α : ℝ) (b : Bool) (h : ¬ euclidean_has_mono_ap (fun x : EuclideanSpace ℝ (Fin 2) => f (‖x‖ ^ 2)) r α b) : ¬ euclidean_has_mono_ap (fun x : EuclideanSpace ℝ (Fin n) => f (‖x‖ ^ 2)) r α b := by rintro ⟨x₀, v, hvα, hcol⟩ by_cases hv0 : v = 0 · have ha0 : ‖v‖ = 0 := by rw [hv0]; simp let x₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![‖x₀‖, 0] let v₂ : EuclideanSpace ℝ (Fin 2) := 0 refine h ⟨x₂, v₂, ?_, ?_⟩ · rw [show ‖v₂‖ = 0 from by simp [v₂], show α = 0 from hvα ▸ ha0] · intro k have hx₂ : ‖x₂‖ ^ 2 = ‖x₀‖ ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [x₂, Fin.sum_univ_two] show f (‖x₂ + (k:ℝ) • v₂‖ ^ 2) = b rw [show x₂ + (k:ℝ) • v₂ = x₂ from by simp [v₂]] rw [hx₂] simpa [hv0] using hcol k · set a : ℝ := ‖v‖ with ha_eq set d : ℝ := ‖x₀‖ with hd_eq set c : ℝ := inner ℝ x₀ v with hc_eq have ha_pos : 0 < a := by rw [ha_eq] exact lt_of_le_of_ne (norm_nonneg v) (Ne.symm (norm_ne_zero_iff.mpr hv0)) have hcs : c ^ 2 ≤ d ^ 2 * a ^ 2 := by have h1 : |c| ≤ d * a := by have := abs_real_inner_le_norm x₀ v rw [← hc_eq, ← hd_eq, ← ha_eq] at this exact this have h2 : |c| ^ 2 ≤ (d * a) ^ 2 := pow_le_pow_left₀ (abs_nonneg c) h1 2 have h3 : (d * a) ^ 2 = d ^ 2 * a ^ 2 := by ring nlinarith [sq_abs c] set t : ℝ := c / a with ht_eq have ht_sq : t ^ 2 = c ^ 2 / a ^ 2 := by rw [ht_eq]; field_simp have hnonneg : 0 ≤ d ^ 2 - t ^ 2 := by have ha2 : (0:ℝ) < a ^ 2 := by positivity have ht2 : t ^ 2 * a ^ 2 = c ^ 2 := by rw [ht_sq]; field_simp nlinarith set s : ℝ := Real.sqrt (d ^ 2 - t ^ 2) with hs_eq have hs : s ^ 2 = d ^ 2 - t ^ 2 := by rw [hs_eq]; exact Real.sq_sqrt hnonneg let x₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![t, s] let v₂ : EuclideanSpace ℝ (Fin 2) := (WithLp.equiv 2 (Fin 2 → ℝ)).symm ![a, 0] have hv₂_sq : ‖v₂‖ ^ 2 = a ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [v₂, Fin.sum_univ_two] have hx₂_sq : ‖x₂‖ ^ 2 = d ^ 2 := by rw [EuclideanSpace.norm_sq_eq] simp [x₂, Fin.sum_univ_two] nlinarith [hs] have hin : inner ℝ x₂ v₂ = c := by rw [PiLp.inner_apply] simp [x₂, v₂, Fin.sum_univ_two] rw [ht_eq]; field_simp have hv2_norm : ‖v₂‖ = α := by have ha : ‖v₂‖ = a := by apply (sq_eq_sq₀ (norm_nonneg _) (le_of_lt ha_pos)).mp rw [hv₂_sq, ha_eq] rw [ha]; exact hvα refine h ⟨x₂, v₂, hv2_norm, ?_⟩ intro k have heq : ‖x₂ + (k:ℝ) • v₂‖ ^ 2 = ‖x₀ + (k:ℝ) • v‖ ^ 2 := by rw [norm_sq_ap_quadratic x₂ v₂ (k:ℝ), norm_sq_ap_quadratic x₀ v (k:ℝ)] rw [hv₂_sq, hin, hx₂_sq, ← ha_eq, ← hc_eq, ← hd_eq] show f (‖x₂ + (k:ℝ) • v₂‖ ^ 2) = b rw [heq] exact hcol k