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 (or, equivalently, ), 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 . If the channel through which the message is being sent is perfect than it is easy to see that 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 elements, then as long as every code word differs by at least 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 (called a linear code), the decoding step is very efficient.
This motivates the question:
Given a distance and a dimension what is the dimension of the largest possible linear code with distance larger than ?
Asymptotically, if and grow such that is fixed the valued is conjectured to be
where is the binary entropy function, if and if . The Gilbert-Varshamov (GV) bound states that the value above is achievable, meaning that , 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 , what is the largest dimension of the largest possible linear code that does not intersect . The problem described above is then equivalent to consider , the Hamming ball of radius centered and punctured at (the set of all vectors with Hamming weight between and ).
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 , we are interested in constructing a linear map such that for , allows to determine if belongs to or , i.e., . An interesting question is to identify the least dimension for which linear classification is possible when the two classes are given. Asking for to classify the two classes is equivalent to asking its nullspace not to contain , so we are looking for the nullspace with largest dimension that avoids . This is an instance of the “critical problem” described above when .
A toy example of this is when the unknown vector 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 and , where . This means that the bright images are all vectors with at most black pixels, whereas the dark images are all vectors with at most white pixels. In this case, the set to be avoided is . It is not difficult to check that, in this case, the largest dimension is , corresponding to the vectors supported on the first coordinates.
In this work we were interested in symmetric sets, meaning a set 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 different types of symmetric Hamming balls, the one centered at and the one centered at , both of which were described above. This subject of this paper is a natural generalization of these sets, the annulus. Given , , and , we define the annulus as
and . When this reduces to the classical Hamming ball .
One can build a subspace that avoids by taking, as its basis, the first canonical basis elements and an optimal subspace with weight at least on the other coordinates, which means that
In this paper we investigate whether this bound is tight. This cannot be the case for all , , and : if is odd and is even it is easy to see that due to parity issues. We believe those to be the only degenerate cases. In fact, we show
Also, if is even, we have .
This motivated us to pose the following Conjecture, that I leave for the readers!
Conjecture ~ Theorem~1 holds for all .