not_numerical_semigroup_frobenius_le_two_mul_genus
The statement numerical_semigroup_frobenius_le_two_mul_genus is false: The structure NumericalSemigroup only requires the complement of the underlying AddSubmonoid to be finite, so S = ℕ (i.e. ⊤ as an AddSubmonoid of ℕ) is a valid numerical semigroup. Its complement is empty, hence numerical_semigroup_frobenius_number S = sSup ∅ = 0 and numerical_semigroup_genus S = ncard ∅ = 0. Taking F = g = 0 the hypotheses hold but the conclusion becomes 0 + 1 ≤ 2 * 0, i.e. 1 ≤ 0, which is false. The classical bound F + 1 ≤ 2g requires the complement to be nonempty (equivalently F > 0, i.e. S ≠ ℕ).
Statement
theorem not_numerical_semigroup_frobenius_le_two_mul_genus : ¬ (∀ (S : NumericalSemigroup) (F g : ℕ)
(h_frob : numerical_semigroup_frobenius_number S = F)
(h_gen : numerical_semigroup_genus S = g), F + 1 ≤ 2 * g)- Related work
- refutes `numerical_semigroup_frobenius_le_two_mul_genus`
- 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_genusThe genus of a numerical semigroup S is the natural number defined as the cardinality of its complement in ℕ: Set.ncard ((S.toAddSubmonoid…
The proof, explained
The proof refutes the universal bound by exhibiting an explicit counterexample: the trivial numerical semigroup S = ℕ (the top submonoid ⊤). Because its complement is empty, its Frobenius number is sSup ∅ = 0 and its genus is |∅| = 0. Specializing the assumed inequality F + 1 ≤ 2 * g to F = 0 and g = 0 yields 1 ≤ 0, a contradiction.
Assume for contradiction that the inequality holds for all numerical semigroups.
We introduce the universal statement as an assumption h: for any numerical semigroup S with Frobenius number F and genus g, F + 1 ≤ 2 * g.
rintro h
There exists a numerical semigroup with Frobenius number 0 and genus 0.
We construct a counterexample by choosing S to be the full additive submonoid ⊤ = ℕ. Its complement is empty, which is finite, making S a valid numerical semigroup. Unfolding the definitions, its Frobenius number is sSup ∅ = 0 (by the convention for complete lattices on ℕ), and its genus is the cardinality of the empty set, which is 0. Both identities are discharged by simplification.
uses
numerical_semigroup_frobenius_number,numerical_semigroup_genushave hce : ∃ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 0 ∧ numerical_semigroup_genus S = 0 := by refine ⟨⟨⊤, ?_⟩, ?_, ?_⟩ · simp · simp [numerical_semigroup_frobenius_number] · simp [numerical_semigroup_genus]
A contradiction is derived from the counterexample.
We extract the counterexample S with Frobenius number 0 and genus 0, and specialize the universal hypothesis h to S, F = 0, and g = 0. This yields 0 + 1 ≤ 2 * 0, or 1 ≤ 0. Linear arithmetic (`omega`) detects that this inequality is impossible, completing the refutation.
obtain ⟨S, hf, hg⟩ := hce have h1 := h S 0 0 hf hg omega
numerical_semigroup_frobenius_number- The Frobenius number of a numerical semigroup S, defined as the supremum of its complement in ℕ (sSup (Sᶜ)).
numerical_semigroup_genus- The genus of a numerical semigroup S, defined as the cardinality of its complement in ℕ (ncard (Sᶜ)).
- The formal definition of `NumericalSemigroup` here only requires the complement of the submonoid in ℕ to be finite, allowing S = ℕ (with empty complement). Classical literature typically requires S ≠ ℕ (a non-empty complement).
- In Mathlib, the supremum of the empty set in ℕ defaults to 0 (the bottom element of ℕ), which gives S = ℕ a Frobenius number of 0 rather than -1 or -∞.
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_frobenius_le_two_mul_genus : ¬ (∀ (S : NumericalSemigroup) (F g : ℕ) (h_frob : numerical_semigroup_frobenius_number S = F) (h_gen : numerical_semigroup_genus S = g), F + 1 ≤ 2 * g) := by rintro h have hce : ∃ S : NumericalSemigroup, numerical_semigroup_frobenius_number S = 0 ∧ numerical_semigroup_genus S = 0 := by refine ⟨⟨⊤, ?_⟩, ?_, ?_⟩ · simp · simp [numerical_semigroup_frobenius_number] · simp [numerical_semigroup_genus] obtain ⟨S, hf, hg⟩ := hce have h1 := h S 0 0 hf hg omega