### Ramanujan's Partition Congruences

Based on the empirical analysis of a table of partitions Ramanujan conjectured his famous partition congruences $$\boxed{\begin{align}p(5n + 4)&\equiv 0\pmod{5}\notag\\ p(7n + 5)&\equiv 0\pmod{7}\notag\\ p(11n + 6)&\equiv 0\pmod{11}\notag\end{align}}\tag{1}$$ and gave some of the most beautiful proofs for them (see here). In addition to these proofs he gave the following generating functions for $p(5n + 4), p(7n + 5)$: $$\sum_{n = 0}^{\infty}p(5n + 4)q^{n} = 5\frac{\{(1 - q^{5})(1 - q^{10})(1 - q^{15})\cdots\}^{5}}{\{(1 - q)(1 - q^{2})(1 - q^{3})\cdots\}^{6}}\tag{2}$$ and \begin{align}\sum_{n = 0}^{\infty}p(7n + 5)q^{n}&= 7\frac{\{(1 - q^{7})(1 - q^{14})(1 - q^{21})\cdots\}^{3}}{\{(1 - q)(1 - q^{2})(1 - q^{3})\cdots\}^{4}}\notag\\ &\,\,\,\,\,\,\,\,+ 49q\frac{\{(1 - q^{7})(1 - q^{14})(1 - q^{21})\cdots\}^{7}}{\{(1 - q)(1 - q^{2})(1 - q^{3})\cdots\}^{8}}\tag{3}\end{align} We have already established $(2)$ in one of our posts and this post deals with the identity $(3)$ concerning generating function of partitions modulo $7$.The identity $(3)$ is exceedingly difficult to prove using elementary techniques and most of the proofs involve heavy symbolic manipulation which is normally done using a software like MAPLE or MACSYMA. I tried to obtain some help from MSE to get a proof which used something possible via hand calculation but did not get any good answers there. I chanced to read an old paper titled "

*Some Identities involving the Partition Function*" by Oddmund Kolberg which provided very nice and elementary proofs of the identities $(2)$ and $(3)$ in a systematic fashion. This post tries to elaborate on the concise proof available in that paper.

### The Basic Technique

