Boolean annulus-avoiding subspace problem

This post is about a recent paper (announced today on the arxiv) by Emmanuel Abbe, Noga Alon, and I on an instance of Crapo and Rota’s “critical problem”. For the first time ever my last name only made me third author! That wasn’t the only “first”, it was also the first time I got Erdos number 2!

The problem considered is related to coding theory, so let me first write a lit bit about that. Every operation is taken over ${GF(2)}$ (or, equivalently, ${\mathbb{F}_2}$ ), the field of two elements. Let’s say one has to send, using a bit string, a message belonging to a certaint set of messages, the message book, with size ${C}$ . If the channel through which the message is being sent is perfect than it is easy to see that ${\lceil\log_2(C)\rceil}$ bits are sufficient, one simply assigns each message to a different bit string. From now one, we call each bit string we use (to encode the messages) a code word, and we call the collection of code words the code book. The question becomes more interesting if the channel adds errors to the string (by flipping some of its bits). Let’s say that we know for a fact that the channel does not flip more than ${s}$ elements, then as long as every code word differs by at least ${2s+1}$ elements from every other codeword the errors are very easy to correct — given the noisy string one simply needs to find the closest code in Hamming distance (Hamming distance between two bit strings is precisely the number of entries they differ in). This precisely the idea behind Error-correcting codes. Moreover, if the code book is a linear subspace of ${\mathbb{F}_2}$ (called a linear code), the decoding step is very efficient.

This motivates the question:

Given a distance ${d}$ and a dimension ${n}$ what is the dimension ${k(d,n)}$ of the largest possible linear code with distance larger than ${d}$ ?

Asymptotically, if ${d}$ and ${n}$ grow such that ${d/n}$ is fixed the valued is conjectured to be

$\displaystyle k(d,n) = n\left[ 1 - H\left(\frac{d}{n}\right)\right] + o(n),$

where ${H}$ is the binary entropy function, ${H(\delta) = -\delta\log_2(\delta) - (1-\delta)\log_2(1-\delta)}$ if ${\delta\in[0,1/2]}$ and ${H(\delta)=1}$ if ${\delta\in(1/2,1]}$ . The Gilbert-Varshamov (GV) bound states that the value above is achievable, meaning that ${k(d,n) \geq n H\left(\frac{d}{n}\right) + o(n)}$ , but the tightness of this bound remains one of the most important open problems in coding theory.

An instance of “the critical problem”, posed by Crapo and Rota, can be described as: Given a set ${S\subset \mathbb{F}_2^n}$ , what is the largest dimension ${K\left(S,\mathbb{F}_2^n\right)}$ of the largest possible linear code that does not intersect ${S}$ . The problem described above is then equivalent to consider ${S=B_0(d)\setminus\{0\}}$ , the Hamming ball of radius ${d}$ centered and punctured at ${0}$ (the set of all vectors ${x}$ with Hamming weight ${\omega(x)}$ between ${1}$ and ${d}$ ).

Another interesting instance of this problem arrises in the linear classification problem (I have been working on that problem on another context, I’ll post about it soon!). Let’s say that, given two disjoint classes ${S_1,S_2 \subseteq \{0,1\}^n}$ , we are interested in constructing a linear map ${M: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m}$ such that for ${x \in S_1 \sqcup S_2}$ , ${Mx}$ allows to determine if ${x}$ belongs to ${S_1}$ or ${S_2}$ , i.e., ${M S_1 \cap M S_2 = \emptyset}$ . An interesting question is to identify the least dimension ${m}$ for which linear classification is possible when the two classes are given. Asking for ${M}$ to classify the two classes is equivalent to asking its nullspace not to contain ${S_1+S_2}$ , so we are looking for the nullspace with largest dimension that avoids ${S_1+S_2}$ . This is an instance of the “critical problem” described above when ${S = S_1+S_2}$ .

A toy example of this is when the unknown vector ${x \in \mathbb{F}_2^n}$ represents the pixels of a black and white image. Let’s say there are two models for the image, the dark and bright images, modeled by the two Hamming balls ${S_1=B_1(s)}$ and ${S_2=B_0(s)}$ , where ${s < n/2}$ . This means that the bright images are all vectors with at most ${s}$ black pixels, whereas the dark images are all vectors with at most ${s}$ white pixels. In this case, the set to be avoided is ${S = B_1(s) + B_0(s) = B_1(2s)}$ . It is not difficult to check that, in this case, the largest dimension is ${n-2s-1}$ , corresponding to the vectors supported on the first ${n-2s-1}$ coordinates.

In this work we were interested in symmetric sets, meaning a set ${S}$ that is invariant under permutation of the entries. This implies that the set is characterized by the Hamming weights of its elements. There are only ${2}$ different types of symmetric Hamming balls, the one centered at ${0}$ and the one centered at ${1}$ , both of which were described above. This subject of this paper is a natural generalization of these sets, the annulus. Given ${n}$ , ${a}$ , and ${b}$ , we define the annulus ${A(a,b,n)}$ as

$\displaystyle A(a,b,n) = \left\{ x\in\mathbb{F}_2^n: a\leq \omega(x) \leq b \right\},$

and ${k(a,b,n) = K\left(A(a,b,n),n\right)}$ . When ${a=1}$ this reduces to the classical Hamming ball ${k(1,b,n) = k(b,n)}$ .

One can build a subspace that avoids ${A(a,b,n)}$ by taking, as its basis, the first ${a-1}$ canonical basis elements and an optimal subspace with weight at least ${b-1}$ on the other ${n-a}$ coordinates, which means that

$\displaystyle k(a,b,n) \geq a-1 + k(1,b,n) = a-1 + k(b,n).$

In this paper we investigate whether this bound is tight. This cannot be the case for all ${a}$ , ${b}$ , and ${n}$ : if ${a}$ is odd and ${n}$ is even it is easy to see that ${k(a,a,n) = n-1}$ due to parity issues. We believe those to be the only degenerate cases. In fact, we show

Theorem 1 ~ If ${a}$ , ${b}$ , and ${n}$ satisfy ${b\geq 2a-2}$ , then

$\displaystyle k(a,b,n) = a-1 + k(b,n-a+1).$

Also, if ${a>n/2}$ is even, we have ${k(a,a,n) = a-1}$ .