rational_quadratic_coloring_implies_euclidean_avoidance
A rational coloring avoiding false length-3 and true length-17 monic quadratic sequences with arbitrary rational lower coefficients yields the required Euclidean coloring in every finite dimension.
Statement
theorem rational_quadratic_coloring_implies_euclidean_avoidance (f : ℚ → Bool) (h3 : ∀ a b : ℚ, ¬ ∀ k : Fin 3, f ((k.val : ℚ) ^ 2 + a * k.val + b) = false) (h17 : ∀ a b : ℚ, ¬ ∀ k : Fin 17, f ((k.val : ℚ) ^ 2 + a * k.val + b) = true) : ∀ n : ℕ, euclidean_avoids_ap n 3 1 17 1- Source
- Squared-norm identity from arXiv:2611.12360 Lemma 2.1, plus a rational-linear retraction of the real numbers.
- Verified
- 13 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_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 transfers the rational coloring f to Euclidean space ℝⁿ by defining c(x) = f(L(‖x‖²)), where L : ℝ → ℚ is a ℚ-linear functional fixing 1 (obtained via the projectivity of ℝ as a ℚ-vector space). Along any unit-step progression x + k • v (with ‖v‖ = 1), the squared norm expands quadratically as k² + 2 ⟨x, v⟩ * k + ‖x‖². Applying L turns this into a monic quadratic sequence in k with rational lower coefficients a = L(2 ⟨x, v⟩) and b = L(‖x‖²). Consequently, any forbidden monochromatic progression in ℝⁿ would induce a forbidden monochromatic monic quadratic sequence on ℚ, contradicting the hypotheses on f.
There exists a ℚ-linear functional L : ℝ → ℚ that acts as the identity on all rational numbers.
Regarding ℝ as a vector space over ℚ, it is a projective ℚ-module. Since 1 ≠ 0 in ℝ, Module.Projective.exists_dual_eq_one provides a ℚ-linear map L : ℝ → ℚ such that L(1) = 1. By linearity, L(r • 1) = r • L(1) = r for any rational r, so L acts as the identity on the rational numbers embedded in ℝ.
uses
Module.Projective.exists_dual_eq_one,Rat.smul_defclassical obtain ⟨L, hL⟩ := Module.Projective.exists_dual_eq_one ℚ (show (1 : ℝ) ≠ 0 by norm_num) have hL_rat (r : ℚ) : L (r : ℝ) = r := by have h := L.map_smul r (1 : ℝ) simpa [hL, Rat.smul_def] using h
In any dimension n, we can define a coloring c : EuclideanSpace ℝ (Fin n) → Bool by c(x) = f(L(‖x‖²)).
We fix an arbitrary dimension n and pull back the rational coloring f through L composed with the squared Euclidean norm of x.
intro n let c : EuclideanSpace ℝ (Fin n) → Bool := fun x => f (L (‖x‖^2))
For any points x, v with ‖v‖ = 1 and any k ∈ ℕ, L(‖x + k • v‖²) evaluates to the rational monic quadratic polynomial k² + L(2 ⟨x, v⟩) * k + L(‖x‖²).
By norm_sq_ap_quadratic, ‖x + k • v‖² expands to ‖v‖² * k² + 2 ⟨x, v⟩ * k + ‖x‖², which simplifies to k² + 2 ⟨x, v⟩ * k + ‖x‖² since ‖v‖ = 1. Applying the ℚ-linear map L, the term k² is fixed because k² is rational, the middle term pulls out the rational scalar k as k • L(2 ⟨x, v⟩), and the constant term becomes L(‖x‖²). Rearranging via ring arithmetic gives the monic quadratic form.
uses
norm_sq_ap_quadratic,one_pow,one_mul,Rat.cast_pow,Rat.cast_natCast,Rat.smul_def,map_add,map_smul,smul_eq_mulhave hquad (x v : EuclideanSpace ℝ (Fin n)) (hv : ‖v‖ = 1) (k : ℕ) : L (‖x + (k : ℝ) • v‖^2) = (k : ℚ)^2 + L (2 * @inner ℝ _ _ x v) * k + L (‖x‖^2) := by rw [norm_sq_ap_quadratic, hv] have hid : (1 : ℝ)^2 * (k : ℝ)^2 + 2 * @inner ℝ _ _ x v * (k : ℝ) + ‖x‖^2 = (((k : ℚ)^2 : ℚ) : ℝ) + (k : ℚ) • (2 * @inner ℝ _ _ x v) + ‖x‖^2 := by simp only [one_pow, one_mul, Rat.cast_pow, Rat.cast_natCast, Rat.smul_def] ring rw [hid, map_add, map_add, hL_rat, map_smul] simp only [smul_eq_mul] ring
The coloring c contains no monochromatic arithmetic progression of length 3 colored false with step size 1.
Assume for contradiction that there is a progression x + k • v for k ∈ {0, 1, 2} with ‖v‖ = 1 such that c(x + k • v) = false for all k. By the quadratic identity, c(x + k • v) = f(k² + a * k + b) with rational coefficients a = L(2 ⟨x, v⟩) and b = L(‖x‖²). This would mean f(k² + a * k + b) = false for all k ∈ Fin 3, directly contradicting the hypothesis h3.
refine ⟨c, ?_, ?_⟩ · rintro ⟨x, v, hv, hc⟩ apply h3 (L (2 * @inner ℝ _ _ x v)) (L (‖x‖^2)) intro k have hh := hc k change f (L (‖x + (k.val : ℝ) • v‖^2)) = false at hh rw [hquad x v hv k.val] at hh exact hh
The coloring c contains no monochromatic arithmetic progression of length 17 colored true with step size 1.
Similarly, assume for contradiction that there is a progression x + k • v for k ∈ {0, ..., 16} with ‖v‖ = 1 such that c(x + k • v) = true for all k. By the quadratic identity, this yields f(k² + a * k + b) = true for all k ∈ Fin 17 with rational coefficients a = L(2 ⟨x, v⟩) and b = L(‖x‖²), directly contradicting the hypothesis h17.
· rintro ⟨x, v, hv, hc⟩ apply h17 (L (2 * @inner ℝ _ _ x v)) (L (‖x‖^2)) intro k have hh := hc k change f (L (‖x + (k.val : ℝ) • v‖^2)) = true at hh rw [hquad x v hv k.val] at hh exact hh
Module.Projective.exists_dual_eq_one- in any projective module over a semifield, for every nonzero element x, there exists a linear functional evaluating to 1 at x
Rat.smul_def- scalar multiplication of an element in a division ring by a rational number equals multiplication by the rational cast into that ring
norm_sq_ap_quadratic- the squared Euclidean norm of x₀ + k • v expands as ‖v‖² * k² + 2 ⟨x₀, v⟩ * k + ‖x₀‖²
one_pow- in any monoid, 1 raised to any natural power is 1
one_mul- multiplying any element on the left by 1 leaves it unchanged
Rat.cast_pow- the cast of a rational power pⁿ into a division ring equals the n-th power of the cast of p
Rat.cast_natCast- casting a natural number through the rationals into a division ring is identical to casting it directly
map_add- an additive homomorphism preserves addition: f(x + y) = f(x) + f(y)
map_smul- a module homomorphism preserves scalar multiplication: f(c • x) = c • f(x)
smul_eq_mul- scalar multiplication of a ring on itself coincides with standard ring multiplication
- The existence of the ℚ-linear functional L : ℝ → ℚ with L(1) = 1 relies on the axiom of choice (via Module.Projective.exists_dual_eq_one), viewing ℝ as an infinite-dimensional vector space over ℚ; this is why the proof begins with the `classical` tactic.
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 rational_quadratic_coloring_implies_euclidean_avoidance (f : ℚ → Bool) (h3 : ∀ a b : ℚ, ¬ ∀ k : Fin 3, f ((k.val : ℚ) ^ 2 + a * k.val + b) = false) (h17 : ∀ a b : ℚ, ¬ ∀ k : Fin 17, f ((k.val : ℚ) ^ 2 + a * k.val + b) = true) : ∀ n : ℕ, euclidean_avoids_ap n 3 1 17 1 := by classical obtain ⟨L, hL⟩ := Module.Projective.exists_dual_eq_one ℚ (show (1 : ℝ) ≠ 0 by norm_num) have hL_rat (r : ℚ) : L (r : ℝ) = r := by have h := L.map_smul r (1 : ℝ) simpa [hL, Rat.smul_def] using h intro n let c : EuclideanSpace ℝ (Fin n) → Bool := fun x => f (L (‖x‖^2)) have hquad (x v : EuclideanSpace ℝ (Fin n)) (hv : ‖v‖ = 1) (k : ℕ) : L (‖x + (k : ℝ) • v‖^2) = (k : ℚ)^2 + L (2 * @inner ℝ _ _ x v) * k + L (‖x‖^2) := by rw [norm_sq_ap_quadratic, hv] have hid : (1 : ℝ)^2 * (k : ℝ)^2 + 2 * @inner ℝ _ _ x v * (k : ℝ) + ‖x‖^2 = (((k : ℚ)^2 : ℚ) : ℝ) + (k : ℚ) • (2 * @inner ℝ _ _ x v) + ‖x‖^2 := by simp only [one_pow, one_mul, Rat.cast_pow, Rat.cast_natCast, Rat.smul_def] ring rw [hid, map_add, map_add, hL_rat, map_smul] simp only [smul_eq_mul] ring refine ⟨c, ?_, ?_⟩ · rintro ⟨x, v, hv, hc⟩ apply h3 (L (2 * @inner ℝ _ _ x v)) (L (‖x‖^2)) intro k have hh := hc k change f (L (‖x + (k.val : ℝ) • v‖^2)) = false at hh rw [hquad x v hv k.val] at hh exact hh · rintro ⟨x, v, hv, hc⟩ apply h17 (L (2 * @inner ℝ _ _ x v)) (L (‖x‖^2)) intro k have hh := hc k change f (L (‖x + (k.val : ℝ) • v‖^2)) = true at hh rw [hquad x v hv k.val] at hh exact hh