# Monthly Archives: March 2015

## Binomial sum modulo prime power: Part 1

In the last post we showed that

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$

and then we used Lucas’ theorem to evaluate the sum modulo $p$.

My initial attempt at evaluating the sum was to note that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

where $\omega=\exp(2\pi i/p)$, but then I was stuck. Numerical examples suggested that this sum is in fact divisible by $p^{\lceil n/(p-1)\rceil}$, but I could not think of a way of extending the argument from the last post. Nonetheless, some extensive google search recently revealed that

Theorem (Fleck, 1913). For any $j$,

$\displaystyle\sum_{m\equiv j\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\left\lfloor \frac{n-1}{p-1}\right\rfloor}}$.

So taking $j=0$ gives the desired claim after noting that

Fact. $\displaystyle \left\lfloor\frac{n-1}{p-1}\right\rfloor+1=\left\lceil\frac{n}{p-1}\right\rceil$.

Proof. Write $n=q(p-1)+r$ with $0\le r. If $r=0$ then the equation is just $q-1+1=q$, and if $r>0$ then it is $q+1=q+1$. $\square$

This article contains a proof of Fleck’s result using the identity $(*)$. Unfortunately I don’t have a good grasp of the theory behind it.

Filed under Number theory

## Number of permutations of prime order

In the last post we counted the number of elements of order 2 in the symmetric group $S_n$. In exactly the same way we can count the number of elements of order $p$, where $p$ is a prime number. Let this number be denoted by $N_p(n)$. Then

\displaystyle\begin{aligned}N_p(n)&=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{(p-1)!^k}{k!}\binom np\binom{n-p}{p}\cdots\binom{n-pk+p}{p}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{n!}{k!(n-pk)!p^k}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\binom{n}{pk}\frac{(pk)!}{k!p^k}.\end{aligned}

Here we adopt the convention $\binom nm=0$ if $m>n$. Note that

$\displaystyle\frac{(pk)!}{k!p^k}=\frac{(pk)!}{p\cdot 2p\cdots kp}\equiv (p-1)!^k\equiv (-1)^k\pmod p$

by Wilson’s theorem. So

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$.

If $n=n_rp^r+\cdots+n_1p+n_0$ and $k=k_{r}p^{r-1}+\cdots+k_2p+k_1$ are base $p$ expansions, then using Lucas’ theorem one has

$\displaystyle\binom{n}{pk}\equiv\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p$.

Therefore

\displaystyle\begin{aligned}N_p(n)&\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p\\ &\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{k_1+\cdots+k_r}\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p\\ &\equiv -1+\prod_{j=1}^r\sum_{k_j=0}^{n_j}(-1)^{k_j}\binom{n_j}{k_j}\pmod p\\ &\equiv -1\pmod p\end{aligned}

This generalizes the result from the previous post.

Corollary. The number of subgroups of order $p$ in $S_n$ is congruent to $1\pmod p$.

Proof. If there are $k$ subgroups of order $p$ in $S_n$, then $N_p(n)=k(p-1)\equiv -1\pmod p$ and so $k\equiv 1\pmod p$. $\square$

1 Comment

Filed under Combinatorics, Number theory

## Number of permutations of order 2

Let $\sigma\in S_n$ be an element of order 2. Then $\sigma$ must be a product of $k\ge 1$ disjoint transpositions. Hence $\sigma$ can be chosen in

$\displaystyle\frac{1}{k!}\binom n2\binom{n-2}{2}\cdots\binom{n-2k+2}{2}=\frac{n!}{k!(n-2k)!2^k}$

ways. So there are exactly

$\displaystyle\boxed{\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{k!(n-2k)!2^k}}$

elements of order 2 in $S_n$.

This can also be expressed in terms of the double factorial

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!$

The following table lists several values of $n$ (left column) along with the number of elements of order 2 in $S_n$:

An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\equiv \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}\pmod 2$

Using the binomial theorem for $(1+1)^n$ and $(1-1)^n$ one deduces

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}-1\equiv 1\pmod 2$

as expected. Thus

Fact. The number of elements of order 2 in $S_n$ is odd for every $n>1$.

1 Comment

Filed under Combinatorics

## Sums of equal powers

Let $k$ be a fixed positive integer. Let

$S_k(n):=1^k+\cdots+n^k$.

Let us consider expressions of the form

$\pm 1^k\pm\cdots\pm n^k=\displaystyle\sum_{j=1}^nj^ke_j=: S(e_1,\dots,e_n)$

where $e_j=\pm 1\,\forall j$.

Note that $S$ takes $2^n$ possible values in $[-S_k(n),S_k(n)]$ which are all congruent modulo $2$. Hence the number of distinct values that $S$ takes is at most

$\displaystyle\left\lceil\frac{2S_k(n)+1}{2}\right\rceil=S_k(n)+1$

Since this is $O(n^{k+1})$, it is eventually dominated by $2^n$. Thus for all sufficiently large $n$, we can find $e_j,e_j'\in\{\pm 1\}$ such that

$\displaystyle\sum_{j=1}^nj^ke_j=\sum_{j=1}^nj^ke_j'\Leftrightarrow\sum_{j=1}^n(e_j-e_j')j^k=0$

with $e_j\neq e_j'$ for some $j$.

Note that $e_j-e_j'\in\{0,\pm 2\}\,\forall j$. Let $A=\{j:e_j-e_j'=2\}$ and $B=\{j:e_j-e_j'=-2\}$. Then $A$ and $B$ are non-empty and disjoint, $A\cup B\subseteq\{1,\dots,n\}$, and

$\displaystyle\sum_{j\in A}j^k=\sum_{j\in B}j^k$.

Thus:

Proposition. Let $k$ be a fixed positive integer. Then one can find distinct positive integers $x_1,\dots, x_r,y_1,\dots,y_s$ such that

$x_1^k+\cdots+x_r^k=y_1^k+\cdots+y_s^k$.

In particular, one can choose $x_i,y_j\le\min\{n\in\mathbb N: 2^n>S_k(n)+1\}\,\forall i,j$.

Example. Let $k=4$. Note that $2^n>S_4(n)+1$ for all $n\ge 20$. So there exist distinct integers $1\le x_i,y_j\le 20$ such that $\sum_ix_i^4=\sum_jy_j^4$. In particular, one has

$1^4+2^4+9^4=3^4+7^4+8^4$

as well as

$7^4+8^4+10^4+13^4=3^4+9^4+14^4$.

Likewise, for fifth powers we can find such $x_i$‘s and $y_j$‘s in $[1,26]$.

This wikipedia article contains many results related to sums of powers.