Exact certification of irrational global minimizers from inexact sum-of-squares certificates

Sum-of-squares programming can certify polynomial inequalities, but in practice its certificates are computed numerically, in floating-point arithmetic. A common way to make them exact is to round them to rational numbers, which typically needs some slack. Bounds that certify optimality at an irrational minimizer have essentially no slack, so rounding alone is generally not enough. We describe one way to handle this case and apply it to the Thomson problem: placing N equal charges on the unit sphere to minimize their Coulomb energy. We round a numerical three-point semidefinite certificate and keep the rounding error as an explicit residual, which gives an energy bound within 10⁻⁵⁰ of the candidate configuration. A quantitative form of complementary slackness, a finite case analysis and a local Hessian bound are then used to turn this nearly tight bound into an exact result. In this way we obtain a computer-assisted proof that the tricapped trigonal prism (N = 9) and the capped square antiprism (N = 10) are the unique minimizers up to rotations, reflections and relabeling. Both results are also formalized in the Lean 4 proof assistant.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-19
DOI
https://doi.org/10.21203/rs.3.rs-11723965/v1
Primary Topic
Advanced Optimization Algorithms Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact certification of irrational global minimizers from inexact sum-of-squares certificates

Katherine Xie
Research Square
Advanced Optimization Algorithms Research
preprint

Exact certification of irrational global minimizers from inexact sum-of-squares certificates

Katherine Xie
preprint en

Abstract

Sum-of-squares programming can certify polynomial inequalities, but in practice its certificates are computed numerically, in floating-point arithmetic. A common way to make them exact is to round them to rational numbers, which typically needs some slack. Bounds that certify optimality at an irrational minimizer have essentially no slack, so rounding alone is generally not enough. We describe one way to handle this case and apply it to the Thomson problem: placing N equal charges on the unit sphere to minimize their Coulomb energy. We round a numerical three-point semidefinite certificate and keep the rounding error as an explicit residual, which gives an energy bound within 10⁻⁵⁰ of the candidate configuration. A quantitative form of complementary slackness, a finite case analysis and a local Hessian bound are then used to turn this nearly tight bound into an exact result. In this way we obtain a computer-assisted proof that the tricapped trigonal prism (N = 9) and the capped square antiprism (N = 10) are the unique minimizers up to rotations, reflections and relabeling. Both results are also formalized in the Lean 4 proof assistant.

Research Square
University of California, Irvine (US)
Advanced Optimization Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon