Covering almost all the layers of the hypercube with multiplicities.

Given a hypercube Q n : = { 0 , 1 } n in R n and k ∈ { 0 , ... , n } , the k -th layer Q k n of Q n denotes the set of all points in Q n whose coordinates contain exactly k many ones. For a fixed t ∈ N and k ∈ { 0 , ... , n } , let P ∈ R [ x 1 , ... , x n ] be a polynomial that has zeroes of multiplicity at least t at all points of Q n ∖ Q k n , and P has zeros of multiplicity exactly t − 1 at all points of Q k n. In this short note, we show that d e g (P) ≥ max ⁡ { k , n − k } + 2 t − 2. Matching the above lower bound we give an explicit construction of a family of hyperplanes H 1 , ... , H m in R n , where m = max ⁡ { k , n − k } + 2 t − 2 , such that every point of Q k n will be covered exactly t − 1 times, and every other point of 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 (1993) [1]. Using the above family of hyperplanes we disprove a conjecture of Venkitesh (2022) [23] on exactly covering symmetric subsets of hypercube 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. [ABSTRACT FROM AUTHOR]