# Tag Archives: prime power

## Jordan-Hölder theorem

I am cramming for my algebra comprehensive exam so I will probably be posting stuff like this for a while.

A chain of subgroups $\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G$ of a finite group $G$ with $H_{i+1}/H_i$ simple for all $i$ is called a composition series of $G$. (The $H_{i+1}/H_i$ are called composition factors.) The theorem in question states that every group has a composition series, and the composition factors in any two such series are unique up to reordering.

We can easily prove the first part of the theorem, that any finite group has a composition series, using the extreme principle. Let $n\ge 0$ be the largest integer for which there is a chain $\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G$ of subgroups. (Such an $n$ exists because there is trivially a chain with $n=1$, and our group is finite.) We claim that the composition factors in this case are simple. If not, WLOG $H_{i+1}/H_i$ has a non-trivial normal subgroup $\widetilde N$. By correspondence, $\widetilde N=N/H_i$ for some $H_i\triangleleft N\triangleleft H_{i+1}$. But then

$\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_i\triangleleft N\triangleleft H_{i+1}\cdots\triangleleft H_n=G$

is a longer chain, a contradiction.

While the proof of the general theorem requires some non-trivial group theory (e.g. see here), we can easily prove the theorem for finite abelian groups using elementary number theory. For such a group, the orders of the composition factors must exactly be the prime factors—listed with multiplicity—of the order of the group. So the result follows immediately from the fundamental theorem of arithmetic.

Filed under Algebra, Number theory

## A weaker version of Burnside’s theorem

Burnside’s theorem in group theory asserts that if $p, q$ are prime numbers and $a, b$ are non-negative integers then a group of order $p^aq^b$ is soluble.

As outlined in the Wikipedia article, the proof of this theorem is not simple and most proofs make use of representation theory. Under a weaker hypothesis, however, we can give the following simpler proof using Sylow’s theorems.

Theorem. Let $G$ be a finite group of order $p^aq^b$. Suppose that $a<\hbox{ord}_qp$ or $b<\hbox{ord}_pq$. Then $G$ is soluble.

Note that if $p=q$ then the hypothesis is trivially satisfied.

An immediate corollary is the following.

Corollary. Every group of order $pq$ is soluble.

To prove the Theorem we shall make use of the following two lemmas.

Lemma 1. If $H$ is a normal subgroup of $G$ then $G$ is soluble iff both $H$ and $G/H$ are soluble.

Proof. See here$\square$

Lemma 2. Finite $p$-groups are soluble.

Proof. We prove by induction on $n\ge 0$ that a group $G$ of order $p^n$ is soluble. The result is trivial for $n=0$ so assume that $n\ge 1$. Using the class equation one easily deduces that the centre $Z$ of $G$ is non-trivial. Hence $Z$ is a normal subgroup of $G$. If $Z=G$ then $G$ is abelian and the result is clear. Otherwise $Z$ is a proper normal subgroup of $G$, so that by the induction hypothesis both $Z$ and $G/Z$ are soluble. Thus $G$ is soluble by Lemma 1. $\square$

Proof of the Theorem. If $p=q$ we are done by Lemma 2, so assume that $p\neq q$. Without loss of generality assume that $b<\hbox{ord}_pq$. Let $n_p$ denote the number of Sylow $p$-subgroups of $G$. By the Sylow theorems, $n_p\mid q^b$ and $n_p\equiv 1\pmod p$, i.e., $n_p=q^j\equiv 1\pmod p$, for some $0\le j\le b$. But $b<\hbox{ord}_pq$, which forces $j=0$, i.e., $n_p=1$. Let $H$ be the unique Sylow $p$-subgroup of $G$. Then by the second Sylow theorem $H$ must be self-conjugate, i.e., a normal subgroup of $G$.

By Lemma 2 both $H$ (which has order $p^a$) and $G/H$ (which has order $q^b$) are soluble. Thus $G$ is soluble, as desired. $\square$

Filed under Algebra

## A nice divisibility result on binomial coefficients

I just came across this cute little result on Quora and generalised it to the following.

Proposition. For any integers $0,

$\displaystyle\frac{n}{(n,k)}$ divides $\displaystyle\binom{n}{k}$.

First proof. Note that

$\displaystyle \frac{k}{(n,k)}\binom nk=\frac{n}{(n,k)}\binom{n-1}{k-1}$.

Since $\displaystyle\left(\frac{n}{(n,k)},\frac{k}{(n,k)}\right)=1$, the result follows. $\square$

Second proof. Let $n=p_1^{a_1}\cdots p_r^{a_r}$ and $k=p_1^{b_1}\cdots p_r^{b_r}$ where $p_1,\dots,p_r$ are the prime factors of $nk$. For each $i$, the base $p_i$ representations of $n$ and $k$ have $a_i$ and $b_i$ trailing zeros respectively. Hence by Kummer’s theorem $p_i^{\max\{a_i-b_i,0\}}$ divides $\displaystyle\binom nk$. Hence

$\displaystyle k\prod_{i=1}^rp_i^{\max\{a_i-b_i,0\}}=\prod_{i=1}^rp_i^{\max\{a_i,b_i\}}=[n,k]$

divides $\displaystyle k\binom nk$. Now the result follows using $[n,k]/k=n/(n,k)$. $\square$

A nice corollary is the following property of Pascal’s triangle.

Corollary. For any integers $0,

$\displaystyle\gcd\left(n,\binom nk\right)>1$.

Using the identity

$\displaystyle\binom nk\binom kr=\binom nr\binom{n-r}{k-r}$

the argument in the first proof above can be adapted to prove the following generalisation:

