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

The Ramanujan conjecture states that the coefficients $\tau(n)$ in the identity


satisfy the inequality $|\tau(n)|\leq d(n)n^{11/2}$, where $d(n)$ is the number of divisors of $n$. A positive answer to the conjecture followed (non-trivially) from Deligne's proof of the Riemann hypothesis for varieties over finite fields, conjectured by Weil.

One can interpret the coefficient $\tau(n)$ combinatorially as follows. Let $(a_n)$ be the sequence $1,1,1,\dots,1,2,2,2,\dots,2,3,3,3,\dots,3,4,\dots$, where each number occurs 24 times. Let $\rho(n)$ be the number of ways of writing $n-1$ as a sum $x_1+\dots+x_r$ of $r$ terms of the sequence for some even number $r$, and let $\sigma(n)$ be the number of ways of writing $n-1$ as a sum $x_1+\dots+x_s$ of $s$ terms of the sequence for some odd number $s$. Then $\tau(n)=\rho(n)-\sigma(n)$. It is easy to check that both $\rho(n)$ and $\sigma(n)$ grow very fast -- at least at a rate $\exp(c\sqrt{n})$ (and I'm almost sure that that is the correct order of magnitude, but haven't carefully checked so don't want to claim it as a fact). So Deligne's result tells us that there is a huge amount of cancellation: the number of representations as an even sum is almost exactly half the total number of representations.

Of course, it tells us something considerably more precise than that, and it seems clear that elementary methods are unlikely to be sufficient for this more precise result. But what if we just ask for a proof that $\tau(n)$ grows at most polynomially? Is that easy to show? If it is, then a much more general result ought to be true. For example, suppose we take an arbitrary non-decreasing sequence $a=(a_1,a_2,a_3,\dots)$ of positive integers such that $cr\leq a_r\leq Cr$ for every $r$. Define $\rho_a(n)$ to be the number of ways of writing $n$ as a sum of an even number of terms of this sequence and $\sigma_a(n)$ as the number of ways of writing $n$ as a sum of an odd number of terms. Must $\tau_a(n)=\rho_a(n)-\sigma_a(n)$ grow at most polynomially? If so, then what can be said about the degree of this polynomial in terms of $c$ and $C$?

Note that we have the identity

$$\prod_{r=1}^\infty(1-q^{a_r})=\sum_n\tau_a(n)q^n\ .$$

(A small remark is that we don't quite recover Ramanujan's $\tau$ function when the sequence takes each positive integer 24 times, because in this combinatorial context there is no motivation for taking the initial $q$ and shifting everything by 1.)

However, in this more general problem, we don't obtain a modular form when we substitute $q=e^{2\pi iz}$. As far as I can see, this rules out not just Deligne's proof methods but also earlier methods such as those of Rankin that gave weaker bounds. However, I don't know my way around this literature: is a result like the one suggested known? Is it even true?

Edit: As Garth Payne points out, it isn't true if all the $a_r$ are odd, since then the parity of the number of terms you need to pick depends on the parity of $n$. So for my question to make sense I need to add some extra condition. I don't really care what that condition is, but one possibility is to take $C$ to be less than 1, but to modify the growth condition to $cn-u\leq a_n\leq Cn+u$ for some $c>0$, $C<1$ and $u$. Or we could insist that each $a_r$ occurs in the sequence an even number of times. Basically, any condition that rules out this kind of example would leave a question that would interest me.

Further edit: Maybe better than those two conditions is just to assume that the density of terms of the sequence that are even is bounded below the whole time.

share|cite|improve this question
$\tau(n)=O(n^{6+\epsilon})$ for all $\epsilon>0$ follows relatively simply from basic complex analysis; this would be covered in a first course in modular forms. – user30035 Mar 29 '13 at 9:15
[but the methods are very specific to modular forms; they need the relationship between $\tau(z)$ and $\tau(-1/z)$] – user30035 Mar 29 '13 at 9:17
J.-P. Serre wrote a paper on $\prod_m(1-q^m)^n$ for various other values of $n$; these are still linked to modular forms, but the behaviour of the coefficients can be rather different (sometimes almost all of the coefficients are zero!). Glasgow Math. J. 27 (1985), 203–221. You might find it of interest. – user30035 Mar 29 '13 at 9:24
The Dirichlet series $L_a(s)=\sum_{n \geq 1} \tau_a(n) n^{-s}$ can be expressed as a Mellin transform and the assumption $cr \leq a_r \leq C_r$ should imply that this Mellin transform makes sense for $\operatorname{Re}(s)$ large enough. However it's not clear to me what can be deduced on the abscissa of convergence, let alone on a polynomial bound an $\tau_a(n)$. As you explain the function is not modular in general so it's not clear what one should expect. – François Brunault Mar 29 '13 at 9:42
Great question, and nice comments. Just a little point of history: the estimate $\tau(n)=O(n^{6+\epsilon})$ and more generally similar estimates for coefficients of cuspidal modular forms, are due to Hecke, and therefore much predate not only Deligne's but even Rankin. Also, as wccanard points out, those estimate are quite "elementary" in the sense that they use only very basic complex analysis (Cauchy's formula) plus the fact that $q \prod (1-q^n)^24$ is indeed modular, which is not trivial but was already known to Jacobi. But you mean "elementary" as "without complex analysis" here. – Joël Mar 29 '13 at 14:30

