Tag Archive

You are currently browsing the tag archive for the ‘Ham sandwich theorem’ tag.

An incidence theorem in higher dimensions

17 March, 2011 in math.AG, math.CO, paper | Tags: , , , | by | 11 comments

Jozsef Solymosi and I have just uploaded to the arXiv our paper “An incidence theorem in higher dimensions“, submitted to Discrete and Computational Geometry. In this paper we use the polynomial Ham Sandwich method of Guth and Katz (as discussed previously on this blog) to establish higher-dimensional versions of the Szemerédi-Trotter theorem, albeit at the cost of an epsilon loss in exponents.

Recall that the Szemerédi-Trotter theorem asserts that given any finite set of points {P} and lines {L} in the plane {{\bf R}^2}, the number of incidences {I(P,L) := \{ (p,\ell) \in P \times L: p \in \ell \}} has the upper bound

\displaystyle |I(P,L)| \ll |P|^{2/3} |L|^{2/3} + |P| + |L|.

Apart from the constant factor, this bound is sharp. As discussed in this previous blog post, this theorem can be proven by the polynomial method, and the strategy can be rapidly summarised as follows. Select a parameter {D \geq 1}. By the polynomial Ham Sandwich theorem, one can divide {{\bf R}^2} into {O(D^2)} cell interiors, each with {O(|P|/D^2)} points, and incident to {O(|L|/D)} lines on the average, plus a boundary set which is an algebraic curve of degree {O(D)}. To handle the contribution of each cell interior, one uses a more elementary incidence bound (such as the bound {|I(P,L)| \ll |P| |L|^{1/2} + |L|} coming from the fact that two points determine at most one line); to handle the contribution on the cell boundary, one uses algebraic geometry tools such as Bezout’s theorem. One then combines all the bounds and optimises in {D} to obtain the result.

As a general rule, the contribution of the cell interiors becomes easier to handle as {D} increases, while the contribution of the cell boundaries become easier as {D} decreases. As such, the optimal value of {D} is often an intermediate one (in the case of Szemerédi-Trotter, the choice {D = |P|^{2/3} |L|^{-1/3}} is typical). Among other things, this requires some control of moderately high degree algebraic sets, though in this planar case {{\bf R}^2}, one only needs to control algebraic curves in the plane, which are very well understood.

In higher dimensions, though, the complexity of the algebraic geometry required to control medium degree algebraic sets increases sharply; compare for instance the algebraic geometry of ruled surfaces appearing in the three-dimensional work of Guth and Katz as discussed here, compared with the algebraic geometry of curves in the two-dimensional Szemerédi-Trotter theorem discussed here.

However, Jozsef and I discovered that it is also possible to use the polynomial method with a non-optimised value of {D}, and in particular with a bounded value {D=O(1)} of {D}, which makes the algebraic geometry treatment of the boundary significantly easier. The drawback to this is that the cell interiors can no longer be adequately controlled by trivial incidence estimates. However, if instead one controls the cell interiors by an induction hypothesis, then it turns out that in many cases one can recover a good estimate. For instance, let us consider the two-dimensional Szemerédi-Trotter theorem in the most interesting regime, namely when the {|P|^{2/3} |L|^{2/3}} term on the RHS is dominant. If we perform the cell decomposition with some small parameter {D}, then we obtain {O(D^2)} cells with {O(|P|/D^2)} points and {O(|L|/D)} lines on the average; applying the Szemerédi-Trotter theorem inductively to each of these cells, we end up with a total contribution of

\displaystyle O( D^2 ) \times O( |P|/D^2)^{2/3} \times O( |L|/D)^{2/3} = O( |P|^{2/3} |L|^{2/3} )

for the cell interiors, and so provided that one can also control incidences on the (low degree) cell boundary, we see that we have closed the induction (up to changes in the implied constants in the {O()} notation).

Unfortunately, as is well known, the fact that the implied constants in the {O()} notation degrade when we do this prevents this induction argument from being rigorous. However, it turns out this method does work nicely to give the weaker incidence bound

