Newsgroups:     sci.math
From:           uphya159@unibi.uni-bielefeld.de (0118)
Subject:        A Word-Problem
Date:           Sun, 9 Aug 92 17:24:11 GMT
Organization:   Universitaet Bielefeld

A Word-Problem:

Let  G = < a,b | aabb=baba, bbaa=abab >  the free group of
two generators a and b with the two relations aabb=baba and bbaa=abab.

Show that  aaabbb unequal bababa.

I've tried all homomorphisms from G to S10 without success.
(e.g.  a->(123), b->(142)  shows  ab unequal ba  but  aaabbb=bababa)

Torsten Sillke
(posted by Udo Sprute,  uphya159@unibi.HRZ.Uni-Bielefeld.DE)

From:           sibley@math.psu.edu (David Sibley)
Newsgroups:     sci.math
Subject:        Re: A Word-Problem
Date:           11 Aug 92 15:15:45 GMT
Reply-To:       sibley@math.psu.edu
Organization:   Dept. of Mathematics, Penn State University

In article 26212@unibi.uni-bielefeld.de, uphya159@unibi.uni-bielefeld.de (0118) writes:
>A Word-Problem:
>
>Let  G = < a,b | aabb=baba, bbaa=abab >  the free group of
>two generators a and b with the two relations aabb=baba and bbaa=abab.
>
>Show that  aaabbb unequal bababa.

Here are two permutations and a verification by GAP.

gap> A;
( 1, 3, 6,16)( 2,20,22,27,11,13,15,23, 5, 7,12,31)( 4,10,17, 9)
( 8,30,32,18,21,26,28,29,14,19,24,25)
gap> B;
( 1,28,22,17,15,14, 6, 8, 5, 4, 2,32)( 3,19,31,10,27,25,16,18,13, 9, 7,26)
(11,21,12,24)(20,29,23,30)
gap> A^2*B^2=(B*A)^2;
true
gap> B^2*A^2=(A*B)^2;
true
gap> A^3*B^3=(B*A)^3;
false

David Sibley
sibley@math.psu.edu

From:           elkies@ramanujan.harvard.edu (Noam Elkies)
Newsgroups:     sci.math
Subject:        Re: A Word-Problem
Date:           11 Aug 92 17:27:30 GMT
Organization:   Harvard Math Department

In article <Bstrq9.MKr@cs.psu.edu> sibley@math.psu.edu writes:
:In article 26212@unibi.uni-bielefeld.de,
:uphya159@unibi.uni-bielefeld.de (0118) writes:
:>A Word-Problem:
:>
:>Let  G = < a,b | aabb=baba, bbaa=abab >  the free group of
:>two generators a and b with the two relations aabb=baba and bbaa=abab.
:>
:>Show that  aaabbb unequal bababa.
:
:Here are two permutations and a verification by GAP.
:
:gap> A;
:( 1, 3, 6,16)( 2,20,22,27,11,13,15,23, 5, 7,12,31)( 4,10,17, 9)
:( 8,30,32,18,21,26,28,29,14,19,24,25)
:gap> B;
:( 1,28,22,17,15,14, 6, 8, 5, 4, 2,32)( 3,19,31,10,27,25,16,18,13, 9, 7,26)
:(11,21,12,24)(20,29,23,30)
:gap> A^2*B^2=(B*A)^2;
:true
:gap> B^2*A^2=(A*B)^2;
:true
:gap> A^3*B^3=(B*A)^3;
:false

...which suggests several questions:

1) Where does this specific word-problem come from?  Perhaps trying to
prove that no rectangle of odd area can be tiled with L-triominos if
only two orientations (related by 180-degree rotation) are allowed?

2) Now that we have a group-theoretic proof, is there an elementary
proof of the same result about tilings?  Note that if all four orientations
(or even three of the four orientations) are allowed then a 5x9 rectangle
can be tiled with L-triominos.

3) How did David Sibley find the two premutations above?  Could they
be affine linear transformations on a 5-dimensional vector space over
Z/2?  The cycle structures (4)(4)(12)(12) of both A and B are compatible
with this guess.

--Noam D. Elkies (elkies@zariski.harvard.edu)
  Dept. of Mathematics, Harvard University

Newsgroups:     sci.math
From:           cgodsil@watserv1.uwaterloo.ca (C. Godsil - C and O)
Subject:        Re: A Word-Problem
Organization:   University of Waterloo
Date:           Wed, 12 Aug 1992 20:27:15 GMT

In article <1992Aug9.172411.26212@unibi.uni-bielefeld.de> uphya159@unibi.uni-bielefeld.de (0118) writes:
>A Word-Problem:
>
>Let  G = < a,b | aabb=baba, bbaa=abab >  the free group of
>two generators a and b with the two relations aabb=baba and bbaa=abab.
>
>Show that  aaabbb unequal bababa.
>
>I've tried all homomorphisms from G to S10 without success.
>(e.g.  a->(123), b->(142)  shows  ab unequal ba  but  aaabbb=bababa)
>
>Torsten Sillke
>(posted by Udo Sprute,  uphya159@unibi.HRZ.Uni-Bielefeld.DE)

