7
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\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, 2018 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, 2018 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, 2018 at 23:17
  • $\begingroup$ Maybe squares of terms of oeis.org/… $\endgroup$
    – Sylvain JULIEN
    Nov 14, 2018 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, 2018 at 9:44

1 Answer 1

Reset to default
11
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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