## The problem

Witsenhausen’s Problem (1974): Let $A$ be a measurable subset of the $d$-dimensional sphere $S^d = \{x\in {\bf R}^{d+1}:\|x\|=1\}$. Suppose that $A$ does not contain two orthogonal vectors. How large can the $d$-dimensional volume of $A$ be?

## A Conjecture

Conjecture: The maximum volume is attained by two open caps of diameter $\pi/4$ around the south pole and the north pole.
For simplicity, let us normalize the volume of $S^d$ to be 1.

## What is known

What is known The Frankl-Wilson theorem (the version described in the previous post) gives the asymptotic bound $Vol(A) \le 2^{(H(1/4)-1)n}=(1.2...)^{-d}$, why?
Consider the set $C_n=(1/\sqrt{n})\{-1,1\}^n$. (And suppose that $n=4p$ where $p$ is a prime, and $d+1=n$.) $C_n$ is a subset of $S^d$.

Let $A$ be a subset of $S^d$ not containing two orthogonal vectors. Now, the intersection of every rotation of $A$ with $C_n$ has at most $4{{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}$ elements.

This gives $Vol(A) \le (4{{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}})/2^n$ and implies the asymptotic bound we described.

This is a beautiful application of the Frankl-Wilson theorem which goes back essentially to the original paper.
(If $d+1$ is not of that form we can suppose that $n$ is the largest integer of the form $n=4p$ smaller than or equal to $d+1$, and embed $C_n$ in $S^d$ by adding extra $n-d$ coordinates and setting them to zero. Using the density of primes we obtain the required result.)

## But we want more!

The proposed example has volume which assymptotically behaves like $(1/\sqrt{2})^n$.

## What standard isoperimetry gives

If we assume that the angle between every two points in $A$ is less than $\pi/2$, then a standard isoperimetric theorem (due to P. Levi) asserts that the volume of $A$ is maximized by an open cap of radius $\pi/4$. But this is a stronger assumption.

## Other methods?

Frankl-Rodl theorem gives weaker (but still exponentially small) bounds. The linear programming method for codes may lead to exponentially small bounds. [Update: see comment by Frank Vallentin.]

## Can the polynomial method help (further)?

I think that the polynomial method (the method we presented to prove Frankl-Wilson’s theorem) is the best avenue for better results. Can it give better results? This is something we should discuss. We should try to replace vectors with plus-minus one entries by more general vectors, perhaps with some weights, and give it a try. So far, no one has succeeded, but I do not know why (and I don’t know if anyone has tried sufficiently hard). The ad-hoc trick from the proof of Frankl-Wilson seems to be one thing that does not generalize so nicely.

## Ideas, comments are most welcome!

This entry was posted in Open problems. Bookmark the permalink.

### 4 Responses to How Large can a Spherical Set Without Two Orthogonal Vectors Be?

1. Frank Vallentin says:

Dear Gil,

thanks for the problem.

The following (semi-infinite) linear program (which is the continuous version of Delsarte’s linear programming bound for discrete point configurations) gives an upper bound for the volume of a measurable set A on the unit sphere S^d which does not contain vectors having inner product exactly t:

minimize z_0
s.t. z_0 + z_1 >= 1, and z_0 + P^d_k(t) >= 0, k = 1, 2, 3, …

where P^d_k is the ultraspherical polynomial of degree k normalized by P^d_k(0) = 1.

For t = 0 this gives only 1/(d+1). However, for t > 0 one gets exponentially small bounds in d.

Using semidefinite programming also does not seem to improve things for t = 0: It stays at 1/(d+1) (at least numerically, I didn’t try to make it rigorous).

2. Gil Kalai says:

Dear Frank,

This is very interesting and quite mysterious. It is already very surprising that you get exponentially small bound in d for t>0. (we shouldnt forget that t0. you can consider balls of radius a around points of a spherical code of distance b and try to optimize over appropriate a and b. But maybe there are better examples.