## 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 new AM-GM inequality

I recently found the following inequalities useful

$\displaystyle \left(x+\frac{a_1+\cdots+a_n}{n}\right)^n\ge (x+a_1)\cdots(x+a_n)\ge \left(x+\sqrt[n]{a_1\cdots a_n}\right)^n$,

for any $x,a_1,\dots,a_n\ge 0$.

To prove the left half of the inequality simply apply AM-GM to the product

$\displaystyle (x+a_1)\cdots (x+a_n)\le \left(\frac{(x+a_1)+\cdots+(x+a_n)}{n}\right)^n$.

The right half follows directly from Hölder’s inequality.

More generally, one has

$\displaystyle\left(\frac{a_1+\cdots+a_n}{n}+\frac{b_1+\cdots+b_n}{n}\right)^n\ge (a_1+b_1)\cdots(a_n+b_n)\\\ge \left(\sqrt[n]{a_1\cdots a_n}+\sqrt[n]{b_1\cdots b_n}\right)^n$

for $a_1,\dots,a_n,b_1,\dots,b_n\ge 0$. The proof goes similarly.

One obtains similar inequalities for any number of vectors $a,b,c,\dots$.

As an example, for $a_i=i$ we get the inequalities

$\displaystyle \left(x+\frac{n+1}{2}\right)^n\ge (x+1)\cdots (x+n)>\left(x+\frac ne\right)^n$

using the fact that $\sqrt[n]{n!}/n\to 1/e$ from above.

Filed under Algebra

## Hilbert’s nullstellensatz

Leaving it here because I want to study this at some point.

I had occasion recently to look up the proof of Hilbert’s nullstellensatz, which I haven’t studied since cramming for my algebra qualifying exam as a graduate student. I was a little unsatisfied with the proofs I was able to locate – they were fairly abstract and used a certain amount of algebraic machinery, which I was terribly rusty on – so, as an exercise, I tried to find a more computational proof that avoided as much abstract machinery as possible. I found a proof which used only the extended Euclidean algorithm and high school algebra, together with an induction on dimension and the obvious observation that any non-zero polynomial of one variable on an algebraically closed field has at least one non-root. It probably isn’t new (in particular, it might be related to the standard model-theoretic proof of the nullstellensatz, with the Euclidean algorithm and high school algebra taking…

View original post 3,546 more words

Filed under Algebra

## Midy’s theorem

Let $b$ have order $d$ modulo $p$. Then the base $b$ expansion of $1/p$ has period $L=(b^d-1)/p$ of length $d$. To see this, note that if $b^d-1=mp$, then

$\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots$.

Note also that $aL for any $1\le a\le p-1$. Hence $a/p$ has period $aL$. Now suppose that $d$ is even. Since $b$ has order $d$ modulo $p$, it follows that $b^{d/2}\equiv -1\pmod p$. Hence $p-a\equiv b^{d/2}a\pmod p$. This means that at their midpoints the two numbers $aL$ and $(p-a)L$ are mirror images of one another. This means that splitting $aL$ midway into two equal parts and adding them gives $b^{d/2}-1$, i.e., a string of $(b-1)$‘s in base $b$. This is known as Midy’s theorem.

For example, with $p=7$ and $b=10$ we get $d=6$, and $L=142857$. Split $L$ into two equal parts $142$ and $857$, adding which gives

$142+857=999$.

In general, if $m$ is any divisor of $d$, then

\begin{aligned} b^d-1&=(b^m-1)(1+b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m})\\&\equiv 0\pmod p\end{aligned}

so

$b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m}\equiv -1\pmod p$

and so splitting $L$ into $m$ equal parts and adding them will always give a multiple of $b^{d/m}-1$.

Filed under Number theory

## Permutation of digits by multiplication

Here is an expository write-up of this post.

The number $N=142857$ is interesting because of the following property

\begin{aligned}N&=142857\\ 2N&=285714\\ 3N&=428571\\ 4N&=571428\\ 5N&=714285\\ 6N&=857142\end{aligned}

and $7N=999999$. The last equation means that

$\displaystyle\frac 17=0.\overline{142857}.$

So multiplying $N$ by $1,2,3,4,5,6$ simply permutes the digits of $N$. As elements of $S_6$ these permutations correspond to (using cycle notation)

$\hbox{id}$, $(153)(264)$, $(165432)$, $(135)(246)$, $(123456)$, $(14)(25)(36)$

respectively. We can read off the following from this list.

• Since $(165432)$ and $(123456)$ are full-length cycles, $3$ and $5$ are primitive roots modulo $7$.
• $2$ and $4$ have order $3$ modulo $7$, while $6$ has order $2$.

In general, if $p$ is an odd prime and $b$ is a positive integer with order $d$ modulo $p$, then $1/p$ will have period $(b^d-1)/p$ of length $d$ in base $b$. This follows simply from observing that if $b^d-1=mp$ then

$\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots$.

Now let $b>p$ be a primitive root modulo $p$. We shall work in base $b$. Then $1/p$ will have period $L=(b^{p-1}-1)/p$ of length $p-1$. Since the periods of $1/p,2/p,\dots,(p-1)/p$ are $L,2L,\dots,(p-1)L$, all of length $p-1$, which are all powers of some permutation of the digits of $L$, and no two of which are congruent modulo $b$, it follows that the digits of $L$ are all distinct. So we’ve shown the following.

Theorem. If $p$ is an odd prime and $b>p$ is a primitive root modulo $p$, then the base $b$ expansion of $1/p$ has period of length $p-1$ with distinct digits.

Taking $p=7$, $b=10$ gives our previous example. So the prime $7$ in base $10$ is indeed very special, since it is the only prime less than $10$ for which $10$ is a primitive root.

1 Comment

Filed under Number theory