7
$\begingroup$

Problem statement: Let $U=\{1,2,...n\}$ and $S$ be the set of all permutations of the elements of $U$. For any $f \in S$ let $I(f)$ denotes the number of inversions (see remark) of $f$. Let $A_j$ denotes the number of permutations $f$ in $S$ such that $I(f)\equiv j\pmod{p}$ $[0\leq j \leq p-1]$ where $p$ is an odd prime number. Then prove that $$A_1=A_2=A_3=\ldots=A_{p-1} \Leftrightarrow p\leq n.$$

My solution to this problem uses roots of unity (as I have posted the answer). I want to find other solutions.

Remark For a permutation $\sigma$ of $\{1,2,\ldots,n\}$ we call a pair $(i,j)$ an inversion in $\sigma$ if $i<j$ but $\sigma(i)>\sigma(j)$.

$\endgroup$
7
  • $\begingroup$ Can you say what is meant by 'inversions'? $\endgroup$ May 14 '20 at 14:55
  • $\begingroup$ For a permutation $\sigma$ of $\{1,2,\ldots,n\}$, a pair $(i,j)$ is called an inversion if $i<j$ but $\sigma(i)>\sigma(j)$. $\endgroup$ May 14 '20 at 14:59
  • 1
    $\begingroup$ Perhaps you could share your proof via roots of unity? $\endgroup$ May 14 '20 at 16:44
  • 1
    $\begingroup$ @caffeinemachine I have posted my solution using roots of unity $\endgroup$ May 14 '20 at 20:09
  • 1
    $\begingroup$ Hi I just edited your question (mainly just to make it less wordy) $\endgroup$ Jul 22 '20 at 9:35
6
$\begingroup$

Claim 1: If $n \geq p$, then $A_0 = A_1 = \cdots = A_{p-1}$

proof: We induct on $n$. Let $B_{i,n}$ be the set of permutations on n elements with $I(f) \equiv i$ mod $p$. The base case of $n=p$ is true becasue for every $0 \leq i \leq p-1$ and way to order $2,3, \cdots, n$, there is a unique position to insert $1$ so that the resulting permutation is in $B_{i,n}$.

Now assume the result is true for $n$. Then summing over the positions one is inserted gives $$|B_{i,n+1}| = \sum_{k = 0}^{p-1} |B_{i-k,n}|\left\lfloor\frac{(n+1-k)}{p} \right \rfloor = |B_{0, n}|\sum_{k = 0}^{p-1}\left\lfloor\frac{(n+1-k)}{p} \right \rfloor$$ so we have proven Claim 1.

Claim 2: It is not true that $A_1 = \cdots = A_{p-1}$ for $n < p$.

proof: Let $n < p$. Suppose towards a contradiction that $A_1 = \cdots = A_{p-1}$. Considering the bijection that maps every permutation to its reversal gives $$|B_{0,n}| = \left|B_{{n \choose 2},n}\right|$$ and since $p$ does not divide ${n \choose 2}$, we get $A_0 = A_1 = \cdots = A_{p-1}$. But this is a contradiction since $p$ does not divide $n!$.

$\endgroup$
5
$\begingroup$

HERE IS MY SOLUTION USING ROOTS OF UNITY

Claim 1: Let $f(x)=x^{a_1}+x^{a_2}+\ldots+x^{a_m}$, where $a_1,a_2,\ldots,a_m\in \mathbb{N}$. Let $p$ be some odd prime. Denote the number of $j\in\{1,2,\ldots,m\}$ with $a_j\equiv i\pmod{p}$, for some $i\in\{0,1,\ldots,p-1\}$, by $N_i$. Let $\varepsilon=e^{\frac{2\pi i}{p}}$. Then $$f(\varepsilon)=N_0+N_1\varepsilon+N_2\varepsilon^2+\ldots+N_{p-1}\varepsilon^{p-1}$$

Proof: For $M\in\mathbb{N}$, if $M\equiv j\pmod{p}$, then $$\varepsilon^M=e^{\frac{2\pi iM}{p}}=e^{\frac{2\pi i(j+kp)}{p}}=e^{\frac{2\pi ij}{p}}e^{2\pi ik}=\varepsilon^j$$ Then, $$f(\varepsilon)=\varepsilon^{a_1}+\varepsilon^{a_2}+\ldots+\varepsilon^{a_m}$$

$$=\sum_{j=0}^{p-1}\varepsilon^j\left(\sum_{a_i\equiv j\pmod{p}}1\right)=\sum_{j=0}^{p-1}N_j\varepsilon^j$$