The main idea of the proof is to start with the following well known identities of Euler and Jacobi: $$f(-q) = (1 - q)(1 - q^{2})(1 - q^{3})\cdots = \sum_{n = -\infty}^{\infty}(-1)^{n}q^{n(3n + 1)/2}\tag{4}$$ and $$f^{3}(-q) = \{(1 - q)(1 - q^{2})(1 - q^{3})\cdots\}^{3} = \sum_{n = 0}^{\infty}(-1)^{n}(2n + 1)q^{n(n + 1)/2}\tag{5}$$ and split each of the series above based on the powers of $q$ modulo some prime number. Here we focus on the specific case where the prime number concerned is $7$. Thus we can write \begin{align}f(-q)&= \sum_{n = -\infty}^{\infty}(-1)^{n}q^{n(3n + 1)/2}\notag\\ &= g_{0} + g_{1} + g_{2} + g_{3} + g_{4} + g_{5} + g_{6}\notag\\ &= \sum_{s = 0}^{6}g_{s}\notag\\ &= \sum_{s = 0}^{6}\left(\sum_{n(3n + 1)/2\,\equiv\, s\pmod{7}}(-1)^{n}q^{n(3n + 1)/2}\right)\tag{6}\end{align} and \begin{align}f^{3}(-q)&= \sum_{n = 0}^{\infty}(-1)^{n}q^{n(n + 1)/2}\notag\\ &= h_{0} + h_{1} + h_{2} + h_{3} + h_{4} + h_{5} + h_{6}\notag\\ &= \sum_{s = 0}^{6}h_{s}\notag\\ &= \sum_{s = 0}^{6}\left(\sum_{n \geq 0,\,n(n + 1)/2\,\equiv\,s\pmod{7}}(-1)^{n}(2n + 1)q^{n(n + 1)/2}\right)\tag{7}\end{align} Clearly the expression $n(3n + 1)/2$ falls into one of the four class classes $0, 1, 2, 5$ modulo $7$ so that $$g_{3} = g_{4} = g_{6} = 0$$ Similarly we have $$h_{2} = h_{4} = h_{5} = 0$$ On the other hand we can evaluate $g_{2}$ by noting that \begin{align}n(3n + 1)/2 &\equiv 2\pmod{7}\notag\\ \Leftrightarrow 24\{n(3n + 1)/2\} + 1&\equiv 49 \equiv 0\pmod{7}\notag\\ \Leftrightarrow (6n + 1)^{2}&\equiv 0\pmod{7}\notag\\ \Leftrightarrow 6n + 1&\equiv 0\pmod{7}\notag\\ \Leftrightarrow n&\equiv 1\pmod{7}\notag\end{align} We thus have \begin{align}g_{2}&= \sum_{n = -\infty}^{\infty}(-1)^{7n + 1}q^{(7n + 1)(21n + 4)/2}\notag\\ &= -\sum_{n = -\infty}^{\infty}(-1)^{7n}q^{2}q^{49n(3n + 1)/2}\notag\\ &= -q^{2}f(-q^{49})\notag\end{align} In a similar fashion we can calculate $h_{6} = -7q^{6}f^{3}(-q^{49})$ so that $h_{6} = 7g_{2}^{3}$.We thus have the following values of $g_{s}, h_{s}$: \begin{align}g_{2} = -q^{2}f(-q^{49}),\, g_{3} = g_{4} = g_{6} &= 0\notag\\ h_{6} = -7q^{6}f^{3}(-q^{49}) = 7g_{2}^{3},\,h_{2} = h_{4} = h_{5} &= 0\tag{8}\end{align} Using the relation $\sum h_{s} = (\sum g_{s})^{3}$ we get $\sum h_{s} = (g_{0} + g_{1} + g_{2} + g_{5})^{3}$ and on equating the terms based on their modulo classes on each side (after cubing RHS) we get $$\boxed{\begin{align}3(g_{0}^{2}g_{2} + g_{1}^{2}g_{0} + g_{2}^{2}g_{5})&= h_{2} = 0\notag\\ 3(g_{1}^{2}g_{2} + g_{2}^{2}g_{0} + g_{5}^{2}g_{1})&= h_{4} = 0\notag\\ 3(g_{0}^{2}g_{5} + g_{2}^{2}g_{1} + g_{5}^{2}g_{2})&= h_{5} = 0\notag\\ g_{2}^{3} + 6g_{0}g_{1}g_{5}&= h_{6} = 7g_{2}^{3}\notag\end{align}}\tag{9}$$ Putting $\alpha = g_{0}/g_{2}, \beta = g_{1}/g_{2}, \gamma = g_{5}/g_{2}$ we can rewrite the above equations as $$\boxed{\begin{align}\alpha \beta^{2} + \alpha^{2} + \gamma &= 0\notag\\ \beta \gamma^{2} + \beta^{2} + \alpha &= 0\notag\\ \gamma \alpha^{2} + \gamma^{2} + \beta &= 0\notag\\ \alpha\beta\gamma &= 1\notag\end{align}}\tag{10}$$ We now relate these quantities with the partition function $p(n)$.

### Relation with Partition Function $p(7n + 5)$

