Group of permutations

Question

Which $S_n$ have an element $\sigma$ such that $\sigma (i) + i$ is always a perfect square?

Answer 1

It seems to be true for $n=3,5,8,9,10$ and then all integers $n$ from $12$ to at least $100$.

EDIT: Yes, this is true. Let $k^2$ be a square greater than $n$ but less than $2n$. Take $\sigma(j) = k^2 - j$ for $j$ from $k^2 - n$ to $n$. Thus $(\sigma(k^2-n), \ldots, \sigma(n))$ are a permutation of $(k^2-n, \ldots, n)$. This reduces the problem for $n$ to the problem for $k^2 - n - 1$.
Now for all integers $n \ge 27$ there is such a $k$ with $k^2 - n - 1 \ge 12$ (because $\sqrt{2n} - \sqrt{n+13} \ge 1$), so once we find such a permutation for all $n$ from $12$ to $26$ we know that there is one for all $n \ge 27$.

Here are suitable permutations for all $n$ up to $26$ for which such permutations exist:

$$ \eqalign{ 3 & [3, 2, 1] \cr 5 & [3, 2, 1, 5, 4] \cr 8 & [8, 7, 6, 5, 4, 3, 2, 1] \cr 9 & [8, 2, 6, 5, 4, 3, 9, 1, 7] \cr 10 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6] \cr 12 & [3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4] \cr 13 & [8, 2, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3] \cr 14 & [3, 2, 1, 5, 4, 10, 9, 8, 7, 6, 14, 13, 12, 11] \cr 15 & [8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10] \cr 16 & [15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9] \cr 17 & [15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8] \cr 18 & [15, 14, 13, 12, 11, 10, 18, 17, 16, 6, 5, 4, 3, 2, 1, 9, 8, 7] \cr 19 & [3, 2, 1, 5, 4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6] \cr 20 & [15, 14, 13, 12, 20, 19, 2, 1, 7, 6, 5, 4, 3, 11, 10, 9, 8, 18, 17, 16] \cr 21 & [15, 14, 1, 12, 20, 10, 2, 8, 7, 6, 5, 13, 3, 11, 21, 9, 19, 18, 17, 16, 4] \cr 22 & [3, 2, 22, 21, 4, 19, 9, 1, 7, 6, 5, 13, 12, 11, 10, 20, 8, 18, 17, 16, 15, 14] \cr 23 & [15, 23, 22, 21, 20, 19, 18, 1, 16, 6, 14, 13, 12, 11, 10, 9, 8, 7, 17, 5, 4, 3, 2] \cr 24 & [8, 2, 22, 5, 4, 10, 9, 1, 7, 6, 14, 24, 23, 11, 21, 20, 19, 18, 17, 16, 15, 3, 13, 12] \cr 25 & [8, 23, 22, 21, 4, 3, 9, 1, 7, 6, 5, 24, 12, 2, 10, 20, 19, 18, 17, 16, 15, 14, 13, 25, 11] \cr 26 & [15, 14, 22, 21, 20, 19, 18, 17, 16, 26, 25, 24, 23, 2, 1, 9, 8, 7, 6, 5, 4, 3, 13, 12, 11, 10] \cr }$$

EDIT: For completeness, to show that there are no solutions for $n=2,4,6,7,11$, in each of those cases we find a set $A$ such that the set $B = \{b: 1 \le b \le n,\ a + b \text{ is a square for some }a \in A\}$ has cardinality less than that of $A$.

$$ \begin{array}{c l l} n & A & B\cr 2 & \{1\} & \emptyset \cr 4 & \{4\} & \emptyset \cr 6 & \{1,6\} & \{3\} \cr 7 & \{1,6\} & \{3\} \cr 11 & \{4,11\} & \{5\} \cr \end{array} $$