'9 CONSTRUCTION or THREE mum ' ORTHOGONAL LATIN SQUARES By 1H5 METHOD OF: g_- _ ._ . . SUM COMPOSITION V II. GEOMETRICAL CONSTRUCTION OF NEW FAMILIES‘O - ' 0F GENERALIZED YOUDEN DESIGNS Dissertation for the Degree of Ph. D. MICHIGAN STATE UNIVERSITY " CH‘ING-JUNG WU 1976 ' This is to certify that the thesis entitled I CONSTRUCTION OF THREE MUTUALLY ORTHOGONAL LATIN SQUARES BY THE METHOD OF SUM COMPOSITION. ll. GEOMETRICAL CONSTRUCTION OF NEW FAMILIES OF GENERALIZED YOUDEN DESIGNS presented by Ching-Jung Wu has been accepted towards fulfillment of the requirements for Ph.D. . Statistics and degree in Probability Major professor Date—JJJuLJfilé—l ' 0-7639 ABSTRACT I. CONSTRUCTION OF THREE MUTUALLY ORTHOGONAL LATIN SQUARES BY THE METHOD OF SUM COMPOSITION II. GEOMETRICAL CONSTRUCTION OF NEW FAMILIES OF GENERALIZED YOUDEN DESIGNS By Ching-Jung Wu Two independent problems are considered in this thesis. The first problem contained in Chapters I and II deals with the construc- tion of three orthogonal Latin squares by sum composition. In the second problem (Chapter III) new families of Generalized Youden Designs are constructed. In Chapter II two methods of construction of three orthogonal Latin squares are discussed. We construct O(n,3) sets by composition of an 0(n‘,3) Vand an 0(r.3) set with n = n + r, where n = pm, p l l m a prime, r =-E—:L, d“: 3. Based on GF(n]), the 0(nl,3) is formed by d . B(xl), B(x2), B(x3); where for any A E GF(n]), A # 0, 8(A) is the nI x nl square with the element A0; + aj in its (i,j) cell, ai,oJ 6 GF(nl). New families of GYD's for v = Sm, s a power of a prime, are constructed in Chapter III. The method of construction is geometrical. In particular this extends the construction of GYD's for m = 2 obtained by Ruiz and Seiden (I97A). The designs constructed here would not have been obtained by the technique used in Ruiz and Seiden. I. CONSTRUCTION OF THREE MUTUALLY ORTHOGONAL LATIN SQUARES BY THE METHOD OF SUM COMPOSITION II. GEOMETRICAL CONSTRUCTION OF NEW FAMILIES OF GENERALIZED YOUDEN DESIGNS By Ching-Jung Wu A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Statistics and Probability I976 TO MY MOTHER AND CHIOU-YEE ACKNOWLEDGMENTS I wish to express my sincere appreciation to Dr. Esther Seiden, under whose direction this thesis was written, for her guidance and con- stant encouragement. I would also like to thank Dr. Dennis C. Gilliland, Dr. James Hannan and Dr. Habib Salehi for their help in the final review of the manuscript . Thanks also go to the Department of Statistics and Probability, Michigan State University and the National Science Founda- tion for their financial support during my stay at Michigan State University. I would also like to thank Noralee Burkhardt who demonstrated both patience and skill in typing this dissertation. Chapter BIBLIOGRAPHY . TABLE OF CONTENTS SUM COMPOSITION OF LATIN SQUARES . I. I I. 2 I 3 A Introduction and Definitions . . Sum Composition of Two Latin Squares . Principles of Construction of 0(n, r) sets by Sum Composition Known Results on the Method of Sum Composition . CONSTRUCTION OF 0(p”+r,3) SETS BY SUM COMPOSITION 2.I 2.2 2.3 2.4 GEOMETRIC CONSTRUCTION OF GENERALIZED YOUDEN DESIGNS . 3. I 3.2 3 3 Some Conditions for Construction of 0(p”+r, 3) Sets . . . . . . Construction of 0(p”+r, 3) Sets when =h, S and 7 . Theorems on the Construction of 0(p“+r, 3) Sets by Sum Composition . . Alternative Construction of O(p”+r, 3) Sets By Sum Composition Introduction . Definitions and Optimality of GYD . Construction of Generalized Youden Designs Page CHAPTER I SUM COMPOSITION OF LATIN SQUARES I.I Introduction and Definitions K. Yamamoto (l96l) introduced the idea of constructing orthogonal Latin squares by a method of sum composition. The method has been generalized by R. Guerin (I966) and this author has christened it ”Yamamoto's Method”. A. Hedayat and E. Seiden (I969) introduced a simple method of constructing orthogonal Latin squares of order n = nI + n2 provided that nI is a power of a prime. Their method of construction was based on some properties of GF(nI). Horton (I97A) extended a theorem of Hedayat and Seiden. Some further results were obtained by F. Ruiz and E. Seiden (I97A). Yet all known results on Hedayat and Seiden's method of sum composition were concerned with the construction of two orthogonal Latin squares, until in I973 Hedayat gave a construction of three orthogonal Latin squares of order A6. In his construction Hedayat used squares of order Al and 5. It should be mentioned however that examples of three mutually orthogonal Latin squares constructed by the method of sum composition were available in the literature. Chi-Chi Shin (l965) published a paper in Chinese describing a construction of orthogonal Latin squares by the method of sum composition and presented three orthogonal Latin squares of order A6, 93, l06, II8, ISA, with nl = Al, 89, lOl, l09, I37 respectively. The construction of Shin was based on a Special representation of squares of order nI which applied to primes but not to powers of primes. In fact that construction could be considered a generalization of Parker's construction of two orthogonal Latin squares of order IO, although Parker did not refer to a method of sum composi- tion. This part of the thesis was inspired by that example of three mutually orthogonal Latin squares of order A6 constructed by Hedayat. We use sum composition, a general method of Headyat and Seiden, to con- struct three orthogonal Latin squares of order> n = n + n where nl I 2 is a power of a prime and n - is an integer divisor of n‘-l. As a 2 result of a theorem proved by P.J. Cameron et al. (I975), we can assert an effective construction of three mutally orthogonal Latin squares by the method of sum composition whenever it could be expected to be possible to carry it out. The result of this part of the thesis thus clears up a problem which has existed for at least six years in this area. It is our hope that this result will stimulate further research in this area and in other related areas as well. Definition I.I.l; A Latin square of order n is a square matrix I 2 l O O wIth n entries of n dIfferent elements, none of them occurrIng twice within any row or column of the matrix. Definition I.I.Z; Two Latin squares of order n are orthogonal if upon superimposition each of the n2 pairs occurs exactly once. A system of two orthogonal Latin squares of order n will be referred to as a 0(n,2) set. Definition I.I.3. r Latin squares of order n are mutually orthogonal if any two of them are orthogonal. A system of r mutually orthogonal Latin squares of order n will be referred to as a 0(n,r) set. Definition I.I.A. A transversal of a Latin square of order n is a set of n cells, exactly one in each row and column, such that all symbols appear exactly once as entries in the set. Two or more transversals are parallel or disjoint if they have no cell in common. Definition I.I.5. A common transversal of a set of Latin squares of the same order is a set of cells which form a transversal for each square. Example I.I.l. LI=FI 2‘} L7 LI r' "l r" ‘ I 2(3):; ;I 2mg _2_(I)A3I i;(u)I 2 L2:3 him: L3=Ih 3 30) III.) 1 2 II (2) l h 3J r n _ I 2 3 I. A 3 2 l L = ‘I 2 I I. 3 L3 A I 2‘ Ll is the only Latin square of order 2; it has no transverals at all. 2’ l'3 form two common parallel transversals of the O(A,2) set formed by The paranthesized cells and the underlined cells in L L2, L3: The O(A,3) set formed by L2,L3,Lh has no common trans- versals. l.2. Sum Composition of Two Latin Squares Let LI and L be two Latin squares of orders n and 2 I n2, nl 3_n2, on two dISJOInt sets of varIetIes Z] = {al,a2,...,anl} and Z = {b ,b ,...,b } respectively, and let L have at least 2 I 2 n2 I n2 parallel transversals. Then we can compose L] with L2 to obtain a Latin square L of order n = nI + n2. Denote this Latin square by L(L',L2). To produce L(L],L2) select arbitrary n2 parallel trans- versals from LI and name the n2 transversals of L in any manner 2 from I to n2. In a square of order n fill the upper left and lower right corner with LI and L2 respectively. Fill the cells (i, n + k), k = l,2,...,n , with that element of transversal k which I 2 appears in row i, i = l,2,...,n Similarly fill the cells (n + k,j) I' I k = l,2,...,n with that element of transversal k which appears in 2 column j, j = l,2,...,n]. Finally replace each of the n] elements of transversal k with bk, k = l,2,3,...,n2, it is easily seen that the resulting square L(LI,L2) is a Latin square of order n on 2' U 22. The procedure just described of filling the first nl entries of column (row) nI + k is called horizontal (vertical) projection of transversal k on column (row) nl + k, k = l,2,...,n2. Example l.2.l. Let XI = {l,2,3} and 22 = {A,B} and l (2) 3 A Ll = 2 3. (I) L2 = (3)1 3 Note that the parenthesized and underlined cells of LI form two parallel transversals. The resulting Latin square L is A 3 I 2 2 A B 3 I L(L],L2) - B I A 2 3 I 3 2 A B 3 I B A 1.3. Principles of Construction of 0(n,r) Setsgby Means of Sum Composition. We start with two important lemmas (Hedayat, I973) which are needed in the construction of 0(n,r) sets. Let B(y) be the n] x nI square with elements 'Yai + aj in its (i,j) cell ai,aj, Y # O in GF(nl), the Galois field of order n], i,j = l,2,...,n] and let LTB(y)] be n x n square with B(y) in its n x n top left corner subsquare, where n > n I I ,- It is well known that {B(A),B(xl),B(x2)} form an O(n,3) set if A,xl,x2 are distinct non-zero. Note that the n cells in BIXl) and I B(x2) corresponding to the n' cells in 8(A) with a fixed entry, say t, form a common transversal for {B(x]),8(x2)}. We call this transversal in B(xl) and B(x2) by T(t). It is clear that as t goes over GF(nl) we have n' parallel transversals for {B(xl),B(x2)}. Lemma I.3.I. Let B(A), B(xl), B(x2), L[B(x])], L[B(x2)] and T(t) be defined as above, where A, x‘,x2 are non-zero elements in GF(n]) and xl # x Then the III pairs obtained by the vertical 2. projection of transversal T(tl) in B(xl) and transversal T(tz) in 8(x2) onto the same row of L[B(xl)] and L[B(x2)] are the same as the nl pairs obtained by transversal T(KV(A,x],x2,tl,t2) in B(xl) and in B(x2) where xltl(A-x2) - xthIA-x') AIXl - x2) (1°3°|) KVIA.x].x2.tl.t2) = Note that the transversal Kv(A,x‘,x2,tl,t2) will be referred to as transversal recovered by the vertical projections of T(tl) and T(t2). Proof: The nl entries correSponding to transversal T(t') in B(xl) can be written as x a. + o. with Ag. + a = t . I I J I I From the last equation above we get ai = -J—-——J-. Upon the vertical projection of transversal T(tl) onto the r-th row of LIB(x')], we get the nI entries tI ' “I I I I X] A '* aJ = A + -jr-- 0] , J = l,2,...,nl. Note that the above expression has nothing to do with the value of r. Similarly, the III entries of the r-th row of L[B(x2)] upon the vertical projection of transversal T(tz) onto it can be expressed in the following form x t A - x 2 2 2 , . _ A + A aj 0 J l,2,...,n]. Thus the n] L[B(xl)] and L[B(x2)] are pairs obtained by the nl entries of the r-th row of x t A - x x t A - x I I I 2 2 2 . _ T+( X a], A + A aj) J — l,2,3,ooo,nlo (I) Now suppose that there exists a transversal T(Kv) in B(xI) and 8(x2) such that the n‘ pairs obtained from the correSponding entries of this transversal is exactly the III pairs given in (I). Then the III pairs obtained from the corresponding cells of this transversal in B(xl) and B(x2) are ' = l,2,...,nl.(2) x t A - x x K A - x l + a l = l v + a. I A J A A A x2‘2 + a A ' x2 = szv + a A ' x2 A J A A A A - xl If x2 # A, upon multiplication of the second equation by X—:—;- and 2 its subtraction from the first equation we get: xltI - x?t2 A - xI = lev - szv A - x' A A A - x2 A A A - x2 which gives the following expression for Kv x t (A - x ) - x t (A - x ) K = l I 2 2 2 ' , Q.E.D. v A(xI - x2) Similarly we can prove the following. Lemma I.3.2. Assumption as in Lemma I.3.I. Then the III pairs obtained by the horizontal projection of transversal T(tl) in B(x‘) and trans- versal T(t2) in B(x2) onto the same column of L[B(x])] and L[B(x2)] are the same as the n] pairs obtained by the transversal T(Kh(A,xl,x2,tl,t2)) where tl(A - x2) - t2(A - x‘) xI ' x2 Kh(A,xl,x2,t],t2) = (1.3.2) Note the transversal Kh is referred as transversal recovered by the horizontal projection of T(tl) and T(tz). The following corollaries are the immediate consequences of Lemma I.3.I and Lemma I.3.2. Corollary I.3.I; II n (I) KV(A,xl,x2,tl,t2) = tl or t2 If and only If t (II) Kh(A,xl,x2,t],t2) = t] or t2 If and only If t I 2' II n l 2' Corollary I.3.2. If t] # t then 2’ KV(A,XI’x2’tI’t2) + Kh(A’xI’x2’tl’t2) = tl + t2 x = A2. if and only if x 2 I The following lemma which can be thought of as the general principle for construction of two orthogonal Latin squares by sum composition is also an immediate consequence of the above lemmas and corollaries. Lemma I.3g3. Let nl = pa, p a prime and a a positive integer, and let n2 Latin squares of order n be a positive integer such that nl 3_2n and two orthogonal 2 2 eXIst, say {L1,L2}. If we can select distinct nonzero elements A,xl,x2 in GFInl), such that two sets of parallel transversals determined by the elements of B(A) in B(xi), say Ti = {T(tij): tU E GF(nl), j = l,2,3,...,n2}. i = l,2, exist, T H T2 = O and such that there I exnst n2 paIrs {(tli’th): I,J = l,2,3,...,n2, no two paIrs havung the same first or second component} such that {KV(A,x],x2,tli,t2j)} U {Kh(A,x],x2,t'i,t2j)} = TI U T2, then L(B(xl)’Ll) and L(B(x2),L2) are orthogonal Latin squares of = + order n n1 n2. Note {KV(A,xI,x )} and {Kh(A,xl,x .)} are 2’tli’t2j Z’tl 2; usually denoted by Kv(l,2) and Kh(l,2) where the pair (l,2) ). .,t I refers to the pair (x],x2 This lemma can be extended to a general principle for the con- struction of r mutually orthogonal Latin squares which we state in the following way. Principle l.3. Let nl = pa,p a prime and a a positive integer, and let n2 be a positive integer such that n' 3_rn and r mutually 2 2 eXlSt, say {L‘,L2,...,Lr}. If we can select distinct nonzero elements A,xl,x2,x3,..., orthogonal Latin squares of order n xr in GFInl), such that r sets of parallel transversals determined by the elements of B(A) in B(xi), say Ti = {T(ti'),..., T(tin )}. i = l,2,...,r, exists, Ti 0 Tj = ¢, i # j, and such that 2 KV(I,j) U Kh(l,J) = Ti U Tj’ I,j = l,2,3,...,r. Then {L(B(x]),L]), L(B(x2),L2),...,L(B(xr),LrI} is an 0(n,r) set, where n = nI + n2. l0 I.A. Known Results on the Method of Sum Composition All the known results concerned with the construction of two orthogonal Latin squares by sum composition have been rigorously de- veloped by Hedayat and Seiden, from I969 to l97A. Ruiz and Seiden in I972 have also discovered some new results in this area. Their works will be summarized as follows. Hedayat and Seiden (l97A) r‘I LE—J, then an Theorem I.A.I. If n = nI + n2, nl = pa 3_7 and n 2 O(n,2) design can be constructed by sum composition. 3, then an n a Theorem I.A.Z: If n — nl + n2, I - p :_7 and n2 O(n,2) design can be constructed by sum composition. Theorem I.A.3. If n = nl + n2, n] = pa 3_7, p = Am+l or 8m+3, m = l,2,3,..., and n2 = A, then an O(n,2) design can be constructed by sum composition. Theorem I.A.A. If n = nl + n2, nl = pa 3_l3, p = Am+l, m = l,2,3,..., and n2 = S, then an O(n,2) design can be constructed by sum composition. Ruiz and Seiden (I97A). Theorem I.A.S. If n = nI + n2, nl = pa 3_ll, p = 7m+l, 7m+2 or 7m+A, m = l,2,3,..., and n2 = A, then an O(n,2) design can be constructed by sum composition. Theorem I.A.6. If n = nl + n2, nI = pa, and n = even (excluding 2 2 and 6), nl 3_2n2, then one can construct an O(n,2) design by sum composition. CHAPTER II CONSTRUCTION OF O(p”+r,3) SETS BY SUM COMPOSITION 2.I Some Conditions for Construction of O(pn+r,3) SEIS n Let p be a prime and r = B—fil-, where d :_3, n = l,2,3,..., r > 3. Let G be a multiplicative subroup of order r in the finite field GF(pn). Without loss of generality we may assume that G is generated by an element t in GF(pn), i.e. G = {I,t,t2,t3,...,tr_l}. u U+Sl u U+SZ Now consider the pairs (tl,t2) = (t ,t ), (tl’t3) = (t ,t ). u+s (t2,t3) = (tU,t 3), where s',52,s3 are some fixed integers and u = O,I,2,...,r-l. By principle I.3 if one can find elements a,b,c,and distinct nonzero elements ,xl,x in GF(pn) such that a-lb, b-lc, c-la 2’x3 are all not in the subgroup G, and such that {KV(A,xl,x2,atl,bt2)} captures {btz}, {Kh(A,x',x ,at],bt2)} captures {atl}, 2 {KV(A,xl,x3,atl,ct3)} captures {ct3}, {Kh(A,xl,x3,atl,ct3)} captures {atl}, {KV(A,x2,x3,bt2,ct3)} captures {ct3}, {Kh(A,x2,x3,bt2,ct3)} captures {btz}, then three mutually orthogonal Latin squares of order pn+r can be constructed if 0(r.3) sets exist. More precisely we may set up the following equations: u+s u+s u l l k ['KV(A,xl,x2,at ,bt ) bt ~t u+sl u m u = 0,l,2,3,...,r-l ) at -t (2.IA) u N‘Kh(A,xl,x2,at ,bt ll u U+S2 U+S2 l KV(A,xl,x3,at ,ct ) = ct t (2.IB) u “+52 . u - o,I,2,3, ,r-l Kh(A,xl,x3,at ,ct ) = at tJ u+s u+s KV(A,x2,x3,btu,ct 3) - ct 3~t2 (2.IC) u u+s3 u n U = 0,I,2,3,...,r-I Kh(A,x2,x3,bt ,ct ) = bt -t for some integers l :_k,n,i,j,2,n < r. Now we consider the system (A) first, by equation (I.3.I) and (I.3.2) in Lemma I.3.I and Lemma I.3.2 respectively, it follows that -s - - ’I I - x2(A xl) ab t x](A x2) = tk I < k < r A(x2 -x;) . ’ ‘— (A') -I SI (x - A) - a bt (x - A) 2 l _ m _ x - t I fi'm < r x2 I By the second equation of (A'), -I SI m -l 51 x](a bt - t ) - a bt A + A x = _ (I) 2 I - tm By (I) and first equation of (A'), the following computation can be easily carried out: SI m -I SI - - t ) - a bt A + A](A - x1) - ab -l l -5l m [xlia bt t xl[A(I - t ) 51 m) s s k -l A - A] = At [xl(a bt - t - xl(a-‘bt I - tm) + a-lbt I -l Sl m - a bt A + A - (l - t )xl] OF "S S S xf(l - ab- t t - a-lbt I + tm) + xl(Za-Ibt lA - 2A - Atm I I m k I S -I 5 + ab- t At + At - Aa- bt ltk) + A2(I - tk)(l - a bt I) = 0 0|" x?(l - ab'It-s'tm)(l - a-lbtsl) + Ax](I - a-Ibtsl)(-2 + tk + ab'It-Sltm) + A2(I - tk)(I - a-Ibts') = 0 or ‘S S [x (I - ab-lt ltm) - A(I - tk)][xl(l - a-‘bt I) - A(I - a- l S lbt 1)] = 0. under the assumption that xl # A, x2 # A and a-lb E G. We must have = “I " tk) (2) By (I) and (2), S _ A(l - a Ibt ltk) x2 - m . (3) I - t It's clear that S 'S x] = x2 Iff (I - a lbt 'IIIk - ab ': II“) = 0. But a'lb E G. Thus xl # x2. Similarly from system (B) and system (C) we should get the following solutions for x],x and x ,x 3 2 respectively. 3 IA A I - ti XI = ( ) -s . (A) l - ac- t th -I S2 I A(I - a ct t ) X = - . , (S) 3 I - tJ ‘ 2. A I ' t x2 = ( -: (6) l-bc-It 3tn .. 5 II. X = A(I - b lct 3t ) (7) 3 I - tn Note that -s . x (A - x1) - ac-lt 2x (A - x ) tl = 3 I 3 I < i < r A(x3 - x?) ’ - (e') S J (x3 - A) - a-lct 2(xI - A) t = x - x ’ I 5-J < r 3 I _ -s t1 _ x3(A - x2) - bc lt 3x2(A - x1) A(x _ x ) , l 5_£ < r 3 2 (C') s n (x3 - A) - b-lct 3(x] - A) t = (x _ x ) , I §_n < r 3 2 (2) = (A) implies that k i A(I - t I _ A(I-t ) xI -s - -s (2.I.I) I - ab-lt Itm l - ac- t t (3) (6) implies that s -l k 2 = A(I - a bt lt ) = A(I ' t I (2 I ll) 2 (I - tm) I b 'I -53 n - C t t (5) = (7) implies that s . s _A(l - a 'ct Zt') _ A(I - b 'a 3:9“) x3_ . _ n (2.I.III) I-tJ I-t From now on we assume that tk+m = t'+J = t2+n = I. By (2.I.III), s -s . . -s _ 'S . -I 3 2 l-I _ j _ -I 3 n I _ ac It 2t; = ab t t (l_ tn)(I bc t t ). (1- t) This and (2.I.I) imply that . s -s _. I = (I - tk)(l - tJ)ab It 3 2t2 ' -s . -s l - bc It 3tn (I - tn)(l - t')(I - ab It Itm) The last equation and (2.I.ll) then implies that . s - . s (I - t£)(l - tk)(l - tJ)ab It 3 th ' = l - a lbt ltk n T -I'5Im l-tm (I - t )(I - t )(I - ab t t ) Since t2+n = tI+J = tm+k = I, it follows immediately from the last equation above that s s -s +5 . lbt ltk)2 = (I _ tk)2t 3 2 It2(£ I). (I - a- $‘S+S If t3 2' is a quadratic residue, this is true when t has even index or 53 = 52 + 51 is chosen to be zero or even Integer, then we get the following solution l6 - -' - k p a Ib = I + (I t )t where 2p = 53 - $2 + sI + 2(R-i) (mod r). From (2.I-I) and (2.I.II) ac‘l = [I :'(I - tk)tp] - T: (I - ti)tp] _ k p -52+j [I + (l - t )t It s . :_(l - ti)tp - a ct t = __ k __ . (8) [I + (I - t )tp] - [+ (I - t')tp] tp+k :.(I - t2) -5 +n + +k 3 P t _' s3+I :_(I - t2) I - b ct = (9) tp+k :_(I - t1) Taking upper sign in (8) and (9) and substituting the right -I sz+i _] s3+£ hand sides of (8) and (9) for I - a ct and l - b ct respectively In (2.I.III), we find that ti = tpT' + I - t2 I + tp+k - + tp k tp-I-i This implies that t"""1 = I provided that I + tp+k ¢ 0. But 2p = 53 - s + sI + 2(2-i) (mod r). We must have s - s + s 5 0 2 3 2 I (mod r). Hence we have the following theorem: Theorem 2.I.l. Under the set-up (2.Ia), (2.Ib), (2.Ic) and the assump- m+k £+n. I+j tion that t = t = t = l, the necessary and sufficient con- dition for a-lb, bc-| and ac I having I7 solution is that s - s + SI E 0 (mod r). In this case the solu- 3 2 tion is given by -I I - tp + tp+k a b = sl+k t bc-I _ I ' tn + tp+k - -s3+k+j and -l _ I - ti + tp+k ‘5 +3 (I - tp + tp+k)ot 2 where p = l + j (mod r). In order to assure an effective construction of three mutually orthogonal Latin squares of order pn + r, we must have sOlutions for a-Ib, bc“l and ac-1 to be such that a-lb, bc-l and ac"I are all not in the subgroup G. + °+° TheOrem 2.I.2. Under the assumptions that tm+k = t2 n = tI J = I and s3 - $2 + sI _ 0 (mod r), If there exists a, I j-a :_r, such that the b set {I + t8 - t.: tb e Gr} distributes in at least three cosets associated with the subgroup Gr’ then we can construct three orthogonal Latin squares of order pn + r by sum composition provided that three orthogonal Latin squares of order r exists ELQQf; By Theorem 2.I.I with p + k = g + j + k = 8. Remark 2.I.I. If we take lower sign in (8) and (9), similarly as above, . . . -l we get very eaSIIy that the conSIstency of the solutions for a b, +'— tp I 2 = bc-l and ac-] implies that -I. This means that one may I8 take lower sign in (8) and (9) when r is even. But when r is even it's readily seen that this is a special case of Theorem 2.I.2. Remark 2.I.2. For computational convenience, we may choose a = 0 and search for two elements in the set {2 - tI : t| E Gr} such that they are in the different cosets (other than the group Gr itself). Remark 2.I.3. In Theorem 2.I.2 the condition that the set {I + t3 - tb : tb E Gr} intersects at least three cosets of Gr is the same as that in Chi ‘Chi Shin's (I965) first solution for construction of 0(P + rs3) SEE. x can be found as follows: Remark 2.I.A. The values of x], x 2’ 3 2 -l SI+2k By (2) and (3) xlx2 = A a bt s +2i By (A) and (S) xix3 = Aza-Ict 2 s +2£ By (6) and (7) x2x3 = AZb-lct 3 From the above three equations, it follows that . _ 2(s +k+I-2) x? = A2(a lb)2t I Therefore -I sl+k-j-2 xI = -A(a b)t (IO) x = -A tk+J+£ (II) 2 and -l 53-k+£-j x = -A(b c)t . (I2) I9 where A # O and A e CF(p”). I21= 3 I. A subgroup of order A is G“ = {l,2 Example 2.I.I. l3. = r. p: 6 9 3,2 ,2 } = {I,8,l2,5}. The set {2-t' : t' 6 Ch} = {l,7,3,l0}. It is clear that 7 and 3 are in different cosets. Since 2 - t = 7 and 2 - t2 = 3, by Theorem 2.I.I and Theorem 2.I.2. We may take tp+k - tIMJI-k = l and t2 = t, t“J = t2, i.e. we may take 2 = I, R + J = 2 and 2 + j + k = A. Since 53 - 52 + sl = 0 (mod A), the following solutions for k,m,i,j, 9.,n,sl,52,s3 can be chosen: k = 2 I = 3 R = l sl = 2 m = 2 j = l n = 3 $2 = O = 2 S3 Then by Theorem 2.I.I, a'Ib = 3, be" = 9, ac" = 3 . We may take a = I, then b = 3, c = 9. We may take A = I, then by Remark 2.I.A, xl = 3, x2 = 12, x3 = IO. U U+SI {(atl,bt2)} = {(t ,3t ) : u = o,I,2,3, sI = 2} u+s {(t”.9t 2) {(I.9). (8.7). (IZ.A) {(atl,ct3)} : u = O, {(I,I0), (8,2), (l2,3), (5,ll)}. l,2,3, 52 O} . (5.6)}. 20 u+s {(bt2,ct3)} = {(3tu,9t 3) : u = o,I,2,3, s3 = 2} = {(3,h), (II,6). (IO,9). (2.7)}. u+sl+k {KV(A,xl,x2,atl,bt2)} = {bt : b = 3, u = o,I,2,3, s1 = 2, k = 2} {3,II,IO,2}. {atu+m : a = I, u = o,I,2,3, m = 2} {Kh(A.xl.x2.atl.bt2)} = {12.S.l.8}. u+sz+i {KV(A,xl,x3,atl,ct3)} = {ct : c = 9, u = o,I,2,3, $2 = O, I = 3} = {6.9.7.AI- {Kh(A,xl,x3,atl,ct3)} = {atu+j : a = I, u = o,I,2,3, j = I} = {8.I2.5.I}- u+s3+2 {KV(A,x2,x3,bt2,ct3)} = {ct : c = 9, u = o,I,2,3, s3 = 2, z = I} = {6’9’7’h}' — U+n o — — .- {Kh(A,x2,x3,bt2,ct3)} - {bt . b — 3, u — o,I,2,3, n - 3} = {2,3,II,IO}. It is clear from the above that transversals at], bt2 and ct are mutually exclusive, moreover {atl} U {bt2} = 3 {KV(A,xl,x2,at],bt2)} U {Kh(A,x],x2,atl,bt2)}, {atl} U {ct3} = ,at],ct3)} U {Kh(A,xl,x3.atl,ct3)} and {th} U {ct3} = bt2,ct3)}. Therefore by principle {KV(A,xl,x3 29x3, 2’x3’ I.3 three orthogonal Latin squares of order l7 can be constructed by {Kv(A,x bt2,ct3)} U {Kh(A,x sum composition. They are constructed as follows. 2I L(B(3),Ll) {atl} = {l,8,l2,5} O A 2 3 A D 6 7 B 9 l0 II C A A 5 6 D 8 9 B II l2 0 C 2 6 7 8 D ID II B O l 2 C A A 9 IO D I2 0 B 2 3 A C 6 A 8 II 9 7 5 3 l l2 l0 8 6 A 2 0 l0 8 6 A 2 0 ll 9 7 5 3 I l2 (I)C7‘-l-~ 2 0 ll -9 7 S 3 I I2 IO 8 6 A D where L = A B C D L(B(l2),L l2 B C 2 3 II 0 2 IO I2 I where L I2 ll IO 2). b D II 9 IO {btz} = l2 0 II B IO I2 9 II 22 {I0,2,3,II} 8 9 A D I2 I0 2 3 II 7 A D ID II A D A I2 II l0 D 6 5 l2 8 7 6 ll l2 IO ll 9 l0 8 B B C 8 l0 l2 3 5 7 2 A 6 7 9 II C 8 6 A 0 I II l2 9 l0 l2 0 IO ll 9 7 L(B(IOI. I- ). {ct }= {9.7.4.6} 3 0 I 2 3 C 5 D B 8 > IO ll l2 9 7 IO II l2 C l D B A A 6 7 8 9 5 3 7 8 C IO D B O A 2 3 A 5 6 I l2 A C 6 D B 9 A II I2 0 I 2 3 IO 8 C 2 D B 5 A 7 8 9 I0 ll l2 0 6 A II D B l A 3 A 5 6 7 8 9 C 2 0 where L = A B C D 2A 2-2-tfl§90§££99£192_9f O(pn+r,3) sets when r = A, 5 and 7. -uo— In this section one aSSUmes that p is an odd prime and n pd ' = r, where d 3.3, r :_3- Although for r = 3, three orthogonal Latin squares 0f order pn + 3 cannot be constructed by sum composition: yet there exists a, l :_a :_3, such that the set {I + t3 - tb : n 2 . . . 6 ur = {l,t,t,t }} dIstrIbutes In at least three cosets. The proof of this and that of the cases for r = A,S,6 are all similar to each other. Thus only a complete proof for r = 7 will be given. Theorem 2.2.I. For r = 3, if p # 7, then {2 - t' : t 6 G = {l,t,t2}} distributes in three cosets. Theorem 2.2.2. For r = A, if p 3_7, then {2 - tl : tI E G = 2 ,t3II II, t, t distributes in at least three cosets. Hence three orthogonal Latin squares of order pn + A can be constructed by sum composition. Theorem 2.2.3. For r = 5, if p # I], then {I + t - t' : t' E G = 2 t3 tA II, t, t }} .distributes in at least three cosets. Hence three orthogonal Latin squares of order pn + S can be constructed by sum composition. Theorem 2.2.A. For r = 7. p ¥ 29, the set {I + t2 - tI : ti 6 G = 2 t3 tA t5 t6 II, t, t }} distributes in at least three cosets. Hence three orthogonal Latin squares of order pn + 7 can be constructed by sum composition. In order to prove Theorem 2.2.A, we need the following lemmas. 25 Lemma 2.2.l. Let dor = pn - I, d 3.3, r :_3, and e be a primitive 2 d root in GF(pn). If Gr = {l,t,t ,...,tr-l}, with t = e , is a multiplicative subgroup of order r in GF(pn) and if 0 :_m,kl,k2, m 21,22 :_r I, kI # k2, I + t # 0, k2 - kl - :_(22 2]) mod r. Then the following system (*) cannot hold. m kl I El 1 + t - t = e t (:2) k .2, I+tm-t2=e't2 k1 I’LI where 0 §_i < d. In other words, if I + tm - t = e t , then k . 2'+k -k . I -k +k l + tm - t 2 # e't I 2 I or e't I 2 I Elggf. Assume the system (*) holds. Then we would have A, k .2 9. t ‘ - t I = e'(t I - t 2) k k -k . l 2 -l I e t ](t 2 I - I) = ~e't 1(t 2 I - I) (I) k k -k . C 2 -£ t'(t2'-I)=e't2(t'2-I). (2) kI i ILI If k2 - kl = 22'- 2‘, (I) would imply that t + e t = 0. But the first equation of (*) would become I + tm = 0 which contradicts the hypothesis that l + tm ¥ 0. k] I 22 If k2 - kI = t] - £2, (2) would imply that t = e t which is clearly impossible for l §_i < d. For i = 0, one has k 1 t I = t 2, i.e. kI = £2. But then (='<) becomes oneequation. Lemma 2.2.2. Notations as in Lemma 2.2.l. The following system cannot hold. 26 I + tm - tk 'tu+J (I) I + tm - t2 = e'tu (2) (*) m k+s i n+j I + t - t = e t (3) + . I+tm-“=e't“ (I) . d . where I :_m :_r, l :_l < d, t = e , l :_J < r. Proof. If the system (*) holds, then (I) - (2) one gets t - tk = e'tu(tJ - l) (3) - (A) one gets ts(t£ - tk) = e't”(tJ - I) From the above two equations one has Hence 5 = n - u (mod r). But by Lemma 2.2.] (2) and (H) cannot hold simultaneously if s = n - u (mod r). Q.E.D. 2 r-l} Lemma 2.2.3. Let G {l,t,t ,...,t be a multiplicative subgroup of order r in the field GF(pn), where r :_5 and 3 :_k < r. Then I + t2 = t + tk iff I + t2 + t3 +...+ tk'l = 0 if. I + t3 = tk + tk+I EIQQI; I + t2 =‘t + ck iff I - t = -t2 + tk Iff I = -t2(] + t + t2 +---+ tk-3) iff l + t2 +...+ tk-I = 0. Since r 3_5. l ' t2 # 0, we have that I + t2 + :3 +...+ tk-l = 0 iff 2 3 tk-I (I - t2)(I + t + t +...+ 3 k + tk+]. ) = 0 iff I + t = t Q.E.D. Lemma 2.2.h ‘when r = 7, I + t2 ¢ t + tk for k = o,I,2,3,h,5,6. Egggf; It is clear that I + t2 # t + tk for k = 0,I,2,3. (I) For k = h, if I + t2 = t + t“, then by Lemma 2.2.3 and the h 6 fact that l+t+t2 +...+ t6=0, we must have that t+t +t5+t = 0. 27 ButvflmHIk = h, by Lemma 2.2.3 again I + t3 = t1+ + t5. Then t + (l + t3) + t6 = 0. Since I + t2 + t3 = 0, it follows that t - t2 + t6 = 0. This implies that l + t2 - t3 = 0. This is impossible since I + t2 + t3 = o. (2) For k = 5, if I + t2 = t + t5, by Lemma 2.2.3, I + t2 + t3 + t“ = 0. Then t + t5 + t6 = o, I + t1I + t5 = 0. Since I + t2 + t3 + t“ = 0, we have t2 + t3 - t5 = 0, i.e. I + t - t3 = 0 (A) But by Lemma 2.2.3 I + t3 =.tS + t6. This and t + t5 + t6 = 0 would imply that 3 _ I + t + t - o . (B) By (A) and (B) it is clear that I + t2 # t + t5. (3) For k = 6, by Lemma 2.2.3 with k = r -I, it is clear that l + t2 # t + tr-l. In particular I + t2 # t + t6 for r = 7. Corollary 2.2.4.When r'= 7, I + t2 # t5 + t6. Proof. It is obvious that I + t2 = t5 + t6 iff I + t2 + t3 = 0. By Lemma 2.2.3, I + t2 = t5 + t6 iff I + t2 = t + t“. But by Lemma 2.2.4 I + t2 # t + t“. Hence I + t2 # t5 + t . Lemma 2.2.5. Let r > k 3_i :_3. Then I + t = t + t iff 3 i-l i k-l I + t + 2:2 + 2t +...+ 2t + t +...+ t = o. ELEQE; Since I + t = t + t iff I - t = -t + t iff '-I 2( k-I) l + t +...+ t' = -t l + t +...+ t , it is obvious that I + t2 # t3 + t5. By Lemma 2.2.5, I + t2 # t3 + tr-l. In fact the 28 the following lemma is true. Lemma 2.2.6. When r = 7, l + t2 I‘ t3 + tk for k = 3,4,5,6. 3599:; It remains to show that I + t2 # 2t3 and I + t2 # t3 + t“. (I) Suppose that I + t2 = 2t3. By Lemma 2.2.5, I + t + 2t2 = 0. This implies that -t2 - t5 + t6 = 0 since (I + t + t2) + t3(l + t + t2) + t6 = 0. Hence I + t3 - t“ = 0, (l - t“) + t3 = O, (I - t2)(l + t2) + t3 = 0. By assumption l + t2 = 2t3, we have 2t3(I - t2) + t3 0. Since t3 f o, 2(I - t2) + I = o, i.e. 2t2 5 3 (mod p). Since I + t + 2t2 E 0, we have that t = -h (mod p). Butvfluyit = -h (mod p), and 2t2 5 3 (mod p), we must have that 29 E 0 (mod p). But as p = 29, we may choose a subgroup of order 7 = {l, t = l6, t2 = 2H, t3 = 7, th = 25, t5 = 6, t6 = 20}. There- forewhenr = 7, l + t2 7‘ 2t3. (2) Assume that l + t2 = t3 + t“. By Lemma 2.2.5 I + t + 2t2 + t3 = 0. Hence -t2 + t“ + t5 + t6 = O or I + t + t2 = t5. This and l + t + 2t2 + t3 = 0 imply that t2+ (13+ t5=0 or I + t + t3 = 0. But I + t + 2t2 + t3 = 0. Therefore if I + t2 = t3 + t“ we must have that 2t2 2 0 (mod p). Since p is odd prime, it is impossible. Q.E.D. Corollary 2.2.5. Let r > k 3.h. Then I + t2 = t“ + tk iff I + t + 2t2 + 2t3 + t“ +...+ tk-l = 0. Proof. It is trivial by Lemma 2.2.5 with i = h. 29 . 2 A 6 It IS clear that l + t # t + t when r # h and by Corollary 2.2.5, we have the following lemma. Lemma 2.2.]. Let r > k :_h and r = 7. Then I + t2 # t“ + tk. .Egggf; It suffices to show that I + t2 f 2th and I + t2 # t“ + t5. (I) Suppose I + t2 = 2th. By Corollary 2.2.5 I + t + 2t2 + 2t3 = 0. Since I + t # 0, 2t2 + l = O, t2‘= 'i. Since I + t + t2 + t3 +...+ t6 = 0, we have that 6t = -5 (mod p). Then as p = 3, I + t2 # 2th. Without loss of generality, we may assume that p # 3. Then 6t = -5 and 2 2t + l = 0 imply that A3 0 (mod p). But if p = #3, we can choose a subgroup of order 7 which is generated by t = AI such that I + t2 # 2th. 2 h 5 2 (2) Suppose I + t = t + t . By Corollary 2.2.5, I + t + 2t + 2t3 + t“ = 0. But I + t + 2:2 + 2t3 + t“ = 0 iff -t2 - t3 + t5 + t6 = 0 iff I + t = t3 + t“ iff t3 = I. This is impossible. Hence I + t2 # t“ + t5. Q.E.D. Lemma 2.2.8. When r = 7, I + t2 - t', i = I,3,h,5,6 are all not in the subgroup G = {l,t,t2,...,t6} of GF(pn), where pn - l = dr, d 3-3. Proof. By Lemma 2.2.A, Corollary 2.2.4, Lemma 2.2.6 and Lemma 2.2.7. 5 6 it suffices to show that I + t2 # 2t and I + t2 # 2t . 2 5 (i) Suppose I + t = 2t . By Lemma 2.2.5, we get I + t + 2t2 + 2t3 + 2th 0 (A) 5 6 2 3+th+t+t Since I + t + t + t O and t2 # 0, it follows 30 from (A) that I + t + t2 = t3 + t“ (B) 5 6 (A) - (B) x t2, we get I + t + 2t + 2t = 0 I + t + (I + t2) + t(I + t2) = o - 2 + 2t + t2 + t3 = o . (c) (A) - (C). we get By (8). 2t2 + t“ = O t2 + 2 = 0 Hence 2t5 = I + t2 = I The last two equations give 8t = -I. Solving the system St = -I {2 (mod p), we have that I29 E 0 mod p. Since p 7‘ 3, we t + 2 = 0 should have #3 E 0 mod p. But for p = 43, we may choose a subgroup of order 7 which is generated by t = bl. Then t2 + 2 = 6 7 0 mod #3. Therefore I + t2 # 2t5. (ii) Suppose I + t2 = 2t6. Then I - t6 = -t2(l - t“) = -t2(I-t2)(l + t2) 3i I + 2t2 + 2th = 0 (D) I + 2t2(l + t2) = 0 I + 2t2 - 2t6 = O t = -I . Since I + t + t2 + t3(I + t2) + t2(t2 + t“) = 0 and I + t2 = 2t6, t2 + t“ = -&, it is clear that 2 5t + 2t + 2 = O (E) Substituting t = -& hinto (E), we must have that 29 E 0 (mod p). But if p = 29, we may choose a subgroup of order 7 which is generated by t = l6 which gives I + t2 = 25 # 40 = 2t6 mod 29. Thus I + t2 # 2t6. Lemma'2.2.9. When r = 7, p III 29, l + t2 ’5 tk, k = I,2,3,lI,5,6. Proof. It is clear that I + t2 # t2 and l + t2 # t. (i) Suppose I + t2 = t3. Since I + t + t2 + t3 + t“ + t5 + t6 = 0, it follows that l+t+t2+th=0. Then This is impossible, since I + t = t . 32 (II) Suppose I + t2 = t“, then I + t + t2 + t3 + t“ + t5 + t6 = 0 gives t“ + t5 + t + t5 = o I + 2t + t = 0 Since t“ = I + t2, 2 + 2t + t2 = o . (A) On the other hand, But t = l + t2, hence 2 3 + 8t + 3t = 0 (8) From (A) and (B), it is readily seen that 2t = 3, t = 3/2. Thus 2.2 - .2 4 1+ (2) - (2) 29 0 mod p. But p i 29, therefore I + t2 # th. (III) Suppose I + t2 = t5. Then I + t2 + t(I + t2) + t“ + t5 + t6 = 0 implies that 2t + 2t + I = o . (c) By (C). By (D). By (E). Hence From (C) and (F), it follows that we must have that (IV) implies that Suppose 33 5 2 t + t + 2t = 0 h 2 + t + t = 0 (D) (I + t2)2 = tI0 I + 2t2 + t4 = t3. -2t + t“ = t3 or 2 + t2 = t3 (E) 2t3 + t4 + t7 = 0 2(2 + t2) + t1I + I = o 2 A + 2t - (I + t) = o by (D). 2 2t - t + 3 = 0 . (F) 2 2 = 2, = —z B F d = —, 3t t 3 y ( ) an t 3 29 E 0 mod p. But p i 29. Therefore I + t2 # t5. I + t2 = t6. Then I + t + t + t3(l + t2) + th(l + t2) = o I + t + 2t2 + t3 = O I + 2:2 + t(I + t2) = o I + 2t2 + I = o t2 + I = o This is impossible. Q.E.D. 3h i Lemma 2.2.IO. Let r = 7. pn - I = 7d, d :3. Then I + t2 - t i = I,3,h,5,6 cannot be all in a coset {eu,eut,eut2,...,eut6}, where I §_u < d. Proof; By Lemma 2.2.I and Lemma 2.2.2 it is not hard to see that the following system cannot hold. I + t2 - t = eutm] I + t2 - t3 = e tm3 I + t2 - t“ = e tmh I + t2 -‘t5 = e th I + t2 - t6 = e tm6 where m;.€ {0,I,2,3,h,5, 6}. Now Theorem 2.2.h is easily seen to be a trivial consequence of Lemma 2.2.8, Lemma 2.2.9 and Lemma 2.2.I0. h 8 12 2I6’220’22h Note if p = 29, we may take G = {l,2 ,2 ,2 , } = {l,l6,25,7,25,23,20}. Then 2 f t = ‘lh = IS = 227 E 23°67 6 2 -G 2 E 2 7 II = 225 e 26 2 - t = -23 = 6 2 - t = -I8 7 . Therefore we have the following theorem. Theorem 2.2.5. Let p be odd prime, pn - I = 7d, d :_3. Then three orthogonal Latin squares of order pn + 7 can be constructed by sum composition. 35 2.3. Theorem on the construction of O(pn + r,3) sets byisum composition. Recently P.J. Cameron, J.I. Hall, J.H. van Lint, T.A. Springer and H.C.A. van Tilberg have proved that under quite general situations the set 5 + Gr = {E + t'lti E Gr} has a nonempty intersection with at least three cosets of Gr in GF(pn) where Gr = {l,t,t2,...,tr-l}, pn - I = dr, d 3_3, r :_3. This theorem which will be stated very precisely at the end of this sections, gives a real nice and complete conclusion about the construction of O(pn + r, 3) sets by sum composition. The following lemmas and theorems although just solved parts of our problem. Yet they have their own advantage in the con- struction of O(pn + r, 3) sets by sum composition. Therefore we state them here for the sake of completeness. n Lemma 2.3.I. For p an odd prime, and 'E—fil-= r, n > I, r is odd number, then there exists an element tk 6 Gr such that 2 - tk # O and 2 - tk E Gr' Proof. (i) Since the pairwise appearances of 2-tR = t| and r is odd, if there exists t1 such that 2 - t2 = 0, then there is at least one tk such that 2-tk # 0 and 2-tk E Gr' (ii) If 2 i Gr’ and 2 - ti 6 6r for all i = l,2,3,...,r-I, then r-I . 2(r-I) - 2( z t') = o. I=l r-I . But 2 t. = 0, we have 2(r-I) - 2(-I) = O or equivalently l=0 2r = 0 (mod p). Since p is odd, r = 0 (mod p). It is clear that this is impossible. Q.E.D. 36 n Lemma 2.3.2. For p an odd prime,-EE; = r, n > I, r is even and r + l # 0 mod p. Then there is an element tk E Gr such that 2 - tk # o and 2 - tk e Gr. Proof. Since the pairwise appearances of 2 - tI = tJ and r is even there is at least one element tk E G such that 2- tk E G . if k 'k I l, 2 - t 2 i Gr’ we are done. So with- there are two elements 2 - t out loss of generality, we may assume that there is only one element such that 2 - tk E Gr and it suffices to show that 2 - tk # 0. Suppose 2 - tk = 0. Since 2 - ti 6 Gr’ for all i ¥ k, it follows that r-l i 2(r - 2) - 2 Z t = 0. i= i¥k r-I . k But 2 tI = O and t = 2. Hence r + l = 0 (mod p) which is i=0 impossible by assumption. Q.E.D. n Lemma 2.3.3. Let p be an odd prime and r = p 5‘ , n > I, d 3_3. If there is i, l :_i < d, such that i(p-I) is not divisible by d and 2 - tk = e'tm for some tk, tm in Gr where e is a primitive element in GF(pn). Then by means of sum composition, the existence of O(r,3) set implies that of O(pn + r,3) set. Proof. 2 - tk = eitm (2 - tk)p = eiptpm 2 - tpk = eiptpm . Since i(p-l) is not divisible by d, e' and e'p cannot be in the same cosets of Gr' Q.E.D. 37 Theorem 2.3.I. Let p be an odd prime, and pn-I = dr, n > I, d :_3. If (d,p-I) = I and r+l # 0 mod p, then by means of sum composition, one can construct O(pn+r,3) set provided that O(r,3) set exists. Egggj; Since (d,p-l) = I and p is odd, it is clear that d is odd. Hence r is even. By Lemma 2.3.2, there exists i,k,m such that 2 - tk = eitm where I 5_i < d, I :_k,m < r. Since (d,p-l) = I and i < d, by Lemma 2.3.3, the theorem follows. The following two corollaries are an immediate consequence of the theorem 2.3.I. - n Corollary 2.3.I. Let p = 3. r = E—il-, n > I, d is odd, r + l # 0 mod 3. If O(r,3) set exists, then one can construct O(3n+r,3) set by sum composition. = p -1 d r+I # 0 mod 5. If O(r,3) set exists, then one can construct Corollary 2.3.2. Let p = 5 and r , n > I, d is odd, 0(5n+r,3) set by sum composition. From section 2.2 we have exceptions for r = 3, A and 5. As one can see very easily that p = 7 is excluded if r = 3, and p = 3 or 5 are excluded if r = h. Similarly p = II is excluded if r = 5. These indicate that two cases have to be excluded, i.e. (a) if Gr is a multiplicative group of a subfield of GF(pn) (b) if Gr is the subgroup of index 2 in a multiplicative group of a subfield of cr(p“). In fact the above exceptions appear in a very natural way as one can see from the following theorem which has been proved recently by the joint effort of five persons as stated at the beginning of this section. 38 Theorem 2.3.2. Let p be a prime, K = GF(p"), p” -I = rd where r _>_ 3 and d 3 3. g e K. (a 5‘ o) and let I;r be the subgroup of order r in Kx. Then the set = i i 5+6r {g+t It ear} 0 O I C x has a nonempty Intersection wIth at least 3 cosets of Gr In K unless (i) Gr is the multiplicative group of a subfield of K and 5 E G. (ii) Gr is the Subgroup of index 2 in the multiplicative group of a subfield Kl of K and g G Kl' (iii) r = 3 and 5 E Gr or -g 6 Gr' (iv) r (V) r 4 and 536 G . I. 5, p = 2, E E Gr' ' A Note -I - t. cannot be in the subgroup G5 = {l,t,t2,t3,t } for i = l,2,3,h, hence Theorem 2.2.3 holds for p = 2 by (v) of Theorem 2.3.2. It is obvious that 2 or -2 cannot be in G if p # 3 3 and 7. It is also obvious that -l - t| is in G for i = I,2, 3 hence p = 2' is excluded by (iii) of Theorem 2.3.2. Therefore Theorem 2.2.I and (iii) of Theorem 2.3.2 have the same conclusion. Similarly Theorem 2.2.2 and (iv) of Theorem 2.3.2 have the same conclusion. In fact for r 3_h by Theorem 2.3.2 we get the following theorem which is the best possible result we can get in construction of O(pn+r,3) sets by sum composition. Theorem 2.3.3. Let p be a prime, pn-l = dr, d 3_3, r z'h, n a positive integer. Then if three orthogonal Latin squares of order r 39 exist, we can construct three orthogonal Latin squares of order pn+r by sum composition unless (i) Gr is a multiplicative group of a subfield of GF(pn). (ii) Gr is the subgroup of index 2 in a multiplicative group of a subfield of cr(p"). 2.4. Alternative Construction of 30(pn+r,3) sets by Sum Composition. If in (2.I.B) , we let KV(A,xl,x3,atl,ct3) capture {atI} and Kh(A,xl,x3,atl,ct3) capture {ct3} and keeps (2.I.A) and (2.I.C), then similar to the previous case we can get a different set of con- ditions for construction of B(pn+r,3) sets. Although by no means we can improve the result of Theorem 2.3.3, yet in the construction of O(pn+r,4) sets this construction may give some help. Thus we state it here for the sake of reference. As in Section 2.I, through this m+k 2+n i+j section we assume that t = t = t = I. Let u+s KV(A,xl,x3,atu,ct 2) = atuti (2.4.8) - u = 0,l,...,r-I. u u+s2 u+s2 j Kh(A,xl,x3,at ,ct ) = ct t where -I 52 x (A - x ) - a ct x (A - x ) i l 3 3 l . t' A(x-x) "1"" I 3 -s . (xl-A)-ac]t 2(x3-A) tJ = I < j < r XI‘X 3 40 interchanging xl and x3, a.1 and a, c.I and c, -52 and 52, by the results in section 2.I, we must have that 'S . = A(I - ac 1t 2t') I I - tJ = A(I - ti) 3 _ s . I - a 1ct 2tJ Since we keep (2.I.A) and (2.I.C) unchanged, (2.I.I), (2.I.II) and (2.I.III) turn out to be _] 'S . = A(I - ac t 2t') = A(I ' tk) (2 h I) I - ab t t S _ )(I - a Ibt 'tk) = A(I - t2) m 'S l t I _ be It 3tn (2.4.II) o S g A(I - t') = A(I - b Ict 3t£) -I 2 j I - t" (2.4.lll) By (2.4.lli), o . S t'(I - t4) = (I - b Ict 3tR) s +j _ -s +i l _ tn By (2.4.l), -s +m+i s _ s ab It I (l - a lbt 'tE)= i - b lct 3t24 s +j+k n a- ct (I - t m) l - t By (2.4.II), - + (' _ b -It S3tn)2 = a2(l - t’“)2tm+n ' c 5 +5 +5 +k+2+j c2t I 2 3 4i if t I 2 3 is a quadratic residue, this is true in particular when t has even index, or s‘ + 52 + 53 is even, then we have the following solutions. -s +n . - - + + l- bc It 3 =:% (I - t2)t q (”1” ') (2.4.l) where 2q = sI + s + 53 (mod r). 2 Substituting (2.4.I) in (2.4.il), we have that s +k . I - a lbtl = 1—:- (I - tm)tq ("fin“) equivalently _ -sl+m c k -s'+q-(k+n+i) I-ab t =iB-(I-t)t (2.4.2) Substituting (2.4.2) in (2.4.l), we have that _ -s +I . s -q+(k+n+I) I - ac t 2 = :_E—(l - tJ)t I (2.4.3) By (2.4.l), (2.4.2) and (2.4.3), it follows that the following system holds . -s +n 1 a(I - t2)t-q+(m+n+') + bt 3 - c = O s +k . (2.I.(*)) a - bt I + C(I - tm)tq Im*"+') = o -s]+i . sl-q+(k+n+i) at :_b(I - tJ)t - c = o In order that a,b and c have non-zero solutions, we must have ' . -s +n :_(l _ t£)t q+(m+n+l) t 3 ‘I s +k . I -t I 1-(] _ tm)tq (m+n+I) = O '5 TI . s -q+(k+n+i) t 2 i (l-tJ)t ' -I It is not hard to get from above determinant that the con- dition turns out to be - - + - - + - - + +’ - + +' $2 53 q :_ 52 s q m SI 52 k I __ sl q k I t t ' t + t [-I- sl-q+n sl-q+k __ sl-q -s3+n :.t + t + t + t = 0 (2.4.4) Let q = HSI + s + $3) = 0 and s = 0. We have that (2.4.4) 2 2 is satisfied when lower sign is taken. Under conditions q = 0 and 52 = 0 mod r, (2.4.(*)) becomes . -s +n -a(l - t£)tm+n+' + bt 3 - c = 0 s +k . a - bt' +c(I - t"‘)t ("m“) = o i sl+(k+n+i) at * b(l - tJ)t - c = 0 Solving above system for a and b in terms of c, we get very easily that Thus we have the following solutions for ab , bc I and ac 43 51+“ m+j i -l t (t - t + I) ab = (2.4.5) t2(tm+n _ tm + I) 2 m+n m bc I = ts(:i ' t + l) , (2.h.6) t I (tn+J - tn + I) _ k m+j _ j ac I = t (t . t +'l) (2.4.7) t'(tn+J - tn + I) Similar to the Remark 2.I.3, it is not hard to find the follow- ing solutions for x], x and x . They are 2 3 s +k+n+i x] g ~Abc-lt I (2.4.8) x2 = -Aa-lctk-n-i (2.4-9) '1 s -k-n+i x3 = -Aab t 3 (2.4.10) Similar to Theorem 2.I.I and Theorem 2.I.2 we can get the follow- ing two theorems. Theorem 2.4.I. Let tm+k = t9‘...” = tI+J = I. Then a sufficient condition for ab-l, bc-l -and ac.I having solution is that sI + 53 = $2 = 0 mod r. in this case the solutions for ab-l, bc.l and ac-1 are given by (2.4.5), (2.4.6) and (2.4.7), respectively. Theorem 2.4.2. Let tm+k = t“n = tI+J = I. If there are elements 5 s . t I, t 3, tm, tn tJ such that 9 (I) 52 = 0 mod r, sl + 53 = 0 (mod r) + +. . .+ . (II) I ' tm + tm n, l - tn + tn J and I - tJ + tJ m are In three different cosets of Gr' an Then O(pn+r,3) set can be constructed by sum composition provided that O(r,3) set exists. Example 2.4.I. As in Example 2.I.l we take p = I3, r = 4. ch = {l,23,26,29} = {l,8,lz,5}. we take S1 = 2 k = 3 i = 3 1 = I 52 = 0 s3 = 2 m = I j = l n = 3 By (2.4.5), (2.4.6) and (2.4.7). it follows that ab“] = I0, bc“I =42, ac-l = 7. We may choose a = I, b = 4, c = 2 and A = I Then xI = 3, x2 = l0, x3 = 2 {(atl.bt2)} =I(1.9).(8.7).(I2.4).(5.6)I {(at,.ct3)} = {(I.2).(8.3).(12.II).(5.I0)} {(bt2.ct3)} = {(4.II).(6.I0).(9.2).(7.3)} u+sl+k {KV(A,x],x2,atl,bt2)} = {bt :b = 4, u = o,I,2,3, sI = 2, k = 3} = {6.9.7.4} {Kh(x,x‘,x2,atl,bt2)} = {atU+m:a = I, u = o,I,2,3, m = I} = {8,I2,S,I} {Kv(x,x],x3,atl,ct3)} = {atU+i:a = i, u = o,I,2,3, i = 3} = {5,l,8,l2} u+sz+j {Kh(A,xl,x3,atl,ct3)} = {ct :c = 2, u = o,I,2,3, 52 = 0, j = I} = {3,II,I0,2} u+s3+2 {Kv(A,x2,x3,bt2,ct3)} = {ct :c = 2, u = o,I,2,3, s3 = 2, 2 ‘ I} = {10.2.3.II} 45 .x .bt2.ct3)} = {bt”+”:b = 4. u = 0.1.2.3. n = 3} = {7.4.6.9}. {Kh(k,x2 3 It is clear that by Principle I.3, three orthogonal Latin squares of order I7 can be constructed by sum composition. We state them as follows for the sake of comparison. L(B(3).L]). {atl} = {l,8,l2,5}. o A 2 3 II o 6 7 B 9 l0 II c I 812 5 A 4 5 6 o 8 9 B II i2 0 c 2 3 I0 I 7 6 7 8 0 IO II B o I 2 c 4 A 5 I2 3 9 9l0 DIZ o B 2.3 4 c 6 A 8 7 I SII l2 D I 2 B 4 5 6 c 8 A Io II 9 3 7 o D 3 4 B 6 7 8 c ID A 12 0 III 5 9 2 5 6 B 8 9 I0 c12 A I 2 3 D o 7 II I, 8 B IO II I2 C I A 3 4 S D 7 2 9 0 6 8 7 C 9 A ll l2 0 D 2 3 B 5 6 I0 4 ll l0 6 4 2 0 ll 9 7 5 3 I l2 C D A B 2 0 II 9 7 5 3 I I2 l0 8 6 4 D n w > where L = com) 00):!) CD>CO bane: where L(B(IO),L2), {bt2} = {9.7.4.6} 0 I 2 3 C 5 ID I] l2 C 7 8 4 C C I0 I D B D B 9 I0 I I2 3 6 IO 46 8 A I0 II I2 A 6 7 8 9 2 3 4 5 6 I2 9 O I 2 3 l0 ll I2 0 7 I, 8 5 C I2 9 C C 7 ID I 6 l0 0 4 47 L(B(2),L3), {ct = {2,3,II,I0} 3} 0 l A B 4 5 6 7 8 9 D C I2 2 3 II l0 2 A B 5 6 7 8 9 IO D C 0 I 3 4 I2 II A B 6 7 8 9 l0 II D C I 2 3 4 5 0 I2 8 7 8 9 ID II I2 D C 2 3 4 A 5 6 I O 8 9 l0 ll 12 0 D C 3 4 5 A B 6 7 2 I l0 II l2 0 I D C 4 12 D I 2 D C 5 6 7 A B IO ll 8 9 4 3 8 l 2 3 D C 6 \l ABII1209I054 3 4 D C 7 8 L0 > m N o N o m \n 5 D C 8 9 ID > a: o N \IU'IUJ 0‘ I; O (I) C IO II l2 A B 2 3 4 ll I2 0 A B 3 4 5 6 CDNU'I 3 2 l 0 l2 ll I0 9 7 6 5 A B C D S 4 3 2 l 0 I2 II l0 9 8 7 D C B A 9 8 7 6 5 4 3 2 l 0 l2 II l0 8 A D C 6 5. 4 3 2 l 0 I2 II I0 9 8 n o > a: where L = A B C D, CHAPTER III GEOMETRIC CONSTRUCTION OF GENERALIZED YOUDEN DESIGNS 3.I. Introduction The original Youden square (YS) for v varieties was a k x v array obtained from a balanced incomplete block design BIBD (v,b,k,r,A), with b = v > k by considering blocks as columns, arranged to make each variety appear once per row. Generalizations, by Shrikhande and Agrawal allowed b = mv for integer m. It was Kiefer (I958) who relaxed the restrictions v > k and b = mv and generalized the BIBD and Y5 to the balanced block design (BBD) and generalized Youden design (GYD). The basic constructive methods for 880's and GYD's, which have been used in optimality considerations for a number of years, were listed and illustrated in Kiefer's paper (I975). Those were methods for combining LS's and known BIBD's to yield the desires structure. Ruiz and Seiden (I974) described a construction of an infinite class of GYD with v = 4, b = k = 6t, t odd, and showed that they are not D-optimal. They also constructed geometrically several families of D-optimal GYD for v = 52, s a power of a prime. This part of the thesis is a generalization of Ruiz and m Seiden (I974) to the case v = s , m :_2. In particular a geometrical construction of GYD for v = 4, b = 6t], k = 6t l.t odd, is per- 2’t 2 formed which seems different from what has appeared in the literature and more extensively covers all nonregular cases for v = 4. It is 48 49 our hope that this construction of nonregular cases for v = 4 will stimulate further research on remaining yet unsolved problem in the design setting of two-way heteogeneity. 3.2. Definitions and Optimality of GYD. (A). Definitions and somegproperties of GYD. in the usual block design setting of one-way heterogeneity, we specify the positive integers b,v and k, and have v varieties and b blocks of size k. A design then can be thought of as a k x b array of variety labels, with blocks as columns. Let nd be ii the number of times that variety i appears in block j in design d and let p = fractional part of k/v, rd = Ejnd and i ij A = Z.n n . dih J dij dhj Definition 3.2.I. A (v,b,k) balanced block design (880) is a design d with all rd equal, all Ad equal for i < h, and I ih d - k/vI < I for all i,j. Ii In Definition 3.2.2. A (v,b,k) balanced incomplete block design (BIB) is a (v,b,k) BBD with k < v. A (v,b,k) BIB design is said to be symmetric if v = b. (6) In the setting of two-way heterogeneity, we write A and ih 0(6) with 6 = R or C for the quantities A and p when rows (R) or columns (C) are considered as blocks. If p(R) or O(C) = O, the design is said to be regular. Definition 3.2.3. A (v,b,k) generalized Youden design (GYD) is a design which is a BBD when each of the rows (columns) is considered as the blocks. 50 In particular we have Definition 3.2.4. A (v,k) Youden design (squares) is a GYD with b = v and k < v. It follows from this definition that a (v,k) Youden design is merely a symmetric BIB design with each row a permutation of the varieties. Therefore we are interested in the GYD with k :_v and b 3_v which will be assumed through this part of the thesis. There are some known properties of GYD, among others, the following two are most frequently used. For the other properties readers are referred to Ruiz and Seiden (I974). Notation. The quotient and remainder of the division of an integer a by another b will be written [a/b] and a(b) respectively. For a GYD d, let rd = r for all i, AsR) = A], i ih A(c) = A for all i and h, [b/v] = mr and [k/v]= nc. dih 2 Proposition 3.2.I. (i) rv = kb. (ii) r = mrk + r(k) = ncb I-r(b) (iii) vr(k) = kb(v)’ br(k) = rb(v). r(k)(b(v) ‘ ') Proposition 3.2.2. (i) AI = mr(r + t(k)) + r(b)(k(v) ‘ 'I v - I (ii) A2 = nc(r + r( Remark 3.2.I. Notice that proposition 3.2.2 yields a necessary condi- tion for the existence of GYD, namely r(who) ' 'I and r(b)(k(v) ' ') v-l v-l have to be all integers. SI (8). Optimality of GYD. Let y denote the observation correspond- ijk ing to the kth variety in the ith row and the jth column. The row, column, and variety effects are denoted by at, Br’ Yc respectively. If eijk scedasticity and normality, then a completely additive model is is the random error with the usual assumptions about homo- .. = + + + e.. . yIJk at 8r Yc IJk If we are interested only in estimation of linear combinations ca, where c is a contrast (2ci = 0), a is the v-vector of at's, then the commonly used optimality criteria are usually formulated in terms of the covariance matrix Vd of the best linear estimators. They are (a) D-optimaiity: minimizing the det Vd' (b) A-optimality: minimizing the tr Vd. (c) E-optimality: minimizing the maximum eigenvalue of Vd' The relationship among these is well known; in the two way heterogeneity setting, D-optimality of a GYD implies A-optimality, and A-optimality implies E-optimality. in the special setting b = k = v, i.e. GYD is a Latin square, Wald (I943) showed that it was D-optimal. Kiefer (I958) shows that the regular GYD is D-optimal. For the nonregular settings, the conclusions known at this time are: (i) A GYD is always A-optimal and is therefore E-optimal. (ii) A GYD is D-optimal unless v = 4. (iii) If v = 4 and k a GYD is never D-optimal. is sufficiently near I, a GYD is not b = (iv) If v = 4 and -E D-optimal. 52 From above known results, it follows that a nonregular GYD with v = 4 is a most interesting one in the consideration of optimality. Now suppose a GYD is nonregular, then b(v) and k(v) are either I, 3 or 2. If b(v) (or k(v)) were I or 3, by PrOposition 3.2.l(iii), r(k) cannot be an integer. Thus b(v) and k(v) have to be 2. But then by Remark 3.2.I, r( and r(b) are divisible by k) 3. This and Proposition 3.2.l(iii) imply that k and b are both divisible by 6. Therefore the only nonregular GYD with v = 4 is of the form with b = 6tl and k = 6t2, tI and t2 odd. Since the optimality in this case has not been solved, it is felt that a new design construction is worth mentioning. Thus a geometric construc- tion of such design is given in the next section. 3.3. Construction of GYD By a flat we mean a (m-I)-dimensional hyperplane in EG(m,x). The set of all flats in EG(m,s) can be further classified into m disjoint sets as follows: The coefficients of the following equations should range through all the elements of GF(s). Gm: ale + a2x2 + + m-lxm-l + xm = a, Gm-l alxl + a2x2 +°'°+ am-2xm-2 + xm-l = a, G2: alxl + x2 = a, G x = a Note that there are Sp flats contained in Gp, p = l,2,3,...,m. 53 Let a0 2,.. the following order: do < a] < a2 <...< as_l. Each point in a flat can be represented by a m-tuples in such .,o be 5 elements of GF(s) arranged in a a ’ I’ s-l a way that the i-th component of the m-tuples is xi = a, a E GF(s), i = l,2,3,...,m. Two points A and B on a flat are ordered as follows: (0). A < B (8 follows A), if the first distinct components of A and B are xi = ai and xi = bi 'respectively, and ai < bi’ ai’bi E GF(s).] We assume from now on that all points in a flat under considera- tion have been arranged according to the above ordering (0) unless other- wise specified. Step I. p = l,2,3,...,m-l. Let 2,, I = i,2,3,...,sp", be pencils in cp, and Li be s x sm-l matrix with the flats in 2, as its rows. Note that the order of the flats in Li could be arbitrary. We define L O l LI "\ ]x(sm l_]) 2 T = I and g = p I _ _ 0 - .Lsp-I (sm '-I)x(sm '-1) (sm '-i)xi . . m . It is clear that Tp is a sp x s I matrix. Let p ngs TPES 25 * 25p L A 35 AA TpE Tp = I and Tp I L €(Sp'l_]) T*€sm-]-sg Sp-I / \\ p 54 Since‘ TS“ is a 5m-1 x Sm.I matrix and the point on the (n + us)th position of any flat in any pencil 2;, where I :_n :_s, O E_U':_Sm-2 - I, is on the flat xm = an_', the elements of the (n + us)th column of Tux form the flat x = a . p m n-I Let OIX(s-I) I E = . '|(s-I)X(s-l) 0(s-I)>