Problema Danzer-Grunbaum

Problema Danzer-Grunbaum este o problemă de geometrie combinatorie care ridică întrebarea care este numărul maxim de puncte care pot fi plasate într-un spațiu multidimensional, astfel încât acestea să nu formeze unghiuri drepte sau obtuze între ele. Se știe că maxim trei astfel de puncte pot fi plasate pe un plan, iar cinci astfel de puncte pot fi plasate în spațiu tridimensional. În 2017, s-a dovedit că Θ astfel de puncte pot fi localizate în spațiul dimensiunilor. $d$ $(2^{d})$

Enunțul problemei

Pentru dat , notăm cu numărul maxim de puncte diferite din spațiul -dimensional, astfel încât orice trei puncte formează un triunghi ascuțit , adică pentru oricare trei, produsul scalar . $d$ $f(d)$ $d$ $x,y,z$ $\langle {yx,zx}\rangle >0$

Cum crește relativ ? $f(d)$ $d$

Cu alte cuvinte, problema este să găsești o formulă simplă care să exprime cu cea mai bună acuratețe posibilă (și, de asemenea, să găsești un algoritm pentru construirea unui set de puncte). $f(d)$ $d$ $f(d)$

Mulțimile ale căror puncte formează numai unghiuri ascuțite se numesc mulțimi cu unghiuri ascuțite . Rețineți că din definiție rezultă că nici trei puncte dintr-o mulțime cu unghi ascuți nu pot fi situate pe aceeași linie.

Din martie 2018, se știe că . $2^{d-1}+1\leq f(d)\leq 2^{d)$

Sarcini conexe

Seturi fără unghiuri obtuze

Următoarea problemă a fost pusă de Erdős chiar mai devreme decât formularea clasică a problemei Danzer-Grunbaum [1] :

Pentru dat , notează cu numărul maxim de puncte diferite din spațiul -dimensional, dintre care trei nu formează un unghi strict obtuz, adică pentru oricare trei dintre ele $d$ $g(d)$ $d$ $x,y,z$ $\langle {yx,zx}\rangle \geq 0$

Cum crește relativ ? $g(d)$ $d$

Se știe că . $g(d)=2^{d)$

Vârfurile cubului

În prima lucrare cu adevărat revoluționară pe această temă, Erdős și Furedi au construit un set mare care satisface condiții date de la vârfurile unui cub dimensional . Prin urmare, în lucrările ulterioare de îmbunătățire a rezultatului lor, următoarea problemă a fost uneori luată în considerare separat: $d$ ${\left\lbrace {0,1}\right\rbrace }^{d)$

Pentru unul dat, notăm cu numărul maxim de vârfuri diferite ale cubului -dimensional , dintre care trei nu formează nici un unghi drept, nici un unghi obtuz, adică pentru oricare trei dintre ele, $d$ $f_{\square }(d)$ $d$ $\left\lbrace {0,1}\right\rbrace ^{d}$ $x,y,z$ $\langle {yx,zx}\rangle >0$

Cum crește relativ ? $f_{\square }(d)$ $d$

Este evident că . $f_{\square}(d)\leq f(d)$

Istoria studiului

Primele mențiuni (Erdős, 1948, 1957)

Istoria problemei începe în 1948, când Pal Erdős a publicat următorul caz special al viitoarei probleme Danzer-Grünbaum [2] în secțiunea „Probleme suplimentare de rezolvat ” din The American Mathematical Monthly :

Să fie date opt puncte în spațiu . Demonstrați că este întotdeauna posibil să găsiți trei dintre ele care nu formează un triunghi ascuțit. ${\mathbb {R} }^{3)$

Adică, problema a întrebat dacă este adevărat că $f(3)<8$

În 1957, în Michigan Mathematical Journal , într-un articol cu multe presupuneri, Erdős a publicat o presupunere generală, dar cu privire la mulțimi obtuze.

Fie un set de puncte într-un spațiu de dimensiune . Este adevărat că atunci printre ele există neapărat trei puncte care formează un unghi obtuz? $S$ $2^{d}+1$ $k$

Adică, ipoteza afirma că . $g(d)\leq 2^{d)$

Articolul spunea că Nicolas Kuiper și Boerdijk au găsit o dovadă , dar dovada lor nu fusese încă publicată. $d=3$

