Linear $f\colon \mathbb{F}^t \to \mathbb{F}^s$ injective on any ball of radius $\epsilon t$?

Question

This may be well-known or trivial, but I cannot find any relevant pointer on the subject. Let $t\geq 1$ be an integer, and fix $\epsilon\in(0,1)$. I would like to find an integer $s=s(t,\epsilon)$ and a matrix $M\in\mathbb{F}_2^{s\times t}$ such that the (linear) transformation $$ f\colon x\in \mathbb{F}_2^t \mapsto Mx \in \mathbb{F}_2^s $$ is injective on each Hamming ball of radius $\epsilon t$; that is, if $x\neq y \in\mathbb{F}_2^t$ and $x,y$ differ on at most $\epsilon t$ coordinates, then $Mx\neq My$. The goal is to achieve this with $s$ being as small as possible.

Clearly, denoting by $V_{t,\ \epsilon}$ the volume of a Hamming ball of radius $\epsilon t$ in $\mathbb{F}_2^t$, one must have $$s\geq \log_2 V_{t,\ \epsilon} = h_2(\epsilon)t+o(t)$$ where $h_2$ is the binary entropy function. Is this lower bound tight (and if so, which $M$ would achieve it)?

Has anybody encountered this question (or a similar one) somewhere?

Thank you,

-- Clément.

Answer 1

Consider a $[N, K]$ linear code $\mathcal C$ over $\mathbb F_2$. Write the codewords as row vectors, and let $H$ denote the paritycheck matrix of the code. Then, $H$ is a $(N-K)\times N$ matrix and we have that $${\mathbf c} \in \mathcal C ~\text{if and only if}~~ \mathbf cH^T = \mathbf 0$$ where $\mathbf 0$ is the zero vector in $\mathbb F_2^{N-K}$. Note that $H$ is a linear map from $\mathbb F_2^N$ to $\mathbb F_2^{N-K}$.

For a given nonzero $\mathbf z \in \mathbb F_2^{N-K}$, the set of vectors $\mathbf x \in \mathbb F_2^N$ such that $\mathbb x H^T = \mathbb z$ is called a coset of the code. It is, of course, a translate of $\mathcal C$, and if the minimum Hamming distance of $\mathcal C$ is $D$, then any two vectors in the coset also are at Hamming distance $D$ or more from each other.

Turning to the OP's problem, if $\mathbf x, \mathbf y \in \mathbb F_2^N$ are at distance smaller than $D$ from each other, then they necessarily must belong to two different cosets of the code, and so it must be that $\mathbf xH^T \neq \mathbf yH^T$. With this as background, I believe that the OP is asking

For a given $N$ and $\epsilon = \frac{D}{N} \in (0,1)$, what is the largest $K$ such that a $[N,K,D]$ linear code over $\mathbb F_2$ exists, and how do I go about finding the paritycheck matrix $H$ of such a code?

People studying coding theory have looked at this problem extensively in the past but a complete solution is not known, except for some small values of $N$. See, for example, this tabulation for some results.