Problem #657: Is it true that if $A\subset \mathbb{R}^2$ is a set of $n$...

---

Progress

In [Er73] Erdős attributes this problem (more generally in $\mathbb{R}^k$) to himself and Davies. In [Er97e] he does not mention Davis, but says this problem was investigated by himself, Füredi, Ruzsa, and Pach.

In [Er73] Erdős says it is not even known in $\mathbb{R}$ whether $f(n)\to \infty$. Sarosh Adenwalla has observed that this is equivalent to minimising the number of distinct differences in a set $A\subset \mathbb{R}$ of size $n$ without three-term arithmetic progressions. Dumitrescu [Du08] proved that, in these terms,\[(\log n)^c \leq f(n) \leq 2^{O(\sqrt{\log n})}\]for some constant $c>0$.

Hunter observed in the comments that a result of Ruzsa coupled with standard tools of additive combinatorics (with details given by Alfaiz and Tang) allow recent progress on the size of subsets without three-term arithmetic progression (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]) yield\[2^{c(\log n)^{1/9}}\leq f(n)\]for some constant $c>0$.

Straus has observed that if $2^k\geq n$ then there exist $n$ points in $\mathbb{R}^k$ which contain no isosceles triangle and determine at most $n-1$ distances.

See also [135].