# Projective planes I

## Projective planes I

European Journal of Combinatorics 31 (2010) 622–643 Contents lists available at ScienceDirect European Journal of Combinatorics journal homepage: ww...

European Journal of Combinatorics 31 (2010) 622–643

Contents lists available at ScienceDirect

European Journal of Combinatorics journal homepage: www.elsevier.com/locate/ejc

Projective planes I Navin Singhi Tata Institute of Fundamental Research, Colaba, Mumbai, 400 005, India

article

info

Article history: Available online 26 April 2009 Dedicated to Professor Michel Deza

1. Introduction A linear space is a pair S = (X , L), where X is a nonempty set and L is a set of subsets of X such that every pair of elements of X is contained in exactly one element of L. Elements of X are called points while those of L are called lines. A projective space is a linear space containing four points, no three of which are collinear and which satisfies Pasch’s axiom. The Pasch’s axiom essentially states that any pair of lines transversal to a pair of intersecting lines is itself intersecting in a point. Each projective space has a unique dimension (see for more details  or ). A classical theorem of projective geometry states that every projective space of dimension 3 or more is essentially coordinatized by a skew field. The result is not true for a projective plane, i.e., a projective space of dimension 2. For many years, people have believed that a finite projective plane with no proper subplane is coordinatized by a prime field and that the order of a finite projective plane is a power of a prime number. Axiomatizing and classifying projective spaces and related structures has been a very active field. Included among a

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

623

624

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

625

626

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

627

628

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

= = F,

w.

Proof. Suppose x ∈ S. It can be easily checked that length of x for X , as a word in F 0 (S ), is 1 and x is the only word in the class of x with length 1. Also 0 is the only word of length 0. We now assume x 6∈ S ∪{0}. Let x0 be a word in the class of x of smallest length. Now, using the previous observations concerning elements of S, it can be easily checked that we can assume x0 6∈ S ∪ {0}. Hence we can find ai ∈ F and a0i ∈ F 0 (S ) such that a0i ∈ ai , x0 = T (a01 , a02 , a03 ), − a01 + a02 , a01 − a02 or a01 + a02 and length of a0i < length of x0 as words, i = 1, 2, 3. We can assume that the lemma is true for all elements of F (S ) containing words of length less than length of x0 . Hence we can assume that there is a unique word in the class of a0i , i.e. in ai , of smallest length, i = 1, 2 or 3. Now if a0i is not such a word of smallest length in ai then we replace a0i with a word of smallest length in the above expression for x0 . Thus, we get a word in the class of x of length smaller than that of x0 . This contradicts our assumption. Thus we can assume lh(a0i ) and rd(ai ) are well defined for i = 1, 2, 3 and x0 = T (rd(a1 ), rd(a2 ), rd(a3 )), − rd(a1 ) + rd(a2 ), rd(a1 ) − rd(a2 ) or rd(a1 ) + rd(a2 ). Now suppose we have another expression for x, i.e. there exists a word x00 in the class of x, x00 = T (b01 , b02 , b03 ), −b01 + b02 , b01 − b02 or b01 + b02 , where b0i ∈ bi , and bi ∈ F , i = 1, 2, 3.

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

629

Then x00 ∼ x0 . Hence there exists a sequence of words y1 , y2 , . . . , ym ∈ F 0 (S ) in the class of x such that y1 = x0 and ym = x00 and yj+1 can be obtained from yj by applying one of the equations in j

j

j

j

j

j

j

j

j

j

(4.1), 1 ≤ j < m. Let yj = T (a1 , a2 , a3 ), − a1 + a2 , a1 − a2 or a1 + a2 , where ai are words in F 0 (S ). Now, clearly we can also choose the sequence y1 , y2 , . . . , ym in such a way that if the yj , yj+1 j +1

satisfy (4.1)(k), then yj+1 is obtained from yj as follows. For some i = 1, 2 or 3, the word ai obtained by replacing some component of j +1

j

j ai

is

by a word obtained from it by applying (4.1)(a)–(j) and

ai0 = ai0 for i0 6= i, i0 = 1, 2 or 3. We will show that either y1 = ym or y1 can be obtained from ym by ‘reducing’, i.e., lh(y1 ) < lh(ym ). Now consider y2 . We can assume y2 6= y1 . Suppose, y1 and y2 satisfy the equations of (4.1)(a)–(i). Using the fact that y1 has smallest length in the class x, it can be easily seen that lh(y2 ) > lh(y1 ). Thus y1 can be obtained from y2 by ‘reducing’. Since we are considering words with symbol + (i.e. l + q in place of T (1, l, q)), we need not consider (4.1)(j). Suppose y1 , y2 satisfy (4.1)(k). Then again, from what we have described above, since a2i ∼ ai , it follows easily that rd(a2i ) is defined and rd(a2i ) = rd(ai ). Thus again y1 can be obtained from y2 by ‘reducing’. From this one can easily see that in each case lh(y2 ) > lh(y1 ). If m = 2, we have proved the above statement. If m > 2, by considering y2 and y3 and arguments similar to those above one can easily see that either y3 = y1 or y1 can be obtained from y3 by ‘reducing’. For example suppose we have the case (4.1)(a) for the pair y1 , y2 . Suppose y2 = c + (−c + y1 ) for some c ∈ F 0 (S ). Now, first suppose that for the pair y2 , y3 , we have one of the cases (4.1)(a)–(i). Then using the fact that lh(y3 ) ≥ lh(y1 ), one can easily see, by considering each case, that either y3 = y1 or the length of y3 is bigger than that of y1 and y1 occurs as a component of the word y3 . Now suppose that the pair y2 , y3 satisfy (4.1)(k). Using our assumption on yi ’s, this implies that y3 is obtained from y2 = c + (−c + y1 ) by replacing one of the words c , −c or y1 by a word obtained by applying (4.1)(a)–(j) to a component of it. Then using an argument similar to one we have used above and the fact that length of y1 is smallest, one can see that y3 cannot be obtained from y2 by reducing y1 . Thus, if lh(y3 ) ≤ lh(y1 ) then the only possibility is y3 = y1 ; otherwise lh(y3 ) > lh(y1 ) and y3 is obtained from y2 by applying (4.1)(a)–(j) to a component of one of the c’s or y1 . Further, if y1 is replaced by a word obtained from it by applying (4.1)(a)–(j) to it then this word has length bigger than that of y1 . Now, if m ≥ 4, we can use y3 in a similar way to how we have used y2 above and consider y1 and y4 . Proceeding in this way we will get the required statement that y1 = ym or lh(y1 ) < lh(ym ). Statements (ii) and (iii) now follow easily.  For the case of free loops, Higman has given in  a proof of the normal form theorem of Evans , which is essentially an analogue of the above lemma for this case. His argument uses [N , F ] for normal subloops N of F and the elements of the lower central series for a free loop. We will develop in the next section analogues of these concepts for semiadditive rings. However, we note here that a free semiadditive ring F (S ) is also a free loop and the above lemma can also be deduced from Higman’s normal form theorem. The proof of Lemma 4.5 implies a little more than what is mentioned in the statement. Remark 4.6. Let x ∈ F . Suppose x = T (a, b, c ), a − b, − a + b or a + b for some a, b, c ∈ F . Then one of the following (i) (ii) or (iii) is true. (i) rd(x) = T (rd(a), rd(b), rd(c )), rd(a) − rd(b), − rd(a) + rd(b) or rd(a) + rd(b), respectively and the length of each of a, b or c is less than that of x. (ii) x = a − b, − a + b or a + b, and one of the following is true: (I) rd(a) = rd(x) + rd(b), rd(b) − rd(x) or rd(x) − rd(b), respectively. (II) rd(b) = −rd(x) + rd(a), rd(a) + rd(x) or − rd(a) + rd(x), respectively. Note that obviously, lh(a) > lh(x), lh(a) > lh(b), in Case (I), and lh(b) > lh(x), lh(b) > lh(a), in Case (II), respectively. (iii) One of the following is true: (I) a = 0 or b = 0 and x = T (a, b, c ) = c. (II) a = 1 and x = T (a, b, c ) = b + c. (III) b = 1, c = 0 and x = T (a, b, c ) = a. (IV) a = 0 and x = b. (V) b = 0 and x = a. (VI) x = 0, a = b and x = a − b or −a + b.

