Erdős distinkta avståndsproblem

I diskret geometri säger Erdős distinkta avståndsproblem att varje uppsättning punkter i planet har ett nästan linjärt antal distinkta avstånd. Den poserades av Paul Erdős 1946 och nästan bevisad av Larry Guth och Nets Katz 2015.

Gissningen

Låt i det följande $g (n)$ beteckna det minimala antalet distinkta avstånd mellan $n$ punkter i planet, eller motsvarande minsta möjliga kardinalitet av deras avståndsuppsättning . I sitt papper från 1946 bevisade Erdős uppskattningarna

{\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{ \sqrt {\log n}}

för någon konstant $c$ . Den nedre gränsen gavs av ett lätt argument. Den övre gränsen ges av ett ${\sqrt {n}}\times {\sqrt {n}}$ kvadratiskt rutnät. För ett sådant rutnät finns $O(n/{\sqrt {\log n}})$ tal under n som är summor av två kvadrater, uttryckta i stor O-notation ; se konstanten Landau–Ramanujan . Erdős förmodade att den övre gränsen var närmare det sanna värdet av g ( n ), och specifikt att (med stor Omega-notation ) $g(n)=\Omega (n^ {c})$ gäller för varje $c < 1$ .

Delvis resultat

Paul Erdős 1946 nedre gräns för $g (n) = Ω(n 1/2)$ förbättrades successivt till:

$g (n) = Ω(n 2/3)$ av Leo Moser 1952,
$g (n) = Ω(n 5/7)$ av Fan Chung 1984,

$g (n) = Ω(n 4/5 /log n)$ av Fan Chung, Endre Szemerédi och William T. Trotter 1992,
$g (n) = Ω(n 4/5)$ av László A. Székely 1993,
$g (n) = Ω(n 6/7)$ av József Solymosi och Csaba D. Tóth 2001,
$g (n) = Ω(n (4 e /(5 e - 1)) - ɛ)$ av Gábor Tardos 2003,
$g (n) = Ω(n ((48 - 14 e)/(55 - 16 e)) - ɛ)$ av Nets Katz och Gábor Tardos 2004,
$g (n) = Ω(n /log n)$ av Larry Guth och Nets Katz 2015.

Högre dimensioner

Erdős övervägde också den högre dimensionella varianten av problemet: för $d\geq 3$ låt $g_{d}(n)$ beteckna det minsta möjliga antalet distinkta avstånd mellan $n$ punkter i $d$ -dimensionellt euklidiskt rum. Han bevisade att $g_{d}(n)=\Omega (n^{1/d})$ och $g_{d}(n)=O(n^{2/d})$ och förmodade att den övre gränsen faktiskt är skarp, dvs $g_{d}(n)=\Theta (n^{2/d})$ . József Solymosi och Van H. Vu erhöll den nedre gränsen $g_{d}(n)=\Omega (n^{ 2/d-2/d(d+2)})$ 2008.

Se även

externa länkar

William Gasarchs sida om problemet