Danzer-Grunbaumův problém

Danzer-Grunbaumův problém je problém kombinatorické geometrie , který vyvolává otázku, jaký je maximální počet bodů, které lze umístit do vícerozměrného prostoru , aby mezi sebou nesvíraly pravé nebo tupé úhly. Je známo, že na rovinu lze umístit maximálně tři takové body a pět takových bodů lze umístit do trojrozměrného prostoru. V roce 2017 bylo prokázáno, že Θ takových bodů se může nacházet v prostoru dimenzí. $d$ $(2^{d})$

Prohlášení o problému

Pro daný , označte maximálním počtem různých bodů v- rozměrném prostoru, takže jakékoli tři body tvoří ostroúhlý trojúhelník , tedy pro jakékoli tři skalární součin . $d$ $f(d)$ $d$ $x, y, z$ $\langle {yx,zx}\rangle >0$

Jak relativně roste ? $f(d)$ $d$

Jinými slovy, problém je najít jednoduchý vzorec, který vyjadřuje s co největší přesností (a také najít algoritmus pro konstrukci množiny bodů). $f(d)$ $d$ $f(d)$

Množiny, jejichž body svírají pouze ostré úhly, se nazývají množiny s ostrými úhly . Všimněte si, že z definice vyplývá, že žádné tři body v ostroúhlé množině nemohou ležet na stejné přímce.

Od března 2018 je známo, že . ${\displaystyle 2^{d-1}+1\leq f(d)\leq 2^{d))$

Související úkoly

Sady bez tupých úhlů

Následující problém nastolil Erdős ještě dříve než klasická formulace Danzer-Grunbaumova problému [1] :

Pro dané , označte maximálním počtem různých bodů v -rozměrném prostoru, z nichž žádné tři nesvírají přísně tupý úhel, tj. pro žádné tři z nich $d$ $g(d)$ $d$ $x, y, z$ $\langle {yx,zx}\rangle \geq 0$

Jak relativně roste ? $g(d)$ $d$

Je známo, že . ${\displaystyle g(d)=2^{d))$

Vrcholy krychle

V první skutečně průlomové práci na toto téma Erdős a Furedi zkonstruovali velkou množinu splňující dané podmínky z vrcholů prostorové krychle . Proto se v dalších pracích zlepšujících jejich výsledek někdy samostatně uvažovalo o následujícím problému: $d$ ${\displaystyle {\left\lbrace {0,1}\right\rbrace }^{d))$

Pro daný jeden označujeme maximálním počtem různých vrcholů -rozměrné krychle , z nichž žádné tři nesvírají pravý ani tupý úhel, tedy pro žádné tři , $d$ $f_{\square }(d)$ $d$ $\left\lbrace {0,1}\right\rbrace ^{d}$ $x, y, z$ $\langle {yx,zx}\rangle >0$

Jak relativně roste ? $f_{\square }(d)$ $d$

Je zřejmé, že . $f_{\square }(d)\leq f(d)$

Historie studia

První zmínky (Erdős, 1948, 1957)

Historie problému začíná v roce 1948, kdy Pal Erdős publikoval následující speciální případ budoucího Danzer-Grünbaumova problému [2] v sekci "Další problémy k řešení " The American Mathematical Monthly :

Nechť je dáno osm bodů v prostoru . Dokažte, že vždy je možné najít tři z nich, které netvoří ostrý trojúhelník. ${\displaystyle {\mathbb {R} }^{3))$

To znamená, že problém se zeptal, zda je to pravda $f(3)<8$

V roce 1957, v Michigan Mathematical Journal , v článku s mnoha dohady, Erdős publikoval obecný dohad, ale ohledně tupých množin.

Dovolit být soubor bodů v prostoru dimenze . Je pravda, že mezi nimi jsou nutně tři body svírající tupý úhel? $S$ $2^{d}+1$ $k$

To znamená, že hypotéza tvrdila, že . ${\displaystyle g(d)\leq 2^{d))$

Článek říkal, že Nicolas Kuiper a Boerdijk našli důkaz , ale jejich důkaz ještě nebyl zveřejněn. $d=3$

Vedle hypotézy byla následující otázka:

Je pravda, že v trojrozměrném prostoru existuje množina šesti (sedmi) bodů tak, že kterékoli tři z nich svírají ostrý úhel?