Alături de ipoteză a fost următoarea întrebare:

Este adevărat că există un set de șase (șapte) puncte în spațiul tridimensional astfel încât oricare trei dintre ele formează un unghi ascuțit?

Sau, cu alte cuvinte, este adevărat că sau . [unu] $f(3)\geq 6$ $f(3)\geq 7$

Prima ipoteză (Danzer și Grünbaum, 1962)

Prima construcție generală pentru rezolvarea acestei probleme a fost construită de Ludwig Danzer și Branko Grünbaum într-o lucrare din 1962. Au construit un punct în spațiul -dimensional , a cărui matrice de coordonate arăta astfel (rândurile sunt puncte diferite, coloanele sunt coordonate diferite): $d$ $2d-1$

{\begin{pmatrix}1&0&0&\cdots &0&0\\-\delta _{1}&1&0&\cdots &0&0\\-\delta _{1}&-1&0&\cdots &0&0\\-\delta _{2} &0&1&\cdots &0&0\\-\delta _{2}&0&-1&\cdots &0&0\\\vdots &\vdots &\ddots &\vdots \\-\delta _{d-2}&0&0&\cdots &1&0\\- \delta _{d-2}&0&0&\cdots &-1&0\\-\delta _{d-1}&0&0&\cdots &0&1\\-\delta _{d-1}&0&0&\cdots &0&-1\end{pmatrix }}

unde sunt numere distincte perechi, toate mai mici. $\delta _{1},\dots ,\delta _{d-1)$

O simplă enumerare combinatorie a diferitelor tipuri de unghiuri care apar face posibil să se arate că niciunul dintre aceste puncte nu formează unghiuri drepte sau obtuze. Rezultă că $f(d)\geq 2d-1$

În aceeași lucrare, autorii au emis ipoteza că este imposibil să se construiască un număr mai mare de puncte care să îndeplinească această condiție, adică aceea [3] . $f(d)=2d-1$

Tot în această lucrare a fost demonstrată limita superioară , ceea ce a fost sugerat anterior de Erdős. $f(d)\leq g(d)\leq 2^{d)$

Aplicarea metodei probabilistice (Erdős, Furedi, 1983)

În 1983, Paul Erdős și Zoltan Furedy au infirmat ipoteza Danzer-Grünbaum folosind o metodă probabilistică , arătând că

f(d)\geq f_{\square}(d)\geq \left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3} }}\right)}^{d}}\right\rfloor

Acest lucru a făcut posibilă construirea de contraexemple pentru conjectura Danzer-Grünbaum pentru . [4] [5] $d\geq 35$

Totuși, datorită particularităților metodei probabilistice, demonstrarea lor a fost ineficientă și nu a permis construirea explicit a acestei mulțimi (cu excepția unei enumerari directe) [3] .

Ideea principală a lui Erdős și Furedy a fost să aleagă un set de puncte, care (cu probabilitate pozitivă) vor avea foarte puține unghiuri drepte și obtuze, și apoi pur și simplu eliminați câte un punct din fiecare dintre aceste unghiuri, eliminându-le astfel pe toate.

Scurtă descriere a ideii de probă

Dovada lui Erdős și Furedi a fost selectarea aleatorie și independentă a punctelor din cubul unității , unde și pentru a demonstra că, cu o astfel de alegere, probabilitatea ca printre ele să fie doar triunghiuri obtuze sau degenerate este pozitivă. $2n$ $\left\lbrace {0,1}\right\rbrace ^{d}$ $n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\ rfloor$ $n$

Alegerea aleatorie a unui punct înseamnă aici generarea acestuia conform schemei Bernoulli cu probabilitatea de a genera unul sau zero pe una sau alta coordonată a punctului, indiferent de celelalte coordonate. $p={\frac {1}{2)}$

Pentru a demonstra estimarea numărului de triunghiuri obtuse s-a folosit proprietatea de liniaritate a așteptării matematice. Probabilitatea ca un anumit triplu de puncte să formeze un unghi drept este egală - acest lucru este ușor de demonstrat luând în considerare separat contribuția fiecărei coordonate la produsul scalar. Înmulțind această probabilitate cu numărul de astfel de triple, obținem valoarea așteptării matematice, iar aceasta va da deja, conform inegalității lui Markov , o probabilitate pozitivă ca variabila aleatoare să nu o depășească. $\left({\frac {3}{4}}\right)^{d}$

