<p>It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&amp;2&amp;\ldots&amp;n\\ (k+1)\bmod n&amp;(k+2)\bmod n&amp;\ldots&amp;(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$$</p>

<p>Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to <a href="https://math.stackexchange.com/q/266569/5676">see whether it has a square root</a>, which can also be done in linear time.</p>

CC BY-SA 3.0
2015-09-28T13:40:06.430Z
2015-09-28T13:40:06.430Z
2017-04-13T12:19:19.363Z
Peter Taylor
<p>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 (<a href="https://mathoverflow.net/questions/135968/how-hard-is-reconstructing-a-permutation-from-its-differences-sequence">How hard is reconstructing a permutation from its differences sequence?</a>) which turned out to be NP-complete. Here, I propose another computational problem which I highly suspect that it is NP-complete.</p>

<p>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)$).</p>

<p>I did not find a notion of shift product for permutations in the literature.</p>

<p>Formally,</p>

<p><strong>Square Permuation</strong></p>

<p><strong>Instance</strong>: A permutation $\pi$ of $1, 2, \ldots n$</p>

<p><strong>Question</strong>: Is permutation $\pi$ a square for the shift product?</p>

<blockquote>
  <p>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?</p>
</blockquote>

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

<p>This was posted on <a href="https://mathoverflow.net/questions/219089/how-hard-is-recognizing-a-permutation-that-is-a-square-for-the-shift-product">mathOverflow</a>.</p>

CC BY-SA 3.0
2015-09-27T22:49:41.480Z
I guess you mean $\pi(i)=\tau(\tau(i)+k \mod n)$. Otherwise it makes little sense.
Maybe a better notation: let's write $[k]\pi$ the $k$-shift of $\pi$.
The question is then: is there a $\tau$ such that $\pi=[k]\tau \circ \tau$?
Marc
CC BY-SA 3.0
2015-09-28T11:08:23.850Z
@Marc Let $\tau(i)$=[2,4,1,6,5,3] then $\tau(i+1)$=[4,1,6,5,3,2]. The shift product $\tau(i+1) \circ \tau(i)$=[1,5,4,2,3,6]. –  Mohammad Al-Turkistany 2 hours ago
Mohammad Al-Turkistany
<cc.complexity-theory><co.combinatorics><np-hardness><permutations>
How hard is recognizing a permutation that is a square for the shift product?
Mohammad Al-Turkistany
# How hard is recognizing a permutation that is a square for the shift product?

(Asked by: username_0 on 2015-09-26)

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?](https://mathoverflow.net/questions/135968/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](https://mathoverflow.net/questions/219089/how-hard-is-recognizing-a-permutation-that-is-a-square-for-the-shift-product).

**Tags:** cc.complexity-theory, co.combinatorics, np-hardness, permutations
> **Comments:**
> **username_1**: I guess you mean $\pi(i)=\tau(\tau(i)+k \mod n)$. Otherwise it makes little sense. Maybe a better notation: let's write $[k]\pi$ the $k$-shift of $\pi$. The question is then: is there a $\tau$ such that $\pi=[k]\tau \circ \tau$?  
> **username_0**: @Marc Let $\tau(i)$=[2,4,1,6,5,3] then $\tau(i+1)$=[4,1,6,5,3,2]. The shift product $\tau(i+1) \circ \tau(i)$=[1,5,4,2,3,6]. –  Mohammad Al-Turkistany 2 hours ago  

---

## 1 answers

### Answer by username_2 on 2015-09-28. Score: 4 | Accepted answer

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](https://math.stackexchange.com/q/266569/5676), which can also be done in linear time.


---

