Erdős-féle eltérő távolságok problémája

A diszkrét geometria területén az Erdős-féle eltérő távolságok problémája az az állítás, mi szerint egy síkban elhelyezkedő Sablon:Math különböző pont között legalább Sablon:Math különböző távolság létezik. A problémát Erdős Pál vetette fel 1946-ban, és Sablon:Harvtxt oldotta meg.

A sejtés

A következőkben jelölje Sablon:Math a sík Sablon:Math pontja közti minimális különböző távolságok számát.1946-os cikkében Erdős igazolta a $\sqrt{n-3/4}-1/2\le g(n)\le cn/\sqrt{\log n}$ becslést néhány $c$ konstansra. Az alsó korlát viszonylag könnyen belátható, a felső korlátot egy $\sqrt{n}\times \sqrt{n}$ négyzetrács adja (hiszen $O(n/\sqrt{\log n})$ olyan n-nél kisebb szám van, ami két négyzetszám összegeként felírható, lásd Landau–Rámánudzsan-konstans). Erdős sejtése szerint a felső korlát közelebb van a g(n) tényleges értékéhez, konkrétabban $g(n)=\mathrm{\Omega }(n^c)$ igaz minden Sablon:Math konstansra.

Részeredmények

Erdős 1946-os Sablon:Math alsó korlátját sikeresen javították a következőkre:

• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv
• Sablon:Math Sablon:Harv

Magasabb dimenziók

Erdős foglalkozott a probléma magasabb dimenziójú változataival is: d≥3-ra jelölje g_d(n) a d dimenziós euklideszi térben n pont közötti lehetséges távolságok minimális számát. Igazolta, hogy Sablon:Math és Sablon:Math, továbbá sejtése szerint a felső korlát valójában éles, tehát Sablon:Math . Sablon:Harvtxt pontosították az alsó korlátot a következőre: Sablon:Math.

Kapcsolódó szócikkek

• Falconer-sejtés
• Erdős-féle egységtávolság-probléma

Irodalom

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation. See also The Guth-Katz bound on the Erdős distance problem by Terry Tao and Guth and Katz’s Solution of Erdős’s Distinct Distances Problem by Pach János.
• Sablon:Citation
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

További információk

• William Gasarch's page on the problem
• János Pach's guest post on Gil Kalai's blog
• Terry Tao's blog entry on the Guth-Katz proof, gives a detailed exposition of the proof.