frobenius_extremal_family_eval_eq
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
- frobenius_extremal_family_frobenius_numberFor any integers n ≥ 3 and q ≥ 2, the Frobenius number of the extremal family
frobenius_extremal_family n qis equal to ((n - 2) * q +…
- frobenius_extremal_family_frobenius_numberFor any integers n ≥ 3 and q ≥ 2, the Frobenius number of the extremal family
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$.
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.
uses
Nat.sub_sub,mul_commrw [Nat.sub_sub, Nat.sub_sub] rw [mul_comm q ((n - 2) * q + 1)] congr 1
$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$.
have h : n - 1 = (n - 2) + 1 := by omega
$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.
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$.
- In natural number arithmetic, subtraction truncates at zero ($a - b = 0$ for $a \le b$), so subtraction is not generally cancellative; `congr 1` succeeds here purely syntactically because both sides subtract from the identical minuend.
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.
/-- 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