Subsets with distinct volumes

Today I wish to mention another new result related to distinct distances. This time it is this paper by Gasarch, Harris, Ulrich, and Zbarsky. I (or rather, google scholar) found this paper on Gasarch’s website (next to a disclaimer stating that this is a work in progress and might be incorrect). [Update (Aug 2013): as commented by David Conlon, these results are not in their final form, and an updated version including also David Conlon and Jacob Fox should appear in the not-too-distant future.] [Update #2 (Jan 2014): The updated version, containing six authors, can be found here.]

The paper contains various results, all related to a generalization of a family of problems that I recently surveyed. Following the notation in the paper, h_{a,d}(n)  concerns distinct volumes of sets of (a-1)  -dimensional simplices (i.e., simplices that are determined by a  points) in {\mathbb R}^d  . Specifically, h_{a,d}(n)  denotes the maximum number satisfying that for every set of n  points in {\mathbb R}^d  , with no a  points on a common (a-2)  -flat, there exists a subset of h_{a,d}(n)  points that do not determine two (a-1)  -dimensional simplices with the same volume.

For example, the case of h_{2,2}(n)  is about distinct distances in the plane. That is, h_{2,2}(n)  is the maximum number such that any set of n  points in {\mathbb R}^2  contains a subset of h_{2,2}(n)  points that do not determine any distance more than once. Thus, the proof of Charalambides (which I also described here) implies the bound h_{2,2}(n) = \Omega(n^{1/3}/\log^{1/3} n)  .

As another example, h_{3,2}(n)  is the maximum number such that any set of n  points in {\mathbb R}^2  , with no three collinear, contains a subset of h_{3,2}(n)  points that do not determine two triangles with the same area. Consider the set of vertices of a regular n  -gon, as in the following figure.

nGon

Such a set does not contain three collinear points, and any triangle area appears \Omega(n)  times. This immediately implies h_{3,2}(n)= O(n^{2/3})  (since any asymptotically larger subset with no repeated triangle areas would determine \omega(n^2)  distinct areas). A somewhat similar result by Iosevich, Roche-Newton, and Rudnev states that for any set \cal P  of n  points in the plane (no three collinear), and for any point p\in{\cal P}  , there are \Omega(n/log n)  distinct areas of triangles that are spanned by p  together with two other points of \cal P  .

Continue reading

Two questions about distinct distances

While working with Joshua Zahl, we stumbled upon a couple of problems related to distinct distances. In addition to being useful to us, I think that these problems are interesting on their own, since they seem to shed light on the structure of point sets that determine a small number of distinct distances. I will now present these two problems.

Let {\cal P}_1  be a set of n  points on the x  -axis and let {\cal P}_2  be a set of n  points on the y  -axis (or on any other two perpendicular lines). Let D({\cal P}_1,{\cal P}_2)  denote the number of distinct distances in {\cal P}_1\times{\cal P}_2  (i.e., distances between points from different sets). It is well known that it is possible to have D({\cal P}_1,{\cal P}_2)=O(n)  . An example is depicted in the following figure.

perpendicular

Let {\cal P} = {\cal P}_1 \cup {\cal P}_2  . My first question is whether it is possible to have D({\cal P})=O(n)  . My intuition is that not only this is impossible, but that D({\cal P})  must be significantly larger; perhaps it must be almost quadratic in n  (it is not difficult to obtain an example where D({\cal P}) = O(n^2/\sqrt{\log n})  ). I will now try to explain why.

Let A  denote the set of x  -coordinates of the points of {\cal P}_1  and let B  denote the set of y  -coordinates of the points of {\cal P}_2  . We set A^2=\{a_1^2,\ldots,a_n^2\}  (notice the difference from the standard notation A\cdot A  ). The set of distances spanned by {\cal P}_1\times{\cal P}_2  is A^2+B^2  . According to Freiman’s theorem, if |A^2+B^2|  is small, then A^2  and B^2  are contained in generalized arithmetic progressions of some bounded size (see also Ruzsa’s paper).

Definition 1. Let q_1,\ldots,q_d,a \in {\mathbb R}  and let \ell_1,\ldots,\ell_d  be positive integers. A d  -dimensional generalized arithmetic progression is a set of the form

P=\{a + \sum_{i=1}^d x_iq_i |  0 \le x_i \le \ell_i \}.

The size of the generalized arithmetic progression is \|P\|=\prod_{i=1}^d (\ell_i+1)  .

For D({\cal P}_1)  to be small, A  also has to be contained in a generalized arithmetic progression. My conjecture is that D({\cal P})  cannot be small since it is impossible for both A  and A^2  to be contained in general arithmetic progressions of some bounded size.

Continue reading

Polynomial partitioning: the basics (part 3)

This is the third in my series of posts about the basics of polynomial partitioning. In the first post of the series we presented the basics of polynomial partitioning and showed how the technique can be used to prove the Szemerédi-Trotter theorem. In the second post we presented Guth and Katz’s proof of the polynomial partitioning theorem. In this post, we compare polynomial partitioning to a previous “popular” partitioning technique.

Several partitioning techniques existed before Guth and Katz introduced polynomial partitioning, and the most common one was probably cuttings (e.g., see Chapter 4 of the book Lectures on discrete geometry by Matoušek). For example, in the proof of the Szemerédi-Trotter theorem that was presented in the previous post, it is rather simple to replace the polynomial partitioning with a cutting while obtaining the same bound (e.g., see here). We discuss the differences and the similarities between the two techniques. We do not explain the basics of cuttings, and assume that the reader is familiar with them.

We start by considering the planar case. Let \cal P  be a set of m  points and let \cal C  be a set of n  constant-degree curves, both in {\mathbb R}^2  . An r  -partitioning polynomial f  for \cal P  has degree O(\sqrt{r})  , and each cell in the corresponding partition contains at most m/r  points of \cal P  . According to Warren’s theorem (Theorem 3 in the first post of the series), the number of cells in this partition is O(r)  . In “contrast”, a (1/\sqrt{r})  -cutting partitions the plane into O(r)  cells such that every cell is intersected by at most n/\sqrt{r}  curves of \cal C  . Thus, it might seem as if the two techniques are complementary, but we now show that they are equivalent in the planar case.

Continue reading

Polynomial partitioning: the basics (part 2)

This is the second in my series of posts about the basics of polynomial partitioning. In the first post of the series we presented the basics of polynomial partitioning and showed how the technique can be used to prove the Szemerédi-Trotter theorem. In this post we present Guth and Katz’s proof of the polynomial partitioning theorem. We first repeat the statement of the theorem.

Theorem 1 (Polynomial partitioning). Let \cal P  be a set of m  points in {\mathbb R}^d  . Then for every 1< r \le m  , there exists an r  -partitioning polynomial f \in {\mathbb R}[x_1,\ldots, x_d]  of degree O(r^{1/d})  .

To prove Theorem 1, we recall the discrete version of the ham sandwich theorem (e.g., see this paper). A hyperplane h  in {\mathbb R}^d  bisects a finite point set S\subset {\mathbb R}^d  if each of the two open halfspaces bounded by h  contains at most |S|/2  points of S  . The bisecting hyperplane may contain any number of points of S  .

Theorem 2. Every d  finite point sets S_1,\ldots,S_d \subset {\mathbb R}^d  can be simultaneously bisected by a hyperplane.

A planar example of Theorem 2 is depicted in the following figure, where both the blue set and the orange set are bisected.

PlanarBisection

We use Theorem 2 to prove the following theorem, which is the discrete version of the polynomial ham sandwich theorem. A polynomial f  in {\mathbb R}[x_1,\ldots,x_d]  bisects a finite point set S\subset {\mathbb R}^d  if f(p) > 0  for at most |S|/2  points p \in S  and f(p) < 0  for at most |S|/2  points p\in S  . The zero set Z(f)  may contain any number of points of S  .

Theorem 3 (Stone and Tukey). Let S_1,\ldots, S_t \subset {\mathbb R}^d  be t  finite point sets, and let D  be the smallest integer such that \binom{D+d}{d}-1\ge t  . Then there exists a nonzero polynomial f\in {\mathbb R}[x_1,\ldots,x_d]  of degree at most D  that simultaneously bisects all of the sets S_i  .

Continue reading

Things are moving fast!

Lately exciting new results concerning distinct distances are constantly being discovered. Marcos Charalambides just uploaded this paper to arXiv. The main result of the paper is the following.

Theorem 1 (Charalambides). Consider a curve \gamma \subset {\mathbb R}^d  of degree m  , and let \cal P  be a set of n  points that are contained in \gamma  . If no irreducible component of \gamma  is an algebraic helix, then the number of distinct distances that are determined by \cal P  is \Omega(n^{5/4})  (where the constant of proportionality depends on d  and m  ).

Algebraic helices are lines and geodesics of the Clifford torus, which is the surface that is parameterized as

(u_1,\cdots,u_k)\to(\alpha_1\cos u_1,\alpha_1\sin u_1,\cdots,\alpha_k\cos u_k,\alpha_k\sin u_k)\subset{\mathbb R}^{2k},

where 2k\le d  and \alpha_1,\cdots,\alpha_k >0  are constants. One reason why I find this result quite interesting is its connection to characterizing sets that determine a small number of distinct distances (say, o(n)  distinct distances; see a brief discussion in this post). Only a few properties of such sets are known. Theorem 1 implies that if \cal P  is a planar n  -point set that determines o(n)  distinct distances, then no constant degree curve, except possibly for planar algebraic helices, can contain \Omega(n^{4/5})  points of \cal P  .

Charalambides states that “the proof relies on a link to a certain structural rigidity question on curves”. I still need time to digest how this proof works, but I am always excited to see new connections between combinatorial geometry problems and other parts of math!

Polynomial partitioning: the basics (part 1)

Guth and Katz’s seminal work provided an almost tight bound for Erdős’s planar distinct distances problem. One can regard the proof of this bound as consisting of four main tools:

  • A reduction from the distinct distances problem to a problem about line intersections in {\mathbb R}^3  . This part is referred to as the Elekes-Sharir reduction or as the Elekes-Sharir framework.
  • The introduction of polynomial partitioning.
  • Applying 19th century analytic geometry tools that are related to ruled surfaces, such as flecnode polynomials.
  • The polynomial technique presented in Guth and Katz’s previous paper. (That is, relying on the existence of a polynomial of a small degree that vanishes on a given point set to reduce incidence problems between points and lines to the interactions between the lines and the algebraic variety which is the zero set of the polynomial.)
We already discussed the Elekes-Sharir framework from item (i) here, here, and here (and due to several new developments, I might write more posts about this subject soon). This series of posts surveys the polynomial partitioning technique from item (ii). Basically, this is a technique for partitioning a d  -dimensional Euclidean space into a small number of “well behaved” cells. While the technique was originally introduced by Guth and Katz to solve the planar distinct distances problem, it already has several additional applications and extensions: a slightly improved upper bound for the three-dimensional unit distances problem (see here and here), improved bounds for various incidence problems (e.g., see here, here, and here), an alternative proof for the existence of a spanning tree with a low crossing number, and even a new range searching algorithm. Several recent works survey the basics of polynomial partitioning such as Zeev Dvir’s survey, Larry Guth’s lecture notes, this paper by Kaplan, Matoušek, and Sharir, and this blog post by Terry Tao.

In what follows, we regard the dimension d  of the ambient space as a (small) constant, and ignore the dependence on d  of the various constants of proportionality in the bounds. Consider a set \cal P  of m  points in {\mathbb R}^d  . Given a polynomial f \in {\mathbb R}[x_1,\ldots, x_d]  , we define the zero set of f  to be Z(f) = \{ p \in {\mathbb R}^d \mid f(p)=0 \}  . For 1 < r \le m  , we say that f \in {\mathbb R}[x_1,\ldots, x_d]  is an r  -partitioning polynomial for \cal P  if no connected component of {\mathbb R}^d \setminus Z(f)  contains more than m/r  points of \cal P  . Notice that there is no restriction on the number of points of \cal P  that lie in Z(f)  . In the following figure, the blue curve is the zero set of a 5-partitioning polynomial, since m=10  and every cell contains at most two points.

5PartPol

The following result is due to Guth and Katz.

Theorem 1 (Polynomial partitioning). Let \cal P  be a set of m  points in {\mathbb R}^d  . Then for every 1< r \le m  , there exists an r  -partitioning polynomial f \in {\mathbb R}[x_1,\ldots, x_d]  of degree O(r^{1/d})  .

In the remainder of this post we show how to apply the polynomial partitioning theorem by presenting an algebraic proof for the Szemerédi-Trotter theorem (for the planar point-line incidence problem). In the following two posts, we prove the polynomial partitioning theorem and compare polynomial partitioning to the previous partitioning technique called cuttings. Parts of these posts are loosely based on parts of this paper by Kaplan, Matoušek, and Sharir. I also plan to discuss, in future posts, more advanced topics related to polynomial partitionings, such as the techniques of using a second partitioning polynomial (see here and here) and of using constant sized partitioning polynomials (introduced by Solymosi and Tao). Thanks to Micha Sharir for helping with the preparation of all three posts.

Continue reading