Exploring the tree of numerical semigroups

Fromentin, Jean; Hivert, Florent

doi:10.1090/mcom/3075

Exploring the tree of numerical semigroups

Authors: Jean Fromentin and Florent Hivert
Journal: Math. Comp. 85 (2016), 2553-2568
MSC (2010): Primary 05A15, 68R05, 68W10
DOI: https://doi.org/10.1090/mcom/3075
Published electronically: December 31, 2015
MathSciNet review: 3511292
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we describe an algorithm visiting all numerical semigroups up to a given genus using a well-suited representation. The interest of this algorithm is that it fits particularly well the architecture of modern computers allowing very large optimizations: we obtain the number of numerical semigroups of genus $g\leq 67$ and we confirm the Wilf conjecture for $g\leq 60$ .

[1] Nicolas Borie, Generating tuples of integers modulo the action of a permutation group and applications, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AS, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013, pp. 767–778 (English, with English and French summaries). MR 3091039
[2] Maria Bras-Amorós, Addition behavior of a numerical semigroup, Arithmetic, geometry and coding theory (AGCT 2003), Sémin. Congr., vol. 11, Soc. Math. France, Paris, 2005, pp. 21–28 (English, with English and French summaries). MR 2182835
[3] Maria Bras-Amorós, Fibonacci-like behavior of the number of numerical semigroups of a given genus, Semigroup Forum 76 (2008), no. 2, 379–384. MR 2377597, https://doi.org/10.1007/s00233-007-9014-8
[4] M. Delgado, Homepage, http://cmup.fc.up.pt/cmup/mdelgado/numbers/.
[5] M. Delgado, P. A. Garciá-Sánchez, and J. Morais, NumericalSgps, A GAP package for numerical semigroups. Available via http://www.gap-system.org.
[6] J. Fromentin and F. Hivert, https://github.com/jfromentin/nsgtree.
[7] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.7.7, 2015.
[8] M. Girkar, Intel instruction set architecture extensions | Intel $\textregistered$ developer zone, Software.intel.com, 2013.
[9] B. V. Iyer, R. Geva, and P. Halpern, Cilk^TM plus in gcc, GNU Tools Cauldron, 2012.
[10] J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Series in Mathematics and its Applications, vol. 30, Oxford University Press, Oxford, 2005. MR 2260521
[11] J. C. Rosales, Fundamental gaps of numerical semigroups generated by two elements, Linear Algebra Appl. 405 (2005), 200–208. MR 2148170, https://doi.org/10.1016/j.laa.2005.03.014
[12] J. C. Rosales and P. A. García-Sánchez, Numerical semigroups, Developments in Mathematics, vol. 20, Springer, New York, 2009. MR 2549780
[13] N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org/.
[14] Software.intel.com, Intel $\textregistered$ Cilk^TM homepage, https://www.cilkplus.org/, 2013.
[15] Software.intel.com, Intel $\textregistered$ Cilk^TM plus reference guide, https://software.intel.com/en-us/node/522579, 2013.
[16] Wikipedia, Advanced vector extension, http://en.wikipedia.org/wiki/Advanced_Vector_Extensions, 2014.
[17] Wikipedia, Duff's device, http://en.wikipedia.org/wiki/Duff's_device, 2014.
[18] Wikipedia, Hyper-threading, http://en.wikipedia.org/wiki/Hyper-Threading, 2014.
[19] Wikipedia, Simd, http://en.wikipedia.org/wiki/SIMD, 2014.
[20] Wikipedia, Streaming simd extensions, http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions, 2014.
[21] Wikipedia, Turbo boost, http://en.wikipedia.org/wiki/Intel_Turbo_Boost, 2014.
[22] Herbert S. Wilf, A circle-of-lights algorithm for the “money-changing problem”, Amer. Math. Monthly 85 (1978), no. 7, 562–565. MR 556658, https://doi.org/10.2307/2320864
[23] Alex Zhai, Fibonacci-like growth of numerical semigroups of a given genus, Semigroup Forum 86 (2013), no. 3, 634–662. MR 3053785, https://doi.org/10.1007/s00233-012-9456-5