We have the generating function of the partition function $p(n)$ given by the formula $$\sum_{n = 0}^{\infty}p(n)q^{n} = \frac{1}{f(-q)}\tag{11}$$ We split the series on the left based on powers of $q$ modulo $7$ so that $\sum p(n)q^{n} = \sum_{s = 0}^{6}P_{s}$ with $P_{s}$ defined by $$P_{s} = \sum_{n = 0}^{\infty}p(7n + s)q^{7n + s}$$ We thus have the following equations \begin{align}P_{0} + P_{1} + P_{2} + P_{3} + P_{4} + P_{5} + P_{6} &= \frac{1}{f(-q)}\notag\\ g_{0} + g_{1} + g_{2} + g_{3} + g_{4} + g_{5} + g_{6} &= f(-q)\notag\end{align} Multiplying the above equations and arranging terms based on their modulo classes we get \begin{align}g_{0}P_{0} + g_{6}P_{1} + g_{5}P_{2} + g_{4}P_{3} + g_{3}P_{4} + g_{2}P_{5} + g_{1}P_{6}&= 1\notag\\ g_{1}P_{0} + g_{0}P_{1} + g_{6}P_{2} + g_{5}P_{3} + g_{4}P_{4} + g_{3}P_{5} + g_{2}P_{6}&= 0\notag\\ g_{2}P_{0} + g_{1}P_{1} + g_{0}P_{2} + g_{6}P_{3} + g_{5}P_{4} + g_{4}P_{5} + g_{3}P_{6}&= 0\notag\\ g_{3}P_{0} + g_{2}P_{1} + g_{1}P_{2} + g_{0}P_{3} + g_{6}P_{4} + g_{5}P_{5} + g_{4}P_{6}&= 0\notag\\ g_{4}P_{0} + g_{3}P_{1} + g_{2}P_{2} + g_{1}P_{3} + g_{0}P_{4} + g_{6}P_{5} + g_{5}P_{6}&= 0\notag\\ g_{5}P_{0} + g_{4}P_{1} + g_{3}P_{2} + g_{2}P_{3} + g_{1}P_{4} + g_{0}P_{5} + g_{6}P_{6}&= 0\notag\\ g_{6}P_{0} + g_{5}P_{1} + g_{4}P_{2} + g_{3}P_{3} + g_{2}P_{4} + g_{1}P_{5} + g_{0}P_{6}&= 0\notag\end{align} Using Cramer's rule we can calculate the desired sum $P_{5}$ corresponding to $p(7n + 5)$ as $P_{5} = D_{5}/D$ where $D$ and $D_{5}$ are the following determinants $$D = \begin{vmatrix}g_{0} & g_{6} & g_{5} & g_{4} & g_{3} & g_{2} & g_{1}\\g_{1} & g_{0} & g_{6} & g_{5} & g_{4} & g_{3} & g_{2}\\

g_{2} & g_{1} & g_{0} & g_{6} & g_{5} & g_{4} & g_{3}\\

g_{3} & g_{2} & g_{1} & g_{0} & g_{6} & g_{5} & g_{4}\\

g_{4} & g_{3} & g_{2} & g_{1} & g_{0} & g_{6} & g_{5}\\

g_{5} & g_{4} & g_{3} & g_{2} & g_{1} & g_{0} & g_{6}\\

g_{6} & g_{5} & g_{4} & g_{3} & g_{2} & g_{1} & g_{0}\end{vmatrix}\tag{12}$$ $$D_{5} = -\begin{vmatrix}g_{1} & g_{0} & g_{6} & g_{5} & g_{4} & g_{2}\\

g_{2} & g_{1} & g_{0} & g_{6} & g_{5} & g_{3}\\

g_{3} & g_{2} & g_{1} & g_{0} & g_{6} & g_{4}\\

g_{4} & g_{3} & g_{2} & g_{1} & g_{0} & g_{5}\\

g_{5} & g_{4} & g_{3} & g_{2} & g_{1} & g_{6}\\

g_{6} & g_{5} & g_{4} & g_{3} & g_{2} & g_{0}\end{vmatrix}\tag{13}$$ Calculating these determinants above is bit of a challenge but is made possible by the vanishing of some of $g's$ and the relations $(9)$.

### Evaluation of determinants $D, D_{5}$

