# 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. 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$. 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?

## 2 thoughts on “Two questions about distinct distances”

1. Frank de Zeeuw |

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.

2. adamsheffer |

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.