A Chinese Remainder Theorem for Partitions

Seethalakshmi K and Steven Spallone

Mathematical Sciences Institute, The Australian National University, Canberra, Australia [email protected] Indian Institute of Science Education and Research, Pune-411021,Maharashtra,India [email protected]

Abstract.

Let $s,t$ be natural numbers, and fix an $s$ -core partition $\sigma$ and a $t$ -core partition $\tau$ . Put $d=\gcd(s,t)$ and $m=\operatorname{lcm}(s,t)$ , and write $N_{\sigma,\tau}(k)$ for the number of $m$ -core partitions of length no greater than $k$ whose $s$ -core is $\sigma$ and $t$ -core is $\tau$ . We prove that for $k$ large, $N_{\sigma,\tau}(k)$ is a quasipolynomial of period $m$ and degree $\frac{1}{d}(s-d)(t-d)$ .

Key words and phrases:

t-core partitions, Ehrhart’s Theorem, transportation polytopes

1. Introduction

For a partition $\lambda$ and a natural number $t$ , the $t$ -core of $\lambda$ , written $\operatorname{core}_{t}\lambda$ , is obtained by removing hooks of size $t$ from the Young diagram of $\lambda$ , until no more can be removed. This analogue of the Division Algorithm has its origins in the representation theory of the symmetric group [Nakayama], and finds application in the study of the partition function [wildon2008counting]. We present an analogue of the Chinese Remainder Theorem in this paper.

Write $\mathcal{C}_{t}$ for the set of $t$ -cores. Suppose $s,t\in\mathbb{N}$ are relatively prime, and consider the map

\operatorname{core}_{s,t}:\mathcal{C}_{st}\to\mathcal{C}_{s}\times\mathcal{C}_{t}

taking $\lambda$ to $(\operatorname{core}_{s}\lambda,\operatorname{core}_{t}\lambda)$ . This map $\operatorname{core}_{s,t}$ is surjective ([fayers2014generalisation], Section 5.1), but far from injective. In fact the fibres are infinite. To capture their behavior we stratify them by length as follows.

Given a partition $\lambda$ , write $\ell(\lambda)$ for its length, meaning the number of parts of $\lambda$ . For a fixed $(\sigma,\tau)\in\mathcal{C}_{s}\times\mathcal{C}_{t}$ , let $m=st$ and put

(1)

N_{\sigma,\tau}(k)=\#\{\lambda\in\mathcal{C}_{m}\mid\operatorname{core}_{s}\lambda=\sigma,\>\operatorname{core}_{t}\lambda=\tau,\>\ell(\lambda)\leq k\}.

In other words, $N_{\sigma,\tau}(k)$ is the cardinality of the $k$ th stratum,

(2)

\operatorname{core}_{s,t}^{-1}(\sigma,\tau)\cap\mathcal{C}_{m}^{k}

where $\mathcal{C}_{m}^{k}$ is the set of $m$ -cores of length no greater than $k$ .

Our first result is:

Theorem 1.

Let $s,t\in\mathbb{N}$ be relatively prime. There is a quasipolynomial $Q_{\sigma,\tau}(k)$ of degree $(s-1)(t-1)$ and period $st$ , so that for integers $k\gg 0$ , we have $N_{\sigma,\tau}(k)=Q_{\sigma,\tau}(k)$ . The leading coefficient of $Q_{\sigma,\tau}(k)$ is a positive number $V_{s,t}$ depending only on $s$ and $t$ .

Here a “quasipolynomial of period $n$ ” is a function on natural numbers whose restriction to each coset $n\mathbb{N}+i$ is a polynomial; see Section 4. The quantity $V_{s,t}$ is the volume of a certain polytope we define in Section LABEL:sec:_proofs_of_thm_1_and_3.

Remark 1.

If $\sigma=\tau$ , then $\sigma$ is simultaneously an $s$ -core and a $t$ -core. In fact, the intersection $\mathcal{C}_{s}\cap\mathcal{C}_{t}$ is finite and well-studied; see [anderson2002partitions] and [fayers2011t].

Our method is as follows. We associate to $\tau\in\mathcal{C}_{t}^{k}$ a multiset $H_{\tau,t}^{k}$ on $\{0,1,\ldots,t-1\}$ of size $k$ , corresponding to the first column hook lengths of $\tau$ modulo $t$ . (This is James’ theory of abacuses [james1984representation, page 78].) Members of (2) correspond to matchings between $H_{\sigma,s}^{k}$ and $H_{\tau,t}^{k}$ . (See Section LABEL:sec:_Counting_fibres_of_the_Sun_Tzu_map.)

Generally, let $F,G$ be multisets of the same size, with multiplicity vectors $\vec{F}$ , $\vec{G}$ . Write $\mathcal{M}(\vec{F},\vec{G})$ for the polytope of real matrices with nonnegative entries, row margins $\vec{F}$ , and column margins $\vec{G}$ . Then the matchings between $F$ and $G$ correspond bijectively with the integer points of $\mathcal{M}(\vec{F},\vec{G})$ .

In our situation, the polytopes $\mathcal{M}$ grow linearly in $k$ , and we may apply Ehrhart’s theory, which says that if $\mathcal{P}$ is a polytope with integer vertices, then the number of integer points in $n\cdot\mathcal{P}$ is a polynomial in $n$ . We refer the reader to Section 4.6.2 of [Stanley], and Chapter 3 of [beck2007computing]. The degree of the polynomial is the dimension of $\mathcal{P}$ , and its leading coefficient is the relative volume of $\mathcal{P}$ .

