Lecture notes for Math 155: Designs and Groups (Spring [2009-]2010)

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

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

h0.ps: 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]

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

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

h3.pdf: Handout #3, containing a sketch (to be filled-in in class) of the existence and uniqueness of the Moore graph of degree 7, a.k.a. the Hoffman-Singleton graph. Can you deduce the size of the automorphism group of this graph?

h4.pdf: Handout #4: 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 and expanded Apr.2 (n≥3 page)

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

A list of sample topics for your final projects

Informal lecture notes:
January 27: Introduction: basic definitions and questions [\D,\B are script D and B; \lam=lambda=λ; 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; dualities and polarities; alternative proof of Fisher using the “variance trick” (equivalently, the Cauchy-Schwarz inequality), which generalizes to an inequality on arbitrary 2-designs
Errors/typos in the textbook: on page 6, in the first display both instances of fancy script \B should be plain B (it's a single block, not the collection of all blocks); and on page 7, part (i) of Theorem 1.21 should have n=k-λ a square, not k.
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 \lam@ -- I don't much like this but couldn't think of anything better]
Errors/typos in the textbook: on page 11, the reference to (1.7) preceding the statement of Proposition 1.33 should be to (1.8); Proposition 1.34 should really be Hughes' 1961 result that n is in {2,4,10}, because we do not yet know that n=4 works, and will not prove that n=10 doesn't occur.
February 12: Introduction to (arcs and) ovals in square 2-designs; a bit about intersection triangles [\E is script E; == is the congruence symbol ≡; \nu is the Greek letter ν]
Yucko in the textbook: in the proof of Proposition 1.48 on page 18, please change ni to Ni to avoid the ugly nn.
February 17: Affine and inversive planes
February 19: Introduction to strongly regular graphs [\mu is the Greek letter μ]
February 22: 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; \rho is the Greek letter ρ]
February 24: Moore graphs of girth 5; the “absolute bound”, and a bit on the Krein bound
February 26 (and March 1): 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 [=~= is the congruence symbol ≅]
corrected Feb.26 after class to include the exceptional isomorphisms involving the not-quite-simple groups of order 24, 120, 336 and fix the proofs of the uniqueness of Π2 and Π3
March 1: 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 3: 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 5: More about the outer automorphism of S6, and Aut(Sn) in general
March 8: First midterm examination
March 10: The (5,6,12) Steiner system and its automorphism group M12 via Aut(S6)
Error/typo in the textbook: The intersection triangle on page 87 for this Steiner system (Table 6.1) should have 3,2,3 in the middle of the bottom row, not 2,3,2
[March 12: existence, uniqueness, and automorphism count of the Moore graph of degree 7, following the third handout above]
March 22: 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 24: Existence, uniqueness, and introduction to the automorphism groups of the 3-(22,6,1) and 4-(23,7,1) designs (a.k.a. (3,6,22) and (4,7,23) Steiner systems) via hyperovals and Baer subplanes in Π4
corrected Mar.26 after class to fix the intersection triangle
Typo in the textbook the next-to-last line of page 21 should have “in accordance with (1.52)”, not (1.42). (noted by N.Kaplan, who also lists a few apparent typos in chapters 4 and 5, which we won't cover in this class)
March 26 (and 29): 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)
March 29: Simplicity of M11 and M23, following Robin J. Chapman's “An elementary proof of the simplicity of the Mathieu groups M11 and M23 (Amer. Math. Monthly) 102 #6 (1995), 544-545. This yields simplicity of M12 and M24 (see e.g. Rotman, Lemma 9.24), and also of M22 once we show that M21 = PSL3(F4) is simple.
March 31: Simplicity of M12 and M24. To be followed by simplicity of PSL groups from the fourth handout above
April 2: see above
April 5: Introduction to subgroups of PSL2(Fq) via Galois' theorem on index-p subgroups of PSL2(Fp)
April 7: A4, S4, A5, and the other finite triangle groups via Cayley graphs
April 9: Determination of the finite fields Fq for which PSL2(Fq) contains G for each of the triangle groups G=A4, S4, A5.
April 12: 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) for p prime.
April 14: 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 16: The Hadamard matrix of order 12 and its automorphism group (which we'll identify with M12, or rather 2.M12)
April 19: The Hadamard matrix H12 and the Mathieu group M12 (and the action of PSL2(Fq) on Paley's Hadamard matrices in general)
April 21: More on M12, the (5,6,12) Steiner system, and the affine (2,3,9) and inversive (3,4,10) planes
corrected Apr.21 after class to clarify the argument for getting from O to all 9+9 translates of O and O'
April 23: A bit on the Golay [24,12,8] code; the 2576 “umbral dodecads”, and M12.2 inside M24
April 26: A bit more about the (3,4,10) design; overview of the maximal subgroups of M24
April 28: Second midterm examination


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

p2.pdf: Second problem set, mostly on square designs and intersection triangles.
Problems 6 and 7 postponed till next week.
Problem 1 corrected [L.Mocz]: the first display should sum i3ni, not ni3, and likewise for the three sums over i in the ensuing text.

p3.pdf: Third problem set: more about the special designs recently introduced, and a bit of inclusion-exclusion
Problems 4 and 5 corrected [Z.Abel and C.Anderson]: for the last part of Problem 4, the field F must be perfect (which is automatic for a finite field but not in general, see the new footnote); for Problem 5, the condition “r == ±1 mod d” should be “d == ±1 mod n” (for starters there's no r in this problem).
As was the case last week, and if it ever happens again, any problems affected by an error that requires correction can be handed in without penalty at the class meeting after the original due date if the error was not announced by the previous meeting (so in this case problems 4 and 5 are due Feb.19 instead of Feb.17).

p4.pdf: Fourth problem set: spherical 3-designs; regular graphs, cont'd
Corrected: of course it's February 2010, not 2009...

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

p7.pdf: The Tutte 8-cage; transvections; the 4-dimensional representation of A7 mod 2
Problem 3 corrected [C.Anderson]: in part (i), the condition n≥3 should have been (and is now) n>3. [Also note that for our purposes an involution is a group element of order exactly 2, so the identity is not allowed; some would call this a “nontrivial involution” or more explicitly a “non-identity involution”.]

p8.pdf: A7 in GL4(F2) cont'd; finite subgroups of PSL2(F) and related matters