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 following paragraph appears in Analytic Number Theory (Iwaniec, Kowalski):

The Siegel-Walfisz theorem asserts that:

$\displaystyle \hspace{5cm} \psi(x;q,a) = \frac{x}{\phi(q)} + O(x(\log x)^{-A})$

for any $q\geq 1, (a,q)=1, x\geq 2$ and $A\geq 0$. Notice that this estimate is non-trivial only if $q \ll (\log x)^A$.

The last sentence is somewhat clear to me intuitively, and ought to answer my question. But I am not quite sure what Vinogradov's '$\ll$' notation is taken to mean in this context, as $q$ is not even a function of $x$. Can anyone clarify this?

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

The $\ll$ in this context means that there is some constant $C > 0$ such that $q \leq C (\log{x})^A$. If $q$ goes to infinity (with $x$) much faster than this then the main term itself can be bounded by the error term (in which case the result would be "trivial").

share|cite|improve this answer
OK, I understand this a little better. But your sentence "If $q$ goes to infinity (with $x$)" seems to imply that we tend to work with $q$ that changes with $x$. Is this the case? Because if $q$ is constant, surely $q \leq C(\log x)^A$ is <i>always</i> going to be true for some $C>0$. – Fahad Sperinck Jan 16 '11 at 14:12
Right, people are often most interested in how big $q$ can be allowed to be compared to $x$. If $q$ is completely fixed then everything is on the same level of difficulty as the prime number theorem. – Matt Young Jan 16 '11 at 18:42
Fahad, the first application of this theorem is Vinogradov's proof that large odd numbers have (many) representations as a sum of three primes. The proof uses the circle method which makes it necessary to understand the behavior of exponential sums around rational numbers with small denominators $q$ (compared to the $N$ you want to represent). This is directly related to the distribution of primes in all arithmetic progressions modulo $q$, where $q$ can be as large as $(\log N)^A$. Rumor(?) says that Vinogradov had the argument 10 years before Siegel-Walfisz, but waited until it appeared! – GH from MO Jan 16 '11 at 18:59

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.