Nebo, jinými slovy, je pravda, že nebo . [jeden] $f(3)\geq 6$ $f(3)\geq 7$

První hypotéza (Danzer a Grünbaum, 1962)

První obecnou konstrukci pro řešení tohoto problému postavili Ludwig Danzer a Branko Grünbaum v článku z roku 1962. Postavili bod v -rozměrném prostoru , jehož matice souřadnic vypadala takto (řádky jsou různé body, sloupce jsou různé souřadnice): $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 }}

kde jsou párově odlišná čísla, všechna menší. ${\displaystyle \delta _{1},\tečky ,\delta _{d-1))$

Jednoduchý kombinatorický výčet různých typů úhlů, které vznikají, umožňuje ukázat, že žádné tři z těchto bodů netvoří pravé nebo tupé úhly. Z toho vyplývá, že $f(d)\geq 2d-1$

V téže práci autoři předpokládali, že není možné sestrojit větší počet bodů splňujících tuto podmínku, tedy že [3] . $f(d)=2d-1$

Také v této práci byla prokázána horní hranice , kterou dříve navrhl Erdős. ${\displaystyle f(d)\leq g(d)\leq 2^{d))$

Aplikace pravděpodobnostní metody (Erdős, Furedi, 1983)

V roce 1983 Paul Erdős a Zoltan Furedy vyvrátili Danzer-Grünbaumovu hypotézu pomocí pravděpodobnostní metody a ukázali, že

f(d)\geq f_{\square }(d)\geq \left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3} }}\vpravo)}^{d}}\vpravo\rpodlaží

To umožnilo sestavit protipříklady k Danzer-Grünbaumově domněnce pro . [4] [5] $d\geq 35$

Vzhledem ke zvláštnostem pravděpodobnostní metody byl však jejich důkaz neefektivní a neumožňoval sestrojit tuto množinu explicitně (kromě přímého výčtu) [3] .

Hlavní myšlenkou Erdőse a Furedyho bylo vybrat nějakou sadu bodů, které (s kladnou pravděpodobností) budou mít velmi málo pravých a tupých úhlů, a pak jednoduše odstranit jeden bod z každého z těchto úhlů, čímž je všechny eliminovat.

Stručný popis nápadu důkazu

Důkazem Erdőse a Furediho bylo náhodně a nezávisle vybrat body z jednotkové krychle , kde a dokázat, že při takovém výběru je pravděpodobnost, že mezi nimi budou pouze tupé nebo zdegenerované trojúhelníky, pozitivní. $2n$ $\left\lbrace {0,1}\right\rbrace ^{d}$ $n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\ patro$ $n$

Náhodným výběrem bodu se zde rozumí jeho generování podle Bernoulliho schématu s pravděpodobností vygenerování jedničky nebo nuly na té či oné souřadnici bodu bez ohledu na ostatní souřadnice. $p={\frac {1}{2))$

K prokázání odhadu počtu tupých trojúhelníků byla použita vlastnost linearity matematického očekávání. Pravděpodobnost, že určitá trojice bodů svírá pravý úhel, je rovná - to lze snadno dokázat tím, že zvlášť uvážíme příspěvek každé souřadnice ke skalárnímu součinu. Vynásobením této pravděpodobnosti počtem takových trojic dostaneme hodnotu matematického očekávání, a to již dá podle Markovovy nerovnosti kladnou pravděpodobnost, že ji náhodná veličina nepřekročí. $\left({\frac {3}{4}}\right)^{d}$

Erdős-Füredi neustálé zlepšování

Zlepšení beze změny metody

I bez změny Erdősovy metody v její podstatě lze získat lepší odhad jednoduše volbou jiného čísla jako parametru, který určuje, kolik náhodných bodů zvolit.

Aigner a Ziegler v roce 2003, popisující Erdősův teorém ve své recenzní knize Důkazy z knihy , tento parametr opravili a získali to . [6] Jde o to nejlepší, co lze tímto způsobem získat. $f_{\square }(d)\geq 2\left\lpatro {{\frac {\sqrt {6}}{9}}{\left({\frac {2}{\sqrt {3}} }\right)}^{d}}\right\rpatro$

Důkaz

Erdősova metoda pro počet vybraných bodů zjistila, že alespoň jednou mezi nimi nejsou žádné ostřejší úhly. $k$ $3{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}\leq {\frac {k^{3}}{2 }}{\left({\frac {3}{4}}\right)}^{d}$

