ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Witsenhausen’s problem [6] asks for the largest measurable set on a unit sphere such that no two points in the set are orthogonal. More precisely, let S n−1 = {x \in Rn : kxk = 1} be the n-dimensional unit sphere, \omega be the standard surface measure, and \omegan the total measure of the sphere. We define \alphan = sup{\omega(I)/\omegan : I \subset S n−1 does not contain orthogonal pairs}. The Double Cap Conjecture claims that the largest such set is achieved by taking the union of two open antipodal spherical caps of angular size \pi/4, i.e. {x \in S n−1 : ke \cdot xk > cos(\pi/4)}, for some fixed point e \in S n−1 . Optimality of this set was conjectured by Kalai [3, Conjecture 2.8]. We model this problem as an independent set problem on a graph. Let G = (S n−1 , E) be a graph with vertex set S n−1 . Two points x, y \in S n−1 share an edge if and only if x \cdot y = 0, i.e. if and only if they are orthogonal. The sets on the sphere avoiding orthogonal pairs are exactly the independent sets of this graph. SDP hierarchies for distance-avoiding sets on compact spaces Bram Bekker (joint work with Olga Kuryatnikova, Fernando Mário de Oliveira Filho, Juan C. Vera)

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.