% \documentstyle[a4,12pt]{article}
\documentclass[a4paper]{article}
\usepackage{a4}
\usepackage{latexsym}
\title{The universal embedding dimension of the binary symplectic
dual polar space}
\author{A. Blokhuis \& A. E. Brouwer}
\date{2000-06-26}
\begin{document}
\maketitle
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Rr}{{\bf R}}
\newcommand{\Zz}{{\bf Z}}
\newcommand{\fsL}{{\cal L}}
\newcommand{\infinity}{{\infty}}
\newcommand{\adj}{\,\sim\,}
\newcommand{\nadj}{\,\not\sim\,}
\newcommand{\rk}{{\rm rk\,}}
\newcommand{\rktwo}{{\rm rk}_2\,}
\newcommand{\udim}{{\rm udim\,}}
\newcommand{\sdim}{{\rm sdim\,}}
\newcommand{\Aut}{\rm Aut\,}

\abstract{The universal embedding dimension of the symplectic
dual polar space $DSp(2d,2)$ equals $(2^d+1)(2^{d-1}+1)/3$.
% Moreover, this dual polar space can be spanned as a linear space
% by the same number of points.
This settles an old conjecture.}

\section{Introduction}

Given a set $X$, let $\Ff_2 X$ denote the vector space with basis $X$
over the field $\Ff_2$ with 2 elements.

Let $(X,\fsL)$ be a partial linear space with lines of size 3.
Consider the linear map $\sigma : \Ff_2 \fsL \rightarrow \Ff_2 X$
sending each line to the sum of its (three) elements.
The {\em universal embedding module} of $(X,\fsL)$ is
the vector space $\Ff_2 X / \sigma(\Ff_2 \fsL)$.
The {\em universal embedding dimension} (udim) of $(X,\fsL)$
is the dimension of the universal embedding module.

Clearly, when $X$ and $\fsL$ are finite,
$\udim (X,\fsL) = |X| - \rktwo N$,
where $N$ is the 0-1 point-line incidence matrix of $(X,\fsL)$
and ${\rm rk}_2$ denotes the 2-rank, that is, the rank over $\Ff_2$.

Let $(X,\fsL)$ be a partial linear space.
A subset $Y$ of $X$ is called a {\em subspace} when
each line that meets $Y$ in at least two points is contained in $Y$.
We say that a subset $S$ of $X$ is a {\em spanning}
(or {\em generating}) subset when it is not contained in a proper subspace.
Let $\sdim (X,\fsL)$ be the cardinality of the smallest spanning subset
of $(X,\fsL)$.

Clearly, if $(X,\fsL)$ is a partial linear space with lines of
size three and $S$ is a spanning subset, then the image of $S$
in $\Ff_2 X / \sigma(\Ff_2 \fsL)$ is not contained in a proper
subspace, and it follows that $\sdim (X,\fsL) \ge \udim (X,\fsL)$.

In this note we are mainly interested in the partial linear space
$DSp(2d,2)$ defined as follows.
Let $V$ be a vector space of dimension $2d$ over $\Ff_2$ provided with
a nondegenerate symplectic form $f$. Let $X$ be the collection of
maximal totally isotropic (t.i.) subspaces (of dimension $d$)
of $(V,f)$. Let $\fsL$ be the collection of
t.i. subspaces of dimension $d-1$ of $(V,f)$.
Then $(X,\fsL)$ becomes a partial linear space with lines of size 3 if
we let $A$ be incident with $L$ whenever $L \subset A$ (for
$A \in X$ and $L \in \fsL$). We shall call this partial linear space
$DSp(2d,2)$ (or $DV$, in case the underlying space needs to be
specified), and its universal embedding module $U_d$.

Our main result is the following.

\begin{Theorem}
\label{mainthm}
For $d \ge 0$ we have $\udim DSp(2d,2) = (2^d+1)(2^{d-1}+1)/3$.
\end{Theorem}

Probably also $\sdim DSp(2d,2) = \udim DSp(2d,2)$, but we do not
show that here.


