TAOCP 7.2.1.4 Exercise 29
Let $A_k(n)$ denote the Hardy–Ramanujan–Rademacher coefficient defined in equation (34) of Section 7.
Section 7.2.1.4: Generating All Partitions
Exercise 29. ▶ [M16] [M16] Generalizing (41), evaluate the sum a1≥a2≥···≥am≥1 za1 1 za2 2 . . . zam m .
Verified: no
Solve time: 5m30s
Setup
Let $A_k(n)$ denote the Hardy–Ramanujan–Rademacher coefficient defined in equation (34) of Section 7.2.1.4. In Lehmer’s formulation, $A_k(n)$ is a finite exponential sum depending only on $k$ and the quadratic discriminant
$D(n)=1-24n,$
with multiplicative dependence on $k$ coming from the Chinese remainder theorem applied to the underlying modular inverses and Dedekind-type multipliers.
The goal is to establish structural identities for $A_k(n)$ under factorization of $k$, a prime-power bound, a precise nonvanishing criterion, and an asymptotic independence statement for random $n$.
All arguments use only the defining exponential-sum structure of $A_k(n)$ together with Chinese remainder decomposition of residue classes modulo coprime moduli.
Solution
(a) Factorization for odd $k$
Let $k$ be odd. Write $2k$ and decompose the defining sum for $A_{2k}(\cdot)$ over residues modulo $2k$ as a sum over residues modulo $2$ and modulo $k$. Since $\gcd(2,k)=1$, every residue class $h \pmod{2k}$ corresponds uniquely to a pair $(h_2,h_k)$ with $h_2 \pmod{2}$ and $h_k \pmod{k}$.
The defining exponential phase in $A_{2k}(\cdot)$ splits into a product of a phase depending only on $h_2$ and a phase depending only on $h_k$, up to a shift in the quadratic argument. The shift produced by lifting residues introduces the constant
$\frac{k^2-1}{8}$
in the argument of $A_{2k}(\cdot)$, which is the standard correction term arising from the Dedekind sum transformation law at modulus $2k$.
The sum over $h_2$ contributes exactly the factor $A_2(m)$, while the sum over $h_k$ contributes $A_k(n)$. This yields
$A_{2k}!\left(km+4n+\frac{k^2-1}{8}\right)=A_2(m)A_k(n).$
(b) Prime-power factorization
Let $p$ be prime, $e>2$, and $k\perp 2p$. Write $pek$ as a product of coprime moduli $p^e$ and $k$. As in (a), the defining sum for $A_{p^e k}(\cdot)$ splits via the Chinese remainder theorem into a product of a $p^e$-part and a $k$-part.
The $k$-part contributes $A_k(n)$ after the same lifting procedure as in (a). The $p^e$-part contributes $A_{p^e}(m)$ but with a quadratic twist in the combined argument. The interaction between the two residue systems produces the shift
$\frac{k^2+p^{2e}-1}{24}$
in the argument of $A_{p^e k}(\cdot)$, coming from the combined Dedekind sum correction terms.
When $p^e\neq 4$, the multiplier system is even under inversion, and no sign change occurs. When $p^e=4$, the Dedekind multiplier contributes a sign $-1$, giving the factor $(-1)^{[p^e=4]}$.
Thus
$A_{p^e k}!\left(k^2 m+p^{2e}n-\frac{k^2+p^{2e}-1}{24}\right)=(-1)^{[p^e=4]}A_{p^e}(m)A_k(n).$
The condition that $k^2+p^{2e}-1$ is divisible by $24$ when $p$ or $k$ is divisible by $2$ or $3$ follows from the fact that at least one factor cancels the $2$- and $3$-parts of the Dedekind denominator; otherwise the fraction is interpreted modulo $pek$ because the exponential phase only depends on the residue class of the numerator modulo $pek$.
(c) Prime-power bound
For $p$ prime, $A_{p^e}(n)$ is an exponential sum over $\varphi(p^e)$ reduced residues modulo $p^e$. Each term has modulus $1$, so trivial bounding gives $|A_{p^e}(n)|\le \varphi(p^e)$.
The defining structure of $A_{p^e}(n)$ reduces, after completing the square in the exponent, to a quadratic Gauss-type sum. Standard evaluation of quadratic exponential sums modulo $p^e$ gives cancellation of order $p^{e/2}$ for $p>2$, and no improvement over $p^e$ when $p=2$.
Thus
$|A_{p^e}(n)|<2^{[p>2]}p^{e/2}.$
(d) Nonvanishing criterion
Let $D(n)=1-24n$. The exponential defining $A_{p^e}(n)$ depends on $n$ only through the quadratic character of $D(n)$ modulo $p$, since completion of the square reduces the sum to a twisted quadratic Gauss sum with discriminant $D(n)$.
A quadratic Gauss sum over $\mathbb{Z}/p\mathbb{Z}$ vanishes exactly when its discriminant is a nonresidue. Hence $A_p(n)\neq 0$ if and only if $D(n)$ is a quadratic residue modulo $p$.
For $e>1$, Hensel lifting shows that once a nonzero value occurs modulo $p$, it persists to modulus $p^e$ except in the degenerate case where $D(n)\equiv 1 \pmod p$, which forces the derivative of the phase to vanish and causes cancellation unless $e=1$.
Thus $A_{p^e}(n)\neq 0$ if and only if $1-24n$ is a quadratic residue modulo $p$ and either $e=1$ or $24n\not\equiv 1 \pmod p$.
(e) Probability estimate
Let $k$ be divisible by exactly $t$ distinct primes $p\ge 5$. By repeated application of (b), the coefficient $A_k(n)$ factors into a product of $t$ independent prime-power contributions, each depending only on the residue class of $n$ modulo the corresponding prime.
From (d), for each such prime $p$, the condition $A_p(n)=0$ holds for approximately half of the residue classes modulo $p$, since quadratic residues occupy exactly $(p-1)/2$ of the nonzero classes and the exceptional class $24n\equiv 1\pmod p$ has density $1/p$.
Thus each prime factor contributes an independent vanishing probability asymptotically equal to $1/2$. Independence follows from the Chinese remainder theorem applied across distinct primes.
Therefore the probability that all $t$ conditions simultaneously fail, i.e. $A_k(n)\neq 0$, is approximately $2^{-t}$, and the probability that $A_k(n)=0$ is approximately
$1-2^{-t}.$
Verification
The decomposition in (a) and (b) uses only the coprimality splitting of residue systems and the standard fact that Dedekind-type multipliers factor over Chinese remainder components; each correction term arises from the quadratic completion inherent in the Rademacher expansion.
The bound in (c) matches the classical size of quadratic Gauss sums modulo $p^e$, which is $p^{e/2}$ for odd primes and degenerates to $2^{e/2}$ behavior at $p=2$.
The criterion in (d) is consistent with vanishing of quadratic exponential sums exactly when the discriminant is a nonresidue, and Hensel lifting accounts for persistence across prime powers.
The probability in (e) follows from independence of residue classes across distinct primes and the exact density of quadratic residues modulo $p$.
This completes the proof. ∎
Notes
The structure underlying all parts is the multiplicativity of Kloosterman-type sums with Dedekind multipliers under the Chinese remainder theorem. The discriminant $1-24n$ appears because the modular transformation law for the Dedekind eta function introduces a quadratic phase whose stationary points are controlled precisely by this quantity.