Chapter 27: Advanced Partition Theory and q-Series

Why do different partition restrictions produce the same generating product?

A partition of a nonnegative integer $n$ is a finite nonincreasing sequence of positive integers whose sum is $n$. The empty sequence partitions zero. Let $p(n)$ count unrestricted partitions, with $p(0)=1$. Two strikingly different restrictions have the same count: partitions into distinct parts and partitions into odd parts.

The ordinary generating functions explain the equality. A part of size $m$ contributes either zero or one copy in the distinct-parts model, giving $1+q^m$. An odd part may occur any number of times, giving $1/(1-q^m)$. Therefore

$$ \prod_{m\geq1}(1+q^m) =\prod_{m\geq1}\frac{1-q^{2m}}{1-q^m} =\prod_{\substack{m\geq1\\m\text{ odd}}}\frac1{1-q^m}. $$

Why is canceling infinite factors legitimate? Can we turn the cancellation into a reversible map on actual partitions? And how does this elementary product connect to the much less elementary asymptotics and congruences of $p(n)$? Those are the chapter's central questions.

The foundation consists of this identity and the final investigation, which supplies its proof tasks and computational formulas. Sections 27.1–27.10 are optional extensions; they develop graduate material and a research bridge. The published prerequisites Binomial coefficients and identities, Partitions and structure types, Generating functions and recurrence relations, and Analytic combinatorics provide the earlier language. Complex analysis and number theory enter the later extensions; omitted analytic prerequisites are identified where used.

27.1 Euler products and partition identities

Optional advanced elective extension; not required to complete the chapter foundation. For a set $S$ of allowed positive part sizes, let $p_S(n)$ count partitions using only sizes in $S$. Choosing a nonnegative multiplicity independently for each allowed size gives the Euler product

$$ \sum_{n\geq0}p_S(n)q^n=\prod_{m\in S}(1-q^m)^{-1}. $$

In the formal power-series ring $\mathbb Z[[q]]$, the coefficient of $q^n$ depends only on factors with $m\leq n$. Thus every coefficient is defined by a finite multiplication. This is the appropriate meaning of an infinite product before convergence is discussed. If $q$ is complex and $|q|\lt1$, the same products converge locally uniformly: on $|q|\leq r\lt1$, the relevant sums of $r^m$ converge and no denominator $1-q^m$ vanishes.

For distinct parts the factor is $1+q^m$; for multiplicity at most $b_m$ the factor is $1+q^m+\cdots+q^{b_mm}$. A variable $u$ marking the total number of parts gives $\prod_{m\geq1}(1-uq^m)^{-1}$ as a formal bivariate series. Restrictions are encoded locally by the allowed choices for each size, while the exponent of $q$ records total weight.

Proof of the opening identity. Factor $1+q^m=(1-q^{2m})/(1-q^m)$. For any requested degree, cancellation takes place among finitely many relevant factors, and all canceled denominators have constant term one and hence are formal units. The numerator cancels exactly the even-sized denominator factors. The remaining factors enumerate odd-part multiplicities. Equality of coefficients proves the distinct-parts/odd-parts theorem.

Solved example. Allow only sizes one and three. The coefficient of $q^7$ in $1/((1-q)(1-q^3))$ counts solutions of $a+3b=7$ with $a,b\geq0$. They are $(7,0),(4,1),(1,2)$, giving the partitions $1^7$, $3+1^4$, and $3+3+1$. Here $1^a$ denotes $a$ copies of the part one, not exponentiation inside the partition.

Exercise. For an integer $r\geq2$, show that partitions with every multiplicity at most $r-1$ are equinumerous with partitions having no part divisible by $r$. Hint: replace each factor by $(1-q^{rm})/(1-q^m)$. Solution: the numerator cancels precisely the denominator factors at sizes divisible by $r$. The argument is coefficientwise and works even when $r$ is composite. For $r=3,n=4$, both families contain four partitions.

27.2 q-binomial theorem

Optional advanced elective extension; not required to complete the chapter foundation. The parameter $q$ refines counting by weight. Define the finite and infinite $q$-Pochhammer symbols by

$$ (a;q)_N=\prod_{j=0}^{N-1}(1-aq^j),\qquad (a;q)_0=1,\qquad (a;q)_\infty=\prod_{j\geq0}(1-aq^j). $$

For integers $0\leq K\leq N$, write the Gaussian coefficient as

$$ \binom NK_q=\frac{(q;q)_N}{(q;q)_K(q;q)_{N-K}}. $$

It is a polynomial, with the quotient understood by cancellation; outside that range it is zero. It counts partitions fitting in a rectangle with at most $K$ rows and at most $N-K$ columns, by total number of cells. In particular, its value at $q=1$ is the ordinary binomial coefficient, even though the uncanceled quotient looks undefined there.

The finite $q$-binomial theorem states