\section{History}
Let us put $m(d) := (2^d+1)(2^{d-1}+1)/3$.
The second author proved in 1990 that $\dim U_d \ge m(d)$
with equality for $d \le 4$, and conjectured that equality
holds for all $d$.
(The result that $\dim U_3 = 15$ can also be found in
\cite{Y} and \cite{BCHW}.)
Cooperstein \cite{C} showed
$\udim DSp(2d,2) = \sdim DSp(2d,2) = m(d)$ for $d \le 5$,
and found $715 \le \udim DSp(12,2) \le \sdim DSp(12,2) \le 716$.
Later, according to McClurg \cite{McC} and Li \cite{L},
A. A. Ivanov \& M. K. Bardoe showed that $\udim DSp(2d,2) = m(d)$
for $d = 6,7$.
%
Ivanov \cite{I} formulated a conjecture on linear modules
that would imply the conjecture on $\dim U_d$.
% Namely:
% 
% {\it Let $V$ be the set of all subspaces in a $GF(2)$-vector space. Let
% $P_i$ be the power set of $i$-subspaces in $V$ made into a
% $GF(2)$-vector space by means of the symmetric difference operator.
% For a flag $\Phi$ in $V$, let $P_i(\Phi)$ denote the set of all
% $i$-subspaces incident with $\Phi$. For $1 \leq j \leq i$, let
% $\Psi_{i,j}$ be the map from $P_i$ into $P_j$ defined by
% $\Psi_{i,j}(v) = P_j(\{v\})$ for an $i$-subspace $v$.
% Do the elements $P_i(\Phi)$, taken for all
% flags of type $\{i-j, i+1\}$, span
% $\langle Im(\Psi_{i+1,i}), ker(\Psi_{i,j})\rangle$?
% 
% The affirmative answer for $j=1$ is well known. An affirmative answer
% for $j=2$ would imply the conjecture of A.E.~Brouwer on the dimension
% of the universal representation of the dual polar space of
% $Sp_{2n}(2)$.}
%
Very recently Paul Li \cite{L} showed $\udim DSp(2d,2) = m(d)$
for all $d$ by proving the case $j=2$ of Ivanov's conjecture.

% The second author also gave detailed conjectures about the
% decomposition of $U_d$ into irreducible $Sp(2d,2)$-modules.
% See Section \ref{irred} below. The cases $d = 3, 4$
% had earlier been done by Steve Smith.


\section{Lower bound}
Let $N$ be the point-line incidence matrix of $DSp(2d,2)$.
Let ${\rm rk}$ denote the rank (over $\Rr$) of a matrix.
Then $\rktwo N \le \rk N$ and $\rk N = \rk N N^\top$.
Let $A$ be the adjacency matrix of the collinearity graph $\Gamma$ on $X$.
Then $N N^\top = A + (t+1)I$ where $t+1$ is the number of lines on each
point. This matrix is positive semidefinite, and its rank is its size
minus the multiplicity of $-t-1$ as eigenvalue of $A$. For this we turn
to \cite{BCN}. The graph $\Gamma$ has classical parameters
$(d,b,\alpha +1,\beta +1) = (d,2,1,3)$ (cf. \cite{BCN}, Table 6.1 and \S 9.4).
The number of lines on each point is the number of codimension 1 subspaces
of a $d$-space, that is, $2^d - 1$.
Comparing with \cite{BCN} (8.4.2) and (8.4.3) we find after a small
computation that $\theta_d = -t-1$ has multiplicity
$f_d = (2^d+1)(2^{d-1}+1)/3$.
Thus $\udim DSp(2d,2) = |X| - \rktwo N \ge |X| - \rk N = f_d =
(2^d+1)(2^{d-1}+1)/3$.

This argument, together with the main result of this paper, shows that
$\rktwo N = \rk N$.

\section{A reformulation}
Let $V$ be a vector space carrying the structure of $Sp(2d,2)$.
Then $V$ can be regarded as $W / N$, where $W$ is a vector space carrying
the structure of $O(2d+1,2)$, and $N$ is the radical of its bilinear form.
Recall that $DV$ is the set of totally singular $d$-spaces in $V$
provided with lines, namely the triples of totally singular $d$-spaces
containing a fixed totally singular $(d-1)$-space.
Let $H$ be a hyperbolic hyperplane of $W$, so that it carries the structure
of $O^+(2d,2)$. Let $DH$ be the set of totally singular $d$-spaces in $H$
provided with grids, namely the sets of six totally singular $d$-spaces
containing a fixed totally singular $(d-2)$-space.
The linear structure of $DV$ can be translated in terms
of the structure of $H$.

