Some Combinatorics and Some Prime Numbers

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

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

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!$.