Improved Lower bound for hypercube edge slicing
Lisa Sauermann, Zixuan Xu · 2025
Read Improved Lower bound for hypercube edge slicing by Lisa Sauermann, Zixuan Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16592.txt.
Introduction
Lisa Sauermann and Zixuan Xu sharpen a slicing bound for cubes in a 2025 paper. A hypercube is a cube pushed into many dimensions, with corners at plus or minus one. A hyperplane is a flat slice through that space. A slice cuts an edge if it meets the edge at one inner point. The pair ask how few slices can cut all edges at once.
That question is more than fifty years old and still open. They prove a new floor on the count of slices for large sizes. Their floor beats the best past floor, set by Klein, by a clear power step. Log factors trim both bounds, but the power gain is the core win. Floor proofs show that cheap full cuts cannot exist.
Catalog record
| CREATOR | Lisa Sauermann, Zixuan Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16592
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Lower bound for hypercube edge slicing Thanks: University of Bonn, Germany. Email: [email protected] . Supported by the DFG Heisenberg Program. Thanks: Massachusetts Institute of Technology. Email: [email protected] Lisa Sauermann, Zixuan Xu Abstract . How many hyperplanes in ℝ n \mathbb{R}^{n} are needed in order to slice every edge of the n n -dimensional hypercube with vertex set { ± 1 } n \{\pm 1\}^{n} ? Here, we say that a hyperplane H ⊆ ℝ n H\subseteq\mathbb{R}^{n} slices an edge of the hypercube if it contains exactly one interior point of the edge. The problem of determining the minimum possible size of a collection of hyperplanes in ℝ n \mathbb{R}^{n} , such that every edge of the hypercube is sliced by at least one of these hyperplanes, is more than 50 years old and has been studied by many researchers. We prove that, for sufficiently large n n , at least Ω ( n 13 / 19 log − 32 / 19 n ) \Omega(n^{13/19}\log^{-32/19}n) hyperplanes are needed, improving upon the best previous lower bound Ω ( n 2 / 3 log − 4 / 3 n ) \Omega(n^{2/3}\log^{-4/3}n) due to Klein. 1. Introduction The n -dimensional hypercube has vertex set \{\pm 1\}^{n} and edges between pairs of vertices differing in exactly one coordinate. We say that a hyperplane H\subseteq\mathbb{R}^{n} slices an edge of the n -dimensional hypercube if H contains exactly one interior point of the edge. In other words, letting vv^{\prime} be an edge with endpoints v,v^{\prime}\in\{\pm 1\}^{n} and H be a hyperplane defined as H=\{x\in\mathbb{R}^{n}\mid\langle a,x\rangle=b\} , the hyperplane H is said to slice the edge vv^{\prime} if \langle a,v\rangle-b and \langle a,v^{\prime}\rangle-b are both nonzero and have different signs. It is natural to ask how many hyperplanes in \mathbb{R}^{n} are needed in order to slice every edge of the n -dimensional hypercube. More formally, what is the minimum possible size of a hyperplane collection \mathcal{H} in \mathbb{R}^{n} such that every edge of the n -dimensional hypercube \{\pm 1\}^{n} is sliced by at least one hyperplane in \mathcal{H} ? This problem has attracted the attention of many researchers over the past 50 years [ 10 , 7 , 5 , 1 , 12 , 6 ] , and has applications to the study of perceptrons [ 10 ] and of threshold circuits for parity [ 11 , 14 ] . It is conjectured that the minimum possible size of a hyperplane collection \mathcal{H} slicing every edge of the n -dimensional hypercube is \Theta(n) , and the current best known upper bound is \lceil(5/6)n\rceil given by a construction of Paterson (see [ 12 ] ). So far, this conjecture is only known to be true under some very specific assumptions on the form of the hyperplanes in \mathcal{H} . It is not hard to show that at least n hyperplanes are needed if for the hyperplanes one can choose normal vectors all of whose entries are non-negative, see [ 1 ] or [ 6 ] . The conjecture is also known to be true in the case where all hyperplanes in \mathcal{H} have normal vectors in \{1,-1\}^{n} following a result of Alon–Bergmann–Coppersmith–Odlyzko [ 2 ] . Recently, it was shown in [ 13 ] that the conjecture also holds when all hyperplanes have normal vectors in \{-C,\dots,C\}^{n} for a fixed integer C>0 . In the general setting, O’Neil [ 10 ] showed that any collection \mathcal{H} of hyperplanes slicing every edge of the hypercube must have size |\mathcal{H}|\geqslant\Omega(\sqrt{n}) . Yehuda and Yehudayoff [ 14 ] improved this lower bound to |\mathcal{H}|\geqslant\Omega(n^{0.51}) . A few years ago, Klein [ 9 ] showed |\mathcal{H}|\geqslant\Omega(n^{2/3}\log^{-4/3}n) , which has been the best known lower bound. In this paper, we improve upon this, showing the following new lower bound. Theorem 1.1 . Let \mathcal{H} be a collection of hyperplanes such that every edge of the n -dimensional hypercube \{\pm 1\}^{n} is sliced by some hyperplane in \mathcal{H} . For n sufficiently large, we have |\mathcal{H}|>\frac{n^{13/19}}{10^{11}\log^{32/19}n}. Theorem 1.1 also implies a new lower bound for the number of wires in depth-two threshold circuits computing the parity function, see [ 14 ] for more details. 1.1. Paper organization In Section 2 , we give a high-level overview of our proof highlighting the key steps and intuition. In Section 3 , we present definitions and probabilistic lemmas that will be used in our proof. Then in Section 4 , we give the proof of Theorem 1.1 assuming a key proposition ( 4.2 ). Finally in Section 5 , we provide the proof of 4.2 , completing the proof of Theorem 1.1 . 2. Proof Overview We start by outlining the main proof strategy, highlighting the key components of the proof. Our proof combines ideas from [ 14 ] and [ 9 ] together with several new ideas. Let \mathcal{H}=\{H_{1},\dots,H_{k}\} be the collection of hyperplanes, where H_{i}=\{x\in\mathbb{R}^{n}\mid\langle v_{i},x\rangle=\lambda_{i}\} has normal vector v_{i}=(v_{i1},\dots,v_{in})\in\mathbb{R}^{n} for each i\in[k] . Note that rescaling the coefficients of the hyperplane equation does not change the slicing properties of the hyperplane, so we may further assume without loss of generality that ||v_{i}||_{2}=1 for all i\in[k] . Then our goal is to find a point X\in[-1/2,1/2]^{n} that is far away from most of the hyperplanes. To be slightly more precise, we want to find X\in[-1/2,1/2]^{n} such that |\langle X,v_{i}\rangle-\lambda_{i}|>5\sqrt{\log n} holds for all but at most O(\sqrt{n}) indices i\in[k] . We can then randomly “round ” X\in[-1/2,1/2]^{n} to a vertex z\in\{\pm 1\}^{n} (to be precise, we take the entries z_{1},\dots,z_{n}\in\{\pm 1\} of z to be independent, with distributions chosen in such a way that \mathbb{E}[z_{i}]=X_{i} for each i ), and consider a uniformly random edge adjacent to z . We claim that with positive probability this edge is not sliced by any of the hyperplanes in \mathcal{H} . Indeed, with high probability, “rounding” X\in[-1/2,1/2]^{n} to a vertex z\in\{\pm 1\}^{n} changes the value of \langle X,v_{i}\rangle by no more than 3\sqrt{\log n} for each i\in[k] . So with high probability z\in\{\pm 1\}^{n} is at distance at least 2\sqrt{\log n} from all but at most O(\sqrt{n}) hyperplanes in \mathcal{H} (more precisely, we have |\langle z,v_{i}\rangle-\lambda_{i}|>2\sqrt{\log n} for all of the k-O(\sqrt{n}) hyperplanes H_{i}\in\mathcal{H} with |\langle X,v_{i}\rangle-\lambda_{i}|>5\sqrt{\log n} ). A hyperplane H_{i}\in\mathcal{H} at distance at least 2\sqrt{\log n} from z cannot slice any edge adjacent to z , because any adjacent vertex z^{\prime}\in\{\pm 1\}^{n} must satisfy |\langle z,v_{i}\rangle-\langle z^{\prime},v_{i}\rangle|\leqslant 2 , so \langle z,v_{i}\rangle-\lambda_{i} and \langle z^{\prime},v_{i}\rangle-\lambda_{i} cannot have different signs. So the only hyperplanes in \mathcal{H} possibly slicing any edge adjacent to z are the ones that are close to X . Using the Erdős–Littlewood–Offord theorem, one can show that a given hyperplane slices a uniformly random edge adjacent to the random rounding z of a given point X\in[-1/2,1/2]^{n} with probability at most O(1/\sqrt{n}) . Since there are at most O(\sqrt{n}) hyperplanes close to X , picking appropriate constants, a union bound implies that with positive probability a random edge adjacent to z is not sliced by any of the hyperplanes in \mathcal{H} . The details of this part are given in Section 4 . So far, the strategy described above was employed in both [ 14 ] and [ 9 ] . The key part of