PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing

Rasul Tutunov, Alexandre Maraval, Antoine Grosnit, Xihan Li, Jun Wang, Haitham Bou-Ammar

arXiv:2512.04829v2cs.AI

TL;DR

Improving sphere-packing bounds requires searching mixed continuous and discrete SDP choices, but solver evaluations can take days and gradients are inaccessible. The paper frames SDP construction as a hierarchical game and applies sample-efficient model-based search, reporting new state-of-the-art upper bounds in twelve dimensions.

  • Problem

    Searching for stronger sphere-packing bounds is difficult because the choices mix continuous parameters and discrete functions, gradients through the SDP solver are inaccessible, and evaluations can take days.

    Source: Semidefinite Programming (SDP) Games… · p. 5

  • Method

    The paper frames SDP construction as a hierarchical game in which an agent selects geometric parameters and admissible functions, using sample-efficient model-based optimisation to guide the search.

    Source: Semidefinite Programming (SDP) Games… · p. 6, Discussion and Future Work · p. 13

  • Results

    The method achieves new state-of-the-art upper bounds for sphere packing in twelve dimensions and discovers 80–85% new monomial terms compared with prior constructions.

    Source: Discussion and Future Work · p. 13

  • Takeaways & Limitations

    The work presents sample-efficient, model-based search as a complementary direction for mathematical discovery in structured problems with tight evaluation budgets.

    Source: Discussion and Future Work · p. 13

    Large SDP costs restrict evaluation counts, higher-dimensional scaling remains computationally demanding, and the surrogate models approximate a complex landscape.

    Source: Discussion and Future Work · p. 14

Abstract

from arXiv · show

Sphere packing, Hilbert's eighteenth problem, asks for the densest arrangement of congruent spheres in n-dimensional Euclidean space. Although relevant to areas such as cryptography, crystallography, and medical imaging, the problem remains unresolved: beyond a few special dimensions, neither optimal packings nor tight upper bounds are known. Even a major breakthrough in dimension $n=8$, later recognised with a Fields Medal, underscores its difficulty. A leading technique for upper bounds, the three-point method, reduces the problem to solving large, high-precision semidefinite programs (SDPs). Because each candidate SDP may take days to evaluate, standard data-intensive AI approaches are infeasible. We address this challenge by formulating SDP construction as a sequential decision process, the SDP game, in which a policy assembles SDP formulations from a set of admissible components. Using a sample-efficient model-based framework that combines Bayesian optimisation with Monte Carlo Tree Search, we obtain new state-of-the-art upper bounds in dimensions $4-16$, showing that model-based search can advance computational progress in longstanding geometric problems. Together, these results demonstrate that sample-efficient, model-based search can make tangible progress on mathematically rigid, evaluation limited problems, pointing towards a complementary direction for AI-assisted discovery beyond large-scale LLM-driven exploration.

Semidefinite Programming (SDP) Games for Sphere Packing

The three-point method turns sphere-packing upper bounds into SDPs whose parameters and admissible functions can vary. The paper frames choosing among these formulations as a hierarchical game, where an agent proposes configurations and the solver returns their objective values as rewards.

Semidefinite Programming (SDP) Games for Sphere Packing

  • The three-point method uses matrix-valued polynomial constraints to encode higher-order geometric relationships, with each SDP’s optimal objective value providing an upper bound on packing density.Each instance is defined by nonnegative parameters r, R with r < R, and functions f1, f2 from F(r, R).Source: Semidefinite Programming (SDP) Games… · p. 4
  • Because the SDP is not uniquely defined, improving the bound becomes a search for the instance with the minimal solver objective over (r, R) and admissible (f1, f2).Source: Semidefinite Programming (SDP) Games… · pp. 4–5
  • Gradient-based and model-free search are difficult because the action space mixes continuous parameters with discrete functions, gradients through the solver are inaccessible, and each SDP evaluation can take days.Source: Semidefinite Programming (SDP) Games… · p. 5
  • The SDP Game’s state records explored parameters, functions, and solver rewards; its hierarchical actions first choose (r, R), then choose (f1, f2) from the resulting admissible class.The second-stage functions must satisfy admissibility and geometric conditions for the resulting bounds to be valid.Source: Semidefinite Programming (SDP) Games… · p. 6
  • Rather than choosing infinite-dimensional functions directly, the agent composes finite sequences of polynomial tokens that preserve the three-point method’s analytic and symmetry conditions.The empty-space token separates monomials, adding structural flexibility for defining SDP instances.Source: Semidefinite Programming (SDP) Games… · p. 6

Model-Based Solvers for Sphere Packing Bounds

