AFTD Auto-Formalizing Theoretical Domains

two_color_generalized_schur_number_prop31

theoremverifiedformalization

For every integer k ≥ 3, every 2-coloring of Fin (k^2 + k - 1) admits a monochromatic solution to (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1, and the 2-coloring of Fin (k^2 + k - 2) defined by color 0 on [1, k-1] ∪ [k^2, k^2+k-2] and color 1 on [k, k^2-1] contains no monochromatic solution.

Statement

theorem two_color_generalized_schur_number_prop31 (k : ℕ) (hk : 3 ≤ k) :
    (∀ c : Fin (k^2 + k - 1) → Fin 2,
      ∃ x y z : Fin (k^2 + k - 1), c x = c y ∧ c y = c z ∧
        (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1) ∧
    ¬ ∃ x y z : Fin (k^2 + k - 2),
      (if x.val + 1 ≤ k - 1 ∨ k^2 ≤ x.val + 1 then (0 : Fin 2) else 1) =
        (if y.val + 1 ≤ k - 1 ∨ k^2 ≤ y.val + 1 then (0 : Fin 2) else 1) ∧
      (if y.val + 1 ≤ k - 1 ∨ k^2 ≤ y.val + 1 then (0 : Fin 2) else 1) =
        (if z.val + 1 ≤ k - 1 ∨ k^2 ≤ z.val + 1 then (0 : Fin 2) else 1) ∧
      (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1
Formalizes
arXiv:2611.01714 Proposition 3.1
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • schur_two_upper_boundFor every integer k ≥ 3, every 2-coloring c : Fin (k^2 + k - 1) → Fin 2 admits a monochromatic solution to (x.val + 1) + (k - 1) * (y.val…
  • schur_two_lower_boundFor every integer k ≥ 3, the 2-coloring of Fin (k^2 + k - 2) that assigns color 0 when x.val + 1 ≤ k - 1 ∨ k^2 ≤ x.val + 1 and color 1…

Read back from the Lean

For any natural number $k$ with $3 \le k$: 1. For every 2-coloring $c : \mathrm{Fin}(k^2 + k - 1) \to \mathrm{Fin}(2)$, there exist elements $x, y, z \in \mathrm{Fin}(k^2 + k - 1)$ such that $c(x) = c(y)$, $c(y) = c(z)$, and $$(x.\mathrm{val} + 1) + (k - 1)(y.\mathrm{val} + 1) = z.\mathrm{val} + 1$$ 2. And there do not exist $x, y, z \in \mathrm{Fin}(k^2 + k - 2)$ such that $$\chi(x) = \chi(y) \land \chi(y) = \chi(z) \land (x.\mathrm{val} + 1) + (k - 1)(y.\mathrm{val} + 1) = z.\mathrm{val} + 1$$ where $\chi(w) : \mathrm{Fin}(k^2 + k - 2) \to \mathrm{Fin}(2)$ is the coloring defined by: $\chi(w) = 0$ if $w.\mathrm{val} + 1 \le k - 1$ or $k^2 \le w.\mathrm{val} + 1$, and $\chi(w) = 1$ otherwise.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem establishes that the two-color generalized Schur number for the equation x + (k - 1)y = z is k^2 + k - 1 for all k ≥ 3. It is stated as a conjunction of an upper bound (every 2-coloring of {1, ..., k^2 + k - 1} admits a monochromatic solution) and a lower bound (an explicit 2-coloring of {1, ..., k^2 + k - 2} avoids monochromatic solutions). The proof combines the two corresponding lemmas, `schur_two_upper_bound` and `schur_two_lower_bound`, into a pair.

  1. Both the upper bound and the lower bound hold for the generalized Schur number.

    The theorem asserts the conjunction of two facts: that every 2-coloring of the first k^2 + k - 1 positive integers admits a monochromatic solution to x + (k - 1)y = z, and that the specified 2-coloring on the first k^2 + k - 2 positive integers avoids any monochromatic solution. The proof constructs the conjunction pair directly from the upper bound lemma `schur_two_upper_bound` and the lower bound lemma `schur_two_lower_bound`.

    line 11

    uses schur_two_upper_bound, schur_two_lower_bound

          (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1 := ⟨schur_two_upper_bound k hk, schur_two_lower_bound k hk⟩
schur_two_upper_bound
For any k ≥ 3, every 2-coloring of {1, ..., k^2 + k - 1} contains a monochromatic solution to x + (k - 1)y = z.
schur_two_lower_bound
For any k ≥ 3, the explicit 2-coloring of {1, ..., k^2 + k - 2} (color 0 on [1, k-1] ∪ [k^2, k^2+k-2] and color 1 on [k, k^2-1]) has no monochromatic solution to x + (k - 1)y = z.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Proposition 3.1: Two-color generalized Schur number T_k(2) = k^2 + k - 1 for x + (k - 1)y = z. -/theorem two_color_generalized_schur_number_prop31 (k : ℕ) (hk : 3 ≤ k) :    (∀ c : Fin (k^2 + k - 1) → Fin 2,      ∃ x y z : Fin (k^2 + k - 1), c x = c y ∧ c y = c z ∧        (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1) ∧    ¬ ∃ x y z : Fin (k^2 + k - 2),      (if x.val + 1 ≤ k - 1 ∨ k^2 ≤ x.val + 1 then (0 : Fin 2) else 1) =        (if y.val + 1 ≤ k - 1 ∨ k^2 ≤ y.val + 1 then (0 : Fin 2) else 1) ∧      (if y.val + 1 ≤ k - 1 ∨ k^2 ≤ y.val + 1 then (0 : Fin 2) else 1) =        (if z.val + 1 ≤ k - 1 ∨ k^2 ≤ z.val + 1 then (0 : Fin 2) else 1) ∧      (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1 := ⟨schur_two_upper_bound k hk, schur_two_lower_bound k hk⟩
See it in the graphDiscuss this resultChallenge it