frobenius_extremal_family_frobenius_number
For any integers n ≥ 3 and q ≥ 2, the Frobenius number of the extremal family frobenius_extremal_family n q is equal to ((n - 2) * q + 1) * q - (n - 1) * q - 1.
Statement
theorem frobenius_extremal_family_frobenius_number (n q : ℕ) (hn : 3 ≤ n) (hq : 2 ≤ q) : FrobeniusNumber (((n - 2) * q + 1) * q - (n - 1) * q - 1) (frobenius_extremal_family n q)- Formalizes
- scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:450
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- frobenius_extremal_familyFor natural numbers n and q,
frobenius_extremal_family n qis the set of natural numbers consisting of all multiples i * q for 1 ≤ i ≤ n… - frobenius_extremal_family_coprimeFor any natural numbers n and q, the numbers q and (n - 2) * q + 1 are coprime.
- frobenius_extremal_family_closure_eqFor n ≥ 2, the additive submonoid closure of
frobenius_extremal_family n qequals the additive submonoid closure of the pair {q, (n - 2)… - frobenius_extremal_family_eval_eqFor 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…
- frobenius_extremal_familyFor natural numbers n and q,
Read back from the Lean
For all natural numbers $n$ and $q$, if $3 \le n$ and $2 \le q$, then the predicate FrobeniusNumber holds for the value $(((n - 2) \cdot q + 1) \cdot q - (n - 1) \cdot q - 1)$ and the set frobenius_extremal_family n q.
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 reduces computing the Frobenius number of the extremal family to the classical two-generator Frobenius problem. First, it replaces the family with the two generators q and (n - 2) * q + 1, which generate the same additive submonoid, and rewrites the target value into Sylvester's form a * b - a - b. Applying Sylvester's formula (frobeniusNumber_pair) then finishes the argument once the hypotheses—coprimality and that both generators exceed 1—are verified from n ≥ 3 and q ≥ 2.
The additive submonoid generated by the extremal family frobenius_extremal_family n q equals the submonoid generated by {q, (n - 2) * q + 1}.
By frobenius_extremal_family_closure_eq, the closures coincide whenever 2 ≤ n. This condition is discharged by linear arithmetic (omega) since n ≥ 3.
uses
frobenius_extremal_family_closure_eqhave h_closure : AddSubmonoid.closure (frobenius_extremal_family n q) = AddSubmonoid.closure {q, (n - 2) * q + 1} := frobenius_extremal_family_closure_eq n q (by omega)
The target value ((n - 2) * q + 1) * q - (n - 1) * q - 1 equals q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1).
By frobenius_extremal_family_eval_eq, using the assumption n ≥ 3 (hn), the formula matches the form a * b - a - b for generators a = q and b = (n - 2) * q + 1.
uses
frobenius_extremal_family_eval_eqhave h_eval : q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) = ((n - 2) * q + 1) * q - (n - 1) * q - 1 := frobenius_extremal_family_eval_eq n q hnIt suffices to show that the Frobenius number of {q, (n - 2) * q + 1} is q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1).
Unfolding the definition of FrobeniusNumber, substituting the submonoid equality h_closure and the arithmetic identity h_eval, and folding the definition back simplifies the goal to computing the Frobenius number of the two generators {q, (n - 2) * q + 1}.
uses
FrobeniusNumberrw [FrobeniusNumber] rw [h_closure] rw [← h_eval] change FrobeniusNumber (q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1)) {q, (n - 2) * q + 1}
The goal reduces to checking the conditions of Sylvester's formula: coprimality of q and (n - 2) * q + 1, and that both strictly exceed 1.
Applying Sylvester's formula frobeniusNumber_pair reduces finding the Frobenius number of a pair {m, n} to verifying that m and n are coprime and each is greater than 1.
uses
frobeniusNumber_pairapply frobeniusNumber_pairq and (n - 2) * q + 1 are coprime.
This coprimality condition is supplied directly by frobenius_extremal_family_coprime.
uses
frobenius_extremal_family_coprime· exact frobenius_extremal_family_coprime n q1 < q.
This follows immediately from the hypothesis 2 ≤ q (hq).
· exact hq1 < (n - 2) * q + 1.
From n ≥ 3, linear integer arithmetic gives 1 ≤ n - 2. Multiplying by q using Nat.mul_le_mul_right yields q ≤ (n - 2) * q. Since q ≥ 2, linear arithmetic (omega) concludes that (n - 2) * q + 1 ≥ 3 > 1.
uses
Nat.mul_le_mul_right· have h1 : 1 ≤ n - 2 := by omega have h2 : 1 * q ≤ (n - 2) * q := Nat.mul_le_mul_right q h1 omega
frobenius_extremal_family_closure_eq- For n ≥ 2, the additive submonoid generated by the extremal family is equal to the additive submonoid generated by the two-element set {q, (n - 2) * q + 1}.
frobenius_extremal_family_eval_eq- For n ≥ 3, the expression q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) simplifies to ((n - 2) * q + 1) * q - (n - 1) * q - 1.
FrobeniusNumber- The predicate stating that a given natural number is the Frobenius number of a set of generators, defined as the greatest natural number not in the additive submonoid they generate.
frobeniusNumber_pair- Sylvester's formula: for coprime integers m, n > 1, the Frobenius number of {m, n} is m * n - m - n.
frobenius_extremal_family_coprime- For any n and q, the integers q and (n - 2) * q + 1 are coprime.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers on the right by a factor preserves the inequality.
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.
/-- Sharpness of the Frobenius upper bound: the Frobenius number of S_{n,q} is ((n - 2) * q + 1) * q - (n - 1) * q - 1. -/theorem frobenius_extremal_family_frobenius_number (n q : ℕ) (hn : 3 ≤ n) (hq : 2 ≤ q) : FrobeniusNumber (((n - 2) * q + 1) * q - (n - 1) * q - 1) (frobenius_extremal_family n q) := by have h_closure : AddSubmonoid.closure (frobenius_extremal_family n q) = AddSubmonoid.closure {q, (n - 2) * q + 1} := frobenius_extremal_family_closure_eq n q (by omega) have h_eval : q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1) = ((n - 2) * q + 1) * q - (n - 1) * q - 1 := frobenius_extremal_family_eval_eq n q hn rw [FrobeniusNumber] rw [h_closure] rw [← h_eval] change FrobeniusNumber (q * ((n - 2) * q + 1) - q - ((n - 2) * q + 1)) {q, (n - 2) * q + 1} apply frobeniusNumber_pair · exact frobenius_extremal_family_coprime n q · exact hq · have h1 : 1 ≤ n - 2 := by omega have h2 : 1 * q ≤ (n - 2) * q := Nat.mul_le_mul_right q h1 omega