AFTD Auto-Formalizing Theoretical Domains

schur_two_upper_bound

theoremverified

For 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 + 1) = z.val + 1.

Statement

theorem schur_two_upper_bound (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
Source
arXiv:2611.01714 Proposition 3.1
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

For every natural number $k$ with $k \ge 3$ and every 2-coloring $c : \text{Fin}(k^2 + k - 1) \to \text{Fin}(2)$, there exist $x, y, z \in \text{Fin}(k^2 + k - 1)$ such that $c(x) = c(y)$, $c(y) = c(z)$, and $(x.\text{val} + 1) + (k - 1) \cdot (y.\text{val} + 1) = z.\text{val} + 1$ in $\mathbb{N}$. In terms of the integers $\{1, 2, \dots, k^2 + k - 1\}$, this asserts the existence of a monochromatic solution $(X, Y, Z)$ to the linear equation $X + (k - 1) Y = Z$.

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

To show that 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 for k ≥ 3, the proof selects five strategic points: p0 = 0, p1 = k - 1, p2 = k, p3 = k^2 - 1, and p4 = k^2 + k - 2. These five points are constructed so that five candidate triples—(p0, p0, p1), (p1, p1, p3), (p0, p2, p3), (p3, p0, p4), and (p1, p2, p4)—each satisfy the generalized Schur equation. A combinatorial helper lemma, verified by the `decide` tactic over all 2^5 = 32 possible 2-colorings of five elements, ensures that at least one of these five triples is monochromatic under any 2-coloring. Finally, a five-way case analysis immediately exhibits the monochromatic solution in every case.

  1. Any 2-coloring of a 5-element set satisfies at least one of five specific monochromatic patterns.

    For any function f : Fin 5 → Fin 2, we show that f 0 = f 1, f 1 = f 3, f 0 = f 2 = f 3, f 3 = f 0 = f 4, or f 1 = f 2 = f 4. Moving f into the goal with `revert`, Lean's `decide` tactic checks all 2^5 = 32 possible colorings exhaustively.

    lines 1–7

    private lemma schur_two_upper_bound_five_color_lemma (f : Fin 5 → Fin 2) :
        (f 0 = f 1) ∨ (f 1 = f 3) ∨
        (f 0 = f 2 ∧ f 2 = f 3) ∨
        (f 3 = f 0 ∧ f 0 = f 4) ∨
        (f 1 = f 2 ∧ f 2 = f 4) := by
      revert f
      decide
  2. For k ≥ 3, five valid indices p0, p1, p2, p3, p4 in Fin (k^2 + k - 1) and their successor identities are well-defined.

    From k ≥ 3, linear integer arithmetic (`omega`) gives 1 ≤ k and 0 < k. Using `pow_pos`, k^2 is positive, and using `le_self_pow`, k ≤ k^2. Five elements p0 = 0, p1 = k - 1, p2 = k, p3 = k^2 - 1, and p4 = k^2 + k - 2 are defined in Fin (k^2 + k - 1), each strictly less than k^2 + k - 1 by linear arithmetic (`omega`). Three predecessor-successor identities ((k - 1) + 1 = k, (k^2 - 1) + 1 = k^2, and (k^2 + k - 2) + 1 = k^2 + k - 1) are also established by `omega`.

    lines 8–24

    uses pow_pos, le_self_pow

    /-- 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. -/
    theorem schur_two_upper_bound (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 := by
      have hk1 : 1 ≤ k := by omega
      have hkpos : 0 < k := by omega
      have hsqpos : 0 < k ^ 2 := pow_pos hkpos 2
      have hsqge : k ≤ k ^ 2 := le_self_pow hk1 (by norm_num : (2:ℕ) ≠ 0)
      let p0 : Fin (k ^ 2 + k - 1) := ⟨0, by omega⟩
      let p1 : Fin (k ^ 2 + k - 1) := ⟨k - 1, by omega⟩
      let p2 : Fin (k ^ 2 + k - 1) := ⟨k, by omega⟩
      let p3 : Fin (k ^ 2 + k - 1) := ⟨k ^ 2 - 1, by omega⟩
      let p4 : Fin (k ^ 2 + k - 1) := ⟨k ^ 2 + k - 2, by omega⟩
      have h1 : k - 1 + 1 = k := by omega
      have hsq1 : k ^ 2 - 1 + 1 = k ^ 2 := by omega
      have hlast : k ^ 2 + k - 2 + 1 = k ^ 2 + k - 1 := by omega
  3. The generalized Schur equation holds for five specific triples among the chosen points.

    Letting P_i = p_i.val + 1, the values are P_0 = 1, P_1 = k, P_2 = k + 1, P_3 = k^2, and P_4 = k^2 + k - 1. We verify by expanding definitions, substituting the successor identities, and applying arithmetic automation (`omega` and `nlinarith [hk]`) that the equation X + (k - 1)Y = Z holds for: (1) e1 with (P_0, P_0, P_1), giving 1 + (k - 1) = k; (2) e2 with (P_1, P_1, P_3), giving k + (k - 1)k = k^2; (3) e3 with (P_0, P_2, P_3), giving 1 + (k - 1)(k + 1) = k^2; (4) e4 with (P_3, P_0, P_4), giving k^2 + (k - 1) = k^2 + k - 1; and (5) e5 with (P_1, P_2, P_4), giving k + (k - 1)(k + 1) = k^2 + k - 1.

    lines 25–43

      have e1 : (p0.val + 1) + (k - 1) * (p0.val + 1) = p1.val + 1 := by
        simp [p0, p1]
        omega
      have e2 : (p1.val + 1) + (k - 1) * (p1.val + 1) = p3.val + 1 := by
        simp [p1, p3]
        rw [h1, hsq1]
        nlinarith [hk]
      have e3 : (p0.val + 1) + (k - 1) * (p2.val + 1) = p3.val + 1 := by
        simp [p0, p2, p3]
        rw [hsq1]
        nlinarith [hk]
      have e4 : (p3.val + 1) + (k - 1) * (p0.val + 1) = p4.val + 1 := by
        simp [p0, p3, p4]
        rw [hsq1, hlast]
        omega
      have e5 : (p1.val + 1) + (k - 1) * (p2.val + 1) = p4.val + 1 := by
        simp [p1, p2, p4]
        rw [h1, hlast]
        nlinarith [hk]
  4. Under any 2-coloring c, at least one of the five candidate triples is monochromatic.

    We apply schur_two_upper_bound_five_color_lemma to the coloring of the 5-element sequence ![p0, p1, p2, p3, p4]. Simplifying the index evaluations with `simpa` yields the disjunction hfive: c p0 = c p1, or c p1 = c p3, or c p0 = c p2 = c p3, or c p3 = c p0 = c p4, or c p1 = c p2 = c p4.

    lines 44–50

    uses schur_two_upper_bound_five_color_lemma

      have hfive : (c p0 = c p1) ∨ (c p1 = c p3) ∨
          (c p0 = c p2 ∧ c p2 = c p3) ∨
          (c p3 = c p0 ∧ c p0 = c p4) ∨
          (c p1 = c p2 ∧ c p2 = c p4) := by
        have h := schur_two_upper_bound_five_color_lemma
          (fun i : Fin 5 => c (![p0, p1, p2, p3, p4] i))
        simpa using h
  5. There exist monochromatic x, y, z in Fin (k^2 + k - 1) satisfying (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1.

    We split cases (`rcases`) on the five disjuncts of hfive. In each case, the corresponding triple ((p0, p0, p1), (p1, p1, p3), (p0, p2, p3), (p3, p0, p4), or (p1, p2, p4)) is monochromatic by the case hypothesis and satisfies the equation by the matching identity (e1, e2, e3, e4, or e5), concluding the proof.

    lines 51–56

      rcases hfive with h | h | h | h | h
      · exact ⟨p0, p0, p1, rfl, h, e1⟩
      · exact ⟨p1, p1, p3, rfl, h, e2⟩
      · exact ⟨p0, p2, p3, h.1, h.2, e3⟩
      · exact ⟨p3, p0, p4, h.1, h.2, e4⟩
      · exact ⟨p1, p2, p4, h.1, h.2, e5⟩
pow_pos
In an ordered monoid with zero, raising a strictly positive element to any natural power yields a strictly positive element.
le_self_pow
In an ordered monoid, an element greater than or equal to 1 is less than or equal to any of its non-zero natural powers.
schur_two_upper_bound_five_color_lemma
Every 2-coloring of a 5-element set satisfies at least one of five specific monochromatic patterns: f 0 = f 1, f 1 = f 3, f 0 = f 2 = f 3, f 3 = f 0 = f 4, or f 1 = f 2 = f 4.

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

private lemma schur_two_upper_bound_five_color_lemma (f : Fin 5 → Fin 2) :    (f 0 = f 1) ∨ (f 1 = f 3) ∨    (f 0 = f 2 ∧ f 2 = f 3) ∨    (f 3 = f 0 ∧ f 0 = f 4) ∨    (f 1 = f 2 ∧ f 2 = f 4) := by  revert f  decide/-- 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. -/theorem schur_two_upper_bound (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 := by  have hk1 : 1 ≤ k := by omega  have hkpos : 0 < k := by omega  have hsqpos : 0 < k ^ 2 := pow_pos hkpos 2  have hsqge : k ≤ k ^ 2 := le_self_pow hk1 (by norm_num : (2:ℕ) ≠ 0)  let p0 : Fin (k ^ 2 + k - 1) := ⟨0, by omega⟩  let p1 : Fin (k ^ 2 + k - 1) := ⟨k - 1, by omega⟩  let p2 : Fin (k ^ 2 + k - 1) := ⟨k, by omega⟩  let p3 : Fin (k ^ 2 + k - 1) := ⟨k ^ 2 - 1, by omega⟩  let p4 : Fin (k ^ 2 + k - 1) := ⟨k ^ 2 + k - 2, by omega⟩  have h1 : k - 1 + 1 = k := by omega  have hsq1 : k ^ 2 - 1 + 1 = k ^ 2 := by omega  have hlast : k ^ 2 + k - 2 + 1 = k ^ 2 + k - 1 := by omega  have e1 : (p0.val + 1) + (k - 1) * (p0.val + 1) = p1.val + 1 := by    simp [p0, p1]    omega  have e2 : (p1.val + 1) + (k - 1) * (p1.val + 1) = p3.val + 1 := by    simp [p1, p3]    rw [h1, hsq1]    nlinarith [hk]  have e3 : (p0.val + 1) + (k - 1) * (p2.val + 1) = p3.val + 1 := by    simp [p0, p2, p3]    rw [hsq1]    nlinarith [hk]  have e4 : (p3.val + 1) + (k - 1) * (p0.val + 1) = p4.val + 1 := by    simp [p0, p3, p4]    rw [hsq1, hlast]    omega  have e5 : (p1.val + 1) + (k - 1) * (p2.val + 1) = p4.val + 1 := by    simp [p1, p2, p4]    rw [h1, hlast]    nlinarith [hk]  have hfive : (c p0 = c p1) ∨ (c p1 = c p3) ∨      (c p0 = c p2 ∧ c p2 = c p3) ∨      (c p3 = c p0 ∧ c p0 = c p4) ∨      (c p1 = c p2 ∧ c p2 = c p4) := by    have h := schur_two_upper_bound_five_color_lemma      (fun i : Fin 5 => c (![p0, p1, p2, p3, p4] i))    simpa using h  rcases hfive with h | h | h | h | h  · exact ⟨p0, p0, p1, rfl, h, e1⟩  · exact ⟨p1, p1, p3, rfl, h, e2⟩  · exact ⟨p0, p2, p3, h.1, h.2, e3⟩  · exact ⟨p3, p0, p4, h.1, h.2, e4⟩  · exact ⟨p1, p2, p4, h.1, h.2, e5⟩
See it in the graphDiscuss this resultChallenge it