Konvexné smery

Nech f je reálna funkcia definovaná na množine všetkých dvojíc reálnych čísiel. Smerom nazveme každý vektor (u,v) jednotkovej dĺžky.  Budeme hovoriť, že funkcia f je konvexná v smere (u,v), ak pre každý bod (a,b) je konvexnou funkcia priradzujúca číslu α číslo f(a+αu,b+αv). Je zrejmé, že ak je funkcia f konvexná vo všetkých smeroch, tak je sama konvexná. Konvexnosť v jednom smere však samozrejme nestačí; napríklad nekonvexná funkcia f(x,y)=x²+y³ je konvexná v smere (1,0):

Stačí na zabezpečenie konvexnosti funkcie f konvexnosť v dvoch rôznych smeroch? V troch? ...

Aké je maximálne prirodzené číslo n, pre ktoré existuje nekonvexná reálna funkcia f  dvoch reálnych premenných, ktorá je konvexná v n rôznych smeroch (u₁,v₁), ... ,(u_n,v_n)?

Éter v štvorrozmernom priestore

Minulý týždeň som konečne odovzdal habilitačnú prácu, odoslal som náš najnovší článok a navyše sa skončilo vyučovanie, takže sa opäť s radosťou vraciam k môjmu blogu :) Mali sme tu už viaceré úlohy z geometrie v rovine aj v priestore. Čo by ste ale povedali na úlohu z geometrie v hyperpriestore?

Predstavme si dvojrozmerných obyvateľov povrchu sférickej planéty, ktorá rotuje okolo svojej osi v nehybnom éteri. Títo obyvatelia síce nevedia vnímať tretí rozmer, ale pohyb povrchu svojej planéty voči éteru odmerať vedia. To znamená, že na istej do seba uzavretej priamke (z nášho pohľadu na rovníku planéty) pozorujú najvyššiu rýchlosť pohybu éteru a v dvoch špeciálnych bodoch (z nášho pohľadu na póloch) pozorujú nulovú rýchlosť pohybu éteru.

Moja otázka znie: Ak by náš trojrozmerný vesmír bol povrchom štvorrozmernej gule rotujúcej v nehybnom štvorrozmernom éteri a vedeli by sme odmerať relatívnu rýchlosť tohto éteru voči nám, ako by sme vnímali oblasti najrýchlejšieho pohybu éteru (čiže akýsi švorrozmerný rovník) a ako by sme vnímali oblasti nulovej rýchlosti pohybu éteru (čiže štvorrozmerné póly)?

Ekvidištantné permutácie

  Nech σ=(σ₁,σ₂,...,σ_n) je permutácia čísiel 1,2,...,n. Ak v rovine postupne spojíme body (σ₁,σ₂), (σ₂,σ₃),...,(σ_n-1,σ_n), (σ_n,σ₁) a (σ₁,σ₂), dostaneme euklidovský graf, ktorý permutáciu σ plne charakterizuje. Na nasledovnom obrázku sú znázornené grafy permutácií (1,3,4,2) a (1,2,5,6,3,4).

Všimnite si, že grafy na obrázkoch majú jednu zaujímavú vlastnosť: rovnakú dĺžku všetkých hrán. Otázka znie:

Existuje permutácia čísiel 1,2,...,n, kde n>6, ktorej graf má všetky hrany rovnakej dĺžky?

Pozoruhodná potvora

Matematické funkcie môžu mať veľmi komplikované vlastnosti, a to aj v prípade, keď sú definované jednoduchým predpisom. Včera mi pri riešení jedného príkladu vyskočila takáto pozoruhodná potvora:

 

kde λ je reálna konštanta. Čo všetko sa o nej dá povedať?

Po prvé si uvedomíme, že táto funkcia je dobre definovaná, pretože členy uvedeného nekonečného súčinu sú pre každé x od istého n v intervale (0,1), takže limita, ktorá určuje tento nekonečný súčin, existuje a je konečná. Tiež si hneď všimneme, že pre celé čísla x rôzne od nuly platí f(x)=0. Avšak prakticky akákoľvek ďalšia vlastnosť tejto funkcie je už netriviálna, ako naznačuje aj jej graf pre λ=1.5365:

