betaFeedback

WorksMathematics

Creation Sequences for Numerical Semigroups and Exact Counts of Semigroup Partitions

Abstract

A numerical semigroup is a subset of the non-negative integers that contains 00, is closed under addition and has finite complement. A threshold graph is built by adding vertices one at a time, each new vertex being isolated or dominating, and the record of these choices is its creation sequence. Reading the creation sequence as a lattice path gives an integer partition and, through the Keith–Nath correspondence, a numerical set in which the dominating vertices are the elements and the isolated vertices are the gaps. We show that threshold graphs with an isolated vertex correspond bijectively to numerical sets, and we study numerical semigroups through their creation sequences. We prove that in the creation sequence of a numerical semigroup of multiplicity mm every block of ones and every non-initial block of zeros has length less than mm, we give criteria for partitions with a unique smallest part and with two distinct part sizes, and we classify all partitions with at most four parts. We show that every partition λλ with gg parts corresponding to a numerical semigroup satisfies ℓ(λ)≥λ1\ell(λ)\geλ_1 and, more strongly, fits inside the staircase (g,g−1,…,1)(g,g-1,\dots,1); equivalently, its creation sequence begins with a Dyck path. Its size equals the genus plus the Weierstrass weight of the semigroup, and asymptotically at most half of all partitions correspond to numerical semigroups. Finally, we obtain exact formulas for the numbers of partitions of nn corresponding to numerical semigroups of genus gg, multiplicity mm and Frobenius number ff, valid in the sharp ranges g≥n/2g\ge n/2, m>n/3m>n/3 and f≥n−n−14f\ge n-\frac{n-1}{4}. These formulas solve the open problems posed by Burson, Nam and Sisneros-Thiry \cite{BNS}, recover all of their counting theorems, and correct several of their statements.

Introduction

Numerical semigroups

A numerical semigroup is a subset SS of the non-negative integers N0\mathbb{N}_0 that contains 0, is closed under addition, and has finite complement in N0\mathbb{N}_0. Numerical semigroups arise naturally in the study of linear Diophantine equations: for coprime positive integers a1,…,aka_1,\ldots,a_k, the set of integers dd for which a1x1+⋯+akxk=da_1x_1+\cdots+a_kx_k=d has a solution in non-negative integers is the numerical semigroup ⟨a1,…,ak⟩\langle a_1,\ldots,a_k\rangle generated by a1,…,aka_1,\ldots,a_k. The largest integer that is not representable in this way is the Frobenius number. The number of non-representable integers is the genus, and the smallest positive representable integer is the multiplicity. Sylvester showed that ⟨a,b⟩\langle a,b\rangle has Frobenius number ab−a−bab-a-b and genus (a−1)(b−1)/2(a-1)(b-1)/2. No such formula is known for three or more generators, and the Frobenius problem of computing these invariants has a long history [16, 2]. Numerical semigroups also appear as value semigroups of curve singularities and as Weierstrass semigroups of points on algebraic curves, where the genus of the semigroup is the genus of the curve and the weight of the semigroup measures how special the point is [8]. Among the many distinguished classes of numerical semigroups, the symmetric, pseudo-symmetric, almost symmetric and Arf semigroups play a central role in commutative algebra, since they correspond to Gorenstein, Kunz, almost Gorenstein and Arf semigroup rings.

A fruitful combinatorial point of view encodes a numerical semigroup by an integer partition. Keith and Nath [13], motivated by the study of partitions with prescribed hook lengths and by the hook length formula for the dimensions of irreducible representations of symmetric groups, observed the following. If one walks along 0,1,2,…0,1,2,\ldots and takes an east step for each element of a numerical set SS and a north step for each gap, the resulting lattice path is the profile of a Young diagram. In this way every numerical set determines a partition λ(S)\lambda(S), and the restriction of this map to numerical semigroups is injective. Under this correspondence: the genus of SS is the number of parts of λ(S)\lambda(S); the Frobenius number of SS is the largest hook length of λ(S)\lambda(S); the multiplicity of SS is one more than the number of parts of λ(S)\lambda(S) equal to 1; the gaps of SS are exactly the hook lengths in the first column of λ(S)\lambda(S).

