Feb. 10 -- new designs from old:
complement; Hadamard 3-designs; derived designs

NB again we choose a different (but still logical) order of
presentation from the textbook's.


Complementary design (p.13, eqs. 1.37-1.38 and Prop. 1.39):
if \D = (X,\B) is a t-(v,k,\lam) design, let

  \B@ = { X \ B : B in \B }

be the collection of complements of blocks, and define \D@ = (X,\B@),
the _complementary design_ of \D.  (Of course \D@@ = \D: the
complement of the complement is the original design).  We claim
that this too is a t-design:

Prop. 1.39: \D@ is a t-(v,v-k,\lam@) design where

1.37  \lam@ = sum( (-1)^s Bin(t,s) \lam_s,  s = 0,1,...,t).

(Recall that \lam_s is the number of blocks containing any s points of X,
and was computed on page 3, see (1.5)).

Proof: Certainly \D@ consists of blocks of size v-k.  We must show:
for any set T of t elements of X, the number of blocks of the original
design \B that are *disjoint* from T is the same, namely \lam@.
This is done by inclusion-exclusion (see Appendix to chapter 1,
Thm. 1.56 and Cor. 1.57 on pages 24 and 25).  For any subset T' of T
let a(T') be the number of blocks B containing T'; inc-exc says that
that the number of blocks disjoint from T is the sum of (-1)^#(T') a(T')
over all 2^t subsets T'.  But a(T') is just \lam_s where where s = #(T'),
and each s occurs Bin(t,s) times, so we're done.o

e.g. if t=2 then \lam@ = \lam - 2r + b  (1.38, see Prob.2 which you
just handed in); in any case the incidence matrix of \B@ is just
M@ = J - M  where M is the incidence matrix of \B and J is the
all-1's matrix of the appropriate size.  Of course \B@ is square
iff \B is.