Erdős-Füredi Îmbunătățiri constante

O îmbunătățire fără schimbarea metodei

Chiar și fără a schimba metoda Erdős în esența sa, se poate obține o estimare mai bună pur și simplu alegând un număr diferit ca parametru care determină câte puncte aleatorii să aleagă.

Aigner și Ziegler în 2003, descriind teorema Erdős în cartea lor de recenzii Proofs from the Book , au corectat acest parametru și au obținut că . [6] Acesta este cel mai bun lucru care poate fi obținut în acest fel. $f_{\square}(d)\geq 2\left\lfloor {{\frac {\sqrt {6}}{9}}{\left({\frac {2}{\sqrt {3}} }\right)}^{d}}\right\rfloor$

Dovada

Metoda Erdős pentru numărul de puncte alese a stabilit că cel puțin o dată printre ele nu mai există unghiuri ascuțite. $k$ $3{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}\leq {\frac {k^{3}}{2 }}{\left({\frac {3}{4}}\right)}^{d}$

Aceasta garantează existența unui set de puncte fără unghiuri drepte sau obtuze. $h(k)=k-{\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}$

Dacă luăm derivata și optimizăm această funcție în raport cu , obținem $k$

h'(k)=1-{\frac {3}{2}}{\left({\frac {3}{4}}\right)}^{d}k^{2}

k^{2}={\frac {2}{3}}{\left({\frac {4}{3}}\right)}^{d}

k_{cel mai bun}={\sqrt {\frac {2}{3}}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

h(k_{cel mai bun})={\left({\frac {2}{\sqrt {3}}}\right)}^{d}{\sqrt {\frac {2}{3}} }\left({1-{\frac {2}{3}}\cdot {\frac {1}{2}}}\right)={\left({\frac {2}{\sqrt {3} }}\right)}^{d}{\sqrt {\frac {2}{3}}}\cdot {\frac {2}{3}}={\frac {2{\sqrt {6}}} {9}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

Bevan (2006)

În 2006, D. Bevan a îmbunătățit estimarea la . [7] $f(d)\geq 2\left\lfloor {{\frac {1}{3}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d +1}}\dreapta\retaj$

Cu toate acestea, punctele din construcția sa nu erau vârfurile unui cub unitar, așa că nu a îmbunătățit estimarea pentru. $f_{\square }(d)$

Scurtă descriere a ideii de probă

În construcția lui Bevan, la fiecare dintre punctele aleatoare alese i s-a adăugat un vector aleator foarte scurt (fiecare are al său), distribuit continuu și uniform în cubul -dimensional pentru unele suficient de mici . $d$ $[-\varepsilon;\varepsilon]^{d)$ $\varepsilon$

Bevan a introdus mai multe leme care arată că unele polinoame din variabile aleatoare distribuite uniform și simetric (considerate ca o nouă variabilă aleatoare) au probabilitatea de a fi pozitive nu mai puțin de . Aceste leme au făcut posibil să se arate că, în mai mult de jumătate din cazuri, o deplasare prin vectori suplimentari nu ascuțit unghiul dintre punctele situate în fața acestuia în unghi drept (deoarece modificarea produsului scalar, care este un cantitativ indicator al clarității unghiului, se exprimă precis prin polinoame în coordonatele vectorilor suplimentari ). ${\frac {1}{2))$

Toate acestea au făcut posibilă consolidarea estimării pentru așteptarea matematică a numărului de unghiuri neacute și să arate că printre punctele alese aleatoriu pot exista doar unghiuri neacute. $k$ ${\frac {3}{2}}{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}$

În plus, Bevan a obținut o serie de rezultate pentru dimensiuni mici , în urma cărora conjectura Danzer-Grünbaum a fost infirmată la . [opt] $d$ $d\geq 7$

Buchok (2009)

În 2009, Larisa Buchok, fără a schimba metodele lui Erdős, Furedi și Bevan pentru generarea punctelor, a calculat mai precis pierderile din ștergerea punctelor implicate în colțurile neacute. S-a dovedit că acest lucru permite obținerea următoarelor estimări [8] :

f_{\square}(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {66}}}{243}}{\left({ \frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor

f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {22{\sqrt {33}}}{243}}{\left({\frac {2 }{\sqrt {3}}}\right)}^{d}}\right\rfloor

Scurtă descriere a ideii de probă

În primul rând, Buchok, având în vedere un set de puncte generat arbitrar, a scos din el acelea triunghiulare obtuz-unghiulare care nu se intersectează (prin puncte) cu altele. Există, evident, puține astfel de triunghiuri - de cel puțin trei ori mai puțin decât toate punctele.

Restul triunghiurilor, datorită „întrețeserii” lor vă permit să eliminați un număr mare de triunghiuri prin eliminarea unui singur punct. Dacă în procesul acestui triunghiuri noi apar care nu se intersectează cu celelalte (care trebuie îndepărtate fiecare printr-un punct separat), atunci se dovedește că numărul lor este compensat de câștigul obținut prin eliminarea unui vârf conținut în mai multe triunghiuri. , a căror înlăturare, de fapt, le face să nu se suprapună.

Toate acestea permit, știind că printre puncte există unghiuri neacute, să se construiască o mulțime de puncte unghiulară ascuțită, spre deosebire de estimarea trivială, când se aleg doar puncte . $k$ $s$ $k-{\frac {k}{3}}-{\frac {3}{4}}\left({s-{\frac {k}{3}}}\right)={\frac {11}{12}}k-{\frac {3}{4}}s$ $ks$

Buchok (2009/2010)

În 2010, Buchok a publicat două metode pentru a îmbunătăți simultan inegalitățile anterioare la rezultate:

f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {165}}}{243}}{\left({\frac {2 }{\sqrt {3}}}\right)}^{d}}\right\rfloor