Constantin, Houston-Edwards and Kaplan [7] used this correspondence to relate numerical sets to core partitions and to integer points in polytopes. They showed that the partitions with largest hook NN that come from numerical semigroups form a vanishing proportion of all partitions with largest hook NN, and they conjectured that the same holds when partitions are counted by size.

A series of papers by Tutaş and her coauthors develops the partition side of the theory for Arf semigroups. Tutaş, Karakaş and Gümüşbaş [21] introduced Arf partitions and characterised Arf numerical semigroups through the hook sets of the Young tableaux of the associated partitions. Tutaş [20] extended this work, studying the relationship between Arf partitions, Young dual diagrams and rational Young diagrams. She showed that the partitions arising from gap sets of numerical semigroups form a semigroup under an intersection operation, and she related Arf partitions to semigroup polynomials, obtaining generating functions for families such as the Lipman semigroups. Karakaş and Tutaş [12] gave a decomposition of partitions and of numerical sets that is compatible with the Keith–Nath correspondence. The authors in [9] introduced almost symmetric Arf partitions and used partition theory to count almost symmetric Arf semigroups of a given genus.

Süer and Yeşil [18] studied the Young diagrams of symmetric and pseudo-symmetric numerical semigroups. They introduced new operations on Young diagrams and on numerical semigroups that yield decompositions of these objects, and they determined when the associated semigroup rings have Gorenstein and Kunz subrings. Süer and Yeşil [19] investigated special subdiagrams of Young diagrams and their numerical semigroups. More recently, Yeşil [22] proved that every almost symmetric numerical semigroup decomposes uniquely, at the level of Young diagrams, into a numerical semigroup, its dual, and a further numerical semigroup. In these works the dual (conjugate) of a Young diagram plays a central role; in particular, symmetric numerical semigroups correspond to self-conjugate diagrams. We use the same phenomenon in § 6. Related partition-theoretic viewpoints appear in recent work of Campioni [6] on unrefinable partitions into distinct parts and numerical semigroups, and of Aragona, Civino and Campioni [1], who characterise maximal unrefinable partitions geometrically via the Keith–Nath transformation and Young diagrams. Burson, Nam and Sisneros-Thiry [5] refined the question of Constantin, Houston-Edwards and Kaplan by counting PG⁡(n,g)\operatorname{PG}(n,g), PF⁡(n,f)\operatorname{PF}(n,f), and PM⁡(n,m)\operatorname{PM}(n,m), the numbers of partitions of nn corresponding to numerical semigroups of genus gg, Frobenius number ff and multiplicity mm. They proved exact identities along lines close to the extreme cases, such as PG⁡(n,g)=p(n−g)\operatorname{PG}(n,g)=p(n-g) for g≥3ng\geq3n and PF⁡(n,n)=⌈n/2⌉\operatorname{PF}(n,n)=\lceil n/2\rceil. They left three problems open: finding the functions that count the exceptional partitions for the genus ([5, Remark 1}) and for the multiplicity ([5 Remark 4]), and finding uniform theorems valid for every shift ([5 Section 6]).

A threshold graph is a graph that can be built from a single vertex by repeatedly adding either an isolated vertex or a dominating vertex [10, 15]. Threshold graphs have many equivalent characterisations, for instance by vertex weights and a threshold, or by forbidden induced subgraphs. They are determined by their degree sequences. The construction of a threshold graph is recorded by a binary word, its creation sequence, with 0 for an isolated vertex and 1 for a dominating vertex. Up to isomorphism, threshold graphs on NN vertices correspond bijectively to binary words of length N−1N-1.

In this paper we connect threshold graphs with numerical semigroups through their creation sequences. We associate numerical semigroups with threshold graphs in three steps:

