# Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ an odd square

For any positive integer $$n$$, as usual we let $$S_n$$ be the symmetric group of all the permutations of $$\{1,\ldots,n\}$$.

QUESTION: Is it true that for each integer $$n>3$$ there is an odd permutation $$\tau\in S_n$$ such that $$\sum_{k=1}^n k\tau(k)$$ is an odd square?

Let $$a(n)$$ denote the number of odd permutations $$\tau\in S_n$$ with $$\sum_{k=1}^nk\tau(k)$$ an odd square. Via a computer I find that $$(a(1),\ldots,a(11))=(0,0,0,2,4,10,42,436,2055,26454,263040).$$ For example, $$(2,4,1,3)$$ and $$(3,1,4,2)$$ are the only two odd permutations in $$S_4$$ meeting our requirement; in fact, $$1\cdot2+2\cdot4+3\cdot1+4\cdot3=5^2\ \ \text{and}\ \ 1\cdot3+2\cdot1+3\cdot4+4\cdot2=5^2.$$ For $$n=2,3,4,5$$, there is no even permutation $$\tau\in S_n$$ such that $$\sum_{k=1}^nk\tau(k)$$ is a square.

I conjecture that the question has a positive answer. Any comments are welcome!

## 1 Answer

I assume you have checked this for small $$n$$, so I will only consider large $$n$$. I will show: if $$n \geq 14$$, then there exists a product $$\sigma = (i_1 j_1) (i_2 j_2) \dots (i_5 j_5)$$ of five transpositions with disjoint supports such that $$\sum_{k = 1}^n k \sigma(k)$$ is an odd square.

For a $$\sigma$$ such as above, we have $$\sum_{k = 1}^n k \sigma(k) = \frac{n(n+1)(2n+1)}{6} - \sum_{r=1}^5 (j_r-i_r)^2.$$ Let us write $$\frac{n(n+1)(2n+1)}{6} -34 = (2h-1)^2+ s,$$ where $$0 \leq s < (2h+1)^2 - (2h-1)^2 = 8h$$. Now, $$34+s$$ is a sum of $$5$$ positive squares (cf. https://math.stackexchange.com/questions/1410157/integers-which-are-the-sum-of-non-zero-squares), so $$34 + s = \sum_{r=1}^5 x_r^2,$$ with $$0. One can check that one can find $$5$$ disjoint pairs $$(i_r,j_r), r=1, \dots 5$$ between $$1$$ and $$x_5+11$$, such that $$j_r = i_r + x_r$$. Thus, if $$n \geq x_5+11$$, the permutation $$\sigma = (i_1 j_1) (i_2 j_2) \dots (i_5 j_5)$$ satisfies $$\sum_{k = 1}^n k \sigma(k) = \frac{n(n+1)(2n+1)}{6} - \sum_{r=1}^5 x_r^2 = (2h-1)^2.$$ It thus remains to check that $$n \geq x_5+11$$. It sufficient to have $$34 + s \leq (n-11)^2$$. We have $$34 + s \leq 33+ 8h \leq 37 + 4 \sqrt{\frac{n(n+1)(2n+1)}{6} -34}.$$ The RHS is $$O(n^{\frac{3}{2}})$$, and it is thus $$< (n-11)^2$$ for $$n$$ large enough. Numerically, one checks that the RHS is $$\leq (n-11)^2$$ for $$n \geq 14$$.