Are there interesting self-complementary designs?  Interesting or not,
we must have v=2k (so in particular v had better be even).
There are various boring examples, and no square examples
exept the trivial 2-(2,1,0) design (since a square design has
(v-1)\lam = k^2-k, and if v=2k then 2k-1 is a factor of k^2-k,
which doesn't happen for k>1).  But we get some self-complementary
3-designs by extending certain square 2-designs -- including indeed
our prototypical example Pi_2.

Let \E be the following design: there are 8 points, X together with
a new point called 0; the blocks each consist of 4 points, and are
line complements in \Pi_2 together with sets of the form "line u {0}".

Claim: This is 3-(8,4,1) design (a.k.a. Steiner (3,4,8) system),
and is self-complementary by construction.

Proof: Self-complementarity is clear.  For the design property:
Let T be any 3-element set of X.  If T contains 0 then any block
containing T must be "line u {0}", and conversely such a line exists
and is unique, namely the line determined by the other two elements of T.
If T does not contain 0, we use our result from the 1st problem set:
either T contains a line or is disjoint from some line, but not both.
For starters this means T cannot be contained in both a line and
a line complement.  If T is in a line then it *is* that line, so
we get our block as  T u {0},  and it is clearly unique.  Otherwise
T is contained in a line complement, which is again unique because
the union of any two lines contains 3+3-1=5 points (a simple application
of inc.-exc.), so cannot be disjoint from the 3-element set T.  QED

Alternative description: X is a 3-dimensional vector space over k=Z/2Z;
the blocks are the 14 four-element subsets that sum to zero, or
equivalently the 14 affine planes (planes translated by a vector).
Either description generalize to give a Steiner (3,4,2^d) system
for every d>2, but it's not self-complementary once d>3.

Right now we're more interested in self-complementarity than the
Steiner property, so instead we generalize as follows.  For any
d=3,4,5,... we can form a self-complementary 3-design in the same way
starting from the Hadamard design of points and hyperplanes in P^(d-1) k,
obtaining a  3-(2^d, 2^(d-1), 2^(d-2) - 1)  design whose points are the
vectors in k^d and whose blocks are the 2^(d+1)-2 affine hyperplanes.

Automorphisms include (and will turn out to equal) the _affine linear
group_ generated by GL_d(k) and translations by V, which is 3-transitive
-- more about this later.

In terms of the associated Hadamard-Sylvester matrix: if the first row
is (+1, +1, +1, ..., +1) then each of the n-1 other rows has n/2 +1's
and n/2 -1's, giving a complementary pair of blocks, for a total of
2(n-1).  We claim (p.12) that these form a  3-(n,n/2,(n/4)-1) design --
and this works for any Hadamard matrix of order n>=4.  [Naturally
such designs are called "Hadamard 3-designs".]  This is a special case
of CvL Ex.5 (= the postponed problem 7).  Another proof: choose any
three columns; we want to show that there are  (n/4) - 1   rows
other than the first where these columns give either +++ or ---.
Since the first row has +++, it is equivalent to show that there are
n/4 rows, including the first, with either +++ or ---.  Choose some
other column, and multiply each row by 1 or -1 to make that column
all +1's (this does not change our design).  We've seen already that
in each pair of columns each of ++, +-, -+, and -- arises n/4 times.
This gives 12 linear conditions on 8 counts; they're not independent
but the only freedom is to add some constant c to each count with an
even number of minus sign, and subtract c from all the other four counts,
and this does not affect the sum of +++ and --- counts, etc.


DERIVED DESIGNS

Building up a 2-design to form a 3-design is quite special.
The other direction is easier -- we already saw that a t-design
is already a (t-1)-design, and more interestingly we can reverse our
above construction as follows (Def. 1.32, p.11): if \D = (X,\B)
is a t-(v,k,\lam) design then for any point p in X we get a t-1 design
\D_p, the _derived design_ with parameters (v-1, k-1, \lam)  whose
point set is  X \ {p}  and whose blocks are  B \ {p}  for every
block B in \B that contains p.  Note that in general \D_p depends on p
(the main exception is when Aut(\D) acts transitively on X).

If a given t-design \D is derived from a (t+1)-design \E then
\E is said to be an _extension_ of \D, necessarily with parameters
(v+1,k+1,\lam).  For instance, a Hadamard 3-design is an extension of
each of the Hadamard 2-designs obtained from the same matrix.  Again,
extensibility -- going from a t-design to a (t+1)-design -- is unusual;
applying to \E the identity bk=vr of (p.4, 1.8) already imposes a
nontrivial necessary condition (Prop. 1.33, p.11): k+1 must divide b(v+1).
[NB there's a typo on p.11: the reference preceding the statement of
this proposition should refer to (1.8), not (1.7).  To prove it, note
that \E's "r" is \D's "b".]

For example: Prop. 1.34- [p.11, Hughes 1961]: if a projective plane
of order n is extendable then n is 2, 4, or 10.

[n=2 we saw already.  n=10 is impossible -- and it turns out that it is
easier, though still not trivial, to prove there's no 3-(112,12,1)
design, but we won't even do that.  n=4 is possible, but we don't
know this yet, though the Proposition is written as if we do.]

Proof: n+2 must divide (n^2+n+1)(n^2+n+2).  But then n+2 divides the
value of the RHS at n = -2, which is 3*4 = 12, and we're done since we
don't allow n=1.

This Diophantine technique will recur several times in the course.

More generally:

Thm. (Cameron 1973, 1.35 on page 11) if \D is an extendable square
2-(v,k,\lam) design then:

(a) \D is Hadamard, or
(b) v = (\lam + 2) (\lam^2 + 4\lam + 2)  and  k = \lam^2 + 3 \lam + 1,
  or
(c) (v,k,\lam) = (495,39,3).

Example: in (b), \lam=1 gives (v,k,\lam) = (21,5,1): a projective plane
of order 4.  We'll see that all such planes are isomorphic, and that
they are extensible (which follows from the uniqueness result plus the
existence of a Steiner (3,6,22) system which you've proved in the last
problem set).  The next case is impossible (Bagchi's result cited on p.13);
beyond that I don't know.

Pf.: let \E be the purported extension, and redefine v,k to be those of \E
(so we'll have to decrement by 1 at the end).  If some \E_p is square
then every \E_p is square (same parameters).  So any two blocks are
either disjoint or meet in \lam+1 points (if they both contain some p,
consider their residues in \E_p).  Conversely if \E satisfies this
condition then each \E_p is square by characterization 1.15d of
square designs (any two blocks have the same-sized intersection).
Also, since now (v-1,k-1,\lam) are the parameters of a square design
the identity (1.9) becomes

(*)  (k-1)(k-2) = (v-2)\lam.

Claim: fix a block, and consider \E^0 := (X^0, \B^0) where
X^0 = complement of B and \B^0 = blocks disjoint from B.
Then \B^0 is a 2-design.  Proof: fix p,q in X^0.  For each r
in B there are \lam blocks B' containing p,q,r, and each r appears
in \lam+1 of them.  So double-count pairs (B',r): for each of k
r's there are \lam choices of B'; for each B' there are \lam+1
choices of r, so the number of choices for B' is  k \lam / (\lam+1).
Hence the number of blocks containing p,q but disjoint from B is
constant, as claimed.  Indeed it is  \lam_2  -  k \lam / (\lam+1),
and \lam_2 = k-1  (apply (*) to the identity \lam_2 = ((v-2)/(k-2)) \lam
which holds in any 3-design); so the count is now
k-1 - k \lam/(\lam+1) = (k-\lam-1) / (\lam+1)  [I wish the book
spelled this out...].

We now apply Fisher's inequality to the 2-design \E^0, which has
parameters (v-k, k, (k-\lam-1)/(\lam+1)) and thus has

(v-k) (v-k-1) (k-\lam-1) / (k (k-1) \lam+1).

We must exclude the degenerate case v-k = k.  In this case
\D is a square design whose blocks have size (|X|-1)/2,
and is thus a Hadamard design; that's case (a).

Otherwise, some manipulation gives  k \geq (\lam+1) (\lam+2).
k = (\lam+1) (\lam+2)  gives case (b) after decrementing to
recover the parameters of \D (and then \E^0 is square too,
so we can hope to undertake further analysis; e.g. for \lam=1
that's a square (16,6,2) design).

On the other hand, consider the integrality condition on the number
b = \lam_0 of blocks of \E.  That number is v(v-1)(v-2) \lam / k(k-1)(k-2),
which (*) simplifies to v(v-1)/k.  Using (*) to express this in terms of
k and \lam rather than k and v we get

 b = ((k-1)(k-2)+\lam) ((k-1)(k-2)+2\lam) / (k\lam^2)

so k divides the numerator and thus divides 2(\lam+1)(\lam+2).
A factor of 2N that's at least as large as N is either N or 2N.
We've dealt with the former case already.  In the latter, we get
\lam^2 b = 8\lam^6 + ... + 9,  so \lam | 9, and \lam=9 yields
fractional b.  So \lam=1 or 3.  The former case gives k=12, v=112
and thus an extension of a projective plane of order 10, which was
already known to be impossible in 1973.  The latter gives k=2*4*5=40,
v=496 and thus case (c).  QED