\begin{Lemma}
The binary vectorspace $U$ spanned by the elements of $DV$ under the relations
that lines sum to zero (that is, the universal embedding module for $DV$),
is canonically isomorphic to the binary vector space $U_H$ spanned
by the elements of $DH$ under the relations that grids sum to zero.
\end{Lemma}
\Proof
If $Z$ is a totally singular $d$-space not contained in $H$, then $Z \cap H$
is a totally singular $(d-1)$-space, a line in the $DO(2d+1,2)$ on $W$.
The two points on this line distinct from $Z$ are contained in $H$,
and we see that $Z$ is expressed canonically as a sum of two
totally singular $d$-spaces in $H$. The relations in $DV$ now translate
into the relations in $DH$.
\qed

If we define spanning in $DH$ by saying that any five elements of a grid
span the sixth, then anything spanned in $DH$ by a subset of $DH$
is also spanned in $DV$.


\section{Spanning}
It remains to indicate a spanning set of $DV$ (the $DSp(2d,2)$ on $V$)
of the right cardinality.

Choose a fixed orthogonal decomposition
$V = H_1 \perp ... \perp H_d$ of $V$ into hyperbolic lines.
Each vector $v \in V$ can be written uniquely in the form
$v = v_1 + ... + v_d$ with $v_i \in H_i$ $(1 \le i \le d)$.
Let the {\em weight} of $v$ be the number of $i$ for which
$v_i \ne 0$.

Let $I = \{ 1,...,d \}$ and let $J \subset I$.
Let $V_J = \perp_{j \in J} H_j$. Let $h_i$ be some
nonzero element of $H_i$ $(1 \le i \le d)$. Consider the map
$\psi : C \rightarrow C + \langle h_i | i \in I \setminus J \rangle$.
It maps the points and lines of $DV_J$ to points and lines of $DV$,
preserving collinearity. Indeed, this map is an isomorphic embedding
of $DV_J$ onto the subspace of $DV$ consisting of the elements that
contain $\{ h_i | i \in I \setminus J \}$.

Let $H_i = \{ 0,h_i^1,h_i^2,h_i^3 \}$.
Our spanning set will be constructed by induction on $d$.
Given a spanning subset $S$ of $V_J$ where $|J| = j$
we take for each $C \in S$ the $2^{d-j}$ points $\psi(C)$
where the elements $h_i$ defining $\psi$
are chosen in all possible ways from $\{ h_i^1,h_i^2 \}$.
This suffices to generate all maximal t.i. subspaces of $V$
that meet all hyperbolic lines $H_i$ for $i \in I \setminus J$
since for any t.i. $C$ of dimension $d-1$ in $H_i^\perp$
the three points $C + \langle h_i^1 \rangle$, $C + \langle h_i^2 \rangle$,
$C + \langle h_i^3 \rangle$ form a line, so that we can generate
maximal t.i. subspaces containing $h_i^3$ using those containing
$h_i^1$ and $h_i^2$. Having taken these, for all possible choices
of $J \subset I$, we take $n_d$ additional points to generate
all of $DV$.

In order to arrive at the right number, we want
$$ (2^d+1)(2^{d-1}+1)/3 = \sum_{j=0}^d 2^{d-j} {d \choose j} n_j$$
that is,
$$n_0 = 1, ~~ n_d = (2^{d-1} - (-1)^{d-1})/3 ~~ (d > 0).$$

\section{Spanning modulo weight one spaces}

For $J \subset I$, let $A_J = \langle h_j^1 | j \in J \rangle$
and $u_J = \sum_{j \in J} h_j^2$ and
$B_J = (A_J \cap u_J^\perp) + \langle u_J \rangle$.
For a partition $\pi$ of $I$, let $B_\pi = \perp_{J \in \pi} B_J$.

{\bf Claim 1} {\it The maximal t.i. subspaces of $V$ containing
a nonzero vector of weight at most 2 generate all of $DV$.}

