Řešitelský článek: Tropická geometrie

Dominika Jochcová (10,0 b), Václav Rozhoň (10,0 b), Zuzana Svobodová (10,0 b), Lenka Vincenová (10,0 b)

Vyšlo v čísle 21.6.

Úvodem

Tento článek vznikl jako volné pokračování společného projektu -- konfery, vznikajícího v průběhu podzimního soustředění korespondenčního semináře M&M pod vedením Josefa Svobody. Tropická geometrie nás natolik zaujala, že jsme se rozhodli touto exotickou strukturou i nadále zabývat a naše příspěvky společně sepsali do tohoto článku.

Tropické operace

Po stručném úvodu se konečně můžeme pustit do samotného formalismu. Nejprve si zavedeme dvě operace – tropické sčítání a tropické násobení, přičemž operaci sčítání definujeme jako
$$``x+y"{} = \mathrm{max}(x,y),$$
tropický zápis značíme do uvozovek. Tropické sčítání je tedy operace ekvivalentní k funkci maximum. 

Tropické násobení definujeme jako 
$$``x\cdot y"{} = x+y,$$
jedná se tedy o ekvivalent sčítání. 

Další operace můžeme definovat podobně jako ty klasické. Tropické dělení bude inverzní operace k tropickému násobení, a proto se bude jednat o klasické odčítání. Mocnění je vlastně opakované násobení, takže tropické mocnění je opakované tropické násobení, tedy se jedná o opakované sčítání, což je (netropické) násobení. V našem textu se obejdeme bez dělení, ale mocnění budeme používat. Zanedlouho si ukážeme, že tropické odčítání definovat nemůžeme. Nyní uveďme pro názornost několik příkladů: $``1+1"{}=1$, $``1+(-1)"{}=1$, $``0\cdot 42"{} = 42$, $``(21+12)^2"{}=42$, $``5+8+13"{}=13$ a $``5\cdot ((-6)+10)"{}=15$. 

Množinu tropických čísel $\mathbb{T}$, na které naše tropické operace budeme používat, definujeme jako
$\mathbb{T}=\mathbb{R}\cup\{-\infty\}$, jedná se tedy o reálná čísla spolu s minus nekonečnem (pro všechna $a\in
\mathbb{T}$ platí $``a+(-\infty)=-\infty"$ a $``a\cdot (-\infty)=-\infty"$). Ukážeme si, že množina tropických čísel
splňuje skoro všechny axiomy tělesa\footnote{Tato struktura je tzv. semitělesem. }$^,$\footnote{Jestliže nevíte, co je algebraické těleso, vězte, že se bez této znalostí v dalších částech obejdeme. }. Projděme si tedy postupně tyto axiomy (u axiomů, kde je napsána pouze odpovídající rovnost dvou výrazů, stačí tyto výrazy převést z tropické algebry do té klasické a ověřit si, že rovnost vskutku platí). 

  • Komutativita sčítání: $``a+b"{}=``b+a"$.
  • Asociativita sčítání: $``(a+b)+c"{}=``a+(b+c)"$.
  • Existence nulového prvku pro operaci sčítání: tímto nulovým prvkem je přidané $-\infty$, neboť pro $\forall a \in \mathbb{T}$ platí $``a+(-\infty)"{}=a$. 
  • Existence inverzního prvku pro sčítání:  tento axiom tělesa množina tropických čísel nesplňuje. Pokud by tomu tak bylo, pro každé $a \in \mathbb{T}$ by existovalo takové $b$, že $``a+b"{}=-\infty$, ale vidíme, že pokud $a\neq -\infty$, tak takové $b$ rozhodně neexistuje. Právě proto nemůžeme definovat operaci odčítání. 
  • Komutativita násobení: $``a\cdot b"{} = ``b\cdot a"$.
  • Asociativita násobení: $``(a\cdot b) \cdot c"{} = ``a \cdot (b \cdot c)"$.
  • Existence jednotkového prvku pro operaci násobení:  pro množinu tropických čísel toto splňuje 0, tedy pro $\forall a \in \mathbb{T}$ platí $``a \cdot 0"{}=a+0=a$. 
  • Existence inverzního prvku pro násobení: pro každé $a \in \mathbb{R}$ můžeme definovat $``a^{-1}"{}=(-a)$, takže $``a \cdot a^{-1} "{}=a+(-a)=0$. Pro $-\infty$ však inverzní prvek nemáme. 
  • Distributivita: $``a \cdot (b + c)"{} = ``(a \cdot b ) +  (a \cdot c)"$.
  • Netrivialita:  nulový a jednotkový prvek jsou různé, což pro množinu tropických čísel platí, jelikož $0 \neq -\infty$. 