\displaystyle |I(P,L)| \ll_\epsilon |P|^{2/3+\epsilon} |L|^{2/3} + |P| + |L|

for any fixed {\epsilon > 0}; the point being that this extra epsilon of room in the exponents means that the induction hypothesis gains a factor of {D^{-\epsilon}} or so over the desired conclusion, allowing one to close the induction with no loss of implied constants if all the parameters are chosen properly. While this bound is weaker than the full Szemerédi-Trotter theorem, the argument is simpler in the sense that one only needs to understand bounded degree algebraic sets, rather than medium degree algebraic sets. As such, this argument is easier to extend to higher dimensions.

Indeed, as a consequence of this strategy (and also a generic projection argument to cut down the ambient dimension, as used in this previous paper with Ellenberg and Oberlin, and an induction on dimension), we obtain in our paper a higher-dimensional incidence theorem:

Theorem 1 (Higher-dimensional Szemerédi-Trotter theorem) Let {d \geq 2k}, and let {P} and {L} be finite sets of points and {k}-planes in {{\bf R}^d}, such that any two {k}-planes in {L} intersect in at most one point. Then we have {|I(P,L)| \ll_{k,\epsilon} |P|^{2/3+\epsilon} |L|^{2/3} + |P| + |L|} for any {\epsilon > 0}.

Something like the transversality hypothesis that any two {k}-planes in {L} intersect in at most one point is necessary, as can be seen by considering the example in which the points {P} are all collinear, and the {k}-planes in {L} all contain the common line. As one particular consequence of this result, we recover (except for an epsilon loss in exponents) the complex Szemerédi-Trotter theorem of Toth, whose proof was significantly more complicated; it also gives some matrix and quaternionic analogues, in particular giving new sum-product theorems in these rings. Note that the condition {d \geq 2k} is natural, because when the ambient dimension is less than {2k}, it is not possible for two {k}-planes to intersect in just one point. Using the generic projection trick, one can easily reduce to the critical case {d=2k}.

Actually, for inductive reasons, we prove a more general result than Theorem 1, in which the {k}-planes are replaced instead by {k}-dimensional real algebraic varieties. The transversality condition is now that whenever a point {p} is incident to two such varieties {\ell, \ell'}, that the tangent cones of {\ell} and {\ell'} at {p} only intersect at {p}. (Also for technical reasons, it is convenient to consider a partial subset {{\mathcal I}} of incidences in {I(P,L)}, rather than the full set of incidences. Indeed, it seems most natural to consider the triplet

\displaystyle \begin{array}{ccccc} \\ && {\mathcal I} && \\ & \swarrow & & \searrow & \\ P & & & & L \end{array}

as a single diagram, rather than to consider just the sets {P} and {L}.)

The reason for working in this greater level of generality is that it becomes much easier to use an induction hypothesis to deal with the cell boundary; one simply intersects each variety {\ell} in {L} with the cell boundary, which usually lowers the dimension of the variety by one. (There are some exceptional cases in which {\ell} is completely trapped inside the boundary, but due to the transversality hypothesis, this cannot contribute many incidences if the ambient dimension is {2k} (so the cell boundary is only {2k-1} dimensional).)

As one application of this more general incidence result, we almost extend a classic result of Spencer, Szemerédi, and Trotter asserting that {n} points in the plane {{\bf R}^2} determine {O(n^{4/3})} unit distances from {{\bf R}^2} to {{\bf C}^2}, at the cost of degrading {O(n^{4/3})} to {O_\epsilon(n^{4/3+\epsilon})}.

The Szemeredi-Trotter theorem via the polynomial ham sandwich theorem

18 February, 2011 in expository, math.AG, math.CO, math.GT | Tags: , , | by | 23 comments

The ham sandwich theorem asserts that, given {d} bounded open sets {U_1,\ldots,U_d} in {{\bf R}^d}, there exists a hyperplane {\{ x \in {\bf R}^d: x \cdot v = c \}} that bisects each of these sets {U_i}, in the sense that each of the two half-spaces {\{ x \in {\bf R}^d: x \cdot v < c \}, \{ x \in {\bf R}^d: x \cdot v > c \}} on either side of the hyperplane captures exactly half of the volume of {U_i}. The shortest proof of this result proceeds by invoking the Borsuk-Ulam theorem.

