Let $f(n) = \theta n^d + a_{d-1} n^{d-1} + \cdots a_1 n + a_0$ be a polynomial with real coefficients, and $\theta$ irrational. Let $S_N = \sum_{n=1}^N e^{2 \pi i f(n)}$. Weyl's Equidistribution theorem for polynomials is equivalent to the claim that $S_N/N \to 0$ as $N \to \infty$. You can read a nice proof of this theorem on Terry Tao's blog (see Corollary's 5 and 6). I had thought that Weyl's Inequality was supposed to be a more precise version of this bound. However, I can't actually figure out how to get Weyl's Inequality to imply the required claim!

Specifically, let $p/q$ be a rational number in lowest terms with $|\theta - p/q| \leq 1/q^2$. Weyl's Inequality is the bound:

$$S_N/N \leq 100 \left( \log N \right)^{d/2^d} \left( \frac{1}{q} + \frac{1}{N} + \frac{q}{N^d} \right)^{1/(2^d-1)}$$

Here are I am quoting from Timothy Gowers' notes. (UPDATE: George Lowther, below, suggests that Gowers may have a typo.) Wikipedia has a softer version, with more freedom in choosing parameters; I think my question applies to both versions.

Now, suppose that the convergents $p_i/q_i$ of $\theta$ grow so fast that $q_{i+1} > e^{(d+1) q_i}$. And take $N \approx e^{q_i}$. I get that, for any choice of $q$ with $|\theta - p/q| < 1/q^2$, either $1/q > 1/\log N$ or $q/N^d > 1$. This gives infinitely many $N$'s for which the right hand bound is useless (greater than $1$). So it seems that Weyl's inequality does not prove $S_N/N \to 0$.

Am I missing something?

The motivation for this question was my attempt to answer this question over at math.SE. So any useful comments you have on that question would be appreciated as well.

  • $\begingroup$ Why prove equidistribution of this sequence using Weyl's inequality? Der Van der Corput lemma (Corollary 2 in terrytao.wordpress.com/2008/06/14/…) provides a much simpler proof. And as you observe yourself, the conclusions of Weyl's inequality here are not very good, which they can't be, since for the numbers you describe, the sequence $\theta n$ is very close to being periodic. $\endgroup$ – Helge Aug 17 '10 at 22:12
  • $\begingroup$ I actually got into this because I was trying to answer the math.SE question I linked, so I needed a strengthened version of $S_N/N \to 0$. I thought Weyl's inequality was what I was looking for, and was then very confused when I realized I couldn't even use it to get that far. $\endgroup$ – David E Speyer Aug 17 '10 at 22:25
  • $\begingroup$ In the math.SE question you say that $S_N/N=O(N^{\epsilon-1/2^d})$. Is it even true? Do you have any reference for this? The proof below by Benoit doesn't seem to extend to give a convergence rate, and Terry Tao's proof doesn't say how fast $S_N/N$ goes to zero. $\endgroup$ – George Lowther Aug 18 '10 at 12:39
  • $\begingroup$ In fact, I don't think it is true even for d=2. By choosing $\theta$ very close to a rational, you can make $S_N/N=\frac1N\sum_{n=1}^n\exp(2\pi i\theta n^2)$ tend to zero as slowly as you like. That is, for any $h\colon\mathbb{N}\to\mathbb{R}$ tending to zero, $\theta$ can be chosen such that $\limsup S_N/(Nh(N))=\infty$. So the equidistribution theorem can't be strengthened without putting further restrictions on how well &theta; can be approximated by rationals. $\endgroup$ – George Lowther Aug 18 '10 at 13:22
  • $\begingroup$ I no longer believe I know such a bound to be true. However, that doesn't mean I see yet how to show that I can make $S_N/N$ go to zero as slowly as I like, in the sense you claim. (It is easy to see that for any $N$ and any $a<1$, there is a $\theta$ such that $S_N/N > a$. But that is not the order of quantifiers I care about.) I'd love to see the details if you have an argument for this. $\endgroup$ – David E Speyer Aug 18 '10 at 14:09

I may be wrong, but it seems to me that in fact the liminf is sufficient since it is obtain via a bound that does not depend on $f$. I do not have time to check this in detail, so I apologize if this is all wrong. The idea is to use the points at which we have a good control on $S_N$ (simultaneously for $f$ and all its translates, and it is the point that seems dubious to me) and then cut the summation interval into pieces of appropriate size.

Let us denote by $S_N^t$ the exponential sum corresponding to the function $f(\cdot+t)$. Then if I am not mistaken, for all $\varepsilon$ there is a $N_\varepsilon$ such that for all $t$, $S_{N_\varepsilon}^t\leqslant \varepsilon N_\varepsilon$. Then given any $K$, one has $$S_{KN_\varepsilon}\leqslant \sum_{k=1}^K S_{N_\varepsilon}^{kN_\varepsilon}\leqslant K\varepsilon N_\varepsilon.$$

Then, for all $N$, letting $K=\lfloor N/N_\varepsilon \rfloor$ we get that $S_N\leqslant K\varepsilon N_\varepsilon + N_\varepsilon\leqslant \varepsilon N+N_\varepsilon$. It follows that $\limsup S_N/N = 0$.

  • $\begingroup$ +1 fantastic! This looks good to me. Weyl's inequality only refers to the degree of f and its leading coefficient, which are the same for all translates of f. So it uniformly bounds all $S^t_N$. $\endgroup$ – George Lowther Aug 18 '10 at 10:24
  • $\begingroup$ Sorry, wasn't very clear there. I meant, for each N it uniformly bounds $\{S^t_N\colon t\in\mathbb{R}\}$. $\endgroup$ – George Lowther Aug 18 '10 at 10:30
  • $\begingroup$ That's really slick! Now to think about whether I can push it to handle the math.SE question... $\endgroup$ – David E Speyer Aug 18 '10 at 11:17
  • 1
    $\begingroup$ I have turned this into a tricky article, see tricki.org/article/… $\endgroup$ – Benoît Kloeckner Aug 26 '10 at 13:09


At first sight I think you might be right about this. Personally, I try to avoid using Weyl's inequality in this form, but rather some statement of the following form: If $|S_N| \geq \epsilon N$, and if $\epsilon > N^{-c}$, then there is some $q \leq \epsilon^{-C}$ such that the fractional part of $q\theta$ is at most $\epsilon^{-C}/N^d$.

In other words: if the exponential sum is large then $\theta$ is very close to a rational with denominator $q$.

I sketch a proof of this ``log-free'' variant below. I don't think the inequality is typically stated in this way because so far as I'm aware it's more effort to prove, and because the form you stated is just fine for Waring's problem, where the factor of $(\log N)^C$ isn't very important. However, as you point out, it does seem to be important when talking about the equidistribution result (although normally one wouldn't involve quantitative estimates when talking about equidistribution results of the type you state).

