Section 6.5: Retrieval on Secondary Keys

Exercise 7. [M24] [M24] (R.L. Rivest.) Find the functions L(t), as defined in the previous exercise, for the following combinatorial hash functions:

(a) m=3,n=2 (b) m=4,n=2 00*-0 00*««-0 1O0>1 1lx0751 *1l1l, -2 lll, -2 101-3 101l, 2 010-3 *1l01>3

100*, +3

Verified: no
Solve time: 3m59s

---

The fundamental issue in the proposed solution is not computational but logical: it replaces the given combinatorial specification with an invented complete function. Once that step is disallowed, there is no legitimate basis for any numerical evaluation of $L(t)$.

A correct solution must therefore start from the definition and use only those consequences that are logically forced by the given rule fragments. If the fragments do not determine a unique function, then $L(t)$ is not a well-defined numerical answer for the corrupted input as written.

1. What $L(t)$ actually depends on

Let $f:{0,1}^m \to {0,\dots,n}$. For a $t$-specified query $Q\subseteq {0,1}^m$ (a subcube obtained by fixing $t$ coordinates), define

$$ L_Q = \left| f(Q) \right|. $$

Then

$$ L(t) = \frac{1}{#{\text{(t)-queries}}} \sum_Q L_Q. $$

Thus, $L(t)$ depends only on how the domain is partitioned into level sets $f^{-1}(y)$, and how those level sets intersect coordinate subcubes.

Crucially:

• One cannot compute $L(t)$ without knowing the induced partition of ${0,1}^m$.
• Partial or wildcard rules must determine this partition uniquely or up to invariance of all relevant intersections.

2. Critical correction to the previous approach

The previous solution failed at this step:

It assumed a full truth table consistent with partially corrupted rules.

This is invalid because:

1. The rule fragments are not formally parseable as constraints on all $2^3$ inputs.
2. Multiple completions of the unspecified entries are possible.
3. Different completions generally produce different values of $L(t)$, since $L(t)$ depends on set cardinalities of images of subcubes.

Therefore, the computation of $L(t)$ from a guessed completion does not answer the exercise.

3. What can be concluded for part (a), $m=3, n=2$

The provided fragments (even after careful normalization of OCR noise) are insufficient to uniquely determine:

• the values of $f(x)$ for all $x \in {0,1}^3$, or
• the induced equivalence classes $f^{-1}(y)$.

In particular:

• Several wildcard patterns overlap inconsistently in the transcription.
• At least one constraint of the form “pattern $\to$ value” is not unambiguously associated with a full set of inputs.
• There is no reliable way to determine whether conflicts are intended or artifacts of corruption.

Hence:

The induced partition of ${0,1}^3$ is not uniquely determined.

Since $L(t)$ is a functional of that partition, it follows that:

$$ \boxed{\text{(L(t)) for part (a) is not well-defined from the given corrupted specification.}} $$

4. What can be concluded for part (b), $m=4, n=2$

The situation in part (b) is strictly worse:

• The rule system is even more corrupted.
• No consistent extraction of a complete or partial constraint system is possible.
• There is not even a stable set of forced equalities between inputs.

Therefore:

$$ \boxed{\text{(L(t)) for part (b) cannot be determined from the provided data.}} $$

5. Proper resolution if the original statement were intact

In a correctly formatted Rivest combinatorial hash specification, the intended method is:

1. Interpret each rule with wildcards as fixing a constant value on a subcube of ${0,1}^m$.
2. Verify that overlapping rules are consistent.
3. Deduce the induced partition of the domain into value classes.
4. For each $t$-subcube, compute how many partition classes intersect it.
5. Average over all $t$-subcubes to obtain $L(t)$.

That procedure requires a fully specified and consistent rule set, which is not recoverable here.

6. Final conclusion

The original solution’s error was not computational but structural: it replaced an underdetermined combinatorial specification with an arbitrary completed function, which invalidates all subsequent results.

With the given corrupted data, the correct mathematical conclusion is:

$$ \boxed{ \text{The specification is insufficient to determine } L(t) \text{ for either part (a) or (b).} } $$