TAOCP 6.5 Exercise 16

Section 6.5: Retrieval on Secondary Keys

Exercise 16. [25] [25] (W. H. Kautz and R. C. Singleton.) Show that a Steiner triple system of order v can be used to construct v(v, 1)/6 codewords of v bits each such that no codeword is contained in the superposition of any two others.

17. [M30] Consider the following way to reduce (2n + 1)-bit keys a_n...do...@n to (n + 1)-bit bucket addresses bo... bn:

bo <, ao; if bk-1 = 0 then by < a_x else by + ax, for 1 <k <n.

a) Describe the keys that appear in bucket bo... bn. b) What is the largest number of buckets that need to be examined, in a basic query that has t bits specified?

18. [M35] (Associative block designs.) A set of m-tuples like (13), with exactly m, n *’s in each of 2” 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,7n) is impossible unless m is a divisor of 2”~'n and n? > 2m(1, 27").

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 complementing 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: yes
Solve time: 2m31s

---

Let $(V,\mathcal{B})$ be a Steiner triple system of order $v$, so each block $B \in \mathcal{B}$ has $|B|=3$ and every 2-element subset of $V$ lies in exactly one block. It follows that $|\mathcal{B}| = v(v-1)/6$.

For each block $B \in \mathcal{B}$, define its incidence vector $x^{(B)} \in {0,1}^v$ by

$$ x^{(B)}_i = \begin{cases} 1, & i \in B,\ 0, & i \notin B. \end{cases} $$

This yields $v(v-1)/6$ codewords of length $v$.

The superposition of two codewords is their bitwise OR, so $x^{(B)}$ is contained in the superposition of $x^{(C)}$ and $x^{(D)}$ if and only if

$$ B \subseteq C \cup D. $$

We must show that this cannot occur when $B, C, D$ are distinct blocks.

Assume for contradiction that $B, C, D \in \mathcal{B}$ are distinct and

$$ B \subseteq C \cup D. $$

Step 1: Intersection property in an STS

If $C \neq B$, then $|C \cap B| \le 1$.

Indeed, if $|C \cap B| \ge 2$, then $C$ and $B$ share a pair of distinct elements. In a Steiner triple system, every pair of elements lies in exactly one block, so this forces $C = B$, a contradiction. Hence $|B \cap C| \le 1$. Similarly,

$$ |B \cap D| \le 1. $$

Step 2: Covering the elements of $B$

Since $B \subseteq C \cup D$, every element of $B$ lies in at least one of $C$ or $D$. Therefore,

$$ B = (B \cap C) \cup (B \cap D). $$

Taking cardinalities and using the general inequality $|X \cup Y| \le |X| + |Y|$, we obtain

$$ |B| \le |B \cap C| + |B \cap D|. $$

From Step 1,

$$ |B \cap C| \le 1, \quad |B \cap D| \le 1, $$

hence

$$ |B| \le 2. $$

Step 3: Contradiction

But $|B| = 3$, so we obtain a contradiction.

Therefore no block $B$ is contained in the union of two distinct blocks $C \cup D$.

Conclusion

The incidence vectors of the blocks of a Steiner triple system of order $v$ form $v(v-1)/6$ binary codewords of length $v$, and no codeword is contained in the superposition (bitwise OR) of any two others. ∎