5
$\begingroup$

It would be useful to me to have a result of the following kind (which I would need to generalize, but this case is already interesting). Let $r<n$ be positive integers and let $\delta>0$ be a fixed constant such as 1/100. Does there exist a subspace $V$ of $\mathbb F_2^n$ that is a $\delta r$-separated $r$-net? That is, I would like every vector to have Hamming distance at most $r$ from some $v\in V$ and any two distinct vectors in $V$ to have distance at least $\delta r$ from each other.

This feels like the kind of thing that coding theorists ought to know about, but what comes up when I do a Google search is more to do with the dimension of $V$ than with whether it is a good net. But perhaps it comes into the "known to be hard" category.

I am interested in more or less the full range of $r$ for given $n$: the existence of such a linear code for some specific $r$ would be interesting but not enough for my eventual purposes.

$\endgroup$
2
  • $\begingroup$ since the answer states that linear vs nonlinear codes make no difference to your question, I was wondering what the direction of your generalization might be, if you don't mind sharing $\endgroup$
    – kodlu
    Commented Sep 30, 2019 at 21:42
  • $\begingroup$ Just to make sure you have heard of the coding theory terminology. If $V$ is a code, $r$ is called its covering radius - the balls of radius $r$ centered at the points of $V$ cover the whole space. The covering radius is a well-studied parameter. A lot is known about it for example for BCH-codes. Don't know if the range of parameters available from there fits your purposes that well. Coding theorists often want the covering radius to be small also. For efficiency. $\endgroup$ Commented Oct 20, 2019 at 10:01

2 Answers 2

12
$\begingroup$

Any maximal $r$-separated set is an $r$-net, otherwise you can augment it with a non-covered point.

But the same holds for linear codes! If a subspace $V$ is $r$-separated but not an $r$-net, you may take a far point $u$: then $\langle V,u\rangle$ is still $r$-separated. So a maximal $V$ fits.

$\endgroup$
1
  • 1
    $\begingroup$ Ah, thank you -- I missed that easy argument, despite being aware of similar arguments! I now need to think about the extent to which it can be generalized to give me what I want. $\endgroup$
    – gowers
    Commented Sep 28, 2019 at 21:11
2
$\begingroup$

As an example I describe what is known about the BCH-codes for the purposes of this question. Just to give an idea of the type of results that are known. I suspect that they are not very useful for the full range of parameters here.

Let us specify a natural number $m$, and let $n=2^m-1$. Let us further specify the parameter $t$ (=the number of bit errors the code can correct). The BCH-code (more accurately, a narrow sense, primitive BCH-code) with designed minimum distance $d_{des}=2t+1$ is a vector space $V(m,t)\subset \Bbb{F}_2^n$ has minimum Hamming distance $d_{min}\ge d_{des}$ and dimension $$k(m,t)=\dim V(m,t)\ge n-mt.$$ The other parameter of interest here is the covering radius $\rho(m,t)$ of $V(m,t)$. That is, the smallest integer $\rho$ such that every point of $\Bbb{F}_2^n$ is within Hamming distance $\rho$ of a vector from the subspace $V(m,t)$. Quite a bit is known about $\rho(m,t)$. This revolves around the solvability of systems of equations over $\Bbb{F}_{2^m}$.

  • In 1987 Tietäväinen proved that $\rho(m,t)\le 2t$ whenever $(2t-1)^{4t+2}\le 2^m$. This places a rather high demand on $m$, and that may prove to be the downfall of the use of BCH-codes here.
  • In most cases (and also asymptotically) the true covering radius is $\rho=2t-1$, a result of Vladuts & Skorobogatov. The length from which on this holds has been brought down by a number of authors since.
  • Usually $\rho\ge2t-1$ follows from the so called supercode lemma. That is easy to describe. We always have $V(m,t)\subseteq V(m,t-1)$. Whenever the inclusion here is strict, and the code $V(m,t-1)$ contains a vector $x$ of Hamming weight $2t-1$ (both of these are true often enough), then $x$ obviously cannot be at a distance $<2t-1$ from a vector of $V(m,t)$, proving the claim.
  • A bit of searching pointed me to a paper by F. Levy-dit-Vehel and S. Litsyn that appeared in IEEE Transactions on Information Theory, vol. 42(3) in May '96. They described the known results at that time.
  • So for BCH-codes the covering radius is often relatively close to the minimum distance (if it were higher, we could make the code bigger). Meaning that your parameter $\delta$ can be made close to $1$.
  • The catch is that the BCH-codes are known to be "asymptotically bad". From the inequality of the dimension we see that $t$ is usually bounded to be at most something like $n/\log_2n$. Also the bounds on $\rho$ don't apply to very small BCH-codes.

Another family of codes whose covering radii have been studied extensively consists of the Reed-Muller codes. The first order Reed-Muller codes in particular could be useful for your purpose.

The main reason you may not have found a lot of information is that for coding theoretical purposes, whenever $\rho>d_{min}$ the code becomes immediately non-interesting. I guess that's the content of Ilya Bogdanov's answer in different language.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .