Essential positive covers of the cube

Linial and Radhakrishnan introduced the following problem. A pair ( a , c ) with a ∈ R n and c ∈ R defines the hyperplane { x : ∑ i a i x i = c } ⊂ R n . Say that a collection of hyperplanes ( a 1 , c 1 ) , … , ( a m , c m ) is an essential cover of the cube { 0 , 1 } n if it is a cover, with no redundant hyperplanes, and every co-ordinate used: i.e., every point in { 0 , 1 } n is contained in some hyperplane; for every j ∈ [ m ] there exists x ∈ { 0 , 1 } n such that x is contained only in ( a j , c j ) ; and for every i ∈ [ n ] there exists j ∈ [ m ] with a i j ≠ 0 . What is the minimum size of an essential cover? Linial and Radhakrishnan showed that the answer lies between ( 4 n + 1 + 1 ) / 2 and ⌈ n / 2 ⌉ + 1 . We give a best possible bound for the case where a i j ⩾ 0 for every i , j . Additionally, we reduce the original problem to a conjecture concerning permanents of matrices.