AFTD Auto-Formalizing Theoretical Domains

frobenius_extremal_family_frobenius_number

theoremverifiedformalization

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

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.

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

    lines 3–4

    uses frobenius_extremal_family_closure_eq

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

    lines 5–6

    uses frobenius_extremal_family_eval_eq

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

    lines 7–10

    uses FrobeniusNumber

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

    line 11

    uses frobeniusNumber_pair

      apply frobeniusNumber_pair
  5. q and (n - 2) * q + 1 are coprime.

    This coprimality condition is supplied directly by frobenius_extremal_family_coprime.

    line 12

    uses frobenius_extremal_family_coprime

      · exact frobenius_extremal_family_coprime n q
  6. 1 < q.

    This follows immediately from the hypothesis 2 ≤ q (hq).

    line 13

      · exact hq
  7. 1 < (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.

    lines 14–16

    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

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