If we take a closer look at $D$ we can see that it is the determinant of a*circulant matrix*$A$ and therefore we can easily find the eigenvalues of this matrix and thereby calculate the determinant $D$ as a product of eigenvalues. If $\omega$ is a $7^{\text{th}}$ root of unity (including $\omega = 1$ also) then we can see that the expression $$g_{0} + \omega g_{1} + \omega^{2}g_{2} + \omega^{3}g_{3}+ \omega^{4}g_{4}+ \omega^{5}g_{5}+ \omega^{6}g_{6}$$ is an eigenvalue of $A$ and the vector $$(1, \omega, \omega^{2}, \omega^{3}, \omega^{4}, \omega^{5}, \omega^{6})$$ is the corresponding eigenvector. If $\omega$ is a primitive $7^{\text{th}}$ root of unity then all the $7^{\text{th}}$ roots of unity are given by powers of $\omega$ and thus for each of $t = 0, 1, 2, 3, 4, 5, 6$ we obtain the eigenvalue $$\lambda_{t} = g_{0} + \omega^{t} g_{1} + \omega^{2t}g_{2} + \omega^{3t}g_{3}+ \omega^{4t}g_{4}+ \omega^{5t}g_{5}+ \omega^{6t}g_{6}$$ and therefore we have the determinant $D$ given by $$D = \prod_{t = 0}^{6}(g_{0} + \omega^{t} g_{1} + \omega^{2t}g_{2} + \omega^{3t}g_{3}+ \omega^{4t}g_{4}+ \omega^{5t}g_{5}+ \omega^{6t}g_{6}) = \prod_{t = 0}^{6}\sum_{s = 0}^{6}\omega^{st}g_{s}$$ Using the definition of $g_{s} = g_{s}(q)$ we can easily see that $\omega^{st}g_{s}(q) = g_{s}(\omega^{t}q)$ and hence we have \begin{align}D&= \prod_{t = 0}^{6}\sum_{s = 0}^{6}\omega^{st}g_{s} = \prod_{t = 0}^{6}\sum_{s = 0}^{6}g_{s}(\omega^{t}q) = \prod_{t = 0}^{6}f(-\omega^{t}q)\notag\\ &= \prod_{t = 0}^{6}\prod_{n = 1}^{\infty}(1 - \omega^{nt}q^{n}) = \prod_{n = 1}^{\infty}\prod_{t = 0}^{6}(1 - \omega^{tn}q^{n})\notag\\ &= \prod_{n \not\equiv 0\pmod{7}}(1 - q^{7n})\prod_{n \equiv 0\pmod{7}}(1 - q^{n})^{7} = \frac{f^{8}(-q^{7})}{f(-q^{49})}\tag{14}\end{align} Before calculating $D_{5}$ we need to perform a direct calculation of the determinant $D$ using the usual definition of a determinant. To simplify the calculation we use the fact that $$g_{0} = \alpha g_{2}, g_{1} = \beta g_{2}, g_{5} = \gamma g_{2}, g_{3} = g_{4} = g_{6} = 0$$ and then we have $$D = g_{2}^{7}\begin{vmatrix}\alpha & 0 & \gamma & 0 & 0 & 1 & \beta\\

\beta & \alpha & 0 & \gamma & 0 & 0 & 1\\

1 & \beta & \alpha & 0 & \gamma & 0 & 0\\

0 & 1 & \beta & \alpha & 0 & \gamma & 0\\

0 & 0 & 1 & \beta & \alpha & 0 & \gamma\\

\gamma & 0 & 0 & 1 & \beta & \alpha & 0\\

0 & \gamma & 0 & 0 & 1 & \beta & \alpha\end{vmatrix} = g_{2}^{7}D'$$ Thanks to the presence of the zeroes in $D'$ and the fact that $\alpha\beta\gamma = 1$ the determinant $D'$ can be calculated by hand with not so unreasonable effort and we get \begin{align}D'&= (\alpha^{7} + \beta^{7} + \gamma^{7}) - 7(\alpha\beta^{5} + \beta\gamma^{5} + \gamma\alpha^{5})\notag\\ &\,\,\,\,\,\,\,\,+ 14(\alpha^{2}\beta^{3} + \beta^{2}\gamma^{3} + \gamma^{2}\alpha^{3}) + 8\tag{15}\end{align} In the same manner we can calculate $D_{5} = -g_{2}^{6}D'_{5}$ where $$D'_{5} = \begin{vmatrix}\beta & \alpha & 0 & \gamma & 0 & 1\\

1 & \beta & \alpha & 0 & \gamma & 0\\

0 & 1 & \beta & \alpha & 0 & 0\\

