The Generalized Trifference Problem

We study the problem of finding the largest numberT(n,m) of ternary vectors of lengthnsuch that for any three distinct vectors there are at leastmcoordinates where they pairwise differ. This problem is a special case of the perfectk-hashing problem in theoretical computer science, corresponding to thek= 3 case. Form= 1, we get the classical trifference problem which is wide open. We prove upper and lower bounds onT(n,m) for various ranges of the parametermand determine the phase transition threshold onm=m(n) whereT(n,m) jumps from constant to exponential in n. By relating the linear version of this problem to a problem on blocking sets in finite geometry, we give explicit constructions and probabilistic lower bounds. We also compute the exact values of this function and its linear variation for small parameters. Moreover, we relate the trifference problem to the sunflower conjecture.