You are here

Difference Sets: Connecting Algebra, Combinatorics, and Geometry

Emily H. Moore and Harriet S. Pollatsek
American Mathematcial Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 67
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Mark Hunacek
, on

One of the real pleasures of our subject, I have always thought, is seeing how different branches of it relate to one another. As an undergraduate at Brooklyn College in the late 1960s and early 1970s, I was lucky enough to take a course in projective geometry, which led me to discover the fascinating connections between that subject and both linear and abstract algebra. Then I learned about finite fields and how they can be used to coordinatize certain kinds of finite projective planes, which in turn led me to see connections between combinatorics and geometry. Somewhere along the line I was advised to talk to one of the more senior members of the department, James Singer, who was good enough to spend time talking to a student who wasn’t even registered in any of his courses about these connections. What I didn’t realize at the time was that Singer was quite an influential person in the area, and that he (thanks to a paper he wrote back in 1938) is largely credited with discovering the concept of a difference set, the subject of this very interesting book. I also didn’t realize, until seeing this book, that the connections between difference sets and other areas of mathematics go far deeper than I had previously thought.

The goal of this book is to introduce difference sets to an undergraduate audience with a relatively modest background (say, a good semester of abstract algebra) and to illustrate connections with algebra, geometry and combinatorics. This goal has certainly been achieved.

The book begins with an excellent opening chapter which gives a provisional definition of a difference set, provides a specific example, and then uses this example to illustrate various ideas which will then be revisited during the rest of the text. Specifically, a difference set is initially defined as follows:

suppose that G is a finite abelian group (written additively) with \(v\) elements and that D is a nonempty proper subset of G with \(k\) elements. D is called a \((v,k,\lambda)\)-difference set if there exists a positive integer \(\lambda\) with the property that every non-identity element of G can be written in exactly \(\lambda\) ways as the difference of two elements of D. So, for example, it can be routinely verified that H = {1, 2 4} is a (7, 3, 1)-difference set in the group \(\mathbf{Z}_7\); this is the initial example given in the text. In chapter 4, the notion of a \((v,k,\lambda)\)-difference set is broadened to allow (possibly) non-abelian groups, with multiplicative notation replacing the additive notation of chapter 1.

Before getting to chapter 4, however, the authors take two chapters to discuss the theory of designs (which are also given by three parameters) and their automorphisms, a discussion that includes a look at group actions. This concept is developed from scratch, but some important results, such as the orbit-stabilizer theorem and Burnside’s lemma, are given without proofs (the proof of the former is left as an exercise, and a reference is given for the proof of the latter). This illustrates, by the way, a very nice feature of this book, which is that, as a student progresses through it, he or she will find frequent discussions (sometimes brief, sometimes more extensive) of topics that may not be in the mainstream of undergraduate mathematics education. We see, for example, discussion of group actions in this chapter, a section on group rings (over the ring of integers) in chapter 4, a little bit of number theory (sums of four squares) and quadratic form theory in chapter 5, etc. Somewhat later in the book there are whole chapters on such side topics; we’ll get to that shortly.

Chapter 4, as previously noted, re-introduces the notion of a difference set, this time in a possibly non-abelian setting; more examples are provided, and connections with designs are mentioned (in brief: every difference set produces a symmetric design with the same parameters, and, going the other way, a group contains a \((v,k,\lambda)\)-difference set if and only if it acts regularly on the points and blocks of a symmetric design with the same parameters). Difference sets in non-abelian groups, by the way, raise some interesting questions noted by the authors, including the (currently unanswered) one as to whether they even exist at all in the dihedral groups Dn. (The conjecture, the authors tell us, is that they do not.)

The next five chapters of this book all involve different aspects of the existence question for difference sets. Chapter 5, for example, gives a statement and proof of a famous result in combinatorics called the Bruck-Ryser-Chowla theorem, which provides necessary conditions for the existence of \((v,k,\lambda)\)-designs (and, hence, by the remarks above, difference sets with the same parameters). My undergraduate projective geometry text, Blattner’s Projective Plane Geometry, made a fleeting reference to this result, but did not even provide a statement of it, let alone a proof; I remember looking up the reference that Blattner provided and, not surprisingly for a third-year undergraduate, finding the cited paper completely incomprehensible. Here, the authors give an undergraduate-accessible proof, using the number theory and quadratic form theory referred to earlier. (This strikes me as a useful reference, since a quick glance at the combinatorics books on my shelf reveal that not all of them give a proof of this result, and those that do don’t make it quite as accessible as the one given here.)

Lots of other issues are discussed in chapters 5 through 9, including but not limited to: three different approaches (one of them by my former professor, Singer) to the creation of difference sets from affine and projective planes; the relationship between difference sets and Hadamard matrices, and the concept of a “multiplier” for a difference set D in a group G (which is an automorphism of G that maps D into a translate of itself).

Chapters 10 and 11 are a self-contained introduction to the theory of group representations (over the field of complex numbers) and characters, necessitated by the fact that these areas are (as described in these chapters) useful in the study of difference sets. Even forgetting for a moment this connection with difference sets, these chapters provide, in about 60 pages, about as clear and concise an introduction (with proofs) to group representation theory as any reference I know, and I would have no hesitation directing a student interested in learning about this subject here as a useful entrée into the area.

The next chapter is entitled “Using Algebraic Number Theory”, and is devoted to showing how group characters and rings of cyclotomic integers can be used to prove results on difference sets, including a fairly technical theorem due to Turyn. After this, the book ends with a final, somewhat expository, chapter on applications of difference sets to various contexts in engineering and other sciences, including error-correcting codes and astronomy.

Since it should be clear from the foregoing that there are not too many standard courses in the undergraduate mathematics curriculum for which this text would be appropriate, an obvious question to ask at this point is: who is the intended audience for this book? Several answers suggest themselves. Because the material in this book covers a wide range of areas and brings together a number of topics that are standard in the usual undergraduate curriculum, this book would seem tailor-made as a text for a senior seminar or capstone course. It certainly has considerable value as a text: it is clearly written, emphasizes motivation, contains lots of examples, has a good bibliography, and contains a respectable number of exercises at the end of each chapter, detailed solutions to which can be found in a lengthy solutions manual available to instructors from the AMS. (Students who do not have access to this manual must make do with a ten-page appendix giving hints and solutions to some of the problems in the text.)

As an alternative possible use of this text, faculty members interested in doing undergraduate research with students might find this book a useful source of ideas; the authors point out, for example, that both of them have supervised undergraduate research on difference sets.

In summary: reading this book taught me some nice mathematics that I didn’t know before, and it did so in an interesting, enjoyable way. I don’t doubt that a good, well-motivated undergraduate would have the same reaction. When you come right down to it, what more can you ask of a mathematics textbook?

Mark Hunacek ( teaches mathematics at Iowa State University.