Ak si niekto z Vás myslí, že je naozaj dobrý v matematickej analýze, môže sa pokúsiť zodpovedať napríklad nasledovné otázky:

• Je hodnota f(x) nenulová pre každé kladné neceločíselné x?
• Aká je množina tých hodnôt λ, pre ktoré je funkcia f ohraničená na celom R?
• Je derivácia tejto funkcie nenulová v každom bode x=2^k, kde k je celé nezáporné číslo?

A ak sa niekomu z Vás podarí zodpovedať na všetky tri tieto otázky do týždňa (samozrejme s rigoróznym dôkazom), tak mu darujem svoj The Princeton Companion to Mathematics, lebo tak bude pravdepodobne v lepších rukách ;-)

Nedosiahnuteľné body

Vo vnútri kruhu máme zakreslený bod A. Na hranici tohto kruhu zvolíme bod B, spojíme ho s bodom A úsečkou a stredom úsečky AB budeme kolmo viesť tetivu t. Uvažujme množinu tých bodov kruhu, ktorými tetiva t určite nemôže prechádzať, nech by sme B zvolili kdekoľvek na hranici kruhu. Čo všetko vieme o tejto množine bodov povedať? 

Poznámka 3.2.: Úlohu už prakticky vyčerpávajúco vyriešil Peťo a to dokonca vo všeobecnej, mnohorozmernej verzii; viď jeho blog.

Fermatova množina

Dnes uplynulo presne 345 rokov od smrti slávneho Fermata a pri tejto príležitosti vyšiel na SME celkom pekný a čitateľsky úspešný článok. Diskusie k podobným článkom sú síce zaujímavé viac z psychologického, než z matematického hľadiska, avšak občas sa v nich vyskytne komentár, nad ktorým sa oplatí zamyslieť. V diskusii k článku o Fermatovi bola pre mňa takou nasledovná otázka čitateľa "toerotik":

"Ak mocnina 2 je Pytagorova veta, a pre [mocninu] 3 vraj mal [Fermat] dôkaz [veľkej Fermatovej vety], ako je to s mocninou napríklad 2,2?"

Teória čísiel nie je mojou silnou stránkou, ale tipol by som si, že táto otázka môže byť netriviálna aj pre špecialistu. Formulujme si preto nasledovnú, podstatne všeobecnejšiu úlohu:

Fermatovou množinou nazvime množinu všetkých reálnych čísiel r, pre ktoré existujú prirodzené čísla x,y,z spĺňajúce x^r+y^r=z^r. Čo všetko vieme povedať o Fermatovej množine?

Jedna z vlastností Fermatovej množiny je tá, že obsahuje čísla 1 a 2, ale neobsahuje žiadne väčšie prirodzené číslo (to je vlastne veľká Fermatova veta). Vieme povedať o nejakých ďalších reálnych číslach, že patria, alebo nepatria do Fermatovej množiny? Vieme povedať, či Fermatova množina obsahuje nekonečne veľa reálnych čísiel? ... Teším sa na Vaše postrehy.

13.1.: V komentároch sa nám podarilo dokázať, že Fermatova množina je hustá v reálnych číslach, čiže pri akomkoľvek reálnom čísle vieme nájsť ľubovoľne blízko nejaké číslo z Fermatovej množiny. Peťo tiež našiel pomerne nedávny článok, z ktorého plynie, že kladné čísla z Fermatovej množiny sú iracionálne, s výnimkou čísiel tvaru 1/n a 2/n, kde n je prirodzené číslo.

Napadlo ma, že by mohlo byť zaujímavé zobraziť grafy funkcií x^r+y^r-z^r reálnej premennej r pre niekoľko "malých" trojíc prirodzených čísiel x,y,z. Tu je výsledok pre všetky trojice prirodzených čisiel x,y,z, ktoré nepresahujú 8:

