# Analog of Cramer's conjecture for primes in a residue class

Let $q$ and $r$ be fixed coprime positive integers, $$1 \le r < q, \qquad \gcd(q,r)=1.$$ Suppose that two prime numbers $p$ and $p'$, with $p<p'$, satisfy $$p \equiv p' \equiv r \ ({\rm mod}\ q), \tag{1}$$ and no other primes between $p$ and $p'$ satisfy $(1)$. Then we have the following

Naive generalization of Cramer's conjecture to primes in residue class $r$ mod $q$: $$p'-p ~<~ \varphi(q)\,(\ln p')^2. \tag{2}$$

(PrimePuzzles Conjecture 77, A. Kourbatov, 2016). See arXiv:1610.03340, "On the distribution of maximal gaps between primes in residue classes" for further details, including the motivation for the $\varphi(q)$ constant. Here, as usual, $\varphi(q)$ denotes Euler's totient function.

Note: In the inequality $(2)$ we take the logarithm of the prime $p'$ at the larger end of the "gap". Very few counterexamples to $(2)$ are known; see Appendix 7.4 in arXiv:1610.03340. Definitely no counterexamples for $q=2, \ p<4\cdot10^{18}$; also none for $1\le r < q \le 1000$, $\ p<10^{10}$.

This conjecture (mostly in a less-naive "almost always" form) is mentioned in the following OEIS sequences listing maximal (record) gaps between primes of the form $p=qk+r$, $\ \gcd(q,r)=1$: A084162, A268799, A268925, A268928, A268984, A269234, A269238, A269261, A269420, A269424, A269513, A269519.

Question 1: Find a counterexample to conjecture $(2)$.

Question 2: Find a counterexample to $(2)$, with prime $q$ and prime $r$.

Question 3: Find a counterexample to $(2)$, with $${p'-p \over \varphi(q)(\ln p')^2} > 1.1 \tag{3}$$ (A.Granville predicts that such counterexamples exist even for $q=2$, with the above ratio greater than $1.12$ -- more precisely, Granville expects that the ratio should exceed or come close to $2e^{-\gamma}$).

Hint: Counterexamples are very rare. To find one, you will likely need to write a program and run it long enough. Good luck!

• I do expect a counterexample. I only think that such counterexamples are very rare. Thank you! – Alex May 8 '17 at 20:06
• No you don't except someone will find a counter-example if you already made some programs. That's why you need to make it clear... – reuns May 8 '17 at 20:13
• Is that $\log \log p'$ or $(\log p')^2$? – daniel May 15 '17 at 15:47
• That's $(\log p')^2$. – Alex May 15 '17 at 16:42
• Did you try discussing the random models underlying those things ? (in particular what is Maier's heuristic under which $\log^2(p)$ should be replaced by $\log^{2+\epsilon}(p)$) – reuns Nov 14 '17 at 15:13

Take $q=1605$, $r=341$, and consider the primes $p=3415781$ and $p'=3624431$.
It is not difficult to check that $$p \equiv p' \equiv 341 \ ({\rm mod} \ 1605), \tag{1}$$ and between $p$ and $p'$ there are no other primes satisfying $(1)$. We have $\varphi(1605)=848$, and the exceptionally large gap is $$3624431 - 3415781 = 208650 > \varphi(q) (\log3624431)^2 = 193434.64\ldots$$