{\bf Claim 2} {\it The maximal t.i. subspaces of $V$ containing
a vector of weight 1 together with those of the form $B_\pi$,
where $\pi$ is a partition of $I$ without parts of size 1,
generate all of $DV$.}

For disjoint nonempty subsets $A$, $B$ of $I$ and a partition $\rho$ of
$I \setminus (A \cup B)$ let us write $A,B,\rho$ for the partition
$\pi$ of $I$ with parts $A$ and $B$ and the parts of $\rho$
(that is, $\pi = \rho \cup \{A,B\}$).
For disjoint subsets $A$, $B$ of $I$, let us write $AB$ for $A \cup B$.

{\bf Claim 3} {\it In $DV$ we have for all pairwise disjoint nonempty subsets
$A$, $B$, $C$, $D$ or $I$ and each partition $\rho$ of
$I \setminus (A \cup B \cup C \cup D)$ without parts of size 1 the equality
$$B_{AB,CD,\rho} + B_{AC,BD,\rho} + B_{AD,BC,\rho} = B_{ABCD,\rho} .$$
% Unfortunately, the following is false:
% Moreover, any summand on the LHS is spanned by the other two summands on the LHS,
% the RHS and all maximal t.i. subspaces of $V$ containing a vector of weight 1.
}

Claim 3 is the only place in the proof where an equality in $U_d$ is used.
If we want to show $\sdim DV = \udim DV$ then this part must be changed.

For brevity, let us call a maximal t.i. subspace
(of some symplectic space) a {\em max}.

% Our job is to span $DV$ with the right number of points,
% and to this end it suffices to span the set of all $B_\pi$
% modulo the maxes containing a vector of weight 1 with
% $(2^{d-1} - (-1)^{d-1})/3$ elements.
% Thus, it suffices to span the binary vector space generated by
% the partitions $\pi$ without parts of size 1, with relations
% $AB,CD,\rho + AC,BD,\rho + AD,BC,\rho = 0$
% with this number of elements.
% The next section does precisely that.

\subsection{Proof of Claim 1}
If $A$ is a max and $v \in V \setminus A$
and $u \in A \setminus v^\perp$ then the three points
$A$, $(A \cap v^\perp) + \langle v \rangle$ and
$(A \cap v^\perp) + \langle u+v \rangle$ form a line.
If $A$ does not contain a nonzero vector of weight at most 2,
then we can choose $u$ of minimal nonzero weight $k$ in $A$
and pick $v$ of weight 2 such that $u+v$ has weight $k-1$,
thus expressing $A$ in terms of maxes containing nonzero vectors
of smaller weight.

\subsection{Proof of Claim 2}

Let $h$ be a nonzero element of $H_i$ for some $i$.
Let $A$ be a max and let $a \in A \setminus h^\perp$.
The three points $A$, $(A \cap h^\perp) + \langle h \rangle$,
$(A \cap h^\perp) + \langle a+h \rangle$ form a line.
This shows that when all points containing a weight 1 vector are
given, we may replace $A$ by $(A \cap h^\perp) + \langle a+h \rangle$
in a spanning set -- that is, we may permute the three nonzero elements
of $H_i$ for each $i$. In particular, modulo the points containing a weight 1
vector, the point $B_\pi$ defined by a partition $\pi$ does not depend
on the numbering of the nonzero elements of the $H_i$.

