Quasipolynomiality and collision asymptotics for ordinarization counts
September 16, 2026; revised version 1.2
Abstract
Let count numerical semigroups of genus and ordinarization number . For every fixed positive integer , we prove that is a quasipolynomial for all positive integers , answering a question of Cyrusian and Kaplan. Its leading coefficient is . We determine the complete next coefficient in closed form, including its constant part and its oscillation: its exact period is two, and its even value is smaller than its odd value by . This gives explicit positive leading terms for in both parities and proves eventual strict monotonicity for every fixed . The proof separates a binomial-sum bulk from exceptional additive relations. Those relations lie in linear hyperplanes through the origin, which prevents them from introducing periodicity in the next coefficient. For growing with and , we prove that . This follows from a Poisson law for forbidden holes and bounds on all tuples outside the bulk, using closure under addition by the multiplicity. The full all-genus counting conjectures remain open.
1. Introduction and main results
A numerical semigroup is an additive submonoid of with finite complement. Its genus is the number of gaps, and its Frobenius number is the largest gap when . The ordinary semigroup of genus is . Repeatedly removing the smallest positive nongap and inserting the largest gap leads to this ordinary semigroup. The number of steps is the ordinarization number .
The ordinarization number equals the number of positive elements of at most ; see [2, Proposition 1.4]. We write
Cyrusian and Kaplan proved eventual quasipolynomiality of degree for fixed [2, Theorem 3.4]. They asked whether the quasipolynomial holds for every positive genus [2, Remark 3.7]. They also discuss the conjecture for every [2, Conjecture 1.5], and prove it for . We answer their quasipolynomiality question and prove the eventual strict version of this conjecture for every fixed positive .
Recall that a quasipolynomial on the positive integers is an expression with rational-valued periodic functions . Equivalently, one polynomial applies in each residue class modulo some positive integer. The degree is the largest for which is not identically zero. Sections 1–5 keep fixed. Section 6 treats sequences with increasing .
Theorem 1.1.
For every positive integer , the function is a quasipolynomial of degree on all positive integers. Put
With the explicit rational number given in Theorem 5.1, we have
Consequently, the leading coefficient is constant and the coefficient of has exact period two.
Corollary 1.2.
For fixed ,
In particular, for every sufficiently large .
The conclusion is pointwise in : no threshold uniform in a growing ordinarization number is asserted. We do not settle monotonicity at every genus, nor monotonicity of the total number of numerical semigroups. A positive constant leading coefficient alone would not prove Corollary 1.2, because a periodic next coefficient can contribute at the same order to successive differences. Determining that coefficient’s oscillation is the essential additional step.
It has precisely gaps. We use as the upper bound in (4); closure under addition will automatically exclude a gap at .
Lemma 2.1.
The set (5) is a numerical semigroup if and only if both of the following conditions hold:
Every numerical semigroup of genus and ordinarization number arises from exactly one such tuple.
Proof.
Condition (6) says exactly that sums of two elements of lie in . For a mixed sum with and , the only possible failure is for some . Such a failure occurs precisely when and . This is excluded exactly by (7). Two summands greater than have sum greater than , and zero causes no obstruction. This proves the equivalence.
For completeness, if has genus and Frobenius number , the map injects into the gaps: otherwise would be a sum of two elements of . Hence , so . There are positive nongaps at most , leaving gaps there and therefore gaps above . These two sets give and uniquely, and the Frobenius bound places in the required interval.
We recall the particular lattice-counting facts needed here. A rational polyhedral Boolean set means a set specified by a finite Boolean combination of rational linear equalities and strict or weak inequalities.
Lemma 2.2.
Let be a bounded rational polyhedral Boolean set. Then
is a quasipolynomial for all positive integers . If is contained in a finite union of rational linear hyperplanes through the origin, then there is a rational constant such that
when . The same conclusion holds for a finite signed sum of such counts.
Proof.
Take the arrangement of all hyperplanes appearing in a description of , together with a rational bounding box. Its cells that belong to are relative interiors of bounded rational polytopes, and they form a finite disjoint partition. Ehrhart’s theorem gives quasipolynomial lattice counts for closed rational polytopes [1, Theorem 3.23]. Removing the boundary by inclusion-exclusion over proper faces gives the same conclusion for relative interiors and therefore for . This argument holds at every positive dilation, including for lower-dimensional polytopes whose affine hulls may meet the lattice only at some dilations.
For the second assertion, refine the arrangement to include the stated hyperplanes. Every selected cell has dimension at most . A cell of dimension lies in some hyperplane , and its affine hull equals . The lattice has full rank in . After choosing a lattice basis of , the closure of this cell becomes a full-dimensional rational polytope in . Its lattice count is
where volume is normalized so that a fundamental parallelepiped of has volume one. One can see this directly by tiling by such parallelepipeds: only those meeting the boundary contribute to the discrepancy, and their number is . Boundary removal has the same error bound. The normalized volume is rational and does not depend on a residue class of .
Cells of dimension at most contribute , by their Ehrhart quasipolynomials. Summing proves (8); signed sums follow by linearity. The requirement that the containing hyperplanes pass through the origin ensures that the full lattice in each top-dimensional affine hull is present at every dilation.
Proposition 2.3.
For fixed positive , the function is a quasipolynomial on all positive integers , of degree at most .
Proof.
Apply Lemma 2.1. Membership in a finite set such as is a finite disjunction of linear equalities, and nonmembership is a conjunction of their negations. All conditions in (4), (6), and (7) are homogeneous in the variables . In particular, strict inequalities are retained as strict inequalities, without introducing an additive constant.
Let be the set obtained by putting in these conditions. It is bounded and rational polyhedral Boolean. Homogeneity gives
Lemma 2.2 gives the desired quasipolynomial, with degree at most the ambient dimension.
3. The bulk and its exceptional hyperplanes
Let be the set of tuples counted by . Define the bulk to consist of the integer tuples in (4) satisfying
These conditions do not themselves impose closure. Put .
Lemma 3.1.
For all positive integers ,
where a binomial coefficient is zero if its lower index exceeds its nonnegative upper index. Moreover, there is such that
Proof.
Choose . The remaining elements of are chosen from . The elements of are chosen from . This proves (10).
We claim that the symmetric difference of and lies in the union of the proper linear hyperplanes
Indeed, if a tuple is valid but , condition (6) forces . If it is valid but , condition (7) forces . These are (12) and (13).
Conversely, suppose a tuple belongs to the bulk. Every sum of two elements of is greater than . Also for all , so the mixed-sum condition is automatic. The only remaining failures of closure are therefore the equalities in (14). This proves the claim. The argument also holds for the real tuples defined by the same Boolean conditions, because it uses only those conditions and the ordering.
Set in the real valid and bulk sets. Their two set differences are bounded rational polyhedral Boolean sets in the union of (12)–(14). These hyperplanes involve no and pass through the origin in . Apply the signed version of Lemma 2.2 with to obtain (11).
Remark 3.2.
The constancy of is crucial. The weaker estimate would permit a correction of the same size as the main term in a successive difference. In contrast, (11) implies
No differentiation of an unspecified error term is used: subtracting two quantities individually of order remains of that order.
First suppose . Expanding the two binomial polynomials gives, uniformly for ,
where is a polynomial and
The polynomial interpretation of the binomial coefficients is valid even when a nonnegative upper index is smaller than the lower index, since the product defining the polynomial then vanishes. There is no endpoint exception in (16).
Write for even and for odd . The first summation point in (10) is . For any fixed polynomial , the trapezoidal summation formula gives
To verify the endpoint term, apply the trapezoidal formula on the mesh from to . Extending the integral to subtracts , whereas the lower endpoint contributes , up to .
The sum equals . Substitution into (16) shows that the coefficient of is , and that the only parity dependence in the next coefficient comes from
Since , the even second coefficient is smaller than the odd second coefficient by . Their average is rational.
It remains to evaluate the integral. Put . Then
Symmetry of and the beta integral therefore give
Dividing by gives .
For the summand in (10) is exactly . Direct summation yields
Proposition 2.3 gives exact quasipolynomiality for positive . Combine Lemmas 3.1 and 4.1, and set . This proves (2). Because , the degree is . On each residue class of a common period, a polynomial that is has zero coefficients in degrees and . Thus (2) identifies those coefficients of the exact quasipolynomial. Since , the second coefficient has exact period two.
Subtract (2) at consecutive genera. The leading term contributes , the constant part contributes only , and the alternating contribution is
Using gives (3). Both parity constants are strictly positive, so the error is eventually smaller than the leading term in each parity.
5. The complete second coefficient
We now evaluate the constant left implicit in the preceding argument. This also answers the question about in the first version of this paper.
In particular, , , and for every positive . Moreover,
The last statement concerns the coefficients as functions of . It does not make the error in (2) uniform in , and does not give a threshold for the counting conjecture.
The three exceptional contributions
All dimensions in the next argument refer to the coordinates at fixed real . Enlarge the equality arrangement used in Section 3 to include all equations
Delete equations with no solutions in the strict ordering region, and identify equations defining the same hyperplane. Two distinct hyperplanes in this arrangement have an intersection of dimension at most . Their bounded integer sections consequently contribute : choose two coordinates with independent coefficients and fix the other coordinates; at most one solution remains. We may therefore compute the coefficient of away from such intersections. Boundary faces of each resulting region do not affect its leading lattice volume.
Suppose first that a valid tuple is outside the bulk because , where . Closure forces . Away from the discarded intersections this is its only additive equality. Thus , every other element of exceeds , and . For example, would force a second equality for ; any other would force a second equality for . Conversely, these inequalities make all low sums except exceed , and make all hole-minus-low-element differences at most . Excluding sums in costs only the discarded intersections. After scaling , the leading contribution is therefore
Indeed, the free low elements lie in , of length , and the holes lie in , also of length . The forced low element is in the first interval. Dividing by the factorials counts unordered sets. Eliminating the coordinate equal to preserves the integer lattice; no Euclidean surface-area factor enters this volume.
The second positive contribution comes from a valid tuple with and . Closure forces for some . Write . Away from multiple equalities, all the other holes are at most and all elements of are at least . These conditions are also sufficient away from the discarded intersections. At , and . The free holes occupy an interval of length ; the free low elements occupy an interval of length . Hence
Here the eliminated coordinate is , again an integral graph. Tuples violating both bulk inequalities have two distinct equalities and are already in the discarded set.
For the negative contribution, a bulk tuple is invalid exactly when a sum is a hole. Distinct such equalities overlap only on discarded intersections, so their leading contributions add. Fix and put . For each low set , the unordered pairs involving its minimum, including , always have sum in . The other low elements lie in . Among their doubled elements, the permitted interval has half its full length. Among two distinct such elements, the permitted unordered region is a triangle of area . Relative to the volume of all choices of the free low elements, these three contributions have factors
Their sum is . Once a sum is forced to be a hole, the other holes have volume . Consequently the magnitude of the negative coefficient is
The last equality uses symmetry and the beta integral. Each sum-hole hyperplane eliminates a hole coordinate with coefficient one, so the same lattice normalization applies. We have proved, for ,
Evaluation and the bulk average
For , reflection about and an elementary antiderivative give
The second integrand is , the negative derivative of . Thus
For , no valid tuple is outside the bulk: either violated bulk inequality would force . A bulk pair fails only at , so . Hence and, using , we obtain . Formulas (24), (25), and (18) have these same values at . For , all three summands of (18) are negative, proving the asserted sign.
Finally, implies
The remaining terms in (18) are smaller by the same central-binomial estimate and the exponential factor . Taking the ratio proves (19) and completes the proof of Theorem 5.1.
Exact sums for reproducing the leading volumes
The three regions above admit convenient finite counting formulas. These count candidates, with multiplicity for the negative contribution; they are not exact formulas for the correction . For , put
The first formula removes the forced element from the possible free-low positions. For the second, sum over the lower forced hole : the number of available other low elements is . The hockey-stick identity then sums their binomial coefficients. For every , define
A binomial coefficient in these formulas is zero unless its two indices are integers with . The last term counts distinct unordered with . There are such pairs. Set .
The equality-arrangement argument proves
In particular their leading coefficients are , respectively. Formula (29) retains a remainder from multiple additive equalities. It must not be used as an exact identity or as a uniform estimate with increasing.
6. Growing ordinarization and a collision limit
The preceding coefficients suggest the scale . We now establish a limit in which this parameter need not vanish. The argument counts the multiple additive coincidences directly, rather than summing a fixed- asymptotic expansion.
Theorem 6.1.
Let be positive integers varying along a sequence such that
where . If , this is the relative asymptotic . More generally, for every sequence with and ,
The error in (31) is additive. When tends to infinity, no relative estimate with that exponential is asserted.
Let count the valid tuples in the bulk and let count the valid tuples outside it. We use the following three ingredients: a uniform estimate for , a bound for using addition by the multiplicity, and a collision law inside the bulk. Throughout this section, a bound with an absolute implicit constant is independent of and .
The bulk measure and its minimum
Lemma 6.2.
If and , then
For a tuple chosen uniformly from , its minimum satisfies in probability.
Proof.
Put and . The evaluation in Section 4 gives . The function is unimodal, and
For completeness, its maximum occurs at and is . On an interval with fixed small , the factor is bounded below by an absolute positive multiple of . Integrating over this interval gives . The error of a mesh Riemann sum for a unimodal nonnegative function is at most an absolute multiple of its maximum. It follows that
For each fixed , the fraction of this sum on tends to zero: on that interval, , giving an exponentially decreasing bound times a polynomial in .
Every summand in (10) is at most . On , both upper binomial indices are at least . Their falling-factorial products differ from the corresponding powers by a relative , uniformly there. This follows from for ; eventually all factors in question are nonnegative. The polynomial weight outside this interval is negligible by the preceding exponential bound. These upper and lower comparisons prove (32) and transfer the concentration of to the exact bulk weights.
Bounding all valid tuples outside the bulk
We need only the necessary closure conditions coming from addition by . The resulting bound includes semigroups with any number of other additive equalities.
Lemma 6.3.
If and , then
This estimate is on the scale of , not necessarily on the smaller scale of .
Proof.
For a semigroup with multiplicity , the holes form initial segments of the arithmetic-progression chains in with step . Indeed, and imply . Ignoring the finite chain lengths, the number of choices of holes is at most
Suppose and put . The set contains the multiples . In each other residue class modulo , its elements form a terminal segment of the chain in , because adding preserves membership. If there are no such tuples. Otherwise stars and bars bounds the choices of by
The inequality follows because the number of weak compositions into parts is nondecreasing with the sum. There is no positive-genus semigroup with multiplicity one. Consequently the entire low-minimum contribution is at most
For the last inequality, bound the product by and compare the increasing sum with an integral extending to . Using and the central-binomial estimate, the right side of (35), divided by , is
For , the low set has exactly possible choices. Every subset of is an initial-chain hole set; there are such subsets. Thus the number of possible hole sets extending above is at most
Eventually , uniformly in this range, and
Here for . Multiplying by the low-set count and summing over bounds the high contribution by . Together with (35) and Lemma 6.2, this proves (33).
Distinct forbidden sums
In a bulk tuple, write
This counts distinct forbidden hole positions, not pairs producing them. Conditional on and , the holes are a uniform subset of an interval of size . Hence the exact conditional validity probability is
Lemma 6.4.
Under the bulk distribution, if and , then
Proof.
By Lemma 6.2, it suffices to work uniformly on . Put . Conditional on , the elements of are a uniform subset of . Subtract and label them in random order as . Their law is that of independent uniform variables on conditioned to be distinct. The probability of a repeat in the independent sample is , so it suffices to establish the assertions under the independent law.
Let count pairs with . Their corresponding low-element sums are precisely those at most . Each indicator has expectation . Indicators on disjoint pairs are independent, and at most pairs of indicators share an index. Thus and in probability.
Two distinct unordered index pairs have equal sums with probability at most : condition on all but a variable with coefficient or in the equality. There are pairs of such pairs. If counts distinct values among the sums counted by , then is at most the number of equal-sum pairs. Therefore
The sums involving the minimum and the doubled other elements add at most distinct positions, so under the distinct-sample law. Conditioning changes the probability statements by . This proves (37) uniformly in the stipulated range of , and hence under the bulk distribution.
The collision law and the count
For a uniformly chosen bulk tuple, let . Thus is the number of distinct holes which are sums of two low nongaps, and the tuple is valid exactly when .
Proposition 6.5.
Under the hypotheses of Theorem 6.1 with finite , converges in distribution to a Poisson variable of mean . In particular, .
Proof.
Conditionally on , is hypergeometric. If denotes the falling factorial, then
For fixed , the conditional factorial moments therefore tend to in probability. This also holds at , directly by the upper bound below. Since and , there is a constant independent of along this sequence (after finitely many terms) such that, for ,
For the moment is zero. Bounded convergence gives convergence of each unconditional factorial moment. Moreover, for , the finite expansion
is justified by the summable majorant . These are the probability generating functions of the asserted Poisson limit. Equivalently, tightness follows from the bounded first moments, and every subsequential limit has this same generating function. Taking proves the stated zero-collision probability directly.
For finite , combine Proposition 6.5 with (32) and (33), using . If , (36) is at most , with the ratio interpreted as zero if fewer than allowable hole positions remain. The exponent tends to infinity in probability by Lemmas 6.2 and 6.4. The bounded avoidance probability therefore has expectation tending to zero. The same decomposition proves (30) with . Finally, any subsequence of has a further subsequence converging in . Applying the just-proved limits on every such subsequence proves (31).
For finite , the valid tuples outside the bulk also form an fraction of all semigroups with these parameters, since the normalized count has a positive limit. This relative conclusion is not asserted when . The theorem gives no error rate fine enough to subtract consecutive genus counts and prove their sign. It also does not reach proportional to . Both distinctions are essential when comparing this result with the full Bras-Amorós counting conjectures.
7. Consequences, checks, and remaining questions
The first three leading coefficients are , , and . The first two agree with the exact formulas of [2, Proposition 2.1 and Theorem 3.5]. These small values illustrate the general coefficient formula; our contribution concerns arbitrary fixed .
The homogeneous description is also effective in principle. For a specified , form the finite arrangement in the proof of Proposition 2.3, enumerate its rational cells, and compute their Ehrhart quasipolynomials. A common multiple of the vertex denominators bounds a period. The argument gives no efficient bound for this enumeration. Once the finitely many constituents are obtained, eventual positivity of (3) reduces the full monotonicity question for that particular to finitely many genera.
The accompanying Python script compares literal closure with Lemma 2.1 on all tuples through genus , checking all exceptional tuples. Independently generated semigroup trees through genus contain semigroups in total; their counts agree with the tuple counts and the known formulas on the overlapping ranges. Exact rational interpolation tests the bulk’s two leading coefficients for , with additional evaluations beyond the interpolation data. For the revised second-coefficient formula, a separate script checks all tuples through genus , verifies that all nonzero signed residuals satisfy two independent additive equalities, and checks the candidate-sum formulas. Exact rational interpolation of those sums for has holdout evaluations; the resulting coefficients also agree with every residue of the cited exact formula. The growing-ordinarization checks additionally verify the chain conditions for all nonordinary semigroups through genus , compare exact bulk fibers with tree counts, and check the outside-bulk bounds on the same range. Literal closure is checked in each bulk fiber through genus . These finite diagnostics do not replace the general proofs.
Several questions remain. Theorem 5.1 evaluates the previously undetermined constant . One can next determine the full period of , evaluate the lower-dimensional multiple-equality contributions, and find bounds for the onset of strict growth. The stronger conjecture asks for monotonicity at every genus and every ordinarization number. The present argument now evaluates the top two coefficients completely for fixed and leaves those further questions open. Theorem 6.1 separately establishes a growing- limit under . It gives neither a relative exponential estimate when , nor an error rate that decides consecutive differences. Reaching proportional to and controlling the full Bras-Amorós Fibonacci sign remain open.
References
[1] M. Beck and S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, 2nd ed., Undergraduate Texts in Mathematics, Springer, 2015. doi:10.1007/978-1-4939-2969-6.
[2] S. Cyrusian and N. Kaplan, Ordinarization numbers of numerical semigroups, Communications in Algebra (2026), 1–24. doi:10.1080/00927872.2026.2615092. Also arXiv:2506.10222v2; theorem numbering follows this version.