630

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

We briefly describe how all the cases described in the above remark occur. First consider an element x ∈ F . Suppose x = T (a1 , a2 , a3 ) for some ai ∈ F , i = 1, 2, 3, a1 6= 0, 1, a2 6= 0 and if a2 = 1, a3 6= 0. Thus x 6∈ S ∪ {0}. Using arguments similar to those used in the proof of Lemma 4.5, let us first show that rd(x) = T (rd(a1 ), rd(a2 ), rd(a3 )). We note that, for words x0 = T (rd(a1 ), rd(a2 ), rd(a3 )) and x00 = rd(x), if lh(ai ) < lh(x00 ), i = 1, 2, 3, then clearly using Lemma 4.5 we get x0 = x00 . Hence we can assume that this is not true for at least one i. Thus lh(x00 ) < lh(x0 ). We will show that we get a contradiction. The words x0 and x00 of F 0 (S ) are in the same class, under the relation ∼. Hence, as we have noted in the proof of Lemma 4.5, we can find a sequence of words y1 , y2 , . . . , ym ∈ F 0 (S ) in the class of x such that y1 = x0 , ym = x00 , yj+1 can be obtained from yj by applying one of the equations in j

j

j

j

j

j

j

j

j

j

(4.1), 1 ≤ j < m, and yj 6= x0 for j 6= 1. Let yj = T (a1 , a2 , a3 ), − a1 + a2 , a1 − a2 or a1 + a2 , where ai are words in F 0 (S ). As before, we can also choose a sequence y1 , y2 , . . . , ym in such a way that if the pair j +1 yj , yj+1 satisfies (4.1)(k), then yj+1 is obtained from yj as follows. For some i = 1, 2 or 3, the word ai j

is obtained by replacing some component of ai by a word obtained from it by applying (4.1)(a)–(j) and j +1 ai0

j ai 0

for i 6= i, i = 1, 2 or 3. Now if y1 , y2 satisfy (4.1)(k), using the fact that each a1i is reduced and our other assumptions, it can be easily seen that y2 = T (a21 , a22 , a23 ) and lh(y2 ) > lh(x0 ). Similarly, if y1 , y2 satisfy (4.1)(a)–(j), by arguments similar to those used in the proof of Lemma 4.5, one can easily see that lh(y2 ) > lh(x0 ). Using similar arguments for pairs yj , yj+1 , it can be shown that for all j ≤ m, lh(x0 ) < lh(yj ). Thus, we get lh(x0 ) < lh(x00 ), a contradiction to our assumption. This proves that x0 = x00 . Now suppose x = −a + b, lh(x) ≥ lh(b) > lh(a). Let us also assume that each of a, b, or x 6= 0. From our assumptions, we have rd(b) 6= rd(a) + rd(x). Now, if rd(b) = rd(a) + rd(d) for some d ∈ F then d = −a + b = x and we get a contradiction to the previous statement. Hence we can assume rd(b) 6= rd(a) + rd(d) for any d ∈ F . Now we can show that rd(x) = −rd(a) + rd(b). This follows from Lemma 4.5 if lh(x) > lh(b). Suppose this is not true; then by arguments similar to those used above, by considering a sequence of yj ’s, with y1 = −rd(a) + rd(b) and ym = rd(x), one gets a contradiction. Using similar arguments for other cases, one arrives at the different possibilities described in the above remark.

=

0

0

Remark 4.7. We will consider an ideal generated by a subset of a semiadditive ring in the usual manner. Suppose A is a subset of a semiadditive ring X . The set of all ideals in X containing A is a nonempty set, since X is in this set. The intersection of all ideals in this set is called the ideal generated by A in X and is denoted by (A). We can generate (A) from A by forming words in symbols from A, or T , +, −, 0 etc., in a quite similar manner as we have formed F (S ). Only, now the words are generated using the conditions (3.1) in the definition of an ideal and they already correspond to the elements of X , since the operations are considered in X . Thus, for example for a, b, c , d ∈ A and x, y, z ∈ X , we can get an element w ∈ (A) corresponding to the word w = a +((d +(T (a, b, c )− b))+(T (x, y, z )− T (x + a, y + b, z + c ))) − d. We note that X may not be in general a free semiadditive ring and two different words may correspond to the same element of X . The set of all elements of X corresponding to the words generated in the above described manner is clearly an ideal in X containing A and is contained in all ideals containing A. Hence (A) is precisely this ideal. We can also define XA , the semiadditive subring generated by A in X , and generate the subring from elements of A in a similar way by taking elements of X corresponding to the words obtained by using the conditions in the definition of a semiadditive subring instead of conditions (3.1). In general, even when 1 ∈ X , we will not take the multiplicative identity 1 in XA unless 1 ∈ A. When XA is a free semiadditive ring, XA = F (A), we will also consider the length function on XA , where lh(x, XA ), x ∈ XA , is the length of x considered as an element of the free semiadditive ring F (A). Now, let S be a set with 1 ∈ S. Let S ∗ = S \ {1}. Let t be any symbol not in S ∪ {0}. Let S ∗∗ = S ∗ ∪ {t }. We consider the free semiadditive ring F (S ∗∗ ) not containing the identity, as described in Remark 4.2. Define a map f : S ∗∗ → S by f (t ) = 1 and f (s) = s for s 6= t. Clearly, f can be extended to a homomorphism from F (S ∗∗ ) to F (S ). Now, note that in F (S ) the only extra relations apart from those obtained from relations in F (S ∗∗ ) by changing t to 1 are the ones generated by the equations of (4.1)(i) and (j). Using this one can easily see that the ideal ker(f ) is generated by the set of elements a − b, where a and b are as described in (4.1)(i) and (j) with 1 replaced by t. Thus we have the following.

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

631

632

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

