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 Free Access
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\leqslant 67$ and we confirm the Wilf conjecture for $g\leqslant 60$.
- 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
Retrieve articles in Mathematics of Computation with MSC (2010): 05A15, 68R05, 68W10
Retrieve articles in all journals with MSC (2010): 05A15, 68R05, 68W10
Additional Information
Jean Fromentin
Affiliation:
Univ. Littoral Côte d’Opale, EA 2597 - LMPA - Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, F-62228 Calais, France
Email:
fromentin@lmpa.univ-littoral.fr
Florent Hivert
Affiliation:
Laboratoire de Recherche Informatique (UMR CNRS 8623), Université Paris Sud, Université Paris-Saclay, Bureau 33, Bât 650 Ada Lovelace, Université Paris Sud Rue Noetzlin, 91190 Gif-sur-Yvette
MR Author ID:
639193
Email:
florent.hivert@lri.fr
Received by editor(s):
November 3, 2014
Received by editor(s) in revised form:
April 10, 2015
Published electronically:
December 31, 2015
Article copyright:
© Copyright 2015
American Mathematical Society
