numerical_semigroup_not_dvd_frobenius
If S is a numerical semigroup with positive Frobenius number F and multiplicity m, then m does not divide F.
Statement
theorem numerical_semigroup_not_dvd_frobenius (S : NumericalSemigroup) (F m : ℕ) (hF : 0 < F)
(h_frob : numerical_semigroup_frobenius_number S = F)
(h_mult : numerical_semigroup_multiplicity S = m) :
¬ m ∣ F- Source
- arXiv:2611.11559, Lemma 2.4
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- NumericalSemigroupA numerical semigroup is an additive submonoid of the natural numbers whose complement in ℕ is finite.
- numerical_semigroup_frobenius_numberThe Frobenius number of a numerical semigroup S is the natural number defined as the supremum of the complement of S in ℕ: sSup…
- numerical_semigroup_multiplicityThe multiplicity of a numerical semigroup S is the natural number defined as the infimum of its strictly positive elements: sInf {x ∈…
- Used by 1
- numerical_semigroup_count_of_dvd_frobeniusIf F is a positive integer and m divides F, then the number of numerical semigroups with Frobenius number F, multiplicity m, and genus g…
Read back from the Lean
For every numerical semigroup S (an additive submonoid of ℕ with finite complement in ℕ) and any natural numbers F and m, if 0 < F, F equals the Frobenius number of S (the supremum in ℕ of the complement ℕ \ S), and m equals the multiplicity of S (the infimum in ℕ of the positive elements belonging to S), then m does not divide F.
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
We argue by contradiction: suppose the multiplicity m divides the Frobenius number F, so F = m * k for some k ∈ ℕ. Because S is an additive submonoid containing m, any positive multiple of m must also belong to S, which implies F ∈ S. However, by definition the Frobenius number F is the supremum of the complement ℕ \ S, so F ∉ S. This contradiction shows that m cannot divide F.
The complement of S in ℕ is nonempty.
If the complement of S were empty, its supremum—which defines the Frobenius number of S—would evaluate to 0 in ℕ. But the Frobenius number F is assumed to be strictly positive (0 < F), yielding an immediate contradiction via linear integer arithmetic.
uses
Set.nonempty_iff_ne_emptyhave hcompl_ne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by rw [Set.nonempty_iff_ne_empty] intro hempty have hzero : numerical_semigroup_frobenius_number S = 0 := by simp [numerical_semigroup_frobenius_number, hempty] omega
The Frobenius number F does not belong to S.
Because the complement of S is nonempty and finite (by the definition of a numerical semigroup), it is bounded above, so its supremum belongs to the complement by Nat.sSup_mem. Since F is this supremum, F lies in the complement of S, meaning F ∉ S.
uses
Nat.sSup_mem,Set.Finite.bddAbovehave hF_compl : F ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by rw [← h_frob] exact Nat.sSup_mem hcompl_ne (Set.Finite.bddAbove S.finite_compl) have hF_notin : F ∉ (S.toAddSubmonoid : Set ℕ) := by simpa using hF_compl
The set T = {x ∈ S | 0 < x} of positive elements in S is nonempty.
The complement of S is finite, hence bounded above by some N ∈ ℕ. Its successor N + 1 is strictly positive by Nat.succ_pos, and cannot belong to the complement of S, as that would imply N + 1 ≤ N. Therefore N + 1 ∈ S, which shows that T is nonempty.
uses
Set.Finite.bddAbove,Nat.succ_poslet T : Set ℕ := {x ∈ (S.toAddSubmonoid : Set ℕ) | 0 < x} have hT_nonempty : T.Nonempty := by rcases (Set.Finite.bddAbove S.finite_compl) with ⟨N, hN⟩ refine ⟨N + 1, ?_, Nat.succ_pos N⟩ by_contra hmem have hcompl : N + 1 ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by simpa using hmem have hle : N + 1 ≤ N := hN hcompl omega
The multiplicity m belongs to S.
The multiplicity m is defined as the infimum of the set T of positive elements of S. By Nat.sInf_mem, the infimum of any nonempty set of natural numbers belongs to the set, so m ∈ T and therefore m ∈ S.
uses
Nat.sInf_memhave hm_eq : m = sInf T := by rw [← h_mult] rfl have hmT : m ∈ T := by rw [hm_eq] exact Nat.sInf_mem hT_nonempty have hmS : m ∈ (S.toAddSubmonoid : Set ℕ) := hmT.1
The multiplicity m does not divide the Frobenius number F.
Suppose for contradiction that m divides F, so F = m * k for some k ∈ ℕ. Since S is an additive submonoid and m ∈ S, the multiple k • m belongs to S by AddSubmonoid.nsmul_mem. Since k • m = m * k = F, this implies F ∈ S, contradicting the earlier fact that F ∉ S.
uses
AddSubmonoid.nsmul_mem,nsmul_eq_mul,mul_commrintro ⟨k, hk⟩ have hF_mem : F ∈ (S.toAddSubmonoid : Set ℕ) := by rw [hk] have hmem := AddSubmonoid.nsmul_mem S.toAddSubmonoid hmS k simpa [nsmul_eq_mul, mul_comm] using hmem exact hF_notin hF_mem
Set.nonempty_iff_ne_empty- A set is nonempty if and only if it is not equal to the empty set.
Nat.sSup_mem- The supremum of a nonempty, bounded-above set of natural numbers belongs to that set.
Set.Finite.bddAbove- A finite subset of a preorder that is directed and nonempty is bounded above.
Nat.succ_pos- The successor of any natural number is strictly positive.
Nat.sInf_mem- The infimum (minimum) of a nonempty set of natural numbers belongs to that set.
AddSubmonoid.nsmul_mem- An additive submonoid is closed under natural number scalar multiplication (repeated addition).
nsmul_eq_mul- In a semiring, natural number scalar multiplication coincides with multiplication.
mul_comm- Multiplication in a commutative structure satisfies a * b = b * a.
- In Lean, the supremum of the empty set of natural numbers is defined to be 0 (`sSup ∅ = 0`). Thus if the complement of S were empty, the Frobenius number would evaluate to 0, which contradicts the hypothesis 0 < F.
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 multiplicity of a numerical semigroup cannot divide its Frobenius number. -/theorem numerical_semigroup_not_dvd_frobenius (S : NumericalSemigroup) (F m : ℕ) (hF : 0 < F) (h_frob : numerical_semigroup_frobenius_number S = F) (h_mult : numerical_semigroup_multiplicity S = m) : ¬ m ∣ F := by -- The Frobenius number belongs to the complement of `S`. have hcompl_ne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by rw [Set.nonempty_iff_ne_empty] intro hempty have hzero : numerical_semigroup_frobenius_number S = 0 := by simp [numerical_semigroup_frobenius_number, hempty] omega have hF_compl : F ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by rw [← h_frob] exact Nat.sSup_mem hcompl_ne (Set.Finite.bddAbove S.finite_compl) have hF_notin : F ∉ (S.toAddSubmonoid : Set ℕ) := by simpa using hF_compl -- Some positive element lies in `S`, so the multiplicity is in `S`. let T : Set ℕ := {x ∈ (S.toAddSubmonoid : Set ℕ) | 0 < x} have hT_nonempty : T.Nonempty := by rcases (Set.Finite.bddAbove S.finite_compl) with ⟨N, hN⟩ refine ⟨N + 1, ?_, Nat.succ_pos N⟩ by_contra hmem have hcompl : N + 1 ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by simpa using hmem have hle : N + 1 ≤ N := hN hcompl omega have hm_eq : m = sInf T := by rw [← h_mult] rfl have hmT : m ∈ T := by rw [hm_eq] exact Nat.sInf_mem hT_nonempty have hmS : m ∈ (S.toAddSubmonoid : Set ℕ) := hmT.1 -- If `m ∣ F`, then `F` is a multiple of an element of the additive monoid `S`. rintro ⟨k, hk⟩ have hF_mem : F ∈ (S.toAddSubmonoid : Set ℕ) := by rw [hk] have hmem := AddSubmonoid.nsmul_mem S.toAddSubmonoid hmS k simpa [nsmul_eq_mul, mul_comm] using hmem exact hF_notin hF_mem