Î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 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 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 alt=Animation illustrating the case of 6 runners|dreapta|miniatura| Exemplu de un caz al conjecturii cu =6 alergători. Alergătorii colorați în negru nu au fost încă singuri. Arcurile albe, de lungime 2/, indică faptul că un alergător este în prezent singur. Alergătorii galbeni au fost singuri la un moment dat. Se consideră alergători pe o pistă circulară de lungime unu. La momentul inițial , 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 dacă se află la o distanță (măsurată de-a lungul cercului) de cel puțin 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 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 și 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 de viteze pozitive, distincte, există un timp astfel încât unde reprezintă partea fracționară a lui . 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 -lea alergător la momentul de timp , 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 alt=A series of red squares and a green line, with slope 2, narrowly hitting the squares.|miniatura| 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ă este un -hipercub cu lungimea laturii în spațiul -dimensional (). Se pune câte o copie centrată a lui în fiecare punct de coordonate semi-întregi. O semidreaptă de la origine fie ratează toate copiile lui , 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ă , 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 vor lăsa goluri, așa cum se arată, și pătrate cu lungimea laturii 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 pe mulțimea numerelor întregi cu mulțimea de distanțe întregi pozitive , are o muchie între și dacă și numai dacă . De exemplu, dacă , orice pereche de numere pare consecutive, și de numere impare consecutive, este adiacentă, toate la un loc formând două componente conexe. O colorare -regulată a numerelor întregi cu pasul atribuie fiecărui număr întreg una dintre culori în funcție de restul modulo . De exemplu, dacă , colorarea se repetă la fiecare numere întregi și fiecare două numere întregi și sunt colorate la fel. Luând , conjectura alergătorului singur implică faptul că admite o colorare -regulată proprie (adică fiecare nod este colorat diferit de vecinii săi) pentru o anumită valoare a pasului. De exemplu, generează o colorare proprie pe graful de distanțe generat de . ( este cunoscut ca numărul cromatic regulat al lui .)

Fiind dat un graf orientat , un flux fără zerouri pe asociază o valoare pozitivă fiecărei muchii , astfel încât fluxul spre exterior din fiecare nod este egal cu fluxul spre interior. Conjectura alergătorului singur implică faptul că, dacă are un flux fără zerouri cu cel mult valori întregi distincte, atunci are un flux cu valori doar în (eventual după inversarea direcțiilor unor arce din ). Acest rezultat a fost demonstrat pentru 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 cea mai mică dintre distanțele maxime de singurătate ale alergătorilor, și decalajul de singurătate valoarea minimă a lui în toate configurațiile cu alergători. Cu această notație, conjectura afirmă că , 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 , atunci nu există moment în care acesta să fie la distanță strict mai mare de unități față de toți ceilalți, arătând că . Alternativ, această concluzie poate fi derivată rapid din teorema de aproximare a lui Dirichlet. Pentru o margine inferioară simplă 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 alergători cu viteze întregi, atunci este adevărată și pentru alergători cu viteze reale.

Margini mai bune Se cunosc mici îmbunătățiri ale marginii inferioare . au arătat pentru că daca este prim, atunci , iar dacă este prim, atunci . au arătat necondiționat pentru suficient de mare că a demonstrat cel mai bun rezultat asimptotic actual: pentru suficient de mare,

pentru o anumită constantă . El a mai arătat și că întreaga conjectură este implicată prin demonstrarea conjecturii pentru viteze întregi de mărime (vezi Notația Big O). Teoretic această implicație permite demonstrarea conjecturii pentru un 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 suficient de mare, este adevărată dacă

Cu alte cuvinte, conjectura este adevărată pentru suficient de mare dacă vitezele cresc suficient de repede. Dacă constanta 22 este înlocuită cu 33, atunci conjectura este adevărată pentru . Un rezultat similar pentru suficient de mare necesită doar o ipoteză similară pentru. Necondiționat de , conjectura este adevărată dacă pentru toți indicii .

Pentru valori particulare ale lui

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

Pentru unele valori ale lui , există exemple sporadice cu o separare maximă de pe lângă exemplul cu dat mai sus. Pentru , singurul exemplu cunoscut (până la translații și scalări) este ; pentru singurul exemplu cunoscut este ; iar pentru exemplele cunoscute sunt și . Există o familie infinită explicită de astfel de cazuri sporadice.

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 , fie pentru un întreg pozitiv , fie , unde este decalajul de singurătate al acelei configurații. El a confirmat această conjectură pentru și câteva cazuri speciale.

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 există un număr întreg pozitiv astfel încât pentru orice colecție de viteze pozitive și distincte să existe un moment de timp astfel încât pentru cu Rifford a confirmat această conjectură pentru și a arătat că valoarea minimă a lui în fiecare caz este dată de pentru și pentru . Rezultatul din urmă ( pentru ) arată că dacă se consideră șase alergători pornind din la momentul de timp cu viteze constante cu și distincte și pozitive, atunci alergătorul staționar este separat printr-o distanță de cel puțin 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ă și sunt fixe și viteze sunt alese uniform aleator din , atunci când . Cu alte cuvinte, alergătorii cu viteze aleatorii vor fi foarte probabil „foarte singuri” la un moment dat – aproape 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 față de un alergător dat. Conjectura a fost generalizată la un analog în corpurile de funcții algebrice.

Note explicative

Note

Bibliografie

Categorie:Conjecturi Categorie:Ecuații diofantice