When $\sigma=\tau=\emptyset$ , and $k$ is a multiple of $st$ , this directly gives our result. The technical heart of this paper is extending Ehrhart’s Theorem to all fibres and all $k$ .

The polytopes $\mathcal{M}(\vec{F},\vec{G})$ arising from row/column constraints are called “transportation polytopes”. Each can be expressed in the form

\mathcal{P}(A,\vec{b})=\{\vec{x}\mid A\vec{x}\leq\vec{b},\vec{x}\geq 0\},

for some totally unimodular matrix $A$ , meaning that all the minors of $A$ are either $0,1$ , or $-1$ . Write $N(A,\vec{b})$ for the number of integer points in the polytope $\mathcal{P}(A,\vec{b})$ . Our extension of Ehrhart’s Theorem is:

Theorem 2.

Let $A$ be an $m\times n$ totally unimodular matrix and $\vec{b},\vec{c}\in\mathbb{Z}^{m}$ . Suppose $A$ does not have any zero rows, and that $\mathcal{P}(A,\vec{b})$ is bounded of dimension $n$ . Then there is a polynomial $f(k)$ so that for integers $k\gg 0$ , we have $N(A,\vec{b}k+\vec{c})=f(k)$ . Moreover $\deg f=n$ and the leading coefficient of $f$ is the volume of $\mathcal{P}(A,\vec{b})$ .

Note that Ehrhart’s Theorem gives the case $\vec{c}=0$ .

Next, suppose $s$ and $t$ are not relatively prime. Let $d=\gcd(s,t)$ , $m=\operatorname{lcm}(s,t)$ and $\ell_{0}=\max(\ell(\sigma),\ell(\tau))$ . Again define $N_{\sigma,\tau}(k)$ by (1).

Theorem 3.

If $\operatorname{core}_{d}(\sigma)=\operatorname{core}_{d}(\tau)$ , then there is a quasipolynomial $Q_{\sigma,\tau}(k)$ of degree $\frac{1}{d}(s-d)(t-d)$ and period $m$ , so that for integers $k\gg 0$ , we have $N_{\sigma,\tau}(k)=Q_{\sigma,\tau}(k)$ . The leading coefficient of $Q_{\sigma,\tau}(k)$ is $\left(V_{\frac{s}{d},\frac{t}{d}}\right)^{d}$ .

(It is easy to see that if $\operatorname{core}_{d}(\sigma)\neq\operatorname{core}_{d}(\tau)$ , then each $N_{\sigma,\tau}(k)=0$ .)

We mention also a simpler related result for the fibres of the map $\operatorname{core}_{s}:\mathcal{C}_{st}\rightarrow\mathcal{C}_{s}$ taking an $st$ -core to its $s$ -core. For $\sigma\in\mathcal{C}_{s}$ , let

N_{\sigma}(k)=\{\lambda\in\mathcal{C}_{st}\mid\operatorname{core}_{s}\lambda=\sigma,\ell(\lambda)\leq k\}.

Theorem 4.

There is a quasipolynomial $Q_{\sigma}(k)$ of degree $s(t-1)$ and period $s$ , so that for $k\geq\ell(\sigma)$ , we have $N_{\sigma}(k)=Q_{\sigma}(k)$ . The leading coefficient of $Q_{\sigma}(k)$ is $\dfrac{1}{(t-1)!^{s}}$ .

The layout of this paper is as follows. In Section 2, we recall terminology for partitions and multisets, and in Section 3, we review James’ Theory of abacuses for computing $t$ -cores. Theorem 4 is worked out in Section 4, as a warm up to later material. Section 5 converts the fibre counting problem into a multiset matching problem. Preliminaries for polytopes are given in Section LABEL:sec:_Preliminaries_of_polytopes_and_notation. Our theory of integer points in polytopes, including Theorem 2, is contained in Section LABEL:sec:_Counting_integer_points_in_polytopes. Finally in Section LABEL:sec:_proofs_of_thm_1_and_3 we apply this to our core problem, giving Theorems 1 and 3.

Acknowledgments

The authors would like to thank Amritanshu Prasad for useful conversations on totally unimodular matrices and polytopes, Brendan McKay for pointing us to Ehrhart theory, and Jyotirmoy Ganguly, Ojaswi Chaurasia and Ragini Balachander for helpful discussions.

2. Preliminaries

Write $\mathbb{N}=\{1,2,\ldots\}$ for the set of natural numbers and $\underline{\mathbb{N}}=\{0,1,2,\ldots\}$ for the set of whole numbers. If $S$ is a set, write ‘ $\operatorname{id}_{S}$ ’ for the identity map. If $f:S\to T$ is a map, write ‘ $\operatorname{im}f$ ’ for the image of $f$ . We write $\wp_{\operatorname{fin}}(S)$ for the set of finite subsets of $S$ .

2.1. Multisets

Let $S$ be a set. When $S$ is a finite set, we write either ‘ $\#S$ ’ or ‘ $|S|$ ’ for the cardinality of $S$ . For $k\in\underline{\mathbb{N}}$ , write $\binom{S}{k}$ for the set of $k$ -element subsets of $S$ . Note that $\#\binom{S}{k}=\binom{\#S}{k}$ .

A multiset on $S$ is a function $F$ from $S$ to $\underline{\mathbb{N}}$ . The cardinality of $F$ is the sum

|F|=\sum_{s\in S}F(s).

The support of a multiset $F$ is

\operatorname{supp}(F)=\{s\in S\mid F(s)\neq 0\}.

