Group of permutations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:26:14Z http://mathoverflow.net/feeds/question/117232 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117232/group-of-permutations Group of permutations Dean Young 2012-12-26T07:24:10Z 2012-12-26T20:40:23Z <p>Which $S_n$ have an element $\sigma$ such that $\sigma (i) + i$ is always a perfect square?</p> http://mathoverflow.net/questions/117232/group-of-permutations/117234#117234 Answer by Robert Israel for Group of permutations Robert Israel 2012-12-26T08:18:30Z 2012-12-26T20:40:23Z <p>It seems to be true for $n=3,5,8,9,10$ and then all integers $n$ from $12$ to at least $100$.</p> <p>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$.<br> 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$.</p> <p>Here are suitable permutations for all $n$ up to $26$ for which such permutations exist:</p> <p><code>\eqalign{ 3 &amp; [3, 2, 1] \cr 5 &amp; [3, 2, 1, 5, 4] \cr 8 &amp; [8, 7, 6, 5, 4, 3, 2, 1] \cr 9 &amp; [8, 2, 6, 5, 4, 3, 9, 1, 7] \cr 10 &amp; [3, 2, 1, 5, 4, 10, 9, 8, 7, 6] \cr 12 &amp; [3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4] \cr 13 &amp; [8, 2, 13, 12, 11, 10, 9, 1, 7, 6, 5, 4, 3] \cr 14 &amp; [3, 2, 1, 5, 4, 10, 9, 8, 7, 6, 14, 13, 12, 11] \cr 15 &amp; [8, 2, 6, 5, 4, 3, 9, 1, 7, 15, 14, 13, 12, 11, 10] \cr 16 &amp; [15, 7, 1, 5, 4, 3, 2, 8, 16, 6, 14, 13, 12, 11, 10, 9] \cr 17 &amp; [15, 7, 1, 5, 4, 3, 2, 17, 16, 6, 14, 13, 12, 11, 10, 9, 8] \cr 18 &amp; [15, 14, 13, 12, 11, 10, 18, 17, 16, 6, 5, 4, 3, 2, 1, 9, 8, 7] \cr 19 &amp; [3, 2, 1, 5, 4, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6] \cr 20 &amp; [15, 14, 13, 12, 20, 19, 2, 1, 7, 6, 5, 4, 3, 11, 10, 9, 8, 18, 17, 16] \cr 21 &amp; [15, 14, 1, 12, 20, 10, 2, 8, 7, 6, 5, 13, 3, 11, 21, 9, 19, 18, 17, 16, 4] \cr 22 &amp; [3, 2, 22, 21, 4, 19, 9, 1, 7, 6, 5, 13, 12, 11, 10, 20, 8, 18, 17, 16, 15, 14] \cr 23 &amp; [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 &amp; [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 &amp; [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 &amp; [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 }</code></p> <p>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 <code>$B = \{b: 1 \le b \le n,\ a + b \text{ is a square for some }a \in A\}$</code> has cardinality less than that of $A$.</p> <p><code>$$\begin{array}{c l l} n &amp; A &amp; B\cr 2 &amp; \{1\} &amp; \emptyset \cr 4 &amp; \{4\} &amp; \emptyset \cr 6 &amp; \{1,6\} &amp; \{3\} \cr 7 &amp; \{1,6\} &amp; \{3\} \cr 11 &amp; \{4,11\} &amp; \{5\} \cr \end{array}$$</code></p>