Lower Bounds for Linear Hashing via Arithmetic Kakeya

Abstract

Affine modular linear hashing is one of the simplest classical hash families. For a prime $p>u$, the hash function is obtained by choosing $s,t$ uniformly from ${\mathbb{Z}}_p$ and mapping each key $x\in \{0,\dots ,u-1\}$ to one of $n$ bins by $h(x)=[(sx+t)\mathrm{mod}p]\mathrm{mod}n$. Despite its simplicity, the maximum load of linear hashing remains poorly understood. For $n$ keys hashed into $n$ bins, the best known upper bound is $O((n\log n{)}^{1/3})$, whereas the best known lower bound is only $\Omega (\log n/\log \log n)$. We prove a lower bound of $\exp (\Omega (\log n/\log \log n))$ for universes of size $n^{1+o(1)}$. Surprisingly, there is a key set for which this load holds not just in expectation, but for every random seed. The proof is driven by two simple reductions: one transfers lower bounds from a real version of linear hashing to modular linear hashing, and the other transfers arithmetic Kakeya constructions to real hashing. We further show that, for sufficiently large $p$, the expected maximum loads in the modular and real settings are essentially the same, giving an alternative route to an $n^{1/3+o(1)}$ upper bound. Finally, we show that any uniform subpolynomial upper bound for either setting would imply a polynomial-length arithmetic Kakeya conjecture and hence the Kakeya conjecture for upper Minkowski dimension.