For fixed integers$n$and$b\geq k$, let$A(b,k,n)$the largest size of a subset of$\{1,2,\ldots,b\}^{n}$such that, for any$k$distinct elements in the set, there is a coordinate where they all differ. Bounding$A(b,k,n)$is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of$(b, k)$-hash families of functions. It is known that, for fixed$b$and$k$,$A(b,k,n)$grows exponentially in$n$. In this paper, we determine new exponential upper bounds for different values of$b$and$k$. A first bound on$A(b,k,n)$for general$b$and$k$was derived by Fredman and Komlós in the ’80s and improved for certain$b\neq k$by Körner and Marton and by Arikan. Only very recently better bounds were derived for general$b$and$k$by Guruswami and Riazanov, while stronger results for small values of$b=k$were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of$b$and$k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions.

For fixed integers$b\geq k$, the problem of perfect$(b,\ k)$-hashing asks for the asymptotic growth of largest subsets of$\{1, 2, \ldots, b\}^{n}$such that for any$k$distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general, was derived by Fredman and Komlós in the ‘80s and improved for certain by Körner and Marton and by Arikan. Only very recently better bounds were derived for the general case by Guruswami and Riazanov, while stronger results for small values of were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to and further strengthen the bounds for some specific small values of and. The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity.