Answers are grounded in this paper and cite their sources.
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=-log₂(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.
No takes yet. Share an insight, caveat, or question.
Li et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: