Some Combinatorics and Some Prime Numbers

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 jpmod{p}$$ $$[0leq 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 pleq 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 but $$sigma(i)>sigma(j)$$.

Mathematics Asked by Shubhrajit Bhattacharya on November 21, 2021

@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}$$.

Answered by Nikita Sivukhin on November 21, 2021

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_min mathbb{N}$$. Let $$p$$ be some odd prime. Denote the number of $$jin{1,2,ldots,m}$$ with $$a_jequiv ipmod{p}$$, for some $$iin{0,1,ldots,p-1}$$, by $$N_i$$. Let $$varepsilon=e^{frac{2pi i}{p}}$$. Then $$f(varepsilon)=N_0+N_1varepsilon+N_2varepsilon^2+ldots+N_{p-1}varepsilon^{p-1}$$

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

$$=sum_{j=0}^{p-1}varepsilon^jleft(sum_{a_iequiv jpmod{p}}1right)=sum_{j=0}^{p-1}N_jvarepsilon^j$$

Claim 2: Let $$b_0,b_1,ldots, b_{p-1}inmathbb{Z}$$. Then $$b_0+b_1varepsilon+b_2varepsilon^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_1varepsilon+b_2varepsilon^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$$ $$ain mathbb{Z}$$ such that $$Q(X)=aPhi_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_{sigmain S_n}X^{i(sigma)}$$ Where for some permutation $$sigmain 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_1varepsilon+A_2varepsilon^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$$ $$lin{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 $$lgeq p-1$$. Then $$I_n(varepsilon)=0$$ if and only if $$n-1geq lgeq p-1$$. Hence we conclude that $$A_0=A_1=A_2=ldots=A_{p-1}$$ if and only if $$ngeq p$$.

Answered by Shubhrajit Bhattacharya on November 21, 2021

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}|leftlfloorfrac{(n+1-k)}{p} right rfloor = |B_{0, n}|sum_{k = 0}^{p-1}leftlfloorfrac{(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!$$.

Answered by cha21 on November 21, 2021

Related Questions

Nimber multiplication

2  Asked on July 30, 2020 by yberman

What is the radius of convergence of $a_n$ where $a_{n+1}=frac{n-5}{n+1}a_n$?

2  Asked on July 28, 2020 by lucas

Discretization formula for a system of two differential equations. “Solution to one of these is the initial condition of the other”. In which sense?

0  Asked on July 27, 2020 by strictly_increasing

Calculating distance when velocity is given

1  Asked on July 27, 2020 by aruha

dimension of intersection of subspaces, one of which of dimension $n-1$

1  Asked on July 27, 2020 by gulzar

Let $A$ be a subset of $mathbb{R}$ such that $A$ is bounded below with inf $A = L > 0$.

2  Asked on July 26, 2020 by outlier