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.

The second problem involves a third point set {\cal P}_3  of n  points, all contained in a line that is parallel to the y  -axis. Let us say that the points of {\cal P}_3  are on the line defined by x=c  , for some constant c \neq 0  .

3linesPerpen

As before, we set {\cal P} = {\cal P}_1 \cup {\cal P}_2 \cup {\cal P}_3  , and let A  denote the set of x  -coordinates in {\cal P}_1  . For D({\cal P}_1,{\cal P}_2)  to be small, A^2  is required to be contained in a generalized arithmetic progression. For D({\cal P}_1,{\cal P}_3)  to be small, (A-c)^2  is required to be contained in a generalized arithmetic progression (where A-c = \{a_1-c,\ldots,a_n-c\}  ). Is it possible for both A^2  and (A-c)^2  to be contained in generalized arithmetic progressions of a bounded size?

Advertisements

2 thoughts on “Two questions about distinct distances

  1. Hi Adam,
    I think the first problem can be partly answered using Elekes-Nathanson-Ruzsa, see
    G. Elekes, M. Nathanson, I. Z. Ruzsa, Convexity and sumsets, J. Number Theory 83 (2000), 194–201.
    Cor 3.1 there says that
    |A+C||f(A)+D|>cn^{5/2}
    for a strictly convex function f and real sets of size n.
    For A the x-coordinates of n points on the x-axis, and B the y-coordinates of n points on the y-axis, we choose C=-A, D=f(B), and f(x)=x^2. Then
    |A-A||f(A)+f(B)|> cn^{5/2},
    so
    |D(A\cup B)|> (|D(A)||D(A\cup B)|)^{1/2} = (|A-A||f(A)+f(B)|)^{1/2} >cn^{5/4}.
    ENR doesn’t use Freiman I think, but Elekes’s composition trick, which you probably know from his paper on distinct distances between two lines.

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