Beating the Probabilistic Lower Bound on q-Perfect Hashing

In this paper, we investigate the achievable rate of perfect hash code. For an integer q >= 2, a perfect q-hash code C is a block code over [q] := {1,..., q} of length n in which every subset {c(1), c(2),..., c(q)} of q elements is separated, i.e., there exists i is an element of[n] such that {proj(i) (c(1)),..., proji (cq)} = [q], where proji (c j) denotes the ith position of c j. Finding the maximum size M(n, q) of perfect q-hash codes of length n, for given q and n, is a fundamental problem in combinatorics, information theory, and computer science. In this paper, we are interested in asymptotic behavior of this problem. Precisely speaking, we will focus on the quantity R-q := lim sup(n ->infinity) log2 M(n,q)/n. A well-known probabilistic argument shows an existence lower bound on Rq, namely R-q >= 1 /q-1 log(2) (1/1-q!/q(q) ) (Fredman and Komlos, SIAM J Algebr Discrete Methods 5(1):61-68, 1984; Korner, SIAM J Algebr Discrete Methods 7(4):560-570, 1986). This is still the best-known lower bound till now except for the case q = 3 (Korner and Marton, Eur J Comb 9(6):523-530, 1988). The improved lower bound of R-3 was discovered in 1988 and there has been no progress on the lower bound of R-q for more than 30 years. In this paper we show that this probabilistic lower bound can be improved for q from 4 to 15 and all odd integers between 17 and 25, and all sufficiently large q.