Scurtă descriere a ideii de probă

În această lucrare, Buchok combină ideea de a alege puncte dintr-o mulțime fixă și ideea de a adăuga o mică abatere a punctelor de la vârfurile unui cub.

Ca și în metoda Erdős și Furedy, Buchok alege puncte aleatoriu, iar fiecare coordonată în mod independent, conform schemei Bernoulli, dar nu cu probabilități

P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}

dar cu un număr mare de opțiuni, cu probabilități

$P(v_{i}=0)=P(v_{i}=1)=P(v_{i}=-\varepsilon _{i})=P(v_{i}=1+\varepsilon _{i})={\frac {1}{4}}$

unde sunt numere suficient de mici (un număr separat pentru fiecare coordonată) care îndeplinesc condițiile $\varepsilon _{1},\dots,\varepsilon _{n)$

\sum \limits _{i=1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})}<1

\varepsilon _{j}^{2}>\sum \limits _{i=j+1}^{d}{(\varepsilon _{i}+{\varepsilon _{i))^{2 })},1\leq j\leq d-1

Toate acestea permit, prin enumerarea a 64 de opțiuni de modificare a contribuției uneia sau alteia coordonate a produsului rocii, să se reducă probabilitatea ca vreo trei puncte să formeze un unghi neacut, spre deosebire de cel standard din Erdős. -Metoda Furedy și, în consecință, reduce așteptările matematice ale numărului de unghiuri neacute. ${\frac {2}{5}}{\left({\frac {3}{4}}\right)}^{d}+{\frac {3}{5}}{\left( {\frac {7}{16}}\right)}^{d}$ ${\left({\frac {3}{4}}\right)}^{d}$

După aceea, tehnica Butchok poate fi aplicată pentru a elimina colțurile obtuze din munca ei anterioară, ceea ce completează dovada.

f(d)\geq {\frac {2}{3}}\left\lfloor {{\sqrt {2}}{\left({\frac {2}{\sqrt {3}}}\ dreapta)}^{d}}\right\rfloor

Scurtă descriere a ideii de probă

Spre deosebire de prima metodă din aceeași lucrare, care a constat în schimbarea însuși algoritmul de alegere a punctelor aleatoare, a doua metodă a oferit alegerea obișnuită conform schemei Erdős-Füredy cu probabilități pentru fiecare coordonată a fiecărui punct. Câștigul principal în acest caz a fost scăderea „inteligentă” a punctelor din cea mai bună combinație (cu cel mai mic număr de unghiuri obtuze). $P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2}}$

