How Large can a Spherical Set Without Two Orthogonal Vectors Be?


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!

About these ads

4 thoughts on “How Large can a Spherical Set Without Two Orthogonal Vectors Be?

  1. Pingback: Extremal Combinatorics VI: The Frankl-Wilson Theorem « Combinatorics and more

  2. Frank Vallentin

    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).

  3. Gil Kalai Post author

    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.

  4. Pingback: A. M. Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s