Nieuczesane myśli topologa

W salonie fryzjerskim siedzi matematyk, obok leży połyskująca para nożyczek, mnóstwo szczotek i innych sprzętów. Matematyk nerwowo wierci się w fotelu - przecież nie od dziś wie, że sfery zaczesać się nie da. Fryzjer intuicyjnie sięga po nożyczki, szalejące nad czołem rozmaitości nie rokują zbyt dobrze. Niechętny rozspójnieniu klient wpada na pomysł - warkocz będzie idealny!

U progu XX wieku Emil Artin wprowadził do topologii dziedzinę (pozornie) blisko związaną z codziennością. Teoria warkoczy znajduje zastosowanie między innymi w biologii i kryptografii oraz w teorii węzłów. Artykuł ten stanowi zaproszenie do elementarnych rozważań nad tym zagadnieniem, przedstawiając niezbędne definicje i fakty dotyczące struktury grup warkoczy oraz klasyczne algorytmy czesania.

Czym jest warkocz dla matematyka?

Dla "normalnego" człowieka warkocz stanowią zaplecione pasma włosów, sznurków itp. Dla wygody (i z empirycznego doświadczenia) wprowadzamy pewne uproszczenia - rozważamy $n$ -pasmowe warkocze umieszczone wewnątrz walca, a końce zaczepione są w różnych punktach podstaw. Zakładamy, że wszelkie przeplecenia odbywają się wewnątrz "tuby", w żadnym punkcie dwa pasma nie łączą się w jedno (nie przecinają się) i nie mogą zawracać. Nie ma też obawy, że ustalona długość pasm i skomplikowanie przepleceń spowoduje, że któreś nie dotrze do punktu zaczepienia końców - topologia to w uproszczeniu "giętka geometria" i nie ma problemu z rozciąganiem pasm.

Tak więc wybieramy po $|n$ punktów na podstawach walca (ułożonego w poziomie), powiedzmy $|p1,$ $p2,...,pn$ na lewej podstawie oraz $|q1,q2,...,qn$ na prawej podstawie. Rozpoczynając od punktów $pi,$ odbywa się splot aż do punktów zaczepienia $|q . j$ Fachowo, warkoczem geometrycznym $|β$ nazywamy układ (ciąg) giętkich pasm (formalnie: wykresów funkcji), które zaplatają się wewnątrz walca, tak jak na rysunku 1.

Warto zwrócić uwagę na zachowanie pasm na podstawach walca. Przypuśćmy, że pasmo zaczynające się w punkcie $p1$ na lewej podstawie, kończy się w punkcie $q4$ na prawej podstawie itd. Wówczas połączenia między podstawami możemy zapisać jako

p1 p2 ... pn 1 2 ... n ( )lub prościej, zostawiają c tylko indeksy:( ) . q4 q2 ... ... 4 2 ... ...

Widzimy, że warkocz definiuje przyporządkowanie liczbom ze zbioru $|{1,2,...,n}$ liczby z tego samego zbioru (niekoniecznie inne). Przyporządkowania (różnowartościowe) opisujące przestawienia/przetasowania liczb nazywa się permutacjami. Permutację pochodzącą od warkocza $|β$ nazywamy permutacją indukowaną przez ten warkocz.

Dwakroć zapleciony "taki sam" warkocz (mimo usilnych chęci czeszącego) zawsze wygląda odrobinę inaczej. Fakt, że możemy użyć określenia "taki sam", pozwala nam wnioskować, że niektóre warkocze reprezentują ten sam "rodzaj" warkocza (chociażby kłos, francuz czy warkocz klasyczny trójpasmowy). Dwa warkocze uznamy za równoważne, jeśli jeden powstaje z drugiego poprzez powyginanie pasm z zaczepionymi nieruchomo końcami. Stąd indukowana permutacja jest ustalona dla konkretnej klasy równoważnych warkoczy.

Struktura grupy

Z warkoczami, poprzez permutacje indukowane, nieodłącznie związana jest grupa permutacji. Grupą permutacji $Sn$ nazywamy zbiór permutacji na $| n$ elementach wraz z działaniem składania, któremu przyjrzymy się na przykładzie grupy $|S3,$ czyli

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 {(1 2 3) ,(1 3 2),(2 1 3),(2 3 1) ,(3 1 2) ,(3 2 1)} .

Rolę elementu neutralnego pełni $|(1 2 3) . 1 2 3$ Pozostaje jeszcze zastanowić się, jak uzyskać wynik złożenia $(1 2 3)⋅(1 2 3) = (1 2 3)? 3 2 1 2 3 1 2 1 3$ Zaczynamy od wewnętrznej permutacji, która przesyła $1 2,$ z kolei zewnętrzna $|2 2,$ więc łącząc te dwa warunki, dostajemy w wyniku $1 2.$ Podobnie postępując z $2$ i $3,$ uzyskujemy permutację końcową. Warto zwrócić uwagę, że zamieniając permutacje miejscami, dostajemy inny wynik: $|(1 2 3) ⋅(1 2 3) = (1 2 3). 2 3 1 3 2 1 1 3 2$ Oczywiście dla każdej permutacji z $|S3$ możemy znaleźć permutację odwrotną, co pokazuje, że $S3$ ma strukturę grupy.

