From: (Torsten Sillke)
Subject: A Word Problem
Date: Aug 92
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.
:: This Problem was solved imediatly by David Sibley.
:: Then there were contributions by Noam Elkies and Marston Conder.
:: Later I learned, that the problem had been solved already by
:: J H Conway (see AMM 97 (1990) 757-773).
---------------------------------------------------------------------
Subject: Re: A Word Problem
Date: Tue, 11 Aug 92 19:07:31 MESZ
I believe I have the example you are looking for. I was led to this
by the theoretical material I sent you the other day.
Let H be the quaternion group of order 8. H admits an automorphism
x of order 3 which permutes i, j, k cyclically. Let K be the
semi-direct product of Z_3 acting on H in this way. Let G be the
central product of K and H. That is, G = (KxH)/<(-1,-1)>.
Let a = (-x,i) and b = (-xi,j) in G. One readily verifies that
a^2*b^2 = (ba)^2 and b^2*a^2 = (ab)^2, yet a^3*b^3 is not (ba)^3.
I leave it to you to independently verify my calculations.
David Sibley
sibley@math.psu.edu
---------------------------------------------------------------------
Article: 12518 of sci.math
From: elkies@ramanujan.harvard.edu (Noam Elkies)
Subject: Re: A Word-Problem
Date: 11 Aug 92 17:27:30 GMT
Organization: Harvard Math Department
In article 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
---------------------------------------------------------------------
Article 12565 of sci.math:
From: cgodsil@watserv1.uwaterloo.ca (C. Godsil - C and O)
Subject: Re: A Word-Problem
Date: 12 Aug 92 20:27:15 GMT
Organization: University of Waterloo
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
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 ]
[ 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 ]
(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
---------------------------------------------------------------------
From: (Torsten Sillke)
Date: 13 Aug 92
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