To zaručuje existenci množiny bodů bez pravých nebo tupých úhlů. $h(k)=k-{\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}$

Pokud vezmeme derivaci a optimalizujeme tuto funkci s ohledem na , dostaneme $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_{best}={\sqrt {\frac {2}{3}}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

h(k_{best})={\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)

V roce 2006 D. Bevan zlepšil odhad na . [7] $f(d)\geq 2\left\lpatro {{\frac {1}{3}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d +1}}\pravé\rpatro$

Body v jeho konstrukci však nebyly vrcholy jednotkové krychle, takže odhad pro nezlepšil. $f_{\square }(d)$

Stručný popis nápadu důkazu

V Bevanově konstrukci byl ke každému zvolenému náhodnému bodu přidán velmi krátký náhodný vektor (každý má svůj vlastní), spojitě a rovnoměrně rozmístěný v -rozměrné krychli pro některé dostatečně malé . $d$ ${\displaystyle [-\varepsilon ;\varepsilon ]^{d))$ $\varepsilon$

Bevan zavedl několik lemmat ukazujících, že některé polynomy v rovnoměrně a symetricky rozdělených náhodných proměnných (považovaných za novou náhodnou proměnnou) mají pravděpodobnost, že budou kladné ne menší než . Tato lemmata umožnila ukázat, že ve více než polovině případů posun o další vektory nezostří úhel mezi body umístěnými před ním v pravém úhlu (protože změna skalárního součinu, která je kvantitativní indikátor ostrosti úhlu, je vyjádřen přesně pomocí polynomů v souřadnicích přídavných vektorů ). ${\frac {1}{2))$

To vše umožnilo posílit odhad pro matematické očekávání počtu neakutních úhlů a ukázat, že mezi náhodně vybranými body mohou být pouze neakutní úhly. $k$ ${\frac {3}{2}}{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}$

Kromě toho Bevan získal řadu výsledků pro malé rozměry , v důsledku čehož byla Danzer-Grünbaumova domněnka vyvrácena v . [osm] $d$ $d\geq 7$

Buchok (2009)

V roce 2009 Larisa Buchok, aniž by změnila metody Erdőse, Furediho a Bevana pro generování bodů, přesněji vypočítala ztráty z mazání bodů zapojených do neakutních rohů. Ukázalo se, že to umožňuje získat následující odhady [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

Stručný popis nápadu důkazu

Za prvé, Buchok, s ohledem na libovolně generovanou množinu bodů, z ní vyčlenil ty tupoúhlé trojúhelníkové, které se neprotínají (bodově) s žádnými jinými. Takových trojúhelníků je evidentně málo – minimálně třikrát méně než všech bodů.

Zbytek trojúhelníků díky jejich "prokládání" umožňuje odstranit velké množství trojúhelníků odstraněním pouze jednoho bodu. Pokud v tomto procesu vzniknou nové trojúhelníky, které se neprotínají s ostatními (každý z nich musí být odstraněn samostatným bodem), pak se ukáže, že jejich počet je kompenzován ziskem získaným odstraněním vrcholu obsaženého v několika trojúhelníkech. , jehož odstraněním se ve skutečnosti stanou nepřekrývajícími se.

To vše umožňuje, s vědomím, že mezi body jsou neostré úhly, sestrojit ostroúhlou sadu bodů, na rozdíl od triviálního odhadu, kdy jsou vybírány pouze body. $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)

V roce 2010 Buchok zveřejnil dvě metody pro zlepšení předchozích nerovností k výsledkům najednou:

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

Stručný popis nápadu důkazu

V této práci Buchok kombinuje myšlenku výběru bodů z pevné množiny a myšlenku přidání malé odchylky bodů od vrcholů krychle.

Stejně jako v Erdősově a Furedyho metodě, Buchok vybírá body náhodně a každou souřadnici nezávisle, podle Bernoulliho schématu, ale ne s pravděpodobnostmi.

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

ale s velkým množstvím možností, s pravděpodobnostmi

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

kde jsou dostatečně malá čísla (samostatné číslo pro každou souřadnici), která splňují podmínky ${\displaystyle \varepsilon _{1},\tečky ,\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

To vše umožňuje prostřednictvím výčtu 64 možností změny příspěvku té či oné souřadnice horninového produktu snížit pravděpodobnost, že některé tři body svírají neostrý úhel, na rozdíl od standardního v Erdős -Füredyho metodu a v souladu s tím snížit matematické očekávání počtu neakutních úhlů. ${\frac {2}{5}}{\left({\frac {3}{4}}\right)}^{d}+{\frac {3}{5}}{\left( {\frac {7}{16}}\right)}^{d}$ ${\left({\frac {3}{4}}\right)}^{d}$

Poté lze použít techniku Butchok k odstranění tupých rohů z její předchozí práce, čímž je důkaz dokončen.

f(d)\geq {\frac {2}{3}}\left\lpatro {{\sqrt {2}}{\left({\frac {2}{\sqrt {3}}}\ vpravo)}^{d}}\pravé\rpodlaží

Stručný popis nápadu důkazu

Na rozdíl od první metody ze stejné práce, která spočívala ve změně samotného algoritmu pro výběr náhodných bodů, druhá metoda nabízela obvyklou volbu podle Erdős-Füredyho schématu s pravděpodobnostmi pro každou souřadnici každého bodu. Hlavním ziskem v tomto případě bylo „chytré“ odečítání bodů v nejlepší kombinaci (s nejmenším počtem tupých úhlů). $P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2))$

