The Partial Elekes-Sharir Framework

A while ago, I had a post about lower bounding the minimum number of distinct distances between points on two lines in {\mathbb R}^2  . That post showed how such an upper bound can be obtained by applying the Elekes-Sharir framework (a pdf file of my guide to the Elekes-Sharir framework can be found here). Since then, we noticed that a much simpler technique can be used to obtain the same bound. I like to call this simpler technique the partial Elekes-Sharir framework since the analysis starts in the same way, but the more technical parts of the original framework are replaced with a simpler analysis. More specifically, the partial framework leads to a planar incidence problem, instead of to one in {\mathbb R}^3  . Since Micha Sharir, József Solymosi, and myself introduced this idea in the spring of 2013 (later on, we discovered that a similar idea was also used by Elekes and Szabó), it was applied and extended in a few additional papers (see here, here, and here). Moreover, I know of at least a couple of additional manuscripts that apply the same ideas for problems not directly involving distinct distances.

The purpose of this post is to present the partial Elekes-Sharir framework, by applying it to obtain a bound for the problem concerning distinct distances on two lines. First, we recall the problem.

Consider a set {\cal P}_1  of n  points on a line \ell_1  , and a set {\cal P}_2  of n  points on a line \ell_2  (such that \ell_1  and \ell_2  are distinct) and let D({\cal P}_1,{\cal P}_2)  denote the number of distinct distances between pairs of points from {\cal P}_1\times{\cal P}_2  . Consider first the “balanced” case, where |{\cal P}_1|=|{\cal P}_2|=n  . When the two lines are parallel or orthogonal, the points can be arranged so that D({\cal P}_1,{\cal P}_2) = \Theta(n)  . For example, see the following figure.

TwoLinesEx

Purdy conjectured that if the lines are neither parallel nor orthogonal then D({\cal P}_1,{\cal P}_2) = \omega(n)  . Elekes and Rónyai proved that the number of distinct distances in such a scenario is indeed superlinear. They did not give an explicit bound, but a brief analysis of their proof shows that D({\cal P}_1,{\cal P}_2) = \Omega(n^{1+\delta})  for some \delta>0  . Elekes derived the improved and concrete bound D({\cal P}_1,{\cal P}_2) = \Omega(n^{5/4})  (when the lines are neither parallel nor orthogonal) and gave a construction, reminiscent of the one by Erdős, with D({\cal P}_1,{\cal P}_2) = O\left(n^2/\sqrt{\log n}\right)  , in which the angle between the two lines is \pi/3  . The unbalanced case, where |{\cal P}_1|\ne |{\cal P}_2|  , has recently been studied by Schwartz, Solymosi, and de Zeeuw, who have shown, among several other related results, that the number of distinct distances remains superlinear when |{\cal P}_1| = n^{1/2 + \varepsilon}  and |{\cal P}_2| = n  , for any \varepsilon>0  .

Our result, taken from this paper is:

Theorem 1. Let {\cal P}_1  and {\cal P}_2  be two sets of points in {\mathbb R}^2  of cardinalities n  and m  , respectively, such that the points of {\cal P}_1  all lie on a line \ell_1  , the points of {\cal P}_2  all lie on a line \ell_2,  and the two lines are neither parallel nor orthogonal. Then

\displaystyle D({\cal P}_1,{\cal P}_2)=\Omega\left( \min\left\{n^{2/3}m^{2/3},n^2,m^2 \right\}\right)  .

Notice that Theorem 1 immediately improves Elekes’s lower bound from \Omega(n^{5/4})  to \Omega(n^{4/3})  . Moreover, the theorem is a generalization of the aformentioned bound by Schwartz, Solymosi, and de Zeeuw.

Proof.     We rotate the plane so that \ell_1  becomes the x  -axis and translate the plane so that \ell_1 \cap \ell_2  is the origin. Let s  denote the slope of \ell_2  after the rotation. We set D=D({\cal P}_1,{\cal P}_2)  and denote the D  distinct distances in {\cal P}_1\times{\cal P}_2  as \delta_1,\ldots, \delta_D  . For a pair of points u  and v  , we denote by \|uv\|  the (Euclidean) length of the straight segment uv  . Let Q  be the set of quadruples (a,p,b,q)  where a,b \in {\cal P}_1  and p,q \in {\cal P}_2  , such that \|ap\|=\|bq\|>0  and ap \neq bq  (the two segments are allowed to share at most one endpoint). The quadruples are ordered, so that (a,p,b,q)  and (b,q,a,p)  are considered as two distinct elements of Q  . The following figure depicts a valid quadruple (a,p,b,q)\in Q  .

ValidQuad

Let E_i = \{(a,p)\in {\cal P}_1 \times {\cal P}_2 \mid |ap|=\delta_i \}  , for i=1,\ldots,D  . We have, by the Cauchy-Schwarz inequality,

