Conjectura alergătorului singur

Î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 Format:Mvar=6 alergători. Alergătorii colorați în negru nu au fost încă singuri. Arcurile albe, de lungime 2/Format:Mvar, 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.Format:Sfn

Această formulare vizuală a conjecturii a fost publicată pentru prima dată în 1998.Format:Sfn În multe formulări, inclusiv în cea originală a lui Jörg M. Wills,Format:SfnmFormat:Sfn 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.Format:Efn 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}\le \mathrm{frac}(v_{i}t)\le 1-\frac{1}{n}(i=1,\dots ,n-1),$$ unde $\mathrm{frac}(x)$ reprezintă partea fracționară a lui $x$.Format:Sfn 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.Format:Efn Această convenție este folosită în restul acestui articol. Conjectura lui Wills a făcut parte din munca sa în aproximarea diofantică,Format:Sfnm 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 Format:Mvar-hipercub cu lungimea laturii $s$ în spațiul Format:Mvar-dimensional ($n\ge 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.Format:Sfn 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 Format:Mvar-regulată a numerelor întregi cu pasul $\lambda \in ℝ$ 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 Format:Mvar-regulată proprie (adică fiecare nod este colorat diferit de vecinii săi) pentru o anumită valoare a pasului.Format:Sfn 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,\dots ,k\}$ (eventual după inversarea direcțiilor unor arce din $G$). Acest rezultat a fost demonstrat pentru $k\ge 5$ cu metode separate, iar întrucât cazurile mai mici ale conjecturii alergătorului singur sunt soluționate, întreaga teoremă este demonstrată.Format:Sfn

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ătateFormat:Sfn ${\delta }_n$ valoarea minimă a lui $\delta$ în toate configurațiile cu $n$ alergători. Cu această notație, conjectura afirmă că ${\delta }_n\ge 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\le 1/n$.Format:Efn Alternativ, această concluzie poate fi derivată rapid din teorema de aproximare a lui Dirichlet. Pentru $n\ge 2$ o margine inferioară simplă ${\delta }_n\ge 1/(2n-2)$ poate fi obținută printr-un argument de probabilitate.Format:Sfn

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.Format:Sfn

Margini mai bune

Se cunosc mici îmbunătățiri ale marginii inferioare $1/(2n-2)$. Format:Harvtxt au arătat pentru $n\ge 5$ că daca $2n-5$ este prim, atunci ${\delta }_n\ge \frac{1}{2n-5}$, iar dacă $4n-9$ este prim, atunci ${\delta }_n\ge \frac{2}{4n-9}$. Format:Harvtxt au arătat necondiționat pentru $n$ suficient de mare că $${\delta }_n\ge \frac{1}{2n-4+o(1)}.$$Format:Harvtxt a demonstrat cel mai bun rezultat asimptotic actual: pentru $n$ suficient de mare, $${\delta }_n\ge \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.Format:Sfn

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}\ge 1+\frac{22\log (n-1)}{n-1}(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\ge 16343$.Format:Sfn Un rezultat similar pentru $n$ suficient de mare necesită doar o ipoteză similară pentru$i=\lfloor n/22\rfloor -1,\dots ,n-2$.Format:Sfn Necondiționat de $n$, conjectura este adevărată dacă $v_{i+1}/v_i\ge 2$ pentru toți indicii $i$.Format:Sfn

Pentru valori particulare ale lui Format:Mvar

Conjectura este adevărată pentru $n\le 7$ alergători. Demonstrațiile pentru $n\le 3$ sunt elementare; cazul $n=4$ a fost stabilit în 1972.Format:Sfnm 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.Format:Sfnm

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.Format:Sfn 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\}$.Format:Sfn Există o familie infinită explicită de astfel de cazuri sporadice.Format:Sfn

Format:Harvtxt 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$,Format:Efn fie $\delta \ge 1/(n-1)$, unde $\delta$ este decalajul de singurătate al acelei configurații. El a confirmat această conjectură pentru $n\le 4$ și câteva cazuri speciale.

Format:Harvtxt 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\ge 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 $\mathrm{frac}(v_{i}t)\in [1/n,1-1/n]$ pentru $i=1,\dots ,n-1$ cu $$t\le \frac{N}{\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 $\epsilon >0$ sunt fixe și $n-1$ viteze sunt alese uniform aleator din $\{1,2,\dots ,k\}$, atunci $P(\delta \ge 1/2-\epsilon )\to 1$ când $k\to \mathrm{\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.Format:Sfn Î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.Format:Sfn Conjectura a fost generalizată la un analog în corpurile de funcții algebrice.Format:Sfn

Bibliografie

• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journalFormat:Legătură nefuncțională
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal
• Format:Cite journal