Claim 2: Let $b_0,b_1,\ldots, b_{p-1}\in\mathbb{Z}$. Then $$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ if and only if $$b_0=b_1=b_2=\ldots=b_{p-1}$$

Proof: Consider the polynomial $$\Phi_p(X)=1+X+X^2+\ldots+X^{p-1}$$ It is well known that $\Phi_p(X)$ is irreducible over $\mathbb{Z}[X]$. Again $\varepsilon$ is a root of $\Phi_p(X)$. Let $$Q(X)=b_0+b_1X+b_2X^2+\ldots+b_{p-1}X^{p-1}$$ By hypothesis $$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ we get that $\varepsilon$ ia also a root of $Q(X)$. Since $\Phi_p(X)$ is irreducible, it is the minimal polynomial of $\varepsilon$. Then $\Phi_p(X)|Q(X)$. Since $\mathrm{deg}(\Phi_p)=\mathrm{deg}(Q)=(p-1)$, $\exists$ $a\in \mathbb{Z}$ such that $Q(X)=a\Phi_p(X)$. Therefore $$b_0=b_1=b_2=\ldots=b_{p-1}$$ The other direction is pretty easy because $\varepsilon$ is a root of $\Phi_p$.


In the book COMBINATORICS OF PERMUTATIONS by MIKLOS BONA you can find the following:

Let, $$I_n(X)=\sum_{\sigma\in S_n}X^{i(\sigma)}$$ Where for some permutation $\sigma\in S_n$(the symmetric group of order $n$) $i(\sigma)$ denotes the number of inversions in $\sigma$. In the the book mentioned above we get, $$I_n(X)=(1+X)(1+X+X^2)\ldots(1+X+X^2+\ldots+X^{n-1})$$

Hence according to the notation in the problem and claim 1, $$I_n(\varepsilon)=A_0+A_1\varepsilon+A_2\varepsilon^2+\ldots+A_{p-1}\varepsilon^{p-1}$$ Following claim 2 we conclude that $I_n(\varepsilon)=0$ if and only if $A_0=A_1=A_2=\ldots=A_{p-1}$.

Now, $I_n(\varepsilon)=0$ if and only if $\exists$ $l\in\{1,2,\ldots,n-1\}$ such that $(1+\varepsilon+\varepsilon^2+\ldots+\varepsilon^l)=0$. Since $\varepsilon$ is an algebraic number of degree $p-1$, we must have $l\geq p-1$. Then $I_n(\varepsilon)=0$ if and only if $n-1\geq l\geq p-1$. Hence we conclude that $A_0=A_1=A_2=\ldots=A_{p-1}$ if and only if $n\geq p$.

$\endgroup$
3
  • $\begingroup$ Very interesting. Thanks. $\endgroup$ May 14 '20 at 20:19
  • $\begingroup$ It would be a good idea to give the reference used (from Bona's book) more precisely. As in, you could mention the proposition number of the section and chapter. $\endgroup$ May 14 '20 at 20:24
  • $\begingroup$ @caffeinemachine COMBINATORICS OF PERMUTATIONS, SECOND EDITION, PAGE NO. 53, THEOREM 2.3 $\endgroup$ May 14 '20 at 20:33
4
$\begingroup$

@cha21 has a nice proof for the case when $p > n$, but for the $p \leq n$ there is an alternative approach for proof:

Claim: if $n \geq p$, then $A_0 = A_1 = ... A_{p-1}$

Proof: Let's define function $C_p(i)$ for permutation $p$ that counts number of inversions $(j, i)$ where $j < i$. More formally: $C_p(i) = |\{ j < i \mid p_j > p_i \}|$.

Then, for every permutation $p$ we can define a sequence $C(p) = [C_p(0), C_p(1), ..., C_p(n - 1)]$. This sequence contained in the set of integer sequences $S(n)$ of length $n$, where $i$-th element of every sequence is in the set $[0..i]$, so $S(n) = \{ s \mid |s| = n \text{ and } \forall_i s_i \in [0..i] \}$ and $C(p) \in S(n)$. It's easy to see, that $|S(n)| = n!$ and therefore for any sequence $s \in S(n)$ there is exactly one permutation $p$ such that $C(p) = s$.

Let's say that two sequences $a$ and $b$ from the set $S(n)$ equivalent iff $a$ and $b$ differs only at position $p-1$. This equivalence relation partition set $S(n)$ into the classes $K_i \subset S(n)$, and it's easy to see that $|K_i| = p$ and sequences from $K_i$ has $p$ different remainder of sum of values by module $p$. This implies, that $A_0 = A_1 = ... = A_{p-1}$.

$\endgroup$

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.