Conjectura alergătorului singur

Problemă nerezolvată în matematică:

Este conjectura alergătorului singur adevărată pentru orice număr de alergători?

(mai multe probleme nerezolvate din matematică)

În teoria numerelor, mai exact în studiul aproximării diofantice, conjectura alergătorului singur este o conjectură despre comportamentul pe termen lung al alergătorilor pe o pistă circulară. Aceasta afirmă că fiecare dintre cei $n$ alergători de pe o pistă de lungime unu, având viteze constante și diferite, va fi singur la un moment dat – cel puțin $1/n$ unități departe de toți ceilalți.

Conjectura a fost formulată pentru prima dată în 1967 de matematicianul german Jörg M. Wills, în limbajul teoriei numerelor, și independent în 1974 de T. W. Cusick; formularea sa ilustrativă și populară în prezent datează din 1998. Se știe că pentru șapte alergători sau mai puțini conjectura este adevărată, dar cazul general rămâne nerezolvat. Implicațiile conjecturii includ soluții la problemele de vedere-obstrucție și margini ale proprietăților, legate de numerele cromatice, ale anumitor grafuri.

Formulare

Exemplu de un caz al conjecturii cu n=6 alergători. Alergătorii colorați în negru nu au fost încă singuri. Arcurile albe, de lungime 2/n, indică faptul că un alergător este în prezent singur. Alergătorii galbeni au fost singuri la un moment dat.

Se consideră $n$ alergători pe o pistă circulară de lungime unu. La momentul inițial $t=0$, toți alergătorii sunt în aceeași poziție și încep să alerge; vitezele alergătorilor sunt constante, toate distincte și pot fi negative. Se spune că un alergător este singur la un moment dat $t$ dacă se află la o distanță (măsurată de-a lungul cercului) de cel puțin $1/n$ față de la orice alt alergător. Conjectura alergătorului singur afirmă că fiecare alergător este singur la un moment dat, indiferent de alegerea vitezelor.

Această formulare vizuală a conjecturii a fost publicată pentru prima dată în 1998. În multe formulări, inclusiv în cea originală a lui Jörg M. Wills, se fac unele simplificări. Alergătorul care va fi singur staționează în origine (cu viteză zero) și, prin urmare se consideră alți $n-1$ alergători, cu viteze diferite de zero. Alergătorii în mișcare mai pot fi restricționați să aibă doar viteze pozitive: prin simetrie, doi alergători cu viteze $x$ și $-x$ se află la aceeași distanță față de 0 în orice moment și, prin urmare, sunt în esență echivalenți. Demonstrarea rezultatului pentru un alergător staționar implică rezultatul general pentru toți alergătorii, deoarece acesta poate fi făcut staționar prin scăderea vitezei lui din vitezele tuturor alergătorilor, lăsându-l cu viteza zero. Conjectura afirmă atunci că, pentru orice colecție $v_{1},v_{2},\dots ,v_{n-1}$ de viteze pozitive, distincte, există un timp $t>0$ astfel încât $${\frac {1}{n}}\leq \operatorname {frac} (v_{i}t)\leq 1-{\frac {1}{n}}\qquad (i=1,\dots ,n-1),$$ unde $\operatorname {frac} (x)$ reprezintă partea fracționară a lui $x$. Interpretat vizual, dacă alergătorii aleargă în sens invers acelor de ceasornic, termenul din mijloc al inegalității este distanța de la origine la al $i$-lea alergător la momentul de timp $t$, măsurată în sens invers acelor de ceasornic. Această convenție este folosită în restul acestui articol. Conjectura lui Wills a făcut parte din munca sa în aproximarea diofantică, studiul referitor la cât de bine pot fracțiile să aproximeze numerele iraționale.

Implicații

Pătratele cu lungimea laturii 1/3 plasata în fiecare punct de coordonate semi-întregi obstrucționează orice semidreaptă din origine (în afara celor aflate pe o axă). Orice lungime mai mică a laturii va crea mici goluri.

Presupunem că $C$ este un n-hipercub cu lungimea laturii $s$ în spațiul n-dimensional ($n\geq 2$). Se pune câte o copie centrată a lui $C$ în fiecare punct de coordonate semi-întregi. O semidreaptă de la origine fie ratează toate copiile lui $C$, caz în care există o gaură (infinitezimală), fie atinge cel puțin o copie. Cusick (1973) a făcut o formulare independentă a conjecturii alergătorului singur în acest context; conjectura implică faptul că există găuri dacă și numai dacă $s<(n-1)/(n+1)$, ignorând semidreptele aflate într-unul dintre hiperplanele de coordonate. De exemplu, plasate în spațiul bidimensional, pătrate cu lungimea laturii mai mică decât $1/3$ vor lăsa goluri, așa cum se arată, și pătrate cu lungimea laturii $1/3$ sau mai mare vor obstrucționa fiecare semidreaptă care nu este paralelă cu o axă. Conjectura generalizează această observație la orice număr de dimensiuni.

