Newsgroups:sci.mathFrom:uphya159@unibi.uni-bielefeld.de (0118)Subject:A Word-ProblemDate:Sun, 9 Aug 92 17:24:11 GMTOrganization: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.mathSubject:Re: A Word-ProblemDate:11 Aug 92 15:15:45 GMTReply-To:sibley@math.psu.eduOrganization: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.mathSubject:Re: A Word-ProblemDate:11 Aug 92 17:27:30 GMTOrganization: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.mathFrom:cgodsil@watserv1.uwaterloo.ca (C. Godsil - C and O)Subject:Re: A Word-ProblemOrganization:University of WaterlooDate: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.mathFrom:umatf071@unibi.uni-bielefeld.de (0105)Subject:Re: A Word-ProblemDate:Thu, 13 Aug 92 13:57:04 GMTOrganization: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.mathSubject:Re: A Word-ProblemDate:13 Aug 92 15:36:15 GMTOrganization: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 -0500From:Aaron Meyerowitz <meyerowi@fau.edu>Reply-To:meyerowi@fau.eduOrganization:F.A.U. MathTo:eppstein@ics.uci.eduSubject: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