AFTD Auto-Formalizing Theoretical Domains

frobenius_extremal_family_eval_eq

theoremverified

For n ≥ 3 and any natural number q, the identity q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) = ((n - 2) * q + 1) * q - (n - 1) * q - 1 holds in the natural numbers.

Statement

theorem frobenius_extremal_family_eval_eq (n q : ℕ) (hn : 3 ≤ n) : q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) = ((n - 2) * q + 1) * q - (n - 1) * q - 1
Source
scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:461
Verified
27 Oct 2026
Axioms
Quot.soundpropext
Used by 1

Read back from the Lean

For all natural numbers $n$ and $q$, if $3 \le n$, then $q \cdot ((n - 2) \cdot q + 1) - q - ((n - 2) \cdot q + 1) = ((n - 2) \cdot q + 1) \cdot q - (n - 1) \cdot q - 1$ (with all operations evaluated in $\mathbb{N}$, where subtraction is truncated at zero and left-associative).

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 rewrites repeated subtractions into $X - Y = X - Z$, where $X = ((n - 2) \cdot q + 1) \cdot q$, using `Nat.sub_sub` and `mul_comm`. Syntactic congruence reduces this to showing the subtrahends $Y$ and $Z$ are equal. Since $n \ge 3$, linear arithmetic gives $n - 1 = (n - 2) + 1$, after which polynomial expansion in the semiring of natural numbers confirms $Y = Z$.

  1. It suffices to show that the subtrahends are equal, namely $q + ((n - 2) \cdot q + 1) = (n - 1) \cdot q + 1$.

    Rewriting the repeated subtractions on both sides as subtracting a sum using `Nat.sub_sub` puts the equation into the form $q \cdot ((n - 2) \cdot q + 1) - (q + ((n - 2) \cdot q + 1)) = ((n - 2) \cdot q + 1) \cdot q - ((n - 1) \cdot q + 1)$. Commuting the factors of the leading product using `mul_comm` makes the minuends identical. By congruence (`congr 1`), it suffices to show that the two subtrahends are equal.

    lines 3–5

    uses Nat.sub_sub, mul_comm

      rw [Nat.sub_sub, Nat.sub_sub]
      rw [mul_comm q ((n - 2) * q + 1)]
      congr 1
  2. $n - 1 = (n - 2) + 1$.

    Since $n \ge 3$, the natural number subtractions do not truncate at zero, so linear integer arithmetic (`omega`) establishes that $n - 1 = (n - 2) + 1$.

    line 6

      have h : n - 1 = (n - 2) + 1 := by omega
  3. $q + ((n - 2) \cdot q + 1) = (n - 1) \cdot q + 1$.

    Rewriting $n - 1$ as $(n - 2) + 1$ produces expressions that expand to the same polynomial in $(n - 2)$ and $q$, which standard semiring simplification (`ring`) closes.

    lines 7–8

      rw [h]
      ring
Nat.sub_sub
For natural numbers, subtracting two numbers in succession equals subtracting their sum: $n - m - k = n - (m + k)$.
mul_comm
Multiplication is commutative: $a \cdot b = b \cdot a$.

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

/-- Algebraic simplification of the two-generator Frobenius formula for S_{n,q}. -/theorem frobenius_extremal_family_eval_eq (n q : ℕ) (hn : 3 ≤ n) : q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) = ((n - 2) * q + 1) * q - (n - 1) * q - 1 := by  rw [Nat.sub_sub, Nat.sub_sub]  rw [mul_comm q ((n - 2) * q + 1)]  congr 1  have h : n - 1 = (n - 2) + 1 := by omega  rw [h]  ring
See it in the graphDiscuss this resultChallenge it