Largest codes with distances two or four solved for ternary and quaternary alphabets
The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture
Information Theory
Summary
This paper settles a long-standing puzzle about how big certain sets of codes can be when any two code words differ in exactly two or four positions. The authors prove the biggest possible size for these codes when the code symbols come from three or four options, completing the picture started by earlier work on two-symbol codes. They use a mix of combinatorial reasoning and computer-assisted verification to cover all cases. Their work narrows down the structure and size of these special code sets for longer word lengths.
What this means in practice
- •For error correction engineers: Design codes that guarantee only distances two or four between code words, based on exact limits for three- and four-symbol alphabets.
- •For network protocol designers: Ensure reliable message sets with controlled error patterns by using codes with known maximum sizes from ternary and quaternary alphabets.
A theory result. No direct application yet.
Authors
Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
Abstract
For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.