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.

  • $\begingroup$ 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. $\endgroup$ – Zhi-Wei Sun Nov 14 '18 at 16:47
  • $\begingroup$ 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} $ . $\endgroup$ – Sylvain JULIEN Nov 14 '18 at 23:13
  • 1
    $\begingroup$ Maybe you can also try to prove that $ a(2l+1) $ for non negative integer $ l $ is a square. $\endgroup$ – Sylvain JULIEN Nov 14 '18 at 23:17
  • $\begingroup$ Maybe squares of terms of oeis.org/… $\endgroup$ – Sylvain JULIEN Nov 14 '18 at 23:22
  • $\begingroup$ 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. $\endgroup$ – 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!

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

  • $\begingroup$ (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) $\endgroup$ – Martin Rubey Nov 14 '18 at 14:02
  • $\begingroup$ @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. $\endgroup$ – Gerry Myerson Nov 14 '18 at 22:06

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.