The Alon-Füredi theorem is something that I have written a lot about in this blog. I spent a considerable amount of time on this theorem during my PhD. In fact, it’s generalisation that I obtained and it’s applications in finite geometry (blocking sets), coding theory (Reed-Muller codes), and computer science (polynomial identity testing), constitute my most cited paper. I have recently learned another nice coding theoretic application of this result, which I would like to share in this post.
Coding theory is an important branch of mathematics with wide ranging applications, like data compression, transmission, storage. One of the main object studied in this area is a linear code. An code is a -dimensional vector subspace of in which the minimum Hamming weight of vectors is equal to . The elements of the vector subspace are known as codewords. The parameter is known as the length of the code and as its minimum distance which is related to the number of errors that can be corrected by the code (higher the value of , higher the error-correcting capacity of the code). The main problem in coding theory is to obtain the largest possible value of , given and the smallest possible given . Some of the fundamental bounds for these problems are the Hamming bound, the Singleton bound and the Griesmer bound. Some famous examples of codes that are optimal w.r.t. these bounds are the Hamming code, Golay code, and Reed-Solomon codes. Along with being useful in practice, these codes are also related to beautiful and deep mathematical theories. Here is a nice introduction to the subject by Venkatesan Guruswami.
The study of codes with certain extra restrictions has also developed because of some specific examples. One such restriction, is that every codeword is minimal, in the sense that if is the support of a codeword and is any codeword with then for some . Such minimal codewords have been used in secret sharing schemes and decoding algorithms. Here is an early paper discussing some properties of minimal codewords. Naturally, one expects that minimal codes will have stronger bounds on their parameters. That’s precisely where Alon-Füredi shows up. In a recent paper, Alfarano, Borello, Neri and Ravagnani have applied this theorem and related results to prove the following:
Theorem 1. In a minimal code, .
Theorem 2. In a minimal code, .
Here is their short proof of Theorem 1 using the Alon-Füredi bound.
Every codeword in a minimal code is also maximal. Let be a non-zero codeword. Then , where is the generator matrix and is a non-zero vector in . Let be the linear polynomial given by where is the -th column of . Consider the polynomial Then , and in fact for any vector , if and only if , which by the maximality of is only possible if for some . Therefore, is non-zero at exactly elements of . From the Alon-Füredi bound, we know that is non-zero at at least points where are unique non-negative integers for which , and . From , we can conclude that , and thus . But note that is precisely the Hamming weight of , and hence the minimum distance of the code is at least .
The proof of Theorem 2 is slightly more involved than Theorem 1, and so I refer you to the paper for that. The same proof appears in this recent paper in a geometric language. Note that one can derive lower bounds on using Singleton bound or the Griesmer bound in combination with Theorem 1, but these are weaker than the bound in Theorem 2.
Interestingly, Theorem 1 can also be proved via the main Alon-Füredi theorem, instead of the Alon-Füredi bound (which is in fact a result of Jamison and Brouwer-Schrijver when applied to ), i.e., any polynomial that vanishes on all points except one in has degree at least (see Theorem 22 in this or Theorem 3.7 in this).