N o t e : If s ( P ) > q* then central X i exist since (a - 2b
--
4)/t
J.L. Britton, The existence of infinite Burnside Groups
293
-
- € 3 0 - 2(rb + ~ 5 - ~4/e)> 0. I f P C A B then Po (cf. 6.8) exists and contains all central X i . Recall that the word “central” has been used in a different sense in Section 10.
> q*
16.4A. Definition. Let V be a ( t + 1)-subelement of size > q”, where 1 < t < n. V contains t-subelements Vi as in Axiom 30; if they satisfy (b) denote by pt+l V any central V j .If the Vi satisfy (a) there are no words pt+l V ;in this case call ( V i , V i + l )where V j and Vi+l are central a protected t-object of V . If some p t + l V exists consider any J = p , p t p t + l V where p u - l J does not exist. Then u 2 2 and J is a ( u - 1)-subelement. If u 2 3 then the u - 2-subelements Ji contained in J by Axiom 30 satisfy (a); call ( J i , J j + l ) where both terms are central a protected (u - 2)-object of V. If u = 2 J is a 1-subelement; we say that V contains a 0-object (even though we shall not define “0-object”.) 1..
16.4B. Note. If V is as in 16.4A and V C B 7 C, it is easy to deduce that there is induced VM ;T CMwhere either u # 0 and VM contains a u-object 0, where 0 is a protected u-object of V , and 0 O‘C CMfor some u-object 0’,or u = 0 (hence VM = C M )and V contains a 0-object. 16.4C. Proposition. Let A be a word containing two q-objects (S,T ) ,( S ’ , T ’ ) ,where q < n, such that they produce E , K . Let
(4)
(In A , (S,T ) );(InA , ( S ‘ ,T ‘ ) )- K
Then the subwords (S,T ) , ( S ‘ ,T ’ ) of A coincide. Proof. It is sufficient to show T, T‘ coincide so assume say T is left of T’. By cancelling (In A , from ( 4 ) we obtain
f)
(5)
T i (T, T ’ ) - K .
Adjustments of associated preobjects are equal:
294
J.L. Britton, The existence of infinite Burnside Groups
where
(8)
T L E Z * ;( T , T ' L E ' Z ' * )
The left side of (8) is a q-subelement. Taking divisions for (8), any Piof non-zero type has size > rb so by 5.21 n o Pihas type > q . Hence in (8), ;may be replaced by =. (8) now has the form 9 M = ( M , , A!,) where M , , M , are distinct maximal q-normal sub4 words of size > u,, and M is q-normal. By 6.19, Im'M, = M = Im'M, hence M , = M,, a contradiction. 16.5. Proposition. I f A D , D and DCare ( n + l)-urelements then so is ADC. Hence Axiom 2 2 holds f o r n + 1.
Proof. 1" . We may assume that D is normal. For let D 5 D'X where D'is ( n + 1 )-normal and put A' = A , C' = X C . Then A D ' X 3 AD' 3 D' so AD' is an urelement. Then A D 5 A ' D ' X 3 AID' 3 D' and D'C = DC so A'D' and D'C' are urelements. Thus if A'D'C' is an urelement then so is A D C . 2". We have
and
Un 2 ... 7 Uo 5 D Y A = D K for some X , Y , H, K, where 2, = ( B k ) ,Un = (R") and R, 13' E Rep L,+l. Since s ( D ) > y o , the situation is similar t o that of 13.1 1 . As in 13.1 1 we use the A-B notation for the 2-sequence; say B , , ._.,B , C Z , and all descendants of say R , , ..., B, in 2, are contained in D. Then we may assume kg/m > r,. As in 13.1 1 we have by 11.8
J. L. Britton, The existence of infinite Burnside Groups
Z,
= D,H,,
295
Un 5 D, K ,
and there is induced U," ; Z,". Moreover L(Z,")/L(B) > a , where Q is as defined in 13.1 1. Since Q > uS5 (P.C.) we have by 13.13 Z," = U," and B = B'. Let the B's for Un be B', , ..., BL,. Then for some a 2 1 BI+, = Bi for all i and rn' = lea. Similarly Bi+a = B j for all i and m = kea. But we may take Bj = Bi. for all j . Write R , for ( B w + s + 2 ,Bg-s-w-l)C Zn and RL for the corresponding subword of U F ; then RI, = (BL+s+l,B&w-l). Un - D , K, induces U," = Z," and hence induces RL = R,. We have
Z,
= R,S,,
U,
RLT,,
for some S,, T,.
Z,
= D,H,,
U,
0,K,
( r = 0, I , ..., n )
Also
where D o , H,, KO= D, H, K respectively. 3". Assume inductively the following. 1 . Z, = R,S,, U, = RI T,, R , = RI, R , C D,. If U is any subword of R , let f r ( U ) be the corresponding subword of RI. 2. R , (Bi+,, Bg-,), h = W + S + 1 ; R n - i ( A , + , , Ag-h-i); if r < n - 2 , R , has the form (PI, P2, Q1. Q2) where P,, P2 are two consecutive preferred A-descendants of B3+hand Q1, Q2 are two consecutive preferred A-descendants of Bg-hp2. 3. U, D, K,?nduces RI = R,. 4. If r < n the images under f, of the preferred A-descendants (for the Z-sequence) contained in R , are the preferred A-descendants (for the U-sequence) contained in R:. 5 . (RnSnRI,Tn) ... (RrSrR: Tr) Call this induction hypothesis P ( r ) . Note that P(n) is true. 4". If P(0)is true then the proposition follows. To see this note that R , C D o = D , say D = X R , Y ; then So = Y H X . By 3 Rb To DK induces Rb- R,, hence To= YKX. Now by 5 RoS,RbTo E ;:1 and (RoSoRbT,)= ( R , YHXRbYKX)= (HDKD) = ( D K D H ) = = (DYADCX). Hence ADCis a subpowerelement of L , + l ; since it contains D it is an urelement. Thus it remains to prove that if P ( r ) holds for some r where n 2 r > 0 then P(r - 1 ) holds. ~
296
J. I,. Britton, The existence of infinite Burnside Groups
5". This subsection, 5", is mainly devoted to recalling some arguments from the proof of 1 1.7. Consider
I n 1 1.7 we obtained from this an equation
Having obtained ( 1 0) we defined D, , Hr , K, by D, = 2," , H, Z ' , K, = F, U y R U ' U y LE,., where Z, = (2," Z ' ) , U, = (U," U ' ) . Since R , C D, and U, D , K,. induces RI = R , we see that (1 0) induces RI = R,. We recall how ( 1 0) was obtained. 2, contains a t-object ( T , , T 2 ) and an s-object ( S , , S,); U, contains objects ( T i , T i ) , ( S ;, S ; ) where ( T , , T,) ( T i , T i ) (producing E , , K~ say) and ( S , , S,) ( S ;, S ; ) (producing E , , K , say). (i) I f r < n then ( T , , T,)c V , , (S,,S,)C Vfwhere V , , Vf are the leftmost, rightmost A-descendants of B,, ..., Bg in 2,. (ii) If r = n and B , , B,, ... are disjoint and of size > u l l (cf. 7.8) then for some u,u ( T ,, T,) C B , ,( S , , S,) C B,. (iii)If Y = n and B , , B,, ... are maximal n-normal of size > Y" then for some 11, u ( T , , T,) = (B,, BU+,), ( S , , S,) = (B", BU+,). By a D-word we mean in these three cases respectively an Adescendant of B , , ,.., B, in 2,; a B,; a subword (Bi, B i + , ) . Write D, for V , , B, or (B,, B L l + , and ) define D, similarly. Note that ( T , , T,) is a protected object of DT in cases (i), (ii), while in case (iii) (Ti,T 2 ) DT. Let D,, D,, D, be D-words such that D,, D,, D,, D,, D, are disjoint (each term being left of the next) and D, C R,. D, contains an object, say a u-object ( U , , U 2 )and in the language of 11.7 D,, which we also denote by D,, clears a u-path with respect t o (9) in which ( U , , U,) has images throughout; in particular there is an object ( U ; , U ; ) in U, such that ( U l , U,) $ ( U ; , U ; ) (producing € 2 , K , say).
7
J. L. Britton, The existence of infinite Burnside Groups
291
Say ( T l ,5'2) T IAS,, ( T i , 5';) E T i BS;; we have ( T , , S 2 ) = e l *( T i , S ~ ) - and K ~
(where C, D are defined by (1 1)). In (1 l), TT, Ti* are such that
T I ' . q . T' = T *
(12)
1 t (
1 )
-1.
T'* 1
ThusA=(D,)RA1D2A2D3A3D4A,(D,)L for someAi ( i = 1, ..., 4). Still recalling 1 1.7 we have Di 3 D: D;. (i = 2,3,4), these being induced by ( 1 1); let ( q D F ) O V so that V is a left subword of D. Then V is disjoint from D i so Ti* C 0;.Now D = D; DiB' D; B"Di D; say and
-
-
Since D (13) (1 4)
E
T;*BSF, T;"
C
Di and dually SF C D; we have from
B = R L E ( D i R ,D,OL)FBR
for some B L , B R . ( 14) is the required equation ( 10) ( BC ( T i ,S;) C Ur , ( O F , D ~ ) ACC Z , ) . 6". Now (U,, U 2 )C D , 5 D, C (Di", D:L) so by ( 13) since either (U,, U 2 )= D , or ( U , , U 2 )is a protected object of D , there is a u-object ( U , , 02)C D and using 9.10 (i) if (G,, U 2 ) ,( U , , U 2 ) produce e5,K~ then
Let ( T l , U 2 )= T,AoU,, ( T i , U ; ) = T i B o U2. Just as we obtained (1 1 ), so we may obtain
where (1 2) holds and hence U;- K
~ U.jl - =
U p -UT-'. Hence
298
J. 1,. Britton, The existence of infinite Burnside Groups
( U , , U 2 )has image (0, , U 2 )in D with respect to ( 1 1 ). Moreover ( U , , U,) c Di,.Let ( U , , U2>,( U , , 0,) produce e4, u4. Then (In C, U 2 )= (In D , U 2 ) . ~ 4
(18) and
(In C, U i ) - (In D,U;)
(19)
(end words 1,K say)
is induced by ( 1 1 ) where K = U F . u4. UF-' and U , = U k U F , U , = Uk U F . Since ( U , , U 2 )C D, and ( U , , U 2 )C D;, D: is disjoint from ( U , , U,) and D i is disjoint from ( U , , U 2 ) ;thus in (1 9), D! is contained in the left side and 0; is contained in the right side. Hence (In D ,
ii2L)
(In D,
U 2 ) . ~ 4=
= (In
D, D i L ) E ( D Y , U ; ) . K - l
and
(20)
(In D,D k L ) E ( U F , U,)
From (17),(18) (In D,U;).u2 = (In D,U,).u4; but ( U ; , U i ) , produce e ; l . e 4 , u4.u;1. By 16.4C, U,is U i . It follows that U 2 )= ( U ; , U ; ) so u2 = K ~ Thus . the left side of (20) can be replaced by (In D, U;).u2 and hence by ( I 5 ) we have (InD, O2).uJ1 = ( I n D,U ; ) ' u 2 . Since 02),( U i , produce e 5 ' e 2 , u 2 . u 5 we have by 16.4C that U2 is U i . Since ( 14), i.e., ( l o ) , induces R: = R , and hence ( 13) induces RI = R , and since D, = D, C R , we have f,((U,, U,)) is U2) hence is ( U ;, U;); in particular ( U , , U 2 ) ( U i , U i ) . 7".Consider (1 ) and, recalling 1 1.7, let (U;', U i ) say be the image of ( U l , U 2 )in D r - l ; let ( U i " , U;") be the image of (U;', U ; ) i n U,. Then ( U ; , U ; ) is the image of ( U i " , U i " ) in U,. Thus in the Z-sequence, U2 has image U; in Z,-, and in the U-sequence U; = f r ( U 2 )has image U;" in U,-,. 8". We prove that if J is maximal r-normal in R,, and properly contained in it, and if s ( J ) > Y' then J is replaced in Z, + Z,-' if and only if f,(J) is replaced in U, + U,-
( U , , i?,)
(o,,
(ol,
u;)
(o,,
,.
,.
J.L. Britton, The existence of infinite Burnside Groups
299
R, c D,= Z," = (04".Dp).Assume r < n. Where ( V l , Vf)= = I/, C, Vf we have C, 3 R, 3 J . Now I/, , Vf are (r + 1)-subelements
and by 1 1.7 they clear paths with respect to (9). Thus J has image J" has image say J' " in U,-, and 9'" has image say say J" in D,-,, J' in U,. Also J' c ( T i ,Si).Since J C ( D p , D,"'),J has images J in D by (13) and j in D by (1 1). Making use of right r-objects we can follow the argument in 6" with J in the r6le of U2. We conclude that f,(J) is J ' . If r = n then since s(J) > r', all Bi are maximal normal of size > r" and we obtain the same conclusion by a simpler direct argument. Recall 12.5 and if J is replaced in 2, + Zr-l put 8 = 1 , otherwise put 3 = 0. If J' is replaced in U, -+ U,-, put cp = 1 , otherwise put cp = 0. Since Im'(J") = J'" with respect t o Ur-l rrl D r - l K r - l so by 12.7 J " , J'" satisfy (0). Since J = J ' we have 8 + cp = 0 (mod 2) and the result follows. 9". Let the preferred A-descendants in R , be Pi (i E I ) . Their cetres Ci (i E I ) which we denote also by C,, Ca+l,..., C,, are disjoint. The set 8, for Z, contains c,, ..., C, hence the iterated nice image of C, (a < u < b ) in Z,-, is equal in II t o the iterated nice image of f,CC,) in U,.-,. Define R,-, as the word generated by the preferred first A-descendants of P, ( u = a + 1 , ..., b - 1) and let RI-, be generated by the preferred first A-descendants of f r ( P , ) (u = a + 1, ..., b - 1). Then R,-, = RI-,. Next, since the iterated nice image of R , in Z r - l , and hence that of C, (a< u < b ) , is contained in D,-,C we have R,-, C Recall that ( U , , U 2 )C D, C R , C (DyR, In Case (i) D, is an A-descendant; we now restrict D, to be a preferred A-descendant, not the two leftmost or the two rightmost, in R,. Making use of the available choice of ( U l , U 2 )within D, we may say that f r p l ( U i )is U;"; indeed fr-l((U;', U;')) is (Ui", U;") SO (U;', U i ) (Ui", U;"). Since ( U i " , U;"), (U;', U;') correspond in U r - l - D r - , K,-, the following lemma implies that Ur-l -D,-,K,-, induces ( U i " , U i " ) = (U;', U;'). It follows that RI-, = Rr-l is induced since if X is any non-empty subword of R,-, such that f,_l(X) = X is induced, then RI-, = R r - l is induced.
"8").
300
J. I,. Britton, The existence of infinite Burnside Groups
16.5A. Lemma. Let
where ( U , , U2j, ( V , , V,) are u-objects and with respect to (2 1) lrn' U, = Vi (i = 1,2). Also let ( U l , U 2 )= ( V , , V,). Then (1 ) induces ( U , U,) = ( V 1 , V2). 9
Proof. If X c ( U , , U z )let f ( X ) be the corresponding subword of ( V ,, V,); thus X = f ( X ) . Now the two u-objects produce 1,1so we have
Since Im' U, = V 2 and U2 = V , we see that Case (b) of 6.16 applies hence by 6.25 U p urlV p (cf. Axiom 40). Let j be minimal such that U y 7 V Y . If j = 0 then ( A U F ) ; ( B 1 ,V y ); also UY = V Y , so where U2 = U k U y UF and V 2 = V k V y V: we have by (22) U: ;V:. Since U2 5 V 2 ,this implies that UF = V:, otherwise a subword of U would equal I in C,, contrary t o Axiom 10. Thus f ( U y ) is V y and the required result follows since (20) induces = VM 2 ' Now let j # 0; we shall obtain a contradiction. Take a Pi of type j ; then Pl!-l Xl!Ii Q i X t E L, (cf. 6.7). Let pi, Qi be the maximal normals of U,, V 2 respectively determined by Pi, Qi. Now f(P,) C V 2 and # Q iby Axiom 40; say f ( p i ) is left of Q i . Thus V , = V;(J'(P,~), Qi.) V i and U2 = U i Pi U i say. Now ( B 1 ,QI) V i= = ( B , , V 2 )= ( A P i ) U; = ( B , , Qi)X,'U; hence V i = X;. U i . But ( f ( P i ) .QI) V i = Pi U; so ( f ( P , ' ) ,Qi).Xl! P,!. By Axiom 24 Q)XE!Pf-'= QI" W ( P i L ) - l = H say. Write H = K L where K is of least length such that s ( K ) > s ( H ) ;hence K n Q:." = N is normal and ( f ( P ; ) ,K ) = L-l. This has the form ( M I ,M 2 ) = M , which leads t o a contradiction as in 16.4C; for f ( P l ! )and K are j-normal, but if ( f ( P l ! jK , ) were a j-subpowerelement, then ( f ( P l ! )N, ) and hence ' f ( P i ) ,0;) would be subpowerelements, contrary t o f(pi.)# Qi.
qf
f(c.)
J.L. Britton, The existence of infinite Burnside Groups
301
16.6. Let Z E Rep(L,+ ,) and let Z contain maximal n-normal subwords Bi (i = 1, ..., m ) of size > r f . Let 2 ; C', say Bi replaced or not according as pi = 1 or 0 and let 2 ; D' using pi = 0 or 1. Let Z 2 C' nzl... 7 C and Z 2 D'nzl... 7 D.Now let "j
= pi (i = 1, ..., q )
CY. 1 =
0; (i = q + 1, ..., m )
Then Z ; B' say by replacing Bi if ai = 1. Making use of the standard choices (1 5.5A) one can show
16.6A. In particular if D is 2 (cf. I6.3A) we have constructed an element of L n + , of the form CMEZM F. Let C = C M Xsay. Then X ;E Z MF. Let CM= C, C, C,; then C3EZMFC1is a subelement of L,+, equal in G, to the subword C3XC, of C. In this way Axiom 33' may be shown to hold for n + 1. 16.7. Axiom 33" is easily proved to hold for n
+ 1.
16.8. Consider Axiom 33'. Say Z , 2 ... 7 A B C D . Now if the equation A ; A L E Z F A Rarises from Z" ; ... 7 A Q say (cf. 16.6A) then Z" = Z T for some T. Since A is normal Z , = 2" i.e., Z T is a C.A. of Z,. Similarly Z'T' is a C.A. of 2,. 16.9. Consider Axiom 33. We have Z , -+ ... Zo = W V E L n + , and W ; WLDWRwith divisions say P,, P,, ... and Q1, Q z , ... . Let the of type n be H , , H,, ..., H,; Any Qi of non-zero type is contained in D.By 12.15 Zn-, contains maximal n-normal subwords K , , ..., K,. The image Li of Ki in 2, in the present case is > r'. Let the maximal normal subwords of size > rf in Zn be Bi (i = 1, ..., m ) and in Z , -+ Zn let pi = 1 if B j is replaced, 0 otherwise. Now Li = Bfci,(i = 1, ..., s). Let Zn + Z' by replacing Bi if (i) pi = 1 and j does not have the form f ( i ) ,or (ii) Pi = 0 and j = f ( i ) . One then shows -+
-,
302
J. L. Britton, The existence of infinite Burnside Groups
WLDWRVn -=1 WLLPWRRV Hence WLLPWRR = W ' is a subelement of L n + l equal in Gn-l to WL D WR and W LD W R may be written W t LD ' W R . By induction W LDWR is a subelement of L n + l .
16.10. Axioms 3 1 B and 3 1C for n + 1 read briefly: 3 1 B. If T ; Y where T is an (n + 1)-subelement then there is a word TLFY R . 3 1C. If (S, T ) nyl(S', TI) where S, T, S ' , T' are maximal ( n + 1)normal there is a word S L ATIR. To prove 3 1B, T contains subelements U j of L, by Axiom 30 for n + 1. If these are maximal normal let two of them be U, V . Let U' = Im' U V' = Im' V;then ( U R ,V L ); ( U R V, I L )and by Axiom 31C we obtain the desired result. If the Ui are not maximal normal then UIC TnzlY , hence Uy nyl YM and we may use Axiom 31B. Now consider 31C. Let the divisions be P I ,P 2 , ... and Q1, Q 2 , ... If S does not have the form Pi of type n + 1 then SL; StLand we may use 31B. Similarly for T. There remains the case when S = P i T = P1. ;Pi and Pi of type n + 1. Now ( P i ,Pi) n ~ (Qi, l Qi) and it is sufficient to show that a word Pi" GQR exists which X;-l1, ( Q i , Qi). BY Axiom 33' for n + I
c.,
nrl
P i = P ; E I Z , F I P F -Piy,
Qi=QkE3Z3F3QF=Qiy
Pi= PFE2Z2F2PF =Pi*, Qi = Q F E , Z 4 F 4 Q F =
QT.
Now P T - l X ; ! I Q T X i t L n + l and contains (2;'. Z , ) hence J, K exist such that K Z i 1 J Z 2E Rep(Ln+l) and J = E i l P:-lX;!l Q4 E,. Similarly Q,?XiP;-' 3 (Z4;2;') and K'Z4J'Z;' E Rep(Ln+l). Now
( Z , F I P F ,P:E,Z2)J'-'
n ~ J l( Z , F , Q ; ,
QFE4Z4)
J.L. Britton, The existence of infinite Burnside Groups
In the left side replace Z,J'-' in G , t o Zk WZ:. Hence
Pi" E l ZF WZF F4 Q f
303
by K ' Z , . By 15.3 the result is equal
n ~ X;-l1(Q: l
E 3 Z 3F , Q p ,
QF E 4 Z 4F4 Qf )
The left side is PTL WQ*'. Now Pi ;P: so P?' = PL EP*LR J and pfEp:LR'WQ*RiF@ is'the reSimilarly QTR = QTdLFQR quired word.
16.11 . Axiom 2 4 is easily shown to hold for n + 1. 16.12. Consider Axiom 18. First note that if Z E Rep(Ln+l) then one can find a sequence Z , + ... Zo frDm Z t o Z , i.e., Z, = Z , = Z such that (i) every Zi has the form Xi" and (ii) for k = 1 , 2 , 3 , ... -+
is a sequence from zk to z k . Now suppose AB E L;+,, s A B ( A )< h,. Then Z k 2... 7 AB, 2 E Rep(Ln+l). By Axiom 33' for n + 1,
B
x B ~ E Z , F B ~ ,z,z,= z k .
Now Z ,
=Zk-lZL,Z -
Hence Z
-+
... -+
Z L Z RZ , R = Z,, and
ZLRFBRA B LE Z L L; thus A is a subelement of
Ln+1.
16.13. The reader will easily verify that the following Axioms hold for n + 1: 2 , 3 , 6 , 7 , 2 1 , 3 1 A . 16.14. Note that Condition D now holds.
J. L. Britton, The existence of infinite Burnside Groups
304
5 17 Informal Summary This section is mainly concerned with the proof of Axioms 1 1 a, 1 1 b for n + 1. In the case of 1 1 a, one would like simply to take W' to be a word of smallest length such that W' = W.The author does not know whether or not such a W' is ((n + 1))-bounded by any parameter or in particular by 1, so in the proof given an alternative to "smallest length" has been used. 17.1. Proposition. Let A c X; Y where A is a subelement of L n + , and s ( A ) > u60. Let A 3 A o ; Ao' 3 B where B is a weak image o f A . Let A , B be (n)-bounded by b < Min(b2,, b31). Then there is a word A L E B R ,(n)-bounded by b + q31 where neither A L nor B R is a subelement of L U ... U 1,. Proof. See the proof of 6.26 and take u60 = u4.
17.1A. Informal note. We shall be interested in applying 17.1 , 17.2 when the (n)-bound of X,Y is greater than the (n)-bound of A , B.
-
17.2. Proposition. Let A C X ; Y where A is a subelement of and s ( A ) > u61. Let A 3 A' A'' 3 B where B is a weak image of A . Let A , B be (n)-bounded by b < b25,b31. Then there is a word A LEBR, (n)-bounded by b + q31 where s(AL) > s ( A ) - 2462 and B R is not a subelement of L LJ u 1,. Also s(A)> s(B)- ~4
(*I
-~ 3 .
s(B) > s ( A ) > u61- > u3. Hence by 6.10 C Bo' -Proof. Bo B, s(C) > s(B) Also s(C) > 2u4 > Now C c BO'c Ao c A , so s(C) < s ( A ) + e3 and follows. C
- u4 - u4.
u4
C
-
(*)
yo.
Now s(C) < s(B0')+ e3 hence s(Bo')2 u61 - 2u4 - e3 > ~ 3 1 , ro + r31 and there is a word BorLEBOR,(n)-bounded by b + q31 and equal in G , to BO'. K-' = E . Bo for end words E, K. BoR is not a subelement of L u -.. u L , and s ( B O ' ~> ) s(Bo')- r31 > yo. Now A = ZBO'T, B =X'BOY'say. The required word A LEBR is ZBOrLEBOR'Y'.
J.L. Britton, The existence of infinite Burnside Groups
3 05
We have
since u62 = 2u4 + 2e3 + ~ 3 1 . For later we require u 6 1 >
u62
+ ro + e3.
17.3. Notation. We use the notation ai (i = 1 , 2 , 3 , ...) for certain expressions which will be defined explicitly in the present section (Section 17). 17.4. Definition. Let U be a linear word (n)-bounded by k39. Call a sequence of subwords A,, ..., A , (m 2 1) of U linearly admissible if 1. Each A iis a subpowerelement of Rep(Ln+l) of size > 2463. 2. A , , ..., A , are pairwise disjoint. 3. ( A i ,A i + l ) is not a subpowerelement of L n + l (i = 1, ..., m - 1). 17.4A. Definition. Let U be (n)-bounded by k39. If U has no linearly admissible subwords put Dk+,(U) = 0. Otherwise, put
(taken over all linearly admissible sequences).
17.4B. Note. Dk+,(U) is finite.
,,
Proof. Take any linearly admissible sequence A ...,A , s(Ai) < L(A,)/e, hence 2 s ( A i )< ZL(Ai)/e < L ( U ) / e .
17.4C. Note. If
o;+l(U)
> 0 then D ; + l ( u ) >
. By 7.1 1,
2463.
17.5. Definition. Let W E II. By Axiom 1 la, since k39 2 bmi,, ( 3 W ' ) W g W', W'is (n)-bounded by k39.
3 06
J. I-. Britton, The existence of infinite Burnside Groups
Hence D L + , ( W ' ) exists; put
17.5A. D n + , ( W ) is 0 or > u63 17.5B. I f Wl
;W 2 then D,+,(W,)
,
= D,+,(w,).
1 7.5C. Proposition. D , + (W) is finite. Proof. It is sufficient to show that there are only finitely many W' as in 17.5. This follows from the next proposition since bmin< so. 17.5D. Proposition. If W, E n and W, is (n)-bounded b y so, then there ure only finitely many W,such that W , is (n)-bounded b y k3, und W, ;W,. Proof. Consider any W,. Then by Axiom 28 (so 6 b2*;k,,
<
Now if W, 2 X and W , 2 Y by simultaneous replacement of the same set of maximal n-normal subwords of W, then X .fl Y ; hence there is a finite set X , , ..., X , such that W, 2X i (i = 1, ..., N ) and if W , 2 Y then ( 3 j ) Y nl: Xi,1 < j < N . Say U,-, Xi.Now Un-, n=;l W,, so Xin-l W,. Now Xiis ( ( n- 1))-bounded by so, W, is ( ( n - I))-bounded by k,, so by an induction hypothesis there are only finitely many choices for W,.
,:
17.6. Proposition. Let R', C' E II. Let U be E. R. and let the cyclic word ( U ) be (n)-bounded b y k3,. Let R'. U . R'-' ;C'. Let A , , ..., A s be disjoint subwords of ( U ) where each A i is a subelement of Rep(L,+,) of size > ~~3 and ( A i ,A i + , )is not a subelement of L n + , ( i = 1 , ..., s ) (where A , + 1 means A , ) . Let C s ( A i ) > a,. Then C' ;X V Y , X V Y is (n)-bounded b y k,, , V is a subword of ( U ) , C s ' ( A i n V ) > C s ( A i )- a,, whcre s ' ( X ) means s ( X ) i f s ( X ) > u63 and 0 otherwise.
J. L. Britton, Theexistence of infinite Burnside Groups
307
17.6A. Note. s ' ( X ) < s ( X ) < s' ( X ) + u63. Also if A B is a subelement of L n + , then s'(AB) < s'(A) + s'(B) + 2uS3+ 2/e. Before proving 17.6 we need a lemma. 17.6B. Lemma. Let A , , ..., A,, B,, ..., B, be disjoint subwords of X where A , is left of B , (and 2.6 applies). Let X be (n)-bounded by k,,. Let A , , ..., A , and also B , , ..., B , be linearly admissible. Let
1
1
'
Then there is a word X ' , (n)-bounded by k3, and equal to X in G,, and there is a linearly admissible sequence C,, ..., C, for X ' such that
Hence D , + , ( X ) > a
+ b - us,.
Proof. Assume ( A , , B , ) = A,EB, is an ( n + 1)-subpowerelement, since otherwise the result is trivial. If s(A,) < us9 then A , ... ,A r - , , B , , ... ,B, is admissible and c = a + b - s ( A , ) 2 a + b - u89. Similarly if s ( B , ) < u89. Now let s(A,), s(B,) > 2489. Now us9 > rb. By Axiom 33" for n + 1 there is a subelement A , D B , = J of Rep Ln+, equal in G, to A , E B , . Where X - X , A , E B , X 2 put X ' - X , A , D B , X , . By 5.1 1, 5.32 X' is (n)-bounded by k3,. Also X ;X ' . Now s ( A , ) + s(DB1) < s(A,DB,) + (2e3 + e,*) and s(B,) < s ( D B 1 )+ e3. Hence S ( A r D B 1 ) ~ S ( A , ) + S ( B 1 ) - U 8 9>S(A,)>U63. ThusAl ,..., A , _ , , J , B,, ..., B, is admissible and
,
c = a-s(A,)
+ s(J) + b - s ( B 1 ) 2 a + b - u8,.
Proof of 17.6. First note that u63 > u,, u60; bmin,k,, Max(b,,,i,, str+)+ q31 < b25, b31. Put N = Z s ( A i ) ;then N > a,.
< b,,
and
308
J. L. Britton, The existence of infinite Burnside Groups
1O . Take C such that C' ;C and C is (n)-bounded by bmin (Axiom 1 la). There is at least one R such that (*)
R is (n)-bounded by bmin and U' exists such that
U' is a C.A. of U and R . U ' .R-' C. Namely, take R to be equal to R' in G, and (n)-bounded by bmin. Of the R satisfying ( * ) choose one such that D,+,(R) < Inf D,+,(R) R + 11e3. Let R . U' ; D where D is (a)-bounded by bmin. We can apply 8.2 of Chapter I since bmin,k,, < 1 - 5(r + E,) - 12/e (cf. the beginning of the proof of 15.3). Hence there are divisions R,R,R, of R , U , U , U3 of U ' , D , D , D , of D where R,; Uil (end words 8, I ) U3 ; D , (end words cp, I ) R, ; D , (end words I, $). As in 15.3 write R = R; R;R', and similarly for U' and D . 2". We have U ; C ( U ) . We shall obtain a contradiction from
+
Zs'(Ai n U ; ) > a,. Let Pi = Ai n U ; and let the Pi of size > u6, be P p , ..., P4 (since
a 2 2 0 there is at least one). Then Zf3 s(Pi) = Z s f ( P i )> a,. Now Pi C U ; C U , so we may consider a weak image Pi of Pi in R i l (i = p , ..., 9). Say RJ1 = X ' P i Y ' , U , = XP4Y. By 17.1 there is a
word P i E P i R , (n)-bounded by Max(bmin,str+)+ 9 3 1 . Also, if s ( P 4 ) > u61 then by 17.2 s ( P t ) > s(Pq)- u62. Put R 3 = X P t E P i R Y ' ; thenR, ;R i l . Let R * - R,.R,. Y f - l P i R - l E - ' P 4L - l X - l Then
R " - R 1 . R , . Y ' - l P i R - l E - l and
< D,+,(R) -~l/e3. We h a v e R3 > XP,">P, ,..., P 4 - , , P ~ . N o w R ;R * a n d R * i s (n)-bounded by Max(Max(bmin,s t y + ) + 9 3 1 , bmin,k,,) = P1 say.
J.L. Britton, The existence of infinite Burnside Groups
309
Now 0,= k39.R" is (n)-bounded by Max(bmi,, s t y + ) + q 3 1 . Hence (cf. 5.28A, 5.22) q-1
C s(P,) + s ( ~ f ; ) , i f s ( P i ) > yo + e3
(yo
+ e3 > u 6 3 )
Dn+,(R)2 s(Pi), otherwise. P
If s(P,) < then C 4 - l s(Pi) > a 2 and Dn+,(R)> a2 - u61 P > 11~3. If s(Pq) > u61 then s ( P i ) > s(Pq) - u62 > yo + e3; if also s(P:) > ro + e3 then s(Pq) - us2 + s(P:) < s ( P k ) + s ( P t ) < s(Pq) + + 2e3 + E:. Thus s(P:) < Max(ro + e 3 , us2 + 2e3 + e;') = a 3 . Now 2 / e + s ( P i ) + s(P:) + C;-l s(Pi) > a2 hence
D,+,(R)> a 2 - 2 / e - s ( P : ) > a 2 - 2 / e - a 3
> l/e3;
thus the result is true if D,+,(R") = 0. Now let D,+,(R") > 0. Then S' exists, (n)-bounded by p1 and R" ;S ' , and there is an admissible sequence B , , ..., B, for S' such that
Let Ci be a weak image of Biin R". There is a word B i ECF (n)bounded by str+ + 2 q 3 1 ,since bmin< s t y + . Also if s ( B k ) > u61 then s ( B i ) > s(B,) - u62. Hence the word R ** where (In S', R i ) E ( C F , Fin R " )
R**
is (nkbounded by P1 since str+ + 2q31 < k39.Also R** R* = ~ r l p L - 1 ~ -so1 4
;R". Now
~ * * p L - 1 ~ - R* 1 == R (7
n
n
where there is no dot on the left side and it is (n)-bounded by pl. Consider the sequence B , , ..., B k - l B p , PF-', Pi!', ..., Pi' where
310
J.L. Britton, The existence of infinite Burnside Groups
X o means X is omitted if s ( X ) < ro + E,. By 17.6B, k- 1
0
q-1
0
cs(Pi)-a4
Dn+l(RP cs(B,)+S(B~)+s(P;)+ 1
P
where a4 = ~ 4 ~ ~ . From the first part of 3" follows
) E;s(Bi) = s(BiL)-s(BR);if Now (C:-'s(B,) + s ( B ; ) ~ s ( B k )< u61 this expression is 2 -u61, while if s(Bk)> then as before s(BF) < a, and the expression is s ( ~ k -) s ( B ~ ) -s(@)
- 2/e
> -a3
- 2/e.
Hence D + l ( R ) 2 -ay4+ a 2 - 2 M a x ( ~2/e ~ ~+, a 3 )+ E t s ( B i ) = - a5 + E ffl s ( B i ) say. Now D,+,(R) > a5 + D n + l ( R f f-) E 2 D n + l ( R " )+ + 1/e3 since we shall define a 2 by the equation a5 = E + 1 /e3. This proves that D,+,(R") < D n + l ( R )- l/e3. 4". Let R" ;T where T is (n)-bounded by bmin.Then C ;T . U". T-' and D n + l ( R )> D n + l ( R " )= D n + l ( T ) a, contradiction. 5". Thus we have C s'(Ai n U ; ) < a 2 . Now N < E s(Ai)= E s'(Ai) and C s f ( A i )< 3(2u63 + 2/e) + s'(A, n Ui>+ c s'(Ai n U ; ) + + C s'(Ai n U;). But s'(Ai n U ; ) = 0 , since 2e2 + 4/e + rb < u63 (cf. 1" of 15.3)
Let Qi = A i n U; and say Qr, ..., Qs have size > u63 (there is at least one since Z: s(Qi)2 N , > a1 - 3(2U,, + 2/e) - a2 > 0. Now Qic U 3 - D, so we may consider a weak image Q: of Qi in D, and there exists a word EQ,", (n)-bounded by str+ + q31 and
elL
D, ;(In D,,Q;")E(Q,", Fin U,)
z D",say
J. L. Britton, The existence of infinite Burnside Groups
311
andD; Dl.D2.D"=-D*,say.HenceC;R.U',R-1 ;D.R-'= = D * . R - l . Put H E R - ' ; then there are divisions D:DgD; of;*, H2 H 3 of H and C , C2C, of C and D3 Hi' (end words 8, I ) (end words cp, I ) H3 C3 (end words I , $) Cl Dr Now -D* -D* = - -(@,Fin U 3 ) ;let V = 0; n Fin U 3 ) . Then J , D:* exists such that Fin U 3 )= JV, 0; = D;* V. 6". Assume that 2: s'( V n Q i ) > a 2 ;we shall obtain a contradiction. ~ ~ ; Put Si = V n Qi and say S q , _..,S, have size > ~ 1 then E i s ( S i ) > a2. Now Si C V C D:; let S; be a weak image in HI' of Si.There is a word SiLES:, (n)-bounded by str+ + q 3 1 and
h,
-
(QF,
(QF,
HI'
;(In H i 1 , SrL) E(S:, 4.
Fin 0:)
where the right side is (n)-bounded by pl. Now U' = J'JV say, and V = V , Vo for some V l , where Vo = (SR,Fin 0 ; ) . Thus H-'= 1 n TEVo = Ro,say, where T = (In&', S f L )Let RE = H i l H i l TE and R t = R: V o ;thus R t 3 Ro. Also R ;H-f =.Hi1H i 1H-'1 = R:. N o w C = R.Ul.R-1 = R " V .J'JV I / . V ~ l R ~ - ' = R ; I . V o J ' J V l . R ~ - l , n 0 0 1 0 where U l = VoJ'JVl is a C.A. of U' hence of U. We shall show Dn+'(R;)< Dn+,(R)- l/e3. The method is the same as before but it may help the reader t o give a sketch. R z 3 Ro 3 Vo 3 S t , S q + l ,..., Ss. Next it can be shown that R: is (n)-bounded by k,, and hence as before
so the result is true if Dn+l(R:)= 0. Now let Dn+,(R(d)> 0. Then Sh exists, (n)-bounded by k3, and R: ;Sb and there is an admissible sequence B , , ..., B, for Sb such that E s(B,) > Dn+'(l?:)- l/e2. Let Ci be a weak image of Bi in R:. Then there is a word
R ~ * = . ( I n S A , B ~ ) E ( C ~ , F i n R : ) a n d R ~R*Z; s o R $ * V o ; R : ; R . R t * V o contains subwordsB1, ..., B,_,, B k , S R ,S q + l ,..., S, and proceeding as before we again obtain the result. As in 4" the result just obtained leads to a contradiction.
312
J. L. Britton, The existence of infinite Burnside Groups
Hence we have Z; s'( V n Q i ) G a2. 7". Now
Therefore Z s'(J n Q i ) 2 N,- s'(Qr) + sf(@) - a 2 - 2uS3- 2 / e > 0 . Fin U 3 )= JDT. Now D*D Hence J I so D* E 1 2*D* 3 F J"( QF, Fin U 3 )E J"JDT so DTD; = J"J. Write J 3 J , J2where J , F J no:. Then
+
(QF,
C ~ (n JQ ~<) C ~ ' (nJQ, ~+) C ~ ' (nJQ~~+)2uS3+ 2/e. But s'(J2 n Q i ) = 0 so
C ~ ' (nJQ, ~2)N,- S ' ( Q , ) + ~ ' ( Q F ) a 2 - 4u63 - 4 / e = N2 (say) > 0. -
-
Hence J , $ I and J , has the form (DT)R C DT C,. Let Ti = J , n Qi = J , n A i n U; and let the Ti of size > u63 be Ta, ..., Tb (there is at least one). Then Z,bs(Ti)> N 2 . Let Ti be a weak image of Ti in C,. Then
where the right side is (n)-bounded by k,, and contains (Ta, ..., Tb-,, T k ) = V say; it is the required X V Y . Also V C U; C ( U ) . Now
J.L. Britton, The existence of infinite Burnside Groups
313
NOW if s ( T b ) > U then S(Tk)> S ( T b ) - U s 2 > 2461 - U62 > 2463, hence S ( T ; ) = s ' (61L T ~) and s ( T b ) = s ' ( T b ) . Therefore s ' ( T ~>) S ' ( T b ) -
- u 6 2 . If s ( T b ) < then S ' ( T b ) < 2461. Hence s ' ( T ~- s)' ( T b ) is greater than - u 6 2 or 0 - U61 so in either case it is greater than -2461. Similarly, s'(Qp) -s'(Qr) > - u 6 1 . Therefore
C ~ ' (n A V )~ 2 -
2
+ N~ , -~a2 -~42463 - 4/e
if we define a1 to be 2a2 + 5 ( 2 U 6 3 + 2 / e ) + 2~~~ 17.7. Corollary. D n + l ( C f 2 ) C. s ( A i ) - a l
- 2(ro + e 3 ) .
Proof. This is trivial if the right side is negative so let E s(A,) > a 1 + 2(ro + e 3 ) . Let Pi = A i n V . Those Pi of size > 2463 have the form (i) P a , ..., P b . Also b
cS(Pi) cS'(Pi) > C s ( A , ) =
a
- "1
> 2(ro + E 3 )
From the sequence (i) delete Pa if it is not normal to obtain (ii) P a + l , ..., P b , where k
b
c S(Pi) z =
a+l
a
S(Pi) - s(Pa)2
b
c S(P,) a
- (Yo
+ € 3 ) > Yo + € 3 .
From the sequence (i) or (ii) delete P b if it is not normal. For the new sequence 2 s(pi)2 2,"s(pi)- 2(ro + e 3 )> o so it is non-empty; it is also admissible, so
17.8. Definition. Put W E J n ( x ) if W is E.R. and ( W ) is (n)-bounded by x , and W e # I in G,.
J. L. Britton, The existence of
314
infiniteBurnside Groups
17.8A. Note. By Axiom 1 1b, if W E II, We # I in G, then some conjugate U of W in G, is in J n ( k 3 9 ) ,because cbmi, < k39. 17.9. Definition. If U EJn(k39)we define B k + , ( U ) as follows. Call A , ... , A, admissible for U if 1. A 1 , ..., A , are disjoint subwords of ( U ) . 2. Each A i is a subelement of Rep(L,+l) of size > u63. 3. (Ai, A i + l ) is not a subelement of L,+, ( i = 1, ..., q ) A , + , = A , . Put Bi, + ( U ) = Sup C:=, s ( Ai) (or 0 if no admissible sequence ex is ts). 17.9A. BL+, ( U ) is finite. 17.10. Definition. Let W E II, We # I in Gn+,. Define Bn+,(W) to be Sup BL+,(U) where U is conjugate to W in G, and U E J, ( k 3 9 ) . 1 7.1 OA. Proposition. B,
+
,( W) is finite.
Proof. Choose U, where U, is conjugate t o W in G, and U, E J,* (k39). Consider any U E Jn(k39)conjugate t o W in G,. Then R'. U .R'-' ;U, for some R'. Let A , , ..., A s be admissible for U. Then by 17.6, 17.7 either C s ( A i )< a l or
B,
+
( U, ) 2 &(A
-
a
,
-
2(ro + € 3 ).
Thus C s(A,) is bounded above, as required.
17.1OB. Note. I f W; # I in Gn+ and W,, W2 are conjugate in G, the11Bn+1(W1)=Bn+l(W2). 17.1 1 . Proposition. I f We # I in Gn+l then there exists K such that (i) K is conjugate to W in G,+l. (ii)I f X is conjugate to W in G,, then B n + l( K ) < Bn+l( X ) + l / e 3 . (iii) K E Moreover, f o r any such K the cyclic word ( K ) is ( n + 1 )-bounded by
k40.
Proof. Let L be conjugate t o W in G,+,. Then Le # I in G n + l and
J. L. Britton, The existence of infinite Burnside Groups
315
B,+l ( L ) exists. Of all such L choose L' such that B n + l ( L ' ) < InfB,+l(L) + l/e3. Thus L ' i s conjugate t o Win G,+l. Now L f e # I in G, so some conjugate K of L' in G, is in J , (k3,) and
B,+l(K)=B,+,(L').
It remains to show that ( K ) is ( n + 1)-bounded by k40. Assume not; then ( K ) contains S where S is an ( n + 1)-subelement of size 2- k40, so n o linearization of ( K ) is a subelement of L u ... u L,. By Axiom 28B, since k3, < d,,, ( K ) (K') where (K') is (n)bounded by str = k41. Also ( K ' ) contains an image S' of S where s(S') > s(S) - u ~ Say . ( K ' ) = (SIT'). Since k,, - us4 > t33 and str < b,, we have S' ;SfLEZFSfR = S " , where S" is (n)-bounded by k41+ c33< k,, and by 5.32, so is ( S " T ' ) .Also s(Z) > s(S') - Y 3 3 > - Y 3 3 - U a + k40 = CYy6 and (116 > MaX(U63, "1 + 1 /e2 + lie3). We have (S"T') = ( A Z ) for some A , and ZT-l E Rep(L,+l) for some T. Thus 2 n ~ T.l Let A . T ;C where C is (n)-bounded by bmin(cf. Axiom 1 la). We may write C = Q-lC'Q where Q is chosen maximally. Now write X conj, Y if X,Y are conjugate in G,; then
W conj,+l K conj, K'
= S'T' ;S"T' conj,AZ
,fl
A . T; C conj, C'.
Thus W conj,+,C'. H e n c e B , + l ( K ) < B,+l(C')+ l/e3. Now K conj, A Z E J , (k3,) and 2 is admissible so B,+,(K) 2 ~ ( 2 Therefore ). Bn+l(C')> 0. Hence B n + l ( C ' )= Sup B h + l ( U ) over U such that U conj, C' and U E J , ( k , , ) . Thus U exists with an admissible sequence for U , say { A i l , such that
Since C' conj, U we have by 17.6 that C' ;X V Y , (n)-bounded by k3, , where V C ( U ) and C s'(Aj n V )> I:$(Ai) - al. Put Pi = A i n V ; then pi, ..., p k , say, have size > 4 3 and c,!s(P,) > c s(A,)- a 1 . C' is (n)-bounded by bmin;let Pl!be a weak image in C' of P i . We have say C' C i ( P i , P i ) Ci. If j < k
J.L. Britton, The existence of infinite Burnside Groups
316
C'
;c;P;"E(P;,
P;) F P ~ =;c".
This is true also when j = k if we interpret (Pi", Pk) to be Pi".C" is (n)-bounded by k39.Now A . T; C- Q-l C'Q ;Q-' C"Q (no dots and D = Q-l C"Q is (n)-bounded by k3,. There are divisions A1A2A3 o f A , TlT2T3of T a n d D 1 D 2 D 3 o f D a n d A 3 - T i 1 , T3 D3, A , D , . Let ni, ...,nk mean PR, Pi+l, ..., Pk-,,Pk and let J Qi = ri n D,. Assume Z: s ' ( Q i ) > s(T) + a7 > 0; we shall obtain a contradiction. Let the Qi of size > uS3be say Q,, ..., Q,. Then Ey s(Qi)> s ( T ) + + a 7 . Let Q; be a weak image of Qi in T3. Then
-
(1)
-
T, ;(In T3. QiL)E(Qp,Qk)F(Q:, Fin T3)- T;', say
(if I = m interpret (Q,",
Qk)as Q,"). T;' is (n)-bounded by k3,. Now
and by 5.32 the last word is (n)-bounded by k39.By Axiom 28 since str+ < b28 and k,, < a28 we have 2-' T 2 7 Z-' T, T2T;' hence Hence (Q,", 2-' T, T, T;' E is a subelement of L n + l . If ( A , , , , A , + , ) would be a subelement I + 2 < m then (Q,,,, Q1+2) of L , + l ; hence I + 2 2 m. Let
Qk)
If rn - 1 = 2 then either Qp nor Qf;, is normal. If m - I = 1 then not both of Qf , are normal. Hence one of the summands H of (2) satisfies
QL
x < 2(ro + E 3 ) + s ' ( H ) . Now
317
J. L. Britton, The existence of infinite Burnside Groups
so
s ' ( H ) - s ( T ) > a7 - 2u61- 2(ro + € 3 )
> (Yo + € 3 ) + u4. Now s( T ) 2 0, so in particular s' ( H )= s ( H ) . From (1 ), T , contains a weak image H' of H and s ( H ' ) > s ( H ) - u4 > yo + e3. Hence
s ( T )2 s ( H ' ) - €3
>s(H)
- u4
- €3 = s ' ( H ) - u4
-
€3.
+ 3(ro + e3) + u4 + e3 we obtain a Hence, defining a7 to be contradiction. Hence C. s'(Qi) < s ( T ) + a7. We have
Cs'(ni)< C sf(nin D,)+ E sr(ni n 0 2 +) C sf(n n 03)+ 2(2u6,+ 2/( Now
so
J. L. Britton, The existence of infinite Burnside Groups
318
C ~ ( A , ) - ~ ( l/e’-T ) >I -
~ + ~ ( z ) - ~ ( T )
Thus p > 0. Let Ri = xi n D,.Let the R i of size > u63 be, say, R , , ..., R , ; there is at least one: CL s(Ri)> p. R j has weak image Ri in A , ; say A = X,(RL, R k ) * X X Then ,.
;X , R: E ( R f , R k )FRLRX2Z = G, say.
AZ
G is E.R; and ( C ) is (n)-bounded by k,,, so G E Jn(k3,). Now K conj, A 2 ;G. Consider the sequence RUR R u + l ..., R , _ , , R k ,
(3)
9
9
z
of subwords of ( G ) and put E - s’(RF)+
+ s’(Z). Then E
s ’ ( R j )+ s‘(Rk)+
> s ‘ ( R ; ) + s‘(Rk)+ s ‘ ( Z )+ p -s‘(Ru) -s’(R,)
Now s ( 2 ) - s( T ) > 1 /e2 + a9 + 1 /e3 so the last expression is greater than C s ( A i ) + 1 /e2 - 2u61+ a9 - “8 + 1/e3. We can obtain an admissible sequence B , , B,, ... from (3) as follows. Delete RF if not normal; delete R; if not normal; then apply 17.6B to obtain a linearly admissible sequence S , , ..., Sp say, where C s(Si) 2 E - 2(ro + e3) - u89. If p = 1 the sequence is already admissible. If p > 2 , apply 17.6B t o s,, ..., S p , S l t o obtain the required B , , ... , B, where C s ( B i )> E s ( S i )- u89. Hence Bn+l ( K ) = B n + l ( A Z )2 S(Bi) > E - U66 where u66 = 2(ro + e3 + ug9).Hence
J.L. Britton, The existence of infinite Burnside Groups
319
since a9 > 2u61 + "8 + u66, i.e., 2a6 - I - (ro + 2 ~- ~ 1 /e 2) - I /e3 > 2 U 6 , + a8 4- u66. But We proved above that c S ( A i ) > Bn+l( K ) - l/e2 - l/e3 so we have a contradiction.
17.1 2. Proposition. Axiom 1 1b holds for n
+ 1.
Proof. Let We # I in Gn+ Of the L such that L conj, + W choose L' such that Bn+,(.L') < Inf B,+,(L) + l/e3. By Axiom 1 lb, since Lre# I , there exists KOsuch that KO is E.R., KO conj, L' and (KO) is (n)-bounded by cbmi, < k39. NOWBn+l(Ko)= Bn+l(L') and KOE Jn(k39). By 17.1 1 (KO)is ( n 1)-bounded by k40. Now k40 = str. Thus (KO)is (n)-bounded by cbmi, and ( n + 1)-bounded by str. Since cbmi, < str < str++ q31 G so, (KO)is ( ( n + 1 ))-bounded by so. Make a simultaneous ( n + 1)-replacement in (KO)by replacing those maximal normal subwords, if any, of size > f . Say (KO)+(K,). Then by Axioms 26,26" no maximal normal subword of (K,) has size 2 + r26,since 5I + r26> u26 ; thus (K, ) is ( n + 1 )-bounded by f + Y , ~+ e3 = k42. It is (n)-bounded by so. Similarly (K2) exists such that (K,) + (K2) and (K,) is n-bounded by k42 and ( ( n - 1))bounded by so ; and so on to obtain finally ( K n + , ), I-bounded by k42-
Now let S be a ( p + 1)-subelement ( I < p < n ) in (K,+,) of size 12.15 it determines a subelement S' of L p + l in (Kn+l-p) and s(S') > s(S) - u65 where us5 = u37 + u4. Hence s(S) < s(S') + + u65 < k42 + u65 = Cb,i,. Thus ( K n + l )is ( ( n + 1))-bounded by cbmi,. Finally Kn+, conj,,, KO conj, L' conj,,, W.
> u49. By
17.13. Corollary. If We $; Z in G , +1 then K exists such that K conjn+lW;X conjn+lW implies Bn+, (K) < Bn+,(X) + l/e3, and K E J n + lwhere , Jn+lis defined as follows. 17.13A. Definition. Put Y E Jn+lif Ye # Zin Gn+,, Y is E.R. and ( Y ) is ( ( n + I))-bounded by str (cf. Axiom 9). Proof of 17.13. For the required K, take the KO of 17.12.
3 20
J.L. Britton, The existence of infinite Burnside Groups
17.14. Note. Axiom 1 1a is just a linear version of Axiom 1 1 b. The proof that Axiom 1 l a holds for ( n + 1 ) is left to the reader. 17.15. Proposition. Let T be E.R. and let ( T ) be (n)-bounded b y k45. Let T e # I in G n + l .Let B n + , ( T )Z ~ 7 1 Then . B n ( T )> 2B,+,(T). Proof. As a preliminary, note that k,, < b 2 5 , b30, b 3 3 2.463 ; - u4 > "30; Min(q*, r* - 2(ro + e 3 )- 4/e) > t33and :u63 - €30 - 1/e2 > rb + ekO+ 2/e. U exists such that U conj, T, U E J , ( k 3 9 ) ,and
there is an admissible sequence A 1, ..., A , for U such that
C S ( A>~B ,), ~( T )
-
l/e2 2
u71-
l / e 2 > al;
say, K t U . R - l ;T . By 17.6 T ; X V Y where X V Y is (n)-bounded by k,,, V C ( U ) and 2 s'(Ai n V ) > 2 s ( A i ) - a 1 . Let Pi = A j n V , and let those Pi of size > u63 be P f , ..., Pg, say. Then EFs(Pi) > C s ( A i ) - a l > B , + , ( T ) - 1 / e 2 - a l > B,+l(T)since ~ 7 > 1 2(1/e2 + "1). For i = J ; ..., g let Pl!be a weak image in T of Pi; then s(p1!)> s(pi) - u4 > s(Pi)since 2163 > 2u4. By Axiom 30 for n + 1, Pl! contains subelements Ui; ( j = 1 ...)ai) of L,. Let Cii be the kernels of the Uii (i fixed); thus if the Uii are disjoint then Cii = Uii. Now (Axiom 3 3 ' )
say where Cb , C: are not subelements of L u ... U L n - l and Cly is ( ( n - I))-bounded by k,, + c33.Also s(Zii) > q* - r33 > u63. Let Pi!' arise from Pi!by replacing Cii by C i for all j , and let T" arise from T by replacing each Pi' by Pi''. Then T n ~ T" l and T" is ( ( n - 1))-bounded by k,, + c33< k3, (cf. 5.32). For fixed i suppose the subword (Zi a - l , Zi b + l ) of PI!'is a subelement of 1 , and a < b. Then Ci", Ei,(Z,, Zib)Fib C: = U is a subelel cib)c Pi! so ment of L , say U V E L,. Now U n ~ (Cia, UV ,,zl(Ci,, Cih)V . Since (Ci,, Cib) is ( ( n - I))-bounded by k,, ( c i a , Cjb) VE L n' Since a < h. this implies that the Uii are not maximal normal
J. L. Britton, The existence of infinite Burnside Groups
321
(cf. 5.28A), i.e., Cij = U i j . Thus (Ui,, Uib) is a subelement of
1,. By Axiom 30, s(Ui,, Uib)> (b + 1 -a)/ti aj/ti > s(P~) - €30 > s(Pj)- €30.
- E;,
and
Next we show there are positive integers ci, k , such that (i) (ci - l)/ti - €5, > rb (ii) kici + 1 < ai. Let c, be the least integer > (rb + ejo) ti + 1 = 6 say, then (i) holds. Now kici + 1 < ki(6 + 1) + 1 < ai if ki < (a, - l)/(6 + 1). Next,
= Ei say
and Ei > 1. Thus for ki we may take [ E i l . Hence k j > E j - 1. Put Ais = Zii where j = 1 + sc, (s = 0 , ,.., ki). Then we have shown that (A,,, A , s + l ) is not a subelement of 1, (cf. 5.21). Thus the sequence { Ais}, i = J ..., g, s = 1, 2, ..., ki, is admissible for T" (since, e.g., (Ai-l A , , ) > (Aio,Ai,)). Hence
i = f s=l
i=f
We show that us3(Ei- 1) > &(Pi) and it will follow. that B n ( T )> 4 2 s ( P i ) > 2B,+,(T) as required. Let a = ~ 3 +0 l/e, p = rb + €j, + 2/e. Then Ei - 1 = (3 s(Pi) - a - p)/p > 4s(Pj)/u63 provided that
17.16. Proposition. If ( U ) is (n)-bounded by k,, and Bn +1( U ) < U 7 1 then ( U ) is ( ( n + 1))-bounded by k46. Proof. If not then ( U ) =_ ( U ' S ) where S is a subelement of L,+l and s(S) 2 k4, 2 51 , t33.Now S ; sLEZFS' E S' where s' is (n)-
322
J. L. Britton, The existence of infinite Burnside Groups
bounded by Thus
k46
+ c3, < k,,,
which is a contradiction
and so is U'S'. Also s ( Z ) >
(k46
2'
-
r33 > d .
< b3,).
17.1 7. Proposition. B: = QC,, ..., Cn+'.J n + l ) . Also C , , ..., J,* ure pairwise disjoint. Hence Axiom 1 holds for n + 1. +
,
Proof. Call the right side H say. Let W E II. If We = I in G,+' then W e = I i n H . I f W e # I i n G n + l t h e n b y 17.13 t h e r e e x i s t s K E J , + l conjugate to W in G,+l. Hence in H we have I = K e = T-' . We.T for some T . So again We = I in H. are disjoint since Cn+lC J,. If X E J n + , then C , , ..., en+' X " # Z in Gn+lwhile if X E C, then X e = I in G, hence in G,+,. 17.1 8. Proposition. Zj TCTD = Pe E Ln+l and L ( T ) 2 L(P) then TC = Pk for some k hence (TC)en ~ I.l Proof. This is trivial (cf. 2.18B). 17.19. Proposition. Let Y A Y B E L , + l , s ( Y ) > ~ 7 2 Then . if Y i s (n)-hoiinded hy k,, we have ( Y A ) e = I in G n + l .
,.
Proof. We have Z + ... + Y A Y B , Z = P e E Rep L, + The first Y ; Y L E Z I F Y Rand the second Y ; Y ' E ' Z 2 F ' Y r( ~ 7 2 t3,; 2 k47 < b3,). Also (2, C Z 2 D )= Z and 2,CZ2 ;Z , FY A Y' E'Z2 by Section 16. Consider Y L E Z I F Y R;Y ' E ' Z 2 F ' Y r . Let J be a weak image of 2,in the right side (k47+ c , ~< b25;~ 7 -2 r3, > u 3 ) . Then s(J n Z,) > ( ~ 7 2- r33 - u 4 ) - 4/e - 2Max(ro, q3, + E , ) = 6 say. Now 6 > u1 and, where 22" E ( J n Z2)0,s ( Z Y ) > 6 - u1 > s , ~ . Say Q; then Q has the form Z r . By Axiom 33 for n + 1 Z y 3 Z Y . We may write Zi = Z ~ Z (i ~= 1,2). Z By ~ 13.23 YL EZ: ;Y'E'Z;. By 13.2 1 and Axiom 19, since s3, 2 ro we - ( E : + 3/9) - E , > l / e . Now have L ( Z M ) / L ( Z>)
Zr -
J. L. Britton, The existence of infinite Burnside Groups
323
Z - ( Z F Z F Z p C Z ~ Z F Z F D ) and ZF = Z F hence (Z? Zp CZi)e n Now
Hence ( YA)e n
~ I ,l by
17.18.
~ I.l
17.20. Proposition. Axiom 8a holds f o r n + 1 ; i.e., if Xe f I in Gn+l and (X) is ( ( n + 1))-bounded b y z 2 then (X') is ( ( n + I))-bounded b y z + ag. Proof. If not we may assume that ( X ' ) 3 S where S is a subelement of L',+~ of size 2 z + a s = y say. Now S = Y k Y L where Y is a C.A. of X is a C.A. of X and k is a non-negative integer. Since Y LC Y C ( X ) we have k 2 1. Clearly Ye I in G n + l . If k = 1 , S = Y L Y Y L .Since s ( S ) 2 y and s ( Y ) < z we have s ( Y L ) > y - z - 2 / e = a s - 2 / e > ~ 7 2 . B y 17.19(YLYR)enT1', a contradiction ( z < k47). If k = 2, S = Y Y Y L .One of Y , Y , Y L has size 2 1 ( y - 4/e) > r,, hences(Y)> 5(y-4/e)-e3 (5.19). Now :(; -4/e)-e3 > 1172. Now apply 17.19 to the subelement Y Y of we obtain Ye n=+l I. If k = 3 we proceed similarly using ( y - 6/e) > Max(r,, e3 + u72>. I f k > 3 t h e n k = 2 s + O whereO=Oor 1 . 2 s + 1 > k>-3hence s 2 2. One of Y s , Y s , Ye YL has size Z f (v - 4/e) hence s(Ys) > ~ 7 2 as above. Thus (i) Yse I. One of Y S p 1Y, has size > i ( i ( 4 - 4/e) - e3 - 2/e) = a (say) > r,, sos(Ys-') > a - e3 hence (ii) Y(s-l)e I. By (i) and (ii) Y e nyl I , contradiction:
+
nrl
nrl
3 24
J. L. Britton, The existence of infinite Burnside Groups
§ 18 Summary In this section we prove Axiom 8.16.
18.1. Notation. We shall write u A instead of Im'A (cf. 6.16). We shall also use the notation PA as follows. Suppose B is a subword of X and also a subword of another word Y ;then any subword A of X such that A C B is also a subword, which will be denoted b y P A , of Y . Of course A = PA.Thus p maps certain subwords of X to subwords of Y . 18.2. Proposition. Let A X C 7 B X D , where each side is (j)-bounded by k,,, j < n and A or B is Iand C o r D is I. Let M be maximal i-normal in A X C and properly contained in X . Let s ( M ) > ~ 7 3 As. sume vM exists and let uM, p M be different subwords of BXD. Then there exists k > 1 such that for s = 1, ..., k ( i )(up)'M exists and has size > u74;(vp),M meets C, or (ii) (vp),M' exists and has size > 2'74; (vp),M' meets D, where M' is pM. Proof. 1 O . If J is Max j-normal in A X C or B X D and s(J) > ul0 then by 6.23 since k,, < kk, kb, uJ exists and either s ( u J ) > s ( J ) - u3 o r s ( v J ) > 1 -s(./)-u2> 1- ~ ~ - k ~ ~ = a s a y . 2". pM is maximal normal in B X D . Both uM, upM exist since 1 i 7 3 > i d l o . Now upM is different from M otherwise VM = uupM = p M by 6.19. Now s ( v M ) > Min(u,, - u 3 , a) > ul0 so if upM is left of M then by 6.20 uupM is left of uM, i.e., p M is left of v p p M , i.e., M' is left of vpM'. Thus without loss of generality M is left of u p M ; we shall prove (i). We use the notation K , = p M , M , = u K , , p M i = Ki+,, M i = vKi. upM = M , has size Z Min(a, u73- u 3 ) > ~ 7 +4 u3 > I t is sufficient t o prove for s = 1 , 2 , 3 , ... . (*) M , exists * s(M,) > u7, and M,-, is left of M , (where M , means M ) . For if k is the largest integer s such that M , exists then pMk cannot exist, otherwise M k + , = upMk would exist because u74> ul0; hence M , d X , i.e., M , meets C. We may assume M 2 exists otherwise (*) holds. Also
J.L. Britton, The existence of infinite Burnside Groups
325
Now consider the following s(lCZ2)> Min(a, s ( M l ) - u 3 ) > statement P(t), t 2 2 : M , exists and has size > 2174, ( M , M 2 ) P ( 2 ) is true since fi (M,-2, M , ) and ( M , M , ) + i 1 u74 > U24 and k48 < k i 2 , k13 (cf. 8.8). Assume P(2), ..., P(t ) true. Then we may assume M,+, exists; otherwise ( * ) holds. Hence M i is left of Mi+l ( i = 0, 1 , ..., t ) . By 8.15 since k4, < k,,, lc17;
7
2174
> u29;
and similarly ( M t - l , M , ) fi ( M , M , ) . Apply 9.1 1 taking S, U, T,S ' , T' to be M,M,,M,,M,-,, M,,,; this is possible since S ( M , + ~ ) > Min(a, u74 - u 3 ) > ~ 3 0 Min(a, , u73- u 3 ) > u j , and li,, < k18, k19. We conclude that U' exists where ( M , - ] , U ' ) fi ( M , M , ) and s ( U ' ) > Min(a - u g , u73- 2u3) - u4 - e3 = > uj,. Thus 0 have U' ( M t - , , U ' ) (M,-,, M,). By 9.12 since u74 > uj, > ~ 3 we is M,. Now s(M,+,) > Min(a, s(M,) - u 3 ) 2 Min(a,P - u 3 ) > Thus P(t + 1 ) is true and (*) is proved.
18.2A. Corollary. The proposition remains true if placed by u73+ ~ 9 0 , + ~ 9 respectively. 0
1174
are re-
Proof. Examine the P.C.'s in the proof of 18.2 and use - u90 > 2u3 + u4 + e3 + u74 and u74 = u73- ~ 9 0 .
QI
18.3. Proposition. Axiom 8.16 holds for n + 1, i.e., if 0, O'are ( n + 1)-preobjects and 0 is an adjustment of 0' and also 0 n ~ 0' l then 0 = 0'. Proof. 0 is (S, T ) where S, T are subelements of Rep(Ln+,) of size
> u21, hence ( n + 1)-normal, and S, T determine distinct maximal ( n + 1)-normal subwords S, 7 and where s=SH then s ( H ) < u22, Similarly for T. 0 is @)-bounded by k,, and ( n + 1)-bounded by '13.
Similarly 0' = ( S ' , T ' ) . Now S F AS,, S' = BS, where A or B is I . Similarly T = ToC, T' f ToD , C or D being I .
.1.L. Britton, The existence of infinite Burnside Groups
3 26
1". Let ( S i , T o )f S O X ' ;then 0 = A S o X ' B , 0' = C S o X ' D . Let H, K be the kernels of S o , To. Then ( S o ,To)= HA K for some A . D exists such that D is (n)-bounded by bmin and H A K ; D.Now s ( H ) > s(So) - ro - e3 - 2/e > u21 - ro - e3 - 2/e > u l , so H > Ho; ;Ho' and s ( H o )> s ( H ) - u l . H o has the form HL and Ho' the form DL,so H L ; ;D L . Similarly KO = K R ; D R . Also D FZ DLD M D R for some D M . Since s(HL)> u21- ro - e3 - 2/e 11 = 8 say and since HL is a subelement of Rep L , + we may apply Axiom 3 1B (8 > ~ 3 1 bmin, ; str' < b31). We obtain a word H L L E D L R ,(n)-bounded by Max(bmin,str+)+ q 3 1 = cp say. Now cp < k12 and s(HLL)> s(HL)- ~ 3 > 1 8 -~ 3 > 1 ro + e 3 . Similarly there is a word D R LFKRR where s(KRR)> 8 - r j l . Moreover ~
,
HA K
;HLLEDLRD MDRLF K R R = J , say,
where J is (n)-bounded by cp. Let S: = H L L ,S* = AS:, TO*= K R R , T* F TZC. Then (S,T ) = A ( S , , To)C ; AJC = (S*, T *) and (S*, T * ) is (n)-bounded by cp and ( n + 1)-bounded b y k,, + u4. Next
s(AS,)
< s ( A )+ s(So) + 2/e
where $ = ( R , + 2e3) + 2/e + r31+ u1 + y o + e3 + 2/e. Thus s(S*) > 1~~~ - $ = 2421 . By 6.14A, since k12 < b2,, u21 - e3 2 U 6 + u4 + € 3 and 1421 - J/ e3 > 146 we have Im s" = S. Hence ~
< s(S*) + u;2 + 2/e where 1fz2= $ + 1422 + 114 + e3. Similarly BJD = ( S t * ,T'*) where if X temporarily denotes St* or T'* then s ( X ) > u& and s ( X ) < s ( X ) + u22 + 2/e. Write 0" (S", T*),
J.L. Britton, The existence of infinite Burnside Groups
327
0'" = (Sf*, TI*). Although these are not preobjects in general, (S*, T * ) n ~ (S'*, l TI*),S'* = BS:, TI* = S:D. 2". We claim that it is sufficient to prove O* = Or*. Let 0" 2 O'*. Then A J C - BJD. Among the left subwords of J that are subelements of RepLn+l let U have maximal length. Then HLLC U . If U = J we would have = T* so Im s*= Im T*, i.e., T. Hence U J . Say J = UV. Thus A U V C - BUVD. A U is the
s=
+
largest left subword of A UVC which is a subelement of Rep Ln + l . H e n c e A U = B U . H e n c e C - D a n d O = 0'. 3". Case 1. 0 " ; 0'" Write kT2 for rp, kT3 for k13+ u4. Take j minimal such that O* = 0'". If j = 0 there is nothing to do so let j > 0. There are divisions jl,P,, ... and Q1, Q2, ... where some Pi has type j . We have O* = AJC, O'* = BJD, (S:, T t ) = J = S t X say. We first show (j-)S* contains a maximal j-normal subword of size > u75; by translation it is sufficient to show AS: or BS: does. Since k! < s(Pi) + s(QJ)< s(P,')+ kr2 < s(c.) + e3 + kr2 we have s(pi)> k! - e3 - kr2 > u75;thus we may assume Q AS:, hence Pi C SgXC and similarly Qi C SZXD. Now C or D is I ; say C is I. Then C S t X so the subword p p i of Of* exists. We prove p p j is not Qi. If p c . = Qi then by 6.22 since kT2 < k,, k7 we have QI c ppi =_ = EPfF where s ( E ) ,s ( F ) < u l . Hence s(QJ n E ) < Max(ro, u1 + e 3 )and
c.
s(Qi n Pi') 2 s(Qi) - 4/e - 2Max(ro, u1 + e 3 )
> k!
-
kT2 - 4/e - 2Max(ro, u1 + e 3 ) > ~ 4 0 .
This contradicts Axiom 40 since kr2 < b40 (and By the dual of 18.2A (with M = pi),since
s(Pi) > k:
-
e3 - kT2 > u73+ ~
9 and 0
X;:: QJX,'E Li).
kr2 < k,,,
a maximal i-normal subword of size > u74+ ~ 9 =0 u73 meets A or B and hence is contained in AS: or BS;. (Since S* or S'* is S: we have s(S:) > u& > rb.) Similarly if D is I. (t)follows since u73= u ? ~ .
J.L. Britton, The existence of infinite Burnside Groups
328
4". Without loss of generality assume B = 1. If A = I then C =1 D , i.e., C = I or I = D ; since kr, < b , we have by Axiom 10 that C = D = and O 4 = 0'" as required. Thus we may suppose that A $ I . For the next part of the argument we shall assume only that
f
(1)
AS:XC
7 S:XD
(instead of =). Let N , be the nice subword of the form (AS:)L I having maximal length. Since s(AS:) > u;, we have as in 6.8 s ( N , ) > u& - u2 - 2/e = y say. Then N, N; C S:XD. Let N, be the nice subword of S Z X D of the form StLhaving maximal length. Then s(N2)> y > s33 and N , N i c ASgXC. Let N , n N i . Then N N ' = N i n N,. Either N is N , or N' is N 2 x b y A x i o m 33 for 12 + 1 N = N ' . Hence s(N) > y > yo. Each of AS:, Sg has size > u& - e3 > u6 + u4 + e3 and k f , < b,, hence (cf. 6.14A) In1 = Hence
-
-
-
Ag ST.
s(sg) > s(As;) - u4
- €3
s(z).
also s(S:) + u;, + 2/e > Thus s ( A ) < u;, + 2/e + (yo + 2 e 3 ) + + u4 + c3 = u , say. Next A C N otherwise s ( N ) < s ( A ) + e3 < a + e3 + y , a contradiction. Thus N 3 AS:' say and s(SR') > y - a - 2/e = b , say. Now N ' is a left subword of S l , N ' = So*" say and has size > y. C, W exist such that AS,*W = Ce E Rep L n + l .By Axiom 19 and 13.21, L(S:')/L(Ce) > b - e3 - ( e r + 3/e) = b' say and b' > 5(a + + 3/e) + 3/e > 5 ( L ( A ) / L ( C e )+) 3/e so L(S,*)/L(C) > 5 L ( A ) / L ( C )+ 3 . But L(S:')/L(C) > b'e > 1 and since AS,*' S t L w e see that A =_ CKfor some k > 0. By (t)A S ; contains a maximal j-normal subword F', which may be assumed proper, of size > u75 = u73.Let F be the leftmost translate in AS: of F'. Where AS: = A'FB we have L ( A ' )< L ( C ) . For any integer N 2 1, F C Ce C CeN and we can consider the translates F, F 1 ,F 2 , ... of F in C e N ;here e.g., F 2 means F + + . NOW L((F, F 6 k ) )< 6k.L(C) + 2L(C) SO
ET
J.L. Britton, The existence of infinite Burnside Groups
329
L(A'(F, F 6 k ) )< ( 6 k + 3 ) L ( C ) < k L ( C ) + L(S,*') = L(ASz'). Thus A'(F, F 6 k )is a left subword of AS:'. With respect to ( 1 ) let uF = T, , p T , = F,, ..., uFi = T i ,pT, = Fi+,, ... . F , means F. Since u73> u and kr2 < kb, k $ , T , exists and T = F so s ( T , ) > u73.Since (F, Fdo ) has length k L ( C ) = L ( A ) ,F k C So, I'-so
vpFk exists; in fact it coincides with F. Thus F2 = pvF exists and coincides with F k . Similarly Fi+, exists and coincides with Fik (i = 1,2, ..., 6). Thus T, , T,, ..., T7 exist. By 8.15, which is available since kr, < k16, k17 and u73> ~ 2 9 (, T , , T 3 )2 ( F , , F 3 )= (F, F 2 k ) ; (since AS:' = StLwe have even ( F , , F 3 ) = ( T , , T 3 ) ) .Let p be maximal such that Tp exists; then p > 7. By 18.2 Tp meets D , hence (In O'*, T p )3 S:X = (S:, T:), and T,, ..., Tp have size > Using that p Ti = Fi + we have F , , F 2 ,..., Fp have size > u ? ~ . We prove by induction on s that if 1 < i < j < s
,
This is true for s = 3. Assume true for some s, 3 < s < p . Then TS+,exists and by 8.15, since u74> u29,if 2 < u < u < s + 1
In particular this holds when u = s - 1, v = s + 1 and when u = s - 1, u = s. By induction hypothesis ( T , , T,) fi (F, F ( s - l ) k ) By . 9.14, since kr2 < k,,, k,, and u74 > ~ 3 1 (, T , , Ts+,)fi (F, F"). Thus the result is true for s + 1. We now have
S t X D = A ' T , R for some R . Since L ( A ' ) / L ( C e )< l / e we have either s ( A ' ) < yo or by Axiom 19 and 13.21 s ( A ' ) < e3 + l / e + + E; + 3/e = {' say; hence s ( A ' ) < Max(ro, {') = { say. Tp meets D, so where S, = S: n ( T , , T p )we have s(S1) 2 u;, - 2/e - { > Max(ro + e3, ~ 9 5 ) .
330
J.L. Brittor;, The existence of infinite Burnside Groups
5". The word ( T , , T p )contains T,* which has size > u;,. The maximal normal subwords of ( T I ,T p )determined by S , , TO* are distinct and of size > 2195; we shall show later that, in view of (2), this is a contradictory situation. 6". Case 2. Not Case I . Here (S*, 7'") n ~ (S'*, l T'*). Using the same notation for the divisions, some Pi has type n + 1 . then by 6.24, since We claim that + s*.For if pi = k*,2 . < . k'8,. k *1 3 < k $ ;u;, - e3 > ul0, Qi = S!?. Let g = Max(ro, u1 + e3).
..
We have u;, - 4/e - 2(.$ + e2 + 2/e) > ~ 4 0 Since . s(Sg) > g, we can write S$ AB' where A is of minimal length such that s ( A ) > .$. Then where A = A a ( L ( a )= 1 ), s ( A ) < 5 + e2 + 2/e so s(B') >, s(Sz) - 2/e - (g + e2 + 2/e) > [. Thus S z = ABC where s(C) > g, s(B ) > s40.Now S: C Pi. = EP,! F where E, F have size < u l . Then A C E and C C F , so B C Pf. Similarly B C QI. B is (n)bounded by kT2 < b40; this is a contradiction by Axiom 40. Similarly # Tg. Hence C (S;, T:) and ppi exists. Now pPi # Qi otherwise we could obtain a contradiction by Axiom 40. Since S: < Pi < TG we have pS: < pPi < pTZ so pP # S'*,T S . Dually for Qi; in particular pQi exists. If ppi < Qi then < pQi; thus without loss of generality we may suppose Q j < ppi. Now 3'" < Qi; thus s'*and ppi are disjoint. Now < pQi < Pi so S*,pi are disjoint. Now kT2 < kb, kr3 < kb, k: - kT3 - e3 > ul0 and zi;, - e3 > tilo; thus we have S X < U < Qi where U is Im' pQi; it follows that s'*and Qi. are disjoint. Also s ( U ) > k: - k*13-'3-'4. Take the leftmost pi of type n + 1 . Then P,-P2- ... .Pi-, has the form S*J for some J . S*J meets o r touches pi, so S*'J meets o r touches p c . . Q i . ... . Qi-, is disjoint from ppi and contains S'*, hence it has the form S*'JL.Let U , be the part of U outside Qi. Then S*'JL contains S'* and U , and
,
c.
<
s*
s( U , ) >, s( U ) - 2 / e - (Yo + E 3 ) 2 k!
Now S*J
-
kT3 - e3 - 1l4 - 2/e - (yo
7S*'JL,i.e.,
+ e 3 )= q
say.
J.L. Britton, The existence of infinite Burnside Groups
(3)
331
A S , * J ~ J ~B S ; J ~
where J - J L J R and j is the maximum type of P,, ..., Pi-l; thus
j < n.
First suppose j = 0 or A = B. Since S*, S'* are maximum subelements of Rep L n + l ,j = 0 implies A f B. Hence A 3 B , so C n ~ Dl. Since C or D is Z we may use Axiom 10 t o conclude that C = D and 0 = 0'. Now let j > 0 and A f B . We show that S$ contains maximal j-normal subwords of size > u 7 3 .Consider a Q iof type j . If QiC BSZ then, by considering translates, S$ contains a maximal normal subword as required. If $ BSZ then QiC S $ J L and pQi exists and is different from (by Axiom 40) so 18.2A is ; if pi < p Q i available ( k & < k 4 8 ;k: - kr2 - e3 > u73+ ~ 9 0 ) hence then a maximal normal subword of size > meets A , but if p o i < then a maximal normal subword of size > u73 meets B . Now (3) has the form
oi c.
(3')
ASZJLJR7 S$JL
or ( 3" )
BS; J~
S; J~ J~
according as B or A is Z;(3') and (3") are of the same form as ( 1 ). Hence the argument of 4" is available; in particular we have " T p meets D" which shows that (3') is impossible, hence (3") holds. Hence Tp meets J R , so (In S t , T p ) 3S Z J L 3 ( S $ , U , ) . Hence ( T I ,T p )contains S , and U,. We have seen that s(S1) 2 u g 5 .Now note that s ( U , ) > r ) 2 u g 5 ,and S , , U , are distinct maximal normal subwords of ( T I, T p ) . 7 " . Thus in both Case 1, Case 2 we have (2), where p 2 7 and the right side is a subpowerelement of Rep L , + so is (j)-bounded by str+ < k S 9 .The left side is (j)-bounded by kF2 < k S 9 .Moreover ( T , , T p )contains two distinct maximal normal subwords, each of size > ug5 2 ug3.By 14, since u73 > u74 > ~ 3 0 the , right side of (2) contains t w o distinct maximal ( n + 1)-normal subwords. This is a contradiction.
J. I,. Britton, The existence of infinite Bitrnside Groups
332
§ 19
19.1. Note. All axioms have now been proved true for n + 1 except Axioms 5 and 29 which we shall discuss in this section. All previous results proved for n and not based on Axioms 5 or 29 are true for n + 1. 19.2. We shall consider a sequence
Y , , Y,,
..., Y,, k
Thus for i = 1, ..., k
-
2 2, Yi u n + ,Yi+,(i = I , ..., k - I).
1 we have Y i , Y j + lE J n + l and either
or some h f ( Y i )nyl some e q r ( Y i + , ) .
nzl
19.2A. We refer to 19.2 as Situation A. A special case of Situation A is when Y , Y,: call this Situation A+. Sitzdution B is as follows: Y , , Y,, ..., Y,E J n + l are given and for S. t. i = 1 ,..., k - l ( Y i l ) n T l ( Y ; + ; ) , s i > l , t i > 1. +
19.2B. We can find ei = f 1 ( i = 1 , ..., k ) such that X i = YFi and for i = 1 , ..., lc - 1 we have in Situation A 1. (x~?) = (x~!:,), 1 < si < t i , or 2. someahf(Xi)- some eqr(Xi+,) and moreover h f ( X i ) is a subword of X T for some positive m (of length < f e L ( X i ) ) and eq,(Xi+,)is a subword of X z l for some positive rn (of length > q'eL(Xi+,)).Similarly in Situation B S. t. 3 . ( X iI ) % ( X i ; ), si 2 1 , ti 2 1.
,
19.3. Choose an integer N > 0 to be kept fixed. We show that if, for some i, si and ti exist then they may be taken Z N and that if ti and si+lboth exist they may be taken to be equal; we shall therefore write s i + l instead of ti in 1 and 3. We need only remark that ( A ) s ( B ) implies (A') z (B') for any integer r # 0, by Axiom 1 1.
J.L. Britton, The existence of infinite Burnside Groups
333
Denote the left side of 1 , 2 , 3 by A i and the right side by B i + l By 5.1 1, A i and Bi+l are ( ( n + 1))-bounded by str+.
19.4. Note. If 1 or 3 holds, thenAi = B i + l , a maximal ( n + 1)normal subword S of one of A i , B i + l ,where s(S) > u & , determines by 16.3A a maximal normal Im* S = S’ in the other such that either Is(S) -s(S’)I < ui(:or Is@) + s(S’) - 11 < u;. Also u2 < u z . u3 < ui(: and uro Z ul0. Moreover a cyclic word Di exist such that A i n+l Di n+! B i + l , Im’(1m‘S) is S’ (where Im‘ is in the sense of 6.21) and D iis ( ( n + 1))bounded by Max(str+,k i 4 ) + ~ 4 < 0 k,,, k23, k16, k17. 19.5. Proposition. In Situation A or B , let B k contain a maximal ( n + 1)-normal subword S o f size > u67. Then A , contains a maximal ( n + 1)-normal subword of size > u68. Proof. Since us7 Z uro A k - 1 contains a maximal ( n + 1)-normal subword of size > u68 2 uro for either s(1m‘S) 2 1 - str+- u; > 2d67 > u68 or s ( h ‘ S )> u67 -Ui(: > u68. Assume Ai contains a maximal ( n + 1)-normal J of size > u68 for some j , 2 < j < k - 1. Then we show that Ai-l does. We have the following cases
where we have identified one of Bi, Ai with a subword of the other. Since J is a subword of a power of Xi we have L ( J ) < 2L(Xi) so in Case 111 some translate of J lies in Bi. In the other case J C Ai C Bi. Thus Bi contains a maximal ( n + 1)-normal subword
334
J.L. Britton, The existence of infinite Burnside Groups
of size > 2168 hence, by translation, at least si 2 N if Bi is cyclic and > -3 + q’e if Bi is linear. If Bi is linear call the two outermost of these maximal normals extrernal, we shall eventually identify this concept with the “extremal” in 10.3. Consider the sequence
For any linear B , in (1 ) except B , we define its extremal subwords similarly. For B , take the outermost maximal normals of size > 2467 as its extremal subwords. For any linear A i in (1) (then B i + l is linear) define its extremal subwords as the images (cf. 6.16) with respect to A i B i + l of the extremal subwords of B i + l ;they have size > - u; = u69. Each term of ( 1 ) except Ai-l contains a maximal normal subword of size > u68. A j - l contains a maximal normal subword of size > u69. Hence each cyclic term contains at least si 2 N > 3 maximal normals of size > u69. In Case IV we have for some A, B , C
-
e q , ( X j ) ABC,
Sf(Xj) B
L ( A ) 2 3L(Xi),
L ( B ) 2 3L(Xi)
since L ( e q , ( X j ) ) L(Gf(Xi)) > L(X,) (q‘e - f e ) > 8 L ( X i ) since 4’ > j + 8 / e . Thus without loss of generality we may suppose that the subword of Bi with which Ai was identified is of the form of B above. Hence B is central in e q , ( X j ) ,i.e., B lies between the extremals of eq,(Xi). For a cyclic word all subwords are central. Call a subword of one o!‘ ( 1 ) C.N. if it is central and maximal normal. Say a C.N. word is initial special if its size is > u69. Certain C.N. words are called special as follows: 1. Any initial special word is special. 2. If X is special in one of A i , B i + l and its image Y(lm‘ or Im*) in the other exists (hence Y is maximal normal and central) then Y is special. 3 . If X is special in one of B i , A i and is central in the other then it is special in the other.
J.L. Britton, The existence of infinite Burnside Groups
335
4. If X is special and X ' is a translate of X and X ' is central then X ' is special. We claim that any special word U has size > u33.There is a sequence C , , C2,... , c k where ck = U, C, is initial special and C,+ arises from C, as in 2 , 3 or 4 ( u = 1, ..., k - I ) . Thus C, is a subword of one of the words ( I ) say W,; thus W , is A f c u or , Rfc,,, say (u = 1 , ..., k ) . If C,+, is Im* C, then W , = W U + ]; let D, be chosen as in 19.4 such that W , - D,- W , + , . The assumptions of Section 10 apply t o the sequence obtained from W , , W 2 , ..., w k by inserting D, between W , , W,,+l whenever D , exists (str+< k 2 , , k23; 4 9 > ~ 3 2 ; Min(u69 - u 3 , 1 - S t Y + - u 2 ) 2 u32). If C,+, arises from C, as in 2, then if C,+, = Im' C, we may regard C, +. Cu+las a transformation 2a of 10.2; if Cu+l= Im* C, we may regard C, C,+, as a pair of transformations of type 2b. If C,+, arises as in 3 we may regard C, C U + ,as a transformation 3a, 3b, 3c or the trivial case of 2b (when ;is -). Now let CU+, arise from C, as in 4. We consider two examples. (i) C, is C.N. in Ai = hf (Xi) and Cu+l = Ci is central and Ai = PC,QC,+,R. Then W , = Ai,W u + l =_ Ai.We may regard C, +. C,+, as a transformation of the form 3a of Section 10 where for J , we take the word constructed from two copies of Ai by identifying the C, of the first copy with the C,+, of the second copy; thus J , is a subword of a power of Xi. (ii) C, C Ai = XisJ. Here we may regard C, -+ C,+, as a transformation of the form 2b; the X u of 2b is the linearization of Ai starting with C,, the Y,+l of 2b is the linearization of A i starting with C,+] (and = Y,+,). By 10.4, since s(C,) > u69 > ~ 3 2 we , see that c k =_ U has size > u 3 3 ,as required. Consider any term W of ( 1 ) and let its special subwords be S , , ..., S, (then Y > 2). If W is cyclic the translate Si is Sp+lsay and Sf = Sp+i for all i (if p + i > Y let S p + i mean Sq where y = p + i (mod Y)). If W is linear and Si is central then S; = S , + p say and +
+
x,
336
J. I,. Britton, The existence of infinite Burnside Groups
If however S; is not central (then W is of the form A , ) choose any p 2 Y and then (2) holds vacuously. Call p the period of W . 2". We prove that without loss of generality the periods of B i , Ai are the same. Case I is trivial. In the other three cases let the special subwords of W , where W is that one of B,, A i which is a subword of the other, be S , , ..., S,. These are central, hence special in the other word W' by the remark about Case IV so the special subwords of W' are ...,S , , S,, ..., S,, ... . If S; C ( S , , S,) then S; = S l + pand both periods are p . In the opposite case the period of W is arbitrary 2 a while the period p of W' is determined but 2 a. Hence the period of W can be taken to be p . 3". Let ni denote the period of Bi and A i . For the remainder of 3". We consider Situation A only. We prove
ni >
(i = j - 1 , ...) k - 1).
If 1 of 19.2B holds then the number of special words in each side is the same; for any special word S has size > u332 uro so Im* S exists, hence Im* S is special. Hence nisi = ni+lsi+l.But si < si+l hence ni > ni+,.Now let 2 hold. Let m be the number of special subwords in S,(Xi) and eqt(Xi+,). Then by 2.16A I m/ni - Zi/L(Xi)I < 3 , I r n / ~ ~ Zi+l/L(Xi+l)l + ~ < 3 where Zi is the length of the subword generated by the two extremal subwords of A , ; similarly for Zi+l. Thus
Hence m/ni < 3 + f e < q'e - 5 < m/ni+l so that ni > 7ri+,. Note: Since nk 2 1 we have ni 2 k + 1 - j . Also note that the number of special subwords in any Bi is > ni(q'e - 5 ) since n,N > n,(q'e - 5 ) (take N > q'e - 5 ) . 4". Next we show that, in Situation A or B, there exist three special subwords A , R, C of B , each of size > u67 and special subwords A ' , R', C' of Ai-,such that
J.L. Britton, The existence of infinite Burnside Groups
337
If follows that Ai-l contains a maximal normal subword of size
> U68 as required; to see this use 9.1 1 (str+ < k18, k19; 2467 2= u~~ 2 ~ 3 0 2467 ; 2 u j 0 ) and
where (A,B ) fi (A',B " ) and
S(B") > Min(1 - S t r + - U 2
we have that B"
-
U4 - € 3 ,
Us7 - U 3
C
(A',B', C') exists
-
Uq - € 3 )
> U j o , U68.
Hence (A',B ' ) 2 (A',B " ) . By 9.12 ( u 2~u j ~0 )B" isB'. In Situation B, if we take r consecutive special subwords in B i + l there are r corresponding special subwords in A i and, since I applies, for any r consecutive specials in A i there are r corresponding specials in Bi. Thus if we take r consecutive specials in B , including three A , B, C of size > us7 there will be r corresponding specials in Ai-, of which A', B', C' say correspond to A , B, C. Note that, in any case, if S, Tare distinct specials in some term of (1) then (S,T ) is an ( n + 1)-object, and moreover if S ' , T' are specials in some term of (1 ) and S' = Im' S, T' = Im' T then (S, T ) 2 (S', T ' ) ;this is by 8.1 5 since s t r + < k16, k17 and u~~ 2 ~ 2 9 . This remains true if Im' is replaced by Im* because, as we have seen, any D j has ( ( n + 1))-bound < Min(k16, k 1 7 ) . Now consider Situation A. We prove that to any rn consecutive specials of B , where rn < rk (q'e - 6), say s d + l , ..., s d + , , there exist rn consecutive specials u d + l , ..., U,+, of Ai-, such that ( s d + j , s d + j ) fi ( u d + j , u d + j ) for all i, j such that 1 < i < j < m. Any r consecutive specials in B j + l determine by 2 above r consecutive specials inAi. Take r consecutive specials a h + l ,..., in A j . In Cases I, 11, IV there are determined r consecutive specials of B i . In Case I11 denote the specials of A i by a , , ..., at without loss of generality and denote those of B j by a x ,..., a y where I < x < y < t and 1 < h + 1 < h + r < t. One of a x ,a , , , , ..., C Y , + ~ - ~ ( p = r i )is a translate of a h + l say a c + l .For a x ,..., a y to contain a c + l ,..., ac+ we require c + r < y which is so if y + 1 - x 2 p + r - 1. Now y + 1 - x > ri(q'e - 5 ) 2 ti+ r > p + r - 1 if r < nj(q'e- 6). Thus if we take r consecutive specials of B , where r < "k (q'e - 6) then since r k < rj (i = j - 1, ..., k ) there are r corresponding specials in Ai-l as required. Let T,, T2, ..., Tb be the specials in B,. Then b > rk(q'e - 5 ) > 3nk
338
J.L. Britton, The existence of infinite Burnside Groups
and at least three of T , , T,, ..., T3*, have size > 2167. Since 3 r k < 7rk(qfe- 4 ) , T , , T,, ..., T3nkhave images U,, U,, ..., U3*, in Aj-1.
19.6. Corollary. In Situation A , if B, contains properly a maximal ( n + 1 )-normal subword o f size > u67 then k is at most equal to the number of maximal ( n + l)-normal subwords o f size > u33 in XE. Proof. Let there be r special subwords in A 1 . Without loss of generality the period x, is at most r. But xl > k , hence k < r. Any special subword is maximal normal of size > u33.If A , is a f ( X 1 ) then A , C X p . If A , is Xi' then A , contains X;' and the number of specials, hence maximal normal subwords, in X;' is > x,,hence the number of maximal normals in XE is > 7r1 2 k.
19.6A. For any word M let p i ( M ) = L ( M ) / L ( X ; ' ) ( i = 1, ..., k ) 19.6B. In Situation A there are two cases: Case (a) j exists such that 2 of 19.2B holds (with i replaced by j ) ; Case (b) not Case (a). In Case (a) let i denote the largest such j . Then A i B i + , and B j + l has the form E ~ , ( X ~ It+ may ~ ) . happen that L ( B i + l )> 4 e L ( X i + l ) , i.e., B,+l also has the form E ~ ( X ~ if+ so ~ )define ; q" to be 4 ; if not define y r f to be 4'. Thus p i + l (B,+l) > 4".
-
19.7. Proposition. In Situation A, let B , contain a maximal ( n + 1)-normal subword ojsize > uS7. Then in Case ( a ) there are subwords A o.f A , , B c1.f B, such that p1( A ) < f + 61e, p k ( B ) > 4" - 16/e and (t)there is a word A LCBDAR,( ( n + 1))-bounded by Ic,, and equal to A in G , + , . In Case ( b ) we have ( b 1 ) if a subword B o j B k is given and 4 / e < p k ( B ) < p k (B,) - 12/e then there is u subword A o f A , such that p l ( A )< p k ( B ) + + 14/e and again (t)holds. Also Nle < p k ( B k ) . ( b 2 ) if a subword A o f A , is given and p , ( A ) > 9/e then there is a subword B o j B, such that ( B )> p1( A ) - 12/e and again (-1) ho Ids.
J.L. Britton, The existence of infinite Burnside Groups
339
Proof. ( b l ) Let b be the number of specials of B , in B . Then I b/7rk - L(B)/L(X,)I< 3. Now 4L(Xk) < L ( B ) < L(B,) - 1 2L(X,) so b > 7rk (L(B)/L(X,) - 3 ) 2 7rk 2 1 , hence b > 2. Now B , 1 XB Y where L(X) = L ( Y ) = 6L(Xk). The number of specials in X is at least four since 7rk(6 - 3 ) > 3. Thus there are specials V l , ..., V , of B , such that those in B are V s , ..., Vm-,; b = m - 8. By 4" above there are specials U , , ..., U, of A such that A = ( U , , U, ) -h ( V , , V , ). B y 9 . 1 5 , ~ i n c e u ~u39 ~ >a n d s t r + < k 2 4 , A n 5 1U f E ( V F , Vk-,)FU,", where the right side is ( ( n + 1))-bounded by Max(str+, k i 4 ) + ~ 4 -0 = k43. We have ( V F , V k - l ) > (V,, V m - 3 > ) B . Now I L ( A ) / L ( X , ) - m/7rl 1 < 3 so
,
p l ( A ) < m/e7r, + 3 / e < ( b + 8)/enk+ 3 / e
< b/e7rk + 1 l / e < p k ( B ) + 14/e
p ( A ) < m/e7rl + 3 / e < ( b + 8)/e7rk+ 3 / e
< b/en, + 1 l / e < p ( B ) + 14/e (b2). Let 8 = p, ( A ) . Let the specials of A , in A be say U , , ..., U,. Then m/7r, > L ( A ) / L ( X , )- 3 = Oe - 3 > 6 , so m > 7 . These m specials of A determine m specials V , , ..., V , of B,. Let A ' = (Ul, U,) B = (V,, V,-3). Then
,
L(B)/L(X,)
> (m-6)/xk-3
2 m/7rk-9
> m/nl-9 > Be- 12
(a) In the proof of 19.5 we saw that Y consecutive specials of A i determine Y of Bi, hence Y of A i - , , if Y < ni(q'e - 6). Since 7ri < ni-, < ... < 7rl it follows that if Y < 7ri(q'e - 6 ) then Y consecutive specials of A i determine Y of A
,.
340
J.L. Britton, The existence of infinite Burnside Groups
In the present case the total number t of specials in Ai = af(Xi) satisfies t/7rj < L ( h f ( X i ) ) / L ( X j+ ) 3 < ef + 3 < q'e - 6 so they determine specials U , , ..., Ut of A 1 . The number of specials in Bi+l is also t , and t/ri+I> - 3 + (L(Eq"(Xi+l))-2L(Xi+1))/L(Xj+l)> q''e-5-
If i < k - 1 , Bi+, c X , " s ' z ... z X i k , so the specials of Bi+l determine t specials of B, say Vl , ..., V , . This is also true if i = k - 1. Finally L( V 4 ,Vt-3)/L(X,) > ( t - 6)/7rk - 3 2 t/7ri+l - 9 > q"e - 14
L(U,, Ut)/L(X,)
< t/7r1 + 3 < t/ni + 3 < ef + 6
19.8. Consider Situation A. For i = 1 , ..., k - 1 let r(i) be the least integer q such that A i Bi+lor A i ; R i + l . Then 0 < r ( i ) < y2 + 1. If r ( i ) > 0 then A j and%j+l contain maximal r(i)-normals of size > 1 -str+ - u ; > q0. Call k - 1 critical; and if 1 < j < k - 2 call j critical if r ( j ) > Max(r(j + l ), ..., r ( k - 1)). Let the critical integers be h, , A, ..., h, in ascending order, where h, is k - 1. Put A, = 0. Let 0 < i < j < t , put a = hi, b = Xi, and consider
calling this sequence Eii. We shall consider two cases: ( l + ) A u r 7 u ) B v + l( u = a + l , ...,b ) i.e., 1 holds throughout Eij, and moreover we do not have that 1 holds throughout ti-lior that 1 holds throughout tii + l . (2') j = i + 1 and 1 does not hold throughout Eii. First consider (1 +): If i > 0 then a is critical; i < j < t so
J.L. Britton, The existence of infinite Burnside Groups
341
a = hi < A, = k - 1, hence r(a) > Max(r(a + l ), ..., r(k - 1 )) 2 0, so B,+, contains maximal r(a)-normal subwords of size > 2 ~ hence 7 ~ so does A , + , since A , + , is cyclic. Now Situation B holds for tijand Situation B is left-right symmetrical. By examination of the P.C.'s used, 19.5 holds if u67, u68 are replaced by uk7 = u 7 0 ,zik8 = u67 respectively, since u70 > u67 > u68; 1 -str+ - v g > uk-,; 1 -str+-uz-Uq - E 3 > ub8; Ub7 > u& + v:; uk7 > ub8 + u 3 + u4 + € 3 . Hence Bb+, contains an r(a)-normal subword of size > ubs = 2467. By 19.7 we have (*) if B C Bb+l and 4/e < p ( B ) < ( N - 12)/e then there is a subword A of A , + , such that A = ALCBDAR,which we abbreviate t o A = - B - , a n d ~ , + ~ ( A ) Max r(u) over u > h , which is 2 0. If 1 < u < A, then r(u) < r(X,) since X, is the smallest critical integer. We prove B h 1 + ,contains an r(X,)-normal subword of size > that Bb+, contains an r(hl)-normal subword of size > u67. If h, = b this is trivial since q02 u67. If h , < b then a + 1 = 1 < h , + 1 < b ; hence A k l + is in tijso is cyclic, and contains an r(hl)-normal subword of size > ~ 7 0 Arguing . as before, B b + , contains an r(hl)-norma1 subword of size > u67. Thus (*) holds. If i = 0 and t = 1 then a = 0, b = k - 1. If r(b) # 0 then B b + , contains an r(b)-normal subword of size > u70 and ( * ) holds. If r(b) = 0 then A , + , f Bb+,; also L(X,+,) 2 L(X,+,) since s,+~ < s ~ + Thus ~ . (*)holds takingA = B (then P , + ~ ( A ) < P~+~(B)). Consider (2+): None of r(a + l ) , ..., r(b - 1) is > r(b). If r(b) > 0 then B b + , contains an r(b)-normal subword of size > 1170 > u67, hence by 19.7 there are subwords A of A , + , , B of B b + , where
,
&+l
(A)
pb+,(B)> 4"- 16/e, and A
=
-B-.
This is also true if r(b) = 0.
19.9. Proposition. In Situatiorz A + either (i) XsinYl X l ! S 1 (i = 1 , ..., k - l ) , or (ii) A , contains a subword A ' a n d B , contains a subword B' where p k ( B ' ) > q - 28/e, p , ( A ' ) < f+ 20/e and A' AfLCB'DArR where the right side is ((n + 1))-bounded by k44.
nrl
J.L. Britton, The existence of infinite Burnside Groups
342
Proof. Assume (i) is false. Then some t i .satisfies (2+). Assume j chosen maximally. Thus either j = t or $it satisfies ( 1 +).Also j = i + 1. Moreover, for the largest u such that A,- B,,, we have
-
6 f ( X , ) eq ( X u + , )(where we have q instead of 4'). There is a subset k,, k , , ..., kp of 0, 1, ..., j such that k , = 0, k P = j , k p - , = i a n d [ k , k i + l ~ a t i ~ f i e ~ ( 1 + ) o r ( 2 +,..., ) ( i =p-1). 0 The following is true for u = p 1 and we prove by induction that it is true for u = 0, 1, ..., p.- 1. (**) For tk the first term contains A' and the last term conU P tains B' such that A' = -B'-, p ( B ' ) > 4 - 16/e and either (i) p ( A ' ) < f + 20/e and l k U k usatisfies +] ( i +), or (ii) p ( A ' ) < f + 6/e. Assume that (**) is true for some u , 0 < u < p - 1. First suppose that (i) holds. Then Ek,-, k , satisfies (2+). Hence its first term contains A" and its last term contains B" where A" = - B"- and p ( B " ) > 4' - 16/e, p ( A " )< f + 6/e. Since 4' > f + 37/e we have p ( R " ) > p ( A ' ) + lie, so L(B") > L ( A ' )+ L(Xd+,) where d = X k u , hence some translate of A' is contained in B " , since A' C A d + , , B " c B d + l . Hence A" = --B"- = -B'-. Now suppose that (ii) holds. If tk,-,k , satisfies (1 +)take the B of (2:) to be A' if p ( A r )Z 4/e while if p ( A ' ) < 4/e take B t o satisfy p ( B ) = 5/e (then B contains a translate o fA' ); this is possible since without loss of generality p ( R ) < f + 6/e < ( N - 12)/e. Then p ( A ) < p ( B ) + 14/c < f + 20/e. If tku-, k , satisfies (2') some translate of A' is contained in B" since p ( A ' ) + lie < f'+ 7 / e < q ' - 16/e < p(B"). Thus by induction, ( * * ) is true for u = 0. Thus Eii has first term containing A' and last term containing B' where p ( B ' ) > q - 16/e and p ( A ' ) < f ' + 20/e. If j = t we have finished since k , = k43. If j # t apply (b2) with A defined t o be B ' ; ( q - 16/e > 9/e). ~
19.10. Proposition. There is n o infinite sequence Y , , Y , , Y 3 ,... slrch that Y j u , , + ~Y j + ]( i = 1 , 2,3, ...), i.e., Axiom 5 holds f o r n Proof. Assume not. Again let r(i) be the least q such that
+ 1.
J. I,. Britton, The existence of infinite Burnside Groups
343
Yi uq Yi+,. Then 0 < r(i) < n + I . Let t = Max r(i) for i = 1 , 2 , 3 , ... . Then t < n + 1. If t < n + 1 then Yiun Yi+,(i = 1 , 2 , ...) contrary t o Axiom 5. Hence = n + 1. Consider Y pU , ( ~ ) , Y ~where v( p ) = E, and consider Y , , ..., YP+,.Now YP+lcontains a maximal t-normal subword so by 19.6 some N exists such that p + 1 < N then r ( i ) < t < n + 1, so Yiun Yi+, ( i = N ,N + 1, ...), a contradiction.
+,,
19.11. Proposition. Axiom 29 holdsjorn + l;i.e., i j X E J , Y E Cn+, and X >n Y then either (j-) some af(X)containsa subelement of L n + l of size > 4 0 , or (j-j-) X s ;U-' Y t . U for some U E II and some s, t such that 1 < s < (tl. Proof. 19.9 is available (with n instead of n + l ) , with X , = X ' , , X , = Y " . If (i) holds then (tt)holds. Now let (ii) hold. A subword A' of a positive power of X , and a subword B' of a positive power of X, exist such that pl(A') < f+ 20/e, p,(B') > q - 2 8 / e , and A' ; A ' L CB'DAlR. Taking a subword of B' if necessary we may without loss of generality suppose B' is a subword of Xi = Y t e E Ln+,. Now s""(B') > L ( B ' ) / L ( X z )- 3 / e - > 4 - 3 1 / e - E : > u g . Since 6.10 holds for n + 1, A' contains a subelem e n t o f L,+, o f ~ i z e > q - 3 1 / e - 1 ( ~ - ~ ~ ( k ~ < b , ~ ) . Let A ' = A I A , where L ( A 1 )= [ L ( A ' ) ] .T h e n A l or A , contains a subelement of 1 of size > ( q - 3 1/ e - ET - u4) - 1 / e = ~ 4 0N. o w L ( A 1 ) G L ( A , ) < i ( 1 + L ( A ' ) ) .
ET
,+,
1
:
+ L ( A ' )< L ( X , ) + L ( X , ) ( e f + 20) =
L ( X , ) ( e f + 21)< 2 e f L ( X 1 ) .
Hence A , and A , each have the form a f ( X , ) = a f ( X ) .
344
J.L. Britton, The existence of infinite Burnside Groups
20.1. We now know that all the axioms hold for n + 1 so it remains to complete the proof of the infiniteness of BS; as described in the introduction to Chapter 11. 20.2. Proposition. If f o r some W E TI we have
then fl;=o J , is not empty. Proof. We use the results of Section 17. For n = 1 , 2 , 3 , ..., choose W , such that W conj, W , E Jn and X conj, W * B,(W,) < B,(X) + E where E = l/e3. Since W conjn+l W , Bn+l(W,+l) < B,+,(W) + E . Since W conj, W,,B,+,(W) = B,+l(Wn). Hence
Since W , E J,, (W,) is (n)-bounded by str < k45. By 17.15 B,+1 ( W n ) < ~ 7 orB,(W,) 1 > 2B,+,(W,). Case 1 . B,(W,) > 2B,+,(W,) ( n = 1 , 2 , 3 , ...) Then
> 2(2(B3( W , )
-E
)
-E
)
> ...
Let s be the least integer such that B l ( W l ) / u 6 3 < 2s and s 2- 1. Let t>s;weprove(i)Bt+l(Wt)=O,(ii)B,+l(Ws+l)=O. Assume B t + l ( W t )> 0; then B t + l( W , ) > u63 and
B l (W,)> 2tB,+1(Wt)- ~ ( 2 ' - l +2t-2 + ... + 2 ) > 2tu63 - ~ ( 2 ' -2 )
J. L. Brifton, The existence of infinite Burnside Groups
345
Since U S 3 > 2/e3. Hence 2'< 2'-' < B,(W,)/US3. This proves (i). Now W , conj, W conj,,, W S + , hence W , conj, W S + , and 0 = B , + l ( W , ) = =Bt+l(W,+l) proving (ii). Now we prove W,+ E n J,. We have W s + l E JS+,c J , c ... c J,. Assume inductively that W s + l E J , for some t > s. Then B t + , ( W S + , ) = = 0 < U71 and ( W , + , ) is (t)-bounded by str = k46. Hence by 17.16 ( W , + , ) is ( ( t + 1))-bounded by str; thus W S + ,E J,+,. Case 2. Not Case 1. For some s = 1 , 2 , 3 , ... B,+,(W,) < ~ 7 1 We . prove B t + l ( W , ) < ~ 7 (t1 = s, s + 1, ...). This is true for t = s; assume inductively that B,+l ( W , ) < ~ 7 for 1 some t 2 s. Then B t + , ( W t + , ) < B t + l ( W t ) + ~ < ~ 7 1 +IfBt+2(Wr+l)> ~ . u~~ thenby 17.15 ~ 7> 1 B,+, ( W , + , ) - E > 2B,+, ( W , + , ) - E 2 2u7, - e . Hence E > ~ 7 21 l/e3, a contradiction. Hence B t + , ( W t + , ) < ~ 7 1 . Now for t 2 s W , conj, W conj, W , so W , conj, W , . Hence B , + l ( W , ) = B , + l ( W , ) < ~ 7 1 Now . W , E J , C JSW1 C ... C J,. Assume W, E J , for some t 2 s. (W,) is ((t))-bounded by str and Bt+, ( W , ) < ~ 7 hence 1 ( W , ) is ((t + 1))-bounded by str. Hence W , E J t + , and W , E n Jn by induction.
,
20.3. Proposition. n;=, Jn is empty. Hence by 20.2 we have B; = qc,,c,, c,, ... 1.
Proof. Suppose not and let U E n J,. Let F be the least integer Now UF has only a finite number of subwords X , , ..., X r . If X i is a subelement of some li of size > qo then j is unique. Hence p exists such that UF contains no subelement of of size > qo. Lp+l u Lp+, u Let rn 2 1. Then U E J , so U $ C, and U E Jm-l.By 5.7
> 1 +fe.
( 3 Y )Y E
c,, u>,-,
Y.
By Axiom 29 either (a,) some t i f ( U )contains a subelement of 1, of size > qo, or T-'. Y t . T , 1 < s < I tl. (b,) Us Let 1 < rn < rn; we prove that not both (b,), (b,,) hold. Y r t ' T', . Y ' E CmlY r eE L,. YIe = I in Otherwise Us'
J.L. Britton, The existence of infinite Burnside Groups
346
Hence in G,-l we have YtsCe = T . U S S r T-' e. = TIT-' = 1. Now Y E C, C J,-l so by 5.12 Y k # I in Gm-l ( k = 1 , 2 , ...), a contradiction. Hence (a,) holds for infinitely many m. Since U F 3 6f (U)' G,nvhence in
- TTI-1 y l t ' s e -
G,n-l.
we have the desired contradiction.
Apart from the consistency of the P.C.'s, this completes the proof of the infiniteness of B$ for all sufficiently large odd e (d 2 2), and we note that B$ is a Generalized Tartakovskii Group.
5 21. Consistency 21.1. Preliminary remarks. In the text, beginning with Section 5, the parameter conditions (P.C.), i.e., equations or inequalities involving parameters only, are emphasized oniy at first, since the reader will soon perceive that the P.C. in a given section of the text are easily identifiable, an understanding of the text being unnecessary for this purpose. The parameters not in the axioms but arising in the text are mainly denoted by the letters ti, k with numerical subscripts. Occasionally Greek letters are used for temporary abbreviations for expressions involving parameters. 21.2. The main parameters may be taken t o have values as in the following table, where E = 1 O-*. Parameter
.f'
Value
e-g
rb 7
zill
ro
r'
r"
r
-E
Moreover
4' = rb -O(l /c) y = Yo
~
O(rb)
q" = t i l l
r"
= Y"
-
-
O(rb) qo = q
O ( r o ) c" = r"
-
O(rb)
+ O(ro)
Here u l l and r" do not occur i n the axioms; they first occur in 7.3.
J.L. Britton, The existence of infinite Burnside Groups
347
21.4. The parameters in the :iiain text may be taken to have orders as follows. O(rb>:
u4
uifori=1,2,3,4,8,12,13,14,16,20,37,41,48,49, 60,62,63,64,65,81,91,92,94,96,97,98, 99 O ( r o ) : uj for j = 1 , 2 , 3 , 5 , 8 ui for i = 5 , 6 , 7 , 9 , 10,21,22,23,24,25,26,27,28, 29,30,31,32,33,39,40,42,43,44,45,46, 47,50,51,52,54, 56,57,59,61.66,67,68, 69,70,71,72,73,74,75,77,78,79,80,82, 83,84,89,90,93,95 u'. for j = 10, 15,28,30,40,43,83,78,79,84,67,68 * vi r d6 , i i i o , ufo, ti u2, 1-O(r): lci for i = 1 , 2 , 3 , 4 , 6 , 8 , 10, 12, 14, 16, 18,20,22,24, 25,26,27,28,29,30,31,34,36,43,44,47, 48,52,53,54,55,56,57,58,59,60,61 k', , kg , ki2, ki4 l-O(ro): ki f o r i = 5 , 7 , 9 , 13, 15, 17, 19,21,23,32,33,35,37 k y , k:, k:, k $ , k ; , k i 3 , ki5, 2i58 + O(ro):1ci for i = 39,40,41,42,45,46,50, 5 1
To,
O( 1 /el: O(r): O(r"):
"35
I
k;4
€1 €5 u36 9
r6 zi34/e
3
4.
348
J . L. Britton, The existence of infinite Burnside Groups
This completes the proof that for all sufficiently large odd e (d 2 2) B: is infinite and is a Generalized Tartakovskii Group.
References [ 1 ] M. Greendlinger, On Dehn's algorithm for the word problem, Comm. Pure App. Math. 1 3 (1960) 67-83. [ 2 ] J . Leech, A problem o n strings of beads, Math. Gaz. 41, No. 338 (1957) 277-278. [ 3 ] R.C. Lyndon, On Dehn's algorithm, Math. Ann. 166 (1966) 208-228. [4] M. Morse and C.A. Hedlund, Unending chess, symbolic dynamics and a problem in semi-groups, Duks Math. J . 11 (1944) 1 - 7 . [ 5 ] P.S. Novikov and S.I. Adjan, On infinite periodic groups, Izv. Akad. Nauk SSSR, Ser. Mat. 32,212-214, 251-524,709-731 (Russian). 161 V.A. Tartakovskii, Solution of the word problem for groups with a k-reduced basis fork > 6, Izv. Akad. Nauk SSSR, Ser. Mat. 13 (1949), 483-494 (Russian).
THE ALGEBRAIC INVARIANCE OF THE WORD PROBLEM IN GROUPS
F.B. CANNONITO” University of California, Irvine
This paper will be a sequel t o my paper [ 21 ; accordingly, I will lean very heavily on it for notation and concepts. Let K , and K , be two subclasses of the class of recursive functions such that K , C K , and K , # K,. Later, candidates will be proposed for K , and K , ; for the present the intuition is this: functions in K , \ K , are more costly to compute than those in K , . I will use K , and K , in connection with the word problem (w.p. henceforth) in finitely generated (f.g.) groups, in order t o discover sufficient conditions on K , and K , which will insure that the “cost” of the solution of the w . ~ is . an algebraic invariant of the group. That is, if K , and K , are properly chosen, then either all f.g. presentations of the group have w.p. solvable by a function in K , or they all have w.p. solvable only by a function from K 2 \ K , . When K , and K , are properly chosen 1 will call them “properly chosen.” The restriction t o f.g. presentations is not artificial since groups can be presented on infinitely many generators so that the w.p. for the infinite system is unsolvable even though this is not so for f.g. presentations. On the other hand, it makes sense to ask if the cost is an algebraic invariant of f.g. presentations since Kabin has shown that when one f.g. presentation has a solvable w.p. so must presentation has a solvable w.p. so must any other, although conceivably the cost might vary. Of course, some reasonable measures of cost may not turn o u t t o be algebraic invariants, neither must two distinct measures be compatible - - that is, assign the *This work was supported by AFOSR Grant No. 1321-67. 349
350
F.B. Cannonito, Algebraic invariance of the word problem
same relative cost on different groups. At any rate, in this paper I will only consider conditions on K , and K , which are sufficient t o insure the invariance of cost and leave the other questions t o ano t he r work . Hvnceforth, for any positive integer n , let the expression ( " n ) appearing in the margin indicate a condition o n K , (and K 2 ) , the integer to serve for bookkeeping purposes. Thus, assume a fixed Gadel numbering y of the words on the alphabet a l , a,, a3... such that the free groups of rank ns< 00, denoted Fn and presented as ( L ( , , ..., a, I ), have the property
Fn has a K , -admissible index y consisting of the set y(Fn ) of integers (indices), the (induced) multiplication rn : y(Fn), y(Fn), and the (induced) inverse function IN : y(Fn)+ y(Fn).
(* 11
--f
Note. In [ 2 ) the admissible indices were specifically ta-admissible, where C" is a member of the Grzegorczyk hierarchy. Here, K , (or K,) will replace the € a , mutatis mutandis. (Sometimes I will write Ki or K for either K , and K , .)
I t is possible to proceed as in [ 21 and define arbitrary Ki-admissible indices ( i = 1,2) for f.g. groups. But with certain exceptions, discussed below, the most natural way to index a group is from the index y of F,, given a presentation II of the group in the form ( a, , ..., a,, I R , S, T, ... ). Such indices are called standard indices in [ 2 1 . Intuitively considered, a standard index for a group with presentation n is obtained ny assigning each coset in Fn/N, ( N = the normal closure of R , S, T, .._in F,) its minimal index. From the proof of Theorem 5.1 of [ 21 we see when the K isatisfy (*2) K , contains the constant functions and K , is closed under the functions + , * , L , substitution, bounded sums: Z , and bounded u
then the propositional connectives, and the bounded quantifiers do not lead o u t of the class of K , decidable relations, and K , is closed under the bounded p-operator. Identical properties hold for
F.B. Cannonito, Algebraic invariance of the word problem
35 1
Note. From (*2) it follows that K , (hence K 2 ) contains the Kalmar elementary functions; cf. Kleene [ 101 p. 285, for la/b] is definable from the functions and operators given in (*2) given the K , definability of “<” and “<”. But these follow from L . In particular, when (*1) and (“2) hold, the condition K , C K 2 implies that for a group presented as Fn/N, the solvability of its w.p. by a K j function, (i = 1,2), implies that F,/N has a Ki-admissible standard index, for this is precisely the content of Theorem 5.1 of
[21.
Note. In order to define the relation E(Y,s) on the indices which holds when and only when the element with index Y, denoted by gr (likewise g,) determines the same coset as g s , it is necessary t o assume the logical conjunction of K , -decidable (resp. K 2 -decidable) relations is K , -decidable (resp. K2-decidable), (cf. p. 380, line 1 1 , of [ 21 ). If the characteristic function CR of a relation R is 0 on the extension of R and 1 otherwise, then C,,, = C, + C, I CR * C,. O n the other hand, CTR = 1 1 C, and so assuming (*2) gives the closure of the Ki-relations under all propositional connectives. It remains to be seen if under narrower assumptions on K , than those given, K , is sufficiently expressive so that ( * 1 ) is satisfied. In connection with this David Thompson, in a private communication, has shown that the Fn have E 2-admissible standard indices, but not E -standard indices. Conversely, when Fn/N has a Ki-admissible (standard) index i . we want t o conclude that the w.p. is Kj-decidable. For this t o be so, we must be able to deduce the Ki-decidability of y (N). From Theorem 5.2 of 121, this will be the case when the natural homomorphism cp : F, + Fn/N is Kj-computable with respect to y and i. At this point let m e recall the definition of the n t h iterate of a function f . That is, given f , a number-theoretic function, we define g(n) “the nth iterate off’” by the recursion
352
F.B. Cannonito, Algebraic invariance of the word problem
Since the operation in the set of indices corresponding to exponentiation of an element of the group is iteration of the induced multiplication function, and since the K-normal form property (cf. Definition 5.3 of [ 21 ) involves such iteration, we obtain the next condition on K, and K2 , namely ( " 3 ) the nth iterate of a K, (resp. K2) function is a K, (resp. K 2 ) function.
Note. Condition ( " 3 ) taken with (*2) implies K , contains the primitive recursive functions. Cf. Pkter [ 151 Section 7. When all conditions thus far assumed on Ki are satisfied we conclude, via Theorem 5.2 and Theorem 5.3 of [2] that the Ki solvability of the w.p. in Fn/N is a consequence of the existence of a Ki-admissible standard index for Fn/N. All that remains is to show the analog of Corollary 7.1 of [2] holds. That is, the Ki decidability of the w.p. is an algebraic invariant. Thus, assume Fn/N and F , /M are two f.g. presentations of the same group and IJ is an isomorphism Fn/N = F, /M. Further, assume F n / N has a Ki-admissible standard index for fixed i = 1,2. I want t o show F,/M has a Ki-admissible standard index. For this purpose it is sufficient t o show M is Ki-decidable in F, since F,,, has a Ki-admissible index by (* I). First, observe that if a group G has any Ki-admissible index i, then all its standard indices are Ki-admissible. For, suppose G is presented as F,/M. Since Fn has a Ki-admissible index for which it has the K , -normal form properly and ( * 3 ) holds, the natural homomorphism F , -+ F,/M is Ki computable, whence the assertion (cf. Lemma 7.1 of [ 21 ). To complete the argument, take Fn/N as G and invoke the equivalence of the Ki-decidability of the w.p. and the existence of a Ki-admissible standard index (cf. Theorem 7.1 of [ 21 ). Thus, I have shown that ( * l ) , ("2) and ( " 3 ) are sufficient t o insure the algebraic invariance of the cost of the w.p. with respect to f.g. presentations. This may be summarized in the
F.B. Cannonito, Algebraic invariance of the word problems
353
Result A . Let K , and K , be as above. In order that K , and K 2 be properly chosen, it is sufficient that K , (resp. K 2 ) be closed under the primitive recursive functions andlor relations and the free groups Fn have K , -admissible standard indices. To some extent the program of discovering how t o insure that K , and K 2 are properly chosen is incomplete, for I ought to show that there are groups whose w.p. is restricted t o either K , or K , \ K , . Succinctly put: that there is adequate pathology for K , and K,: As it turns out, for the choices I will propose for K , and K , the “pathological” groups exist. There is, however, some doubt
in my mind concerning whether or not one ought always t o strive for finitely presented pathology. Of course, before it is known that finitely presented pathological groups exist - and with the hindsight we presently have regarding how difficult it was, initially at least, to obtain such groups - it probably is very reasonable t o insist on producing finitely presented groups before agreeing that a (more or less) profound concept has been apprehended. However, with the exception, possibly, of the residually finite groups for which it is clear that finite presentability is fundamental (because the w.p. for f.g. residually finite (r.f.) groups may be unsolvable in general while the finitely presented r.f. groups have solvable w.P., cf. V.H. Dyson [ 4 ] , or A.W. Mostowski [ 141 ) it seems clear that for the purposes of algebra the more important concept is “finitely generated”. Hence, if one produces f.g. pathological groups one ought t o feel that the significance of the K , and K , is reasonably well established, especially if we can produce f.g. recursively presented pathological groups, for there is every reason to believe that having done so, the finitely presented pathological groups will be forthcoming through the Higman embedding technique (such reasons t o become apparent below). Indeed, for the choices of K , and K , t o be proposed, the Higman embedding does furnish the finitely presented pathological groups. Thus, I also want the condition (*4) there exist f.g. recursively presented groups with w.p. solvable by K , functions (resp. by K , \ K , but not K , functions).
354
F.B. Cannonito, Algebraic invariance of the word problem
Note. The requirement that the group be both recursively presented and have a solvable w.p. is redundant since a f.g. group, which has a solvable w.p. with respect t o a finite system of generators, can be recursively presented with respect to these generators because the multiplication table of the group is then r.e. Of course, the converse does not hold. That is, not every f.g. recursively presented group has a solvable w.p. For the first candidates for K , and K,, I will take the primitive recursive (p.r.) functions and the recursive functions, respectively. The f*, then have admissible p.r. indexings (in fact, elementary indexings) by Lemma 4.1 of [ 21. Clearly ("n) for n = 2 , 3 are immediate and ( * 4 ) follows from Theorem 7.2 of [ 21, choosing, e.g. 01 = 4 and (Y = w + 1. My student R.W. Gatterdam has shown in his doctoral dissertation [ 71 that the Higman embedding technique prererves p.r. solvability of the word problem. To fix ideas, let G be recursively presented and let the Higman process, denoted by il, take G into finitely presented G, ; in diagrams G '1GH . Then, h i t t e r d a m has shown that H is a p.r. process and the set of indices of the image o f G in GI, is p.r. decidable in the solution t o the w.p. of Hence, for G possessing K , (= p.r. functions)-admissible index. we obtain GH with K1-admissible index; that is, a finitely presentable group with K , -decidable w.p. However for G possessing K 7 \ K , but not K , -admissible index we obtain f.p. G, with K ; \ K , decidable w.p. but not K , -decidable w.p. Because, if G, has K , solvable w.p. given, say, by function f , then the function g(.u) = ( . f ' ( x )x, E H ( G )
1*
, otherwise,
solves the w.p. in G and is K , contrary t o assumption; ("*" denotes any convenient value outside of H ( G ) ) .Hence, we have
Result B. Prirnitive recursiveness o j t h e solution of the w.p.is an ulgebruic invariant of'finitely generuted groups.
F.B. Cannonito, Algebraic invariance of the word problem
355
Note. Boone has announced in his paper [ 11, footnote 4, p. 50, the existence of a finite presentation with recursive but not p.r. solvable w.p. Applying the analysis above, J am able t o assert, for this group, the algebraic invariance of its word problem. But, in any event combining Result B, the case a = o + 1 of [ 21, Theorem 7.2, o r Theorems 7 and 8 of [ 31, and the construction of Gatterdam [ 71 gives
Result C. We can construct a finitely presented group G with algebraically invariant recursive but not p.r. solution to its w.p. A somewhat more provocative choice for K , and K , devolves as follows: If T(a, b, c) is the (intuitive) Kleene T-predicate, let 7 (x, y , z ) be a formula of the normal number theory N either as given in Mendelson [ 131 or in Kin0 [ 9 ] or Kleene [ 10,111, which expresses T . That is, if o is the standard model of", let
t 7(a, b, c ) when o I= T(a, b, c ) , N and N
7(a, b, c ) when not o t= T(a, b, c).
We say a (number theoretjc) function f : o -+ w is provably recursive in N if .f has an index e such that
Vx '7
3 y s ( e , x,y ) .
It is easy to see not every recursive f is probably recursive in N (cf. Fischer [ 61, Theorem 5.1). In fact, as Enderton has shown [ 51, n o recursive function need be provably recursive in N . I assume the formula 7 is chosen so that, at least, all p.r. functions are provably recursive; this is always possible as Kin0 has shown in [ 91 . Thus, let K , be the functions provably recursive in N and take K , t o be all recursive functions. Then ("1) holds because of the assumption on 7 and my Lemma 4.1 in [ 2 ] . Likewise ("2) and ("3) hold because of the assumption on 7, and because if g is a
356
F.B. Cannonito, Algebraic invariance of the word problem
function p.r. in provably recursive functionsfi,f., ._.,f m , then g is provably recursive (cf. Property 4.1 in [ 51 ). Condition (*4) is
also immediate, cf. the discussion for the preceding choice of K , and K,, mutatis mutandis, and the Theorem 8.3 of Fischer [61 which shows there is a recursive but not provably recursive set of integers. (Alternately, the existence of such a set follows from the existence of a recursive but not provably recursive enumeration of the provably recursive functions, the construction given in my Lemma 3.1 of [ 21, and Property 4.1 of Fischer [ 61 ). Note. From (“4) and the fact (alluded to above) that the Higman embedding process preserves provable recursiveness we deduce the amusing consequence, given in Result D below: there exists a finitely presentable group with intuitively solvable w.p. such that it is not possible to prove in formal number theory that the solution is a recursive function. Consider this result in the light of objections given by some mathematicians (e.g. Wang [ 171 , p. 89, and Peter [ 151 ) to the converse of Church’s thesis: every recursive function is effectively computable. That is, a function is recursive if it has an index e such that (+)
w b V x 3 y T(e,x, y ) .
However, nothing is said, in general, about how y is determined by x. Alternately, for the machine interpretation of T(a, b, c ) given by Kleene in [ 101 p. 243, nothing is said regarding how the length c of the computation depends, a priori, on the input b. It is not altogether convincing that functions for which property (+) holds are effectively when y is not known to depend on x in some satisfactory way. The argument from experience which goes - all functions known on intuitive grounds to be effectively computable are, in fact, recursive - really does not insure that some proper subclass of the recursive functions might not already contain all such algorithms. Yet, if one chooses t o regard the class of functions provably recursive in (say) N (with respect t o a “realistic” formula 7 )as the true class of effectively computable functions we can deduce an anomalous version (Result D) of the Novikov-Boone
.
F.B. Cannonito, Algebraic invariance of the word problem
351
theorem in which the “bad” group has, on intuitive grounds, a “solvable” w.p. despite the fact that on formal grounds its w.p. is unsolvable! (However, cf. Kleene [ 101 , paragraph 3 of footnote 17 1 on p. 241 for a discussion of the converse t o Church’s thesis in which the converse is framed so that, in Kleene’s view, it is not contestible. Kreisel has written me, as well as published elsewhere, concerning his view o n Church’s thesis. He argues that it is necessary t o make a distinction between the concepts “mechanical” and “constructive” and, if one identifies these, then it is hard, if not impossible, t o doubt Church’s thesis. Presumably this means the converse is not in doubt whatever the view on mechanical vs. constructive.) In summary, then, we have by means of Gatterdam’s analysis [ 71 ,
Result D. We can construct a finitely presented group with algebraically invariant recursive but not provably recursive solution to its w.p. Note. The “effective” construction of the groups of Results C, D and E follows from the effectivity of Gatterdam’s construction and from the effective construction of sets of integers with characteristic functions of suitable subrecursive degree of solvability. Here, by subrecursive degree, 1 mean solvable by a K , or K , function for properly chosen K , or K,. The existence of suitable characteristic functions is not difficult to obtain. F o r example, refer t o Lemma 3.1 of [ 21. For the recursive vs. provably recursive case use the recursive but not provably recursive function which enumerates the provably recursive functions of N . The “effective” existence of such a function follows from the fact that N is an axiomatic formal theory, (cf. Mendelson [ 131, p. 29 (3)). Similarly one can show the Peter function is actually provably recursive and obtain Result E, mutatis mutandis. Another choice for K , and K , are the p.r. functions and the provably recursive functions. The discussion above carries over immediately, it only being necessary t o note that Rosza PCter’s recursive but not p.r. function cp enumerating the p.r. functions can
358
F.R. Cannonito, Algebraic invariance of the word problem
be shown, using Kino’s characterization of provably recursive functions, t o be provably recursive since cp is given by a transfinite induction up t o 0 2(cf. ; PCter [ 161, p. 125 f.) From this we obtain the existence of a set of integers which is provably recursive but not p.r. Such a set can be used t o satisfy (*4) in the standard riianner (cf. my Theorem 7.2 of [ 21 for the details). I state for the record the
R m i l t E. We can construct a ,finitely presented group with algehr-aicalh~invariant provably recursive but not p.r. solution to its \t’. p . At this point it is tempting t o try to carry o u t the above arguments for the finer degrees of the Grzegorczyk hierarchy. That is, take K , as 6 and K , as 8 a + k for fixed cy 2 3 and k 2 1 (here (Y > 3 since K , needs the elementary functions and probably a bit more). While t o a great extent this can be carried o u t , certain imperfections, which threaten to be of a permanent nature, persist at the present state of science. Since this represents a departure from the point of view in my paper [2] I will go into some detail. The proofs, which are more or less automatic once the difficulties are perceived, will, as usual, be omitted or else published elsewhere. The chief difficulty is encountered in the attempt t o obtain an M a analog of Theorem 5.3 of (21 which holds for suitably chosen K , ( b u t which does not hold precisely as stated in 121 ). This theorem provides the link whereby if we know that one of the quotients G / H of a K , group G has a Ki admissible index then H is K , decidable i n G . T ~ w the , equivalence between the word problem being solvable by Ki functions and the existence of a Ki index for G is established by this theorem (in conjunction with the K , analogs of Theorems 5.1 and 5.2 of [ 21 ). However, for the choice for K , the result of Theorem 5.3 does say. of E a for K , and not go precisely over (despite the incorrect claim in [ 21 that it does). The difficulty lies in showing that the natural homomorp h i m cp : G G / H is foa-computable, even under the assumption G has the E a normal form property. For, if we denote by i and j the & a indice\ in G and C / H respectively, then the index normal +
F.B. Cannonito, Algebraic invariance of the word problem
359
form decomposition of an element x in i ( G ) as x = 7,a! ~ o . . . o T @-r ,, a
goes over under (p to Cp(x) = k T l lo...o k , in j ( G / H ) and there is n o way in general to provide an a priori I%& bound on the iterated a multiplication in j ( G / H ) by which we obtain each kTl I . I t is for this reason that I required in (*3) that K , be closed under iteration. Thus, the best that can be said for the case under consideration is that Cp(x) is Z @ + l computable. Now, we usually apply this reault t o the special case G is a free group of rank n < and i is a standard index, so the iterated multiplications in i ( G ) which give T~~~ cause n o trouble since an 83 bound is available in terms of the Kleene concatenation function x * y . But there seems t o be n o way t o treat the iterations induced in j ( G / H ) by the index normal form owing t o the wholly arbitrary nature of the index j . If, in fact, j is a standard index then there is n o difficulty (but this would be tantamount t o assuming G / H hadan Ea! solvable w.P., the very property we hoped t o deduce from Theorem 5.3). As a consequence of this imperfection in the theory the algebraic invariance of the w.p. with respect t o the M a heirarchy applies only t o standard Ea! indices. It should be noted, however, that it is completely unreasonable t o consider the w.p. with respect t o any other kind of index because only the standard indices effectively relate words in the free group with their corresponding index through the technique of Godelization. In fact, n o way is presently known to construct an example of a non standard index despite the fact that allowance for the existence of these indices must be made. In summary then, all 1 can say is that p(x) is at most Ma!+l computable and accordingly, G/H has an E a + l solvable w.p. It is of minor comfort t o know that this is the worst that can prevail; for, given that G is an ga! computable group, we know that G has at most an standard index. Thus it is conceivable that a group G may have its word problem solvable precisely at level &a!+1 and not lower for any f.g. presentation and yet have an index for which it is an ga! group. It can not have an index at levels less than a! for this would, via the equivalence of w.p. and standard index, give rise to a standard index at ga! and contradict the algebraic invariance at level a! + 1 . For the sake of completeness 1 will list the easily demonstrated properties of 8“ indices for f.g. groups, a! > 3 (GH standing for “Grzegorczyk hierarchy”):
-
F.B. Cannonito, Algebraic invariance of the word problem
360
GH GH GH GH
1. f.g. subgroups of &a groups are
2. 3. 4.
GH 5.
-standard. -standard. G is an 8" group implies G is G is $"-standard implies all standard indices are at most Z a . G is &"-standard but not lower for standard indices implies G i s n o t a n & P g r o u p f o r a n y P < a - 1. &a solvable w.p. is equivalent t o &"-standard. This property is algebraically invariant for f.g. presentations.
A second difficulty occurs in building &" indices for free products with amalgamation of $" groups. Again iteration is the culprit. For, if G, and G , are &a groups with isomorphic subgroups H , < G , and H , < G , and with the isomorphism cp : H , tf H , such that both N, and H, are 8" decidable and cp and cp-l are computable, then the best we can say is G I *pG2 is at most This is because it is natural t o build an index for G,*,G2 from the indices of G I and G, . However the reduction of the product of two normal forms ( h x ,... x , )~( k y ,... y m ) = h ' z , ... z p involves repeated iteration of the process which "slips k past x,, ". In this process the index of the element in the amalgamated subgroup can grow arbitrarily large and hence there is n o a priori &a bound for the entire iteration. Hence G,*,G2 is at most &"+I is the best that can be said. The easily demonstrated revisions of [ 2 ] Section 6 are listed below ( A F P stands for "amalgamated free product"):
AFP 1 . If Gi is &%tandard and Hi < G , is &"-decidable for i = 1 , 2 and cp is an isomorphism of H I and H , such that both cp and g 1are & a computable then G1*,G2 is &"+l-standard. AFP 2. G, *G, is &"-standard when G , and G, are. A F P 3 . 1 f G l = G 2 a n d H 1 = H 2 andcp= 1(;IHthenG1*,G2 is&" standard (under the conditions in AFP 1). As a consequence of AFP 3 we can show the groups Ga+l presented in [ 2 ] as
for certain Ma:'
-decidable subsets Ucu+lof o,are, in fact,
-
F.B. Cannonito, Algebraic invariance of the word problem
36 1
standard and thus, have an &ff+l algebraically invariant w.p. (although conceivably they could have anomalous E f f indices). The next flaw of the &,a heirarchy turns up when we try to follow Gatterdam’s analysis of the Higman embedding. The difficulty is this: at a certain point in the construction it is necessary to pass from a group G and an isomorphism cp : H -+ H’ < G for some H < G t o a new group G, obtained from G by adjoining an infinite cycle t satisfying t k t - l =cp(k) for all k in H . It can be seen that G, is embedded in a certain free product with amalgamation. Consequently this construction preserves K , cost ( [ 71 Theorem 3.1). However, for the E f f hierarchy Gatterdam shows the passage from G t o G, possibly jumps two levels from E a to & f f + 2 and the Higman technique needs (at this state of science) a countable number of applications building a tower T , viz. G, G V l ,(G,, ),*, ... . Hence for the present it appears that the full class of p.r. functions is the minimum class which can accommodate the Higman construction. It remains to be seen if either the jump from gff t o E f f + in passing from G t o G, is necessary, or if (more likely) countably many applications do not force a p.r. index for the union of the tower T t o E f f + k for some k suffices. but rather, only a finite jump from A successful solution t o either problem will suffice to show the Higman embedding preserves the 8“ hierarchy (albeit possibly enThen because the groups tailing a finite shift from && t o %+I are recursively presented, we would conclude there is adequate pathology for the 8“ hierarchy. For the present all that we can say is for any p Z 3 there is a finitely presented (henceforth f.p.) group whose word problem can not be solved at level lower than 0.This is a consequence of Gatterdam’s proof that the Higman embedding preserves p.r. solution to the w.p. Since the groups G&+1 are recursively presented and p.r. they are embeddable in a p.r. group which a fortiori resides at some (unknown) level y of the &“ hierarchy. Then the word problem is solvable at level y + 1. Since the Gff+l have word problems at arbitrarily high levels we
* Cfr. this volume, “The computability of Group Constructions, Part 1,”
by the author and R.W. Gatterdam for a solution to this problem showing the “strong Britton extension” only jumps two levels at most (Theorem 5.3).
362
F.B. Cannonito, Algebraic invariance of the word problem
get the assertion, for the set of 7’s obtained by the embedding is necessarily cofinal in the natural numbers. Note. It may be possible through the use of techniques employed by Boone in [ 1 ] t o go directly from the sets Ua+l t o f.p. groups with w.p. solvable at level but not lower (for k < 00 depending uniformly on a ) . I d o not know whether o r not this program is feasible, but I1.J. Collins and C.F. Miller 111 have expressed belief in the potential fruitfulness of such an approach to finding adequate pathology for the 8 @hierarchy. Finally, with respect t o the g a hierarchy let m e observe that there is n o p.r. group which contains a copy of every f.p. &a group. For suppose such a group G exists. Then being p.r. G is g a for some a . But all f.g. subgroups of G a groups are at most E a + l and we know there are f.p. groups at arbitrarily high levels of the G a hierarchy. Thus the assumption on G is impossible. (I am indebted to Gatterdam for pointing this o u t to me.) Next, I want t o comment on the cost of the w.p. for small cance