AFTD Auto-Formalizing Theoretical Domains

numerical_semigroup_exists_at_m_eq_succ_frobenius

theoremverified

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.

  1. 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.

    lines 7–19

      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 }
  2. 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.

    lines 20–26

    uses Set.Finite.subset, Set.finite_lt_nat, not_or.mp, not_le.mp

      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⟩
  3. 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].

    lines 27–37

    uses Set.mem_Icc, not_or.mp

      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
  4. 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.

    lines 38–48

    uses Set.mem_Ici, Or.inr

      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⟩
  5. 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).

    lines 49–52

    uses csSup_Icc

      refine ⟨S, ?_, ?_, ?_⟩
      · change sSup ((S.toAddSubmonoid : Set ℕ)ᶜ) = F
        rw [hcompl]
        exact csSup_Icc hF
  6. 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.

    lines 53–55

    uses csInf_Ici

      · change sInf {x : ℕ | x ∈ (S.toAddSubmonoid : Set ℕ) ∧ 0 < x} = F + 1
        rw [hpos]
        exact csInf_Ici
  7. 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.

    lines 56–58

    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

/-- 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
See it in the graphDiscuss this resultChallenge it