Rational G-Circulants Satisfying the Matrix Equation A² = dI + λJ Citation Lam, Clement Wing Hong (1974) Rational G-Circulants Satisfying the Matrix Equation A² = dI + λJ. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/7qh9-nn17. https://resolver.caltech.edu/CaltechTHESIS:02022021-194446003 Abstract A g-circulant is a square matrix of rational numbers in which each row is obtained from the preceding row by shifting the elements cyclically g columns to the right. This work studies g-circulants A which satisfy the matrix equation A 2 = dI + λJ, where I is the identity matrix and J is the matrix of 1's. Necessary and sufficient conditions are given for the existence of solutions when g = 1. The existence of (0,1) g-circulants satisfying A 2 = dI + λJ is shown to be equivalent to the existence of (v, k, λ, g)-addition sets, which are generalizations of difference sets. It is proved that there are no nontrivial (v, k, λ, 1)-addition sets. Some examples of (v, k, λ, g)-addition sets are given and the multiplier theorem for (v, k, λ, g)-addition sets is also proved. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics and Engineering Science) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Minor Option: Engineering Thesis Availability: Public (worldwide access) Research Advisor(s): Ryser, Herbert J. Thesis Committee: Unknown, Unknown Defense Date: 5 March 1974 Funders: Funding Agency Grant Number Caltech UNSPECIFIED Army Research Office (ARO) UNSPECIFIED Record Number: CaltechTHESIS:02022021-194446003 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:02022021-194446003 DOI: 10.7907/7qh9-nn17 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 14071 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 04 Feb 2021 17:16 Last Modified: 29 Jul 2024 22:40 Thesis Files PDF - Final Version See Usage Policy. 11MB Repository Staff Only: item control page

