

A007323


The number of numerical semigroups of "genus" n; conjecturally also the number of power sum bases for symmetric functions in n variables.
(Formerly M1064)


6



1, 1, 2, 4, 7, 12, 23, 39, 67, 118, 204, 343, 592, 1001, 1693, 2857, 4806, 8045, 13467, 22464, 37396, 62194, 103246, 170963, 282828, 467224, 770832, 1270267, 2091030, 3437839, 5646773, 9266788, 15195070, 24896206, 40761087, 66687201, 109032500
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

From Don Zagier's email of Apr 11 1994: (Start)
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 ith elementary symmetric polynomial. Here one has no choice, because sigma_i=0 for i>n and fewer than n sigma's would not suffice.
But, by Newton's formulas, the field is also given as Q(s_1,...,s_n) where s_i is the ith power sum, and now one can ask whether some other sequence s_{j_1},...,s_{j_n} (0<j_1<...<j_n) also works.
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.
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_36s_5)/5(s_1^3s_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.
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).
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)
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]
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]


REFERENCES

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.
S. Kakeya, On fundamental systems of symmetric functions, Jap. J. Math., 2, (1925), 6980.
S. Kakeya, On fundamental systems of symmetric functions II, Jap. J. Math., 4, (1927), 7785.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Maria BrasAmorós, Table of n, a(n) for n = 0..72 [For history of these computations see the Extensions section  N. J. A. Sloane, Aug 16 2019]
Matheus Bernardini, and Fernando Torres, Counting numerical semigroups by genus and even gaps, arXiv:1612.01212 [math.CO], 20162017.
Matheus Bernardini, and Fernando Torres, Counting numerical semigroups by genus and even gaps, Discrete Mathematics 340.12 (2017): 28532863.
Matheus Bernardini, Counting numerical semigroups by genus and even gaps via Kunzcoordinate vectors, arXiv:1906.07310 [math.CO], 2019.
Victor Blanco, Justo Puerto, Computing the number of numerical semigroups using generating functions, arXiv:0901.1228 [math.CO], 2009.
Maria BrasAmoros, Home Page [Has many of these references]
M. BrasAmoros, Algebraic Geometry, Coding and Computing , Segovia, Spain, 2007.
M. BrasAmoros, IMNS 2018 , Granada, Spain, 2008.
M. BrasAmoros, FibonacciLike Behavior of the Number of Numerical Semigroups of a Given Genus, Semigroup Forum, 76 (2008), 379384. See also, arXiv:1706.05230 [math.NT], 2017.
M. BrasAmoros, Bounds on the Number of Numerical Semigroups of a Given Genus, Journal of Pure and Applied Algebra, vol. 213, n. 6 (2009), pp. 9971001. arXiv:0802.2175.
M. BrasAmoros and S. Bulygin, Towards a Better Understanding of the Semigroup Tree, arXiv:0810.1619 [math.CO], 2008; Semigroup Forum 79 (2009) 561574.
M. BrasAmoros and A. de Mier, Representation of Numerical Semigroups by Dyck Paths, arXiv:math/0612634 [math.CO], 2006; Semigroup Forum 75 (2007) 676681.
Maria BrasAmorós, J. FernándezGonzález, arXiv version, arXiv:1607.01545 [math.CO], 20162017; Computation of numerical semigroups by means of seeds, Mathematics of Computation 87 (313), American Mathematical Society, 25392550, September 2018.
Maria BrasAmorós, J. FernándezGonzález, The rightgenerators descendant of a numerical semigroup, arXiv:1911.03173 [math.CO], 2019. To appear in Mathematics of Computation, American Mathematical Society, 2020.
CombOS  Combinatorial Object Server, Generate numerical semigroups
Shalom Eliahou, Jean Fromentin, Semigroupes Numériques et Nombre d’or, Images des Mathématiques, CNRS, 2018. In French.
Sergi Elizalde, Improved bounds on the number of numerical semigroups of a given genus, arXiv:0905.0489 [math.CO], 2009. [Maria BrasAmoros, Sep 01 2009]
G. Failla, C. Peterson, R. Utano, Algorithms and basic asymptotics for generalized numerical semigroups in N^d, Semigroup Forum, Jan 31 2015, DOI 10.1007/s0023301596908.
S. R. Finch, Monoids of natural numbers
S. R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
Jean Fromentin, Exploring the tree of numerical semigroups, arXiv:1305.3831 [math.CO], 20132015. See also, hal00823339.
Jean Fromentin, Shalom Eliahou, Semigroupes numériques et nombre d’or (II), (in French), Images des Mathématiques, CNRS, 2018.
Florent Hivert, High Performance Computing Experiments in Enumerative and Algebraic Combinatorics, PASCO 2017 Proceedings of the International Workshop on Parallel Symbolic Computation, Article No. 2.
Trevor Hyde, Math Overflow post on reference for result mentioned in Zagier's email.
Nathan Kaplan, Counting Numerical Semigroups, arXiv:1707.02551 [math.CO], 2017. Also Amer. Math. Monthly, 124 (2017), 862875.
Jiryo Komeda, NonWeierstrass numerical semigroups. Semigroup Forum 57 (1998), no. 2, 157185. [Maria BrasAmoros, Sep 01 2009]
Nivaldo Medeiros, Numerical Semigroups
Alex Zhai, Fibonaccilike growth of numerical semigroups of a given genus, Semigroup Forum, 86 (2013), 634662. See also, arXiv:1111.3142 [math.CO], 2011.
Y. Zhao, Constructing numerical semigroups of a given genus, Semigroup Forum 80 (2010) 242254.
Index entries for sequences related to semigroups


FORMULA

Conjectures: A) a(n) >= a(n1)+a(n2); B) a(n)/(a(n1)+a(n2)) approaches 1; C) a(n)/a(n1) approaches the golden ratio; D) a(n) >= a(n1). Conjectures A, B, C, D were presented by M. BrasAmoró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), 379384. Conjectures B and C are proved in by Zhai, 2011.  Maria BrasAmorós, Oct 24 2007, corrected Aug 31 2009


EXAMPLE

G.f. = x + 2*x^2 + 4*x^3 + 7*x^4 + 12*x^5 + 23*x^6 + 39*x^7 + 67*x^8 + ...
a(1) = 1 because the unique numerical semigroup with genus 1 is N \ {1}
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}


CROSSREFS

Row sums of A199711. [corrected by Jonathan Sondow, Nov 05 2017]
Sequence in context: A082548 A270995 A299023 * A099604 A026790 A054165
Adjacent sequences: A007320 A007321 A007322 * A007324 A007325 A007326


KEYWORD

nonn,nice


AUTHOR

Don Zagier (don.zagier(AT)mpimbonn.mpg.de), Apr 11 1994


EXTENSIONS

The terms from a(17) to a(52) were contributed (in the context of semigroups) by Maria BrasAmoros (maria.bras(AT)gmail.com), Oct 24 2007. The computations were done with the help of Jordi Funollet and Josep M. Mondelo.
Terms a(53)a(60) were taken from the Fromentin (2013) paper.  N. J. A. Sloane, Sep 05 2013
Terms a(61) to a(70) were taken from https://github.com/hivert/NumericMonoid.
Terms a(71) and a(72) were computed by J. FernándezGonzález and Maria BrasAmorós.


STATUS

approved



