Improved Upper Bounds for Slicing the Hypercube Duncan Soiffer, Nathaniel Itty ∗, Christopher D. Rosin ∗, Blake Bruell, Mason DiCicco, Gábor N. Sárközy, Ryan Offstein, Daniel Reichman Abstract A collection of hyperplanes ℋ \mathcal{H} slices all edges of the n n -dimensional hypercube Q n Q_{n} with vertex set { − 1 , 1 } n \{-1,1\}^{n} if, for every edge e e in the hypercube, there exists a hyperplane in ℋ \mathcal{H} intersecting e e in its interior. Let S ⁡ ( n ) S(n) be the minimum number of hyperplanes needed to slice Q n Q_{n} . We prove that S ⁡ ( n ) ≤ ⌈ 4 ​ n 5 ⌉ S(n)\leq\lceil\frac{4n}{5}\rceil , except when n n is an odd multiple of 5 5 , in which case S ⁡ ( n ) ≤ 4 ​ n 5 + 1 S(n)\leq\frac{4n}{5}+1 . This improves upon the previously known upper bound of S ⁡ ( n ) ≤ ⌈ 5 ​ n 6 ⌉ 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 Q_{n} that can be sliced using k < n k0 . Significant mathematical and computational efforts have been directed to improve the upper bound on S(n) [ 13 , 10 , 39 , 12 ] . Roughly speaking, a recurring idea in the computational works is to compute all sliceable subsets of edges of Q_{n} : sets of edges that can simultaneously be cut by a single hyperplane. Thereafter, solve the resulting Set Cover instance with parameter k to decide whether k sets from the set family consisting of all sliceable sets can cover all edges of Q_{n} . These works resulted in upper and lower bounds on S(n,k) , and established that S(n)=n for all n\leq 5 and S(6)=5 ; it is currently open if S(7)=5 . For a recent survey of these results, see [ 23 ] . Despite these efforts, the Paterson bound has not been improved since it was announced in [ 24 ] . A central challenge in algorithmically finding slicing hyperplanes is the exponential growth of the vertex and edge sets of Q_{n} and the exponential complexity of solving the NP-hard Set Cover problem. These factors combine to produce prohibitive running times even for relatively small values of n . The curse of dimensionality presents an additional obstacle: an exhaustive search over even a single hyperplane with integer coefficients in [-C,C] quickly becomes infeasible for modest values of C and n ; similarly, determining all sliceable subsets of E_{n} quickly becomes infeasible. In contrast, we rely on local search algorithms, which avoid the prohibitive running time arising from previous approaches to compute S(n) . The use of AI as a tool in the process of proving or disproving mathematical statements has increased in recent years [ 28 , 16 , 8 , 14 , 6 , 31 , 4 ] . In particular, our use of generative AI for the discovery of algorithms that can find objects of mathematical significance is influenced by recent breakthroughs achieved using methods such as FunSearch [ 28 ] , its successor AlphaEvolve [ 22 ] , and CPro1 [ 29 ] . CPro1 [ 29 ] and AlphaEvolve [ 22 ] are both systems which revolve around using large language models (LLMs) to generate large numbers of programs in service of solving mathematical problems. CPro1 has solved long-standing open instances of combinatorial design problems [ 30 ] and instances described in recent research literature [ 31 ] . AlphaEvolve has been used to generate new algorithms, optimize existing programs, and improve bounds and constructions for an impressive range of mathematical problems. The primary difference between CPro1 and AlphaEvolve lies in how they generate candidate programs: CPro1 uses an LLM to propose diverse strategies and implement them from scratch, and provides automated hyperparameter tuning for programs that expose hyperparameters, whereas AlphaEvolve starts from an initial program and iteratively refines it using LLMs in a sophisticated evolutionary loop. While AlphaEvolve is not available for public use, the open source OpenEvolve [ 35 ] and CodeEvolve [ 3 ] tools have replicated or improved on several of AlphaEvolve’s results, and have been used to produce new results [ 9 , 20 ] . The hypercube slicing problem differs from some of the problems that have recently attracted interest in studies of generative AI and other computational approaches for mathematics, such as circle and hexagon packing and minimizing ratios of maximum to minimum distance [ 22 , 14 , 3 , 5 ] . In these problems, one is interested in finding a construction minimizing or maximizing a certain real parameter (for example, placing n disjoint unit hexagons in a larger hexagon whose side length is as small as possible). In contrast, slicing the hypercube involves a “hard” constraint (either all edges are sliced by a set of hyperplanes or they are not). A recurring theme when considering AI assisted mathematical proofs is to what extent the proof depends on AI tools such as LLMs. Using the recent informal taxonomy of quantifying the degree of reliance of math proofs on AI tools [ 37 ] , our proof falls somewhere between “AI-powered modifications of existing solutions (which could be either human-generated or AI-generated)” to “Complex interactions between humans and AI tools in which the AI tools provided crucial calculations.” 4 Algorithms for Slicing the Hypercube We found the collection of hyperplanes presented in Theorem 1 by developing a local search algorithm targeted toward the hypercube slicing problem. Initially, we manually created an algorithm ( Algorithm 2 ) based on tabu search, which has previously proven useful in constructing mathematical objects [ 25 ] and optimization methods geared towards combinatoric problems [ 21 ] . After many rounds of alteration and optimization, this algorithm found constructions slicing all but 6 edges of Q_{10} with 8 planes, but was unable to improve the bound established by Paterson. After a prolonged period without improved results, we opted to explore algorithmic approaches to the hypercube slicing problem using CPro1 [ 29 ] , with the results from our tabu algorithm serving as high-quality test cases. 4.1 Algorithm Search CPro1 prompts a large language model with a formal problem definition and asks it to propose a diverse set of solution strategies, which it then implements as efficient C programs. To use CPro1, problems are defined by a set of constraints, and a specific instance of that problem assigns concrete values to the parameters of those constraints; the task is to determine whether the constraints are satisfiable for that instance. In hypercube slicing, an instance specifies the hypercube dimension n , the number of hyperplanes k , and the minimum number of edges s that must be sliced (with s equal to the total number of edges for a full solution). CPro1 evaluates candidate programs on a collection of “dev” instances known to be solvable—here, instances (n,k,s) for which our tabu search had already discovered solutions. The highest-performing candidates on these instances are then evaluated on instances for which no solution is currently known. We configured CPro1 with a definition of the hypercube slicing problem with integer coefficients restricted to [-40,40] and no other constraints. We performed five runs of CPro1, with 200 candidate programs generated per run. Two runs used small dev instances with n<8 , while the remaining three used larger dev instances with n up to 17 . CPro1 generated and tested diverse strategies, such as simulated annealing and tabu search, and variations within these strategies, such as alternative cost functions. From the runs that used small dev instances, the best program used an adaptively edge-weighted hillclimbing search ( Section 4.2 ). The method was effective for small instances: it solved all our dev instances for n<8 , matching the results of our tabu search. However, this technique by itself could not find a set of k hyperplanes slicing Q_{10} . From the runs that used larger dev instances, several programs were able to improve upon our previous best results for n>12 with k=n-3 , though still fell short of slicing all edges. One such run produced an improvement for n=15, k=12 where all coefficients were equal to the same value in the first 13 dimensions across all planes, and only the last 2 columns varied. While this program was not more generally successful, and could not find a full solution for n=10, k=8 , we decided to pursue this intriguing constraint ourselves. We manually modified the adaptively edge-weighted hill-climbing search to constrain the initial columns to all have the same constant value. Observing bias terms with low magnitudes across many high-performing partial solutions, and informed by observations from manually constructing the tabu search algorithm, we also fixed all bias terms to 0 ( +0.5 , an arbitrary offset to avoid passing through vertices). Following this, we manually explored varying values for the constant and for the number of constrained columns, improving upon our best partial results for instances including n=11 , k=8 , with further runs obtaining the full solution to n=10, k=8 . Following this, we explored other approaches to improving the algorithm. By hill-climbing in smaller local neighborhoods, we reduced the number of times computation is spent checking proposed moves which are later rejected. Further, observing that the planes in solutions for n=10 , k=8 , and n=6 , k=5 slice very similar numbers of edges in the reduced hypercube induced by their fixed columns ( Section 4.3 ), we added a variance penalty which encourages planes to slice similar numbers of edges in the reduced hypercube. While these approaches yielded improved partial results and significant performance gains—decreasing the time to find solutions for n=10 , k=8 by more than two orders of magnitude when combined—they proved insufficient for finding full solutions in dimensions n>10 for k=n-3 . The AI method CPro1 provided the ingredients here in separate solutions: the efficient edge-weighted hillclimbing search, and the constraint on initial columns, but did not by itself produce a combined program that could solve n=10 k=8 . In hindsight, it seems the insight on constraining the initial columns was close at hand: our previous experiments with tabu search had already constrained several values in each row to be the same value, just not the same columns or the same value across all rows, and we also observe now that Paterson’s original solution to n=6 k=5 can be put in a form in which the first 3 columns are all equal to the same identical constant while only the last three columns vary. This highlights how AI-based research and discovery tools can produce large volumes of potential insights in the process of exploration, but also highlights the importance of surfacing these results for human review and synthesis. 4.2 Local search Across all proposed programs, we found that local hill-climbing search algorithms were consistently most effective. Such algorithms begin with an initial candidate solution (i.e., k hyperplanes), then: 1. Given the current candidate, generate similar candidates—say, by changing a single coefficient of a hyperplane—replacing the current if the “fitness” improves (in our case, a count of the edges sliced). 2. Repeat until a fitness threshold is reached. Out of many such local search strategies, we found that approaches with adaptive weighting yielded dramatically improved solutions. This involves incrementing the “weight” of each edge—the value contributed to the fitness function when sliced—if it remains unsliced for many iterations; such dynamic weighting is a technique commonly used in other combinatorial optimization problems (e.g. [ 7 ] ) to help algorithms escape local optima. We define a set of allowed neighbors to search over in step (1). We allow neighbors \mathcal{H}^{\prime} with Hamming distance \leq 2 within a single plane, that is, we search over collections of hyperplanes where exactly one hyperplane differs in \leq 2 coordinates. We further restrict this by requiring that each coordinate differs by no more than d , a hyperparameter, which reduces computation spent evaluating moves which are unlikely to be productive. 4.3 Reduced Hypercube Following initial testing with CPro1, we observed that across several runs with strong slicing results, every hyperplane obeyed a composition (a representation of n as \ell positive integers, n=\sum_{i=1}^{\ell}b_{i} ) which essentially prescribes groups of identical coefficients. Each b_{i} denotes the size of a group of equal coefficients. For example, the hyperplanes in ( 1 ) satisfy a [6,1,1,1,1] composition. Enforcing a particular composition not only reduces the dimensionality of the search space, but also enables a natural optimization to the fitness computation: rather than operating on the n\times 2^{n-1} edges of the n -cube, we map the cube to a grid in \ell dimensions with extent [b_{1},\ldots,b_{\ell}] . We formalize this reduction with the concept of a reduced hypercube (proofs and further details in Appendix D ). Given a composition [b_{1},\ldots,b_{\ell}] of n , any vertex (v_{1},v_{2},\cdots,v_{n}) has a reduced representation with \ell coordinates, where each new coordinate is the sum of the coordinates in the composition. This grid has only |V|=\prod_{i=1}^{\ell}(b_{i}+1) vertices, where two reduced vertices are connected by an edge if and only if they differ by exactly 2 in one coordinate, corresponding to changing the sign of a coordinate in the original hypercube. Furthermore, this grid has |V|(\ell-\sum_{i=1}^{\ell}\frac{1}{{b}_{i}+1}) edges, and computing the fitness of a candidate hyperplane reduces to evaluating slicing of these (multiplicity weighted) grid edges. Given a collection of planes \mathcal{H} satisfying such a composition, we let \phi(\mathcal{H}) denote the function which yields the set of reduced edges. As an example, enforcing [6,1,1,1,1] effectively maps Q_{10} to a 5 -dimensional, 6\times 1\times 1\times 1\times 1 grid via the linear projection (x_{1},\ldots,x_{10})\to(x_{1}+\cdots+x_{6},x_{7},\ldots,x_{10}) . This grid has 320 edges – a 16\times reduction from the 5120 edges of Q_{10} . In addition, the slicing computations only involve 5 multiplications per hyperplane instead of 10 . When searching over hyperplanes under these constraints, we find that using |\phi(\mathcal{H})| as a fitness function is more effective for finding full solutions, while a version which retains edge multiplicities corresponding to the unreduced hypercube is more effective at finding high-slicing partial solutions. Further, we observe that search algorithms typically perform best under highly constrained patterns with only a single b_{i}>1 and all other b_{j}=1 , so long as b_{i} is not too large. We also observe that while the number of edges sliced by each plane in a full solution \mathcal{H}^{*} can vary significantly, the number of reduced edges sliced is nearly constant across each plane. That is, |\phi(H_{i})|\approx|\phi(H_{j})|~~\forall H_{i},H_{j}\in\mathcal{H}^{*} . Inspired by this observation, we subtract a variance penalty to encourage planes to slice similar numbers of edges in the reduced hypercube. Formally, given a weighting w on each edge, we define fitness function \psi as \psi(\mathcal{H},w):=\sum_{(v_{1},v_{2})\in\phi(\mathcal{H})}w(v_{1},v_{2})-\operatorname{Var}\bigl(\{\,|\phi(H)|:H\in\mathcal{H}\,\}\bigr) (2) Together, these alterations to the basic adaptive edge-weighted search framework yield Algorithm 1 . Algorithm 1 Our adaptive edge-weighted search 1: E_{n} , the edges of the reduced hypercube for n dimensions; number of planes k ; hyperparameters max_iterations, weight_period, and weight_limit 2: \mathcal{H}^{*}\leftarrow\emptyset 3: while time limit not exceeded do 4: \mathcal{H}\leftarrow\text{random valid collection of $k$ planes} 5: Initialize weights w:E_{n}\to\mathbb{R} to w(v_{1},v_{2}):=1 for all (v_{1},v_{2})\in E_{n} 6: while t<\text{max\_iterations} do 7: \mathcal{H}^{\prime}\leftarrow\operatorname{RandomNeighbor}(\mathcal{H}) 8: if \psi(\mathcal{H}^{\prime},w)\geq\psi(\mathcal{H},w) then \triangleright Accept if \geq weighted fitness 9: if \psi(\mathcal{H}^{\prime},w)>\psi(\mathcal{H},w) then \triangleright Reset timer if > weighted fitness 10: t_{w}\leftarrow 0 11: end if 12: if |\phi(\mathcal{H}^{\prime})|>|\phi(\mathcal{H})| then \triangleright Reset timer if higher slicing number 13: t\leftarrow 0 14: end if 15: \mathcal{H}\leftarrow\mathcal{H}^{\prime} 16: end if 17: if t_{w}>\text{weight\_period} then \triangleright Increase weights for unsliced edges 18: w(v_{1},v_{2})\leftarrow\min\left(w(v_{1},v_{2})+1,\text{weight\_limit}\right)~~\forall(v_{1},v_{2})\notin\phi(\mathcal{H}) 19: t_{w}\leftarrow 0 20: end if 21: t_{w}\leftarrow t_{w}+1 22: t\leftarrow t+1 23: end while 24: if |\phi(\mathcal{H})|>|\phi(\mathcal{H}^{*})| then \triangleright Track overall best solution 25: \mathcal{H}^{*}\leftarrow\mathcal{H} 26: end if 27: end while 4.4 AI-Driven Discovery and Researcher Intervention Is the use of generative AI for our improved constructions necessary? Prior to involving AI, we experimented extensively for over a year with tabu search without improving the upper bound on S(n) . Certainly, it is possible, and perhaps probable, that with further time and computational investment we would have discovered hyperplane arrangements which slice Q_{10} (and tabu search has been used before for finding combinatorial constructions [ 25 ] ). However, utilizing an AI-driven automated discovery system rapidly accelerated this progress by dramatically increasing the volume of ideas that could be attempted and from which insights could be gleaned. It is also natural to ask: Is human involvement necessary to arrive at our solutions? While LLM-driven automated systems are powerful enough to discover solutions that slice Q_{6} with 5 planes and attain strong partial slicing results, they were unable to obtain improvements on S(n) without further human intervention. Only by combining researcher oversight with the insights surfaced by automated search and discovery were we able to achieve the results in Tables 1 and 2 . To support our assessment, we present results from OpenEvolve, CPro1, and our initial tabu search algorithm when ran on the hypercube slicing problem. For OpenEvolve, we evaluate using the LLMs OpenAI o4-mini, OpenAI GPT-5-mini, Google Gemini 3 Pro and Flash, and use the provided templates for generating Rust code; for CPro1 we evaluate with OpenAI o4-mini and generate C code ( Section 4.1 ). Both systems are given a similar number of attempts (programs). We observe the different methods of generating programs between OpenEvolve and CPro1 reflected in their LLM usage patterns: over 80% of CPro1’s LLM tokens are output tokens from generating diverse candidate programs starting from the problem definition, whereas over 80% of OpenEvolve’s LLM tokens are input tokens for analysis of prior programs and results. These systems are still new, and it is not yet clear what the right patterns are for using LLMs to generate programs for solving mathematical problems. Some researchers have found that AlphaEvolve’s evolutionary loop was unnecessary for some of the results it has achieved [ 15 ] , but its success across a wide variety of mathematical and non-mathematical domains demonstrates the framework’s versatility. We compare results obtained from our manually created tabu search, OpenEvolve without further instruction beyond the problem description, OpenEvolve with the additional constraint that hyperplanes should contain groups of identical coefficients, CPro1 before human intervention, and our final results with CPro1 after introducing our manual changes. Table 3 demonstrates that OpenEvolve and CPro1 without further oversight could achieve strong results, reproducing the bound on S(n) due to Paterson and in some cases improving on our previous partial slicing constructions achieved by tabu search, but failed to produce a new upper bound for S(n) . Meanwhile, CPro1 code with our manually introduced changes consistently achieves state of the art results, highlighting the importance of introducing human oversight at points within the discovery process beyond initial problem formulation. Tabu search OpenEvolve Composition- constrained OpenEvolve CPro1 CPro1 + Human n=6 k=5 192 192 192 192 192 n=10 k=8 5114 5100 5112 5114 5120 n=15 k=12 245252 240509 238215 245628 245748 Table 3: Comparison of the number of edges sliced by our manually created tabu search algorithm, AI-only systems, and AI systems with human intervention. Underlines indicate full hypercube slicing. 5 Discussion and Conclusions This work illustrates once again the effectiveness of AI in finding constructions in large high-dimensional spaces which can prove challenging for effective search by human researchers [ 36 , 27 ] . Our new constructions were obtained on a personal machine without requiring excessive computing power, pointing to the applicability of AI in mathematics (and other disciplines) for researchers that may not have access to computational resources of industrial scale, so long as LLM queries remain within budget. In particular, we believe that CPro1 could be useful in finding constructions in combinatorics, geometry and theoretical computer science. Importantly, while AI-driven search and discovery can explore vast spaces that are otherwise intractable to attempt through human effort alone, we also advocate that large-scale AI-driven search methods be explicitly designed to support human-in-the-loop workflows. In our experience, the task was not accomplished by an AI system in isolation; rather, progress emerged when the automated, high-throughput search surfaced human-interpretable patterns and partial insights, which were then used to manually guide further refinement. We therefore argue that AI-driven automated discovery systems should actively organize and present observations and recurring patterns in ways that are accessible to human researchers, enabling targeted interventions and closer integration with the search and discovery system. We expect that further improvements on the upper bound for S(n) are possible. For instance, when searching for lower bounds for S(15,12) we find constructions of 12 hyperplanes only 12 edges from fully slicing Q_{15} , constructions for S(14,11) only 22 edges from slicing Q_{14} , and constructions for S(13,10) , S(12,9) , and S(11,8) only 24 edges from slicing their respective hypercubes. Considering the belief that S(n)=\Omega(n) , the progress recorded here could bring us closer to finding the precise value of S(n) . Beyond mathematical interest in slicing the hypercube, the problem of lower bounding S(n,k) is attractive for evaluating AI for math systems considering the ease of verifying that a given solution slices a given set of edges but the relative difficulty in constructing such solutions. A recurring feature in our constructions is that the collections of slicing hyperplanes appear to be low-dimensional in nature. In particular, the first several coefficients of each hyperplane are identical, and we observe additional forms of repetitive structure in many solutions ( Appendix B ). These patterns may point to underlying structural properties of optimal or near-optimal slicing hyperplanes. An interesting direction of further study is to formalize the existence of “good” solutions to the slicing problem carrying low-dimensional structure, and to what extent full solutions admit such properties. Our work has several limitations. While finite constructions of slicing hyperplanes translate to an upper bound on S(n) , they fall short of proving upper bounds on S(n) of order o(n) (if such upper bounds exist). Furthermore, our methodology is not applicable to proving lower bounds on S(n) or upper bounds on S(n,k) . While the improved bounds and constructions presented here are a step towards a better understanding of the slicing problem and may lead to deeper insights, it is probable that new theoretical ideas will be required to determine S(n) . Appendix A Paterson construction for slicing Q_{6} Solutions are listed such that each row corresponds to the vector of coefficients of a hyperplane, with the final entry representing the bias term. For example, the first hyperplane is 1x_{1}+1x_{2}+1x_{3}+3x_{4}+3x_{5}-4x_{6}=0 . \begin{array}[]{rrrrrrr}1&1&1&3&3&-4&0\\ -2&-2&-2&3&3&-1&0\\ 3&3&3&1&1&-4&0\\ -1&-1&-1&3&3&6&0\\ 3&3&3&1&1&8&0\\ \end{array} (3) Appendix B Additional constructions for slicing Q_{10} Additional constructions which slice Q_{10} are listed below. Note that there exist many solutions without -9 as the repeated coefficient, we simply find that fixing this value leads to finding solutions quickly. Below is the first full solution to Q_{10} that we found. \begin{array}[]{rrrrrrrrrrr}-9&-9&-9&-9&-9&-9&7&-16&5&35&0.5\\ -9&-9&-9&-9&-9&-9&-32&-4&-17&8&0.5\\ -9&-9&-9&-9&-9&-9&32&5&19&-4&0.5\\ -9&-9&-9&-9&-9&-9&-3&15&-3&-38&0.5\\ -9&-9&-9&-9&-9&-9&15&3&-36&4&0.5\\ -9&-9&-9&-9&-9&-9&8&-35&-2&-12&0.5\\ -9&-9&-9&-9&-9&-9&-4&33&7&16&0.5\\ -9&-9&-9&-9&-9&-9&-18&-4&34&-5&0.5\\ \end{array} Upon closer observation of this solution, it appears that the planes can be paired such that the free values in one member of the pair are very roughly the negation of the free values in the other members of the pair, after permutation. Indeed, enforcing this constraint during the search enables it to find solutions for k=8 n=10 and k=10 n=12 , and the search is more efficient due to the greatly reduced size of the search space. However, we fail to find solutions of this form even for k=6 n=7 despite the fact it is fast to find solutions under normal conditions, and most partial results obtained under these constraints are also worse. This suggests this structure is not a global phenomenon across all n and k , it is interesting to ask under what conditions such solutions are possible. We also observed many solutions where the free values in one plane were (approximately) a permutation of the free values in another plane, with some negated. Imposing these constraints leads to highly structured solutions for n=10 k=8 but does not appear to work (that is, our algorithm could not find full slicing solutions) for most other values of k and n . The solution we present in Equation 1 was obtained using this method, it can be observed that the first 4 rows each use the same free values but permuted or negated. The same is true for the final 4 rows, using the same pattern. Additionally, when explicitly restricting the number of allowed coefficient magnitudes, we also arrive at full solutions with high degrees of structure, with one such construction presented below. \begin{array}[]{rrrrrrrrrrr}-9&-9&-9&-9&-9&-9&30&4&3&-20&0.5\\ -9&-9&-9&-9&-9&-9&20&-3&4&30&0.5\\ -9&-9&-9&-9&-9&-9&-30&-3&-4&20&0.5\\ -9&-9&-9&-9&-9&-9&-20&3&-3&-30&0.5\\ -9&-9&-9&-9&-9&-9&-3&-38&11&-3&0.5\\ -9&-9&-9&-9&-9&-9&4&-11&-38&-4&0.5\\ -9&-9&-9&-9&-9&-9&3&38&-11&3&0.5\\ -9&-9&-9&-9&-9&-9&-4&11&38&3&0.5\\ \end{array} Appendix C CPro1’s initial improvement to S(15,12) This CPro1-produced set of 12 hyperplanes slices 245628 out of the 245760 edges of Q_{15} , an improvement over our prior tabu search result of 245252. CPro1 produced this solution which use the same value in the initial columns, without being prompted or constrained to do so. \begin{array}[]{rrrrrrrrrrrrrrrr}-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-2&-2&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-2&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&2&-2&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&2&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-6&-2&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-6&10&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-6&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&6&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&8&16&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&8&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-10&0&0.5\\ -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&10&0&0.5\\ \end{array} Appendix D The Reduced Hypercube The sets of hyperplanes slicing the highest number of edges exhibited a common property: each hyperplane had groups of identical coefficients, obeying a composition. Definition 1 . A composition \beta of Q_{n} is an ordered list of positive integers [b_{1},b_{2},\ldots,b_{\ell}] such that \sum_{i=1}^{\ell}b_{i}=n , where each b_{i} represents the size of the i -th group. Let B_{j} denote the the j ’th group of \beta . The solution in Equation 1 satisfies a [6,1,1,1,1] composition, while Mike Paterson’s solution in Equation 3 satisfies [3,2,1] . Figure 1: A 6 -dimensional hypercube under the [3,2,1] composition reduces to 46 edges, and is transformed into a 3\times 2\times 1 lattice in three dimensions. Definition 2 . A hyperplane that \mathbf{a} satisfies a composition \beta in \ell dimensions has a reduced hyperplane representation, \mathbf{a}^{\beta}=(a^{\beta}_{1},\dots,a^{\beta}_{\ell})\in\mathbb{R}^{\ell} where a_{i}=a^{\beta}_{j} for all i\in B_{j} . Definition 3 . Any vertex \mathbf{v}=(v_{1},v_{2},\cdots,v_{n}) has a reduced vertex representation \mathbf{v}^{\beta}=(v^{\beta}_{1},v^{\beta}_{2},\cdots,v^{\beta}_{\ell}) under a composition \beta in \ell dimensions where v^{\beta}_{j}=\sum_{i\in\beta_{j}}v_{i} . Observe that the possible values for v^{\beta}_{j} are \{-{b}_{j},-{b}_{j}+2,\cdots,{b}_{j}-2,{b}_{j}\} : The sum of b_{j} vertex coordinates (with value \pm 1 ) has minimum -{b}_{j} and maximum {b}_{j} – Intermediate values are obtained by changing a single coordinate from -1 to 1 , which is a difference of 2 . Definition 4 . Two reduced vertices, \mathbf{v}^{\beta} and \mathbf{w}^{\beta} , are connected by a reduced edge, e^{\beta}=(\mathbf{v}^{\beta},\mathbf{w}^{\beta}) , if the edge e=(\mathbf{v},\mathbf{w}) exists on the original hypercube. Theorem 2 . Two reduced vertices, \mathbf{v}^{\beta} and \mathbf{w}^{\beta} , are connected by an edge if and only if they differ by exactly 2 in one coordinate. Proof. \mathbf{v}^{\beta} and \mathbf{w}^{\beta} are connected by an edge if and only if \mathbf{v} and \mathbf{w} are adjacent. Without loss of generality, assume they differ in the i -th coordinate. Observe that |v_{i}-w_{i}|=2 as one must be -1 and the other 1 , and no other coordinate differs. \begin{split}\left|v^{\beta}_{j}-w^{\beta}_{j}\right|&=\left|\sum_{k\in{B}_{j}}v_{k}-\sum_{k\in{B}_{j}}w_{k}\right|\\ &=\left|\left(\sum_{k\in{B}_{j}\setminus\{i\}}v_{k}\right)+v_{i}-\left(\sum_{k\in{B}_{j}\setminus\{i\}}w_{k}\right)-w_{i}\right|\\ &=\left|v_{i}-w_{i}\right|=2\end{split} ∎ Corollary 1 . The sum of coordinates of any two reduced vertices connected by an edge differ by exactly 2. Definition 5 . A reduced hypercube, Q^{\beta}=(V^{\beta},E^{\beta}) , is the reduced representation of a hypercube Q given a composition \beta , where V^{\beta} is the set of all reduced vertices, and E^{\beta} is a set of reduced edges between these vertices. We can easily find |V^{\beta}| by applying Definition 3 and the observation that follows: |V^{\beta}|=\prod_{i=1}^{\ell}|\{-{b}_{i},-{b}_{i}+2,\cdots,{b}_{i}-2,{b}_{i}\}|=\prod_{i=1}^{\ell}({b}_{i}+1). (4) Edges in direction (dimension) i connect consecutive values in the i -th coordinate. There are b_{i} such transitions (from -b_{i} to -b_{i}+2 , from -b_{i}+2 to -b_{i}+4 , etc.). For each of the \prod_{j\neq i}(b_{j}+1) choices of the other coordinates, we get b_{i} edges. Summing over all \ell directions: |E^{\beta}|=\sum_{i=1}^{\ell}b_{i}\prod_{j\neq i}(b_{j}+1). To obtain the alternative form, factor out |V^{\beta}|=\prod_{j=1}^{\ell}(b_{j}+1) Theorem 3 . For a hyperplane \mathbf{a} and vertex \mathbf{v} satisfying a composition \beta , \mathbf{a}^{\beta}\cdot\mathbf{v}^{\beta}=\mathbf{a}\cdot\mathbf{v} Proof. \mathbf{a}\cdot\mathbf{v}=\sum_{k=1}^{n}a_{k}v_{k}+b=\sum_{i=1}^{\ell}a^{\beta}_{i}\left(\sum_{j\in B_{i}}v_{j}\right)+b=\sum_{i=1}^{\ell}a^{\beta}_{i}\cdot v^{\beta}_{i}+b=\mathbf{a}^{\beta}\cdot\mathbf{v}^{\beta} ∎ Theorem 4 . A set of hyperplanes A all satisfying \beta slice all the edges of the hypercube Q if and only if the set of reduced hyperplanes A^{\beta} slices all the edges of the reduced hypercube Q^{\beta} . Proof. By Definition 4 , every edge of Q_{n} maps to some edge in E^{\beta} and every edge in E^{\beta} is the image of at least one edge in Q_{n} . The result follows from Theorem 3 . ∎ Theorem 4 establishes that the search for slicing sets can be restricted to the reduced hypercube. The reduced hypercube preserves the property that vertices of any edge differ in exactly one coordinate, allowing us to apply existing search techniques without modification. D.1 Computing the Sliced Edges in the Reduced Hypercube To map the number of edges sliced on the reduced hypercube to the original hypercube, we need to know the number of edges corresponding to a reduced edge. Let \mathbf{\widehat{v}}^{\beta} represent the number of negative coordinates in each composition group, where \widehat{v}^{\beta}_{j}=\sum_{i\in{b}_{j}}[v_{i}=-1]. Note that this representation still uniquely identifies each reduced vertex, as the number of -1 s directly gives the sum. Each reduced vertex represents many vertices in the hypercube. For a composition \beta we can calculate the number of vertices which map to a reduced vertex, \mathbf{v}^{\beta} , by considering all vertices in which the sum of the coordinates in each composition group are equal. If the sums are equal, the number of negative coordinates is also equal, and if a coordinate is not negative it is positive. Therefore, we only need to count the number of ways of selecting negative coordinates in each composition group: |\mathbf{v}^{\beta}|=\prod_{i=1}^{\ell}\binom{{b}_{i}}{\widehat{v}^{\beta}_{i}}. (5) Each reduced edge also corresponds to many edges in the hypercube, as many pairs of vertices on the hypercube will map to the same pair of reduced vertices. Definition 6 . For a reduced edge e=(u^{\beta},v^{\beta})\in E^{\beta} , its multiplicity \mu(e) is the number of edges in Q_{n} that map to e . For a reduced vertex v^{\beta} , let \widehat{v}^{\beta}_{j}=(b_{j}-v^{\beta}_{j})/2 denote the number of -1 coordinates in block j among its preimages. Theorem 5 . Let e=(u^{\beta},v^{\beta})\in E^{\beta} with u^{\beta}_{i}