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

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.

• Perhaps, one can use induction on $n$ to provide an answer. Apr 2, 2021 at 14:47
• Simple heuristics show that if $k \geq 2$, then for any $n$ sufficiently large, there should exist a permutation $\sigma \in S_n$ such that the resulting product is a $k$-th power. We can even give heuristics for the number of such $\sigma$, which I believe is very large. Apr 6, 2021 at 20:18

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

• @Brunault Great! Thank you! Apr 18, 2021 at 10:02