About almost covering subsets of the hypercube

Abstract

Let $\mathbb{F}$ be a field, and consider the hypercube $\{0,1{\}}^n$ in ${\mathbb{F}}^n$. Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a polynomial $P(X_1,\dots ,X_n)\in \mathbb{F}[X_1,\dots ,X_n]$ vanishes on every point of the hypercube $\{0,1{\}}^n$ except those with at most $r$ many ones then the degree of the polynomial will be at least $n-r$. This is a generalization of Alon and Füredi's fundamental result (European Journal of Combinatorics 1993) about polynomials vanishing on every point of the hypercube except at the origin (point with all zero coordinates). Sziklai and Weiner proved their interesting result using Möbius inversion formula and the Zeilberger method for proving binomial equalities. In this short note, we show that a stronger version of Sziklai and Weiner's result can be derived directly from Alon and Füredi's result.

2 pages. Fixed a typo in the proof of Theorem 4. Results unchanged