$$ \prod_{j=0}^{N-1}(1+tq^j) =\sum_{K=0}^Nq^{K(K-1)/2}\binom NK_qt^K. $$

Proof mechanism. Choosing $K$ factors gives indices $0\leq j_1\lt\cdots\lt j_K\leq N-1$, weighted by $q^{\sum j_i}$. Subtract $0,1,\ldots,K-1$ from those indices and reverse the resulting sequence. This gives a rectangle partition of weight $\sum j_i-K(K-1)/2$, and the construction is reversible. The corresponding polynomial satisfies

$$ \binom NK_q=\binom{N-1}K_q+q^{N-K}\binom{N-1}{K-1}_q, $$

which also follows algebraically from the quotient definition. The initial values and recurrence identify the two polynomials.

The infinite $q$-binomial theorem, in an analytic form, is

$$ \sum_{n\geq0}\frac{(a;q)_n}{(q;q)_n}z^n =\frac{(az;q)_\infty}{(z;q)_\infty}, \qquad |q|\lt1,\quad |z|\lt1. $$

For any complex $a$, the quotient is analytic in this disk. Write it as $R(z)$. The product gives $(1-z)R(z)=(1-az)R(qz)$ and $R(0)=1$. Equating coefficients yields $(1-q^n)c_n=(1-aq^{n-1})c_{n-1}$, proving the displayed series. This also proves the identity formally in $z$ over the rational-function field in $a,q$. The finite and infinite conventions are recorded in NIST DLMF §§17.2 and 17.5.

We will also use Euler's expansion, obtained from the finite theorem by replacing $t$ by $-z$ and taking the locally uniform limit:

$$ (z;q)_\infty=\sum_{n\geq0}\frac{(-1)^nq^{n(n-1)/2}}{(q;q)_n}z^n. $$

Exercise. Specialize the infinite theorem to $a=q$. Hint: cancel all but the first denominator factor. Solution: the coefficient ratio is one for every $n$, and the product ratio is $1/(1-z)$, recovering $\sum_{n\geq0}z^n$. This infinite statement uses $|z|\lt1$; evaluating a finite Gaussian polynomial at $q=1$ does not authorize substitution into a divergent infinite product.

27.3 Euler pentagonal number theorem

Optional advanced elective extension; not required to complete the chapter foundation. In the product $E(q):=(q;q)_\infty=\prod_{m\geq1}(1-q^m)$, choosing a distinct part contributes a minus sign. Consequently its coefficient at weight $n$ is the number of distinct-part partitions of $n$ with even length minus the number with odd length.

Euler's pentagonal number theorem states, formally in $q$ and analytically for $|q|\lt1$,

$$ E(q)=\sum_{k\in\mathbb Z}(-1)^kq^{k(3k-1)/2} =1-q-q^2+q^5+q^7-q^{12}-q^{15}+\cdots. $$

We prove it with Franklin's sign-reversing involution. Let $\lambda=(d_1\gt\cdots\gt d_s\gt0)$ be a nonempty distinct partition. Let $a=d_s$ be its smallest part, and let $b$ be the length of the consecutive run at the top: $d_1,d_2,\ldots,d_b$ decrease by one at each step, and either $b=s$ or $d_b-d_{b+1}\geq2$.

If $a\leq b$ and $a\lt s$, delete the bottom row of length $a$ and add one cell to each of the first $a$ rows. If $a\gt b$, remove one cell from each of the first $b$ rows and create a new bottom row of length $b$, except when $b=s$ and $a=b+1$. Both operations preserve total size and change the number of rows by one. At the boundary of the top run, the gap conditions keep all row lengths distinct; the stated exceptions are precisely where the construction fails.

Inverse check. In the deletion case, the new top run has length exactly $a$ and its smallest row is larger than $a$, so the insertion case reverses it. In the insertion case, the new smallest row has length $b$ and the top run has length at least $b$, so deletion reverses it. Therefore the operation is an involution on all nonexceptional partitions and pairs opposite signs.

The unpaired cases are $a=b=s$ and $b=s,a=s+1$, namely

$$ (2s-1,2s-2,\ldots,s),\qquad (2s,2s-1,\ldots,s+1). $$

Their weights are $s(3s-1)/2$ and $s(3s+1)/2$, and both have sign $(-1)^s$. The empty partition contributes one. All remaining terms cancel, proving the theorem.

Solved finite check and diagram. The left panel lists every distinct partition of $5$. The involution pairs $(5)$ with $(4,1)$; $(3,2)$ survives. The right panel lists every distinct partition of $7$: $(7)$ pairs with $(6,1)$, and $(5,2)$ with $(4,2,1)$; $(4,3)$ survives. Every dot is one cell, row lengths are the parts, paired diagrams have equal weight and opposite signs, and the gold diagrams are exceptional.

