Exploring the tree of numerical semigroups

Fromentin, Jean; Hivert, Florent

doi:10.1090/mcom/3075

Exploring the tree of numerical semigroups
HTML articles powered by AMS MathViewer

by Jean Fromentin and Florent Hivert;

Math. Comp. 85 (2016), 2553-2568

DOI: https://doi.org/10.1090/mcom/3075

Published electronically: December 31, 2015

PDF | Request permission

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\leqslant 67$ and we confirm the Wilf conjecture for $g\leqslant 60$.

References

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
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
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, DOI 10.1007/s00233-007-9014-8
M. Delgado, Homepage, http://cmup.fc.up.pt/cmup/mdelgado/numbers/.
M. Delgado, P. A. Garciá-Sánchez, and J. Morais, NumericalSgps, A GAP package for numerical semigroups. Available via http://www.gap-system.org.
J. Fromentin and F. Hivert, https://github.com/jfromentin/nsgtree.
The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.7.7, 2015.
M. Girkar, Intel instruction set architecture extensions | Intel® developer zone, Software.intel.com, 2013.
B. V. Iyer, R. Geva, and P. Halpern, Cilk™ plus in gcc, GNU Tools Cauldron, 2012.
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, DOI 10.1093/acprof:oso/9780198568209.001.0001
J. C. Rosales, Fundamental gaps of numerical semigroups generated by two elements, Linear Algebra Appl. 405 (2005), 200–208. MR 2148170, DOI 10.1016/j.laa.2005.03.014
J. C. Rosales and P. A. García-Sánchez, Numerical semigroups, Developments in Mathematics, vol. 20, Springer, New York, 2009. MR 2549780, DOI 10.1007/978-1-4419-0160-6
N. J. A. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org/.
Software.intel.com, Intel® Cilk™ homepage, https://www.cilkplus.org/, 2013.
Software.intel.com, Intel® Cilk™ plus reference guide, https://software.intel.com/en-us/node/522579, 2013.
Wikipedia, Advanced vector extension, http://en.wikipedia.org/wiki/Advanced_Vector_Extensions, 2014.
Wikipedia, Duff’s device, http://en.wikipedia.org/wiki/Duff’s_device, 2014.
Wikipedia, Hyper-threading, http://en.wikipedia.org/wiki/Hyper-Threading, 2014.
Wikipedia, Simd, http://en.wikipedia.org/wiki/SIMD, 2014.
Wikipedia, Streaming simd extensions, http://en.wikipedia.org/wiki/Streaming_SIMD_Extensions, 2014.
Wikipedia, Turbo boost, http://en.wikipedia.org/wiki/Intel_Turbo_Boost, 2014.
Herbert S. Wilf, A circle-of-lights algorithm for the “money-changing problem”, Amer. Math. Monthly 85 (1978), no. 7, 562–565. MR 556658, DOI 10.2307/2320864
Alex Zhai, Fibonacci-like growth of numerical semigroups of a given genus, Semigroup Forum 86 (2013), no. 3, 634–662. MR 3053785, DOI 10.1007/s00233-012-9456-5