numerical_semigroup_exists_at_m_eq_succ_frobenius
For every positive integer F, there exists a numerical semigroup S with Frobenius number F, multiplicity F + 1, and genus F.
Statement
theorem numerical_semigroup_exists_at_m_eq_succ_frobenius (F : ℕ) (hF : 0 < F) :
∃ S : NumericalSemigroup,
numerical_semigroup_frobenius_number S = F ∧
numerical_semigroup_multiplicity S = F + 1 ∧
numerical_semigroup_genus S = F- Source
- arXiv:2611.11559, Lemma 2.3
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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 ∈…
- numerical_semigroup_genusThe genus of a numerical semigroup S is the natural number defined as the cardinality of its complement in ℕ: Set.ncard ((S.toAddSubmonoid…
Read back from the Lean
For every positive natural number $F$, there exists a numerical semigroup $S$ whose Frobenius number is $F$, whose multiplicity is $F + 1$, and whose genus is $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
For any positive integer F, the set S = {0} ∪ {n ∈ ℕ | n ≥ F + 1} forms an additive submonoid whose complement in ℕ is the discrete interval [1, F]. Because [1, F] is finite, S is a numerical semigroup; its maximum omitted integer is sup [1, F] = F, its smallest positive element is inf [F + 1, ∞) = F + 1, and the count of omitted integers is |[1, F]| = F.
M = {0} ∪ {n ∈ ℕ | F + 1 ≤ n} is an additive submonoid of ℕ.
We define M as the set containing 0 and all natural numbers at least F + 1. It contains 0 by definition. To check closure under addition for a, b ∈ M, if either a = 0 or b = 0, the sum is the other element, which already lies in M; if both a ≥ F + 1 and b ≥ F + 1, then a + b ≥ 2(F + 1) ≥ F + 1, so the sum also lies in M.
open Set in let M : AddSubmonoid ℕ := { carrier := {n : ℕ | n = 0 ∨ F + 1 ≤ n} zero_mem' := by simp add_mem' := by intro a b ha hb rcases ha with rfl | ha · simpa using hb · rcases hb with rfl | hb · right simpa using ha · right omega }
The complement of M in ℕ is finite, yielding a valid numerical semigroup S.
Any natural number n not in M cannot be 0 and cannot be at least F + 1, which by not_or.mp and not_le.mp implies n < F + 1. Thus the complement of M is a subset of {i ∈ ℕ | i < F + 1}. Because this initial segment is finite by Set.finite_lt_nat, the complement of M is finite by Set.Finite.subset. Pairing M with this finiteness property gives the numerical semigroup S.
uses
Set.Finite.subset,Set.finite_lt_nat,not_or.mp,not_le.mphave hfin : (M : Set ℕ)ᶜ.Finite := by apply Set.Finite.subset (Set.finite_lt_nat (F + 1)) intro n hn have hn' : ¬ (n = 0 ∨ F + 1 ≤ n) := by simpa [M] using hn have h2 : ¬ F + 1 ≤ n := (not_or.mp hn').2 simpa using not_le.mp h2 let S : NumericalSemigroup := ⟨M, hfin⟩
The complement of S in ℕ is the closed discrete interval [1, F].
An integer n is in the complement of S if and only if n ∉ M. If n ∉ M, then by not_or.mp, n ≠ 0 (so 1 ≤ n) and ¬(F + 1 ≤ n) (so n ≤ F). Conversely, if 1 ≤ n ≤ F, then n cannot be 0 and cannot be ≥ F + 1, so n ∉ M. Using Set.mem_Icc, this establishes the equality with [1, F].
uses
Set.mem_Icc,not_or.mphave hcompl : (S.toAddSubmonoid : Set ℕ)ᶜ = Set.Icc 1 F := by ext n change n ∉ (M : Set ℕ) ↔ n ∈ Set.Icc 1 F simp only [M, Set.mem_Icc] constructor · intro hn have h := not_or.mp hn constructor <;> omega · rintro ⟨h1, h2⟩ hmem have hmem' : n = 0 ∨ F + 1 ≤ n := by simpa [M] using hmem omega
The set of positive elements of S is the ray [F + 1, ∞).
An element n belongs to S and is strictly positive if and only if (n = 0 ∨ F + 1 ≤ n) and 0 < n. The case n = 0 contradicts 0 < n, leaving F + 1 ≤ n, which by Set.mem_Ici defines [F + 1, ∞). Conversely, any n ≥ F + 1 belongs to M by Or.inr and is strictly positive since F ≥ 1.
uses
Set.mem_Ici,Or.inrhave hpos : {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} = Set.Ici (F + 1) := by ext n change (n ∈ (M : Set ℕ) ∧ 0 < n) ↔ n ∈ Set.Ici (F + 1) simp only [M, Set.mem_Ici] constructor · rintro ⟨h, hnpos⟩ rcases h with h0 | hge · omega · exact hge · intro hge exact ⟨Or.inr hge, by omega⟩
The Frobenius number of S is F.
With S as the witness, the Frobenius number is by definition the supremum of its complement. Since the complement is [1, F], its supremum is F by csSup_Icc, using the assumption that 0 < F (so 1 ≤ F).
uses
csSup_Iccrefine ⟨S, ?_, ?_, ?_⟩ · change sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) = F rw [hcompl] exact csSup_Icc hF
The multiplicity of S is F + 1.
The multiplicity is the infimum of the set of strictly positive elements of S. Since this set is [F + 1, ∞), its infimum is F + 1 by csInf_Ici.
uses
csInf_Ici· change sInf {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} = F + 1 rw [hpos] exact csInf_Ici
The genus of S is F.
The genus is defined as the cardinality of the complement of S. Since the complement is [1, F], Set.ncard_Icc_nat gives its cardinality as F + 1 - 1, which arithmetic simplifies to F.
uses
Set.ncard_Icc_nat· change ((S.toAddSubmonoid : Set ℕ)ᶜ).ncard = F rw [hcompl, Set.ncard_Icc_nat] omega
Set.Finite.subset- A subset of a finite set is finite.
Set.finite_lt_nat- The set of natural numbers strictly less than a given bound is finite.
not_or.mp- If a disjunction is false, then both disjuncts are false: ¬(P ∨ Q) implies ¬P ∧ ¬Q.
not_le.mp- For natural numbers, if a ≤ b is false, then b < a.
Set.mem_Icc- An element belongs to the closed interval [a, b] if and only if it satisfies a ≤ x ≤ b.
Set.mem_Ici- An element belongs to the closed ray [b, ∞) if and only if b ≤ x.
Or.inr- Given a proof of B, one obtains a proof of A ∨ B.
csSup_Icc- In a conditionally complete partial order, the supremum of the closed interval [a, b] (for a ≤ b) is b.
csInf_Ici- In a conditionally complete partial order, the infimum of the closed ray [a, ∞) is a.
Set.ncard_Icc_nat- The number of natural numbers in the discrete interval [a, b] is b + 1 - 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.
/-- Existence of the unique numerical semigroup with multiplicity F + 1 and Frobenius number F. -/theorem numerical_semigroup_exists_at_m_eq_succ_frobenius (F : ℕ) (hF : 0 < F) : ∃ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = F ∧ numerical_semigroup_multiplicity S = F + 1 ∧ numerical_semigroup_genus S = F := by open Set in let M : AddSubmonoid ℕ := { carrier := {n : ℕ | n = 0 ∨ F + 1 ≤ n} zero_mem' := by simp add_mem' := by intro a b ha hb rcases ha with rfl | ha · simpa using hb · rcases hb with rfl | hb · right simpa using ha · right omega } have hfin : (M : Set ℕ)ᶜ.Finite := by apply Set.Finite.subset (Set.finite_lt_nat (F + 1)) intro n hn have hn' : ¬ (n = 0 ∨ F + 1 ≤ n) := by simpa [M] using hn have h2 : ¬ F + 1 ≤ n := (not_or.mp hn').2 simpa using not_le.mp h2 let S : NumericalSemigroup := ⟨M, hfin⟩ have hcompl : (S.toAddSubmonoid : Set ℕ)ᶜ = Set.Icc 1 F := by ext n change n ∉ (M : Set ℕ) ↔ n ∈ Set.Icc 1 F simp only [M, Set.mem_Icc] constructor · intro hn have h := not_or.mp hn constructor <;> omega · rintro ⟨h1, h2⟩ hmem have hmem' : n = 0 ∨ F + 1 ≤ n := by simpa [M] using hmem omega have hpos : {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} = Set.Ici (F + 1) := by ext n change (n ∈ (M : Set ℕ) ∧ 0 < n) ↔ n ∈ Set.Ici (F + 1) simp only [M, Set.mem_Ici] constructor · rintro ⟨h, hnpos⟩ rcases h with h0 | hge · omega · exact hge · intro hge exact ⟨Or.inr hge, by omega⟩ refine ⟨S, ?_, ?_, ?_⟩ · change sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) = F rw [hcompl] exact csSup_Icc hF · change sInf {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} = F + 1 rw [hpos] exact csInf_Ici · change ((S.toAddSubmonoid : Set ℕ)ᶜ).ncard = F rw [hcompl, Set.ncard_Icc_nat] omega