\documentstyle[12pt]{article}
%\setlength{\topmargin}{.2in}
%\setlength{\textwidth}{6.2in}
%\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.6in}
\setlength{\evensidemargin}{0.6in}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2(1995),
\#R9\hfill}
\thispagestyle{empty}
\newtheorem{remark}{Remark}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{result}[theorem]{Result}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{question}{Question}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
%\makeindex
%\makeglossary
%HYPHENATION
\hyphenation{col-linea-tion}
\hyphenation{Wed-der-burn}
\hyphenation{Kro-neck-er}
\hyphenation{des-argues-ian}
\hyphenation{Ha-da-mard}
\hyphenation{Shri-khan-de}
\hyphenation{Buek-en-hout}
\hyphenation{De-landt-sheer}
\hyphenation{Kleid-man}
\hyphenation{An-dria-mana-li-man-ana}
\hyphenation{Syl-vest-er}
%NEWCOMMANDS
\newcommand{\jmod}[2]{\mbox{ $\equiv #1$}\mbox{ \rm (mod $#2$)}}
%HOW TO USE: for ``5 equiv 2 (mod 7)'' type $5 \jmod{2}{7}$
\newcommand{\njmod}[2]{\mbox{ $\not \equiv #1$}\mbox{ \rm (mod $#2$)}}
%for 5 NOT equiv 0 mod p use \njmod
\newcommand{\done}{\mbox{\large {\boldmath $\Box$}}}
\newcommand{\nonres}{\mbox{$\not \! \! \raisebox{-.2ex}{\mbox{$\Box$}}$}}
\newcommand{\res}{\raisebox{-.2ex}{\mbox{$\Box$}}}
\newcommand{\jvec}{\mbox{\boldmath $\jmath$}}
\newcommand{\square}{\mbox{\Large ${\bf \Box}$}}
\newcommand{\pf}{\noindent{\bf Proof:}}
\newcommand{\eg}{\noindent{\bf Example:}}
\newcommand{\egs}{\noindent{\bf Examples:}}
\newcommand{\rk}{\noindent{\bf Remark:}}
\newcommand{\rks}{\noindent{\bf Remarks:}}
\newcommand{\note}{\noindent{\bf Note:}}
\newcommand{\F}{\mbox{$\bf F$}}
\newcommand{\CA}{\mbox{$\cal A$}}
\newcommand{\bmi}[1]{\mbox{\boldmath $ #1$}}
%How to use \bmi: to get bold math ital R, type \bmi{R} in
%any mode...math or not.
\date{}
\begin{document}
\title{On 2-ranks of Steiner triple systems}
\author{E. F. Assmus, Jr.\thanks{The author wishes especially
to thank {\sc Paul Camion} and
{\sc Pascale Charpin}. The research
atmosphere that they have created at {\em Projet Codes, INRIA\/}
surely contributed to this investigation, which took place during
the early months of 1995 while the author was a visitor.
}}
% {Mathematics Department, Lehigh University,
% 14 E.~Packer Avenue, Bethlehem PA 18015-3174 USA}}
\maketitle
\begin{center}Submitted: March 13, 1995; Accepted: April 17, 1995\\
\bigskip
{\bf Abstract}
\end{center}
{Our main result is an existence and uniqueness theorem for
Steiner triple systems which associates to every such system
a binary code --- called the ``carrier'' --- which depends {\em
only\/} on the order of the system and
its 2-rank. When the Steiner triple
system is of 2-rank less than the
number of points of the system, the carrier organizes all the
information necessary to construct
directly {\em all systems of the given order and
$2$-rank\/} from Steiner triple systems of
a specified smaller order.
The carriers are an easily understood, two-parameter
family of binary codes related to the Hamming
codes. % This part of the paper can be viewed as a
%constructive elaboration of a program begun by Teirlinck and
%brought to what was then seen as a definitive end by Doyen,
%Hubaut and Vandensavel almost twenty years ago.
We also discuss Steiner quadruple systems and prove an analogous
existence and uniqueness theorem; in this case the binary code
(corresponding to the carrier in the triple
system case) is the dual of the code obtained
from a first-order Reed-Muller code by repeating it a certain
specified number of times.
Some particularly intriguing possible enumerations and some
general open problems are discussed. We also present
applications of this coding-theoretic
classification to the theory of triple and quadruple
systems giving, for example, a direct proof of the fact that
all triple systems are derived provided those of full 2-rank
are and showing that whenever there are resolvable quadruple
systems on $u$ and on $v$ points there is a resolvable
quadruple system on $uv$ points.
The methods used in both the classification and the
applications make it
abundantly clear why the number of triple and quadruple
systems grows in such a staggering way and why a triple
system that extends to a quadruple system has, generally,
many such extensions.\footnote{AMS
Primary Classification: 05B07; Secondary Classification: 94B25.}
}
\section{Introduction}
The work we report on here began as
an effort to understand the surprising
facts uncovered by a comprehensive computer study of the
80 Steiner triple systems of order 6 (on 15 points)
undertaken by Tonchev and Weishaar \cite{tonweis}. Among the
results we establish, perhaps the easiest to state and prove is
the following:
\smallskip
{\em A Steiner triple system on $n$ points
has $2$-rank $n-1$ if and only if its
binary code is the direct sum of an even
code
and
a full
code $\bmi{F}_{\!\!2}^{r}$. Moreover we have $n=2r+1$
with the support of the full code
the support of the unique
maximal subsystem on $r$ points --- the support of
the even code being the corresponding
complementary oval.\/}
\smallskip
This result explains
why only one binary code arose from the sixteen
Steiner triple systems of 2-rank 14 and order 6
and immediately gives the code's
weight enumerator.
\smallskip
But the result cited above was a relatively minor consequence
of this investigation since it quickly evolved into a full-fledged
investigation of Steiner triple systems of deficient 2-rank --- that
is, 2-rank less than the number of points of the system. In fact
the work can be taken as a {\em binary view\/} of the whole range of
Steiner triple systems: we show in principle how to construct
recursively
all Steiner triple systems of deficient 2-rank
using the degenerate system on one point and those systems of
full 2-rank as a starting point.
Thus the systems of full 2-rank are seen
as the building blocks\,\footnote{This
will undoubtedly strike some readers as
going a bit far in deciding what the building blocks
should be and, indeed, the vast majority of Steiner triple systems
have full 2-rank.} since, from the binary point
of view, Steiner triple systems of
full 2-rank must be viewed as unintelligible and hence taken
as given facts of life.
The mandarins in the binary world
peopled by Steiner triple systems are
the systems given by the points and lines of a projective
geometry over the field $\bmi{F}_{\!\!2}$ and the binary codes involved are
the Hamming codes. Here the 2-rank is as deficient as it can
possibly be: the 2-rank of the design of points and lines of
PG$_{k-1}(\bmi{F}_{\!\!2})$ is $2^k -1 - k$, or better, $n-k$, where
$n=2^k -1$ is the number of points of this classical system. Our basic
existence and uniqueness theorem for Steiner triple systems of
deficient 2-rank is the following:
\smallskip
{\em For any
admissible\,\footnote{That is, $n\jmod{3,7}{12}.$ Note that
necessarily $k\geq 2$.}
$n>7$, writing $n+1=u\times 2^k$ with $u$ odd, and
choosing
an $i$ with $1\leq i 7$ and we construct many such systems
via Theorem~\ref{thm-SQS}. We
have honored the classical systems by leaving them unmentioned
for those $n$ of the form $2^k -1$.
In particular, then, we show that the binary code of a Steiner
triple system is completely determined by its 2-rank; this explains
why Tonchev and Weishaar found only five codes (one for each
dimension between 11 and 15) among the 80 Steiner triple systems
on 15 points.\footnote{The computer study done by Tonchev and
Weishaar also looked at the binary codes given by the
{\em column spaces\/} of the incidence matrices; these
so-called {\em point codes\/} are
a complete invariant for the 80 triple systems. Thus the
80 incidence matrices of the Steiner triple systems of order
6 have the remarkable property that their binary row spaces
produce only five essentially distinct codes of block
length 15 while their
binary column spaces produce 80 essentially distinct codes
of block length 35. This phenomenon may very well be
characteristic of Steiner triple systems in general.
For a brief
discussion of the matter see \cite[Section~7]{ak:update}.}
Some may wish to see this effort
as a ``constructive'' redoing of a
program begun by Luc Teirlinck % \cite{teir1}
and brought to what
seemed then to be a definitive end by Doyen, Hubaut and
Vandensavel when they proved their marvelous theorem describing the
modular ranks of Steiner triple systems. % \cite{doyen}.
We
will not, however, use their results here; the reader
need only know the basic facts about codes and designs\footnote{Easily
gleaned from Chapters 1 and 2 of \cite{ak:book} or, indeed,
from almost any book discussing designs and codes.} to
understand the material to follow.
Others may wish to see it as an elaboration of an ancient
``doubling'' construction frequently attributed to Reiss, who in
the Spring of 1856 gave a
proof of the fact that Steiner triple systems exist for all
$n\jmod{1,3}{6}$. Again, the reader need not be familiar
with the constructions necessary to give such a proof.
So, we will be concerned throughout with Steiner triple systems
of 2-rank that is {\em not\/} maximal. It is surely true
that such systems are rare and that most Steiner
triple systems on
$n\jmod{3,7}{12}$ points have full 2-rank. In order for the rank to
drop not only must the point set be of cardinality
congruent to 3 modulo 4, as we have insisted
in the existence and uniqueness result above,
but the system must necessarily have
subsystems of maximal size. But,
the smaller the 2-rank the closer the system is to the
classical system of points and lines of a projective geometry
over the two-element field and it makes
sense to say something about such systems.
We will
associate to each such system a binary code which we will
call the {\em carrier\/}. We will determine all possible carriers
and show how to construct all systems of deficient
2-rank from the carriers and systems
of smaller order. The carriers turn out to be
a two-parameter family of easily understood
binary codes with enormous automorphism groups, and these
codes visibly
exhibit the structure of the binary projective space attached
to each Steiner triple system of deficient 2-rank. Moreover,
the carrier organizes the data necessary to construct the Steiner
triple systems of which it is the carrier and makes it clear
why the number of such systems grows in such a staggering
way with $n$.
One should expect a classification such as the one just described to
reduce a question about Steiner triple systems to the same
question about those of full 2-rank. As an illustration of
just that we give a direct proof of a result (Theorem~\ref{thm-ext})
closely related to a result of Mendelsohn\footnote{Mendelsohn's
result (see \cite{men}) is couched in the language of {\em sloops\/}
and {\em squiens\/}; it very well may be equivalent to our
result.}
that immediately gives the following:
\smallskip
{\em If Steiner triple systems of full $2$-rank are derived
then all Steiner triple systems
are derived.\footnote{A Steiner triple system is derived if
it extends to a Steiner quadruple system.}}
\smallskip
To be fair this leaves a lot unproved, but it is not entirely
out of the question that one could show that those with full
2-rank are derived. Moreover, the results we describe in
Section~\ref{sec-App} also show how to construct all Steiner
quadruple systems of deficient 2-rank, an easier
task, and Theorem~\ref{thm-SQS} yields
many derived Steiner triple systems of full 2-rank.
The reader looking for the flavor of the subject may
want to read only Section~\ref{S1} and Section~\ref{sec-Con}.
The main technical development comes in Section~\ref{3}. The
construction of all triple systems of deficient 2-rank is
treated in Section~\ref{sec-carcon} and
Section~\ref{C1} discusses some particularly easy cases
of the construction.
Section~\ref{sec-App} includes an application
to the question of which triple systems are derived and initiates
a discussion of
Steiner quadruple systems. We complete that discussion
in Section~\ref{sec-SQS}
by stating and proving our
existence and uniqueness theorem for quadruple
systems of deficient
2-rank, Theorem~\ref{SQSex}, and giving an application to
resolvable Steiner quadruple systems. Section~\ref{sec-Con} mentions
the ``ternary'' view of Steiner triple systems and makes some concluding
remarks.
\section{Steiner triple systems of deficient 2-rank}\label{S1}
Suppose we are given a Steiner triple system on a set $S$ of
cardinality $n$ whose binary code $D$ is a
proper subspace of $\bmi{F}_{\!\!2}^n$. This implies
that $n$ is congruent to 3 modulo 4 since the order,
$\frac{n-3}{2}$, of the system must be even. If $r$ is the number
of weight-one vectors in $D$ then, of course, $r3$.}
$1$-$(2l,2,r)$ design.
In particular $C$ has $rl$ vectors of
weight $2$.
\end{proposition}
\pf\ Clearly the weight-two vectors of $C$ coming from the
triples of the system meeting the trivializing subsystem in
exactly one point yield a resolvable 1-design with parameters
1-$(2l,2,r)$.
We need only show that there are no
further weight-two vectors in $C$. So suppose $v$ were another
weight-two vector in $C$. Then there would be a triple of the
system whose support covered the support of $v$ and was disjoint from the
trivializing subsystem. Thus the sum of $v$ and the incidence
vector of the triple would yield a weight-one vector in $C$,
a contradiction.\done
\smallskip
Thus, knowing only the carrier allows one to know the order of
the triple system from which it came: since $r$ is intrinsic
to the carrier, we know from the carrier alone
that the system must have
$2l+r$ points and be of order $l +\frac{r-3}{2}$. For any
binary code $C$ --- of even block length
$2l$ and of minimum weight 2 --- if the weight-two vectors
yield a resolvable $1$-$(2l,2,r)$ design, we shall call $r$ the
{\bf index} of $C$. Thus a binary code of
index $r$ and block length $2l$ will have precisely
$rl$ vectors of weight two and the index $r$ of such a code
will clearly
satisfy
$1\leq r \leq 2l-1$. Note that when $r=2l-1$
we are in the codimension 1 case already treated.
For such a $C$ to be the carrier
of the binary code of a Steiner triple system we must,
in addition, have
$r$ congruent to 1 or 3 modulo 6. But the condition on the
weight-two vectors of $C$ is, alone, very strong as the next
proposition will show.
\begin{proposition}\label{propE}
Let $C$ be a binary code of minimum-weight $2$ and block
length $v$. Assume that
the weight-two vectors of $C$ form a %resolvable
$1$-$(v,2,r)$
design. Then, %$r$ is odd,
% and
$r+1$ divides $v$ and the weight-two vectors
of $C$ generate a subcode isomorphic to the direct sum of
$\frac{v}{r+1}$ copies of
the even-weight subcode of $\bmi{F}_{\!\!2}^{r+1}$. If the
$1$-design is resolvable, then $r$ must be odd and any
resolution of the $1$-$(v,2,r)$ design is built from
$\frac{v}{r+1}$ independently chosen resolutions of the
design of weight-two vectors of $\bmi{F}_{\!\!2}^{r+1}$.
\end{proposition}
\pf\ Since the
weight-two vectors of
$C$ form a
1-$(v,2,r)$ design,
given any coordinate \bmi{e} of $C$ there are precisely $r$ weight-two
vectors of $C$ with a 1 at this coordinate.
These $r$ vectors generate an
$r$-dimensional even subcode $E$ of $C$ whose
support is the $r+1$ coordinates
supporting the given $r$ vectors. Thus $E$ is isomorphic
to the full even-weight subcode of $\bmi{F}_{\!\!2}^{r+1}$.
It is easy to see that
this process partitions the
set of coordinates of the code $C$ into subsets of
cardinality $r+1$ and gives all but the last
assertion of the Proposition. So suppose $r$ were even. Let
$\cal P$ be a parallel class of some resolution of the design.
Then $\cal P$ would have at least one of its 2-subsets supporting
a vector with a 1 in the support of $E$ and a 1 outside the support
of $E$. But then we could produce a weight-two vector with a 1
at \bmi{e} and a 1 outside the support of $E$, an impossibility.
It follows not only that $r$ is odd, but also that any
resolution of the design yields a resolution of the weight-two
vectors of $E$. Clearly, any independently chosen resolutions
of the supports of the weight-two vectors of the
various even subcodes can be stitched together
to give a resolution of the 1-design.\done
\smallskip
In particular, we have determined the binary code generated
by the weight-two vectors of
a carrier of index $r$. Moreover, all resolutions of the
design given by the weight-two vectors of the carrier are
obtained by piecing together, however one wishes,
$\frac{2l}{r+1}$ arbitrarily chosen resolutions of the
2-subsets of an
$(r+1)$-set. As the reader might imagine the number of such
choices grows in a staggering way. Even when $2l=r+1$ and
we are in the codimension 1 case already treated,
the number of ways to choose just {\em one\/} resolution
of the design of
2-subsets of
a $2l$-set grows very quickly with $l$ (see \cite{DGM,menrosa}).
\medskip
\rk\
If the trivializing subsystem of a Steiner triple system on
$n$ points has $r$ points, then, by the
above Proposition,
$r+1$ divides $n+1$. In fact, we will show that the
quotient is a power of 2, a crucial result.
\medskip
Suppose $C$, of block length $2l$ and index $r$, is the carrier
of a Steiner triple system. Then the
trivializing subsystem and the weight-two vectors of $C$
account for $rl+\frac{r(r-1)}{6}=r\frac{r+6l-1}{6}$ triples
of the triple system. All other triples, in number
\[
\frac{l}{3}(2l-r-1),
\] must have their incidence
vectors in the carrier's support and hence yield weight-three
vectors of the carrier (unless, of course, $n=2r+1$ and hence
$2l=r+1$ with $C$ the full even-weight
subcode
of $\bmi{F}_{\!\!2}^{2l}$). Moreover, any weight-two vector in the carrier's
ambient space which is {\em not\/}
in the carrier has its support contained in the support of a
unique triple disjoint from the trivializing subsystem. Such a
triple yields a weight-three vector of $C$ and, in fact,
other weight-three vectors in $C$ which are not incidence vectors
of the Steiner triple system at hand since any weight-two vector
in $C$ whose support meets the support of the triple non-trivially
(in, therefore, precisely one point) gives another weight-three
vector in $C$ whose support is not a triple of the Steiner
triple system. We have thus proved the following
\begin{proposition}\label{1}
Let $C$ be the carrier of a Steiner triple system on $n$
points whose trivializing
subsystem is a proper subsystem with $r$ points. Then setting
$n-r=2l$ there are, among the weight-three vectors of $C$,
\[
\frac{l}{3}(2l-r-1)
\]
vectors with the property that no two of these vectors have
supports meeting in more than one point.
\end{proposition}
We remark that the proposition is operative only when $2l>r+1$.
\medskip
\noindent{\bf Examples:}
{\bf 1)} Observe that for $l=1$ (and hence $r=1$) the $[2,1]$
binary code $C$ of minimum weight 2 is
unique and looks like a carrier, but is
not since the unique Steiner triple system on 3 points has
2-rank one and not two. Nevertheless we will denote this simple
code by $\bmi{C}_{1,1}$ below.
{\bf 2)} A slightly more interesting example occurs when $l=2$. Here there is
a unique resolution of the set of 2-subsets of a 4-set and
the binary even-weight subcode $C$ of $\bmi{F}_{\!\!2}^4$ is
a putative carrier of index 3. One can indeed (as we shall
see below in a more general context, Theorem~\ref{thm-con})
construct the unique
Steiner triple system on 7 points from the data but $C$ will
not be the carrier. This code is denoted by
$\bmi{C}_{3,1}$ below.
Our final example of this section is more pungent; although it
too is not
a carrier, it will be a maquette for the carriers we
will eventually characterize.
{\bf 3)}
Consider the binary $[6,4]$ code
$C=\bmi{C}_{1,2}$ with generator matrix
\[
\left(
\begin{array}{cccccc}
1&1&0&0&0&0\\
0&0&1&1&0&0\\
0&0&0&0&1&1\\
1&0&1&0&1&0
\end{array}
\right)
\]
corresponding to the case $l=3$ and $r=1$.
Its weight enumerator is, visibly,
\[
X^0+3X^2+8X^3+3X^4+X^6
\]
and its weight-two vectors yield a resolvable 1-$(6,2,1)$
design; thus $C$ has index 1. But, again, it is not the carrier of
a Steiner triple system since that system would have to be
the Fano plane, which has 2-rank four and not five.
One {\em can\/} construct the Fano plane from the code
$C$ simply by choosing any four
($4=\frac{l}{3}(2l-r-1)$) of the eight weight-three vectors
satisfying the criterion of the Proposition. That
choice is essentially unique, as the reader can easily
verify. For example, a normalized choice is the following:
\[
\begin{array}{cccccc}
1&0&1&0&1&0\\
1&0&0&1&0&1\\
0&1&1&0&0&1\\
0&1&0&1&1&0
\end{array}
\]
and the gross number of choices is two.
The automorphism group of $C$ is clearly the semi-direct
product of Sym(3) acting in the obvious way on the elementary
abelian group of order 8 (viewed as the direct product of
three copies of the cyclic group of order 2). As we shall
later see, we should think of the cyclic group as Sym(2) and
the Sym(3) here should be thought of as the group of the
projective line over $\bmi{F}_{\!\!2}$, that is as $PGL_2(\bmi{F}_{\!\!2})$.
For $l=3$ no other
value for the index
is possible since
any resolvable 1-$(6,2,r)$ design with $r>1$ generates
the full even-weight subcode of
$\bmi{F}_{\!\!2}^6$ and 5 is not congruent to 1 or 3 modulo 6.)
\medskip
We now use Proposition~\ref{propE} and the condition of Proposition~\ref{1}
to completely describe all possible carriers.
\begin{theorem}\label{main}
Suppose $C$ is the carrier of a Steiner triple system. Then
$C$ is a code of block length $2l$, minimum weight $2$, and
index $r$ for some $r\jmod{1,3}{6}$. Moreover,
\[
\frac{2l}{r+1}=2^m-1
\]
for some positive integer $m$, $C$ is uniquely determined
by $r$ and $m$, and a Steiner system
with $C$ as its carrier must have $\frac{n+1}{r+1}=2^m$
and its $2$-rank must be
\[
n-m=n-\log_2(\frac{n+1}{r+1}).
\]
\end{theorem}
\pf\ We already know that $r+1$ divides $2l$; if $2l=r+1$
we are in the codimension 1 case and $C$ is the full even-weight
subcode of $\bmi{F}_{\!\!2}^{2l}$. Here $m=1$. Assume, therefore,
that $r+1<2l$. Setting
$\frac{2l}{r+1}=s$ we have that the subcode of $C$ generated
by the weight-two vectors is isomorphic to the direct sum
of $s$ copies of the even-weight subcode of $\bmi{F}_{\!\!2}^{r+1}$
and that the $s$ supports partition the coordinates of $C$.
Let the set of these $s$
supports be $\cal S$. Since $r+1<2l$ we must
have weight-three vectors in $C$. Suppose $v$ is such a
weight-three vector. Then it cannot have two 1s in any
given $S\in {\cal S}$ and hence defines a triple of the set
$\cal S$. If $\{R,S,T\}\subseteq {\cal S}$ is such a triple,
then every vector with one 1 in each of $R$, $S$ and $T$
is a weight-three vector in $C$. In particular, each such
triple of $\cal S$ yields $(r+1)^3$ weight-three vectors
of $C$. If
$\{R,S,T\}$ and
$\{R,S,T'\}$ are two such triples then $T=T'$
for, otherwise, we could produce a weight-two vector
in $C$ with one 1 in $T$ and
another in $T'$, an impossibility. It follows from Proposition~\ref{1}
that we have defined a Steiner triple system on $\cal S$.
We next show that this triple system must be a classical
triple system coming from the design of points and lines
of some PG$_{m-1}(\bmi{F}_{\!\!2})$ and thus produce the $m$ of
the Theorem. Suppose the triple system just defined
on $\cal S$ is {\em not\/}
such a classical system. Then some linear combination of the
triples produces a vector of weight one. Ordering each of the
subsets in $\cal S$ and mimicking that linear combination with weight-three
vectors of $C$ adjusted, say, flushright, we would produce a vector
of weight one in $C$ --- which yields the desired contradiction.
Now, since such a classical
triple system is uniquely determined by $m$ and since
$C$ is generated by its weight-two and weight-three vectors, we
see that $r$ and $m$ uniquely determine $C$.
Determining the dimension of $C$ and hence the 2-rank of
any triple system with $C$ as carrier is easy: the classical
triple system has 2-rank $2^m-1-m$ and since there are $2^m-1$
even subcodes, each of dimension $r$,
to take into account the dimension of
$C$ is $r(2^m-1) +2^m-1-m$ and the 2-rank of the triple
system with $C$ as carrier is dim$(C) +r= (r+1)2^m-(m+1)$
and, since $2l+r=n$, we are done.\done
\smallskip
The carrier determined by $r$ and $m$ will henceforth be
denoted by
\[
\bmi{C}_{r,m}
\]
and its properties described explicitly in the Theorem below.
\begin{corollary}\label{cor-n}
If a Steiner triple system has a trivializing subsystem on
$r$ points, then the Steiner system is on $n=(r+1)2^m -1$ points
for some positive integer $m$.
\end{corollary}
The proof just given yields more than the Theorem. It allows
us to display every possible carrier and determine its
automorphism group:
\begin{theorem}
If $C$ is a carrier of a Steiner triple system, then $C^\perp$
is isomorphic to the code one obtains from the dual
of the Hamming code on $2^m-1$ points by repeating
it $r+1$ times. We denote this carrier $C$
by $\bmi{C}_{r,m}$. It is of block length $(r+1)s$
where $r\jmod{1,3}{6}$ and $s=(2^m-1)$ and enjoys the following
properties:
\begin{itemize}
\item The $(r+1)s$ coordinates of $\bmi{C}_{r,m}$
are split into $s$ sets each
of cardinality $r+1$
\item On the $s$ sets is imposed a classical Steiner triple
system
\item A vector of weight $2$ is in $\bmi{C}_{r,m}$ if and only if its
support is contained in one of the $s$ sets
\item A vector of weight $3$ is in $\bmi{C}_{r,m}$ if and only if its
support is such that no two elements are in one of the $s$
sets and the three sets that do have a non-empty intersection
with its support form a triple of the imposed classical
Steiner triple system
\item $\bmi{C}_{r,m}$ is generated by its vectors of weight $2$
and $3$.
\end{itemize}
\end{theorem}
\begin{corollary}
The automorphism group of $\bmi{C}_{r,m}$ is the semi-direct
product of $PGL_m(\bmi{F}_{\!\!2})$ and the direct product
of $2^m-1$ copies of {\em Sym}$(r+1)$ where the projective
group acts on the direct product in the obvious way.
\end{corollary}
\begin{corollary}
A carrier $\bmi{C}_{r,m}$ has
$$r(\frac{r+1}{2})(2^m-1)$$
vectors of weight
$2$ and
$$(r+1)^3\frac{(2^{m}-1)(2^{m-1}-1)}{3}$$
vectors of weight $3$.\footnote{It is, of course, easy to give
the weight enumerator of each $\bmi{C}_{r,m}$ and we will soon
do so --- thus determining the weight enumerator of all binary
codes of Steiner triple systems of deficient 2-rank. We have
given the number of vectors of weight 2 and 3 in the Corollary
simply to emphasize those aspects of the carrier that are
important in the construction of all Steiner
triple systems of deficient
2-rank.}
\end{corollary}
We have taken the liberty in the statement of the Theorem to
include the binary code $\{0\}$ as an honorary Hamming code of block
length one.\footnote{In fact, it deserves the name: it is a single-error
correcting code of block length one with every vector in the ambient
space at distance 1 or less from a unique vector in the code.}
It corresponds to the case
$m=1$ where we have, of course, simply the even-weight subcode
of $\bmi{F}_{\!\!2}^{r+1}$. Letting $\jvec$ be the all-one vector
of length $r+1$, observe that the dual of
the code $\bmi{F}_{\!\!2}\,\jvec$, which is
the dual of the Hamming code of block length one
repeated $r+1$ times, is
precisely this even code. A resolution of the 1-$(r+1, 2,r)$
design given by its weight-two vectors can, in general, be had
in many ways: for $r=1$ or $r=3$ just one, but for $r=7$ six and in
396 ways for
$r=9$ \ --- and then the combinatorial explosion arrives \cite{DGM}.
A resolution of the 1-design given by $\bmi{C}_{r,m}$ when $m>1$ can
be formed by stitching together resolutions, chosen independently,
for each of the $2^m-1$ even subcodes. To choose a
collection of weight-three vectors of $\bmi{C}_{r,m}$
satisfying the hypothesis of Proposition~\ref{1} one must and can
choose $(r+1)^2$ vectors, no two
with two common 1s, for each of the
triples,
again independently,
of the imposed triple system and that is very easy.
We describe all possible choices next:
We think of the choice as an $(r+1)\times 3$ array of
square matrices of size $r+1$. The pigeon-hole principle
forces one to have $r+1$ 1s in each column of the array. Thus
we can assume that in the first of the three columns of
matrices we have arranged matters so that the first matrix
has 1s in its first column with 0s elsewhere, the second
has 1s in its second column with 0s elsewhere, etc. Then
we may assume that the second column of matrices is just
the identity matrix repeated $r+1$ times. Finally, the
third column consists of $r+1$ permutation matrices,
$P_1,P_2,\ldots,P_{r+1}$ where $P_iP_j^{-1}$ has no fixed
points for distinct $i$ and $j$. For example, we could
take $P_i=Z^{i-1}$, $1\leq i\leq r+1$, where $Z$ is the
cyclic shift. This choice was that given
in the Example displaying the code $\bmi{C}_{1,2}$, where there
is only one choice up to equivalence.
From the description of $\bmi{C}_{r,m}$ in terms of the dual
to the Hamming code of block length $s=2^m-1$ one uses
the MacWilliams transform to compute easily its weight enumerator:
\[
\frac{1}{s+1}\left( (1+X)^{s(r+1)}
+s(1-X^2)^{\frac{(r+1)(s-1)}{2}}(1-X)^{r+1}\right).
\]
\begin{corollary}
If $D$ is the binary code of a Steiner triple system on
$n$ points of \ $2$-rank $n-m$ with
a trivializing
subsystem on $r$ points, its weight enumerator is
\[
\frac{1}{2^m}\left( (1+X)^{n-r}
+(2^m-1)(1-X^2)^{\frac{n-2r-1}{2}}(1-X)^{r+1}
\right)(1+X)^r.
\]
\end{corollary}
\pf\ We have that $n=(r+1)2^m-1$ with $s=2^m-1$ and that the
binary code of the triple system is the direct sum of
$\bmi{C}_{r,m}$ and $\bmi{F}_{\!\!2}^r$.\done
\section{Constructing systems from a carrier}\label{sec-carcon}
We begin by pointing out how to construct a Steiner
triple system from a putative carrier satifying the
criterion of Proposition~\ref{1}. It follows that each
of the codes $\bmi{C}_{r,m}$ will define triple systems (which
may possibly have larger carriers) and that the number of
systems $\bmi{C}_{r,m}$ constructs grows very fast as $r$ and $m$ do.
\begin{theorem}\label{thm-con}
Suppose $C$ is a binary code of block length $2l$,
minimum weight $2$ and index
$r$ where $r\jmod{1,3}{6}$.
Suppose also that $C$ contains a collection of
$\frac{l}{3}(2l-r-1)$ weight-three vectors with the property
that no two have supports intersecting in more than one point.
Then, given the following data,
\begin{itemize}
\item A Steiner triple system on $r$ points
\item A resolution of the supports of the weight-two vectors
of $\,C$ into $r$ parallel classes
\item A bijection of the parallel classes of the above given
resolution with the points of the above given triple system
\item A collection, possibly empty,
of $\frac{l}{3}(2l-r-1)$ weight-three
vectors of $\,C$ with the property
that no two have supports intersecting in more than one point,
\end{itemize}
there is a Steiner triple system on $2l+r$ points containing
the given system on $r$ points as a subsystem. Moreover, if
the Steiner triple system given in the data
is of $2$-rank $r$, then the carrier of the constructed system
is $\bmi{C}_{r,m}$, where $2l=(r+1)(2^m-1)$,
and the trivializing subsystem is that Steiner
triple system; if the system on $r$ points is of deficient
$2$-rank, then the carrier may be larger and that will depend on
the choice of the other data.
\end{theorem}
\pf\ Let $S'$ be the set of cardinality $r$ on which the
Steiner triple system of the data
is given and $T$ the set of coordinate
places of the code $C$. We assume, of course, that $S'$ and
$T$ are disjoint; we construct the sought for triple system
on the set $S=S'\cup T$.
Here are the triples on $S$:
\begin{itemize}
\item The given triples on $S'$
\item
For each $x\in S'$ corresponding, under the given bijection, to
the parallel class $\cal P$ of the given resolution the
triples of the form $\{x\}\cup P$ where $P\in{\cal P}$
\item
The triples from the supports of the selected
weight-three vectors of $C$
\end{itemize}
It is easy to see that no two
of the 3-subsets we have described meet in more than one point.
Moreover, the number of these 3-subsets of $S$ is
$$rl + \frac{r(r-1)}{6} + \frac{l}{3}(2l-r-1)=
\frac{(2l+r)(2l+r-1)}{6}$$
and we have a Steiner triple system
on $S$. Let $D$ be the binary
code of the constructed triple system.
If the given triple system on $S'$ has 2-rank $r$ it is
clear that it must be the trivializing subsystem
since
the projection of $D$ onto $T$ is contained in
$C$ and generated by the weight-two and chosen weight-three
vectors of $C$. If the given triple system on $S'$
has 2-rank less than $r$ it may or may not be the
trivializing subsystem but, because the projection is
contained in $C$, it will contain the trivializing
subsystem by Proposition~\ref{propT}.\done
\medskip
\rks\
{\bf 1)} If the code $C$ is the full even-weight subcode of
$\bmi{F}_{\!\!2}^{2l}$ of maximal index $2l-1$ with $l$ not divisible
by 3, then the construction proceeds without recourse to
any weight-three vectors of $C$ (and, in fact, there aren't
any). All one needs is a resolution of the set of 2-subsets
of a $2l$-set and a Steiner triple system on $2l-1$ points. There
are always resolutions and always triple systems (because of our
restriction on $l$).
This case of the construction goes back at least as far as
Reiss \cite{reiss} and is very well-known; all Steiner triple systems with
a maximal subsystem are clearly so constructible, the carrier, of
course, is merely $\bmi{C}_{r,1}$ and the maximal subsytem is on
$r$ points.
\smallskip
{\bf 2)} It is instructive to take a minimalist approach to this
construction and decide what transpires when one begins with
the degenerate triple system on one point and does not even
assume that the carriers or Hamming codes are known, but
``discovers'' both in the construction process.
The
degenerate triple system, yields the binary code $\{0\}
\subseteq \bmi{F}_{\!\!2}$ which is the honorary Hamming code
of block length 1 which
yields the carriers $\bmi{C}_{r,1}$.
At this point we
have but one triple system at our disposable and can only use
$\bmi{C}_{1,1}$; turning the crank yields the unique triple
system on 3 points, giving the Hamming code of block length
$3=2^2-1$ and hence
the carriers $\bmi{C}_{r,2}$.
Now we have two
triple systems at our disposal and we can use the one on
3 points together with the carrier $\bmi{C}_{3,1}$ which
yields only the Fano plane, the unique triple system on
7 points; the Fano plane also arises
from the degenerate system and $\bmi{C}_{1,2}$. Using the
system on three points together with $\bmi{C}_{3,2}$ yields
all the systems on 15 points of 2-ranks 11, 12 and 13.
We therefore get the carriers $\bmi{C}_{r,3}$ and $\bmi{C}_{r,4}$.
The next turn of the crank yields, among other
systems, the 23 triple systems on
15 points with 2-rank less than 15,
more carriers and so on. All possible 2-ranks appear
because one can fiddle with the data to make sure
that the triple system one uses becomes the
trivializing subsystem.\footnote{This sort of fiddling has
been used by Key and Sullivan \cite{keysul2} and by Phelps
\cite[Page 107]{phelps1} to alter one system to get another ---
but not in the systematic context we are describing.}
The reader may want to
show that, restricting the
triple systems to only those
constructed at a given stage,
only triple systems on $n=2^k-1$ points can be
constructed and all will have deficient 2-rank
between $n-k$ and $n-1$ . It also follows
from Theorem~\ref{thm-ext} that only derived triple systems
will arise.
Although all 23
triple systems on 15 points with deficient 2-rank will appear,
that will cease to be true for the systems on 31 points since
we have restricted ourselves only to triple system the
construction process produces. Thus we will miss
those on 31 points coming from the 57 systems on 15 points
with
2-rank 15.
{\bf 3)} A slightly less minimalist approach might admit, say,
the classical triple systems coming from affine geometries
over $\bmi{F}_3$ --- all of which have full 2-rank
--- besides
those constructed during the process. One would then get
the Steiner triple systems on 19 points of 2-rank 18, among
others. Once again, Theorem~\ref{thm-ext} shows that only
derived Steiner triple systems will arise.
{\bf 4)} One could even envision admitting {\em all\/} Steiner
triple systems of full
2-rank that are derived (thus,
for example, admitting the two on 13 points, the
57 on 15 points not produced by the minimalist approach, and
those produced by Theorem~\ref{thm-SQS}). Once
again only derived systems result and, for example, one
obtains the Steiner triple systems on 27 points of 2-rank
26 and all the triple systems on 31 points of deficient
2-rank.
{\bf 5)} Using the carrier $C=\bmi{C}_{9,1}$ there is only one
choice for
the Steiner triple system:
the affine plane of order 3 of full 2-rank. In this case
one always gets $C$ as the carrier and the affine plane of
order 3 as the trivializing subsytem. Here there are 396
distinct resolutions (up to equivalence under Sym(10)) and simply
using the group of the affine plane cuts the possible number
of Steiner triple systems on 19 points with 2-rank 18 to at most
332,640. Moreover, the data allow one to compute the
exact number and this has been done by
Seah and Stinson \cite{stinseah}: there are 284,457.
In this case of Steiner triple systems of order 8 (on
19 points) the
2-rank is either 18 or 19 (from Theorem~\ref{main})
and Brendan McKay estimates that the number of Steiner
triple systems is 11 or 12 billion. Thus, the vast
majority have full 2-rank. The combinatorial explosion of
the number of resolutions of a $2l$-set comes at $l=6$. The
precise number has been computed by Dinitz, Garnick and
McKay (see \cite{DGM});
there
are
526,915,620 up to equivalence under Sym(12).
It seems unlikely that anything but asymptotic results will
be available beyond 19 for the codimension 1 case.
{\bf 6)} Using the carrier $\bmi{C}_{9,2}$
of block length 30
with, again, the affine plane of order 3 being the only
choice for the trivializing subsystem, we must choose
on each of the three 10-sets a resolution of the set of 2-subsets.
There will be a choice of 396 possible resolutions for
each of the set of 2-subsets
of the three 10-sets --- and therefore
a gross number of choices of
$(396)^3$. The splicing will introduce a factor of $(9!)^2$
with the bijection boosting that factor to $(9!)^3$. There is still
the choice of the weight-three vectors which will introduce a
another large factor, namely
the number of ways to choose nine
(since we may assume the first is the identity permutation)
fixed-point free permutations from Sym(10) such that the product
of any one with the inverse of any other is again fixed-point
free.
But, since all the automorphism
data is available, the calculation might
conceivably be within reach and certainly estimates, such as
those given by Ferch and Stinson in \cite{stinferch}, could be made.
If so, the number of Steiner triple systems
on 39 points of 2-rank 37 would be determined or estimated ---
that is Steiner triple systems on 39 points with a trivializing
subsystem on 9 points.
{\bf 7)} Observe that not only can one estimate the number of systems
one gets by the construction (knowing, of course, that every
triple system with the given 2-rank will be constructed) but,
in principle, one can determine the automorphism group
of the constructed system from the automorphism group of the
trivializing subsystem and the subgroup of the known
automorphism group of the carrier leaving the data
invariant. Although it is known that most Steiner triple systems
have a trivial automorphism group, that doesn't prohibit there
being automorphisms here since we are {\em not\/} able to
construct systems of full 2-rank --- which dominate
at every stage.
{\bf 8)} It is possible to generalize this construction somewhat
so as to be able to produce {\em some\/} Steiner triple systems of full
2-rank. To do so one partially disregards
the coding theory and imposes the triples of
{\em any\/} triple system
on the various $(r+1)$-sets.
The matter is more easily explained in terms of Steiner
quadruple systems and we do that in Section~\ref{sec-SQS}.
\medskip
We summarize what we have proved in an existence and uniqueness
theorem which captures, by Theorem~\ref{thm-con} and
Corollary~\ref{cor-n}, all Steiner
triple systems of deficient 2-rank. In particular, for
$n>7$ and $m>0$ a Steiner triple system on $n$ points of
2-rank $n-m$ has a binary code isomorphic to
\[
\bmi{C}_{r,m}\oplus \bmi{F}_{\!\!2}^{r}
\]
and, of course, those of full 2-rank have simply $\bmi{F}_{\!\!2}^n$
as their binary code.
\begin{theorem}\label{thm-exun}
Let $n>7$ be congruent to $3$ or $7$ modulo $12$ and
set $n+1=u\times 2^k$ with $u$ odd. Then, for any choice of
$i$ with $1\leq i2$ and its binary code is obtained from the corresponding Hamming code
by simply adjoining a vector of
weight one.
\end{proposition}
\begin{proposition}
If a Steiner triple system has a three-point trivializing
subsystem then it is on $2^{m+1}-1$ points for
some $m>2$ and its binary code is obtained from the corresponding
Hamming code by simply adjoining two weight-one vectors.
\end{proposition}
It should not be a difficult matter to determine all the Steiner
triple systems that arise in these two cases; we have not tried
to do so. A more interesting case arises when one takes the
Fano plane as the trivializing subsystem; here one employs the
carrier $\bmi{C}_{7,m}$ and there will be a choice available
both for the resolution of the set of 2-subsets of the 8-set,
for the seams and for the bijection. A computer study seems
appropriate; all the Steiner triple systems on 31 points of 2-rank 27,
28 and 29 could, perhaps, be enumerated.
Clearly one expects the
number of triple systems to increase
markedly with $i$ as this
parameter increases from 1 to $k-1$ in Theorem~\ref{thm-exun}.
We have here a nice example of how lowering the rank
constrains the systems being discussed. Even for triple
systems on 19 points one has billions of systems of 2-rank
19 but only hundreds of thousands with 2-rank 18. (The Tonchev-Weishaar
study recorded one system of rank 12, five of rank 13, and sixteen
of rank 14.)
\section{Applications}\label{sec-App}
In November of
1852 when Steiner originally asked for those $n$ for which
there was a Steiner triple system and for the number of such systems
for each such $n$, he also asked\,\footnote{Question (b) of the infinite
list of questions he posed: \cite{steiner}.} whether or
not such systems extended to Steiner quadruple systems, that is
he asked, for any given Steiner triple system, whether or not it
was possible to introduce a collection of 4-subsets of the underlying
set with the property that no one of these 4-subsets contained a
triple but every 3-subset not a triple was in a unique member of
the introduced 4-subsets.
Now we would express Steiner's question
as follows: ``Does every Steiner triple system on $n$ points extend to
a Steiner quadruple system on $n+1$ points?'' or ``Is every Steiner
triple system derived?'' since one gets such a system from a
Steiner quadruple system by suppressing a point and using only the
quadruples through that point.
All classical systems are derived and, in
general, in many ways so; in particular, the unique systems on
3, 7 and 9 points are derived. Both triple systems on 13 points are
derived as are
all 80 triple systems on 15 points; these results
were computer generated. It is widely
believed that all Steiner triple systems are derived
and an enormous effort has gone into proving this result; for a
survey of what is known about derived systems see
\cite{phelps1}.
We make
a contribution to the subject
by reducing the question to those Steiner triple systems with full
2-rank. But, more importantly, the proof is very robust and
sheds a lot of light on the question; the proof
explicitly displays the quadruple systems that are
the extension and thus also clearly shows why
an enormous number of extensions arise. Here is what we prove:
\begin{theorem}\label{thm-ext}
Any Steiner triple system whose trivializing
subsystem is derived is itself derived.
\end{theorem}
\pf\ We assume the carrier of the system is $\bmi{C}_{r,m}$ and
view the point set of the system as $s=2^m-1$ disjoint $(r+1)$-sets
and a disjoint $r$ set in the obvious way. We must define
4-subsets covering each triangle (i.e.\ a 3-subset which is not
itself a triple of the system) exactly once with none
of the introduced 4-subsets containing a triple.
On the $r$-set we use those
4-subsets that define one of
the trivializing subsystem's extensions since the $r$-subset
is
the support of the
trivializing subsystem --- which we are assuming
is derived. Similarly, we use (independently as
always in this work) Steiner quadruple systems on $r+1$ points
on each of the $(r+1)$-sets; these quadruple systems
need have no relation to the trivializing
subsystem. These choices are rather obvious
ones; the first introduces
\[
\frac{1}{24}r(r-1)(r-3)
\]
4-subsets and the second
\[
\frac{s}{24}(r+1)r(r-1).
\]
We next itemize some not quite so obvious choices:
\begin{itemize}
\item For each point $p$ of the $r$-set, each
choice of two, $R$ and $S$ say,
of the $(r+1)$-sets, and
each choice of % the $(\frac{r+1}{2})^2$,
$P_R\subseteq R$
and $P_S\subseteq S$ say, where $P_R$ and $P_S$ are in
the parallel class defined by $p$, we use the 4-subset
$P_R\cup P_S$. This introduces
\[r{{s}\choose{2}}(\frac{r+1}{2})^2
\]
4-subsets.
\item For each triple $t$ of the trivializing subsystem on
the $r$-set, each $p\in t$, and each of the % $s(\frac{r+1}{2})$
2-subsets, $P$ say, in the parallel class defined by $p$ we use the
4-subset $P\cup t'$, where $t'$ is the triple $t$ with $p$
removed. This introduces
\[\frac{1}{2} r(r-1)s(\frac{r+1}{2})
\]
4-subsets.
\item For each triple $\{R,S,T\}$ of the classical system on
the $(r+1)$-sets, each point $p$ of the trivializing subsystem,
and every triple $\{x,y,z\}$ of the
constructed triple system, with $x\in R, y\in S$ and $z\in T$, we use
the three 4-subsets $\{x',y,z,p\}, \{x,y',z,p\}$ and
$\{x,y,z',p\}$ where $\{x,x'\}, \{y,y'\}$ and $\{z,z'\}$ are
in the parallel class defined by $p$. This introduces
\[
\frac{1}{2} s(s-1)r(r+1)^2
\]
4-subsets.
\end{itemize}
And finally we employ the classical system on the
$(r+1)$-sets to introduce 4-subsets with the property that they
have one point in each of four $(r+1)$-sets. We pick, of course,
four $(r+1)$-sets corresponding to some extension of the
classical system. Any extension of
the classical system will do, but, as we
shall see later, one gets a
``nicer'' quadruple system if one
chooses the natural extension arising
from the points and
2-flats of $AG_m(\bmi{F}_{\!\!2})$.
If $\{R,S,T,U\}$ is such a 4-subset we will
need to pick $(r+1)^3$ 4-subsets of the form $\{x,y,z,w\}$
with $x\in R, y\in S, z\in T$ and $w\in U$ with no two meeting
in more than two points to insure that each of the
$4\times (r+1)^3$ of those 3-subsets of the underlying point
set that are contained in $R\cup S\cup T\cup U$ --- but with no
two points in an individual one of the $(r+1)$-sets --- is
covered exactly once. One again can normalize the choice much
as was done in picking the triples
in the construction given in Section~\ref{sec-carcon}.
So, for example, the
first column would be $(r+1)^2$ 1s followed by 0s, the second
$(r+1)^2$ 0s followed by
$(r+1)^2$ 1s followed by 0s, etc.~through the $(r+1)$-st column.
Then, for the next three columns against the 1s in column one
we would put the same array as we did for the triples; for the
1s in column two we can repeat with, say, a cyclic shift on the
last $r+1$ columns consisting of the fixed-point free
permutation matrices. Here is an illustration for the case
we have already treated with $r=1$:
\[
\begin{array}{cccccccc}
1&0&1&0&1&0&1&0\\
1&0&1&0&0&1&0&1\\
1&0&0&1&1&0&0&1\\
1&0&0&1&0&1&1&0\\
0&1&1&0&1&0&0&1\\
0&1&1&0&0&1&1&0\\
0&1&0&1&1&0&1&0\\
0&1&0&1&0&1&0&1
\end{array}
\]
This introduces
\[\frac{1}{24}s(s-1)(s-3)(r+1)^3
\]
4-subsets.
Since the triples of the constructed triple system either lie
completely in the $r$-set, have one point in the $r$-set and
two points in some $(r+1)$-set, or three points distributed
over three $(r+1)$-sets defining a triple of the classical
system on the collection of $(r+1)$-sets, one sees easily
that no one of the 4-subsets introduced contains a triple of
the constructed Steiner triple system.
Seeing that no two of the chosen 4-subsets meet in more than
two points is not difficult. One can then
sum and find the right number of 4-subsets, namely
\[
\frac{1}{24}[s(r+1)+r][s(r+1)+r-1][s(r+1)+r-3]
\]
---
or what may be more instructive and is, moreover,
fun, actually see how each triangle
is covered. For example, if a triangle has two points in one
$(r+1)$-set and one in the $r$-set one uses the doubleton to
define a point $p$ in the $r$-set (which must be different from
the point we were given) and uses these two points of the
$r$-set to get a triple $t$ of the trivializing subsystem and
then employs the second of the itemized prescriptions above.
This completes the proof.\done
\smallskip
\begin{corollary} If all Steiner triple systems on $n$ points
and $2$-rank $n$ are derived, then
all Steiner triple systems are derived.
\end{corollary}
\pf\ The proof is quite obvious and proceeds via induction
on the order of the triple system.\done
\smallskip
The Theorem is more robust than it first appears. For example
it shows that all Steiner triple systems on 31 points with 2-rank
less than 31 are derived since we know those
of smaller order are. Even without one line of computation the
Theorem shows that all Steiner triple systems on 19 points of
2-rank 18 are derived --- but
this was already known. As far
as I know it had not, however, been observed that all Steiner triple
systems on 39 points of 2-rank 37 are derived, an immediate consequence
of the Theorem since the trivializing
subsystem must be the affine plane over
$\bmi{F}_3$ --- although this could have been seen via
existing methods. In fact, the Theorem itself could have been proved
with existing methods since Kevin Phelps \cite{phelps5}
had shown that any system with a maximal derived subsystem was
itself derived, and combining this with Teirlinck's notion of
projective dimension \cite{teir1} gives the result. But the
direct proof above is simple and exhibits explicitly
an enormous number of the
extensions.
\smallskip
There is another point to be made about the proof: except for
the arbitrarily chosen quadruple systems on the $(r+1)$-sets
and the 4-subsets given to us on the $r$-set by our hypothesis,
one sees easily that all the 4-subsets chosen are contained
in the linear span of the constructed Steiner triple system. This
is
because we have chosen the design of points and 2-flats of an
affine geometry to extend the classical Steiner triple system
on the $(r+1)$-sets.
But for this extraneous
data the same thing is true
since on each of the $(r+1)$-sets we see the full
even-weight subcode and on the $r$-set the full code. Thus
we have the following
\begin{corollary}
If the trivializing subsystem of a Steiner triple system
is derived, then not only is the Steiner system derived,
but
the extension can be so chosen that the
binary code of the resulting quadruple system is simply that
of the Steiner system with an overall parity check added
and its code is given by $2^m$ full even-weight subcodes of
$\bmi{F}_{\!\!2}^{r+1}$ with the planes of the affine geometry
$AG_m(\bmi{F}_{\!\!2})$ imposed as those weight-four vectors
with one $1$ in each of four of these even subcodes.
\end{corollary}
Both the Theorem and this Corollary were proved by Key and
Sullivan in
the cases $r=1$ and $r=3$; these cases correspond to the
degenerate triple system and the one on three points, both of
which are derived.\footnote{The degenerate quadruple system
has two points and no blocks.}
\smallskip
And the proof isn't through yielding information:
it can be read
as a construction vehicle for Steiner quadruple systems; as such it
gives the following
\begin{corollary}\label{cor-SQS}
Given any $2^m$ Steiner quadruple systems on $r+1$
points, where $m$
is a positive integer, there is a Steiner quadruple system
on $2^m(r+1)$ points containing each of the given systems as
subsystems, one
on each of $2^m$ disjoint subsets of the constructed system. Moreover,
the Steiner quadruple system can be chosen so that its $2$-rank
is $2^m(r+1) -m-1$.
\end{corollary}
Such a construction in the case $m=1$ has been known for a
long time and was used by Lindner and Rosa \cite{lindrosa1}
to construct 31,021 Steiner quadruple systems on 16 points.
It should be clear to the reader why so many systems
arose. In this case the construction is, as our discussion
clearly shows,
essentially Reiss's
``doubling'' construction, but that does not seem to have been
explicitly acknowledged in the literature
\cite[Construction A$^*$]{lindrosa}.
Since the binary code of
a Steiner quadruple system is an even
code,
the maximal 2-rank for a Steiner quadruple system
on $v$ points is $v-1$ and if it is $v-1$ its binary code is
the full even-weight subcode of $\bmi{F}_{\!\!2}^v$. The construction we
have just given constructs {\em all\/} Steiner quadruple systems
of deficient 2-rank.\footnote{I.e.\ 2-rank strictly less than $v-1$.}
It would have been easier to classify
Steiner quadruple systems of deficient 2-rank first,
but then we would have missed those Steiner triple systems,
if any, that are not derived. The carrier is
constructed by taking the first-order Reed-Muller code,
repeating it $r+1$ times, and then dualizing as we shall soon
see.
\bigskip
Since the classification presented above should reduce
a question about Steiner triple systems to the same
question about those of full 2-rank --- as we did above for Steiner's
question (b) --- Kevin Phelps's
question of whether or not
every Steiner triple system on $2^k-1$ points can be seen as the
set of weight-three vectors of a perfect binary code containing
the zero vector (see \cite{ak:update}) ought to be
so reduced. In this case all such
Steiner systems of deficient 2-rank are built from Steiner systems
on $2^i-1$ points for some $i3$.
\end{corollary}
\pf\ For $m=4$ we cannot use the Theorem but there are
precisely 57
such triple systems. From then on the Theorem produces the systems ---
taking $r=1$, for example.\done
\medskip
One can even impose conditions on the ingredient quadruple systems
to force a condition on the constructed system. As an illustration
of the method we give the following construction of ``resolvable''
quadruple systems, i.e.\ quadruple systems for which the
quadruples can themselves be organized into parallel classes.
Here we must be in the even-order case: the quadruple system must
be on a set of points whose cardinality is congruent to 4 or 8
modulo 12.
\begin{corollary} If there are resolvable quadruple systems on
$r+1$ and $s+1$ points, then there is a resolvable quadruple
system on $(r+1)(s+1)$ points.
\end{corollary}
\pf\ Since in the construction we can clearly piece the
resolutions of the systems on $r+1$ points together and those
quadruples given by resolution of the weight-two vectors themselves
form several parallel classes,
we need only worry about the overarching
quadruple system on $s+1$ points
which we, of course, assume is resolvable --- just as
we assume the systems chosen on $r+1$ points are. We need to
show that we can organize the choice of the 4-subsets for
each quadruple into parallel classes and then use the
resolution of the overarching system. We simply give an
illustration for the case $r=1$ treated extensively above:
\[
\begin{array}{cccccccc}
1&0&1&0&1&0&1&0\\
0&1&0&1&0&1&0&1\\
&&&&&&&\\
1&0&1&0&0&1&0&1\\
0&1&0&1&1&0&1&0\\
&&&&&&&\\
1&0&0&1&1&0&0&1\\
0&1&1&0&0&1&1&0\\
&&&&&&&\\
1&0&0&1&0&1&1&0\\
0&1&1&0&1&0&0&1
\end{array}
\]
\section{Conclusions}\label{sec-Con}
The reader familiar with the work of Teirlinck and of
Doyen, Hubaut and Vandensavel will surely be asking about
a ``ternary'' view of Steiner triple systems and, to be sure,
such a view exists and the above program is easily carried
out. We leave
as an exercise for the reader the task of exploring
this ternary world, making the appropriate definitions, and
proving the analogous results. We merely mention that one
system is a mandarin in both worlds: the Steiner triple
system on 3 points is both the projective line over $\bmi{F}_{\!\!2}$
and the affine line over $\bmi{F}_{\!\!3}$. Note, however, that there
are triple systems that are welcome neither in the binary
nor the ternary world. Such is the lot, for example, of the
two systems on 13 points.
The classification in the case of Steiner quadruple systems
bears a superficial resemblance to the ternary view of Steiner
triple systems since the mandarins in both cases are the {\em affine
geometries\/} and instead of seeing a ``point at
infinity'' as we did in defining the trivializing subsystem
one sees an array of systems spread, much like parallel classes, on
the point set --- just as in Corollary~\ref{cor-SQS} --- with a
mandarin as overseer.
A more serious question concerns possible generalization to
Steiner systems of the form $S(t,t+1,v)$ for $t>3$. Here the reader
will surely want to consult Teirlinck's work and perhaps
also Cameron's book \cite{cameron:1}, where the matter
is discussed.
It does not seem
likely, however, that anything further can be said and $t=3$
seems to be
the natural boundary --- as Michel Dehon's work \cite{dehon} indicates
even when one goes to $S_\lambda(t,t+1,v)$.
A mathematician dipping into the vast literature on the topic
of Steiner triple systems --- as I did when writing up the results
described above --- has to be struck with the chaotic nature of
many of the results and most of the
constructions and the lack of organizing
principles. One can only hope that the single construction
that quite loudly presented itself for discovery as this work
developed
will be a step in the direction of organization.
\vbox{
{\flushleft{{\sc Address:}\\
Projet Codes, INRIA\\
Domaine de Voluceau - Roquencourt, B.P.~105\\ 78153 Le Chesnay
CEDEX, France\\
E-mail address: Edward.Assmus@inria.fr\\}}}
\smallskip
\vbox{{\flushleft{
{\sc Permanent Address:}\\
Department of Mathematics\\ Lehigh University,
14 E.~Packer Avenue\\
Bethlehem, PA 18015-3174, USA\\
E-mail: efa0@lehigh.edu
}}}
\bibliographystyle{plain} \bibliography{bib}
\end{document}