Since $P(q):=\sum_{n\geq0}p(n)q^n=1/E(q)$, coefficient comparison gives

$$ p(n)=\sum_{k\geq1}(-1)^{k+1} \left(p\left(n-\frac{k(3k-1)}2\right)+p\left(n-\frac{k(3k+1)}2\right)\right), $$

where $p(n)=0$ for $n\lt0$. Only finitely many summands remain at each $n$. This is a useful exact recurrence, with alternating pairs of signs $+,+,-,-,+,+,\ldots$.

Exercise. Compute $p(7)$ from earlier values. Hint: $p(0),\ldots,p(6)=1,1,2,3,5,7,11$. Solution: the contributing offsets are $1,2,5,7$, giving $p(7)=p(6)+p(5)-p(2)-p(0)=11+7-2-1=15$. Keeping the offset seven is essential even though it subtracts the empty partition.

27.4 Jacobi triple product

Optional advanced elective extension; not required to complete the chapter foundation. A bilateral series sums over all integers, and the quadratic exponent ensures convergence in both directions. For $0\lt|q|\lt1$ and $z\neq0$, Jacobi's triple product is

$$ \sum_{k\in\mathbb Z}(-1)^kz^kq^{k(k-1)/2} =(z;q)_\infty(q/z;q)_\infty(q;q)_\infty. $$

Both sides converge locally uniformly for $z$ away from zero. The theorem turns a theta-type series into three products; our sign and exponent conventions agree with the $q$-version in NIST DLMF §17.8.

Proof. Denote the product by $T(z)$ and expand it in a Laurent series $\sum_{k\in\mathbb Z}c_kz^k$. Cancellation of product factors gives $T(qz)=-z^{-1}T(z)$. Hence $c_{k+1}=-q^kc_k$, so $c_k=(-1)^kq^{k(k-1)/2}c_0$. It remains to determine the constant, a step that the functional equation alone does not settle.

Euler's expansion from Section 27.2 gives

$$ c_0=(q;q)_\infty\sum_{r\geq0}\frac{q^{r^2}}{(q;q)_r^2}=1. $$

To justify the last equality, every Ferrers diagram has a unique largest square in its upper-left corner, its Durfee square, of side $r$. The square contributes $q^{r^2}$. The cells to its right form a partition with at most $r$ rows; those below form one with largest part at most $r$. Each region has generating function $1/(q;q)_r$, with conjugation identifying the two types. This reversible decomposition proves the sum equals $P(q)$. Uniform convergence justifies the Laurent coefficient multiplication, completing the proof.

Solved specialization. Replace the base $q$ in the triple product by $q^3$ and take $z=q$. The exponent becomes $k+3k(k-1)/2=k(3k-1)/2$, while the product factors cover residues $1,2,0$ modulo three. Thus the product becomes $E(q)$ and recovers Euler's pentagonal theorem through a second route.

Exercise. Differentiate the triple product with respect to $z$ at $z=1$ and derive Jacobi's cubic identity. Hint: isolate the factor $1-z$ before differentiating, then pair terms indexed by $-j$ and $j+1$. Solution: the product derivative is $-E(q)^3$. The paired series derivatives sum to $-(-1)^j(2j+1)q^{j(j+1)/2}$, so

$$ E(q)^3=\sum_{j\geq0}(-1)^j(2j+1)q^{j(j+1)/2}. $$

Differentiation is justified by local uniform convergence. This identity will provide a short proof of a partition congruence in Section 27.10.

27.5 Rogers–Ramanujan identities

Optional advanced elective extension; not required to complete the chapter foundation. The two Rogers–Ramanujan identities are

$$ \sum_{r\geq0}\frac{q^{r^2}}{(q;q)_r} =\frac1{(q;q^5)_\infty(q^4;q^5)_\infty}, $$

$$ \sum_{r\geq0}\frac{q^{r(r+1)}}{(q;q)_r} =\frac1{(q^2;q^5)_\infty(q^3;q^5)_\infty}. $$

They hold formally in $q$ and analytically for $|q|\lt1$, with the empty term equal to one. These are established theorems; see NIST DLMF §17.2(vi).

The first left side counts partitions whose successive parts differ by at least two. For exactly $r$ parts, subtract the staircase $(2r-1,2r-3,\ldots,1)$, of weight $r^2$. The remaining sequence is nonincreasing and nonnegative, with at most $r$ positive parts, giving $1/(q;q)_r$. Adding the staircase is the inverse. The second identity imposes the additional condition that the smallest part is at least two; subtract $(2r,2r-2,\ldots,2)$, of weight $r(r+1)$.

The first right side allows part sizes congruent to $1$ or $4$ modulo five; the second allows sizes congruent to $2$ or $3$. Unlike Euler's odd/distinct identity, these products do not follow from a direct numerator-denominator cancellation of the gap-condition sums.

