Lecture notes for Math 155: Designs and Groups (Spring [2015-]2016)

If you find a mistake, omission, etc., please let me know by e-mail.

Apropos of mistakes etc., here’s a short list of corrections to the textbook from previous editions of Math 155r.

Also, the existence of nontrivial Steiner systems with t ≥ 6, described on the bottom of page 2 as “possibly the most important open problem in design theory”, was finally solved two years ago by Peter Keevash.

The orange balls mark our current location in the course, and the current problem set.

h0.pdf: introductory handout, showing different views of the projective plane of order 2 (a.k.a. Fano plane) and Petersen Graph [see also the background pattern for this page].
Section: Mondays 1-2 PM in Science Center 111
CA office hours: Mondays Wednesdays 8-9 in Pforzheimer Dining Hall,
except that the Apr. 27 Office Hour is moved to Apr. 26 to precede the second midterm
First Lowell House Office Hours: Tuesday Feb.9, 8:00-9:30 in the Dining Hall;
Second Lowell House Office Hours: Tuesday Feb.23, 8:00-9:30 in the Dining Hall;
Third Lowell House Office Hours: Thursday March 3, 8:00-9:30 in the Dining Hall;
Fourth Lowell House Office Hours: Thursday April 14, 8:30-10:30 in the Dining Hall
Fifth Lowell House Office Hours: Monday April 25, 7:25-8:55 in the Dining Hall

faculty legislation requires all instructors to include a statement outlining their policies regarding collaboration on their syllabi” — as stated in h1.pdf: for homework, “As usual in our department, you are allowed — indeed encouraged — to collaborate on solving homework problems, but must write up your own solutions.” For the final project or presentation, work on your own even if another student has chosen the same topic. (As with theses etc. it is still OK to ask peers to read drafts of your paper, or see dry runs of your presentation, and make comments.) In all cases, acknowledge sources as usual, including peers in your homework group.

h1.pdf: Ceci n’est pas un Math 155 syllabus.

h2.pdf: Handout #2, containing some basic definitions and facts about finite fields.

The first midterm examination will be Monday, March 7 in class. It will cover only material in problem sets 1-4 (so that you can study your graded solution sets while preparing for it).

h3.pdf: Handout #3: outline of a proof of the simplicity of PSL2(F) (F a finite field of at least 4 elements) and PSLn(F) for n≥3 and any finite field F
corrected April 6: the PSL2(F) conjugates of x↦x+c include x↦x+a2c, not “are” x↦x+a2c

h4.pdf: Handout #4: The exceptional isomorphism PSL2(F7)=GL3(F2) via the automorphism group of the 3-(8,4,1) Steiner system

Here are Andries E. Brouwer’s tables of strongly regular graphs. For instance, the first table shows all parameters for v≤50 allowed by the integrality condition. Green means the graph exists, in which case the first column has "!" if it is unique up to automorphisms, and "n!" with some n>1 if the number of isomorphism classes is known to be exactly n (see the comments column: if there are no comments, look at the entry above for the complementary-graph parameters). Red means there is no such graph (and the comments indicate why not). Yellow means that existence is an open question; there is no such case for v≤50, but the next page (for 50<v≤100) already shows a few examples.

a reference for practically all the group theory we shall need, and much more, is Joseph J. Rotman’s An Introduction to the Theory of Groups (Springer 1995), which you can view, and download (for personal use only), from hollis.harvard.edu on a Harvard computer.

The second midterm examination will be Wednesday, April 27 in class. It will concentrate on material from problem sets 5-8, but 1-4 are also fair game.

The final project is due Thursday, May 5 at 11PM. Unlike the problem sets, this is not collaborative: you must work on your own, even if a classmate is writing on the same topic. (You may ask friends to read drafts, but you probably prefer to ask this of me…) Unlike the midterms, here you may (and should!) use references — as usual cite them properly, and use your own words in your written project. Here is the list of sample topics that I described in class April 8.

