For any prime $p$, divide $[1,p^2]$ into $p$ equal intervals of length $p$, so that the first interval is $[1,p]$, the next $[p+1,2p]$, and so on. It is definitely unproven but seems likely that there will always be a prime in every one of these intervals. It is even probably true when you substitute any natural $n$ in place of the prime $p$ above.

I've noticed a stricter condition that seems to hold. If you divide $p^2$ as described above, not only will there be a prime in every interval of length $p$, but there will always be at least one way to select those primes such that no value is repeated $\bmod{p}$.

A good name for this might be the Rook Conjecture, as this is equivalent to saying that if you number the squares of a $p\times p$ sized chessboard, there is always at least one way to place $p$ rooks on prime-numbered squares yet have no rooks share a rank or file.


$p=3,\qquad S=\{3,5,7\}\equiv\{0,2,1\} \pmod{3}$ $p=5,\qquad S=\{5,7,11,19,23\}\equiv\{0,2,1,4,3\} \pmod{5}$


I've verified this for $p\leq 1000$. As usual, I am curious whether this is a known result and/or where to look for related work, and of course any counterexamples should they exist. I'm also curious whether this result seems to others to be surprising, or expected; I'm having a hard time deciding the answer for myself.

  • 2
    $\begingroup$ Check 'Bertrand's Postulate'. $\endgroup$ – SL_MathGuy Jan 21 at 22:56
  • $\begingroup$ Did you also check it for the positive integers in the range $[2,1000]$ ? $\endgroup$ – Peter Jan 21 at 22:56
  • 1
    $\begingroup$ @SL_MathGuy This is not enough, but maybe Opperman's conjecture implies it which states that $g_n\le \sqrt{p_n}$ for sufficiently large $n$ $\endgroup$ – Peter Jan 21 at 23:00
  • $\begingroup$ @Peter If I understand you, that's not directly applicable, since you could only hit every value $\bmod n$ when $n$ is prime. $\endgroup$ – Trevor Jan 21 at 23:05
  • 1
    $\begingroup$ It seems unlikely that you'll find any counterexamples if you haven't found any up to $1000$. On the random model of the primes, the expected number of $p$-tuples covering the remainders in this way is about $\frac{p!}{\log^pp}$, which grows quite quickly. If there were systematic effects preventing these tuples, they should have shown up in your data. $\endgroup$ – joriki Jan 22 at 1:35

The GRH neither implies that there is a prime in $[p^2-p,p^2]$ nor that the least prime $\equiv a\bmod p$ is $\le p^2$. Thus your conjecture is very strong and there is no fear to use the random model for the primes.

You are saying that for some permutation $\sigma$ of $[1,p-1]$, all the $np+\sigma(n),n\in [1,p-1]$ are primes.

The probability that they are all primes is $$\approx\prod_{n=1}^{p-1}\frac1{\log( np+\sigma(n))} \approx \frac{C}{\log^{p-1} p}$$ the probability that no permutation works is $$\approx (1-\frac{C}{\log^{p-1} p})^{(p-1)!}\approx \exp(- \frac{C (p-1)!}{\log^{p-1-\epsilon} p}) $$

The probability that no permutation works for some $p\ge k$ is $$f(k)\le \sum_{p\ge k}\exp(- \frac{C (p-1)!}{\log^{p-1-\epsilon} p})$$ Since the series converges and $$\lim_{k\to \infty} f(k)=0$$ then the random model predicts that your conjecture holds for $p$ large enough.

(Why did I use the $\approx$ symbol ? Because the random model is case specific : we can and we should take in account the "congruences constraints" before assuming all the implied random variables are independent, which is what we need to simplify everything. Here I don't have any good argument for why this computation does take in account the relevant congruence constraints.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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