The solver combines Bayesian optimisation for continuous geometric parameters with Monte Carlo Tree Search for constructing admissible functions. These components iterate, using each costly SDP evaluation to update the search and guide subsequent proposals.

Bayesian Optimisation for Geometric Parameters

  • Bayesian optimisation proposes geometric parameters (r, R) using a probabilistic surrogate of the SDP objective, balancing exploration and exploitation when evaluations are expensive.The surrogate’s uncertainty helps select where another costly evaluation may be most valuable.Source: Model-Based Solvers for Sphere Packing… · p. 8

MCTS for Function Construction

  • Conditioned on (r, R), Monte Carlo Tree Search constructs admissible functions by exploring token sequences through selection, expansion, simulation, and backpropagation.Simulation completes a function with the policy model; backpropagation updates traversed nodes using the simulated reward.Source: Model-Based Solvers for Sphere Packing… · p. 8

Iterative Model-Based Loop

  • The iterative loop has Bayesian optimisation propose (r, R), MCTS construct (f1, f2), and the solver evaluate the SDP before the surrogate is updated.The cycle progressively refines the search using a limited number of expensive evaluations.Source: Model-Based Solvers for Sphere Packing… · p. 8

Model-Based Solvers for Sphere Packing Bounds

New Upper Bounds for Sphere Packing

The model-based agent improves the best-known sphere-packing upper bounds in twelve dimensions, while discovering new polynomial structures and high-performing geometric parameter regimes. In the n=8 case study, it approaches the known optimum and exhibits several of the target function properties, though one normalization condition remains unmet.

Discussion and Future Work

Although costly SDP evaluations make sample-intensive search infeasible, the paper reports state-of-the-art sphere-packing upper bounds and new structural insights from sample-efficient model-based search. Its discussion also identifies scaling and solver costs as limitations and outlines directions for extending the framework.

Evaluation setting

  • Each SDP evaluation may take days, making sample-intensive search infeasible in this setting.The analytic constraints are also described as rigid, delicate, and highly structured.Source: Discussion and Future Work · p. 13

Results

  • 80–85% of monomial terms are new versus prior constructions, while the method achieves state-of-the-art sphere-packing upper bounds in dimension 12.The agent nevertheless recovers core human-designed components; many new polynomials are low degree, which the authors associate with strong influence in the SDP.Source: Discussion and Future Work · p. 13

Geometric parameter exploration

  • The agent searches a broader two-dimensional (r, R) landscape than classical treatments, which fix r = 1, and identifies previously unconsidered regions.The authors report that this behavior leads to improved upper bounds and points to geometric regimes for further analysis.Source: Discussion and Future Work · p. 13

Dimension-8 case study

  • In dimension 8, the method recovers functions resembling the magic function's sign constraints and Fourier-space behavior, while producing bounds that improve on classical linear-programming results and approach the optimum numerically.The search does not use knowledge of modular forms or E8's special algebraic properties.Source: Discussion and Future Work · pp. 13–14

Limitations

  • SDP costs limit the number of evaluations and make higher-dimensional scaling demanding; surrogate models remain approximations, and solver efficiency is a bottleneck.The authors identify faster solvers or differentiable surrogates as open challenges.Source: Discussion and Future Work · p. 14

Future work

  • The authors propose extending the framework to higher-point bounds, combining mathematician-suggested symbolic constraints with learned exploration, and developing faster surrogate solvers.They also suggest that recurring low-degree motifs could inform analytic conjectures and that the methodology may generalize to other geometric and analytic problems.Source: Discussion and Future Work · p. 14

Takeaway

  • The authors present strategic, sample-efficient search as a complementary direction for AI-assisted mathematics, rather than replacing human reasoning or using massive computational sweeps.They emphasize structured search with principled inductive biases for problems too rigid, delicate, or expensive for brute-force exploration.Source: Discussion and Future Work · pp. 13–14

Methods

The three-point method turns admissible functions into an SDP whose objective gives a sphere-packing upper bound. Bayesian Optimisation selects continuous parameters, and Monte-Carlo Tree Search builds polynomial structures for costly SDP evaluation.

The Three-Point Method for Sphere Packing Bounds

Bayesian Optimisation

  • A Gaussian Process surrogate and HEBO acquisition choose costly (r, R) evaluations; input and output warping accommodates heteroskedastic, non-stationary evaluation noise.Source: Bayesian Optimisation · pp. 16–17

Monte-Carlo Tree Search

  • After BO selects a promising (r, R), MCTS builds polynomial structures through selection, expansion, simulation, and backpropagation; heuristics prune costly evaluations and prior SDP results warm-start related simulations.Source: Monte-Carlo Tree Search · pp. 17–18

Related papers

Loading 2512.04829v2…