Is $\prod_{k=1}^nk^{\sigma(k)}$ a square or a cube for some $\sigma\in S_n$?

Question

Note that for any permutation $\sigma\in S_5$ the product $\prod_{k=1}^5k^{\sigma(k)}$ is neither a square nor a cube.

Question. Let $n>5$ be an integer. Is the product $\prod_{k=1}^nk^{\sigma(k)}$ a square for some $\sigma\in S_n$? Is the product $\prod_{k=1}^nk^{\sigma(k)}$ a cube for some $\sigma\in S_n$?

The question looks not very challenging, and I believe that the answer should be positive. Any ideas to provide a proof?

The question can be refined further, for example, I conjecture that for any integer $n>5$ there is a permutation $\sigma\in S_n$ with $\sigma(1)=1$ and $\sigma(2)=2$ such that $\prod_{k=1}^n k^{\sigma(k)}=(p-1)^3$ for some prime $p$. Let $a(n)$ denote the number of such permutations $\sigma$. I find that $$a(6)=1,\ a(7)=3,\ a(8)=2,\ a(9)=27,\ a(10)=44,\ a(11)=154.$$

For the above question, I ask for an actual proof of the positive answer, rather than inaccurate heuristic arguments.

Answer 1

We show the following.

Theorem. For any $n \geq 6$, there is a permutation $\sigma \in S_n$ such that $\prod_{k=1}^n k^{\sigma(k)}$ is a square (respectively, a cube).

Proof. Let us first handle the case of squares. It is equivalent to find a subset $A$ of $\{1,\ldots,n\}$ with cardinality $r = \lceil \frac{n}{2} \rceil$ such that the product of the elements of $A$ is a square (indeed, for such an $A$, choose any permutation $\sigma$ such that $\sigma(n)$ is odd for $n \in A$, and even for $n \notin A$). Consider the pairs of integers $(m,2m)$ with $1 \leq m \leq n/2$ and $v_2(m) \equiv 0 \pmod{2}$. These pairs are disjoint. Let $N$ be the number of such pairs. Since the probability that an integer $m \geq 1$ satisfies $v_2(m) \equiv 0 \pmod{2}$ is $\frac{1}{2} + \frac{1}{2}\times \frac{1}{4} + \frac{1}{2}\times \frac{1}{4^2} + \cdots = \frac{2}{3}$, we have $N \sim_{n \to \infty} \frac{n}{3}$, and a closer analysis shows that $2N \geq r+1$ for $n \geq 8$. Let us put in $A$ the pairs $(m,2m)$ in increasing order until $|A| \in \{r+1,r+2\}$. Then the product $P$ of the elements of $A$ is a square or twice a square. If $|A|=r+1$, we remove the number $1$ or $2$ from $A$ according to whether $P$ is a square or twice a square. If $|A|=r+2$, we remove the numbers $\{1,4\}$ or $\{1,2\}$ according to whether $P$ is a square or twice a square (removing 4 is possible since $n \geq 8$). The cases $n=6,7$ are dealt with by hand.

Now the case of cubes. We need to find disjoint subsets $A,B$ of $\{1,\ldots,n\}$ with respective cardinality $r_1 = \lceil \frac{n}{3} \rceil$ and $r_2 = \lceil \frac{n-r_1}{2} \rceil$ such that $PQ^2$ is a cube, where $P$ (resp. $Q$) is the product of the elements of $A$ (resp. $B$). We wish to use the pairs $(m,2m)$ as above. Given such a pair, we put one element in $A$ and the other in $B$, giving the products $m^1 \times (2m)^2 = 4m^3$ or $m^2 \times (2m)^1 = 2m^3$, which are either twice a cube or four times a cube. As we saw, the number $N$ of such pairs is roughly $n/3$, but it turns out this is not quite enough to fill in $A$ and $B$. So we use more pairs, namely $(3m,4m)$ with $n/6 < m \leq n/4$ and $v_2(m) \equiv v_3(m) \equiv 0 \pmod{2}$. These pairs are disjoint from the previous ones and their number $N'$ satisfies $N' \sim_{n \to \infty} \frac{n}{24}$. A closer analysis shows that $N+N' \geq r_1$ for $n \notin \{1,7,13\}$. Let us assume $n \geq 8$ and $n \neq 13$. In particular $r_1 \geq 3$.

Case 1. $N'=0$. Then $N \geq r_1 \geq 3$. We keep only the first $r_1$ pairs $(m,2m)$. In particular, we still have $(1,2)$, $(3,6)$ and $(4,8)$. If $r_1=r_2$ then swapping $(1,2)$ or $(3,6)$ if necessary, we can get $|A|=r_1$, $|B|=r_2$ and $PQ^2$ is a cube. If $r_1=r_2+1$ then we remove ($4^2$ or $8^2$) and we possibly swap $(1,2)$ or $(3,6)$ to get the same result.

Case 2. $N'=1$. Let $(3m,4m)$ be the unique pair of the second type, which we will keep. We have $N \geq r_1-1$. Let us first assume $N \geq r_1$. Swapping $(3m,4m)$ if necessary, we may assume that $v_3((3m)^a (4m)^b) \equiv 1 \pmod{3}$ with $\{a,b\}=\{1,2\}$. We keep only the first $r_1$ pairs $(m,2m)$. In particular we still have $(1,2)$, $(3,6)$ and $(4,8)$. If $r_1=r_2$ then we remove ($3^1$ or $6^1$) and ($1^2$ or $2^2$) so that $|A|=r_1$, $|B|=r_2$ and $PQ^2$ is a cube. If $r_1=r_2+1$, we remove ($3^1$ or $6^1$) and ($1^2$ or $2^2$) and ($4^2$ or $8^2$) so that again $A$ and $B$ have the right cardinality and $PQ^2$ is a cube. Finally, the case $N = r_1-1$ happens only for $n \in \{16, 17, 19, 25, 31\}$. These values of $n$ will be handled separately at the end.

Case 3. $N' \geq 2$. We may swap the numbers inside two of the pairs $(3m,4m)$ so that the power of $3$ becomes a cube. Now $N \geq r_1-N' \geq 2$ for $n \geq 6$. We keep only the first $r_1-N'$ pairs $(m,2m)$. If $r_1=r_2$ then we swap $(1,2)$ or $(3,6)$ if necessary so that the power of $2$ becomes a cube. If $r_1=r_2+1$ then we remove ($1^2$ or $2^2$) and possibly swap $(3,6)$ to get the correct power of $2$.

Finally, the cases $n=6,7,13,16,17,19,25,31$ can be handled with a computer, just looping over all disjoint subsets $A,B \subset \{1,\ldots,n\}$ of respective cardinality $r_1$ and $r_2$ (solutions are found quickly). Note that it is not necessary to compute the products $PQ^2$, just keep track of the exponents mod $3$ in the prime factorization of the integers $1 \leq k \leq n$ (these exponents mod $3$ should be precomputed). $\Box$