1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $ $\endgroup$ – Astaulphe Mar 17 at 20:12

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.