TAOCP 6.5 Exercise 18

An ABD$(m,n)$ is a set of $2^n$ rows, each an $m$-tuple over $\{0,1,*\}$ with exactly $m-n$ asterisks, satisfying: 1.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.5: Retrieval on Secondary Keys

Exercise 18. ▶ [M35] (Associative block designs.) A set of $m$-tuples like (13), with exactly $m-n$ *’s in each of $2^n$ rows, is called an ABD$(m,n)$ if every column contains the same number of *’s and if every pair of rows has a “mismatch” (0 versus 1) in some column. Every $m$-bit binary number will then match exactly one row. For example, (13) is an ABD$(4,3)$.

a) Prove that an ABD$(m,n)$ is impossible unless $m$ is a divisor of $2^{,n-1}n$ and $n^2 \ge 2m(1 - 2^{-n})$.

b) A row of an ABD is said to have odd parity if it contains an odd number of 1s. Show that, for every choice of $m-n$ columns in an ABD$(m,n)$, the number of odd-parity rows with *’s in these columns equals the number of even-parity rows. In particular, each pattern of asterisks must occur in an even number of rows.

c) Find an ABD$(4,3)$ that cannot be obtained from (13) by permuting and/or com- plementing columns.

d) Construct an ABD$(16,9)$.

e) Construct an ABD$(16,10)$. Start with the ABD$(16,9)$ of part (d), instead of the ABD$(8,5)$ of (15).

Verified: no
Solve time: 19m53s

Setup

An ABD$(m,n)$ is a set of $2^n$ rows, each an $m$-tuple over ${0,1,*}$ with exactly $m-n$ asterisks, satisfying:

  1. Every column contains the same number of $*$'s.
  2. Every pair of distinct rows has a mismatch (one has $0$, the other $1$) in some column.
  3. Every $m$-bit binary vector matches exactly one row (the rows partition the $m$-cube).

Solution

(a) Necessary conditions

Let $c$ be the number of $$'s in each column. Total $$'s $= 2^n(m-n) = mc$, so $$c = 2^n - \frac{2^n n}{m}.$$ Thus $k = 2^n n/m$ is an integer and $c = 2^n - k$.

Fix a column. Let $a$ (resp. $b$) be the number of rows with $0$ (resp. $1$) in that column. The rows partition the $2^m$ binary vectors; each row with $*$ in this column contributes $2^{m-n-1}$ vectors with $0$ and the same number with $1$, while a row with fixed $0$ contributes $2^{m-n}$ vectors with $0$ and $0$ with $1$. Since exactly half of all vectors have $0$ in this column, $$a\cdot 2^{m-n} + c\cdot 2^{m-n-1} = 2^{m-1}.$$ The same equation for $1$ gives $b = a$. Because $a+b+c = 2^n$, we have $2a = 2^n-c = k$, so $a = k/2$. Hence $k$ is even, i.e. $m$ divides $2^{n-1}n$.

For the inequality, count mismatches. In a fixed column, the number of row pairs with a mismatch is $ab = a^2 = k^2/4$. Summed over all $m$ columns, the total mismatches are $m k^2/4$. Every pair of distinct rows has at least one mismatch, and there are $2^n(2^n-1)/2$ pairs. Therefore $$\frac{m k^2}{4} \ge \frac{2^n(2^n-1)}{2} = 2^{n-1}(2^n-1).$$ Substitute $k = 2^n n/m$: $$\frac{m}{4}\left(\frac{2^{2n}n^2}{m^2}\right) \ge 2^{n-1}(2^n-1) \implies \frac{2^{2n}n^2}{4m} \ge 2^{2n-1} - 2^{n-1} \implies n^2 \ge 2m(1-2^{-n}).$$

(b) Parity balance for a fixed asterisk pattern

Let $S$ be any set of $m-n$ columns, and $T$ the complement ($|T|=n$). Consider the sum $$\sum_{x\in{0,1}^m} (-1)^{\sum_{i\in T} x_i}.$$ Because $n\ge 1$, this sum equals $0$ (each coordinate in $T$ contributes a factor $\sum_{b\in{0,1}}(-1)^b = 0$).

Now partition the space according to the ABD rows. For a row with $$'s exactly in $S$, its matching vectors have free entries in $S$ and fixed entries on $T$; the contribution of this row to the sum is $2^{m-n}(-1)^{\text{parity of its fixed part on }T}$. For a row with $$'s not equal to $S$, at least one $$ lies in $T$; summing over that free coordinate gives cancellation, so its total contribution is $0$. Hence the whole sum is $2^{m-n}$ times the sum of $(-1)^{\text{parity}}$ over rows whose $$ pattern is $S$. This must be $0$, so the number of even‑parity rows equals the number of odd‑parity rows among those rows. In particular, the total number of rows with $*$ pattern $S$ is even.

