Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_{\infty}$ sense. More concretely, consider a set $S\subset\mathbb{F}_{q}^{n}$ and a randomly chosen linear ${map}L:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}^{t}$ with q
^t
taken to be sufficiently smaller than $|S|$. Let U
S
denote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable $L(U_{S})$ is close to uniform in the $\ell_{\infty}$ norm. In other words, every element in the range $\mathbb{F}_{q}^{t}$ has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or $\ell_{1}$, distance (for a richer class of functions) as well as prior work on the expected largest ’bucket size’ in linear hash functions [1]. By known bounds from the load balancing literature [2], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.