Let me try to be a little more specific about how to prove this ``log free'' variant of Weyl's inequality that I've mentioned. Presumably there is a reference in the literature. However you can start from the presentation that I give on pages 59-60 of these notes


At some point one obtains many $h_1, h_2, \dots, h_d$ for which $\Vert \theta h_1,\dots, h_d \Vert$ is small. At this point it is standard to invoke the divisor function estimate to show that there are in fact many $n$ for which $\Vert \theta n \Vert$ is small. However in doing this one loses an $N^{\epsilon}$ (it's worse than $\log^C N$ - are you sure you've quoted Gowers accurately?). To avoid losing it, let $S$ be the set of all $h_1\dots h_d$ mentioned above. Then $\Vert \theta (s_1 + s_2 + \dots + s_m) \Vert$ is small for all choices of $s_1,\dots, s_m \in S$, and one can argue* that for big enough $m$ this set of sums of $S$ is really big (i.e. there is no loss of $N^{\epsilon}$.)

*The key point is that for large enough $m$, the number of representations of any $n \in [X^d, 2X^d]$ as a sum of $m$ things of the form $h_1 \dots h_d$, $h_i \sim X$ is bounded by $C X^{d(m-1)}$. The usual proof would have $m = 1$, where this statement is actually false. The problem is, I think I'd need to use the Hardy-Littlewood method (which uses Weyl's inequality, but only the weaker form with the $N^{\epsilon}$) to prove this statement! Little surprise that you don't find this argument in textbooks then.

