59 Communication Complexity — Func Hash
59.1 Overview
This module establishes a key probabilistic lemma for Newman’s theorem: a uniformly random hash function \(h : \alpha \to \mathrm{Fin}\, k\) collides on any two distinct inputs with probability at most \(1/k\). The argument proceeds by decomposing the collision event into \(k\) pairwise-disjoint pieces, measuring each piece, and summing.
59.2 Declarations
\(\texttt{HashSpace}\, \alpha \, k\) is the type of all functions \(\alpha \to \mathrm{Fin}\, k\), i.e. the space of hash functions on \(\alpha \) with output range \(\{ 0,\dots ,k-1\} \). Equipped with the product probability measure (uniform over each coordinate), it serves as the ambient probability space for the random-hash argument.
For \(x, y : \alpha \) and \(a : \mathrm{Fin}\, k\), \(\texttt{collisionPiece}\, k\, x\, y\, a\) is the set of hash functions \(h \in \texttt{HashSpace}\, \alpha \, k\) satisfying \(h(x) = a\) and \(h(y) = a\), i.e. the subset of the product space where both \(x\) and \(y\) are mapped to the fixed value \(a\). These pieces partition the collision event \(\{ h \mid h(x) = h(y)\} \).
For any \(x, y : \alpha \) and any \(k\),
For any \(x, y : \alpha \) and \(k\), the sets \(\texttt{collisionPiece}\, k\, x\, y\, a\) for \(a : \mathrm{Fin}\, k\) are pairwise disjoint: if \(a \ne b\) then \(\texttt{collisionPiece}\, k\, x\, y\, a \cap \texttt{collisionPiece}\, k\, x\, y\, b = \emptyset \).
For \(k \ge 1\) and any \(a : \mathrm{Fin}\, k\), the uniform measure of the singleton \(\{ a\} \subseteq \mathrm{Fin}\, k\) equals \(1/k\) as an extended non-negative real: \(\mu (\{ a\} ) = 1/k \in \mathbb {R}_{\ge 0}^\infty \).
For \(k \ge 1\) and any \(a : \mathrm{Fin}\, k\), the real-valued uniform measure of \(\{ a\} \) in \(\mathrm{Fin}\, k\) equals \(1/k \in \mathbb {R}\), i.e. \(\mu _{\mathbb {R}}(\{ a\} ) = 1/k\).
Let \(\alpha \) be a finite type, \(k \ge 1\), \(x \ne y \in \alpha \), and \(a : \mathrm{Fin}\, k\). Under the product measure on \(\texttt{HashSpace}\, \alpha \, k\),
Let \(\alpha \) be a finite type, \(k \ge 1\), and let \(x \ne y \in \alpha \). For a uniformly random hash function \(h : \alpha \to \mathrm{Fin}\, k\),
That is, \(\mu _{\mathbb {R}}\bigl(\{ h \in \texttt{HashSpace}\, \alpha \, k \mid h(x) = h(y)\} \bigr) \le 1/k\).