Optimization hierarchies for extremal geometry through complete positivity
Abstract
Completely positive functions are an extension of completely positive matrices. They are known to characterize maximal spherical codes and maximum-density distance-avoiding subsets of ℝn and certain compact metric spaces. This thesis expands this framework to related classes of problems in finite measure spaces and to the sphere-packing problem. For the latter, this is sharpened to show that the optimal sphere-packing density can be approximated using Schwartz functions. Converging hierarchies of semidefinite programming bounds on the size of optimal spherical codes are known, based on approximations of completely positive functions and the Lovász theta number of a graph. This thesis extends these hierarchies to distance-avoiding sets and similar problems and to the sphere-packing problem, and proves their convergence to the maximum density. For distance-avoiding sets, additional hierarchies, such as the moment hierarchy, are introduced and shown to be stronger than the completely positive hierarchy, hence they also converge. Related hierarchies for compact packing problems are also investigate. These bounds are implemented for Witsenhausen's problem, which asks for the maximum fraction αn of the n-dimensional unit sphere that is coverable by a set avoiding orthogonal pairs; and for the t-almost-equiangular-set problem: finding the maximum size α(n,t) of a subset of the n-dimensional unit sphere in which every triple contains a pair with inner product t ∈ [−1,1). An analytic solution to this bound yields an enumeration of optimal constructions for n = 2 and $3$ when t ≥ 0.
Related
- Competing coherence geometries in positive maps: positivity hierarchies, atomicity, and optimal entanglement witnesses
- Quantum inflation and source-transfer hierarchies are complete for tree networks
- The complete spectrum of the linearized p-Laplacian at a Sobolev extremal
- An explicit bound on the extremal function for complete graph minors
- Complete centroaffine extremal hypersurfaces and centroaffine Bernstein conjecture
BibTeX
@misc{bekker2026optimization,
title = {{Optimization hierarchies for extremal geometry through complete positivity}},
author = {Bram Bekker},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34845},
eprint = {2609.34845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimization hierarchies for extremal geometry through complete positivity
AU - Bram Bekker
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34845
UR - https://arxiv.org/abs/2609.34845
AB - Completely positive functions are an extension of completely positive matrices. They are known to characterize maximal spherical codes and maximum-density distance-avoiding subsets of ℝ^n and certain compact metric spaces. This thesis expands this framework to related classes of problems in finite measure spaces and to the sphere-packing problem. For the latter, this is sharpened to show that the optimal sphere-packing density can be approximated using Schwartz functions. Converging hierarchies of semidefinite programming bounds on the size of optimal spherical codes are known, based on approximations of completely positive functions and the Lovász theta number of a graph. This thesis extends these hierarchies to distance-avoiding sets and similar problems and to the sphere-packing problem, and proves their convergence to the maximum density. For distance-avoiding sets, additional hierarchies, such as the moment hierarchy, are introduced and shown to be stronger than the completely positive hierarchy, hence they also converge. Related hierarchies for compact packing problems are also investigate. These bounds are implemented for Witsenhausen's problem, which asks for the maximum fraction α_n of the n-dimensional unit sphere that is coverable by a set avoiding orthogonal pairs; and for the t-almost-equiangular-set problem: finding the maximum size α(n,t) of a subset of the n-dimensional unit sphere in which every triple contains a pair with inner product t ∈ [−1,1). An analytic solution to this bound yields an enumeration of optimal constructions for n = 2 and $3$ when t ≥ 0.
ER -