|
| |
|
|
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 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.
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.
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_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.
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Maria Bras-Amorós, Home Page [Has many of these references]
Maria Bras-Amorós, IMNS 2018, Granada, Spain, 2008.
|
|
|
FORMULA
|
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 by Zhai, 2011. - Maria Bras-Amoró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
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
Don Zagier (don.zagier(AT)mpim-bonn.mpg.de), Apr 11 1994
|
|
|
EXTENSIONS
|
The terms from a(17) to a(52) were contributed (in the context of semigroups) by Maria Bras-Amorós (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(73) to a(75) were taken from the Delgado et al. (2023) paper. - Daniel Zhu, Feb 16 2024
|
|
|
STATUS
|
approved
|
| |
|
|
