arXiv preprint ·
The probabilistic bound for perfect hashing is sharp only for binary alphabets
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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\ge3$ 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\ge 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
A Universal Threshold Theory for Local Properties of Random Linear Codes
First-Order Model Checking on Monadically Dependent Graph Classes
All minimum cuts of symmetric submodular functions
Tusnády's problem and online two-sample thinning
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.