0 & 0 & 1 & \beta & \alpha & \gamma\\

\gamma & 0 & 0 & 1 & \beta & 0\\

0 & \gamma & 0 & 0 & 1 & \alpha\end{vmatrix}$$ and \begin{align}D'_{5}&= (\alpha\beta^{5} + \beta\gamma^{5} + \gamma\alpha^{5}) - 4(\alpha^{2}\beta^{3} + \beta^{2}\gamma^{3} + \gamma^{2}\alpha^{3})\notag\\ &\,\,\,\,\,\,\,\,+ 3(\alpha^{3}\beta + \beta^{3}\gamma + \gamma^{3}\alpha) - 8\tag{16}\end{align} Since we know the value of $D'$ in a closed form as $$D' = \frac{D}{g_{2}^{7}} = -\frac{f^{8}(-q^{7})}{q^{14}f^{8}(-q^{49})}\tag{17}$$ the real issue is to evaluate $D'_{5}$ in a closed form. For this we try to find relation between $D'$ and $D'_{5}$. We use a new set of variables $y_{1}, y_{2}, y_{3}$ defined by $$y_{1} = \alpha^{3}\beta, y_{2} = \beta^{3}\gamma, y_{3} = \gamma^{3}\alpha\tag{18}$$ and then apply equation $(10)$ to evaluate the following expressions \begin{align}\alpha^{2}\beta^{3}&= y_{1}y_{2} = - y_{1} - 1\tag{19a}\\ \beta^{2}\gamma^{3} &= y_{2}y_{3} = - y_{2} - 1\tag{19b}\\ \gamma^{2}\alpha^{3} &= y_{3}y_{1} = - y_{3} - 1\tag{19c}\end{align} $$y_{1}y_{2}y_{3} = 1\tag{20}$$ $$\alpha\beta^{5} = y_{1} - y_{2} + 1, \beta\gamma^{5} = y_{2} - y_{3} + 1, \gamma\alpha^{5} = y_{3} - y_{1} + 1\tag{21}$$ \begin{align}\alpha^{7}&= - y_{1}^{2} + y_{1} - y_{3} - 1\tag{22a}\\ \beta^{7}&= - y_{2}^{2} + y_{2} - y_{1} - 1\tag{22b}\\ \gamma^{7}&= - y_{3}^{2} + y_{3} - y_{2} - 1\tag{22c}\end{align} Using equation $(15)$ and the above relations between $y_{i}$ we get \begin{align}D'&= -(y_{1}^{2} + y_{2}^{2} + y_{3}^{2}) - 14(y_{1} + y_{2} + y_{3}) - 58\notag\\ &= -(y_{1} + y_{2} + y_{3})^{2} - 16(y_{1} + y_{2} + y_{3}) - 64\notag\\ &= -(y_{1} + y_{2} + y_{3} + 8)^{2}\notag\end{align} Using equation $(17)$ we get $$y_{1} + y_{2} + y_{3} + 8 = \pm\frac{f^{4}(-q^{7})}{q^{7}f^{4}(-q^{49})}$$ and clearly we can see that the expression $y_{1}$ begins with $-q^{-7}$ so that we need to take the negative sign on RHS in above equation. We finally have $$y_{1} + y_{2} + y_{3} = -\frac{f^{4}(-q^{7})}{q^{7}f^{4}(-q^{49})} - 8\tag{23}$$ In the same manner we can see that $$D'_{5} = 7(y_{1} + y_{2} + y_{3}) + 7 = -7\frac{f^{4}(-q^{7})}{q^{7}f^{4}(-q^{49})} - 49$$ We now have \begin{align}\sum_{n = 0}^{\infty}p(7n + 5)q^{7n + 5}&= P_{5} = \frac{D_{5}}{D} = \frac{-g_{2}^{6}D'_{5}}{g_{2}^{7}D'} = -\frac{D'_{5}}{g_{2}D'}\notag\\ &= \frac{1}{q^{2}f(-q^{49})}\cdot\frac{q^{14}f^{8}(-q^{49})}{f^{8}(-q^{7})}\left(7\frac{f^{4}(-q^{7})}{q^{7}f^{4}(-q^{49})} + 49\right)\notag\\ &= q^{5}\left(7\frac{f^{3}(-q^{49})}{f^{4}(-q^{7})} + 49q^{7}\frac{f^{7}(-q^{49})}{f^{8}(-q^{7})}\right)\notag\end{align} Cancelling $q^{5}$ from both sides and replacing $q^{7}$ by $q$ we get the Ramanujan's identity $$\sum_{n = 0}^{\infty}p(7n + 5)q^{n} = 7\frac{f^{3}(-q^{7})}{f^{4}(-q)} + 49q\frac{f^{7}(-q^{7})}{f^{8}(-q)}$$ The above proof is totally elementary and it is probable that Ramanujan did something similar to obtain his formula. The same technique of splitting series for $f(-q)$ and $1/f(-q)$ into multiple parts based on the modulo classes of the powers of $q$ can be used to prove the identity $(2)$ for partitions modulo $5$. In the above technique the only hard part is the calculation of determinants by brute force which is somewhat laborious. For a person like Ramanujan with unmatched powers of symbolic manipulation this would have been a child's play.

