🤖 AI

Improved Upper Bounds for Slicing the Hypercube

This paper improves the known upper bound for the minimum number of hyperplanes required to slice all edges of an $n$ -dimensional hypercube from $\lceil 5n/6 \rceil$ to approximately $4n/5$ , a result achieved by constructing a specific solution for $n=10$ using the CPro1 tool that combines reasoning LLMs with automated hyperparameter tuning.

Original authors: Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Slicing a 10-Dimensional Cube

Imagine you have a giant, perfect cube made of wire. In our normal 3D world, a cube has 12 edges. Now, imagine this cube exists in 10 dimensions. This "hypercube" has thousands of edges (specifically, 5,120 of them).

The mathematical challenge the authors tackled is this: What is the minimum number of flat sheets (hyperplanes) you need to cut through this 10D cube so that every single wire edge is sliced in half?

If you slice an edge, the sheet must pass right through the middle of the wire, not just touch the end.

The Old Record vs. The New Record

For over 50 years, the best anyone could do was a rule of thumb established in 1971 by a mathematician named Paterson. His rule said: "To slice a cube of size $n$ , you need roughly $5/6$ of $n$ sheets."

For a 10-dimensional cube, Paterson's rule said you needed 9 sheets to guarantee every edge was cut.

The Breakthrough:
The authors in this paper found a way to do it with only 8 sheets.

Old Way: You needed 9 planes.
New Way: You only need 8 planes.

They proved that for almost any size of hypercube, you can slice it all with roughly $4/5$ of the dimension number (or even fewer), which is a significant improvement over the old $5/6$ limit.

How Did They Do It? (The Human + AI Team-Up)

This is where the story gets interesting. The authors didn't just sit down and solve this with a pencil and paper. They used a "team effort" between human mathematicians and a specific type of Artificial Intelligence called CPro1.

Think of the problem like trying to find a specific needle in a haystack the size of a galaxy.

The Human Role: The humans set up the rules and acted as the "detectives." They knew that previous attempts had failed because the search space was too huge. They also noticed a pattern in the AI's partial successes: the best solutions seemed to have a lot of repetition (like a pattern where the first few numbers in a list are always the same).
The AI Role: The AI (CPro1) acted as a "super-fast generator." It wrote thousands of different computer programs (algorithms) to try and find the solution. It tried different strategies, like "simulated annealing" (a method that cools down a solution to find the best one) and "hill climbing" (climbing up a hill to find the highest peak).
The Collaboration: The AI generated a massive list of "almost good" solutions. It couldn't quite find the perfect 8-sheet solution on its own. However, the humans looked at the AI's "almost good" attempts, spotted the hidden pattern (the repetition), and manually tweaked the search rules to force the AI to look in that specific area. Once the humans gave the AI that nudge, the AI quickly found the perfect 8-sheet solution.

The Analogy: Imagine you are looking for a hidden treasure. The AI is a robot that can dig 10,000 holes a minute but doesn't know where to dig. The human is the map-reader. The robot digs everywhere and says, "Hey, I found a lot of dirt that looks like it might be near the treasure." The human looks at the dirt, realizes, "Aha! The treasure is always under the red rocks," and tells the robot, "Only dig under red rocks now." The robot then instantly finds the treasure.

The "Reduced Hypercube" Trick

To make the search faster, the authors used a clever math trick called the Reduced Hypercube.

Imagine you have a giant, complex maze. Instead of trying to solve the whole maze at once, you realize that many parts of the maze are identical copies of each other. So, you shrink the maze down into a tiny, simplified version that keeps all the important rules but removes the boring repetition.

In their math, they grouped the 10 dimensions of the cube into smaller groups where the numbers were the same. This turned a massive, impossible-to-solve problem into a much smaller, manageable puzzle. This allowed them to check millions of possibilities in seconds instead of years.

What They Found (The Results)

For 10 Dimensions: They found a specific set of 8 planes that slices all 5,120 edges.
For Other Sizes: They also found new, better ways to slice cubes of other sizes (like 11, 12, or 15 dimensions) using fewer planes than previously thought possible.
The Pattern: They noticed that the "best" solutions always had a very structured, repetitive look. The first few numbers in the equations for the planes were always identical. This suggests that the most efficient way to slice these cubes isn't random; it follows a strict, elegant pattern.

Why This Matters (According to the Paper)

The paper emphasizes two main points:

Mathematical Progress: They broke a 50-year-old record for a famous problem in geometry.
How We Do Math: They showed that the best way to solve these hard problems right now isn't just "AI doing everything" or "Humans doing everything." It's a partnership. The AI generates the volume of ideas and patterns, and the human provides the insight to interpret those patterns and guide the search.

The authors explicitly state that the AI did not "think" or "derive" the math proofs on its own. The AI generated code, the humans interpreted the results, and the humans wrote the final mathematical proof. The tools they used are open-source, meaning other researchers can use the same "human-AI team" approach to solve other hard math problems.

Technical Summary: Improved Upper Bounds for Slicing the Hypercube

