# Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $$n$$ there is a permutation $$\pi_n$$ of $$\{1,\ldots,n\}$$ such that $$k+\pi_n(k)$$ is prime for every $$k=1,\ldots,n$$ (cf. http://arxiv.org/abs/1809.01012). Motivated by this, here I pose the following question.

QUESTION: Is my following conjecture true?

Conjecture. (i) For any positive integer $$n$$, there is a permutation $$\sigma_n$$ of $$\{1,\ldots,n\}$$ such that $$k\sigma_n(k)+1$$ is prime for every $$k=1,\ldots,n$$.

(ii) For any integer $$n>2$$, there is a permutation $$\tau_n$$ of $$\{1,\ldots,n\}$$ such that $$k\tau_n(k)-1$$ is prime for every $$k=1,\ldots,n$$.

I have checked the conjecture for $$n$$ up to $$11$$. For example, $$(1, 3, 2, 9, 6, 5, 10, 11, 4, 7, 8)$$ is a permutation of $$\{1,\ldots,11\}$$ with $$\begin{gather}1\times1+1,\ 3\times2+1,\ 2\times3+1,\ 9\times4+1,\ 6\times5+1, \ 5\times 6+1, \\10\times 7+1,\ 11\times8+1,\ 4\times9+1,\ 7\times10+1,\ 8\times11+1 \end{gather}$$ all prime, and $$(3, 2, 1, 5, 4, 7, 6, 9, 8, 11, 10)$$ is a permutation of $$\{1,\ldots,11\}$$ with $$\begin{gather}3\times1-1,\ 2\times2-1,\ 1\times3-1,\ 5\times4-1,\ 4\times5-1, \ 7\times 6-1, \\6\times 7-1,\ 9\times8-1,\ 8\times9-1,\ 11\times10-1,\ 10\times11-1 \end{gather}$$ all prime.

Remark. I also conjecture that for any integer $$n>2$$ there is a permutation $$\pi_n$$ of $$\{1,\ldots,n\}$$ such that the $$2n$$ numbers $$k+\pi_n(k)\pm1\ (k=1,\ldots,n)$$ are all prime. This is stronger than the twin prime conjecture.

• Let $a(n)$ be the number of permutations $\sigma_n$ of $\{1,\ldots,n\}$ such that $k\sigma_n(k)+1$ is prime for every $k=1,\ldots,n$. Then the values of $a(1),\ldots,a(11)$ are $1, \,2,\, 1,\, 6,\, 1,\, 24,\, 9,\, 38,\, 36, \,702, \,196$ respectively. See oeis.org/A321597. – Zhi-Wei Sun Nov 14 '18 at 16:47
• Your second conjecture boils down to saying there is a prime $q_{n,k}$ such that $\tau(k)$ is the inverse of $k$ in $\mathbb{Z}/q_{n,k}\mathbb{Z}$ . – Sylvain JULIEN Nov 14 '18 at 23:13
• Maybe you can also try to prove that $a(2l+1)$ for non negative integer $l$ is a square. – Sylvain JULIEN Nov 14 '18 at 23:17
• Maybe squares of terms of oeis.org/… – Sylvain JULIEN Nov 14 '18 at 23:22
• Letting $a(2n+1)=b(n)^2$, the following Pari/GP code works well: b(n)=matpermanent(matrix(n,n,i,j,isprime(2*i*(2*j+1)+1))); it computes $b(n)$ for all $n<30$ in less than 8 minutes on my machine. – François Brunault Nov 15 '18 at 9:44

Let us look at one "difficult" sub-case, which completely avoids the permutation issue. With $$k=n$$ it is required that there exists some small $$x \leq n$$, such that $$nx+1$$ is prime. Therefore this necessary condition is related to Linnik's theorem. https://en.wikipedia.org/wiki/Linnik%27s_theorem
By Linnik's theorem it is known that $$nx+1 \ll n^5$$ exists. (The constant 5 was proved by Xylouris, (PhD Thesis, Bonn, 2011) \"{U}ber die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression. https://bib.math.uni-bonn.de/downloads/bms/BMS-404.pdf )
Let $$p(a,n)$$ denote the least prime in the arithmetic progression $$a+nx$$. It is known that on GRH one has $$p(a,n)\leq \varphi(n)^2 (\log n)^2$$, which is just a bit larger than $$n^2$$. ($$\varphi$$ denotes Euler's totient function.)
In view of this, it seems, one would need to make considerable progress on the difficult topic "least prime in arithmetic progression", at least in the special case of the residue class $$1 \bmod n$$. As I am not aware that for $$1\bmod n$$ significantly better results are known than in the general case, I would assume that even assuming GRH we do not quite get the necessary condition $$x \leq n$$, for this one prime!