În teoria grafurilor, un graf cu distanțe $G$ pe mulțimea numerelor întregi cu mulțimea de distanțe întregi pozitive $D$, are o muchie între $x$ și $y$ dacă și numai dacă $|x-y|\in D$. De exemplu, dacă $D=\{2\}$, orice pereche de numere pare consecutive, și de numere impare consecutive, este adiacentă, toate la un loc formând două componente conexe. O colorare k-regulată a numerelor întregi cu pasul $\lambda \in \mathbb {R}$ atribuie fiecărui număr întreg $n$ una dintre $k$ culori în funcție de restul $\lfloor \lambda n\rfloor$modulo $k$. De exemplu, dacă $\lambda =0.5$, colorarea se repetă la fiecare $2k$ numere întregi și fiecare două numere întregi $2m$ și $2m+1$ sunt colorate la fel. Luând $k=|D|+1$, conjectura alergătorului singur implică faptul că $G$ admite o colorare k-regulată proprie (adică fiecare nod este colorat diferit de vecinii săi) pentru o anumită valoare a pasului. De exemplu, $(k,\lambda )=(2,0.5)$ generează o colorare proprie pe graful de distanțe generat de $D=\{2\}$. ($k$ este cunoscut ca numărul cromatic regulat al lui $D$.)

Fiind dat un graf orientat $G$, un flux fără zerouri pe $G$ asociază o valoare pozitivă $f(e)$ fiecărei muchii $e$, astfel încât fluxul spre exterior din fiecare nod este egal cu fluxul spre interior. Conjectura alergătorului singur implică faptul că, dacă $G$ are un flux fără zerouri cu cel mult $k$ valori întregi distincte, atunci $G$ are un flux cu valori doar în $\{1,2,\ldots ,k\}$ (eventual după inversarea direcțiilor unor arce din $G$). Acest rezultat a fost demonstrat pentru $k\geq 5$ cu metode separate, iar întrucât cazurile mai mici ale conjecturii alergătorului singur sunt soluționate, întreaga teoremă este demonstrată.

Rezultate cunoscute

Pentru o configurație dată de alergători, fie $\delta$ cea mai mică dintre distanțele maxime de singurătate ale alergătorilor, și decalajul de singurătate $\delta _{n}$ valoarea minimă a lui $\delta$ în toate configurațiile cu $n$ alergători. Cu această notație, conjectura afirmă că $\delta _{n}\geq 1/n$, o margine care, dacă este corectă, nu poate fi îmbunătățită. De exemplu, dacă alergătorul care va fi singur este staționar și se aleg vitezele $v_{i}=i$, atunci nu există moment în care acesta să fie la distanță strict mai mare de $1/n$ unități față de toți ceilalți, arătând că $\delta _{n}\leq 1/n$. Alternativ, această concluzie poate fi derivată rapid din teorema de aproximare a lui Dirichlet. Pentru $n\geq 2$ o margine inferioară simplă $\delta _{n}\geq 1/(2n-2)$ poate fi obținută printr-un argument de probabilitate.

Conjectura poate fi redusă la cazul în care vitezele alergătorilor sunt numere întregi pozitive: Dacă conjectura este adevărată pentru $n$ alergători cu viteze întregi, atunci este adevărată și pentru $n$ alergători cu viteze reale.

Margini mai bune

Se cunosc mici îmbunătățiri ale marginii inferioare $1/(2n-2)$. Chen & Cusick (1999) au arătat pentru $n\geq 5$ că daca $2n-5$ este prim, atunci $\delta _{n}\geq {\tfrac {1}{2n-5}}$, iar dacă $4n-9$ este prim, atunci $\delta _{n}\geq {\tfrac {2}{4n-9}}$. Perarnau & Serra (2016) au arătat necondiționat pentru $n$ suficient de mare că $$\delta _{n}\geq {\frac {1}{2n-4+o(1)}}.$$Tao (2018) a demonstrat cel mai bun rezultat asimptotic actual: pentru $n$ suficient de mare, $$\delta _{n}\geq {\frac {1}{2n-2}}+{\frac {c\log n}{n^{2}(\log \log n)^{2}}}$$ pentru o anumită constantă $c>0$. El a mai arătat și că întreaga conjectură este implicată prin demonstrarea conjecturii pentru viteze întregi de mărime $n^{O(n^{2})}$ (vezi Notația Big O). Teoretic această implicație permite demonstrarea conjecturii pentru un $n$ dat verificând o mulțime finită de cazuri, dar numărul de cazuri crește prea repede pentru a fi practic.

