Which simultaneous core families are "regular", and what that predicts

A partition of an integer can be drawn as a staircase of boxes, called a Young diagram. Each box has a "hook length": the boxes to its right, plus the boxes below it, plus itself. A partition is an $s$-core if no hook length is divisible by $s$. It is a simultaneous core if it is an $s$-core for several values of $s$ at once. When the moduli are coprime, only finitely many such partitions exist. A standard tool records each partition by its "β-set", the set of first-column hook lengths. In that language the core condition becomes a closure rule: if $x$ is in the set, so is $x-s$.

The motivating example comes from Xiong. For $(t,t+1)$-cores with distinct parts, he showed that the β-sets are exactly the subsets of $\{1,\dots,t-1\}$ with no two consecutive elements. Such subsets are counted by Fibonacci numbers (Core Partitions with Distinct Parts). "No two consecutive elements" is a rule that a finite-state machine can check while reading the residues $1,2,\dots$ in order.

This note proposes that the same holds much more generally, and that it matters. Our claim is that whenever the moduli are affine in one parameter, as in $(s, ms-r, ms+r)$, the β-set condition can be compiled into one of two kinds of machine. The first is a finite machine whose number of states depends only on $(m,r)$, not on $s$. The second is a machine that also carries one unbounded counter. Which kind a family admits decides three things at once:

  1. which logical fragment computes its counts (bounded or semi-bounded guarded recursion in the sense of Durand et al.);
  2. whether its largest size is an eventually quasi-polynomial function of $s$, computable mechanically for every $m$ rather than for $m\le 3$ only;
  3. where the roots of its statistic polynomials lie, and hence whether their coefficients are log-concave.

Core Claim

Fix $(m,r)$. Encode a β-set of an $(s, ms-r, ms+r)$-core as a word of length about $s$. Letter $i$ records how many β-elements fall in residue class $i$ modulo $s$, stored as a bounded difference from the previous letter where possible.

The shift conditions $x-(ms\pm r)\in\beta$ link only residues that differ by $r$, and the allowed differences are bounded in terms of $m$. So the constraint is local along the word. Two outcomes follow.

Bounded-height families. If an extra condition keeps the running height bounded, the family is recognized by a finite automaton. The condition may be the family's own shift structure, or a restriction such as distinct parts. The automaton has a nonnegative transfer matrix $M(x)$ of size independent of $s$. Here $x$ marks a multiplicative statistic such as the number of β-elements. The generating polynomial of the family is then

$$P_s(x)=u^{\top}M(x)^{\,s}\,v ,$$

where $u$ and $v$ are fixed boundary vectors. The count is $N(s)=P_s(1)$.

Counter families. If height is unbounded, one counter is needed. The ordinary $(s,s+1)$-cores are the standard example: they are counted by Catalan numbers, which are not generated by any finite automaton.

