The Elekes-Sharir Framework (part 2)

In my first post about the Elekes-Sharir framework, we presented the history of the reduction and its basic technical details. In this post we present another application of the framework, reproving a result by Szemerédi on the minimum number of distinct distances in sets with no k  collinear points. As usual, thanks to Micha Sharir for helping with the preparation of the post.

One set of open problems that still seem to be beyond our reach concerns the characterization of point sets that determine a small number of distinct distances (e.g., see this post). Hardly anything is known about these problems, and as a first step Erdős suggested to determine whether every such point set (say, every point set that spans O(n/\sqrt{\log n})  distinct distances) contains \Omega(\sqrt{n})  points on a line, or even only \Omega(n^\varepsilon)  such points. The only non-trivial result comes from an unpublished lemma of Szemerédi (the proof can be found in the book Combinatorial Geometry by Pach and Agarwal).

We now show how a variant of Szemerédi bound can be proved by applying the Elekes-Sharir framework. The proof can be seen as equivalent to Szemerédi’s proof and thus does not seem to shed new light on the problem. However, it seems to me that the proof does provide more intuition for the Elekes-Sharir framework, and prepares us for more advanced uses, as the one that will be presented in the following post.

Lemma. (Szemerédi) Consider a set \cal P  of n  points in the plane and a positive constant k  , such that no line contains k  points of \cal P  . Then \cal P  spans \Omega(n)  distinct distances.

Proof.     As before, let x  denote the number of distinct distances that are spanned by \cal P  and denote these distances as \delta_1,\delta_2,\ldots,\delta_x  . We assume, for contradiction, that x=o(n)  . We apply the Elekes-Sharir framework as explained in the previous post, with a single change – we further restrict Q  to contain only quadruples (a,p,b,q)  where a=b  (and p\neq q  ). Let us first update the lower bound analysis. For every point p\in{\cal P}  , we set E^{p}_i = \left\{q\in {\cal P} \mid |pq| = \delta_i \right\}  . Notice that for every p\in{\cal P}  we have \sum_{i=1}^x|E_i^{p}| = n-1  . As in the original analysis, we apply the Cauchy-Schwarz inequality to obtain a lower bound on |Q|  .

|Q| = \sum_{p\in{\cal P}}\sum_{i=1}^x 2\binom{|E^{p}_i|}{2} \ge \sum_{p\in{\cal P}}\sum_{i=1}^x \left(|E^{p}_i| - 1\right)^2 \ \ \ \ \ \ \ \

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ge \frac{1}{x} \sum_{p\in{\cal P}}\left(\sum_{i=1}^x |E_i^{p}| - 1\right)^2 \hspace{-2mm}= \frac{n(n-1-x)^2}{x}  \ \ \ \ \ \ \ \ \ \ \ \ (1)

(the first sum iterates over all the possible candidates for the first/third point of the quadruple).

To upper bound |Q|  , we consider proper rigid motions as before. Since no non-trivial translation takes a  to itself, no quadruple of Q  corresponds to a translation, and it remains to bound the number of quadruples that correspond to a rotation. When considering a quadruple of the form (a,p,a,q)  we notice a detail that was swept under the rug in the analysis in previous post. Namely, \ell_{aa}  cannot be a lifting of some perpendicular bisector to {\mathbb R}^3  , since aa  is not a segment and does not have a perpendicular bisector. The only rotations that take a  to itself are rotations around a  , so their parametrizations are all of the form (a_x,a_y,r)  , for r\in{\mathbb R}  . That is, the set of the parametrizations of these rotations is the line defined by the equations x=a_x  and y=b_x  . Notice that this line is parallel to the z  -axis.

We have a set of n  lines that are parallel to the z  -axis, each containing a point (p_x,p_y,0)  such that p = (p_x,p_y)\in {\cal P}  . We refer to these lines as blue lines. We also have n^2-n  additional lines \ell_{pq}  where p\neq q  , which are not parallel to the z  -axis. We refer to these as red lines. Notice that any quadruple (a,p,a,q)\in Q  corresponds to a red-blue intersection (the blue line consisting of rotations that take a  to itself and the red line of rotations that take p  to q  ). This situation is depicted in the following figure.

RedBlue

If there is a plane that fully contains k  blue lines, by projecting it on the xy  -plane we obtain a line that contains k  points of {\cal P}  (each blue line is projected to a distinct point of    \cal P  ). By the assumption such a line does not exist, and thus no plane contains k  blue lines. This in turn implies that a red line cannot intersect k  blue lines (since all of the blue lines that are intersected by a specific red line are coplanar). Since every red line intersects at most k-1  blue lines, there are at most (k-1)(n^2-n)  red-blue intersections, and thus |Q|\le (k-1)(n^2-n)  . Combining this with (1) and recalling that x=o(n)  implies

x\ge (n(n-1-x)^2)/((k-1)(n^2-n)) = \Omega(n).

This contradicts our assumption that x=o(n)  and concludes the proof.     \Box

This proof is equivalent to Szemerédi’s original proof since the core of both proofs is double counting the isosceles triangles spanned by \cal P  . A minor change in the proof implies that for any n  point set \cal P  that spans O(n/\sqrt{\log n})  distinct distances, there is a line containing \Omega(\sqrt{\log n})  points of \cal P  . However, it seems that we are still far from Erdős’s conjecture of \Omega(\sqrt{n})  points on a line, or even only \Omega(n^\varepsilon)  .

Advertisements

2 thoughts on “The Elekes-Sharir Framework (part 2)

  1. Pingback: The Elekes-Sharir Framework (part 3) | Some Plane Truths

  2. Pingback: Polynomial partitioning: the basics (part 1) | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s