cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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
Offset: 0

Views

Author

Don Zagier (don.zagier(AT)mpim-bonn.mpg.de), Apr 11 1994

Keywords

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
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]

Examples

			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}

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

Crossrefs

Row sums of A199711.

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 the paper by Zhai, 2011. - Maria Bras-Amorós, Oct 24 2007, corrected Aug 31 2009

Extensions

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.
Terms a(53)-a(60) were taken from the Fromentin (2013) paper. - N. J. A. Sloane, Sep 05 2013
Terms a(61)-a(70) were taken from https://github.com/hivert/NumericMonoid.
Terms a(71)-a(72) were computed by J. Fernández-González and Maria Bras-Amorós.
Terms a(73)-a(75) were taken from the Delgado et al. (2023) paper. - Daniel Zhu, Feb 16 2024
Terms a(76)-a(77) were taken from Maria Bras-Amorós 2025 paper. - Maria Bras-Amorós, Mar 20 2025

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.