Polynomy

Polynom (mnohočlen) je výraz ve tvaru:

$$P(x) = \sum_{i=0}^n a_i\cdot x^i = a_n x^n + a_{n-1}x^{n-1} + \dots + a_0,$$

kde $a_n$ není 0 a pro číslo $n$ používáme označení stupeň polynomu. Obdobně můžeme definovat tropické polynomy podle pravidel tropického sčítání a násobení. Příkladem takového tropického polynomu je třeba $P(x) = ``3x^3+1x+(-5)"{} = ``3 \cdot x \cdot x \cdot x + 1 \cdot x + (-5) "{}= \mathrm{max}(3x+3,x+1,-5)$. 

Pojďme nyní sestrojit graf tohoto polynomu. Všimněme si, že pracujeme s maximem z několika lineárních funkcí. Můžeme je tedy vynést do grafu jako na obrázku \ref{fig:graf}. Výsledný graf pak vznikne jako maximum z oněch tří funkcí.

U normálních polynomů můžeme zavést kořen jako takové $x_0$, že $P(x_0)=0$. Pro nás bude užitečný fakt, že jestliže rozšíříme obor svého zájmu na komplexní čísla, má každý (klasický) polynom stupně $n$ právě $n$ kořenů (některé ale můžeme počítat vícekrát, tomu se říká násobnosti) a jestliže známe všechny kořeny daného polynomu, můžeme jej rozložit na součin výrazů ve tvaru $(x-x_0)$. Tak třeba polynom $P(x)=2x^2-5x-3$ má kořeny $-\frac{1}{2}$ a 3; přitom platí $2x^2-5x-3=2(x+\frac{1}{2})(x-3)$. Budou ale mít kořeny svoji tropickou analogii?

Kdybychom kořeny tropických mnohočlenů definovali jako průsečíky polynomu s osou $x$ (tedy $P(x_0)=0$), výsledek by
nebyl příliš zajímavý -- pokud by absolutní člen polynomu nebyl 0, tak by měl každý polynom maximálně jeden kořen. Ukazuje se, že lepší je kořen tropického polynomu definovat jako takové číslo $x_0$, ve kterém se láme graf polynomu. Jinými slovy pro něj platí $a_i+ix_0=a_j+jx_0$, kde $i$ a $j$ jsou sklony dvou po sobě jdoucích úseků v grafu polynomu. Rozdíl $|i-j|$ pro taková $i$ a $j$ pak bude násobností kořene $x_0$. 