Write ‘ $\big{(}\!\tbinom{S}{k}\!\big{)}$ ’ for the set of multisets on $S$ of cardinality $k$ . Note that $\#\big{(}\!\tbinom{S}{k}\!\big{)}=\big{(}\!\tbinom{\#S}{k}\!\big{)}$ , where

\bigg{(}\!\!\dbinom{n}{k}\!\!\bigg{)}=\binom{k+n-1}{k}.

Write $\mathcal{M}_{\operatorname{fin}}(S)$ for the set of multisets on $S$ with finite support. Thus

\mathcal{M}_{\operatorname{fin}}(S)=\bigcup_{k\geq 0}\bigg{(}\!\!\dbinom{S}{k}\!\!\bigg{)}.

Given finite sets $S,T$ and a map $f:S\to T$ , define $f_{*}:\mathcal{M}_{\operatorname{fin}}(S)\to\mathcal{M}_{\operatorname{fin}}(T)$ by

f_{*}(F)(t)=\sum\limits_{s\in f^{-1}(t)}F(s).

We use the same notation to denote the restriction $f_{*}:\big{(}\!\tbinom{S}{k}\!\big{)}\to\big{(}\!\tbinom{T}{k}\!\big{)}$ , when $k$ is understood.

Lemma 1.

For $G\in\mathcal{M}_{\operatorname{fin}}(T)$ , we have

\#(f_{*})^{-1}(G)=\prod_{t\in T}\big{(}\!\tbinom{\#f^{-1}(t)}{G(t)}\!\big{)}.

Proof.

We need to count the $F\in\mathcal{M}_{\operatorname{fin}}(S)$ such that for all $t\in T$ , we have

\begin{split}G(t)&=f_{*}(F)(t)\\ &=\sum_{s\in f^{-1}(t)}F(s).\\ \end{split}

