MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Letting $d(m)$ be the number of divisors of $m$, is it the case that for $m=8n+6$,

$$ d(m) \equiv \sum_{k=1}^{m-1} d(k) d(m-k) \pmod{8}\ ?$$

It's easy to show that both sides are 0 mod 4: the left side since two primes appear to odd order in the factorization of $m$, and the right side since $m$ is neither a square nor the sum of two squares and so even products all appear twice.

But they also seem to match mod 8 for small values. Does this keep going, or does it fail somewhere?

share|cite|improve this question
up vote 17 down vote accepted

The congruence you state is true for all $m \equiv 6 \pmod{8}$. The proof I give below relies on the theory of modular forms. First, observe that $$ \sum_{k=1}^{m-1} d(k) d(m-k) = 2 \sum_{k=1}^{\frac{m-2}{2}} d(k) d(m-k) + d\left(\frac{m}{2}\right)^{2}. $$ Noting that $d(m) \equiv d\left(\frac{m}{2}\right)^{2} \pmod{8}$ if $m \equiv 6 \pmod{8}$, it suffices to prove that for every $m \equiv 6 \pmod{8}$ that $$\sum_{k=1}^{\frac{m-2}{2}} d(k) d(m-k)$$ is a multiple of $4$. The only terms in the sum that are not multiples of $4$ are those where $k$ is a perfect square, and $m-k = py^{2}$, where $p$ is prime, and $p$ divides $y$ to an even power (or $k = py^{2}$ where $p$ divides $y$ to an even power, and $m-k$ is a square). It suffices therefore to show that if $m \equiv 6 \pmod{8}$, then $m$ has an even number of representations in the form $m = x^{2} + py^{2}$ with $x, y \in \mathbb{Z}$ with $x, y > 0$ and $p$ a prime number (and the $p$-adic valuation of $y$ is even).

If $m = x^{2} + py^{2}$, then either $x$ is even, which forces $p = 2$ and $y$ odd, or $x$ is odd, in which case $y$ is odd and $p \equiv 5 \pmod{8}$.

The function $F(z) = \sum_{n=0}^{\infty} \sigma(2n+1) q^{2n+1}$, $q = e^{2 \pi i z}$ is a modular form of weight $2$ for $\Gamma_{0}(4)$. Here $\sigma(k)$ denotes the sum of the divisors function. A simple calculation shows that if $n \equiv 5 \pmod{8}$, then $\sigma(n) \equiv 2 \pmod{4}$ if and only if $n = py^{2}$ for some prime $p \equiv 5 \pmod{8}$ and a some perfect square $y$ (and moreover, the power of $p$ dividing $y$ is even, a condition which will remain in effect). It follows from this that $$ \frac{1}{2} \sum_{n \equiv 5 \pmod{8}} \sigma(n) q^{n} \equiv \sum_{\substack{p \equiv 5 \pmod{8} \\ y \geq 1}} q^{py^{2}} \pmod{2}, $$ where by this statement I mean that the power series on the left and right hand sides have integer coefficients and the coefficient of $q^{k}$ on the left side is congruent (modulo $2$) to the coefficient of $q^{k}$ on the right hand side.

By twisting $F(z)$ by Dirichlet charaters mod $8$, one can see that $G(z) = \frac{1}{2} \sum_{n \equiv 5 \pmod{8}} \sigma(n) q^{n}$ is a modular form of weight $2$ on $\Gamma_{0}(64)$. Now, observe that $F(z) \equiv \sum_{\substack{n \geq 1 \\ n \text{ odd }}} q^{n^{2}} \pmod{2}$. Now, we find that $$ F(z) G(z) + F(4z) F(2z) \equiv \sum_{x, y \geq 1, p \equiv 5 \pmod{8} \text{ prime }} q^{x^{2} + py^{2}} + \sum_{x,y} q^{x^{2} + 2y^{2}} \pmod{2}. $$ where in the second term on the right hand side we have $x \equiv 2 \pmod{4}$ and $y \equiv 1 \pmod{2}$.

The left hand side is now a modular form of weight $4$ on $\Gamma_{0}(64)$, and a computation shows that the first $1000$ Fourier coefficients are even. Indeed, Sturm's theorem proves that if the first $32$ coefficients are even, then all of them are. It follows that the number of representations of $m$ in the form $x^{2} + py^{2}$ when $m \equiv 6 \pmod{8}$ is always even, and hence the desired congruence is true.

share|cite|improve this answer
What a delightful proof. This question comes from an investigation related to overpartitions, where representations by sum of squares also pop up, but in a different form than this. How interesting that it happens again. I've also observed the phenomenon for other arithmetic progressions; I shall study your proof and try to adapt it. – William J. Keith Jul 31 '14 at 4:00
Very nice. Can you give a convenient reference to Sturm's theorem? – GH from MO Jul 31 '14 at 8:38
Jacob Sturm's original paper is titled "Congruences of modular forms" and is published in a Springer Lecture Notes in Mathematics, 1240. Another good source is William Stein's book "Modular Forms:A Computational Approach" which is available online here. Sturm's theorem is Theorem 9.18 on page 171, and a proof is given there. – Jeremy Rouse Jul 31 '14 at 13:36
@JeremyRouse: Thank you for the valuable references! – GH from MO Jul 31 '14 at 16:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.