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

Question

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

Answer 1

The conjecture is true. See this paper of Marshall Hall and this thread on mathoverflow.

The key idea is to reduce the problem to expliciting a way to go from $ a_i + b_i \equiv c_i \mod n $ for all $ i $ (where $ a_i $ is given and $ b, c $ are permutations of $ [\![1, n]\!] $) to $ a_i' + b_i' \equiv c_i \mod n $ where $ a_i' $ is a tuple differing from $ a $ in only two positions and $ b' $ is a permutation of $ [\![1, n]\!] $. This transformation turns out to be possible by repeated "fixing up".

Answer 2

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.