Stejně jako v první metodě byly body posunuty o vektor malé pevné délky (stačí vzít ) od krychle, ale pouze po jedné souřadnici a přísně v závislosti na tom, zda pro daný středový bod existují další tupé úhly. tupý úhel, pro nějž je bočním bodem (tj. stejně jako v prvním díle Buchoka byly pravoúhlé trojúhelníky rozděleny na protínající se a neprotínající se, ale analyzovány trochu jinak než v prvním díle). $\varepsilon >0$ $\varepsilon <{\frac {1}{4}}$

Přesněji řečeno, všechny body nejlepší kombinace byly rozděleny do čtyř tříd podle spokojenosti vlastností:

$Q_1$ : všechny úhly s vrcholem v daném bodě jsou ostré;
$Q_{2}$ : bod je vrcholem alespoň jednoho pravého úhlu a všechny ostré úhly s vrcholem v tomto bodě patří do ostrých trojúhelníků;
$Q_{3}$ : bod je vrchol alespoň jednoho pravého úhlu a právě jednoho ostrého úhlu pravoúhlého trojúhelníku;
$Q_{4}$ : bod je vrcholem alespoň jednoho pravého úhlu a alespoň dvou ostrých úhlů pravoúhlých trojúhelníků.

Body splňující vlastnost byly jednoduše odstraněny ze sady (protože jich nemůže být mnoho) a souřadnice zbytku byly změněny, jak je popsáno výše. $Q_{4}$

Stejně jako v první metodě úplné prohledání tabulky 64 možností pro příspěvek jedné nebo druhé souřadnice ke skalárnímu součinu umožnilo prokázat, že po těchto změnách souřadnic nebudou existovat žádné pravoúhlé nebo tupoúhlé trojúhelníky v sadě.

Důkaz druhého z výsledků byl získán nejpozději v roce 2009, neboť je zmíněn v průzkumu na toto téma. [9] [10]

Zlepšení pravděpodobnostního schématu pomocí hypergrafů (Ackerman a Ben-Zvi, 2008/2009)

Zatímco jiní matematici pracovali na základních vylepšeních Erdősovy metody, Eyjal Ackerman a Oren Ben-Zvi nezávisle publikovali v roce 2009 důkaz získaný v roce 2008 o existenci takové konstanty , která $c>0$

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

Jednalo se o první asymptotické zlepšení odhadu od Erdős-Füredyho práce.

Důkaz zabíral pouze jednu stránku a spočíval v aplikaci jednoho dříve ověřeného algoritmického lemmatu o velikosti nezávislé množiny v hypergrafu za speciálních podmínek na Erdős-Füredyho konstrukci. [jedenáct]

Stručný popis nápadu důkazu

Ackerman a Zvi použili speciální případ lemmatu z průzkumu Bertrama-Kretzberga a Lefmanna o algoritmických aspektech hledání nezávislých množin v hypergrafech. [12] V konkrétním posuzovaném případě bylo uvedeno toto:

Nechť jsou dány konstanty . $c,\varepsilon >0$