(ii) Let us consider the semiadditive subring A of G generated by S (G). Let x ∈ G; then either x ∈ S (G) or x = T (a1 , a2 , a3 ), a1 − a2 , −a1 + a2 , or a1 + a2 , where ai ∈ G and lh(ai , F ) < lh(x, F ), 1 ≤ i ≤ 3. Now, if any one of ai 6∈ S (G), we can repeat the above process for ai ; proceeding in this way it can be easily seen by induction on lh(x, F ) that there is an element w ∈ A such that rd(w, F ) = rd(x, F ). Thus w = x and x ∈ A. Hence A = G. Thus G is generated by S (G). We will show (see Lemma 4.12 below) that G = F (S (G)). We also note that the above argument implies that some elements of S (G) are components of rd(x, F ) (see also Remark 4.13 below). Lemma 4.12. Let G be a semiadditive subring of F . Then G is a free semiadditive ring on S (G), i.e., the homomorphism iS (G),F is an isomorphism from F (S (G)) onto G. Proof. Let G1 = F (S (G)) be the free semiadditive ring generated by taking S (G) as the set of symbols. Let f : G1 → G be the homomorphism iS (G),F obtained by extending the identity map on S (G). We note that, since G is generated by S (G), iS (G),F (G1 ) = G. Now suppose there exist y1 , y2 ∈ G1 such that f (y1 ) = f (y2 ). We will show that y1 = y2 . This and the above remark then imply the result. Suppose y1 6= y2 . Let us also assume that lh(y1 , G1 ) ≥ lh(y2 , G1 ) and we have chosen y1 of smallest length, for which there exists y2 satisfying these conditions. Now suppose f (y1 ) = 0. Then we can assume that y2 = 0. This implies y1 6∈ S (G) ∪ {0}. Hence y1 = T (q1 , q2 , q3 ), − q1 + q2 , q1 − q2 or q1 + q2 , qi ∈ G1 , lh(qi , G1 ) < lh(y1 , G1 ), i = 1, 2, 3. The assumption on y1 implies that if qi 6= 0 then f (qi ) 6= 0, i = 1, 2, 3. Using this and y1 6= 0, one can easily see that if y1 = T (q1 , q2 , q3 ), we get the contradiction that f (y1 ) = T (f (q1 ), f (q2 ), f (q3 )) 6= 0. Thus we must have y1 = −q1 + q2 , q1 − q2 or q1 + q2 . But this implies f (q1 ) = f (q2 ) or f (0 − q2 ), with q1 6= q2 or 0 − q2 respectively. This contradicts our assumption on y1 . Hence, we can assume that f (y1 ) 6= 0. Also, since y1 6= y2 , lh(y1 , G1 ) ≥ lh(y2 , G1 ) and f (y1 ) = f (y2 ), we can also assume that y1 6∈ S (G). Thus y1 6∈ S (G)∪{0}. Hence, we can assume that rd(y1 , G1 ) = T (rd(q1 , G1 ), rd(q2 , G1 ), rd(q3 , G1 )), rd(q1 , G1 ) − rd(q2 , G1 ), −rd(q1 , G1 ) + rd(q2 , G1 ) or rd(q1 , G1 ) + rd(q2 , G1 ), for some qi ∈ G1 , i = 1, 2, 3. We will use Remark 4.6 to show that the reduced expression for f (y1 ) in F is obtained by replacing G1 , y1 and qi , i = 1, 2, 3, by F , f (y1 ) and f (qi ) respectively, in the above reduced expression for y1 . The above expression for rd(y1 , G1 ) implies that lh(qi , G1 ) < lh(y1 , G1 ), i = 1, 2, 3. Now, if f (qi ) = 0 or y, y ∈ S (G), then for i = 1, 2, 3, qi = 0 or y respectively (note that y = f (y) for y ∈ S (G)); otherwise, we get a contradiction to our assumption on y1 . Suppose y1 = T (q1 , q2 , q3 ). Then, from the above reduced expression for y1 , it is clear that q1 6= 0, 1, q2 6= 0 and if q2 = 1, q3 6= 0. This implies f (q1 ) 6= 0, 1, f (q2 ) 6= 0 and if f (q2 ) = 1, f (q3 ) 6= 0. Similarly, one can prove that if y1 = q1 − q2 , − q1 + q2 or q1 + q2 , we must have the following. If q1 = 0, then y1 = 0 − q2 and if q2 = 0 then y1 = −q1 + 0. Also if f (q1 ) = 0 then f (y1 ) = 0 − f (q2 ) and if f (q2 ) = 0 then f (y1 ) = −f (q1 ) + 0. Now, clearly f (y1 ) = T (f (q1 ), f (q2 ), f (q3 )), f (q1 ) − f (q2 ), − f (q1 ) + f (q2 ) or f (q1 ) + f (q2 ). Let us assume that the reduced expression for f (y1 ) in F is not the same as the expression obtained from this equation by changing f (qi ) to rd(f (qi ), F ). We can use the above discussion and Remark 4.6 and it can be easily seen that the only possible cases are those in Remark 4.6(ii). Thus we get one of the following six equations: rd(f (q1 ), F ) = rd(f (y1 ), F ) + rd(f (q2 ), F ), rd(f (q2 ), F )− rd(f (y1 ), F ) or rd(f (y1 ), F ) − rd(f (q2 ), F ), rd(f (q2 ), F ) = −rd(f (y1 ), F ) + rd(f (q1 ), F ), rd(f (q1 ), F ) + rd(f (y1 ), F ) or rd(f (y1 ), F ) + rd(f (q1 ), F ). Let us first consider the case, y1 = q1 − q2 and rd(f (q1 ), F ) = rd(f (y1 ), F ) + rd(f (q2 ), F ). Clearly f (q1 ) 6∈ S (G1 ). Thus, q1 6∈ S (G1 ) ∪ {0}. Hence, there exist pi ∈ G1 , i = 1, 2, 3, such that q1 = T (p1 , p2 , p3 ), p1 − p2 , − p1 + p2 or p1 + p2 , and its reduced expression is obtained by replacing each pi by rd(pi , G1 ) in this equation. In particular, lh(pi , G1 ) < lh(qi , G1 ) < lh(y1 , G1 ). From this, it follows that if y1 + q2 = q1 = p1 + p2 , then p2 6= q2 . Also our assumption on y1 implies that if p2 6= q2 then f (p2 ) 6= f (q2 ). Now consider the equation f (q1 ) = T (f (p1 ), f (p2 ), f (p3 )), f (p1 ) − f (p2 ), − f (p1 ) + f (p2 ) or f (p1 ) + f (p2 ). Our above discussion implies that the expression obtained from the right side of this equation by replacing f (pi ) by rd(f (pi ), F ), i = 1, 2, is not the same as the expression

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

633

634

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

We note that (r1 + r2 )0 = r10 + r20 + s01 (r10 , r20 ) and (T (r1 , r2 , r3 ))0 = r10 r20 + r30 + t 0 (r10 , r20 , r30 ). From this it can be easily seen that (R01 , ⊕, T ) is a semiadditive ring and 0 is an isomorphism of semiadditive rings. Thus, any semiadditive ring has a twisted representation in a suitable linear binary commutative ring. Example 5.2 (Albert’s Generalized Twisted Fields ). Let A1 be finite field GF (pr ) and let α, β be automorphisms of A1 different from the identity automorphism. Let c ∈ A1 be such that c 6= xα−1 yβ−1 for all x, y ∈ A∗1 . Now let x, y, z ∈ A1 . Define t10 (x, y, z ) = −cxα yβ . Let ⊕ and T be operations defined on A1 with twisting quadruple ((0), 0A1 ,A1 , 0A1 ×A1 ,A1 , t10 ). Then (A1 , ⊕, T ) is a well known semiadditive ring. In fact it is a pre-semifield called Albert’s generalized twisted field.