Actually, I'd be very interested to see a decent reference for all this.


I made the following attempt to prove the result using Weyl's inequality, which failed. It only manages to show that $\liminf S_N/N\to0$. However, as mentioned in Benoît's answer, with a little bit more work the equidistribution theorem does follow.

The problem with the proof below is that the convergents $q_i$ can grow so fast that they jump right over the (huge) intervals in (1) below - as David mentions in the question.

The inequality you wrote is equivalent to $$ S_N/N\le100\left(\frac{(\log N)^{d(1-2^{-d})}}{q}+\frac{(\log N)^{d(1-2^{-d})}}{N}+\frac{(\log N)^{d(1-2^{-d})}q}{N^d}\right)^{1/(2^d-1)} $$ As long as it can be shown that each of the three terms inside the parentheses is less than or equal to any fixed $\epsilon>0$ for large enough N, then $S_N/N\to0$. The middle term tends to zero, so that is no problem. For the remaining two terms to be less than $\epsilon$, we need $$ \begin{array} {}\displaystyle\epsilon^{-1}(\log N)^{d(1-2^{-d})}\le q\le \epsilon N^d/(\log N)^{d(1-2^{-d})}.&&(1) \end{array} $$ For large N, this gives a big range from which to choose our q. In fact, as you increase N these intervals eventually overlap $$ \begin{array} {}\displaystyle\epsilon N^d/(\log N)^{d(1-2^{-d})}>\epsilon^{-1}(\log(N+1))^{d(1-2^{-d})}.&&(2) \end{array} $$ Choose $N_0$ large enough that, for all $N\ge N_0$, $(\log N)^{d(1-2^{-d})}/N<\epsilon$ and (2) is satisfied. Then, the union of the intervals (1) over $N\ge N_0$ covers the range $[\epsilon^{-1}(\log N_0)^{d(1-2^{-d})},\infty)$. As there exist infinitely many coprime p,q with $\vert\theta-p/q\vert\le1/q^2$, we can take $q>\epsilon^{-1}(\log N_0)^{d(1-2^{-d})}$.

Initially, I attempted to go from here to conclude that $S_N/N$ is small for $N\ge N_0$, which was the error in my first version of this answer. Instead, this argument just shows that q must lie in one of the intervals (1) for some $N\ge N_0$, in which case $S_N/N\le 100(3\epsilon)^{1/(2^d-1)}$. So, we can find large N making $S_N/N$ as small as we like, and $\liminf S_N/N\to0$.

  • $\begingroup$ But there has to be $p$, with $GCD(p,q)=1$, such that $|\theta - p/q| < 1/q^2$. How do you guarantee that for your choice of $q$'s? $\endgroup$ – David E Speyer Aug 17 '10 at 22:36
  • $\begingroup$ You can find arbitrarily large q's satisfying $\vert\theta-p/q\vert\le1/q^2$. As p/q tends to $\theta$ for large q, even after canceling to get p/q in lowest terms, there will be infinitely many distinct q's. So, certainly, you can find p/q in lowest terms with q exceeding the bound $N_0$. $\endgroup$ – George Lowther Aug 17 '10 at 22:39
  • $\begingroup$ I definitely agree that this shows lim inf S_N/N=0. $\endgroup$ – David E Speyer Aug 17 '10 at 22:54
  • $\begingroup$ ok, I edited my answer accordingly, and to refer to Benoît's answer. $\endgroup$ – George Lowther Aug 18 '10 at 11:36

This response is in answer to David's further question about whether it is possible to bound the rate at which SN/N tends to zero, as he was wanting to use Weyl's inequality to do. This is not possible, even in the case d=2 and f(n)=θn2. (for d=1 it is not hard to show that SN is bounded so $S_N/N=O(N^{-1})$). Set $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Given any function h: ℕ → ℝ+ with liminfnh(n) = 0, I show that there are irrational θ with $$ \begin{array}{}\displaystyle\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty.&&(*)\end{array} $$

[Note: The following is a much simpler argument than the original version]. I'll use the Baire category theorem to find counterexamples

