AFTD Auto-Formalizing Theoretical Domains

numerical_semigroup_not_dvd_frobenius

theoremverified

If S is a numerical semigroup with positive Frobenius number F and multiplicity m, then m does not divide F.

Statement

theorem numerical_semigroup_not_dvd_frobenius (S : NumericalSemigroup) (F m : ℕ) (hF : 0 < F)
    (h_frob : numerical_semigroup_frobenius_number S = F)
    (h_mult : numerical_semigroup_multiplicity S = m) :
    ¬ m ∣ F
Source
arXiv:2611.11559, Lemma 2.4
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_multiplicityThe multiplicity of a numerical semigroup S is the natural number defined as the infimum of its strictly positive elements: sInf {x ∈…
Used by 1

Read back from the Lean

For every numerical semigroup S (an additive submonoid of ℕ with finite complement in ℕ) and any natural numbers F and m, if 0 < F, F equals the Frobenius number of S (the supremum in ℕ of the complement ℕ \ S), and m equals the multiplicity of S (the infimum in ℕ of the positive elements belonging to S), then m does not divide 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

We argue by contradiction: suppose the multiplicity m divides the Frobenius number F, so F = m * k for some k ∈ ℕ. Because S is an additive submonoid containing m, any positive multiple of m must also belong to S, which implies F ∈ S. However, by definition the Frobenius number F is the supremum of the complement ℕ \ S, so F ∉ S. This contradiction shows that m cannot divide F.

  1. The complement of S in ℕ is nonempty.

    If the complement of S were empty, its supremum—which defines the Frobenius number of S—would evaluate to 0 in ℕ. But the Frobenius number F is assumed to be strictly positive (0 < F), yielding an immediate contradiction via linear integer arithmetic.

    lines 7–12

    uses Set.nonempty_iff_ne_empty

      have hcompl_ne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by
        rw [Set.nonempty_iff_ne_empty]
        intro hempty
        have hzero : numerical_semigroup_frobenius_number S = 0 := by
          simp [numerical_semigroup_frobenius_number, hempty]
        omega
  2. The Frobenius number F does not belong to S.

    Because the complement of S is nonempty and finite (by the definition of a numerical semigroup), it is bounded above, so its supremum belongs to the complement by Nat.sSup_mem. Since F is this supremum, F lies in the complement of S, meaning F ∉ S.

    lines 13–17

    uses Nat.sSup_mem, Set.Finite.bddAbove

      have hF_compl : F ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by
        rw [← h_frob]
        exact Nat.sSup_mem hcompl_ne (Set.Finite.bddAbove S.finite_compl)
      have hF_notin : F ∉ (S.toAddSubmonoid : Set ℕ) := by
        simpa using hF_compl
  3. The set T = {x ∈ S | 0 < x} of positive elements in S is nonempty.

    The complement of S is finite, hence bounded above by some N ∈ ℕ. Its successor N + 1 is strictly positive by Nat.succ_pos, and cannot belong to the complement of S, as that would imply N + 1 ≤ N. Therefore N + 1 ∈ S, which shows that T is nonempty.

    lines 19–27

    uses Set.Finite.bddAbove, Nat.succ_pos

      let T : Set ℕ := {x ∈ (S.toAddSubmonoid : Set ℕ) | 0 < x}
      have hT_nonempty : T.Nonempty := by
        rcases (Set.Finite.bddAbove S.finite_compl) with ⟨N, hN⟩
        refine ⟨N + 1, ?_, Nat.succ_pos N⟩
        by_contra hmem
        have hcompl : N + 1 ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by
          simpa using hmem
        have hle : N + 1 ≤ N := hN hcompl
        omega
  4. The multiplicity m belongs to S.

    The multiplicity m is defined as the infimum of the set T of positive elements of S. By Nat.sInf_mem, the infimum of any nonempty set of natural numbers belongs to the set, so m ∈ T and therefore m ∈ S.

    lines 28–34

    uses Nat.sInf_mem

      have hm_eq : m = sInf T := by
        rw [← h_mult]
        rfl
      have hmT : m ∈ T := by
        rw [hm_eq]
        exact Nat.sInf_mem hT_nonempty
      have hmS : m ∈ (S.toAddSubmonoid : Set ℕ) := hmT.1
  5. The multiplicity m does not divide the Frobenius number F.

    Suppose for contradiction that m divides F, so F = m * k for some k ∈ ℕ. Since S is an additive submonoid and m ∈ S, the multiple k • m belongs to S by AddSubmonoid.nsmul_mem. Since k • m = m * k = F, this implies F ∈ S, contradicting the earlier fact that F ∉ S.

    lines 36–41

    uses AddSubmonoid.nsmul_mem, nsmul_eq_mul, mul_comm

      rintro ⟨k, hk⟩
      have hF_mem : F ∈ (S.toAddSubmonoid : Set ℕ) := by
        rw [hk]
        have hmem := AddSubmonoid.nsmul_mem S.toAddSubmonoid hmS k
        simpa [nsmul_eq_mul, mul_comm] using hmem
      exact hF_notin hF_mem
Set.nonempty_iff_ne_empty
A set is nonempty if and only if it is not equal to the empty set.
Nat.sSup_mem
The supremum of a nonempty, bounded-above set of natural numbers belongs to that set.
Set.Finite.bddAbove
A finite subset of a preorder that is directed and nonempty is bounded above.
Nat.succ_pos
The successor of any natural number is strictly positive.
Nat.sInf_mem
The infimum (minimum) of a nonempty set of natural numbers belongs to that set.
AddSubmonoid.nsmul_mem
An additive submonoid is closed under natural number scalar multiplication (repeated addition).
nsmul_eq_mul
In a semiring, natural number scalar multiplication coincides with multiplication.
mul_comm
Multiplication in a commutative structure satisfies a * b = b * 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

/-- The multiplicity of a numerical semigroup cannot divide its Frobenius number. -/theorem numerical_semigroup_not_dvd_frobenius (S : NumericalSemigroup) (F m : ℕ) (hF : 0 < F)    (h_frob : numerical_semigroup_frobenius_number S = F)    (h_mult : numerical_semigroup_multiplicity S = m) :    ¬ m ∣ F := by  -- The Frobenius number belongs to the complement of `S`.  have hcompl_ne : ((S.toAddSubmonoid : Set ℕ)ᶜ).Nonempty := by    rw [Set.nonempty_iff_ne_empty]    intro hempty    have hzero : numerical_semigroup_frobenius_number S = 0 := by      simp [numerical_semigroup_frobenius_number, hempty]    omega  have hF_compl : F ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by    rw [← h_frob]    exact Nat.sSup_mem hcompl_ne (Set.Finite.bddAbove S.finite_compl)  have hF_notin : F ∉ (S.toAddSubmonoid : Set ℕ) := by    simpa using hF_compl  -- Some positive element lies in `S`, so the multiplicity is in `S`.  let T : Set ℕ := {x ∈ (S.toAddSubmonoid : Set ℕ) | 0 < x}  have hT_nonempty : T.Nonempty := by    rcases (Set.Finite.bddAbove S.finite_compl) with ⟨N, hN⟩    refine ⟨N + 1, ?_, Nat.succ_pos N⟩    by_contra hmem    have hcompl : N + 1 ∈ ((S.toAddSubmonoid : Set ℕ)ᶜ) := by      simpa using hmem    have hle : N + 1 ≤ N := hN hcompl    omega  have hm_eq : m = sInf T := by    rw [← h_mult]    rfl  have hmT : m ∈ T := by    rw [hm_eq]    exact Nat.sInf_mem hT_nonempty  have hmS : m ∈ (S.toAddSubmonoid : Set ℕ) := hmT.1  -- If `m ∣ F`, then `F` is a multiple of an element of the additive monoid `S`.  rintro ⟨k, hk⟩  have hF_mem : F ∈ (S.toAddSubmonoid : Set ℕ) := by    rw [hk]    have hmem := AddSubmonoid.nsmul_mem S.toAddSubmonoid hmS k    simpa [nsmul_eq_mul, mul_comm] using hmem  exact hF_notin hF_mem
See it in the graphDiscuss this resultChallenge it