The group  G = < a, b : a^2*b^2=(b*a)^2, b^2*a^2=(a*b)^2 >  is soluble:

Let  K  be the subgroup generated by  p = a*b  and  q = b*a .
This subgroup is normal,  with quotient  G/K  cyclic
(NB:  p^a = q,  p^b = p^-1*q^2,  q^a = q^-1*p^2,  &  q^b = p ).

Let  L  be the subgroup generated by  u = p^3  and  v = q^3 .
This subgroup too is normal (with  u^a = v = u^b  and  v^a = u = v^b ),
and also Abelian (since in fact both p and q centralize both u and v).

Further, the quotient  K/L  is a homomorphic image of the (3,3,3) triangle
group  < p, q : p^3 = q^3 = (p*q)^3 = 1 >,  which is Abelian-by-cyclic,
and is therefore soluble.

Now since  G/K is cyclic,  K/L is soluble,  and  L is Abelian, 
it follows that  G itself is soluble.

Here's a finite matrix representation of  G  over GF(2):

  A = [ 0  1  0  0  0 ]            B = [ 1  0  1  1  0 ]
      [ 0  0  1  0  0 ]                [ 0  0  1  0  0 ]
      [ 1  0  0  0  0 ]                [ 1  0  0  0  0 ]
      [ 0  0  0  1  0 ]                [ 1  1  1  0  0 ]
      [ 0  0  0  0  1 ]                [ 0  0  0  0  1 ]

  A^3*B^3 = [ 0  1  1  1  0 ]      B^3*A^3 = [ 0  1  1  1  0 ]
            [ 1  0  1  1  0 ]                [ 1  0  1  1  0 ]
            [ 1  1  0  1  0 ]                [ 1  1  0  1  0 ]
            [ 1  1  1  0  0 ]                [ 1  1  1  0  0 ]
            [ 0  0  0  1  1 ]                [ 1  1  1  0  1 ]

  (A^3*B^3)^2 = (B^3*A^3)^2 = [ 1  0  0  0  0 ]
                              [ 0  1  0  0  0 ]
                              [ 0  0  1  0  0 ]
                              [ 0  0  0  1  0 ] 
                              [ 1  1  1  1  1 ] 
							  
These matrices generate a factor group of order 96, with centre of order 2,
and clearly isomorphic to a subgroup of AGL(4,2). 

Marston Conder  (marston@dibbler.uwaterloo.ca)        12 August 1992

Newsgroups:     sci.math
From:           umatf071@unibi.uni-bielefeld.de (0105)
Subject:        Re: A Word-Problem
Date:           Thu, 13 Aug 92 13:57:04 GMT
Organization:   Universitaet Bielefeld

This is the problem the word-problem comes from:

                   1
                  1 1
                 2 2 3
                3 2 3 3
               3 3 1 1 2
              1 2 2 1 2 2
             1 1 2 3 3 1 1
            2 3 3 1 3 2 1 3
           2 2 3 1 1 2 2 3 3
                                                            o
This figure shows that you can tile a triangle T9 with T2: o o

QUESTION: which T(n) can be tiled with T2?

SOLUTION:
 The number of points of T(n) is ( n+1 \choose 2 ) = t(n).
 3 | t(n)  iff  n = 0, 2 (mod 3).

 CASE I: if n = 0, 2, 9, 11 (mod 12) then T(n) is tileable.
   From T9 you can get T11 and T12 adding:

      1 2 2 1 2 2 1 2 2 1
     1 1 2 1 1 2 1 1 2 1 1

   or
      1 1 2 2 3 3 1 1 2 2
     2 1 3 2 1 3 2 1 3 2 1
    2 2 3 3 1 1 2 2 3 3 1 1

   With T11, T12, and k times

     1 2 2 1 2 2 1 2 2 1 2 2
    1 1 2 1 1 2 1 1 2 1 1 2

   you can construct T(n+12) from T(n).

 CASE II: if n = 3, 5, 6, 8 (mod 12) then T(n) is not tileable.
   This is the hard case. You can look at the equivalent triomino
   puzzle. In this case T5 would look like:

              o                The allowed L-triominoes are:
            o o                      o         o o
          o o o   = T5             o o   and   o
        o o o o
      o o o o o                (only 180-degree rotation)

   Now let's try group theory:
   You can read about this technique in the article:
     Dmitry V. Fomin, Getting it together with "polyominoes",
     quantum 2:2 (Nov/Dec 1991) 20-23, 61
   So you get the group: G = < a, b| aabb=baba, bbaa=abab >.
   If a^n b^n <> (ba)^n for n = 3, 5, 6, 8 (mod 12) then is T(n) not
   tileable. Is a^n b^n = (ba)^n for some n = 3, 5, 6, 8 (mod 12) then
   a^3 b^3 = (ba)^3. This you can see be the same technique as in CASE I.
   You have the additional possibility of reduction in the group. If you
   show a^3 b^3 <> (ba)^3 then CASE II is solved. David Sibley found a
   homomorphism, which shows this inequality. So CASE II is proofed.

