The footprint bound

Studying the set of common zeros of systems of polynomial equations is a fundamental problem in algebra and geometry. In this post we will look at estimating the cardinality of the set of common zeros, when we already know that it is finite. In fact, with some extra theory one can also determine whether the set of zeros is finite or not.

My main motivation here is to popularise the so-called footprint bound, especially among combinatorialists (combinators?). As an application, we will see a nice “conceptual” proof of the so-called Alon-Füredi theorem, which is a result that in particular solves the following well-known geometric problem whose $3$ -dimensional case appeared as Problem 6 in IMO 2007:

Let $S$ be a finite subset of a field $F$ and let $a \in S^n$ . What is the minimum number of hyperplanes in $F^n$ that can cover all the points in $S^n$ , while missing the point $a$ ?

(The answer is $n(|S| - 1)$ .)

To be able to state the footprint bound we need some definitions. A monomial order is a total order on the set of all monomials in $F[x_1, \dots, x_n]$ which satisfies the property $u \leq v \implies uw \leq vw$ for any monomials $u, v, w$ . For example, we can look at the graded lexicographic order in which we first compare the total degree of the monomials and if that’s equal then we compare them lexicographically, i.e., for $u = (u_1, \dots, u_n)$ and $v = (v_1, \dots, v_n)$ we have $\prod x_i^{u_i} > \prod x_i^{v_i}$ if $\sum u_i > \sum v_i$ or if $\sum u_i = \sum v_i$ and the left-most non-zero entry of the vector $u - v$ is positive (so for example, we will have $x_1^2 x_2^3 \geq x_1^2 x_2 x_3^2$ ).

Now given a polynomial $f$ in $F[x_1, \dots, x_n]$ and a monomial ordering $\leq$ , we denote the largest monomial appearing in $f$ w.r.t. “ $\leq$ ” by $LM(f)$ (a.k.a. leading monomial). And if $J$ is an ideal of polynomials then we define $LM(J) = \{LM(f) : f \in J\}$ . Given an ideal $J$ , we are going to give an upper bound on the set $V(J) = \{x \in F^n : f(x) = 0~\forall f \in J\}$ . For that, let $\Delta(J)$ denote the set of those monomials which are not contained in the (monomial) ideal $\langle LM(J) \rangle$ (these are also known as standard monomials). Then this set $\Delta(J)$ is known as the footprint of the ideal $J$ .

Theorem 1 (Footprint bound [7], [5,§5.3]) If $\Delta(J)$ is finite, then we have $|V(J)| \leq |\Delta(J)|$ . Moreover, the bound is sharp if the ideal $J$ is radical.
Proof. Exercise! (show that $\Delta(J)$ is a basis of the vector space $F[x_1, \dots, x_n]/J$ .)

Of course, the usefulness of this bound (at least in combinatorial situations) depends on how easily we can calculate, or estimate, $|\Delta(J)|$ . Say $J$ is generated by $g_1, \dots, g_r$ and let $\Delta(g_1, \dots, g_r) = \{x^u : x^u \not \in \langle LM(g_i) \rangle ~\forall i\}$ . Then clearly $\Delta(J) \subseteq \Delta(g_1, \dots, g_r)$ , and since we have a finite list of monomials to check, with right choice of $g_i$ ‘s it can be easier to compute $\Delta(g_1, \dots, g_r)$ . Ideally, we would like $\Delta(J)$ to be equal to $\Delta(g_1, \dots, g_r)$ , and in fact this does happen when $g_1, \dots, g_r$ forms a Gröbner basis of $J$ (if you know what a Gröbner basis is; but you don’t really need to for the rest of this post). Let’s consider an example. Let $n = 2$ and $J = \langle x^2 y^3 - y, x^3y - x, x^4 - y^3, y^4 - xy^2 \rangle \subset F[x, y]$ , and consider the graded lexicographical order. Then the multiples of the leading monomials $x^2y^3, x^3y, x^4, y^4$ can be seen pictorially as follows:

grid_footprint

The monomials which are multiples of these four monomials, i.e. the monomials in the ideal generated by these leading monomials, correspond to the integer points in the shaded region. Therefore, the elements of $\Delta(x^2 y^3 - y, x^3y - x, x^4 - y^3, y^4 - xy^2)$ corresponds to the points in the unshaded region, and hence $|\Delta(J)| \leq |\Delta(x^2 y^3 - y, x^3y - x, x^4 - y^3, y^4 - xy^2)| = 12$ , which implies that these polynomials have at most $12$ common solutions (Wolfram Alpha tells me that there are in fact only $2$ ).