Proof mechanism sketch; the deep finite summation step is omitted. For gap partitions with largest part at most $M$, splitting according to whether $M$ occurs gives a recurrence $D_M=D_{M-1}+q^MD_{M-2}$, with appropriate empty initial cases. Gaussian polynomials express its finite solutions after the staircase subtraction. Schur's finite Rogers–Ramanujan identities transform those solutions into alternating quadratic sums; their proof requires further $q$-binomial algebra and is not supplied here. Passing coefficientwise to the limit and applying Jacobi's triple product with base $q^5$ yields the residue-class products. The staircase interpretation explains the sums, but does not prove the missing sum-to-product equality by itself.

Solved example. At weight six, the gap-at-least-two partitions are $(6),(5,1),(4,2)$. The first product permits sizes $1,4,6$ at this weight, giving $(6),(4,1,1),(1^6)$. Both counts are three. With minimum part at least two, only $(6),(4,2)$ remain; the second product gives $(3,3),(2,2,2)$, again two. These lists check the theorem's interpretations without suggesting a component-by-component correspondence.

Exercise. Check the first identity at weight eight. Hint: three parts would require at least $5+3+1=9$. Solution: the gap partitions are $(8),(7,1),(6,2),(5,3)$; the residue-class partitions are $(1^8),(4,1^4),(4,4),(6,1,1)$. Both counts are four. This finite check is evidence for a computation, not a proof for every weight.

27.6 Partition bijections and involutions

Optional advanced elective extension; not required to complete the chapter foundation. A weight-preserving bijection proves equality of counting sequences through an explicit inverse. A sign-reversing involution instead proves cancellation in a signed generating function. Both require checking domains and exceptional cases.

For the odd/distinct theorem, fix an odd size $m$ with multiplicity $a_m$. Its binary expansion is $a_m=\sum_{j\geq0}\varepsilon_{m,j}2^j$, with $\varepsilon_{m,j}\in\{0,1\}$. Replace those copies by one part $2^jm$ whenever the corresponding digit is one. The total weight is preserved because $ma_m=\sum_j\varepsilon_{m,j}2^jm$.

The output parts are distinct: every positive integer has a unique decomposition $2^jm$ with $m$ odd. Conversely, split each distinct part $2^jm$ into $2^j$ copies of its odd core $m$. Different powers give the binary digits of the reconstructed multiplicity. This proves a complete bijection, including the empty partition; no choice of merging order can change its final output.

Solved trace. Start with $(3,3,1,1,1,1)$, of weight ten. The multiplicity of three is $2=2^1$, giving part six, and the multiplicity of one is $4=2^2$, giving part four. The distinct partition is $(6,4)$. Splitting six into two threes and four into four ones recovers the original partition. The number of parts changes from six to two, so the bijection preserves weight but does not preserve length.

For Franklin's involution, the invariant is total weight while the sign $(-1)^{\text{length}}$ changes. Its exceptions must be identified structurally, not discarded as computational failures. At weight twelve the exceptional partition $(5,4,3)$ has three parts and therefore contributes $-q^{12}$ to $E(q)$. Every other distinct partition of that weight is canceled by its partner.

A different basic bijection is Ferrers conjugation: transpose the rows and columns. It sends a partition with largest part $L$ and length $s$ to one with largest part $s$ and length $L$, preserving total weight. It proves that partitions with at most $r$ parts and partitions with largest part at most $r$ have the same generating function, the fact used in the Durfee-square proof.

Exercise. Apply binary merging to $(5,3,3,3,1,1,1,1,1)$ and give the inverse. Hint: the two multiplicities equal to three or five each have two nonzero binary digits. Solution: one five remains; three threes become six and three; five ones become four and one. The result is $(6,5,4,3,1)$, of weight nineteen. Splitting each even part into copies of its odd core reverses the construction.

27.7 Rank and crank statistics

Optional advanced elective extension; not required to complete the chapter foundation. Partition congruences say that certain totals are divisible by a modulus. A statistic can explain that divisibility by dividing the relevant partitions into equally numerous residue classes.

For a nonempty partition $\lambda$, Dyson's rank is its largest part minus its number of parts. To define the Andrews–Garvan crank, let $\omega$ be its number of ones and let $\mu$ count its parts strictly larger than $\omega$, with multiplicity. The crank is the largest part if $\omega=0$, and $\mu-\omega$ if $\omega\gt0$. Give the empty partition rank and crank zero for our finite enumerations.

These statistics have established equidistribution theorems. Rank residues explain the progressions $5n+4$ modulo five and $7n+5$ modulo seven. Crank residues explain those progressions and also $11n+6$ modulo eleven. The original crank theorem is Andrews and Garvan, Dyson's crank of a partition (1988). The general equidistribution proofs require further generating-function identities and are omitted here; direct small enumeration below is a check, not their proof.

