WE1.R7.4

Improved Upper Bound for the Size of a Trifferent Code

Siddharth Bhandari, Toyota Technological Institute at Chicago, United States; Abhishek Khetan, Indian Institute of Science, India

Session:
Combinatorics and Information Theory 1

Track:
21: Other topics

Location:
VIP

Presentation Time:
Wed, 10 Jul, 10:50 - 11:10

Session Chair:
Chaoping Xing, Shanghai Jiaotong University
Abstract
A subset $\calC\subseteq\set{0,1,2}^n$ is said to be a \emph{trifferent} code (of block length $n$) if for every three distinct codewords $x,y, z \in \calC$, there is a coordinate $i\in \set{1,2,\ldots,n}$ where they all differ, that is, $\set{x(i),y(i),z(i)}=\set{0,1,2}$. Let $T(n)$ denote the size of the largest trifferent code of block length $n$. Understanding the asymptotic behavior of $T(n)$ is closely related to determining the zero-error capacity of the $(3/2)$-channel defined by Elias~\cite{Elias1988}, and is a long-standing open problem in the area. Elias had shown that $T(n)\leq 2\times (3/2)^n$ and prior to our work the best upper bound was $T(n)\leq 0.6937 \times (3/2)^n$ due to Kurz~\cite{Kurz2023trifferent}. We improve this bound to $T(n)\leq c \times n^{-2/5}\times (3/2)^n$ where $c$ is an absolute constant.
Resources