There are $\big{(}\!\tbinom{\#f^{-1}(t)}{G(t)}\!\big{)}$ many choices for the values of $F$ on the fibre over $t\in T$ . Multiplying these gives the formula. ∎

Note that

\operatorname{im}f_{*}=\{H\in\mathcal{M}_{\operatorname{fin}}(T)\mid\operatorname{supp}(H)\subseteq\operatorname{im}(f)\}.

For maps $f:S\to T$ and $g:T\to U$ , note that $\left(g\circ f\right)_{*}=g_{*}\circ f_{*},$ and $\left(\operatorname{id}_{S}\right)_{*}=\operatorname{id}_{\big{(}\!\tbinom{S}{k}\!\big{)}}$ . This makes the association $S\leadsto\mathcal{M}_{\operatorname{fin}}(S)$ a functor from the category of sets to itself.

2.2. Partitions and Pseudopartitions

A partition $\lambda$ is a weakly decreasing finite sequence of natural numbers. Thus $\lambda=\left(a_{1},a_{2},\ldots,a_{\ell}\right)$ , with $a_{1}\geq a_{2}\geq\cdots\geq a_{\ell}>0$ . In these terms $a_{1}+a_{2}+\cdots+a_{\ell}$ is the size of $\lambda$ , and $\ell=\ell(\lambda)$ is the length of $\lambda$ . We allow the empty partition $\lambda=\emptyset$ ; its length is $0$ . Write $\Lambda$ for the set of partitions, and $\Lambda^{\ell}$ for the set of partitions of length $\ell$ .

We define pseudopartitions to be weakly decreasing finite sequences of whole numbers. Thus $\lambda=\left(a_{1},a_{2},\ldots,a_{\ell}\right)$ , with $a_{1}\geq a_{2}\geq\cdots\geq a_{\ell}\geq 0$ . Again, $\ell$ is the length of $\lambda$ . For instance $\lambda=(5,4,3,1,0,0)$ is a pseudopartition of length $6$ , with $2$ “trailing zeros”. Write $\underline{\Lambda}$ for the set of pseudopartitions, and $\underline{\Lambda}^{k}$ for the set of pseudopartitions of length $k$ . Let $z:\underline{\Lambda}\to\underline{\Lambda}$ be the map which adds a trailing zero to the end of a pseudopartition. For instance $z((5,4,0))=(5,4,0,0)$ . If $\lambda$ is a pseudopartition of length $\ell\leq k$ , define

u^{k}(\lambda)=z^{k-\ell}(\lambda)\in\underline{\Lambda}^{k}.

Write $r:\underline{\Lambda}\to\Lambda$ for the map which removes all trailing zeros from the pseudopartition to make it a partition, e.g., $r((5,4,3,1,0,0))=(5,4,3,1)$ . The fibres of $r$ are the $z$ -orbits of partitions.

2.3. Young Diagrams

The Young diagram of a partition $\lambda=\left(a_{1},a_{2},\ldots,a_{\ell}\right)$ is given by

\mathcal{Y}(\lambda)=\{(i,j)\in\mathbb{N}\times\mathbb{N}\mid 1\leq i\leq\ell,1\leq j\leq a_{i}\}.

It is visualized as a collection of left justified cells arranged in rows with $a_{i}$ cells in the $i$ -th row.

Example 1.

Here is $\mathcal{Y}((5,4,3,1))$ :

\ytableausetup

centertableaux \ytableaushort,\none, \none * 5,4,3,1

The hook $\mathfrak{h}_{c}$ associated to a cell $c$ of $\mathcal{Y}(\lambda)$ consists of all cells to the right of $c$ and below $c$ , together with $c$ itself. The hooklength is the total number of cells in the hook. In the above diagram, the hooklength for the $(1,1)$ -cell is $8$ . A hook with hooklength $t$ is called a $t$ -hook.

Remark 2.

It would be more consistent to say “hooksize” rather than “hooklength”, but the usage is standard.

Of particular importance are the hooklengths corresponding to cells in the first column of $\mathcal{Y}(\lambda)$ ; we can use these to reconstruct $\lambda$ . The set of first column hooklengths in Example 1 is $\{8,6,4,1\}$ .

2.4. Beta sets

The map which takes a partition $\lambda$ to the set of first column hooklengths of $\mathcal{Y}(\lambda)$ gives a bijection between $\Lambda$ and $\wp_{\operatorname{fin}}(\mathbb{N})$ . In this paragraph we extend this to a bijection between $\underline{\Lambda}$ and $\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ .

Define $\beta:\underline{\Lambda}\to\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ by

\beta((a_{1},a_{2},\ldots,a_{\ell}))=\{a_{1}+(\ell-1),a_{2}+(\ell-2),\ldots,a_{\ell}\}.

The inverse $\beta^{-1}:\wp_{\operatorname{fin}}(\underline{\mathbb{N}})\to\underline{\Lambda}$ is given by

\beta^{-1}(\{h_{1},\ldots,h_{\ell}\})=(h_{1}-(\ell-1),h_{2}-(\ell-2),\ldots,h_{\ell}),

for $h_{1}>\cdots>h_{\ell}\geq 0$ . When $\lambda$ is a partition, $\beta(\lambda)$ is the set of first column hooklengths of $\mathcal{Y}(\lambda)$ . We also write ‘ $H_{\lambda}$ ’ for $\beta(\lambda)$ .

The “add a trailing zero” map $z$ translates under $\beta$ to

Z=\beta\circ z\circ\beta^{-1}:\wp_{\operatorname{fin}}(\underline{\mathbb{N}})\to\wp_{\operatorname{fin}}(\underline{\mathbb{N}}),

which comes out to be

\{x_{1},\ldots,x_{\ell}\}\mapsto\{x_{1}+1,\ldots,x_{\ell}+1,0\}.

Similarly we can translate $u^{k}$ to

U^{k}=\beta\circ u^{k}\circ\beta^{-1}.

Definition 1.

Let $\lambda$ be a partition. A beta set of $\lambda$ is a set of the form $Z^{j}(\beta(\lambda))$ for some $j\in\underline{\mathbb{N}}$ .

Example 2.

Let $\lambda=(5,4,3,1)$ . Then $H_{\lambda}=\{8,6,4,1\}$ , so the beta sets of $\lambda$ are:

\{8,6,4,1\}\overset{Z}{\mapsto}\{9,7,5,2,0\}\overset{Z}{\mapsto}\{10,8,6,3,1,0\}\overset{Z}{\mapsto}\ldots

Definition 2.

If $\lambda$ is a partition of length $\ell\leq k$ , write $H_{\lambda}^{k}$ for the beta set of $\lambda$ with cardinality $k$ , i.e.,

H_{\lambda}^{k}=U^{k}(H_{\lambda})=Z^{k-\ell}(H_{\lambda}).

In the example above, $H_{\lambda}^{6}=\{10,8,6,3,1,0\}$ .

The $\beta$ -set version of the “remove all trailing zeros” retraction $r$ is

R=\beta\circ r\circ\beta^{-1}:\wp_{\operatorname{fin}}(\underline{\mathbb{N}})\to\wp_{\operatorname{fin}}(\mathbb{N}).

It can be computed directly as follows. Given $X\in\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ with $0\in X$ , put

m=\min(\underline{\mathbb{N}}-X),

i.e., the smallest whole number not in $X$ . Then $R(X)$ is obtained by removing $\{0,\ldots,m-1\}$ from $X$ and subtracting $m$ from the remaining members. Of course, if $0\notin X$ , then $R(X)=X$ .

3. Cores

Definition 3.

A $t$ -core is a partition having no $t$ -hook in its Young diagram. Write $\mathcal{C}_{t}$ for the set of $t$ -cores, and put

\mathcal{C}_{t}^{k}=\{\lambda\in\mathcal{C}_{t}\mid\ell(\lambda)\leq k\}.

3.1. Hook Removal

Suppose $\lambda$ is a partition whose Young diagram contains a $t$ -hook $\mathfrak{h}$ . One may remove $\mathfrak{h}$ from $\mathcal{Y}(\lambda)$ by simply deleting $\mathfrak{h}$ , then moving any disconnected cells one unit up and one unit to the left.

Example 3.

The removal of a 6-hook from the partition $(5,4,3,1)$ :

\ydiagram

[*(white)] 5,0,1+2,0 *[*(black!25)]5,4,3,1 $\leadsto$ \ydiagram5,0,1+2 $\leadsto$ \ydiagram5,2

In fact, if we remove $t$ -hooks successively until no $t$ -hook remains, the final Young diagram does not depend on the choices of hooks at each step. The corresponding partition is called the $t$ -core of $\lambda$ , and denoted ‘ $\operatorname{core}_{t}\lambda$ ’.

Example 4.

We remove $6$ -hooks successively from the Young diagram of $(5,4,3,1)$ to obtain its $6$ -core, which is the partition $(1)$ . In Example 3 we removed a 6-hook from $(5,4,3,1)$ to get $(5,2)$ , continuing from there we remove the remaining 6-hook:

\ydiagram

[*(white)] 0,1+1 *[*(black!25)]5,2 $\to$ \ydiagram0,1+1

Lemma 2.

Let $\lambda$ be a partition, and $X=\{x_{1},\ldots,x_{k}\}$ a $\beta$ -set for $\lambda$ . Then $\mathcal{Y}(\lambda)$ has a $t$ -hook iff $\exists\hskip 2.84544pt1\leq i\leq k$ so that $x_{i}\geq t$ and $x_{i}-t\notin X$ . In this case, there is a $t$ -hook $\mathfrak{h}$ of $\mathcal{Y}(\lambda)$ so that

(3)

\{x_{1},\ldots,x_{i}-t,\ldots,x_{k}\}

is a $\beta$ -set for $\lambda\backslash\mathfrak{h}$ .

Proof.

This is [james1984representation, Lemma 2.7.13]. ∎

Example 5.

The sequence of hook removals in Example 4 corresponds to the sequence

\{8,6,4,1\}\leadsto R(\{8,0,4,1\})=\{6,2\}\leadsto R(\{0,2\})=\{1\}

of $\beta$ -sets.

3.2. $\beta$ -set Version

Fix $t\geq 1$ .

Definition 4.

A subset $X$ of $\underline{\mathbb{N}}$ is $t$ -reduced, provided whenever $x\in X$ with $x\geq t$ , we have $x-t\in X$ . Write $\mathcal{R}_{t}$ for the set of finite $t$ -reduced subsets of $\mathbb{N}$ , and $\underline{\mathcal{R}}_{t}$ for the set of finite $t$ -reduced subsets of $\underline{\mathbb{N}}$ .

For example, $X=\{0,1,3,4,6\}$ is $3$ -reduced but not $2$ -reduced. We view $\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ , and thus $\underline{\mathcal{R}}_{t}$ , inside $\mathcal{M}_{\operatorname{fin}}(\underline{\mathbb{N}})$ via recognizing a subset of $\underline{\mathbb{N}}$ as a multiset on $\underline{\mathbb{N}}$ . Note that the retraction $R$ maps $\underline{\mathcal{R}}_{t}$ to $\mathcal{R}_{t}$ .

Let

f_{t}:\underline{\mathbb{N}}\to\mathbb{Z}/t\mathbb{Z}

be the usual remainder mod $t$ map, and let

\rho_{t}=(f_{t})_{*}:\mathcal{M}_{\operatorname{fin}}(\underline{\mathbb{N}})\to\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/t\mathbb{Z})

be the induced map on multisets.

The subset $\underline{\mathcal{R}}_{t}$ is a transversal for $\rho_{t}$ , in the sense that for each $F\in\mathcal{M}_{\operatorname{fin}}(\underline{\mathbb{N}})$ there is a unique $F_{0}\in\underline{\mathcal{R}}_{t}$ with $\rho_{t}(F)=\rho_{t}(F_{0})$ .

Remark 3.

For $X\in\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ , the map $X\mapsto X_{0}$ is traditionally visualized in terms of a base $t$ abacus, having $t$ runners labeled $0$ to $t-1$ , on which beads may be stacked. Given $X$ , beads are arranged on the abacus corresponding to their base $t$ place value of members of $X$ . To bring $X$ to $t$ -reduced form, one simply slides the beads up. This is James’ abacus method from [james1984representation, page 78].

For example, given $X=\{8,6,4,1\}$ and $t=6$ , the abacus method

$\begin{array}[]{cccccc}\overline{0}&\overline{1}&\overline{2}&\overline{3}&\overline{4}&\overline{5}\\ \hline\cr\circ&\bullet&\circ&\circ&\bullet&\circ\\ \bullet&\circ&\bullet&\circ&\circ&\circ\end{array}\hskip 28.45274pt\leadsto\hskip 28.45274pt\begin{array}[]{cccccc}\overline{0}&\overline{1}&\overline{2}&\overline{3}&\overline{4}&\overline{5}\\ \hline\cr\bullet&\bullet&\bullet&\circ&\bullet&\circ\\ \circ&\circ&\circ&\circ&\circ&\circ\\ \end{array}$

gives $X_{0}=\{4,2,1,0\}.$

The map $\rho_{t}$ has a “minimal” section

c_{t}:\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/t\mathbb{Z})\to\mathcal{M}_{\operatorname{fin}}(\underline{\mathbb{N}})

