{"id":"arxiv/2611.08230","url":"https://arxiv.org/abs/2611.08230","tags":["math.CO","cs.IT"],"score":0,"title":"The probabilistic bound for perfect hashing is sharp only for binary alphabets","domain":"math.CO","source":"arxiv","authors":["Shitao Li","Minjia Shi"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}