not_numerical_semigroup_count_fibonacci_recurrence
The statement numerical_semigroup_count_fibonacci_recurrence is false: The identity is false. Take F = 3, m = 2, g = 2: indeed F + 2 = 5 ≤ 6 = 3*m and m = 2 ≤ 2 = F - 1.
LHS: n_{3,2,2} = 1. The complement of such a semigroup is contained in {0,1,2,3} (3 is a gap, everything ≥ 4 is in S), 0 is in S, multiplicity 2 forces 2 ∈ S and 1 ∉ S, and the genus is 2, so the gap set is exactly {1,3}. Hence the unique such semigroup is {0,2} ∪ [4,∞).
RHS: n_{1,1,1} + n_{1,1,0} = 0 + 0. A semigroup with Frobenius number 1 has 1 as a gap (1 = sSup of the gap set, and the sSup of a finite nonempty set of naturals is a member of it), while multiplicity 1 forces 1 ∈ S (sInf of the positive elements is a member). Contradiction.
So the claimed equation reads 1 = 0. The recurrence fails for every (F, m, g) = (F, F-1, F-1) with F ≥ 3 (the semigroup {0, F-1} ∪ [F+1,∞)); brute-force enumeration up to F = 18 finds no other failures. A probable correction is to add the hypothesis m ≤ F - 2 (equivalently F ≥ m + 2).
Statement
theorem not_numerical_semigroup_count_fibonacci_recurrence : ¬ (∀ (F m g : ℕ) (hlow : F + 2 ≤ 3 * m) (hhigh : m ≤ F - 1), numerical_semigroup_count F m g =
numerical_semigroup_count (F - 2) (m - 1) (g - 1) +
numerical_semigroup_count (F - 2) (m - 1) (g - 2))- Related work
- refutes `numerical_semigroup_count_fibonacci_recurrence`
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- numerical_semigroup_countThe counting function n_{F,m,g} of numerical semigroups, defined as the number (cardinality) of numerical semigroups with Frobenius number…
- NumericalSemigroupA numerical semigroup is an additive submonoid of the natural numbers whose complement in ℕ is finite.
- 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…
- 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_frobenius_numberThe Frobenius number of a numerical semigroup S is the natural number defined as the supremum of the complement of S in ℕ: sSup…
The proof, explained
The proof disproves the claimed Fibonacci-type recurrence for counting numerical semigroups by exhibiting a counterexample at parameters (F, m, g) = (3, 2, 2), which satisfy the hypotheses F + 2 ≤ 3m and m ≤ F - 1. At these values, the recurrence asserts that n_{3,2,2} = n_{1,1,1} + n_{1,1,0}. The proof constructs the semigroup S₀ = {0, 2} ∪ [4, ∞) and proves it is the unique numerical semigroup with invariants (3, 2, 2), establishing that the left-hand side is 1. On the right-hand side, no numerical semigroup can have both Frobenius number 1 and multiplicity 1 (since 1 would have to be both in the semigroup and in its gap set), so both terms vanish. This forces 1 = 0, refuting the recurrence.
Assume for contradiction that the Fibonacci recurrence holds for all valid parameters.
We introduce the universal hypothesis `hcontra`, which asserts that for all natural numbers F, m, g satisfying F + 2 ≤ 3 * m and m ≤ F - 1, the count of numerical semigroups satisfies the Fibonacci-like recurrence. Our goal is to derive False.
intro hcontraIf a numerical semigroup S has multiplicity m > 0, then m ∈ S.
The multiplicity is defined as the infimum of the set A of positive elements in S. If A were empty, its infimum would be 0 by `Nat.sInf_empty`, contradicting m > 0. Thus A is nonempty, and by `Nat.sInf_mem` its infimum belongs to A, which proves m ∈ S.
uses
Set.not_nonempty_iff_eq_empty,Nat.sInf_empty,Nat.sInf_memhave mult_mem : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m → 0 < m → m ∈ (S.toAddSubmonoid : Set ℕ) := by intro S m h hm unfold numerical_semigroup_multiplicity at h set A : Set ℕ := {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} with hA have hne : A.Nonempty := by by_contra hc rw [Set.not_nonempty_iff_eq_empty] at hc rw [hc, Nat.sInf_empty] at h omega have hmem := Nat.sInf_mem hne rw [h] at hmem exact hmem.1
If a numerical semigroup S has multiplicity m, then every positive element x ∈ S satisfies m ≤ x.
Because m is the infimum of the set of positive elements in S, any positive x ∈ S is at least the infimum by `Nat.sInf_le`.
uses
Nat.sInf_lehave mult_le : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m → ∀ x ∈ (S.toAddSubmonoid : Set ℕ), 0 < x → m ≤ x := by intro S m h x hx hx0 unfold numerical_semigroup_multiplicity at h rw [← h] exact Nat.sInf_le ⟨hx, hx0⟩
If a numerical semigroup S has Frobenius number F > 0, then F is in the complement of S (F is a gap).
The Frobenius number is defined as the supremum of the gap set Sᶜ. If Sᶜ were empty, its supremum in ℕ would be 0 by `csSup_empty`, contradicting F > 0. Since Sᶜ is nonempty and finite (thus bounded above), its supremum belongs to Sᶜ by `Nat.sSup_mem`, showing F ∈ Sᶜ.
uses
Set.not_nonempty_iff_eq_empty,csSup_empty,Nat.sSup_memhave frob_mem_compl : ∀ (S : NumericalSemigroup) (F : ℕ), numerical_semigroup_frobenius_number S = F → 0 < F → F ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := by intro S F h hF unfold numerical_semigroup_frobenius_number at h have hne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by by_contra hc rw [Set.not_nonempty_iff_eq_empty] at hc rw [hc, csSup_empty] at h simp at h omega have hmem := Nat.sSup_mem hne S.finite_compl.bddAbove rwa [h] at hmem
If a numerical semigroup S has Frobenius number F, then every gap x ∈ Sᶜ satisfies x ≤ F.
Since Sᶜ is finite and thus bounded above, every element x ∈ Sᶜ is bounded above by the supremum of Sᶜ, which is F, by `le_csSup`.
uses
le_csSuphave compl_le_frob : ∀ (S : NumericalSemigroup) (F : ℕ), numerical_semigroup_frobenius_number S = F → ∀ x ∈ (S.toAddSubmonoid : Set ℕ)ᶜ, x ≤ F := by intro S F h x hx unfold numerical_semigroup_frobenius_number at h calc x ≤ sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) := le_csSup S.finite_compl.bddAbove hx _ = F := h
The set S₀ = {0, 2} ∪ [4, ∞) forms a valid numerical semigroup `nsS` whose gap set is {1, 3}.
We define S₀ = {0, 2} ∪ [4, ∞) and check that 0 ∈ S₀ and that S₀ is closed under addition. Its complement in ℕ is explicitly {1, 3}, which is finite by `Set.toFinite`, yielding a valid numerical semigroup `nsS`.
uses
Set.mem_union,Set.mem_insert_iff,Set.mem_singleton_iff,Set.mem_Ici,Set.mem_compl_iff,Set.toFinitelet nsC : Set ℕ := {0, 2} ∪ Set.Ici 4 have nsC_add : ∀ a ∈ nsC, ∀ b ∈ nsC, a + b ∈ nsC := by intro a ha b hb simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at * omega let nsSub : AddSubmonoid ℕ := { carrier := nsC, zero_mem' := by simp [nsC], add_mem' := fun {a b : ℕ} (ha : a ∈ nsC) (hb : b ∈ nsC) => nsC_add a ha b hb } have nsSub_carrier : (nsSub : Set ℕ) = nsC := rfl have nsSub_compl : (nsC : Set ℕ)ᶜ = {1, 3} := by ext n simp only [nsC, Set.mem_compl_iff, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] omega have hnsF : ((nsSub : Set ℕ)ᶜ).Finite := by rw [nsSub_carrier, nsSub_compl] exact Set.toFinite _ let nsS : NumericalSemigroup := { toAddSubmonoid := nsSub, finite_compl := hnsF }
The semigroup S₀ has Frobenius number 3, genus 2, and multiplicity 2.
The gap set of S₀ is {1, 3}, so its maximum is 3 (Frobenius number 3) and its cardinality is 2 (genus 2). The set of positive elements of S₀ is {2} ∪ [4, ∞), whose minimum is 2, established via `le_antisymm`, `Nat.sInf_le`, and `le_csInf`.
uses
le_antisymm,Nat.sInf_le,le_csInf,Set.mem_setOf_eq,Set.mem_union,Set.mem_insert_iff,Set.mem_singleton_iff,Set.mem_Icihave nsS_carrier : (nsS.toAddSubmonoid : Set ℕ) = nsC := nsSub_carrier have nsS_frob : numerical_semigroup_frobenius_number nsS = 3 := by unfold numerical_semigroup_frobenius_number rw [nsS_carrier, nsSub_compl] norm_num have nsS_genus : numerical_semigroup_genus nsS = 2 := by unfold numerical_semigroup_genus rw [nsS_carrier, nsSub_compl] simp have nsS_mult : numerical_semigroup_multiplicity nsS = 2 := by unfold numerical_semigroup_multiplicity rw [nsS_carrier] have hmem : (2:ℕ) ∈ {x : ℕ | x ∈ nsC ∧ 0 < x} := by simp [nsC] apply le_antisymm · exact Nat.sInf_le hmem · apply le_csInf ⟨2, hmem⟩ intro b hb simp only [Set.mem_setOf_eq, nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at hb omega
Any numerical semigroup S with Frobenius number 3, multiplicity 2, and genus 2 is equal to S₀.
Let C = Sᶜ be the gap set of S. Frobenius number 3 implies 3 ∈ C and every gap n satisfies n ≤ 3. Since 0 ∈ S and multiplicity 2 implies 2 ∈ S, we have 0 ∉ C and 2 ∉ C, so C ⊆ {1, 3}. If 1 ∉ C, then C ⊆ {3}, giving |C| ≤ 1 by `Set.ncard_le_ncard` and `Set.ncard_singleton`, contradicting genus |C| = 2. Hence C = {1, 3} by `Set.Subset.antisymm`, which forces the carrier of S to be {0, 2} ∪ [4, ∞) = S₀. Semigroup extensionality (`AddSubmonoid.ext` and `NumericalSemigroup.mk.injEq`) then yields S = S₀.
uses
Set.mem_insert_iff,Set.mem_singleton_iff,Set.ncard_le_ncard,Set.toFinite,Set.ncard_singleton,Set.Subset.antisymm,not_or,Set.mem_union,Set.mem_Ici,AddSubmonoid.ext,NumericalSemigroup.mk.injEqhave uniq : ∀ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 3 → numerical_semigroup_multiplicity S = 2 → numerical_semigroup_genus S = 2 → S = nsS := by intro S hfrob hmult hgen set C : Set ℕ := (S.toAddSubmonoid : Set ℕ)ᶜ with hC have h3C : 3 ∈ C := by rw [hC] exact frob_mem_compl S 3 hfrob (by norm_num) have hupper : ∀ n ∈ C, n ≤ 3 := by intro n hn rw [hC] at hn exact compl_le_frob S 3 hfrob n hn have h0S : (0:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := S.toAddSubmonoid.zero_mem have h2S : (2:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 2 hmult (by norm_num) have hsub : C ⊆ {1, 3} := by intro n hn have hn3 : n ≤ 3 := hupper n hn rw [hC] at hn have hn0 : n ≠ 0 := fun h => hn (h ▸ h0S) have hn2 : n ≠ 2 := fun h => hn (h ▸ h2S) simp only [Set.mem_insert_iff, Set.mem_singleton_iff] omega have h1C : 1 ∈ C := by by_contra h1 have hsub3 : C ⊆ ({3} : Set ℕ) := by intro n hn have h := hsub hn simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h ⊢ rcases h with h | h · rw [h] at hn; exact absurd hn h1 · exact h have hle : C.ncard ≤ ({3} : Set ℕ).ncard := Set.ncard_le_ncard hsub3 (Set.toFinite _) rw [Set.ncard_singleton] at hle have hgen' : C.ncard = 2 := by rw [hC] exact hgen omega have hCeq : C = {1, 3} := by apply Set.Subset.antisymm hsub intro n hn simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hn rcases hn with rfl | rfl · exact h1C · exact h3C have hcarrier : (S.toAddSubmonoid : Set ℕ) = nsC := by ext n constructor · intro hn have hnotC : n ∉ C := by rw [hC] intro hmem exact hmem hn rw [hCeq] at hnotC simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] at hnotC simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] omega · intro hn by_contra hns have hmem : n ∈ C := by rw [hC]; exact hns rw [hCeq] at hmem simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at hn omega have hsubeq : S.toAddSubmonoid = nsSub := by apply AddSubmonoid.ext intro n change n ∈ (S.toAddSubmonoid : Set ℕ) ↔ n ∈ (nsC : Set ℕ) rw [hcarrier] have hnsS : nsS = ⟨nsSub, hnsF⟩ := rfl rw [hnsS] obtain ⟨a, b⟩ := S simp only [NumericalSemigroup.mk.injEq] exact hsubeq
The count of numerical semigroups with parameters (F, m, g) = (3, 2, 2) is 1.
The uniqueness result implies that the set of numerical semigroups with parameters (3, 2, 2) is exactly the singleton {S₀}. By `Set.ncard_singleton`, its cardinality is 1, so `numerical_semigroup_count 3 2 2 = 1`.
uses
Set.mem_setOf_eq,Set.mem_singleton_iff,Set.ncard_singletonhave hX : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 3 ∧ numerical_semigroup_multiplicity S = 2 ∧ numerical_semigroup_genus S = 2} = {nsS} := by ext S simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] constructor · rintro ⟨a, b, c⟩ exact uniq S a b c · rintro rfl exact ⟨nsS_frob, nsS_mult, nsS_genus⟩ have hcount3 : numerical_semigroup_count 3 2 2 = 1 := by unfold numerical_semigroup_count rw [hX, Set.ncard_singleton] have count_one_zero : ∀ g : ℕ, numerical_semigroup_count 1 1 g = 0 := by
For any genus g, the count of numerical semigroups with Frobenius number 1 and multiplicity 1 is 0.
Multiplicity 1 requires 1 ∈ S (by `mult_mem`), while Frobenius number 1 requires 1 ∈ Sᶜ (by `frob_mem_compl`). Since 1 cannot simultaneously be in S and in Sᶜ, no such semigroup exists. The set is empty, so its cardinality is 0.
uses
Set.not_nonempty_iff_eq_emptyintro g unfold numerical_semigroup_count have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 1 ∧ numerical_semigroup_multiplicity S = 1 ∧ numerical_semigroup_genus S = g} = ∅ := by rw [← Set.not_nonempty_iff_eq_empty] rintro ⟨S, hfrob, hmult, -⟩ have h1mem : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 1 hmult (by norm_num) have h1compl : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := frob_mem_compl S 1 hfrob (by norm_num) exact h1compl h1mem rw [hempty] simp
The recurrence produces the contradiction 1 = 0.
Specializing the universal recurrence assumption `hcontra` to F = 3, m = 2, g = 2 satisfies the required bounds 3 + 2 ≤ 3 * 2 and 2 ≤ 3 - 1. It equates `numerical_semigroup_count 3 2 2` to `numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0`. Substituting the known values yields 1 = 0 + 0, which linear arithmetic (`omega`) recognizes as a contradiction.
have h1 := hcontra 3 2 2 (by norm_num) (by norm_num) rw [hcount3] at h1 have h1' : (1:ℕ) = numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0 := h1 rw [count_one_zero 1, count_one_zero 0] at h1' omega
AddSubmonoid.ext- Two additive submonoids of an additive monoid are equal if and only if they contain the exact same elements.
Nat.sInf_empty- The infimum of the empty set of natural numbers is defined to be 0.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
Nat.sInf_mem- The infimum of a nonempty set of natural numbers belongs to that set (i.e., every nonempty subset of ℕ has a minimum).
Nat.sSup_mem- The supremum of a nonempty, bounded-above set of natural numbers belongs to that set (i.e., it achieves its maximum).
NumericalSemigroup.mk.injEq- Two numerical semigroups constructed with `NumericalSemigroup.mk` are equal if and only if their underlying additive submonoids are equal.
Set.mem_Ici- An element belongs to the closed interval [b, ∞) if and only if b ≤ x.
Set.mem_compl_iff- An element belongs to the complement of a set if and only if it does not belong to the set.
Set.mem_insert_iff- An element belongs to the insertion of an element a into a set s if and only if it equals a or belongs to s.
Set.mem_setOf_eq- Membership of x in the set of elements satisfying a predicate p is equivalent to p(x).
Set.mem_singleton_iff- An element belongs to the singleton set {b} if and only if it equals b.
Set.mem_union- An element belongs to the union of two sets if and only if it belongs to at least one of them.
Set.ncard_le_ncard- If s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
Set.ncard_singleton- The cardinality of a singleton set is 1.
Set.not_nonempty_iff_eq_empty- A set is not nonempty if and only if it is the empty set.
Set.Subset.antisymm- If two sets are subsets of each other, they are equal.
Set.toFinite- A set whose subtype is finite is a finite set.
csSup_empty- In a conditionally complete linear order with a bottom element (such as ℕ), the supremum of the empty set is ⊥ (which is 0).
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
le_csInf- If an element a is a lower bound for a nonempty set s in a conditionally complete lattice, then a ≤ inf s.
le_csSup- Any element of a bounded-above set in a conditionally complete lattice is less than or equal to the supremum of that set.
not_or- The negation of a disjunction is equivalent to the conjunction of the negations (De Morgan's law).
- In Lean, the infimum and supremum of the empty set in ℕ default to 0 (`Nat.sInf_empty` and `csSup_empty`), requiring brief contradiction arguments in the proofs of `mult_mem` and `frob_mem_compl` to establish nonemptiness from strictly positive invariants.
- The definition of `NumericalSemigroup` bundles an additive submonoid with a proof of finite complement; proving equality of two semigroups requires unpacking and comparing the underlying submonoids using `NumericalSemigroup.mk.injEq` and `AddSubmonoid.ext`.
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.
theorem not_numerical_semigroup_count_fibonacci_recurrence : ¬ (∀ (F m g : ℕ) (hlow : F + 2 ≤ 3 * m) (hhigh : m ≤ F - 1), numerical_semigroup_count F m g = numerical_semigroup_count (F - 2) (m - 1) (g - 1) + numerical_semigroup_count (F - 2) (m - 1) (g - 2)) := by intro hcontra have mult_mem : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m → 0 < m → m ∈ (S.toAddSubmonoid : Set ℕ) := by intro S m h hm unfold numerical_semigroup_multiplicity at h set A : Set ℕ := {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} with hA have hne : A.Nonempty := by by_contra hc rw [Set.not_nonempty_iff_eq_empty] at hc rw [hc, Nat.sInf_empty] at h omega have hmem := Nat.sInf_mem hne rw [h] at hmem exact hmem.1 have mult_le : ∀ (S : NumericalSemigroup) (m : ℕ), numerical_semigroup_multiplicity S = m → ∀ x ∈ (S.toAddSubmonoid : Set ℕ), 0 < x → m ≤ x := by intro S m h x hx hx0 unfold numerical_semigroup_multiplicity at h rw [← h] exact Nat.sInf_le ⟨hx, hx0⟩ have frob_mem_compl : ∀ (S : NumericalSemigroup) (F : ℕ), numerical_semigroup_frobenius_number S = F → 0 < F → F ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := by intro S F h hF unfold numerical_semigroup_frobenius_number at h have hne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by by_contra hc rw [Set.not_nonempty_iff_eq_empty] at hc rw [hc, csSup_empty] at h simp at h omega have hmem := Nat.sSup_mem hne S.finite_compl.bddAbove rwa [h] at hmem have compl_le_frob : ∀ (S : NumericalSemigroup) (F : ℕ), numerical_semigroup_frobenius_number S = F → ∀ x ∈ (S.toAddSubmonoid : Set ℕ)ᶜ, x ≤ F := by intro S F h x hx unfold numerical_semigroup_frobenius_number at h calc x ≤ sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) := le_csSup S.finite_compl.bddAbove hx _ = F := h let nsC : Set ℕ := {0, 2} ∪ Set.Ici 4 have nsC_add : ∀ a ∈ nsC, ∀ b ∈ nsC, a + b ∈ nsC := by intro a ha b hb simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at * omega let nsSub : AddSubmonoid ℕ := { carrier := nsC, zero_mem' := by simp [nsC], add_mem' := fun {a b : ℕ} (ha : a ∈ nsC) (hb : b ∈ nsC) => nsC_add a ha b hb } have nsSub_carrier : (nsSub : Set ℕ) = nsC := rfl have nsSub_compl : (nsC : Set ℕ)ᶜ = {1, 3} := by ext n simp only [nsC, Set.mem_compl_iff, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] omega have hnsF : ((nsSub : Set ℕ)ᶜ).Finite := by rw [nsSub_carrier, nsSub_compl] exact Set.toFinite _ let nsS : NumericalSemigroup := { toAddSubmonoid := nsSub, finite_compl := hnsF } have nsS_carrier : (nsS.toAddSubmonoid : Set ℕ) = nsC := nsSub_carrier have nsS_frob : numerical_semigroup_frobenius_number nsS = 3 := by unfold numerical_semigroup_frobenius_number rw [nsS_carrier, nsSub_compl] norm_num have nsS_genus : numerical_semigroup_genus nsS = 2 := by unfold numerical_semigroup_genus rw [nsS_carrier, nsSub_compl] simp have nsS_mult : numerical_semigroup_multiplicity nsS = 2 := by unfold numerical_semigroup_multiplicity rw [nsS_carrier] have hmem : (2:ℕ) ∈ {x : ℕ | x ∈ nsC ∧ 0 < x} := by simp [nsC] apply le_antisymm · exact Nat.sInf_le hmem · apply le_csInf ⟨2, hmem⟩ intro b hb simp only [Set.mem_setOf_eq, nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at hb omega have uniq : ∀ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 3 → numerical_semigroup_multiplicity S = 2 → numerical_semigroup_genus S = 2 → S = nsS := by intro S hfrob hmult hgen set C : Set ℕ := (S.toAddSubmonoid : Set ℕ)ᶜ with hC have h3C : 3 ∈ C := by rw [hC] exact frob_mem_compl S 3 hfrob (by norm_num) have hupper : ∀ n ∈ C, n ≤ 3 := by intro n hn rw [hC] at hn exact compl_le_frob S 3 hfrob n hn have h0S : (0:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := S.toAddSubmonoid.zero_mem have h2S : (2:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 2 hmult (by norm_num) have hsub : C ⊆ {1, 3} := by intro n hn have hn3 : n ≤ 3 := hupper n hn rw [hC] at hn have hn0 : n ≠ 0 := fun h => hn (h ▸ h0S) have hn2 : n ≠ 2 := fun h => hn (h ▸ h2S) simp only [Set.mem_insert_iff, Set.mem_singleton_iff] omega have h1C : 1 ∈ C := by by_contra h1 have hsub3 : C ⊆ ({3} : Set ℕ) := by intro n hn have h := hsub hn simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at h ⊢ rcases h with h | h · rw [h] at hn; exact absurd hn h1 · exact h have hle : C.ncard ≤ ({3} : Set ℕ).ncard := Set.ncard_le_ncard hsub3 (Set.toFinite _) rw [Set.ncard_singleton] at hle have hgen' : C.ncard = 2 := by rw [hC] exact hgen omega have hCeq : C = {1, 3} := by apply Set.Subset.antisymm hsub intro n hn simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hn rcases hn with rfl | rfl · exact h1C · exact h3C have hcarrier : (S.toAddSubmonoid : Set ℕ) = nsC := by ext n constructor · intro hn have hnotC : n ∉ C := by rw [hC] intro hmem exact hmem hn rw [hCeq] at hnotC simp only [Set.mem_insert_iff, Set.mem_singleton_iff, not_or] at hnotC simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] omega · intro hn by_contra hns have hmem : n ∈ C := by rw [hC]; exact hns rw [hCeq] at hmem simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hmem simp only [nsC, Set.mem_union, Set.mem_insert_iff, Set.mem_singleton_iff, Set.mem_Ici] at hn omega have hsubeq : S.toAddSubmonoid = nsSub := by apply AddSubmonoid.ext intro n change n ∈ (S.toAddSubmonoid : Set ℕ) ↔ n ∈ (nsC : Set ℕ) rw [hcarrier] have hnsS : nsS = ⟨nsSub, hnsF⟩ := rfl rw [hnsS] obtain ⟨a, b⟩ := S simp only [NumericalSemigroup.mk.injEq] exact hsubeq have hX : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 3 ∧ numerical_semigroup_multiplicity S = 2 ∧ numerical_semigroup_genus S = 2} = {nsS} := by ext S simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] constructor · rintro ⟨a, b, c⟩ exact uniq S a b c · rintro rfl exact ⟨nsS_frob, nsS_mult, nsS_genus⟩ have hcount3 : numerical_semigroup_count 3 2 2 = 1 := by unfold numerical_semigroup_count rw [hX, Set.ncard_singleton] have count_one_zero : ∀ g : ℕ, numerical_semigroup_count 1 1 g = 0 := by intro g unfold numerical_semigroup_count have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = 1 ∧ numerical_semigroup_multiplicity S = 1 ∧ numerical_semigroup_genus S = g} = ∅ := by rw [← Set.not_nonempty_iff_eq_empty] rintro ⟨S, hfrob, hmult, -⟩ have h1mem : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ) := mult_mem S 1 hmult (by norm_num) have h1compl : (1:ℕ) ∈ (S.toAddSubmonoid : Set ℕ)ᶜ := frob_mem_compl S 1 hfrob (by norm_num) exact h1compl h1mem rw [hempty] simp have h1 := hcontra 3 2 2 (by norm_num) (by norm_num) rw [hcount3] at h1 have h1' : (1:ℕ) = numerical_semigroup_count 1 1 1 + numerical_semigroup_count 1 1 0 := h1 rw [count_one_zero 1, count_one_zero 0] at h1' omega