Essential covers of the cube by hyperplanes

Abstract

A set L of linear polynomials in variables X₁,X₂,...,X_n with real coefficients is said to be an essential cover of the cube {0,1}ⁿ if (E1) for each v∈{0,1}ⁿ, there is a p∈L such that p(v)=0; (E2) no proper subset of L satisfies (E1), that is, for every p∈L, there is a v∈{0,1}_n such that p alone takes the value 0 on v; (E3) every variable appears (in some monomial with non-zero coefficient) in some polynomial of L. Let e(n) be the size of the smallest essential cover of {0,1}ⁿ. In the present note we show that ̅η+1+1)≤e(n)≤⌈n/2⌉+1.