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$ Commented Nov 13, 2022 at 1:01
  • $\begingroup$ $\langle3,4\rangle$ is generated by integers in $[3]$? $\endgroup$ Commented Nov 13, 2022 at 1:20
  • 1
    $\begingroup$ @GerryMyerson sorry, off-by-one error, will correct. $\endgroup$ Commented Nov 13, 2022 at 1:53
  • $\begingroup$ For $n=6$ I get $9$, not $8$. $\endgroup$ Commented Nov 13, 2022 at 2:16
  • $\begingroup$ Aren't there two semigroups for $n=2$: $\mathbb N$ and $2\mathbb N$ ? $\endgroup$ Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .