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!
 A: 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$.
