Primes arising from permutations

Question

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.

Answer 1

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