The probabilistic bound for perfect hashing is sharp only for binary alphabets
Abstract
We investigate the optimal asymptotic rate Rq of perfect q-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let Bq=−log2(1−q!/qq)/(q−1) denote the classical probabilistic lower bound. We prove that Rq=Bq if and only if q=2, establishing an explicit strict improvement for every q≥3 and settling the first assertion of a conjecture of Xing and Yuan (Combinatorica 43 (2023), 347--366). More significantly, we show that, for every η>0, Rq≥ Bq+exp(−(2+η)q) for all sufficiently large integers q. This improves the previously known increments of scale exp(−3q+O(ln q)) by an exponential factor. We also establish a structural limitation of the concatenation method. For pairwise uniform inner codes of subexponential length, the resulting rate bound exceeds Bq by at most exp(−3q+o(q)). Thus, exponentially long inner codes are necessary to achieve the new improvement scale within this framework. Our proofs combine Fourier analysis, high-dimensional simplex codes, additive permutation counts, and entropy bounds for hypergraph matchings. We further strengthen lower bounds from short inner codes and improve several known numerical estimates.
Related
- Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
- Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling
- Maximal Center of Distances of Finite Ultrametric Spaces and Perfect Binary Trees
- A proof of the Braun-Etzion-Vardy bound for binary subspace codes
- Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
BibTeX
@misc{li2026probabilistic,
title = {{The probabilistic bound for perfect hashing is sharp only for binary alphabets}},
author = {Shitao Li and Minjia Shi},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08230},
eprint = {2611.08230},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08230},
}
RIS
TY - UNPB
TI - The probabilistic bound for perfect hashing is sharp only for binary alphabets
AU - Shitao Li
AU - Minjia Shi
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08230
UR - https://arxiv.org/abs/2611.08230
AB - We investigate the optimal asymptotic rate R_q of perfect q-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let B_q=−log_2(1−q!/q^q)/(q−1) denote the classical probabilistic lower bound. We prove that R_q=B_q if and only if q=2, establishing an explicit strict improvement for every q≥3 and settling the first assertion of a conjecture of Xing and Yuan (Combinatorica 43 (2023), 347--366). More significantly, we show that, for every η>0, R_q≥ B_q+exp(−(2+η)q) for all sufficiently large integers q. This improves the previously known increments of scale exp(−3q+O(ln q)) by an exponential factor. We also establish a structural limitation of the concatenation method. For pairwise uniform inner codes of subexponential length, the resulting rate bound exceeds B_q by at most exp(−3q+o(q)). Thus, exponentially long inner codes are necessary to achieve the new improvement scale within this framework. Our proofs combine Fourier analysis, high-dimensional simplex codes, additive permutation counts, and entropy bounds for hypergraph matchings. We further strengthen lower bounds from short inner codes and improve several known numerical estimates.
ER -