Let $A$ be a max containing a vector $a$ of weight 2 but none of weight 1.
By what was just observed, we may assume that $a = h_1^1 + h_2^1$.
Since $h_1^1 \notin A$, there is a vector $u \in A$ with $u_1 = h_1^2$,
and we can find a basis $E$ of $A$ containing $a$ and $u$ and such
that $e_1 = 0$ for $e \in E \setminus \{ a,u \}$.
Now use induction on $d$. Let $\tilde{u} = u - u_1$ and
$\tilde{E} = E \setminus \{ a,u \} \cup \{ \tilde{u} \}$.
Then $\tilde{E}$ is the basis of a maximal t.i. subspace
$\tilde{A}$ of $\tilde{V} := H_2 \perp ... \perp H_d$.
(Indeed, $\tilde{u}$ is not linearly dependent on $E \setminus \{ a,u \}$
since otherwise $A$ would contain a weight 1 vector.)
By induction $\tilde{A}$ can be generated by maxes
containing a vector of weight 1 together with maxes
of the form $B_\pi$ where $\pi$ is a partition of
$\{2,...,d\}$ without parts of size 1.
Define a map $\phi : \tilde{V} \rightarrow V$ by
$\phi(x) = x + f(x,a) u_1$, and let this map induce a map
$\bar{\phi}$ from the maxes of $\tilde{V}$ to those of $V$
defined by $\bar{\phi} (C) = \phi(C) + \langle a \rangle$.
This map preserves collinearity and preserves the property of having
a weight 1 vector in some $H_i$, $i > 2$.
If $C$ contains $h_2^1$, then so does $\bar{\phi} (C)$.
If $C$ contains $h_2^2$ then $\bar{\phi} (C)$
contains $B_{\{1,2\}}$. (Now apply induction to $D$,
where $C = \langle h_2^2 \rangle + D$ and
$D \subset H_3 \perp ... \perp H_d$ to conclude that
$\bar{\phi} (C) = B_{\{1,2\}} \perp D$ is generated as desired.)
Finally, $\bar{\phi} (B_J) = B_J$ if $2 \notin J$ and
$\bar{\phi} (B_J) = B_{J \cup \{1\}}$ if $2 \in J$.

\subsection{Proof of Claim 3}
The relation that the sum of the six elements of a grid sum to zero
yields in particular that $B_{AB,CD,\rho} + B_{AC,BD,\rho} + B_{AD,BC,\rho}
= B_{ABCD,\rho} + P + Q$, where $P$ and $Q$ are identical modulo elements
containing (a weight 1 vector) $h_i^1$ for some $i$.

\subsection{Proof of the main theorem}
In the next section we shall show that the binary vector space generated by
the partitions $\pi$ without parts of size 1, with relations
$AB,CD,\rho + AC,BD,\rho + AD,BC,\rho = 0$ has dimension
$(2^{d-1} - (-1)^{d-1})/3$. By induction on the number of parts
of the partition, it follows from Claim 3 that we can express
an arbitrary partition in terms of these basis partitions.
And then from Claim 2 that an arbitrary max can be expressed
in terms of maxes containing a vector of weight 1 and maxes
of the form $B_\pi$ for basic $\pi$. Thus we found a basis of
$U_d$ of the right cardinality. \qed

\section{Dimension of a partition space}

Let $\Pi$ be the set of all partitions of $I := \{1,...,d\}$
without parts of size 1. Turn $\Pi$ into a partial linear space
with lines of size 3 by letting any three partitions
$AB,CD,\rho$ and $AC,BD,\rho$ and $AD,BC,\rho$ (for nonempty pairwise
disjoint subsets $A,B,C,D$ of $I$) be collinear.
Let $R$ be the set of lines obtained this way.

\begin{Proposition}
For $d \ge 1$ we have
$\udim (\Pi,R) = \sdim (\Pi,R) = (2^{d-1} - (-1)^{d-1})/3$.
\end{Proposition}

We cannot have a smaller $\udim (\Pi,R)$, because that would lead
to an upper bound on $\udim DSp(2d,2)$ violating our lower bound.
Thus, it suffices to show that $\sdim (\Pi,R) \le (2^{d-1} - (-1)^{d-1})/3$.

A spanning set $S$ of this size is easy to exhibit explicitly.
Let us say that two pairs $ij$ and $kl$ (subsets of $I$) {\em cross}
when one separates the other, say $i < k < j < l$.
Take for $S$ the collection of all elements $\pi$ of $\Pi$ such that:

(S1) All elements of $\pi$ have size 2 or 3, except possibly the
element containing $d$.

(S2) No two pairs in $\pi$ cross.

(S3) The smallest element of each pair in $\pi$ is smaller
than every element in a part of size larger than 2.

(S4) The triples in $\pi$ can be ordered such that in the union of the non-pairs,
each triple consists of the three smallest elements not in earlier triples.

The {\em shape} of a partition is the vector of sizes of its parts,
given in increasing order, but with the size of the part containing $d$
given last. We write multiplicities as exponents.