### Partition Congruence $p(49n + 47) \equiv 0\pmod{49}$

Ramanujan's motivation for the identity $(3)$ was to prove the partition congruence $$p(49n + 47) \equiv 0\pmod{49}\tag{24}$$ and he gave a very short proof of this congruence in the following manner. Using binomial theorem it is easy to check that $$(1 - q)^{7} = 1 - q^{7} + 7J$$ where $J$ is a power series in $q$ with integral coefficients and hence we can write $$\frac{1 - q^{7}}{(1 - q)^{7}} = 1 + 7J$$ where $J$ again represents some power series in $q$ with integer coefficients (note that each instance of $J$ may represent a different power series in $q$). Replace $q$ with $q^{2}, q^{3}, \ldots$ and multiplying the results we get $$\frac{(1 - q^{7})(1 - q^{14})(1 - q^{21})\cdots}{\{(1 - q)(1 - q^{2})(1 - q^{3})\cdots\}^{7}} = \frac{f(-q^{7})}{f^{7}(-q)}= 1 + 7J\tag{25}$$ Using identity $(3)$ we can write $$\dfrac{{\displaystyle \sum_{n = 0}^{\infty}p(7n + 5)q^{n + 1}}}{7f^{2}(-q^{7})} = qf^{3}(-q)\frac{f(-q^{7})}{f^{7}(-q)} + 7q^{2}\frac{f^{5}(-q^{7})}{f^{8}(-q)}$$ and using $(25)$ we can now write $$\dfrac{{\displaystyle \sum_{n = 0}^{\infty}p(7n + 5)q^{n + 1}}}{7f^{2}(-q^{7})} = qf^{3}(-q) + 7J = \sum_{n = 0}^{\infty}(-1)^{n}(2n + 1)q^{n(n + 1)/2 + 1} + 7J$$ We next need to analyze the coefficient of $q^{7n}$ on both sides. On the RHS we can see that \begin{align}\frac{n(n + 1)}{2} + 1 &\equiv 0\pmod{7}\notag\\ \Leftrightarrow n(n + 1) + 2 &\equiv 0\pmod{7}\notag\\ \Leftrightarrow n(n + 1) &\equiv 5\pmod{7}\notag\\ \Leftrightarrow 4n(n + 1) + 1 &\equiv 0\pmod{7}\notag\\ \Leftrightarrow (2n + 1)^{2} &\equiv 0\pmod{7}\notag\\ \Leftrightarrow (2n + 1) &\equiv 0\pmod{7}\notag\end{align} so that the coefficient of $q^{7n}$ on the RHS is a multiple of $7$. It follows that the coefficient of $q^{7n}$ in $\sum_{n = 0}^{\infty}p(7n + 5)q^{n + 1}$ is a multiple of $49$. Thus we have $p(49n + 47)\equiv 0\pmod{49}$.**Print/PDF Version**

Good one!

Anonymous

October 28, 2015 at 5:13 PM