with image equal to $\underline{\mathcal{R}}_{t}$ , described as follows. Given $F\in\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/t\mathbb{Z})$ , put

c_{t}(F)=\bigcup_{i=0}^{t-1}\{at+i\mid 0\leq a\leq F(i)\}.

Thus the map $F\mapsto F_{0}$ above is $c_{t}\circ\rho_{t}$ .

Definition 5.

Given $X\in\wp_{\operatorname{fin}}(\underline{\mathbb{N}})$ , put

\operatorname{Core}_{t}(X)=R(c_{t}(\rho_{t}(X))).

Proposition 1.

If $\lambda$ is a pseudopartition, then

\operatorname{core}_{t}(r(\lambda))=\beta^{-1}(\operatorname{Core}_{t}(\beta(\lambda))).

Proof.

Let $X=\beta(\lambda)$ , and suppose $X_{0}$ is obtained from $X$ by a sequence of steps, where each step replaces some $x_{i}\geq t$ with $x_{i}-t$ , so long as $x_{i}-t\notin X$ . By Lemma 2, $X_{0}$ is a $\beta$ -set for $\operatorname{core}_{t}(r(\lambda))$ .

By construction, $X_{0}\in\underline{\mathcal{R}}_{t}$ , with $\rho_{t}(X)=\rho_{t}(X_{0})$ . By the above, we must have $c_{t}(\rho_{t}(X))=X_{0}$ . It follows that $R(c_{t}(\rho_{t}(X)))=\beta(\operatorname{core}_{t}(r(\lambda)))$ , and the proposition follows. ∎

