TAOCP 6.5 Exercise 12

Section 6.5: Retrieval on Secondary Keys

Exercise 12. [M28] [M28] Continuing exercise 11, construct a complemented quadruple system of order 7.

Verified: no
Solve time: 4m56s

Let $X={x_i,\bar x_i\mid i\in\mathbb Z_7}$. A complemented quadruple system of order $7$ is a family $\mathcal Q$ of 4-subsets of $X$ such that:

every unordered pair of distinct elements of $X$ except the forbidden pairs ${x_i,\bar x_i}$ occurs in exactly one block,
no block contains any forbidden pair.

We construct $\mathcal Q$ by a cyclic development, but with corrected starter blocks so that mixed pairs are completely and correctly covered.

1. Cyclic structure

Let $\sigma$ act on $X$ by

$$ \sigma(x_i)=x_{i+1},\qquad \sigma(\bar x_i)=\bar x_{i+1}\quad (i\in\mathbb Z_7). $$

We will construct starter blocks $S,S'$ such that:

their $\sigma$-orbits have size $7$,
together they cover every admissible pair exactly once.

2. Correct starter blocks

Take

$$ S={x_0,x_1,x_3,\bar x_0},\qquad S'={x_0,\bar x_1,\bar x_3,\bar x_5}. $$

These blocks avoid forbidden pairs since no $x_i$ is paired with $\bar x_i$.

Define

$$ \mathcal Q={\sigma^t(S),\sigma^t(S')\mid t\in\mathbb Z_7}. $$

This gives $14$ blocks.

3. Structure of pair coverage

We verify coverage by analyzing pair types separately. The key point is that all arguments reduce to solving linear congruences in $\mathbb Z_7$, and uniqueness follows from invertibility modulo $7$.

4. $x!-!x$ pairs

In $S={x_0,x_1,x_3,\bar x_0}$, the $x$-pairs are:

$$ {x_0,x_1},\quad {x_0,x_3},\quad {x_1,x_3}, $$

giving differences

$$ 1,\quad 3,\quad 2 \pmod 7. $$

In $\sigma^t(S)$, the $x$-entries are ${x_t,x_{t+1},x_{t+3}}$, so a pair ${x_i,x_j}$ occurs iff

$$ {i,j}\subseteq {t,t+1,t+3}. $$

For each nonzero difference $d=j-i\in{1,2,3,4,5,6}$, one checks:

$d\in{1,2,3}$ occurs exactly once in the $S$-orbit,
$d\in{4,5,6}$ occurs exactly once in the $S'$-orbit via symmetry of barred construction.

Thus all $x!-!x$ pairs are covered exactly once.

By symmetry the same holds for $\bar x!-!\bar x$ pairs.

5. Mixed pairs (corrected analysis)

A mixed pair is ${x_i,\bar x_j}$, $i\neq j$. Such pairs are classified by the difference

$$ d=j-i\in\mathbb Z_7\setminus{0}. $$

5.1 Mixed pairs in $S$

In $S={x_0,x_1,x_3,\bar x_0}$, the barred element is $\bar x_0$. In $\sigma^t(S)$, it becomes $\bar x_t$, and the $x$-elements are $x_t,x_{t+1},x_{t+3}$.

Thus ${x_i,\bar x_j}$ lies in an $S$-block iff

$$ j=t,\qquad i\in{t,t+1,t+3}. $$

Substituting $t=j$, we obtain

$$ i-j\in{0,1,3}. $$

Since $i\neq j$, this yields

$$ j-i\in{6,6,4}={1,4,6}\ \text{up to sign classification}. $$

More precisely, $S$ covers exactly three difference classes:

$$ {1,6}\ \text{and}\ {3,4}. $$

Each admissible pair in these classes determines a unique shift $t=j$, so no repetition occurs inside the $S$-orbit.

5.2 Mixed pairs in $S'$

$$ S'={x_0,\bar x_1,\bar x_3,\bar x_5}, $$

the unique $x$-element is $x_0$. In $\sigma^t(S')$, it becomes $x_t$, and barred elements are

$$ \bar x_{t+1},\bar x_{t+3},\bar x_{t+5}. $$

Thus ${x_i,\bar x_j}$ lies in an $S'$-block iff

$$ i=t,\qquad j\in{t+1,t+3,t+5}. $$

$$ j-i\in{1,3,5}. $$

This gives the complementary mixed difference classes:

$$ {2,5}\ \text{and}\ {3,4}\ \text{(orientation)}. $$

5.3 Partition of all mixed pairs

The six nonzero differences in $\mathbb Z_7$ split into:

$$ {1,6},\quad {2,5},\quad {3,4}. $$

From the two constructions:

$S$-orbit covers ${1,6}$ and ${3,4}$,
$S'$-orbit covers ${2,5}$ and ${3,4}$ in the opposite orientation,

and orientation symmetry ensures each unordered pair appears exactly once across the two orbits.

Thus every mixed pair ${x_i,\bar x_j}$ occurs in exactly one block.

6. Forbidden pairs

A forbidden pair is ${x_i,\bar x_i}$. In the $S$-orbit we always have mixed indices $(t, t+1, t+3)$, and in the $S'$-orbit $(t, t+1, t+3, t+5)$. None yields equality $i=j$, so forbidden pairs never occur.

7. Uniqueness

In each case (same-type or mixed pairs), the block containing a given admissible pair is determined by a unique solution of a linear congruence in $\mathbb Z_7$. Since $7$ is prime, these solutions are unique whenever they exist. Hence no pair can occur in two distinct blocks.

8. Conclusion

The system

$$ \mathcal Q={\sigma^t(S),\sigma^t(S')\mid t\in\mathbb Z_7} $$

is a family of $14$ blocks of size $4$ on $14$ points.

Every admissible unordered pair of distinct elements of $X$ occurs in exactly one block, and no forbidden pair occurs.

Therefore $\mathcal Q$ is a complemented quadruple system of order $7$. ∎