This dichotomy is the key ingredient. Its consequences:

  • Counting complexity. For bounded-height families, $M^s=M^{\lceil s/2\rceil}M^{\lfloor s/2\rfloor}$. This is exactly the halving recursion that Durand et al. use to characterize arithmetic circuits of logarithmic depth with bounded fan-in (#NC¹). So counts fall in $\#Win\text{-}FO(GPR_{\mathrm{bound}})$. Counter families need the semi-unbounded fragment. This resolves the tension that the linear shift constraints of β-sets do not look like halving guards: associativity of the transfer product converts one into the other.
  • Extremal sizes. The largest size becomes a maximum-weight path problem through position-dependent layers, i.e. a product of matrices in which addition is replaced by max. For fixed $(m,r)$ its value is eventually quasi-polynomial in $s$. "At most two maximizers" becomes a statement about ties in that path problem.
  • Root location. When $M(x)$ reduces to a three-term recurrence with the right sign pattern, the polynomials $P_s(x)$ interlace in $s$. They are then real-rooted, so their coefficients are ultra-log-concave by Newton's inequalities. When the recurrence is not of that form, we instead aim to confine the complex roots, in the style of Billey et al., who bound the roots of peak polynomials to force positivity in a binomial basis.

Relation to prior work

Work that motivates the proposal. Xiong's distinct-parts paper builds, in effect, the first bounded-height automaton ("nice subsets" of $\{1,\dots,t-1\}$). He extracts the count $F_{t+1}$, the maximum size $\lfloor (t+1)^2/2\rfloor$ and the average size. He does not study roots, log-concavity, or families beyond $(t,t+1)$. Xiong's results on $(t,mt\pm1)$-cores with distinct parts (Eur. J. Comb.; On the largest sizes of certain simultaneous core partitions with distinct parts) and on consecutive cores (largest size of $(t,\dots,t+p)$-cores; On the largest size of (t, t+1, ..., t+p)-core partitions) show two things: counts per residue collapse to all-or-nothing values, and there are at most two (respectively four) maximizers. We read both as symptoms of a small underlying state space.

Work that supplies the method we must beat. Sha and Xiong introduced generalized-β-sets and hand-designed "adjustments" that strictly increase a size function. With these they settled the Nath–Sellers conjecture for $(s,ms-1,ms+1)$-cores, and they note that current techniques stop around $m\le 3$. Their adjustments are local moves on exactly the word we propose to automate. The difference is that we would derive the maximum from the compiled machine for every $(m,r)$, rather than inventing a new adjustment sequence per case.

Work that supplies analytic tools. Three-term recurrences and their zeros are the subject of the chain-sequence work of Chain sequences and zeros of polynomials related to a perturbed RII type recurrence. We reuse the interlacing viewpoint from it, not its specific recurrence.

Work that constrains the proposal. The matroid result of Liu et al. needed multivariate complete log-concavity precisely because univariate real-rootedness fails for general matroids. This warns us that real-rootedness should be predicted per family, not assumed.

A logical characterization we do not use. Barlag and Vollmer characterize constant-depth real circuits by first-order logic over metafinite structures. Everything here is over the integers, and the relevant depth is logarithmic, not constant. We therefore expect that characterization to be the wrong level and do not use it.

Research Program

The first deliverable is a compiler. Its input is a moduli family affine in $s$, optionally restricted to distinct parts. Its output is either a finite transfer automaton or a one-counter automaton, together with a machine-checkable proof that the automaton's accepted words biject with the family's β-sets for every $s$. The proof works by induction on word length, which is possible because the constraints are local.

The second deliverable is an atlas over $m\le 10$ and small $r$, with and without distinct parts, recording for each family:

  • its type (bounded-height or counter);
  • the size of its automaton;
  • its counting recurrence;
  • the quasi-polynomial for its largest size, with period and extremizers.

The third deliverable is analytic. For the number-of-parts polynomial $P_s(x)$ of each bounded-height family, we either prove real-rootedness by interlacing or give an explicit root-confinement region with its coefficient consequence. For the size statistic itself, whose weight depends on position, we make no real-rootedness claim. Instead we test unimodality and asymptotic normality of the size distribution. That distribution is one of the open "partition statistics" questions in Direction 1.

The logical classification is proved as a corollary. Bounded-height counting is expressed in $GPR_{\mathrm{bound}}$ via the halving decomposition. We then ask whether counter families provably require more, or merely have no known bounded-fan-in formula. The proposal does not claim an unconditional separation.

Baselines

Naive reference point. The naive baseline enumerates all β-sets satisfying the closure rules directly, by depth-first search over subsets of the poset below the Frobenius bound. From these it computes counts, sizes and maximizers. It is exact, so it serves as ground truth for small $s$. Its cost grows with the family size, which is exponential in $s$. We run it on the same machine as the compiler, with the same wall-clock budget per family. Our method beats it if it (a) agrees exactly wherever enumeration finishes, and (b) extends to values of $s$ and $m$ where enumeration times out.

Strongest existing method. The strongest competitor is the Sha–Xiong adjustment method, because it is the only method with proven largest-size results for $(s,ms-1,ms+1)$-cores. There is no runtime or coverage number to compare against: no reported result found on Lacuna for any computational benchmark on simultaneous-core extremal problems. Its "score" is qualitative. It yields a theorem for $m\le 3$, and the authors identify larger $m$ as open.

A fair comparison has two parts. First, our pipeline must reproduce their formula, and Xiong's $\lfloor (t+1)^2/2\rfloor$ and maximizer counts, with no family-specific input. Second, it must produce certified formulas for $m=4,\dots,10$. Beating this baseline means certified coverage of families their method has not reached.

Guess-and-check baseline. Compute $N(s)$ and the largest size for small $s$, then fit linear recurrences or quasi-polynomials of increasing order with standard computer algebra. It gets the same data budget as our pipeline: the same $s$ range from the enumerator.

Ablation for the key ingredient. We run the path-maximization and transfer computation on the uncompressed state, which stores the full per-residue count vector, instead of the compiled bounded-height alphabet. If the compressed and uncompressed pipelines scale identically, the claimed dichotomy is not what is doing the work.

Ablation for the root-location mechanism. We compute roots of $P_s(x)$ for counter families and for bounded-height families whose matrices lack the interlacing sign pattern. If these are also always real-rooted, the structural explanation is wrong, or at least not the operative one.

Why not just…?

Why not just guess recurrences from computed data? This is the real threat. For any single family, guessing will likely find the correct formula faster than building a compiler. What guessing cannot do is certify the formula for all $s$, bound the recurrence order in advance, or explain why a family is Fibonacci-like rather than Catalan-like. The compiler supplies an a priori state bound, and that bound turns a guess into a proof. We will run guessing as a baseline. If it finds formulas our automata then fail to certify, the compiler is incomplete. If guessed recurrences for bounded-height families exceed our automaton-size bound, our encoding claim is false.

Why not just extend Sha–Xiong adjustments case by case? It may work for $m=4$. But each case has so far needed a new sequence of moves, and the authors themselves flag the $m\le 3$ barrier. Our experiment settles it directly: if the maximizers found by the path computation for $m\ge 4$ are reachable by the existing adjustment types, their method generalizes and ours is merely a faster route. If new move types appear, that explains why case-by-case extension stalled.

Why not prove log-concavity with complete log-concavity, as for matroids? Liu et al. needed that machinery because matroid polynomials are not real-rooted. The sampling consequences in Chen et al. likewise rest on matroid structure that β-set posets do not obviously have. Generating polynomials of order ideals of general posets are not log-concave in general. The transfer matrix gives a more specific handle when it exists. We keep complete log-concavity as the fallback for families where interlacing fails, and we test it numerically on the quadratic reductions Chen et al. describe.

Why not train a graph neural network on β-set posets? Grohe shows that bounded-depth graph neural networks stay within TC⁰-type queries. On the BREC expressiveness benchmark the best model in the benchmark paper reaches only 70.2% accuracy (BREC). More to the point, a learned predictor yields neither exact values nor proofs, and this problem needs both. We do not include it as a baseline.

Proposed Experiments

Ground truth comes from the proven results in the file: Xiong's $F_{t+1}$ count, the $\lfloor (t+1)^2/2\rfloor$ maximum and the Fibonacci-convolution average for $(t,t+1)$-cores with distinct parts; the at-most-two maximizers for $(t,mt\pm1)$-cores with distinct parts; the 1-or-2 maximizers by parity of $t$ for $(t,t+1,t+2)$-cores; and Sha–Xiong's largest size for $(s,ms\pm1)$-type families.

First decisive check. The compiler, given only the moduli, must reproduce all of these exactly, and must classify $(t,t+1)$-cores without the distinct-parts restriction as counter-type. That second requirement is a check against their Catalan count.

Second check. For $m$ from 4 to 10, compare compiled largest sizes and maximizer counts against brute-force enumeration for every $s$ the enumerator reaches. Record where the quasi-polynomial period stabilizes.

Third check. For every bounded-height family, compute the roots of $P_s(x)$ for $s$ up to several hundred. Test whether real-rootedness holds exactly in the families whose matrices have the interlacing sign pattern, and fails in at least some that lack it. Report the coefficient shape of the size distribution: unimodality, and variance growth compared with the Gaussian prediction.

The proposal is falsified in its central claim if either of two things happens. One is a moduli family with local shift constraints that is neither finite-state nor one-counter. The other is a bounded-height family whose largest size fails to be eventually quasi-polynomial.