Example 6.

Let $t=6$ . For $\lambda=(5,4,3,1)$ , $X=H_{\lambda}=\{8,6,4,1\}$ . Put $F=\rho_{t}(X)$ . Then $\operatorname{supp}F=\{0,1,2,4\}$ , and $F$ takes value $1$ at each point in its support. Thus

c_{t}(X)=\{0\}\cup\{1\}\cup\{2\}\cup\{4\}=\{4,2,1,0\},

and therefore

\begin{split}\operatorname{core}_{6}(5,4,3,1)&=\beta^{-1}(R(\operatorname{Core}_{6}(X)))\\ &=\beta^{-1}(\{1\})\\ &=(1).\end{split}

For a partition $\lambda$ of length no greater than $k$ , let

(4)

H_{\lambda,t}^{k}=\rho_{t}(H_{\lambda}^{k})\in\big{(}\!\tbinom{\mathbb{Z}/t\mathbb{Z}}{k}\!\big{)}.

Proposition 2.

The map $\mathscr{A}_{t}:\mathcal{C}_{t}^{k}\to\big{(}\!\tbinom{\mathbb{Z}/t\mathbb{Z}}{k}\!\big{)}$ taking $\lambda\mapsto H_{\lambda,t}^{k}$ is a bijection. Thus

\#\mathcal{C}_{t}^{k}=\binom{k+t-1}{k}.

(Compare [zhong2020bijections, Theorem 2.4].)

Proof.

We have

\mathscr{A}_{t}=\rho_{t}\circ\beta\circ u^{k}.

Let us see that

(5)

\mathscr{A}_{t}^{-1}=r\circ\beta^{-1}\circ c_{t}:\big{(}\!\tbinom{\mathbb{Z}/t\mathbb{Z}}{k}\!\big{)}\to\mathcal{C}_{t}^{k}.

is in fact inverse to $\mathscr{A}_{t}$ . On the one hand,

\begin{split}\rho_{t}\>\beta\>u^{k}\>r\>\beta^{-1}\>c_{t}&=\rho_{t}\>U^{k}\>R\>c_{t}\\ &=\rho_{t}\>c_{t}\\ &=\operatorname{id}\text{ on $\big{(}\!\tbinom{\mathbb{Z}/t\mathbb{Z}}{k}\!\big{)}$}.\\ \end{split}

On the other hand,

\begin{split}r\>\beta^{-1}\>c_{t}\>\rho_{t}\>\beta\>u^{k}&=\beta^{-1}\>R\>c_{t}\>\rho_{t}\>\beta\>u^{k}\\ &=\operatorname{core}_{t}\circ\>r\>u^{k}\\ &=\operatorname{core}_{t}\\ &=\operatorname{id}\text{ on $\mathcal{C}_{t}^{k}$}.\qed\end{split}

Note that

H^{k}_{\operatorname{core}_{t}\lambda,t}=H_{\lambda,t}^{k}.

Lemma 3.

For $i\geq\ell(\lambda)$ , we have

H_{\lambda,t}^{i+t}(j)=H_{\lambda,t}^{i}(j)+1.

By definition,

\begin{split}H_{\lambda}^{i+t}&=Z^{t}(H_{\lambda}^{i})\\ &=(H_{\lambda}^{i}+t)\cup\{t-1,t-2,\ldots,0\}.\\ \end{split}

Hence the multiplicity of $j$ in $(H_{\lambda}^{i+t}\mod t)$ is one more than its multiplicity in $H_{\lambda}^{i}$ .

4. Reducing a $t$ -core modulo a divisor of $t$

In this section we enumerate the fibres of the retractions

\operatorname{core}_{b}:\mathcal{C}_{a}^{k}\to\mathcal{C}_{b}^{k},

when $b$ is a divisor of $a$ . In particular, we demonstrate that the size of these fibres is quasipolynomial in $k$ . This could be regarded as a warm-up for our main theorems.

Definition 6.

A function $f:\mathbb{N}\rightarrow\mathbb{\mathbb{Q}}$ is a quasipolynomial, provided there exists a positive integer $p$ so that for each $0\leq i<p$ , the function

n\mapsto f(i+np)

where $n\in\underline{\mathbb{N}}$ is a polynomial. The degree of $f$ is the maximum of the degrees of these polynomials. The integer $p$ is a period of $f$ .

This definition is equivalent to the one in [Stanley, Section 4.4].
Let

f_{b}^{a}:\mathbb{Z}/a\mathbb{Z}\to\mathbb{Z}/b\mathbb{Z}

be the usual remainder mod $b$ map, and let

\rho_{b}^{a}=(f_{b}^{a})_{*}:\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/a\mathbb{Z})\to\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/b\mathbb{Z})

be the induced map on multisets. We use the same notation for the restriction

\rho_{b}^{a}:\big{(}\!\tbinom{\mathbb{Z}/a\mathbb{Z}}{k}\!\big{)}\to\big{(}\!\tbinom{\mathbb{Z}/b\mathbb{Z}}{k}\!\big{)}.

Proposition 3.

The following diagram commutes:

Proof.

Going down, then right, then up the diagram is the composition

\begin{split}\mathscr{A}_{b}^{-1}\>\rho_{b}^{a}\>\mathscr{A}_{a}&=r\>\beta^{-1}\>c_{b}\>\rho_{b}^{a}\>\rho_{a}\>\beta\>u^{k}\\ &=\beta^{-1}R\>c_{b}\>\rho_{b}\>\beta\>u^{k}\\ &=\operatorname{core}_{b}.\\ \end{split}