Červenou bodkou som zaznačil čísla r, v ktorých platí x^r+y^r-z^r=0, čiže čísla z Fermatovej množiny. Keď som zväčšoval počet trojíc x,y,z, červené bodky skutočne čím ďalej, tým hustejšie pokrývali množinu reálnych čísiel...

Planéta X

Planéta X má tvar gule, pričom jej obývateľná zóna tvorí pás okolo rovníka, ktorého šírka je jedna šestina obvodu planéty. (Čiže najkratšia cesta od jedného kraja tohoto pásu po druhý kraj, samozrejme po povrchu planéty, má dĺžku šestinu obvodu tejto planéty.) Koľko percent povrchu tejto planéty je obývateľných? Koľko percent povrchu planéty X by bolo obývateľných, ak by bola nie troj, ale štyridsaťdvarozmerná?

Poznámka: V prípade 42 rozmernej planéty je úloha dosť náročná; už len formulovať ju matematicky presne nie je jednoduché. Ak chcete, môžeme o tom samozrejme podiskutovať a vyriešiť túto úlohu aspoň numericky...

Poznámka 3.12.: No, "dosť náročná" je pre ten 42 rozmerný prípad asi eufemizmus. "Pekelná" je asi lepší prívlastok a to napriek tomu, že riešenie je len dávno známy špeciálny prípad tvrdení z článku, ktoré sme s Vladom Lackom prednedávnom zaslali do časopisu. Ale nič to. Môžeme tu mať aj takúto úlohu. Ak by sa niekto cítil byť veľký frajer...

Braňov problém

Dnes sa u mňa stavil Braňo Novotný (doktorand na MÚ SAV) a z voľnej debaty vyplynul nasledovný rekreačný matematický problém. Poznámka: rekreačný sa vo všeobecnosti nerovná jednoduchý.

Pre 2n bodov v rovine nazveme disjunktným párovaním také rozdelenie týchto bodov do n dvojíc, že úsečky spájajúce jednotlivé páry sa nepretínajú (krajné body považujeme za súčasť úsečky). Z ilustračného obrázku vľavo hore vidíme, že vieme nájsť konfigurácie štyroch bodov v rovine, pre ktoré existuje práve jedno, práve dve a aj práve tri disjunktné párovania. Viac disjunktných párovaní štvorice bodov očividne nemôže existovať. Pre šesť bodov je však situácia komplikovanejšia:

Koľko disjunktných párovaní môže mať šestica bodov v rovine? Formálnejšie: Nájdite množinu M tých čísel m, že existuje šestica bodov v rovine, ktoré je možné disjunktne popárovať práve m spôsobmi.

Keď usporiadame 6 bodov tak, aby ležali na spoločnej priamke, existuje len jedno párovanie, t.j. množina M obsahuje číslo 1. Ak usporiadame 6 bodov do vrcholov pravidelného šesťuholníka, nájdeme 5 rôznych popárovaní, čiže aj číslo 5 patrí do množiny M. (Pozri obrázok vpravo; každá z piatich farieb určuje iné disjunktné párovanie.)

Ktoré ďalšie čísla patria do tejto množiny? (Väčšinu z nich nájdete jednoduchým experimentovaním s obrázkmi.) Viete nájsť horné ohraničenie množiny M, t.j. také číslo, že žiadne m z M nemôže byť väčšie?

27.10.: Nasledujúce obrázky ukazujú, že do množiny M patria čísla 3,4,5,6,7,10.




10.11.: Ako upozornil Braňo v komentároch, existujú aj konfigurácie (zobrazené nižšie) vedúce na 11 a 12 disjunktných párovaní.


Zostáva nám teda ešte nasledovná úloha: Patria do množiny M niektoré z čísiel 2,8,9,13,14,15?

Chaotický trojfarebný trojuholník

Chaotickým k-farebným trojuholníkom veľkosti n nazvime trojuholník poskladaný z 1+2+...+n kameňov k farieb, ktorý neobsahuje žiadnu trojicu kameňov rovnakej farby umiestnených vo vrcholoch trojuholníka so stranami rovnobežnými so základným trojuholníkom.

