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 be a set of points on the -axis and let be a set of points on the -axis (or on any other two perpendicular lines). Let denote the number of distinct distances in (i.e., distances between points from different sets). It is well known that it is possible to have . An example is depicted in the following figure.

Let . My first question is whether it is possible to have . My intuition is that not only this is impossible, but that must be significantly larger; perhaps it must be almost quadratic in (it is not difficult to obtain an example where ). I will now try to explain why.

Let denote the set of -coordinates of the points of and let denote the set of -coordinates of the points of . We set (notice the difference from the standard notation ). The set of distances spanned by is . According to Freiman’s theorem, if is small, then and are contained in

*generalized arithmetic progressions*of some bounded size (see also Ruzsa’s paper).**Definition 1.**Let and let be positive integers. A -dimensional generalized arithmetic progression is a set of the form

The

*size*of the generalized arithmetic progression is .For to be small, also has to be contained in a generalized arithmetic progression. My conjecture is that cannot be small since it is impossible for both and to be contained in general arithmetic progressions of some bounded size.

The second problem involves a third point set of points, all contained in a line that is parallel to the -axis. Let us say that the points of are on the line defined by , for some constant .

As before, we set , and let denote the set of -coordinates in . For to be small, is required to be contained in a generalized arithmetic progression. For to be small, is required to be contained in a generalized arithmetic progression (where ). Is it possible for both and to be contained in generalized arithmetic progressions of a bounded size?

Advertisements

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

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

so

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.

Thanks a lot Frank!

That is exactly what we were looking for.

I also found a slight improvement to the paper you’ve mentioned in http://arxiv.org/pdf/1111.5159.pdf

I’ll send you an email with some more details soon.