The Certification Limits of KS-Type Layer Relaxations: A Square-Root Ceiling and Its Breakdown
arXiv:2607.12134
The paper analyzes the certification power of Kuznetsov‑Sahinidis‑type separable bilinear layer relaxations, proving that they can at most certify a deficit of order √N for most singleton costs, while at a critical cost they can achieve linear certification, and it studies how these bounds apply to Lennard‑Jones systems.
Abstract
A separable bilinear layer relaxation assigns a population cost to each layer and a nonpositive bilinear coupling to each pair of layers, then excludes a profile span whenever the relaxed minimum exceeds a reference value. We ask what a Kuznetsov-Sahinidis-type relaxation can certify at best. Let gamma = g(1) be the singleton-layer cost. For every valid relaxation with gamma > -1/2, every reference bounded per particle, and every underlying system satisfying two elementary low-energy witness conditions, we prove that the certified deficit N - rho(N) is at most of order sqrt(N), with an explicit bound depending only on the reference bound and gamma. Thus no relaxation in this class can certify a larger asymptotic deficit, independently of the detailed layer cost, interaction kernel, or reference. The threshold is sharp in the abstract witness class: at gamma = -1/2 we construct a valid relaxation with a bounded sound reference and deficit N - 1. The geometric Lennard-Jones system behaves differently. A three-atom chain restores the square-root ceiling at the endpoint, while sufficiently negative singleton costs allow valid relaxations with linear deficit. For still lower costs, beyond the stability constant, no sound relaxation excludes any span. These regimes define a certification spectrum for layer relaxations and reveal a reentrant transition between no exclusion, linear exclusion, and the universal square-root ceiling.
11 pages. Submitted to the Journal of Global Optimization