Solved instance. Enumerate all partitions of four and calculate both statistics.

Both residue columns contain each residue once, but their assignments differ. For $(2,1,1)$, $\omega=2$ and no part is strictly larger than two, so its crank is $0-2=-2$; using “at least” instead of “strictly larger” would be incorrect.

At weight six, the eleven partitions have crank residues modulo eleven appearing once each. The rank does not do so: rank one occurs twice, for $(4,1,1)$ and $(3,3)$. Thus a divisibility explanation depends on the statistic, not just on the total count.

Exercise. Compute the rank and crank of $(5,2,1,1)$, and prove that conjugation negates rank. Hint: count ones first; then interchange largest part and length under conjugation. Solution: its rank is $5-4=1$. There are two ones and exactly one part greater than two, so the crank is $1-2=-1$. If a diagram has largest part $L$ and length $s$, its conjugate has rank $s-L$, the negative of $L-s$.

27.8 Hardy–Ramanujan asymptotic formula

Optional advanced elective extension; not required to complete the chapter foundation. Unrestricted integer partitions have generating function $P(q)=1/(q;q)_\infty$. For positive integers $n\to\infty$, the Hardy–Ramanujan theorem states

$$ p(n)\sim H(n):=\frac1{4\sqrt3\,n} \exp\left(\pi\sqrt{\frac{2n}{3}}\right). $$

The symbol means $H(n)/p(n)\to1$. It does not assert that $H(n)-p(n)$ tends to zero or that rounding the estimate yields $p(n)$. The hypotheses concern unrestricted partitions and the large-integer limit; the formula must not be substituted for counts under an arbitrary restriction.

Proof mechanism sketch. Put $q=e^{-t}$ and $C=\pi\sqrt{2/3}$. The eta transformation gives, for real $t\to0^+$,

$$ P(e^{-t})\sim\sqrt{\frac{t}{2\pi}} \exp\left(\frac{\pi^2}{6t}-\frac{t}{24}\right). $$

In the coefficient integral the main exponent is $nt+\pi^2/(6t)$, with stationary point $t\approx\pi/\sqrt{6n}$. Substitution predicts $C\sqrt n$. A Gaussian analysis contributes the prefactor, and bounds on the remaining arcs establish the coefficient equivalence. The modular transformation and arc estimates are omitted analysis prerequisites; the real-axis estimate alone is insufficient. This is an established theorem of Hardy and Ramanujan, Asymptotic formulæ in combinatory analysis (1918).

Solved numerical comparison. Compute exact values by Euler's recurrence and evaluate the approximation separately. The following estimates and errors are rounded.

The relative error decreases in this sample, while the absolute error at $n=200$ is roughly $1.27\times10^{11}$. These computations illustrate the theorem and show why absolute and relative accuracy answer different questions.

Exercise. Deduce $\log p(n)/\sqrt n\to C$. Hint: take the logarithm of $p(n)/H(n)\to1$. Solution: $\log p(n)=C\sqrt n-\log n-\log(4\sqrt3)+o(1)$. Since $\log n/\sqrt n\to0$, division gives the claimed limit. This logarithmic statement is weaker than the full asymptotic, because it loses the prefactor.

27.9 Rademacher series

Optional advanced elective extension; not required to complete the chapter foundation. Rademacher replaces a leading approximation by an exact convergent series. The distinction is crucial: sufficiently many terms, together with a tail and numerical error bound, can certify an integer count.

For $n\geq1$, set $N=n-1/24\gt0$ and $C=\pi\sqrt{2/3}$. Define the sawtooth function $((x))=x-\lfloor x\rfloor-1/2$ for noninteger $x$, and $((x))=0$ for integer $x$. The Dedekind sum and its associated coefficient are

$$ s(h,k)=\sum_{r=1}^{k-1}\left(\left(\frac rk\right)\right) \left(\left(\frac{hr}k\right)\right),\qquad A_k(n)=\sum_{\substack{0\leq h\lt k\\\gcd(h,k)=1}} \exp\left(\pi i s(h,k)-\frac{2\pi i nh}{k}\right). $$

The empty sum $s(0,1)$ is zero and $\gcd(0,1)=1$, so $A_1(n)=1$. Pairing $h$ with $k-h$ makes $A_k(n)$ real. The coefficient phases depend on $n$; they must not be replaced by their absolute values when summing the series.

The exact formula is

$$ p(n)=\frac1{\pi\sqrt2}\sum_{k\geq1}A_k(n)\sqrt k\, \frac{d}{dn}\left(\frac{\sinh(C\sqrt N/k)}{\sqrt N}\right). $$

The derivative treats $n$ as a real variable and uses $N=n-1/24$; the completed expression is evaluated at the integer of interest. This classical theorem originates with Rademacher, A Convergent Series for the Partition Function p(n) (1937); NIST DLMF 27.14.9–11 gives the modern conventions. Its derivation uses eta transformations and a refined circle contour and is omitted here.