\begin{Lemma}\quad
$S$ contains precisely ${d-1 \choose m} - {d-1 \choose m-1}$ elements
of shape $2^m 3^n h$.
\end{Lemma}

\Proof
For a partition of shape $2^m 3^n h$,
let an {\em edge} be one of the $m$ pairs not containing $d$.
There are ${d-1 \choose m}$ ways of choosing the set of largest elements
of the edges. Such a choice determines at most one partition in $S$:
We know the largest elements of all pairs.
Condition (S3) ensures that we know where the smallest elements of
the pairs are, and condition (S4) says that the triples now are determined
uniquely. The fact that the pairs do not cross is equivalent to the statement
that smallest elements of pairs and largest elements of pairs behave as
open and close parentheses in a well-formed parenthesized expression.

We use an Andr\'e type argument to find the number of bad choices.
Go along the elements $1,...,d$ of $I$ and and construct a path in $\Zz^2$
from $(0,1)$ to $(d,1)$ by moving for each $i$ diagonally upwards
(vector $(1,1)$) when $i$ is the smallest element of a pair,
diagonally downwards (vector $(1,-1)$) when $i$ is the largest element
of a pair, and horizontally (vector $(1,0)$) otherwise.
There is an unmatched closing parenthesis if and only if our path
meets the $X$-axis. But the cases in which that happens are in 1-1
correspondence (by reflecting the part of the path before the place
where the $X$-axis is met for the first time in the $X$-axis)
with the paths from $(0,-1)$ to $(d,1)$ with $m+1$ or $m+2$ steps up
and $m-1$ non-final steps down. Thus, there are ${d-1 \choose m-1}$
bad choices for the set of largest elements of edges.
\qed

In particular, if $d = 2m$ then $S$ contains precisely
${2m \choose m} - {2m \choose m-1} = {1 \over m+1}{2m \choose m}$
1-factors (partitions into $m$ pairs). This, together with the
rest of the present paper, shows that this number is
the universal embedding dimension of the space of 1-factors
(a subspace of $(\Pi,R)$). This is the main result of \cite{BB}.

\begin{Lemma}
$S$ has cardinality $(2^{d-1} - (-1)^{d-1})/3$.
\end{Lemma}

\Proof
Given a shape with largest element larger than 3,
let the {\em derived} shape be the one obtained by
subtracting 2 from the largest element and adding a new pair.
Thus, for $d = 9$ we have the sequence of successively derived shapes
9, 27, 225, 2223 and also 36, 234, 2232 and also 333.
Adding the number of elements of $S$ of some shape in a maximal sequence
of successively derived shapes starting with $3^n h$
we find ${d-1 \choose m}$ when $d = 2m+3n+2$ or $d = 2m+3n+3$.
That means that
we must show that $\sum_m {d-1 \choose m} = (2^{d-1} - (-1)^{d-1})/3$
where the sum is over all nonnegative $m$ with
$d = 2m+3n+2$ or $d = 2m+3n+3$ for some nonnegative $n$.
Replace in the first case $m$ by $d-1-m$ to transform it
into $d = 2m-3n$. This reduces the problem to showing that
$\sum_m {d-1 \choose m} = (2^{d-1} - (-1)^{d-1})/3$
where the sum is over all $m$ with $3 | m+d$.
And that is an easy exercise. (If $\omega$ is a cube root of unity,
then $\sum_i {d-1 \choose i} \omega^i = (1 + \omega)^{d-1}$.
Now make a suitable linear combination of the three equations
obtained for the three cube roots of unity, and use that if
$\omega$ is a primitive cube root of unity then $1 + \omega$
is a sixth root of unity.) \qed

So, the size is right. Next we must worry about spanning.
First we handle partitions with two parts.
Given a subset $J$ of $I$, let the corresponding partition be
the partition $\{ J, I \setminus J \}$. Now we can talk about
spanning among subsets of $I$ (in $(\Pi,R)$).

\begin{Lemma}\quad

(i) The pairs $12, ..., 1d$ span the collection of all pairs.

