Magányosfutó-sejtés

A magányosfutó-sejtés (lonely runner conjecture, LRC) J. M. Wills több mint ötvenéves, számelméleti, közelebbről a diofantikus approximációval kapcsolatos sejtése. Folyományai a matematika több területén előfordulnak, köztük találhatók takarási problémák,^[1] illetve a távolsággráfok és cirkuláns (irányítatlan, ciklikus csoportot tartalmazó, csúcstranzitív gráfok) kromatikus számának meghatározása is.^[2] A sejtés szemléletes nevét L. Goddyntól kapta 1998-ban.^[3]

Példa a magányosfutó-sejtésre 6 futóval

A sejtés

Vegyünk egységnyi hosszú körpályát, rajta k futóval. A t = 0 időpillanatban elindul az összes futó, azonos kiindulási pontból, állandó, de páronként különböző sebességgel. Egy futót t időpillanatban „magányosnak” tekintünk akkor, ha legalább 1 / k távolságra van az összes többi futótól az adott t pillanatban. A magányosfutó-sejtés azt állítja, hogy minden futó magányos valamilyen időpillanatban. A probléma egy célszerű átfogalmazása felteszi, hogy a futók sebessége egész szám, nincs közös prímosztójuk és a magányosnak választott futó sebessége zérus. A sejtés ekkor úgy szól, hogy bármely k − 1 darab, 1 legnagyobb közös osztójú pozitív egész szám által alkotott D halmazt tekintve,

${\displaystyle \exists t\in \mathbb {R} \quad \forall d\in D\quad ||td||\geq {\frac {1}{k}},}$

ahol ||x|| az x valós szám távolságát jelöli a legközelebbi egésztől. A sejtéssel ekvivalens feladatok között van az 1971-ben megfogalmazott takarási probléma (view obstruction problem^[4]) is.

Alacsony k értékekre a feladat viszonylag egyszerű, de a futók számának növekedésével rendkívül bonyolulttá válik.

Eddigi eredmények

k	bizonyítás éve	szerzője	jegyzet
1	-	-	triviális: t = 0; bármely t
2	-	-	triviális: t = 1 / (2 · (v1−v0))
3	-	-	Bármely bizonyítás k>3-ra bizonyítja a k=3 esetet is
4	1972	Betke és Wills;[5] Cusick[6]	-
5	1984	Cusick és Pomerance;[7] Bienia et al.[3]	-
6	2001	Bohman, Holzman, Kleitman;[8] Renault[9]	-
7	2008	Barajas és Serra[2]	-

Dubickas 2011-ben megmutatta,^[10] hogy elegendően nagy számú futó esetén, melyek sebességei ${\displaystyle v_{1}<v_{2}<\dots <v_{k}}$, a magányosfutó-sejtés igaz, amennyiben ${\displaystyle {\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {33\log(k)}{k}}}$.