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.


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.

Continue reading

Incidences and Planar Curves Containing Many Grid Points

Alex Iosevich just visited us here at Tel Aviv University. Alex gave a wonderful talk about “Distribution of simplexes in discrete and continuous settings”, though his talk is not the topic of this post.


Alex showed me a cute proof concerning how many points of a planar integer grid can be contained in an irreducible curve. (If I am not mistaken, Nets Katz showed me a variant of the same proof a while ago.) With Alex’s permission, I now present my own variant of this proof.

Consider a \sqrt{n}\times\sqrt{n}  integer grid {\cal G}  in {\mathbb R}^2  . It is easy to prove that any constant-degree algebraic curve passes through O(\sqrt{n})  points of {\cal G}  . This bound is tight, since a line can pass through \Theta(\sqrt{n})  points of {\cal G}  . Somewhat surprisingly, every other constant-degree algebraic curve passes through an asymptotically smaller number of grid points.

Lemma 1. Let {\cal G}  be a \sqrt{n}\times\sqrt{n}  integer grid in {\mathbb R}^2  .
(a) Let C  be a constant-degree algebraic curve which is not a line. Then C  contains o(\sqrt{n})  points of {\cal G}  (recall that little-o()  notation implies asymptotically smaller).
(b) Let C  be a strictly convex curve (not necessarily algebraic). Then C  contains O(n^{1/3})  points of {\cal G}  .


Continue reading