Binary codes that are linear over the reals

105 Views Asked by At

Let $C\subseteq\{0,1\}^n$ be a binary code with distance $d$. We can embed $\{0,1\}^n$ into $\mathbb{R}^n$ in the natural way, and thus view $C$ as a subset of $\mathbb{R}^n$. We will then say that $C$ is $\mathbb{R}$-linear if $C=V\cap\{0,1\}^n$ for some linear subspace $V\subseteq\mathbb{R}^n$. In other words, any linear combination of codewords with real coefficients is also a codeword, provided the linear combination lands in $\{0,1\}^n$. Note that $C$ is not necessarily $\mathbb{F}_2$-linear.

I'm looking for non-trivial upper bounds the size of $\mathbb{R}$-linear binary codes. I'm specifically interested in the case where $d\geq \alpha n$ for some (small) constant $\alpha$. Concretely, I'm looking to prove the following: for any constant $\alpha>0$, there exists a constant $\beta>0$, such that all $\mathbb{R}$-linear binary codes $C$ with distance $d\geq \alpha n$ must satisfy $|C|\leq \beta$, regardless of $n$.

What I Know:

It is easy to construct $C$ with $|C|=2^{\lfloor n/d\rfloor}\approx 2^{1/\alpha}$ using the repetition code. Namely, partition the $n$ positions into $k:=\lfloor n/d\rfloor$ sets $S_j$ of size $\geq d$. For a vector $v\in\{0,1\}^k$, let $c(v)\in\{0,1\}^n$ be the vector such that $c_i(v)=v_j$ where $i\in S_j$. Let $C=\{c(v)\}_{v\in\{0,1\}^k}$. $C$ is $\mathbb{R}$-linear since the map $v\mapsto c(v)$ is a linear map from $\mathbb{R}^k$ into $\mathbb{R}^n$. $C$ also has distance $d$, since any two vectors differ in (at least) the positions in some $S_j$, which all have size at least $d$.

In the case $d=2$, there is a better construction where $|C|=\binom{n}{\lfloor n/2\rfloor}\approx (\sqrt{2/\pi})2^n/n^{1/2}$. Partition $[n]$ into two sets $S,T$, where $|S|=\lfloor n/2\rfloor$. Let $C\subseteq\{0,1\}^n$ be the total of entries in $S$ and $T$ are the same. This is a linear constraint, so $C$ is $\mathbb{R}$-linear. It also has distance 2, since any two vectors in $v$ must either have:
(1) the same totals for $S$ and $T$. In this case, they must differ in at least two elements of $S$, or at least two elements of $T$ (or both)
(2) Different totals for $S$ and $T$. But then they must differ by at least one element of $S$ and one element of $T$.
Based on doing a brute-force search over small examples, this construction seems optimal for $d=2$. But I don't know how to prove it. In fact, I don't know any upper bounds, except for the trivial ones that follow from $C$ being a binary code.