Feb.3 [& 5] Important examples of designs I:
projective planes and higher-dimensional projective spaces

Usually when we introduce a new kind of mathematical structure
we give a selection of important examples, and transformations that
construct new examples from known ones.  But for t-designs,
so far we've given several necessary conditions on the parameters
but precious few examples with t>1 -- only Pi_2, and a couple of
similar designs relegated to the first problem set -- and no
transformations except for the facts that a t-design is also an
s-design for each s<t, and the dual of a square 2-design is a
square 2-design, which have yet to give us any new examples.
Today we remedy this by introducing the first of several batches of
important examples of 2-designs: algebraic projective spaces, including
notably projective planes; and square designs coming from Hadamard matrices.

While there's (still?) only one example is known of parameters for
a square 2-design that pass the BRC condition (1.21, p.7) but
do not arise for any design, there's also (still!?) no value of
\lam known to arise infinitely often -- except for \lam=1.
A square 2-design with \lam=1 (i.e. a square 2-design that's also
a Steiner 2-system) is called a (combinatorial) _projective plane_,
and its blocks are called _lines_, because (as with the prototypical
example of Pi_2) any two of its points determine a unique line,
and any two lines meet in a unique point.  In a square 2-(t,k,1) design
let k=n+1, so t=n^2+n+1, either using r(k-1)=(v-1)\lam or directly
because a point determines n+1 lines each of which contains n further
points and no two of these n(n+1) points coincide [that's actually
a special case of our argument for r(k-1)=(v-1)\lam].  We then say that
the projective plane has _order n_; e.g. Pi_2 has order 2.  (Not order
n+1 as might be expected; we already saw that n=r-\lam is an important
parameter in Fisher's inequality (where it was the coefficient of I in
M\T M = (r-\lam I) + \lam J) and in the BRC theorem, and this is
even more decisively the case for projective planes.

