Let N denote the monoid of natural numbers. A numerical semigroup is a cofinite submonoid S ⊆ N. For the purposes of this paper, a generalized numericalsemigroup (GNS) is a cofinite submonoid S ⊆ N^d. The cardinality of N^dS is calledthe genus. We describe a family of algorithms, parameterized by (relaxed) monomial orders, that can be used to generate trees of semigroups with each GNS appearing exactly once. Let N_g,d denote the number of generalized numerical semigroups S ⊆ N^d of genus g. We compute N_g,d for small values of g, d and provide coarse asymptotic bounds on Ng,d for large values of g, d. For a fixed g, we show that F_g(d) = N_g,d isa polynomial function of degree g. We close with several open problems/conjecturesrelated to the asymptotic growth of N_g,d and with suggestions for further avenues of research.

Algorithms and Asymptotics for generalized numerical semigroups in N^d

FAILLA, Gioia;
2016

Abstract

Let N denote the monoid of natural numbers. A numerical semigroup is a cofinite submonoid S ⊆ N. For the purposes of this paper, a generalized numericalsemigroup (GNS) is a cofinite submonoid S ⊆ N^d. The cardinality of N^dS is calledthe genus. We describe a family of algorithms, parameterized by (relaxed) monomial orders, that can be used to generate trees of semigroups with each GNS appearing exactly once. Let N_g,d denote the number of generalized numerical semigroups S ⊆ N^d of genus g. We compute N_g,d for small values of g, d and provide coarse asymptotic bounds on Ng,d for large values of g, d. For a fixed g, we show that F_g(d) = N_g,d isa polynomial function of degree g. We close with several open problems/conjecturesrelated to the asymptotic growth of N_g,d and with suggestions for further avenues of research.
Numerical semigroup, Frobenius number, Monoid
File in questo prodotto:
File Dimensione Formato  
Failla_2016_Sem.Forum_Algorithms_editor.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 428.43 kB
Formato Adobe PDF
428.43 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12318/2033
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 13
social impact