(We have used Proposition 1 and Equation (5).) ∎

Lemma 4.

For $G\in\mathcal{M}_{\operatorname{fin}}(\mathbb{Z}/b\mathbb{Z})$ , we have

\#(\rho^{a}_{b})^{-1}(G)=\prod_{j\in\mathbb{Z}/b\mathbb{Z}}\big{(}\!\tbinom{\frac{a}{b}}{G(j)}\!\big{)}.

Proof.

This follows from Lemma 1. ∎

Given $\sigma\in\mathcal{C}_{b}$ , let

N_{\sigma}(k)=\#\{\lambda\in\mathcal{C}_{a}\mid\operatorname{core}_{b}\lambda=\sigma,\ell(\lambda)\leq k\}.

Theorem 5.

There is a quasipolynomial $Q_{\sigma}(k)$ of degree $a-b$ and period $b$ , so that for $k\geq\ell(\sigma)$ , we have $N_{\sigma}(k)=Q_{\sigma}(k)$ . The leading coefficient of $Q_{\sigma}(k)$ is $\dfrac{1}{(\frac{a}{b}-1)!^{b}}$ .

Proof.

Let $c=\frac{a}{b}$ . By Proposition 3 and Lemma 4, for $\ell(\sigma)\leq i<~{}\ell(\sigma)+~{}b$ we have

	$\displaystyle N_{\sigma}(i+nb)$	$\displaystyle=\prod\limits_{j=0}^{b-1}\big{(}\!\tbinom{c}{H_{\sigma,b}^{i+nb}(j)}\!\big{)}$
		$\displaystyle=\prod\limits_{j=0}^{b-1}\big{(}\!\tbinom{c}{H_{\sigma,b}^{i}(j)+n}\!\big{)}$
		$\displaystyle=\prod\limits_{j=0}^{b-1}\binom{n+H_{\sigma,b}^{i}(j)+c-1}{H_{\sigma,b}^{i}(j)+n}$
		$\displaystyle=\prod\limits_{j=0}^{b-1}\binom{n+H_{\sigma,b}^{i}(j)+c-1}{c-1}.$

Now each

\binom{n+H_{\sigma,b}^{i}(j)+c-1}{c-1}

is a polynomial function of $n$ of degree $c-1$ and leading term

\frac{n^{c-1}}{(c-1)!}.

Therefore $N_{\sigma}(i+nb)$ is a polynomial in $n$ of degree $a-b$ and leading coefficient $\dfrac{1}{(\frac{a}{b}-1)!^{b}}$ . Thus the restriction of $N_{\sigma}(k)$ to the coset $i+b\underline{\mathbb{N}}$ is a polynomial, and the theorem follows.

This shows that for $k\geq\ell(\sigma)$ , $N_{\sigma}(k)$ is a quasipolynomial of degree $a-b$ and leading coefficient $\dfrac{1}{(\frac{a}{b}-1)!^{b}}$ . ∎

Example 7.

Let $a=6,b=2$ , and $\sigma=(4,3,2,1)\in\mathcal{C}_{2}$ . Then $\ell(\sigma)=4$ and $c=\frac{a}{b}=3.$ We have

H_{\sigma}^{4}=\{7,5,3,1\}\text{ and }H_{\sigma}^{5}=\{8,6,4,2,0\}.

Hence, $H_{\sigma,2}^{4}(j)=\begin{cases}0\text{ for }j=0\\ 4\text{ for }j=1\end{cases}$ and $H_{\sigma,2}^{5}(j)=\begin{cases}5\text{ for }j=0\\ 0\text{ for }j=1.\end{cases}$
By Theorem 5, for $n\geq 0$ ,

	$\displaystyle N_{\sigma}(4+2n)$	$\displaystyle=\binom{n+2}{2}\binom{n+6}{2}$
		$\displaystyle=\frac{1}{4}(n^{4}+14n^{3}+65n^{2}+112n+60)$

and

	$\displaystyle N_{\sigma}(5+2n)$	$\displaystyle=\binom{n+7}{2}\binom{n+2}{2}$
		$\displaystyle=\frac{1}{4}(n^{4}+16n^{3}+83n^{2}+152n+84).$

5. Converting to a Multiset Matching Problem

In this section we recall the map $\operatorname{core}_{s,t}$ from the introduction, and interpret the fibre counting problem in terms of multisets. By the usual Chinese Remainder Theorem, we may view $\mathbb{Z}/m\mathbb{Z}$ as the fibre product of $\mathbb{Z}/s\mathbb{Z}$ and $\mathbb{Z}/t\mathbb{Z}$ over $\mathbb{Z}/d\mathbb{Z}$ . So we then investigate the effect of the functor $S\leadsto\big{(}\!\tbinom{S}{k}\!\big{)}$ on a fibre product. This study allows us to express $N_{\sigma,\tau}(k)$ in terms of classical combinatorial constants arising in margin problems for integral matrices. Moreover we give a factorization of $N_{\sigma,\tau}(k)$ , which allows a reduction to the case where $s,t$ are relatively prime.

5.1. The Map $\operatorname{core}_{s,t}$

Let $s,t\in\mathbb{N}$ , and put $d=\gcd(s,t)$ and $m=\operatorname{lcm}(s,t)$ . Consider the map

\operatorname{core}_{s,t}:\mathcal{C}_{m}\rightarrow\mathcal{C}_{s}\times\mathcal{C}_{t}