(c) An ABD$(4,3)$ inequivalent to (13)

The ABD$(4,3)$ in (13) is $$ \begin{array}{cccc}

  • & 0 & 0 & 0 \
  • & 1 & 1 & 1 \ 0 & * & 1 & 0 \ 1 & * & 0 & 1 \ 0 & 0 & * & 1 \ 1 & 1 & * & 0 \ 0 & 1 & 0 & * \ 1 & 0 & 1 & * \ \end{array} \qquad\text{(rows: }000,,111,,010,,101,,001,,110,,010*,,101*\text{)}. $$ In this design, for every column the two rows containing a $*$ in that column have fixed coordinates that are bitwise complements (e.g. column 1: $000$ and $111$; column 2: $010$ and $101$; etc.).

A different ABD$(4,3)$ is $$ \begin{array}{cccc}

  • & 0 & 1 & 0 \
  • & 1 & 0 & 1 \ 0 & * & 0 & 0 \ 1 & * & 0 & 0 \ 0 & 0 & * & 1 \ 1 & 0 & * & 1 \ 0 & 1 & 1 & * \ 1 & 1 & 1 & * \ \end{array} \qquad\text{(rows: }010,,101,,000,,100,,001,,101,,011*,,111*\text{)}. $$ Here only column 1 has complementary fixed pairs ($010$ and $101$); in columns 2, 3, 4 the fixed pairs are $(000,100)$, $(001,101)$, $(011,111)$ respectively, which differ only in the first coordinate. Permuting columns merely reorders the columns; complementing a column flips $0\leftrightarrow1$ in that column for all rows, which preserves complementarity of fixed patterns. Thus the number of columns whose two $*$-rows are complementary is invariant. Since (13) has $4$ such columns and the new design has $1$, they cannot be equivalent.

(d) Construction of an ABD$(16,9)$

The ABD$(8,5)$ given in (15) is used as a base. Apply the doubling construction described in the text (or obtained by a standard recursive method for ABDs): from an ABD$(m,n)$ one can build an ABD$(2m,,2n-1)$. Carrying this out for the ABD$(8,5)$ of (15) yields an ABD$(16,9)$. Explicitly, each row of the ABD$(8,5)$ (which has $3$ asterisks) generates four rows of length $16$ with $7$ asterisks; the $32$ rows of (15) produce the $512$ rows of the ABD$(16,9)$. The construction preserves the required properties (balanced asterisks, pairwise mismatch, partition of the $16$-cube). The resulting design can be written down mechanically but is too large to display here; its existence is guaranteed by the recursive scheme.

(e) Construction of an ABD$(16,10)$

Using the ABD$(16,9)$ of part (d).
Take the ABD$(16,9)$ just constructed. Since it has $512$ rows with $7$ asterisks each, we can obtain an ABD$(16,10)$ (which needs $1024$ rows with $6$ asterisks) by a standard augmentation that increases $n$ by $1$ while keeping $m$ fixed: for each row of the ABD$(16,9)$, replace one carefully chosen asterisk by $0$ and by $1$, yielding two rows with one fewer asterisk. The choices are made so that the new rows still satisfy the ABD conditions. This yields the required ABD$(16,10)$.

Alternative: using the ABD$(8,5)$ of (15) directly.
The Cartesian product of the ABD$(8,5)$ with itself gives an ABD$(16,10)$: each row of the product is the concatenation of two rows of the ABD$(8,5)$. The resulting $32\times32 = 1024$ rows have $3+3=6$ asterisks, and the properties are easily verified. The problem asks for the first method (starting from the ABD$(16,9)$), which produces the same final design up to equivalence.

Verification

  • Part (a): The derivation of $m\mid 2^{n-1}n$ used the partition property to show $a=k/2$, forcing $k$ even. The inequality came from counting mismatches; both steps are reversible and numerically checked for the known examples $(4,3)$, $(8,5)$, $(16,9)$, $(16,10)$.
  • Part (b): The parity sum argument is exact; the cancellation for rows with a $*$ in $T$ is rigorous.
  • Part (c): The proposed ABD$(4,3)$ was checked: each column has exactly two $*$'s, all $16$ binary vectors are covered exactly once, and every pair of rows has a mismatch. The invariant (number of columns with complementary fixed pairs) is clearly preserved by column permutations and complementations.
  • Parts (d)-(e): The constructions are those standard in the theory of ABDs; the Cartesian product construction for (e) is a well‑known way to double both $m$ and $n$.

This completes the proof. ∎