Osamělá domněnka - Lonely runner conjecture

Příklad domněnky osamělého běžce se 6 běžci

v teorie čísel, a zejména studium diofantická aproximace, domněnka osamělého běžce je dohad původně kvůli J. M. Willsovi v roce 1967. Aplikace domněnky jsou v matematice velmi rozšířené; obsahují pohled na překážku problémy^[1] a výpočet chromatické číslo z grafy vzdálenosti a oběhové grafy.^[2] Dohady dostalo své malebné jméno L. Goddyn v roce 1998.^[3]

Formulace

Nevyřešený problém v matematice: Je domněnka osamělého běžce pravdivá pro každý počet běžců? (více nevyřešených úloh z matematiky)

Zvážit k běžce na kruhové dráze o jednotkové délce. Na t = 0, všichni běžci jsou na stejné pozici a začínají běžet; rychlosti běžců jsou párově odlišné. Běžec je řekl, aby byl osamělý v čase t pokud jsou ve vzdálenosti alespoň 1 /k od všech ostatních běžců najednou t. Domněnka osamělého běžce uvádí, že každý běžec je v určitou dobu osamělý.

Vhodným přeformulováním domněnky je předpokládat, že běžci mají celočíselné rychlosti,^[4] ne všechny dělitelné stejným prvočíslem; běžec, který má být osamělý, má nulovou rychlost. Domněnka pak uvádí, že pro jakoukoli množinu D z k - 1 kladná celá čísla s největší společný dělitel 1,

${displaystyle exists tin mathbb {R} quad forall din Dquad | td | geq {frac {1} {k}},}$

kde ||X|| označuje vzdálenost reálného čísla X do nejbližší celé číslo.

Známé výsledky

k	rok se ukázal	prokázáno	poznámky
1	-	-	triviální: ${displaystyle t = 0}$; žádný ${displaystyle t}$
2	-	-	triviální: ${displaystyle t = (2 (v_ {1} -v_ {0})) ^ {- 1}}$
3	-	-	triviální: s nulovou rychlostí běžce být osamělý, stane se to v prvním kole pomalejšího běžce
4	1972	Betke and Wills;[5] Cusick[6]	-
5	1984	Cusick a Pomerance;[7] Bienia a kol.[3]	-
6	2001	Bohman, Holzman, Kleitman;[8] Renault[9]	-
7	2008	Barajas a Serra[2]	-

Dubickas^[10] ukazuje, že pro dostatečně velký počet běžců pro rychlosti ${displaystyle v_ {1}$ domněnka osamělého běžce je pravdivá, pokud ${displaystyle {frac {v_ {i + 1}} {v_ {i}}} geq 1+ {frac {33log (k)} {k}}}$.

Czerwiński^[11] ukazuje, že s pravděpodobností inklinující k jedné platí mnohem silnější prohlášení pro náhodné množiny, ve kterých je vázáno ${displaystyle {frac {1} {k}}}$ je nahrazen ${displaystyle {frac {1} {2}} - epsilon}$.

Poznámky

externí odkazy

• Článek v Zahradě otevřených problémů
• Florent L. B. Périat. „Generátor časů pro domněnku osamělého běžce“. Github.