Annotation:
  Noam Elkies is right, that the homomorphis of David Sibley shows that
  it is implossible to tile an odd rectangle with the L-triomino (only
  180-degree rotation allowed) too. In this case you have to show that
  a^3 b <> b a^3.

Torsten Sillke

From:           elkies@ramanujan.harvard.edu (Noam Elkies)
Newsgroups:     sci.math
Subject:        Re: A Word-Problem
Date:           13 Aug 92 15:36:15 GMT
Organization:   Harvard Math Department

In article <1992Aug13.135704.2280@unibi.uni-bielefeld.de>
umatf071@unibi.uni-bielefeld.de (0105) writes:
"This is the problem the word-problem comes from:
"
"                   1
"                  1 1
"                 2 2 3
"                3 2 3 3
"               3 3 1 1 2
"              1 2 2 1 2 2
"             1 1 2 3 3 1 1
"            2 3 3 1 3 2 1 3
"           2 2 3 1 1 2 2 3 3
"                                                            o
"This figure shows that you can tile a triangle T9 with T2: o o
"
"QUESTION: which T(n) can be tiled with T2?
[...]

So it was a tiling problem, but not the one I had imagined...

"  Noam Elkies is right, that the homomorphism of David Sibley shows that
"  it is impossible to tile an odd rectangle with the L-triomino (only
"  180-degree rotation allowed) too. In this case you have to show that
"  a^3 b <> b a^3.

I omitted a step here: the commutators [a^3,b^2] and [b^2,a^3] vanish
(aaabb=a(aabb)=a(baba)=(abab)a=(bbaa)a=bbaaa, and likewise aabbb=bbbaa;
in ffect I'm tiling 2x3 and 3x2 rectangles with the allowed L-triominos),
and aaabbb=bababa iff a^3 and b^3 commute since b(abab)a=b(bbaa)a;
so the group-theory identity [a^m,b^n]=1 that would result from a tiling
of any odd mxn rectangle by allowed L-triominos is equivalent to any of
[aaa,b]=1, [aaa,bbb]=1, or aaabbb=bababa.

--Noam D. Elkies (elkies@zariski.harvard.edu)
  Dept. of Mathematics, Harvard University

Date:           Wed, 31 Jan 2001 09:19:39 -0500
From:           Aaron Meyerowitz <meyerowi@fau.edu>
Reply-To:       meyerowi@fau.edu
Organization:   F.A.U. Math
To:             eppstein@ics.uci.edu
Subject:        junkyard correction

I love and use your junkyard site frequently!
Looking for a remembered result I found it at
 http://www.ics.uci.edu/~eppstein/junkyard/wordprob.html
but it didn't work!
Halfway down one finds:
 A = [ 0  1  0  0  0 ]          B = [ 1  0  1  1  0 ]
     [ 0  0  1  0  0 ]              [ 0  0  1  0  0 ]
     [ 1  0  0  0  0 ]              [ 1  0  0  0  0 ]
     [ 0  0  0  1  0 ]              [ 1  1  1  0  0 ]
     [ 0  0  0  0  1 ]              [ 0  0  0  0  1 ]

  A^3*B^3 = [ 0  1  1  1  0 ]      B^3*A^3 = [ 0  1  1  1  0 ]
            [ 1  0  1  1  0 ]                [ 1  0  1  1  0 ]
            [ 1  1  0  1  0 ]                [ 1  1  0  1  0 ]
            [ 1  1  1  0  0 ]                [ 1  1  1  0  0 ]
            [ 0  0  0  1  1 ]                [ 1  1  1  0  1 ]

which MAPLE shows is wrong. Actually, for A and B
as given it is clear that any product will give

        [             0 ]
        [             0 ]
        [        X    0 ]
        [             0 ]
        [ 0  0  0  0  1 ]

I tried to guess the incorrect entry or entries After i gave up, I
searched and found:

 http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/word_problem_L3

which has it correctly. For matrix A the entry in row 3 column 1 is "1"
and not "0". Note that the matrices are over GF(2).

  A = [ 0  1  0  0  0 ]            B = [ 1  0  1  1  0 ]
      [ 0  0  1  0  0 ]                [ 0  0  1  0  0 ]
      [ 1  0  0  0  0 ]                [ 1  0  0  0  0 ]
      [ 0  0  0  1  0 ]                [ 1  1  1  0  0 ]
      [ 1  0  0  0  1 ]                [ 0  0  0  0  1 ]

  A^3*B^3 = [ 0  1  1  1  0 ]      B^3*A^3 = [ 0  1  1  1  0 ]
            [ 1  0  1  1  0 ]                [ 1  0  1  1  0 ]
            [ 1  1  0  1  0 ]                [ 1  1  0  1  0 ]
            [ 1  1  1  0  0 ]                [ 1  1  1  0  0 ]
            [ 0  0  0  1  1 ]                [ 1  1  1  0  1 ]

regards,
Aaron Meyerowitz