cp's OEIS Frontend

A007323 Number of numerical semigroups of genus n; conjecturally also the number of power sum bases for symmetric functions in n variables.

%I A007323 M1064 #225 Apr 13 2025 16:36:11
%S A007323 1,1,2,4,7,12,23,39,67,118,204,343,592,1001,1693,2857,4806,8045,13467,
%T A007323 22464,37396,62194,103246,170963,282828,467224,770832,1270267,2091030,
%U A007323 3437839,5646773,9266788,15195070,24896206,40761087,66687201,109032500
%N A007323 Number of numerical semigroups of genus n; conjecturally also the number of power sum bases for symmetric functions in n variables.
%C A007323 From Don Zagier's email of Apr 11 1994: (Start)
%C A007323 Given n, one knows that the field of symmetric functions in n variables a_1,...,a_n is the field Q(sigma_1,...,sigma_n), where sigma_i is the i-th elementary symmetric polynomial. Here one has no choice, because sigma_i=0 for i>n and fewer than n sigma's would not suffice.
%C A007323 But, by Newton's formulas, the field is also given as Q(s_1,...,s_n) where s_i is the i-th power sum, and now one can ask whether some other sequence s_{j_1},...,s_{j_n} (0<j_1<...<j_n) also works.
%C A007323 For n=1 the only possibility is clearly s_1, since Q(s_i) = Q(a^i) does not coincide with Q(a) for i>1, but for n=2 one has two possibilities Q(s_1,s_2) or Q(s_1,s_3), since from s_1=a+b and s_3=a^3+b^3 one can reconstruct s_2 = (s_1^3+2s_3)/3s_1.
%C A007323 Similarly, for n=3 one has the possibilities (123), (124), (125), and (135) (the formula in the last case is s_2 = (s_1^5+5s_1^2s_3-6s_5)/5(s_1^3-s_3); one can find the corresponding formulas in the other cases easily) and for n=4 there are 7: 1234, 1235, 1236, 1237, 1245, 1247, and 1357.
%C A007323 A theorem of Kakutani (I do not know a reference) says that the sequences which occur are exactly the finite subsets of N whose complements are additive semigroups (for instance, the complement of {1,2,4,7} is 3,5,6,8,9,..., which is closed under addition).
%C A007323 This is a really beautiful theorem. I wrote a simple program to count the sets of cardinality n which have the property in question for n = 1, ..., 16. (End)
%C A007323 This sequence relates to numerical semigroups, which are basic fundamental objects but little known: A numerical semigroup S < N is defined by being: closed under addition, contains zero and N \ S is finite. [John McKay, Jun 09 2011]
%C A007323 The theorem alluded to in the email by Zagier is due to Kakeya, not Kakutani (see references.) The theorem states that if a sequence of n positive integers k1, k2,..., kn forms the complement of a numerical semigroup, then the power sums p_k1, p_k2,..., p_kn forms a basis for the rational function field of symmetric functions in n variables. Kakeya conjectures that every power sum basis of the symmetric functions has this property, but this is still an open problem. Thanks to user Gjergji Zaimi on Math Overflow for the references. [Trevor Hyde, Oct 18 2018]
%D A007323 Sean Clark, Anton Preslicka, Josh Schwartz and Radoslav Zlatev, Some combinatorial conjectures on a family of toric ideals: A report from the MSRI 2011 Commutative Algebra graduate workshop.
%D A007323 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007323 Maria Bras-Amorós, <a href="/A007323/b007323.txt">Table of n, a(n) for n = 0..77</a>
%H A007323 Matheus Bernardini, <a href="https://arxiv.org/abs/1906.07310">Counting numerical semigroups by genus and even gaps via Kunz-coordinate vectors</a>, arXiv:1906.07310 [math.CO], 2019.
%H A007323 Matheus Bernardini and Gilberto Brito, <a href="https://arxiv.org/abs/2106.13296">On Pure k-sparse gapsets</a>, arXiv:2106.13296 [math.CO], 2021.
%H A007323 Matheus Bernardini and Fernando Torres, <a href="https://arxiv.org/abs/1612.01212">Counting numerical semigroups by genus and even gaps</a>, arXiv:1612.01212 [math.CO], 2016-2017.
%H A007323 Matheus Bernardini and Fernando Torres, <a href="https://doi.org/10.1016/j.disc.2017.08.001">Counting numerical semigroups by genus and even gaps</a>, Discrete Mathematics 340.12 (2017): 2853-2863.
%H A007323 Matheus Bernardini and Patrick Melo, <a href="https://arxiv.org/abs/2202.07694">A short note on a theorem by Eliahou and Fromentin</a>, arXiv:2202.07694 [math.CO], 2022.
%H A007323 Victor Blanco and Justo Puerto, <a href="http://arxiv.org/abs/0901.1228">Computing the number of numerical semigroups using generating functions</a>, arXiv:0901.1228 [math.CO], 2009.
%H A007323 Maria Bras-Amorós, <a href="http://crises-deim.urv.cat/~mbras/">Home Page</a> [Has many of these references]
%H A007323 Maria Bras-Amorós, <a href="http://www.singacom.uva.es/oldsite/seminarios/WorkshopSG/workshop2/Bras_SG_2007.pdf">Algebraic Geometry, Coding and Computing</a>, Segovia, Spain, 2007.
%H A007323 Maria Bras-Amorós, <a href="https://cmup.fc.up.pt/cmup/ASA/numsgps_meeting/schedule_slides.html">IMNS 2018</a>, Granada, Spain, 2008.
%H A007323 Maria Bras-Amorós, <a href="http://dx.doi.org/10.1007/s00233-007-9014-8">Fibonacci-Like Behavior of the Number of Numerical Semigroups of a Given Genus</a>, Semigroup Forum, 76 (2008), 379-384. See <a href="https://arxiv.org/abs/1706.05230">also</a>, arXiv:1706.05230 [math.NT], 2017.
%H A007323 Maria Bras-Amorós, <a href="http://dx.doi.org/10.1016/j.jpaa.2008.11.012">Bounds on the Number of Numerical Semigroups of a Given Genus</a>, Journal of Pure and Applied Algebra, vol. 213, n. 6 (2009), pp. 997-1001. arXiv:0802.2175.
%H A007323 Maria Bras-Amorós, <a href="https://arxiv.org/abs/2503.14664">Exploring the unleaved tree of numerical semigroups up to a given genus</a>, arXiv:2503.14664 [math.CO], 2025. See pp. 1, 15.
%H A007323 Maria Bras-Amorós, <a href="https://arxiv.org/abs/2503.14664"> Exploring the unleaved tree of numerical semigroups up to a given genus</a>, arXiv:2503.14664 [math.CO], 2025.
%H A007323 Maria Bras-Amorós and S. Bulygin, <a href="http://arxiv.org/abs/0810.1619">Towards a Better Understanding of the Semigroup Tree</a>, arXiv:0810.1619 [math.CO], 2008; <a href="http://dx.doi.org/10.1007/s00233-009-9175-8">Semigroup Forum 79 (2009) 561-574</a>.
%H A007323 Maria Bras-Amorós and A. de Mier, <a href="http://arxiv.org/abs/math/0612634">Representation of Numerical Semigroups by Dyck Paths</a>, arXiv:math/0612634 [math.CO], 2006; <a href="http://dx.doi.org/10.1007/s00233-007-0717-7">Semigroup Forum 75 (2007) 676-681</a>.
%H A007323 Maria Bras-Amorós and J. Fernández-González, <a href="https://arxiv.org/abs/1607.01545">arXiv version</a>, arXiv:1607.01545 [math.CO], 2016-2017; <a href="https://doi.org/10.1090/mcom/3292">Computation of numerical semigroups by means of seeds</a>, Mathematics of Computation 87 (313), American Mathematical Society, 2539-2550, September 2018.
%H A007323 Maria Bras-Amorós and J. Fernández-González, <a href="https://doi.org/10.1090/mcom/3502">The right-generators descendant of a numerical semigroup</a>, Math. Comp. 89 (2020), 2017-2030. arXiv:<a href="https://arxiv.org/abs/1911.03173">1911.03173</a> [math.CO].
%H A007323 Gilberto Brito and Stéfani Vieira, <a href="https://arxiv.org/abs/2407.21563">A certain sequence on pure kappa-sparse gapsets</a>, arXiv:2407.21563 [math.CO], 2024. See p. 2.
%H A007323 CombOS - Combinatorial Object Server, <a href="http://combos.org/sgroup.html">Generate numerical semigroups</a>
%H A007323 Manuel Delgado, Shalom Eliahou, and Jean Fromentin, <a href="https://arxiv.org/abs/2310.07742">A verification of Wilf's conjecture up to genus 100</a>, arXiv:2310.07742, 2023.
%H A007323 Shalom Eliahou and Jean Fromentin, <a href="https://images-archive.math.cnrs.fr/Semigroupes-numeriques-et-nombre-d-or-I.html">Semigroupes Numériques et Nombre d’or</a>, Images des Mathématiques, CNRS, 2018. In French.
%H A007323 Sergi Elizalde, <a href="http://arxiv.org/abs/0905.0489">Improved bounds on the number of numerical semigroups of a given genus</a>, arXiv:0905.0489 [math.CO], 2009. [Maria Bras-Amorós, Sep 01 2009]
%H A007323 G. Failla, C. Peterson, and R. Utano, <a href="http://dx.doi.org/10.1007/s00233-015-9690-8">Algorithms and basic asymptotics for generalized numerical semigroups in N^d</a>, Semigroup Forum, Jan 31 2015, DOI 10.1007/s00233-015-9690-8.
%H A007323 Gilberto B. Almeida Filho and Matheus Bernardini, <a href="https://arxiv.org/abs/2208.07692">Gapsets and the k-generalized Fibonacci sequences</a>, arXiv:2208.07692 [math.CO], 2022.
%H A007323 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Monoids of natural numbers</a> [broken link]
%H A007323 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009. [Cached copy, with permission of the author]
%H A007323 Jean Fromentin, <a href="http://arxiv.org/abs/1305.3831">Exploring the tree of numerical semigroups</a>, arXiv:1305.3831 [math.CO], 2013-2015. See <a href="https://hal.archives-ouvertes.fr/hal-00823339">also</a>, hal-00823339.
%H A007323 Jean Fromentin and Shalom Eliahou, <a href="https://images-archive.math.cnrs.fr/Semigroupes-numeriques-et-nombre-d-or-II.html">Semigroupes numériques et nombre d’or (II)</a>, (in French), Images des Mathématiques, CNRS, 2018.
%H A007323 Jean Fromentin and Florent Hivert, <a href="https://doi.org/10.1090/mcom/3075">Exploring the tree of numerical semigroups</a>, Math. Comp. 85 (2016), 2553-2568.
%H A007323 Florent Hivert, <a href="https://dx.doi.org/10.1145/3115936.3115938">High Performance Computing Experiments in Enumerative and Algebraic Combinatorics</a>, PASCO 2017 Proceedings of the International Workshop on Parallel Symbolic Computation, Article No. 2.
%H A007323 Trevor Hyde, <a href="https://mathoverflow.net/questions/310210/reference-for-kakutani-result-on-power-sum-bases-of-symmetric-functions">Math Overflow post on reference for result mentioned in Zagier's email.</a>
%H A007323 S. Kakeya, <a href="https://doi.org/10.4099/jjm1924.2.0_69">On fundamental systems of symmetric functions</a>, Jap. J. Math., 2, (1925), 69-80.
%H A007323 S. Kakeya, <a href="https://doi.org/10.4099/jjm1924.4.0_77">On fundamental systems of symmetric functions II</a>, Jap. J. Math., 4, (1927), 77-85.
%H A007323 Nathan Kaplan, <a href="https://arxiv.org/abs/1707.02551">Counting Numerical Semigroups</a>, arXiv:1707.02551 [math.CO], 2017. Also Amer. Math. Monthly, 124 (2017), 862-875.
%H A007323 Jiryo Komeda, <a href="http://dx.doi.org/10.1007/PL00005972">Non-Weierstrass numerical semigroups</a>. Semigroup Forum 57 (1998), no. 2, 157-185. [Maria Bras-Amorós, Sep 01 2009]
%H A007323 Nivaldo Medeiros, <a href="https://web.archive.org/web/20150911134119/http://w3.impa.br/~nivaldo/algebra/semigroups/index.html">Numerical Semigroups</a>
%H A007323 Alex Zhai, <a href="https://doi.org/10.1007/s00233-012-9456-5">Fibonacci-like growth of numerical semigroups of a given genus</a>, Semigroup Forum, 86 (2013), 634-662. See also, arXiv:<a href="https://arxiv.org/abs/1111.3142">1111.3142</a> [math.CO], 2011.
%H A007323 Y. Zhao, <a href="http://dx.doi.org/10.1007/s00233-009-9190-9">Constructing numerical semigroups of a given genus</a>, Semigroup Forum 80 (2010) 242-254.
%H A007323 Daniel G. Zhu, <a href="https://doi.org/10.5070/C63261988">Sub-Fibonacci behavior in numerical semigroup enumeration</a>, Comb. Theory 3(2) (2023), #10. arXiv:<a href="https://arxiv.org/abs/2202.05755">2202.05755</a> [math.CO], 2022-2023.
%H A007323 <a href="/index/Se#semigroups">Index entries for sequences related to semigroups</a>
%F A007323 Conjectures: A) a(n) >= a(n-1)+a(n-2); B) a(n)/(a(n-1)+a(n-2)) approaches 1; C) a(n)/a(n-1) approaches the golden ratio;  D) a(n) >= a(n-1). Conjectures A, B, C, D were presented by M. Bras-Amorós in the seminar Algebraic Geometry, Coding and Computing, in Segovia, Spain, in 2007, and at IMNS 2018 in Granada, Spain, in 2008. Conjectures A, B, C were then published in the Semigroup Forum, 76 (2008), 379-384. Conjectures B and C are proved in the paper by Zhai, 2011. - _Maria Bras-Amorós_, Oct 24 2007, corrected Aug 31 2009
%e A007323 G.f. = x + 2*x^2 + 4*x^3 + 7*x^4 + 12*x^5 + 23*x^6 + 39*x^7 + 67*x^8 + ...
%e A007323 a(1) = 1 because the unique numerical semigroup with genus 1 is N \ {1}
%e A007323 a(3) = 4 because the four numerical semigroups with genus 3 are N \ {1,2,3}, N \ {1,2,4}, N \ {1,2,5}, and N \ {1,3,5}
%Y A007323 Row sums of A199711.
%K A007323 nonn,nice
%O A007323 0,3
%A A007323 Don Zagier (don.zagier(AT)mpim-bonn.mpg.de), Apr 11 1994
%E A007323 The terms a(17)-a(52) were contributed (in the context of semigroups) by Maria Bras-Amorós, Oct 24 2007. The computations were done with the help of Jordi Funollet and Josep M. Mondelo.
%E A007323 Terms a(53)-a(60) were taken from the Fromentin (2013) paper. - _N. J. A. Sloane_, Sep 05 2013
%E A007323 Terms a(61)-a(70) were taken from https://github.com/hivert/NumericMonoid.
%E A007323 Terms a(71)-a(72) were computed by J. Fernández-González and _Maria Bras-Amorós_.
%E A007323 Terms a(73)-a(75) were taken from the Delgado et al. (2023) paper. - _Daniel Zhu_, Feb 16 2024
%E A007323 Terms a(76)-a(77) were taken from Maria Bras-Amorós 2025 paper. - _Maria Bras-Amorós_, Mar 20 2025