[Use arrow keys to navigate.]

$ \newcommand{mset}[2]{\left\{ #1 \;\middle|\; #2 \right\}} \newcommand{PPP}{\mathcal{P}} \newcommand{CCC}{\mathcal{C}} \newcommand{FFF}{\mathcal{F}} \newcommand{RR}{\mathbb{R}} \newcommand{ZZ}{\mathbb{Z}} \newcommand{NN}{\mathbb{N}} \newcommand{comp}{\operatorname{com}} \newcommand{mvec}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{mmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{mmod}{\; \operatorname{mod} \;} \newcommand{lcm}{\operatorname{lcm}} \newcommand{ehr}{\operatorname{ehr}} $

Combinatorial Witnesses for Congruences of Restricted Partition Functions via Ehrhart Theory

Felix Breuer
RISC, JKU, Linz
FWF SFB Algorithmic and Enumerative Combinatorics

joint work with
Dennis Eichhorn (UC Irvine) and Brandt Kronholm (RISC)

Restricted Partitions

Partition of 18 with 3 parts: $ 18 = 9 + 5 + 4 $

\begin{eqnarray*} p(n,d) &=\;\; \#&&\text{partitions of $n$} \\ &&&\text{into exactly $d$ parts} \end{eqnarray*}

Congruences

\begin{eqnarray*} p(s\cdot k + r,d) &\equiv& 0 \mmod m \text{ for all $k\in\ZZ_{\geq 0}$} \end{eqnarray*}

\begin{eqnarray*} p(6k,3) &\equiv& 0 \mmod 3 \text{ for all $k\in\ZZ_{\geq 0}$} \end{eqnarray*}

Witnesses?

Geometry

partitions $\leftrightarrow$ integer points

$$9 + 5 + 4 \leftrightarrow (9,5,4) $$

$p(18,3)$

$p(18,3)$

$p(24,3)$

$p(30,3)$

Restricted Partition Polytope

\begin{align*} p(n,d) = \#\ZZ^d \cap n\cdot\PPP_d =: \ehr_{\PPP_d}(n) \end{align*}

\begin{align*} \color{white}{n\cdot}\PPP_d = \left\{ x\in\RR^d \; \middle| \right. \; & \sum x_i = 1, \\ & \left. x_1\geq x_2 \geq \ldots \geq x_d > 0 \right\} \end{align*}

\begin{align*} n\cdot\PPP_d = \left\{ x\in\RR^d \; \middle| \right. \; & \sum x_i = n, \\ & \left. x_1\geq x_2 \geq \ldots \geq x_d > 0 \right\} \end{align*}

\begin{align*} \PPP_3 = \left\{ x\in\RR^3_{\geq 0} \middle| \right. \; & x_1+x_2+x_3 = 1, \end{align*}

\begin{align*} \PPP_3 = \left\{ x\in\RR^3_{\geq 0} \middle| \right. \; & x_1+x_2+x_3 = 1, \\ & \left. \color{red}{x_1\geq x_2}, \color{green}{x_2\geq x_3}, \color{blue}{x_3 > 0} \right\} \end{align*}

Example

Partition Cone

\begin{align*} \CCC_d &= \mset{x\in\RR^d}{x_1 \geq \ldots \geq x_d > 0} \\ \end{align*}

\begin{align*} n\PPP_d &= \mset{x\in\RR^d}{\sum x_i = n} \cap \CCC_d \end{align*}

\begin{align*} \CCC_d &= V \left( \RR_{\geq 0}^{d-1} \times \RR_{> 0} \right) \end{align*}

$V = \mmat{ \color{red}{\lcm(d)} & \color{green}{\frac{\lcm(d)}{2}} & \ldots & \color{blue}{\frac{\lcm(d)}{d}} \\ \color{red}{0} & \color{green}{\frac{\lcm(d)}{2}} & \ldots & \color{blue}{\frac{\lcm(d)}{d}} \\ \color{red}{0} & \color{green}{0} & & \color{blue}{\frac{\lcm(d)}{d}} \\ \color{red}{\vdots} & \color{green}{\vdots} & & \color{blue}{\vdots} \\ \color{red}{0} & \color{green}{0} & & \color{blue}{\frac{\lcm(d)}{d}} }$

$\lcm(d) := \lcm(1,2,\ldots,d)$

For $d=3$: $\lcm(3)=6$ and $V = \mmat{ \color{red}{6} & \color{green}{3} & \color{blue}{2} \\ \color{red}{0} & \color{green}{3} & \color{blue}{2} \\ \color{red}{0} & \color{green}{0} & \color{blue}{2} }$

Partition Cone

\begin{align*} \CCC_d &= V \left( \RR_{\geq 0}^{d-1} \times \RR_{> 0} \right) \end{align*}

Fundamental Parallelepiped

\begin{align*} \FFF_d &= V\left( [0,1)^{d-1}\times (0,1]\right) \end{align*}

\begin{align*} \CCC_d &= V\left(\RR_{\geq 0}^{d-1} \times \RR_{> 0} \right) \\ \FFF_d &= V\left( [0,1)^{d-1}\times (0,1]\right) \end{align*}

Ehrhart's Observation

\begin{align*} \CCC_d &= V\ZZ_{\geq 0}^3 + \FFF_d \end{align*}

\begin{align*} \CCC_d &= V\left(\RR_{\geq 0}^{d-1} \times \RR_{> 0} \right) \\ \FFF_d &= V\left( [0,1)^{d-1}\times (0,1]\right) \end{align*}

\begin{align*} \CCC_d &= V\ZZ_{\geq 0}^3 + \FFF_d \end{align*}

$$ H_n = \mset{x\in\RR^3}{\sum x_i = n} $$ $$ 21\PPP_3 = H_{21} \cap \CCC_3 $$

$$ \frac{ \sum_{v\in \FFF_3} x^v } { (1-x^{(6,0,0)})(1-x^{(3,3,0)})(1-x^{(2,2,2)}) } \;\; \longleftrightarrow \;\; \frac{\cdots}{(1-q^6)^3} $$

\begin{align*} &\sum_{n\geq 0} p(n,3) q^n = \frac{q^3}{(1-q)(1-q^2)(1-q^3)} = \frac{q^3(1+q+q^2+q^3+q^4+q^5)(1+q^2+q^4)(1+q^3)}{(1-q^6)^3} \\ = &\frac{0q^0 + 0q^1 + 0q^2 + 1 q^3 + 1q^4 + 2q^5 + 3q^6 + 4 q^7 + 5q^8 + 4 q^9 + 5q^{10} + 4q^{11} + 3q^{12} + 2q^{13} + 1q^{14} + 1q^{15} + 0q^{16} + 0q^{17} }{(1-q^6)^3} \end{align*}

\begin{align*} p(6k+0,3) =& 0\binom{k+2}{2} + 3\binom{k+1}{2} + 3\binom{k}{2} \\ p(6k+1,3) =& 0\binom{k+2}{2} + 4\binom{k+1}{2} + 2\binom{k}{2} \\ p(6k+2,3) =& 0\binom{k+2}{2} + 5\binom{k+1}{2} + 1\binom{k}{2} \\ p(6k+3,3) =& 1\binom{k+2}{2} + 4\binom{k+1}{2} + 1\binom{k}{2} \\ p(6k+4,3) =& 1\binom{k+2}{2} + 5\binom{k+1}{2} + 0\binom{k}{2} \\ p(6k+5,3) =& 2\binom{k+2}{2} + 4\binom{k+1}{2} + 0\binom{k}{2} \end{align*}

Theorem. [B-Eichhorn-Kronholm]

There are explicit cycles witnessing the congruences $$ p(\ell\lcm(\ell)k+r,\ell) \equiv 0 \mod \ell $$ for all $\ell\in\NN$ prime, $-\binom{\ell}{2} < r < \ell$ and $1\leq k \in \ZZ$.

Example: $r=1$, $\ell=3$. Here $3 \lcm(3) = 18$. $$ p(18\cdot k + 1,3) \equiv 0 \mmod 3 $$ In particular $ p(19,3) \equiv 0 \mmod 3 $.

Theorem. [B-Eichhorn-Kronholm]

There are explicit cycles witnessing the congruences $$ p(\pi_{d,\ell}k+r,d) \equiv 0 \mod \ell $$ for all $\ell\in\NN$ prime, $d\in\NN$, $-\binom{d}{2} < r < d$ and $1\leq k \in \ZZ$.

Example: $d=3$, $r=1$, $\ell=5$. Here $\pi_{d,\ell} = 5\lcm(3) = 30$. $$ p(30\cdot k + 1,3) \equiv 0 \mmod 5 $$ In particular $ p(31,3) \equiv 0 \mmod 5 $.

Theorem. [B-Eichhorn-Kronholm]

There are explicit cycles witnessing the congruences $$ p(\lcm(\ell)k - t\ell,\ell) \equiv 0 \mod \ell $$ for all $\ell\in\NN$ an odd prime, $0 \leq t \leq \frac{\ell-3}{2}$ and $1\leq k \in \ZZ$.

Example: $p(6k,3) \equiv 0 \mod 3$

Example: $p(115,5) \equiv 0 \mod 5$. $\lcm(4) = 12$, $\lcm(5)=60$.

A crank for a given artihmetic progression of divisibilities modulo $m$ is a function $c_n:P(n,d) \rightarrow \{ 0,\ldots,m-1 \}$ such that $$ |c^{-1}(0)| = \ldots = |c^{-1}(m-1)| $$ for all $n$ in the arithmetic progression.

A supercrank is a crank that witnesses divisibility for any $n$ such that $m|p(n,d)$.

Theorem. [B-Eichhorn-Kronholm]

If $m$ is a prime of the form $6j-1$, then \[ p(n,3) \equiv 0 \mod m \] if and only if $n = \pm 0,1,2,2m-2,2m+1 \mod 6m$. Moreover, $$ c(\lambda) = (\lambda_1 - \lambda_3) \mod m$$ is a supercrank witnessing all of these divisibilities.

Summary

Congruences from Coefficients

How many constituents of $p(\operatorname{lcm}(d)k+r,d)$ have coefficients with non-trivial greatest common divisor?

#parts #constituents #non-trival gcds % non-trivial gcds examples (gcd, frequency)
3 6 3 50% [(3, 1), (2, 2)]
4 12 6 50% [(6, 2), (3, 4)]
5 60 4 7% [(5, 4)]
6 60 22 37% [(10, 4), (5, 6), (2, 12)]
7 420 203 48% [(196, 1), (14, 4), (7, 8), (4, 12), (2, 178)]
8 840 118 14% [(14, 3), (7, 3), (343, 4), (49, 6), (2, 102)]
9 2520 460 18% [(10, 20), (5, 100), (2, 340)]
10 2520 118 5% [(5, 118)]
11 27720 7277 26% [(1815, 3), (33, 6), (605, 6), (22, 28), (30, 128), (10, 156), (11, 188), (15, 228), (6, 360), (5, 826), (3, 2510), (2, 2838)]
12 27720 6468 23% [(66, 4), (165, 4), (110, 20), (30, 20), (121, 40), (33, 68), (22, 74), (10, 108), (6, 112), (15, 150), (55, 152), (11, 822), (2, 1432), (3, 1690), (5, 1772)]

The Period of $p(n,d) \mmod \ell$

$$\pi_{d,\ell^a} = \ell^{r_\ell(d)+a-1}L_d$$ $$L = \text{the $\ell$-free part of $\lcm(d)$}$$ $$ r_\ell(d) = \text{the least integer such that $\ell^{r_\ell(d)} \geq \sum_{i=1}^d \ell^{\nu_\ell(i)}$}$$ $$ \nu_\ell(m) = \text{the largest integer such that $\ell^{\nu_\ell(m)} | m$} $$

Example: $\pi_{\ell,\ell}$ $$L = \lcm(\ell-1)$$ $$ \sum = \underbrace{1+1+\ldots+1}{\ell-1} + \ell = 2\ell -1 \leq \ell^2$$ $$\pi_{\ell,\ell} = \ell^2 \lcm(\ell-1) = \ell\lcm(\ell)$$

Example: $\pi_{14,3}$ $$\lcm(14) = 1 \cdot 2 \cdot 3 \cdot 2 \cdot 5 \cdot 1 \cdot 7 \cdot 2 \cdot 3 \cdot 1 \cdot 11 \cdot 1 \cdot 13 \cdot 1$$ $$L = 1 \cdot 2 \cdot 1 \cdot 2 \cdot 5 \cdot 1 \cdot 7 \cdot 2 \cdot 1 \cdot 1 \cdot 11 \cdot 1 \cdot 13 \cdot 1$$ $$ \sum = 1+1+3+1+1+3+1+1+9+1+1+3+1+1 = 28 \leq 3^4$$ $$\pi_{14,3} = 3^4 L = 3^2 \lcm(14) $$