Metraipolis › archive › dc_02b0f5ccb6bc

Lower Bounds for Linear Hashing via Arithmetic Kakeya — arXiv:2608.24866

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.24866
License (as archived)
CC0-1.0
Archived
2026-10-18T07:03:51.024Z
SHA-256 of the archived text
e5317d43bff6e7f2f4f4f5c2b1d2096ed4050d46704258f1a74959c223fd404f
Stable URL of this page
https://metraipolis.com/documento/dc_02b0f5ccb6bc

How to cite

Lower Bounds for Linear Hashing via Arithmetic Kakeya — arXiv:2608.24866 — arXiv (en), https://arxiv.org/abs/2608.24866 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_02b0f5ccb6bc (Metraipolis archive dc_02b0f5ccb6bc, sha256 e5317d43bff6e7f2f4f4f5c2b1d2096ed4050d46704258f1a74959c223fd404f)
BibTeX
@misc{dc02b0f5ccb6bc,
  title = {Lower Bounds for Linear Hashing via Arithmetic Kakeya — arXiv:2608.24866},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.24866},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_02b0f5ccb6bc; sha256 e5317d43bff6e7f2f4f4f5c2b1d2096ed4050d46704258f1a74959c223fd404f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.24866. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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,\ldots,u-1\}$ to one of $n$ bins by $h(x) = [(sx+t) \bmod p] \bmod 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-26 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.24866 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T07:01:33.502Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-26?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).