4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Perhaps, one can use induction on $n$ to provide an answer. $\endgroup$ Apr 2, 2021 at 14:47
  • $\begingroup$ 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. $\endgroup$ Apr 6, 2021 at 20:18

1 Answer 1

8
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ @Brunault Great! Thank you! $\endgroup$ Apr 18, 2021 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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