How hard is recognizing a permutation that is a square for the shift product?

Question

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation problem (How hard is reconstructing a permutation from its differences sequence?) which turned out to be NP-complete. Here, I propose another computational problem which I highly suspect that it is NP-complete.

The shift of a permutation $\pi(i)$ of numbers $1, 2, \ldots n$ is defined as $\sigma(i)$= $\pi(i+k \mod n)$ for some fixed $k$, $1 \le k \lt n$. The shift product of a permutation $\pi$ is defined as $ \pi(i+k \mod n) \circ \pi(i)$. We say that a permutation $\pi$ is a square for the shift product if there is a permutation $\tau$ such that $\pi$ is the shift product of $\tau$ (i.e. $\pi(i)= \tau(i+k \mod n) \circ \tau(i)$).

I did not find a notion of shift product for permutations in the literature.

Formally,

Square Permuation

Instance: A permutation $\pi$ of $1, 2, \ldots n$

Question: Is permutation $\pi$ a square for the shift product?

Is there an efficient algorithm to determine whether a given permutation $\pi$ is a square for the shift product of some permutation $\tau$, or is it NP-complete?

The problem appears to be hard even when the shift amount $k=1$.

This was posted on mathOverflow.

Answer 1

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix} \right)$$ be the shift permutation. Then the shift of $\tau$ is just $\sigma = \tau \circ \rho_k$, and the shift product of $\tau$ is $\tau \circ \rho_k \circ \tau$. But $$\pi = \tau \circ \rho_k \circ \tau \iff \rho_k \circ \pi = (\rho_k \circ \tau)^2$$

Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to see whether it has a square root, which can also be done in linear time.