AFTD Auto-Formalizing Theoretical Domains

integer_quadratic_coloring_divisor

theoremverified

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.

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

    lines 2–6

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

    line 7

      refine ⟨fun z => f ((m : ℤ)*z), ?_, ?_⟩
  3. 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.

    lines 8–14

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

    lines 15–21

    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.

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