Ca și în prima metodă, punctele au fost mutate de un vector de lungime fixă mică (este suficient să luați ) departe de cub, dar numai de-a lungul unei coordonate și strict în funcție de dacă există și alte unghiuri obtuze pentru un punct central dat de un unghi obtuz, pentru care este punct lateral (adică, ca în prima lucrare a lui Buchok, triunghiurile dreptunghiulare au fost subîmpărțite în intersectare și neintersectare, dar analizate puțin diferit față de prima lucrare). $\varepsilon >0$ $\varepsilon <{\frac {1}{4)}$

Mai precis, toate punctele celei mai bune combinații au fost împărțite în patru clase în funcție de satisfacția proprietăților:

$Q_1$ : toate unghiurile cu un vârf într-un punct dat sunt acute;
$Q_{2}$ : un punct este un vârf de cel puțin un unghi drept, iar toate unghiurile ascuțite cu un vârf în acest punct aparțin triunghiurilor ascuțite;
$Q_{3}$ : un punct este un vârf de cel puțin un unghi drept și exact un unghi ascuțit al unui triunghi dreptunghic;
$Q_{4)$ : punctul este un vârf de cel puțin un unghi drept și cel puțin două unghiuri ascuțite de triunghiuri dreptunghiulare.

Punctele care satisfac proprietatea au fost pur și simplu eliminate din set (din moment ce nu pot fi multe dintre ele), iar coordonatele celorlalte au fost modificate, așa cum este descris mai sus. $Q_{4)$

Ca și în prima metodă, o căutare completă a tabelului cu 64 de opțiuni pentru contribuția uneia sau alteia coordonate la produsul scalar a făcut posibil să se demonstreze că, după aceste modificări ale coordonatelor, nu va exista unghi drept sau unghi obtuz. triunghiuri din multime.

Dovada celui de-al doilea dintre rezultate a fost obținută cel târziu în 2009, întrucât este menționată într-un sondaj pe această temă. [9] [10]

Îmbunătățirea unei scheme probabilistice prin hipergrafe (Ackerman și Ben-Zvi, 2008/2009)

În timp ce alți matematicieni lucrau la îmbunătățiri elementare ale metodei Erdős, Eyjal Ackerman și Oren Ben-Zvi au publicat în mod independent în 2009 o dovadă, obținută în 2008, a existenței unei constante astfel încât $c>0$