\begin{figure}[htbp]
\centering
\begin{minipage}{.47\textwidth}
    \centering
    \includegraphics[width=\textwidth]{images/r1.png}
    \caption{Graf tropického polynomu $``3x^3+1x+(-5)"$.}
    \label{fig:graf}
\end{minipage}
\hspace{1em}
\begin{minipage}{.47\textwidth}
    \centering
    \includegraphics[width=\textwidth]{images/r2.png}
    \caption{Graf tropického polynomu $``x^5+2x+0"$.}
    \label{fig:graf2}
\end{minipage}
\end{figure}

Pojďme nyní nalézt kořeny našeho polynomu na obrázku \ref{fig:graf}. Prvním kořenem je místo zlomu konstantní funkce $y=(-5)$ a lineární funkce $y=x+1$, kořen tedy nalezneme po vyřešení snadné lineární rovnice
$$x+1=(-5),$$
tedy $x_0=-6$. Podobně řešením rovnice
$$x+1=3x+3$$
dostaneme dvojný kořen $x_1=x_2=-1$. Povšimněme si, že tento polynom třetího stupně má tři kořeny. 

Rozeberme nyní ještě jeden tropický polynom, tentokrát $Q(x)=``x^5+2x+0"{}=\mathrm{max}(5x,2+x,0)$, jehož graf je na obrázku \ref{fig:graf2}. Nyní je pro nás hračkou spočítat, že má kořen $(-2)$ násobnosti jedna a kořen $\frac{1}{2}$ násobnosti čtyři. Polynom má stupeň pět a pět kořenů, vypadá to tedy, že tropický mnohočlen by mohl mít tolik kořenů, jaký je jeho stupeň, což je již zmíněná vlastnost klasických polynomů. Tento fakt si uvědomíme následující úvahou. 

Sklony jednotlivých úseků grafu, jež odpovídají mocninám členů polynomu, si postupně označíme $s_0, s_1, \dots s_k$, přičemž $s_k$ odpovídá nejvyšší mocnině v polynomu a je to tedy jeho stupeň. Jednotlivé kořeny jsou zlomy mezi úseky a jejich násobnosti jsou rozdíly mezi jejich sklony. Posloupnost násobností jednotlivých kořenů je tedy $(s_1-s_0), (s_2-s_1), \dots , (s_k-s_{k-1})$. Nás zajímá celkový počet kořenů (počítajíce jejich násobnosti), jenž určíme jakožto součet násobností jednotlivých kořenů, tedy
$$(s_k-s_{k-1}) + (s_{k-1}-s_{k-2}) + \dots (s_1-s_0) = s_k - s_0$$
Jestliže polynom obsahuje absolutní člen, máme $s_0=0$ a poté je počet kořenů vskutku roven stupni polynomu. Pokud v předpisu našeho polynomu chybí absolutní člen, představíme si, že jej máme, ale jeho hodnota je rovna $-\infty$ \footnote{Jestliže v normálním polynomu chybí nějaký člen $a_i x^i$, znamená to, že jeho koeficient $a_i$ je nula.  U tropických protějšků tuto roli plní $-\infty$. }. Potom máme kořen násobnosti $s_0$ v minus nekonečnu a vidíme, že hodnota stupně polynomu zůstává rovna počtu kořenů. 

To však není jediná podobnost tropických polynomů s těmi opravdovými. Ukazuje se, že když známe kořeny tropického polynomu, můžeme jej rozložit podobně jako ten klasický. Ukážeme si to na příkladu našich dvou polynomů. Platí:
$$``3x^2+1x+(-5)"{} = ``3\cdot(x+(-6))\cdot(x+(-1))^2"$$
a
$$``0x^5+2x+0"{}=``0\cdot(x+(-2))\cdot\left(x+\frac{1}{2}\right)^4".$$

Důkaz tohoto tvrzení neuvádíme, nicméně lze jej zase založit na představě grafu polynomu.

Přidáváme proměnnou

Již jsme si ukázali, že klasické polynomy v jedné proměnné mají podobné vlastnosti jako jejich tropické protějšky. Jak to bude, když polynomům přidáme další proměnnou?

Polynomem ve dvou proměnných myslíme výraz typu

$$ P(x,y) = \sum_{i,j} a_{ij} x^i y^j,$$

tedy třeba $2x^5y^2+3xy^2+6$, $x^2+y^2-4$ nebo $y-x$. Stupněm polynomu pak myslíme maximum ze součtů  $i+j$ všech jeho členů, tedy stupně našich polynomů jsou postupně 7, 2 a 1. Tropický polynom pak z toho klasického dostaneme pouhým přidáním uvozovek. 

Často nás zajímá, pro které dvojice $x$ a $y$ je $P(x,y)=0$ (obdoba kořenů polynomů s jednou proměnnou). Pokud si tyto dvojice (jsou to vlastně souřadnice bodů) vyznačíme na plochu, dostaneme tzv. algebraickou křivku; třeba náš druhý polynom odpovídá kružnici a třetí polynom přímce. Stupněm křivky pak rozumíme stupeň odpovídajícího polynomu. 

Jak si nyní představit tropický polynom ve dvou proměnných? Každý člen $``a_{ij}x^iy^j"{} = a_{ij}+i\cdot x+j\cdot y$ nám v prostoru vymezuje nějakou rovinu (pro každý bod z jeho dvou souřadnic dostaneme třetí -- jeho výšku) a hodnota polynomu v každém bodě je maximum z výšek všech rovin. Můžeme si to tedy představit tak, že se shora díváme na všechny roviny a vždy vidíme jen část té, která je zrovna nejvýš. 

Vezměme si třeba tropický polynom $``x+y+0"{} = \mathrm{max}(x,y,0)$. Máme tři roviny; jednu s konstantní výškou 0, další, která s ní svírá úhel $45^\circ$ a jejíž výška je v každém bodě rovna jeho $x$-ové souřadnici a třetí rovinu, jejíž výška je obdobně v každém bodě rovna jeho souřadnici $y$. První rovina bude nejvýš pro body ze třetího kvadrantu, kde $x$ i $y$ jsou menší než nula. Pokud zbylou oblast symetricky rozdělíme podle osy prvního a třetího kvadrantu, dostaneme dvě oblasti, ve kterých je nejvýš druhá, rsp. třetí plocha (viz obr. \ref{fig:t1}). 

Stejně jako u polynomů s jednou proměnnou nás teď nebude zajímat, kdy je polynom roven nule, ale jak vypadají místa, kde se lomí, jde nám tedy o okraje našich oblastí. Na obrázku \ref{fig:t1} máme vyznačeny jednotlivé oblasti polynomu $``x+y+0"$, okraje oblastí nám vytvořily tropickou křivku. Snadno nahlédneme, že křivky polynomů $``a\cdot x + b\cdot y + c"$ vypadají všechny stejně a mění se pouze jejich poloha. Na obrázku \ref{fig:t2} pak máme složitější křivku odpovídající polynomu druhého stupně. 

\begin{figure}[htbp]
\centering
\begin{minipage}{.47\textwidth}
  \begin{center}
  \includegraphics[width=.9\textwidth]{images/t1.png}
  \end{center}
  \caption{Polynom $``x+y+0"$ a jeho tropická křivka.}
  \label{fig:t1}
\end{minipage}
\hspace{1em}
\begin{minipage}{.47\textwidth}
  \begin{center}
  \includegraphics[width=0.9\textwidth]{images/t2.png}
  \end{center}
  \caption{Polynom $``3xy+(-3)x^2+(-2)y^2+x+y+0"$.}
  \label{fig:t2}
\end{minipage}
\end{figure}

A k čemu to je?

Jestliže jste dočetli až sem, již víte, že tropické polynomy mají s těmi opravdovými mnoho společného. Přesto se může zdát, že se jedná o pouhou hříčku znuděných matematiků, opak je však pravdou. V této části již nebudeme příliš formální (konec konců, tropická geometrie je stará pouze několik desítek let, a tak nám jistě uvěříte, že ji nelze pořádně pochopit po přečtení několika stránek \footnote{či absolvování jedné konfery}). 

Vraťme se nyní k polynomům a algebraickým křivkám z klasického světa; víme, že křivky prvního stupně jsou přímky a křivky druhého stupně mohou vypadat jako nám známé paraboly, hyperboly, elipsy, kružnice nebo třeba dvě přímky (třeba rovnice $x^2 - y^2=0$ popisuje osy kvadrantů a rovnice $y^2-4=0$ odpovídá dvěma rovnoběžkám vzdáleným 2 od osy $x$). Už křivky druhého stupně tedy mohou nabývat mnohých podob a postupujeme-li dál, je situace čím dál tím složitější. Podívejme se třeba na několik polynomů stupně 4 na obr. \ref{fig:krivky4}. 

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=0.23\hsize]{images/k1.png}
        \includegraphics[width=0.23\hsize]{images/k2.png}
        \includegraphics[width=0.23\hsize]{images/k3.png}
        \includegraphics[width=0.23\hsize]{images/k4.png}
    \end{center}
    \caption{Několik křivek 4. stupně, převzato z \cite{bit}. }
    \label{fig:krivky4}
\end{figure}

Vidíme, že jedna křivka může sestávat z několika čar, neboli komponent (třeba hyperbola se skládá ze dvou komponent, zatímco parabola jen z jedné). Každá komponenta přitom je, nebo není omezená (obě komponenty hyperboly utíkají do nekonečna, zatímco jediná komponenta elipsy je uzavřená sama do sebe). 

Nás by zajímalo, kolik komponent křivka $n$-tého stupně může mít a v jakém mohou být vzájemném vztahu. Tedy pokud křivka obsahuje dvě uzavřené komponenty, nezajímá nás jejich přesná poloha, ale pouze zda je jedna uvnitř druhé (viz první a třetí křivku na obr. \ref{fig:krivky4}). Maximální počet komponent křivky v závislosti na jejím stupni je známý\footnote{Konkrétně křivka, jejíž stupeň je $n$, může mít nejvýše $\frac{n(n-1)+2}{2}$ komponent. Tedy křivka druhého stupně má maximálně dvě komponenty (hyperbola) a křivka čtvrtého stupně maximálně sedm komponent (druhá křivka na obr. \ref{fig:krivky4})}, ale popis jejich vzájemných vztahů obecně znám není. Nejedná se přitom o ledajaký problém, nýbrž je to šestnáctý z 23 problémů zveřejněných v roce 1900 tehdejším slovutným matematikem Davidem Hilbertem. Z těchto problémů již některé byly vyřešeny a některé (jako ten náš nebo známá Riemannova hypotéza) stále zůstávají otevřené. 

A právě v hledání algebraických křivek nám tropická geometrie pomáhá. Existuje totiž jistý algoritmus, na jehož začátku máme tropickou křivku stupně $n$. S tou pak uděláme jisté operace (přidáme a odebereme úsečky podle určitých pravidel) a máme zaručeno, že takto vzniklá křivka má stejné uspořádání jako nějaká algebraická křivka stupně $n$. Tímto způsobem tedy můžeme hledat třeba právě křivky s vysokým počtem komponent či nějakým speciálním uspořádáním. 

Tímto algoritmem jsme se však již na konfeře nezabývali a tak nastal čas tento článek ukončit. Ještě předtím však pozornému čtenáři zodpovězme otázku, která ho jistě trápila po celou dobu četby tohoto článku. Kde se vzalo přídavné jméno \uv{tropický}? Tropické geometrii dali její jméno francouzští matematikové jako poctu jejich brazilskému kolegovi, který se tímto oborem zabýval. Citujme na závěr \cite{intro}: \uv{Přídavné jméno tropický nemá žádný hlubší význam. Prostě odráží pohled Francouzů na Brazílii. }

\renewcommand{\refname}{\hfil \textnormal{\textsf{\Large Reference}} \hfil}
\begin{thebibliography}{99}
\bibitem{pepa}
Josef Svoboda. \textit{Tropická geometrie}. Sborník MKS, Zásada. 2014
\bibitem{bit}
Erwan Brugallé. \textit{A bit of Tropical Geometry}. 2014
\bibitem{intro}
Diane Maclagan. \textit{Introduction to Tropical Geometry}. 2013 
\bibitem{telesa}
Tělesa [online]. 2014 [cit. 2015-01-27]. Dostupné z: \url{http://www.matematika.cz/telesa}
\bibitem{onlinetrop}
Introductory Workshop: Tropical Geometry [online]. 2009 [cit. 2015-01-27]. Dostupné z: \url{http://www.msri.org/workshops/481}
\bibitem{simon}
Imre Simon [online]. 2014 [cit. 2015-01-27]. Dostupné z: \url{http://en.wikipedia.org/wiki/Imre_Simon}
\end{thebibliography}