Essential Hyperplane Covers of the Boolean Cube

Definitions and mathematical statement

Using the conventional real-affine interpretation, let $H_i\subset{\mathbb{R}}^n$ be proper hyperplanes \[ H_i=\{x\in{\mathbb{R}}^n:a_i\cdot x=b_i\},\qquad a_i\ne0,\quad 1\leq i\leq m. \] They form an essential cover of $\{0,1\}^n$ with all variables represented when the following conditions hold:

1. Every cube vertex lies in some $H_i$.
2. For each $i$, there is a vertex $x_i\in\{0,1\}^n$ lying in $H_i$ and in no other $H_j$; thus removing $H_i$ destroys the cover.
3. For every coordinate $j\in\{1,\ldots,n\}$, some normal $a_i$ has $(a_i)_j\ne0$.

The last condition does not require every coefficient of every hyperplane to be nonzero. Define $f(n)$ as the minimum possible $m$ for such a cover. The source does not state the coefficient field, so the displayed real convention requires confirmation rather than replacement by a finite-field problem.

Determine $f(n)$, or narrow the gap recorded in the source as \[ \Omega(\sqrt n)\leq f(n)\leq n/2+1. \] The lower-bound notation means that some constants $c>0,n_0$ satisfy $f(n)\geq c\sqrt n$ for all integers $n\geq n_0$ in the intended range. The upper bound is reproduced literally. Its parity, integer rounding and small-$n$ range are not supplied; because $f(n)$ is an integer, these conventions matter, and no floor or ceiling correction is invented. For example, the literal bound at $n=1$ would need checking against the two distinct vertices, so it cannot automatically be read as an all-positive-$n$ statement.

The supplied assessment checked 2026-08-21 labels the problem open and says later work improves lower bounds without determining $f(n)$. No improved numerical formula is provided, so the displayed historical gap is not asserted to be the best currently available bound. The corrected-verified note reports normalization of the explicit covering function and gap.

Short English statement

Minimize the number of hyperplanes covering the Boolean cube, with a uniquely covered witness for each hyperplane and at least one nonzero coefficient for each coordinate. Preserve the supplied square-root versus linear gap, while flagging its missing parity and rounding conventions.

Sources

• Local UnsolvedMath registry, permanent ID 30001071, source code catalogue entry; supplied complete source record and corrected-verified notation note. Literature checked 2026-08-21: the assessment is supplied dated curation, not independently verified here.
• Discrete Geometry (2009), Oberwolfach Reports, DOI 10.4171/owr/2008/44, pp. 2477--2556: https://doi.org/10.4171/owr/2008/44. Proposed-year metadata gives 2008.
• New lower bounds for essential covers: https://arxiv.org/abs/2209.00140.