Problem Definition
The paper addresses the problem of determining $S(n)$ , the minimum number of hyperplanes required to "slice" all edges of an $n$ -dimensional hypercube $Q_n$ . The hypercube $Q_n$ has a vertex set $\{-1, 1\}^n$ . A hyperplane $H$ slices an edge if it intersects the line segment connecting the edge's endpoints in its interior. A collection of hyperplanes is a "full solution" if every edge in $Q_n$ is sliced by at least one hyperplane in the collection.

Historically, the best known upper bound for $S(n)$ was established by Paterson (reported by O'Neil in 1971) as $S(n) \le \lceil 5n/6 \rceil$ . Despite significant attention from combinatorics, geometry, and theoretical computer science, this bound had not been improved in over fifty years. While lower bounds have seen recent progress (currently $\Omega(n^{13/19} \log^{-32/12} n)$ ), the gap between upper and lower bounds remains large.

Methodology
The authors employ a hybrid approach combining automated search driven by Large Language Models (LLMs) with human oversight and mathematical insight.

AI-Driven Algorithm Discovery (CPro1): The authors utilized CPro1, a system that uses LLMs to generate, evaluate, and tune search algorithms for combinatorial problems. They configured CPro1 to propose diverse strategies (e.g., simulated annealing, tabu search) to find collections of $k$ hyperplanes that slice edges of $Q_n$ . The system generated thousands of candidate programs, evaluated them on "dev" instances (where solutions were already known), and identified promising strategies for harder instances.
Local Search and Adaptive Weighting: Analysis of the AI-generated candidates revealed that local hill-climbing search algorithms with adaptive edge weighting were most effective. In this method, the "weight" of unsliced edges is increased over iterations, forcing the algorithm to prioritize difficult edges and escape local optima.
The Reduced Hypercube and Structural Constraints: A critical mathematical insight derived from observing the AI's partial solutions was the existence of a "composition" structure. The authors formalized the concept of a reduced hypercube, where the $n$ $n$ -dimensional hypercube is projected onto an $\ell$ $ℓ$ -dimensional lattice based on grouping hyperplane coefficients into equal sets.
- Enforcing a specific composition (e.g., $[6, 1, 1, 1, 1]$ for $n=10$ ) drastically reduces the search space dimensionality.
- This reduction allows for efficient fitness calculations by mapping the $n$ -cube to a smaller grid.
- The authors observed that in high-performing solutions, the first several coefficients of each hyperplane were identical. They manually incorporated this constraint (fixing initial columns to a constant value) and fixed bias terms to $0.5$ to avoid vertices.
Human Synthesis: The AI systems (CPro1 and OpenEvolve) successfully reproduced known bounds and found strong partial solutions but failed to find the full solution for $S(10) \le 8$ in isolation. The breakthrough occurred when human researchers synthesized insights from the AI's output—specifically the edge-weighted hill-climbing strategy and the column-composition constraint—to manually design a final algorithm. This algorithm successfully found a set of 8 hyperplanes slicing $Q_{10}$ .

Key Contributions and Results

Improved Upper Bound: The paper proves that $S(n) \le \lceil 4n/5 \rceil$ for all $n$ that are not odd multiples of 5. If $n$ is an odd multiple of 5, $S(n) \le 4n/5 + 1$ . This improves upon the decades-old bound of $\lceil 5n/6 \rceil$ .
Construction for $n=10$ : The core of the proof is the explicit construction of 8 hyperplanes that slice all 5,120 edges of $Q_{10}$ . The authors provide the specific coefficient vectors for these hyperplanes.
Subadditivity Argument: Using the known subadditivity property $S(k+\ell) \le S(k) + S(\ell)$ and the new $S(10) \le 8$ result, the authors derive the general bounds for all $n$ .
New Lower Bounds for Partial Slicing: The authors provide new lower bounds for $S(n, k)$ , the maximum number of edges sliceable by $k$ hyperplanes, for various $n$ and $k$ (summarized in Tables 1 and 2). These include tight bounds for cases where full slicing is achieved.
Methodological Framework: The paper demonstrates a workflow where AI generates high-volume candidate algorithms and identifies structural patterns, which are then interpreted and synthesized by humans to produce rigorous mathematical constructions.

Significance and Claims
The paper claims that its primary contribution is breaking a 50-year stagnation in the upper bound for the hypercube slicing problem. It highlights the structured nature of the discovered solutions, noting that optimal or near-optimal slicing hyperplanes appear to possess low-dimensional structures (repetitive coefficients).

Regarding the role of AI, the authors position their work as a "Level C" collaboration (substantive human-AI collaboration) where both parties contribute essentially. They argue that while AI tools can explore vast, intractable search spaces and surface interpretable patterns, human oversight is currently necessary to synthesize these patterns into valid mathematical proofs and final constructions. The authors emphasize that their results were achieved on personal machines using open-source tools, suggesting that such AI-assisted discovery is accessible to researchers without industrial-scale computing resources. They conclude that further improvements to $S(n)$ are likely possible and that the problem of bounding $S(n, k)$ serves as an attractive benchmark for evaluating AI systems in mathematical discovery.