\displaystyle |Q| = 2\sum_{i=1}^D\binom{|E_i|}{2} \ge \sum_{i=1}^D \left(|E_i|-1 \right)^2 \ge \frac{1}{D}\left(\sum_{i=1}^D (|E_i|-1) \right)^2

\displaystyle = \frac{\left(mn -D\right)^2}{D}. \qquad \qquad (1)

In the remainder of the proof we derive an upper bound on |Q|  , showing that |Q|=O(m^{4/3}n^{4/3} + n^2 +m^2)  . This, combined with (1)  , yields the lower bound asserted in the theorem.

Consider a quadruple (a,p,b,q)  where a,b\in{\cal P}_1  and p,q\in{\cal P}_2  . Write a=(a_x,0), b=(b_x,0),  p=(p_x,sp_x)  , and q=(q_x,sq_x)  . Recall that this quadruple is in Q  if and only if \|ap\|=\|bq\|  , or

\displaystyle (a_x-p_x)^2+ s^2p_x^2 = (b_x-q_x)^2+s^2q_x^2. \qquad \qquad (2)

We apply a reduction to a parametric plane. For every pair of points p,q\in {\cal P}_2  , we define a corresponding point v_{pq}=(p_x,q_x)\in{\mathbb R}^2  . We denote the set of these \Theta(n^2)  points as {\cal P}'  . For every pair of points a,b\in {\cal P}_1  , we define a corresponding hyperbola \gamma_{ab}  given by the equation

\displaystyle a_x^2 - b_x^2 -2a_xx +2b_xy +x^2(1+s^2) -y^2(1+s^2) = 0.

We denote the set of these \Theta(n^2)  hyperbolas as \cal H  . Notice that (2)  is satisfied if and only if the point v_{pq}  is incident to the hyperbola \gamma_{ab}  . That is, to upper bound |Q|  , it suffices to upper bound the number of incidences in {\cal P}'\times {\cal H}  .

It can be easily verified that, since s\neq 0  , no hyperbola in {\cal H}  is degenerate (i.e., the product of two lines). Moreover, the same hyperbola of {\cal H}  cannot be obtained by two different pairs of points a,b\in {\cal P}_1  .

By definition, two (non-degenerate) hyperbolas intersect in at most four points. That is, any pair of hyperbolas from \cal H  can be incident to at most four common points from {\cal P}'  . Moreover, the roles of \ell_1  and \ell_2  (and of {\cal P}_1  and {\cal P}_2  ) are fully symmetric, and can be interchanged, by regarding the pairs of distinct points in {\cal P}_1^2  (resp., {\cal P}_2^2  ) as a set of points (a,b)  in the plane (resp., as a set of hyperbolas \gamma_{p,q}  , defined in a fully symmetric manner). This implies, in particular, that there are at most four hyperbolas of \cal H  that pass through a given pair of points in {\cal P}'  . We can thus apply an incidence bound of Pach and Sharir.

Theorem 2 (Pach and Sharir `98). Consider a point set \cal P  , a set of simple curves \Gamma  , both in {\mathbb R}^2  , and two constant positive integers k  and s  , such that
  • For every k  points of \cal P  there are at most s  curves of \Gamma  that are incident to each of the k  points.
  • Every two curves of \Gamma  intersect in at most s  points.
Then I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),  where the constant of proportionality depends on k  and s  .

We can apply Theorem 2 on {\cal H} \times {\cal P}'  with k=2  and s=4  , to obtain

\displaystyle |Q|=O\left(|{\cal P}'|^{2/3}|{\cal H}|^{2/3} + |{\cal P}'| + |{\cal H}|\right) = O\left(m^{4/3}n^{4/3} + m^2 + n^2\right).

Combining this bound with the lower bound in (1) implies the assertion of the theorem.     \Box

Advertisements

6 thoughts on “The Partial Elekes-Sharir Framework

  1. In my limited understanding, Elekes-Szabo used (along with a lot else) the approach that was introduced in Elekes-Ronyai (2000) and Elekes (1999), and recently used by Charalambides, as you mentioned here. I sometimes call that the “5/4 method”, to distinguish it from the “4/3 method” that you introduced with Sharir and Solymosi. Not to suggest that those are better names, just that they help to distinguish…

  2. Hi Frank,

    You always raise interesting issues! What I meant by saying that the Elekes-Szabo paper applies similar ideas is that it also counts quadruples, provides a lower bound for the number of quadruples by using Cauchy-Schwarz, and an upper bound by an incidence problem. If I am not mistaken, this is not the case in the other papers that you have mentioned.

    • After looking at the Elekes-Szabo paper again I see that you’re right. I always thought that somewhere in there they used the “5/4 method”, but I see now that they do count quadruples, so it is more like the “4/3 method”.
      I’ve always found it a very difficult paper…

  3. Pingback: Recent Results (Feb `14) | Some Plane Truths

  4. Pingback: Incidences and the Sum-Product Problem | 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