Our April 29 meeting will be in Room 310, to accommodate the meeting of the Friends of Harvard Mathematics which will take place in 507 for much of the day. (Yes, that is during Reading Period but I expect I'll want to make up at least one class.)

Informal lecture notes:

January 27: Introduction: basic definitions and questions [\D,\B are script D and B; Bin(n,k) = binomial coefficient n!/(k!(n-k!))]
January 29: Duality and the incidence matrix of a design; Fisher's theorem [\T = transpose]
February 1: Square designs continued: theorem of Bruck-Ryser and Chowla; alternative proof of Fisher using the “variance trick” (equivalently, the Cauchy-Schwarz[-Buniakowsky] inequality), which generalizes to an inequality on arbitrary 2-designs; dualities and polarities
February 3 and 5: Important examples of designs, I: projective planes, and higher-dimensional projective spaces; uniqueness and automorphisms of Π2
February 5 and 8: Important examples of designs, II: “Hadamard 2-designs” (square 2-(4m−1,2m−1,m−1) designs associated with Hadamard matrices of order 4m); Sylvester's and Paley's constructions
February 10: New designs from old: complement, Hadamard 3-designs, derived designs [@ is an \overline (a.k.a. vinculum) for design complements, so \D@ is the design complementary to \D, and likewise \B@ and λ@ -- I don't much like this but couldn't think of anything better]
Here’s my mathoverflow writeup of (a generalization of) the technique we introduced today for solving Diophantine equations of the form B(n)/A(n) Z, incluing the example of the 2-3-7-57 result for Moore graphs.
February 12: Introduction to (arcs and) ovals in square 2-designs; a bit about intersection triangles [\E is script E]
February 15: No class, Presidents Day
February 17: Affine and inversive planes
February 19: No class, I was speaking at SUnMaRC
February 22: Introduction to strongly regular graphs
February 24: The adjacency matrix of a graph (not necessarily regular), and the integrality condition on the parameters of a strongly regular graph [\j is a boldface j, denoting an all-1’s vector]
February 26: Moore graphs of girth 5; the “absolute bound”, and a bit on the Krein bound
February 29: Overview of the second part of the course, where groups will play a more central role; introduction of some of our techniques via uniqueness and automorphism group of Π2 (again) and Π3
["ATLAS" = Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups by John Conway et al.]
March 2: Preliminaries for the uniqueness and automorphism group of Π4: n-arc counts; simply transitive action of PGLn(k) on ordered (n+1)-tuples of points in general linear position in Pn−1(k); hyperovals in a projective plane of order 4 and their duals
March 4: Uniqueness and number of automorphisms of Π4; outer automorphism of S6 via permutations of a hyperoval O lifted to Aut(Π4) and acting on the dual hyperoval O*
March 7: First midterm examination
March 9: More about the outer automorphism of S6, and Aut(Sn) in general
March 21: The (5,6,12) Steiner system and its automorphism group M12 via Aut(S6)
March 23: The simplicity of the alternating group An (n≥5), introduced via the determinant partition of the 168 hyperovals in Π4 into three classes of 56 each
March 25: Interlude: recognizing Sn and An from their index-n subgroups Sn−1 and An−1. Then, back to the Lüneburg construction: The 4-(23,7,1) Steiner system D23 via hyperovals and Baer subplanes
March 28 and 30 (and 32): Existence, uniqueness, and introduction to the automorphism group M24 of the 5-(24,8,1) design (a.k.a. (5,8,24) Steiner systems); the relations among (P)SL3(F4), (P)GL3(F4), (P)ΣL3(F4), and (P)ΓL3(F4)
April 1: finish M24 notes; background for Robin Chapman’s note “An Elementary Proof of the Simplicity of the Mathieu Groups M11 and M23”: the notation H≤G for “H is a (not necessarily normal) subgroup of G”; theorems of Lagrange (1771: H ≤ G ⇒ #H | #G), Cauchy (1845: prime p | #G ⇒ G contains at least one cyclic subgroup of order p, indeed Np+1 of them for some integer N), and Sylow (1872); explanation of the start of the proof: “non-trivial” = “other than {e}” (because the conclusion is H=G), and “It is easy to see” because the image under g of the orbit Hx is the orbit H(gx) [any g in G, using gH=Hg which is a consequence of normality of H in G]. Also, the reference to Rotman 9.22 should go to 9.24 in the edition we’re using (to be covered Monday).
April 4: Simplicity of M12 and M24. To be followed by simplicity of PSL groups from the third handout above
April 6: See above. For (0), the row and column operations of basic linear algebra mean (after a bit of accounting for the determinant) that SLn(F) is generated by coordinate transvections together with diagonal matrices and the signed permutation matrices that correspond to simple transpositions. To reduce the latter two to coordinate transvections, compute

[1 a] [1 0] [1 c]     [ab+1 abc+a+c]
[   ] [   ] [   ]  =  [            ]
[0 1] [b 1] [0 1]     [ b     bc+1 ]

and choose a,b,c to make ab+1 or abc+a+c zero. In part (1), consider the conjugate of x↦x+c by x↦a²x (which corresponds to diag(a,1/a)).
April 8: Description of some possible topics for the final project
April 11: Introduction to subgroups of PSL2(Fq) via Galois’ theorem on index-p subgroups of PSL2(Fp);
isomorphism between the groups PSL2(F7) and GL3(F2) via the 3-(8,4,1) design, following the fourth handout above
April 13: A4, S4, A5, and the other finite triangle groups via Cayley graphs
April 15: Determination of the finite fields Fq for which PSL2(Fq) contains G for each of the triangle groups G=A4, S4, A5.
April 18: Outline of the proof of Dickson’s list of finite subgroups of (P)SL2(K) for any field K. We follow Suzuki’s exposition, concentrating on the subgroups whose order is not a multiple of the characteristic, which is what we need for Galois’ theorem on the smallest permutation representation of PSL2(Fp) [Context: a fundamental tool for studying finite groups G is their linear representations G → GLn(F), and Dickson’s theorem is the first of many results that describe groups with linear representations of small dimension.]
April 20: S4 and A5 twins in PSL2(F); the twin A5’s in PSL2(F11) and the identification of PSL2(F11) with the automorphism group of the Paley biplane
April 22: The Hadamard matrix of order 12 and its automorphism group (which we’ll identify with M12, or rather 2.M12); also (not in the notes), a blurb for Conway’s “M13 and “2.M13, see this article (where the part that isn’t Conway’s stems from Jeremy Martin’s senior thesis here)
April 25: The Hadamard matrix H12 and the Mathieu group M12 (and the action of PSL2(Fq))
April 27: Second midterm examination
April 29: Makeup lecture, roughly corresponding to part of these notes, with 1) more on M12, the (5,6,12) Steiner system, and the affine (2,3,9) and inversive (3,4,10) planes; and 2) a bit on the binary Golay [24,12,8] code (there's also a ternary Golay [12,6,6] code constructible from H12), the 2576 “umbral dodecads”, and M12.2 inside M24

### *****************************************************************

p1.pdf: First problem set, exploring the Fano plane (and generalizations) and Petersen graph from the introductory handout.

The use of English words to encode combinatorial structure, as in {BUD, BYE, DOE, DRY, ORB, RUE, YOU} ≅ Π2, is one of many bits of mathematics (and wordplay) that I was introduced to by the writings of the late great Martin Gardner. In page 208 of Mathematical Carnival (New York: Knopf, 1975) he introduces the following game: Each of the following words is printed on a card: HOT, HEAR, TIED, FORM, WASP, BRIM, TANK, SHIP, WOES. The nine cards are placed face up on the table. Players take turns removing a card. The first to hold three cards that bear the same letter is the winner. (The Canadian mathematician Leo Moser , who devised this game, called it “Hot.”) What familiar combinatorial structure does this set of words encode? Hint: “Hot” is the last of three games described on this page; the first is: Nine playing cards, with values from ace to nine, are face up on the table. Players take turns picking a card. The first to obtain three cards that add to 15 is the winner. (The endnotes for this chapter “16. Jam, Hot, and other games” cite Leo Moser, “The Game is Hot.” Recreational Mathematics Magazine, Vol.1, June, 1961, pages 23–24.) Another variation, using the words BET, BUG, CLOG, EACH, FRAUD, GEM, LAMB, MUTT, STILL, is here.

p2.pdf: Second problem set, mostly on square designs and intersection triangles.

p3.pdf: Third problem set: more about the special designs recently introduced, and a bit of inclusion-exclusion

p4.pdf: Fourth problem set: Strongly regular graphs I
[the TeX macro I used to center the bar of G more-or-less correctly is  \def\Gbar{\,\overline{\!G}} .]

p5.pdf: Uniqueness of Π5 via ovals, synthemes, and totals [“syntheme” = one of the 15 partitions of a six-element set into three pairs; “total” = one of the 6 collections of synthemes that cover each of 15 pairs once; the text calls these “1-factors” and “1-factorizations” respectively (page 81).]

p6.pdf: Some finite group theory
For problem 3, you may assume that PSL2(Fq) is simple for q>3, and thus that PGL2(Fq) has no normal subgroups other than itself, {1}, and (when q is odd) PSL2(Fq). We shall prove these results soon (they are also in Rotman).

p8.pdf (final problem set):
More on Π2 structures and the identification of A8 with GL4(F2);
Finite subgroups of PSL2(F) and related matters