On distinct distances and \(\lambda \)-free point sets
type: Item
instance of: scholarly article
title: On distinct distances and \(\lambda \)-free point sets
zbMATH Open document ID: 1159.52018
author: Adrian Dumitrescu
published in: Discrete Mathematics
publication date: 2009-01-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 52A40
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 5499789
zbMATH Keywords: distinct distances
zbMATH Keywords: midpoint-free sets
zbMATH Keywords: \(\lambda \)-triples
zbMATH Keywords: set arithmetic
MaRDI profile type: Publication
full work available at URL: j.disc.2007.11.046
OpenAlex ID: W2034645577
cites work: On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
cites work: Q4328181
cites work: On Sets of Distances of n Points
cites work: Q3997075
cites work: Q3856819
cites work: Integer Sets Containing No Arithmetic Progressions
cites work: Q4657584
cites work: Q4455112
cites work: Isosceles triangles determined by a planar point set
cites work: Arithmetical progressions and the number of sums
cites work: Distinct distances in the plane
cites work: Integer sets containing no arithmetic progressions
cites work: On distinct sums and distinct distances.
DOI: 10.1016/J.DISC.2007.11.046
description: scientific article; zbMATH DE number 5499789