Conjectura a fost demonstrată pentru ipoteze specifice asupra vitezelor alergătorilor. Pentru $n$ suficient de mare, este adevărată dacă $${\frac {v_{i+1}}{v_{i}}}\geq 1+{\frac {22\log(n-1)}{n-1}}\qquad (i=1,\dots ,n-2).$$ Cu alte cuvinte, conjectura este adevărată pentru $n$ suficient de mare dacă vitezele cresc suficient de repede. Dacă constanta 22 este înlocuită cu 33, atunci conjectura este adevărată pentru $n\geq 16343$. Un rezultat similar pentru $n$ suficient de mare necesită doar o ipoteză similară pentru$i=\lfloor n/22\rfloor -1,\dots ,n-2$. Necondiționat de $n$, conjectura este adevărată dacă $v_{i+1}/v_{i}\geq 2$ pentru toți indicii $i$.

Pentru valori particulare ale lui n

Conjectura este adevărată pentru $n\leq 7$ alergători. Demonstrațiile pentru $n\leq 3$ sunt elementare; cazul $n=4$ a fost stabilit în 1972. Cazurile $n=5$, $n=6$, și $n=7$ au fost rezolvate în 1984, 2001 respectiv 2008. Prima demonstrație pentru $n=5$ a fost asistată de calculator, dar toate cazurile au fost demonstrate de atunci prin metode elementare.

Pentru unele valori ale lui $n$, există exemple sporadice cu o separare maximă de $1/n$ pe lângă exemplul cu $v_{i}=i$ dat mai sus. Pentru $n=5$, singurul exemplu cunoscut (până la translații și scalări) este $\{0,1,3,4,7\}$; pentru $n=6$ singurul exemplu cunoscut este $\{0,1,3,4,5,9\}$; iar pentru $n=8$ exemplele cunoscute sunt $\{0,1,4,5,6,7,11,13\}$ și $\{0,1,2,3,4,5,7,12\}$. Există o familie infinită explicită de astfel de cazuri sporadice.

Kravitz (2021) a formulat o versiune mai puternică a conjecturii care include cazuri de aproape-egalitate. Mai exact, el a conjecturat că pentru o mulțime dată de viteze $v_{i}$, fie $\delta =s/(s(n-1)+1)$ pentru un întreg pozitiv $s$, fie $\delta \geq 1/(n-1)$, unde $\delta$ este decalajul de singurătate al acelei configurații. El a confirmat această conjectură pentru $n\leq 4$ și câteva cazuri speciale.

Rifford (2022) a abordat problema timpului necesar pentru ca un alergător să devină singur. El a formulat o conjectură mai puternică afirmând că pentru orice număr întreg $n\geq 3$ există un număr întreg pozitiv $N$ astfel încât pentru orice colecție $v_{1},v_{2},\dots ,v_{n-1}$ de viteze pozitive și distincte să existe un moment de timp $t>0$ astfel încât $\operatorname {frac} (v_{i}t)\in [1/n,1-1/n]$ pentru $i=1,\dots ,n-1$ cu $$t\leq {\frac {N}{\operatorname {min} (v_{1},\dots ,v_{n-1})}}.$$Rifford a confirmat această conjectură pentru $n=3,4,5,6$ și a arătat că valoarea minimă a lui $N$ în fiecare caz este dată de $N=1$ pentru $n=3,4,5$ și $N=2$ pentru $n=6$. Rezultatul din urmă ($N=2$ pentru $n=6$) arată că dacă se consideră șase alergători pornind din $0$ la momentul de timp $t=0$ cu viteze constante $v_{0},v_{1},\dots ,v_{5}$ cu $v_{0}=0$ și $v_{1},\dots ,v_{5}$ distincte și pozitive, atunci alergătorul staționar este separat printr-o distanță de cel puțin $1/6$ de ceilalți în timpul primelor două tururi ale celui mai lent alergător nestaționar (dar nu neapărat în timpul primului tur).

Alte rezultate

Există un rezultat mult mai puternic pentru viteze alese aleator: folosind convenția cu alergătorul staționar, dacă $n$ și $\varepsilon >0$ sunt fixe și $n-1$ viteze sunt alese uniform aleator din $\{1,2,\ldots ,k\}$, atunci $P(\delta \geq 1/2-\varepsilon )\to 1$ când $k\to \infty$. Cu alte cuvinte, alergătorii cu viteze aleatorii vor fi foarte probabil „foarte singuri” la un moment dat – aproape $1/2$ unități de cel mai apropiat alergător. Întreaga conjectură este adevărată dacă „singurătatea” este înlocuită cu „aproape singurătatea”, adică cel mult un alt alergător se află până la $1/n$ față de un alergător dat. Conjectura a fost generalizată la un analog în corpurile de funcții algebrice.

