Conference abstracts

Session B2 - Graph Theory and Combinatorics

July 13, 18:00 ~ 18:25 - Room B7

On the computation of numerical semigroups

Maria Bras

Universitat Rovira i Virgili, Spain   -   maria.bras@urv.cat

A numerical semigroup is a subset of the positive integers (${\mathbb N}$) together with $0$, closed under addition, and with a finite complement in ${\mathbb N}\cup\{0\}$. The number of gaps is its {\it genus}. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus $g$, denoted $(n_g)_{g\geq 0}$, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each $g$, %it holds $n_{g+2}\geq n_{g+1}+n_{g}$ or, even more simple, $n_{g+1}\geq n_g$.

All algorithms used to compute $n_g$ explore by brute force approach the tree that contains at each depth the semigroups of genus equal to that depth, and in which the parent of a semigroup is the semigroup obtained when adjoining to the child its largest gap. We present a new algorithm for descending the tree using the new notion of seed of a numerical semigroup.

Joint work with Julio Fernández-González (Universitat Politècnica de Catalunya).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.