# 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. Nov 14, 2018 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}$ . Nov 14, 2018 at 23:13
• Maybe you can also try to prove that $a(2l+1)$ for non negative integer $l$ is a square. Nov 14, 2018 at 23:17
• Maybe squares of terms of oeis.org/… Nov 14, 2018 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. Nov 15, 2018 at 9:44

## 1 Answer

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!

(Even with a very strong result on least primes in progressions the above comment says nothing towards the existence of the permutation).

• (I am very sorry, I was reading this on my very old smartphone, which decided that I should downvote. I wanted to upvote, but stackexchange says I cannot, unless the question is edited) Nov 14, 2018 at 14:02
• @Martin, I have made a (trivial) edit, so you should be able to retract your downvote. Christian, I will not be offended if you revert my edit. Nov 14, 2018 at 22:06