Dovolit být hypergraf, jehož všechny hrany se skládají ze tří vrcholů, který obsahuje vrcholy a jehož průměrný stupeň vrcholů nepřesahuje , Kde pro . $H$ $n$ $t^{2}$ $t\to\infty$ $n\to\infty$

Nechť také počet dvojic typových hran (jakýchsi „cyklů“ ve smyslu hypergrafu) nepřesáhne . $\left({\left\lbrace {a,b,c}\right\rbrace ,\left\lbrace {a,b,d}\right\rbrace }\right)$ ${\displaystyle cnt^{3-\varepsilon ))$

Pak, v polynomiálním čase, můžeme najít v nezávislé množině velikostí vrcholů $n$ $H$ $\Omega \left({\frac {n{\sqrt {\log t}}}{t}}\right)$

Autoři použili konstrukci Erdős-Fyuredi, aniž by jakkoli změnili algoritmus výběru bodů. Ale spolu s průměrem počtu neakutních trojúhelníků vypočítali také průměr počtu cyklů (ve výše uvedeném smyslu) v hypergrafu, jehož hrany odpovídají trojicím bodů tvořících pravé nebo tupé úhly (to se počítá díky linearitě průměru, stejně jako počet tupých úhlů, ale při zohlednění nikoli trojic bodů, ale čtyř).

Nezávislá množina bodů v takovém hypergrafu bude právě ta množina, která neobsahuje tupé trojúhelníky a při volbě parametrů má velikost $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)$

Improving the Degree Foundation (Harangi, 2011)

V roce 2011 Harangi dokázal exponenciální odhad s lepším exponentním základem, konkrétně dokázal existenci konstanty takové, že $c>0$

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

Jeho důkazem byla i úprava konstrukce Erdős-Füredi. [13]

První betonový design (Zacharov, 2017)

30. dubna 2017 Dmitrij Zacharov, studující v 10. třídě a student Andreje Raigorodského , publikoval předtisk explicitní (nikoli pravděpodobnostní) konstrukce sestávající z bodů, které tvoří pouze ostré úhly. $2^{\left\lceil {\frac {d}{2}}\right\rceil }$

Zacharovův návrh nebyl vyvinutím Erdősovy metody, ale použil novou, jednoduchou myšlenku popsanou na jedné stránce. [14] [3]

V listopadu téhož roku byl důkaz zveřejněn v Discrete & Computational Geometry . [patnáct]

Stručný popis nápadu důkazu

Zacharovova metoda spočívala v sestavení sady bodů opakovaně . V tomto případě byl přechod proveden ze sady pro kótovací prostor do sady pro kótovací prostor $d$ $d+2$

Za základ byl vzat princip konstrukce krychle (nebo rovnoběžnostěnu), kdy se všechny body „zkopírují“ a kopie se přenesou do určité vzdálenosti podél nové dimenze, ortogonální ke všem segmentům mezi body v předchozí konstrukci (a obecně na všechny rovné čáry v předchozím prostoru). Tím by se zdvojnásobil počet bodů a změnily by se dostupné úhly (u úhlů, jejichž body patří do různých kopií) jen nepatrně (skalární součin se nezmění o více než hodnotu úměrnou druhé mocnině posunu v nové dimenzi). Při takové konstrukci však vznikají pravé úhly tvaru , kde a jsou různými kopiemi jednoho bodu. $\angle {v_{2}v_{1}w_{1))$ $v_{1}$ $v_{2}$

Aby se zbavil pravých úhlů, provedl Zacharov posun podél dvou nových dimenzí najednou, o vektor o stejné délce, ale v různých směrech, a obě kopie každého bodu se pohybovaly podél nových dimenzí, na rozdíl od stavby krychle. , kdy všechny body z předchozí konstrukce zůstanou v hranicích jejího bývalého prostoru. To vše umožnilo mírně „zkosit“ vznikající „vertikální“ (protažené podél zaváděné nové dimenze) segmenty mezi body, aby se zbavily úhlů, které svírají se segmenty, které leží výhradně v předchozím prostoru menšího dimenze.

Přesněji řečeno, má-li Zakharov zasazeno bez pravých a tupých úhlů, vybere Zacharov pro každý bod dvourozměrný vektor dostatečně malé (a co je důležité, stejné pro všechny) délky, a to takovým způsobem, aby platil pro jakoukoli jinou délku. . Pak, pro dostatečně malou délku vektorů , je možné dokázat, že nastavené body $S$ ${\displaystyle {\mathbb {R} }^{d))$ $x\in S$ $\phi (x)=\left({\alpha (x),\beta (x)}\right)$ $\phi (x)\not =\pm \phi (y)$ $x,y\in S$ $\phi(x)$

