AFTD Auto-Formalizing Theoretical Domains

frobenius_extremal_family_closure_eq

theoremverified

For n ≥ 2, the additive submonoid closure of frobenius_extremal_family n q equals the additive submonoid closure of the pair {q, (n - 2) * q + 1}.

Statement

theorem frobenius_extremal_family_closure_eq (n q : ℕ) (hn : 2 ≤ n) : AddSubmonoid.closure (frobenius_extremal_family n q) = AddSubmonoid.closure {q, (n - 2) * q + 1}
Source
scout/2610-32219-a-sharp-upper-bound-for-the-frobenius-number.md:457
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • frobenius_extremal_familyFor natural numbers n and q, frobenius_extremal_family n q is the set of natural numbers consisting of all multiples i * q for 1 ≤ i ≤ n…
Used by 1

Read back from the Lean

For all natural numbers $n$ and $q$, if $2 \le n$, then the additive submonoid of $\mathbb{N}$ generated by the Frobenius extremal family of parameters $n$ and $q$ is equal to the additive submonoid of $\mathbb{N}$ generated by the set $\{q, (n - 2)q + 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 equality of submonoid closures is proved by mutual inclusion using antisymmetry. In the forward direction, every element of the family is either a multiple $i \cdot q$ of $q$ (which lies in the closure because $q$ does) or the element $(n - 2)q + 1$ itself. In the reverse direction, $(n - 2)q + 1$ is explicitly in the family, and $q = 1 \cdot q$ belongs to the family because $n \ge 2$ ensures $1 \le n - 1$.

  1. The equality of the submonoid closures reduces to proving mutual inclusion.

    By antisymmetry of the inclusion order on submonoids (`le_antisymm`), it suffices to show that each submonoid closure is contained in the other.

    line 3

    uses le_antisymm

      apply le_antisymm
  2. To show the forward inclusion, it suffices to show that every element $i \cdot q$ (with $1 \le i \le n - 1$) and $(n - 2)q + 1$ belongs to the closure of $\{q, (n - 2)q + 1\}$.

    By `AddSubmonoid.closure_le`, a submonoid closure is contained in a submonoid if and only if its generating set is. Unfolding `frobenius_extremal_family n q`, every element in the family is either of the form $i \cdot q$ for some $1 \le i \le n - 1$, or equals $(n - 2)q + 1$.

    lines 4–7

    uses AddSubmonoid.closure_le

      · rw [AddSubmonoid.closure_le]
        intro x hx
        unfold frobenius_extremal_family at hx
        rcases hx with ⟨i, hi1, hin, rfl⟩ | hx
  3. Every multiple $i \cdot q$ belongs to the closure of $\{q, (n - 2)q + 1\}$.

    The element $q$ is in the generator set $\{q, (n - 2)q + 1\}$, so it belongs to its closure by `AddSubmonoid.subset_closure`. Because additive submonoids are closed under natural-number multiples (`AddSubmonoid.nsmul_mem`), $i \bullet q$ is in the closure, which rewrites via `nsmul_eq_mul` to the product $i \cdot q$.

    lines 8–11

    uses AddSubmonoid.subset_closure, AddSubmonoid.nsmul_mem, nsmul_eq_mul

        · have hq : q ∈ AddSubmonoid.closure ({q, (n - 2) * q + 1} : Set ℕ) :=
            AddSubmonoid.subset_closure (by simp)
          have := AddSubmonoid.nsmul_mem (AddSubmonoid.closure ({q, (n - 2) * q + 1} : Set ℕ)) hq i
          rwa [nsmul_eq_mul] at this
  4. The element $(n - 2)q + 1$ belongs to the closure of $\{q, (n - 2)q + 1\}$.

    In the second branch of the union, $x = (n - 2)q + 1$ by `Set.mem_singleton_iff`. Since $(n - 2)q + 1$ is one of the two generators in $\{q, (n - 2)q + 1\}$, it lies in the closure by `AddSubmonoid.subset_closure`.

    lines 12–14

    uses Set.mem_singleton_iff, AddSubmonoid.subset_closure

        · rw [Set.mem_singleton_iff] at hx
          subst hx
          exact AddSubmonoid.subset_closure (by simp)
  5. To show the reverse inclusion, it suffices to show that both $q$ and $(n - 2)q + 1$ belong to `frobenius_extremal_family n q`.

    By `AddSubmonoid.closure_le` and `AddSubmonoid.subset_closure`, it suffices to show each element of $\{q, (n - 2)q + 1\}$ belongs to `frobenius_extremal_family n q`. By `Set.mem_insert_iff` and `Set.mem_singleton_iff`, any such element is either $q$ or $(n - 2)q + 1$. Rewriting with `Set.mem_union` splits the goal into showing that each belongs to the union defining the extremal family.

    lines 15–21

    uses AddSubmonoid.closure_le, AddSubmonoid.subset_closure, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_union

      · rw [AddSubmonoid.closure_le]
        intro x hx
        apply AddSubmonoid.subset_closure
        unfold frobenius_extremal_family
        rw [Set.mem_insert_iff, Set.mem_singleton_iff] at hx
        rw [Set.mem_union]
        rcases hx with rfl | rfl
  6. The generator $q$ belongs to `frobenius_extremal_family n q`.

    We choose the left branch of the union. Setting $i = 1$, we have $1 \le 1$ by `le_refl`, $1 \le n - 1$ by linear arithmetic (`omega`) since $2 \le n$, and $1 \cdot q = q$ by ring properties (`ring`).

    lines 22–23

    uses le_refl

        · left
          exact ⟨1, le_refl 1, by omega, by ring⟩
  7. The generator $(n - 2)q + 1$ belongs to `frobenius_extremal_family n q`.

    We choose the right branch of the union, where $(n - 2)q + 1 \in \{(n - 2)q + 1\}$ holds definitionally by `rfl`.

    lines 24–25

        · right
          rfl
le_antisymm
If $a \le b$ and $b \le a$ in a partial order, then $a = b$.
AddSubmonoid.closure_le
An additive submonoid closure $\operatorname{closure}(s)$ is contained in a submonoid $S$ if and only if $s \subseteq S$.
AddSubmonoid.subset_closure
Any set $s$ is contained in its additive submonoid closure $\operatorname{closure}(s)$.
AddSubmonoid.nsmul_mem
If an element $x$ belongs to an additive submonoid $S$, then every natural multiple $n \bullet x$ also belongs to $S$.
nsmul_eq_mul
Scalar multiplication by a natural number $n \bullet a$ in a semiring is equal to multiplication $n \cdot a$.
Set.mem_singleton_iff
An element $a$ belongs to the singleton set $\{b\}$ if and only if $a = b$.
Set.mem_insert_iff
An element $x$ belongs to $\{a\} \cup s$ if and only if $x = a$ or $x \in s$.
Set.mem_union
An element $x$ belongs to $a \cup b$ if and only if $x \in a$ or $x \in b$.
le_refl
The ordering relation is reflexive: $a \le a$ for all $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

/-- The additive submonoid generated by S_{n,q} equals that generated by {q, (n - 2) * q + 1}. -/theorem frobenius_extremal_family_closure_eq (n q : ℕ) (hn : 2 ≤ n) : AddSubmonoid.closure (frobenius_extremal_family n q) = AddSubmonoid.closure {q, (n - 2) * q + 1} := by  apply le_antisymm  · rw [AddSubmonoid.closure_le]    intro x hx    unfold frobenius_extremal_family at hx    rcases hx with ⟨i, hi1, hin, rfl⟩ | hx    · have hq : q ∈ AddSubmonoid.closure ({q, (n - 2) * q + 1} : Set ℕ) :=        AddSubmonoid.subset_closure (by simp)      have := AddSubmonoid.nsmul_mem (AddSubmonoid.closure ({q, (n - 2) * q + 1} : Set ℕ)) hq i      rwa [nsmul_eq_mul] at this    · rw [Set.mem_singleton_iff] at hx      subst hx      exact AddSubmonoid.subset_closure (by simp)  · rw [AddSubmonoid.closure_le]    intro x hx    apply AddSubmonoid.subset_closure    unfold frobenius_extremal_family    rw [Set.mem_insert_iff, Set.mem_singleton_iff] at hx    rw [Set.mem_union]    rcases hx with rfl | rfl    · left      exact ⟨1, le_refl 1, by omega, by ring⟩    · right      rfl
See it in the graphDiscuss this resultChallenge it