# Possible n-uplets that are the difference term by term of two permutations

In this post, I'll consider everything modulo $$n$$.

I need to find all $$n$$-uplets $$\{a_1, \dots a_n\}$$ (multiplicity taken into account, but not order) that can be written as $$\{\sigma_1 - 1, \dots, \sigma_n - n\}$$ where $$\sigma$$ is a permutation of $$[\![1, n ]\!]$$. Formally, I want to find $$A = \{ (\sigma_1 - 1, \dots, \sigma_n - n\}\ |\ \sigma \text { permutation of } [\![1, n ]\!] \}$$.

If you denote $$B = \{\{a_1, \dots, a_n\}\ |\ a_1, \dots, a_n,\ a_1 + \dots + a_n \equiv 0\}$$, I conjecture that $$A = B$$.

This looks like a well-known result but I can't get my hand on a single proof.

Examples :

$$(0, 0, 1, 3)$$ comes from $$1 2 4 3$$.

$$(2, 2, 2, 2, 4, 4, 4, 4) = (2, 4, 2, 4, 2, 4, 2, 4)$$ which comes from $$36507214$$.

$$(0, 3, 3, 3, 3, 6, 6, 6, 6) = (3, 6, 0, 3, 6, 3, 3, 6, 6)$$ which comes from $$483720156$$. This last example has unique solution up to permutation (by keeping the same cycle lengths, I mean).

Solutions are most of the time unique.

It's straightforward that $$A \subseteq B$$ because $$\{a_1, \dots, a_n\} \in A$$ implies $$a_1 + \dots + a_n \equiv \sigma_1 - 1 + \dots + \sigma_n - n = \sigma_1 + \dots + \sigma_n - 1 - \dots - n = 0$$

I wandered trying to go from a $$n$$-uplet to another. Here's my best attempt : If $$\sigma$$ and $$\tau$$, two permutations such that $$(\sigma_1 - 1, \dots, \sigma_n - n) = (a_1, \dots, a_n)$$ and $$(\tau_1 - 1, \dots, \tau_n - n) = (b_1, \dots, b_n)$$, then $$\sigma \circ \tau$$ gives $$\{\tau_{\sigma_1} - 1, \dots, \tau_{\sigma_n} - n\} = \{a_1 + b_{\sigma_1}, \dots, a_n + b_{\sigma_n}\}$$

The conjecture is false; see a counterexample at the bottom of this answer.

Consider the map $$M$$ of the space of permutations $$\sigma$$ of size $$n$$ to the space of $$n$$-tuples $$a$$ of the form $$a_i= \sigma_i - i$$. This map is invertible: Given any $$a$$ in the range of $$M(\sigma)$$, $$M^{-1}(a) = \{a_1+1,a_2+2,\cdots,a_n+n\} \pmod n$$ with $$0$$ replaced by $$n$$.

And $$\{a_1+1,a_2+2,\cdots,a_n+n\} \pmod n$$ with $$0$$ replaced by $$n$$ is a valid permutation precisely because $$a$$ is in the range of $$M(\sigma)$$.

Thus that map and its inverse form a bijection from the space of starting permutations to the set of values of $$a$$ that are in the range of $$M$$. So if you prove that the range of $$M$$ is the set you have described (the set of $$n$$-tuples which have members adding to $$0 \pmod n$$ you will have proven that the two required sets are equivalent.

In your posting you already show that the condition on set $$A^*$$ of having members adding to $$0 \pmod n$$ is necessary, it remains to show that it is sufficient. In attempting to form a constructive proof, however, I have uncovered a counterexample.

Let $$n=4$$; then $$[\![ 0,3,0,1]\!] \in A^*$$ but the starting "permutation" that leads to $$[\![ 0,3,0,1]\!]$$ is $$(1,1,2,4)$$ which is not in the permutation group.

• You missed an important point : $(a_1, \dots, a_n)$ is unordered. I do have a notational issue : $(a_1, \dots, a_n)$ usually (meaning not in my question neither in this comment) stands for a tuple (order, multiplicity), and $\{a_1, \dots, a_n\}$ stands for a set (not order, not multiplicity). What I mean is what we may call a "multiset" (not order, multiplicity). In your counter-example $(0, 3, 0, 1) = (0, 0, 1, 3)$ which comes from the permutation $1 2 4 3$ – Astaulphe Mar 17 at 20:12