On Distinct Distances Between a Variety and a Point Set

Bryce McLaughlin, Mohamed Omar

Published 2018-12-08Version 1

We consider the problem of Erd\"{o}s on determining the minimum number of distinct distances $f(n)$ that any set of $n$ points in the plane must determine. In a seminal paper, Erd\"{o}s showed that $f(n) = O(n/\sqrt{\log n})$, and conjectured $f(n)=\Omega(n^c)$ for every $c<1$. This was resolved by Guth and Katz, who proved $f(n)=\Omega(n / \log n)$. The question remains where $f(n)$ falls asymptotically between $n/\log n$ and $n/\sqrt{\log n}$. A recent result of Pohoata and Sheffer shows that if $\Theta(n)$ of the $n$ points lie on a line, then Erd\"{o}s' upper bound is asymptotically tight, meaning $f(n)=\Theta \left( n/\sqrt{\log n} \right)$. We generalize this result, proving that $f(n)=\Theta \left( n/\sqrt{\log n} \right)$ if $\Theta(n)$ of the points lie on an algebraic curve of a fixed degree.