A useful generalisation of the ham sandwich theorem is the polynomial ham sandwich theorem, which asserts that given {m} bounded open sets {U_1,\ldots,U_m} in {{\bf R}^d}, there exists a hypersurface {\{ x \in {\bf R}^d: Q(x)=0\}} of degree {O_d( m^{1/d} )} (thus {P: {\bf R}^d \rightarrow {\bf R}} is a polynomial of degree {O(m^{1/n})} such that the two semi-algebraic sets {\{ Q > 0 \}} and {\{ Q < 0\}} capture half the volume of each of the {U_i}. (More precisely, the degree will be at most {D}, where {D} is the first positive integer for which {\binom{D+d}{d}} exceeds {m}.) This theorem can be deduced from the Borsuk-Ulam theorem in the same manner that the ordinary ham sandwich theorem is (and can also be deduced directly from the ordinary ham sandwich theorem via the Veronese embedding).

The polynomial ham sandwich theorem is a theorem about continuous bodies (bounded open sets), but a simple limiting argument leads one to the following discrete analogue: given {m} finite sets {S_1,\ldots,S_m} in {{\bf R}^d}, there exists a hypersurface {\{ x \in {\bf R}^d: Q(x)=0\}} of degree {O_d( m^{1/d} )}, such that each of the two semi-algebraic sets {\{ Q > 0 \}} and {\{ Q < 0\}} contain at most half of the points on {S_i} (note that some of the points of {S_i} can certainly lie on the boundary {\{Q=0\}}). This can be iterated to give a useful cell decomposition:

Proposition 1 (Cell decomposition) Let {P} be a finite set of points in {{\bf R}^d}, and let {D} be a positive integer. Then there exists a polynomial {Q} of degree at most {D}, and a decomposition

\displaystyle {\bf R}^d = \{ Q = 0\} \cup C_1 \cup \ldots \cup C_m

into the hypersurface {\{Q=0\}} and a collection {C_1,\ldots,C_m} of cells bounded by {\{P=0\}}, such that {m = O_d(D^d)}, and such that each cell {C_i} contains at most {O_d( |P|/D^d )} points.

A proof is sketched in this previous blog post. The cells in the argument are not necessarily connected (being instead formed by intersecting together a number of semi-algebraic sets such as {\{ Q > 0\}} and {\{Q<0\}}), but it is a classical result (established independently by Oleinik-Petrovskii, Milnor, and Thom) that any degree {D} hypersurface {\{Q=0\}} divides {{\bf R}^d} into {O_d(D^d)} connected components, so one can easily assume that the cells are connected if desired. (Incidentally, one does not need the full machinery of the results in the above cited papers – which control not just the number of components, but all the Betti numbers of the complement of {\{Q=0\}} – to get the bound on connected components; one can instead observe that every bounded connected component has a critical point where {\nabla Q = 0}, and one can control the number of these points by Bezout’s theorem, after perturbing {Q} slightly to enforce genericity, and then count the unbounded components by an induction on dimension.)

Remark 1 By setting {D} as large as {O_d(|P|^{1/m})}, we obtain as a limiting case of the cell decomposition the fact that any finite set {P} of points in {{\bf R}^d} can be captured by a hypersurface of degree {O_d(|P|^{1/m})}. This fact is in fact true over arbitrary fields (not just over {{\bf R}}), and can be proven by a simple linear algebra argument (see e.g. this previous blog post). However, the cell decomposition is more flexible than this algebraic fact due to the ability to arbitrarily select the degree parameter {D}.

The cell decomposition can be viewed as a structural theorem for arbitrary large configurations of points in space, much as the Szemerédi regularity lemma can be viewed as a structural theorem for arbitrary large dense graphs. Indeed, just as many problems in the theory of large dense graphs can be profitably attacked by first applying the regularity lemma and then inspecting the outcome, it now seems that many problems in combinatorial incidence geometry can be attacked by applying the cell decomposition (or a similar such decomposition), with a parameter {D} to be optimised later, to a relevant set of points, and seeing how the cells interact with each other and with the other objects in the configuration (lines, planes, circles, etc.). This strategy was spectacularly illustrated recently with Guth and Katz‘s use of the cell decomposition to resolve the Erdös distinct distance problem (up to logarithmic factors), as discussed in this blog post.

In this post, I wanted to record a simpler (but still illustrative) version of this method (that I learned from Nets Katz), namely to provide yet another proof of the Szemerédi-Trotter theorem in incidence geometry:

Theorem 2 (Szemerédi-Trotter theorem) Given a finite set of points {P} and a finite set of lines {L} in {{\bf R}^2}, the set of incidences {I(P,L):= \{ (p,\ell) \in P \times L: p \in \ell \}} has cardinality

\displaystyle |I(P,L)| \ll |P|^{2/3} |L|^{2/3} + |P| + |L|.

This theorem has many short existing proofs, including one via crossing number inequalities (as discussed in this previous post) or via a slightly different type of cell decomposition (as discussed here). The proof given below is not that different, in particular, from the latter proof, but I believe it still serves as a good introduction to the polynomial method in combinatorial incidence geometry.

Read the rest of this entry »

The Kakeya conjecture and the Ham Sandwich theorem

27 November, 2008 in expository, math.AG, math.AT, math.CA, math.CO | Tags: , , , , | by | 22 comments

One of my favourite family of conjectures (and one that has preoccupied a significant fraction of my own research) is the family of Kakeya conjectures in geometric measure theory and harmonic analysis.  There are many (not quite equivalent) conjectures in this family.  The cleanest one to state is the set conjecture:

Kakeya set conjecture: Let n \geq 1, and let E \subset {\Bbb R}^n contain a unit line segment in every direction (such sets are known as Kakeya sets or Besicovitch sets).  Then E has Hausdorff dimension and Minkowski dimension equal to n.

One reason why I find these conjectures fascinating is the sheer variety of mathematical fields that arise both in the partial results towards this conjecture, and in the applications of those results to other problems.  See for instance this survey of Wolff, my Notices article and this article of Łaba on the connections between this problem and other problems in Fourier analysis, PDE, and additive combinatorics; there have even been some connections to number theory and to cryptography.  At the other end of the pipeline, the mathematical tools that have gone into the proofs of various partial results have included:

[This list is not exhaustive.]

Very recently, I was pleasantly surprised to see yet another mathematical tool used to obtain new progress on the Kakeya conjecture, namely (a generalisation of) the famous Ham Sandwich theorem from algebraic topology.  This was recently used by Guth to establish a certain endpoint multilinear Kakeya estimate left open by the work of Bennett, Carbery, and myself.  With regards to the Kakeya set conjecture, Guth’s arguments assert, roughly speaking, that the only Kakeya sets that can fail to have full dimension are those which obey a certain “planiness” property, which informally means that the line segments that pass through a typical point in the set must be essentially coplanar. (This property first surfaced in my paper with Katz and Łaba.)  Guth’s arguments can be viewed as a partial analogue of Dvir’s arguments in the finite field setting (which I discussed in this blog post) to the Euclidean setting; in particular, both arguments rely crucially on the ability to create a polynomial of controlled degree that vanishes at or near a large number of points.  Unfortunately, while these arguments fully settle the Kakeya conjecture in the finite field setting, it appears that some new ideas are still needed to finish off the problem in the Euclidean setting.  Nevertheless this is an interesting new development in the long history of this conjecture, in particular demonstrating that the polynomial method can be successfully applied to continuous Euclidean problems (i.e. it is not confined to the finite field setting).

In this post I would like to sketch some of the key ideas in Guth’s paper, in particular the role of the Ham Sandwich theorem (or more precisely, a polynomial generalisation of this theorem first observed by Gromov).

Read the rest of this entry »

Archives