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

Posted on May 22, 2009 by Gil Kalai

spherical

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.13975...)^{-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. Pingback: Extremal Combinatorics VI: The Frankl-Wilson Theorem « Combinatorics and more

  2. Frank Vallentin says:
    May 24, 2009 at 7:36 pm

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

    Reply
  3. Gil Kalai says:
    May 24, 2009 at 8:40 pm

    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.

    Reply

  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 comment