AFTD Auto-Formalizing Theoretical Domains

numerical_semigroup_count_of_dvd_frobenius

theoremverified

If F is a positive integer and m divides F, then the number of numerical semigroups with Frobenius number F, multiplicity m, and genus g is 0.

Statement

theorem numerical_semigroup_count_of_dvd_frobenius (F m g : ℕ) (hF : 0 < F) (hdvd : m ∣ F) :
    numerical_semigroup_count F m g = 0
Source
arXiv:2611.11559 Section 2
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • numerical_semigroup_countThe counting function n_{F,m,g} of numerical semigroups, defined as the number (cardinality) of numerical semigroups with Frobenius number…
  • numerical_semigroup_not_dvd_frobeniusIf S is a numerical semigroup with positive Frobenius number F and multiplicity m, then m does not divide F.
  • 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…
  • 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…

Read back from the Lean

For all natural numbers $F$, $m$, and $g$, if $0 < F$ and $m \mid F$, then the count of numerical semigroups with Frobenius number $F$, multiplicity $m$, and genus $g$ is 0.

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 proof unfolds the definition of `numerical_semigroup_count` as the cardinality of the set of numerical semigroups with Frobenius number F, multiplicity m, and genus g. It then establishes that this set is empty: if such a semigroup existed, its multiplicity would divide its positive Frobenius number, contradicting the theorem `numerical_semigroup_not_dvd_frobenius`. Finally, the cardinality of the empty set is evaluated to 0.

  1. The count of numerical semigroups is expressed as the cardinality of the set of numerical semigroups satisfying the given Frobenius number, multiplicity, and genus.

    Unfolding the definition of `numerical_semigroup_count` replaces the count with the cardinality (`Set.ncard`) of the set of all numerical semigroups S having Frobenius number F, multiplicity m, and genus g.

    line 4

      unfold numerical_semigroup_count
  2. The set of numerical semigroups with Frobenius number F, multiplicity m, and genus g is empty.

    By set extensionality (`ext S`), a numerical semigroup S belongs to this set if and only if it satisfies all three conditions, whereas no element belongs to the empty set (`Set.mem_ofPred_eq`, `Set.mem_empty_iff_false`, `iff_false`). If such a semigroup S existed with Frobenius number F and multiplicity m, the lemma `numerical_semigroup_not_dvd_frobenius` would imply that m cannot divide F, directly contradicting the hypothesis that m divides F. Therefore, no such semigroup exists and the set is empty.

    lines 5–10

    uses Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false, numerical_semigroup_not_dvd_frobenius

      have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = F ∧
          numerical_semigroup_multiplicity S = m ∧ numerical_semigroup_genus S = g} = ∅ := by
        ext S
        simp only [Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false]
        rintro ⟨hf, hm, _⟩
        exact numerical_semigroup_not_dvd_frobenius S F m hF hf hm hdvd
  3. The cardinality of the empty set evaluates to 0, completing the proof.

    Substituting the fact that the set of satisfying numerical semigroups is empty, its cardinality is 0 by `Set.ncard_empty`.

    line 11

    uses Set.ncard_empty

      rw [hempty, Set.ncard_empty]
Set.mem_ofPred_eq
Membership of an element in a set defined by a predicate {y | p y} is equivalent to the predicate holding for that element.
Set.mem_empty_iff_false
An element belongs to the empty set if and only if false; that is, the empty set contains no elements.
iff_false
A proposition is equivalent to false if and only if its negation holds.
numerical_semigroup_not_dvd_frobenius
For any numerical semigroup with a positive Frobenius number F and multiplicity m, the multiplicity m does not divide F.
Set.ncard_empty
The cardinality of the empty set is 0.

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

/-- No numerical semigroup has multiplicity dividing its positive Frobenius number, so the count is zero. -/theorem numerical_semigroup_count_of_dvd_frobenius (F m g : ℕ) (hF : 0 < F) (hdvd : m ∣ F) :    numerical_semigroup_count F m g = 0 := by  unfold numerical_semigroup_count  have hempty : {S : NumericalSemigroup | numerical_semigroup_frobenius_number S = F ∧      numerical_semigroup_multiplicity S = m ∧ numerical_semigroup_genus S = g} = ∅ := by    ext S    simp only [Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false]    rintro ⟨hf, hm, _⟩    exact numerical_semigroup_not_dvd_frobenius S F m hF hf hm hdvd  rw [hempty, Set.ncard_empty]
See it in the graphDiscuss this resultChallenge it