Algorithms and basic asymptotics for generalized numerical semigroups in \({\mathbb {N}}^d\)
详细信息 查看全文
- 作者：Gioia Failla ; Chris Peterson ; Rosanna Utano
- 关键词：Numerical semigroup ; Monoid ; Frobenius number
- 刊名：Semigroup Forum
- 出版年：2016
- 出版时间：April 2016
- 年：2016
- 卷：92
- 期：2
- 页码：460-473
- 全文大小：428 KB
- 参考文献：1.Assi, A., García-Sánchez, P.A.: Constructing the set of complete intersection numerical semigroups with a given Frobenius number. Appl. Algebra Eng. Commun. Comput. 24(2), 133–148 (2013)MathSciNet CrossRef MATH
2.Blanco, V., García-Sánchez, P.A., Puerto, J.: Counting numerical semigroups with short generating functions. Int. J. Algebra Comput. 21(7), 1217–1235 (2011)MathSciNet CrossRef MATH
3.Blanco, V., Rosales, J.C.: The set of numerical semigroups of a given genus. Semigroup Forum 85, 255–267 (2012)MathSciNet CrossRef MATH
4.Blanco, V., Rosales, J.C.: On the enumeration of the set of numerical semigroups with fixed Frobenius number. Comput. Math. Appl. 63, 1204–1211 (2012)MathSciNet CrossRef MATH
5.Bras-Amorós, M.: Fibonacci-like behavior of the number of numerical semigroups of a given genus. Semigroup Forum 76, 379–384 (2008)MathSciNet CrossRef MATH
6.Bras-Amorós, M.: Bounds on the number of numerical semigroups of a given genus. J. Pure Appl. Algebra 213, 997–1001 (2009)MathSciNet CrossRef MATH
7.Bras-Amorós, M.: Towards a better understanding of the semigroup tree. Semigroup Forum 79(3), 561–574 (2009)MathSciNet CrossRef MATH
8.Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (2007). ISBN 0-387-35650-9CrossRef MATH
9.Eliahou, S., Ramíres Alfonsín, J.: Two-generator numerical semigroups and Fermat and Mersenne numbers, SIAM. J. Discret. Math. 25, 622–630 (2011)CrossRef MATH
10.Elizalde, S.: Improved bounds on the number of numerical semigroups of a given genus. J. Pure Appl. Algebra 214, 1862–1873 (2010)MathSciNet CrossRef MATH
11.Fröberg, R., Gottlieb, C., Häggkvist, R.: On numerical semigroups. Semigroup Forum 35, 63–83 (1986/1987)
12.Kaplan, N.: Counting numerical semigroups by genus and some cases of a question of Wilf. J. Pure Appl. Algebra 216, 1016–1032 (2012)MathSciNet CrossRef MATH
13.Martino, I., Martino, L.: On the variety of linear recurrences and numerical semigroups. Semigroup Forum 88, 569–574 (2014)MathSciNet CrossRef MATH
14.Nari, H., Numata, T., Watanabe, K.-I.: Genus of numerical semigroups generated by three elements. J. Algebra 358, 67–73 (2012)MathSciNet CrossRef MATH
15.Pisón-Casares, P., Vigneron-Tenorio, A.: \({\mathbb{N}}\) -solutions to linear systems over \({\mathbb{Z}}\) . Linear Algebra Its Appl. 384, 135–154 (2004)MathSciNet CrossRef MATH
16.Rosales, J.C.: On finitely generated submonoids of \({\mathbb{N}}^k\) . Semigroup Forum 50, 251–262 (1995)MathSciNet CrossRef MATH
17.Rosales, J.C., Branco, M.B.: The Frobenius problem for numerical semigroups. J. Number Theory 131, 2310–2319 (2011)MathSciNet CrossRef MATH
18.Rosales, J.C., García-Sánchez, P.A.: Numerical Semigroups, Developments in Mathematics, vol. 20. Springer, New York (2009). ISBN 978-1-4419-0159-0CrossRef MATH
19.Rosales, J.C., García-Sánchez, P.A., García-García, J.I.: Presentations of finitely generated submonoids of finitely generated commutative monoids. Int. J. Algebra Comput. 12, 659–670 (2002)MathSciNet CrossRef MATH
20.Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences, Published electronically at OEIS.org (sequence A007323)
21.Wilf, H.S.: A circle-of-lights algorithm for the money-changing problem. Am. Math. Mon. 85, 562–565 (1978)MathSciNet CrossRef MATH
22.Zhai, A.: Fibonacci-like growth of numerical semigroups of a given genus. Semigroup Forum 86, 634–662 (2013)MathSciNet CrossRef MATH
23.Zhao, Y.: Constructing numerical semigroups of a given genus. Semigroup Forum 80, 242–254 (2010)MathSciNet CrossRef MATH - 作者单位：Gioia Failla (1)
Chris Peterson (2)
Rosanna Utano (3)
1. Universitá Mediterranea di Reggio Calabria, DIIES, Via Graziella, Feo di Vito, Reggio Calabria, Italy
2. Departement of Mathematics, Colorado State University, Fort Collins, CO, 80523, USA
3. Dipartimento di Matematica e Informatica, Universitá di Messina, Viale Ferdinando Stagno D’Alcontres 31, 98166, Messina, Italy - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Algebra - 出版者：Springer New York
- ISSN：1432-2137
文摘
Let \({\mathbb {N}}\) denote the monoid of natural numbers. A numerical semigroup is a cofinite submonoid \(S\subseteq {\mathbb {N}}\). For the purposes of this paper, a generalized numerical semigroup (GNS) is a cofinite submonoid \(S\subseteq {\mathbb {N}}^d\). The cardinality of \({\mathbb {N}}^d \setminus S\) is called the 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\subseteq {\mathbb {N}}^d\) of genus \(g\). We compute \(N_{g,d}\) for small values of \(g,d\) and provide coarse asymptotic bounds on \(N_{g,d}\) for large values of \(g,d\). For a fixed \(g\), we show that \(F_g(d)=N_{g,d}\) is a polynomial function of degree \(g\). We close with several open problems/conjectures related to the asymptotic growth of \(N_{g,d}\) and with suggestions for further avenues of research.