S'=\left\lbrace {(x_{1},\tečky ,x_{d},\alpha (x),\beta (x)):x\in S}\right\rbrace \cup \ vlevo\lbrace {(x_{1},\tečky ,x_{d},-\alfa (x),-\beta (x)):x\v S}\vpravo\rbrace

také nesvírají pravé ani tupé úhly (a to, že se tyto množiny neprotínají, je zřejmé z konstrukce ). $\phi(x)$

To dokazuje opakování a indukcí i celý teorém. $f(d+2)\geq 2f(d)$

Odhad přes Fibonacciho čísla (Zakharov, 2017)

V červenci 2017 Zacharov zveřejnil předtisk dokumentu, který to dokazuje

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

kde je -té Fibonacciho číslo a je absolutní konstanta. [16] Druhá nerovnost vyplývá z Binetova vzorce . $F_{n}$ $n$ $c>0$

Stručný popis nápadu důkazu

Myšlenka byla stejná jako v prvním díle - kopírování bodů s následným posunem o dostatečně malý dvourozměrný vektor v nových dimenzích.

Nyní jsme však uvažovali o kombinaci bodů v- dimenzionální množině, mezi nimiž body (maximální možný počet) leží v nějaké jediné nadrovině dimenze . Operace s kopírováním a posouváním byla tedy provedena pouze pro ně a nové rozměry byly zavedeny ortogonálně , takže v důsledku operace se celkový počet rozměrů zvýšil pouze o jeden a pro počet bodů byl použit rekurzivní výraz bylo získáno $d$ $f(d-1)$ ${\displaystyle H\subset {\mathbb {R} }^{d))$ $d-1$ $H$

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

Odhad maximálního pořadí (Gerencher a Harangi 2017)

Vzhled Zacharovova díla vyvolal pokusy najít lepší protipříklady pro nízké dimenze. Předpokládalo se, že poté byly zkonstruovány příklady množin s ostrým úhlem, což dokazuje $f(d)\geq 2^{d-1}+1$

f(4)\geq 9

f(5)\geq 17

Myšlenka použitá při konstrukci těchto příkladů byla mírné kolísání bodů -rozměrné krychle v , včetně podél poslední souřadnice, která nesouvisí s -rozměrným podprostorem této krychle. [17] $(d-1)$ ${\displaystyle {\mathbb {R} }^{d))$ $(d-1)$

Tuto myšlenku lze snadno zobecnit do vyšších dimenzí, což Gerincher a Harangi udělali v září 2017 a publikovali článek dokazující výsledek pro všechny . Podobně jako u grizzlyho řešení nám jejich výsledek umožňuje sestavit ostroúhlou množinu dané velikosti z bodů libovolně blízkých vrcholům krychle (vzdálených od nich ne více než ). V tomto článku byla zmíněna i diskuze na fóru. [osmnáct] $f(d)\geq 2^{d-1}+1$ $d$ $\varepsilon >0$

Stručný popis nápadu důkazu

K formalizaci důkazu byla použita dvě lemmata:

posunutím jednoho z bodů -rozměrné krychle na libovolně malou vzdálenost můžete všechny rohy obsahující tento bod zostřit (úhly, pro které byl bod laterální, zmizí kvůli vlastnostem krychle a rohy, kde to bod je střed, nestanou se tupými kvůli dodatečnému posunutí bodu podél -té souřadnice); $(d-1)$ $d$
pro jakoukoli konečnou množinu bodů existuje taková, že posunutí některého z bodů v libovolném směru o vzdálenost menší nezpůsobí, že ostré úhly tvořené body množiny budou pravé nebo tupé. Toto tvrzení je dokázáno tím, že se z této množiny vezme minimum všech kladných skalárních součinů úhlových segmentů mezi body. Protože skalární součin „nejhoršího“ úhlu bude stále kladný, má přijatelné meze změny. $\varepsilon >0$ $\varepsilon$

Dále bylo pro každý vrchol krychle provedeno následující:

