Skip to content

Erdős problem 655

Let x1,,xnR2x_1,\ldots,x_n\in \mathbb{R}^2 be such that no circle whose centre is one of the xix_i contains three other points. Are there at least (1+c)n2(1+c)\frac{n}{2} distinct distances determined between the xix_i, for some constant c>0c>0 and all nn sufficiently large?

Sources

Browse retained paths and inspect the exact material available for this Problem.

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

655.lean

Retained formal statement1 of 2

Let x1,,xnR2x_1,\ldots,x_n\in \mathbb{R}^2 be such that no circle whose centre is one of the xix_i contains three other points. Are there at least (1+c)n2(1+c)\frac{n}{2} distinct distances determined between the xix_i, for some constant c>0c>0 and all nn sufficiently large?

The answer is no: as Zach Hunter observed, the regular n-gon (n points equally spaced on a circle) is valid and determines only ⌊n/2⌋ < (1+c)n/2 distinct distances, for every c > 0. (In the spirit of related conjectures of Erdős and others, presumably some kind of assumption that the points are in general position was intended; see erdos_655.variants.general_position.)

The disproof — the regular n-gon construction together with its supporting lemmas — is formalised at the linked commit.

FormalConjectures/ErdosProblems/655.leanErdos655.erdos_6555 linesExact file
Falsec > 0,    ∀ᶠ (n : ℕ) in Filter.atTop,      ∀ (X : Finset (EuclideanSpace ℝ (Fin 2))),        X.card = nErdos655.IsValid X → (1 + c) * ↑n / 2 ≤ ↑(EuclideanGeometry.distinctDistances X)
SolvedProof has a holeformal conjecturesexternal proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page