Bibliografie

• Barajas, Javier; Serra, Oriol (2008). „The lonely runner with seven runners”. The Electronic Journal of Combinatorics. 15 (1): R48. doi:10.37236/772 . 
• ——; —— (septembrie 2009). „On the chromatic number of circulant graphs”. Discrete Mathematics. 309 (18): 5687–5696. doi:10.1016/j.disc.2008.04.041 . 
• Betke, U.; Wills, J. M. (1972). „Untere schranken für zwei diophantische approximations-funktionen”. Monatshefte für Mathematik. 76 (3): 214. doi:10.1007/BF01322924. 
• Bienia, Wojciech; Goddyn, Luis; Gvozdjak, Pavol; Sebő, András; Tarsi, Michael (ianuarie 1998). „Flows, view obstructions, and the lonely runner”. Journal of Combinatorial Theory, Series B. 72 (1): 1–9. doi:10.1006/jctb.1997.1770 . 
• Bohman, Tom; Holzman, Ron; Kleitman, Dan (februarie 2001). „Six lonely runners”. The Electronic Journal of Combinatorics. 8 (2): R3. doi:10.37236/1602 . 
• Chen, Yong-Gao; Cusick, T. W. (ianuarie 1999). „The view-obstruction problem for n-dimensional cubes”. Journal of Number Theory. 74 (1): 126–133. doi:10.1006/jnth.1998.2309 . 
• Chow, Sam; Rimanić, Luka (ianuarie 2019). „Lonely runners in function fields” (PDF). Mathematika. 65 (3): 677–701. doi:10.1112/S002557931900007X. 
• Cusick, T. W. (1973). „View-obstruction problems”. Aequationes Mathematicae. 9 (2–3): 165–170. doi:10.1007/BF01832623. 
• —— (1974). „View-obstruction problems in n-dimensional geometry”. Journal of Combinatorial Theory, Series A. 16 (1): 1–11. doi:10.1016/0097-3165(74)90066-1 . 
• ——; Pomerance, Carl (1984). „View-obstruction problems, III”. Journal of Number Theory. 19 (2): 131–139. doi:10.1016/0022-314X(84)90097-0 . 
• Czerwiński, Sebastian (2012). „Random runners are very lonely”. Journal of Combinatorial Theory, Series A. 119 (6): 1194–1199. arXiv:1102.4464 . doi:10.1016/j.jcta.2012.02.002. 
• —— (mai 2018). „The lonely runner problem for lacunary sequences”. Discrete Mathematics. 341 (5): 1301–1306. doi:10.1016/j.disc.2018.02.002 . 
• ——; Grytczuk, Jarosław (septembrie 2008). „Invisible runners in finite fields”. Information Processing Letters. 108 (2): 64–67. doi:10.1016/j.ipl.2008.03.019. 
• Dubickas, A. (2011). „The lonely runner problem for many runners”. Glasnik Matematicki. 46: 25–30. doi:10.3336/gm.46.1.05. 
• Goddyn, L.; Wong, Erick B. (2006). „Tight instances of the lonely runner” (PDF). Integers. 6 (A38). Accesat în 1 mai 2022. 
• Kravitz, N. (2021). „Barely lonely runners and very lonely runners: a refined approach to the Lonely Runner Problem”. Combinatorial Theory. 1. arXiv:1912.06034 . doi:10.5070/C61055383. 
• Perarnau, Guillem; Serra, Oriol (martie 2016). „Correlation among runners and some results on the lonely runner conjecture”. The Electronic Journal of Combinatorics. 23 (1): P1.50. arXiv:1407.3381 . doi:10.37236/5123 . 
• Renault, J. (2004). „View-obstruction: A shorter proof for 6 lonely runners”. Discrete Mathematics. 287 (1–3): 93–101. doi:10.1016/j.disc.2004.06.008 . 
• Rifford, L. (2022). „On the time for a runner to get lonely” (PDF). Acta Applicandae Mathematicae. 180: Paper No. 15. doi:10.1007/s10440-022-00515-9. 
• Tao, Terence (31 decembrie 2018). „Some remarks on the lonely runner conjecture”. Contributions to Discrete Mathematics. 13: No 2 (2018). doi:10.11575/cdm.v13i2.62728 . 
• Wills, Jörg M. (1967). „Zwei sätze über inhomogene diophantische approximation von irrationalzehlen”. Monatshefte für Mathematik. 71 (3): 263–269. doi:10.1007/BF01298332.