bylo zjištěno, v jakých již existujících ostrých rozích by nedošlo k poškození; $\varepsilon$
daný vrchol byl posunut v požadovaném směru o vektor menší délky , takže tupé úhly se s ním staly ostré. $\varepsilon$

Na konci byl přidán ještě jeden bod, který byl od krychle po -té souřadnici velmi vzdálen a podél zbytku se shodoval se středem krychle. Také úhly, které tento bod svíral s ostatními, se ukázaly být ostré. $d$

Poznámky

↑ 1 2 The Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291-300, Paul Erdős, Some unsolved problems Archived 3 June 2018 at Wayback Machine , str. 296, úkol 19
↑ The American Mathematical Monthly, Vol. 55, č.p. 7, srpen — září 1948; Paul Erdos, Problémy pro řešení 4305-4309 Archivováno 28. srpna 2018 na Wayback Machine , s. 431, úkol 4306
↑ 1 2 3 Raigorodsky A.M. Sady s ostrým úhlem // Kvant. - 2018. - Vydání. 3 . — S. 10–13 . (Ruština)
↑ P. Erdos, Z. Furedi. Největší úhel mezi n body v d-rozměrném euklidovském prostoru // Kombinatorická matematika.--Marseille-Luminy, 1981.--P. 275-283; Severní Holandsko matematika. Stud.--75.--North-Holland, Amsterdam, 1983 (nedostupný odkaz) . Získáno 19. března 2018. Archivováno z originálu 28. srpna 2018. (neurčitý)
↑ Raygorodsky, 2009 , s. osm.
↑ Aigner, 2006 , str. 93-94.
↑ D. Bevan, "Soubory bodů určujících pouze akutní úhly a některé související problémy s barvením", Electron. J. Combin., 13:1 (2006), 24 s. . Získáno 19. března 2018. Archivováno z originálu 2. května 2018. (neurčitý)
↑ 1 2 L. V. Buchok, „Acute Danzer-Grunbaum Triangles“, Uspekhi Mat. Nauk, 2009, svazek 64, vydání 3(387), strany 181-182 . Získáno 19. března 2018. Archivováno z originálu 3. června 2018. (neurčitý)
↑ L. V. Buchok, „O dvou nových přístupech k získávání odhadů v problému Danzer-Grunbaum,“ Mat. poznámky, 2010, ročník 87, číslo 4, strany 519-527" . Získáno 19. března 2018. Archivováno z originálu 12. května 2018. (neurčitý)
↑ Raygorodsky, 2009 , s. 21.
↑ Eyal Ackerman, Oren Ben-Zwi, „O sadách bodů, které určují pouze ostré úhly“, European Journal of Combinatorics, svazek 30, číslo 4, květen 2009, strany 908-910
↑ Claudia Bertram-Kretzberg, Hanno Lefmann, „Algorithmic Aspects of Uncrowded Hypergraphs“, SIAM J. Compput., 29(1), 201–230
↑ Viktor Harangi, "Acute Sets In Euclidean Spaces", SIAM J. Discrete Math., 25(3), 1212-1229 . Získáno 19. března 2018. Archivováno z originálu 31. května 2019. (neurčitý)
↑ arXiv:1705.01171 D. Zakharov, "Akutní sady" . Získáno 19. března 2018. Archivováno z originálu 28. srpna 2018. (neurčitý)
↑ Dmitriy Zakharov, "Acute Sets", "Discrete & Computational Geometry" . Získáno 19. března 2018. Archivováno z originálu 10. června 2018. (neurčitý)
↑ D. Zakharov, "Akutní sady" . Získáno 19. března 2018. Archivováno z originálu 28. srpna 2018. (neurčitý)
↑ Vylepšené (?) Erdősovo řešení pro ostré trojúhelníky; kopie této stránky je připojena k arXiv : 0906.0290
↑ arXiv:1709.03411, Balázs Gerencsér, Viktor Harangi, "Akutní soubory exponenciálně optimální velikosti" . Získáno 19. března 2018. Archivováno z originálu 28. srpna 2018. (neurčitý)

Literatura

Raigorodsky, A. M. Danzer-Grünbaum ostroúhlé trojúhelníky . - M. : MTSNMO, 2009. - 31 s. — ISBN 978-5-94057-539-9 . Archivováno 8. května 2018 na Wayback Machine
Aigner M. Ziegler G. Důkazy z knihy. Nejlepší důkaz od dob Euklida až po současnost. — Mir, 2006.