The prime number theorem tells us that , if $\pi\left(x\right)$ denotes the number of primes less than or equal to $x$, we have $$\pi\left(x\right)\sim\frac{x}{\log x}.$$ In a similar manner considered $1\leq a \leq q$ with $(a,q)=1$ and defined $\pi\left(x,a,q\right)$ the number of primes less than or equal to $x$ congruous $a\,\textrm{mod}\, q$ and $\phi\left(n\right)$ the number of minor numbers and coprime with $n$, we have $$\pi(x,a,q)\thicksim\frac{1}{\phi(q)}\frac{x}{\log x}.$$ If $q$ is "small" you have asymptotic formulas for $\pi\left(x,a,q\right)$ (see the Siegel - Walfisz theorem). For any $q$ we have the estimate $$\pi(x,a,q)\gg\frac{1}{\phi(q)}\frac{x}{\log x}.$$ I would like to know if there is an estimate of the type $$\pi(x,a,q)\ll\frac{1}{\phi(q)}\frac{x}{\log x}$$ for any $q$. I hope I was clear! Sorry for my bad english!

  • 2
    $\begingroup$ It is a consequence of Dirichlet's theorem on arithmetic progressions. $\endgroup$
    – Alvin
    Oct 21, 2013 at 12:23
  • 4
    $\begingroup$ Look up "Brun-Tithcmarsch inequality". $\endgroup$ Oct 21, 2013 at 13:39
  • 5
    $\begingroup$ It is not true that we know the lower bound $\pi(x;q,a) \gg \frac1{\phi(q)}\frac x{\log x}$ for all ranges of $q$ and $x$. (By the way, the notation $\pi(x;q,a)$ is more standard than $\pi(x,a,q)$.) $\endgroup$ Oct 21, 2013 at 19:55
  • 2
    $\begingroup$ For fixed $q$, yes, this follows from the asymptotic formula. But if $q$ can grow with $x$, then we don't know this lower bound in all ranges. $\endgroup$ Oct 22, 2013 at 9:58
  • 1
    $\begingroup$ @The_Cam: Greg Martin is right. If we knew the bound $\pi(x;q,a) \gg \frac1{\phi(q)}\frac x{\log x}$, then for any $\epsilon>0$ we would know that $\pi(x;q,a)>0$ for some $x\ll_\epsilon q^{1+\epsilon}$. However, this consequence is only known for $x\ll q^{5.2}$ at the moment, see en.wikipedia.org/wiki/Linnik%27s_theorem $\endgroup$
    – GH from MO
    Oct 22, 2013 at 17:04

2 Answers 2


For $x\leq\phi(q)$ the estimate $\pi(x,a,q)\ll\frac{1}{\phi(q)}\frac{x}{\log x}$ would imply $\pi(x,a,q)\ll\frac{1}{\log x}$, i.e. $\pi(x,a,q)=0$ for large $x$ which is clearly false. So a bound you envision can only hold for $x$ slightly above $\phi(q)$. On the other hand, for any $\epsilon>0$, the Brun-Titchmarsh inequality implies $$\pi(x,a,q)\ll_\epsilon\frac{1}{\phi(q)}\frac{x}{\log x},\qquad x>q^{1+\epsilon}.$$

  • $\begingroup$ $(3.3)$ in Andrew Granville paper in my comment implies when $q$ is small(perhaps $x>q^{1+\epsilon}$ can satisfies) $$\pi(x,q;a)\sim \frac{x-x^\beta}{\varphi(q)\log x}\ge (1-\epsilon) \frac{x}{\varphi(q)\log x}$$ where $\beta$ is real zero of $L(s,\chi) $ that is close to $1 $ with the assumption $\chi(a)=1 $ which can be omitted. $\endgroup$
    – H.Flip
    Oct 23, 2013 at 2:03
  • $\begingroup$ @Houfei: The problem is that $\beta$ is not fixed, but depends on $q$, so the lower bound you state is much harder to achieve. Linnik managed to do this for $x>q^L$ and $L$ large (the Linnik constant), and research since has focused on lowering the value of $L$. Currently we have $L=5.2$, while the Generalized Density Hypothesis (a consequence of GRH) would allow any $L>2$. $\endgroup$
    – GH from MO
    Oct 23, 2013 at 7:47

Siegel - Walfisz theorem states $$\psi(x,q;a)=x/\phi(q)+O(x/\log^Ax)$$when q is small;q is big ,the results is trival . (When is the Siegel-Walfisz theorem non-trivial?)

if $q \ll log^Ax$,we have $$\sum_{x\equiv 1 \bmod q } \Lambda(n)\ge (1-\epsilon) x/\varphi(q).$$

(Prime numbers in arithmetic progressions : uniformity with respect to the modulus )

I think q is big, there is no the $\ll$ results as you asked. Since when q is big ,there may be existing Siegel-zeros, then there exist constants 0 < β−, β+ < 1 such that $x^{\beta_{-}}/\beta_{-}\ll x-\phi(q)\pi(x,q;a) \log x \ll x^{\beta}_{+}/ \beta _{+}$. (see section 3 , and http://www.dms.umontreal.ca/~andrew/PDF/ItalySurvey.pdf) or see Theorem (Siegel-Walfisz with a twist). in (Chebyshev function in arithmetic progressions)


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.