wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Group with many trivially intersecting subgroups
        
(Message started by: ecoist on Mar 2^nd, 2006, 2:24pm)

Title: Group with many trivially intersecting subgroups
Post by ecoist on Mar 2^nd, 2006, 2:24pm

Determine all groups G of order n² containing n+1 subroups of order n, any two of which intersect in the identity of G.

Title: Re: Group with many trivially intersecting subgrou
Post by Michael_Dagg on Mar 4^th, 2006, 1:28pm

I guess that the only examples are vector spaces of even dimension over the finite fields F_p.

These are indeed of the form required: if |G| = p^(2n), view G as the cartesian product
H x H of two copies of the additive group of the field H of p^n elements. Then there
is the subgroup { ( 0, h ) ; h in H } and the subgroups { (h, k h ) ; h in H } for each
fixed k in the field H.

One might think that more general groups G = H x H would apply, but I don't know
what other possibilities exist for H besides cyclic simple groups. The problem would
be to enumerate all the subgroups of order |H|. Among them are: the group { 1 } x H, and
all the groups { (x, phi(x)) ; x in H } for each endomorphism phi of H. However, in order
for these to be disjoint, we would have to choose the phi's so that

phi(x) = phi'(x) ==> ( phi=phi' or x = 1 ).

In particular, for every two non-identity elements x and y there have to be endomorphisms
carrying x to y. That means that all these elements have to have the same order, so H is a
p-group (of exponent p). But every endomorphism of a p-group carries the Frattini subgroup
back to within itself, so there would be no such phi if x is in the Frattini subgroup but not y.
This this means the Frattini group is trivial, i.e. H is an elementary-abelian p-group. As I
showed in the previous paragraph, for such an H, G = H x H always meets the condition for
some selection of subgroups of order |H|.

So it looks like "group squares" H x H only work with H is elementary abelian. However,
I do not claim that my list of all subgroups of order |H| in H x H is complete; it could
be that there are others, and maybe including those others in the list of subgroups of order|H|
would allow you to find |H|+1 of these subgroups which are disjoint.

At this moment I can only guess that the condition implies that G has to be a square H x H in
the first place. It's a sort of unusual condition.

How did this problem arise?

Title: Re: Group with many trivially intersecting subgrou
Post by ecoist on Mar 4^th, 2006, 1:48pm

Quote:

How did this problem arise?

I was trying to use group theory to construct orthogonal latin squares. The existence of such a group insures the existence of a complete set of mutually orthogonal latin squares of order n, or equivalently, the existence of a projective plane of order n.

As your analysis suggests, this group theory approach yields nothing new on mutually orthogonal latin squares.

Title: Re: Group with many trivially intersecting subgrou
Post by Michael_Dagg on Mar 7^th, 2006, 4:29pm

That explains why G has to be square.

If this had been posted as a latin squares problem I would have likely not bitten.

If you know group theory, you can take my previous remarks and compose a construction.

Title: Re: Group with many trivially intersecting subgrou
Post by ecoist on Mar 7^th, 2006, 5:20pm

Quote:

If you know group theory, you can take my previous remarks and compose a construction.

One solver used his knowledge of geometry to partially solve the problem, but no knowledge of combinatorics or geometry is needed to solve this problem completely.

You know group theory apparently, so why not complete your analysis? Or do you expect your solution to be too long to bother with? I hope you reconsider posting a proof. I enjoy seeing proofs different from mine.

Title: Re: Group with many trivially intersecting subgrou
Post by Michael_Dagg on Mar 8^th, 2006, 2:55pm

This is likely more useful than anything else I can offer:

MR1829097 (2002g:05036)
Colbourn, Charles J.(1-VT-C); Dinitz, Jeffrey H.(1-VT-C)
Mutually orthogonal Latin squares: a brief survey of constructions.
(English. English summary)
ÿÿÿðE-ñw7Ç`

Title: <ÿÿàÿÿü
Post by on

Title: ���€�&
Post by on

This post was corrupted, and has now been reproduced in reply 12. --towr

Title: Re: Group with many trivially intersecting subgrou
Post by Michael_Dagg on Oct 25^th, 2006, 9:11am

Icarus, notice that ecoist's solution has gone corrupt -- well, sort of.

There are lots of nice solutions on this forum that would be a pity to loose.

Title: Re: Group with many trivially intersecting subgrou
Post by Icarus on Oct 25^th, 2006, 7:25pm

Indeed. Unfortunately, I don't have any more ability to correct this than you do. I've sent an E-mail to William Wu about it. I don't know if he'll be able to do anything either.

Title: Re: Group with many trivially intersecting subgrou
Post by william wu on Oct 25^th, 2006, 9:46pm

Hello,

Allegedly around 1% of data hosted on OCF was lost in the recent OCF server outage, when the hard drives failed. Please let me know of any other instances of lost/corrupted data, and I will try to work with the staff to recover it if possible.

It appears the forum is much faster now! :D

Title: Re: Group with many trivially intersecting subgrou
Post by towr on Oct 26^th, 2006, 1:06am

on 10/25/06 at 21:46:51, william wu wrote:

It appears the forum is much faster now! :D

Appearances may be deceiving. It comes and goes; the forum was even unreachable at timed yesterday.

Quote:

Please let me know of any other instances of lost/corrupted data, and I will try to work with the staff to recover it if possible.

alien's account has been lost (I emailed you about it, but maybe that got lost too)
And posts seem to be disappearing occasionally.

Title: Re: Group with many trivially intersecting subgrou
Post by ecoist on Oct 7^th, 2007, 10:37am

Finally getting around to rewriting the corrupted post solving this problem!

Let G be a group of order n² with n+1 subgroups of order n with pairwise trivial intersection. Then G is an elementary abelian p-group.

Proof. The integer n is greater than 1 because a group of order 1 cannot have two subgroups. Also, every nonidentity element of G belongs to a unique one of the n+1 given subgroups of order n. Let A and B be any two of the given subgroups of order n. Then G=AB. We show A is normal in G. Suppose that, for some x in G, x^-1ax lies outside A. Then, without loss we may assume x^-1ax=b in B, and that x=a*b*, with a* in A and b* in B. But then

b=x^-1ax=b*^-1a*^-1aa*b*;

so

b*bb*^-1=a*^-1aa*=1,

because A and B have trivial intersection. Hence b=1, contradiction. Therefore, A is normal in G; and so, too, are all of the given subgroups of order n. Next we show that G is abelian. So far, we know that G is the direct product of A and B. Let x be any element of G outside of both A and B. Then x belongs to a unique one, say C, of the given subgroups of order n. Hence every element of C commutes with every element of both A and B (because G is the direct product of both C and A and C and B), whence x is in the center of G. Switching roles of A, B, and C, it follows that G is abelian. Finally, we show that every nonidentity element of G must have the same prime order. Let a be an element of prime order p in A and let b be any nonidentity element of B. Then ab lies outside both A and B and hence lies in a unique one of the given subgroups of order n, say, without loss, C. Now C determines an isomorphism from A to B defined by, f(a) is the unique element of B such that af(a) lies in C. It follows that every nonidentity element of A has order p. Hence A and B are elementary abelian p-groups; and so G is an elementary abelian p-group of order p^2k, for some prime p and positive integer k.