A note on Alon's combinatorial Nullstellensatz

Abstract. Alon's Combinatorial Nullstellensatz (Theorem 1.1 from [2]), and in particular the resulting nonvanishing criterion (Theorem 1.2 from [2]) is a very useful algebraic tool in combinatorics. It has several remarkable applications, see [4], [5], [7], [9], [10], [14], [15], for some recent examples. It is a theorem on polynomial functions on a discrete box \({\mathbf{S}}=S_1\times\dots\times S_n\), where \(S_i\), \(i=1,\dots,n\) are finite subsets of a field \(\mathbb{F}\). It is a natural question to ask: what other finite subsets \(X\subseteq\mathbb{F}\) allow a similar result? Here we characterize those sets \(X\subseteq \mathbb{F}^n\), whose vanishing ideal \(I(X)\) has a Gröbner basis similar to the Gröbner basis of \(I({\mathbf{S}})\).