For computation, put $u_k=C\sqrt N/k$. The $k$th term becomes

$$ T_k(n)=\frac{A_k(n)\sqrt k}{2\pi\sqrt2\,N^{3/2}} \bigl(u_k\cosh u_k-\sinh u_k\bigr). $$

A proved, elementary tail bound. Let $R_K(n)=\sum_{k=1}^KT_k(n)$. There are at most $k$ terms in $A_k$, each of modulus one, so $|A_k(n)|\leq k$. For $0\leq u\leq U$,

$$ u\cosh u-\sinh u=\int_0^u t\sinh t\,dt \leq\frac{u^3}{3}\cosh U. $$

Here $\sinh t\leq t\cosh U$ follows by integrating $\cosh v\leq\cosh U$. For $k\gt K$ take $U=C\sqrt N/(K+1)$. Substitution gives $|T_k(n)|\leq C^3\cosh U/(6\pi\sqrt2\,k^{3/2})$. Comparing the sum with $\int_K^\infty x^{-3/2}dx$ proves absolute convergence and

$$ |p(n)-R_K(n)|\leq B_K(n):= \frac{C^3}{3\pi\sqrt2\sqrt K} \cosh\left(\frac{C\sqrt N}{K+1}\right). $$

This bound is intentionally simple and may be much larger than the actual error. It is sufficient for a rigorous small demonstration without invoking sharper exponential-sum estimates.

Solved certification. At $n=5$, the partial sums for $K=1,2,5,10,20$ are approximately $7.262100194$, $7.027886465$, $7.019167288$, $6.997272195$, and $6.997770187$. They are not monotone, because the phases cause cancellations. Direct rational interval arithmetic with bounds for the elementary functions verifies

$$ 6.99777018\lt R_{20}(5)\lt6.99777020,\qquad B_{20}(5)\lt0.294. $$

Thus the exact integer lies strictly between $6.70377018$ and $7.29177020$, whose only integer is $7$. This certifies $p(5)=7$. The interval computation uses outward rounding, a Machin arctangent formula to bound $\pi$, Taylor remainders for cosine and exponential, and exact rational Dedekind sums. Agreement of two floating-point runs alone would not certify that interval.

Exercise. Compute $A_2(n)$ and explain its parity dependence. Hint: the only allowed residue is $h=1$, and $s(1,2)=0$. Solution: $A_2(n)=e^{-\pi in}=(-1)^n$. Thus the second term corrects the first upward for even $n$ and downward for odd $n$. A certified rounding procedure also requires the numerical uncertainty of $R_K$ plus the tail bound to fit inside a single integer's rounding interval.

27.10 Modular forms and partition congruences

Optional research specialization extension; not required to complete the chapter foundation. Modular forms impose transformation laws on analytic functions and thereby constrain their Fourier coefficients. The congruences below are established theorems.

Let $\tau$ lie in the upper half-plane and $q=e^{2\pi i\tau}$, so $|q|\lt1$. A holomorphic modular form of integer weight $w$ for $\mathrm{SL}_2(\mathbb Z)$ is holomorphic in that half-plane, satisfies

$$ f\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)^w f(\tau) \quad\text{for integers }a,b,c,d\text{ with }ad-bc=1, $$

and is holomorphic at the cusp, meaning its Fourier expansion at infinity has no negative powers. For a congruence subgroup one must check all its cusps, and a character may occur in the transformation law.

Dedekind's eta function is $\eta(\tau)=q^{1/24}E(q)$. It obeys

$$ \eta(\tau+1)=e^{\pi i/12}\eta(\tau),\qquad \eta(-1/\tau)=(-i\tau)^{1/2}\eta(\tau), $$

with the consistent analytic square-root branch. These standard transformations are recorded in NIST DLMF §23.18. The phase and square root matter: $\eta$ is not an ordinary integer-weight form with trivial multiplier. Its 24th power $\Delta(\tau)=\eta(\tau)^{24}$ is a weight-12 cusp form. Moreover $\eta(\tau)^{-1}=q^{-1/24}P(q)$ has weight $-1/2$ with a multiplier and a pole at the cusp; the partition generating function is not itself a positive-weight holomorphic modular form.

Ramanujan's congruences are, for every $n\geq0$,

$$ p(5n+4)\equiv0\pmod5,\qquad p(7n+5)\equiv0\pmod7,\qquad p(11n+6)\equiv0\pmod{11}. $$

The original statements appear in Ramanujan, Congruence properties of partitions. A short primary-source treatment using eta powers and theta identities is Zagier, Ramanujan's congruences for partitions modulo 5, 7 and 11. We prove the modulo-five case below; the other two are cited theorems, and their eta-power identities are omitted prerequisites.