f_{\square}(d)\geq c{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

Aceasta a fost prima îmbunătățire asimptotică a estimării de la lucrarea Erdős-Füredy.

Dovada a ocupat doar o pagină și a constat în aplicarea construcției Erdős-Füredy a unei leme algoritmice demonstrate anterior privind dimensiunea unei mulțimi independente într-un hipergraf în condiții speciale. [unsprezece]

Scurtă descriere a ideii de probă

Ackerman și Zvi au folosit un caz special al lemei din sondajul efectuat de Bertram-Kretzberg și Lefmann asupra aspectelor algoritmice ale găsirii de mulțimi independente în hipergrafe. [12] Cazul particular luat în considerare a precizat următoarele:

Să fie date constante . $c,\varepsilon >0$

Fie un hipergraf, ale cărui muchii constau din trei vârfuri, care conține vârfuri și al cărui grad mediu de vârfuri nu depășește , unde pentru . $H$ $n$ $t^{2}$ $t\to\infty$ $n\la\infty$

Să nu depășească și numărul de perechi de muchii de tip (un fel de „cicluri” în sensul unui hipergraf) . $\left({\left\lbrace {a,b,c}\right\rbrace ,\left\lbrace {a,b,d}\right\rbrace }\right)$ $cnt^{3-\varepsilon }$

Apoi, în timp polinomial , se poate găsi într- o mulțime independentă de vârfuri de dimensiune $n$ $H$ $\Omega \left({\frac {n{\sqrt {\log t}}}{t}}\right)$

Autorii au folosit construcția Erdős-Fyuredi fără a modifica în vreun fel algoritmul de selecție a punctelor. Dar, alături de media numărului de triunghiuri neacute, au calculat și media numărului de cicluri (în sensul menționat mai sus) într-un hipergraf ale cărui muchii corespund triplelor de puncte care formează unghiuri drepte sau obtuze (aceasta se calculează prin liniaritatea mediei, la fel ca numărul unghiurilor obtuze, dar prin luarea în considerare nu a triplelor de puncte, ci a patrurilor).

Un set independent de puncte într-un astfel de hipergraf va fi doar setul care nu conține triunghiuri obtuse și, cu alegerea parametrilor , are dimensiunea $n=c_{1}{\left({\frac {2}{\sqrt {3}}}\right)}^{{\frac {101}{100}}d},t=c_{ 2}{\left({\frac {2}{\sqrt {3}}}\right)}^{\frac {d}{100}}$ $\Omega \left({{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right)$

Îmbunătățirea Fundației Degree (Harangi, 2011)

În 2011, Harangi a demonstrat o estimare exponențială cu o bază de exponenți mai bună, și anume, a demonstrat existența unei constante astfel încât $c>0$

f(n)\geq c{\left({\sqrt[{10}]{\frac {144}{23))}\right)}^{d}>c\cdot 1.201^{d}

Dovada lui a fost și o modificare a construcției Erdős-Füredi. [13]

Primul proiect din beton (Zakharov, 2017)

La 30 aprilie 2017, Dmitri Zakharov, învață în clasa a X-a și fiind elev al lui Andrei Raigorodsky , a publicat o preprint a unei construcții explicite (nu probabilistice) constând din puncte care formează doar unghiuri ascuțite. $2^{\left\lceil {\frac {d}{2}}\right\rceil }$

Designul lui Zakharov nu a fost o dezvoltare a metodei Erdős, ci a folosit o idee nouă, simplă, descrisă pe o pagină. [14] [3]

În noiembrie același an, dovada a fost publicată în Discrete & Computational Geometry . [cincisprezece]

Scurtă descriere a ideii de probă

Metoda lui Zaharov a fost de a construi un set de puncte în mod recurent . În acest caz, tranziția a fost efectuată de la setul pentru spațiul de dimensiune la setul pentru spațiul de dimensiune $d$ $d+2$

Principiul construirii unui cub (sau paralelipiped) a fost luat ca bază, atunci când toate punctele sunt „copiate” și copiile sunt transferate la o anumită distanță de-a lungul unei noi dimensiuni, ortogonale cu toate segmentele dintre punctele din construcția anterioară (și în general la toate liniile drepte din spațiul anterior). Acest lucru ar dubla numărul de puncte și ar modifica unghiurile disponibile (pentru unghiurile ale căror puncte aparțin unor copii diferite) doar ușor (produsul scalar se va schimba cu cel mult o cantitate proporțională cu pătratul deplasării în noua dimensiune). Cu toate acestea, cu o astfel de construcție, apar unghiuri drepte ale formei , unde și sunt copii diferite ale unui punct. $\angle {v_{2}v_{1}w_{1))$ $v_{1}$ $v_{2}$

Pentru a scăpa de unghiurile drepte, Zaharov a efectuat o deplasare de-a lungul a două noi dimensiuni simultan, printr-un vector de aceeași lungime, dar în direcții diferite, iar ambele copii ale fiecărui punct s-au deplasat de-a lungul noilor dimensiuni, spre deosebire de construirea unui cub. , când toate punctele din construcția anterioară rămân în limitele spațiului său anterior. Toate acestea au făcut posibilă „deformarea” puțină a segmentelor „verticale” emergente (extinse de-a lungul noii dimensiuni care se introduce) între puncte pentru a scăpa de unghiurile pe care le formează cu segmentele care se află exclusiv în spațiul anterior al unei mai mici. dimensiune.

Mai precis, având un set fără unghiuri drepte și obtuze, Zaharov alege pentru fiecare punct un vector bidimensional de o lungime suficient de mică (și, mai important, aceeași pentru toate) și în așa fel încât să fie valabil pentru orice alt punct. . Apoi, pentru o lungime suficient de mică a vectorilor , este posibil să se demonstreze că punctele de setare $S$ ${\mathbb {R} }^{d)$ $x\în S$ $\phi (x)=\left({\alpha (x),\beta (x)}\right)$ $\phi (x)\not =\pm \phi (y)$ $x,y\în S$ $\phi(x)$

S'=\left\lbrace {(x_{1},\dots,x_{d},\alpha (x),\beta (x)):x\in S}\right\rbrace \cup \ stânga\lbrace {(x_{1},\dots ,x_{d},-\alpha (x),-\beta (x)):x\in S}\right\rbrace

de asemenea, nu formează unghiuri drepte sau obtuze (și faptul că aceste mulțimi nu se intersectează este evident din construcție ). $\phi(x)$

Aceasta dovedește recurența și, prin inducție , întreaga teoremă. $f(d+2)\geq 2f(d)$

Estimare prin numere Fibonacci (Zakharov, 2017)

În iulie 2017, Zakharov a publicat un preprint al unei lucrări care dovedește acest lucru

f(d)>F_{n}>c{\left({\frac {1+{\sqrt {5}}}{2}}\right)}^{d}>c\cdot 1,618^ {d}

unde este --lea număr Fibonacci și este o constantă absolută. [16] A doua inegalitate rezultă din formula lui Binet . $F_{n}$ $n$ $c>0$

Scurtă descriere a ideii de probă

Ideea a fost aceeași ca și în prima lucrare - copierea punctelor cu deplasarea ulterioară de către un vector bidimensional suficient de mic în dimensiuni noi.

Cu toate acestea, acum am considerat o combinație de puncte într-o mulțime -dimensională, printre care punctele (numărul maxim posibil) se află într-un singur hiperplan de dimensiune . În consecință, operația cu copiere și deplasare a fost efectuată numai pentru ei, iar noile dimensiuni au fost introduse ortogonale , astfel încât, în urma operației, numărul total de dimensiuni a crescut cu doar unul, iar pentru numărul de puncte o expresie recursivă. a fost obținut $d$ $f(d-1)$ $H\subset {\mathbb {R} }^{d)$ $d-1$ $H$

f(n+1)=f(n)+f(n-1)

Estimare maximă de comandă (Gerencher și Harangi 2017)

Apariția operei lui Zaharov a provocat încercări de a găsi contraexemple mai bune pentru dimensiuni reduse. S-a presupus că , după care au fost construite exemple de mulțimi cu unghi ascuți, demonstrând că $f(d)\geq 2^{d-1}+1$

f(4)\geq 9

f(5)\geq 17

Ideea folosită în construcția acestor exemple a fost o ușoară fluctuație a punctelor cubului -dimensional în , inclusiv de-a lungul ultimei coordonate care nu are legătură cu subspațiul -dimensional al acestui cub. [17] $(d-1)$ ${\mathbb {R} }^{d)$ $(d-1)$

Această idee poate fi generalizată cu ușurință la dimensiuni mai mari, ceea ce Gerincher și Harangi au făcut în septembrie 2017 și au publicat un articol care dovedește rezultatul pentru orice . La fel ca soluția lui Grizzly, rezultatul lor ne permite să construim o mulțime unghiulară ascuțită de o dimensiune dată din puncte arbitrar apropiate de vârfurile cubului (la distanță de ele nu mai mult de ). Discuția pe forum a fost menționată și în acest articol. [optsprezece] $f(d)\geq 2^{d-1}+1$ $d$ $\varepsilon >0$

Scurtă descriere a ideii de probă

Au fost folosite două leme pentru a formaliza demonstrația:

prin deplasarea unuia dintre punctele cubului -dimensional la o distanță arbitrar mică, puteți face toate colțurile care conțin acest punct să fie acute (unghiurile pentru care punctul a fost lateral să dispară din cauza proprietăților cubului și colțurile în care acest punct punctul este central nu devin obtuz din cauza decalajului punctului suplimentar de-a lungul coordonatei --a); $(d-1)$ $d$
pentru orice set finit de puncte, există astfel încât împingerea oricăruia dintre puncte în orice direcție cu o distanță mai mică nu face ca unghiurile ascuțite formate de punctele setului să fie drepte sau obtuze. Această afirmație este dovedită prin luarea minimului tuturor produselor scalare pozitive ale segmentelor unghiulare dintre punctele din această mulțime. Deoarece produsul scalar al unghiului „cel mai rău” va fi în continuare pozitiv, are limite acceptabile de schimbare. $\varepsilon >0$ $\varepsilon$

În continuare, pentru fiecare vârf al cubului, s-au făcut următoarele:

s-a aflat la ce colțuri ascuțite deja existente nu ar fi deteriorate; $\varepsilon$
vârful dat a fost mutat în direcția dorită de un vector de lungime mai mică , astfel încât unghiurile obtuze cu acesta devin ascuțite. $\varepsilon$

La sfârșit, a mai fost adăugat un punct, care era foarte departe de cub de-a lungul coordonatei --a, iar de-a lungul restului a coincis cu centrul cubului. Unghiurile formate de acest punct cu celelalte s-au dovedit, de asemenea, ascuțite. $d$

Note

↑ 1 2 The Michigan Mathematical Journal, volumul 4, numărul 3 (1957), 291-300, Paul Erdős, Some unsolved problems Arhivat la 3 iunie 2018 la Wayback Machine , p. 296, sarcina 19
↑ The American Mathematical Monthly, Vol. 55, nr. 7, aug. — sept. 1948; Paul Erdos, Probleme pentru soluție 4305-4309 Arhivat la 28 august 2018 la Wayback Machine , p. 431, sarcina 4306
↑ 1 2 3 Raigorodsky A.M. Seturi cu unghi ascuțit // Kvant. - 2018. - Emisiune. 3 . — P. 10–13 . (Rusă)
↑ P. Erdos, Z. Furedi. Cel mai mare unghi dintre n puncte din spațiul euclidian d-dimensional // Matematică combinatorie.--Marseille-Luminy, 1981.--P. 275-283; Matematică din Olanda de Nord. Stud.--75.--North-Holland, Amsterdam, 1983 (link inaccesibil) . Preluat la 19 martie 2018. Arhivat din original la 28 august 2018. (nedefinit)
↑ Raygorodsky, 2009 , p. opt.
↑ Aigner, 2006 , p. 93-94.
^ D. Bevan, „Sets of Points Determining Only Acute Angles and Some Related Coloring Problems”, Electron. J. Combin., 13:1 (2006), 24 p. . Preluat la 19 martie 2018. Arhivat din original la 2 mai 2018. (nedefinit)
↑ 1 2 L. V. Buchok, „Acute Danzer-Grunbaum Triangles”, Uspekhi Mat. Nauk, 2009, volumul 64, numărul 3(387), paginile 181-182 . Preluat la 19 martie 2018. Arhivat din original la 3 iunie 2018. (nedefinit)
↑ L. V. Buchok, „Despre două abordări noi pentru obținerea estimărilor în problema Danzer-Grunbaum”, Mat. note, 2010, volumul 87, numărul 4, paginile 519-527" . Preluat la 19 martie 2018. Arhivat din original la 12 mai 2018. (nedefinit)
↑ Raygorodsky, 2009 , p. 21.
^ Eyal Ackerman, Oren Ben-Zwi, „On sets of points that determine only acute angles”, European Journal of Combinatorics, volumul 30, numărul 4, mai 2009, paginile 908-910.
↑ Claudia Bertram-Kretzberg, Hanno Lefmann, „The Algorithmic Aspects of Uncrowded Hypergraphs”, SIAM J. Comput., 29(1), 201–230
↑ Viktor Harangi, „Acute Sets In Euclidean Spaces”, SIAM J. Discrete Math., 25(3), 1212-1229 . Preluat la 19 martie 2018. Arhivat din original la 31 mai 2019. (nedefinit)
↑ arXiv:1705.01171 D. Zaharov, „Seturi acute” . Preluat la 19 martie 2018. Arhivat din original la 28 august 2018. (nedefinit)
↑ Dmitriy Zakharov, „Seturi acute”, „Geometrie discretă și computațională” . Preluat la 19 martie 2018. Arhivat din original la 10 iunie 2018. (nedefinit)
↑ D. Zaharov, „Seturi acute” . Preluat la 19 martie 2018. Arhivat din original la 28 august 2018. (nedefinit)
↑ Soluție Erdős îmbunătățită (?) pentru triunghiuri acute; o copie a acestei pagini este atașată la arXiv : 0906.0290
↑ arXiv:1709.03411, Balázs Gerencsér, Viktor Harangi, „Seturi acute de mărime optimă exponențial” . Preluat la 19 martie 2018. Arhivat din original la 28 august 2018. (nedefinit)

Literatură

Raigorodsky, A. M. Danzer-Grünbaum triunghiuri unghiulare ascuțite . - M. : MTSNMO, 2009. - 31 p. — ISBN 978-5-94057-539-9 . Arhivat pe 8 mai 2018 la Wayback Machine
Aigner M. Ziegler G. Dovezi din carte. Cele mai bune dovezi din vremea lui Euclid până în zilele noastre. — Lumea, 2006.