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<p-1. 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.

2 Comments

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:

Screenshot 2015-03-15 20.54.56

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.

Leave a comment

Filed under Number theory