AFTD Auto-Formalizing Theoretical Domains

not_numerical_semigroup_frobenius_le_two_mul_genus

theoremverifiedoriginal

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.

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

    line 4

      rintro h
  2. 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.

    lines 5–10

    uses numerical_semigroup_frobenius_number, numerical_semigroup_genus

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

    lines 11–13

      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ᶜ)).

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

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