Improved Upper Bounds for Slicing the Hypercube
This work addresses a combinatorial geometry problem in theoretical computer science and mathematics, providing incremental improvements to long-standing bounds.
The paper tackles the problem of slicing all edges of an n-dimensional hypercube with the minimum number of hyperplanes, proving an improved upper bound of S(n) ≤ ⌈4n/5⌉, except for odd multiples of 5 where it is S(n) ≤ 4n/5 + 1, which beats the previous bound of S(n) ≤ ⌈5n/6⌉ from 1971.
A collection of hyperplanes $\mathcal{H}$ slices all edges of the $n$-dimensional hypercube $Q_n$ with vertex set $\{-1,1\}^n$ if, for every edge $e$ in the hypercube, there exists a hyperplane in $\mathcal{H}$ intersecting $e$ in its interior. Let $S(n)$ be the minimum number of hyperplanes needed to slice $Q_n$. We prove that $S(n) \leq \lceil \frac{4n}{5} \rceil$, except when $n$ is an odd multiple of $5$, in which case $S(n) \leq \frac{4n}{5} +1$. This improves upon the previously known upper bound of $S(n) \leq \lceil\frac{5n}{6} \rceil$ due to Paterson reported in 1971. We also obtain new lower bounds on the maximum number of edges in $Q_n$ that can be sliced using $k<n$ hyperplanes. We prove the improved upper bound on $S(n)$ by constructing $8$ hyperplanes slicing $Q_{10}$ aided by the recently introduced CPro1: an automatic tool that uses reasoning LLMs coupled with automated hyperparameter tuning to create search algorithms for the discovery of mathematical constructions.