A certified refinement and asymptotic analysis of the Kuznetsov-Sahinidis diameter bound for Lennard-Jones clusters

Technical Summary: A Certified Refinement and Asymptotic Analysis of the Kuznetsov–Sahinidis Diameter Bound for Lennard–Jones Clusters

Problem Statement
The Lennard–Jones (LJ) cluster problem seeks the global minimum of the pairwise potential energy $V_{LJ}(r) = r^{-12} - 2r^{-6}$ for $N$ identical atoms in $\mathbb{R}^3$. While heuristic searches provide putative minima for thousands of cluster sizes, deterministic global optimization—which yields numerical certificates of optimality—has succeeded only for very small clusters ($N \le 6$). A critical component of any deterministic branch-and-bound solver is an a priori bound on the diameter of an optimal cluster. This bound restricts the spatial search box. Kuznetsov and Sahinidis (KS) previously established such a bound using a "layer argument," partitioning space into unit-width layers and charging each layer a loose internal energy bound of $-\binom{n}{2}$ (assuming all intra-layer pairs sit at the potential minimum).

Methodology
This paper refines the KS bound by replacing the loose per-layer energy charge with a "certified estimate" derived from the KS subset inequality and proven minima for small clusters ($V^*_5$ and $V^*_6$).

1. Refined Energy Lower Bound:
   The authors define a new per-layer energy function $f(n)$:

   • For $n \le 6$, $f(n) = V^*_n$ (using proven minima).
   • For $n \ge 7$, $f(n) = \frac{n(n-1)}{30}V^*_6$, derived from the subset inequality $V^*_n \ge \frac{n(n-1)}{M(M-1)}V^*_M$ with $M=6$.
     This replaces the trivial bound $-\binom{n}{2}$ used by KS. Additionally, the inter-layer interaction kernel is tightened conservatively to $\bar{v}(d) = V_{LJ}(d-1)$ for $d \ge 3$, reflecting the minimum possible separation between layers.

2. Optimization over Profiles:
   The problem of finding the tightest diameter bound becomes minimizing the total lower bound energy $ELB(\mathbf{n})$ over all population profiles $\mathbf{n} = (n_1, \dots, n_D)$ where $\sum n_k = N$ and $n_k \ge 1$.

   • Reduction to Band Forms: Using a "layer-cake" decomposition, the authors show that minimizing $ELB$ is equivalent to maximizing specific band forms.
   • Arrangement-Free Certification: To avoid the combinatorial explosion of checking all permutations, the authors prove an "arrangement-free lower bound" (Lemma 2). This lemma demonstrates that for any fixed multiset of layer populations, the energy is minimized when the surplus atoms are arranged in a "centred decreasing" profile (largest populations in the center, decreasing outward).
   • Rigorous Verification: The authors employ directed-rounding arithmetic to verify that the minimum energy of any configuration spanning $D$ layers strictly exceeds the energy of the best-known putative configuration $V_{put}(N)$. If this condition holds, no global minimizer can span $D$ layers, allowing the diameter bound to be decremented.

3. Asymptotic Analysis:
   The paper derives the asymptotic form of the original KS bound and the gain of the refinement. It utilizes lattice constants ($\sigma_0$ and $C_{bg}$) derived from the interaction kernel to solve the minimization problem analytically for large $N$.

Key Results

• Certified Refinements: For 92 cluster sizes in the range $15 \le N \le 200$, the refined bound certifies that the optimal cluster must occupy one fewer layer than the original KS bound ($\rho_{new} = \rho_{KS} - 1$). The smallest margin of improvement is $0.0027$ at $N=38$, and the largest is $29.0$ at $N=196$.
• Asymptotic Form: The paper resolves an open question regarding the asymptotic behavior of the KS bound. Contrary to the empirical linear fit ($\approx 0.798N$) observed in finite ranges, the true asymptotic form is $\rho_{KS}(N) = N - \Theta(\sqrt{N})$. The linear fit is identified as a finite-size artifact.
• Asymptotic Gain: The improvement provided by the refinement grows as $\Theta(\sqrt{N})$ layers, with an exact asymptotic constant derived in Corollary 2.
• Solver Impact: A direct test on tractable sizes ($N \le 6$) reveals that the diameter box is not the binding resource for deterministic solvers; tightening the box by one layer did not reduce the computational cost of proving optimality. For sizes where the refinement applies ($N \ge 38$), no deterministic solver currently runs.

Significance and Claims
The authors present this work as a theoretical note and a rigorous tightening of a published a priori bound, rather than a breakthrough in solving the global optimization problem itself.

• No New Global Minima: The paper explicitly states it does not certify any new global minima for $N \ge 7$. The refinement relies on existing putative minima ($V_{put}$) as upper bounds but does not assume they are the true global minima.
• Mechanism Clarification: The primary contribution is a precise account of the mechanism by which the KS bound can be improved: replacing the loose intra-layer energy assumption with certified subset estimates and proving that the optimal distribution of atoms follows a centred decreasing profile.
• Modest Scope: The authors emphasize that the gain is modest (one layer for $N \le 200$) and that the result does not currently enable the solution of larger clusters. The significance lies in the mathematical rigor of the certificate (using directed rounding and arrangement-free proofs) and the resolution of the asymptotic behavior of the bound, settling a point left open by Kuznetsov and Sahinidis.