Complete modulo-five proof. In $\mathbb F_5[[q]]$, the binomial theorem gives $(1-q^m)^5\equiv1-q^{5m}$. Therefore $E(q)^5\equiv E(q^5)$ and

$$ P(q)\equiv\frac{E(q)^4}{E(q^5)}\pmod5. $$

Multiply the pentagonal expansion of $E$ by the cubic identity for $E^3$. A summand has exponent $g_k+t_j$, where $g_k=k(3k-1)/2$, $t_j=j(j+1)/2$, and coefficient $(-1)^{k+j}(2j+1)$. The integer identity

$$ 24(g_k+t_j)+4=(6k-1)^2+3(2j+1)^2 $$

shows that $g_k+t_j\equiv4\pmod5$ implies $x^2+3y^2\equiv0$, with $x=6k-1,y=2j+1$. If $y\not\equiv0$, this would make $2=(x/y)^2$ a quadratic residue modulo five, which it is not. Thus $x\equiv y\equiv0$, and the coefficient is divisible by five. Every coefficient of $q^{5n+4}$ in $E^4$ therefore vanishes modulo five. The inverse of $E(q^5)$ has only powers divisible by five and constant term one, so dividing cannot change that conclusion. This proves the congruence.

Solved product refinement. A deeper established dissection identity is

$$ \sum_{n\geq0}p(5n+4)q^n =5\frac{(q^5;q^5)_\infty^5}{(q;q)_\infty^6}. $$

It is recorded in NIST DLMF 27.14.15; its full dissection proof is not needed for the complete argument above. The product quotient has integral coefficients. Its initial expansion is $1+6q+27q^2+\cdots$, giving $p(4)=5,p(9)=30,p(14)=135$. The $q^2$ coefficient is $21+6$: either two unit-weight choices in $(1-q)^{-6}$, or one weight-two choice in $(1-q^2)^{-6}$.

Research-method bridge, proof sketch. Eta products and theta series can be placed in spaces of modular forms of a known weight and level. The finite dimension and a valid coefficient bound can then turn a finite identity check into a proof, after holomorphy at every cusp, transformation laws, and integrality are established. Arbitrary agreement through a chosen cutoff does not establish any of these hypotheses. The modular-space construction and its finite-check theorem are omitted here; Zagier's paper gives a concrete theta-series route for the three classical congruences.

Exercise. Verify the modulo-five residue argument by listing squares, and check $p(19)$. Hint: the square residues are $0,1,4$; the first four quotient coefficients are $1,6,27,98$. Solution: twice a nonzero square is $2$ or $3$, never a square. The cubic product coefficient is $56+36+6=98$, giving $p(19)=5\cdot98=490$. This small calculation agrees with Euler's recurrence, while the preceding residue proof covers every $n$.

Verify a q-series identity and assess a partition asymptotic

The investigation separates three claims: an identity of formal series, a finite computation, and a limiting estimate. Use the odd/distinct identity for the first, exact integer recurrence values for the second, and $H(n)=e^{\pi\sqrt{2n/3}}/(4\sqrt3\,n)$ for the third. Optional advanced parts connect the same Euler product to congruences and certified exact evaluation.

Part A: warm-up, 15 points. Compute the coefficients through $q^{10}$ of $\prod_{m\geq1}(1+q^m)$ and $\prod_{m\text{ odd}}(1-q^m)^{-1}$. Show the four partitions of six on each side. Hint: for degree at most ten, factors of size greater than ten have no effect.

Worked solution. Both coefficient lists, beginning at degree zero, are

$$ 1,1,1,2,2,3,4,5,6,8,10. $$

The opening table lists the weight-six correspondence. A finite computation can begin with an array whose only nonzero entry is the constant coefficient one. For distinct parts, update indices in descending order for each size $m$; for odd parts with unlimited multiplicity, update indices in ascending order for each allowed odd $m$. Reversing either order changes the restriction being counted.

Part B: proof, 25 points. Prove the product identity for every degree, then construct its binary-multiplicity bijection and verify its inverse. Hints: split denominator factors into even and odd sizes; decompose each positive integer into a power of two times an odd integer.

Solution outline. For a fixed degree, all relevant cancellations are finite. The numerator in $\prod_m(1-q^{2m})/(1-q^m)$ removes exactly the even factors. For the bijection, binary digits of an odd size's multiplicity select distinct parts $2^jm$. Unique odd cores prevent collisions, preserve total weight, and recover those digits under splitting. Thus both algebra and a reversible map prove equality; matching the displayed eleven coefficients alone does not.

Part C: exact computation, 20 points. Generate $p(n)$ through $n=1000$ using the pentagonal recurrence, whose offsets are $k(3k\mp1)/2$ and whose signs occur in pairs $+,+,-,-,\ldots$. Independently check a selected range using the unrestricted product. Hint: with every size allowed and unbounded multiplicity, ascending array updates generate $\prod_{m=1}^M(1-q^m)^{-1}$ through degree $M$.

