Paper 2026/1894

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes

Abstract

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the proximity-gaps property up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction—typically at most $\operatorname{poly}(n)/q$—of exceptional coefficients $z\in\mathbb{F}_q$ for which $f+zg$ is $\delta_1$-close to $C$. The work [BGKS20] shows that every linear code of relative distance $\delta$ satisfies proximity gaps up to the one-and-a-half Johnson radius \[ J_{3/2}(\delta)=1-(1-\delta)^{1/3}. \]We prove that this threshold is tight for general linear codes at every distance $0<\delta<1$. Specifically, for every $0<\delta<1$, we construct a linear code of relative distance arbitrarily close to $\delta$ and words $f,g\in\mathbb{F}_q^n$ that are both \[ 1-(1-\delta)^{4/9} \]far from the code, but for which a constant fraction of coefficients $z\in\mathbb{F}_q$ make $f+zg$ nearly $J_{3/2}(\delta)$-close to the code. Our counterexamples continue to hold even when a fixed amount of distance-dependent slack is allowed.