taking an $m$ -core $\lambda$ to $(\operatorname{core}_{s}\lambda,\operatorname{core}_{t}\lambda)$ . As in Proposition 3, we have a commutative diagram

(6)

where the maps out of $\mathcal{C}_{m}^{k}$ and $\mathcal{C}_{s}^{k}\times\mathcal{C}_{t}^{k}$ are the bijections of Proposition 2, and

\rho_{s,t}=\rho^{m}_{s}\times\rho^{m}_{t}.

Let $N_{\sigma,\tau}(k)$ be the cardinality of the fibre of $\operatorname{core}_{s,t}$ over $(\sigma,\tau)$ for $k\in\mathbb{N}$ . Thus

N_{\sigma,\tau}(k)=\#\{\lambda\in\mathcal{C}_{m}^{k}\mid\operatorname{core}_{s}\lambda=\sigma,\operatorname{core}_{t}\lambda=\tau\}.

By the commutativity of (6), counting fibres of $\operatorname{core}_{s,t}$ is equivalent to counting fibres of $\rho_{s,t}$ .

5.2. Matchings

For finite sets $S,T$ , consider the projection maps $\operatorname{pr}_{S}:S\times T\to S$ and $\operatorname{pr}_{T}:S\times T\to T$ . There are corresponding multiset maps

(\operatorname{pr}_{S})_{*}:\big{(}\!\tbinom{S\times T}{k}\!\big{)}\to\big{(}\!\tbinom{S}{k}\!\big{)},\hskip 5.69046pt\hskip 5.69046pt(\operatorname{pr}_{T})_{*}:\big{(}\!\tbinom{S\times T}{k}\!\big{)}\to\big{(}\!\tbinom{T}{k}\!\big{)}.

and

\operatorname{pr}:\big{(}\!\tbinom{S\times T}{k}\!\big{)}\to\big{(}\!\tbinom{S}{k}\!\big{)}\times\big{(}\!\tbinom{T}{k}\!\big{)}

given by $\operatorname{pr}=(\operatorname{pr}_{S})_{*}\times(\operatorname{pr}_{T})_{*}.$

Definition 7.

Let $F\in\big{(}\!\tbinom{S}{k}\!\big{)}$ and $G\in\big{(}\!\tbinom{T}{k}\!\big{)}$ . We say that $\Phi\in\big{(}\!\tbinom{S\times T}{k}\!\big{)}$ is a matching from $F$ to $G$ , provided $\operatorname{pr}(\Phi)=(F,G)$ .

Say $|S|=m$ and $|T|=n$ , with $S=\{x_{1},\ldots,x_{m}\}$ and $T=\{y_{1},\ldots,y_{n}\}$ , Given $F,G$ as above, define vectors

\vec{F}=(F(x_{1}),\ldots,F(x_{m}))

and

\vec{G}=(G(y_{1}),\ldots,G(y_{n})).

So $k$ is the sum of the components of $\vec{F}$ , and also the sum of the components of $\vec{G}$ .

One says that an $m\times n$ matrix $A$ has row margins $\vec{F}$ , if $F(x_{i})$ is the sum of the entries of the $i$ th row for each $i$ . Similarly $A$ has column margins $\vec{G}$ , if $G(y_{i})$ is the sum of the entries of the $j$ th column for each $j$ .

Proposition 4.

Given $F\in\big{(}\!\tbinom{S}{k}\!\big{)}$ and $G\in\big{(}\!\tbinom{T}{k}\!\big{)}$ , there is a bijection between the set of matchings from $F$ to $G$ and the set of non-negative integral matrices with row margins $\vec{F}$ and column margins $\vec{G}$ .

Proof.

Suppose that $(m_{ij})$ is such a matrix. Then

\Phi(x_{i},y_{j})=m_{ij}

is a matching from $F$ to $G$ , and this gives the required bijection. ∎

Write $M_{F,G}$ for the number of matrices with nonnegative integer entries having row margins $\vec{F}$ and column margins $\vec{G}$ . According to [brualdi2006combinatorial, Corollary 8.1.4], if the sum of the components of $\vec{F}$ equals the sum of the components of $\vec{G}$ , then $M_{F,G}\geq 1$ .

A Chinese Remainder Theorem for Partitions

Abstract.

Key words and phrases:

1. Introduction

Theorem 1.

Remark 1.

Theorem 2.

Theorem 3.

Theorem 4.

Acknowledgments

2. Preliminaries

2.1. Multisets

Lemma 1.

Proof.

2.2. Partitions and Pseudopartitions

2.3. Young Diagrams

Example 1.

Remark 2.

2.4. Beta sets

Definition 1.

Example 2.

Definition 2.

3. Cores

Definition 3.

3.1. Hook Removal

Example 3.

Example 4.

Lemma 2.

Proof.

Example 5.

3.2. β\beta-set Version

Definition 4.

Remark 3.

Definition 5.

Proposition 1.

Proof.

Example 6.

Proposition 2.

Proof.

Lemma 3.

4. Reducing a tt-core modulo a divisor of tt

Definition 6.

Proposition 3.

Proof.

Lemma 4.

Proof.

Theorem 5.

Proof.

Example 7.

5. Converting to a Multiset Matching Problem

5.1. The Map cores,t\operatorname{core}_{s,t}

5.2. Matchings

Definition 7.

Proposition 4.

Proof.

3.2. $\beta$ -set Version

4. Reducing a $t$ -core modulo a divisor of $t$

5.1. The Map $\operatorname{core}_{s,t}$