threshold graph GG ⟼\longmapsto creation sequence s(G)s(G) ⟼\longmapsto partition λG\lambda_G ⟼\longmapsto numerical set SGS_G.

The partition λG\lambda_G is obtained by reading s(G)s(G) as a lattice path (1 = east, 0 = north), and SGS_G is the Keith–Nath numerical set of λG\lambda_G. Thus the vertex added at step ii is dominating exactly when i∈SGi \in S_G. Threshold graphs with an isolated vertex correspond bijectively to numerical sets (Theorem 3.9), and graph-theoretic quantities translate into semigroup invariants (Proposition 3.12). The creation sequence makes additive closure visible: SGS_G fails to be a semigroup exactly when the vertices added at two steps xx and yy are dominating while the vertex added at step x+yx+y is isolated.

Section 2 collects preliminaries on numerical semigroups, partitions and the Keith–Nath correspondence. Section 3 introduces threshold graphs and creation sequences and proves the correspondence theorem. Sections 4–8 contain the structural results, and Section 9 the counting results. Section 10 collects the solutions of the open problems of [5], and the last section lists further questions. More precisely, working entirely with creation sequences, we obtain the following interesting results.

  1. Structural criteria (Section 4). In the creation sequence of a numerical semigroup of multiplicity mm, every block of ones and every non-initial block of zeros has length less than mm (Theorem 4.2). In partition language, no part occurs more often than the smallest part, and consecutive distinct parts differ by at most that multiplicity. We give complete criteria for partitions with a unique smallest part (Theorem 4.5) and with two distinct part sizes (Theorem 4.7), and a column criterion deciding every creation sequence (Theorem 4.9).

  1. Classification by patterns (Section 5). We classify all partitions with at most four parts (Table 2).

kkpatternSλS_\lambda is a semigroup if and only ifby
2n1=n2n_1 = n_2alwaysThm 4.6
2n1>n2n_1 > n_2d1=1d_1 = 1Thm 4.5
3n1=n2=n3n_1 = n_2 = n_3alwaysThm 4.6
3n1=n2>n3n_1 = n_2 > n_3neverThm 4.5
3n1>n2=n3n_1 > n_2 = n_3d1≤2d_1 \le2Thm 4.7
3n1>n2>n3n_1 > n_2 > n_3d1=d2=1d_1 = d_2 = 1Thm 4.5
4n1=n2=n3=n4n_1 = n_2 = n_3 = n_4alwaysThm 4.6
4n1=n2=n3>n4n_1 = n_2 = n_3 > n_4neverThm 4.5
4n1=n2>n3=n4n_1 = n_2 > n_3 = n_4d2=1d_2 = 1Thm 4.7
4n1=n2>n3>n4n_1 = n_2 > n_3 > n_4neverThm 4.5
4n1>n2=n3=n4n_1 > n_2 = n_3 = n_4d1≤3d_1 \le3Thm 4.7
4n1>n2=n3>n4n_1 > n_2 = n_3 > n_4neverThm 4.5
4n1>n2>n3=n4n_1 > n_2 > n_3 = n_4(d2,d1)=(1,2)(d_2,d_1) = (1,2)Prop 5.2
4n1>n2>n3>n4n_1 > n_2 > n_3 > n_4d1=d2=d3=1d_1 = d_2 = d_3 = 1Thm 4.5

Table 2. Partitions with at most four parts whose creation sequence gives a numerical semigroup.

  1. Symmetry and density (Section 6). Conjugation of partitions reverses and complements the creation sequence. Consequently every semigroup partition satisfies ℓ(λ)≥λ1\ell(\lambda) \ge\lambda_1, with equality exactly for self-conjugate partitions, that is, symmetric semigroups (Theorem 6.2). We deduce that asymptotically at most half of all partitions correspond to numerical semigroups (Theorem 6.7).

  1. The staircase theorem (Section 7). Every semigroup partition with gg parts lies inside the staircase (g,g−1,…,1)(g,g-1,\ldots,1); equivalently, its creation sequence satisfies a ballot condition and begins with a Dyck path (Theorem 7.2, Corollary 7.6). The size of the partition equals the genus plus the weight of the semigroup (Corollary 7.4).

  1. The semigroup tree (Section 8). Deleting the largest part of a semigroup partition gives a semigroup partition; this realises the tree of numerical semigroups in partition language.

  1. Exact counting and the open problems of [5] (Sections 9 and 10). We prove

