schur_two_lower_bound
For 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 otherwise contains no monochromatic solution to (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1.
Statement
theorem schur_two_lower_bound (k : ℕ) (hk : 3 ≤ k) : ¬ ∃ 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
- Source
- arXiv:2611.01714 Proposition 3.1
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- 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 \ge 3$, there do not exist elements $x, y, z \in \mathrm{Fin}(k^2 + k - 2)$ such that: 1. $x.val + 1$, $y.val + 1$, and $z.val + 1$ all have the same color under the 2-coloring $c : \mathbb{N} \to \mathrm{Fin}(2)$ defined by $c(n) = 0$ if $n \le k - 1 \lor k^2 \le n$, and $c(n) = 1$ otherwise (that is, $c(x.val + 1) = c(y.val + 1)$ and $c(y.val + 1) = c(z.val + 1)$); and 2. $(x.val + 1) + (k - 1) \cdot (y.val + 1) = z.val + 1$.
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 proof proceeds by contradiction, assuming there exists a monochromatic solution (x, y, z) to (x + 1) + (k - 1) * (y + 1) = z + 1 in {1, ..., k^2 + k - 2}. Setting vx = x + 1, vy = y + 1, vz = z + 1, it splits into two cases depending on the color of vx. If vx has color 0 (in [1, k - 1] ∪ [k^2, ∞)), subcases on vy and vx show that vz either falls strictly between k - 1 and k^2 (violating color 0) or exceeds the domain bound k^2 + k - 2. If vx has color 1 (in [k, k^2 - 1]), then vy ≥ k and vx ≥ k force vz = vx + (k - 1)vy ≥ k + (k - 1)k = k^2, directly contradicting vz < k^2.
Assume for contradiction that a monochromatic solution exists, introduce shifted variables vx, vy, vz, and establish their range bounds.
We assume for contradiction that there exist x, y, z in Fin (k^2 + k - 2) of the same color satisfying (x + 1) + (k - 1) * (y + 1) = z + 1. We define vx = x.val + 1, vy = y.val + 1, and vz = z.val + 1. Since x, y ≥ 0, we have 1 ≤ vx and 1 ≤ vy. Furthermore, since z.val < k^2 + k - 2 by `z.isLt`, we obtain vz ≤ k^2 + k - 2.
intro ⟨x, y, z, hxy, hyz, heq⟩ set vx := x.val + 1 set vy := y.val + 1 set vz := z.val + 1 have hz_lt : vz ≤ k^2 + k - 2 := by have := z.isLt omega have hvx_pos : 1 ≤ vx := by omega have hvy_pos : 1 ≤ vy := by omega
In Case 1, where vx has color 0, vy and vz must also have color 0.
We perform a case split on whether vx has color 0, that is, vx ≤ k - 1 ∨ k^2 ≤ vx. Under this hypothesis, the color of vx simplifies to 0. Since x and y have the same color, vy cannot have color 1 (which would mean 0 = 1), so vy must also have color 0 (vy ≤ k - 1 ∨ k^2 ≤ vy). Similarly, since y and z share the same color, vz must also have color 0 (vz ≤ k - 1 ∨ k^2 ≤ vz).
by_cases hx : vx ≤ k - 1 ∨ k^2 ≤ vx · -- Color 0 simp only [hx, ↓reduceIte] at hxy have hy : vy ≤ k - 1 ∨ k^2 ≤ vy := by by_contra hny simp [hny] at hxy simp only [hy, ↓reduceIte] at hyz have hz : vz ≤ k - 1 ∨ k^2 ≤ vz := by by_contra hnz simp [hnz] at hyz
If both vy ≤ k - 1 and vx ≤ k - 1, then k ≤ vz < k^2, contradicting that vz has color 0.
We split into subcases on vy. In the subcase vy ≤ k - 1, we further split on vx. When vx ≤ k - 1, we lower-bound vz = vx + (k - 1) * vy: since vx ≥ 1 and vy ≥ 1, multiplying 1 ≤ vy by k - 1 with `Nat.mul_le_mul_left` gives k - 1 ≤ (k - 1) * vy, so vz ≥ 1 + (k - 1) = k. For the upper bound, multiplying vy ≤ k - 1 by k - 1 gives (k - 1) * vy ≤ (k - 1)^2, so vz ≤ (k - 1) + (k - 1)^2 = (k - 1) * k. Since k - 1 < k and k > 0, `Nat.mul_lt_mul_of_pos_right` and `sq` give (k - 1) * k < k^2. Thus k ≤ vz < k^2, which contradicts vz ≤ k - 1 ∨ k^2 ≤ vz.
uses
Nat.mul_le_mul_left,Nat.mul_lt_mul_of_pos_right,sqrcases hy with hy | hy · -- vy ≤ k - 1 rcases hx with hx | hx · -- vx ≤ k - 1 have h_low1 : (k - 1) * 1 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hvy_pos have h_low : k ≤ vz := by omega have h_up1 : (k - 1) * vy ≤ (k - 1) * (k - 1) := Nat.mul_le_mul_left _ hy have h_up3 : (k - 1) * k < k^2 := by have hk_pos : 0 < k := by omega have h_lt : k - 1 < k := by omega have := Nat.mul_lt_mul_of_pos_right h_lt hk_pos rw [sq] omega have h_up : vz ≤ (k - 1) * k := by have : vx + (k - 1) * vy ≤ (k - 1) + (k - 1) * (k - 1) := by omega have : (k - 1) + (k - 1) * (k - 1) = (k - 1) * k := by have : 1 ≤ k := by omega zify [this] ring omega omega
If vy ≤ k - 1 and k^2 ≤ vx, then vz > k^2 + k - 2, contradicting the domain bound vz ≤ k^2 + k - 2.
In the second subcase for vx, we have k^2 ≤ vx. Since 1 ≤ vy, multiplying by k - 1 on the left via `Nat.mul_le_mul_left` gives k - 1 ≤ (k - 1) * vy. Thus vz = vx + (k - 1) * vy ≥ k^2 + k - 1, which strictly exceeds the upper bound k^2 + k - 2, a contradiction detected by linear arithmetic (`omega`).
uses
Nat.mul_le_mul_left· -- k^2 ≤ vx have : (k - 1) * 1 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hvy_pos omega
If k^2 ≤ vy, then vz > k^2 + k - 2, contradicting vz ≤ k^2 + k - 2.
In the remaining subcase for vy, we have k^2 ≤ vy. Multiplying on the left by k - 1 via `Nat.mul_le_mul_left` yields (k - 1) * k^2 ≤ (k - 1) * vy. Since k ≥ 3, we have 2 ≤ k - 1, and multiplying by k^2 on the right with `Nat.mul_le_mul_right` gives 2 * k^2 ≤ (k - 1) * k^2. Since k ≤ k^2 by `Nat.le_self_pow`, vz ≥ 1 + 2 * k^2 > k^2 + k - 2, which contradicts vz ≤ k^2 + k - 2.
uses
Nat.mul_le_mul_left,Nat.mul_le_mul_right,Nat.le_self_pow· -- k^2 ≤ vy have : (k - 1) * k^2 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hy have hk' : 2 ≤ k - 1 := by omega have : 2 * k^2 ≤ (k - 1) * k^2 := Nat.mul_le_mul_right (k^2) hk' have : k ≤ k^2 := Nat.le_self_pow (by omega) k omega
In Case 2, where vx has color 1, vy and vz must also have color 1.
When vx does not satisfy the color 0 condition, its color is 1. Simplifying the hypothesis hxy reduces it to 1 = ..., so assuming vy has color 0 leads to 1 = 0, a contradiction; hence vy has color 1. Repeating the same reasoning on hyz shows that vz must also have color 1.
· -- Color 1 simp only [hx, ↓reduceIte] at hxy have hy : ¬(vy ≤ k - 1 ∨ k^2 ≤ vy) := by intro hy' simp [hy'] at hxy simp only [hy, ↓reduceIte] at hyz have hz : ¬(vz ≤ k - 1 ∨ k^2 ≤ vz) := by intro hz' simp [hz'] at hyz
Color 1 implies k ≤ vx, k ≤ vy, and vz < k^2, which forces vz ≥ k^2, a contradiction.
Having color 1 means failing the condition v ≤ k - 1 ∨ k^2 ≤ v, which translates to k ≤ vx, k ≤ vy, and vz < k^2. Multiplying k ≤ vy on the left by k - 1 with `Nat.mul_le_mul_left` yields (k - 1) * k ≤ (k - 1) * vy. Then vz = vx + (k - 1) * vy ≥ k + (k - 1) * k = k^2. But vz ≥ k^2 contradicts vz < k^2, completing the proof.
uses
Nat.mul_le_mul_lefthave hk1 : k ≤ vx := by omega have hk2 : k ≤ vy := by omega have hk3 : vz < k^2 := by omega have h_bound : k^2 ≤ vz := by calc k^2 = k + (k - 1) * k := by have : 1 ≤ k := by omega zify [this] ring _ ≤ vx + (k - 1) * vy := by have : (k - 1) * k ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hk2 omega _ = vz := heq omega
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers n ≤ m on the left by k preserves the inequality (k * n ≤ k * m).
Nat.mul_lt_mul_of_pos_right- Multiplying a strict inequality of natural numbers n < m on the right by a positive natural number k > 0 preserves strict inequality (n * k < m * k).
sq- The square of an element a ^ 2 is defined as a * a.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers n ≤ m on the right by k preserves the inequality (n * k ≤ m * k).
Nat.le_self_pow- Any natural number a is less than or equal to a ^ n provided the exponent n is nonzero.
- Identities involving natural number subtraction such as (k - 1) + (k - 1) * (k - 1) = (k - 1) * k are proved formally via `zify` and `ring`, which cast to the integers ℤ to allow standard polynomial arithmetic.
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.
/-- For every integer k ≥ 3, the 2-coloring of Fin (k^2 + k - 2) with A₁ = [1, k-1] ∪ [k^2, k^2+k-2] and A₂ = [k, k^2-1] contains no monochromatic solution to (x.val + 1) + (k - 1) * (y.val + 1) = z.val + 1. -/theorem schur_two_lower_bound (k : ℕ) (hk : 3 ≤ k) : ¬ ∃ 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 := by intro ⟨x, y, z, hxy, hyz, heq⟩ set vx := x.val + 1 set vy := y.val + 1 set vz := z.val + 1 have hz_lt : vz ≤ k^2 + k - 2 := by have := z.isLt omega have hvx_pos : 1 ≤ vx := by omega have hvy_pos : 1 ≤ vy := by omega by_cases hx : vx ≤ k - 1 ∨ k^2 ≤ vx · -- Color 0 simp only [hx, ↓reduceIte] at hxy have hy : vy ≤ k - 1 ∨ k^2 ≤ vy := by by_contra hny simp [hny] at hxy simp only [hy, ↓reduceIte] at hyz have hz : vz ≤ k - 1 ∨ k^2 ≤ vz := by by_contra hnz simp [hnz] at hyz rcases hy with hy | hy · -- vy ≤ k - 1 rcases hx with hx | hx · -- vx ≤ k - 1 have h_low1 : (k - 1) * 1 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hvy_pos have h_low : k ≤ vz := by omega have h_up1 : (k - 1) * vy ≤ (k - 1) * (k - 1) := Nat.mul_le_mul_left _ hy have h_up3 : (k - 1) * k < k^2 := by have hk_pos : 0 < k := by omega have h_lt : k - 1 < k := by omega have := Nat.mul_lt_mul_of_pos_right h_lt hk_pos rw [sq] omega have h_up : vz ≤ (k - 1) * k := by have : vx + (k - 1) * vy ≤ (k - 1) + (k - 1) * (k - 1) := by omega have : (k - 1) + (k - 1) * (k - 1) = (k - 1) * k := by have : 1 ≤ k := by omega zify [this] ring omega omega · -- k^2 ≤ vx have : (k - 1) * 1 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hvy_pos omega · -- k^2 ≤ vy have : (k - 1) * k^2 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hy have hk' : 2 ≤ k - 1 := by omega have : 2 * k^2 ≤ (k - 1) * k^2 := Nat.mul_le_mul_right (k^2) hk' have : k ≤ k^2 := Nat.le_self_pow (by omega) k omega · -- Color 1 simp only [hx, ↓reduceIte] at hxy have hy : ¬(vy ≤ k - 1 ∨ k^2 ≤ vy) := by intro hy' simp [hy'] at hxy simp only [hy, ↓reduceIte] at hyz have hz : ¬(vz ≤ k - 1 ∨ k^2 ≤ vz) := by intro hz' simp [hz'] at hyz have hk1 : k ≤ vx := by omega have hk2 : k ≤ vy := by omega have hk3 : vz < k^2 := by omega have h_bound : k^2 ≤ vz := by calc k^2 = k + (k - 1) * k := by have : 1 ≤ k := by omega zify [this] ring _ ≤ vx + (k - 1) * vy := by have : (k - 1) * k ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hk2 omega _ = vz := heq omega