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

For my work, i need the following Conjecture: Let $N$ large number such that exist a prime number $q$ and $A>\frac{1}{2}$ such that $N^{1/2}<N^{A}\leq q-1<N.$ Then $\forall a\in\left[1,\, q\right)$ $$\frac{1}{\phi\left(q\right)}\frac{N}{\log N}\ll\pi\left(N;\, q,\, a\right)\ll\frac{1}{\phi\left(q\right)}\frac{N}{\log N}.$$ Is it wrong or in part demonstrated? Thank you!

share|improve this question
I am not completely sure I understand what you are asking. As I understand it this can hardly work as if q is almost N then the right hand side will tend to 0 but of course there still will be some prime in some classes. –  quid Nov 7 '13 at 21:43
As quid said, the statement is false for $q$ very close to $N$, say for $q>N/\sqrt{\log N}$ and $a=2$ and $N$ large. –  GH from MO Nov 8 '13 at 7:03
For my purposes, is important that $N^{1/2}<q-1$. @GHfromMO if I change in $N^{1/2}<q-1<N/\sqrt{\log N}$, is the conjecture admissible? –  user42503 Nov 8 '13 at 8:41
The lower bound is not even known under GRH. The upper bound is known for $q<N^{0.999}$, say, and $N$ large. This follows from the Brun-Titchmarsh inequality. I don't know from the top of my head what is known or expected to be true for $q$ very close to $N$. –  GH from MO Nov 8 '13 at 9:27
We expect that if $N\gg q(\log q)^2$, then there is a prime $p\equiv a\pmod{q}$ with $p\le N$. (This was conjectured by Heath-Brown; see here dms.umontreal.ca/%7Eandrew/PDF/laval.pdf and the references there). On the other hand, it has been proven that if $N\le (\log q)^{2-\epsilon}$, then there might be AP's which have no prime $p\equiv a\pmod q$ with $p\le N$. (See here dms.umontreal.ca/%7Eandrew/PDF/LeastPrimeAP.pdf.) Limitations to such problems can be understood using Cramer's model and its variations. –  Dimitris Koukoulopoulos Nov 8 '13 at 14:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.