A counterexample to a proximity gap conjecture

This is a solution to a problem discussed at the 2024 research workshop concerning Conjecture 2.4 of https://ia.cr/2023/630.

The following is known.

Theorem 1 (Diamond-Posen 2023). Let $C \subset {\mathbb{F}}_q^n$ be a linear code with distance at least $d$, and let $e < d/3$ be some parameter. Suppose that there is a line $\ell$ such that at least $e+2$ points on $\ell$ are at distance at most $e$ from $C$. Then, every point on $\ell$ is at distance at most $e$ from $C$.

It was asked whether the threshold of $d/3$ here is tight. We give a counterexample demonstrating that it is tight; that is, we give an example where $e=d/3$ and the conjecture does not hold.

Suppose $e \ge d/3$. Let $k=e+2$ (this will be the number of points on $\ell$ at distance at most $e$ from $C$, and can in fact be arbitrary). Then let $n=ke+2d$, and let $q > k$ be an arbitrary prime.

Define the vectors $a_i, b, c$ as follows (for $0 \le i < k$). Let $a_i$ have ones in indices $ie$ to $(i+1)e-1$ (zero-indexing), and zeroes elsewhere. Also, let $b$ have ones in indices $ke$ to $ke+d-1$, and $c$ have ones in indices $ke+d$ to $ke+2d-1$, and zeroes elsewhere. That is,

$$\begin{aligned} a_i &= (\underbrace{0, \dots, 0}_{ie}, \underbrace{1, \dots, 1}_{e}, \underbrace{0, \dots, 0}_{n-(i+1)e}), \\ b &= (\underbrace{0, \dots, 0}_{ke}, \underbrace{1, \dots, 1}_{d}, \underbrace{0, \dots, 0}_{d}), \\ c &= (\underbrace{0, \dots, 0}_{ke+d}, \underbrace{1, \dots, 1}_{d}) \end{aligned}$$ (Note that $a_i$, $b$, $c$ all have ones in disjoint sets of indices.)

Now, for $0 \le i < q$, define the vector $$\begin{aligned} u_i &= b + ic \\ &= (\underbrace{0, \dots, 0}_{ke}, \underbrace{1, \dots, 1}_{d}, \underbrace{i, \dots, i}_{d}). \end{aligned}$$ These vectors all lie on a line, so we let $\ell$ be the set of all $u_i$. Finally, we obtain vectors $v_i$, for $0 \le i < k$, by perturbing the $u_i$:

$$\begin{aligned} v_i &= a_i + u_i = a_i + b + ic \\ &= (\underbrace{0, \dots, 0}_{ie}, \underbrace{1, \dots, 1}_{e}, \underbrace{0, \dots, 0}_{(k-i-1)e}, \underbrace{1, \dots, 1}_{d}, \underbrace{i, \dots, i}_{d}). \end{aligned}$$

The code $C$ will then just be generated by the $v_i$: $$C = \mathop{\mathrm{span}}\{v_i\}_{0 \le i < k}.$$

For $0 \le i < k$, the vectors $u_i$ have distance at most $e$ from $v_i$, and therefore from $C$. It remains to check that $C$ has distance at least $d$, and that the other vectors $u_j$ have distance greater than $e$ from $C$.

Claim 2. $C$ has distance at least $d$.

Proof. Let $v \in C$ be nonzero; we will show that the Hamming weight of $v$ is at least $d$. Note that $v$ is the (nonzero) linear combination of some $v_i=a_i + b + ic$. If there are at most two $v_i$ in the linear combination, then the coefficient of either $b$ or $c$ must be nonzero, and thus $d$ of the last $2d$ entries must be nonzero, and we are done. Otherwise, there are at least three $v_i$, which means there are three $a_i$ with nonzero coefficients, and thus again at least $3e \ge d$ nonzero entries. Thus we are done. ◻

Claim 3. For $k \le j < q$, $u_j$ has distance at least $2e$ from $C$.

Proof. Let $v \in C$; we will show that $v$ has distance at least $2e$ from $u_j$. Note again that $v$ is the linear combination of some $v_i = a_i + b + ic$, for $0 \le i < k$. If there is only one vector in this linear combination, then it will be impossible for $v$ to have the same coefficients of $b$ and $c$ as $u_j$, so $v$ will have distance at least $d > 2e$ from $u_j$. Otherwise, there are two vectors in the linear combination, and thus there are two $a_i$ with nonzero coefficients, and thus $v$ will have distance at least $2e$ from $u_j$. ◻