AFTD Auto-Formalizing Theoretical Domains

euclidean_radial_ap_avoidance_transfer_from_plane

theoremverified

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.

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

    line 2

      rintro ⟨x₀, v, hvα, hcol⟩
  2. 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.

    lines 3–16

    uses EuclideanSpace.norm_sq_eq, Fin.sum_univ_two

      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
  3. 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².

    lines 17–30

    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]
  4. 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².

    lines 31–41

    uses Real.sq_sqrt

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

    lines 42–54

    uses EuclideanSpace.norm_sq_eq, Fin.sum_univ_two, PiLp.inner_apply

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

    lines 55–67

    uses sq_eq_sq₀, norm_nonneg, le_of_lt, norm_sq_ap_quadratic

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

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

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