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!

  • $\begingroup$ I do expect a counterexample. I only think that such counterexamples are very rare. Thank you! $\endgroup$ – Alex May 8 '17 at 20:06
  • $\begingroup$ 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... $\endgroup$ – reuns May 8 '17 at 20:13
  • $\begingroup$ Is that $\log \log p' $ or $(\log p')^2 $? $\endgroup$ – daniel May 15 '17 at 15:47
  • $\begingroup$ That's $(\log p')^2$. $\endgroup$ – Alex May 15 '17 at 16:42
  • $\begingroup$ 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)$) $\endgroup$ – 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$$

  • $\begingroup$ This only answers question 1. No counterexamples answering questions 2, 3 thus far. $\endgroup$ – Alex Oct 11 '17 at 10:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.