Optimization hierarchies for distance-avoiding sets in compact spaces

Witsenhausen’s problem asks for the maximum fraction <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript n"> <mml:semantics> <mml:msub> <mml:mi> α </mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\alpha _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis n minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(n-1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. The best upper bounds for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript n"> <mml:semantics> <mml:msub> <mml:mi> α </mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\alpha _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript n"> <mml:semantics> <mml:msub> <mml:mi> α </mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\alpha _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in low dimensions.