## 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).

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?