frobenius_extremal_family_closure_eq
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 qis the set of natural numbers consisting of all multiples i * q for 1 ≤ i ≤ n…
- frobenius_extremal_familyFor natural numbers n and q,
- 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 $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$.
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.
uses
le_antisymmapply le_antisymmTo 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$.
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
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$.
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
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`.
uses
Set.mem_singleton_iff,AddSubmonoid.subset_closure· rw [Set.mem_singleton_iff] at hx subst hx exact AddSubmonoid.subset_closure (by simp)
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.
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
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`).
uses
le_refl· left exact ⟨1, le_refl 1, by omega, by ring⟩
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`.
· 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
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.
/-- 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