Almost covering all the layers of hypercube with multiplicities

Abstract

Given a hypercube ${\mathcal{Q}}^n:=\{0,1{\}}^n$ in ${\mathbb{R}}^n$ and $k\in \{0,\dots ,n\}$, the $k$-th layer ${\mathcal{Q}}_k^n$ of ${\mathcal{Q}}^n$ denotes the set of all points in ${\mathcal{Q}}^n$ whose coordinates contain exactly $k$ many ones. For a fixed $t\in \mathbb{N}$ and $k\in \{0,\dots ,n\}$, let $P\in \mathbb{R}\left[x_1,\dots ,x_n\right]$ be a polynomial that has zeroes of multiplicity at least $t$ at all points of ${\mathcal{Q}}^n\setminus {\mathcal{Q}}_k^n$, and $P$ has zeros of multiplicity exactly $t-1$ at all points of ${\mathcal{Q}}_k^n$. In this short note, we show that $$deg(P)\ge \max \left\{k,n-k\right\}+2t-2.$$Matching the above lower bound we give an explicit construction of a family of hyperplanes $H_1,\dots ,H_m$ in ${\mathbb{R}}^n$, where $m=\max \left\{k,n-k\right\}+2t-2$, such that every point of ${\mathcal{Q}}_k^n$ will be covered exactly $t-1$ times, and every other point of ${\mathcal{Q}}^n$ will be covered at least $t$ times. Note that putting $k=0$ and $t=1$, we recover the much celebrated covering result of Alon and Füredi (European Journal of Combinatorics, 1993). Using the above family of hyperplanes we disprove a conjecture of Venkitesh (The Electronic Journal of Combinatorics, 2022) on exactly covering symmetric subsets of hypercube ${\mathcal{Q}}^n$ with hyperplanes. To prove the above results we have introduced a new measure of complexity of a subset of the hypercube called index complexity which we believe will be of independent interest. We also study a new interesting variant of the restricted sumset problem motivated by the ideas behind the proof of the above result.

16 pages, substantial changes from previous version, title and abstract changed to better reflect the content of the paper

References in corpus (2)

• Exact hyperplane covers for subsets of the hypercube
• Restricted Variable Chevalley-Warning Theorems