Formulujeme si jednu teoretickú úlohu a jednu súťaž pre všetkých, ktorí si myslia, že sú programátorskí machri.

Úloha: Dokážte, že existuje najväčší trojfarebný chaotický trojuholník. Inými slovami, ukážte, že existuje prirodzené číslo n také, že trojfarebný chaotický trojuholník veľkosti n už principiálne nie je možné skonštruovať. Môžete použiť Peťove riešenie predchádzajúceho príkladu a Van der Waerdenovu vetu, na ktorú nás upozornil Nanyk.

Súťaž: Pomocou počítača nájdite trojfarebný chaotický trojuholník s veľkosťou aspoň 15, t.j. väčší ako ten, ktorý som našiel ja:


Nie som si úplne istý s tým, že existuje väčší trojfarebný chaotický trojuholník ako ten môj, ale považujem to za veľmi pravdepodobné. Môj trojuholník je totiž výsledkom krátkeho výpočtu jednoduchého programu v pomalom jazyku R. Každopádne ak sa do riešenia tejto úlohy pustíte, pošlite nám najväčší trojfarebný chaotický trojuholník aký nájdete.

28.8.: Mišo našiel chaotický trojfarebný trojuholník veľkosti 16! Tu je:


Kto Miša prekoná má môj obdiv! To už ale bude asi poriadne ťažké...

Me3ce

Predstavme si, že vedľa seba kladieme farebné kamene. Monochromatická ekvidištantná trojica, skrátene me3ca, bude každá taká trojica kameňov rovnakej farby, pre ktorú platí: vzdialenosť prvého a druhého kameňa tejto trojice je rovnaká ako vzdialenosť druhého a tretieho kameňa tejto trojice. Na ilustračnom obrázku som znázornil sériu 10 kameňov dvoch farieb, ktorá obsahuje až 5 me3íc.

Ako sa môžete sami ľahko presvedčiť (napríklad otestovaním všetkých 512 možností na počítači), každá séria pozostávajúca z deväť kameňov dvoch farieb už nutne obsahuje nejakú me3cu. Osem kameňov dvoch farieb však me3cu obsahovať nemusí; všimnite si napríklad postupnosť 0X0XX0X0. Takže s dvomi farbami je otázka existencie bezme3cových sérií jednoduchá. Ukazuje sa však, že pre tri farby je to oveľa ťažšie:

Existuje také prirodzené číslo n, že každá séria n kameňov troch farieb obsahuje aspoň jednu me3cu?

Sám na túto zdanlivo jednoduchú otázku neviem odpovedať; môj polhodinový limit na jej vyriešenie nestačil. Preto sa opäť s dôverou obraciam na Vás. :-) Vzhľadom na to, že tento problém nie je triviálny, môžete do komentárov uvádzať nielen úplné riešenie, ale aj každý potenciálne užitočný postreh.

Poznámka 26.8.: Ako v komentári upozornil Nanyk, tento problém je zhodou okolností známy a veľmi ťažký a odpoveď je kladná pre ľubovoľný počet farieb a ľubovoľnú dĺžku ekvidištantnej série. Pre tri farby je maximálna bezme3cová séria dĺžky 26, napríklad

RRYYRRYBYBBRBRRYRYYBRBBYBY

a je dokázané, že každá séria dĺžky 27 už nejakú me3cu obsahuje.

A ak si chcete privyrobiť 1000 dolárov stačí, keď pre každé k ukážete, že pre niektoré n menšie než 2 na k² platí, že každá séria kameňov dvoch farieb dĺžky n už obsahuje nejakú ekvidištantnú monochromatickú k-ticu. Túto odmenu Vám udelí jeden z najvýznamnejších žijúcich matematikov, Ronald Graham.

Päť miest na sfére

Nasledovné tvrdenie sa mi zdá "intuitívne zrejmé", ale nedarí sa mi ho elegantne dokázať. (Súvisí priamo s jedným problémom na Peťovom blogu). Možno budete vy úspešnejší.