As noted in the introduction a well known conjecture states that every finite division ring is isomorphic to a generalized twisted field. In the generalized twisted field operations are twisted using automorphisms of fields. While Example 5.1 shows that if we use general maps for twisting, any semiadditive ring has a twisted representation in a suitable commutative ring, Example 5.2 and this conjecture suggest that PTR may have twisted complete representations in specialized rings. Studying twisted representations can provide a good tool for studying classification of projective planes. In

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

635

636

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

(v) (x + a) · y = x · y + a · y, x · (y + a) = x · y + x · a. (vi) x · (y · a) = y · (x · a). Remark 5.6. (i) We have not used brackets in the right side of (5.5)(iv), since using (5.5)(i)–(iii) and the fact that I is an ideal, one can easily see that the order in which the terms appear does not matter. (ii) By taking x = y = z = 0, one can easily see that if I is central in A, then as a semiadditive ring, I satisfies all cadl laws. Hence I is a commutative linear binary ring (not necessarily containing a multiplicative identity). (iii) Suppose I is central in A and J ⊆ I is an ideal in A; then clearly J is also central in A. Remark 5.7. Suppose I is an ideal in a semiadditive ring A. Let M be a set and suppose we are given a set of ideals Jk , k ∈ M, of A such that Jk ⊆ I and I /Jk is central in A/Jk for all k ∈ M. Let J = ∩Jk , where the intersection is taken over all k ∈ M. Using the equations in (5.5), one can easily see that I /J is also central in A/J. We note that the trivial ideal (0A + I ) is clearly a central ideal in A/I. Thus, the set of all ideals J1 ⊆ I of A such that I /J1 is central in A/J1 is nonempty. Let J be the intersection of all such ideals J1 . Then using Remark 5.7, it follows that I /J is a central ideal in A/J. Also J is the minimal such ideal, i.e., if J1 ⊆ I is any ideal in A such that I /J1 is central in A/J1 then J ⊆ J1 . We will denote the ideal J by [I , A]. Our notation is quite similar to the one used by Higman  for the case of loops. In fact we will study the relationship between F /I and F /[I , F ] in a manner somewhat similar to that of Higman for the case of free loops. Now, let I be an ideal in a semiadditive ring A with a multiplicative identity. We choose a set L of coset representatives for the cosets of I in A. Thus L ⊆ A, A/I = {` + I | ` ∈ L} and for `1 , `2 ∈ L, `1 6= `2 , `1 + I 6= `2 + I. We also assume that 0A , 1A ∈ L. We will sometimes also denote L by L(I, A). Now define two functions ` : A → L and h : A → I as follows. Let x ∈ A. Then, define `(x) ∈ L to be the unique element of L satisfying x ∈ `(x) + I. Define h(x) by h(x) = −`(x) + x. Thus, (5.8) x = `(x) + h(x). Define a function t : L × L × L → I by t (`1 , `2 , `3 ) = h(T (`1 , `2 , `3 )), `1 , `2 , `3 ∈ L. Also, define s(`1 , `2 ) = t (1F , `1 , `2 ), `1 , `2 ∈ L. (5.9) Let `1 , `2 , `3 , ∈ L. Then: (i) s(`1 , `2 ) = h(`1 + `2 ) = t (1F , `1 , `2 ) = −`(`1 + `2 ) + (`1 + `2 ) ∈ I. (ii) t (`1 , `2 , `3 ) = h(T (`1 , `2 , `3 )) = −`(T (`1 , `2 , `3 )) + T (`1 , `2 , `3 ) ∈ I. We will sometimes denote the functions `, h, s, t by `(I , A), h(I , A), s(I , A), t (I , A), respectively. The following remark follows easily from the definitions. Remark 5.10. Let I be a central ideal in A. Let x, y, z ∈ A, h1 , h2 , h3 ∈ I and `1 , `2 ∈ L. Then: (i) (a) h(x + y) = h(x) + h(y) + s(`(x), `(y)). (b) h(x − y) = h(x) − h(y) − s(`(x − y), `(y)). (c) h(−x + y) = −h(x) + h(y) − s(`(x), `(−x + y)). (ii) (a) `(x + y) = `(`(x) + `(y)). (b) `(x − y) = `(`(x) − `(y)). (c) `(−x + y) = `(−`(x) + `(y)). (iii) (a) h(T (x, y, z )) = h(x) · h(y) + h(z ) + `(x) · h(y) + `(y) · h(x) + t (`(x), `(y), `(z )). (b) `(T (x, y, z )) = `(T (`(x), `(y), `(z ))). (iv) (a) `1 · h1 = h1 · `1 . (b) `1 · (h1 · h2 ) = (`1 · h1 ) · h2 = h1 · (`1 · h2 ). (c) `1 · (`2 · h1 ) = `2 · (`1 · h1 ). (d) (`1 + h1 ) · `2 = `1 · `2 + h1 · `2 . (v) (a) h(0F ) = 0F , h(1F ) = 0F , `(0F ) = 0F , `(1F ) = 1F . (b) s(`1 , 0F ) = s(0F , `1 ) = t (0F , `1 , `2 ) = t (`1 , 0F , `2 ) = t (`1 , 1F , 0F ) = 0F . We will continue to use the notation of the previous sections. We will assume that F = F (S ) is the free semiadditive ring generated freely by S , S ∗ = S \ {1F } and I is an ideal of F . We will denote by α the natural homomorphism α(I , (0F ), F , F ) and the quotient ring F /I by R. Thus, α(x) = x + I for all

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

637

