Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors

raigor

Andrei Raigorodskii

(This post follows an email by Aicke Hinrichs.)

In a previous post we discussed the following problem:

Problem: 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?

Setting the volume of the sphere to be 1, the Frankl-Wilson theorem gives a lower bound (for large d) of  1.203^{-d},
2) The double cap conjecture would give a lower bound (for large d) of 1.414^{-d}.

A result of A. M. Raigorodskii from 1999 gives a better bound of 1.225^{-d}. (This has led to an improvement concerning the dimensions where a counterexample for Borsuk’s conjecture exists; we will come back to that.) Raigorodskii’s method supports the hope that by considering clever configurations of points instead of just \pm 1-vectors and applying the polynomial method (the method of proof we described for the Frankl-Wilson theorem) we may get closer to and perhaps even prove the double-cap conjecture.

What Raigorodskii did was to prove a Frankl-Wilson type result for vectors with 0,\pm1 coordinates with a prescribed number of zeros. Here is the paper.

Now, how can we beat the 1.225^{-d} record???

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

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

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here is an open discussion post around Roth theorem (March 2009). Here are two “open discussion” posts on the cap set problem (first, and second) from Gowers’s blog (January 2011). These posts include several interesting Fourier theoretic approaches towards improvement of the Roth-Meshulam bound. The second post describes a startling example by Seva Lev.

Suppose that the maximum size of a cap set in \Gamma(n)=\{1,2,3\}^n is n/g(n).  Here is an obvious fact:

The maximum size of a set F in G with the property that every x,y\in G (x \ne y) satisfy x+y \notin G is at most the maximum size of a cap set in G

Proof: Indeed the condition for F is stronger than being a cap set. We require for every x,y \in F x \ne y not only that x+y \notin F but even x+y \notin G.  

Part C.  A more direct relation between Frankl-Rodl’s theorem and the cap set problem and all sorts of fine gradings on subsets of {1,2,…,n}.

In part A we moved from sets avoiding affine lines (cap sets) to sets avoiding “modular lines” and used the Frankl-Rodl theorem to deal with the latter. This may look artificial. Here is a simpler connection between the cap set problem and the Frankl-Rodl theorem.

17. Why weaker forms of the Frankl-Rodl Theorem follow from upper bounds on cap sets.

Consider Continue reading

Around the Cap-Set problem (B)

Part B: Finding special cap sets

This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.)  I will use here a different notation than in part A to make it compatible with various posts of polymath1 which consider similar objects. We write \Gamma(n) = \{0,1,2\}^n and \Gamma_{a,b,c} denotes all vectors of length n with a 0’s, b 1’s and c 2’s.

An affine line are three vectors x,y,z so that x_i + y_i + z_i = 0 (mod~3) for every i. A cap set is a subset of \Gamma(n) without an affine line. The cap set problem asks for the maximum size of a cap set. For information on the cap set problem itself look here.  For questions regarding density of sets avoiding other types of lines look here.

In the first part we considered the case that n=3m and considered “modular lines” , i.e., three vectors  x,y,z so that the number of solutions to x_i+y_i+z_i=a(mod~3)  is divisible by m for every a. When n is divisible by 9 the Frankl-Rodl theorem implies that a subset of \Gamma with more than (3-\epsilon)^n elements must contain a modular line, and even a modular line with two equal elements. (Question: does the same statement follow from Frankl-Rodl theorem when n is divisible by 3 and not by 9?) 

10. Some propositions in the desired direction.

Proposition 6:  Suppose that n=3m, and that m=1 (mod~3). If every set of size > (3-\epsilon)^n has a modular line, then every set of size > (3-\epsilon)^n has a modular line which is either an affine  line, or  the number of is such that x_i + y_i + z_i =a is precisely m for a=0,1,2.

(So we can get rid of a few “types” of modular lines which are not really affine  lines, but not all of them.)

Proposition 6 follows from the much more transparent  proposition:

Proposition 7:  There are sets of constant density which do not contain a modular line \{x,y,z\} for which the numbers of solutions of x_i + y_i + z_i =a(mod~3) for a=0,1,2 is never a permutation of (0,m,2m).

Proof: Consider all vectors where the sum of the coordinates is zero modulo 3. This property is preserved under sums but it does not hold for the sums we are looking at. (All the quantities: 0+m+4m, 0+0 +4m, 0+2m+2m, 0+2m+0, m, 2m are not divisible by 3.)  

11. A strong variant form of the problem

Here are innocent-looking variants of Problem 1: (the existence of modular lines)

Problem 6:  How large can a set F in \Gamma(7m)  be without three vectors x, y and z such that |\{i:x_i+y_i+z_i=a\}|=o(mod~m)  for a=0,1,2,3,4,5,6?

Problem 7:  How large can a set F in \Gamma (7m)  be without three vectors x, y and z such that |\{i: x_1+y_i+z_i=a\}| = m for every a=0,1,2,3,4,5,6? Continue reading

A Problem on Planar Percolation

Conjecture (Gady Kozma):  Prove that the critical probability for planar percolation on a Cayley graph of the group Z^2 is always an algebraic number.

Gady  mentioned this conjecture in his talk here about percolation on infinite Cayley graphs.  (Update April 30: Today Gady mentioned to me an even bolder question: to show that for every group \Gamma, either all critical probabilities of its Cayley graphs are algebraic, or none is!!;  I recall a similarly bold conjecture regarding the property of being an expander which turned out to be false but was fruitful nevertheless.)

Many problems Continue reading

(Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Richard_Stanley-1

Richard Stanley

This post is authored by Eran Nevo. (It is the second in a series of five posts.)

The g-conjecture: the commutative algebra connection

Let K be a triangulation of a (d-1)-dimensional sphere. Stanley’s idea was to associate with K a ring R, and study the relations between algebraic properties of R and combinatorial properties of K.

Face ring

Fix a field k. The face ring (Stanley-Reisner ring) of K over k is k[K]=k[x_{1},..,x_{n}]/I_{K} where I_{K} is the homogenous ideal generated by the monomials whose support is not in K, \{\prod_{i\in S}x_i:\ S\notin K\}. For example, if K is the boundary of a triangle, then k[K]=k[x,y,z]/(xyz). k[K] is graded by degree (variables have degree one, 1 has degree zero), and let’s denote the degree i part by k[K]_i. This part is a finite dimensional k-vector space and we can collect all these dimensions in a sequence, or a series, called the Hilbert series of k[K], which carries the same information as f(K). More precisely,

hilb(k[K]):=\sum_{i\geq 0}\dim_k k[K]_i t^i = \frac{h_0(K)+h_1(K)t+...+h_d(K)t^d}{(1-t)^d}

(recall that K is (d-1)-dimensional).

Cohen-Macaulay (CM) ring

The ring k[K] is called Cohen Macaulay (CM) if there are d elements \Theta=\{\theta_1,..,\theta_d\} in k[K]_1 such that k[K] is a free k[\Theta]-module. As hilb(k[\Theta])=\frac{1}{(1-t)^d}, the numerical consequence is that hilb(k[K]/(\Theta))=h(K) (we use h both as a vector and as a polynomial, with the obvious identification).

Macaulay (revisited) showed that the Hilbert series of standard rings (=quatient of the polynomial ring by a homogenous ideal) are exactly the M-vectors (sequences).

A theorem of Riesner characterizes the simplicial complexes K with a CM face ring over a fixed field k in terms of the homology of K and its face links (with $k$-coefficients). It follows that if K is a simplicial sphere then k[K] is CM, hence h(K) is an $M$ vector! This gives more inequalities on f(K). This is also how Stanley proved the Upper Bound Conjecture, for face number of spheres: It follows that if K is a (d-1)-sphere with n vertices, and C(d,n) is the boundary of the cyclic d-polytope with n vertices, then for every i, f_i(K)\leq f_i(C(d,n)). This is as h_i(K)\leq \binom{n-d+i-1}{i}=h_i(C(d,n)).

Hard Lefschetz

Let K be the boundary of a simplicial d-polytope. Stanley observed that the hard Lefschetz theorem for toric varieties, an important theorem in algebraic geometry, translates in the language of face rings as follows: there exists \Theta as above and \omega\in k[K]_1 such that the maps

w^{d-2i}: (k[K]/(\Theta))_i\rightarrow (k[K]/(\Theta))_{d-i}

are isomorphisms between those vector spaces for any integer 0\leq i\leq \frac{d}{2}. In particular, w: (k[K]/(\Theta))_{i-1}\rightarrow (k[K]/(\Theta))_{i} is injective for 1\leq i\leq \frac{d}{2}. Thus, the quotient ring k[K]/(\Theta, \omega) has Hilbert series starting with g(K). This means, again by Macaulay theorem, that g(K) is an M-vector!

Later, in 1993, McMullen gave a different proof of this part of his conjectured g-theorem. His proof actually proves hard Lefschetz for this case. See McMullen’s survey paper `Polyhedra and polytopes: algebra and combinatorics’.

Problems

Does hard Lefschetz theorem hold for non polytopal spheres?

Can you think of examples of simplicial spheres which cannot be realized as the boundary of convex polytopes?

How the g-Conjecture Came About

This post complements Eran Nevo’s first  post on the g-conjecture

1) Euler’s theorem

euler1

Euler

Euler’s famous formula V-E+F=2 for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close to this formula a century earlier.) The formula for d-dimensional polytopes P is

f_0(P)-f_1(P)+f_2(P)+\dots+(-1)^{d-1}f_{d-1}(P)=1-(-1)^d.

The first complete proof (in high dimensions) was provided by Poincare using algebraic topology. Earlier geometric proofs were based on “shellability” of polytopes which was only proved a century later. But there are elementary geometric proofs that avoid shellability.

2) The Dehn-Sommerville relations

Dehn

Consider a 3-dimensional simplicial polytope, – Continue reading

(Eran Nevo) The g-Conjecture I

This post is authored by Eran Nevo. (It is the first in a series of five posts.)

mcmullen

Peter McMullen

The g-conjecture

What are the possible face numbers of triangulations of spheres?

There is only one zero-dimensional sphere and it consists of 2 points.

The one-dimensional triangulations of spheres are simple cycles, having n vertices and n edges, where n\geq 3.

The 2-spheres with n vertices have 3n-6 edges and 2n-4 triangles, and n can be any integer \geq 4. This follows from Euler formula.

For higher-dimensional spheres the number of vertices doesn’t determine all the face numbers, and for spheres of dimension \geq 5 a characterization of the possible face numbers is only conjectured! This problem has interesting relations to other mathematical fields, as we shall see. Continue reading

An Open Discussion and Polls: Around Roth’s Theorem

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

How does g(n) behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is?

Update 1: for the discussion: Here are a few more specific questions that we can wonder about and discuss.

1) Is the robustness of Behrend’s bound an indication that the truth is in this neighborhood.

2) Why arn’t there analogs for Salem-Spencer and Behrend’s constructions for the cup set problem?

3) What type of growth functions can we expect at all as the answer to such problems?

4) Where is the deadlock in improving the upper bounds for AP-free sets?

5) What new kind of examples one should try in order to improve the lower bounds? Are there some directions that were already extensively explored?

6) Can you offer some analogies? Other problems that might be related?

 

Continue reading