Say we are now interested in estimating the number of zeros of a polynomial $f \in F[x_1, \dots, x_n]$ contained in a finite grid $S = S_1 \times \cdots \times S_n$ , where $S_i \subseteq F$ , assuming that $f$ does not vanish on all points of $S$ . This is precisely what the Alon-Füredi theorem is all about. Let $s_i = |S_i|$ and $g_i = \prod_{a \in S} (x_i - a)$ . Then $g_i$ is a polynomial of degree $s_i$ , and the points of the $S$ are the common solutions of the polynomials $g_1, \dots, g_n$ . What we are interested in is $V(J)$ for $J = \langle f, g_1, \dots, g_n \rangle$ . For that we will first assume that $f$ is in its reduced form, so that $LM(f)$ (with respect to any monomial ordering) is of the form $\prod x_i^{u_i}$ where $0 \leq u_i \leq s_i - 1$ for all $i$ . We can always do this by reducing higher powers of $x_i$ by using the equation $g_i(x_i) = 0$ (the so-called grid reduction [3, Chapter 8]). Say $\deg (f) = d$ and $x^u = \prod x_i^{u_i}$ is the leading monomial of $f$ , with $\sum u_i = d$ . Then $\Delta(x^u, x_1^{s_i}, \dots, x_n^{s_n})$ is equal to the set of all monomials of the form $\prod x_i^{v_i}$ where there exists an index $j$ for which $v_j < u_j$ . The number of such monomials is in fact equal to $\prod s_i - \prod (s_i - u_i)$ because $\prod s_i$ is the total number of reduced monomials, and $\prod (s_i - u_i)$ of them are those which are multiples of $x^u$ . If we let $c_i = s_i - u_i$ , then we have $1 \leq c_i \leq s_i$ and $\sum c_i = (\sum s_i) - d$ , which directly implies the Alon-Füredi theorem:

Theorem 2 (Alon-Füredi [1, Theorem 5]) Let $f$ be a polynomial which does not vanish on the entire grid $S = S_1 \times \cdots \times S_n$ , then $f$ does not vanish on at least $\min \{ \prod c_i : 1 \leq c_i \leq s_i ~\forall i,~ \sum c_i = (\sum |S_i|) - \deg f\}$ points of $S$ .

Compared to the other proof of the Alon-Füredi theorem, I feel like this proof gives us a better understanding of where that bound comes from and “why” this theorem is true. Also, the same proof also gives the generalized version of the Alon-Füredi theorem [3, Theorem 9.1.2] (over fields). Moreover, one can also prove Alon’s combinatorial nullstellensatz using the footprint bound as follows.

Theorem 3 (Combinatorial Nullstellensatz) Let $f$ be such that $LM(x) = x^u$ with $u = (u_1, \dots, u_n)$ satisfying $u_i < |S_i|$ for all $i$ . Then there exists an $a \in S$ for which $f(a) \neq 0$ .
Proof. The size of the footprint of the ideal $I = \langle f, g_1, \dots, g_n \rangle$ is strictly less than $|S|$ since $u$ , being the exponent of a leading monomial, is not contained in it. Therefore by the footprint bound we have $|V(I)| < |S|$ , which implies that there is a point where $f$ does not vanish.

So, footprint bound is a nice algebraic result which has several interesting applications and extensions [2, 4, 6, 7, 8, 9, 10]. It is particularly useful for studying systems of polynomial equations over a finite field $\mathbb{F}_q$ , where we can take the grid $S$ to be equal to $\mathbb{F}_q^n$ . For further reading on this bound see the papers in the references below.

And now for the extra theory, here is a characterisation of systems of polynomial equations which have only finitely many common zeros (the so-called zero dimensional affine varieties over the algebraic closure of the field).

Theorem 4 ([5, Page 234]) Let $k$ be an algebraically closed field and let $V = V(I)$ be an affine variety in $k^n$ where $I$ is an ideal in $k[x_1, \dots, x_n]$ . Then the following statements are equivalent:

$V$ is a finite set.
For each $i$ , there exists some $m_i \geq 0$ such that $x_i^{m_i} \in \langle LM(I) \rangle$ .
Let $G$ be a Gröbner basis for $I$ . Then for each $i$ , there exists some $m_i \geq 0$ such that $x_i^{m_i} = LM(g_i)$ for some $g_i \in G$ .
The set $\Delta(I)$ is finite.
The $k$ -vector space $k[x_1, \dots, x_n]/I$ is finite-dimensional.

References

[1] N. Alon and Z. Füredi. Covering the cube by affine hyperplanes. European J. Combin., 14(2):79–83, 1993.
[2] P. Beelen, M. Datta, and S. R. Ghorpade. Vanishing ideals of projective spaces over finite fields and a projective footprint bound. arXiv:1801.09139.
[3] A. Bishnoi, Some contributions to incidence geometry and polynomial method, PhD Thesis (2016), Ghent University.
[4] C. Carvalho. On the second Hamming weight of some Reed–Muller type codes. Finite Fields Appl., 24:88–94, 2013.
[5] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007.
[6] O. Geil. On the second weight of generalized Reed-Muller codes. Designs, Codes and Cryptography, 48(3): 323-330, 2008.
[7] O. Geil and T. Høholdt. Footprints or generalized Bezout’s theorem. IEEE Trans- actions on Information Theory, 46(2):635–641, 2000.
[8] O. Geil and C. Thomsen. Weighted Reed–Muller codes revisited. Designs, Codes and Cryptography, 66(1):195–220, 2013.
[9] O. Geil and U. Martínez-Penãs. Bounding the number of common zeros of multivariate polynomials and their consecutive derivatives, arXiv:1707.01354.
[10] R. Pellikaan and X.-W. Wu. List decoding of q-ary Reed-Muller codes. IEEE Transactions on Information Theory, 50(4):679–682, 2004.

The footprint bound

About Anurag Bishnoi

1 Response to The footprint bound

Leave a comment Cancel reply

Recent Posts

Archives

Categories

Blogs I Follow

The footprint bound

Share this:

Related

About Anurag Bishnoi

1 Response to The footprint bound

Leave a comment Cancel reply

Recent Posts

Archives

Categories

Blogs I Follow