2
$\begingroup$

For a given integer $n$, I am interested in the number of different numerical semigroups one can make with a generating set consisting only of integers in $[n]$.

I have done some small examples. For $n=1$ there is only $\langle 1\rangle$ and the same goes for $n=2$. For $n=3$ there are only $\langle 1\rangle$ and $\langle 2,3\rangle$ and for $n=4$ there are $\langle 1\rangle$, $\langle 2,3\rangle$, and $\langle 3,4\rangle$. For $n=5$ I won't list all the ones I found but I believe there to be $7$ of them, and for $n=6$ I found $8$ (of course I may have made a mistake).

I have found references online counting numerical subgroups by multiplicity $m$ and genus $g$, but was not able to find anything on this variant of the counting problem. In fact, it would be really great if I could figure out how to count the number of numerical semigroups with generating set in $[n]$ and with genus $g$, for given integers $n$ and $g$. Any remarks or pointers to the literature would be greatly appreciated. Thanks in advance!

$\endgroup$
11
  • $\begingroup$ Hi! The binary operation is $+$ here. So, for instance, $\langle 2,3\rangle = {\bf N}\setminus \{1\}$. Sorry, I should have specified. $\endgroup$ Nov 13, 2022 at 1:01
  • $\begingroup$ $\langle3,4\rangle$ is generated by integers in $[3]$? $\endgroup$ Nov 13, 2022 at 1:20
  • 1
    $\begingroup$ @GerryMyerson sorry, off-by-one error, will correct. $\endgroup$ Nov 13, 2022 at 1:53
  • $\begingroup$ For $n=6$ I get $9$, not $8$. $\endgroup$ Nov 13, 2022 at 2:16
  • $\begingroup$ Aren't there two semigroups for $n=2$: $\mathbb N$ and $2\mathbb N$ ? $\endgroup$ Nov 13, 2022 at 3:06

1 Answer 1

3
$\begingroup$

A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different semigroups equals the number of different $\langle g\rangle \cap [n]$ for $g\subseteq [n]$ (and this is what is computed in a naive way by the Sage code that I shared in the comments).

The question has an implicit restriction that the complement of $\langle g\rangle$ must be finite, which is equivalent to $g$ being set-wise coprime. Let's refer to the semigroups under this restriction as primitive and denote their number as $P(n)$. Without this restriction the semigroups (ie. both primitive and non-primitive) are enumerated by OEIS A103580. It is easy to see the following connection between the two counts: $${\tt A103580}(n) = \sum_{k=1}^n P(\lfloor \tfrac{n}{k}\rfloor ),$$ which implies that $P(n)$ can be obtained via Möbius inversion: $$P(n) = \sum_{k=1}^n \mu(k)\cdot {\tt A103580}(\lfloor \tfrac{n}{k}\rfloor ).$$ From 100 terms provided in the OEIS for A103580, we can immediately obtain $P(n)$ for $n\leq 100$.

Efficient computation of A103580 is discussed in the paper Counting numerical semigroups by Frobenius number, multiplicity, and depth by Sean Li (see Remark on page 12).

PS. I've added $P(n)$ to the OEIS as sequence A358392.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.