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!


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$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.