Note that we have the identity

$$\prod_{r=1}^\infty(1-q^{a_r})=\sum_n\tau_a(n)q^n\ .$$

I'm afraid I'm missing something, but it seems that if we take all the $a_r$ odd, then there is no cancellation. For example, take $a_r=2r-1$, $c=1$, $C=2$, and replace $q$ by $-q$. We have

$$\prod_{r=1}^\infty(1+q^{2r-1})=\sum_n(-1)^n\tau_a(n)q^n\ ,$$

and the growth of $\tau_a(n)$ is clearly not polynomial.

share|cite|improve this answer
I'm taking $1-q^{a_r}$, and not $1+(-q)^{a_r}$. – gowers Mar 29 '13 at 16:43
Ah, I see the point now. OK, I'll go back and add a condition. – gowers Mar 29 '13 at 16:45

A sufficient condition that $\tau_a(n)$ grows at most polynomially in $n$ is that $\prod_{r=1}^\infty (1-q^{a_r})$ be a expressible as a finite product $S_1 \ldots S_m$ of series with bounded coefficients. (Let $S_i=\sum_{j=1}^\infty c_{i,j} q^j$, and let $B_j$ be the bound for the coefficients of $S_j$. $\tau_a(n)=\sum_{t_1+\cdots +t_m=n} c_{1,t_1} \cdots c_{1,t_m}$, hence $|\tau_a(n)| \le B_1 \ldots B_m n^m$.)

Thus, it follows from a 24-fold application of the pentagonal number theorem, $$\prod_{n=1}^\infty (1-x^n)=\sum_{k=-\infty}^\infty(-1)^kx^{k(3k-1)/2},$$ that $\tau(n)$ grows polynomially. (This argument presumably goes back to Ramanujan.)

The condition of having the density of even terms bounded below is not sufficient to have $\tau_a(n)$ be bounded by a polynomial; $a_n=4n-2$ is a counterexample by a similar argument to my previous answer (replace $q$ with $iq$). We can get rid of counterexamples in that vein by requiring that the sequence $a_n$ has an infinite subsequence $b_n$ such that $\tau_b$ is bounded, which leads me to wonder what bearing the boundedness of $\tau_b(n)$ for an infinite subsequence $b$ of $a$ has on the polynomial boundedness of $\tau_a(n)$, i.e., is it conceivably necessary or sufficient?

share|cite|improve this answer
So here the exponent is 24? – Will Sawin Mar 29 '13 at 23:31
@Will Sawin. I'm not sure what you're asking. For Gowers' weak form of the Ramanujan Conjecture I'm taking $S_1=S_2=\cdots=S_{24}=\prod_{n=1}^\infty(1-q^n)=1-q-q^2+q^5+q^7-\cdots$ and $S_{25}=q$. – Garth Payne Mar 30 '13 at 2:04
@Will Sawin. @Douglas Zare. You can get exponent $\frac{23}{2}$ by taking into account that most of the coefficients are 0. Let $T_i(n)$ bound the number of coefficients in $c_{i,0},\ldots,c_{i,n}$ that are nonzero. Then $|\tau_a(n)| \le B_1 \ldots B_m T_2(n) \ldots T_{m}(n)$. ($T_1$ doesn't figure into it because the choice of $t_1$ is determined by the choices of the other $t_i$.) When the $S_i$ are as above, we can take $T_i(n)=c\sqrt n$ for $i=1,\ldots 24$ and $T_{25}(n)=1$. – Garth Payne Mar 30 '13 at 14:55

It seems very unlikely. There are plenty of meromorphic modular functions (as in Payne's answer) whose coefficients fail to satisfy polynomial growth, for example,

$$q^{\frac{M-1}{24}} \cdot \frac{\eta(\tau)}{\eta(M \tau)} = \prod_{n \nmid M} (1-q^n).$$

If one multiplies this by any power of $\eta(\tau)$, the result (a meromorphic modular form) still has a pole at the cusp above $0$, and the coefficients will exhibit similar behavior. So it would seem that very regular sequences will still cause you problems. The fact that the functions above exhibit coefficient growth of the flavour $\exp(c \sqrt{n})$ [at least in arithmetic progressions] is not obvious, but I imagine such a proof is incidental for your purposes.

share|cite|improve this answer
+1, just for the nom de plume – Yemon Choi Mar 30 '13 at 10:28

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.