Bram Bekker

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 Rn 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 investigated. 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.

Witsenhausen’s problem asks for the maximum fraction αn of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. The best upper bounds for αn are given by extensions of the Lovász theta number. In this paper, optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, are extended to Witsenhausen’s problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds for αn in low dimensions.

For t ∈[-1, 1), a set of points on the (n-1)-dimensional unit sphere is called t-almost equiangular if among any three distinct points there is a pair with inner product t. We propose a semidefinite programming upper bound for the maximum cardinality α(n, t) of such a set based on an extension of the Lovász theta number to hypergraphs. This bound is at least as good as previously known bounds and for many values of n and t it is better. We also refine existing spectral methods to show that α(n, t) ≤2(n+1) for all n and t ≤0, with equality only at t = -1/n. This allows us to show the uniqueness of the optimal construction at t = -1/n for n ≤5 and to enumerate all possible constructions for n ≤3 and t ≤0.