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$– AlvinCommented Oct 21, 2013 at 12:23
-
5$\begingroup$ Look up "Brun-Tithcmarsch inequality". $\endgroup$– Dimitris KoukoulopoulosCommented 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$– Greg MartinCommented 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$– Greg MartinCommented 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 MOCommented Oct 22, 2013 at 17:04
2 Answers
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.FlipCommented 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$ Commented 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)
