integer_quadratic_coloring_divisor
If an integer coloring avoids the false length-3 and true length-17 quadratic patterns with curvature q m, then another integer coloring avoids the same patterns with curvature q.
Statement
theorem integer_quadratic_coloring_divisor (q m : ℕ) (f : ℤ → Bool) (h3 : ∀ a b : ℤ, ¬ ∀ k : Fin 3, f (((q * m : ℕ) : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = false) (h17 : ∀ a b : ℤ, ¬ ∀ k : Fin 17, f (((q * m : ℕ) : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = true) : ∃ g : ℤ → Bool, (∀ a b : ℤ, ¬ ∀ k : Fin 3, g ((q : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = false) ∧ (∀ a b : ℤ, ¬ ∀ k : Fin 17, g ((q : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = true)- Source
- Divisibility reduction for the rational quadratic route to OP-1482.
- Verified
- 13 Nov 2026
- Axioms
propext
The proof, explained
To construct a coloring g : ℤ → Bool avoiding length-3 false and length-17 true quadratic progressions with curvature q, we dilate the domain of the given coloring f by defining g(z) = f(m * z). Evaluating g on a quadratic progression with curvature q corresponds to evaluating f at m * (q * k^2 + a * k + b) = (q * m) * k^2 + (m * a) * k + m * b, which is a progression of the same length and color with curvature q * m. The hypotheses that f avoids length-3 false and length-17 true progressions with curvature q * m then immediately rule out both forbidden patterns for g.
For any k ∈ ℕ and a, b ∈ ℤ, the scaling identity m * (q * k^2 + a * k + b) = (q * m) * k^2 + (m * a) * k + m * b holds in ℤ. automation
We establish an auxiliary identity named algebra by distributing multiplication by m across the quadratic expression and pushing the cast from ℕ to ℤ across the product q * m, verified by polynomial ring arithmetic.
have algebra (k : ℕ) (a b : ℤ) : (m : ℤ)*((q : ℤ)*(k : ℤ)^2 + a*k+b) = ((q*m:ℕ):ℤ)*(k : ℤ)^2 + ((m : ℤ)*a)*k + (m : ℤ)*b := by push_cast ring
The desired coloring is witnessed by g(z) = f(m * z), reducing the problem to checking that g avoids monochromatic length-3 false progressions and length-17 true progressions.
We instantiate the existential quantifier with the scaled coloring g(z) = f(m * z) and split the conjunction into two subgoals, one for each forbidden pattern.
refine ⟨fun z => f ((m : ℤ)*z), ?_, ?_⟩
The coloring g contains no monochromatic false length-3 quadratic progression with curvature q.
Suppose, for contradiction, that there exist integers a and b such that g(q * k^2 + a * k + b) = false for all k ∈ {0, 1, 2}. Applying the hypothesis h3 with linear coefficient m * a and constant term m * b requires showing f((q * m) * k^2 + (m * a) * k + m * b) = false for each k. For any such k, by definition of g we have f(m * (q * k^2 + a * k + b)) = false, and rewriting via the identity algebra gives f((q * m) * k^2 + (m * a) * k + m * b) = false, reaching a contradiction.
uses
algebra· intro a b hh apply h3 ((m : ℤ)*a) ((m : ℤ)*b) intro k have hk := hh k change f ((m : ℤ)*((q : ℤ)*(k.val : ℤ)^2+a*k.val+b)) = false at hk rw [algebra k.val a b] at hk exact hk
The coloring g contains no monochromatic true length-17 quadratic progression with curvature q.
Suppose, for contradiction, that there exist integers a and b such that g(q * k^2 + a * k + b) = true for all k ∈ {0, ..., 16}. Applying the hypothesis h17 with linear coefficient m * a and constant term m * b reduces the goal to showing f((q * m) * k^2 + (m * a) * k + m * b) = true for each k. For any such k, by definition of g we have f(m * (q * k^2 + a * k + b)) = true, which rewrites by algebra to f((q * m) * k^2 + (m * a) * k + m * b) = true, reaching a contradiction.
uses
algebra· intro a b hh apply h17 ((m : ℤ)*a) ((m : ℤ)*b) intro k have hk := hh k change f ((m : ℤ)*((q : ℤ)*(k.val : ℤ)^2+a*k.val+b)) = true at hk rw [algebra k.val a b] at hk exact hk
algebra- For any natural number k and integers a and b, m * (q * k^2 + a * k + b) = (q * m) * k^2 + (m * a) * k + m * b in the integers.
- The scaling identity relating quadratic progressions of curvature q to those of curvature qm is verified by Lean's ring tactic after pushing casts from ℕ to ℤ.
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 integer_quadratic_coloring_divisor (q m : ℕ) (f : ℤ → Bool) (h3 : ∀ a b : ℤ, ¬ ∀ k : Fin 3, f (((q * m : ℕ) : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = false) (h17 : ∀ a b : ℤ, ¬ ∀ k : Fin 17, f (((q * m : ℕ) : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = true) : ∃ g : ℤ → Bool, (∀ a b : ℤ, ¬ ∀ k : Fin 3, g ((q : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = false) ∧ (∀ a b : ℤ, ¬ ∀ k : Fin 17, g ((q : ℤ) * (k.val : ℤ)^2 + a*k.val+b) = true) := by have algebra (k : ℕ) (a b : ℤ) : (m : ℤ)*((q : ℤ)*(k : ℤ)^2 + a*k+b) = ((q*m:ℕ):ℤ)*(k : ℤ)^2 + ((m : ℤ)*a)*k + (m : ℤ)*b := by push_cast ring refine ⟨fun z => f ((m : ℤ)*z), ?_, ?_⟩ · intro a b hh apply h3 ((m : ℤ)*a) ((m : ℤ)*b) intro k have hk := hh k change f ((m : ℤ)*((q : ℤ)*(k.val : ℤ)^2+a*k.val+b)) = false at hk rw [algebra k.val a b] at hk exact hk · intro a b hh apply h17 ((m : ℤ)*a) ((m : ℤ)*b) intro k have hk := hh k change f ((m : ℤ)*((q : ℤ)*(k.val : ℤ)^2+a*k.val+b)) = true at hk rw [algebra k.val a b] at hk exact hk