Na jednotkovej sfére S je 5 miest, pričom žiadne tri z nich neležia na spoločnej hlavnej kružnici. Ak spojíme najkratšou cestou každé mesto s každým (samozrejme po povrchu), tak sumárna dĺžka všetkých ciest bude menšia ako 6π.

Poznámka 1: Ľahko sa dá ukázať, že súčet dĺžok všetkých ciest je menší ako 20π/3. Totiž ak si označíme ako d_ij vzdialenosť miest i a j, tak máme:

Nerovnosť plynie z očividnej vlastnosti, že obvod akéhokoľvek trojuholníka na sfére je menší ako 2π.

Poznámka 2: Sériou trikov už viem dokázať dokonca nasledovné zovšeobecnenie pre akýchkoľvek n bodov (nielen 5) a to na akejkoľvek jednotkovej sfére (nielen v trojrozmernom priestore):


kde α je 0 pre párne n a 1 pre nepárne n. Ale stručný dôkaz neviem ani v špeciálnom prípade n=5, takže sa teším na vaše nápady.

Najmenšia vzdialenosť dvoch bodov

V práci môjho bakalára sa vyskytol nasledovný okrajový, ale celkom zaujímavý algoritmický problém:

Vstupom je n vektorov x₁,...,x_n v m-rozmernom Euklidovskom priestore. Cieľom je zistiť Euklidovskú vzdialenosť dvoch najbližších bodov, t.j. vypočítať hodnotu

Otázkou je, či je možné skonštruovať asymptoticky rýchlejší algoritmus, než výpočet vzdialeností medzi všetkými n(n-1)/2 dvojicami rôznych bodov.

Poznámka: Sám neviem na tento problém odpovedať v plnej všeobecnosti (vlastne len pre m=1), takže neviem ani odhadnúť, aký je vo všeobecnosti náročný. Naviac, som si takmer istý, že tomuto jednoducho formulovanému problému sa už ľudia venovali, takže vyriešený už asi je. To nám však nebráni, aby sme sa nad ním zamysleli.

Odmocniny ortogonálnych matíc

Počas písania predchádzajúceho príspevku ma napadol nasledovný problém, tentokrát však z kategórie ťažkých (možno by bol jemne netriviálny aj pre mojich kolegov z algebry; teda aspoň ja ho neviem uspokojivo vyriešiť).

Nech k je prirodzené číslo a nech U je ortogonálna matica typu m krát m. Nájdite predpis pre počet a metódu konštrukcie všetkých ortogonálnych matíc V, pre ktoré platí U=V^k.

Keď som sa nad týmto problémom trochu zamyslel, dospel som k názoru, že práve takáto úloha môže byť vhodná na "kolektívne" riešenie. Urobme teda pedagogický experiment: Keď Vás napadne niečo nové a relevantné, napíšte to do komentáru a spoločne sa budeme snažiť prísť problému na kĺb. Ja sám sa nebudem snažiť tento problém intenzívne riešiť, iba možno občas napíšem nejaký motivačný postreh. Tiež sa nebudem pýtať na riešenie mojich kolegov, ktorí sa veľmi dobre v danej problematike orientujú, pretože vážne hrozí, že by nám úlohu hneď vyriešili a pokazili by nám radosť z objavovania :-) Možno sa nám podarí trochu poodhaliť kreatívny proces matematického uvažovania a pritom sa aj vzdeláme vo veľmi zaujímavej a dôležitej oblasti. Takže na úvod len niekoľko postrehov.

Postreh 1 (algebraický): Ak je k párne, tak je nutnou podmienkou existencie aspoň jednej k-tej odmocniny matice U rovnosť det(U)=1, t.j. U musí byť takzvanou špeciálnou ortogonálnou maticou, resp. maticou rotácie. Dôkaz: Všimnime si, že determinant akejkoľvek ortogonálnej matice V môže byť iba +1 alebo -1: Z definície ortogonality V máme VV^T=I, kde I je jednotková matica a zo základných vlastností determinantu máme

1=det(I)=det(VV^T)=det(V)det(V^T)=det(V)².

Teda det(U)=det(V^k)=det(V)^k=1. QED.