n=1 is possible but yields the complete 2-(3,2,1) design.  For
n=2, n=3, n=4, and n=5 we shall show that there is a unique
projective plane of order n and determine its automorphism group.
These will all be special cases of the following construction,
already shown in our first meeting for n=2 (though there we were
able to suppress a step that is necessary for n>2), and applicable
whenever n is a prime power, producing a projective plane with
more than n^8 automorphisms.  Warning: for some such n it is known
that there are non-isomorphic projective planes of order n.
(It seems that the first example is for n=9, when there are four
such planes [Lam, Kolesova, and Theil 1988, computer-assisted]; see
<http://www.uwyo.edu/moorhouse/pub/planes>.)  It is a famous open
question whether there is a finite projective plane whose order is
not a prime power; the first open case is n=12 (BRC disposes of 6
but not 10).

_Proof of uniqueness of the 2-(7,3,1) design:_ as is often the case
with highly symmetric combinatorial structures S, we can identify
any other structure S' with the same parameters with S even if we
specify some parts _p_, _p'_ of S and S' respectively and require tha
the identification take _p_ to _p'_.  Taking S'=S, this then shows that
the automorphism group Aut(S) "acts transitively on the _p_'s",
and lets us count the automorphisms.  In particular, if p pins down
S completely then the number of _p_'s equals the number of automorphisms
(which then "acts simply transitively" on the _p_'s).  If we already
have a group G acting on S, we can then check whether G=Aut(S) by
comparing cardinalities.

Here we argue as follows.  Let D be any 2-(7,3,1) design.  We'll show
D is isomorphic to Pi_2.  Fix a point P of D, an ordering (l1,l2,l3)
of the three lines through P, and one of the other lines l' of D.
This can be done in 7*3!*4 = 168 ways.  Map them arbitrarily to
corresponding elements of Pi_2.  This tells us the images of all
seven points: there's P itself; the points P1,P2,P3 where l' meets
l1,l2,l3 respectively; and the points Q1,Q2,Q3 of l1,l2,l3 which are
neither p nor on l'.  We've also found four of the lines, and readily
check that the others are {P1,Q2,Q3}, {Q1,P2,Q3}, {Q1,Q2,P3}.
This gives an isomorphism of D with Pi_2 (and a construction of Pi_2
if we don't know one already) and shows that |Aut(Pi_2)| = 168.
Moreover we already know that Pi_2 has automorphisms by GL_3(Z/2Z)
[the group of invertible 3x3 matrices mod 2 -- GL stands for
"General Linear"].  Thus these are all the automorphisms, and we're done.

On to projective planes of arbitrary prime-power order.  We define the
(algebraic) projective plane over any field k as follows.  [See pages
7-8 of the textbook. You may well have seen this already, as well as
projective spaces of other dimensions, at least over the real and
complex fields; projective spaces are ubiquitous in complex analysis,
algebraic topology, Lie groups, and of course algebraic geometry.
Before the end of the day we'll define projective space of dimension d
for all d.]

The plane is called \P^2(k) or k\P^2 (the latter notation is more
common when k is the field of real or complex numbers; please
don't use the textbook's PG(2,q)).  Fix a 3-dimensional vector space
V over k.  The "points" of \P^2(k) are the 1-dimensional subspaces of V
("lines through the origin", a.k.a. "nonzero vectors modulo scaling"),
and the "lines" are 2-dimensional subspaces of ("planes through the
origin"), each consisting of the "points" that are _its_ 1-dimensional
subspaces.  The design properties are then consequences of linear algebra
in V: any two distinct 1-dim. spaces are contained in a unique
2-dim. space (their span), and any two distinct 2-dim. spaces W,W'
intersect in a 1-dim. space because

  dim(W) + dim(W') = dim(W+W') + dim(W\cap W')

and here the LHS is 2+2=4 and the first term on the RHS is 3
(since W is distinct from W', the vector space sum W+W' is all of V).

Now suppose k is finite (see handout for basics about finite fields),
of order n=q.  Then we get a finite design, whose number v of points is
#(V-{0}) / #(1-dim. space - {0}) = (q^3-1) / (q-1) = q^2+q+1, while
Likewise k = (q^2-1)/(q-1) = q+1.  (We did this already when q=2
but didn't see the "modulo scaling" part because there q-1 was 1
so there was no nontrivial scaling!)  The fact that b=q^2+q+1=v
can then be obtained in several ways, but the nicest is to identify
\P^2(k) with its combinatorial dual via (yes!) the dual vector space.
Recall that for every finite-dimensional vector space V over a field k
we define a dual vector space

  V* = Hom(V,k),

a k-vector space of dimension equal to dim(V), and thus isomorphic
(non-canonically) with V; and that the _annihilator_ of any subspace
W of V is the subspace W\perp of V*, defined by

  W\perp = {v* in V* : v*(w) = 0 for all w in W},

with

  dim(W) + dim(W\perp) = dim(V)

(so the dimension of W\perp is the "codimension" of W and vice versa).
Duality reverses inclusions of subspaces:

  W \subset W' <==> W\perp \superset W'\perp .

Now if V is 3-dimensional then so is V*; the 1- and 2-dimensional
subspaces of V correspond respectively [sic!] to 2- and 1-dimensional
subspaces of V*, with inclusions reversed.  So the projective plane
obtained from V* is the combinatorial dual of the one obtained from V.

           V                                    V*

  points p: 1-dim. subspaces   <-->   2-dim. subspaces (lines) p\perp
   lines l: 2-dim. subspaces   <-->   1-dim. subspaces (points) l\perp
       l contains p            <==>   l\perp contained in p\perp

In particular the number of 2-dimensional subspaces of V equals the
number of 1-dimensional subspaces of V*, which is (q^3-1)/(q-1)=q^2+q+1
as already seen.

We can get higher-dimensional projective spaces P^n(k) starting from
V of dimension n+1.  (n=0 and n=1 works too, but P^0 is not very
interesting -- just a point -- and P^1 isn't big enough to make
a nontrivial design in the same way.)  An m+1 dimensional subspace
W of V yields an m-dimensional projective subspace P(W) = (W-{0})/k*
of the projective space P^n(k) = P(V).  For each m=2,3,...,n-1
the m-dimensional subspaces are the blocks of a 2-design whose
points are the points (0-dim. subspace) of V.  This design is
Steiner iff m=2 (two points determine a unique line), and square iff
m=n-1: the _hyperplanes_ are again points of a dual projective space.

           V                                    V*

  points p: 1-dim. subspaces   <-->  (n-1) dim. proj. subspaces p\perp
   lines l: 2-dim. subspaces   <-->  (n-2) dim. proj. subspaces l\per.
       ...
  hyperplanes h: (n-1)-dim. subsp. <-->    points h\perp
     P(W) contains P(W')       <==>   P(W\perp) contained in P(W'\perp)

The nice way to explain why these are all 2-designs is that all
pairs of distinct points in projective space are equivalent:
for any two pairs (p,p') and (q,q') of 1-dimensional subspaces of V,
there's an invertible linear map  T : V --> V  such that A(p)=q and
A(p')=q'.  Since the projective space is defined using just the
linear structure, T yields an automorphism of each of our designs
(that is, the design obtained for each value of m=2,3,...,n-1),
and shows that there are as many blocks containing p and p'
as there are containing q and q'.  We say that the automorphism group
acts "2-transitively" on the points; more on this later.  For any d,m
we can also construct a design with points and blocks being d- and
m-dimensional projective subspaces, but for 1<d<m<n that's only a
1-design, not a 2-design, and indeed the automorphism group is
1-transitive but not 2-transitive; e.g. you can't map lines l,l' to
lines m,m' if l and l' intersect while m and m' are skew.  [Warning:
t-transitivity of Aut(D) on points is a sufficient condition for
a design D to be a t-design, but it is not necessary, though
it might look that way from the nice examples we'll show.]

Coordinates on projective space P^n(k):  (x_0,x_1,...,x_n)
[NB we start the index at 0, so n+1 coordinates], not all zero,
but regarded as the same as (x'_0,x'_1,...,x'_n) if proportional,
i.e. if there exists c in k* such that  x'_i = c x_i  for each i
(notation: k* := {c in k: c \neq 0} = multiplicative group of k).
To emphasize that the coordinates are in effect a ratio, we use
colons rather than commas to separate them: (x_0 : x_1 : ... : x_n).
These are known as _projective_ or _homogeneous_ _coordinates_.
For example, n+1 points

  (x0_0 : x0_1 : ... : x0_n),
  (x1_0 : x1_1 : ... : x1_n),
  ...,
  (xn_0 : xn_1 : ... : xn_n)

are on a projective hyperplane (of dimension n-1) <==> the corresponding
vectors in k^(n+1) are on a vector hyperplane (of dimension n) <==>
the order-(n+1) determinant of xi_j vanishes.  NB this is well-defined:
changing any xi to ci*xi with nonzero ci multiplies the determinant by
c0 c1 c2 ... cn, but preserves the condition that it be zero.  Likewise
the coordinates of an arbitrary vector in x* in V* are (x0*,x1*,...,xn*),
acting on V via the usual inner product:

  (x0*,x1*,...,xn*) (x0,x1,...,xn) = x0* x0 + x1* x1 + ... + xn* xn

and (x0* : x1* : ... : xn*) are homogeneous coordinates on the dual
projective space, and the hyperplane x* contains the point x iff
x* x = 0 (again this makes sense even though "x* x" needn't be a
well-defined element of k).  One more example: a _hypersurface of
degree d_ in P^n is the locus of P(x0,x1,...,xn) = 0  where P is a
(usually irreducible nonzero) *homogeneous* polynomial of degree d;
this condition (though not usually the value of P) is again invariant
under scaling.  For example, a hypersurface of degree 1 is a hyperplane.

Automorphisms of P^2(k), and more generally any of the n-1
2-designs from P^n(k) (n>1): GL(V) = GL_{n+1}(k) acts, but
scalar matrices act trivially; indeed it's not hard to see that
these are the only matrices that act trivially -- that is, these
are the kernel of the map GL(V) --> Aut(D).  (Indeed it's a normal
subgroup, isomorphic with k*.)  So we have an action of GL_{n+1}(k)/k*,
known as the _projective general linear group_ PGL_{n+1}(k).  If
#k = q^f with f>1 we also get an action of the field automorphisms
(we'll later give more details about how these automorphisms interact
with PGL_{n+1}(k)).  That turns out to be the full automorphism group.
We won't prove it (except for projective planes of order 2, 3, 4, 5),
because it depends on results that the book cites (1.23 and 1.24
on page 8) but does not prove or even fully state.  Basically one
"coordinatizes" D, reconstructing the structure of k and coordinates
(x0:...:xn) from the combinatorics of D.  That could make a good
final project if you're interested.