Expected checks and solution outline. The initial values through size ten are $1,1,2,3,5,7,11,15,22,30,42$. Further checks are $p(50)=204226$, $p(100)=190569292$, $p(200)=3972999029388$, and

$$ p(1000)=24061467864032622473692149727991. $$

The recurrence needs $O(\sqrt n)$ offset terms at size $n$, so computing all values through $M$ uses $O(M^{3/2})$ integer additions and subtractions and $O(M)$ stored integers. These are operation counts, not bit-complexity bounds: the integers grow with $M$. Product dynamic programming provides an independent $O(M^2)$-update check.

Part D: assess the asymptotic, 20 points. Evaluate $H(n)$ at the requested sizes and report $H(n)/p(n)-1$. Explain which accuracy claim the theorem proves and whether rounding recovers exact counts. Hint: compare relative error with absolute error, and avoid evaluating a large exponential at insufficient precision.

Verified numerical reference. The signed relative errors at $n=10,50,100,200,1000$ are approximately $0.145341,0.0654398,0.0457136,0.0320293,0.0141524$. Thus the leading estimate is still about $1.42\%$ high at $n=1000$. The theorem proves relative error tending to zero, not the direction of error or monotonicity at every size. It also supplies no absolute-error bound below one-half. At $n=100$, $H(n)\approx199280893.350$, while the exact count is $190569292$, so rounding fails substantially.

These calculations illustrate a proved theorem; they do not prove its limiting assertion. The full Hardy–Ramanujan contour argument is an optional analytic extension rather than a required part of this investigation.

Part E: congruence and application, 20 points. Let $E=\prod_{m\geq1}(1-q^m)$. For this foundation investigation, use the supplied identities

$$ E(q)=\sum_{k\in\mathbb Z}(-1)^kq^{g_k},\qquad E(q)^3=\sum_{j\geq0}(-1)^j(2j+1)q^{t_j}, $$

where $g_k=k(3k-1)/2$ and $t_j=j(j+1)/2$; their optional proofs appear in Sections 27.3 and 27.4. Show $E^5\equiv E(q^5)$, and use $24(g_k+t_j)+4=(6k-1)^2+3(2j+1)^2$ to prove $p(5n+4)\equiv0\pmod5$. Verify the first three values and explain an application of the original product identity.

Solution outline. Frobenius holds coefficientwise modulo five. An exponent congruent to four in $E^4$ forces both squares in the displayed identity to vanish, since two is a quadratic nonresidue modulo five; the factor $2j+1$ in the cubic coefficient then vanishes. Dividing by $E(q^5)$ changes exponents only by multiples of five. The checks are $p(4)=5,p(9)=30,p(14)=135$. This proof connects Euler and Jacobi identities to the arithmetic controlled more broadly by eta transformations; a numerical list of multiples of five would not establish the infinite congruence.

A cross-disciplinary interpretation uses an idealized collection of equally spaced independent energy modes, with mode $m$ contributing $m$ units. Unlimited occupation of each odd mode has generating product $\prod_{m\text{ odd}}(1-q^m)^{-1}$; zero-or-one occupation of every mode has product $\prod_m(1+q^m)$. Euler's identity says that the two mathematical models have equal numbers of configurations at each total energy, even though their occupancy rules differ. Binary merging explicitly translates their configurations. Here $q$ may serve as an energy-marking variable, or as $e^{-\beta\varepsilon}$ with positive inverse-temperature parameter $\beta$ and energy unit $\varepsilon$; the model assumes independent modes without additional degeneracy or interaction.

Optional certification extension, ungraded. Reproduce $R_{20}(5)$ using exact rational Dedekind sums and outward-rounded elementary-function intervals. Use the bound $B_{20}(5)\lt0.294$ to certify the unique integer seven. Solution route: prove the tail bound from $|A_k|\leq k$ and $u\cosh u-\sinh u\leq u^3\cosh U/3$; then include every numerical uncertainty in the interval. The displayed partial-sum interval together with the tail gives $(6.70377018,7.29177020)$, containing only seven. A high-precision decimal approximation without rigorous error control is a useful check but not this certification.

Optional identity extension, ungraded. Replace binary multiplicities by base three and prove the multiplicity-at-most-two/no-multiple-of-three identity. At weight four the unrestricted-repetition side contains $(4),(2,2),(2,1,1),(1^4)$, while the bounded-multiplicity side contains $(4),(3,1),(2,2),(2,1,1)$. Merge three equal parts into one triple-sized part according to base-three digits; reverse by splitting off the largest power of three. This is a proof exercise extending an established identity, not a claim that a new research conjecture has been discovered.