For any countable collection An of open dense subsets of ℝ, the intersection A = ∩nAn is dense in ℝ.

In particular, any such A is nonempty. We can say more than this; if S is a countable subset of the reals then $A\setminus S=\left(\bigcap_nA_n\right)\cap\left(\bigcap_{s\in S}\mathbb{R}\setminus\{s\}\right)$ is an intersection of dense open sets, so is dense. In particular, A will contain a dense set of irrational values.

To construct counterexamples then, it is only necessary to show that the set of all θ at which the sequence diverges to infinity is an intersection of countably many open sets, and show that it contains a dense set of rational numbers. The Baire category theorem implies that it will also diverge at a dense set of irrationals.

In fact, for any sequence xn(θ) depending continuously on a real parameter θ, the set of values of θ for which it diverges to infinity is an intersection of countably many open sets $$ \{\theta\colon\sup_n\vert x_n(\theta)\vert=\infty\}=\bigcap_n\bigcup_m\{\theta\colon\vert x_m(\theta)\vert>n\\}. $$

So, we only need to find a dense set of rational numbers at which (*) holds.

Let θ = a/b for integers a,b with b > 0. Setting $x=S_b(\theta)/b$ then $S_N(\theta)/N\to x$ as $N\to\infty$.

Proof: If m ≡ n (mod b) then θm2 - θn2 is an integer, and $e^{2\pi i\theta m^2}=e^{2\pi i \theta n^2}$. So $n\mapsto e^{2\pi i\theta n^2}$ has period b, giving $$ S_{bN}(\theta)=\sum_{j=0}^{N-1}\sum_{k=1}^{b}e^{2\pi i\theta(jb+k)^2}=N\sum_{k=1}^be^{2\pi i\theta k^2}. $$ So, SbN(θ) = NSb(θ). Now, any N can be written as N = bM + R for some R < b. Then, $\vert S_N-MS_b\vert\le R$ and, dividing by N gives $\vert S_N/N-S_b/b\vert\to0$ as N goes to infinity.

As |SN(θ)/(h(N)N)| ∼ |x|/h(N) → ∞ whenever x is nonzero, the following shows that (*) holds whenever θ is of the form a/p for an odd prime p not dividing a. Such rationals are dense, so the existence of irrational θ for which (*) holds follows from the Baire category theorem.

Let θ = a/p for integers a,p with p an odd prime not dividing a. Then $x=S_p(\theta)/p$ is nonzero.

Proof: Note that $u=e^{2\pi i a/p}$ is a primitive p'th root of unity with minimal polynomial $X^{p-1}+X^{p-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{p-1}\}$ are linearly independent over the rationals and $$ S_p(\theta)=\sum_{k=1}^{p}u^{k^2}=1+2\sum_{k=1}^{(p-1)/2}u^{k^2} $$ is nonzero.

In fact as pointed out by David below, Sp is a Gauss sum and has size √p.

  • $\begingroup$ Interesting. I hope you can fix this. Note that, when $p$ is prime, $\sum_{k=0}^{p-1} e^{2 \pi i k^2/p}$ is a Gauss sum, and is known to have norm $\sqrt{p}$. People probably know the values of Gauss sums for composite denominators, although I don't. $\endgroup$ – David E Speyer Aug 18 '10 at 16:35
  • $\begingroup$ I tried to fix it, but it just shifted the error to the proof of (3). I'm hopeful it can still be fixed though. $\endgroup$ – George Lowther Aug 18 '10 at 16:44
  • $\begingroup$ In fact, I think (3) can be fixed by requiring that there are no solutions to $x^2+1=0$ (mod b). Then you can show that $S_b$ is not fixed by the element of the Galois group taking u to 1/u. I'm going to come back to this. $\endgroup$ – George Lowther Aug 18 '10 at 16:53
  • $\begingroup$ About Gauss sums with composite denominators: looks like they are just products of Gauss sums with prime (or prime power) denominators! I edited my answer again, and hopefully it holds together now. $\endgroup$ – George Lowther Aug 18 '10 at 17:27
  • $\begingroup$ OK, this works. Nice. I should probably ask another question at some point... $\endgroup$ – David E Speyer Aug 18 '10 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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