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

Question

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!

Answer 1

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<x_1 \leq x_2 \leq x_3 \leq x_4 \leq x_5$. 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$.