(ii) If moreover $d \ge 6$, then all partitions of $I$ into two parts
are generated by the $d-2$ pairs $12, ..., 1(d-1)$ and the triple $123$.
\end{Lemma}
\Proof
Interpreted for partitions with two parts, our relation
$AB,CD + AC,BD + BC,AD = 0$ means that while generating
subsets we may take the symmetric difference (`sum') of two sets
that have a nonempty intersection and do not together cover $I$.
Since the pair $ij$ is the sum of the pairs $1i$ and $1j$ we have (i).
The pairs $12, ..., 1(d-1)$ generate all pairs not containing $d$,
and using the triple we find all triples not containing $d$,
and then all subsets of $I \setminus \{ d \}$ of cardinality
between 2 and $d-2$. Since we may also take complements, we have (ii).
\qed

\begin{Lemma}
$S$ spans $(\Pi,R)$.
\end{Lemma}
\Proof
Given a partition $\pi$ in $\Pi$, we must show that it is in the span of $S$.
Use induction on the number of pairs, assuming that we have already spanned
all partitions with more pairs than $\pi$. If $\pi$ has two parts of size
at least 4, then use the previous lemma to see that $\pi$ is spanned by
partitions with fewer parts of size at least four. If $\pi$ has a part of size
at least 4 and it does not contain $d$, then use induction and the previous lemma
(on the union of this part and the part containing $d$) to span $\pi$ by partitions
satisfying (S1). If $\pi$ has a pair and a non-pair violating (S3), use
part (i) of the previous lemma to fix that. If $\pi$ contains two triples,
or a triple and a larger part (containing $d$) such that (S4) is violated,
then again use induction and the previous lemma on these two parts to fix that.
Finally our relation expresses a partition with two crossing pairs in
two partitions with fewer crossing pairs.
\qed


% \section{Conjectures -- unfinished}
% \label{irred}
% 
% {\bf Conjecture} [Brouwer, 1992]
% {\it $U_d$ contains $M(\lambda_d)$ with multiplicity 1.
% If $j < d$, then
% $U_d$ contains $M(\lambda_j)$ with multiplicity $f(d-j+1)$,
% where $f(m) = {1 \over 3} (2^w - (-1)^w)$, and where $w$
% is found by writing $m$ in binary:
% $m = \sum_{i=0}^t m_i 2^i$ with $m_t = 1$, and
% taking $w = t + \sum m_i - 2$.}
% 
% \medskip
% Thus, we have the following values for the multiplicities
% $f(m)$, $m \ge 1$:
% 
% \begin{center}
% \begin{tabular}{r|rrrrrrrrrr}
% & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
% \hline
% 0 &  & 1 & 0 & 1 & 1 & 1 & 1 & 3 & 1 & 3 \\
% 10 & 3 & 5 & 3 & 5 & 5 & 11 & 3 & 5 & 5 & 11 \\
% 20 & 5 & 11 & 11 & 21 & 5 & 11 & 11 & 21 & 11 & 21 \\
% 30 & 21 & 43 & 5 & 11 & 11 & 21 & 11 & 21 & 21 & 43  \\
% 40 & 11 & 21 & 21 & 43 & 21 & 43 & 43 & 85 & 11 & 21 \\
% 50 & 21 & 43 & 21 & 43 & 43 & 85 & 21 & 43 & 43 & 85  \\
% \end{tabular}
% \end{center}
% 
% \medskip
% 
% Evidence for the decomposition into irreducibles:
% 
% It has been checked for $d \le 4$.
% 
% The dimensions of the irreducibles are known:
% 
% First, $\dim M(\lambda_d) = 2^d$.
% 
% The Weyl module $W(\lambda_m)$ for $\lambda_m$ has dimension
% ${2d \choose m} - {2d \choose m-2}$
% (Brouwer \cite{B}; Premet \& Suprunenko \cite{PS} did
% the odd characteristic case), and decomposition is as
% for the symmetric groups (Brouwer \cite{B}, cf. James \cite{J}):
% for $0 \le j \le m$ this module contains the irreducible $M(\lambda_j)$
% (with multiplicity 1) iff $m-j$ when written in binary
% is a subset of $2(d-j+1)$ written in binary.
% This determines $\dim M(\lambda_m)$.
% 
% Thus, the dimensions of the irreducible modules are
% as given below. The exponents are the conjectured multiplicities.
% The dimensions add up to $\dim U_d$ for $0 \le d \le 100$,
% so probably there is a theorem in number theory here.
% 
% \begin{center}
% \begin{tabular}{r|c|rrrrrrrrrr}
% $d$ & $\dim U_d$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
% \hline
% 0 & 1 & $1^1$ \\
% 1 & 2 & $1^0$ & $2^1$ \\
% 2 & 5 & $1^1$ & $4^0$ & $4^1$ \\
% 3 & 15 & $1^1$ & $6^1$ & $14^0$ & $8^1$ \\
% 4 & 51 & $1^1$ & $8^1$ & $26^1$ & $48^0$ & $16^1$ \\
% 5 & 187 & $1^1$ & $10^1$ & $44^1$ & $100^1$ & $164^0$ & $32^1$ \\
% 6 & 715 & $1^3$ & $12^1$ & $64^1$ & $208^1$ & $364^1$ & $560^0$ & $64^1$ \\
% 7 & 2795 & $1^1$ & $14^3$ & $90^1$ & $336^1$ & $910^1$ & $1288^1$ & $1912^0$ & $128^1$ \\
% 8 & 11051 & $1^3$ & $16^1$ & $118^3$ & $544^1$ & $1582^1$ & $3808^1$ & $4488^1$ & $6528^0$ & $256^1$ \\
% 9 & 43947 & $1^3$ & $18^3$ & $152^1$ & $780^3$ & $2906^1$ & $6972^1$ & $15504^1$ & $15504^1$ & $22288^0$ & $512^1$\\
% \end{tabular}
% \end{center}


\begin{thebibliography}{BCN}

\bibitem[BCN]{BCN} A. E. Brouwer, A. M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, Heidelberg, 1989.

\bibitem{BB} A. Blokhuis \& A. E. Brouwer,
{\it The universal embedding dimension of the near polygon
on the $1$-factors of a complete graph},
Des. Codes Cryptogr. {\bf 17} (1999) 299--303.

% \bibitem{BS} M. K. Bardoe \& Peter Sin,
% {\it The permutation modules for ${\rm GL}(n+1,{F}\sb q)$ acting
% on ${P}\sp n({F}\sb q)$ and ${F}\sp {n-1}\sb q$},
% J. London Math. Soc. (2) {\bf 61} (2000) 58--80. 

% \bibitem{B} A. E. Brouwer,
% {\it The composition factors of the Weyl modules with
% fundamental weights for the symplectic group},
% preprint, submitted 1992.
% Available at\\
% {\tt \verb#http://www.win.tue.nl/~aeb/preprints/isodim.tex.gz#} .

\bibitem{BCHW} A. E. Brouwer, A. M. Cohen, J. I. Hall \& H. A. Wilbrink,
{\it Near polygons and Fischer spaces},,
Geom. Dedic. 49 (1994) 349--368.

\bibitem{C} B. N. Cooperstein,
{\it On the generation of some dual polar spaces
of symplectic type over $GF(2)$},
Europ. J. Combin. {\bf 18} (1997) 741--749.

\bibitem{I} A. A. Ivanov,
Problem posed at the problem session of the Workshop on
Distance-Regular Graphs, 18-22 November 1996.

% \bibitem{J} G. D. James,
% {\it The representation theory of the symmetric groups},
% Lecture Notes in Math. 682, Springer, Berlin, 1978.

\bibitem{L} Paul Li,
{\it On the universal embedding of the $Sp_{2n}(2)$ dual polar space},
preprint, April 2000.

\bibitem{McC} Ph. McClurg,
{\it On the rank of certain incidence matrices over ${\rm GF}(2)$},
European J. Combin. {\bf 20} (1999) 421--427. 

% \bibitem{PS} A. A. Premet \& I. D. Suprunenko,
% {\it The Weyl modules and the irreducible representations of the
% symplectic group with the fundamental highest weights},
% Comm. Alg. 11(12) (1983) 1309--1342.

\bibitem{Y} S. Yoshiara,
{\it Embeddings of flag-transitive classical locally polar geometries
of rank 3}, Geometriae Dedicata {\bf 43} (1992) 121-165.

\end{thebibliography}

\end{document}
