wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Lagrange's Theorem
        
(Message started by: Eigenray on Sep 20^th, 2007, 7:29pm)

Title: Lagrange's Theorem
Post by Eigenray on Sep 20^th, 2007, 7:29pm

Everybody knows that if a finite group G has a subgroup of order n, then n divides |G|. For which n is the converse true? That is, classify those integers n for which the following statement is true:

If n divides |G| for some finite group G, then G has a subgroup of order n.

(One direction is well known. The other took me a while!)

An easier problem (though it doesn't seem to help in solving the first one) is to classify the n for which the following holds: if n divides the order of a finite group G, then G has a subgroup of index n.

Title: Re: Lagrange's Theorem
Post by JiNbOtAk on Sep 20^th, 2007, 9:35pm

on 09/20/07 at 19:29:59, Eigenray wrote:

Everybody knows that if a finite group G has a subgroup of order n, then n divides |G|.

Okay, I have to disagree. I for one, do not know that. ( I have trouble understanding it, never mind knowing it )

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 20^th, 2007, 9:55pm

on 09/20/07 at 21:35:42, JiNbOtAk wrote:

Okay, I have to disagree. I for one, do not know that. ( I have trouble understanding it, never mind knowing it )

This fact goes by the name [link=http://en.wikipedia.org/wiki/Lagrange%27s_theorem_%28group_theory%29]Lagrange's Theorem[/link], hence the title of the thread. It is one of the most basic theorems of group theory. Not to discourage you, but if you're not familiar with it, you probably won't make much progress on this problem without significant study. It took me three years ;)

Title: Re: Lagrange's Theorem
Post by Sameer on Sep 20^th, 2007, 10:09pm

on 09/20/07 at 21:55:31, Eigenray wrote:

I was studying and was planning to do research in error coding... which also involves a lot of this subject and I still don't understand it properly... just to take a wild wild guess.. 2^n -1 has to be prime number?

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 20^th, 2007, 10:22pm

on 09/20/07 at 22:09:29, Sameer wrote:

That is sufficient. But it is not necessary. For example, it holds for n=4,8,9, and 11. Why?

Title: Re: Lagrange's Theorem
Post by Sameer on Sep 20^th, 2007, 10:43pm

I have a vague recollection of something involving a number with product of primes and the something about the power of those prime products.. gotta dig up the book and find out..

Title: Re: Lagrange's Theorem
Post by JiNbOtAk on Sep 21^st, 2007, 12:20am

I've heard of Lagrange, just not his theorem. Maybe I should have attended more of my Engineering Maths class back in uni. :P

on 09/20/07 at 22:22:17, Eigenray wrote:

That is sufficient. But it is not necessary.

Now what does this mean ? It's enough, but not needed ? ???

<Note to self : It's never a good idea to break away from one's natural habitat.>

Title: Re: Lagrange's Theorem
Post by towr on Sep 21^st, 2007, 12:43am

on 09/21/07 at 00:20:56, JiNbOtAk wrote:

Now what does this mean ? It's enough, but not needed ?

X sufficient for Y: X -> Y
X necessary for Y: not X -> not Y

Title: Re: Lagrange's Theorem
Post by towr on Sep 21^st, 2007, 12:46am

on 09/20/07 at 22:22:17, Eigenray wrote:

That is sufficient. But it is not necessary. For example, it holds for n=4,8,9, and 11. Why?

I would guess n has to be a power of a single prime.
But then, mathematics isn't a guessing game. I'm thinking about taking algebra next quarter; maybe I'll finally understand all this group theory a bit then. :P

Title: Re: Lagrange's Theorem
Post by ThudanBlunder on Sep 21^st, 2007, 2:46am

on 09/21/07 at 00:46:25, towr wrote:

I'm thinking about taking algebra next quarter;

Now that you have finished your thesis, aren't they kicking you out into the real world? ;)

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 21^st, 2007, 4:02am

on 09/21/07 at 00:46:25, towr wrote:

I would guess n has to be a power of a single prime.

That is exactly correct. Now all you have to do is prove it!

Title: Re: Lagrange's Theorem
Post by Barukh on Sep 21^st, 2007, 4:28am

I want to understand the question. Are we trying to find all n such that for every finite group G, if n | |G|, then G has a subgroup of order n?

Title: Re: Lagrange's Theorem
Post by towr on Sep 21^st, 2007, 4:34am

on 09/21/07 at 02:46:09, ThudanBlunder wrote:

Now that you have finished your thesis, aren't they kicking you out into the real world? ;)

No, not yet. I'm still working on a bachelor's degree in philosophy as well (which I hope to complete within 9 months or so).

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 21^st, 2007, 4:57am

on 09/21/07 at 04:28:46, Barukh wrote:

I want to understand the question. Are we trying to find all n such that for every finite group G, if n | |G|, then G has a subgroup of order n?

Yes that is it. And the same question with 'order n' replaced by 'index n' (although the proofs do not seem to have much in common).

Title: Re: Lagrange's Theorem
Post by ThudanBlunder on Sep 21^st, 2007, 5:04am

on 09/21/07 at 04:34:19, towr wrote:

No, not yet. I'm still working on a bachelor's degree in philosophy as well...

I know Abstract Algebra is useful for philosophy; but Group Theory?
I suppose it could come in useful in the classification of your wacky, anything-is-possible theories which may give your tutors a few grey hairs. :P

Title: Re: Lagrange's Theorem
Post by towr on Sep 21^st, 2007, 6:17am

on 09/21/07 at 05:04:49, ThudanBlunder wrote:

I know Abstract Algebra is useful for philosophy; but Group Theory?

Well, I only need ~30 credits of philosophy, spread over a 60 credit year, so I have time left for some extracurricular courses.

Title: Re: Lagrange's Theorem
Post by Michael_Dagg on Sep 21^st, 2007, 6:57am

on 09/20/07 at 19:29:59, Eigenray wrote:

(One direction is well known. The other took me a while!)

Title: Re: Lagrange's Theorem
Post by Barukh on Sep 21^st, 2007, 7:09am

After inspecting my home math library, seems like it's precisely [hide]the Sylow's theorem[/hide].

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 21^st, 2007, 12:43pm

on 09/21/07 at 07:09:29, Barukh wrote:

After inspecting my home math library, seems like it's precisely [hide]the Sylow's theorem[/hide].

That will only help in one direction. And even then, the statement of the theorem is not quite enough.

Title: Re: Lagrange's Theorem
Post by Barukh on Sep 22^nd, 2007, 3:15am

on 09/21/07 at 12:43:23, Eigenray wrote:

That will only help in one direction.

Correct.

Quote:

And even then, the statement of the theorem is not quite enough.

How come? Sylow theorem states: "If n is a power of a prime, and n | |G|, then G has a subgroup of order n."

::)

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 22^nd, 2007, 6:21am

It guarantees a subgroup of order p^k, where p^k is the largest power of p dividing |G|. But you also need subgroups of order pⁱ for all i < k. (Of course, this may follow from the [link=http://en.wikipedia.org/wiki/Sylow_theorems#Proof_of_the_Sylow_theorems]proof[/link] of the theorem.)

Title: Re: Lagrange's Theorem
Post by Obob on Sep 22^nd, 2007, 7:00am

Let us prove that if a prime power divides the order of a group G, then G has a subgroup of that order.

Since the Sylow theorems guarantee a subgroup of order p^k, it is enough to show that any p-group G has subgroups of each prime power order. Let g be any nonidentity element whatsoever. By Lagrange, the order of g is a prime power. Then some suitable power of g has order p. Now consider G/<g>. By induction on the order of G, G/<g> has subgroups of every order dividing |G/<g>|. But subgroups of G/<g> are in bijective correspondence with subgroups of G containing <g>. So G has subgroups of each prime power order.

Title: Re: Lagrange's Theorem
Post by Barukh on Sep 22^nd, 2007, 9:41am

on 09/22/07 at 06:21:20, Eigenray wrote:

??? This is a statement of the existence of Sylow p-subgroup.

All three books on Abstract Algebra (Johnson, Herstein, Fraleigh) state and prove Sylow's first theorem as I described it before.

Title: Re: Lagrange's Theorem
Post by ecoist on Sep 22^nd, 2007, 3:40pm

I hope this is a partial proof and not swiss cheese.

[hide]Let n be a positive integer not a power of a prime. We construct a group G of order a multiple of n which contains no subgroup of order n. There exists a prime p dividing n such that n=am, where a is a power of p, m is prime to p, and a < m. Let F be the field Z_p extended by a primitive m-th root of unity, say x. Then m divides |F|-1; whence |F|>a. Let V be the additive structure of F and let M=<x>. Then M acts faithfully and irreducibly on V. Let G be the corresponding semi-direct product of M and V. Suppose that H is a
subgroup of G of order n. Then, W = (V intersect H), is a proper subgroup of V and a nontrivial normal subgroup of H. Thus the normalizer of W in G contains a Sylow subgroup of G, for each prime
dividing the order of G. Hence W is normal in G. Therefore, M fixes W, a nontrivial proper subgroup of V, contradicting that M acts irreducibly on V. Hence G has no subgroup of order n.[/hide]

Title: Re: Lagrange's Theorem
Post by Eigenray on Sep 22^nd, 2007, 6:35pm

on 09/22/07 at 07:00:21, Obob wrote:

Now consider G/<g>.

But this is not a group.

on 09/22/07 at 09:41:56, Barukh wrote:

All three books on Abstract Algebra (Johnson, Herstein, Fraleigh) state and prove Sylow's first theorem as I described it before.

The usual statement of Sylow's theorem is about maximal p-subgroups.

on 09/22/07 at 15:40:49, ecoist wrote:

I hope this is a partial proof and not swiss cheese.

That's exactly what I had! Note that [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1156557417]this[/link] is a special case.

Title: Re: Lagrange's Theorem
Post by Obob on Sep 22^nd, 2007, 7:24pm

Yes, Eigenray, you are right. I was trying to make the proof as simple as possible, and ended up making it simpler than possible :).

For a real proof, note that any group of order p^a has nontrivial center. This follows from letting G act on itself by conjugation; then all orbits have order a power of p, and since their sum is the order of G and the identity has an orbit of size 1, there must be other orbits of size 1. Now pick a nonidentity element g from the center. Some power h of g has order p, and <h> is normal. So we can consider G/<h>, and proceed by induction.

Title: Re: Lagrange's Theorem
Post by ecoist on Oct 8^th, 2007, 2:29pm

Solution for Eigenray's easier problem:

Determine those integers n such that if n divides the order of a group G, then G has a subgroup of index n.

[hide]We show that the only such n is n=1. Let n>1. Let G be the alternating group on 2n letters. Then G is a simple group of order greater than n!, and its order is divisible by n. If G had a subgroup of index n, then G would be isomorphic to a subgroup of the symmetric group on n letters, contradicting the fact that G has order larger than n!.[/hide]