PG⁡(n,g)=p(n−g)−E(2n−3g)(2g≥n),PM⁡(n,m)=pˉ(n−m+1)−H(n−2m)(m−1≤n<3m),PF⁡(n,n−k)=p(k)⌊n−k2⌋−Ck(n−k)(n≥4k+1).\begin{aligned} \operatorname{PG}(n,g) &= p(n-g)-E(2n-3g) && (2g \ge n),\\ \operatorname{PM}(n,m) &= \bar{p}(n-m+1)-H(n-2m) && (m-1 \le n < 3m),\\ \operatorname{PF}(n,n-k) &= p(k)\left\lfloor\frac{n-k}{2}\right\rfloor-C_k(n-k) && (n \ge4k+1). \end{aligned}

where EE, HH and CkC_k are explicit finite counts of tail partitions defined through their creation sequences. We show that the three ranges are sharp, and we give exact formulas on the boundary lines. These results solve the open problems of [5], Remarks 1 and 4, Section 6] and recover all of their counting theorems; in the process we correct their Theorem 3, Corollary 4, Theorem 7(3)-(5) and Theorem 10-(4).

Preliminaries

Numerical sets and numerical semigroups

Let N0={0,1,2,…}\mathbb{N}_0 = \{0,1,2,\ldots\}. A numerical set is a subset S⊂N0S \subset\mathbb{N}_0 with 0∈S0 \in S and N0∖S\mathbb{N}_0 \setminus S finite. A numerical set is a numerical semigroup if it is closed under addition. The elements of N0∖S\mathbb{N}_0 \setminus S are the gaps of SS, and we record the following invariants:

  • (i) the genus g(S)=∣N0∖S∣g(S) = \lvert\mathbb{N}_0 \setminus S\rvert;

  • (ii) the Frobenius number F(S)=max⁡(N0∖S)F(S) = \max(\mathbb{N}_0 \setminus S), with the convention F(N0)=−1F(\mathbb{N}_0) = -1;

  • (iii) the conductor c(S)=F(S)+1c(S) = F(S) + 1, the least integer cc with [c,∞)⊆S[c,\infty) \subseteq S;

  • (iv) the multiplicity m(S)=min⁡(S∖{0})m(S) = \min(S \setminus\{0\}).

For A⊆N0A \subseteq\mathbb{N}_0 we write ⟨A⟩\langle A\rangle for the set of all finite sums of elements of AA; if gcd⁡(A)=1\gcd(A) = 1 this is a numerical semigroup. Every numerical semigroup SS has a unique minimal system of generators, consisting of its minimal generators: the nonzero elements that are not the sum of two nonzero elements of SS. Their number is the embedding dimension, and it is at most m(S)m(S). For 0≠n∈S0 \ne n \in S, the Apéry set Ap⁡(S,n)={s∈S:s−n∉S}\operatorname{Ap}(S,n) = \{s \in S : s - n \notin S\} contains exactly one element in each residue class modulo nn.

