# The Rook Conjecture: arrangement of $p$ primes being distinct $\pmod{p}$ through $p^2$

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.

Examples

$$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}$$

etc.

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.

• Check 'Bertrand's Postulate'. – SL_MathGuy Jan 21 at 22:56
• Did you also check it for the positive integers in the range $[2,1000]$ ? – Peter Jan 21 at 22:56
• @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$ – Peter Jan 21 at 23:00
• @Peter If I understand you, that's not directly applicable, since you could only hit every value $\bmod n$ when $n$ is prime. – Trevor Jan 21 at 23:05
• 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. – 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.)