schur_two_upper_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- two_color_generalized_schur_number_prop31For 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) =…
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.
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.
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 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`.
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
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.
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]
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.
uses
schur_two_upper_bound_five_color_lemmahave 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
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.
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.
- The elements of Fin (k^2 + k - 1) are 0-indexed integers strictly less than k^2 + k - 1. In the equation, each element is shifted by 1 (e.g., x.val + 1), which corresponds to using 1-based integers 1, 2, ..., k^2 + k - 1 in standard mathematical statements of Schur-type theorems.
- The helper lemma schur_two_upper_bound_five_color_lemma is proved by the `decide` tactic, which exhaustively checks all 2^5 = 32 possible 2-colorings of a 5-element set via computational reflection.
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.
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⟩