\documentstyle[a4,12pt]{article}

\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}

\title{An associative block design $ABD(8,5)$}
\author{A. E. Brouwer}
\date{January 31, 1997}
\begin{document}
\maketitle

\centerline{Dedicated to Maja on the occasion of her 17th birthday.}

\medskip

\begin{abstract}
An associative block design is a certain balanced partition
of a hypercube into smaller hypercubes. We construct such a design,
thus settling the smallest open case.
\end{abstract}

An ${\rm ABD}(k,w)$ is a $b \times k$ matrix (where $b = 2^w$)
with entries from $\{0,1,*\}$ such that (i) the stars form a
1-design: each row has $k-w$ stars and each column $b(k-w)/k$ stars,
and (ii) the rows represent disjoint subsets of $\{0,1\}^k$.
Here a row represents the set of binary vectors of length $k$
obtained by replacing its stars in all possible ways by zeros and ones.

This concept was introduced in 1974 by Rivest \cite{R,R2}
in order to find a hash function with good worst-case
behaviour with respect to partial-match queries.

For example, the 8 rows
{\tt
\begin{tabular}{cc}
00*0 & 11*1 \\
100* & 011* \\
{}*100 & *011 \\
1*10 & 0*01 \\
\end{tabular}}
form an ${\rm ABD}(4,3)$.

In order to save space, let us extend our alphabet with
the minus sign, where a row containing $r$ minus signs
stands for the $2^r$ rows obtained by replacing these
minus signs in all possible ways by zeroes and ones.

Then the only other ${\rm ABD}(4,3)$ is the following:
{\tt
\begin{tabular}{c}
*000 \\
{}*111 \\
-*10 \\
-0*1 \\
-10* \\
\end{tabular}}

The theory is as follows (see \cite{Br,P,PvL,R}):

\begin{Proposition}

{\rm (i) (\cite{R})}
An ${\rm ABD}(k,w)$ has exactly $bw/(2k)$ zeros
and $bw/(2k)$ ones in each column.
In particular, $bw/(2k)$ is an integer.

{\rm (ii) (\cite{Br})}
In an ${\rm ABD}(k,w)$ with $w > 0$ any given star pattern
occurs in an even number of rows. Moreover, among the rows
with a given star pattern there are as many with an even
number of ones as with an odd number of ones.

{\rm (iii)}
For $w \le 4$ the only ${\rm ABD}(k,w)$ are the trivial
ones with $w = 0$ or $w = k$ (represented by a single row of
stars respectively minus signs only),
and the two examples shown above.

{\rm (iv) (\cite{P})}
If $w > 3$, then $k \le w(w-1)/2$.

{\rm (v) (\cite{PvL})}
There is no ${\rm ABD}(10,5)$.

{\rm (vi) (\cite{R})}
If ${\rm ABD}(k_i,w_i)$ exist for $i = 1,2$, then there
also is an ${\rm ABD}(k_1k_2,w_1w_2)$.

{\rm (vii) (\cite{Br})}
Suppose that $k \ge w > 0$ and $k' \ge w' > 0$ and
$k' \ge k$ and $w'/k' \ge w/k$. Then if an ${\rm ABD}(k,w)$
exists, and $2^{w'} w' / (2k')$ is an integer, then also
${\rm ABD}(k',w')$ exists.

\end{Proposition}

One may use generating function arguments to get more detailed
information on the possible star patterns. See \cite{Br}.

The purpose of this note is to show that an ${\rm ABD}(8,5)$ exists:

\begin{center}
{\tt
\begin{tabular}{cc}
{}-0000*** & {}*01*10*0 \\
{}-0001*** & {}-*1*1*11 \\
{}-001*0** & {}**11*001 \\
{}-**1010* & {}*10*00*0 \\
{}*0*1*110 & {}*1*0*001 \\
{}**01*111 & {}*100**11 \\
{}-**1110* & {}-1*0*10* \\
{}-*1*00*0 & {}*1**0110 \\
{}*010**01 & {}*1**1000 \\
{}-*1*0*11 & {}-1**1*10 \\
{}*010*1*0 & {}*101*0*1
\end{tabular}}
\end{center}

\medskip

Now the smallest open case is the question whether an ${\rm ABD}(12,6)$ exists.

\section*{Acknowledgement}
This note was inspired by a letter from Knuth, who asked
whether there had been any progress on ABDs since 1976,
and in particular, whether the existence of an ${\rm ABD}(8,5)$
was still open.

\begin{thebibliography}{}

\bibitem{Br} A. E. Brouwer
{\it On associative block designs\/},
pp. 173--184 in:
Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976),
Vol. I, Colloq. Math. Soc. J\'anos Bolyai 18,
North-Holland, Amsterdam, 1978.

\bibitem{P} J. A. La Poutr\'e,
{\it A theorem on associative block designs\/},
Discrete Math. {\bf 58} (1986) 205--208.

\bibitem{PvL} J. A. La Poutr\'e \& J. H. van Lint,
{\it An associative block design ${\rm ABD}(10,5)$
does not exist\/},
Utilitas Math. {\bf 31} (1987) 219--225.

\bibitem{R} R. L. Rivest,
{\it On hash-coding algorithms for partial match retrieval\/},
Proceedings of the 15th Annual Symposium on Switching and
Automata Theory, October 1974, pp. 95--103.

\bibitem{R2} R. L. Rivest,
Analysis of associative retrieval algorithms,
Laboratoire de recherche en informatique et automatique,
IRIA rapport 54, f\'evrier 1974.

\end{thebibliography}

\end{document}