References

  1. [1]Aragona, R., Civino, R., Campioni, L.: A geometric characterization of maximal unrefinable partitions via the Keith–Nath transformation and Young diagrams, Results Math. (2026). doi:10.1007/s00025-026-02722-4.DOI
  2. [2]Assi, A., García-Sánchez, A. P.: Numerical Semigroups and Applications, RSME Springer Series, vol. 1, Springer, 2016.
  3. [3]Backelin, J.: On the number of semigroups of natural numbers, Math. Scand. 66 (1990), 197–215.DOI
  4. [4]Bras-Amorós, M.: Bounds on the number of numerical semigroups of a given genus, J. Pure Appl. Algebra 213 (2009), 997–1001.
  5. [5]Burson H. E., Nam H. H., Sisneros-Thiry, S.: On integer partitions corresponding to numerical semigroups, Results Math. 78 (2023), 193.arxiv.org/abs/2302.08391
  6. [6]Campioni, L.: Unrefinable partitions into distinct parts and numerical semigroups, Boll Unione Mat Ital, (2026), https://doi.org/10.1007/s40574-026-00532-8.
  7. [7]Constantin, H., Houston-Edwards, B., Kaplan, N.: Numerical sets, core partitions, and integer points in polytopes, in: Combinatorial and Additive Number Theory II, Springer, 2017, pp. 99–127.DOI
  8. [8]Eisenbud, D., Harris, J.: Existence, decomposition, and limits of certain Weierstrass points, Invent. Math. 87 (1987), 495–515.DOI
  9. [9]Gümüşbaş Öztürk, N., Tutaş, N., Er., N.: Almost symmetric Arf partitions, Turkish J. Math. 44(6) (2020), 2185–2198. doi:10.3906/mat-2003-74.
  10. [10]Hammer, P., L., Ibaraki, T., Simeone, B.: Threshold sequences, SIAM J. Algebraic Discrete Methods 2 (1981), 39–49.DOI
  11. [11]Hardy, H., G., Ramanujan, S.: Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. (2) 17 (1918), 75–115.
  12. [12]Karakaş, H., İ., Tutaş, N.: A decomposition of partitions and numerical sets, Semigroup Forum 101(3) (2020), 704–715. doi:10.1007/s00233-019-10080-7.DOI
  13. [13]Keith, W., J., Nath, R.: Partitions with prescribed hooksets, J. Comb. Number Theory 3(1) (2011), 39.arxiv.org/abs/1011.1945
  14. [14]Kunz . E.: Über die Klassifikation numerischer Halbgruppen, Regensburger Math. Schriften 11 (1987).DOI
  15. [15]Mahadev, N., V., R., Peled, U., N.: Threshold Graphs and Related Topics, Annals of Discrete Mathematics, vol. 56, North-Holland, Amsterdam, 1995.
  16. [16]Rosales, J., C., García-Sánchez, P. A.: Numerical Semigroups, Developments in Mathematics, vol. 20, Springer, New York, 2009.DOI
  17. [17]Stanley, P., R.: Catalan Numbers, Cambridge University Press, 2015.DOI
  18. [18]Süer, M., Yeşil, M.: Symmetric and pseudo-symmetric numerical semigroups via Young diagrams and their semigroup rings, J. Korean Math. Soc. 58(6) (2021), 1367–1383.arxiv.org/abs/2011.08540
  19. [19]Süer, M., Yeşil, M. : Special subdiagrams of Young diagrams and numerical semigroups, Turkish J. Math. 48(2) (2024), 346–359.DOI
  20. [20]Tutaş, N.: On partitions and Arf semigroups, Open Math. 17(1) (2019), 343–355. doi:10.1515/math-2019-0025.DOI
  21. [21]Tutaş, N, Karakaş, H., İ., Gümüşbaş, N.: Young tableaux and Arf partitions, Turkish J. Math. 43(1) (2019), 448–459. doi:10.3906/mat-1807-181.DOI
  22. [22]Yeşil, M.: Young diagram decompositions for almost symmetric numerical semigroups, Results Math. 80 (2025), 217. doi:10.1007/s00025-025-02527.DOI
  23. [23]Zhai, A.: Fibonacci-like growth of numerical semigroups of a given genus, Semigroup Forum 86 (2013), 634–662.arxiv.org/abs/1111.3142

Paper details

vlnc:W_kvbjqx75
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents