Asymptotically Sharp Length Thresholds for \texorpdfstring{$q$}{q}-ary Codes with Distances \texorpdfstring{$2$}{2} and \texorpdfstring{$4$}{4}

Abstract

For an integer $q\ge 5$, let $A_q(n,\{2,4\})$ be the largest cardinality of a subset of a $q$-ary Hamming space of length $n$ in which every two distinct words have distance $2$ or $4$. Set \[ N(q)=\left\lceil\max\left\{2q+1, \frac{17+\sqrt{8q^2+96q-95}}2\right\}\right\rceil. \] We prove that $A_q(n,\{2,4\})=1+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ for every $n\ge N(q)$. In particular, $N(q)=2q+1$ for $q\ge 26$. An explicit code of size $q(n-2)$ shows that the least eventual threshold $N_{\ast }(q)$ satisfies $N_{\ast }(q)\ge 2q-1$; consequently $2q-1\le N_{\ast }(q)\le 2q+1$ for every $q\ge 26$. The argument applies to arbitrary integer alphabet sizes, without a linearity assumption. Its main ingredients are synchronization of symbols on intersecting supports, weighted bounds for $2$-intersecting families of four-sets, and a joint estimate for the weight-two and weight-four layers in a common-three-core configuration. No computational verification is required.