Podobnie jak w przypadku permutacji, w zbiorze warkoczy na określonej liczbie pasm wprowadzamy działanie składania warkoczy. Intuicyjnie można je rozumieć jako przedłużenie jednego warkocza drugim poprzez związanie pasm. Wyobraźmy sobie dwa identyczne walce z warkoczami wewnątrz o ustalonej liczbie pasm. Przyjmijmy, że końce pierwszego warkocza i początki drugiego występują dokładnie w tych samych miejscach na podstawach. Zestawiamy te walce tak, aby wskazane punkty się spotkały, i sklejamy pasma na styku. Mamy więc walec o podwójnej długości ze związanymi dwoma warkoczami. Znów mamy twór spełniający definicję warkocza geometrycznego, a tym samym wynik działania, co widać na rysunku 2.

Nietrudno zauważyć, że takie określenie spełnia aksjomaty grupy: zachodzi łączność, mamy warkocz neutralny o prostych pasmach i dla każdego warkocza możemy wskazać warkocz do niego odwrotny - odbicie lustrzane.

Zauważmy również, że permutacją indukowaną przez złożenie warkoczy jest złożenie odpowiednich permutacji. Przykładowo, na rysunku 2 pierwszy z warkoczy indukuje permutację $1 2 3 4 |(4 3 1 2),$ zaś drugi $1 2 3 4 |(1 2 4 3).$ Ich złożenie to $|(1 2 3 4), 3 4 1 2$ czyli permutacja wyniku. Warto również zwrócić uwagę na to, że złożenie powyższych permutacji w odwrotnej kolejności da inny wynik. To pokazuje, że złożenie warkoczy $σ ∗τ$ nie będzie tym samym co $τ∗ σ .$

Zapiszmy to słowami!

Aby usystematyzować opis warkoczy, wprowadza się tak zwane warkocze elementarne, czyli "cegiełki" budulcowe każdego warkocza. Precyzyjniej, warkoczem elementarnym $σi$ nazywamy warkocz, w którym występuje tylko jedno przeplecenie: $|(i + 1)$ -sze pasmo przecina $i$ -te (przechodząc ponad nim), a pozostałe pasma pozostają proste (rys. 3). Jego odwrotnością $|σ−1 i$ jest warkocz elementarny, w którym $i$ -te pasmo przechodzi ponad $|(i + 1)$ -szym. Odpowiednio "rozluźniając" sploty, możemy podzielić dowolny warkocz na segmenty, w których występuje tylko jedno przełożenie pasm odpowiadające konkretnemu warkoczowi elementarnemu (przykład na rysunku 4). Każdy warkocz możemy zatem przedstawić jako złożenie (połączenie) warkoczy elementarnych. Taki opis (który nazywamy słowem) niestety nie jest jednoznaczny. Zastanówmy się, czy warkocz z rysunku 5 "bardzo" się zmieni, jeśli zamiast początkowego przełożenia pasm trzeciego i czwartego (od dołu) wykonać je najpierw na paśmie pierwszym i drugim? Biorąc pod uwagę giętkość i ciągliwość, zmiana nie będzie istotna.

Jak zatem sprawdzić, kiedy różne słowa opisują ten sam warkocz? Problem ten rozstrzyga twierdzenie zaproponowane przez Artina i Magnusa. Wyróżnia ono trzy typy niejednoznaczności zapisu warkoczy:

(a): Złożenie warkoczy elementarnych $−1 |σi∗σ i$ oraz $−1 |σi ∗ σi$ jest równoważne warkoczowi neutralnemu.
(b): Jeśli w warkoczach elementarnych $σi$ oraz $σ j$ przeplecenia występują na niezależnych pasmach, tzn. $i − j > 1,$ wówczas warkocz $σi ∗σ j$ jest równoważny warkoczowi $σ j∗ σi$ (przykład na rysunku 6).
(c): W przypadku gdy przeplecenia w warkoczach elementarnych $σi$ oraz $σ j$ mają jedno wspólne pasmo (czyli $j = i± 1$ ), to warkocz $σ ∗ σ ∗ σ i j i$ jest równoważny $σ ∗ σ ∗ σ , j i j$ co widać na rysunku 7.

Wspomniane twierdzenie orzeka, że jeśli dwa słowa kodują ten sam warkocz, to jedno z nich można uzyskać z drugiego poprzez zastosowanie operacji (a)-(c). Niestety twierdzenie to nie daje algorytmicznej formuły na rozwiązanie tego zadania.

Problem słów - algorytmy

