Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
It is a consequence of Dirichlet's theorem on arithmetic progressions. –  Alvin Oct 21 '13 at 12:23
Look up "Brun-Tithcmarsch inequality". –  Dimitris Koukoulopoulos Oct 21 '13 at 13:39
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)$.) –  Greg Martin Oct 21 '13 at 19:55
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. –  Greg Martin Oct 22 '13 at 9:58
@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 –  GH from MO Oct 22 '13 at 17:04

2 Answers 2

up vote 10 down vote accepted

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}.$$

share|improve this answer
$(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. –  Houfei Oct 23 '13 at 2:03
@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$. –  GH from MO Oct 23 '13 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 (Chebychev Function in Arithmetic Progressions )

share|improve this answer

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.