Proposition. For any integers $0\le r\le k\le n$,

$\displaystyle\frac{\binom nr}{\left(\binom nr,\binom kr\right)}$ divides $\displaystyle\binom{n}{k}$.

Corollary. Any two entries $\neq 1$ in a given row of Pascal’s triangle have a common factor $>1$.

Filed under Number theory

## Number of irreducible polynomials over a finite field

I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.

Let $q$ be a prime power and $n$ any positive integer. We wish to count the number $C(n)$ of monic irreducible polynomials of degree $n$ over the finite field $\mathbb F_q$.

Note that the zeros of

$\displaystyle F_d(X):=\prod_{\deg(f)=d}f(X)$

are precisely the elements of degree $d$ over $\mathbb F_q$, where the product is taken over monic irreducible polynomials $f\in\mathbb F_q[X]$. Further, we have the following:

Lemma 1. Let $g\neq h$ be relatively prime polynomials over a field $k$. Then $g$ and $h$ have no common zeros.

Proof. Since $k[X]$ is a PID, there are polynomials $u,v\in k[X]$ such that $ug+vh=1$. If $\alpha$ is a common zero of $g$ and $h$ in some extension $K/k$, then $X-\alpha$ divides $1=ug+vh$ in $K[X]$, a contradiction. $\square$

Lemma 2. If $f$ is irreducible over a field $k$, then $f$ has distinct zeros.

Proof. Note that any multiple zero of $f$ must be a common zero of $f$ and its formal derivative $f'$. Since $f$ is irreducible over $k$, it follows that $f$ and $f'$ are relatively prime over $k$. Now apply lemma 1 to $f$ and $f'$. $\square$

It follows that the zeros of

$\displaystyle \prod_{d\mid n}F_d(X)$

are all distinct and are precisely the elements of the union of all the subfields of $\mathbb F_{q^n}$, which is just $\mathbb F_{q^n}$. This implies

$(*)\qquad\qquad\qquad\qquad\quad\displaystyle\prod_{d\mid n}F_d(X)=X^{q^n}-X$,

since $\mathbb F_{q^n}$ is the splitting field of $X^{q^n}-X$ over $\mathbb F_q$. Now a comparison of the degrees of both sides reveals that

$\displaystyle\sum_{d\mid n}dC(d)=q^n$.

Finally, Möbius inversion gives

$\displaystyle \boxed{C(n)=\frac 1n\sum_{d\mid n}\mu(d)q^{n/d}}$.

Filed under Combinatorics, Number theory

## Prime power dividing product of consecutive integers

The following proposition (not as a proposition but merely as a one-line fact) was stated in a paper that I have been studying as ‘easily seen’ to hold, while I, unfortunately, could not see it so easily! Nonetheless, I think it is a nice result.

For $a$ a positive integer, we use the usual notation $v_p(a)$ to denote the largest integer $k$ such that $p^k\mid a$ and $p^{k+1}\nmid a$. (Apparently, this is called the $p$-adic order, I still haven’t figured out why.) Further, we write $p^k\parallel a$ if $v_p(a)=k$.

Proposition. Let $p$ be a prime number and $n,k$ positive integers. Let $n+a$ be an integer with $n\le n+a\le n+k$ that is maximally divisible by $p$, i.e., with $v_{p}(n+a)=\max\{v_{p}(n+j):0\le j\le k\}$. Then, if

$\displaystyle p^h\parallel\frac{n(n+1)\cdots (n+k)}{n+a}$,

then $p^h\mid k!$.

We will use the following lemma which is easy to prove.

Lemma. For all real numbers $\alpha,\beta$,

$\displaystyle \lfloor\alpha+\beta\rfloor=\begin{cases}\lfloor\alpha\rfloor+\lfloor\beta\rfloor+1,&\{\alpha\}+\{\beta\}\ge 1\\ \lfloor\alpha\rfloor+\lfloor\beta\rfloor,&\{\alpha\}+\{\beta\}<1\end{cases}$

where $\{\alpha\}:=\alpha-\lfloor\alpha\rfloor$ is the fractional part of $\alpha$.

Proof of the proposition. Let $s=v_{p}(n+a)$. Then

$\displaystyle h=\sum_{j=1}^s\left(\left\lfloor\frac{n+k}{p^j}\right\rfloor-\left\lfloor\frac{n-1}{p^j}\right\rfloor\right)-s$.

First suppose that $(k+1,p)=1$. Then $v_{p}(k!)=v_{p}((k+1)!)$, so by the lemma we get

$\displaystyle h\le\sum_{j=1}^s\left(\left\lfloor\frac{k+1}{p^j}\right\rfloor+1\right)-s\le v_p((k+1)!)=v_{p}(k!)$,

as desired. Now suppose that $p^u\parallel k+1$ for some $u\ge 1$. Then $\{\frac{k+1}{p^j}\}=0$, so $\{\frac{n-1}{p^j}\}+\{\frac{k+1}{p^j}\}<1$, for each $j\le u$. Thus

\displaystyle\begin{aligned}h&\le\sum_{j=1}^u\left\lfloor\frac{k+1}{p_i^j}\right\rfloor+\sum_{j=u+1}^s\left(\left\lfloor\frac{k+1}{p_i^j}\right\rfloor+1\right)-s\\ &=\sum_{j=1}^u\left(\left\lfloor\frac{k}{p_i^j}\right\rfloor+1\right)+\sum_{j=u+1}^s\left(\left\lfloor\frac{k}{p_i^j}\right\rfloor+1\right)-s\\ &\le v_{p}(k!).\end{aligned}

Hence the result follows. $\square$