Bounds on Trifferent Codes

Abstract

A trifferent code of length n is a subset of {0, 1, 2}ⁿ such that for any three distinct elements in it, there is a coordinate in which they all differ pairwise. The quantity T(n) denotes the largest size of such a code of length n. A motivation to study this problem comes from an application in information theory, where T(n) is related to the zero-error capacity of the (3/2)-channel, defined by Elias in 1988. This problem has seen renewed interest due to recently established connections between linear trifferent codes, strong blocking sets in projective geometry and minimal codes in coding theory.
In this thesis, we examine the most recent breakthrough in the upper bound of T(n) by Bhandari and Khetan, coming from r-bounded trifferent codes, which are trifferent codes with each codeword having exactly r many 2s. The quantity T_b(n,r) denotes the largest size of r-bounded trifferent codes of length n.
We generalize previous results by Bhandari and Khetan to give the upper bound T_b(n, r) ≤ c × n^r−2/5 for all r ≥ 3. We also build upon ideas given by Bishnoi and Kovács and prove the lower bound T_b(n, r) ≥ n^{⌈r/2⌉−o(1)} for all r ≥ 3 using special existing hypergraph constructions. In order to improve the lower bound for the quantity T_b(n, 2), we use a SAT solver to compute small-sized 2-bounded trifferent codes. With the help of these computations, we come up with two new constructions for 2-bounded trifferent codes which improve the prevailing (trivially obtained) lower bound of T_b(n, 2) ≥ 2n – 2 to T_b(n, 2) ≥ 2n (from Construction 1, in joint work with Jozefien D’haeseleer) and an even better
bound of T_b(n, 2) ≥ (20/9)n – O(1) (from Construction 2).