TAOCP 6.5 Exercise 13

Let $m = 2n$ and let $V = \mathbb{F}_2^m$, so $|V| = 2^m = 4^n$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.5: Retrieval on Secondary Keys

Exercise 13. [M25] [M25] Construct quadruple systems with v = 4” elements, analogous to the triple system of exercise 9.

Verified: yes
Solve time: 2m25s

Let $m = 2n$ and let $V = \mathbb{F}_2^m$, so $|V| = 2^m = 4^n$. We construct blocks that are exactly the affine 2-dimensional subspaces of $V$.

Construction

For any $x \in V$ and any linearly independent vectors $a,b \in V$ (over $\mathbb{F}_2$), define the block

$$ B(x;a,b) = {x,; x+a,; x+b,; x+a+b}. $$

Let $\mathcal{B}$ be the set of all such blocks.

Step 1: Each block has 4 distinct elements

Since $a \neq 0$ and $b \neq 0$, we have $x \neq x+a$, $x \neq x+b$. If $x+a = x+b$, then $a=b$, contradicting linear independence. Also $x+a+b \neq x$ because $a+b \neq 0$ when $a$ and $b$ are distinct nonzero vectors in characteristic $2$. Similarly $x+a+b$ differs from $x+a$ and $x+b$. Hence each block has four distinct elements.

Step 2: Every triple is contained in at least one block

Let $u,v,w \in V$ be distinct. Define

$$ a = v-u,\quad b = w-u. $$

Then $a \neq 0$, $b \neq 0$, and $a \neq b$ since $v \neq w$. Over $\mathbb{F}_2$, this implies $a,b$ are linearly independent.

Now set $x = u$. Then

$$ x+a = v,\quad x+b = w,\quad x+a+b = u + (v-u) + (w-u) = u+v+w. $$

Thus ${u,v,w} \subseteq B(u; v-u, w-u)$. So every 3-subset is contained in at least one block.

Step 3: Key structural fact (the fourth point is forced)

Let $u,v,w$ be distinct and consider any block containing them. We show the fourth element is uniquely determined.

From Step 2, the natural candidate is

$$ t = u+v+w. $$

We verify this is intrinsic to any block.

Take any block

$$ B(x;a,b) = {x,\ x+a,\ x+b,\ x+a+b} $$

and suppose $u,v,w \in B(x;a,b)$. Then $u,v,w$ are three distinct elements of this set. In $\mathbb{F}_2$,

$$ x + (x+a) + (x+b) + (x+a+b) = 0, $$

so the sum of all four elements in any block is $0$. Hence in any such 4-set, the fourth element equals the sum of the other three.

Therefore, if $u,v,w$ are three elements of a block, the remaining element must be

$$ u+v+w. $$

So any block containing ${u,v,w}$ must contain exactly the set

$$ {u,v,w,u+v+w}. $$

Step 4: Uniqueness of the block

We now show there is exactly one block containing ${u,v,w}$.

Define

$$ t = u+v+w. $$

Then the set

$$ A = {u,v,w,t} $$

is an affine 2-dimensional subspace:

$$ A = u + \mathrm{span}{v-u,\ w-u}. $$

Since $v \neq u$, $w \neq u$, and $v-u \neq w-u$, the vectors $v-u$ and $w-u$ are linearly independent over $\mathbb{F}_2$, hence they generate a unique 2-dimensional subspace. Therefore there is a unique affine 2-plane containing $u,v,w$, namely $A$.

But every block in $\mathcal{B}$ is exactly an affine 2-plane, and conversely every affine 2-plane has the form $B(x;a,b)$. Hence there is exactly one block containing ${u,v,w}$, namely

$$ {u,\ v,\ w,\ u+v+w}. $$

Step 5: Conclusion

  • Each block has 4 elements.
  • Every 3-subset of $V$ is contained in a block.
  • The fourth element is uniquely determined as $u+v+w$, so the block containing any triple is unique.

Thus $(V,\mathcal{B})$ is a Steiner quadruple system on $4^n$ points. ∎