Postreh 2 (geometrický): Ak by sme hľadali riešenia V s determinantom 1, tak vlastne hľadáme takú "rotáciu" V, ktorej k-násobným opakovaným použitím dostaneme zadanú "rotáciu" U. Dá sa ale tušiť, že každá rotácia U sa dá poskladať z k-opakovaných rotácií V, t.j. naša domnienka je, že det(U)=1 je postačujúcou podmienkou na existenciu aspoň jednej k-tej odmocniny matice U.

Postreh 3 (algebraický): Pre niektoré ortogonálne matice U existuje viac ako jedna k-ta odmocnina: Napríklad, ako jednotková matica I, tak aj matica -I je ortogonálna a platí I=I.I, ale aj I=(-I)(-I).

Postreh 4 (4.12.07): Už pre jednotkovú maticu I typu 2x2 existuje nespočítateľne veľa druhých odmocnín! Ako sa dá ľahko skontrolovať, pre každé reálne θ je nasledovná matica ortogonálna druhá odmocnina matice I.



Postreh 5 (5.12.07). Predchádzajúca matica je len špeciálny prípad širokej triedy ortogonálnych druhých odmocnín jednotkovej matice I typu mxm. Môžete si skontrolovať, že ortogonálnou druhou odmocninou matice I je každá matica V tvaru

kde u₁,...,u_m je systém navzájom kolmých vektorov dĺžky 1 a i₁,...,i_m sú 0 alebo 1. To teda znamená, že jednotková matica mxm pre akékoľvek m>=2 má nekonečne veľa ortogonálnych druhých odmocnín.

A ako som na tento predpis pre V prišiel? Ako je to so zdanlivo komplikovanými matematickými vzorcami časté, myšlienky, ktoré k nim vedú, sú založené na veľmi jednoduchých geometrických predstavách, analógiách a mechanických formálnych postupoch. (Niekedy je však ťažké tieto postupy zrozumiteľne popísať. Na druhej strane občas akoby niektorí prehnane ctižiadostiví matematici svoje postupy zámerne tajili aby sa mohli vyťahovať svojimi úžasnými formulkami. Podobne ako David Copperfield neprezradí sériu triviálnych fínt, na ktorých sa zakladá na prvé videnie prekvapivý výsledný efekt :-)

Takže najprv som si uvedomil, že matica z Postrehu 4 zodpovedá preklopeniu roviny okolo nejakej priamky prechádzajúcej počiatkom súradnicovej sústavy. To je ale taká transformácia roviny, ktorá nechá jednotkový smerový vektor u danej priamky nezmenený a druhý jednotkový vektor, kolmý na u, preklopí na opačný. Analogické transformácie sa predsa dajú skonštruovať v ľubovoľnom priestore! Ak by sme mali akýkoľvek systém navzájom kolmých jednotkových vektorov, tak môžeme vytvoriť transformáciu, ktorá niektoré z týchto vektorov preklopí a iné nechá nezmenené. Je úplne zrejmé, že dvojnásobné použitie tejto transformácie opäť vráti všetky vektory do pôvodnej polohy! Je už len záležitosťou základnej techniky lineárnej algebry z prvého ročníka formálne zapísať maticu V, ktorá tomuto preklápaniu zodpovedá.

Čo sa teda týka ortogonálnych druhých odmocnín jednotkových matíc, tento špeciálny prípad pôvodného problému už máme skoro vyriešený, hoci ešte by sme sa mohli spýtať, či existujú aj ortogonálne druhé odmocniny jednotkovej matice, ktoré nie sú typu matice V popísanej vyššie. (Tipol by som si, že nie.) Trochu ťažšie, ale stále nie úplne všeobecné otázky sú nasledovné: Ako skonštruovať triedu všetkých k-tych odmocnín jednotkovej matice pre k>2? Je množina všetkých tretích ortogonálnych odmocnín jednotkovej matice typu 2x2 konečná, alebo je nekonečná? Ako skonštruovať druhú odmocninu z akejkoľvek zadanej ortogonálnej matice (s determinantom 1)?

...

Máte nejaké nápady?