Witsenhausen’s Problem (1974): Let be a measurable subset of the -dimensional sphere . Suppose that does not contain two orthogonal vectors. How large can the -dimensional volume of be?
Conjecture: The maximum volume is attained by two open caps of diameter around the south pole and the north pole.
For simplicity, let us normalize the volume of to be 1.
What is known
What is known The Frankl-Wilson theorem (the version described in the previous post) gives the asymptotic bound , why?
Consider the set . (And suppose that where is a prime, and .) is a subset of .
Let be a subset of not containing two orthogonal vectors. Now, the intersection of every rotation of with has at most elements.
This gives 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 is not of that form we can suppose that is the largest integer of the form smaller than or equal to , and embed in by adding extra 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 .
What standard isoperimetry gives
If we assume that the angle between every two points in is less than , then a standard isoperimetric theorem (due to P. Levi) asserts that the volume of is maximized by an open cap of radius . But this is a stronger assumption.
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.