Author |
Topic: Lagrange's Theorem (Read 851 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Lagrange's Theorem
« on: Sep 20th, 2007, 7:29pm » |
 Quote  Modify
|
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.
|
| « Last Edit: Sep 21st, 2007, 4:59am by Eigenray » |
 IP Logged |
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: Lagrange's Theorem
« Reply #1 on: Sep 20th, 2007, 9:35pm » |
Quote Modify
|
on Sep 20th, 2007, 7:29pm, 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 )
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #2 on: Sep 20th, 2007, 9:55pm » |
Quote Modify
|
on Sep 20th, 2007, 9:35pm, 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 Lagrange's Theorem, 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 
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Lagrange's Theorem
« Reply #3 on: Sep 20th, 2007, 10:09pm » |
Quote Modify
|
on Sep 20th, 2007, 9:55pm, Eigenray wrote:
This fact goes by the name Lagrange's Theorem, 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 |
|
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?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #4 on: Sep 20th, 2007, 10:22pm » |
Quote Modify
|
on Sep 20th, 2007, 10:09pm, Sameer 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? |
|
That is sufficient. But it is not necessary. For example, it holds for n=4,8,9, and 11. Why?
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Lagrange's Theorem
« Reply #5 on: Sep 20th, 2007, 10:43pm » |
Quote Modify
|
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..
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: Lagrange's Theorem
« Reply #6 on: Sep 21st, 2007, 12:20am » |
Quote Modify
|
I've heard of Lagrange, just not his theorem. Maybe I should have attended more of my Engineering Maths class back in uni. 
on Sep 20th, 2007, 10:22pm, 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.>
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Lagrange's Theorem
« Reply #7 on: Sep 21st, 2007, 12:43am » |
Quote Modify
|
on Sep 21st, 2007, 12:20am, 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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Lagrange's Theorem
« Reply #8 on: Sep 21st, 2007, 12:46am » |
Quote Modify
|
on Sep 20th, 2007, 10:22pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Lagrange's Theorem
« Reply #9 on: Sep 21st, 2007, 2:46am » |
Quote Modify
|
on Sep 21st, 2007, 12:46am, 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?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #10 on: Sep 21st, 2007, 4:02am » |
Quote Modify
|
on Sep 21st, 2007, 12:46am, 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!
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Lagrange's Theorem
« Reply #11 on: Sep 21st, 2007, 4:28am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Lagrange's Theorem
« Reply #12 on: Sep 21st, 2007, 4:34am » |
Quote Modify
|
on Sep 21st, 2007, 2:46am, 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #13 on: Sep 21st, 2007, 4:57am » |
Quote Modify
|
on Sep 21st, 2007, 4:28am, 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).
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Lagrange's Theorem
« Reply #14 on: Sep 21st, 2007, 5:04am » |
Quote Modify
|
on Sep 21st, 2007, 4:34am, 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.
|
| « Last Edit: Sep 21st, 2007, 5:08am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Lagrange's Theorem
« Reply #15 on: Sep 21st, 2007, 6:17am » |
Quote Modify
|
on Sep 21st, 2007, 5:04am, 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.
|
| « Last Edit: Sep 21st, 2007, 6:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Lagrange's Theorem
« Reply #16 on: Sep 21st, 2007, 6:57am » |
Quote Modify
|
on Sep 20th, 2007, 7:29pm, Eigenray wrote:
(One direction is well known. The other took me a while!)
|
|
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Lagrange's Theorem
« Reply #17 on: Sep 21st, 2007, 7:09am » |
Quote Modify
|
After inspecting my home math library, seems like it's precisely the Sylow's theorem.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #18 on: Sep 21st, 2007, 12:43pm » |
Quote Modify
|
on Sep 21st, 2007, 7:09am, Barukh wrote:| After inspecting my home math library, seems like it's precisely the Sylow's theorem. |
|
That will only help in one direction. And even then, the statement of the theorem is not quite enough.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Lagrange's Theorem
« Reply #19 on: Sep 22nd, 2007, 3:15am » |
Quote Modify
|
on Sep 21st, 2007, 12:43pm, 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."
|
| « Last Edit: Sep 22nd, 2007, 3:15am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #20 on: Sep 22nd, 2007, 6:21am » |
Quote Modify
|
It guarantees a subgroup of order pk, where pk is the largest power of p dividing |G|. But you also need subgroups of order pi for all i < k. (Of course, this may follow from the proof of the theorem.)
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Lagrange's Theorem
« Reply #21 on: Sep 22nd, 2007, 7:00am » |
Quote Modify
|
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 pk, 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Lagrange's Theorem
« Reply #22 on: Sep 22nd, 2007, 9:41am » |
Quote Modify
|
on Sep 22nd, 2007, 6:21am, Eigenray wrote:| It guarantees a subgroup of order pk, where pk is the largest power of p dividing |G|. But you also need subgroups of order pi for all i < k. (Of course, this may follow from the proof of the theorem.) |
|
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.
|
| « Last Edit: Sep 22nd, 2007, 9:42am by Barukh » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Lagrange's Theorem
« Reply #23 on: Sep 22nd, 2007, 3:40pm » |
Quote Modify
|
I hope this is a partial proof and not swiss cheese.
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 Zp 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.
|
| « Last Edit: Sep 22nd, 2007, 3:43pm by ecoist » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Lagrange's Theorem
« Reply #24 on: Sep 22nd, 2007, 6:35pm » |
Quote Modify
|
on Sep 22nd, 2007, 7:00am, Obob wrote:
But this is not a group.
on Sep 22nd, 2007, 9:41am, 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 Sep 22nd, 2007, 3:40pm, ecoist wrote:| I hope this is a partial proof and not swiss cheese. |
|
That's exactly what I had! Note that this is a special case.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print