Improved Upper Bound for the Size of a Trifferent Code

作者：Siddharth Bhandari, Abhishek Khetan · 年份：2024 · DOI：10.1109/isit57864.2024.10619477 · 被引用次数：1 · 研究领域：Algorithms and Data Compression、DNA and Biological Computing、Error Correcting Code Techniques

A subset$\mathcal{C} \subseteq\{0,1,2\}^n$is said to be a trifferent code (of block length$n$) if for every three distinct codewords$x, y, z \in \mathcal{C}$, there is a coordinate$i \in\{1,2, \ldots, n\}$where they all differ, that is,$\{x(i), y(i), z(i)\}=\{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 [Eli88], and is a longstanding 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 [Kur24]. We improve this bound to$T(n) \leq c \times n^{-2 / 5} \times(3 / 2)^n$where$c$is an absolute constant.