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?


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").

  • $\begingroup$ 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$. $\endgroup$ – Sputnik Jan 16 '11 at 14:12
  • $\begingroup$ 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. $\endgroup$ – Matt Young Jan 16 '11 at 18:42
  • 1
    $\begingroup$ 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! $\endgroup$ – GH from MO Jan 16 '11 at 18:59

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.