MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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. – user9072 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 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 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.