x ∈ F . Let us also assume that the set of coset representatives is L = L (I , F ). We will denote by J the ideal J = [I , F ] ⊆ I . Now, I /J is a central ideal in F /J. Also note that (F /J )/(I /J ) = R. We will assume that L (I /J , F /J ) = L + J = {`1 + J | `1 ∈ L}. We also assume that `, h, s and t denote the functions `(I , F ), h(I , F ), s(I , F ) and t (I , F ) respectively. We will denote the natural homomorphisms α(J , (0F ), F , F ) and α(I /J , (0F + J ), F /J , F /J ) by αJ and αJ ,I respectively. The functions `(I /J , F /J ), h(I /J , F /J ), s(I /J , F /J ) and t (I /J , F /J ) will be denoted by `J , hJ , sJ , tJ respectively. The following can be verified easily from definitions. Remark 5.11. (i) α = αJ ,I αJ . (ii) Let x ∈ F and `1 , `2 , `3 ∈ L. Then, `J (`1 + J ) = `1 + J, hJ (x + J ) = h(x) + J, sJ (`1 + J , `2 + J ) = s(`1 , `2 ) + J and tJ (`1 + J , `2 + J , `3 + J ) = t (`1 , `2 , `3 ) + J (iii) The equations of Remark 5.10 are satisfied with I , A replaced by I /J , F /J, and `, h, s, t replaced by `J , hJ , sJ , tJ respectively. We will often consider a polynomial ring Z[W ] over Z or the ring (W )Z consisting of all polynomials in Z[W ] with no constant term. For a set Y ⊆ Z[W ], let mon[Y ] be the set of all monomials in Y , i.e., the set of all finite products of elements of Y . We can consider 1Z as the empty product of elements of Y . Thus, 1Z ∈ mon[Y ]. If X is a subset of Y , we will denote by monX [Y ] the set of all monomials in mon[Y ] in which at least one element from X appears. Thus, for example monY [Y ] is the set mon[Y ] \ {1Z }. We now describe a semiadditive ring (R , B) corresponding to the pair (F , I ). The semiadditive ring (R, B) is defined on a set R × B, where B is a subring of a polynomial ring. The ideas involved in our construction of (R, B) are somewhat similar to the ideas developed by Higman  for the construction of a loop (L, A) corresponding to a normal subloop of a free loop. Let L = L(I , F ). We note that `(0F ) = 0F , `(1F ) = 1F . Let us define, for any subset A ⊆ F , `(A) by `(A) = {`(x) | x ∈ A}. (5.12) R = F /I = {`1 + I | `1 ∈ L} = {α(x) | x ∈ F }. Now let Wt be the set of new symbols t 0 (`1 , `2 , `3 ), `1 , `2 , `3 ∈ L, `1 6= 0F , `2 6= 0F , (`1 , `2 ), (`1 , `3 ), (`2 , `3 ) 6= (1F , 0F ). Similarly, define Wh and Wk to be the set of new symbols Wh = {bh(x) | x ∈ S } and Wk = {bk(`1 ) | `1 ∈ L \ {0F , 1F }}. Let W1 = Wt ∪ Wh ∪ Wk . We assume that all symbols in W1 are distinct and are distinct from other previously considered symbols. In particular, they are not in F or Z[S ∗ ]. Let W = Wt ∪ Wh ⊆ W1 . We will denote the polynomial ring Z[W1 ] by B1 . Let B be the ideal in B1 generated by W . It can be easily seen that B is a free Z module with W 0 = monW [W1 ] as a basis. We note that 0B1 = 0B = 0Z and 1B1 = 1Z . Also, B does not have a multiplicative identity. We now consider the cases where one of the parameters is 0F or 1F . Let `1 , `2 ∈ L. Define: (5.13)(a) t 0 (0F , `1 , `2 ) and t 0 (`1 , 0F , `2 ) to be 0Z ; (b) t 0 (1F , 0F , `1 ), t 0 (1F , `1 , 0F ) and t 0 (`1 , 1F , 0F ) to be −bk(`1 )bh(1F ); (c) bh(0F ), bk(0F ) to be 0Z and bk(1F ) to be 1Z − bh(1F ); (d) s0 (`1 , `2 ) to be t 0 (1F , `1 , `2 ) + bk(`1 )bh(1F ); (e) b1 (x) to be bk(`(x)) + bh(x) ∈ B1 when x ∈ S ∪ {0F }. With these definitions, s0 (`1 , `2 ) and t 0 (`1 , `2 , `3 ) are defined for all `1 , `2 , `3 ∈ L. We also note that s0 (`1 , `2 ) ∈ B. Now, for all `1 ∈ L and h01 ∈ B, define `1 · h01 by (5.14) `1 · h01 = h01 · `1 = bk(`1 )h01 ∈ B. Using the above definitions, it can be easily checked that the equations given in Remark 5.10(iv)(a)–(d) are satisfied for all `i ∈ L, h0i ∈ B, i = 1, 2, with hi replaced by h0i respectively. Define two functions ` : R × B → L and b : R × B → B as follows. Let x ∈ F and y = (x + I , b) ∈ R × B. Then, define `(y) = `(x) and b(y) = b. Also define a function b1 : R × B → B1 by b1 (y) = bk(`(y)) + b(y). We can now define two operations + and T on R × B as follows. Let x, y, z ∈ R × B. Then we define x + y, −x + y, x − y and T (x, y, z ) by the following rules. (5.15) (a) `(x + y), `(−x + y), `(x − y) and `(T (x, y, z )) are defined by the equations of the Remark 5.10(ii) (a), (b), (c) and (iii)(b) respectively.

638

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

(b) b(x + y), b(−x + y), b(x − y) and b(T (x, y, z )) are defined by the equations of Remark 5.10(i)(a),(b),(c) and (iii)(a) respectively with h, s, t replaced by b, s0 , t 0 respectively, where `(x) · b(y) and `(y) · b(x) are as defined by the equation of (5.14). It can be easily seen that the operations + and T are well defined on R × B and (R × B, +, T ) is a semiadditive ring with (0F + I , 0Z ) and (1F + I , bh(1F )) as additive and multiplicative identities respectively. We will denote this semiadditive ring by (R , B). Remark 5.16. It can be easily checked from the definitions and the equations of (5.5), (5.13) and (5.15) that the set (0F + I , B) of all elements (0F + I , h1 ), h1 ∈ B, is a central ideal of (R, B) and is isomorphic to the ring B. We will identify (0F + I , h1 ) with h1 ∈ B. Thus, B is identified with (0F + I , B). Hence we can assume that B ⊆ (R , B), and is a central ideal in (R, B). The quotient ring (R, B)/B ' R under the map taking (x + I , h1 ) + B to x + I. Now, for each x ∈ S ∪ {0F }, let us define δ(x) = (x + I , bh(x)) ∈ (R , B). The map δ : S → (R, B) taking x ∈ S to δ(x) can be uniquely extended to a homomorphism δ : F (S ) → (R , B). Lemma 5.17. Let x ∈ F . Then: (i) `(δ(x)) = `(x). (ii) If h ∈ I, δ(h) = b(δ(h)). (iii) δ(I ) = δ(F ) ∩ B. (iv) b(δ(x)) = b(δ(`(x))) + δ(h) for some h ∈ I. Proof. Suppose x ∈ S. Then δ(x) = (x + I , bh(x)). Clearly, `(δ(x)) = `(x). Hence (i) is satisfied for x ∈ S. Now suppose x = x1 + x2 , −x1 + x2 , x1 − x2 or T (x1 , x2 , x3 ), xi ∈ F , lh(xi , F ) < lh(x, F ), i = 1, 2, 3. Then, δ(x) = δ(x1 ) + δ(x2 ), −δ(x1 ) + δ(x2 ), δ(x1 ) − δ(x2 ) or T (δ(x1 ), δ(x2 ), δ(x3 )). We can assume that (i) is satisfied for x1 , x2 and x3 . Using this fact and the equations of (5.15), it can be easily checked that (i) is satisfied for x. This proves that (i) is satisfied for all x ∈ F . Now if h ∈ I, clearly `(h) = 0F , and using (i), we get `(δ(h)) = 0F . Thus, b(δ(h)) = δ(h) ∈ B. We also note that if δ(h) ∈ B, clearly `(δ(h)) = 0F . Hence using (i), `(h) = 0F . Thus, h ∈ I. This proves (ii) and (iii). Now, clearly x = `(x) + h for some h ∈ I. Hence, δ(x) = δ(`(x)) + δ(h). Also note that s0 (`(x), 0F ) = 0B . Thus, using the equations of (5.15), we get b(δ(x)) = b(δ(`(x))) + b(δ(h)) = b(δ(`(x))) + δ(h). This proves (iv).  Remark 5.18. (i) Remark 5.16 and Lemma 5.17(i) imply that we can take {δ(`1 ) = (`1 + I , b(δ(`1 ))) | `1 ∈ L} as a set of coset representatives for the central ideal B of (R, B). We will denote δ(`1 ) by `01 for all `1 ∈ L. Let L 0 = {`0 | ` ∈ L }. For each y ∈ (R, B), define `0 (y ) = δ(`(y )) and h0 (y ) = b(y )−b(`0 (y )). Similarly for x ∈ F , define `0 (x) = δ(`(x)). The following can be checked easily using Lemma 5.17. For all y ∈ (R, B): (a) b(y) = b(`0 (y)) + h0 (y). (b) If y = δ(`1 ) = `01 then h0 (y) = 0B . (c) If y = δ(x), x ∈ F , then h0 (y) = δ(h(x)) ∈ δ(I ) (note that h = h(I , F )). (d) If y ∈ δ(I ), then `0 (y) = 0(R,B) = (0F + I , 0B ) and h0 (y) = y. (ii) Let `1 ∈ L. From (i), one can easily see the following: (a) {b(y) | y ∈ δ(F ), `(y) = `1 } = b(`01 ) + δ(I ). (b) {b1 (y) | y ∈ δ(F ), `(y) = `1 } = bk(`1 ) + b(`01 ) + δ(I ) = b1 (`01 ) + δ(I ). Remark 5.19. Let y1 = δ(x1 ), y2 = δ(x2 ), x1 , x2 ∈ I. It can be easily checked that y1 + y2 , y1 − y2 , y1 y2 ∈ δ(I ). Thus, δ(I ) is a subring of B. In particular, (δ(I ), +) is a subgroup of (B, +). Now, let `1 , `2 , `3 ∈ L. In F , T (`1 , `2 , `3 ) = `(T (`1 , `2 , `3 )) + t (`1 , `2 , `3 ). Hence, T (`01 , `02 , `03 ) = ` (T (`1 , `2 , `3 ))+δ(t (`1 , `2 , `3 )). Also, in δ(F ), using (5.14) and Remark 5.18(i) we get T (`01 , `02 , `03 ) = `0 (T (`1 , `2 , `3 ))+ b(`01 )b(`02 )+ b(`03 )+ bk(`01 )b(`2 )+ bk(`02 )b(`1 )+ t 0 (`1 , `2 , `3 )− b(`0 (T (`1 , `2 , `3 ))). Using these equations we get (5.20)(i) b(`0 (T (`1 , `2 , `3 ))) = t 0 (`1 , `2 , `3 ) − δ(t (`1 , `2 , `3 )) + b(`01 )b(`02 ) + b(`03 ) + bk(`01 )b(`02 ) + bk(`02 )b(`01 ). In particular, the above equation for `1 = 1F implies the following. (5.20)(ii) b(`0 (`1 + `2 )) = s0 (`1 , `2 ) − δ(s(`1 , `2 )) + b(`01 ) + b(`02 ). 0

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

639

Remark 5.21. (i) The equations of Remark 5.18(i) show that `0 (y) and h0 (y) correspond to the functions ` and h of Remark 5.10 for the central ideal B of (R, B). Thus, `0 (y) and h0 (y) satisfy the equations of (5.9)(ii) and Remark 5.10(i)–(v), for the pair ((R, B), B). In fact using the equations of (5.20)(i), (ii), it can be easily checked that these equations will be satisfied with `, h, s(`1 , `2 ) and t (`1 , `2 , `3 ) replaced by `0 (y), h0 (y), δ(s(`1 , `2 )) and δ(t (`1 , `2 , `3 )) respectively. Here for y1 , y2 ∈ (R, B), the dot product used in the equations of Remark 5.10(iii)(a) and (iv) is defined by `0 (y1 )·h0 (y2 ) = (bk(`(y1 )) + b(`0 (y1 )))h0 (y2 ). In particular, for all y1 , y2 , y3 ∈ (R, B): (a) h0 (y1 + y2 ) = h0 (y1 ) + h0 (y2 ) + δ(s(`(y1 ), `(y2 ))). (b) h0 (T (y1 , y2 , y3 )) = h0 (y1 )h0 (y2 ) + h0 (y3 ) + (bk(`0 (y1 )) + b(`0 (y1 )))h0 (y2 ) + (bk(`0 (y2 )) + b(`0 (y2 )))h0 (y1 ) + δ(t (`(y1 ), `(y2 ), `(y3 ))). (ii) From the proof of Lemma 5.17(iii), one can easily see that for all h1 ∈ I , `1 ∈ L: (a) b(δ(`1 + h1 )) = b(`01 ) + δ(h1 ). (b) δ(`1 · h1 ) = (bk(`01 ) + b(`01 ))δ(h1 ) = b1 (`01 )δ(h1 ) ∈ δ(I ). Let A be a linear binary commutative ring. Let N be an A-module. Let us denote by HomA (N , N ) the ring of all endomorphisms of N as an A-module, i.e., the homomorphisms f : (N , +) → (N , +) of additive groups such that for all x ∈ A, y ∈ N, f (xy) = xf (y). It can be easily seen that Hom(N , N ) is a linear binary ring, where for f , g ∈ Hom(N , N ), f + g and fg are defined by (f + g )(x) = f (x) + g (x) and (fg )(x) = f (g (x)). Now, suppose N is a central ideal in a semiadditive ring A. Let q : W1 → A be a function such that q(W ) ⊆ N. Now, N is a linear binary commutative ring satisfying the cadl rules. In particular N is an N-module. For each x in A, let us denote by x∗N the map x∗N : N → N taking h1 ∈ N to xh1 ∈ N. Using the fact that N is central in A, it can be easily checked that x∗N ∈ HomN (N , N ). For w ∈ W1 , define q∗ (w) = q(w)∗N . Now, B1 = Z[W1 ]. Hence, the function q∗ from W1 to HomN (N , N ) can clearly be extended to a unique homomorphism ψ 1 (q, N ) : B1 → HomN (N , N ) such that ψ1 (q, N ) |W1 = q∗ . Define a function q1 : W 0 → N as follows. (5.22) Let a ∈ mon[Wk ], w ∈ W 0 . Then: q1 (w) = q(w) if w ∈ W ; q1 (aw) = ψ1 (q, N )(a)q1 (w). Using the fact that B is a subring of the polynomial ring B1 and B is a free Z module generated by W 0 , it can be easily seen that q1 defines a unique homomorphism of binary rings, q01 : B → N, such that q01 |W 0 = q1 . We will denote the homomorphism q01 by ψ(q, N ). Remark 5.23. (i) The homomorphism ψ(q, N ) : B → N of binary rings defined above is the unique homomorphism satisfying the following conditions. Let w ∈ W 0 and a ∈ Wk . Then: (a) ψ(q, N )(w) = q(w) if w ∈ W . (b) ψ(q, N )(aw) = q(a)ψ(q, N )(w). (ii) ψ(q, N )(ah1 ) = q(a)ψ(q, N )(h1 ) for all a ∈ Wk and h1 ∈ B. Now, consider the map δ . Suppose δ(y) = 0B for some y ∈ F . Then clearly `(δ(y)) = 0F . Using Lemma 5.17, it follows that y ∈ I. Thus, ker(δ) ⊆ I. Also, I /ker(δ) ' δ(I ) is a central ideal in F /ker(δ) ' δ(F ) ⊆ (R, B). This implies that J ⊆ ker(δ) and the map δJ : F /J → (R , B) taking x + J to δ(x) for all x ∈ F is a well defined homomorphism. The following remark now follows easily. Remark 5.24. (i) J ⊆ ker(δ). (ii) δJ αJ = δ . We will show that ker(δ) = J. Before proving this result we will prove a more general factorizing theorem. Our proof is very similar to that given by Higman  for the case of loops. Let f : A1 → A2 be a homomorphism of semiadditive rings. A factorization of f is a pair (β, γ ) of homomorphisms β : A1 → M , γ : M → A2 of semiadditive rings such that f = γ β . The maps β and γ are called factors of F in a factorization. Such a factorization is called central if ker(γ ) is central in M. Now suppose γ : F → M and θ : M → R give a central factorization of the canonical map α : F → R = F /I. We note that using the fact that I /J is a central ideal in F /J and Remark 5.11(i), it follows that αJ is a factor of a central factorization of α . Also, ker(γ ) ⊆ I and γ (I ) ⊆ ker(θ ). Hence, γ (I ) is central in M.

640

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

This implies that I /ker(γ ) is central in F /ker(γ ). The definition of J now implies that J ⊆ ker(γ ). It can be easily checked that αJ is a factor of a factorization of γ . Thus, we have proved: Theorem 5.25. Suppose γ : F → M is a factor of a central factorization of α . Then αJ is a factor of a factorization of γ . Theorem 5.26. The homomorphism δ is a factor of a central factorization of α . Also suppose γ : F → M and  : M → R give a central factorization of α . Then: (a) There is a homomorphism θ : (R, B) → M such that δ and θ give a factorization of γ . (b) Suppose M (L) is a set of elements m(`1 ), `1 ∈ L, such that m(`1 ) ∈  −1 (`1 + I ) and m(0F ) = 0M . The homomorphism θ in (a) can be chosen in such a way that θ satisfies θ ((`1 + I , 0B )) = m(`1 ) for all `1 ∈ L. Proof. Let π : (R, B) → R be the projection map defined by π (y) = `(y) + I = α(`(y)). Then π is clearly a homomorphism. Now ker(π) = B is a central ideal in (R, B). Also, for x ∈ F , π (δ(x)) = α(`(x)) = α(x). Thus δ and π give a central factorization of α . Now suppose we are given γ and  , as in the statement of the lemma. Then, N = ker() is a central ideal in M. In particular, as a semiadditive ring, N satisfies all cadl rules. For each `1 ∈ L, choose m(`1 ) ∈ M satisfying (m(`1 )) = α(`1 ). For `1 = 0F , we choose m(0F ) = 0M . All other m(`1 )’s can be chosen arbitrarily. Let `1 , `2 , `3 ∈ L and x ∈ S. Clearly, (m(`(x))) = α(x) = (γ (x)). Hence for some d(x) ∈ N we have: (5.27) (i) γ (x) = m(`(x)) + d(x). We note that since m(0F ) = 0M = γ (0F ), d(0F ) = 0M . Similarly, using the fact that γ (1F ) = 1M , we get m((1F )) = 1M − d(1F ). Now, using (5.9) it follows that for some c (`1 , `2 , `3 ) ∈ N we have the following: (5.27) (ii) T (m(`1 ), m(`2 ), m(`3 )) = m(`(T (`1 , `2 , `3 ))) + c (`1 , `2 , `3 ). Also, using m(0F ) = 0M , m(1F ) + d(1F ) = 1M and the fact that N is a central ideal in M, it can be easily checked that c 0 (`1 , 1F , 0F ) + m(`1 )d(1F ) = c (0F , `1 , `2 ) = c (`1 , 0F , `2 ) = 0M . Now define c (`1 , `2 ) = c (1F , `1 , `2 ) + m(`1 )d(1F ). Using the fact that N is a central ideal in M, (5.9) and (5.27)(ii), we get the following: (5.27) (iii) m(`1 ) + m(`2 ) = m(`(`1 + `2 )) + c (`1 , `2 ). Also, since m(0F ) = 0F we have c (`1 , 0F ) = c (0F , `2 ) = 0F . Define a function q : W1 → M as follows. Let `1 , `2 , `3 , `4 ∈ L and x ∈ S. Define: (5.28) q(t 0 (`1 , `2 , `3 )) = c 0 (`1 , `2 , `3 ), q(bh(x)) = d(x) and q(bk(`4 )) = m(`4 ). We note that q(W ) ⊆ N and q(s0 (`1 , `2 )) = c (`1 , `2 ). Now, using Remark 5.23, it follows that q defines a homomorphism φ : B → N where φ = ψ(q, N ). Thus, φ |W = q and φ(bk(`4 )h1 ) = m(`4 ) · φ(h1 ) for all h1 ∈ B. Define a map θ : (R, B) → M by θ (y) = m(`(y))+φ(b(y)). Now let i = 1, 2, 3, yi ∈ (R, B), `(yi ) = `i and b(yi ) = h0i . Then, h0i ∈ B and φ(h0i ) ∈ N. Using the above definitions and equations, the fact that N is central in M, the equations of (5.5), (5.9), (5.15) and Remark 5.10, and some simple calculations, one gets the following equations: (5.29)(a) θ (y1 + y2 ) = m(`(`1 + `2 )) + φ(h01 ) + φ(h02 ) + c (`1 , `2 ) = θ (y1 ) + θ (y2 ). (b) θ(T (y1 , y2 , y3 )) = m(`(T (`1 , `2 , `3 ))) + φ(h01 ) · φ(h02 ) + φ(h03 ) + m(`1 ) · φ(h02 ) + m(`2 ) · φ(h01 ) + c 0 (`1 , `2 , `3 ) = T (θ (y1 ), θ (y2 ), θ (y3 )). Thus, θ is a homomorphism of semiadditive rings. Also, note that for x ∈ S , `(x) = `1 , θ (δ(x)) = θ(`1 + I , bh(x)) = m(`1 ) + d(x) = γ (x). From this it can be easily seen that γ = θ δ . This proves (a). Now, since θ ((`1 + I , 0B )) = m(`1 ) for all `1 ∈ L, the proof of Statement (a) implies Statement (b).  Now consider the natural map αJ : F → F /J. Using Theorems 5.26 and 5.25 or Remark 5.24 we get two factorizations: αJ = θ δ and δ = δJ αJ , where θ : (R, B) → F /J and δJ : F /J → (R, B). Thus we get αJ = θ δJ αJ and δ = δJ θ δ . This implies that θ and δJ are mutually inverse isomorphisms between αJ (F ) = F /J and δ(F ) ⊆ (R, B). Now, let ζ = αJ ,I . Thus, for all x ∈ F , ζ (x + J ) = x + I. Let σ be the restriction to δ F of the natural map π : (R, B) → R; then we have α = ζ αJ = σ δ . Hence for x ∈ F , ζ (αJ (x)) = σ (δ(x)) = σ (δJ (αJ (x))). Thus ζ = σ δJ . Similarly we can prove σ = ζ θ . This implies that δJ (I /J ) = F δ ∩ B and θ (F δ ∩ B) = I /J. Thus, we have proved: Theorem 5.30. The semiadditive rings δ(F ) and F /J are isomorphic under an isomorphism in which I /J corresponds to δ(I ) = δ(F ) ∩ B.

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643

641

Remark 5.31. (i) The above result is similar to Lemma 3 of  for loops. Higman used these methods to prove for a free loop P the uniqueness of the reduced form. Higman also used it to prove that ∩Pi = (0) where P0 = P and Pi+1 = [Pi , P ], i ∈ N, are the terms of the lower central series of a free loop P. In Section 4 we have proved a weaker form of this result: that ∩Fj = (0). Using results proved here, and arguments similar to those used by Higman, one should be able to prove analogous results for the semiadditive rings, though we will not need these results for our purposes here. (ii) We also note that from the definition of J one can easily check that J ⊆ F1 = [F , F ]. Thus, if I 6⊆ F1 , clearly J 6= I, and using the above lemma it follows that δ(I ) ' I /J 6= (0). It can be easily checked that this condition is satisfied when F /I is a finite PTR. A proof will be given in part II . Theorem 5.32. For each `1 ∈ L \ {0}, choose a b0 (`1 ) ∈ B such that (`1 + I , b0 (`1 )) ∈ δ(F ). Suppose M = {b0 (`1 ) | `1 ∈ L \ {0F }}. Let M1 be the ideal in (R, B) generated by M. Then, M1 ∩ δ(F ) = (0(R,B) ). Proof. Let π be the projection map taking y ∈ (R, B) to `(y) + I. Thus, δ and π give a factorization of α with ker(π ) = B. Let M (L) = M ∪ {0(R,B) }. Using Theorem 5.26 with γ = δ , we can construct a factorization δ = θ δ where θ : (R, B) → (R, B) such that θ ((`1 + I , 0B )) = (`1 + I , b0 (`1 )) for all `1 ∈ L \ {0F }. We note that θ is the identity map on δ(F ). In particular, θ ((`1 + I , b0 (`1 ))) = (`1 + I , b0 (`1 )). Also, θ (`1 + I , 0B ) = (`1 + I , b0 (`1 )). Thus θ (0F + I , b0 (`1 )) = 0. This implies that b0 (`1 ) ∈ ker(θ ). Hence, for all w ∈ M1 , θ (w) = 0B , while θ (y) = y for y ∈ δ(F ).  Now, let `1 , `2 ∈ L, `1 , `2 6= 0F , `1 6= `2 . Let us also assume that I 6= J. This implies that δ(I ) ' I /J 6= (0). Hence using Remark 5.18(ii)(a), one can easily choose b0 (`1 ) for the above lemma so that for y1 = (`1 + I , b0 (`1 )), b(y1 ) = b0 (`1 ) 6= 0B . Then the above lemma implies that b(y1 ) 6∈ δ(I ). Also, again using Remark 5.18(ii)(a), it follows that the coset b(`01 ) + δ(I ) 6= δ(I ). In particular, b(`01 ) 6∈ δ(I ). Now, suppose that b(`01 ) = b(y2 ) for some y2 ∈ δ(F ), `(y2 ) = `2 . Then, using Remark 5.18(ii)(a), b(`01 ) = b(`02 ) + δ(h1 ) for some h1 ∈ I. Now, using the fact that δ(I ) 6= (0) and Remark 5.18(ii)(a), we can choose y02 = (`2 + I , b0 (`2 )) for the above lemma, so that y02 6= y2 . Remark 5.18(ii) implies that b(`01 ) = b(y2 ) = b(y02 ) + δ(h01 ) for some h01 ∈ I , δ(h01 ) 6= 0B . For `1 , we choose b0 (`1 ) = b(`01 ). Then, as in the proof of Theorem 5.32, we will get θ (b(`01 )) = θ (b(y02 )) = 0B , while θ (δ(h01 )) = δ(h01 ) 6= 0B . But this implies that θ (b(`01 )) = θ (b(y02 )) + θ (δ(h01 )) = δ(h01 ) 6= 0B . Thus, we get a contradiction. Hence, b(`01 ) 6= b(y2 ). Thus, we have proved that b(`01 ) + δ(I ) 6= b(`02 ) + δ(I ). Now note that using Remark 5.19, it follows that B/δ(I ) is a group. Define a map g1 (L , B) : L → B/δ(I ) as follows. Let `1 ∈ L. Define g1 (L, B)(`1 ) = b(`01 ) + δ(I ). The following lemma now follows easily. Theorem 5.33. Suppose J 6= I. Then the map g1 (L, B) is one-to-one. Remark 5.34. Let M1 be as described in the statement of Theorem 5.32, J 6= I and `1 ∈ L. (i) Using Theorem 5.32 and Remark 5.18(ii)(a) it can be easily seen that M1 ∩ (b(`01 ) + δ(I )) = M1 ∩ {b(y) | y ∈ δ(F ), `(y) = `1 } = {b0 (`1 )}. (ii) Let h1 ∈ M1 , h2 ∈ B. Then (`1 , 0B ) · h1 = bk(`1 )h1 and h1 h2 are also in M1 . From this one can easily see that the ideal generated by M in (R, B) is equal to the ideal generated by M in B1 = M1 . (iii) Using Remark 5.19 and (ii) one can easily see that for all y1 , y2 ∈ M1 + δ(I ), yi = ai + hi , ai ∈ M1 , hi ∈ δ(I ), i = 1, 2: (a) y1 h2 = a1 h2 + h1 h2 ∈ M1 + δ(I ). (b) y1 y2 = (a1 a2 + a1 h1 + a2 h2 ) + h1 h2 ∈ M1 + δ(I ). (c) b(`01 ) = b0 (`1 ) − h0 (`1 + I , b0 (`1 )) ∈ M1 + δ(I ). (d) bk(`1 )y1 = bk(`1 )a1 − b(`01 )h1 + (bk(`1 ) + b(`01 ))h1 ∈ M1 + δ(I ). Theorem 5.35. Let J 6= I. For each `1 ∈ L \ {0}, choose a b0 (`1 ) ∈ B such that (`1 + I , b0 (`1 )) ∈ δ(F ). Suppose M = {b0 (`1 ) | `1 ∈ L \ {0}}. Let M1 be the ideal in (R, B) generated by M. Then: (i) The additive loop ((R, B), +) = (δ(F ), +) ⊕ (M1 , +), i.e.: (a) M1 ∩ δ(F ) = (0(R,B) ). (b) The additive subloop of (R, B) generated by δ(F ) and M1 is (R, B). (ii) The additive subgroups (M1 , +) and (δ(I ), +) of B satisfy M1 ⊕ δ(I ) = B.

642

N. Singhi / European Journal of Combinatorics 31 (2010) 622–643