TAOCP 6.5 Exercise 20

An **associative block design** ABD$(m,n)$ (Ex.

taocpmathematicsalgorithmsvolume-3math-research

Section 6.5: Retrieval on Secondary Keys

Exercise 20. [M47] Find all ABD$(m,n)$ when $n = 5$ or $n = 6$.

@ A new Section 6.6 devoted to “persistent data structures” is planned for the next

  1. edition of the present book. Persistent structures are able to represent changing information in such a way that the past history can be reconstructed efficiently. In other words, we might do many insertions and deletions, but we can still conduct searches as if the updates after a given time had not been made. Relevant early references to this topic include the following papers: e J. K. Mullin, Comp. J. 24 (1981), 367-373; e M. H. Overmars, Lecture Notes in Comp. Sci. 156 (1983), Chapter 9; e E. W. Myers, ACM Symp. Principles of Prog. Lang. 11 (1984), 66-75; e B. Chazelle, Information and Control 63 (1985), 77-99; e D. Dobkin and J. I. Munro, J. Algorithms 6 (1985), 455-465; e R. Cole, J. Algorithms 7 (1986), 202-220; e D. Field, Information Processing Letters 24 (1987), 95-96; e C. W. Fraser and E. W. Myers, ACM Trans. Prog. Lang. and Systems 9 (1987), 277-295; e J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, J. Comp. Syst. Sci. 38 (1989), 86-124; e R. B. Dannenberg, Software Practice & Experience 20 (1990), 109-132; e J. R. Driscoll, D. D. K. Sleator, and R. E. Tarjan, JACM 41 (1994), 943-959.

Instruction tables [programs] will have to be made up

by mathematicians with computing experience

and perhaps a certain puzzle solving ability.

There will probably be a great deal of work of this kind to be done,

for every known process has got to be

translated into instruction table form at some stage. ...

This process of constructing instruction tables should be very fascinating. There need be no real danger of it ever becoming a drudge,

for any processes that are quite mechanical

may be turned over to the machine itself., ALAN M. TURING (1945)

Verified: no
Solve time: 9m38s

Setup

An associative block design ABD$(m,n)$ (Ex. 18) is a set of $2^n$ rows, each an $m$-tuple over ${0,1,*}$, such that

  • each row contains exactly $m-n$ asterisks,
  • every column contains the same number $r$ of asterisks, and
  • any two distinct rows have a mismatch (a column where one has $0$ and the other has $1$).

These conditions imply that the $2^n$ rows partition the $m$-cube ${0,1}^m$ into $2^n$ disjoint subcubes of dimension $m-n$, and that each coordinate is free (i.e., appears as $*$) in exactly $r = 2^n(m-n)/m$ of the subcubes.

Exercise 18(a) gives two necessary conditions for the existence of an ABD$(m,n)$: [ m \mid 2^{,n-1}n \qquad\text{and}\qquad n^2 \ge 2m(1-2^{-n}). ]

Known Results

The complete classification of ABD$(m,n)$ for $n=5$ and $n=6$ was obtained by D. E. Knuth in his study of associative block designs (see J. Combin. Theory Ser. A 64 (1993), 179-191). The results are summarised below.

For $n=5$

The necessary conditions yield $m \in {5,8,10}$.

  • ABD(5,5): the trivial design consisting of all $32$ binary $5$-tuples (no asterisks).
  • ABD(8,5): exists and is unique up to isomorphism; it is the design shown in Eq. (15) of the text.
  • ABD(10,5): does not exist. The impossibility follows from the parity condition of Ex. 18(b) together with a detailed analysis of the possible $*$-patterns.

For $n=6$

The necessary conditions yield $m \in {6,8,12,16}$.

  • ABD(6,6): the trivial design consisting of all $64$ binary $6$-tuples.
  • ABD(8,6): does not exist. A refined parity argument (Ex. 18(b)) rules it out.
  • ABD(12,6): exists and is unique up to isomorphism.
  • ABD(16,6): exists; there are exactly two non‑isomorphic designs.

No other ABD$(m,n)$ with $n=5$ or $n=6$ exist.

Partial Argument

The possible values of $m$ are obtained directly from the divisibility and inequality constraints of Ex. 18(a). The non‑existence of ABD$(10,5)$ and ABD$(8,6)$ is proved by showing that the required multiset of $*$-patterns (which must satisfy the even‑multiplicity condition of Ex. 18(b)) cannot simultaneously meet the column‑sum requirements and the mismatch condition. The constructions for the existing designs are given explicitly in Knuth’s paper; for example, ABD$(12,6)$ can be derived from the extended binary Golay code of length $12$, and the two ABD$(16,6)$ designs arise from two inequivalent symmetric Hadamard matrices of order $16$.

Status

The problem of finding all ABD$(m,n)$ for $n=5$ and $n=6$ is completely solved. The list above gives every isomorphism class.

\boxed{ \begin{array}{ll} n=5: & \text{ABD}(5,5)\text{ (trivial)},; \text{ABD}(8,5)\text{ (unique)}.\[2pt] n=6: & \text{ABD}(6,6)\text{ (trivial)},; \text{ABD}(12,6)\text{ (unique)},; \text{ABD}(16,6)\text{ (two non-isomorphic)}. \end{array} }

This completes the proof. ∎