Author |
Topic: Classroom Dilemma in Group Theory (Read 1211 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Classroom Dilemma in Group Theory
« on: May 19th, 2006, 3:15pm » |
 Quote  Modify
|
In an undergraduate course in abstract algebra, a student complained about his grade on a homework problem. His professor said, "You proved only that your map preserves squares". The student countered, "But the groups are abelian; isn't that enough proof?" The professor said "No.", but he wasn't sure. Question:
Do there exist non-isomorphic finite abelian groups G and H together with a 1-1 mapping f from G onto H satisfying f(g2)=(f(g))2, for all g in G?
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #1 on: May 19th, 2006, 7:46pm » |
Quote Modify
|
As an aside, the professor was correct in his grading: if your audience is not clear about a step in your proof, then your proof was insufficient - regardless of whether or not the step was correct. The whole point of a proof is to convince your audience of the truth of the theorem. If your audience is not clear on each step, then you have failed to convince them.
And the fact that the student could not point out to his professor why it is that his step was correct, shows that the student was not sure of it either. While it is somewhat forgivable to lose your audience on occasion (after all you can never be totally sure of what they know), it is unforgivable in a proof to rely on something you aren't clear on yourself. This is how we get such embarassing results as the "the Reals are denumerable" proof to be found in the General/whatever forum.
|
| « Last Edit: May 19th, 2006, 8:05pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Classroom Dilemma in Group Theory
« Reply #2 on: May 19th, 2006, 8:51pm » |
Quote Modify
|
If I am not mistaken, there is a denumerable model of the reals!
Hmm. I've often had a terrible time understanding some of John Thompson's proofs in group theory because he leaves so many details to the reader, but I wouldn't dare say those proofs are "insufficient". On the other hand, the student admitted that he couldn't fill in the gap in his proof, so in this case I agree that his grade was correct.
|
| « Last Edit: May 19th, 2006, 9:07pm by ecoist » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #3 on: May 20th, 2006, 7:30am » |
Quote Modify
|
You are mistaken. The reals are not denumerable, and therefore no true model of them can be denumerable, either.
As for John Thompson's proofs, his point is not to convince you of the truth of his theorems so much as to train you in how to prove them yourself. In this case, it is entirely appropriate for him to make you figure things out on your own.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Classroom Dilemma in Group Theory
« Reply #4 on: May 20th, 2006, 8:48am » |
Quote Modify
|
You will find some wonderful and bizaare things in the field of mathematical logic. The model is denumerable; the reals are not. May have something to do with metamathematics versus mathematics, I forget.
You a mind reader, Icarus? I always thought a proof was meant to reveal the truth, not to perform as an intellectual bar bell.
|
|
IP Logged |
|
|
|
JP05
Guest
|
|
Re: Classroom Dilemma in Group Theory
« Reply #5 on: May 20th, 2006, 11:17am » |
Quote Modify
 Remove
|
Interesting discussion; I don't have the answer and don't quite understand if the problem question is actually related to the stated dilemma. But since M_D seems to switch up between complex analysis and group theory, one can ponder how to bate him for this discussion (only kidding). Just occurred to me that it would be nice if there was group theory in complex analysis but my guess is that some how one would be working with elements that are modulus of z's.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Classroom Dilemma in Group Theory
« Reply #6 on: May 20th, 2006, 11:38am » |
Quote Modify
|
I'd prefer the problem question over the debate (which I'll swing at if no one else does).
Incidentally, there's much opportunity to do group theory in complex analysis, especially on
the subgroups of the Moebius group PSL(2,C) which acts on the upper-half-plane.
|
| « Last Edit: May 20th, 2006, 3:14pm by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #7 on: May 21st, 2006, 12:46pm » |
Quote Modify
|
on May 20th, 2006, 8:48am, ecoist wrote:| The model is denumerable; the reals are not. |
|
Perhaps we have different definitions for what "denumerability of the model" would mean. By my definition, a "denumerable model" for the real numbers would mean that the real numbers were paradoxical, and would spell the end of mathematics and logic as we know it.
The only other possible meanings I can think of for "denumerable model" are ones satisfied by all models, as no mathematical theory can have more than a denumerable number of formal objects and theorems.
Quote:| You a mind reader, Icarus? I always thought a proof was meant to reveal the truth, not to perform as an intellectual bar bell. |
|
I am not familiar with John Thompson, and am assuming you are refering to a text book he has published. Teaching how to prove things is part of what textbooks are all about.
Anyway, I agree with Michael. I didn't intend to stir up a contraversy with my comments.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Classroom Dilemma in Group Theory
« Reply #8 on: May 21st, 2006, 2:47pm » |
Quote Modify
|
I meant the usual definition of "denumerable". The set of objects modeling the reals has the cardinality of the set of integers. Presumably, the model behaves like the reals but, of course, cannot be isomorphic to the reals. "Behaves like" may be a theorem of metamathematics, outside the scope of theorems deducible from axioms for the reals. I don't understand the intricacies of mathematical logic, so I am unable to resolve the understandable incredulity arising from this claim, nor can I provide a reference.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #9 on: May 22nd, 2006, 3:08pm » |
Quote Modify
|
I'd have to see a reference to even understand what is meant, here.
To have a cardinality, the model must consist of a set (or very similar concept, such as a class). For it to be a model of the reals, it and its operations must satisfy the axioms of the set of real numbers. By Cantor's theorems, any set with operations that satisfy the axioms of the Real numbers cannot be denumerable.
Therefore, either this model is built within an inconsistent theory, or else what is denumerable about it is something other than its set.
For example, the set of constructible elements of the model (that is, the set of all elements that can be uniquely identified by some logical statement) may be what is denumerable. But this is true in all mathematical theories: Since any logical statement is a finite list of symbols from a finite set of primatives, there are only a countable number of statements, and so at most a countable number of constructible objects.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JP05
Guest
|
|
Re: Classroom Dilemma in Group Theory
« Reply #10 on: May 22nd, 2006, 3:19pm » |
Quote Modify
Remove
|
on May 20th, 2006, 11:38am, Michael_Dagg wrote:| ... especially on the subgroups of the Moebius group PSL(2,C) which acts on the upper-half-plane. |
|
I love shooting myself in the foot. Care to elaborate?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Classroom Dilemma in Group Theory
« Reply #11 on: May 22nd, 2006, 11:07pm » |
Quote Modify
|
on May 22nd, 2006, 3:08pm, Icarus wrote:| I'd have to see a reference to even understand what is meant, here. |
|
LST?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #12 on: May 23rd, 2006, 8:22pm » |
Quote Modify
|
That may well be what ecoist was thinking of, but note that the countable sub-models demanded by LST satisfy all first-order sentences, but since the completeness axiom is a second-order sentence, it is not satisfied. Indeed, the article points out that no countable model can satisfy the completeness axiom as well as the other axioms of the Real numbers, since this would mean it was not countable.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Classroom Dilemma in Group Theory
« Reply #13 on: May 24th, 2006, 11:02pm » |
Quote Modify
|
on May 22nd, 2006, 3:19pm, JP05 wrote:
Start another thread for this.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #14 on: May 26th, 2006, 3:44pm » |
Quote Modify
|
In order to set this thread back on track, I am going to give my rather incomplete thoughts on the matter.
First, since the groups are abelian, I am going to use additive notation instead the multiplicative notation that ecoist has used. This certainly makes the notation nicer under the limitations of this forum. The key condition becomes
f(2x) = 2f(x). Clearly, this extends to f(2kx) = 2kf(x), for all k >= 0.
Note that since f is bijective, it has an inverse which also satisfies f-1(2x) = 2f-1(x). Hence anything we can deduce about f is also true for f-1.
f(0) = f(2*0) = 2f(0), so f(0) = 0, and f-1(0) = 0.
Also,
Any finite abelian group is (if I recall correctly) uniquely isomophic to Zp1^k1 + Zp2^k2 + ... + Zpn^kn, where the pi are all prime and the ki > 0.
I have more, but am out of time.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #15 on: May 28th, 2006, 5:50pm » |
Quote Modify
|
Between lack of time and a web connection that keeps konking out, I've had a hard time getting back to this.
In the meantime, I have decided to limit my remarks to one more observation:
Even when G and H are isomorphic, f is not necessarily an isomorphism. Consider f : Z7 --> Z7 defined by:
f(0) = 0
f(1) = 3
f(2) = 6
f(3) = 1
f(4) = 5
f(5) = 4
f(6) = 2
It is easy to verify that f satisfies the doubling condition, but f is not a morphism, since f(1+2) = 1, while f(1) + f(2) = 2.
However, ecoist has cleverly phrased his problem so as to make this insufficient to disprove it.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Classroom Dilemma in Group Theory
« Reply #16 on: May 28th, 2006, 7:02pm » |
Quote Modify
|
I was not trying to be clever. Just relating a classroom incident. Icarus has shown that, in some cases, the automorphism group of a finite abelian group can be extended non-trivially to its "doubling group" (the set of all doubling 1-1 maps of a finite group is a group under function composition). Using the example Icarus gives, the doubling group for Z7 contains the automorphism (132645) and the doubling map (13)(26)(45), making the doubling group of Z7 of order at least 18. Icarus's observation does suggest that there might be finite abelian groups G and H such that there is a doubling map for G which is not an isomorphism of G yet it corresponds to an automorphism of H.
Icarus's remarks about the properties of maps preserving doubling leads to the fact that, if G and H are finite abelian 2-groups related by a 1-1 doubling map, then both have the same number of elements of the same order. This is trivially true for groups of prime order. Maybe the same is true for other finite abelian groups as well. I don't know the full solution of the posted problem.
|
| « Last Edit: May 28th, 2006, 9:08pm by ecoist » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Classroom Dilemma in Group Theory
« Reply #17 on: May 29th, 2006, 7:16am » |
Quote Modify
|
Some thoughts:
Given an abelian group G, associate a graph G' whose vertices are the elements of G, and whose directed edges are (x, 2x) for each x in G. Then there is a doubling bijection between G and H iff G' and H' are isomorphic (and the "doubling group" of G is just Aut(G')).
Given G', we can recover the Sylow 2-subgroup of G, as follows. Let Ki be the kernel of multiplication by 2i in G; this is the set of vertices within a distance i of 0, so is recoverable from G'. If the 2-torsion of G is [prod] (Z2i)ni,
then
ki:= log2|Ki| = n1 + 2n2+ ... + (i-1)ni-1 + i(ni+....),
so we can inductively recover the ni: n1=2k1-k2, n2=3k1-k3-2n1, ...
Moreover, if G = PxH, where P is a 2-group and |H| is odd, then H' is the subgraph consisting of the cycles of G'. So if there are non-isomorphic groups with isomorphic graphs, then we can find a counterexample among groups of odd order.
If |G| is odd, then G' is a union of cycles, so can be described up to isomorphism by the numbers Gi, the number of vertices in G' contained in a cycle of length i. Here is how to compute these for G = [prod] Zp_ik_i:
First, for an odd prime p, let Gk=Zpk. Then G0 is trivial, and
Gki = Gk-1i, except Gkr = Gk-1r + phi(pk),
where r is the order of 2 mod pk. Secondly,
(GxH)k = [sum]lcm(i,j)=k Gi Hj.
|
| « Last Edit: May 29th, 2006, 7:20am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Classroom Dilemma in Group Theory
« Reply #18 on: May 29th, 2006, 8:02am » |
Quote Modify
|
Yes. For example, Zp2 and Zp2, where p is a Wieferich prime, both have (p2-1)/r cycles of length r, where r is the order of 2 mod p (= the order of 2 mod p2).
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Classroom Dilemma in Group Theory
« Reply #19 on: May 29th, 2006, 9:58am » |
Quote Modify
|
Wow! Smallest example for G has order 10932?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Classroom Dilemma in Group Theory
« Reply #20 on: May 29th, 2006, 5:42pm » |
Quote Modify
|
Even if it is, it is probably just another example of the "Law of Small Numbers", which states that many properties are true for small numbers simply because small numbers do not provide enough freedom for things to go wrong.
Once you get into large enough values, things go wrong nearly all the time.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Classroom Dilemma in Group Theory
« Reply #21 on: May 29th, 2006, 7:03pm » |
Quote Modify
|
on May 29th, 2006, 9:58am, ecoist wrote:| Wow! Smallest example for G has order 10932? |
|
Yes.
Call two odd-order abelian groups G and H 2-isomorphic (G =2 H) if the graphs G', H' are isomorphic, i.e., Gk=Hk for all k, where (slight change in notation) Gk is the number of vertices of G' in a cycle of length k.
Claim 1: If GxA =2 HxA for some abelian group A, then G =2 H.
It follows that any 2-isomorphic groups are of the form GxA, HxA, where G =2 H are minimal in the sense that if
G = [prod] (Z(pi))(mp,i); H = [prod] (Z(pi))(np,i),
then for each p,i, either mp,i=0 or np,i=0.
Proof of claim: WLOG, we may suppose A = Z(pk) for some p,k. If rk is the order of 2 mod pk, then rk = pmax(0,k-t)r1, where t is maximal wrt rt=r1=r. Thus Ak is non-zero only if k=1 or k=pbr for some i. So suppose (GxA)k = (HxA)k, i.e.,
(*) Gk + [sum][i,pbr]=k GiA(pbr) = Hk + [sum][i,pbr]=k HiA(pbr)
for all k. Note that if r doesn't divide k, (*) gives Gk = Hk immediately. If r|k, we show Gk=Hk, by induction on the smallest a such that par doesn't divide k.
So suppose pa+1r doesn't divide k, but par | k. By induction, assume that Gi=Hi whenever par doesn't divide i, so we may subtract from both sides of (*) the terms for which par doesn't divide i. The remaining sum is over all i,b, such that [i,pbr]=k and par | i; it follows from our assumptions that the only such terms are for b<a and i=k. Thus
Gk(1+Ar+...+Apar) = Hk(1+Ar+...+Apar),
and Gk=Hk, as claimed.
Claim 2: If G =2 H are minimal, then the largest prime p dividing |G|=|H| is a Wieferich prime.
Proof: Recall that for any prime power qk, (Z(qk))t is non-zero iff t=rq,s is the order of 2 mod qs for some 0<s<k.
Let i,j be largest with mp,i, np,j non-zero. By minimality and WLOG, i<j. Suppose p is not Wieferich, i.e., r2 > r1; then rk = pk-1r1 for all k. Hence (Zpk)t=0 if k<j and pj-1|t. And if q < p, then (Zqk)t=0 if p|t, since rq,s | phi(qs) is never divisible by p. It follows that Gt=0 whenever pj-1|t. But this contradicts Hr_j > (Z(pj))r_j = phi(pj) > 0.
Now suppose G =2 H are non-isomorphic groups of order n < 10932; by claim 1 we may suppose they are minimal. Then they are non-trivial, so by claim 2, there's some Wieferich prime p | n. Since p>1093, mp,i=np,i=0 for i>1, so mp,1=np,1>0, contradicting minimality.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Classroom Dilemma in Group Theory
« Reply #22 on: Jun 11th, 2006, 4:05pm » |
Quote Modify
|
Here is some commentary:
So you want to have a one-to-one correspondence between two abelian groups, which
commutes with the squaring operation. I don't think that's too hard -- you just have to
have two different groups where the squaring operation breaks the sets up into the
same orbit structure. (It's a little easier to think about this when the groups have odd
order so that squaring is an invertible map, i.e. it really is a group operation on the sets
G and H.)
Actually since the groups are abelian, it's more natural to write this out additively. You
want f : G --> H with f(2x) = 2 f(x).
So suppose you look at (Z/p)^2 and Z/(p^2) where p = 1093. It has already been mentioned
that this is the smallest prime for which 2^p = 2 mod p^2 (the only other such prime known
is p = 3511, although it has been conjectured that there are infinitely more such). What you can
show is that the order of 2 mod p is 364 = 1092/3 (i.e. 2 is a cube but not a higher nontrivial
power in Z/p); equivalently, 2^k = 1 mod p iff k is a multiple of 364. But it's also true that 2 is
of order 364 mod p^2. Thus when performing the doubling operation on either (Z/p)^2 or Z/(p^2)
we break the groups into orbits: the identity element is in an orbit by itself, and every other element
is in an orbit of length 364.
So have f send the identity to the identity, and then beyond that, pick an arbitrary pairing of the
(1093^2-1)/364 orbits in one group with the orbits in the other group; for each pair of orbits pick
arbitrary representatives of each orbit and have f send one to the other, and then extend f to
the rest of the orbits by f(2x)=2f(x).
I know this example is too large to write out fully. You can work out a similar example by hand if you
replace the doubling function by the tripling function: Z/121 and (Z/11)^2 are non-isomorphic but
tripling breaks each of these up into the identity element plus 24 orbits of 5 elements each.
Apart from the identity elements, the orbits are represented by these elements of Z/121:
1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17,
19, 20, 22, 25, 26, 31, 34, 35, 38, 40, 61,
67, 76
and these elements of (Z/11)^2 : (i,1) (i=0,...,10), (i,2), (i=0,...,10), and (1,0) and (2,0). That is, you
can define
f(1)=(0,1), f(2)=(1,1), f(4)=(2,1), f(5)=(3,1), f(7)=(4,1), ...,
f(19)=(0,2), f(20)=(1,2), f(22)=(2,2), ...,
f(67)=(1,0), f(76)=(2,0)
and then complete the mapping f by decreeing f(3x) = 3f(x) for all x. So this one is doable because the
congruence 3^p = 3 mod p^2 has a small solution (p=11) whereas 2^p = 2 mod p^2 does not.
As Eigenray pointed out, the keyword here is "Weierfrich prime", modulo spelling. (These
were important a hundred years ago in the proposed proofs of Fermat's Last Theorem.)
|
| « Last Edit: Jun 12th, 2006, 2:26pm by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print