Introduction
Numerical semigroups
A numerical semigroup is a subset S S S of the non-negative integers N 0 \mathbb{N}_0 N 0 that contains 0, is closed under addition, and has finite complement in N 0 \mathbb{N}_0 N 0 . Numerical semigroups arise naturally in the study of linear Diophantine equations: for coprime positive integers a 1 , … , a k a_1,\ldots,a_k a 1 , … , a k , the set of integers d d d for which a 1 x 1 + ⋯ + a k x k = d a_1x_1+\cdots+a_kx_k=d a 1 x 1 + ⋯ + a k x k = d has a solution in non-negative integers is the numerical semigroup ⟨ a 1 , … , a k ⟩ \langle a_1,\ldots,a_k\rangle ⟨ a 1 , … , a k ⟩ generated by a 1 , … , a k a_1,\ldots,a_k a 1 , … , 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 ⟨ a , b ⟩ has Frobenius number a b − a − b ab-a-b ab − a − b and genus ( a − 1 ) ( b − 1 ) / 2 (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 0 , 1 , 2 , … and takes an east step for each element of a numerical set S S S 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) λ ( S ) , and the restriction of this map to numerical semigroups is injective. Under this correspondence: the genus of S S S is the number of parts of λ ( S ) \lambda(S) λ ( S ) ; the Frobenius number of S S S is the largest hook length of λ ( S ) \lambda(S) λ ( S ) ; the multiplicity of S S S is one more than the number of parts of λ ( S ) \lambda(S) λ ( S ) equal to 1; the gaps of S S S are exactly the hook lengths in the first column of λ ( S ) \lambda(S) λ ( 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 N N N that come from numerical semigroups form a vanishing proportion of all partitions with largest hook N N N , 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) PG ( n , g ) , PF ( n , f ) \operatorname{PF}(n,f) PF ( n , f ) , and PM ( n , m ) \operatorname{PM}(n,m) PM ( n , m ) , the numbers of partitions of n n n corresponding to numerical semigroups of genus g g g , Frobenius number f f f and multiplicity m m m . 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) PG ( n , g ) = p ( n − g ) for g ≥ 3 n g\geq3n g ≥ 3 n and PF ( n , n ) = ⌈ n / 2 ⌉ \operatorname{PF}(n,n)=\lceil n/2\rceil PF ( n , n ) = ⌈ n /2 ⌉ . 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 N N N vertices correspond bijectively to binary words of length N − 1 N-1 N − 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 G G G ⟼ \longmapsto ⟼ creation sequence s ( G ) s(G) s ( G ) ⟼ \longmapsto ⟼ partition λ G \lambda_G λ G ⟼ \longmapsto ⟼ numerical set S G S_G S G .
The partition λ G \lambda_G λ G is obtained by reading s ( G ) s(G) s ( G ) as a lattice path (1 = east, 0 = north), and S G S_G S G is the Keith–Nath numerical set of λ G \lambda_G λ G . Thus the vertex added at step i i i is dominating exactly when i ∈ S G i \in S_G i ∈ 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: S G S_G S G fails to be a semigroup exactly when the vertices added at two steps x x x and y y y are dominating while the vertex added at step x + y x+y x + 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.
Structural criteria (Section 4). In the creation sequence of a numerical semigroup of multiplicity m m m , every block of ones and every non-initial block of zeros has length less than m m m (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 ).
Classification by patterns (Section 5). We classify all partitions with at most four parts (Table 2 ).
Table 2. Partitions with at most four parts whose creation sequence gives a numerical semigroup.
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 ℓ ( λ ) ≥ λ 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 ).
The staircase theorem (Section 7). Every semigroup partition with g g g parts lies inside the staircase ( g , g − 1 , … , 1 ) (g,g-1,\ldots,1) ( g , g − 1 , … , 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).
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.
Exact counting and the open problems of [5 ] (Sections 9 and 10). We prove
PG ( n , g ) = p ( n − g ) − E ( 2 n − 3 g ) ( 2 g ≥ n ) , PM ( n , m ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) ( m − 1 ≤ n < 3 m ) , PF ( n , n − k ) = p ( k ) ⌊ n − k 2 ⌋ − C k ( n − k ) ( n ≥ 4 k + 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} PG ( n , g ) PM ( n , m ) PF ( n , n − k ) = p ( n − g ) − E ( 2 n − 3 g ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) = p ( k ) ⌊ 2 n − k ⌋ − C k ( n − k ) ( 2 g ≥ n ) , ( m − 1 ≤ n < 3 m ) , ( n ≥ 4 k + 1 ) .
where E E E , H H H and C k C_k C 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 N 0 = { 0 , 1 , 2 , … } \mathbb{N}_0 = \{0,1,2,\ldots\} N 0 = { 0 , 1 , 2 , … } . A numerical set is a subset S ⊂ N 0 S \subset\mathbb{N}_0 S ⊂ N 0 with 0 ∈ S 0 \in S 0 ∈ S and N 0 ∖ S \mathbb{N}_0 \setminus S N 0 ∖ S finite. A numerical set is a numerical semigroup if it is closed under addition. The elements of N 0 ∖ S \mathbb{N}_0 \setminus S N 0 ∖ S are the gaps of S S S , and we record the following invariants:
(i) the genus g ( S ) = ∣ N 0 ∖ S ∣ g(S) = \lvert\mathbb{N}_0 \setminus S\rvert g ( S ) = ∣ N 0 ∖ S ∣ ;
(ii) the Frobenius number F ( S ) = max ( N 0 ∖ S ) F(S) = \max(\mathbb{N}_0 \setminus S) F ( S ) = max ( N 0 ∖ S ) , with the convention F ( N 0 ) = − 1 F(\mathbb{N}_0) = -1 F ( N 0 ) = − 1 ;
(iii) the conductor c ( S ) = F ( S ) + 1 c(S) = F(S) + 1 c ( S ) = F ( S ) + 1 , the least integer c c c with [ c , ∞ ) ⊆ S [c,\infty) \subseteq S [ c , ∞ ) ⊆ S ;
(iv) the multiplicity m ( S ) = min ( S ∖ { 0 } ) m(S) = \min(S \setminus\{0\}) m ( S ) = min ( S ∖ { 0 }) .
For A ⊆ N 0 A \subseteq\mathbb{N}_0 A ⊆ N 0 we write ⟨ A ⟩ \langle A\rangle ⟨ A ⟩ for the set of all finite sums of elements of A A A ; if gcd ( A ) = 1 \gcd(A) = 1 g cd( A ) = 1 this is a numerical semigroup. Every numerical semigroup S S S 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 S S S . Their number is the embedding dimension , and it is at most m ( S ) m(S) m ( S ) . For 0 ≠ n ∈ S 0 \ne n \in S 0 = n ∈ S , the Apéry set Ap ( S , n ) = { s ∈ S : s − n ∉ S } \operatorname{Ap}(S,n) = \{s \in S : s - n \notin S\} Ap ( S , n ) = { s ∈ S : s − n ∈ / S } contains exactly one element in each residue class modulo n n n .
Example 2.1. The numerical semigroup ⟨ 3 , 5 ⟩ = { 0 , 3 , 5 , 6 , 8 , 9 , 10 , … } \langle3,5\rangle= \{0,3,5,6,8,9,10,\ldots\} ⟨ 3 , 5 ⟩ = { 0 , 3 , 5 , 6 , 8 , 9 , 10 , … } has gaps { 1 , 2 , 4 , 7 } \{1,2,4,7\} { 1 , 2 , 4 , 7 } , so g = 4 g = 4 g = 4 , F = 7 F = 7 F = 7 and m = 3 m = 3 m = 3 . Its Apéry set with respect to 3 3 3 is { 0 , 5 , 10 } \{0,5,10\} { 0 , 5 , 10 } . In accordance with Sylvester’s formulas, F = 3 ⋅ 5 − 3 − 5 F = 3 \cdot5 - 3 - 5 F = 3 ⋅ 5 − 3 − 5 and g = ( 3 − 1 ) ( 5 − 1 ) / 2 g = (3 - 1)(5 - 1)/2 g = ( 3 − 1 ) ( 5 − 1 ) /2 . For ⟨ 3 , 5 , 7 ⟩ = N 0 ∖ { 1 , 2 , 4 } = { 0 , 3 , 5 , 6 , 7 , … } \langle3,5,7\rangle= \mathbb{N}_0 \setminus\{1,2,4\} = \{0,3,5,6,7,\ldots\} ⟨ 3 , 5 , 7 ⟩ = N 0 ∖ { 1 , 2 , 4 } = { 0 , 3 , 5 , 6 , 7 , … } , g = 3 g = 3 g = 3 , F = 4 F = 4 F = 4 and m = 3 m = 3 m = 3 . Note that the numerical set N 0 ∖ { 1 , 3 , 4 } = { 0 , 2 , 5 , 6 , … } \mathbb{N}_0 \setminus\{1,3,4\} = \{0,2,5,6,\ldots\} N 0 ∖ { 1 , 3 , 4 } = { 0 , 2 , 5 , 6 , … } is not a semigroup, since 2 + 2 = 4 2 + 2 = 4 2 + 2 = 4 is a gap.
A numerical semigroup S S S is symmetric if, for all x ∈ Z x \in\mathbb{Z} x ∈ Z , x ∈ S x \in S x ∈ S if and only if F ( S ) − x ∉ S . I t i s ∗ p s e u d o − s y m m e t r i c ∗ i f F(S) - x \notin S. It is *pseudo-symmetric* if F ( S ) − x ∈ / S . I t i s ∗ p se u d o − sy mm e t r i c ∗ i f F(S)$ is even and, for all x ≠ F ( S ) / 2 x \ne F(S)/2 x = F ( S ) /2 , x ∈ S x \in S x ∈ S if and only if $F(S) - x \notin S. It is irreducible if it cannot be written as the intersection of two numerical semigroups properly containing it. A numerical semigroup is irreducible if and only if it is symmetric or pseudo-symmetric, and this happens if and only if g ( S ) = ⌈ ( F ( S ) + 1 ) / 2 ⌉ g(S) = \lceil(F(S) + 1)/2\rceil g ( S ) = ⌈( F ( S ) + 1 ) /2 ⌉ [16 ] . For every numerical semigroup, g ( S ) ≥ ( F ( S ) + 1 ) / 2 g(S) \ge(F(S) + 1)/2 g ( S ) ≥ ( F ( S ) + 1 ) /2 . A numerical semigroup is Arf if x + y − z ∈ S x + y - z \in S x + y − z ∈ S for all x ≥ y ≥ z x \ge y \ge z x ≥ y ≥ z in S S S [16 ] ; Arf semigroups and their partitions are the subject of [21 , 20 , 9 ] .
Example 2.2. ⟨ 3 , 5 ⟩ \langle3,5\rangle ⟨ 3 , 5 ⟩ and ⟨ 4 , 5 , 6 ⟩ \langle4,5,6\rangle ⟨ 4 , 5 , 6 ⟩ are symmetric: both have g = 4 = ( F + 1 ) / 2 g = 4 = (F + 1)/2 g = 4 = ( F + 1 ) /2 with F = 7 F = 7 F = 7 . For ⟨ 4 , 5 , 6 ⟩ \langle4,5,6\rangle ⟨ 4 , 5 , 6 ⟩ , for instance, the gaps 1 , 2 , 3 , 7 1,2,3,7 1 , 2 , 3 , 7 are exactly the numbers 7 − s 7 - s 7 − s with s ∈ { 6 , 5 , 4 , 0 } s \in\{6,5,4,0\} s ∈ { 6 , 5 , 4 , 0 } . ⟨ 3 , 5 , 7 ⟩ \langle3,5,7\rangle ⟨ 3 , 5 , 7 ⟩ is pseudo-symmetric: F = 4 F = 4 F = 4 is even and g = 3 = ( F + 2 ) / 2 g = 3 = (F + 2)/2 g = 3 = ( F + 2 ) /2 . ⟨ 4 , 5 , 6 , 7 ⟩ = { 0 , 4 , 5 , … } \langle4,5,6,7\rangle= \{0,4,5,\ldots\} ⟨ 4 , 5 , 6 , 7 ⟩ = { 0 , 4 , 5 , … } has F = 3 F = 3 F = 3 and g = 3 > ⌈ ( 3 + 1 ) / 2 ⌉ g = 3 > \lceil(3 + 1)/2\rceil g = 3 > ⌈( 3 + 1 ) /2 ⌉ , so it is not irreducible.
If S ≠ N 0 S \ne\mathbb{N}_0 S = N 0 is a numerical semigroup, then S ∪ { F ( S ) } S \cup\{F(S)\} S ∪ { F ( S )} is again a numerical semigroup, of genus g ( S ) − 1 g(S) - 1 g ( S ) − 1 . Therefore all numerical semigroups form a rooted tree with root N 0 \mathbb{N}_0 N 0 , in which the parent of S S S is S ∪ { F ( S ) } S \cup\{F(S)\} S ∪ { F ( S )} . The children of S S S are the semigroups S ∖ { x } S \setminus\{x\} S ∖ { x } for the minimal generators x > F ( S ) x > F(S) x > F ( S ) [16 ] . The number n g n_g n g of numerical semigroups of genus g g g satisfies 2 F g ≤ n g ≤ 1 + 3 ⋅ 2 g − 3 2F_g \le n_g \le1 + 3 \cdot2^{g-3} 2 F g ≤ n g ≤ 1 + 3 ⋅ 2 g − 3 for g > 3 g > 3 g > 3 , with F g F_g F g the Fibonacci numbers [4 ] , and n g n_g n g grows like C φ g C\varphi^g C φ g , where φ \varphi φ is the golden ratio [23 ] .
Partitions and Young diagrams
A partition of n n n is a non-increasing sequence λ = ( λ 1 , … , λ k ) \lambda= (\lambda_1,\ldots,\lambda_k) λ = ( λ 1 , … , λ k ) of positive integers with ∣ λ ∣ = \lvert\lambda\rvert= ∣ λ ∣ =
∑ i = 1 k λ i = n . \sum_{i=1}^{k} \lambda_i = n. i = 1 ∑ k λ i = n .
We write λ ⊢ n \lambda\vdash n λ ⊢ n , ℓ ( λ ) = k \ell(\lambda) = k ℓ ( λ ) = k for the number of parts, and use exponents for repeated parts, that is, ( 3 , 2 2 , 1 3 ) = ( 3 , 2 , 2 , 1 , 1 , 1 ) (3,2^2,1^3) = (3,2,2,1,1,1) ( 3 , 2 2 , 1 3 ) = ( 3 , 2 , 2 , 1 , 1 , 1 ) . The Young diagram of λ \lambda λ is the left-justified array of cells with λ i \lambda_i λ i cells in row i i i , rows numbered from the top. The conjugate λ ′ \lambda' λ ′ is obtained by reflecting the diagram across its main diagonal, so that λ j ′ = # { i : λ i ≥ j } \lambda'_j = \#\{i : \lambda_i \ge j\} λ j ′ = # { i : λ i ≥ j } ; a partition is self-conjugate if λ = λ ′ \lambda= \lambda' λ = λ ′ . The hook of a cell ( i , j ) (i,j) ( i , j ) consists of the cell itself, the cells to its right in row i i i (the arm ), and the cells below it in column j j j (the leg ). Its hook length is
h ( i , j ) ( λ ) = λ i − j + λ j ′ − i + 1. h_{(i,j)}(\lambda) = \lambda_i - j + \lambda'_j - i + 1. h ( i , j ) ( λ ) = λ i − j + λ j ′ − i + 1.
In particular h ( 1 , 1 ) ( λ ) = λ 1 + ℓ ( λ ) − 1 h_{(1,1)}(\lambda)=\lambda_1+\ell(\lambda)-1 h ( 1 , 1 ) ( λ ) = λ 1 + ℓ ( λ ) − 1 . A partition is a hook if it has the form ( a , 1 b ) (a,1^b) ( a , 1 b ) . For partitions μ , λ \mu,\lambda μ , λ we write μ ⊆ λ \mu\subseteq\lambda μ ⊆ λ if μ i ≤ λ i \mu_i\le\lambda_i μ i ≤ λ i for all i i i . We use the following counting functions:
p ( n ) = # { λ ⊢ n } , p ˉ ( n ) = # { λ ⊢ n : 1 ∉ λ } , a ( n ) = p ˉ ( n ) − 1 ( n ≥ 2 ) , p(n)=\#\{\lambda\vdash n\},\qquad\bar p(n)=\#\{\lambda\vdash n:1\notin\lambda\},\qquad a(n)=\bar p(n)-1\ (n\ge2), p ( n ) = # { λ ⊢ n } , p ˉ ( n ) = # { λ ⊢ n : 1 ∈ / λ } , a ( n ) = p ˉ ( n ) − 1 ( n ≥ 2 ) ,
a ˉ ( n ) = # { λ ⊢ n : 1 ∉ λ , ℓ ( λ ) ≥ 2 , λ 1 = λ 2 } , b ( n ) = # { λ ⊢ n + 2 : ℓ ( λ ) ≤ n , λ 1 ≤ n } . \bar a(n)=\#\{\lambda\vdash n:1\notin\lambda,\ \ell(\lambda)\ge2,\ \lambda_1=\lambda_2\},\qquad b(n)=\#\{\lambda\vdash n+2:\ell(\lambda)\le n,\ \lambda_1\le n\}. a ˉ ( n ) = # { λ ⊢ n : 1 ∈ / λ , ℓ ( λ ) ≥ 2 , λ 1 = λ 2 } , b ( n ) = # { λ ⊢ n + 2 : ℓ ( λ ) ≤ n , λ 1 ≤ n } .
Removing one part equal to 1 1 1 shows that p ( n ) − p ( n − 1 ) = p ˉ ( n ) p(n)-p(n-1)=\bar p(n) p ( n ) − p ( n − 1 ) = p ˉ ( n ) . By the Hardy–Ramanujan formula [11 ] , p ( n ) ∼ 1 4 n 3 e π 2 n / 3 p(n)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{2n/3}} p ( n ) ∼ 4 n 3 1 e π 2 n /3 ; in particular p ( n − 1 ) / p ( n ) → 1 p(n-1)/p(n)\to1 p ( n − 1 ) / p ( n ) → 1 .
The Keith–Nath correspondence
Let S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 be a numerical set with Frobenius number F F F . Walk along 0 , 1 , … , F 0,1,\ldots,F 0 , 1 , … , F , taking an east step for each element of S S S and a north step for each gap. Starting from the bottom-left corner, this traces the profile of a Young diagram, and we denote the corresponding partition by λ ( S ) \lambda(S) λ ( S ) . The rows of λ ( S ) \lambda(S) λ ( S ) correspond to the north steps, that is, to the gaps. The length of the row belonging to a gap x x x is the number of elements of S S S smaller than x x x . Conversely, every partition λ ≠ ∅ \lambda\ne\varnothing λ = ∅ equals λ ( S ) \lambda(S) λ ( S ) for exactly one numerical set S S S [13 ] , and we set λ ( N 0 ) = ∅ \lambda(\mathbb{N}_0)=\varnothing λ ( N 0 ) = ∅ . We write S K N ( λ ) S^{KN}(\lambda) S K N ( λ ) for the inverse map.
Proposition 2.3 ([13 , 5 ] ). Let S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 be a numerical set and λ = λ ( S ) \lambda=\lambda(S) λ = λ ( S ) . Then g ( S ) = ℓ ( λ ) g(S)=\ell(\lambda) g ( S ) = ℓ ( λ ) and F ( S ) = h ( 1 , 1 ) ( λ ) F(S)=h_{(1,1)}(\lambda) F ( S ) = h ( 1 , 1 ) ( λ ) . The gaps of S S S are exactly the hook lengths h ( i , 1 ) ( λ ) h_{(i,1)}(\lambda) h ( i , 1 ) ( λ ) of the first column. If S S S is a numerical semigroup and S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 , then m ( S ) − 1 m(S)-1 m ( S ) − 1 is the number of parts of λ \lambda λ equal to 1 1 1 .
Proof. The number of north steps is the number of gaps, and the path has F + 1 F+1 F + 1 steps in total, namely λ 1 \lambda_1 λ 1 east steps and ℓ ( λ ) \ell(\lambda) ℓ ( λ ) north steps, so F = λ 1 + ℓ ( λ ) − 1 = h ( 1 , 1 ) ( λ ) F=\lambda_1+\ell(\lambda)-1=h_{(1,1)}(\lambda) F = λ 1 + ℓ ( λ ) − 1 = h ( 1 , 1 ) ( λ ) . The gap x x x corresponding to row i i i is the index of its north step; the steps after it consist of λ 1 − λ i \lambda_1-\lambda_i λ 1 − λ i east steps and i − 1 i-1 i − 1 north steps. So x = F − ( λ 1 − λ i ) − ( i − 1 ) = λ i + ℓ ( λ ) − i = h ( i , 1 ) ( λ ) x=F-(\lambda_1-\lambda_i)-(i-1)=\lambda_i+\ell(\lambda)-i=h_{(i,1)}(\lambda) x = F − ( λ 1 − λ i ) − ( i − 1 ) = λ i + ℓ ( λ ) − i = h ( i , 1 ) ( λ ) . Finally, if S S S is a semigroup with multiplicity m m m , the path begins with one east step (the element 0 0 0 ) followed by m − 1 m-1 m − 1 north steps (the gaps 1 , … , m − 1 1,\ldots,m-1 1 , … , m − 1 ). These give exactly m − 1 m-1 m − 1 rows of length 1 1 1 , and all later rows are longer.
Example 2.4. The numerical set S = { 0 , 3 , 4 , 7 , 9 , 10 , 12 , → } S=\{0,3,4,7,9,10,12,\to\} S = { 0 , 3 , 4 , 7 , 9 , 10 , 12 , → } has gaps { 1 , 2 , 5 , 6 , 8 , 11 } \{1,2,5,6,8,11\} { 1 , 2 , 5 , 6 , 8 , 11 } , so g = 6 g=6 g = 6 , F = 11 F=11 F = 11 and least positive element 3 3 3 . It is not a semigroup, since 3 + 3 = 6 3+3=6 3 + 3 = 6 is a gap. Its Keith–Nath path is E N N E E N N E N E E N ENNEEN NEN EEN E N N E E N N E N E E N and λ ( S ) = ( 6 , 4 , 3 , 3 , 1 , 1 ) \lambda(S)=(6,4,3,3,1,1) λ ( S ) = ( 6 , 4 , 3 , 3 , 1 , 1 ) . Indeed λ \lambda λ has 6 6 6 parts, h ( 1 , 1 ) = 6 + 6 − 1 = 11 h_{(1,1)}=6+6-1=11 h ( 1 , 1 ) = 6 + 6 − 1 = 11 , exactly two parts equal to 1 1 1 (one less than the least positive element), and first-column hook lengths 11 , 8 , 6 , 5 , 2 , 1 11,8,6,5,2,1 11 , 8 , 6 , 5 , 2 , 1 , which are the gaps. (This is the example of [5 Figure 1] .)
Following [5 ] , a partition λ \lambda λ corresponds to a numerical semigroup if S K N ( λ ) S^{KN}(\lambda) S K N ( λ ) is a numerical semigroup. We write PG ( n , g ) \operatorname{PG}(n,g) PG ( n , g ) , PM ( n , m ) \operatorname{PM}(n,m) PM ( n , m ) and PF ( n , f ) \operatorname{PF}(n,f) PF ( n , f ) for the numbers of such λ ⊢ n \lambda\vdash n λ ⊢ n with, respectively, exactly g g g parts, exactly m − 1 m-1 m − 1 parts equal to 1 1 1 , and largest hook length f f f . By Proposition 2.3, these count partitions of n n n corresponding to numerical semigroups of genus g g g , multiplicity m m m and Frobenius number f f f . Finally, let S ′ ( n ) S'(n) S ′ ( n ) be the number of partitions of size at most n n n corresponding to numerical semigroups, and P ( n ) = ∑ j ≤ n p ( j ) P(n)=\sum_{j\le n}p(j) P ( n ) = ∑ j ≤ n p ( j ) ; Constantin, Houston-Edwards and Kaplan conjectured that S ′ ( n ) / P ( n ) → 0 S'(n)/P(n)\to0 S ′ ( n ) / P ( n ) → 0 [7 ] .
Threshold graphs, creation sequences and numerical sets
Threshold graphs and their creation sequences
Definition 3.1. A graph G = ( V , E ) G=(V,E) G = ( V , E ) is a threshold graph if there are weights wt : V → R \operatorname{wt}:V\to\mathbb{R} wt : V → R and a threshold t ∈ R t\in\mathbb{R} t ∈ R such that, for distinct u , v ∈ V u,v\in V u , v ∈ V , { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E if and only if wt ( u ) + wt ( v ) ≥ t \operatorname{wt}(u)+\operatorname{wt}(v)\ge t wt ( u ) + wt ( v ) ≥ t .
Equivalently [10 , 15 ] , G G G is a threshold graph if and only if it can be built from a single vertex v 0 v_0 v 0 by adding vertices v 1 , … , v N − 1 v_1,\ldots,v_{N-1} v 1 , … , v N − 1 one at a time, each new vertex being either isolated (adjacent to no earlier vertex) or dominating (adjacent to every earlier vertex).
Definition 3.2. The creation sequence of such a construction is the word s = s 1 s 2 ⋯ s N − 1 s=s_1s_2\cdots s_{N-1} s = s 1 s 2 ⋯ s N − 1 with s i = 1 s_i=1 s i = 1 if v i v_i v i is dominating and s i = 0 s_i=0 s i = 0 if v i v_i v i is isolated. The first vertex v 0 v_0 v 0 involves no choice and receives no symbol. Conversely, every binary word s s s of length N − 1 N-1 N − 1 determines a threshold graph G ( s ) G(s) G ( s ) on { v 0 , … , v N − 1 } \{v_0,\ldots,v_{N-1}\} { v 0 , … , v N − 1 } , in which, for i < j i<j i < j , v i v_i v i is adjacent to v j v_j v j if and only if s j = 1 s_j=1 s j = 1 .
Lemma 3.3 ([15 ] ). The map s ↦ G ( s ) s\mapsto G(s) s ↦ G ( s ) induces a bijection between binary words of length N − 1 N-1 N − 1 and isomorphism classes of threshold graphs on N N N vertices. In particular there are 2 N − 1 2^{N-1} 2 N − 1 threshold graphs on N N N vertices up to isomorphism.
We write s ( G ) s(G) s ( G ) for the creation sequence of a threshold graph G G G given by Lemma 3.3 .
Lemma 3.4. Let N ≥ 2 N\ge2 N ≥ 2 . A threshold graph G G G on N N N vertices has an isolated vertex if and only if s ( G ) s(G) s ( G ) ends in 0.
Proof. If s ( G ) s(G) s ( G ) ends in 0, the last vertex is adjacent to no earlier vertex and no vertex is added after it, so it is isolated in G G G . If s ( G ) s(G) s ( G ) ends in 1, the last vertex is adjacent to all other vertices, so no vertex is isolated.
From threshold graphs to partitions and numerical sets
Definition 3.5. Let G G G be a threshold graph whose creation sequence w = s ( G ) w=s(G) w = s ( G ) ends in 0. Read 1 w 1w 1 w (a leading 1 for v 0 v_0 v 0 , followed by w w w ) as a lattice path: an east step for each 1 and a north step for each 0. This path is the profile of a Young diagram, and we call the corresponding partition λ G \lambda_G λ G . Its rows correspond to the isolated vertices v i v_i v i (i ≥ 1 i\ge1 i ≥ 1 ), and the row of v i v_i v i has length equal to the number of vertices v j v_j v j with j < i j<i j < i that are v 0 v_0 v 0 or dominating. The numerical set of G G G is
S G = { 0 } ∪ { i ≥ 1 : v i is dominating } ∪ { N , N + 1 , … } . S_G=\{0\}\cup\{i\ge1:v_i\text{ is dominating}\}\cup\{N,N+1,\ldots\}. S G = { 0 } ∪ { i ≥ 1 : v i is dominating } ∪ { N , N + 1 , … } . Conversely, for a numerical set S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 with Frobenius number F F F , let G ( S ) G(S) G ( S ) be the threshold graph on v 0 , … , v F v_0,\ldots,v_F v 0 , … , v F in which v i v_i v i (1 ≤ i ≤ F 1\le i\le F 1 ≤ i ≤ F ) is dominating if i ∈ S i\in S i ∈ S and isolated if i ∉ S i\notin S i ∈ / S .
The partition λ G \lambda_G λ G is not the degree partition of G G G , which is the partition usually attached to a threshold graph [15 ] . It is the lattice-path reading of the creation sequence, and it is chosen so that S G S_G S G is the Keith–Nath set of $\lambda_G ({xref}Theorem 3.9). {xref}Figure 1` shows an example.
Figure 1. The threshold graph G ( S ) G(S) G ( S ) for S = ⟨ 4 , 5 , 6 ⟩ = { 0 , 4 , 5 , 6 , 8 , … } S=\langle4,5,6\rangle=\{0,4,5,6,8,\ldots\} S = ⟨ 4 , 5 , 6 ⟩ = { 0 , 4 , 5 , 6 , 8 , … } . Its creation sequence is s = 0001110 s=0001110 s = 0001110 : v 1 , v 2 , v 3 , v 7 v_1,v_2,v_3,v_7 v 1 , v 2 , v 3 , v 7 are isolated and v 4 , v 5 , v 6 v_4,v_5,v_6 v 4 , v 5 , v 6 are dominating. It has 4 + 5 + 6 = 15 4+5+6=15 4 + 5 + 6 = 15 edges, v 7 v_7 v 7 is an isolated vertex, and λ G = ( 4 , 1 , 1 , 1 ) \lambda_G=(4,1,1,1) λ G = ( 4 , 1 , 1 , 1 ) .
The creation sequence of a partition
A partition determines the creation sequence of a threshold graph. Most of our proofs are phrased in terms of partitions whose smallest part is 1, which are the only ones that can correspond to numerical semigroups, so we record this direction explicitly.
Definition 3.6. For a partition λ = ( n 1 ≥ n 2 ≥ ⋯ ≥ n k ) \lambda=(n_1\ge n_2\ge\cdots\ge n_k) λ = ( n 1 ≥ n 2 ≥ ⋯ ≥ n k ) define its creation sequence
C ( λ ) = 01 n k − 1 − n k 01 n k − 2 − n k − 1 0 ⋯ 01 n 1 − n 2 0. C(\lambda)=01^{n_{k-1}-n_k}01^{n_{k-2}-n_{k-1}}0\cdots01^{n_1-n_2}0. C ( λ ) = 0 1 n k − 1 − n k 0 1 n k − 2 − n k − 1 0 ⋯ 0 1 n 1 − n 2 0. This is a binary word with exactly k k k zeros and n 1 − n k n_1-n_k n 1 − n k ones, and it always ends in 0. For a binary word w = c 1 c 2 ⋯ c F w=c_1c_2\cdots c_F w = c 1 c 2 ⋯ c F ending in 0 put
S w = { 0 } ∪ { i : c i = 1 } ∪ { F + 1 , F + 2 , … } , S_w=\{0\}\cup\{i:c_i=1\}\cup\{F+1,F+2,\ldots\}, S w = { 0 } ∪ { i : c i = 1 } ∪ { F + 1 , F + 2 , … } , and write S λ = S C ( λ ) S_\lambda=S_{C(\lambda)} S λ = S C ( λ ) . Thus the letter at position i i i records whether i ∈ S λ i\in S_\lambda i ∈ S λ . In the language of Definition 3.2 , C ( λ ) C(\lambda) C ( λ ) is the creation sequence of the threshold graph G ( C ( λ ) ) G(C(\lambda)) G ( C ( λ )) : its vertex v i v_i v i is dominating exactly when i ∈ S λ i\in S_\lambda i ∈ S λ .
The word C ( λ ) C(\lambda) C ( λ ) only sees the differences between consecutive parts and the number of parts. Therefore, C ( λ ) = C ( λ + c ( 1 k ) ) C(\lambda)=C(\lambda+c(1^k)) C ( λ ) = C ( λ + c ( 1 k )) for every shift c c c that keeps the parts positive. For instance ( 2 , 1 ) (2,1) ( 2 , 1 ) , ( 4 , 3 ) (4,3) ( 4 , 3 ) and ( 5 , 4 ) (5,4) ( 5 , 4 ) all have creation sequence 010.
Lemma 3.7.
The map w ↦ S w w\mapsto S_w w ↦ S w is a bijection from binary words ending in 0 onto numerical sets different from N 0 \mathbb{N}_0 N 0 . The gaps of S w S_w S w are the positions of the zeros, so F ( S w ) = ∣ w ∣ F(S_w)=|w| F ( S w ) = ∣ w ∣ and g ( S w ) g(S_w) g ( S w ) is the number of zeros.
For a nonempty partition λ \lambda λ with smallest part n k n_k n k , put
w K N ( λ ) = 1 n k − 1 C ( λ ) . w^{KN}(\lambda)=1^{n_k-1}C(\lambda). w K N ( λ ) = 1 n k − 1 C ( λ ) . Then S K N ( λ ) = S w K N ( λ ) S^{KN}(\lambda)=S_{w^{KN}(\lambda)} S K N ( λ ) = S w K N ( λ ) . The map λ ↦ w K N ( λ ) \lambda\mapsto w^{KN}(\lambda) λ ↦ w K N ( λ ) is a bijection from the nonempty partitions onto the binary words ending in 0. It restricts to a bijection λ ↦ C ( λ ) \lambda\mapsto C(\lambda) λ ↦ C ( λ ) from partitions with smallest part 1 onto the words that begin and end with 0; for such λ \lambda λ , S λ = S K N ( λ ) S_\lambda=S^{KN}(\lambda) S λ = S K N ( λ ) .
For an arbitrary partition, S λ = S K N ( λ ^ ) S_\lambda=S^{KN}(\hat{\lambda}) S λ = S K N ( λ ^ ) with λ ^ = ( n 1 − n k + 1 , … , n k − 1 − n k + 1 , 1 ) \hat{\lambda}=(n_1-n_k+1,\ldots,n_{k-1}-n_k+1,1) λ ^ = ( n 1 − n k + 1 , … , n k − 1 − n k + 1 , 1 ) . If n k ≥ 2 n_k\ge2 n k ≥ 2 , then 1 ∈ S K N ( λ ) 1\in S^{KN}(\lambda) 1 ∈ S K N ( λ ) , and S K N ( λ ) S^{KN}(\lambda) S K N ( λ ) is not a numerical semigroup.
Proof. (1) A numerical set S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 is determined by its gap set, which is finite and nonempty with maximum F ( S ) F(S) F ( S ) . Recording membership of 1 , … , F ( S ) 1,\ldots,F(S) 1 , … , F ( S ) gives a word of length F ( S ) F(S) F ( S ) whose last letter is 0. This construction is inverse to w ↦ S w w\mapsto S_w w ↦ S w . The statements about gaps, F F F and g g g are immediate from the definition of S w S_w S w .
(2) Follow the Keith–Nath path of λ \lambda λ from the bottom-left corner. The bottom row has length n k n_k n k , so the path begins with n k n_k n k east steps; the first of them is the element 0. The path then takes one north step for each row. Between the north step of a row of length n i + 1 n_{i+1} n i + 1 and that of the next row up, of length n i n_i n i , it takes exactly n i − n i + 1 n_i-n_{i+1} n i − n i + 1 east steps. Reading the steps after the first one, with 1 for east and 0 for north, gives 1 n k − 1 1^{n_k-1} 1 n k − 1 followed by the letters of C ( λ ) C(\lambda) C ( λ ) , that is, the word w K N ( λ ) w^{KN}(\lambda) w K N ( λ ) . The last step is the north step of the top row, which is the gap F F F . Thus, S K N ( λ ) = S w K N ( λ ) S^{KN}(\lambda)=S_{w^{KN}(\lambda)} S K N ( λ ) = S w K N ( λ ) . Conversely, a word ending in 0 with k k k zeros can be written uniquely as 1 e 0 1 d k 0 ⋯ 1 d 1 0 1^e0\,1^{d_k}0\cdots1^{d_1}0 1 e 0 1 d k 0 ⋯ 1 d 1 0 with e , d i ≥ 0 e,d_i\ge0 e , d i ≥ 0 , and it equals w K N ( λ ) w^{KN}(\lambda) w K N ( λ ) for exactly one partition, namely the one with k k k parts, n k = e + 1 n_k=e+1 n k = e + 1 and n i − n i + 1 = d i n_i-n_{i+1}=d_i n i − n i + 1 = d i . The word begins with 0 exactly when e = 0 e=0 e = 0 , that is, n k = 1 n_k=1 n k = 1 , and then w K N ( λ ) = C ( λ ) w^{KN}(\lambda)=C(\lambda) w K N ( λ ) = C ( λ ) .
(3) The partitions λ \lambda λ and λ ^ \hat{\lambda} λ ^ have the same number of parts and the same differences between consecutive parts, so C ( λ ) = C ( λ ^ ) C(\lambda)=C(\hat{\lambda}) C ( λ ) = C ( λ ^ ) , and λ ^ \hat{\lambda} λ ^ has smallest part 1. If n k ≥ 2 n_k\ge2 n k ≥ 2 , the Keith–Nath path of λ \lambda λ begins with n k ≥ 2 n_k\ge2 n k ≥ 2 east steps, so 0 , 1 ∈ S K N ( λ ) 0,1\in S^{KN}(\lambda) 0 , 1 ∈ S K N ( λ ) . A numerical semigroup containing 1 is N 0 \mathbb{N}_0 N 0 , but S K N ( λ ) ≠ N 0 S^{KN}(\lambda)\ne\mathbb{N}_0 S K N ( λ ) = N 0 , since λ ≠ ∅ \lambda\ne\varnothing λ = ∅ . □ \square □
Proposition 3.8. Let λ = ( n 1 ≥ ⋯ ≥ n k ) \lambda=(n_1\ge\cdots\ge n_k) λ = ( n 1 ≥ ⋯ ≥ n k ) and let a = # { i : n i = n k } a=\#\{i:n_i=n_k\} a = # { i : n i = n k } be the number of copies of its smallest part. Then
F ( S λ ) = ∣ C ( λ ) ∣ = k + n 1 − n k = h ( 1 , 1 ) ( λ ^ ) , g ( S λ ) = k = ℓ ( λ ) , m ( S λ ) = a + 1. F(S_\lambda)=|C(\lambda)|=k+n_1-n_k=h_{(1,1)}(\hat{\lambda}),\qquad
g(S_\lambda)=k=\ell(\lambda),\qquad
m(S_\lambda)=a+1. F ( S λ ) = ∣ C ( λ ) ∣ = k + n 1 − n k = h ( 1 , 1 ) ( λ ^ ) , g ( S λ ) = k = ℓ ( λ ) , m ( S λ ) = a + 1. If λ \lambda λ has at least two distinct parts, then C ( λ ) C(\lambda) C ( λ ) begins with exactly a a a zeros followed by a 1. Every maximal block of zeros other than the first, say of length L L L , corresponds to a part value larger than n k n_k n k that occurs exactly L L L times, and every maximal block of ones corresponds to a difference n i − n i + 1 > 0 n_i-n_{i+1}>0 n i − n i + 1 > 0 .
Proof. The length and the number of zeros were computed in Definition 3.6 , and h ( 1 , 1 ) ( λ ^ ) = λ ^ 1 + k − 1 = n 1 − n k + k h_{(1,1)}(\hat{\lambda})=\hat{\lambda}_1+k-1=n_1-n_k+k h ( 1 , 1 ) ( λ ^ ) = λ ^ 1 + k − 1 = n 1 − n k + k . In C ( λ ) C(\lambda) C ( λ ) the letters between the i i i -th and ( i + 1 ) (i+1) ( i + 1 ) -st zeros (counting from the left) are 1 n k − i − n k − i + 1 1^{n_{k-i}-n_{k-i+1}} 1 n k − i − n k − i + 1 . The first a − 1 a-1 a − 1 of these differences vanish and the a a a -th does not. Therefore the word starts with 0 a 1 0^a1 0 a 1 , and its first 1 1 1 is at position a + 1 = m ( S λ ) a+1=m(S_\lambda) a + 1 = m ( S λ ) . More generally, a maximal run of L L L zeros after the first run means that L − 1 L-1 L − 1 consecutive differences vanish, with nonzero differences on both sides (or the end of the word). This happens exactly when some part value occurs L L L times, and that value exceeds n k n_k n k because a 1 1 1 precedes the run. A maximal run of ones is a single nonzero difference.
The correspondence and its dictionary
Theorem 3.9. Let N ≥ 2 N \ge2 N ≥ 2 . The maps
G ↦ s ( G ) ↦ λ G ↦ S G G \mapsto s(G) \mapsto\lambda_G \mapsto S_G G ↦ s ( G ) ↦ λ G ↦ S G restrict to bijections between the following four sets:
(a) threshold graphs on N N N vertices with at least one isolated vertex, up to isomorphism;
(b) binary words of length N − 1 N-1 N − 1 ending in 0 0 0 ;
(c) nonempty partitions with largest hook length h ( 1 , 1 ) = N − 1 h_{(1,1)}=N-1 h ( 1 , 1 ) = N − 1 ;
(d) numerical sets with Frobenius number N − 1 N-1 N − 1 .
Moreover s ( G ) = w K N ( λ G ) s(G)=w^{KN}(\lambda_G) s ( G ) = w K N ( λ G ) , S G = S s ( G ) = S K N ( λ G ) S_G=S_{s(G)}=S^{KN}(\lambda_G) S G = S s ( G ) = S K N ( λ G ) , and the inverse of G ↦ S G G\mapsto S_G G ↦ S G is S ↦ G ( S ) S\mapsto G(S) S ↦ G ( S ) . The smallest part of λ G \lambda_G λ G is 1 1 1 if and only if v 1 v_1 v 1 is isolated, that is, 1 ∉ S G 1\notin S_G 1 ∈ / S G , and in that case s ( G ) = C ( λ G ) s(G)=C(\lambda_G) s ( G ) = C ( λ G ) .
Proof. By Lemma 3.3 , G ↦ s ( G ) G\mapsto s(G) G ↦ s ( G ) is a bijection from threshold graphs on N N N vertices onto words of length N − 1 N-1 N − 1 , and by Lemma 3.4 the graphs with an isolated vertex correspond to the words ending in 0 0 0 , which establishes the bijection between (a) and (b).
By Lemma 3.7 -(2}, the Keith–Nath path of a nonempty partition λ \lambda λ is 1 w K N ( λ ) 1w^{KN}(\lambda) 1 w K N ( λ ) . By Definition 3.5 , the path of λ G \lambda_G λ G is 1 s ( G ) 1s(G) 1 s ( G ) . Therefore, w K N ( λ G ) = s ( G ) w^{KN}(\lambda_G)=s(G) w K N ( λ G ) = s ( G ) , and Lemma 3.7 -(2) shows that w ↦ λ w\mapsto\lambda w ↦ λ with w K N ( λ ) = w w^{KN}(\lambda)=w w K N ( λ ) = w is a bijection from words ending in 0 0 0 onto nonempty partitions. The path has λ 1 \lambda_1 λ 1 east steps and ℓ ( λ ) \ell(\lambda) ℓ ( λ ) north steps, so N = λ 1 + ℓ ( λ ) = h ( 1 , 1 ) ( λ ) + 1 N=\lambda_1+\ell(\lambda)=h_{(1,1)}(\lambda)+1 N = λ 1 + ℓ ( λ ) = h ( 1 , 1 ) ( λ ) + 1 . The statement about the smallest part is the last assertion of Lemma 3.7 -(2), which gives the bijection between (b) and (c).
By Lemma 3.7 -(1), w ↦ S w w\mapsto S_w w ↦ S w is a bijection onto numerical sets with F ( S w ) = ∣ w ∣ = N − 1 F(S_w)=|w|=N-1 F ( S w ) = ∣ w ∣ = N − 1 . By Definition 3.5 , S G = S s ( G ) S_G=S_{s(G)} S G = S s ( G ) , and S s ( G ) = S K N ( λ G ) S_{s(G)}=S^{KN}(\lambda_G) S s ( G ) = S K N ( λ G ) by Lemma 3.7 -(2). Finally, G ( S ) G(S) G ( S ) has creation sequence equal to the word of S S S , so S ↦ G ( S ) S\mapsto G(S) S ↦ G ( S ) inverts G ↦ S G G\mapsto S_G G ↦ S G , there we have the bijection between (c) and (d).
Proposition 3.10. 1. Every numerical semigroup S ≠ N 0 S\ne\mathbb{N}_0 S = N 0 has a creation sequence: there is a unique threshold graph G = G ( S ) G=G(S) G = G ( S ) with an isolated vertex such that S G = S S_G=S S G = S . Its creation sequence is s ( G ) = c 1 ⋯ c F ( S ) s(G)=c_1\cdots c_{F(S)} s ( G ) = c 1 ⋯ c F ( S ) , with c i = 1 c_i=1 c i = 1 if and only if i ∈ S i\in S i ∈ S .
The converse fails. For every N ≥ 3 N\ge3 N ≥ 3 there are threshold graphs on N N N vertices with an isolated vertex whose numerical set S G S_G S G is not a numerical semigroup, and for N ≥ 2 N\ge2 N ≥ 2 there are threshold graphs whose creation sequence ends in $1, w h i c h d o n o t d e t e r m i n e a n u m e r i c a l s e t w i t h F r o b e n i u s n u m b e r , which do not determine a numerical set with Frobenius number , w hi c h d o n o t d e t er min e an u m er i c a l se tw i t h F r o b e ni u s n u mb er N-1.
Proof. (1) This is the bijection between (d) and (a) of Theorem 3.9 , restricted to numerical semigroups.
(2) For N ≥ 3 N\ge3 N ≥ 3 , let s = 010 N − 3 s=010^{N-3} s = 01 0 N − 3 , that is, v 1 v_1 v 1 is isolated, v 2 v_2 v 2 is dominating and v 3 , … , v N − 1 v_3,\ldots,v_{N-1} v 3 , … , v N − 1 are isolated. Then S G = { 0 , 2 } ∪ [ N , ∞ ) S_G=\{0,2\}\cup[N,\infty) S G = { 0 , 2 } ∪ [ N , ∞ ) . If N ≥ 5 N\ge5 N ≥ 5 , then 2 + 2 = 4 ≤ N − 1 2+2=4\le N-1 2 + 2 = 4 ≤ N − 1 is a gap, so S G S_G S G is not a semigroup. For N = 3 N = 3 N = 3 and N = 4 N = 4 N = 4 use instead s = 10 s = 10 s = 10 and s = 100 s = 100 s = 100 , then 1 ∈ S G 1 \in S_G 1 ∈ S G , but S G ≠ N 0 S_G \ne\mathbb{N}_0 S G = N 0 , so S G S_G S G is not a semigroup. Finally, the graph with creation sequence 1 N − 1 1^{N-1} 1 N − 1 (the complete graph K N K_N K N ) has no isolated vertex, by Lemma 3.4 .
Thus creation sequences (equivalently, threshold graphs with an isolated vertex) are in bijection with numerical sets, and the numerical semigroups form a proper subclass. By Corollary 3.13, the proportion of threshold graphs that yield semigroups is the proportion of numerical sets with Frobenius number N − 1 N - 1 N − 1 that are semigroups. There are 2 N − 2 2^{N-2} 2 N − 2 numerical sets with Frobenius number N − 1 N - 1 N − 1 , but only of the order of 2 N / 2 2^{N/2} 2 N /2 numerical semigroups with that Frobenius number [3 ] , so this proportion tends to 0 as N → ∞ N \to\infty N → ∞ .
Example 3.11. Table 1 lists all 2 3 = 8 2^3 = 8 2 3 = 8 threshold graphs on N = 5 N = 5 N = 5 vertices that have an isolated vertex, that is, all creation sequences s = c 1 c 2 c 3 c 4 s = c_1c_2c_3c_4 s = c 1 c 2 c 3 c 4 with c 4 = 0 c_4 = 0 c 4 = 0 . In each case S G = { 0 } ∪ { i : c i = 1 } ∪ [ 5 , ∞ ) S_G = \{0\} \cup\{i : c_i = 1\} \cup[5,\infty) S G = { 0 } ∪ { i : c i = 1 } ∪ [ 5 , ∞ ) . Only two of the eight creation sequences give numerical semigroups: 0000, giving { 0 , 5 , 6 , … } = ⟨ 5 , 6 , 7 , 8 , 9 ⟩ \{0,5,6,\ldots\} = \langle5,6,7,8,9\rangle { 0 , 5 , 6 , … } = ⟨ 5 , 6 , 7 , 8 , 9 ⟩ , and 0010, giving { 0 , 3 , 5 , 6 , … } = ⟨ 3 , 5 , 7 ⟩ \{0,3,5,6,\ldots\} = \langle3,5,7\rangle { 0 , 3 , 5 , 6 , … } = ⟨ 3 , 5 , 7 ⟩ . For example, the creation sequence 0100 builds the threshold graph in which v 2 v_2 v 2 is adjacent to v 0 v_0 v 0 , v 1 v_1 v 1 and v 3 , v 4 v_3,v_4 v 3 , v 4 are isolated. Its partition is ( 2 , 2 , 1 ) (2,2,1) ( 2 , 2 , 1 ) and its numerical set { 0 , 2 , 5 , 6 , … } \{0,2,5,6,\ldots\} { 0 , 2 , 5 , 6 , … } is not closed under addition, because v 2 v_2 v 2 is dominating while v 2 + 2 = v 4 v_{2+2}=v_4 v 2 + 2 = v 4 is isolated.
Table 1. The eight threshold graphs on five vertices with an isolated vertex. Only two of their creation sequences give numerical semigroups.
Proposition 3.12. Let G G G be a threshold graph on N ≥ 2 N \ge2 N ≥ 2 vertices with an isolated vertex, and put S = S G S = S_G S = S G , λ = λ G \lambda= \lambda_G λ = λ G and g = g ( S ) g = g(S) g = g ( S ) . Then the following holds.
F ( S ) = N − 1 = h ( 1 , 1 ) ( λ ) F(S) = N - 1 = h_{(1,1)}(\lambda) F ( S ) = N − 1 = h ( 1 , 1 ) ( λ ) ;
g ( S ) g(S) g ( S ) is the number of isolated vertices v i v_i v i with i ≥ 1 i \ge1 i ≥ 1 (isolated at the moment they are added), and equals ℓ ( λ ) \ell(\lambda) ℓ ( λ ) ;
m ( S ) m(S) m ( S ) is the least i ≥ 1 i \ge1 i ≥ 1 such that v i v_i v i is dominating (m ( S ) = N m(S) = N m ( S ) = N if there is none), and equals 1 plus the number of parts of λ \lambda λ equal to 1;
the number of edges of G G G is ∑ x ∈ S , 0 < x < F ( S ) x \sum_{x \in S,\ 0 < x < F(S)} x ∑ x ∈ S , 0 < x < F ( S ) x ;
∣ λ ∣ |\lambda| ∣ λ ∣ is the number of non-adjacent pairs { v i , v j } \{v_i,v_j\} { v i , v j } with i < j i < j i < j such that v i v_i v i is v 0 v_0 v 0 or dominating (and v j v_j v j is isolated). Equivalently, ∣ λ ∣ = # { non-edges of G } − ( 2 2 ) |\lambda| = \#\{\text{non-edges of }G\} - \binom{2}{2} ∣ λ ∣ = # { non-edges of G } − ( 2 2 ) ;
S S S is a numerical semigroup if and only if, for all i , j ≥ 1 i,j \ge1 i , j ≥ 1 with i + j ≤ N − 1 i + j \le N - 1 i + j ≤ N − 1 , the vertex v i + j v_{i+j} v i + j is dominating whenever v i v_i v i and v j v_j v j are;
the complement G ‾ \overline{G} G is a threshold graph whose creation sequence is obtained from s ( G ) s(G) s ( G ) by interchanging 0 and 1.
Proof. (1)–(3) follow from Theorem 3.9 , Lemma 3.7 (1) and Proposition 3.8 , since the gaps of S S S in [ 1 , N − 1 ] [1,N-1] [ 1 , N − 1 ] are the indices of the isolated vertices and the elements are the indices of the dominating ones.
(4) Every edge { v i , v j } \{v_i,v_j\} { v i , v j } with i < j i<j i < j is created when v j v_j v j is added, and v j v_j v j is then dominating, so j ∈ S j\in S j ∈ S . A dominating vertex v x v_x v x creates exactly x x x edges, one to each of v 0 , … , v x − 1 v_0,\ldots,v_{x-1} v 0 , … , v x − 1 .
(5) A pair { v i , v j } \{v_i,v_j\} { v i , v j } with i < j i<j i < j is a non-edge exactly when v j v_j v j is isolated, that is, j j j is a gap. There are ( j 2 ) \binom{j}{2} ( 2 j ) such pairs in which v i v_i v i is also isolated (i ≥ 1 i\geq1 i ≥ 1 ). The remaining non-edges are counted, for each gap j j j , by the number of elements of S S S smaller than j j j , which is the length of the row of λ \lambda λ belonging to j j j (Definition 3.5 ). Summing over the gaps gives ∣ λ ∣ |\lambda| ∣ λ ∣ .
(6) This is closure under addition for sums of nonzero elements up to F ( S ) = N − 1 F(S)=N-1 F ( S ) = N − 1 . Sums involving 0 0 0 , or sums exceeding F ( S ) F(S) F ( S ) , lie in S S S automatically.
(7) For i < j i<j i < j , v i v_i v i and v j v_j v j are adjacent in G ‾ \overline{G} G exactly when s j = 0 s_j=0 s j = 0 . So G ‾ = G ( s ˉ ) \overline{G}=G(\bar{s}) G = G ( s ˉ ) , where s ˉ \bar{s} s ˉ is the complementary word.
Corollary 3.13. The number of threshold graphs on N N N vertices, up to isomorphism, that have an isolated vertex and whose numerical set is a numerical semigroup equals the number of numerical semigroups with Frobenius number N − 1 N-1 N − 1 .
Proof. This follows from Theorem 3.9 .
Remark 3.14. By Proposition 3.12 -(7), complementation of threshold graphs interchanges 0 0 0 and 1 1 1 in the creation sequence. It leaves the class (a) whenever s ( G ) s(G) s ( G ) ends in 0 0 0 , since then s ( G ‾ ) s(\overline{G}) s ( G ) ends in 1 1 1 . Conjugation of partitions corresponds instead to complementing and reversing the word (Lemma 6.1 ).
Definition 3.15. For a partition κ = ( κ 1 ≥ ⋯ ≥ κ r ) \kappa=(\kappa_1\geq\cdots\geq\kappa_r) κ = ( κ 1 ≥ ⋯ ≥ κ r ) let
w ( κ ) = 1 κ r 0 1 κ r − 1 − κ r 0 ⋯ 1 κ 1 − κ 2 0 , w(\kappa)=1^{\kappa_r}0\,1^{\kappa_{r-1}-\kappa_r}0\cdots1^{\kappa_1-\kappa_2}0, w ( κ ) = 1 κ r 0 1 κ r − 1 − κ r 0 ⋯ 1 κ 1 − κ 2 0 ,
a word of length κ 1 + r \kappa_1+r κ 1 + r whose positions we index by 0 , 1 , … , κ 1 + r − 1 0,1,\ldots,\kappa_1+r-1 0 , 1 , … , κ 1 + r − 1 . Let Σ ( κ ) ⊆ N 0 \Sigma(\kappa)\subseteq\mathbb{N}_0 Σ ( κ ) ⊆ N 0 be the set of positions of its ones together with all integers ≥ κ 1 + r \geq\kappa_1+r ≥ κ 1 + r . We put Σ ( ∅ ) = N 0 \Sigma(\varnothing)=\mathbb{N}_0 Σ ( ∅ ) = N 0 , and we treat negative integers as never lying in Σ ( κ ) \Sigma(\kappa) Σ ( κ ) .
Lemma 3.16. Let κ \kappa κ be a nonempty partition with r r r parts. Then the following holds.
Σ ( κ ) = S K N ( κ ) \Sigma(\kappa)=S^{KN}(\kappa) Σ ( κ ) = S K N ( κ ) . In particular 0 ∈ Σ ( κ ) 0\in\Sigma(\kappa) 0 ∈ Σ ( κ ) and [ κ 1 + r , ∞ ) ⊆ Σ ( κ ) [\kappa_1+r,\infty)\subseteq\Sigma(\kappa) [ κ 1 + r , ∞ ) ⊆ Σ ( κ ) .
The zeros of w ( κ ) w(\kappa) w ( κ ) are exactly at the positions z t = κ t + r − t z_t=\kappa_t+r-t z t = κ t + r − t for t = 1 , … , r t=1,\ldots,r t = 1 , … , r , and z 1 > z 2 > ⋯ > z r z_1>z_2>\cdots>z_r z 1 > z 2 > ⋯ > z r .
Σ ( κ ) + Σ ( κ ) ⊇ Σ ( κ ) \Sigma(\kappa)+\Sigma(\kappa)\supseteq\Sigma(\kappa) Σ ( κ ) + Σ ( κ ) ⊇ Σ ( κ ) ; in particular every integer ≥ κ 1 + r \geq\kappa_1+r ≥ κ 1 + r lies in Σ ( κ ) + Σ ( κ ) \Sigma(\kappa)+\Sigma(\kappa) Σ ( κ ) + Σ ( κ ) .
Proof. (1) Reading w ( κ ) w(\kappa) w ( κ ) from position 0 is exactly the Keith–Nath path of κ \kappa κ (east for 1, north for 0), which starts with κ r ≥ 1 \kappa_r\geq1 κ r ≥ 1 east steps, so position 0 carries a 1.
(2) The zero that ends the block 1 κ t − κ t + 1 1^{\kappa_t-\kappa_{t+1}} 1 κ t − κ t + 1 is preceded by κ t \kappa_t κ t ones in total (the lengths of the blocks telescope) and by r − t r-t r − t zeros. Its position is therefore κ t + r − t \kappa_t+r-t κ t + r − t , and these positions strictly decrease in t t t because κ t ≥ κ t + 1 \kappa_t\geq\kappa_{t+1} κ t ≥ κ t + 1 .
(3) This follows from 0 ∈ Σ ( κ ) 0\in\Sigma(\kappa) 0 ∈ Σ ( κ ) and (1).
Structural criteria
Throughout this section w w w is a binary word ending in 0, and S = S w S=S_w S = S w .
Theorem 4.1. If the first 1 of w w w is at position m m m and ∣ w ∣ < 2 m |w|<2m ∣ w ∣ < 2 m , then S w S_w S w is a numerical semigroup. In partition language: if λ \lambda λ has smallest part repeated a a a times and κ + n 1 − n k < 2 a + 2 \kappa+n_1-n_k<2a+2 κ + n 1 − n k < 2 a + 2 , then S λ S_\lambda S λ is a numerical semigroup.
Proof. Every nonzero element of S S S is at least m m m , so the sum of two nonzero elements is at least 2 m > ∣ w ∣ = F ( S ) 2m > |w| = F(S) 2 m > ∣ w ∣ = F ( S ) and therefore lies in S S S . Sums involving 0 0 0 are trivially in S S S . The second statement is the first combined with Proposition 3.8.
Theorem 4.2. Let S w S_w S w be a numerical semigroup with multiplicity m m m , so that w = 0 m − 1 1 ⋯ w = 0^{m-1}1\cdots w = 0 m − 1 1 ⋯ . Then the following holds.
every maximal block of ones in w w w has length at most m − 1 m-1 m − 1 ; and
every maximal block of zeros in w w w other than the first has length at most m − 1 m-1 m − 1 .
Proof. (1) Let the ones occupy the positions u , u + 1 , … , u + L − 1 u, u+1, \ldots, u+L-1 u , u + 1 , … , u + L − 1 with L ≥ m L \ge m L ≥ m . The position u + L u+L u + L carries a 0 0 0 : the block is maximal, and it cannot end the word because w w w ends in 0 0 0 . Every integer y ≥ u y \ge u y ≥ u can be written as y = u + i + q m y = u+i+qm y = u + i + q m with 0 ≤ i ≤ m − 1 0 \le i \le m-1 0 ≤ i ≤ m − 1 and q ≥ 0 q \ge0 q ≥ 0 . Since u + i ∈ S u+i \in S u + i ∈ S and m ∈ S m \in S m ∈ S , closure gives y ∈ S y \in S y ∈ S . In particular u + L ∈ S u+L \in S u + L ∈ S , a contradiction.
(2) Let the zeros occupy the positions u , … , u + L − 1 u, \ldots, u+L-1 u , … , u + L − 1 with L ≥ m L \ge m L ≥ m , and suppose this block is not the first one. Then position u − 1 u-1 u − 1 carries a 1 1 1 , and u − 1 ≥ m u-1 \ge m u − 1 ≥ m because the first 1 1 1 is at m m m . Now ( u − 1 ) + m ∈ [ u , u + m − 1 ] ⊆ [ u , u + L − 1 ] (u-1)+m \in[u,u+m-1] \subseteq[u,u+L-1] ( u − 1 ) + m ∈ [ u , u + m − 1 ] ⊆ [ u , u + L − 1 ] is a gap, but it is the sum of two elements of S S S , a contradiction.
Corollary 4.3. Let λ = ( n 1 ≥ ⋯ ≥ n k ) \lambda= (n_1 \ge\cdots\ge n_k) λ = ( n 1 ≥ ⋯ ≥ n k ) , and let a a a be the number of copies of its smallest part. If S λ S_\lambda S λ is a numerical semigroup, then the following holds.
consecutive distinct parts differ by at most a a a : n i − n i + 1 ≤ a n_i-n_{i+1} \le a n i − n i + 1 ≤ a for all i i i ; and
no part value occurs more often than the smallest part: every part value occurs at most a a a times.
In particular (long first block): if the next part value above n k n_k n k exceeds n k n_k n k by at least a + 1 a+1 a + 1 , then S λ S_\lambda S λ is not a numerical semigroup.
Proof. By Proposition 3.8, m ( S λ ) = a + 1 m(S_\lambda) = a+1 m ( S λ ) = a + 1 , the blocks of ones are the nonzero differences, and the non-initial blocks of zeros are the multiplicities of the part values above n k n_k n k . Apply Theorem 4.2.
Remark 4.4. Corollary 4.3-(1) is the partition form of the observation in [5 Section 2.3] that “the gap between two parts is no larger than m λ m_\lambda m λ ”.
Theorem 4.5. Suppose the smallest part of λ \lambda λ occurs exactly once, that is, a = 1 a=1 a = 1 , and k ≥ 2 k \ge2 k ≥ 2 . Then S λ S_\lambda S λ is a numerical semigroup if and only if C ( λ ) = ( 01 ) k − 1 0 C(\lambda) = (01)^{k-1}0 C ( λ ) = ( 01 ) k − 1 0 , that is, if and only if the parts of λ \lambda λ are distinct consecutive integers λ = ( c + k − 1 , c + k − 2 , … , c ) \lambda= (c+k-1,c+k-2,\ldots,c) λ = ( c + k − 1 , c + k − 2 , … , c ) . In this case S λ = ⟨ 2 , 2 k + 1 ⟩ S_\lambda= \langle2,2k+1\rangle S λ = ⟨ 2 , 2 k + 1 ⟩ .
Proof. If C ( λ ) = ( 01 ) k − 1 0 C(\lambda) = (01)^{k-1}0 C ( λ ) = ( 01 ) k − 1 0 , the ones sit at the even positions 2 , 4 , … , 2 k − 2 2,4,\ldots,2k-2 2 , 4 , … , 2 k − 2 and the zeros at the odd positions 1 , 3 , … , 2 k − 1 1,3,\ldots,2k-1 1 , 3 , … , 2 k − 1 . Thus S λ = { 0 , 2 , 4 , … , 2 k − 2 } ∪ [ 2 k , ∞ ) S_\lambda= \{0,2,4,\ldots,2k-2\} \cup[2k,\infty) S λ = { 0 , 2 , 4 , … , 2 k − 2 } ∪ [ 2 k , ∞ ) , which consists of all even numbers and all odd numbers ≥ 2 k + 1 \ge2k+1 ≥ 2 k + 1 ; this is ⟨ 2 , 2 k + 1 ⟩ \langle2,2k+1\rangle ⟨ 2 , 2 k + 1 ⟩ .
Conversely, let S λ S_\lambda S λ be a semigroup. Its multiplicity is a + 1 = 2 a+1=2 a + 1 = 2 , so by Theorem 4.2 every block of ones and every non-initial block of zeros has length 1. The first block of zeros has length a = 1 a=1 a = 1 . Thus w w w alternates, w = ( 01 ) j 0 w=(01)^j0 w = ( 01 ) j 0 , and the number of zeros gives j = k − 1 j=k-1 j = k − 1 . Finally, w = ( 01 ) k − 1 0 w=(01)^{k-1}0 w = ( 01 ) k − 1 0 means that all differences equal 1 and no part repeats.
Theorem 4.6. If λ = ( c k ) \lambda=(c^k) λ = ( c k ) , then C ( λ ) = 0 k C(\lambda)=0^k C ( λ ) = 0 k and S λ = { 0 } ∪ [ k + 1 , ∞ ) S_\lambda=\{0\}\cup[k+1,\infty) S λ = { 0 } ∪ [ k + 1 , ∞ ) is a numerical semigroup.
Proof. All differences vanish, so C ( λ ) = 0 k C(\lambda)=0^k C ( λ ) = 0 k . The nonzero elements of S λ S_\lambda S λ are at least k + 1 k+1 k + 1 , so the sum of two of them is at least 2 k + 2 > k = F ( S λ ) 2k+2>k=F(S_\lambda) 2 k + 2 > k = F ( S λ ) .
Theorem 4.7. Let λ = ( A p , B q ) \lambda=(A^p,B^q) λ = ( A p , B q ) with A > B ≥ 1 A>B\ge1 A > B ≥ 1 , p , q ≥ 1 p,q\ge1 p , q ≥ 1 , and put d = A − B d=A-B d = A − B . Then S λ S_\lambda S λ is a numerical semigroup if and only if
d + p ≤ q + 1. d+p \le q+1. d + p ≤ q + 1.
Proof. Here C ( λ ) = 0 q 1 d 0 p C(\lambda)=0^{q}1^{d}0^{p} C ( λ ) = 0 q 1 d 0 p , so m = q + 1 m=q+1 m = q + 1 , the elements in ( 0 , F ] (0,F] ( 0 , F ] are q + 1 , … , q + d q+1,\ldots,q+d q + 1 , … , q + d , the gaps are 1 , … , q 1,\ldots,q 1 , … , q and q + d + 1 , … , q + d + p q+d+1,\ldots,q+d+p q + d + 1 , … , q + d + p , and F = q + d + p F=q+d+p F = q + d + p . If d + p ≤ q + 1 d+p\le q+1 d + p ≤ q + 1 , then F ≤ 2 q + 1 < 2 m F\le2q+1<2m F ≤ 2 q + 1 < 2 m and Theorem 4.1 applies. Suppose instead that d + p ≥ q + 2 d+p\ge q+2 d + p ≥ q + 2 . If d ≥ q + 1 d\ge q+1 d ≥ q + 1 , then S λ S_{\lambda} S λ is not a semigroup by Theorem 4.2 -(1). If d ≤ q d\le q d ≤ q , then 2 m = 2 q + 2 2m=2q+2 2 m = 2 q + 2 satisfies q + d + 1 ≤ 2 q + 2 q+d+1\le2q+2 q + d + 1 ≤ 2 q + 2 (because d ≤ q + 1 d\le q+1 d ≤ q + 1 ) and 2 q + 2 ≤ q + d + p = F 2q+2\le q+d+p=F 2 q + 2 ≤ q + d + p = F (because d + p ≥ q + 2 d+p\ge q+2 d + p ≥ q + 2 ). So 2 m 2m 2 m is a gap while m ∈ S λ m\in S_{\lambda} m ∈ S λ , and S λ S_{\lambda} S λ is not a semigroup.
Corollary 4.8. Let λ = ( n 1 , n 2 k − 1 ) \lambda=(n_{1},n_{2}^{k-1}) λ = ( n 1 , n 2 k − 1 ) with n 1 > n 2 n_{1}>n_{2} n 1 > n 2 and d = n 1 − n 2 d=n_{1}-n_{2} d = n 1 − n 2 . Then S λ S_{\lambda} S λ is a numerical semigroup if and only if d ≤ k − 1 d\le k-1 d ≤ k − 1 . In particular ( n , 1 j ) (n,1^{j}) ( n , 1 j ) corresponds to a numerical semigroup if and only if j ≥ n − 1 j\ge n-1 j ≥ n − 1 , and PF ( n , n ) = ⌈ n / 2 ⌉ \operatorname{PF}(n,n)=\lceil n/2\rceil PF ( n , n ) = ⌈ n /2 ⌉ [5 Theorem 6] .
Proof. Take p = 1 p=1 p = 1 and q = k − 1 q=k-1 q = k − 1 in Theorem 4.7 . The partitions of n n n with largest hook n n n are exactly the hooks ( n − j , 1 j ) (n-j,1^{j}) ( n − j , 1 j ) with 0 ≤ j ≤ n − 1 0\le j\le n-1 0 ≤ j ≤ n − 1 . For 1 ≤ j ≤ n − 2 1\le j\le n-2 1 ≤ j ≤ n − 2 , Theorem 4.7 with d = n − j − 1 d=n-j-1 d = n − j − 1 , p = 1 p=1 p = 1 , q = j q=j q = j shows that ( n − j , 1 j ) (n-j,1^{j}) ( n − j , 1 j ) corresponds to a semigroup if and only if n − j ≤ j + 1 n-j\le j+1 n − j ≤ j + 1 , that is, j ≥ ⌊ n / 2 ⌋ j\ge\lfloor n/2\rfloor j ≥ ⌊ n /2 ⌋ . For j = n − 1 j=n-1 j = n − 1 , ( 1 n ) (1^{n}) ( 1 n ) corresponds to a semigroup (Theorem 4.6 ). For j = 0 j=0 j = 0 and n ≥ 2 n\ge2 n ≥ 2 , ( n ) (n) ( n ) has no part 1. In all cases the condition is j ≥ ⌊ n / 2 ⌋ j\ge\lfloor n/2\rfloor j ≥ ⌊ n /2 ⌋ , which holds for n − ⌊ n / 2 ⌋ = ⌈ n / 2 ⌉ n-\lfloor n/2\rfloor=\lceil n/2\rceil n − ⌊ n /2 ⌋ = ⌈ n /2 ⌉ values of j j j .
The following criterion decides every creation sequence. It is Kunz’s description of numerical semigroups of fixed multiplicity [14 , 16 ] , restated in the language of words.
Theorem 4.9. Let w = c 1 ⋯ c F w=c_{1}\cdots c_{F} w = c 1 ⋯ c F end in 0 and contain at least one 1, let m m m be the position of its first 1, and set c i = 1 c_{i}=1 c i = 1 for i > F i>F i > F . Say that position i i i lies in column i m o d m i\bmod m i mod m . Then S w S_{w} S w is a numerical semigroup if and only if
(i) c i = 1 c_{i}=1 c i = 1 implies c i + m = 1 c_{i+m}=1 c i + m = 1 for every i ≥ 1 i\ge1 i ≥ 1 ; equivalently, column 0 contains no zero and each column r ∈ { 1 , … , m − 1 } r\in\{1,\ldots,m-1\} r ∈ { 1 , … , m − 1 } reads 0 ⋯ 01 ⋯ 1 0\cdots01\cdots1 0 ⋯ 01 ⋯ 1 from top to bottom; and
(ii) the numbers k r k_{r} k r of zeros in column r r r satisfy
k i + k j ≥ k i + j ( 1 ≤ i ≤ j , i + j < m ) , k_{i}+k_{j}\ge k_{i+j}\qquad(1\le i\le j,\ i+j<m), k i + k j ≥ k i + j ( 1 ≤ i ≤ j , i + j < m ) , k i + k j + 1 ≥ k i + j − m ( 1 ≤ i ≤ j ≤ m − 1 , i + j > m ) . k_{i}+k_{j}+1\ge k_{i+j-m}\qquad(1\le i\le j\le m-1,\ i+j>m). k i + k j + 1 ≥ k i + j − m ( 1 ≤ i ≤ j ≤ m − 1 , i + j > m ) . In that case g ( S w ) = ∑ r k r g(S_{w})=\sum_{r}k_{r} g ( S w ) = ∑ r k r and F ( S w ) = max r ( k r m + r ) − m F(S_{w})=\max_{r}(k_{r}m+r)-m F ( S w ) = max r ( k r m + r ) − m .
Proof. Put w 0 = 0 w_{0}=0 w 0 = 0 and, for 1 ≤ r ≤ m − 1 1\le r\le m-1 1 ≤ r ≤ m − 1 , w r = k r m + r w_{r}=k_{r}m+r w r = k r m + r . Assume that S = S w S=S_{w} S = S w is a semigroup. Since m ∈ S m\in S m ∈ S , x ∈ S x\in S x ∈ S implies x + m ∈ S x+m\in S x + m ∈ S , which is (i). Consequently the column r r r consists of k r k_{r} k r zeros followed by ones, so the least element of S S S congruent to r r r modulo m m m is w r w_{r} w r , and x ∈ S x\in S x ∈ S if and only if x ≥ w x m o d m x\ge w_{x\bmod m} x ≥ w x mod m . For i , j ≥ 1 i,j\ge1 i , j ≥ 1 , the element w i + w j ∈ S w_{i}+w_{j}\in S w i + w j ∈ S is congruent to i + j i+j i + j , so w i + w j ≥ w ( i + j ) m o d m w_{i}+w_{j}\ge w_{(i+j)\bmod m} w i + w j ≥ w ( i + j ) mod m . For i + j < m i+j<m i + j < m this reads ( k i + k j ) m + i + j ≥ k i + j m + i + j (k_{i}+k_{j})m+i+j\ge k_{i+j}m+i+j ( k i + k j ) m + i + j ≥ k i + j m + i + j , and for i + j > m i+j>m i + j > m it reads ( k i + k j + 1 ) m + ( i + j − m ) ≥ k i + j − m m + ( i + j − m ) (k_{i}+k_{j}+1)m+(i+j-m)\ge k_{i+j-m}m+(i+j-m) ( k i + k j + 1 ) m + ( i + j − m ) ≥ k i + j − m m + ( i + j − m ) . This is (ii).
Conversely, assume (i) and (ii). By (i), x ∈ S x\in S x ∈ S if and only if x ≥ w x m o d m x\ge w_{x\bmod m} x ≥ w x mod m . Let x , y ∈ S x,y\in S x , y ∈ S with residues i , j i,j i , j . If i = 0 i=0 i = 0 , then x x x is a multiple of m m m and x + y ≥ y ≥ w j x+y\ge y\ge w_{j} x + y ≥ y ≥ w j , so x + y ∈ S x+y\in S x + y ∈ S ; similarly if j = 0 j=0 j = 0 or i + j = m i+j=m i + j = m (then w 0 = 0 w_{0}=0 w 0 = 0 ). Otherwise (ii) gives x + y ≥ w i + w j ≥ w ( i + j ) m o d m x+y\ge w_{i}+w_{j}\ge w_{(i+j)\bmod m} x + y ≥ w i + w j ≥ w ( i + j ) mod m , so x + y ∈ S x+y\in S x + y ∈ S .
Finally, the gaps are the k r k_{r} k r zeros of each column, and the largest gap is max r ( w r − m ) \max_{r}(w_{r}-m) max r ( w r − m ) .
Corollary 4.10. Let g ≥ 1 g\ge1 g ≥ 1 . Then the following holds.
Exactly one partition with g g g parts and exactly one part equal to 1 corresponds to a numerical semigroup, namely the staircase ( g , g − 1 , … , 1 ) (g,g-1,\ldots,1) ( g , g − 1 , … , 1 ) , with S = ⟨ 2 , 2 g + 1 ⟩ S=\langle2,2g+1\rangle S = ⟨ 2 , 2 g + 1 ⟩ .
For g ≥ 2 g\ge2 g ≥ 2 , exactly ⌊ g / 3 ⌋ + 1 \lfloor g/3\rfloor+1 ⌊ g /3 ⌋ + 1 partitions with g g g parts and exactly two parts equal to 1 correspond to numerical semigroups. They are the partitions with C ( λ ) C(\lambda) C ( λ ) having k 1 k_{1} k 1 zeros in column 1 and k 2 = g − k 1 k_{2}=g-k_{1} k 2 = g − k 1 zeros in column 2 (modulo 3), where g / 3 ≤ k 1 ≤ ( 2 g + 1 ) / 3 g/3\le k_{1}\le(2g+1)/3 g /3 ≤ k 1 ≤ ( 2 g + 1 ) /3 ; the corresponding semigroup is ⟨ 3 , 3 k 1 + 1 , 3 k 2 + 2 ⟩ \langle3,3k_{1}+1,3k_{2}+2\rangle ⟨ 3 , 3 k 1 + 1 , 3 k 2 + 2 ⟩ .
Proof. (1) This is Theorem 4.5 with smallest part 1.
(2) Here m = 3 m=3 m = 3 and the positions 1, 2 are gaps, so k 1 , k 2 ≥ 1 k_1,k_2\ge1 k 1 , k 2 ≥ 1 . The only instances of (ii) are ( i , j ) = ( 1 , 1 ) (i,j)=(1,1) ( i , j ) = ( 1 , 1 ) , giving 2 k 1 ≥ k 2 2k_1\ge k_2 2 k 1 ≥ k 2 , and ( i , j ) = ( 2 , 2 ) (i,j)=(2,2) ( i , j ) = ( 2 , 2 ) , giving 2 k 2 + 1 ≥ k 1 2k_2+1\ge k_1 2 k 2 + 1 ≥ k 1 . With k 2 = g − k 1 k_2=g-k_1 k 2 = g − k 1 these become k 1 ≥ g / 3 k_1\ge g/3 k 1 ≥ g /3 and k 1 ≤ ( 2 g + 1 ) / 3 k_1\le(2g+1)/3 k 1 ≤ ( 2 g + 1 ) /3 , and they also force k 1 , k 2 ≥ 1 k_1,k_2\ge1 k 1 , k 2 ≥ 1 when g ≥ 2 g\ge2 g ≥ 2 . The number of integers k 1 k_1 k 1 in [ g / 3 , ( 2 g + 1 ) / 3 ] [g/3,(2g+1)/3] [ g /3 , ( 2 g + 1 ) /3 ] is ⌊ ( 2 g + 1 ) / 3 ⌋ − ⌈ g / 3 ⌉ + 1 \lfloor(2g+1)/3\rfloor-\lceil g/3\rceil+1 ⌊( 2 g + 1 ) /3 ⌋ − ⌈ g /3 ⌉ + 1 . Checking the three residues g = 3 q , 3 q + 1 , 3 q + 2 g=3q,3q+1,3q+2 g = 3 q , 3 q + 1 , 3 q + 2 , this equals q + 1 = ⌊ g / 3 ⌋ + 1 q+1=\lfloor g/3\rfloor+1 q + 1 = ⌊ g /3 ⌋ + 1 in each case. By Theorem 4.9 , each such pair ( k 1 , k 2 ) (k_1,k_2) ( k 1 , k 2 ) gives exactly one semigroup, whose Apéry elements are 3 , 3 k 1 + 1 , 3 k 2 + 2 3,3k_1+1,3k_2+2 3 , 3 k 1 + 1 , 3 k 2 + 2 .
Remark 4.11. Theorem 4.9 shows that no finite list of equality patterns can classify all partitions: every infinite pattern family contains both semigroups and non-semigroups, and a pattern only determines which columns are compared. The number of partitions with g g g parts corresponding to numerical semigroups is the number n g n_g n g of numerical semigroups of genus g g g , which grows like C φ g C\varphi^g C φ g with φ \varphi φ the golden ratio [23 ] .
Classification by equality patterns
In this section we apply results of § 4 to partitions described by their pattern of equalities and strict inequalities among the parts. We first record the consequences for partitions with a unique smallest part, then treat the pattern n 1 > n 2 > n 3 = n 4 n_1>n_2>n_3=n_4 n 1 > n 2 > n 3 = n 4 , and finally determine, for every partition with at most four parts, exactly when S λ S_\lambda S λ is a numerical semigroup (Theorem 5.3 and Table 2 ).
Corollary 5.1. Let k ≥ 2 k\ge2 k ≥ 2 . Then the following holds.
Every partition into distinct consecutive integers gives a numerical semigroup; for example ( n , n − 1 ) (n,n-1) ( n , n − 1 ) , the staircase ( k , k − 1 , … , 1 ) (k,k-1,\ldots,1) ( k , k − 1 , … , 1 ) and ( 4 , 3 , 2 , 1 ) (4,3,2,1) ( 4 , 3 , 2 , 1 ) .
If n 1 > n 2 > ⋯ > n k n_1>n_2>\cdots>n_k n 1 > n 2 > ⋯ > n k and some n i − n i + 1 ≥ 2 n_i-n_{i+1}\ge2 n i − n i + 1 ≥ 2 , then S λ S_\lambda S λ is not a semigroup. In particular ( n , j ) (n,j) ( n , j ) with 1 ≤ j ≤ n − 2 1\le j\le n-2 1 ≤ j ≤ n − 2 never gives a semigroup.
If the smallest part is unique and some part is repeated, then S λ S_\lambda S λ is not a semigroup. This covers the patterns n 1 = n 2 > ⋯ > n k n_1=n_2>\cdots>n_k n 1 = n 2 > ⋯ > n k (with k ≥ 3 ) ; k\ge3); k ≥ 3 ) ; n_1>\cdots>n_r=n_{r+1}>\cdots>n_k$ with r + 1 < k r+1<k r + 1 < k ; and n 1 = ⋯ = n k − 1 > n k n_1=\cdots=n_{k-1}>n_k n 1 = ⋯ = n k − 1 > n k with k ≥ 3 k\ge3 k ≥ 3 .
Proof. In each case the smallest part is unique, so Theorem 4.5 applies. In (1) the parts are distinct consecutive integers. In (2) and (3) they are not: in (2) some difference is at least 2, and in (3) some part is repeated.
Proposition 5.2. Let n 1 > n 2 > n 3 = n 4 n_1>n_2>n_3=n_4 n 1 > n 2 > n 3 = n 4 , x = n 2 − n 3 x=n_2-n_3 x = n 2 − n 3 and y = n 1 − n 2 y=n_1-n_2 y = n 1 − n 2 . Then S λ S_\lambda S λ is a semigroup if and only if ( x , y ) = ( 1 , 2 ) (x,y)=(1,2) ( x , y ) = ( 1 , 2 ) , in which case S λ = ⟨ 3 , 5 ⟩ S_\lambda=\langle3,5\rangle S λ = ⟨ 3 , 5 ⟩ .
Proof. Here C ( λ ) = 0 2 1 x 0 1 y 0 C(\lambda)=0^{2}1x0^{1}y0 C ( λ ) = 0 2 1 x 0 1 y 0 and m = 3 m=3 m = 3 . So 3 , … , x + 2 ∈ S λ 3,\ldots,x+2\in S_\lambda 3 , … , x + 2 ∈ S λ , x + 3 x+3 x + 3 is a gap, x + 4 , … , x + y + 3 ∈ S λ x+4,\ldots,x+y+3\in S_\lambda x + 4 , … , x + y + 3 ∈ S λ , and F = x + y + 4 F=x+y+4 F = x + y + 4 . If x ≥ 3 x\ge3 x ≥ 3 or y ≥ 3 y\ge3 y ≥ 3 , Theorem 4.2 -(1) applies. The remaining cases are x , y ∈ { 1 , 2 } x,y\in\{1,2\} x , y ∈ { 1 , 2 } which are listed as follows:
(i) ( x , y ) = ( 1 , 1 ) (x,y)=(1,1) ( x , y ) = ( 1 , 1 ) : S λ = { 0 , 3 , 5 , 7 , … } S_\lambda=\{0,3,5,7,\ldots\} S λ = { 0 , 3 , 5 , 7 , … } , and 3 + 3 = 6 3+3=6 3 + 3 = 6 is a gap.
(ii) ( x , y ) = ( 2 , 1 ) (x,y)=(2,1) ( x , y ) = ( 2 , 1 ) : S λ = { 0 , 3 , 4 , 6 , 8 , … } S_\lambda=\{0,3,4,6,8,\ldots\} S λ = { 0 , 3 , 4 , 6 , 8 , … } , and 3 + 4 = 7 3+4=7 3 + 4 = 7 is a gap.
(iii) ( x , y ) = ( 2 , 2 ) (x,y)=(2,2) ( x , y ) = ( 2 , 2 ) : S λ = { 0 , 3 , 4 , 6 , 7 , 9 , … } S_\lambda=\{0,3,4,6,7,9,\ldots\} S λ = { 0 , 3 , 4 , 6 , 7 , 9 , … } , and 4 + 4 = 8 4+4=8 4 + 4 = 8 is a gap.
(iv) ( x , y ) = ( 1 , 2 ) (x,y)=(1,2) ( x , y ) = ( 1 , 2 ) : S λ = { 0 , 3 , 5 , 6 , 8 , 9 , … } = ⟨ 3 , 5 ⟩ S_\lambda=\{0,3,5,6,8,9,\ldots\}=\langle3,5\rangle S λ = { 0 , 3 , 5 , 6 , 8 , 9 , … } = ⟨ 3 , 5 ⟩ .
Theorem 5.3. For partitions with at most four parts, S λ S_\lambda S λ is a numerical semigroup exactly in the cases listed in Table 2 , where d i = n i − n i + 1 d_i=n_i-n_{i+1} d i = n i − n i + 1 .
Proof. We go through the rows of Table 2 .
(i) All parts equal: Theorem 4.6 .
Unique smallest part (the patterns n 1 > n 2 n_1 > n_2 n 1 > n 2 , n 1 = n 2 > n 3 n_1 = n_2 > n_3 n 1 = n 2 > n 3 , n 1 > n 2 > n 3 n_1 > n_2 > n_3 n 1 > n 2 > n 3 , n 1 = n 2 = n 3 > n 4 n_1 = n_2 = n_3 > n_4 n 1 = n 2 = n 3 > n 4 , n 1 = n 2 > n 3 > n 4 n_1 = n_2 > n_3 > n_4 n 1 = n 2 > n 3 > n 4 , n 1 > n 2 = n 3 > n 4 n_1 > n_2 = n_3 > n_4 n 1 > n 2 = n 3 > n 4 , n 1 > n 2 > n 3 > n 4 n_1 > n_2 > n_3 > n_4 n 1 > n 2 > n 3 > n 4 ): Theorem 4.5 . A semigroup occurs exactly when the parts are distinct and consecutive, which is possible only in the strictly decreasing patterns.
(ii) Two part sizes (the patterns n 1 > n 2 = n 3 n_1 > n_2 = n_3 n 1 > n 2 = n 3 , n 1 > n 2 = n 3 = n 4 n_1 > n_2 = n_3 = n_4 n 1 > n 2 = n 3 = n 4 , n 1 = n 2 > n 3 = n 4 n_1 = n_2 > n_3 = n_4 n 1 = n 2 > n 3 = n 4 ): Theorem 4.7 , with ( p , q ) = ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 2 ) (p,q) = (1,2),(1,3),(2,2) ( p , q ) = ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 2 ) respectively, giving d 1 ≤ 2 d_1 \le2 d 1 ≤ 2 , d 1 ≤ 3 d_1 \le3 d 1 ≤ 3 and d 2 ≤ 1 d_2 \le1 d 2 ≤ 1 .
(iii) The pattern n 1 > n 2 > n 3 = n 4 n_1 > n_2 > n_3 = n_4 n 1 > n 2 > n 3 = n 4 : Proposition 5.2 .
Example 5.4.
( 4 , 3 ) (4,3) ( 4 , 3 ) : C = 010 C = 010 C = 010 , S = { 0 , 2 , 4 , 5 , … } = ⟨ 2 , 5 ⟩ S = \{0,2,4,5,\ldots\} = \langle2,5\rangle S = { 0 , 2 , 4 , 5 , … } = ⟨ 2 , 5 ⟩ .
( 5 , 5 , 3 ) (5,5,3) ( 5 , 5 , 3 ) : C = 01 2 0 2 C = 01^{2}0^{2} C = 0 1 2 0 2 , S = { 0 , 2 , 3 , 6 , … } S = \{0,2,3,6,\ldots\} S = { 0 , 2 , 3 , 6 , … } ; 2 + 2 = 4 ∉ S 2+2=4 \notin S 2 + 2 = 4 ∈ / S .
( 6 , 4 , 4 ) (6,4,4) ( 6 , 4 , 4 ) : C = 0 2 1 2 0 C = 0^{2}1^{2}0 C = 0 2 1 2 0 , S = { 0 , 3 , 4 , 6 , … } = ⟨ 3 , 4 ⟩ S = \{0,3,4,6,\ldots\} = \langle3,4\rangle S = { 0 , 3 , 4 , 6 , … } = ⟨ 3 , 4 ⟩ .
( 6 , 4 , 3 , 1 ) (6,4,3,1) ( 6 , 4 , 3 , 1 ) : C = 01 2 0101 2 0 C = 01^{2}0101^{2}0 C = 0 1 2 010 1 2 0 , S = { 0 , 2 , 3 , 5 , 7 , 8 , 10 , … } S = \{0,2,3,5,7,8,10,\ldots\} S = { 0 , 2 , 3 , 5 , 7 , 8 , 10 , … } ; 2 + 2 = 4 ∉ S 2+2=4 \notin S 2 + 2 = 4 ∈ / S .
( 4 , 3 , 2 , 1 ) (4,3,2,1) ( 4 , 3 , 2 , 1 ) : C = 0101010 C = 0101010 C = 0101010 , S = ⟨ 2 , 9 ⟩ S = \langle2,9\rangle S = ⟨ 2 , 9 ⟩ .
( 4 , 4 , 3 , 2 ) (4,4,3,2) ( 4 , 4 , 3 , 2 ) : C = 01010 2 C = 01010^{2} C = 0101 0 2 , S = { 0 , 2 , 4 , 7 , … } S = \{0,2,4,7,\ldots\} S = { 0 , 2 , 4 , 7 , … } ; 2 + 4 = 6 ∉ S 2+4=6 \notin S 2 + 4 = 6 ∈ / S .
( 9 , 7 , 3 , 3 ) (9,7,3,3) ( 9 , 7 , 3 , 3 ) : C = 0 2 1 4 01 2 0 C = 0^{2}1^{4}01^{2}0 C = 0 2 1 4 0 1 2 0 , S = { 0 , 3 , 4 , 5 , 6 , 8 , 9 , 11 , … } S = \{0,3,4,5,6,8,9,11,\ldots\} S = { 0 , 3 , 4 , 5 , 6 , 8 , 9 , 11 , … } ; 3 + 4 = 7 ∉ S 3+4=7 \notin S 3 + 4 = 7 ∈ / S .
( 7 , 5 , 4 , 4 ) (7,5,4,4) ( 7 , 5 , 4 , 4 ) : C = 0 2 101 2 0 C = 0^{2}101^{2}0 C = 0 2 10 1 2 0 , S = { 0 , 3 , 5 , 6 , 8 , … } = ⟨ 3 , 5 ⟩ S = \{0,3,5,6,8,\ldots\} = \langle3,5\rangle S = { 0 , 3 , 5 , 6 , 8 , … } = ⟨ 3 , 5 ⟩ .
( 9 , 8 , 8 , 2 ) (9,8,8,2) ( 9 , 8 , 8 , 2 ) : C = 01 6 0 2 10 C = 01^{6}0^{2}10 C = 0 1 6 0 2 10 , S = { 0 , 2 , … , 7 , 10 , 12 , … } S = \{0,2,\ldots,7,10,12,\ldots\} S = { 0 , 2 , … , 7 , 10 , 12 , … } ; 2 + 6 = 8 ∉ S 2+6=8 \notin S 2 + 6 = 8 ∈ / S .
( 9 , 9 , 6 , 6 ) (9,9,6,6) ( 9 , 9 , 6 , 6 ) : C = 0 2 1 3 0 2 C = 0^{2}1^{3}0^{2} C = 0 2 1 3 0 2 , S = { 0 , 3 , 4 , 5 , 8 , … } S = \{0,3,4,5,8,\ldots\} S = { 0 , 3 , 4 , 5 , 8 , … } ; 3 + 3 = 6 ∉ S 3+3=6 \notin S 3 + 3 = 6 ∈ / S .
( 7 , 7 , 6 , 6 ) (7,7,6,6) ( 7 , 7 , 6 , 6 ) : C = 0 2 10 2 C = 0^{2}10^{2} C = 0 2 1 0 2 , S = { 0 , 3 , 6 , 7 , … } = ⟨ 3 , 7 , 8 ⟩ S = \{0,3,6,7,\ldots\} = \langle3,7,8\rangle S = { 0 , 3 , 6 , 7 , … } = ⟨ 3 , 7 , 8 ⟩ , with gaps { 1 , 2 , 4 , 5 } \{1,2,4,5\} { 1 , 2 , 4 , 5 } .
( 9 , 9 , 9 , 5 ) (9,9,9,5) ( 9 , 9 , 9 , 5 ) : C = 01 4 0 3 C = 01^{4}0^{3} C = 0 1 4 0 3 , S = { 0 , 2 , 3 , 4 , 5 , 9 , … } S = \{0,2,3,4,5,9,\ldots\} S = { 0 , 2 , 3 , 4 , 5 , 9 , … } ; 3 + 3 = 6 ∉ S 3+3=6 \notin S 3 + 3 = 6 ∈ / S .
( 4 , 1 , 1 , 1 ) (4,1,1,1) ( 4 , 1 , 1 , 1 ) : C = 0 3 1 3 0 C=0^3 1^3 0 C = 0 3 1 3 0 , S = { 0 , 4 , 5 , 6 , 8 , … } = ⟨ 4 , 5 , 6 ⟩ S=\{0,4,5,6,8,\ldots\}=\langle4,5,6\rangle S = { 0 , 4 , 5 , 6 , 8 , … } = ⟨ 4 , 5 , 6 ⟩ .
( 7 , 6 , 5 , 4 , 3 , 2 , 1 ) (7,6,5,4,3,2,1) ( 7 , 6 , 5 , 4 , 3 , 2 , 1 ) : C = ( 01 ) 6 0 C=(01)^6 0 C = ( 01 ) 6 0 , S = ⟨ 2 , 15 ⟩ S=\langle2,15\rangle S = ⟨ 2 , 15 ⟩ .
( 11 , 9 , 7 , 5 , 3 , 1 ) (11,9,7,5,3,1) ( 11 , 9 , 7 , 5 , 3 , 1 ) : C = 0 ( 1 2 0 ) 5 C=0(1^2 0)^5 C = 0 ( 1 2 0 ) 5 , S = { 0 , 2 , 3 , 5 , 6 , 8 , 9 , 11 , 12 , 14 , 15 , 17 , … } S=\{0,2,3,5,6,8,9,11,12,14,15,17,\ldots\} S = { 0 , 2 , 3 , 5 , 6 , 8 , 9 , 11 , 12 , 14 , 15 , 17 , … } ; 2 + 2 = 4 ∉ S 2+2=4\notin S 2 + 2 = 4 ∈ / S .
( 11 , 11 , 9 , 7 , 5 , 3 , 2 ) (11,11,9,7,5,3,2) ( 11 , 11 , 9 , 7 , 5 , 3 , 2 ) : C = 010 ( 1 2 0 ) 4 0 C=010(1^2 0)^4 0 C = 010 ( 1 2 0 ) 4 0 , S = { 0 , 2 , 4 , 5 , 7 , 8 , 10 , 11 , 13 , 14 , 17 , … } S=\{0,2,4,5,7,8,10,11,13,14,17,\ldots\} S = { 0 , 2 , 4 , 5 , 7 , 8 , 10 , 11 , 13 , 14 , 17 , … } ; 2 + 4 = 6 ∉ S 2+4=6\notin S 2 + 4 = 6 ∈ / S .
( 13 , 11 , 7 , 5 , 5 ) (13,11,7,5,5) ( 13 , 11 , 7 , 5 , 5 ) : C = 02 1 20140120 C=0 2^1 2 0 1 4 0 1 2 0 C = 0 2 1 20140120 , S = { 0 , 3 , 4 , 6 , 7 , 8 , 9 , 11 , 12 , 14 , … } S=\{0,3,4,6,7,8,9,11,12,14,\ldots\} S = { 0 , 3 , 4 , 6 , 7 , 8 , 9 , 11 , 12 , 14 , … } ; 4 + 6 = 10 ∉ S 4+6=10\notin S 4 + 6 = 10 ∈ / S .
( 13 , 11 , 9 , 8 , 8 , 6 , 4 , 2 ) (13,11,9,8,8,6,4,2) ( 13 , 11 , 9 , 8 , 8 , 6 , 4 , 2 ) : C = 01 2 01 2 01 2 01 2 01 2 01 2 0 C=0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 C = 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 ; 2 + 2 = 4 ∉ S 2+2=4\notin S 2 + 2 = 4 ∈ / S .
( 5 , 5 , 5 , 5 , 3 ) (5,5,5,5,3) ( 5 , 5 , 5 , 5 , 3 ) : C = 01 2 0 4 C=0 1^2 0^4 C = 0 1 2 0 4 , S = { 0 , 2 , 3 , 8 , … } S=\{0,2,3,8,\ldots\} S = { 0 , 2 , 3 , 8 , … } ; 2 + 2 = 4 ∉ S 2+2=4\notin S 2 + 2 = 4 ∈ / S .
Conjugation and symmetry
In this section we use the full Keith–Nath word: u ( λ ) = c 0 c 1 ⋯ c F u(\lambda)=c_0c_1\cdots c_F u ( λ ) = c 0 c 1 ⋯ c F , c x = 1 c_x=1 c x = 1 if and only if x ∈ S K N ( λ ) x\in S^{KN}(\lambda) x ∈ S K N ( λ ) , where F = h ( 1 , 1 ) ( λ ) F=h_{(1,1)}(\lambda) F = h ( 1 , 1 ) ( λ ) . It always has c 0 = 1 c_0=1 c 0 = 1 and c F = 0 c_F=0 c F = 0 , and u ( λ ) = 1 C ( λ ) u(\lambda)=1C(\lambda) u ( λ ) = 1 C ( λ ) when the smallest part of λ \lambda λ is 1. We write u ˉ \bar{u} u ˉ for the complement of u u u (interchange 0 and 1) and u r e v u^{\mathrm{rev}} u rev for the reversed word. Recall that a numerical semigroup S S S is symmetric if x ∈ S x\in S x ∈ S if and only if F ( S ) − x ∉ S F(S)-x\notin S F ( S ) − x ∈ / S for all x ∈ Z x\in\mathbb{Z} x ∈ Z , and irreducible if it is not the intersection of two numerical semigroups properly containing it.
Lemma 6.1. For every nonempty partition λ \lambda λ , u ( λ ′ ) = ( u ( λ ) ‾ ) r e v u(\lambda')=(\overline{u(\lambda)})^{\mathrm{rev}} u ( λ ′ ) = ( u ( λ ) ) rev . Equivalently, h ( 1 , 1 ) ( λ ′ ) = h ( 1 , 1 ) ( λ ) = F h_{(1,1)}(\lambda')=h_{(1,1)}(\lambda)=F h ( 1 , 1 ) ( λ ′ ) = h ( 1 , 1 ) ( λ ) = F and, for 0 ≤ x ≤ F 0\le x\le F 0 ≤ x ≤ F , x ∈ S K N ( λ ′ ) x\in S^{KN}(\lambda') x ∈ S K N ( λ ′ ) if and only if F − x ∉ S K N ( λ ) F-x\notin S^{KN}(\lambda) F − x ∈ / S K N ( λ ) .
Proof. The profile of λ \lambda λ is a lattice path of F + 1 F+1 F + 1 unit steps, going from the lower end of the first column to the right end of the first row. Transposition in the main diagonal maps the diagram of λ \lambda λ onto that of λ ′ \lambda' λ ′ , and maps this path onto the profile of λ ′ \lambda' λ ′ . It exchanges horizontal and vertical steps, and it traverses the path in the opposite direction: the start of the path of λ \lambda λ becomes the end of the path of λ ′ \lambda' λ ′ . Therefore the step with index x x x in u ( λ ′ ) u(\lambda') u ( λ ′ ) is the complement of the step with index F − x F-x F − x in u ( λ ) u(\lambda) u ( λ ) . The number of steps is unchanged, so the largest hook lengths agree.
Theorem 6.2. Let λ \lambda λ correspond to a numerical semigroup S S S . Then ℓ ( λ ) ≥ λ 1 \ell(\lambda)\ge\lambda_1 ℓ ( λ ) ≥ λ 1 , and the following are equivalent:
Moreover, if F ( S ) F(S) F ( S ) is even, then ℓ ( λ ) ≥ λ 1 + 1 \ell(\lambda)\ge\lambda_1+1 ℓ ( λ ) ≥ λ 1 + 1 .
Proof. Let F = F ( S ) = λ 1 + ℓ ( λ ) − 1 F=F(S)=\lambda_1+\ell(\lambda)-1 F = F ( S ) = λ 1 + ℓ ( λ ) − 1 and g = g ( S ) = ℓ ( λ ) g=g(S)=\ell(\lambda) g = g ( S ) = ℓ ( λ ) . Consider the map σ : { 0 , … , F } → { 0 , … , F } \sigma:\{0,\ldots,F\}\to\{0,\ldots,F\} σ : { 0 , … , F } → { 0 , … , F } , σ ( x ) = F − x \sigma(x)=F-x σ ( x ) = F − x . Since σ ∘ σ = i d \sigma\circ\sigma=\mathrm{id} σ ∘ σ = id , σ \sigma σ is an involution, and the group ⟨ σ ⟩ = { i d , σ } ≅ Z / 2 Z \langle\sigma\rangle=\{\mathrm{id},\sigma\}\cong\mathbb{Z}/2\mathbb{Z} ⟨ σ ⟩ = { id , σ } ≅ Z /2 Z acts on { 0 , … , F } \{0,\ldots,F\} { 0 , … , F } by i d ⋅ x = x \mathrm{id}\cdot x=x id ⋅ x = x and σ ⋅ x = F − x \sigma\cdot x=F-x σ ⋅ x = F − x . The orbit of x x x under this action is { x , σ ( x ) } = { x , F − x } \{x,\sigma(x)\}=\{x,F-x\} { x , σ ( x )} = { x , F − x } . The orbits partition { 0 , … , F } \{0,\ldots,F\} { 0 , … , F } , and they are the pairs { x , F − x } \{x,F-x\} { x , F − x } of integers adding up to F F F , together with the fixed point { F / 2 } \{F/2\} { F /2 } when F F F is even (the only one with σ ( x ) = x \sigma(x)=x σ ( x ) = x ). Each orbit contains at most one element of S S S : if x x x and F − x F-x F − x were both in S S S , then F = x + ( F − x ) ∈ S F=x+(F-x)\in S F = x + ( F − x ) ∈ S , a contradiction.
If F F F is odd, then the action has no fixed points, so there are ( F + 1 ) / 2 (F+1)/2 ( F + 1 ) /2 orbits, all of size 2. Thus, ∣ S ∩ [ 0 , F ] ∣ ≤ ( F + 1 ) / 2 |S\cap[0,F]|\le(F+1)/2 ∣ S ∩ [ 0 , F ] ∣ ≤ ( F + 1 ) /2 and g = ( F + 1 ) − ∣ S ∩ [ 0 , F ] ∣ ≥ ( F + 1 ) / 2 g=(F+1)-|S\cap[0,F]|\ge(F+1)/2 g = ( F + 1 ) − ∣ S ∩ [ 0 , F ] ∣ ≥ ( F + 1 ) /2 . If F F F is even, there are F / 2 F/2 F /2 orbits of size 2 and the fixed orbit { F / 2 } \{F/2\} { F /2 } , which contains no element of S S S , since F / 2 + F / 2 = F F/2+F/2=F F /2 + F /2 = F . Therefore, ∣ S ∩ [ 0 , F ] ∣ ≤ F / 2 |S\cap[0,F]|\le F/2 ∣ S ∩ [ 0 , F ] ∣ ≤ F /2 and g ≥ F / 2 + 1 g\ge F/2+1 g ≥ F /2 + 1 . Substituting F = λ 1 + g − 1 F=\lambda_1+g-1 F = λ 1 + g − 1 gives g ≥ λ 1 g\ge\lambda_1 g ≥ λ 1 in the first case and g ≥ λ 1 + 1 g\ge\lambda_1+1 g ≥ λ 1 + 1 in the second.
Equivalence of (a) and (b): Equality g = λ 1 g=\lambda_1 g = λ 1 forces F = 2 g − 1 F=2g-1 F = 2 g − 1 to be odd and ∣ S ∩ [ 0 , F ] ∣ = ( F + 1 ) / 2 |S\cap[0,F]|=(F+1)/2 ∣ S ∩ [ 0 , F ] ∣ = ( F + 1 ) /2 , that is, every orbit { x , F − x } \{x,F-x\} { x , F − x } of the action contains exactly one element of S S S . For $0\le x\le F$ this is precisely symmetry. For x < 0 x<0 x < 0 or x > F x>F x > F the condition x ∈ S x\in S x ∈ S if and only if F − x ∉ S F-x\notin S F − x ∈ / S holds trivially: if x < 0 x<0 x < 0 then x ∉ S x\notin S x ∈ / S and F − x > F F-x>F F − x > F , so F − x ∈ S F-x\in S F − x ∈ S , and the case $x>F is symmetric. Conversely, symmetry gives exactly one element of S S S in each orbit, and the equality follows.
Equivalence of (b) and (c): By Lemma 6.1, S S S is symmetric if and only if S K N ( λ ′ ) = S K N ( λ ) S^{KN}(\lambda^{\prime})=S^{KN}(\lambda) S K N ( λ ′ ) = S K N ( λ ) , and since the Keith–Nath map is a bijection, this holds if and only if λ ′ = λ \lambda^{\prime}=\lambda λ ′ = λ .
Remark 6.3. The equivalence of (b) and (c) in Theorem 6.2, that symmetric numerical semigroups correspond to self-conjugate Young diagrams, is known and plays a central role in [18 , 22 ] ; see also [20 ] for Young duals of Arf semigroups. Our contribution here is the inequality ℓ ( λ ) ≥ λ 1 \ell(\lambda)\ge\lambda_1 ℓ ( λ ) ≥ λ 1 and its consequences below.
Corollary 6.4. Let λ \lambda λ correspond to a numerical semigroup S S S . Then S S S is irreducible if and only if ℓ ( λ ) − λ 1 ∈ { 0 , 1 } \ell(\lambda)-\lambda_1\in\{0,1\} ℓ ( λ ) − λ 1 ∈ { 0 , 1 } . It is symmetric if the difference is 0, and pseudo-symmetric if it is 1.
Proof. A numerical semigroup is irreducible if and only if g ( S ) = ⌈ ( F ( S ) + 1 ) / 2 ⌉ g(S)=\lceil(F(S)+1)/2\rceil g ( S ) = ⌈( F ( S ) + 1 ) /2 ⌉ , and it is then symmetric for F F F odd and pseudo-symmetric for F F F even [16 Chapter 3] . With g = ℓ g=\ell g = ℓ and F = λ 1 + ℓ − 1 F=\lambda_1+\ell-1 F = λ 1 + ℓ − 1 : for F F F odd the condition reads ℓ = λ 1 \ell=\lambda_1 ℓ = λ 1 , and for F F F even it reads ℓ = ( λ 1 + ℓ ) / 2 + 1 \ell=(\lambda_1+\ell)/2+1 ℓ = ( λ 1 + ℓ ) /2 + 1 , that is, ℓ = λ 1 + 1 \ell=\lambda_1+1 ℓ = λ 1 + 1 . A difference of 0 forces F F F odd and a difference of 1 forces F F F even.
Corollary 6.5. Both λ \lambda λ and λ ′ \lambda^{\prime} λ ′ correspond to numerical semigroups if and only if λ = λ ′ \lambda=\lambda^{\prime} λ = λ ′ and the corresponding semigroup is symmetric.
Proof. Theorem 6.2 applied to λ \lambda λ and to λ ′ \lambda^{\prime} λ ′ gives ℓ ( λ ) ≥ λ 1 \ell(\lambda)\ge\lambda_1 ℓ ( λ ) ≥ λ 1 and λ 1 = ℓ ( λ ′ ) ≥ λ 1 ′ = ℓ ( λ ) \lambda_1=\ell(\lambda^{\prime})\ge\lambda^{\prime}_1=\ell(\lambda) λ 1 = ℓ ( λ ′ ) ≥ λ 1 ′ = ℓ ( λ ) . Thus the equality holds, and λ = λ ′ \lambda=\lambda^{\prime} λ = λ ′ by the theorem. The converse is clear.
For the density statement, let S ′ ( n ) S^{\prime}(n) S ′ ( n ) be the number of partitions of size at most n n n corresponding to numerical semigroups, and let P ( n ) = ∑ j ≤ n p ( j ) P(n)=\sum_{j\le n}p(j) P ( n ) = ∑ j ≤ n p ( j ) , as in [7 ] .
Lemma 6.6. Let e ( n ) = # { λ ⊢ n : ℓ ( λ ) = λ 1 } e(n)=\#\{\lambda\vdash n:\ell(\lambda)=\lambda_1\} e ( n ) = # { λ ⊢ n : ℓ ( λ ) = λ 1 } . Then e ( n ) / p ( n ) → 0 e(n)/p(n)\to0 e ( n ) / p ( n ) → 0 .
Proof. Fix K ≥ 1 K\ge1 K ≥ 1 . For 1 ≤ s ≤ K 1\le s\le K 1 ≤ s ≤ K , let D s = { λ ⊢ n : ℓ ( λ ) − λ 1 = 2 s } D_s=\{\lambda\vdash n:\ell(\lambda)-\lambda_1=2s\} D s = { λ ⊢ n : ℓ ( λ ) − λ 1 = 2 s } , E = { λ ⊢ n : ℓ ( λ ) = λ 1 } E=\{\lambda\vdash n:\ell(\lambda)=\lambda_1\} E = { λ ⊢ n : ℓ ( λ ) = λ 1 } , and let B s = { λ ⊢ n : λ 1 − λ 2 < s } B_s=\{\lambda\vdash n:\lambda_1-\lambda_2<s\} B s = { λ ⊢ n : λ 1 − λ 2 < s } (with λ 2 = 0 \lambda_2=0 λ 2 = 0 if ℓ ( λ ) = 1 \ell(\lambda)=1 ℓ ( λ ) = 1 ). For λ ∈ E ∖ B s \lambda\in E\setminus B_s λ ∈ E ∖ B s with n ≥ 2 n\ge2 n ≥ 2 define
ϕ s ( λ ) = ( λ 1 − s , λ 2 , … , λ ℓ , 1 s ) . \phi_s(\lambda)=(\lambda_1-s,\lambda_2,\ldots,\lambda_\ell,1^s). ϕ s ( λ ) = ( λ 1 − s , λ 2 , … , λ ℓ , 1 s ) .
This is a partition because λ 1 − s ≥ λ 2 ≥ 1 \lambda_1-s\ge\lambda_2\ge1 λ 1 − s ≥ λ 2 ≥ 1 . It has ℓ + s \ell+s ℓ + s parts and largest part λ 1 − s \lambda_1-s λ 1 − s , so ϕ s ( λ ) ∈ D s \phi_s(\lambda)\in D_s ϕ s ( λ ) ∈ D s . Moreover ϕ s \phi_s ϕ s is injective: λ \lambda λ is recovered by deleting s s s parts equal to 1 and adding s s s to the first part. The sets E , D 1 , … , D K E,D_1,\ldots,D_K E , D 1 , … , D K are pairwise disjoint, so
∣ E ∣ + ∑ s = 1 K ( ∣ E ∣ − ∣ B s ∣ ) ≤ p ( n ) , |E|+\sum_{s=1}^{K}(|E|-|B_s|)\le p(n), ∣ E ∣ + s = 1 ∑ K ( ∣ E ∣ − ∣ B s ∣ ) ≤ p ( n ) ,
which implies ( K + 1 ) e ( n ) ≤ p ( n ) + K ∣ B K ∣ (K+1)e(n)\le p(n)+K|B_K| ( K + 1 ) e ( n ) ≤ p ( n ) + K ∣ B K ∣ .
By conjugation, λ 1 − λ 2 \lambda_1-\lambda_2 λ 1 − λ 2 equals the number of parts of λ ′ \lambda^{\prime} λ ′ equal to 1. Therefore
∣ B K ∣ = ∑ t < K # { μ ⊢ n : μ has exactly t parts equal to 1 } = ∑ t < K p ˉ ( n − t ) , |B_K|=\sum_{t<K}\#\{\mu\vdash n:\mu\text{ has exactly }t\text{ parts equal to }1\}=\sum_{t<K}\bar p(n-t), ∣ B K ∣ = t < K ∑ # { μ ⊢ n : μ has exactly t parts equal to 1 } = t < K ∑ p ˉ ( n − t ) ,
and p ˉ ( n − t ) = p ( n − t ) − p ( n − t − 1 ) = o ( p ( n ) ) \bar p(n-t)=p(n-t)-p(n-t-1)=o(p(n)) p ˉ ( n − t ) = p ( n − t ) − p ( n − t − 1 ) = o ( p ( n )) by the Hardy–Ramanujan asymptotic formula, which gives p ( n − 1 ) / p ( n ) → 1 p(n-1)/p(n)\to1 p ( n − 1 ) / p ( n ) → 1 [11 ] . Thus lim sup e ( n ) / p ( n ) ≤ 1 / ( K + 1 ) \limsup e(n)/p(n)\le1/(K+1) lim sup e ( n ) / p ( n ) ≤ 1/ ( K + 1 ) for every K K K .
Theorem 6.7. For every n n n ,
# { λ ⊢ n : λ corresponds to a numerical semigroup } ≤ p ( n ) + e ( n ) 2 , \#\{\lambda\vdash n:\lambda\text{ corresponds to a numerical semigroup}\}\le\frac{p(n)+e(n)}{2}, # { λ ⊢ n : λ corresponds to a numerical semigroup } ≤ 2 p ( n ) + e ( n ) , and consequently
lim sup n → ∞ S ′ ( n ) P ( n ) ≤ 1 2 . \limsup_{n\to\infty}\frac{S^{\prime}(n)}{P(n)}\le\frac{1}{2}. n → ∞ lim sup P ( n ) S ′ ( n ) ≤ 2 1 .
Proof. By Theorem 6.2 , the partitions in question satisfy ℓ ( λ ) ≥ λ 1 \ell(\lambda) \ge\lambda_1 ℓ ( λ ) ≥ λ 1 . Conjugation is an involution exchanging { ℓ > λ 1 } \{\ell> \lambda_1\} { ℓ > λ 1 } and { ℓ < λ 1 } \{\ell< \lambda_1\} { ℓ < λ 1 } , so these two sets have the same size ( p ( n ) − e ( n ) ) / 2 (p(n)-e(n))/2 ( p ( n ) − e ( n )) /2 , and # { ℓ ≥ λ 1 } = ( p ( n ) − e ( n ) ) / 2 + e ( n ) = ( p ( n ) + e ( n ) ) / 2 \#\{\ell\ge\lambda_1\} = (p(n)-e(n))/2+e(n) = (p(n)+e(n))/2 # { ℓ ≥ λ 1 } = ( p ( n ) − e ( n )) /2 + e ( n ) = ( p ( n ) + e ( n )) /2 . Summing over j ≤ n j \le n j ≤ n and using e ( j ) / p ( j ) → 0 e(j)/p(j) \to0 e ( j ) / p ( j ) → 0 (Lemma 6.6 ) together with P ( n ) → ∞ P(n) \to\infty P ( n ) → ∞ gives the limit statement.
Remark 6.8. Constantin, Houston-Edwards and Kaplan conjectured that S ′ ( n ) / P ( n ) → 0 S'(n)/P(n) \to0 S ′ ( n ) / P ( n ) → 0 [7 ] . Theorem 6.7 is an unconditional first step. Numerically the ratio is much smaller: S ′ ( 44 ) / P ( 44 ) ≈ 0.115 S'(44)/P(44) \approx0.115 S ′ ( 44 ) / P ( 44 ) ≈ 0.115 .
The staircase theorem
Let δ g = ( g , g − 1 , … , 2 , 1 ) \delta_g=(g,g-1,\ldots,2,1) δ g = ( g , g − 1 , … , 2 , 1 ) be the staircase partition with g g g parts. We say λ ⊆ δ g \lambda\subseteq\delta_g λ ⊆ δ g if λ i ≤ g + 1 − i \lambda_i \le g+1-i λ i ≤ g + 1 − i for every i i i . For a numerical set S S S with gaps x 1 < x 2 < ⋯ < x g x_1 < x_2 < \cdots< x_g x 1 < x 2 < ⋯ < x g , the weight of S S S is
w ( S ) = ∑ i = 1 g x i − g ( g + 1 ) 2 = ∑ i = 1 g ( x i − i ) ≥ 0. w(S)=\sum_{i=1}^{g}x_i-\frac{g(g+1)}{2}=\sum_{i=1}^{g}(x_i-i)\ge0. w ( S ) = i = 1 ∑ g x i − 2 g ( g + 1 ) = i = 1 ∑ g ( x i − i ) ≥ 0.
For numerical semigroups arising as Weierstrass semigroups of algebraic curves, this is the classical weight of the Weierstrass point [8 ] .
Lemma 7.1. Let S ≠ N 0 S \ne\mathbb{N}_0 S = N 0 be a numerical set with gaps x 1 < ⋯ < x g x_1 < \cdots< x_g x 1 < ⋯ < x g and Keith–Nath partition λ = λ ( S ) \lambda=\lambda(S) λ = λ ( S ) . The row of λ \lambda λ belonging to the gap x i x_i x i is the row λ g + 1 − i \lambda_{g+1-i} λ g + 1 − i , and
λ g + 1 − i = x i − ( i − 1 ) ( 1 ≤ i ≤ g ) . \lambda_{g+1-i}=x_i-(i-1)\qquad(1\le i\le g). λ g + 1 − i = x i − ( i − 1 ) ( 1 ≤ i ≤ g ) .
Proof. Rows correspond to gaps, and they are listed from the top, so the largest gap x g x_g x g gives the first row and the smallest gap x 1 x_1 x 1 gives the last row λ g \lambda_g λ g . The length of the row of x i x_i x i is the number of elements of S S S in [ 0 , x i ) [0,x_i) [ 0 , x i ) . That interval contains x i x_i x i integers, of which exactly i − 1 i-1 i − 1 are gaps.
Theorem 7.2. Let S S S be a numerical set of genus g ≥ 1 g \ge1 g ≥ 1 with gaps x 1 < ⋯ < x g x_1 < \cdots< x_g x 1 < ⋯ < x g , let λ = λ ( S ) \lambda=\lambda(S) λ = λ ( S ) , and let u = c 0 c 1 ⋯ c F u=c_0c_1\cdots c_F u = c 0 c 1 ⋯ c F be its Keith–Nath word (so c 0 = 1 c_0=1 c 0 = 1 and C ( λ ) = c 1 ⋯ c F C(\lambda)=c_1\cdots c_F C ( λ ) = c 1 ⋯ c F when the smallest part of λ \lambda λ is 1). The following conditions are equivalent:
(i) x i ≤ 2 i − 1 x_i \le2i-1 x i ≤ 2 i − 1 for i = 1 , … , g i=1,\ldots,g i = 1 , … , g ;
(ii) λ ⊆ δ g \lambda\subseteq\delta_g λ ⊆ δ g ;
(iii) for i = 1 , … , g i=1,\ldots,g i = 1 , … , g , at least i i i of the letters c 1 , … , c 2 i − 1 c_1,\ldots,c_{2i-1} c 1 , … , c 2 i − 1 are zeros, where c x = 1 c_x=1 c x = 1 for x > F x>F x > F .
If S S S is a numerical semigroup, these conditions hold. Moreover, equality x i = 2 i − 1 x_i=2i-1 x i = 2 i − 1 for all i i i (equivalently λ = δ g \lambda=\delta_g λ = δ g ) holds if and only if S = ⟨ 2 , 2 g + 1 ⟩ S=\langle2,2g+1\rangle S = ⟨ 2 , 2 g + 1 ⟩ .
Proof. Equivalence of (i) and (ii): by Lemma 7.1 , λ g + 1 − i ≤ g + 1 − ( g + 1 − i ) = i \lambda_{g+1-i}\le g+1-(g+1-i)=i λ g + 1 − i ≤ g + 1 − ( g + 1 − i ) = i is equivalent to x i − ( i − 1 ) ≤ i x_i-(i-1)\le i x i − ( i − 1 ) ≤ i , that is, to x i ≤ 2 i − 1 x_i\le2i-1 x i ≤ 2 i − 1 .
Equivalence of (i) and (iii): the zeros of u u u at positions ≥ 1 \ge1 ≥ 1 are exactly the gaps. So at least i i i zeros among c 1 , … , c 2 i − 1 c_1,\ldots,c_{2i-1} c 1 , … , c 2 i − 1 says that at least i i i gaps lie in [ 1 , 2 i − 1 ] [1,2i-1] [ 1 , 2 i − 1 ] , that is, x i ≤ 2 i − 1 x_i\le2i-1 x i ≤ 2 i − 1 .
Now, we show that every numerical semigroup satisfy (i). Let S S S be a numerical semigroup and fix i i i . Partition { 1 , … , x i − 1 } \{1,\ldots,x_i-1\} { 1 , … , x i − 1 } into the classes { y , x i − y } \{y,x_i-y\} { y , x i − y } ; there are ⌈ ( x i − 1 ) / 2 ⌉ \lceil(x_i-1)/2\rceil ⌈( x i − 1 ) /2 ⌉ of them. If both elements of a class were in S S S , their sum x i x_i x i would be in S S S . So each class contains a gap smaller than x i x_i x i , and distinct classes are disjoint. Since exactly i − 1 i-1 i − 1 gaps are smaller than x i x_i x i , we get i − 1 ≥ ⌈ ( x i − 1 ) / 2 ⌉ ≥ ( x i − 1 ) / 2 i-1\ge\lceil(x_i-1)/2\rceil\ge(x_i-1)/2 i − 1 ≥ ⌈( x i − 1 ) /2 ⌉ ≥ ( x i − 1 ) /2 , that is, x i ≤ 2 i − 1 x_i\le2i-1 x i ≤ 2 i − 1 .
Finally, if x i = 2 i − 1 x_i=2i-1 x i = 2 i − 1 for all i i i , then the gaps are 1 , 3 , … , 2 g − 1 1,3,\ldots,2g-1 1 , 3 , … , 2 g − 1 , so S S S consists of all even numbers and all integers ≥ 2 g \ge2g ≥ 2 g , that is, S = ⟨ 2 , 2 g + 1 ⟩ S=\langle2,2g+1\rangle S = ⟨ 2 , 2 g + 1 ⟩ . By Lemma 7.1 , this is the case λ g + 1 − i = i \lambda_{g+1-i}=i λ g + 1 − i = i for all i i i , that is, λ = δ g \lambda=\delta_g λ = δ g . Conversely, ⟨ 2 , 2 g + 1 ⟩ \langle2,2g+1\rangle ⟨ 2 , 2 g + 1 ⟩ has gaps 1 , 3 , … , 2 g − 1 1,3,\ldots,2g-1 1 , 3 , … , 2 g − 1 .
Remark 7.3. The case i = g i=g i = g of Theorem 7.2 is F ≤ 2 g − 1 F\leq2g-1 F ≤ 2 g − 1 , equivalently λ 1 ≤ ℓ ( λ ) \lambda_1\leq\ell(\lambda) λ 1 ≤ ℓ ( λ ) . So Theorem 7.2 refines the first statement of Theorem 6.2 : it bounds every row, not only the first one. The gap inequality x i ≤ 2 i − 1 x_i\leq2i-1 x i ≤ 2 i − 1 is a classical argument for gaps. What is new here is its reformulation as containment in a staircase and as a ballot condition on creation sequences, together with the consequences below. In the threshold-graph language of § 3 , the ballot condition says that for every i ≤ g i\leq g i ≤ g , at least i i i of the vertices v 1 , … , v 2 i − 1 v_1,\ldots,v_{2i-1} v 1 , … , v 2 i − 1 are isolated.
Corollary 7.4. Let λ \lambda λ have smallest part 1 1 1 , and let S = S λ S=S_\lambda S = S λ have genus g g g . Then ∣ λ ∣ = g + w ( S ) |\lambda|=g+w(S) ∣ λ ∣ = g + w ( S ) . If S S S is a numerical semigroup, then 0 ≤ w ( S ) ≤ ( g 2 ) 0\leq w(S)\leq\binom{g}{2} 0 ≤ w ( S ) ≤ ( 2 g ) , and therefore
g ≤ ∣ λ ∣ ≤ g ( g + 1 ) 2 . g\leq|\lambda|\leq\frac{g(g+1)}{2}. g ≤ ∣ λ ∣ ≤ 2 g ( g + 1 ) . Equality on the left holds exactly for λ = ( 1 g ) \lambda=(1^g) λ = ( 1 g ) (S = { 0 } ∪ [ g + 1 , ∞ ) S=\{0\}\cup[g+1,\infty) S = { 0 } ∪ [ g + 1 , ∞ ) ), and on the right exactly for λ = δ g \lambda=\delta_g λ = δ g (S = ⟨ 2 , 2 g + 1 ⟩ S=\langle2,2g+1\rangle S = ⟨ 2 , 2 g + 1 ⟩ ). Moreover, the number of non-edges of the threshold graph G ( S ) G(S) G ( S ) equals
∑ i x i = g ( g + 1 ) 2 + w ( S ) . \sum_i x_i=\frac{g(g+1)}{2}+w(S). i ∑ x i = 2 g ( g + 1 ) + w ( S ) .
Proof. By Lemma 7.1, ∣ λ ∣ = ∑ i = 1 g ( x i − i + 1 ) = ∑ i x i − ( g 2 ) = w ( S ) + ( g + 1 2 ) − ( g 2 ) = w ( S ) + g |\lambda|=\sum_{i=1}^{g}(x_i-i+1)=\sum_i x_i-\binom{g}{2}=w(S)+\binom{g+1}{2}-\binom{g}{2}=w(S)+g ∣ λ ∣ = ∑ i = 1 g ( x i − i + 1 ) = ∑ i x i − ( 2 g ) = w ( S ) + ( 2 g + 1 ) − ( 2 g ) = w ( S ) + g . The gaps are distinct positive integers, so x i ≥ i x_i\geq i x i ≥ i and w ( S ) ≥ 0 w(S)\geq0 w ( S ) ≥ 0 , with equality if and only if the gaps are 1 , … , g 1,\ldots,g 1 , … , g , that is, λ = ( 1 g ) \lambda=(1^g) λ = ( 1 g ) . For a semigroup, Theorem 7.2 gives x i ≤ 2 i − 1 x_i\leq2i-1 x i ≤ 2 i − 1 , so w ( S ) ≤ ∑ i ( i − 1 ) = ( g 2 ) w(S)\leq\sum_i(i-1)=\binom{g}{2} w ( S ) ≤ ∑ i ( i − 1 ) = ( 2 g ) , with equality if and only if x i = 2 i − 1 x_i=2i-1 x i = 2 i − 1 for all i i i , that is, λ = δ g \lambda=\delta_g λ = δ g . Finally, by Proposition 3.12-(5), a pair { v i , v j } \{v_i,v_j\} { v i , v j } with i < j i<j i < j is a non-edge exactly when j j j is a gap, and each gap x x x contributes x x x such pairs.
Corollary 7.5. For all n , g ≥ 1 n,g\geq1 n , g ≥ 1 , PG ( n , g ) \operatorname{PG}(n,g) PG ( n , g ) is the number of numerical semigroups of genus g g g and weight n − g n-g n − g . In particular:
PG ( n , g ) = 0 \operatorname{PG}(n,g)=0 PG ( n , g ) = 0 unless g ≤ n ≤ g ( g + 1 ) / 2 g\leq n\leq g(g+1)/2 g ≤ n ≤ g ( g + 1 ) /2 , and PG ( g , g ) = PG ( g ( g + 1 ) 2 , g ) = 1 \operatorname{PG}(g,g)=\operatorname{PG}\left(\frac{g(g+1)}{2},g\right)=1 PG ( g , g ) = PG ( 2 g ( g + 1 ) , g ) = 1 ;
for 0 ≤ w ≤ g 0\leq w\leq g 0 ≤ w ≤ g , the number of numerical semigroups of genus g g g and weight w w w is
p ( w ) − E ( 2 w − g ) , p(w)-E(2w-g), p ( w ) − E ( 2 w − g ) , and it equals p ( w ) p(w) p ( w ) when 2 w ≤ g 2w\leq g 2 w ≤ g .
Proof. By Lemma 3.7, the partitions of n n n with g g g parts corresponding to numerical semigroups are the λ ( S ) \lambda(S) λ ( S ) for the semigroups S S S of genus g g g with ∣ λ ( S ) ∣ = n |\lambda(S)|=n ∣ λ ( S ) ∣ = n , and ∣ λ ( S ) ∣ = g + w ( S ) |\lambda(S)|=g+w(S) ∣ λ ( S ) ∣ = g + w ( S ) by Corollary 7.4. (1) follows from the bounds and equality cases in Corollary 7.4.
For (2), put n = g + w n=g+w n = g + w ; the condition w ≤ g w\leq g w ≤ g is 2 g ≥ n 2g\geq n 2 g ≥ n , and 2 n − 3 g = 2 w − g 2n-3g=2w-g 2 n − 3 g = 2 w − g . Apply Theorem 9.5 , and Lemma 9.4(1) when 2 w ≤ g 2w\leq g 2 w ≤ g .
Corollary 7.6. Let S S S be a numerical set of genus g ≥ 1 g\geq1 g ≥ 1 with Keith–Nath word c 0 c 1 ⋯ c_0c_1\cdots c 0 c 1 ⋯ (with c x = 1 c_x=1 c x = 1 for x > F x>F x > F ). Read the 2 g 2g 2 g letters c 1 c 2 ⋯ c 2 g c_1c_2\cdots c_{2g} c 1 c 2 ⋯ c 2 g as a lattice path, with 0 0 0 an up-step and 1 1 1 a down-step. Then S S S satisfies the conditions of Theorem 7.2 if and only if this path is a Dyck path (it has g g g up-steps and g g g down-steps and never goes below its starting level). The map S ↦ c 1 ⋯ c 2 g S\mapsto c_1\cdots c_{2g} S ↦ c 1 ⋯ c 2 g is a bijection from such numerical sets onto Dyck paths of semilength g g g . Consequently there are exactly C g = 1 g + 1 ( 2 g g ) C_g=\frac{1}{g+1}\binom{2g}{g} C g = g + 1 1 ( g 2 g ) of them, and the number n g n_g n g of numerical semigroups of genus g g g satisfies n g ≤ C g n_g\leq C_g n g ≤ C g .
Proof. Put a i = x i − i a_i=x_i-i a i = x i − i . The up-steps of the path are at the positions of the gaps in [ 1 , 2 g ] [1,2g] [ 1 , 2 g ] . The i i i -th gap x i x_i x i is preceded, among c 1 , … , c x i − 1 c_1,\ldots,c_{x_i-1} c 1 , … , c x i − 1 , by i − 1 i-1 i − 1 zeros and therefore by exactly a i = x i − i a_i=x_i-i a i = x i − i ones.
Assume (i) of Theorem 7.2 . Then all g g g gaps lie in [ 1 , 2 g − 1 ] [1,2g-1] [ 1 , 2 g − 1 ] , so c 1 ⋯ c 2 g c_1\cdots c_{2g} c 1 ⋯ c 2 g has exactly g g g up-steps and g g g down-steps. A path with g g g up-steps and g g g down-steps is a Dyck path if and only if for every i i i , the i i i -th up-step is preceded by at most i − 1 i-1 i − 1 down-steps. (If some prefix had more down-steps than up-steps, consider the first such prefix: it ends with a down-step, and the next up-step, say the i i i -th, is preceded by at least i i i down-steps; the converse is immediate.) Here this condition reads a i ≤ i − 1 a_i \le i-1 a i ≤ i − 1 , which is (i). So the path is a Dyck path.
Conversely, a Dyck path of semilength g g g has g g g up-steps, at positions 1 ≤ x 1 < ⋯ < x g ≤ 2 g − 1 1 \le x_1 < \cdots< x_g \le2g-1 1 ≤ x 1 < ⋯ < x g ≤ 2 g − 1 satisfying x i − i ≤ i − 1 x_i-i \le i-1 x i − i ≤ i − 1 . Putting S = N 0 ∖ { x 1 , … , x g } S = \mathbb{N}_0 \setminus\{x_1,\ldots,x_g\} S = N 0 ∖ { x 1 , … , x g } gives the unique numerical set of genus g g g satisfying (i) whose word begins with the given path. Thus the map is a bijection. The number of Dyck paths of semilength g g g is C g C_g C g [17 ] . The inequality n g ≤ C g n_g \le C_g n g ≤ C g follows because every numerical semigroup satisfies (i) of Theorem 7.2 .
Remark 7.7. For large g g g the bound n g ≤ C g n_g \le C_g n g ≤ C g is much weaker than the known bound n g ≤ 1 + 3 ⋅ 2 g − 3 n_g \le1+3\cdot2^{g-3} n g ≤ 1 + 3 ⋅ 2 g − 3 ( g ≥ 3 ) (g \ge3) ( g ≥ 3 ) [4 ] . The point of Corollary 7.6 is structural: the creation sequences of numerical semigroups of genus g g g form a subset of an explicit Catalan family defined by (iii) of Theorem 7.2 . Numerically, n g / C g = 1 , 1 , 4 / 5 , 7 / 14 , 12 / 42 , … n_g/C_g = 1, 1, 4/5, 7/14, 12/42, \ldots n g / C g = 1 , 1 , 4/5 , 7/14 , 12/42 , … for g = 1 , … , 5 g=1,\ldots,5 g = 1 , … , 5 .
The semigroup tree in partition language
The numerical semigroups form a rooted tree: the parent of S ≠ N 0 S \ne\mathbb{N}_0 S = N 0 is S ∪ { F ( S ) } S \cup\{F(S)\} S ∪ { F ( S )} , and the children of S S S are the sets S ∖ { x } S \setminus\{x\} S ∖ { x } for the minimal generators x > F ( S ) x > F(S) x > F ( S ) [16 ] . Creation sequences turn this tree into an operation on the largest part.
Theorem 8.1. If λ = ( λ 1 , … , λ ℓ ) \lambda=(\lambda_1,\ldots,\lambda_\ell) λ = ( λ 1 , … , λ ℓ ) corresponds to a numerical semigroup and ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 , then so does ( λ 2 , … , λ ℓ ) (\lambda_2,\ldots,\lambda_\ell) ( λ 2 , … , λ ℓ ) , and it corresponds to S ∪ { F ( S ) } S \cup\{F(S)\} S ∪ { F ( S )} . The partition ( 1 ) (1) ( 1 ) corresponds to { 0 , 2 , 3 , … } \{0,2,3,\ldots\} { 0 , 2 , 3 , … } , whose parent is N 0 ↔ ∅ \mathbb{N}_0 \leftrightarrow\varnothing N 0 ↔ ∅ .
Proof. Let S = S K N ( λ ) S=S^{\mathrm{KN}}(\lambda) S = S KN ( λ ) and F = F ( S ) F=F(S) F = F ( S ) . The set S ∗ = S ∪ { F } S^*=S\cup\{F\} S ∗ = S ∪ { F } is a numerical semigroup: a sum of two nonzero elements of S ∗ S^* S ∗ involving F F F exceeds F F F and hence lies in S S S , and sums of elements of S S S lie in S S S . Write u ( λ ) = u ∗ 1 λ 1 − λ 2 0 u(\lambda)=u^*1^{\lambda_1-\lambda_2}0 u ( λ ) = u ∗ 1 λ 1 − λ 2 0 , where u ∗ u^* u ∗ ends with the north step of the second row. In S ∗ S^* S ∗ every integer beyond the last letter of u ∗ u^* u ∗ is an element. So the Keith–Nath word of S ∗ S^* S ∗ is u ∗ u^* u ∗ , which is the word of ( λ 2 , … , λ ℓ ) (\lambda_2,\ldots,\lambda_\ell) ( λ 2 , … , λ ℓ ) : the path of λ \lambda λ with its top row removed.
Theorem 8.2. Let λ \lambda λ correspond to a numerical semigroup S S S with multiplicity m m m and Frobenius number F F F , and let d ≥ 0 d \ge0 d ≥ 0 . Then ( λ 1 + d , λ 1 , λ 2 , … , λ ℓ ) (\lambda_1+d,\lambda_1,\lambda_2,\ldots,\lambda_\ell) ( λ 1 + d , λ 1 , λ 2 , … , λ ℓ ) corresponds to a numerical semigroup if and only if F + d + 1 F+d+1 F + d + 1 is a minimal generator of S S S . In particular this forces d ≤ m − 1 d \le m-1 d ≤ m − 1 .
Proof. Prepending the part λ 1 + d \lambda_1+d λ 1 + d appends 1 d 0 1^d0 1 d 0 to the Keith–Nath word, so the new numerical set is S ∖ { F + d + 1 } S\setminus\{F+d+1\} S ∖ { F + d + 1 } . For x ∈ S ∖ { 0 } x\in S\setminus\{0\} x ∈ S ∖ { 0 } , the set S ∖ { x } S\setminus\{x\} S ∖ { x } is a numerical semigroup if and only if x x x is not a sum of two nonzero elements of S ∖ { x } S\setminus\{x\} S ∖ { x } . Since such summands are smaller than x x x , this is the same as x x x being a minimal generator. Every y ≥ F + m + 1 y\ge F+m+1 y ≥ F + m + 1 equals m + ( y − m ) m+(y-m) m + ( y − m ) with y − m > F y-m>F y − m > F , so it is not a minimal generator. Thus, F + d + 1 ≤ F + m F+d+1\le F+m F + d + 1 ≤ F + m .
Corollary 8.3. If λ \lambda λ corresponds to a numerical semigroup, then so does each of its suffixes ( λ i , … , λ ℓ ) (\lambda_i,\ldots,\lambda_\ell) ( λ i , … , λ ℓ ) . Every partition corresponding to a numerical semigroup is obtained from ( 1 ) (1) ( 1 ) by repeatedly prepending a new largest part λ 1 + d \lambda_1+d λ 1 + d , where 0 ≤ d ≤ m − 1 0\le d\le m-1 0 ≤ d ≤ m − 1 and F + d + 1 F+d+1 F + d + 1 is a minimal generator.
Proof. Iterate Theorem 8.1 ; the construction follows from Theorem 8.2 .
Exact counts of semigroup partitions
Here “λ \lambda λ corresponds to a numerical semigroup” is meant in the sense of [5 ] . By Lemma 3.7 , it holds if and only if the smallest part of λ \lambda λ is 1 1 1 and S C ( λ ) S_{C(\lambda)} S C ( λ ) is a semigroup. Many of the partitions below have the shape
λ = ( t + 1 , κ 1 + 1 , … , κ r + 1 , 1 m − 1 ) , t ≥ κ 1 , m ≥ 2 , (1) \lambda=(t+1,\kappa_1+1,\ldots,\kappa_r+1,1^{m-1}),\qquad t\ge\kappa_1,\ m\ge2, \tag*{(1)} λ = ( t + 1 , κ 1 + 1 , … , κ r + 1 , 1 m − 1 ) , t ≥ κ 1 , m ≥ 2 , (1)
where κ = ( κ 1 , … , κ r ) \kappa=(\kappa_1,\ldots,\kappa_r) κ = ( κ 1 , … , κ r ) is a partition. The parts of ρ = ( t + 1 , κ + 1 ) \rho=(t+1,\kappa+1) ρ = ( t + 1 , κ + 1 ) are at least 2, so λ \lambda λ has exactly m − 1 m-1 m − 1 parts equal to 1 and m ( S K N ( λ ) ) = m m(S^{\mathrm{KN}}(\lambda))=m m ( S KN ( λ )) = m . Its creation sequence is
C ( λ ) = 0 m − 1 w ( κ ) 1 t − κ 1 0 , C(\lambda)=0^{m-1}w(\kappa)1^{t-\kappa_1}0, C ( λ ) = 0 m − 1 w ( κ ) 1 t − κ 1 0 ,
where w ( κ ) w(\kappa) w ( κ ) occupies the positions m , … , m + κ 1 + r − 1 m,\ldots,m+\kappa_1+r-1 m , … , m + κ 1 + r − 1 , and F = m + t + r F=m+t+r F = m + t + r . Put e = F − 2 m = t + r − m e=F-2m=t+r-m e = F − 2 m = t + r − m .
Lemma 9.1. For λ \lambda λ as in (1):
if e < 0 e<0 e < 0 , then λ \lambda λ corresponds to a numerical semigroup;
if e ≥ 0 e\geq0 e ≥ 0 and e ∈ Σ ( κ ) + Σ ( κ ) e\in\Sigma(\kappa)+\Sigma(\kappa) e ∈ Σ ( κ ) + Σ ( κ ) , then it does not;
if e ≥ 0 e\geq0 e ≥ 0 , e ∉ Σ ( κ ) + Σ ( κ ) e\notin\Sigma(\kappa)+\Sigma(\kappa) e ∈ / Σ ( κ ) + Σ ( κ ) and m ≥ κ 1 + r m\geq\kappa_1+r m ≥ κ 1 + r , then it does.
Proof. Write P P P for the set of p ≥ 0 p\geq0 p ≥ 0 such that m + p ∈ S m+p\in S m + p ∈ S and m + p < F m+p<F m + p < F . By Lemma 3.16 ,
P = ( Σ ( κ ) ∩ [ 0 , κ 1 + r − 1 ] ) ∪ [ κ 1 + r , t + r − 1 ] . P=\bigl(\Sigma(\kappa)\cap[0,\kappa_1+r-1]\bigr)\cup[\kappa_1+r,t+r-1]. P = ( Σ ( κ ) ∩ [ 0 , κ 1 + r − 1 ] ) ∪ [ κ 1 + r , t + r − 1 ] .
The gaps larger than m m m are m + z t m+z_t m + z t for the zero positions z t ≤ κ 1 + r − 1 z_t\leq\kappa_1+r-1 z t ≤ κ 1 + r − 1 of w ( κ ) w(\kappa) w ( κ ) , together with F = m + ( t + r ) F=m+(t+r) F = m + ( t + r ) .
(1) If e < 0 e<0 e < 0 then F < 2 m F<2m F < 2 m , and Theorem 4.1 applies.
(2) Since m ≥ 2 m\geq2 m ≥ 2 we have e = t + r − m ≤ t + r − 1 e=t+r-m\leq t+r-1 e = t + r − m ≤ t + r − 1 , so P ∩ [ 0 , e ] = Σ ( κ ) ∩ [ 0 , e ] P\cap[0,e]=\Sigma(\kappa)\cap[0,e] P ∩ [ 0 , e ] = Σ ( κ ) ∩ [ 0 , e ] . If e = p + q e=p+q e = p + q with p , q ∈ Σ ( κ ) p,q\in\Sigma(\kappa) p , q ∈ Σ ( κ ) , then p , q ≤ e p,q\leq e p , q ≤ e lie in P P P , and ( m + p ) + ( m + q ) = 2 m + e = F (m+p)+(m+q)=2m+e=F ( m + p ) + ( m + q ) = 2 m + e = F is a gap.
(3) Suppose that ( m + p ) + ( m + q ) (m+p)+(m+q) ( m + p ) + ( m + q ) is a gap for some p , q ∈ P p,q\in P p , q ∈ P . It is not F F F , since then p + q = e p+q=e p + q = e with p , q ∈ P ∩ [ 0 , e ] ⊆ Σ ( κ ) p,q\in P\cap[0,e]\subseteq\Sigma(\kappa) p , q ∈ P ∩ [ 0 , e ] ⊆ Σ ( κ ) . So 2 m + p + q = m + z 2m+p+q=m+z 2 m + p + q = m + z for a zero position z ≤ κ 1 + r − 1 < m z\leq\kappa_1+r-1<m z ≤ κ 1 + r − 1 < m , giving m + p + q = z < m m+p+q=z<m m + p + q = z < m , which is impossible. Sums involving 0 or elements larger than F F F are in S S S . □ \square □
Remark 9.2. Let G = G ( S λ ) G=G(S_\lambda) G = G ( S λ ) be the threshold graph of λ \lambda λ (Definition 3.5 ), with vertices v 0 , … , v F v_0,\ldots,v_F v 0 , … , v F . For λ \lambda λ as in (1), the construction of G G G proceeds as follows:
(i) v 1 , … , v m − 1 v_1,\ldots,v_{m-1} v 1 , … , v m − 1 are isolated and v m v_m v m is the first dominating vertex;
(ii) the vertices v m , … , v m + κ 1 + r − 1 v_m,\ldots,v_{m+\kappa_1+r-1} v m , … , v m + κ 1 + r − 1 are added according to the creation sequence w ( κ ) w(\kappa) w ( κ ) of the tail κ \kappa κ (v m + p v_{m+p} v m + p is dominating if and only if p p p is a 1-position of w ( κ ) w(\kappa) w ( κ ) );
(iii) a run of dominating vertices follows;
(iv) the last vertex v F = v 2 m + e v_F=v_{2m+e} v F = v 2 m + e is isolated.
By Proposition 3.12 -(6), S λ S_\lambda S λ fails to be a semigroup exactly when two dominating vertices v x , v y v_x,v_y v x , v y (x , y ≥ 1 x,y\geq1 x , y ≥ 1 ) have an isolated vertex v x + y v_{x+y} v x + y . Lemma 9.1 says that, under its hypotheses, the only isolated vertex that can be reached in this way is the last one, v F v_F v F . It is reached if and only if e = p + q e=p+q e = p + q for two 1-positions p , q p,q p , q of the tail’s creation sequence (position 0 and all positions beyond w ( κ ) w(\kappa) w ( κ ) count as 1-positions). Thus whether λ \lambda λ is exceptional is decided by the creation sequence of its tail alone. This mechanism underlies all the solutions in § 10 .
Genus
Definition 9.3. For an integer j j j let
E ( j ) = # { ν a partition : 2 ∣ ν ∣ + ℓ ( ν ) − j ∉ Σ ( ν ) } . E(j)=\#\{\nu\text{ a partition}:2|\nu|+\ell(\nu)-j\notin\Sigma(\nu)\}. E ( j ) = # { ν a partition : 2∣ ν ∣ + ℓ ( ν ) − j ∈ / Σ ( ν )} .
Lemma 9.4.
E ( j ) = 0 E(j)=0 E ( j ) = 0 for j ≤ 0 j\leq0 j ≤ 0 , and only partitions with ∣ ν ∣ < j |\nu|<j ∣ ν ∣ < j contribute to E ( j ) E(j) E ( j ) ; in particular E ( j ) E(j) E ( j ) is finite.
E ( j ) = # { ν : 2 ∣ ν ∣ + ℓ ( ν ) < j } + # { ( ν , t ) : 1 ≤ t ≤ ℓ ( ν ) , 2 ∣ ν ∣ − ν t + t = j } E(j)=\#\{\nu:2|\nu|+\ell(\nu)<j\}+\#\{(\nu,t):1\leq t\leq\ell(\nu),\ 2|\nu|-\nu_t+t=j\} E ( j ) = # { ν : 2∣ ν ∣ + ℓ ( ν ) < j } + # {( ν , t ) : 1 ≤ t ≤ ℓ ( ν ) , 2∣ ν ∣ − ν t + t = j } , and for each ν \nu ν at most one t t t occurs.
Every ν \nu ν counted by E ( j ) E(j) E ( j ) satisfies ∣ ν ∣ + ℓ ( ν ) ≤ j |\nu|+\ell(\nu)\leq j ∣ ν ∣ + ℓ ( ν ) ≤ j .
Proof. Put d = 2 ∣ ν ∣ + ℓ ( ν ) − j d = 2|\nu| + \ell(\nu) - j d = 2∣ ν ∣ + ℓ ( ν ) − j and r = ℓ ( ν ) r = \ell(\nu) r = ℓ ( ν ) . By Lemma 3.16 , d ∉ Σ ( ν ) d \notin\Sigma(\nu) d ∈ / Σ ( ν ) if and only if d < 0 d < 0 d < 0 , or 0 ≤ d < ν 1 + r 0 \le d < \nu_1 + r 0 ≤ d < ν 1 + r and d = z t = ν t + r − t d = z_t = \nu_t + r - t d = z t = ν t + r − t for some t t t . The latter is the equation 2 ∣ ν ∣ − ν t + t = j 2|\nu| - \nu_t + t = j 2∣ ν ∣ − ν t + t = j . The map t ↦ 2 ∣ ν ∣ − ν t + t t \mapsto2|\nu| - \nu_t + t t ↦ 2∣ ν ∣ − ν t + t is strictly increasing, so at most one t t t occurs. This proves (2).
If j ≤ 0 j \le0 j ≤ 0 then d ≥ 0 d \ge0 d ≥ 0 , and d = z t d = z_t d = z t would give 2 ∣ ν ∣ − ν t + t ≤ 0 2|\nu| - \nu_t + t \le0 2∣ ν ∣ − ν t + t ≤ 0 , which is impossible for ν ≠ ∅ \nu\ne\varnothing ν = ∅ (since ∣ ν ∣ ≥ ν t |\nu| \ge\nu_t ∣ ν ∣ ≥ ν t and t ≥ 1 t \ge1 t ≥ 1 ); for ν = ∅ \nu= \varnothing ν = ∅ we have Σ = N 0 ∋ d \Sigma= \mathbb{N}_0 \ni d Σ = N 0 ∋ d . If ∣ ν ∣ ≥ j |\nu| \ge j ∣ ν ∣ ≥ j , then d ≥ ∣ ν ∣ + r ≥ ν 1 + r d \ge|\nu| + r \ge\nu_1 + r d ≥ ∣ ν ∣ + r ≥ ν 1 + r , so d ∈ Σ ( ν ) d \in\Sigma(\nu) d ∈ Σ ( ν ) . This proves (1).
For (3): if d < 0 d < 0 d < 0 then ∣ ν ∣ + r ≤ 2 ∣ ν ∣ + r < j |\nu| + r \le2|\nu| + r < j ∣ ν ∣ + r ≤ 2∣ ν ∣ + r < j . Otherwise d = z t < ν 1 + r d = z_t < \nu_1 + r d = z t < ν 1 + r gives 2 ∣ ν ∣ − ν 1 < j 2|\nu| - \nu_1 < j 2∣ ν ∣ − ν 1 < j , and ∣ ν ∣ ≥ ν 1 + r − 1 |\nu| \ge\nu_1 + r - 1 ∣ ν ∣ ≥ ν 1 + r − 1 gives ∣ ν ∣ + r ≤ 2 ∣ ν ∣ − ν 1 + 1 ≤ j |\nu| + r \le2|\nu| - \nu_1 + 1 \le j ∣ ν ∣ + r ≤ 2∣ ν ∣ − ν 1 + 1 ≤ j .
Theorem 9.5. For all integers n ≥ 1 n \ge1 n ≥ 1 and g g g with n / 2 ≤ g ≤ n n/2 \le g \le n n /2 ≤ g ≤ n ,
PG ( n , g ) = p ( n − g ) − E ( 2 n − 3 g ) . \operatorname{PG}(n,g) = p(n-g) - E(2n-3g). PG ( n , g ) = p ( n − g ) − E ( 2 n − 3 g ) . Proof. Let k = n − g k = n-g k = n − g , so k ≤ g k \le g k ≤ g , and put j = 2 k − g = 2 n − 3 g j = 2k-g = 2n-3g j = 2 k − g = 2 n − 3 g .
Removing the first column is a bijection from partitions λ ⊢ n \lambda\vdash n λ ⊢ n with exactly g g g parts onto partitions μ ⊢ k \mu\vdash k μ ⊢ k with ℓ ( μ ) ≤ g \ell(\mu) \le g ℓ ( μ ) ≤ g ; the latter condition is automatic because ℓ ( μ ) ≤ k ≤ g \ell(\mu) \le k \le g ℓ ( μ ) ≤ k ≤ g . So there are p ( k ) p(k) p ( k ) candidates. Let A = ℓ ( μ ) A = \ell(\mu) A = ℓ ( μ ) , let ν \nu ν be μ \mu μ with its first column removed, and put s = ∣ ν ∣ = k − A s = |\nu| = k-A s = ∣ ν ∣ = k − A and r = ℓ ( ν ) ≤ A r = \ell(\nu) \le A r = ℓ ( ν ) ≤ A . Then
λ = ( ν 1 + 2 , … , ν r + 2 , 2 A − r , 1 g − A ) , \lambda= (\nu_1+2,\ldots,\nu_r+2,2^{A-r},1^{g-A}), λ = ( ν 1 + 2 , … , ν r + 2 , 2 A − r , 1 g − A ) , and λ \lambda λ is determined by ν \nu ν (given n n n and g g g ). A partition ν \nu ν arises in this way if and only if A = k − s ≥ r A = k-s \ge r A = k − s ≥ r , that is, ∣ ν ∣ + ℓ ( ν ) ≤ k |\nu| + \ell(\nu) \le k ∣ ν ∣ + ℓ ( ν ) ≤ k . We consider the following cases:
Case-I: A = g A = g A = g . Then k = g k = g k = g , μ = ( 1 g ) \mu= (1^g) μ = ( 1 g ) , ν = ∅ \nu= \varnothing ν = ∅ and λ = ( 2 g ) \lambda= (2^g) λ = ( 2 g ) . This has no part 1, so it does not correspond to a semigroup (Lemma 3.7 ), and it is counted by E ( j ) = E ( g ) E(j) = E(g) E ( j ) = E ( g ) because − g ∉ Σ ( ∅ ) -g \notin\Sigma(\varnothing) − g ∈ / Σ ( ∅ ) and g ≥ 1 g \ge1 g ≥ 1 .
Case-II: A < g A < g A < g . Then λ \lambda λ has g − A ≥ 1 g-A \ge1 g − A ≥ 1 parts equal to 1, and
C ( λ ) = 0 g − A 1 0 A − r w ( ν ) . C(\lambda) = 0^{g-A}1\,0^{A-r}w(\nu). C ( λ ) = 0 g − A 1 0 A − r w ( ν ) . So m = g − A + 1 m = g-A+1 m = g − A + 1 is the multiplicity, the positions m + 1 , … , T − 1 m+1,\ldots,T-1 m + 1 , … , T − 1 are gaps with
T = m + ( A − r ) + 1 = g − r + 2 , T = m+(A-r)+1 = g-r+2, T = m + ( A − r ) + 1 = g − r + 2 , and w ( ν ) w(\nu) w ( ν ) occupies the positions T , … , F T,\ldots,F T , … , F , where F = T + ν 1 + r − 1 = g + ν 1 + 1 F = T+\nu_1+r-1 = g+\nu_1+1 F = T + ν 1 + r − 1 = g + ν 1 + 1 . (If ν = ∅ \nu= \varnothing ν = ∅ , then F = T − 1 F = T-1 F = T − 1 .) The nonzero elements of S S S up to F F F are m m m and T + p T+p T + p for p ∈ Σ ( ν ) ∩ [ 0 , ν 1 + r − 1 ] p \in\Sigma(\nu) \cap[0,\nu_1+r-1] p ∈ Σ ( ν ) ∩ [ 0 , ν 1 + r − 1 ] . We check which sums of two such elements can be gaps.
Two elements ≥ T \ge T ≥ T : their sum is at least 2 T = 2 g − 2 r + 4 2T = 2g-2r+4 2 T = 2 g − 2 r + 4 . Since g ≥ k = s + A ≥ s + r g \ge k = s+A \ge s+r g ≥ k = s + A ≥ s + r and s ≥ ν 1 + r − 1 s \ge\nu_1+r-1 s ≥ ν 1 + r − 1 , we get g ≥ ν 1 + 2 r − 1 g \ge\nu_1+2r-1 g ≥ ν 1 + 2 r − 1 , and so 2 T ≥ g + ν 1 + 3 > F 2T \ge g+\nu_1+3 > F 2 T ≥ g + ν 1 + 3 > F .
The element m m m and an element ≥ T \ge T ≥ T : the sum is at least m + T = 2 g − k + s − r + 3 ≥ g + s − r + 3 m+T = 2g-k+s-r+3 \ge g+s-r+3 m + T = 2 g − k + s − r + 3 ≥ g + s − r + 3 (using k ≤ g k \le g k ≤ g ). Since s − r ≥ ν 1 − 1 s-r \ge\nu_1-1 s − r ≥ ν 1 − 1 , this exceeds F = g + ν 1 + 1 F = g+\nu_1+1 F = g + ν 1 + 1 .
The element m m m twice: 2 m = T + d 2m = T+d 2 m = T + d with
d = 2 m − T = 2 ( g − k + s + 1 ) − ( g − r + 2 ) = 2 s + r − ( 2 k − g ) = 2 ∣ ν ∣ + ℓ ( ν ) − j . d = 2m-T = 2(g-k+s+1)-(g-r+2) = 2s+r-(2k-g) = 2|\nu|+\ell(\nu)-j. d = 2 m − T = 2 ( g − k + s + 1 ) − ( g − r + 2 ) = 2 s + r − ( 2 k − g ) = 2∣ ν ∣ + ℓ ( ν ) − j . Thus S S S is a semigroup if and only if 2 m 2m 2 m is not a gap. If d < 0 d < 0 d < 0 , then m < 2 m < T m < 2m < T m < 2 m < T and 2 m 2m 2 m is a gap. If d ≥ 0 d \ge0 d ≥ 0 , then 2 m 2m 2 m is a gap if and only if d d d is the position of a zero of w ( ν ) w(\nu) w ( ν ) . The positions ≥ ν 1 + r \ge\nu_1+r ≥ ν 1 + r correspond to integers > F >F > F , which lie in S S S . So in all cases λ \lambda λ fails if and only if d ∉ Σ ( ν ) d \notin\Sigma(\nu) d ∈ / Σ ( ν ) .
The failing λ \lambda λ correspond bijectively to the partitions ν \nu ν with d ∉ Σ ( ν ) d \notin\Sigma(\nu) d ∈ / Σ ( ν ) that arise, specifically with ∣ ν ∣ + ℓ ( ν ) ≤ k |\nu|+\ell(\nu)\le k ∣ ν ∣ + ℓ ( ν ) ≤ k . By Lemma 9.4 -(3) every ν \nu ν counted by E ( j ) E(j) E ( j ) satisfies ∣ ν ∣ + ℓ ( ν ) ≤ j ≤ k |\nu|+\ell(\nu)\le j\le k ∣ ν ∣ + ℓ ( ν ) ≤ j ≤ k , so all of them arise. Therefore exactly E ( j ) E(j) E ( j ) candidates fail.
Proposition 9.6. The generating function of E E E is
∑ j ≥ 1 E ( j ) x j = x 1 − x ∏ i ≥ 1 1 1 − x 2 i + 1 + ∑ v ≥ 1 ∑ t ≥ 1 x ( 2 t − 1 ) v + t ( x 2 ; x 2 ) t − 1 ( x 2 ; x 2 ) v . \sum_{j\ge1} E(j)x^j=\frac{x}{1-x}\prod_{i\ge1}\frac{1}{1-x^{2i+1}}+\sum_{v\ge1}\sum_{t\ge1}\frac{x^{(2t-1)v+t}}{(x^2;x^2)_{t-1}(x^2;x^2)_v}. j ≥ 1 ∑ E ( j ) x j = 1 − x x i ≥ 1 ∏ 1 − x 2 i + 1 1 + v ≥ 1 ∑ t ≥ 1 ∑ ( x 2 ; x 2 ) t − 1 ( x 2 ; x 2 ) v x ( 2 t − 1 ) v + t . where ( q ; q ) s = ∏ i = 1 s ( 1 − q i ) (q;q)_s=\prod_{i=1}^{s}(1-q^i) ( q ; q ) s = ∏ i = 1 s ( 1 − q i ) .
Proof. We use Lemma 9.4-(2). Since 2 ∣ ν ∣ + ℓ ( ν ) = ∑ i ( 2 ν i + 1 ) 2|\nu|+\ell(\nu)=\sum_i(2\nu_i+1) 2∣ ν ∣ + ℓ ( ν ) = ∑ i ( 2 ν i + 1 ) , the generating function of 2 ∣ ν ∣ + ℓ ( ν ) 2|\nu|+\ell(\nu) 2∣ ν ∣ + ℓ ( ν ) over all ν \nu ν is ∏ i ≥ 1 ( 1 − x 2 i + 1 ) − 1 \prod_{i\ge1}(1-x^{2i+1})^{-1} ∏ i ≥ 1 ( 1 − x 2 i + 1 ) − 1 . Multiplying by x / ( 1 − x ) = ∑ j ≥ 1 x j x/(1-x)=\sum_{j\ge1}x^j x / ( 1 − x ) = ∑ j ≥ 1 x j counts, for each j j j , the partitions with 2 ∣ ν ∣ + ℓ ( ν ) < j 2|\nu|+\ell(\nu)<j 2∣ ν ∣ + ℓ ( ν ) < j . For the second term, fix t ≥ 1 t\ge1 t ≥ 1 and v = ν t ≥ 1 v=\nu_t\ge1 v = ν t ≥ 1 . The parts above row t t t are v + α 1 ≥ ⋯ ≥ v + α t − 1 v+\alpha_1\ge\cdots\ge v+\alpha_{t-1} v + α 1 ≥ ⋯ ≥ v + α t − 1 with α \alpha α a partition into at most t − 1 t-1 t − 1 parts. The parts below row t t t form a partition β \beta β with all parts ≤ v \le v ≤ v . Then
2 ∣ ν ∣ − ν t + t = 2 ( t − 1 ) v + 2 ∣ α ∣ + v + 2 ∣ β ∣ + t = ( 2 t − 1 ) v + t + 2 ∣ α ∣ + 2 ∣ β ∣ . 2|\nu|-\nu_t+t=2(t-1)v+2|\alpha|+v+2|\beta|+t=(2t-1)v+t+2|\alpha|+2|\beta|. 2∣ ν ∣ − ν t + t = 2 ( t − 1 ) v + 2∣ α ∣ + v + 2∣ β ∣ + t = ( 2 t − 1 ) v + t + 2∣ α ∣ + 2∣ β ∣. The generating functions of α \alpha α and β \beta β , weighted by x 2 ∣ ⋅ ∣ x^{2|\cdot|} x 2∣ ⋅ ∣ , are 1 / ( x 2 ; x 2 ) t − 1 1/(x^2;x^2)_{t-1} 1/ ( x 2 ; x 2 ) t − 1 and 1 / ( x 2 ; x 2 ) v 1/(x^2;x^2)_v 1/ ( x 2 ; x 2 ) v .
As the consequence of the preceding result we recover Theorems 1, 2, and 5 [5 ] , and provide the correct versions of Theorem 3 and Corollary 4.
Corollary 9.7.
PG ( n , g ) = p ( n − g ) \operatorname{PG}(n,g)=p(n-g) PG ( n , g ) = p ( n − g ) whenever 3 g ≥ 2 n 3g\ge2n 3 g ≥ 2 n [5 Theorem 1] . The bound is sharp: if n / 2 ≤ g < 2 n / 3 n/2\le g<2n/3 n /2 ≤ g < 2 n /3 , then PG ( n , g ) < p ( n − g ) \operatorname{PG}(n,g)<p(n-g) PG ( n , g ) < p ( n − g ) .
PG ( 3 n − i , 2 n − i ) = p ( n ) − E ( i ) \operatorname{PG}(3n-i,2n-i)=p(n)-E(i) PG ( 3 n − i , 2 n − i ) = p ( n ) − E ( i ) for n ≥ i n\ge i n ≥ i . Since E ( 1 ) = 1 E(1)=1 E ( 1 ) = 1 and E ( 2 ) = E ( 3 ) = 2 E(2)=E(3)=2 E ( 2 ) = E ( 3 ) = 2 , this gives [5 Theorem 2] .
PG ( 3 n + 2 − k , 2 n − k ) = p ( n + 2 ) − 4 − k = b ( n ) − k \operatorname{PG}(3n+2-k,2n-k)=p(n+2)-4-k=b(n)-k PG ( 3 n + 2 − k , 2 n − k ) = p ( n + 2 ) − 4 − k = b ( n ) − k for k = 0 , 1 , 2 k=0,1,2 k = 0 , 1 , 2 and n ≥ k + 2 n\ge k+2 n ≥ k + 2 . This corrects [5 Theorem 3, Corollary 4] , which state b ( n ) − ( k + 2 ) b(n)-(k+2) b ( n ) − ( k + 2 ) and p ( n + 2 ) − 6 − k p(n+2)-6-k p ( n + 2 ) − 6 − k .
PG ( 3 n + 2 − j , 2 n − j ) − PG ( 3 n − 1 − j , 2 n − 2 − j ) = p ˉ ( n + 2 ) \operatorname{PG}(3n+2-j,2n-j)-\operatorname{PG}(3n-1-j,2n-2-j)=\bar{p}(n+2) PG ( 3 n + 2 − j , 2 n − j ) − PG ( 3 n − 1 − j , 2 n − 2 − j ) = p ˉ ( n + 2 ) for n ≥ j + 3 n\ge j+3 n ≥ j + 3 , which is [5 Theorem 5] with the improved range n ≥ j + 3 n\ge j+3 n ≥ j + 3 in place of n ≥ j + 5 n\ge j+5 n ≥ j + 5 .
Proof. (1) If 3 g ≥ 2 n 3g\ge2n 3 g ≥ 2 n then 2 n − 3 g ≤ 0 2n-3g\le0 2 n − 3 g ≤ 0 and E = 0 E=0 E = 0 by Lemma 9.4-(1). If j = 2 n − 3 g ≥ 1 j=2n-3g\ge1 j = 2 n − 3 g ≥ 1 , then ν = ∅ \nu=\varnothing ν = ∅ is counted by E ( j ) E(j) E ( j ) (since − j < 0 -j<0 − j < 0 ), so E ( j ) ≥ 1 E(j)\ge1 E ( j ) ≥ 1 .
(2) For ( 3 n − i , 2 n − i ) (3n-i,2n-i) ( 3 n − i , 2 n − i ) we have 2 N − 3 g = i 2N-3g=i 2 N − 3 g = i , and g ≥ N / 2 g\ge N/2 g ≥ N /2 if and only if n ≥ i n\ge i n ≥ i . The values of E E E come from Table 3 . By hand, with d = 2 ∣ ν ∣ + ℓ ( ν ) − j d=2|\nu|+\ell(\nu)-j d = 2∣ ν ∣ + ℓ ( ν ) − j : E ( 1 ) E(1) E ( 1 ) counts only ∅ \varnothing ∅ (for ν = ( 1 ) \nu=(1) ν = ( 1 ) , d = 2 d=2 d = 2 is beyond w ( ( 1 ) ) = 10 w((1))=10 w (( 1 )) = 10 ). E ( 2 ) E(2) E ( 2 ) counts ∅ \varnothing ∅ and ( 1 ) (1) ( 1 ) (d = 1 d=1 d = 1 is the zero of 10 10 10 ); for ( 2 ) (2) ( 2 ) and ( 1 , 1 ) (1,1) ( 1 , 1 ) we get d = 3 , 4 d=3,4 d = 3 , 4 , beyond words of length 3. E ( 3 ) E(3) E ( 3 ) counts ∅ \varnothing ∅ and ( 2 ) (2) ( 2 ) (d = 2 d=2 d = 2 is the zero of w ( ( 2 ) ) = 110 w((2))=110 w (( 2 )) = 110 ), while ( 1 ) (1) ( 1 ) gives d = 0 ∈ Σ d=0\in\Sigma d = 0 ∈ Σ and ( 1 , 1 ) (1,1) ( 1 , 1 ) gives d = 3 d=3 d = 3 .
(3) Here 2 N − 3 g = k + 4 2N-3g=k+4 2 N − 3 g = k + 4 , and g ≥ N / 2 g\ge N/2 g ≥ N /2 if and only if n ≥ k + 2 n\ge k+2 n ≥ k + 2 . From Table 3 , E ( 4 ) = 4 E(4)=4 E ( 4 ) = 4 , E ( 5 ) = 5 E(5)=5 E ( 5 ) = 5 and E ( 6 ) = 6 E(6)=6 E ( 6 ) = 6 , so PG = p ( n + 2 ) − 4 − k \operatorname{PG}=p(n+2)-4-k PG = p ( n + 2 ) − 4 − k . Moreover b ( n ) = p ( n + 2 ) − 4 b(n)=p(n+2)-4 b ( n ) = p ( n + 2 ) − 4 : among the partitions of n + 2 n+2 n + 2 , exactly ( 1 n + 2 ) (1^{n+2}) ( 1 n + 2 ) and ( 2 , 1 n ) (2,1^n) ( 2 , 1 n ) have more than n n n parts, and exactly ( n + 2 ) (n+2) ( n + 2 ) and ( n + 1 , 1 ) (n+1,1) ( n + 1 , 1 ) have a part larger than n n n . In the proof of [5 Theorem 3] , the partitions { n + 2 , 2 , 2 , 1 2 n − k − 2 } \{n+2,2,2,1^{2n-k-2}\} { n + 2 , 2 , 2 , 1 2 n − k − 2 } and { n + 3 , 1 2 n − k − 1 } \{n+3,1^{2n-k-1}\} { n + 3 , 1 2 n − k − 1 } are removed from the domain of the map but not added back, although for n ≥ 7 n\ge7 n ≥ 7 they correspond to numerical semigroups (for instance, the second is a hook with d = n + 2 ≤ 2 n − k − 1 d=n+2\le2n-k-1 d = n + 2 ≤ 2 n − k − 1 , which is covered by Corollary 4.8).
(4) For both terms 2 N − 3 g = j + 4 2N-3g=j+4 2 N − 3 g = j + 4 , so the E E E -terms cancel, and p ( n + 2 ) − p ( n + 1 ) = p ˉ ( n + 2 ) p(n+2)-p(n+1)=\bar{p}(n+2) p ( n + 2 ) − p ( n + 1 ) = p ˉ ( n + 2 ) . The conditions g ≥ N / 2 g\ge N/2 g ≥ N /2 for the two terms are n ≥ j + 2 n\ge j+2 n ≥ j + 2 and n ≥ j + 3 n\ge j+3 n ≥ j + 3 .
Table 3. The exceptional-case functions E E E (genus) and H H H , h = H − 1 h=H-1 h = H − 1 (multiplicity).
Corollary 9.8. The exceptional-case functions of [5 Remark 1] are given by
h 1 ( i ) = p ( n ) − PG ( 3 n − i , 2 n − i ) = E ( i ) ( n ≥ i ) , h_1(i)=p(n)-\operatorname{PG}(3n-i,2n-i)=E(i) \qquad(n\ge i), h 1 ( i ) = p ( n ) − PG ( 3 n − i , 2 n − i ) = E ( i ) ( n ≥ i ) , h 2 ( i ) = b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) = E ( i + 4 ) − 4 ( n ≥ i + 2 ) , h_2(i)=b(n)-\operatorname{PG}(3n+2-i,2n-i)=E(i+4)-4 \qquad(n\ge i+2), h 2 ( i ) = b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) = E ( i + 4 ) − 4 ( n ≥ i + 2 ) , and they are independent of n n n . More generally, for any line PG ( L 1 ( n ) − k , L 2 ( n ) − k ) \operatorname{PG}(L_1(n)-k,L_2(n)-k) PG ( L 1 ( n ) − k , L 2 ( n ) − k ) with 2 L 2 ( n ) − k ≥ L 1 ( n ) 2L_2(n)-k\ge L_1(n) 2 L 2 ( n ) − k ≥ L 1 ( n ) , we have
p ( L 1 ( n ) − L 2 ( n ) ) − PG ( L 1 ( n ) − k , L 2 ( n ) − k ) = E ( 2 L 1 ( n ) − 3 L 2 ( n ) + k ) . p(L_1(n)-L_2(n))-\operatorname{PG}(L_1(n)-k,L_2(n)-k)=E(2L_1(n)-3L_2(n)+k). p ( L 1 ( n ) − L 2 ( n )) − PG ( L 1 ( n ) − k , L 2 ( n ) − k ) = E ( 2 L 1 ( n ) − 3 L 2 ( n ) + k ) . Proof. All three identities are Theorem 9.5 with the stated arguments. For the second, use b ( n ) = p ( n + 2 ) − 4 b(n)=p(n+2)-4 b ( n ) = p ( n + 2 ) − 4 from Corollary 9.7-(3).
Multiplicity
Definition 9.9. For i ≥ 0 i \ge0 i ≥ 0 , let
H ( i ) = # { κ a partition : ∣ κ ∣ ≤ i , i − ∣ κ ∣ ∈ Σ ( κ ) + Σ ( κ ) } , H(i)=\#\{\kappa\text{ a partition}:|\kappa|\le i,\ i-|\kappa|\in\Sigma(\kappa)+\Sigma(\kappa)\}, H ( i ) = # { κ a partition : ∣ κ ∣ ≤ i , i − ∣ κ ∣ ∈ Σ ( κ ) + Σ ( κ )} , and set H ( i ) = 0 H(i)=0 H ( i ) = 0 for i < 0 i<0 i < 0 . The empty partition contributes to H ( i ) H(i) H ( i ) for every i ≥ 0 i\ge0 i ≥ 0 .
Theorem 9.10. For all integers m ≥ 2 m\ge2 m ≥ 2 and n ≥ m − 1 n\ge m-1 n ≥ m − 1 with 3 m > n 3m>n 3 m > n ,
PM ( n , m ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) . \operatorname{PM}(n,m)=\bar{p}(n-m+1)-H(n-2m). PM ( n , m ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) .
Proof. If n = m − 1 n=m-1 n = m − 1 , the only candidate is λ = ( 1 m − 1 ) \lambda=(1^{m-1}) λ = ( 1 m − 1 ) , which corresponds to ⟨ m , m + 1 , … , 2 m − 1 ⟩ \langle m,m+1,\ldots,2m-1\rangle ⟨ m , m + 1 , … , 2 m − 1 ⟩ , and p ˉ ( 0 ) = 1 \bar{p}(0)=1 p ˉ ( 0 ) = 1 ; if n = m n=m n = m , no such λ \lambda λ exists and p ˉ ( 1 ) = 0 \bar{p}(1)=0 p ˉ ( 1 ) = 0 . So assume n ≥ m + 1 n\ge m+1 n ≥ m + 1 . Put i = n − 2 m i=n-2m i = n − 2 m and R = n − m + 1 R=n-m+1 R = n − m + 1 .
A partition of n n n with exactly m − 1 m-1 m − 1 parts equal to 1 is λ = ( ρ , 1 m − 1 ) \lambda=(\rho,1^{m-1}) λ = ( ρ , 1 m − 1 ) with ρ ⊢ R \rho\vdash R ρ ⊢ R having no part 1; there are p ˉ ( R ) \bar{p}(R) p ˉ ( R ) of them. Writing ρ = ( t + 1 , κ 1 + 1 , … , κ r + 1 ) \rho=(t+1,\kappa_1+1,\ldots,\kappa_r+1) ρ = ( t + 1 , κ 1 + 1 , … , κ r + 1 ) gives a bijection between such ρ \rho ρ and pairs ( t , κ ) (t,\kappa) ( t , κ ) with t ≥ κ 1 t\ge\kappa_1 t ≥ κ 1 and t + 1 + ∣ κ ∣ + r = R t+1+|\kappa|+r=R t + 1 + ∣ κ ∣ + r = R . Each λ \lambda λ has the shape (1), and
e = t + r − m = ( R − 1 − ∣ κ ∣ − r ) + r − m = i − ∣ κ ∣ . e=t+r-m=(R-1-|\kappa|-r)+r-m=i-|\kappa|. e = t + r − m = ( R − 1 − ∣ κ ∣ − r ) + r − m = i − ∣ κ ∣.
Given κ \kappa κ , the value of t t t is determined, and κ \kappa κ arises if and only if t = m + e − r ≥ κ 1 t=m+e-r\ge\kappa_1 t = m + e − r ≥ κ 1 .
If ∣ κ ∣ > i |\kappa|>i ∣ κ ∣ > i , then e < 0 e<0 e < 0 and λ \lambda λ corresponds to a semigroup by Lemma 9.1-(1). Let ∣ κ ∣ ≤ i |\kappa|\le i ∣ κ ∣ ≤ i . Since 3 m ≥ n + 1 3m\ge n+1 3 m ≥ n + 1 we have i ≤ m − 1 i\le m-1 i ≤ m − 1 , so κ 1 + r ≤ ∣ κ ∣ + 1 ≤ m \kappa_1+r\le|\kappa|+1\le m κ 1 + r ≤ ∣ κ ∣ + 1 ≤ m (using ∣ κ ∣ ≥ κ 1 + r − 1 |\kappa|\ge\kappa_1+r-1 ∣ κ ∣ ≥ κ 1 + r − 1 ). Therefore Lemma 9.1-(2),(3) apply, and λ \lambda λ fails if and only if i − ∣ κ ∣ ∈ Σ ( κ ) + Σ ( κ ) i-|\kappa|\in\Sigma(\kappa)+\Sigma(\kappa) i − ∣ κ ∣ ∈ Σ ( κ ) + Σ ( κ ) . Moreover every such κ \kappa κ arises, since t = m + e − r ≥ m − r ≥ κ 1 t=m+e-r\ge m-r\ge\kappa_1 t = m + e − r ≥ m − r ≥ κ 1 .
Thus the failing λ \lambda λ are in bijection with the partitions counted by H ( i ) H(i) H ( i ) . □ \square □
Theorem 9.11. For every m ≥ 2 m\ge2 m ≥ 2 ,
PM ( 3 m , m ) = p ˉ ( 2 m + 1 ) − H ( m ) + m . \operatorname{PM}(3m,m)=\bar{p}(2m+1)-H(m)+m. PM ( 3 m , m ) = p ˉ ( 2 m + 1 ) − H ( m ) + m .
In particular Theorem 9.10 fails at n = 3 m n=3m n = 3 m , and the range 3 m > n 3m>n 3 m > n is sharp.
Proof. Now i = m i=m i = m and R = 2 m + 1 R=2m+1 R = 2 m + 1 , and we reuse the parametrisation from the proof of Theorem 9.10. Partitions κ \kappa κ with ∣ κ ∣ > m |\kappa|>m ∣ κ ∣ > m give semigroups, as before. Let ∣ κ ∣ ≤ m |\kappa|\le m ∣ κ ∣ ≤ m , so e = m − ∣ κ ∣ ≥ 0 e=m-|\kappa|\ge0 e = m − ∣ κ ∣ ≥ 0 . Then κ \kappa κ arises if and only if t = 2 m − ∣ κ ∣ − r ≥ κ 1 t=2m-|\kappa|-r\ge\kappa_1 t = 2 m − ∣ κ ∣ − r ≥ κ 1 , that is, κ 1 + r + ∣ κ ∣ ≤ 2 m \kappa_1+r+|\kappa|\le2m κ 1 + r + ∣ κ ∣ ≤ 2 m . Since κ 1 + r ≤ ∣ κ ∣ + 1 \kappa_1+r\le|\kappa|+1 κ 1 + r ≤ ∣ κ ∣ + 1 , with equality exactly for hooks, this fails precisely when ∣ κ ∣ = m |\kappa|=m ∣ κ ∣ = m and κ \kappa κ is a hook. There are exactly m m m hooks of size m m m . For every other κ \kappa κ with ∣ κ ∣ ≤ m |\kappa|\le m ∣ κ ∣ ≤ m we have κ 1 + r ≤ m \kappa_1+r\le m κ 1 + r ≤ m , so Lemma 9.1-(2),(3) apply exactly as before.
Therefore the failing λ \lambda λ correspond to the κ \kappa κ counted by H ( m ) H(m) H ( m ) , except the m m m hooks of size m m m , which do not arise. Each of these hooks is counted by H ( m ) H(m) H ( m ) , because e = 0 ∈ Σ ( κ ) + Σ ( κ ) e=0\in\Sigma(\kappa)+\Sigma(\kappa) e = 0 ∈ Σ ( κ ) + Σ ( κ ) . Therefore the number of failures is H ( m ) − m H(m)-m H ( m ) − m . □ \square □
Theorem 9.12. For every m ≥ 2 m\ge2 m ≥ 2 ,
PM ( 3 m + 1 , m ) = p ˉ ( 2 m + 2 ) − H ( m + 1 ) + m . \operatorname{PM}(3m+1,m)=\bar{p}(2m+2)-H(m+1)+m. PM ( 3 m + 1 , m ) = p ˉ ( 2 m + 2 ) − H ( m + 1 ) + m .
Proof. Now i = m + 1 i=m+1 i = m + 1 and R = 2 m + 2 R=2m+2 R = 2 m + 2 , and we again use the parametrisation ρ ↔ ( t , κ ) \rho\leftrightarrow(t,\kappa) ρ ↔ ( t , κ ) from the proof of Theorem 9.10, with e = m + 1 − ∣ κ ∣ e=m+1-|\kappa| e = m + 1 − ∣ κ ∣ and t = m + e − r t=m+e-r t = m + e − r . Partitions κ \kappa κ with ∣ κ ∣ > m + 1 |\kappa|>m+1 ∣ κ ∣ > m + 1 have e < 0 e<0 e < 0 and give semigroups. Let ∣ κ ∣ ≤ m + 1 |\kappa|\le m+1 ∣ κ ∣ ≤ m + 1 . Then κ \kappa κ arises if and only if t ≥ κ 1 t\ge\kappa_1 t ≥ κ 1 , that is,
κ 1 + r + ∣ κ ∣ ≤ 2 m + 1. \kappa_1+r+|\kappa|\le2m+1. κ 1 + r + ∣ κ ∣ ≤ 2 m + 1.
Recall that κ 1 + r ≤ ∣ κ ∣ + 1 \kappa_1+r\le|\kappa|+1 κ 1 + r ≤ ∣ κ ∣ + 1 , with equality exactly for hooks, and that ∣ κ ∣ − ( κ 1 + r − 1 ) |\kappa|-(\kappa_1+r-1) ∣ κ ∣ − ( κ 1 + r − 1 ) is the number of cells of κ \kappa κ outside its first row and first column. We sort the partitions with ∣ κ ∣ ≤ m + 1 |\kappa|\le m+1 ∣ κ ∣ ≤ m + 1 into four classes. (a) Not arising. The displayed inequality fails exactly when ∣ κ ∣ = m + 1 |\kappa|=m+1 ∣ κ ∣ = m + 1 and κ 1 + r ≥ m + 1 \kappa_1+r\ge m+1 κ 1 + r ≥ m + 1 . These are the m + 1 m+1 m + 1 hooks of size m + 1 m+1 m + 1 , and the m − 2 m-2 m − 2 partitions ( a , 2 , 1 b ) (a,2,1^b) ( a , 2 , 1 b ) with a ≥ 2 a\ge2 a ≥ 2 and a + b = m − 1 a+b=m-1 a + b = m − 1 (one cell outside the first row and column). For all of them e = 0 ∈ Σ ( κ ) + Σ ( κ ) e=0\in\Sigma(\kappa)+\Sigma(\kappa) e = 0 ∈ Σ ( κ ) + Σ ( κ ) , so all 2 m − 1 2m-1 2 m − 1 are counted by H ( m + 1 ) H(m+1) H ( m + 1 ) although they do not arise.
(b) Arising with κ 1 + r ≤ m \kappa_1+r\le m κ 1 + r ≤ m . Here m ≥ κ 1 + r m\ge\kappa_1+r m ≥ κ 1 + r , and Lemma 9.1 -(2),(3) show that λ \lambda λ fails if and only if e ∈ Σ ( κ ) + Σ ( κ ) e\in\Sigma(\kappa)+\Sigma(\kappa) e ∈ Σ ( κ ) + Σ ( κ ) , exactly as counted by H ( m + 1 ) H(m+1) H ( m + 1 ) .
(c) Arising with κ 1 + r ≥ m + 1 \kappa_1+r\ge m+1 κ 1 + r ≥ m + 1 . Since ∣ κ ∣ ≤ m + 1 |\kappa|\le m+1 ∣ κ ∣ ≤ m + 1 , and the case ∣ κ ∣ = m + 1 |\kappa|=m+1 ∣ κ ∣ = m + 1 belongs to (a), this forces ∣ κ ∣ = m |\kappa|=m ∣ κ ∣ = m and κ \kappa κ a hook, κ = ( m − s , 1 s ) \kappa=(m-s,1^s) κ = ( m − s , 1 s ) with 0 ≤ s ≤ m − 1 0\le s\le m-1 0 ≤ s ≤ m − 1 , and then e = 1 e=1 e = 1 . For s = 0 s=0 s = 0 , 1 ∈ Σ ( ( m ) ) 1\in\Sigma((m)) 1 ∈ Σ (( m )) , so λ \lambda λ fails by Lemma 9.1 -(2), and it is counted by H ( m + 1 ) H(m+1) H ( m + 1 ) . For s ≥ 1 s\ge1 s ≥ 1 , Σ ( κ ) = { 0 } ∪ [ s + 1 , m − 1 ] ∪ [ m + 1 , ∞ ) \Sigma(\kappa)=\{0\}\cup[s+1,m-1]\cup[m+1,\infty) Σ ( κ ) = { 0 } ∪ [ s + 1 , m − 1 ] ∪ [ m + 1 , ∞ ) (see the proof of Lemma 9.16), so 1 ∉ Σ ( κ ) + Σ ( κ ) 1\notin\Sigma(\kappa)+\Sigma(\kappa) 1 ∈ / Σ ( κ ) + Σ ( κ ) and H ( m + 1 ) H(m+1) H ( m + 1 ) does not count κ \kappa κ . Nevertheless λ \lambda λ fails: the last letter of w ( κ ) w(\kappa) w ( κ ) is a 0 0 0 at position κ 1 + r − 1 = m \kappa_1+r-1=m κ 1 + r − 1 = m , so 2 m = m + m 2m=m+m 2 m = m + m is a gap while m ∈ S m\in S m ∈ S . This gives m − 1 m-1 m − 1 failures not counted by H ( m + 1 ) H(m+1) H ( m + 1 ) .
The number of failures is therefore H ( m + 1 ) − ( 2 m − 1 ) + ( m − 1 ) = H ( m + 1 ) − m H(m+1)-(2m-1)+(m-1)=H(m+1)-m H ( m + 1 ) − ( 2 m − 1 ) + ( m − 1 ) = H ( m + 1 ) − m , and PM ( 3 m + 1 , m ) = p ˉ ( 2 m + 2 ) − H ( m + 1 ) + m \operatorname{PM}(3m+1,m)=\bar p(2m+2)-H(m+1)+m PM ( 3 m + 1 , m ) = p ˉ ( 2 m + 2 ) − H ( m + 1 ) + m .
In the following result, we recover and obtain the correct versions of some results discussed in [5 ] , Section 5.
Corollary 9.13. Put h ( i ) = H ( i ) − 1 h(i)=H(i)-1 h ( i ) = H ( i ) − 1 . Since a ( n + 1 ) = p ˉ ( n + 1 ) − 1 a(n+1)=\bar p(n+1)-1 a ( n + 1 ) = p ˉ ( n + 1 ) − 1 , we have a ( n + 1 ) − PM ( 2 n − i , n − i ) = h ( i ) a(n+1)-\operatorname{PM}(2n-i,n-i)=h(i) a ( n + 1 ) − PM ( 2 n − i , n − i ) = h ( i ) whenever n ≥ 2 i + 1 n\ge2i+1 n ≥ 2 i + 1 .
If m > n / 2 m>n/2 m > n /2 (with m ≥ 2 m\ge2 m ≥ 2 and n ≥ m − 1 n\ge m-1 n ≥ m − 1 ), then PM ( n , m ) = p ˉ ( n + 1 − m ) \operatorname{PM}(n,m)=\bar p(n+1-m) PM ( n , m ) = p ˉ ( n + 1 − m ) [5 Proposition 9] .
PM ( 2 n − i , n − i ) = a ( n + 1 ) − h ( i ) \operatorname{PM}(2n-i,n-i)=a(n+1)-h(i) PM ( 2 n − i , n − i ) = a ( n + 1 ) − h ( i ) for n ≥ 2 i + 1 n\ge2i+1 n ≥ 2 i + 1 , with h ( 0 ) , h ( 1 ) , h ( 2 ) , h ( 3 ) = 0 , 1 , 2 , 5 h(0),h(1),h(2),h(3)=0,1,2,5 h ( 0 ) , h ( 1 ) , h ( 2 ) , h ( 3 ) = 0 , 1 , 2 , 5 . This is [5 Theorem 10] . For i = 3 i=3 i = 3 the correct range is n ≥ 7 n\ge7 n ≥ 7 : at n = 6 n=6 n = 6 we have 3 m = n 3m=n 3 m = n , and Theorem 9.11 gives PM ( 9 , 3 ) = a ( 7 ) − 5 + 3 = a ( 7 ) − 2 \operatorname{PM}(9,3)=a(7)-5+3=a(7)-2 PM ( 9 , 3 ) = a ( 7 ) − 5 + 3 = a ( 7 ) − 2 . At n = 5 n=5 n = 5 , direct computation gives PM ( 7 , 2 ) = 0 = a ( 6 ) − 3 \operatorname{PM}(7,2)=0=a(6)-3 PM ( 7 , 2 ) = 0 = a ( 6 ) − 3 .
PM ( 2 n − j , n − j ) − PM ( 2 ( n − 1 ) − j , ( n − 1 ) − j ) = p ˉ ( n + 1 ) − p ˉ ( n ) = a ˉ ( n + 1 ) \operatorname{PM}(2n-j,n-j)-\operatorname{PM}(2(n-1)-j,(n-1)-j)=\bar p(n+1)-\bar p(n)=\bar a(n+1) PM ( 2 n − j , n − j ) − PM ( 2 ( n − 1 ) − j , ( n − 1 ) − j ) = p ˉ ( n + 1 ) − p ˉ ( n ) = a ˉ ( n + 1 ) for n ≥ 2 j + 2 n\ge2j+2 n ≥ 2 j + 2 [5 Theorem 12, Corollary 13] .
PM ( 3 j + 2 , j + 1 ) − PM ( 3 j , j ) = a ˉ ( 2 j + 2 ) − j \operatorname{PM}(3j+2,j+1)-\operatorname{PM}(3j,j)=\bar a(2j+2)-j PM ( 3 j + 2 , j + 1 ) − PM ( 3 j , j ) = a ˉ ( 2 j + 2 ) − j for j ≥ 2 j\ge2 j ≥ 2 [5 Theorem 14] .
PM ( 3 j , j ) − PM ( 3 j − 2 , j − 1 ) = a ˉ ( 2 j + 1 ) + 1 \operatorname{PM}(3j,j)-\operatorname{PM}(3j-2,j-1)=\bar a(2j+1)+1 PM ( 3 j , j ) − PM ( 3 j − 2 , j − 1 ) = a ˉ ( 2 j + 1 ) + 1 for j ≥ 3 j\ge3 j ≥ 3 [5 Theorem 15] .
Proof. (1) If m > n / 2 m>n/2 m > n /2 , then i < 0 i<0 i < 0 , so H ( i ) = 0 H(i)=0 H ( i ) = 0 , and 3 m > n 3m>n 3 m > n .
(2) For ( 2 n − i , n − i ) (2n-i,n-i) ( 2 n − i , n − i ) the condition 3 m > n 3m>n 3 m > n reads n > 2 i n>2i n > 2 i . The values H ( 0 ) , … , H ( 3 ) = 1 , 2 , 3 , 6 H(0),\ldots,H(3)=1,2,3,6 H ( 0 ) , … , H ( 3 ) = 1 , 2 , 3 , 6 are computed directly from Definition 9.9 ; for example, H ( 1 ) H(1) H ( 1 ) counts ∅ \varnothing ∅ (as 1 ∈ N 0 1\in\mathbb{N}_0 1 ∈ N 0 ) and ( 1 ) (1) ( 1 ) (as 0 ∈ Σ ( κ ) + Σ ( κ ) 0\in\Sigma(\kappa)+\Sigma(\kappa) 0 ∈ Σ ( κ ) + Σ ( κ ) ). For n = 5 n=5 n = 5 : a partition of 7 7 7 with exactly one part 1 1 1 has a unique smallest part, so by Theorem 4.5 it corresponds to a semigroup only if it is a staircase ( κ , … , 2 , 1 ) (\kappa,\ldots,2,1) ( κ , … , 2 , 1 ) of size 7 7 7 ; there is none, so PM ( 7 , 2 ) = 0 = a ( 6 ) − 3 \operatorname{PM}(7,2)=0=a(6)-3 PM ( 7 , 2 ) = 0 = a ( 6 ) − 3 .
(3) Both terms have i = j i=j i = j , so the H H H -terms cancel. For n ≥ 2 n\ge2 n ≥ 2 the partitions of n + 1 n+1 n + 1 with no part 1 1 1 split into those with ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 and λ 1 = λ 2 \lambda_1=\lambda_2 λ 1 = λ 2 , counted by a ˉ ( n + 1 ) \bar a(n+1) a ˉ ( n + 1 ) , and those with λ 1 > λ 2 \lambda_1>\lambda_2 λ 1 > λ 2 (or ℓ = 1 \ell=1 ℓ = 1 ). Subtracting 1 1 1 from the largest part maps the latter bijectively onto the partitions of n n n with no part 1 1 1 ; the inverse adds 1 1 1 to the largest part. Thus p ˉ ( n + 1 ) − p ˉ ( n ) = a ˉ ( n + 1 ) \bar p(n+1)-\bar p(n)=\bar a(n+1) p ˉ ( n + 1 ) − p ˉ ( n ) = a ˉ ( n + 1 ) (compare [5 Corollary 13] ). The condition 3 m > n 3m>n 3 m > n for the second term reads n ≥ 2 j + 2 n\ge2j+2 n ≥ 2 j + 2 .
(4) Since 3 ( j + 1 ) > 3 j + 2 3(j+1)>3j+2 3 ( j + 1 ) > 3 j + 2 , Theorem 9.10 gives PM ( 3 j + 2 , j + 1 ) = p ˉ ( 2 j + 2 ) − H ( j ) \operatorname{PM}(3j+2,j+1)=\bar p(2j+2)-H(j) PM ( 3 j + 2 , j + 1 ) = p ˉ ( 2 j + 2 ) − H ( j ) , and Theorem 9.11 gives PM ( 3 j , j ) = p ˉ ( 2 j + 1 ) − H ( j ) + j \operatorname{PM}(3j,j)=\bar p(2j+1)-H(j)+j PM ( 3 j , j ) = p ˉ ( 2 j + 1 ) − H ( j ) + j . Subtract, and use (3).
(5) Theorem 9.11 gives PM ( 3 j , j ) = p ˉ ( 2 j + 1 ) − H ( j ) + j \operatorname{PM}(3j,j)=\bar p(2j+1)-H(j)+j PM ( 3 j , j ) = p ˉ ( 2 j + 1 ) − H ( j ) + j , and Theorem 9.12 with m = j − 1 m=j-1 m = j − 1 gives PM ( 3 j − 2 , j − 1 ) = p ˉ ( 2 j ) − H ( j ) + j − 1 \operatorname{PM}(3j-2,j-1)=\bar p(2j)-H(j)+j-1 PM ( 3 j − 2 , j − 1 ) = p ˉ ( 2 j ) − H ( j ) + j − 1 . Subtract, and use (3).
The following presents an answer to [5 Remark 4] .
Corollary 9.14. The function asked for in [5 Remark 4] is h ( i ) = H ( i ) − 1 h(i)=H(i)-1 h ( i ) = H ( i ) − 1 , valid for n ≥ 2 i + 1 n\ge2i+1 n ≥ 2 i + 1 . Its first values are listed in Table 3 .
Proof. This is Corollary 9.13-(2), Theorem 9.10 applied to ( 2 n − i , n − i ) (2n-i,n-i) ( 2 n − i , n − i ) gives PM ( 2 n − i , n − i ) = p ˉ ( n + 1 ) − H ( i ) = a ( n + 1 ) − ( H ( i ) − 1 ) \operatorname{PM}(2n-i,n-i)=\bar{p}(n+1)-H(i)=a(n+1)-(H(i)-1) PM ( 2 n − i , n − i ) = p ˉ ( n + 1 ) − H ( i ) = a ( n + 1 ) − ( H ( i ) − 1 ) whenever 3 ( n − i ) > 2 n − i 3(n-i)>2n-i 3 ( n − i ) > 2 n − i , that is, n ≥ 2 i + 1 n\ge2i+1 n ≥ 2 i + 1 .
Frobenius number
For a partition π \pi π put c π = π 1 + ℓ ( π ) c_\pi=\pi_1+\ell(\pi) c π = π 1 + ℓ ( π ) (so c ∅ = 0 c_{\varnothing}=0 c ∅ = 0 ), and for ε ∈ { 0 , 1 } \varepsilon\in\{0,1\} ε ∈ { 0 , 1 } let
G π ( ε ) = # { e : 0 ≤ e < c π , e ≡ ε ( m o d 2 ) , e ∉ Σ ( π ) + Σ ( π ) } . G_\pi(\varepsilon)=\#\{e: 0\le e<c_\pi,\ e\equiv\varepsilon\pmod{2},\ e\notin\Sigma(\pi)+\Sigma(\pi)\}. G π ( ε ) = # { e : 0 ≤ e < c π , e ≡ ε ( mod 2 ) , e ∈ / Σ ( π ) + Σ ( π )} .
Theorem 9.15. For all integers k ≥ 0 k\ge0 k ≥ 0 and n ≥ 4 k + 1 n\ge4k+1 n ≥ 4 k + 1 ,
PF ( n , n − k ) = ∑ π ⊢ k ( ⌈ n − k 2 ⌉ − c π + G π ( n − k ) ) = p ( k ) ⌈ n − k 2 ⌉ − C k ( n − k ) , \operatorname{PF}(n,n-k)=\sum_{\pi\vdash k}\left(\left\lceil\frac{n-k}{2}\right\rceil-c_\pi+G_\pi(n-k)\right)=p(k)\left\lceil\frac{n-k}{2}\right\rceil-C_k(n-k), PF ( n , n − k ) = π ⊢ k ∑ ( ⌈ 2 n − k ⌉ − c π + G π ( n − k ) ) = p ( k ) ⌈ 2 n − k ⌉ − C k ( n − k ) ,
where C k ( ε ) = ∑ π ⊢ k ( c π − G π ( ε ) ) C_k(\varepsilon)=\sum_{\pi\vdash k}(c_\pi-G_\pi(\varepsilon)) C k ( ε ) = ∑ π ⊢ k ( c π − G π ( ε )) depends only on k k k and on the parity of n − k n-k n − k (Table 4).
Proof. Let λ ⊢ n \lambda\vdash n λ ⊢ n have h ( 1 , 1 ) ( λ ) = n − k h_{(1,1)}(\lambda)=n-k h ( 1 , 1 ) ( λ ) = n − k . Let t = λ 1 − 1 t=\lambda_1-1 t = λ 1 − 1 be its arm and b = ℓ ( λ ) − 1 b=\ell(\lambda)-1 b = ℓ ( λ ) − 1 its leg, so t + b + 1 = n − k t+b+1=n-k t + b + 1 = n − k . The cells outside the first row and the first column form the partition π = ( λ 2 − 1 , … , λ ℓ − 1 ) \pi=(\lambda_2-1,\ldots,\lambda_\ell-1) π = ( λ 2 − 1 , … , λ ℓ − 1 ) (zeros omitted), with ∣ π ∣ = k |\pi|=k ∣ π ∣ = k , r = ℓ ( π ) ≤ b r=\ell(\pi)\le b r = ℓ ( π ) ≤ b and π 1 ≤ t \pi_1\le t π 1 ≤ t . Conversely every triple ( t , b , π ) (t,b,\pi) ( t , b , π ) with π ⊢ k \pi\vdash k π ⊢ k , t ≥ π 1 t\ge\pi_1 t ≥ π 1 , b ≥ r b\ge r b ≥ r and t + b = n − k − 1 t+b=n-k-1 t + b = n − k − 1 arises from exactly one λ = ( t + 1 , π 1 + 1 , … , π r + 1 , 1 b − r ) \lambda=(t+1,\pi_1+1,\ldots,\pi_r+1,1^{b-r}) λ = ( t + 1 , π 1 + 1 , … , π r + 1 , 1 b − r ) . This λ \lambda λ can correspond to a semigroup only if it has a part 1, i.e. b ≥ r + 1 b\ge r+1 b ≥ r + 1 . (For k = 0 k=0 k = 0 and n = 1 n=1 n = 1 the only partition is λ = ( 1 ) \lambda=(1) λ = ( 1 ) , which corresponds to N 0 ∖ { 1 } \mathbb{N}_0\setminus\{1\} N 0 ∖ { 1 } , in agreement with ⌈ 1 / 2 ⌉ = 1 \lceil1/2\rceil=1 ⌈ 1/2 ⌉ = 1 ; from now on we assume n − k ≥ 2 n-k\ge2 n − k ≥ 2 .) In that case it has the shape (1) with κ = π \kappa=\pi κ = π and m = b − r + 1 ≥ 2 m=b-r+1\ge2 m = b − r + 1 ≥ 2 , and
e = t + r − m = n − k − 2 − 2 b + 2 r , m = n − k − e 2 . e=t+r-m=n-k-2-2b+2r,\qquad m=\frac{n-k-e}{2}. e = t + r − m = n − k − 2 − 2 b + 2 r , m = 2 n − k − e .
For fixed π \pi π , as b b b runs from r + 1 r+1 r + 1 to n − k − 1 − π 1 n-k-1-\pi_1 n − k − 1 − π 1 (the upper limit is t ≥ π 1 t\ge\pi_1 t ≥ π 1 ), e e e runs through all integers e ≡ n − k ( m o d 2 ) e\equiv n-k\pmod{2} e ≡ n − k ( mod 2 ) in the interval
I π = [ − ( n − k ) + 2 c π , n − k − 4 ] . I_\pi=\left[-(n-k)+2c_\pi,\ n-k-4\right]. I π = [ − ( n − k ) + 2 c π , n − k − 4 ] .
By Lemma 9.1, the classification of e ∈ I π e\in I_\pi e ∈ I π is given as follows.
(i) e < 0 e<0 e < 0 : semigroup. The number of such e e e of the right parity in I π I_\pi I π is ⌈ ( n − k ) / 2 ⌉ − c π \lceil(n-k)/2\rceil-c_\pi ⌈( n − k ) /2 ⌉ − c π . Indeed, they are − ( n − k ) + 2 c π + 2 s -(n-k)+2c_\pi+2s − ( n − k ) + 2 c π + 2 s for 0 ≤ s ≤ ( n − k − 2 c π − 1 ) / 2 0\le s\le(n-k-2c_\pi-1)/2 0 ≤ s ≤ ( n − k − 2 c π − 1 ) /2 , and ⌊ ( n − k − 1 ) / 2 ⌋ + 1 = ⌈ ( n − k ) / 2 ⌉ \lfloor(n-k-1)/2\rfloor+1=\lceil(n-k)/2\rceil ⌊( n − k − 1 ) /2 ⌋ + 1 = ⌈( n − k ) /2 ⌉ . This needs n − k ≥ 2 c π n-k\ge2c_\pi n − k ≥ 2 c π , which holds because c π ≤ k + 1 c_\pi\le k+1 c π ≤ k + 1 and n ≥ 4 k + 1 n\ge4k+1 n ≥ 4 k + 1 (for k = 0 k=0 k = 0 , c π = 0 c_\pi=0 c π = 0 ).
(ii) e ≥ c π e\ge c_\pi e ≥ c π : failure, by Lemma 9.1(2), because e ∈ Σ ( π ) ⊆ Σ ( π ) + Σ ( π ) e\in\Sigma(\pi)\subseteq\Sigma(\pi)+\Sigma(\pi) e ∈ Σ ( π ) ⊆ Σ ( π ) + Σ ( π ) (Lemma 3.16).
(iii) 0 ≤ e < c π 0\le e<c_\pi 0 ≤ e < c π : failure if e ∈ Σ ( π ) + Σ ( π ) e\in\Sigma(\pi)+\Sigma(\pi) e ∈ Σ ( π ) + Σ ( π ) , and a semigroup otherwise, provided m ≥ c π m\ge c_\pi m ≥ c π (Lemma 9.1(3)). For these e e e we have m = ( n − k − e ) / 2 ≥ ⌈ ( n − k − c π + 1 ) / 2 ⌉ m=(n-k-e)/2\ge\lceil(n-k-c_\pi+1)/2\rceil m = ( n − k − e ) /2 ≥ ⌈( n − k − c π + 1 ) /2 ⌉ , and this is at least c π c_\pi c π as soon as n ≥ k + 3 c π − 2 n\ge k+3c_\pi-2 n ≥ k + 3 c π − 2 . That holds since c π ≤ k + 1 c_\pi\le k+1 c π ≤ k + 1 and n ≥ 4 k + 1 n\ge4k+1 n ≥ 4 k + 1 .
It remains to check that all e ∈ [ 0 , c π ) e\in[0,c_\pi) e ∈ [ 0 , c π ) of the right parity lie in I π I_\pi I π . The lower end is fine since − ( n − k ) + 2 c π ≤ 0 -(n-k)+2c_\pi\le0 − ( n − k ) + 2 c π ≤ 0 . For the upper end, c π − 1 ≤ k ≤ n − k − 4 c_\pi-1\le k\le n-k-4 c π − 1 ≤ k ≤ n − k − 4 when k ≥ 2 k\ge2 k ≥ 2 . For k = 1 k=1 k = 1 (so π = ( 1 ) \pi=(1) π = ( 1 ) and c π = 2 c_\pi=2 c π = 2 ) the right parity and n ≥ 5 n\ge5 n ≥ 5 give e ≤ n − 5 e\le n-5 e ≤ n − 5 in all cases. For $k=0 there is nothing to check.
For each π \pi π we obtain ⌈ ( n − k ) / 2 ⌉ − c π + G π ( n − k ) \lceil(n-k)/2\rceil-c_\pi+G_\pi(n-k) ⌈( n − k ) /2 ⌉ − c π + G π ( n − k ) semigroups; now sum over π ⊢ k \pi\vdash k π ⊢ k .
Lemma 9.16. Let k ≥ 2 k\ge2 k ≥ 2 and let π = ( k − j , 1 j ) \pi=(k-j,1^j) π = ( k − j , 1 j ) be a hook of size k k k , 0 ≤ j ≤ k − 1 0\le j\le k-1 0 ≤ j ≤ k − 1 . Then k ∉ Σ ( π ) + Σ ( π ) k\notin\Sigma(\pi)+\Sigma(\pi) k ∈ / Σ ( π ) + Σ ( π ) if and only if j ≥ ⌈ ( k − 1 ) / 2 ⌉ j\ge\lceil(k-1)/2\rceil j ≥ ⌈( k − 1 ) /2 ⌉ . Consequently exactly ⌈ k / 2 ⌉ \lceil k/2\rceil ⌈ k /2 ⌉ hooks of size k k k satisfy k ∉ Σ ( π ) + Σ ( π ) k\notin\Sigma(\pi)+\Sigma(\pi) k ∈ / Σ ( π ) + Σ ( π ) .
Proof. For j = 0 j=0 j = 0 , w ( π ) = 1 k 0 w(\pi)=1^k0 w ( π ) = 1 k 0 and Σ ( π ) = [ 0 , k − 1 ] ∪ [ k + 1 , ∞ ) \Sigma(\pi)=[0,k-1]\cup[k+1,\infty) Σ ( π ) = [ 0 , k − 1 ] ∪ [ k + 1 , ∞ ) , so k = 1 + ( k − 1 ) k=1+(k-1) k = 1 + ( k − 1 ) lies in the sumset. For j ≥ 1 j\ge1 j ≥ 1 , w ( π ) = 10 j − 1 1 k 0 w(\pi)=10^{j-1}1^k0 w ( π ) = 1 0 j − 1 1 k 0 , so Σ ( π ) = { 0 } ∪ [ j + 1 , k − 1 ] ∪ [ k + 1 , ∞ ) \Sigma(\pi)=\{0\}\cup[j+1,k-1]\cup[k+1,\infty) Σ ( π ) = { 0 } ∪ [ j + 1 , k − 1 ] ∪ [ k + 1 , ∞ ) . Writing k = x + y k=x+y k = x + y with x , y ∈ Σ ( π ) x,y\in\Sigma(\pi) x , y ∈ Σ ( π ) : if x = 0 x=0 x = 0 , then y = k ∉ Σ ( π ) y=k\notin\Sigma(\pi) y = k ∈ / Σ ( π ) ; otherwise x , y ∈ [ j + 1 , k − 1 ] x,y\in[j+1,k-1] x , y ∈ [ j + 1 , k − 1 ] , which is possible if and only if 2 ( j + 1 ) ≤ k 2(j+1)\le k 2 ( j + 1 ) ≤ k . So k ∉ Σ ( π ) + Σ ( π ) k\notin\Sigma(\pi)+\Sigma(\pi) k ∈ / Σ ( π ) + Σ ( π ) exactly when 2 j + 2 > k 2j+2>k 2 j + 2 > k , that is, j ≥ ⌈ ( k − 1 ) / 2 ⌉ j\ge\lceil(k-1)/2\rceil j ≥ ⌈( k − 1 ) /2 ⌉ . The number of such j ∈ [ 0 , k − 1 ] j\in[0,k-1] j ∈ [ 0 , k − 1 ] is k − ⌈ ( k − 1 ) / 2 ⌉ = ⌈ k / 2 ⌉ k-\lceil(k-1)/2\rceil=\lceil k/2\rceil k − ⌈( k − 1 ) /2 ⌉ = ⌈ k /2 ⌉ .
Theorem 9.17. For every k ≥ 1 k \ge1 k ≥ 1 ,
PF ( 4 k , 3 k ) = p ( k ) ⌈ 3 k 2 ⌉ − C k ( k m o d 2 ) − ⌈ k 2 ⌉ . \operatorname{PF}(4k,3k)=p(k)\left\lceil\frac{3k}{2}\right\rceil-C_k(k\bmod2)-\left\lceil\frac{k}{2}\right\rceil. PF ( 4 k , 3 k ) = p ( k ) ⌈ 2 3 k ⌉ − C k ( k mod 2 ) − ⌈ 2 k ⌉ . In particular, Theorem 9.15 fails at n = 4 k n=4k n = 4 k , and the range n ≥ 4 k + 1 n \ge4k+1 n ≥ 4 k + 1 is sharp.
Proof. For k = 1 k=1 k = 1 : the partitions of 4 4 4 with largest hook 3 3 3 are just ( 2 , 2 ) (2,2) ( 2 , 2 ) , which has no part 1 1 1 , so PF ( 4 , 3 ) = 0 \operatorname{PF}(4,3)=0 PF ( 4 , 3 ) = 0 . The right-hand side is 1 ⋅ 2 − 1 − 1 = 0 1\cdot2-1-1=0 1 ⋅ 2 − 1 − 1 = 0 .
Let k ≥ 2 k \ge2 k ≥ 2 and n = 4 k n=4k n = 4 k , and follow the proof of Theorem 9.15. The conditions n − k ≥ 2 c π n-k\ge2c_\pi n − k ≥ 2 c π and c π − 1 ≤ n − k − 4 c_\pi-1\le n-k-4 c π − 1 ≤ n − k − 4 still hold, since 3 k ≥ 2 k + 2 3k\ge2k+2 3 k ≥ 2 k + 2 and 3 k − 4 ≥ k 3k-4\ge k 3 k − 4 ≥ k . The only step that can fail is m ≥ c π m\ge c_\pi m ≥ c π for 0 ≤ e < c π 0\le e<c_\pi 0 ≤ e < c π . Here m = ( 3 k − e ) / 2 m=(3k-e)/2 m = ( 3 k − e ) /2 , so m < c π m<c_\pi m < c π implies e > 3 k − 2 c π e>3k-2c_\pi e > 3 k − 2 c π . Since e < c π e<c_\pi e < c π , this requires 3 k − 2 c π < c π − 1 3k-2c_\pi<c_\pi-1 3 k − 2 c π < c π − 1 , which implies c π > k + 1 3 c_\pi>k+\frac{1}{3} c π > k + 3 1 , that is, c π = k + 1 c_\pi=k+1 c π = k + 1 . This implies π \pi π is a hook of size k k k . For a hook, e ≡ 3 k ≡ k ( m o d 2 ) e\equiv3k\equiv k\pmod2 e ≡ 3 k ≡ k ( mod 2 ) , and 3 k − 2 ( k + 1 ) < e ≤ k 3k-2(k+1)<e\le k 3 k − 2 ( k + 1 ) < e ≤ k forces e = k e=k e = k and m = k m=k m = k .
So the formula of Theorem 9.15 is correct except possibly for the pairs ( π a hook , e = k ) (\pi\text{ a hook},e=k) ( π a hook , e = k ) . If k ∈ Σ ( π ) + Σ ( π ) k\in\Sigma(\pi)+\Sigma(\pi) k ∈ Σ ( π ) + Σ ( π ) , then the formula already counts this pair as a failure by Lemma 9.1 -(2). If k ∉ Σ ( π ) + Σ ( π ) k\notin\Sigma(\pi)+\Sigma(\pi) k ∈ / Σ ( π ) + Σ ( π ) , the formula counts it as a semigroup. However m = k m=k m = k , and position k = π 1 + r − 1 k=\pi_1+r-1 k = π 1 + r − 1 is the last letter of w ( π ) w(\pi) w ( π ) , which is 0 0 0 . So 2 m = m + k 2m=m+k 2 m = m + k is a gap while m ∈ S m\in S m ∈ S , and λ \lambda λ is not a semigroup. By Lemma 9.16 there are exactly ⌈ k / 2 ⌉ \lceil k/2\rceil ⌈ k /2 ⌉ such hooks, and the formula overcounts by exactly this number.
In the following result we recover and correct some results discussed in [5 ] , Section 4.
Corollary 9.18.
PF ( n , n ) = ⌈ n / 2 ⌉ \operatorname{PF}(n,n)=\lceil n/2\rceil PF ( n , n ) = ⌈ n /2 ⌉ [5 Theorem 6] .
PF ( 2 n , 2 n − 1 ) = n − 1 \operatorname{PF}(2n,2n-1)=n-1 PF ( 2 n , 2 n − 1 ) = n − 1 and PF ( 2 n + 1 , 2 n ) = n − 2 \operatorname{PF}(2n+1,2n)=n-2 PF ( 2 n + 1 , 2 n ) = n − 2 for n ≥ 3 n\ge3 n ≥ 3 [5 Theorem 7-(1),(2)] .
PF ( 2 n , 2 n − 2 ) = PF ( 2 n − 1 , 2 n − 3 ) = 2 n − 7 \operatorname{PF}(2n,2n-2)=\operatorname{PF}(2n-1,2n-3)=2n-7 PF ( 2 n , 2 n − 2 ) = PF ( 2 n − 1 , 2 n − 3 ) = 2 n − 7 for n ≥ 5 n\ge5 n ≥ 5 ; and PF ( 2 n , 2 n − 3 ) = 3 n − 11 \operatorname{PF}(2n,2n-3)=3n-11 PF ( 2 n , 2 n − 3 ) = 3 n − 11 , PF ( 2 n − 1 , 2 n − 4 ) = 3 n − 17 \operatorname{PF}(2n-1,2n-4)=3n-17 PF ( 2 n − 1 , 2 n − 4 ) = 3 n − 17 for n ≥ 7 n\ge7 n ≥ 7 . These are [5 Theorem 7(3)–(5)] , whose hypothesis n > 2 n>2 n > 2 must be strengthened as stated. For example PF ( 6 , 4 ) = 0 ≠ − 1 \operatorname{PF}(6,4)=0\ne-1 PF ( 6 , 4 ) = 0 = − 1 , and PF ( 12 , 9 ) = 5 ≠ 7 \operatorname{PF}(12,9)=5\ne7 PF ( 12 , 9 ) = 5 = 7 by Theorem 9.17 .
PF ( n , n − k ) − PF ( n − 2 , n − k − 2 ) = p ( k ) \operatorname{PF}(n,n-k)-\operatorname{PF}(n-2,n-k-2)=p(k) PF ( n , n − k ) − PF ( n − 2 , n − k − 2 ) = p ( k ) for n ≥ 4 k + 3 n\ge4k+3 n ≥ 4 k + 3 [5 Theorem 8] .
Proof. We use the constants C 0 = 0 C_0=0 C 0 = 0 , C 1 ( 0 ) = 2 C_1(0)=2 C 1 ( 0 ) = 2 , C 1 ( 1 ) = 1 C_1(1)=1 C 1 ( 1 ) = 1 , C 2 ( 0 ) = C 2 ( 1 ) = 5 C_2(0)=C_2(1)=5 C 2 ( 0 ) = C 2 ( 1 ) = 5 , C 3 ( 0 ) = 11 C_3(0)=11 C 3 ( 0 ) = 11 and C 3 ( 1 ) = 8 C_3(1)=8 C 3 ( 1 ) = 8 . We derive two of them.
For k = 1 k=1 k = 1 , π = ( 1 ) \pi=(1) π = ( 1 ) , c π = 2 c_\pi=2 c π = 2 and Σ ( π ) = { 0 } ∪ [ 2 , ∞ ) \Sigma(\pi)=\{0\}\cup[2,\infty) Σ ( π ) = { 0 } ∪ [ 2 , ∞ ) , so 0 0 0 lies in the sumset and 1 1 1 does not; therefore, G ( 0 ) = 0 G(0)=0 G ( 0 ) = 0 , G ( 1 ) = 1 G(1)=1 G ( 1 ) = 1 , C 1 ( 0 ) = 2 C_1(0)=2 C 1 ( 0 ) = 2 and C 1 ( 1 ) = 1 C_1(1)=1 C 1 ( 1 ) = 1 . The others follow in the same way from Definition 3.15.
(1) is Corollary 4.8 .
(2) Take k = 1 k=1 k = 1 . For PF ( 2 n , 2 n − 1 ) \operatorname{PF}(2n,2n-1) PF ( 2 n , 2 n − 1 ) the quantity n ′ − k = 2 n − 1 n'-k=2n-1 n ′ − k = 2 n − 1 is odd, so PF = ⌈ ( 2 n − 1 ) / 2 ⌉ − C 1 ( 1 ) = n − 1 \operatorname{PF}=\lceil(2n-1)/2\rceil-C_1(1)=n-1 PF = ⌈( 2 n − 1 ) /2 ⌉ − C 1 ( 1 ) = n − 1 . For PF ( 2 n + 1 , 2 n ) \operatorname{PF}(2n+1,2n) PF ( 2 n + 1 , 2 n ) it is 2 n 2n 2 n , which is even, so PF = n − C 1 ( 0 ) = n − 2 \operatorname{PF}=n-C_1(0)=n-2 PF = n − C 1 ( 0 ) = n − 2 . The range n ′ ≥ 4 k + 1 = 5 n'\ge4k+1=5 n ′ ≥ 4 k + 1 = 5 holds for n ≥ 3 n\ge3 n ≥ 3 .
(3) k = 2 k=2 k = 2 : PF = 2 ⌈ ( n ′ − 2 ) / 2 ⌉ − 5 \operatorname{PF}=2\lceil(n'-2)/2\rceil-5 PF = 2 ⌈( n ′ − 2 ) /2 ⌉ − 5 , giving 2 ( n − 1 ) − 5 = 2 n − 7 2(n-1)-5=2n-7 2 ( n − 1 ) − 5 = 2 n − 7 for n ′ = 2 n n'=2n n ′ = 2 n and for n ′ = 2 n − 1 n'=2n-1 n ′ = 2 n − 1 ; the range n ′ ≥ 9 n'\ge9 n ′ ≥ 9 means n ≥ 5 n\ge5 n ≥ 5 . For k = 3 k=3 k = 3 : PF ( 2 n , 2 n − 3 ) = 3 ( n − 1 ) − C 3 ( 1 ) = 3 n − 11 \operatorname{PF}(2n,2n-3)=3(n-1)-C_3(1)=3n-11 PF ( 2 n , 2 n − 3 ) = 3 ( n − 1 ) − C 3 ( 1 ) = 3 n − 11 and PF ( 2 n − 1 , 2 n − 4 ) = 3 ( n − 2 ) − C 3 ( 0 ) = 3 n − 17 \operatorname{PF}(2n-1,2n-4)=3(n-2)-C_3(0)=3n-17 PF ( 2 n − 1 , 2 n − 4 ) = 3 ( n − 2 ) − C 3 ( 0 ) = 3 n − 17 ; the range n ′ ≥ 13 n'\ge13 n ′ ≥ 13 means n ≥ 7 n\ge7 n ≥ 7 . At the excluded values: the only partitions of 6 6 6 with largest hook 4 4 4 are ( 3 , 3 ) (3,3) ( 3 , 3 ) and ( 2 , 2 , 2 ) (2,2,2) ( 2 , 2 , 2 ) , neither of which has a part 1 1 1 , so PF ( 6 , 4 ) = 0 \operatorname{PF}(6,4)=0 PF ( 6 , 4 ) = 0 ; and PF ( 12 , 9 ) = 3 ⋅ 5 − 8 − 2 = 5 \operatorname{PF}(12,9)=3\cdot5-8-2=5 PF ( 12 , 9 ) = 3 ⋅ 5 − 8 − 2 = 5 by Theorem 9.17 .
(4) When n n n increases by 2 2 2 , ⌈ ( n − k ) / 2 ⌉ \lceil(n-k)/2\rceil ⌈( n − k ) /2 ⌉ increases by 1 1 1 and the parity is unchanged. The range n − 2 ≥ 4 k + 1 n-2\ge4k+1 n − 2 ≥ 4 k + 1 is n ≥ 4 k + 3 n\ge4k+3 n ≥ 4 k + 3 .
In the following result we provide an answer to [5 ] , Remark 3.
Corollary 9.19. For 2 n ≥ 4 j + 1 2n\ge4j+1 2 n ≥ 4 j + 1 ,
PF ( 2 n , 2 n − j ) = p ( j ) ⌈ n − j 2 ⌉ − C j ( j m o d 2 ) , \operatorname{PF}(2n,2n-j)=p(j)\left\lceil n-\frac{j}{2}\right\rceil-C_j(j\bmod2), PF ( 2 n , 2 n − j ) = p ( j ) ⌈ n − 2 j ⌉ − C j ( j mod 2 ) , which replaces the upper bound of [5 Remark 3] by an identity.
Proof. Apply Theorem 9.15 with 2 n 2n 2 n in place of n n n and k = j k=j k = j . Then ⌈ ( 2 n − j ) / 2 ⌉ = ⌈ n − j / 2 ⌉ \lceil(2n-j)/2\rceil=\lceil n-j/2\rceil ⌈( 2 n − j ) /2 ⌉ = ⌈ n − j /2 ⌉ , and 2 n − j ≡ j ( m o d 2 ) 2n-j\equiv j\pmod{2} 2 n − j ≡ j ( mod 2 ) .
Tables
Table 4. Constants in Theorem 9.15: PF ( n , n − k ) = p ( k ) ⌈ ( n − k ) / 2 ⌉ − C k ( ε ) \operatorname{PF}(n,n-k)=p(k)\lceil(n-k)/2\rceil-C_k(\varepsilon) PF ( n , n − k ) = p ( k ) ⌈( n − k ) /2 ⌉ − C k ( ε ) with ε ≡ n − k ( m o d 2 ) \varepsilon\equiv n-k\pmod{2} ε ≡ n − k ( mod 2 ) , valid for n ≥ 4 k + 1 n\ge4k+1 n ≥ 4 k + 1 .
Remark 9.20. All statements were also checked by computer. Sections 4–8, including the staircase theorem and its consequences, were tested on all 2 16 − 1 2^{16}-1 2 16 − 1 numerical sets with Frobenius number at most 16; Theorem 4.7 on all ( A p , B q ) (A^p,B^q) ( A p , B q ) with A ≤ 15 A\le15 A ≤ 15 and p , q ≤ 8 p,q\le8 p , q ≤ 8 ; and Table 2 on all partitions with at most four parts and largest part at most 12. Theorems 9.5, 9.10, 9.11, 9.12, 9.15 and 9.17 were compared with a direct enumeration of all 51,861 numerical semigroups whose partition has size at most 44. There were no exceptions.
Summary of solutions to the open problems of Burson, Nam and Sisneros-Thiry
In this section we list the open problems of [5 ] and give their solutions, all obtained from creation sequences. Throughout, “for all n n n beyond a linear bound” means for all n n n at least a linear function of the shift, and we state the bound explicitly each time.
The common method
Each problem asks about partitions close to an extreme case: many parts, many parts equal to 1, or a hook that contains almost all cells. In each case the creation sequence (equivalently, the threshold graph) of such a partition consists of, an initial run of isolated vertices, the creation sequence of a small tail partition (ν \nu ν or κ \kappa κ ), a long run of dominating vertices, and a final isolated vertex.
By Lemma 9.1 and Remark 9.2 (and by the corresponding step in the proof of Theorem 9.5, where the only critical vertex is v 2 m v_{2m} v 2 m ), whether the partition corresponds to a semigroup depends only on the creation sequence of the tail and on one integer offset. The offset is determined by the shift (i i i , j j j or k k k ) and not by n n n . Therefore the number of exceptions is a function of the shift alone, and it counts tails with a prescribed arithmetic property. This is exactly the kind of function that [5 ] asked for.
Problem. Note that p ( n ) − PG ( 3 n − i , 2 n − i ) p(n)-\operatorname{PG}(3n-i,2n-i) p ( n ) − PG ( 3 n − i , 2 n − i ) and b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) b(n)-\operatorname{PG}(3n+2-i,2n-i) b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) can be found for each specific i i i , and state: “it is an open problem to find functions h 1 ( i ) h_1(i) h 1 ( i ) and h 2 ( i ) h_2(i) h 2 ( i ) such that p ( n ) − PG ( 3 n − i , 2 n − i ) = h 1 ( i ) p(n)-\operatorname{PG}(3n-i,2n-i)=h_1(i) p ( n ) − PG ( 3 n − i , 2 n − i ) = h 1 ( i ) and b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) = h 2 ( i ) b(n)-\operatorname{PG}(3n+2-i,2n-i)=h_2(i) b ( n ) − PG ( 3 n + 2 − i , 2 n − i ) = h 2 ( i ) for all possible values of i i i .”
Solution. By Theorem 9.5 and Corollary 9.8 ,
h 1 ( i ) = E ( i ) ( n ≥ i ) , h 2 ( i ) = E ( i + 4 ) − 4 ( n ≥ i + 2 ) . h_1(i)=E(i)\quad(n\ge i),\qquad h_2(i)=E(i+4)-4\quad(n\ge i+2). h 1 ( i ) = E ( i ) ( n ≥ i ) , h 2 ( i ) = E ( i + 4 ) − 4 ( n ≥ i + 2 ) .
where E ( j ) E(j) E ( j ) is the number of partitions ν \nu ν such that 2 ∣ ν ∣ + ℓ ( ν ) − j 2|\nu|+\ell(\nu)-j 2∣ ν ∣ + ℓ ( ν ) − j is not a 1-position of the creation sequence of ν \nu ν (Definition 9.3 ). A closed generating function for E E E is given in Proposition 9.6 , and its values are listed in Table 3 . In threshold-graph language, the tail ν \nu ν is exceptional exactly when the vertex v 2 m v_{2m} v 2 m of G ( S λ ) G(S_\lambda) G ( S λ ) is isolated.
Example 10.1. h 1 ( 4 ) = E ( 4 ) = 4 h_1(4)=E(4)=4 h 1 ( 4 ) = E ( 4 ) = 4 . The tails counted are ∅ \varnothing ∅ and ( 1 ) (1) ( 1 ) (here 2 ∣ ν ∣ + ℓ ( ν ) < 4 2|\nu|+\ell(\nu)<4 2∣ ν ∣ + ℓ ( ν ) < 4 ), together with ( 1 , 1 ) (1,1) ( 1 , 1 ) and ( 3 ) (3) ( 3 ) (here 2 ∣ ν ∣ − ν t + t = 4 2|\nu|-\nu_t+t=4 2∣ ν ∣ − ν t + t = 4 for t = 1 t=1 t = 1 ). For every n ≥ 4 n\ge4 n ≥ 4 the four partitions of 3 n − 4 3n-4 3 n − 4 with 2 n − 4 2n-4 2 n − 4 parts that do not correspond to numerical semigroups are therefore
( 2 n , 1 n − 4 ) , ( 3 , 2 n − 2 , 1 n − 3 ) , ( 3 , 3 , 2 n − 4 , 1 n − 2 ) , ( 5 , 2 n − 4 , 1 n − 1 ) , (2^n,1^{n-4}),\qquad(3,2^{n-2},1^{n-3}),\qquad(3,3,2^{n-4},1^{n-2}),\qquad(5,2^{n-4},1^{n-1}), ( 2 n , 1 n − 4 ) , ( 3 , 2 n − 2 , 1 n − 3 ) , ( 3 , 3 , 2 n − 4 , 1 n − 2 ) , ( 5 , 2 n − 4 , 1 n − 1 ) ,
obtained from the tails ∅ , ( 1 ) , ( 1 , 1 ) , ( 3 ) \varnothing,(1),(1,1),(3) ∅ , ( 1 ) , ( 1 , 1 ) , ( 3 ) by the parametrisation in the proof of Theorem 9.5 .
Problem. “It is an open problem to find a specific function h ( i ) h(i) h ( i ) such that a ( n + 1 ) − PM ( 2 n − i , n − i ) = h ( i ) a(n+1)-\operatorname{PM}(2n-i,n-i)=h(i) a ( n + 1 ) − PM ( 2 n − i , n − i ) = h ( i ) for all possible values of i i i .”
Solution. By Theorem 9.10 and Corollary 9.14 ,
h ( i ) = H ( i ) − 1 ( n ≥ 2 i + 1 ) . h(i)=H(i)-1\quad(n\ge2i+1). h ( i ) = H ( i ) − 1 ( n ≥ 2 i + 1 ) .
where H ( i ) H(i) H ( i ) is the number of partitions κ \kappa κ with ∣ κ ∣ ≤ i |\kappa|\le i ∣ κ ∣ ≤ i such that i − ∣ κ ∣ i-|\kappa| i − ∣ κ ∣ is a sum of two 1-positions of the creation sequence of κ \kappa κ (Definition 9.9 ). The term − 1 -1 − 1 removes the empty tail, which corresponds to the one-part partitions already excluded from a ( n + 1 ) a(n+1) a ( n + 1 ) . At the boundary n = 2 i n=2i n = 2 i , where 3 m = n 3m=n 3 m = n , Theorems 9.11 and 9.12 give the exact corrections on the next two lines:
a ( 2 i + 1 ) − PM ( 3 i , i ) = H ( i ) − 1 − i , a ( 2 i ) − PM ( 3 i − 2 , i − 1 ) = H ( i ) − 1 − ( i − 1 ) . a(2i+1)-\operatorname{PM}(3i,i)=H(i)-1-i,\qquad a(2i)-\operatorname{PM}(3i-2,i-1)=H(i)-1-(i-1). a ( 2 i + 1 ) − PM ( 3 i , i ) = H ( i ) − 1 − i , a ( 2 i ) − PM ( 3 i − 2 , i − 1 ) = H ( i ) − 1 − ( i − 1 ) .
Below these lines only finitely many n n n remain for each i i i .
Example 10.2. h ( 3 ) = H ( 3 ) − 1 = 5 h(3)=H(3)-1=5 h ( 3 ) = H ( 3 ) − 1 = 5 . The tails with ∣ κ ∣ ≤ 3 |\kappa|\le3 ∣ κ ∣ ≤ 3 and 3 − ∣ κ ∣ 3-|\kappa| 3 − ∣ κ ∣ a sum of two 1-positions are ( 1 ) (1) ( 1 ) (offset 2), ( 2 ) (2) ( 2 ) (offset 1), and ( 3 ) (3) ( 3 ) , ( 2 , 1 ) (2,1) ( 2 , 1 ) , ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) (offset 0), plus the empty tail. The tail ( 1 , 1 ) (1,1) ( 1 , 1 ) is not exceptional: its creation sequence is 100, and the offset 1 is not a sum of two elements of { 0 , 3 , 4 , … } \{0,3,4,\ldots\} { 0 , 3 , 4 , … } . This corrects the range in [5 Theorem 10-(4)] to n ≥ 7 n\ge7 n ≥ 7 (Corollary 9.13 ).
Problem. [5 Remark 3] give only the upper bound PF ( 2 n , 2 n − j ) ≤ p ( j ) ⌈ 2 n − j 2 ⌉ − ∑ i = 1 n − ⌊ j / 2 ⌋ p ( j , i ) \operatorname{PF}(2n,2n-j)\le p(j)\left\lceil\frac{2n-j}{2}\right\rceil-\sum_{i=1}^{n-\lfloor j/2\rfloor}p(j,i) PF ( 2 n , 2 n − j ) ≤ p ( j ) ⌈ 2 2 n − j ⌉ − ∑ i = 1 n − ⌊ j /2 ⌋ p ( j , i ) , and note that the method extends to further exceptional cases as j j j grows. Solution. By Theorem 9.15 and Corollary 9.19,
PF ( 2 n , 2 n − j ) = p ( j ) ⌊ n − j 2 ⌋ − C j ( j m o d 2 ) ( 2 n ≥ 4 j + 1 ) , \operatorname{PF}(2n,2n-j)=p(j)\left\lfloor\frac{n-j}{2}\right\rfloor-C_j(j\bmod2)\qquad(2n\ge4j+1), PF ( 2 n , 2 n − j ) = p ( j ) ⌊ 2 n − j ⌋ − C j ( j mod 2 ) ( 2 n ≥ 4 j + 1 ) ,
where C j ( ε ) = ∑ π ⊢ j ( c π − G π ( ε ) ) C_j(\varepsilon)=\sum_{\pi\vdash j}(c_\pi-G_\pi(\varepsilon)) C j ( ε ) = ∑ π ⊢ j ( c π − G π ( ε )) . Here c π = π 1 + ℓ ( π ) c_\pi=\pi_1+\ell(\pi) c π = π 1 + ℓ ( π ) is the length of the creation sequence of π \pi π , and G π ( ε ) G_\pi(\varepsilon) G π ( ε ) counts the offsets e < c π e<c_\pi e < c π of parity ε \varepsilon ε that are not sums of two 1-positions of that sequence. More generally, PF ( n , n − k ) = p ( k ) ⌊ ( n − k ) / 2 ⌋ − C k ( n − k ) \operatorname{PF}(n,n-k)=p(k)\left\lfloor(n-k)/2\right\rfloor-C_k(n-k) PF ( n , n − k ) = p ( k ) ⌊ ( n − k ) /2 ⌋ − C k ( n − k ) for n ≥ 4 k + 1 n\ge4k+1 n ≥ 4 k + 1 . At the boundary n = 4 k n=4k n = 4 k the exact correction is − ⌈ k / 2 ⌉ -\lceil k/2\rceil − ⌈ k /2 ⌉ (Theorem 9.17 ), coming from the hooks of size k k k whose creation sequences 10 j 1 k − j − 1 0 10^j1^{k-j-1}0 1 0 j 1 k − j − 1 0 have too long a zero block (Lemma 9.16).
Problem. “Many of the results above involve functions of the form PG ( L 1 ( n ) − k , L 2 ( n ) − k ) \operatorname{PG}(L_1(n)-k,L_2(n)-k) PG ( L 1 ( n ) − k , L 2 ( n ) − k ) , PM ( L 3 ( n ) − k , L 4 ( n ) − k ) \operatorname{PM}(L_3(n)-k,L_4(n)-k) PM ( L 3 ( n ) − k , L 4 ( n ) − k ) , and PF ( L 5 ( n ) , L 6 ( n ) − k ) \operatorname{PF}(L_5(n),L_6(n)-k) PF ( L 5 ( n ) , L 6 ( n ) − k ) for some specific linear functions L i ( n ) L_i(n) L i ( n ) and certain values of k k k . It is an open problem to extend the results uniformly to general theorems that hold for any value of k k k .”
Solution. The following three theorems hold for every value of the shift simultaneously.
PG ( n , g ) = p ( n − g ) − E ( 2 n − 3 g ) for 2 g ≥ n (xref‘Theorem 9.5‘), \operatorname{PG}(n,g)=p(n-g)-E(2n-3g)\qquad\text{for }2g\ge n\qquad\text{({xref}`Theorem 9.5`),} PG ( n , g ) = p ( n − g ) − E ( 2 n − 3 g ) for 2 g ≥ n ( xref ‘Theorem 9.5‘),
PM ( n , m ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) for m − 1 ≤ n < 3 m (xref‘Theorem 9.10‘), \operatorname{PM}(n,m)=\bar{p}(n-m+1)-H(n-2m)\qquad\text{for }m-1\le n<3m\qquad\text{({xref}`Theorem 9.10`),} PM ( n , m ) = p ˉ ( n − m + 1 ) − H ( n − 2 m ) for m − 1 ≤ n < 3 m ( xref ‘Theorem 9.10‘),
PF ( n , n − k ) = p ( k ) ⌊ n − k 2 ⌋ − C k ( n − k ) for n ≥ 4 k + 1 (xref‘Theorem 9.15‘). \operatorname{PF}(n,n-k)=p(k)\left\lfloor\frac{n-k}{2}\right\rfloor-C_k(n-k)\qquad\text{for }n\ge4k+1\qquad\text{({xref}`Theorem 9.15`).} PF ( n , n − k ) = p ( k ) ⌊ 2 n − k ⌋ − C k ( n − k ) for n ≥ 4 k + 1 ( xref ‘Theorem 9.15‘).
Along any line of the kind considered in [5 ] , for instance PG ( L 1 ( n ) − k , L 2 ( n ) − k ) \operatorname{PG}(L_1(n)-k,L_2(n)-k) PG ( L 1 ( n ) − k , L 2 ( n ) − k ) with 2 L 2 ( n ) − k ≥ L 1 ( n ) 2L_2(n)-k\ge L_1(n) 2 L 2 ( n ) − k ≥ L 1 ( n ) , substituting gives an explicit formula for every k k k (Corollary 9.8 ). All counting theorems of [5 Sections 3–5] are special cases of these theorems and of the boundary Theorems 9.11 , 9.12 and 9.17 (Corollaries 9.7 , 9.13 and 9.18). The three ranges are sharp (Corollary 9.7 (1) and Theorems 9.11 and 9.17 ).
Concluding remarks
The creation-sequence point of view reduces the counting problems of [5 ] to a single mechanism. Close to the extreme cases, a partition fails to correspond to a numerical semigroup only because of a bounded tail ν \nu ν or κ \kappa κ , and whether it fails is decided by the Keith–Nath set of that tail. This is why the exceptional counts are independent of n n n . The same words explain the symmetry ℓ ( λ ) ≥ λ 1 \ell(\lambda)\ge\lambda_1 ℓ ( λ ) ≥ λ 1 and the tree structure. The following questions remain open.
Extend Theorems 9.5 , 9.10 and 9.15 below g = n / 2 g=n/2 g = n /2 , m = n / 3 m=n/3 m = n /3 and n = 4 k n=4k n = 4 k . The boundary theorems 9.11 and 9.17 suggest that each further step adds a correction term counted by hooks, or by partitions close to hooks.
For each fixed shift our formulas hold for all n n n beyond a linear bound, and the first boundary case is exact. The remaining finitely many small n n n for each shift (g < n / 2 g<n/2 g < n /2 , 3 m < n 3m<n 3 m < n , n < 4 k n<4k n < 4 k ) are not covered by a single formula (for the multiplicity, 3 m < n − 1 3m<n-1 3 m < n − 1 ). Theorems 9.11 and 9.17 suggest that each further step introduces a correction counted by hooks or near-hooks.
The density conjecture of Constantin, Houston-Edwards and Kaplan, S ′ ( n ) / P ( n ) → 0 S'(n)/P(n)\to0 S ′ ( n ) / P ( n ) → 0 , which [5 ] recall as motivation, is not resolved. We prove the bound lim sup S ′ ( n ) / P ( n ) ≤ 1 2 \limsup S'(n)/P(n)\le\frac{1}{2} lim sup S ′ ( n ) / P ( n ) ≤ 2 1 (Theorem 6.7 ).
Find the asymptotic growth of E ( j ) E(j) E ( j ) and H ( i ) H(i) H ( i ) .
Acknowledgement: The first author would like to take this opportunity to gratefully acknowledge the American Mathematical Society and the International Mathematical Union for their generous support of his visit to Philadelphia, USA, to attend ICM 2026, and for providing excellent facilities and a stimulating academic environment that fostered fruitful research discussions and valuable academic interactions.
Declaration of competing interests : The authors declare no conflicts of interest.
Data Availability: Data sharing is not applicable to this article as no datasets were generated or analysed during the current study.