betaFeedback

WorksMathematics

The probabilistic bound for perfect hashing is sharp only for binary alphabets

Abstract

We investigate the optimal asymptotic rate RqR_q of perfect qq-hash codes, a fundamental extremal problem in combinatorics, information theory, and computer science. Let Bq=−log⁡2(1−q!/qq)/(q−1)B_q=-\log_2(1-q!/q^q)/(q-1) denote the classical probabilistic lower bound. We prove that Rq=BqR_q=B_q if and only if q=2q=2, establishing an explicit strict improvement for every q≥3q\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η>0, Rq≥Bq+exp⁡(−(2+η)q)R_q\ge B_q+\exp(-(2+η)q) for all sufficiently large integers qq. This improves the previously known increments of scale exp⁡(−3q+O(ln⁡q))\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 BqB_q by at most exp⁡(−3q+o(q))\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.

Paper details

vlnc:W_evm72ppv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…