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.

Leave a comment

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.

Leave a comment

Filed under Algebra

Hilbert’s nullstellensatz

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

What's new

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

Leave a comment

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<b^d 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.

Leave a comment

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