A coding theoretic application of the Alon-Füredi theorem

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 [n, k, d]_q code is a k-dimensional vector subspace of \mathbb{F}_q^n in which the minimum Hamming weight of vectors is equal to d. The elements of the vector subspace are known as codewords. The parameter n is known as the length of the code and d as its minimum distance which is related to the number of errors that can be corrected by the code (higher the value of d, higher the error-correcting capacity of the code). The main problem in coding theory is to obtain the largest possible value of k, given n, d, q and the smallest possible n given k, d, q. 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 \sigma(c) = \{i : c_i \neq 0\} is the support of a codeword c and c' is any codeword with \sigma(c') \subseteq \sigma(c) then c' = \lambda c for some \lambda \in \mathbb{F}_q. 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 [n, k, d]_q code, d \geq (q-1)(k - 1) + 1.

Theorem 2. In a minimal [n, k, d]_q code, n \geq (q + 1)(k - 1).

Here is their short proof of Theorem 1 using the Alon-Füredi bound.

Every codeword in a minimal code is also maximal. Let c be a non-zero codeword. Then c = u G, where G is the k \times n generator matrix and u is a non-zero vector in \mathbb{F}_q^k. Let f_i \in \mathbb{F}_q[x_1, \dots, x_k] be the linear polynomial given by c_i \cdot x = 0 where c_i is the i-th column of G. Consider the polynomial f = \prod_{i \in \sigma(c)} f_i. Then f(u) \neq 0, and in fact for any vector v, f(v) \neq 0 if and only if \sigma(c) \subseteq \sigma(v G), which by the maximality of c = uG is only possible if v = \lambda u for some \lambda. Therefore, f is non-zero at exactly q - 1 elements of \mathbb{F}_q^k. From the Alon-Füredi bound, we know that f is non-zero at at least (q - b)q^{k - a - 1} points where a, b are unique non-negative integers for which \deg f = a(q - 1) + b, and 1 \leq b \leq q - 1. From q - 1 \geq (q - b)q^{k - a - 1}, we can conclude that k - a - 1 = 0, and thus \deg f = (q - 1)(k - 1) + b \geq (q - 1)(k - 1) + 1. But note that \deg f is precisely the Hamming weight of c, and hence the minimum distance of the code is at least (q - 1)(k - 1) + 1. \square

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 n 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 \mathbb{F}_q^n), i.e., any polynomial f that vanishes on all points except one in \mathbb{F}_q^n has degree at least n(q-1) (see Theorem 22 in this or Theorem 3.7 in this).

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method and tagged , , , , , . Bookmark the permalink.

2 Responses to A coding theoretic application of the Alon-Füredi theorem

  1. Fedor Petrov says:

    Does generalized Alon-Füredi (“the minimal number of non-zero values of the non-zero polynomial p(x_1,\ldots,x_n) on the grid A_1\times A_2\times \ldots \times A_n under constraints which are upper bounds on deg(p) and deg_{x_i} (p) is attained on the product of monomials x_i-\rm const“) has applications of this sort for codes?

    • I don’t know applications of that result in the context of minimal codes. But it’ll be interesting to find some coding theoretic interpretation/application of those degree constraints. I’ll think about it, especially in the context of this new paper.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s