RATIONAL G-CIRCULANTS SATISFYING THE MATRIX EQUATION A 2 = dI + \.J Thesis by Clement Wing Hong Lam In Partial Fulfillment of the Requir ernent for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1974 (Submitted March 5, 1974) ii ACKNOWLEDGMENTS I wish to express my gratitude to Professor H . J. Ryser for his invaluabl e assistance in the preparation of this thesis . I would also like to thank Professor O . T . Todd and Professor H. H. Kisilevsky for many helpful conversations on this and related topics. Special thanks go to the California Institute of Technology and the United States Army Research Office at Durham for their financial support in the form of a teaching and a research assistantship, respectively. Finally, I would like to thank my wife, Lily, for her encouragement and help in preparing the manuscript. iii ABSTRACT Ag-circulant is a square matrix of rational numbers in which each row is obtained from the preceding row by shifting the elements cyclically g columns to the right. This work studies g-circulants A which satisfy the matrix equation A 2 = dI + \J, identity matrix and J is the matrix of 1 1 s. where I is the Necessary and sufficient conditions are given for the existence of solutions when g = 1. existence of (0, 1) g-cir culant s satisfying A 2 The = dI + \.J is shown to be equivalent to the existence of (v, k, A, g)-addition sets, which are gen eralizations of difference sets. It is proved that there are no non- trivial (v, k, \, 1 )-addition sets. Some examples of (v, k, A, g)-addition sets are given and the multiplier theorem for (v, k, A, g)-addition sets is also proved. iv TABLE OF CONTENTS Chapter Title Page Acknowledgments 11 Abstract iii Table of Contents lV 1 INTRODUCTION 1 2 ELEMENTARY PROPERTIES OF G-CIRCULANTS 5 3 RATIONAL G-CIRCULANTS SATISFYING 2 = dI + A.J 8 4 THE CASE g = 1 16 5 ADDITION SETS 23 6 (v, k, A, g)-ADDITION SETS 40 References 49 A 1 Chapter 1 INTRODUCTION Ag-circulant matrix, or simply a g-circulant, is an n x n square matrix of rational numbers, in which each row (except the first) is obtained from the preceding row by shifting the elements cyclically g columns to the right. The connection between the elements a . . of the ith row and lJ elements of the preceding row is given by ( 1. 1) where indices are reduced to their least positive remainders modulo n . A I -circulant will simply be called a circulant. A primitive g-circulant is a (0, 1) - n x n as follows: p .. = 1 if j = gi (mod n) lJ ( p = g ! p.. = 0 lJ otherwise where the indices run from 0 to n- 1. matrix P I I g defined , It can be ea s ily seen t h at P (1. 2) g is indeed a g -circulant . Unless otherwise specified, the indices for an n x n matrix will run from O to n-1. The circulant with 1 1 s in the (0, 1 ), (1, 2), •• • , (n-1, 0) positions and with O's elsewhere will be denoted by C. A generalized Hall polynomial, or simply a Hall polynomial, of a g-cir culant matrix A is the polynomial a.x 1 i ( 1. 3) 2 where (a , a , ••• , an - l) is the first row of A . 0 1 A (v, k, A) - difference set D = [ d , d , •• •, dk} is a callee 2 1 tion of k residues modulo v, such that for any residu e a -/=. 0 (mod v) , the congruence d. l d. J - a ( 1. 4) (mod v) has exactly "- solution pairs (d., d.) with d. and d . in D. l J l J With every (v, k, 11.) - difference set D, we associate a rriatrix A given by k A d. = ~ G l ( 1. 5) i=l This is called the incidence matrix 0£ the (v, k, 11.) - difference set . When the meaning is clear from the context, the incidence matrix will be called a difference set. The matrix J will denote the matrix with all 1 1 s. The matrix I will be the identity matrix. G-circulants have appear e d in many recent combinatoria l problems . Knuth [ 1970 J inve sti g ated t he (0, I) - matr i ces A wh ich satisfy the relation (1. 6) A necessary condition for a solution is that the order n of the matrix is a square. Indeed, when n is a square, there exists a $-circulant which satisfies (1. 6 ). Ryser [l 970J investigated (0, 1) - matrices A of order n which 2 satisfy the matrix equation A =D +11.J, where D is a diagonal matrix. He 3 showed that apart from certain exceptional matrices, A 2 A must satisfy = dI + :\.J , where in (1. 7) the matrix A has constant line sums (1 • 7 ) c, and the param- eters satisfy the conditions 2 = d + ),_n (1. 8) -),_ < d ~ C - A. ( 1. 9) c and Again for d = 1, c-circulant A and any parameter set that satisfies (1. 8) and (1. 9) , a exists, satisfying (1. 7). g-circulant matrix can also be considered as an adjacency matrix of a graph. Such graphs have been given many names: cyclic graphs, starred polygons, etc. (El spas and Turner [ 1970 J; Turner [1967], Tuero [1961], and Berggren [1962]). Albow and Brenner [1963] have derived some elementary multiplicative properties of Chapter 2. g-circulants, . which will be summarized in However, the main purpose of this work is to investi gat e the existence of rational g-circulants which satisfy the matrix equation (1. 7). It should be pointed out that the eigenvalues of a are especially easy to calculate. g- circulant (Al bow and Brenner [1963 J ). Equa- tion (1. 7) puts a severe restriction on the possible eigenvalues of A. This 11 eigenvalue II approach has been successful in the study of many combinatorial problems: Ryser [ 1970 ], Hoffman and Singleton [ 1960 J. However, in the study of g-circulants, the theory of polynomial 4 congruences is a more suitable and powerful technique. implies the same conditions on the eigenvalues. First of all, it But, more impor - tantly, the Chinese remainder theorem is a powerful tool in constructing solutions. With this remark, we proceed with the study of g- circulants. 5 Chapter 2 ELEMENTARY PROPERTIES OF G-CIRCULANTS The first two theorems are taken from Albow and Brenner [1963 ]. They are elementary and are quoted without proof. Theorem 2. 1 (Albow and Brenner) The equation (2. 1) characterizes the A is a g-circulant property of A. That is, the matrix g-circulant if and only if relation (2. 1) is valid. CP Corollary 2. 2 Proof: Since P g is a g = P g Cg. g- circulant, Corollary 2. 2 follows from Theorem 2. 1. Theorem 2. 3 (Albow and Brenner) an h-circulant, then AB is a If A is a g-circulant and B is gh-circulant. Corollary 2. 4 Proof: By Theorem 2. 3, P gph is a first row is identical to that of P gh' gh-circulant. Moreover, its Thus P gph = P gh' Similarly for p hp g = p gh . Corollary 2. 5 If A is a g-circulant, with (a , a , ... , an-l) as its 0 1 first row, then n-1 . 1 A=P (~ a.c "i • g i=O 1 1 (2. 2) 6 Proof: It is easy to see that the first row of the right hand side of Moreover, if we multiply the relation (2. 2) is (a , a , ••• , an-l ). 0 1 right hand side of (2. 2) by C on the left, we get n-1 . ~ 1 (6 a.c = P cg i a.ci) 1 CP g i=O ) 1 g = P i=O n-1 i\ g ( 6 a.C ) C • g ' i=O Thus, the right hand side of (2. 2) is a 1 1 g-circulant. So, relation (2. 2) holds. Conversely, we note that a matrix of the form (2. 2) is a g -circulant because it is the product of a g - circulant and a I -circulant. Theorem 2. 6 If A is a g-circulant and if B is an h-circulant with 8 A (x) and 8B (x) as their respective generalized Hall polynomials, then the generalized Hall polynomial of AB is given by ( 2. 3) Proof: Let (a , a , ••• ,an_ ) and (b , 6 , ••• , bn_ ) be the first 1 1 0 0 1 1 rows of A and B, respectively. The generalized Hall polynomials of A and B are n-1 8 A (x) = 6 i=O a.xi 1 and n-1 6 i=O respectively. . b.x 1 1 7 By Corollary 2. 5, n-1 A 6 = P g i=O . a .C 1 1 and Hence, = P h g n-1 h. ) (n6-1 b.c -~ 6 a.C (i=O 1 i=O 1 1 1 1 Since circulants multiply like polynomials (mod xn-1) and 8 AB (x ) is n-1 h"1 \ (n-1 1. ) defined by ( 6 a.C /\6 b.C , we have 1 1 1 i=O i=O 8 Chapter 3 RATIONAL G-CIRCULANTS SATISFYING A 2 = dI + AJ In this chapter, we will be considering g-circulants which satisfy the matrix equation A 2 = dI + A.J , where d and A are rational numbers. ( 3. 1 ) By applying Corollary 2. 4 and Theorem 2. 6 to this special case, we obtain the following result. Let d and A be rational numbers. Theorem 3. 1 An n x n g - circulant A satisfies (3. 1) if/ and. only if (i) d -/- 0 implies g (ii) 8A(xg) 8A(x) - 2 = 1 (mod n) , (3. 2) d + A T(x) (mod xn-1) T (x) = 1 + x + .•. where X n-1 Proof: If A satisfies (3. 1 ), then (ii) follows from Theorem 2. 6. Moreover, if d-/- 0, implies that g 2 then dl + A.J is a = 1 (mod n). If a implies that the first row of A 2 I -circulant, and Theorem 2 . 3 g-circulant is e qual to the first row of dI + A.J . Now, if d = 0, (ii) is enough to assure that A implies that A 2 A satisfies (3 . 2), (ii) 2 = AJ. is a I-circulant, and we have A 2 If d-/- 0, (i) = dI + AJ. Next, we want to look carefully at the polynomial c ongruence relation ( 3. 3) In the remaining parts of this work, we are only concerned with the matrix equation A 2 = dl + A.J, and in this context, there is no 9 ambiguity in writing 8(x) for 8 A (x ). Let cp (x) be the monic polynomial satisfied by the primitive w w-th root of unity over the rational field, i.e. the w-th cyclotomic polynomial. It is well known that this polynomial is irreducible over the rationals, and that Q[x]/cp (x) is isomorphic to the cyclotomic w field Q(s J, where Q[x] is the polynomial ring with rational coef- ficients, s w is a primitive w-th root of unity, and Q is the field of rational numbers. Let us look at equation (3. 3) modulo the various cp (x) 1 s, where w w divides n. These reduced polynomial congruence relations are easier to solve, and we will construct a solution to (3. 3) using the Chinese remainder theorem. We let the remainder of 8 {x) taken modulo cp (x) be 8 (x). w As cp (x) divides w cp (xg) when (g, w) = 1, we find that the remainder w Since w divides n, of 8(xg) taken modulo cp {x) is 8 (xg). w divides xn -1 . w cp (x) w Relation (3. 3 ), when taken mod ulo cp (x), gives w For w= 1, cp (x) = x - 1, w and Q[x]/(x-1) is m e rely Q. (3. 4) becomes a numerical relationship, or w 2 C = d + All J where c = 8(1 g) is the row sum of the g-circulant A. Now, 10 For w-/- 1, cp (x) divides T( x ). Thus (3.4)becomes w 8 (x g) 8 (x) w - w (mod cp (x)) d ( 3. 5) w It follows that (3. 5) induces a factorization of d 1n Q( sJ, namely ew( s wg) ew( s w) = d and vice v ersa. ( 3. 6 ) This is because the isomorphism between Q [ x ] / cp (x ) w and Q( s ) can be obtained by mapping f(x) of Q [x] / cp (x) onto f( s ) in w Q( SJ· w w Results in difference sets corresponding to (3. 5) and (3 . 6 ) have been noted in Baumert [1971 ] . The Chinese remainder theorem establishes the isomorphism ( 3 . 7) Thus, if we are given a set of polynomials 8 (x) 1 s corresponding to . the various cp (x) s, 1 we can find a unique 8 (x) modulo xn -1 , w that for all w such w\n, 8 (x ) = 8 (x ) (mod cp (x) ) . w w In fact, Baumert gives an explicit formula for determining 0 (x ). e(x) - n-1 I · 8 (x) B W n, W (x) (mod x n -1) , Thu s ( 3. 8) win where B (x) = n,w l r and µ is the Mobius function . IW n W X -1 µ(-) r - r r X -1 ( 3. 9) 11 With the above observations, we can prove the following theorem. Theorem 3. 2 Let .J and :\ be rational numbers. Ann X n g-circulant A satisfies the matrix equation A 2 = dl + :\J if and only if (i) d '/- 0 implies g 2 -= 1 (mod n) ( 3. 10) (ii) the row sum c of A satisfies 2 C = d + All ( 3. 11) and (iii) for all divisors wof n, w'/- 1, (3. 12) where S is a primitive w-th root of unity, and 9 (x) is the remainder w w of the Hall polynomial of A taken modulo cp W(x). Proof: Assume that a A 2 = dl + 11.J. g-circulant A satisfies the matrix equation Condition (i) of Theorem 3. 1 implies (3. 10). Condition (ii) of the same theorem implies that the Hall polynomial of A satisfies ( 3. 13) Let w be a divisor of n and cp (x) the w-th cyclotomic polyW nomial. Relation (3. 13), when taken modulo cpw(x) becomes 9 (xg) 8 (x) = d + AT (x) w w (mod cp (x)) , w (3. 14) 12 where 8 (x) is the remainder of 8 (x) taken modulo cp (x). w w For w = 1, (3. 14) gives the relationship (3. 11 ). For w f l, (3. 14) becomes (mod cp (x) ) . ( 3. 15) w It follows that (3. 15) induces a factorization of d in Q( s ) of the form w (3. 12), and we have proved the necessary part of th e theorem. Next, we assume that A is a polynomial. g - circulant w ith 0 (x ) as its Hall Be cause of the isomorphism between Q [x] / cp (x) and w Q(sw), (3. 12) induces the polynomial congruence 8 (xg) 8 (x) w for all divisors w =d (mod cp (x) ) , w w of n not equal to 1. When ( 3. 16) w = 1, cp 1 (x) = (x-1) and (3.11) implies that (3. 1 7) Since 8 (x) is merely the remainder of tre Hall polynomial of A taken w modulo cp (x), relation (3. 1 7) can b e written as w 8 (xg) 8(x) - d + \.n (mod cp (x )) . 1 (3. 1 8 ) And (3. 16) can be written as (3. 19) for all divisors w of n not equal to 1. Hence we find that 8(xg) 8 (x) satisfies all of the congruences in (3. 18) and (3. 19). Since cl + \.T(x) is a lso congruent lo cl mocluJo rr w(x ) 13 and congruent to d + An modulo cp (x), the Chinese re 1 mainder theorem implies that for w/ l n (mod x -1) • Now, together with (3. 10), the conditions (i) and (ii) of Theorem 3. 1 are satisfied, and hence A satisfies the matrix equation A 2 = dl + AJ. In fact, Theorem 3. 2 gives us a method of constructing solutions for (3. 1) when the conditions of Theorem 3. 2 are satisfied. How- ever, we have to interpret (3. 12) carefully. In the field Q(sJ, every element can be represented as ~ (w) -1 a. S l , \ /_, l W where a. E: l Q, and i=O ~ (w) If g ~ -function. is the Euler 2 = 1 (mod n), sending s w (g, w) = 1 for all divisors w of n. to s g is an automorphism of Q. w The map o Now (3. 12) can be inter - preted as saying that d factorizes in Q(sw) into a product of 8 w( S w) and its image 8 (s g) under the map a. w w We now prove the following theorem. Theorem 3. 3 - 1 (mod n). Let d and A be rational numbers, and g 2 = Suppose we have (i) d + An is a rational square, and (ii) for every win not equal to 1, {3.20) d factors in Q(s ) as ew(s wg) ew<s I.If) = d. , w (3.21) 14 Then there exists an n X n g-circulant A which satisfies (3. 1 ). Proof: Using the isomorphism between Q( s w ) and Q[x] / C{J (x), for w each w, we can define a polynomial 8 (x) such that w 8 (xg) 8 (x) w w =d (mod C{J w (x)). (3. 22) Using the Chinese remainder theorem, we can define a polynomial 8(x) in Q[x] / xn -1, such that 8(x) = 8w (x) (mod C+Jw (x)) ( 3. 2 3) (mod C+J (x )) • 1 (3. 24) for all win not equal to 1, and 8(x) Putting xg for - Jd + An x in (3. 23 ), we obtain 8 (xg) But (g, w) = 1 as g 2 - =8 w (xg) (mod C{J 1 (mod n); hence C{J w (xg) ) • (x) divides w (3. 25) C,O (xg) . w Hence (3. 24) implies 8 (xg) We now define an n X n Then 8 modulo w = 8 (xg) w (mod cp w (x) ) • (3 .26 ) g-circulant A with 8(x) as its Hall polynomial. (x) will be the remainder of the Hall polynomial of A taken C{J w (x). A satisfies (3 . 1). The conditions of Theorem 3. 2 are satisfied and hence 15 The problem of finding g-circulant solutions to (3. 1) now re duces to the problem of determining when d can be factorized into the special form of (3. 21 ). complicated. The problem involving general g 1 s is very However, for g = 1, (3. 21) is equivalent to the require- 2 ment that the polynomial x - d has both of its roots in Q(sJ, this case we say that d is a square in Q(l;W). carries this investigation further. and in The next chapter 16 Chapter 4 THE CASE g = 1 In this chapter we will solve the equation A 2 = dI + 11.J , (4. 1) Since g = 1 we auto- where the matrix A is a rational circulant. matically have g 2 = 1 (mod n). is now simply 0 (S w w ). Moreover, in condition (3. 21 ), 0 {I; g) w w Thus, the conditions in Theorem 3. 3 are simplified to (i) d + 11.n is a rational square, and ( 4. 2) (ii) d is a square in every cyclotomic field Q(sw), where w is a divisor of n and not equal to 1. ( 4. 3) If d is itself a rational square, condition (4. 3) is automatically satisfied. The study of the case where d is not a rational square requires the following number theoretical lemma. Many of the facts quoted can be found in Lang [ 1965 J. Lemma 4. 1 s k be a p'1, -th root of Let p be an odd prime and let unity, where k ~ 1. p Then the cyclotomic field Q(s k) has a unique quadratic subfield a(f(-l)(p-l)/Z p). p Proof: When p is an odd prime, the Galois group of the cyclotomic field Q(s k) over Q is cyclic; in fact, it is isomorphic to the multi- p k * k plicative group (Z/p Z) of residues modulo p that are relatively prime top • k The degree of the field extension is t (p ), where t (x) is the Euler i > -function. It is well known that ip (p k ) = (p-1 )p k-1 • 17 Since p is an odd prime, even. Thus, there exists a uniqu e subgroup of index 2 in the Galois group, and correspondingly a unique It is well known that the quadratic subfiel d in Q( s p) . 1 ) (p -1 ) 72 p ) • As Q( s ) is a subfield in Q( s l ), this is the quadratic subfield. is Q ( ✓ (- p pC unique quadratic subfield. The next theorem gives the necessary and sufficient condit i on for the- existen c e of a solution to (4 . 1). of distinct solutions. Moreover, it gives the numb e r Here two solutions are treated as distinct pro- vided their Hall polynomials are different. 1 We will use the Legendre symbol (~ ) -2.:..!. for (-1) 2 J and T(n) will denote the number of divisors of n. Theorem 4. 2 Let A be a rational circulant matrix of order n > 1. The matrix equation A z = dI + 11.J (4 . 4 ) has a solution if and only if d + 11.n is a r ational square, a nd ( 4. 5) d is a ration square unless n is a power of an odd prime p , in w hi c h case it can also be the product of a rational square with ( -l) p. , Pf (4 . 6 ) Moreover , if a solution exists, the number of distinct solutions 1s found as follows: if d = 0 and 11. = 0, then there is only one solution, A = 0; ( 4. 7) if d = 0 and A f. 0, ( 4. 8) then there are two solutions; 18 if d I- 0 and d + 11.n = 0, then there are 2'T"(n)-l solutions; and (4. 9) if d -/ 0 and d + 11.n -/ 0, then there are 2 'T (n) (4. 10) solutions. Proof: Assume that both conditions (4. 5) and (4. 6) are satisfied. Condition (4. 5) is the same as condition (4. 2). then condition (4. 3) is also satisfied. If d is a square, If d is not a rational square, condition (4.6) implies that n is a power of an odd prime, and that d is the product of a rational square with ( ~ ~p. In this case, we can show that d is still a square in all the cyclotomic fields of condition (4. 3). This is because all the divisors of n are powers of the same odd prime. Hence, Lemma 4. 1 implies that all of these fields have the same quadratic subfield o(/( ;1 ) p ). The fact that d is a square in this quadratic subfield implies that it is a square in all the cyclotomic fields in question. Hence, conditions ( 4. 5) and ( 4. 6) are equivalent to the conditions (4. 2) and (4. 3). Using the Chinese re- mainder theorem, we can construct a 0(x) such that ( 4. 11) The existence of 0 (x) satisfying (4. 11) is equivalent to the existen ce of a rational circulant satisfying the matrix equation (4 . 4), and we have proved the sufficient part of the theorem. Next, we suppose that there exists a solution of (4. 4). (4. 5) must be satisfied. Then To prove (4. 6 ), we have to prove that if d is not a rational square, then n is a power of an odd prime is a product of a rational square with ( -pl p and d )p. If n is even, then by (4. 3), · d is a square in Q( s ). 2 But 19 s2 = -1 and Q(!; 2 ) = Q. Thus (4. 3) implies that d is a square in Q, I contradicting the assumption that d is not a rational square. Let p be an odd prime dividing n. 2 that is d = a , is a square in Q(!; ), p a quadratic subfield of Q(!;p). is unique. Then (4. 3) implies that d not in Q. a But then Q(a) is By Lemma 4. 1, the quadratic subfield Hence a = a +b• {mp for some a, b in Q. Hence (4 . 12) Since d = a 2 is in Q, we have 2ab = O. would be a rational square. If b = O; then a = a and d Hence a = 0 and d = ( -1 ) b 2 p, p (4.13) which is the required form. Suppose there exists another odd prime q /. p which divides n. By similar reasoning d = (q-1) c 2q, where c E: But (4.13) and (4.14) together imply that either p/q or rational square, and this is impossible. (4 . 14) Q. -p/q is a Hence n must be the power of an odd prime. It still remains for us to count the number of distinct solutions. In constructing solutions, we use the Chinese remainder theorem to construct a polynomial 8 (x) 2 n 8(x) in Q[x] /x -1 such that = d + 11.n (mod x-1) ( 4. 15) 20 8 (x) and 2 = d (4. 16) where w divides n and is not equal to 1. Hence 8(x) is congruent to the square roots of the right hand sides of (4. 15) and (4. 16). In taking square roots, different choice of sign will give us different 8(x) 1 s, long as the terms involved are not equal to O. the cases involving O's separately. as So, we have to look at When both d and d+ An are non-zero, there are a total of 'r(n) square roots. Hence there are 2-r(n) solutions in this case. If d = 0 and A = 0, the equation reduces to A 2 = O. If 8 (x) is the Hall polynomial of A, ( mod cp w(x)) 8 (x) - O for all divisors w of n. The only possible solution is for 8(x) = O. Hence there is only one solution, namely A = O. If d = 0 and A -:/ 0, there are two choices for the square root of An. The other square roots in condition (4 . 3) are all O's . Thus, there are only two solutions. If d -:/ 0 and d + An = 0, there are -r(n) - 1 cyclotomic fields in condition (4. 3), each of which gives two choices for the square root of d. Thus, there are a total of 2 -r(n)-1 choices. Let us now look at some examples of the construction of solutions . Recall that 8 (x) B . (x) 8(x) = .!._ \ n l W n, W w\n ( 4. 1 7) 21 and B For n = 5, B 5 1 (x) = \L n, w (x) = x 4 r Iw (X-nr -1- ) • µ, ( -W ) r r X (4.18) - 1 + x 3 + x 2 + x + 1, and ' B 5 5 4 3 2 (x) = -x - x - x - x + 4 • ' Example 1: d = 1, c = 4 and A = 3. Conditions (4.2 ) and (4 . 3) g ive 8 l (x) = ± 4, and 8 (x) = ± 1 • 5 Consider the case 8 (x) = +4 and 8 (x) = +l. 1 5 Using (4. 17), e(x) = 51 (3x4 + 3x 3 + 3x 2 + 3x + 8) The other 3 solutions are x and -(x 4 4 1 4 3 2 + x 3 + x 2 + x, - 5 (3x + 3x + 3x + 3x + 8), + x 3 + x 2 + x ). Example 2: d = 5, Observe that (I; of unity. 5 (mod x -1 ). 8(x/ = 1 + 3T (x) which satisfies 4 c = 15 and A= 44. s3 - S2 + I; ) 2 = 5 where I; is a primitive 5th root Thus 8 (x) = ± 15, 1 8 (x)=±(x 5 4 and -x 3 -x 2 +x). Taking the positive sign in both cases, (4. 15) gives 8 (x) = 4x 4 + 2x 3 + Zx 2 + 4x + 3. 22 Again, 8 (x) satisfies 8 (x) 2 = 5 + 44T (x) (mod x 5 - 1 ). Once we obtain a rational circulant satisfying equation (4. 1 ), it is not difficult to get a non-negative integral circulant satisfying the equation, although possibly with a different d and 11.. A is a rational circulant satisfying (4. 1 }. Suppose that We can construct an integral circulant by multiplying A by an appropriate factor. Then we can add enough multiples of J to obtain a non-negative integral circulant. The resulting circulant still satisfies equation (4. 1) except possibly with a different d and 11.. The interesting case occurs when A is a (0, 1) circulant. In the next chapter, we will classify all the (0, 1) circulant solutions to equation (4. 1 ). 23 Chapter 5 ADDITION SETS In chapter 4, we answered the question of the existence of rational 1-circulants A satisfying the matrix equation A 2 = dI + :\.J. (5. 1) In this chapter we restrict our attention to (0, 1) 1-circulants. There are some easy solutions to (5. 1): I 2 J 2 =I, ( 5. 2) = nJ, (5. 3) · (J -I/ = I + (n -2) J , (5. 4) and if n is even, ( 5. 5) (5. 6) where C is the special I -circulant defined in Chapter 1. The question now is whether there exist any other (0, 1 )circulants which satisfy (5. 1 ). It turns 1 out that in the (0, 1) case, the existence of such a circulant is equivalent to the existence of a math. ematical object which is defined as follows. A (v, k, :\.)-addition set A= [a , a 2 , ••• , 1 aJ, or simply an a.ddition set, is a collection of k distinct residues modulo v, such that for any residue a F O modulo v, the congruence a. 1 + a. = a J (mod v) ( 5. 7) 24 has exactly A solution pairs (a., a.) with a. and a . in A. J 1 1 J To avo id degenerate configurations, we further require that k Remark 5. 1 1 ~ ( 5. 8) It can be easily seen that every additio n set corresponds to a (0, 1) circulant satisfying A 2 = dI + 11.J. Given an addition set A, we c a n define a v X v circulant A whose first row has l's in every a. -t h position, where a . belongs to the addition set A. 1 1 The matrix A will have line sums k and will satisfy (5. 1) with an appropriate d, but the s a me A. Conversely, given a (0, 1) circul ant A satisfying (5. 1 ), an adq.ition set can be formed fr om the first row o f A. With the above remark, there is n o a mbiguity in defining a Hall p o lyno mial 8 (x) for an addition set A by k 8 (x) = I a. X l a . E: A. ( 5. 9) = d + 11.T(x) (mod xv -1), (5. 10) l i=l O bserve that k [ 8(x) J2 = I a.+a. J Xl i, j where T (x) = 1 + x + x 2 3 + x + ••• x v-1 Here, because of the similarity o f addition sets with difference sets and block designs, we change the notation for the parameters (n, c, 11.) to (v, k, 11.). Corresponding to the solutions (5. 2) t o (5. 6 ), we have the foll owing addition sets 25 (i) A= [ 0} , (ii) A= [ 0, 1, (iii) A= [ 1, 2, (iv) if v is even, A = [ v /2} (v) if vi s even, A -- .. ., v-1} , • 0 • , v-1} , fo (5 . 11) 1, l, ~2 -1, ~2 +1, ~+2 2 , •••, v-1} • ••• , The question now is whether there are any other addition sets . The main purpose of this chapter~ to derive Theorem 5 . 16 which asserts that (5 . 11) contains all ~the addition sets. Let us fi r st re stat e th e various parameter relations . 2 We h a v e =d+Av , (5 . 12) -A< d :::: k - A • ( 5. 1 3) l :::: k and Let us state some definitions which are helpful in the development of this chapt er . sets of residue s modul o v . by A EB B , An a ddi tion table of A and B, d enote d is a k X k mat r i x, w h ose (i, j)-th ent r y is (a. l + b .) taken J · modulo v . A shift of A ~ s , den ote d by s + A , is s + A = {s +a.\ a . E: A} . l l (5 . 14) Similarly, a matrix M = (m . . ) is a shift of a matrix N = (n . . ) if th e re lJ -lJ exists an integer a such that for all i, j m .. lJ = a+ n lJ. . (mod v) • 26 Let 2r divide v (r need not be maximal). A basic r -set is a set A of 2r residues modulo v defined by A = 1'- 2rv \ i = 0, 1, ••• , 2r -1 'JL The addition table AEB A is the basic r -block. Proposition 5. 2 The basic r -set A is closed under addition modulo v and each a E: A appears exactly 2r times in the basic r -block. Proof: It is easy to see that A is closed under addition modulo v a nd that the entries in each row of its addition table are distinct. Hence every a E: A appea r s in each row of the basic r -block exactly once . Thus, each a E: A appears exactly 2r times in the addition table. Corollary 5. 3 Let A be the basic r -set and let B = b + A and C = c + A be shifts of A by b and c, respectively. Then every residue that appears in the addition table B EB C is from the set (b + c) + A, and each residue appears exactly 2r times in B EB C. Proof: Let M be B EB C. as in A, If we pre serve th e same ordering in B and C M will be just a shift of the basic r -blo ck by (b + c). Hence, all the residues that appecl-r in M are from (b + c) + A and each appears exactly 2r times in M . It should be remarked that if A is any set of residues, the addition table A EB A is symmetric. li_ A is an addition set, then every non-zero residue occurs 11. times in the addition table, and 0 occurs (d + \) times. 27 We will call any addition set that 1s not covered by those listed in (5. 11) a new solution. Theorem 5. 4 If 11. is odd, there is no new solution. Proof: Let A be an addition set, with sider its addition table. 11. being odd, and let us con- Since the table is symmetric, every non- zero residue o: that appears in an off diagonal position (i, j) also appears in the off diagonal position (j, i). Since 11. is odd, o: must appear on the main diagonal an odd number of times. v-1 non-zero a 1 s and k diagonal positions. k:.:;; v. Hence k = v or v-1. But there are Hence k ~ v-1. But In both of these cases, the only solutions are the ones in (5. 11 ). Theorem 5. 5 Let A be a new solution. Then v is even. if a E: A and a is not equal to O or v/2, then a+ v/2 E: Moreover, A. Proof: If there does not exist an a E: A not equal to O or v /2, then A= [O}, [v/2}, or [O, v/2}. The only addition sets in these cases are given by (5. 11 ). Assume then that we can choose an a E: A not equal to O or v/2. Then 2a will be a non-zero entry in the main diagonal of the addition table for A. 11. is even. Since A is a new solution, Theorem 5. 4 implies that Hence, the non-zero residues that appear in the main diagonal must appear there an even number of times. In particular, there exists b E: A not equal to a such that 2a = Zb or (mod v) , 2(a-b) = 0 · (mod v) • (5.15) 28 If v is odd, (5. 15) implies that a= b, which contradicts the choice of b. Hence v is even, and the only b not equal to a which satisfies (5.15) is b = a + v/2. Lemma 5. 6 If r ::::: 1, Zr lv and tJ-ie addition set A is a union of distinct shifts of the basic r -set, then either (i) k = v, or (ii) zr+l Iv and the set A is a union of distinct shifts of the basic (r+ 1 )-set. Proof: We can rearrange A to group the shifts together, i.e. the first Zr elements of A will be the set d 1 + B, where B is the basic r -set, the second Zr elements will be d + B, and so on. Zr +l Since A is a union of distinct shifts, we have (5.16) Let With the above rearrangement, the addition table for A will be an s X s matrix of Zr X Zr blocks. of the basic r -block. Each of these blocks will be a shift Since every entry in a block appears Zr times, we have (5. 1 7) However, the s X s matrix of blocks is still a symmetric matrix. The . off diagonal blocks again appear in pairs, one on each side of the diagonal. An entry in the off diagonal block would then appear in multiples of zr+l. r r+l . If A = 2 (mod 2 ), every non-zero residue must 29 appear in some diagonal block. The total number of diagonal blocks is s and each block has 2r distinct entries. or, ~ k But 2r divides v and 2r Hence v-1 • (5. 18) divides k with r ~ 1. Hence k=v. If A== O(mod 2r+l), every non-zero residue a that appears in one diagonal block must appear again in another diagonal block. Suppose a appears in the block defined by the shifts x + B and y + B. Then and a == 2x + i _:::_ (mod v) , 2r (5. 19) a == 2y + j _:::_ (mod v) , 2r (5. 20) for some i and j between O and 2r -1. Hence, - 2 y +E r 2 (mod v) , or 2(x -y) == (j-i)v 2r If 2 \ (j -i), (mod v) • x and y will be in the same shift, contradicting the fact that they represent different shifts of B. . ·) an d 2r+l d"1v1.d es v. (J-1, Hence 2 does not divide M oreover, x == y + (j -i )v r+l 2 (mod v /2) • 30 Hence either X = y + (j -i)v 2 r+l (mod v) , or In either case, the two shifts x + B and y + B will differ only by 2 :+l' . that is x+B Hence the two shifts x + B and y + B can be grouped together into a shift of the basic (r+l)-set. Suppose there exists another diagonal block which is defined by the shift z + B. diagonal block. Let f3 be a non-zero residue that appears in this We now show that defined by either x + B or y + B. defined by x + B. f3 does not appear in the blocks Suppose f3 appears also in the block Then the previous argument implies that the two shifts x + B and z + B differ only by (v /2r+l ). Thus the two shifts y + B and z + B will be identical, contrary to the choice of z + B. Hence the shift z + B will have to pair up with yet another shift to form a shift of the basic (r+l )-set. Continuing in this manner, we can show that the whole set A is a union of distinct shifts of the basic (r+l )-set. Let us consider the implications of Lemma 5. 6. If k = v, the only addition set is A= [O, 1, ••• , v-1} which is covered by (5. 11 ). The other alternative is an induction step. Since v is finite, there exists a maximum r such that 2r divides v and the induction must 31 terminate. Thus Lemma 5. 6 implies that if for some r ~ 1, Zr divides v and the addition set A is a union of distinct shifts of the basic r-set, then A= [O, 1, ••• , v-1 }. If k is even, the hypothesis of Lemma 5. 6 is satisfied with r = 1, and we obtain the next theorem. Theorem 5. 7 There is no new solution for k an even integer . Proof: Theorem 5. 5 established the fact that v is even. Hence, z1 divides v. Moreover, if a E: A and not equal to O or v/2, then a+v /2 The two elements a and a + v /2 togeth e r are a shift of E: A. the basic 1 -set. Thus the elements of A, not equal to O or v /2, pair up as shifts of the basic 1--set. Now k is even which means that A has an even number of elements. Hence O and v /2 are either both in A or both not in A. basic 1-set. In either case, A is a union of shifts of the With the use of Lemma 5. 6, we obtain the result that there is no new solution for k an even integer. Let us summarize the results obtained up to this point. Theorem 5. 4 implies that we only have to consider the case of 11. an even integer. Theorem 5 . 5 implies that v is even, and if a E: A and not equal to O or v/2, then a+ v/2 E: A. Theorem 5. 7 settles the case of k an even integer, and we now proceed to consider the case of k an odd integer. Proposition 5 . 8 If k is odd, then either O or v /2 is in A, but not both. Proof: Theorem 5. 5 says that those a I s in A not equal to O or v /2 come in pairs. Since k is odd, the number of elements of A is odd. 32 Hence either O or v /2 is in A but not both. Remark 5. 9 solution. If A is a new solution, then v /2 + A is again a new Hence we can assume that O E: A without loss of generality. Remark 5. 10 If A is a new solution, so is the complement of A consisting of the residues modulo v that are not in A. Hence in the search for new solutions we can restrict our attention to the cases in which k Proposition 5. 11 (mod 4 ). ~ v /2 • (5.21) Let A be a new solution with k odd and A =2 Then k ~ v /2 + 1. Proof: With Proposition 5. 8 and Remark 5. 9, we can assume that 0 is in A. Let us define a new set A'= A - [O}. Now, if a E: A', then a + v/2 E: A' . the basic 1-set. Hence A' is a union of shifts of With ·s uitable rearrangement of the elements in A', the addition table for A' is again a matrix of 2 X 2 blocks. Entries in the off diagonal blocks appear in multiples of 4, and entries in the diagonal blocks appear in multiples of 2. Observe that the addition table for A is just the addition table for A' adjoined with an extra column and row which correspond to the 0 in A. The entries in the column also appear in the row as the addition table is symmetric. Hence, in the addition table for A, the 33 only entries that appear with multiplicity 2 are those on the main diagonal block, or on the extra column and row. There are a total of (k-1) /2 main diagonal blocks, each with 2 distinct elements. entries. As for the extra column, there are (k-1) non-zero Since all other non-zero entries occur in multiples of 4 and ;\ = 2 (mod 4), every non-zero residue must appear in the main diagonal bh>cks or the extra column. Thus [(k-1 )/2] X 2 + k-1 :?: v-1 2 (k - I ) ::?: v - I • or Theorem 5. 5 implies that v is even. (5. 22) Hence (5. 22) can be refined to 2(k-l)::?: v k ::?: ~ 2 or +I • Remark 5. IO and Proposition 5. 11 imply that we can assume ;\ = 0 (mod 4). Theorem 5. I 2 and O E: A. Let A be a new solution with k odd, ;\ = 0 (mod 4 ), Then (i) v = 2 (mod 4), and (ii) d = I • Proof: In the proof of Proposition 5. 11, we studied the multiplicities of entries in the addition table for A. Now when ;\ = 0 (mod 4 ), the entries with multiplicity 2 must combine among themselves to give multiplicity 4. Let us consider the non-zero entries in the extra row. First of all, they are all distinct since they are exactly the entries in 34 A - [O }. Secondly, there are (k-1) non-zero entries in the row. Hence, all these (k-1) non-zero entries must appear as entries in the diagonal blocks. However, if v = O(mod 4), then v/2 is even and all the entries in the diagonal blocks are even. entries in A are even, Hence all the non-zero But then all the entries in the addition table will be even contradicting the fact that A is an addition set. Hence v = 2 (mod 4). Since v = 2 (mod 4), v/2 is odd. k-1 elements and - 2 odd elements. the addition table modulo 2. Then A contains k;l even Since v is even, we can consider The numbers of entries congruent to 0 modulo 2 is The number of entries congruent to 1 modulo 2 is However, by the remark following Corollary 5. 3 we observe that d is the difference of the number of entries congruent to O modulo 2 and 1 modulo 2. Hence d = or d = 1 • Up to this point, all the results on addition sets are derived from the fact that the addition table is symmetric. To obtain further results, we will use the techniques developed in Chapter 4. first summarize the results that we will need later on. Let us 35 Theorem 5. 13 If a new solution exists, then one exists satisfying the following conditions: (i) v == 2 (mod 4) , (ii) d = 1, and (iii) k ~ (5.23) v /2. As in Chapter 4, we denote the Hall polynomial of an addition set by 8 (x). Let w divide v, polynomial. Let 8 (x) be the remainder of 8 (x) taken modulo cp and let cp (x) be the w-th cyclotomic w w w (x). Furthermore, we let 8 [w] (x) denote the remainder of 8(x) taken w modulo (x -1 ), and we let T (x) = 1 + x + • • • + x w ~l • If A is a new solution satisfying the conditions in Theorem 5. 13, then its Hall polynomial satisfies 8(x) 2 == 1 + AT (x) (mod xv -1) . V (5. 24) The results in Chapter 4 imply that e1 (x)= ±k, and (5.25) 8 (x) = ± 1, (5. 26) w for w dividing v not equal to 1. Since 8(x) has non-negative coeffi- cients, = +k. 8 (x) 1 (5.27) We now let p be an odd prime dividing v. Equation (5.24) taken modulo (xp -1) be comes 2 ( 8 [p] (x)) == 1 + ~v T p (x) (mod xp -1). 36 Observe that 8[p](x) again has integral coefficients. structions of Chapter 4, With the fact that 8 [p J (x). Using the con- 8[p](x) is determined by 8 (x) and 1 8p(x). 9 (x) = +k, there are only two possibilities for 1 The restriction that it has integral coefficients will give us a condition on the sign of 9 (x). p Theorem 5. 14 If A is a new solution satisfying the conditions in (5. 23) and p is an odd prime dividing v, then +l 8 (x) = p '-1 f when p divides (k-1) { when p divides (k+l) f (5.28) Proof: We will use equations (4. 17) and (4. 18) to construct 8[p](x). It is easy to calculate that B p, l (x) = T (x) p B = p - T (x). p and that If 8 (x) p p,p (x) = +l, then e[p](x) = 1 +(k-1 )T (x) p p . (5 . 29) If 8 (x) = -1, then p =-l+(k+l)T (x). p p (5. 30) Since p is an odd prime, (5. 29) and (5. 30) cannot both have integral coefficients. However, as (k+l )(k'..l) = \v, 37 If p divides any odd prime dividing v will divide either k+l or k-1. k+l, then e[p](x) is given by (5. 30) and ep (x) = -1. If p divides k-1, e[p](x) is given by (5. 29) and 8p(x) = 1. Carrying the construction one step further, we obtain the following result. The or em 5. 15 If A is a new solution satisfying the conditions in (5. 23), then v/2 divides either k-1 or k+l. Proof: Condition (i) of (5. 2 3) implies that v /2 is odd. odd prime dividing v/2. p divides k-1. Let p be an Then p divides either k-1 or k+l. Suppose We will show that v/2 divides k-1. Assume that there exists another odd prime q dividing v/2 such that q divides k+l. We now consider the possibilities for 8[pq](x), which has integral coefficients. B pq, 1 (x) = T pq A little calculation gives (x), and Since p divides k-1 by Theorem 5. 14, we have 8 (x) = 1. p 8p{x) = -1. Similarly Since e (x) is equal to k, the only choice in the formula 1 (4. 17) is in the sign of 8 pq (x). If 8 pq (x) = 1, then 38 e[pq] (x) = l + k+l pq If 8 pq (x) = -1, then q-1 k-1 T (x) - -2 e[ pq J(x)=-1+pq q pq I . 1 (xp ) • i=O However, pq does not divide k+l or k-1. Hence 8[pq](x) cannot have integral coefficients, which is a contradiction. Thus, if there exists an odd prime divisor of v/2 that divides k-1, then all the odd prime divisors of v /2 divide k-1. Hence v /2 is co-prime to k+ 1. But since (k+ 1 )(k-1) = Av; we find that v /2 divides k-1. On the other hand, if there does not exist an odd prime divisor of v /2 that divides k-1, then v/2 is co-prime to k-1 and v/2 divides k+l. Finally, we can prove that there are no new solutions. Theorem 5.16 The list (5.11) contains all of the addition sets. Proof: We have shown that if a new solution exi sts, then one exists that satisfies all the conditions in (5. 23). Theorem 5 . 15 implies that v/2 divides either k-1 or k+l. If v/2 divides k+l, then we have k+l ;e:: v/2 • Since k and v /2 are both odd, (5. 31) implies that k 2: v /2 . With condition (iii) of (5. 23 ), we have k Since k 2 = 1 + AV, we have = v /2 • (5. 31) 39 V 2 = 4 + 4 AV • The only integral solutions of (5. 32) are (5. 32) 11. = 0 and v = ±2. The addi- tion sets with these parameters are included in (5. 11 ). If v/2 divides k-1 , then either k=l or k-1 ~ v/2 • (5. 33) The addition sets with k=l are included in (5. 11). contradicts condition (iii) of (5. 23). Relation (5. 33) This finishes our proof. In the next chapter, we will look at a generalization of addition sets. Since the generalization will include all the difference sets, there will be non-trivial solutions. 40 Chapter 6 (v, k, 11., g) - ADDITION SETS In Chapter 5, we considered (0, 1) 1-circulants satisfying the matrix equation A 2 (6. 1) = dI + 11.J , and we have shown that the existence of such matrices is connected with the existence of addition sets. In this chapter, we will consider (0, 1) g-circulants satisfying (6. 1 ). These matrices correspond to a generalized version of addition sets. A (v, k, 11., g)-addition set A = [a , a , ••• , ak}, or simply 2 1 a g-addition set, is a collection of k distinct residues modulo v, such that for any residue a t O (mod v) the congruence a. + ga. = a(mod v) 1 J has exactly 11. solution pairs (6. 2) (a., a.) with a. and a. in A. 1 J J 1 Further - more, we require that k ::2: 1 • (6. 3) It should be pointed out that when g = -1, the ( -1) -addition sets are the previously defined difference sets, and when g = 1, the I -addition sets are those studied in Chapter 5. Remark 6. 1 Again, it can be easily seen that every g-addition set cor~esponds to a (0, 1) g-circulant satisfying A 2 = dI + 11.J. Given a g-addition set A, we can define the fir st row of a g-circulant matrix A by placing 1 's in each of the a. -th positions, where the a. 1 s 1 l 41 belong to the g-addition set A . obtained by shifting. The complete g-circulant is then Conversely, given a (0, 1) g-circulant A satisfying (6. 1 ), we can form a g-addition set from the fir st row of A. We can define a Hall polynomial by k e(x) = I 8 (x) for a g-addition set A a. X 1 (6. 4) a. E: A. 1 i=l Observe that 8 (x) 8 (xg) = k \ . a.+ga. Lx1 J i, j=l = d + 11. T (x) ( 6. 5) (mod xv -1 ). One can prove some elementary results about (v, k, A, g)- addition sets. Theorem 6. 2 If d f. 0, then g 2 - 1 (mod v). Proof: We have seen that a (v, k, 11., g)-addition set corresponds to a (0, 1) g-circulant satisfying A 2 = dl + 11.J. Using conclusion (i) of Theorem 3. 1, we obtain Theorem 6. 2. The multiplier theorem is important in the study of differen ce sets and a similar result can be proved for g-addition sets. Let us fir st make some definitions. Let A be a (v, k, A, g)-addition set. Define A+ x = [a + x \ a E: A} for each residue x modulo v. Then A +xis called a shift (6. 6) of A. If A is a (v, k, A, g)- addition set and x is any residue modulo v, define 42 xA = [ xa I a E: A} (6. 7) I£ xA is a shift of A, then x is a multiplier of A. In particular, if xA = A, then x fixes A. The trivial multiplier I always fixes a g-addition set. The following theorem is a generalization of the multiplier theorem for difference sets to addition sets. The proof is very similar to the original one given for difference sets. Theorem 6. 3 where k 2 and p > A, (Hall and Ryser [ 1951 J ). If A= (a 1 , a 2 , •.. , ak} is a = d + AV, (v, k, A, g)-addition set, and if p is a prime dividing d such that (p, v) = 1 then p is a multiplier of the g-addition set. Proof: Since A is a g-addition set, its Hall polynomial satisfies V (mod x -1) • ( 6. 8) Observe that if f(x) is an arbitrary polynomial with integral coefficients, then f(x)T (x) = f( I )T (x) By hypothesis p divides d but not v . Thi-s implies p does not divide k . V (mod x -1) . Also p > A and k (6 . 9 ) 2 = d + AV. Thus (mod p) . Since all the binomial coefficients(?), where 1 (6.10) 1 = 1, 2, ••• p-1, are I divisible by p, we have (6. 11) 43 We now multiply (6. 8) by 8(x) p-1 and apply (6. 9), (6.10) and (6. 11). The resulting relationship is (6. 12) where R(x) is a polynomial with integral coefficients. Pu.ting x = 1 in (6. 12), we get k 2 = "Av + pR ( 1 ) Thus (6. 13) pR(l) = d • We now have four relations (6. 14) The first of these is (6 . 8) . The second uses the fact that pA i s again a g-addition set, since p is prime to v. The third one is (6. 12), and the fourth one is obtained by putting xg in (6. 12 ), and observing that g 2 = 1 (mod v), T(xg) = T(x) (mod xv -1) and In (6.14), the product of the left sides of the first two congruences is the same as the product of the third and fourth. Hence 44 [1c T(x) + pR(x)} [1c T(x) + pR(xg)} = (d+1cT(x)) 2 (mod xv -1). (6.15) Now, using pR(l) = d, together with (6. 9), we see that (6. 15) simplifies to 2 g 2 p R(x)R(x ) = d The expression 8(~) 8(xg) o f V (mod x -1). (6. 12) regarded as a polynomial of degree less than v has non-negative integral coefficients. p > 't.., cients. (6. 16) Now and this implies that R(x) in (6. 12) has non-negative coeffi The structure of (6. 16) implies that R(x) cannot have more than one positive term. Hence, R(x) is a monomial, (say wxs), and = pwxs = dxs pR(x) V (mod x -1) . (6. 1 7) We now multiply (6.11) by 8(x) and apply (6. 8), (6. 9) and (6. 17). This gives Dividing by d, X s 8(x) V (mod x -1) , (6. 18) which implies that p is a multiplier. Remark 6. 4 Observe that since R(x) is a monomial, by substituting it into (6. 16) we get p Hence, 2 W 2 · s+gs = d2 X v \ s(g+l) • V (mod x -1) . (6. 19) The multiplier theorem is useful in constructing difference 45 sets. It is hoped that new g-addition sets can also be constructed. Next we consider some examples of (v, k, A, g)-addition sets. The following result was fir st reported in Ryser [ 1970]. Theorem 6. 5 If k 2 = 1 + \v, then the set A= [O, 1, •.• , k-1} is a (v, k, 11., k)-addition set with d = 1. Proof: Let 8(x) be the Hall polynomial for A. Then 2 k k -l 8 (x) 8 (x ) = 1 + x + • • • + x • (6 . 20) V Equation (6. 20) taken modulo (x -1) becomes k 8(x)8(x ) = 1 + \(1 + x + ••• + x v-1 ) v (mod x -1). (6. 21) Hence A is a (v, k, A, k)-addition set with d = 1. Remark 6. 6 In the case of difference sets, it is well known that is never a multiplier of a non-trivial difference set. -1 (Johnsen [1964], Brualdi [1965] and Yates [1967]). Let us consider the (8, 3, 1, 3)addition set constructed in Theorem 6. 5 . It can be easily checked that -1 is the only non-trivial multiplier for this 3-addition set. Theorem 6. 7 Let A be a (v, k, A, g}-addition set with d f. 0. Then it is also a (v, k, A, h)-addition set if and only if gh is a multiplier fixing A. Proof: Assume that A is both a g- and an h-addition set. V (mod x -1) , Then (6 . 22) 46 and h 8(x)8(x ) = d + 11.T(x) Substituting x h V (mod x -1) . (6. 23) for x in (6. 22), we obtain (6. 24) Hence, (6. 24) implies (6 . 25) Multiplying (6.25) by 8(x}, we have Using (6. 23}, we have Observing that 1 8 (x )T (x) = kT (x) (mod xv -1) , for any i, we have d 8 (xgh) + 11.kT (x) = d 8 (x) + 11.kT (x) If d -/- 0, (mod xv -1) • (6. 26) implies that 8(x gh ) -= 8(x) (mod xv -1) , which is the same as saying that gh is a multiplier fixing A. Next we assume that A is a g-addition set with gh as a multiplier fixing A. Then (6.26) 47 V (6. 2 7) (mod x -1) . Since gh is a multiplier fixing A, 8(x) = 8(xgh) (mod xv -1 ). V Hence (6. 28) (mo d x -1 ). Substituting xg for x in (6. 28), we have (6.29) We now use the fact that d (= 0 implies g divides (xvg_l) and that T(xg) = T(x) 2 = 1 (mod v), (mod xv -1). that (xv-1) Equation (6. 29) then implies that 8(xh )8(x) which means that Corollary 6. 8 - d + \T(x) = (mod x V -1), A is also an h-addition set. A (v, k, \)-difference set is also a (v, k, A, g)-addition set if -g fixes A. Corollary 6 . 8 implies the existence of many (v, k, A, g)-addition sets. The following is a list of those with g (= -l and v < 50. V k A g d A 15 7 3 11 4 {O, 1, 2, 4, 5, 8, 10} 21 5 1 13 4 { 3, 6, 7, 12, 14} 3.5 17 8 6 9 £0, 1, 3, 4, 7, 9, 11, 12, 13, 14, 16, 1 7, 21, 27, 28, 29, 33} 40 13 4 31 9 {1, 2, 3, 5, 6, 9, 14, 15, 18, 20, 25, 27, . 35} 48 There is still much that can be done concerning g-addition sets. The following are some suggestions. 1) Construct solutions with d -/- 0, 1, or k-:\.. 2) Find more non-existence results. 3) Search for all possible 4) Generalize the notion of g-addition sets to the notion of g-addition sets for, say, g-addition sets over an abelian group. v :-;; 100. 49 REFERENCES Ablow, C. M., and Brenner, J. L. 1963 "Roots and Canonical Forms for Circulant Matrices, 11 Trans. Amer. Math . Soc. 107, 360 -376. Baumert, L. D. 1971 Cyclic Difference Sets, Lecture Notes in Mathematics , Vol. 182, Springer -Verlag. Berggren, J. L. 1962 11 An algebraic characterization of symmetric graphs with a prime number of vertices, 11 Bull. Aust. Math. Soc. 7, 131-134. Brualdi, R. A. 11 1965 A Note on Multipliers of Difference Sets, 11 J. Res. Nat. Bus. Standards, Sect. B 698, 87-89. El spas, B., and Turner, J. 1970 "Graphs with Circulant Adjacency Matr ice s , " J. Comb. Theory 9, 297-307. Hall, M., and Ryser, H. J . 1951 "Cyclic Incidence Matrices, " Canad. J. Math, 3, 495 -502. Hoffman, A. J., and Singleton, R . R. "On Moore Graphs with Diameters 2 and 3, 11 I. B. M. 1960 J. Res. Develop. 4, 497-504, Johnsen, E. C. 1964 "The Inverse Multiplier for Abelian Group Differenc e Sets, 11 Canad. J . Math. 16, 787-796. 50 References (Continued} Knuth, D. E. 1970 11 Notes on central groupoids, 11 J. Comb. Theory 8, 376-390. Lang, S. 1965 Algebra,. Addison-Wesley Ryser, H. J. 1970 ''A Generalization of the Matrix Equation A 2 = J, 11 Lin. Alg~ and its Appl. 3, 451-460. Tuero, M. 1961 11 A contribution to the Theory of Cyclic Graphs, 11 Matrix and Tensor Quart., 74-80. Turner, J. 1967 11 Point -Symmetric Graphs with a Prime Number of Points, 11 J. Comb. Theory 3, 136-145. Yates, D. L. 1967 11 Another Proof of a Theorem on Difference Sets , " Proc. Cambridge Philos. Soc. 63, 595-596.