On distinct distances and \(\lambda \)-free point sets (Q998391): Difference between revisions

In 1946 Erdős raised the following famous problem: What is the minimum number of distinct distances determined by \(n\) points in the plane? Denoting this number by \(g(n)\), he conjectured that \(g(n)=\Omega(n/\sqrt{\log n})\) and showed that this bound is attained by the \(\sqrt n \times \sqrt n\) integer grid. Considering the restriction of this problem for \(n\) points on the line, clearly they determine at least \(n-1\) distinct distances; this bound is tight, since \(n\) equidistant points determine only \(n-1\) distances, but the above construction has a very regular grid-like structure, so it is a natural question to ask what happens if we perturb the regularity of the grid, say by not allowing two points together with their midpoint to be in the set? In order to answer this question, the author introduces the following notion: let \(\lambda \in (0,1)\) be a fixed rational number; a set of points \(P\) in the plane is \(\lambda\)-free if for any triple of distinct points \(a, b, c\in P\) \(\lambda a+(1-\lambda)b\neq c\). The main result in the paper is the following estimate on the minimum number of distinct distances in a \(\lambda\)-free point set on the line: Let \(g_{\lambda}(n)\) denote the minimum number of distinct distances determined by a \(\lambda\)-free set of \(n\) points on the line. Then \(g_{\lambda}(n)\) satisfies: \[ \lim_{n\to \infty} \frac{g_{\lambda}(n)}{n} = \infty \] and \[ g_{\lambda}(n)\leq n2^{c_{\lambda}\sqrt{\log n}} \] for a suitable constant \(c_{\lambda}\). Furthermore, in particular \(g_{1/2}(n)\geq c_1n(\log n)^{c_2}\) for some absolute constants \(c_1, c_2 >0\). Other related distance problems are also discussed in the paper, including possible implications of obtaining good estimates on the minimum number of distinct distances in a \(\lambda\)-free point set in the plane for the general problem of distinct distances in the plane.