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

        riddles >> putnam exam (pure math) >> Classroom Dilemma in Group Theory
        
(Message started by: ecoist on May 19th, 2006, 3:15pm)
Title: Classroom Dilemma in Group Theory
Post by ecoist on May 19th, 2006, 3:15pm
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?
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 19th, 2006, 7:46pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by ecoist on May 19th, 2006, 8:51pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 20th, 2006, 7:30am
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.
Title: Re: Classroom Dilemma in Group Theory
Post by ecoist on May 20th, 2006, 8:48am
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.
Title: Re: Classroom Dilemma in Group Theory
Post by JP05 on May 20th, 2006, 11:17am
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Michael_Dagg on May 20th, 2006, 11:38am
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 21st, 2006, 12:46pm

on 05/20/06 at 08:48:29, 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.
Title: Re: Classroom Dilemma in Group Theory
Post by ecoist on May 21st, 2006, 2:47pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 22nd, 2006, 3:08pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by JP05 on May 22nd, 2006, 3:19pm

on 05/20/06 at 11:38:53, 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?
Title: Re: Classroom Dilemma in Group Theory
Post by Barukh on May 22nd, 2006, 11:07pm

on 05/22/06 at 15:08:30, Icarus wrote:
I'd have to see a reference to even understand what is meant, here.

LST (http://en.wikipedia.org/wiki/L%C3%B6wenheim-Skolem_theorem)?
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 23rd, 2006, 8:22pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Michael_Dagg on May 24th, 2006, 11:02pm

on 05/22/06 at 15:19:26, JP05 wrote:
Care to elaborate?


Start another thread for this.
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 26th, 2006, 3:44pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 28th, 2006, 5:50pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by ecoist on May 28th, 2006, 7:02pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Eigenray on May 29th, 2006, 7:16am
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Eigenray on May 29th, 2006, 8:02am
Yes.  For example, Zp2 and Zp2, where p is a [link=http://mathworld.wolfram.com/WieferichPrime.html]Wieferich prime[/link], both have (p2-1)/r cycles of length r, where r is the order of 2 mod p (= the order of 2 mod p2).
Title: Re: Classroom Dilemma in Group Theory
Post by ecoist on May 29th, 2006, 9:58am
Wow!  Smallest example for G has order 10932?
Title: Re: Classroom Dilemma in Group Theory
Post by Icarus on May 29th, 2006, 5:42pm
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.
Title: Re: Classroom Dilemma in Group Theory
Post by Eigenray on May 29th, 2006, 7:03pm

on 05/29/06 at 09:58:31, 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.
Title: Re: Classroom Dilemma in Group Theory
Post by Michael_Dagg on Jun 11th, 2006, 4:05pm
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.)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board