Czasem codzienność wymusza od nas syzyfową pracę rozplątywania różnych rzeczy, chociażby kabli. W przypadku warkoczy orzeczenie, czy być może skomplikowana plątanina rzeczywiście coś splotła czy nie, jest zagadnieniem z kombinatorycznej teorii grup zwanym problemem słów. W dalszej części przyjrzymy się metodom rozstrzygania go. Ograniczymy naszą uwagę do warkoczy czystych, czyli takich, które indukują permutację identycznościową (tzn. nie zmieniają układu końców). Innych warkoczy nie ma sensu rozpatrywać, ponieważ nie mogą być równoważne z neutralnym.

W 1926 roku ukazał się artykuł Emila Artina "Theorie der Zöpfe", w którym przedstawił on algorytm "czesania" (porządkowania kolejności przepleceń) warkoczy. Weźmy warkocz czysty $β$ o $n$ pasmach i rozczeszmy go w następujący sposób:

(1): Tworzymy kopię warkocza $|β$ i usuwamy z niej pierwsze pasmo od góry, zastępując je prostym. Otrzymany w ten sposób warkocz nazywamy $|γ1$ (rys. 8).
(2): Rozważmy złożenie $α = β ∗ γ−1 1 1$ (rys. 9). Gdybyśmy zabrali pierwsze od góry pasmo z $α1,$ to pozostałe pasma moglibyśmy rozplątać. W tej sytuacji, posługując się operacjami (a)-(c), możemy doprowadzić $α 1$ do równoważnej postaci, w której w każdym przepleceniu bierze udział pierwsze pasmo (rys. 10). Nasz wyjściowy warkocz możemy zapisać jako $|β =α 1∗γ 1.$ Wówczas w jego pierwszej części $|(α1)$ w każdym przepleceniu bierze udział pierwsze pasmo i nie bierze ono udziału w żadnym przepleceniu pozostałej części warkocza.
(3): Procedurę opisaną w krokach 1 i 2 powtarzamy dla warkocza $γ1.$
(4): Po odpowiedniej liczbie powtórzeń otrzymujemy rozkład $β = α ∗ ...∗ α , 1 n−1$ w którym każdy z segmentów $|α i$ jest "wyczesany" (tzn. w jego przepleceniach bierze udział tylko $i$ -te pasmo od góry, rys. 11).

Rys. 8. Warkocze: $\|β$ (z lewej) i $\|γ 1$ (z prawej) Rys. 8. Warkocze: $\| β$ (z lewej) i $\| γ1$ (z prawej)	Rys. 10. Warkocz $α1$ po naciągnięciu pasm Rys. 10. Warkocz $α1$ po naciągnięciu pasm
Rys. 9. Warkocz $α 1$ Rys. 9. Warkocz $α 1$	Rys. 11. Postać normalna warkocza $\|β$ Rys. 11. Postać normalna warkocza $\|β$

Tak uzyskany "wyczesany" rozkład nazywamy postacią normalną. Dla każdego warkocza istnieje dokładnie jeden "wyczesany" warkocz, w którym wszystkie $|αi$ są zredukowane zgodnie z relacjami. Jak łatwo się domyślić, badany warkocz jest równoważny neutralnemu wtedy i tylko wtedy, gdy po czesaniu jest neutralny (ma proste pasma).

Przyjrzymy się teraz drugiej metodzie rozstrzygania problemu słów w grupie warkoczy, zaproponowanej przez Patricka Dehornoya w 1997 roku. Redukcja rączek polega na wskazaniu podwarkoczy określonego typu, tzw. rączek, które stopniowo opuszczane za pomocą pewnego odwzorowania (homomorfizmu) rozplatają warkocz, a tym samym pozwalają na sprawdzenie jego neutralności. Formalnie, rączką nazywamy podwarkocz postaci $|σe∗ x ∗σ −e, i i$ gdzie $|e = ±1,$ a $x$ złożony jest tylko z generatorów $±1 σ j$ przy $j < i,$ rysunek 12 tłumaczy nazwę. Podobnie jak poprzednio, będziemy rozpatrywać warkocze czyste. Przesuwając się od początku warkocza po lewej znajdujemy pierwszą rączkę i opuszczamy ją (rys. 13). W otrzymanym warkoczu również szukamy rączki itd., aż do wyczerpania dostępnych rączek. W zależności od tego, czy końcowy warkocz jest neutralny czy też nie, dostajemy odpowiedź. Nie ma obawy, że zmienimy warkocz w trakcie przeprowadzania redukcji, ponieważ korzystamy tylko z operacji dozwolonych (wskazanych przez twierdzenie Artina i Magnusa). Z algorytmicznego punktu widzenia sytuacja również jest dobra, ponieważ algorytm redukcji nigdy się nie zapętli.

Imponujący warkocz podskakuje w rytm przytupów - wybór krawata to nie błaha sprawa. Sprzedawca pokazuje kolejno różne modele, jednak matematyk nieustannie obserwuje zwinnie tworzone węzły, do Windsora kolejno dołącza four-in-hand, eldredge i Shelby... Wreszcie kupuje siedem z nich - nie tylko dla urozmaicenia dni, ale i zabawy. Skoro da się opisać warkocze, to czemu by nie spróbować z węzłami?