AFTD Auto-Formalizing Theoretical Domains

schur_two_lower_bound

theoremverified

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

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.

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

    lines 9–17

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

    lines 18–27

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

    lines 28–48

    uses Nat.mul_le_mul_left, Nat.mul_lt_mul_of_pos_right, sq

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

    lines 49–51

    uses Nat.mul_le_mul_left

          · -- k^2 ≤ vx
            have : (k - 1) * 1 ≤ (k - 1) * vy := Nat.mul_le_mul_left _ hvy_pos
            omega
  5. 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.

    lines 52–57

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

    lines 58–66

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

    lines 67–79

    uses Nat.mul_le_mul_left

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

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

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