Primes in arithmetic progression $a \pmod q$

Question

Can we prove the "Bertrand postulate" for primes $a \pmod q$, namely: there is always a prime number $p\equiv a \pmod q$ betwen $nq$ and $nq^2$ for every $n>0$ and $(a,q)=1$. (This would mean that between $nq$ and $nq^2$ there are always at least $\varphi(q)$ primes, each belonging to a different residue class modulo $q$.)

Answer 1

This question appears to have been addressed by P. Moree in this paper. In the notation of that paper, he defines

$$\displaystyle B_m(z,d) = \liminf \{c : \forall x \geq c, (x,zx) \text{ contains at least } m \text{ primes} $$ $$\displaystyle \text{ congruent to } a \pmod{d} \text{ for all } \gcd(a,d) = 1\}.$$

In particular, he proves that provided the quantity $\sigma(d)$ defined to be

$$\displaystyle \sigma(d) = \sum_{\substack{p \leq d \\ p \nmid d}} \frac{1}{p}$$

is strictly less than one, then one can obtain an explicit estimate for $B_m(z,d)$ whenever

$$\displaystyle z > \frac{d}{(d-1)(1 - \sigma(d))}.$$

His methods generalize an elementary argument of Erdos (who gave an elementary proof of the original Bertrand's postulate), and so do not run into the problems that one encounters when attempting to use the known analytic theorems to attack the problem (i.e., possible existence of Siegel zeroes, etc.). Unfortunately, by Mertens' theorem the hypothesis that $\sigma(d) < 1$ is extremely strict: indeed, Moree shows that $\sigma(d) < 1$ implies that $d \leq 840$.

In principle, one can approach the problem by obtaining a reasonably explicit lower bound for the number of primes in an arithmetic progression, up to some bound $x$. For each pair $(a,q)$ with $\gcd(a,q) = 1$ define $N(a,q)$ to be a positive number with the property that whenever $x > N(a,q)$ we have

$$\pi(x; a,q) > \frac{2x}{3 \phi(q) \log x},$$

say. Then for $q \geq 2$ and $nq > N(a,q)$ there will always be a prime congruent to $a \pmod{q}$ in the interval $(nq, nq^2)$, since by the Brun-Titchmarsh theorem we have

$$\displaystyle \pi(x; a,q) \leq \frac{2x}{\phi(q) \log (x/q)}$$

for all $x \geq q \geq 2$. In particular,

$$\displaystyle \pi(nq^2; a, q) - \pi(nq; a, q) > \frac{2nq^2}{3\phi(q) \log(nq^2)} - \frac{2nq}{\phi(q) \log(n)}$$ $$ = \frac{2nq}{3\phi(q)} \left(\frac{(2q -3) \log n - 6 \log q}{\log n(\log n + \log q^2)} \right)$$

which is positive. Calculating $N(a,q)$ however seems to be a very hard problem.

Answer 2

Given a fixed $a$ and $q$, this should be true for sufficiently large $n$ by the explicit versions of Dirichlet's theorem on arithmetic progressions. We cannot prove that this is true for every $n$. The best we have is variants of Linnick's theorem, which just tells us that there are constant $L$ and , such that for any such $q$ and $a$, there is a prime $p$ with $p \equiv a$ (mod $q$), and $p < cq^L$. The best known such constant for $L$ currently is a little larger than 5. Your claim is much stronger; even if one has $n=1$ fixed, you would be asking us to prove $L=2$, $c=1$ and want also that one can find such a $p$ where $p$ also obeys the lower bound $p > q$. Your claim if I understand it is an interesting one, and is strong enough that we're nowhere near proving it if it is true. I'm not sure I'd conjecture either way whether your claim is true or not. If it is false, I suspect that counterexamples can be found with small amounts of computation.