The ham sandwich theorem asserts that, given bounded open sets in , there exists a hyperplane that bisects each of these sets , in the sense that each of the two half-spaces on either side of the hyperplane captures exactly half of the volume of . 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 bounded open sets in , there exists a hypersurface of degree (thus is a polynomial of degree such that the two semi-algebraic sets and capture half the volume of each of the . (More precisely, the degree will be at most , where is the first positive integer for which exceeds .) 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 finite sets in , there exists a hypersurface of degree , such that each of the two semi-algebraic sets and contain at most half of the points on (note that some of the points of can certainly lie on the boundary ). This can be iterated to give a useful cell decomposition:
Proposition 1 (Cell decomposition) Let be a finite set of points in , and let be a positive integer. Then there exists a polynomial of degree at most , and a decomposition
into the hypersurface and a collection of cells bounded by , such that , and such that each cell contains at most 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 and ), but it is a classical result (established independently by Oleinik-Petrovskii, Milnor, and Thom) that any degree hypersurface divides into 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 – to get the bound on connected components; one can instead observe that every bounded connected component has a critical point where , and one can control the number of these points by Bezout’s theorem, after perturbing slightly to enforce genericity, and then count the unbounded components by an induction on dimension.)
Remark 1 By setting as large as , we obtain as a limiting case of the cell decomposition the fact that any finite set of points in can be captured by a hypersurface of degree . This fact is in fact true over arbitrary fields (not just over ), 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 .
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 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 and a finite set of lines in , the set of incidences has cardinality
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.
Let us begin with a trivial bound:
Lemma 3 (Trivial bound) For any finite set of points and finite set of lines , we have .
The slickest way to prove this lemma is by the Cauchy-Schwarz inequality. If we let be the number of points incident to a given line , then we have
and hence by Cauchy-Schwarz
On the other hand, the left-hand side counts the number of triples with . Since two distinct points determine at most one line, one thus sees that the left-hand side is at most , and the claim follows.
Now we return to the Szemerédi-Trotter theorem, and apply the cell decomposition with some parameter . This gives a decomposition
into a curve of degree , and at most cells , each of which contains points. We can then decompose
By removing repeated factors, we may take to be square-free.
Let us first deal with the incidences coming from the cells . Let be the lines in that pass through the cell . Clearly
and thus by the trivial bound
Now we make a key observation (coming from Bezout’s theorem: each line in can meet at most cells , because the cells are bounded by a degree curve ). Thus
and hence by Cauchy-Schwarz, we have
Putting all this together, we see that
Now we turn to the incidences coming from the curve . Applying Bezout’s theorem again, we see that each line in either lies in , or meets in points. The latter case contributes at most incidences, so now we restrict attention to lines that are completely contained in . The points in the curve are of two types: smooth points (for which there is a unique tangent line to the curve ) and singular points (where and both vanish). A smooth point can be incident to at most one line in , and so this case contributes at most incidences. So we may restrict attention to the singular points. But by one last application of Bezout’s theorem, each line in can intersect the zero-dimensional set in at most points (note that each partial derivative of also has degree ), giving another contribution of incidences. Putting everything together, we obtain
for any . An optimisation in then gives the claim.
Remark 2 If one used the extreme case of the cell decomposition noted in Remark 1, one only obtains the trivial bound
On the other hand, this bound holds over arbitrary fields (not just over ), and can be sharp in such cases (consider for instance the case when is a finite field, consists of all the points in , and consists of all the lines in .)