2009-01-25

Sztuka i sztuczki

W wielu językach indoeuropejskich słowa "sztuka" i "sztuczny" mają, jak w języku polskim wspólny źródłosłów. W angielskim: "art" - "artificial", w niemieckim: "künst" - "künstlich", w rosyjskim: "iskusstwo" - "isskustwiennyj", we francuskim: "le art" - "artificielle". To oczywiście nie przypadek, tylko utrwalony w głębinach języka fakt, że sztuka jest wytworem człowieka. Piękno natomiast, które czasem, naiwnie, jest uważane za nieodłączny atrybut pozwalający uznać wytwór za "sztukę" tkwi również w "naturze" czyli zaprzeczeniu sztuki.
Nic dziwnego, że nie jest dla nas niezwykłe rozumieć sztukę szeroko rozciągając ją na wszelkie wytwory ludzkie. Ale w wąskim pojęciu przez sztukę rozumie się te, które w zasadzie są zupełnie zbędne albo raczej zbytkowne, tzn. nie zaspokajają ani nie ułatwiają jakichś łatwo definiowalnych i elementarnych z punku widzenia egzystencji potrzeb. W pierwszym rzędzie obliczone na efekt estetyczny (stąd naiwne przekonanie o jakim wspomniałem) ale również na komunikacyjny, wyrażający idee filozoficzne, symbolizujący - władzę, miłość, wiarę,strach etc.
W tym kontekście obszerna część nauki ma wiele wspólnego ze sztuką - jest wytworem ludzkim, jest sztuczna, nie zaspokaja potrzeby pierwotnej ale dalsze -estetyczne i inne tego typu. Czasem sztuka przenika się wprost z nauką.
Ostatnio - stąd w ogóle pomysł tego postu -natrafiłem na niesamowite napędzane wiatrem kroczące rzeźby holenderskiego artysty Theo Jansena. Piękny obrazek można znaleźć choćby w reklamie BMW na YouTube:


Za tymi niezwykłymi rzeźbami-maszynami kryje się sporo ciekawej matematyki i trochę ciekawej historii. Sposoby zamieniania ruchów najprostszych - jak obrotowy - na skomplikowane to esencja konstrukcji mechanicznych w ogóle. Zdumiewająca i chyba dziś trochę funkcjonująca na obrzeżach powszechnej uwagi to sztuka (bo wszelkie mechanizmy są pochowane przed nami za osłonami, obudowami a ciężar zainteresowania techniką przeniósł się w kierunku komputerów i cyfrowego świata). Pełno tam wspaniałych pomysłów, często genialnych w swojej prostocie. Maszyny Jansena przywodzą na myśl pomysły wielkiego matematyka rosyjskiego Pafnucego Lwowicza Czebyszewa (tego od wielomianów Czebyszewa i od twierdzenia Czebyszewa o rozmieszczeniu liczb pierwszych). Pracując nad mechanizmami przekładającymi ruch kołowy na inne bardziej skomplikowane jego wymyślił między innymi maszynę kroczącą której zasadę działania można poznać również podglądając YouTube:



Maszyna Czebyszewa doczekałą się prototypu i prezentacji na Wystawie Światowej w Paryżu w roku 1878. Geometria? Technika? Sztuka? W kontekście Theo Jansena - czemu nie?
Jest w internecie kilka programów, które pozwalają na samodzielne zabawy z konstrukcjami ala Czebyszew czy Jansen. Wspomnę dwa: popularny ostatnio i zabawny Phun i niesamowity klasyk do zabaw z geometrią o ogromnych możliwościach (ach ta niemiecka robota!): Cinderella.
Przy okazji, kiedy rozmyślam o związkach nauki, sztuki i techniki, przychodzi mi też do głowy sztuka robienia sztuczek jakimi są efekty specjalne. Zapierające dech w piersiach sceny albo zadziwiające postacie kreowane w filmach - toż to sztuczki na miarę sztuki. To stara profesja. Czyż niektóre zadziwiające dzieła jednego z największych uczonych epoki Hellenistycznej - Herona z Aleksandrii -nie w takim celu (tzn. jako efekty specjalne) zostały stworzone?
Zresztą epoka hellenistyczna podniosła dociekania naukowe na rzecz sztuki do rangi osobnej nauki. Tzw. skenografia czyli umiejętność iluzji trójwymiarowych stosowana w malarstwie, rzeźbie, architekturze i w końcu w scenografii spektakli teatralnych wywodzi z siebie gmach geometrii rzutowej - ważnej do dziś i w technice i w malarstwie i będącej jednym z fundamentów współczesnej matematyki.
Wracając do mechanizmów podobnych tym Jansena - sprawdźcie rozdział "Kinematyka" w książce Hilberta i Cohn-Vossen "Geometria poglądowa". Można się z niego dowiedzieć niedużo, ale za to ciekawych rzeczy na ten temat.

2009-01-18

Skojarzenia: złożoność, V.I.Arnold, testy pierwszości, Euler, bezsenna noc u teściów

Niekoniecznie w tej kolejności, bo skojarzenia powinny być reprezentowane przez graf raczej niż ciąg słów.

Jakiś czas temu wpadł mi w ręce tekst wykładu V.I.Arnolda, dotyczącego pewnej miary złożoności skończonego ciągu zero-jedynkowego. Cały artykuł dostępny jest gdzieś w internecie postaram się streścić go nieco poniżej.


Weźmy ciąg o ustalonej długości n, którego elementami są 0 i 1. Tzn. interesują nas funkcje f:{0,…,n-1} -> {0,1}. Zbiór takich funkcji możemy utożsamić z
(Z2)n

Rozważmy teraz trzy operacje

S,I,F: (Z2)n -> (Z2)n

I(f) = f (I jest identycznością)

S(f)(i) = f(i+1 mod n) (S jest operatorem przesunięcia cyklicznego w lewo)

F = S + I (mod 2)

F(g)(i) = g(i)+g((i+1) mod n) (mod 2)

Przykład:


n=4 g = [1,0,0,1]

I(g) = [1,0,0,1]

S(g) =[0,0,1,1]

F(g) = [1+ 0, 0+0, 0+1, 1+1] = [1,0,1,0]


Wszystkie operacje powyżej są liniowe nad Z2.

Operacja F ma ciekawe własności:


Własność 1.

F((Z2)n) = {f(Z2)n | #f--1({1}) jest parzyste}

Dowód:


Niech G: (Z2)n-> Z2 będzie zdefiniowana następująco:

G(f) = ∑i∈{0,...,n-1}f(i). Wówczas, GF = G(S+I) = GS+GI = GI+GI = 0

Dowodzi to zawierania "⊂".

W drugą stronę.

Niech H: (Z2)n->(Z2)nbędzie zdefiniowane następująco

H(f)(j) = ∑i∈{0,...,j-1}f(i)

przy czym sumę po zbiorze pustym przyjmujemy jako 0.

Wówczas, jeżeli ilość jedynek w ciągu f jest parzysta, to FH=I. Bo:

FH(f)(j) = ∑i∈{0,...,j-1}f(i) + ∑i∈{0,...,j}f(i) = f(j) dla j = 0,...,n-2

FH(f)(n-1) = ∑i∈{0,...,n-2}f(i) + ∑i∈f(i) = ∑i∈{0,...,n-2}f(i) + ∑i∈{0,...,n-1}f(i) = f(n-1)

W ostatniej sekwencji równości wykorzystaliśmy założenie o parzystej liczbie jedynek.

Zawieranie "⊃" dokazane.

Własność 2:

fF((Z2)n) ⇒ #F-1({f}) = 2

Dowód:

Niech 0 oznacza [0,...,0] a 1 [1,...,1]

Wówczas, co łatwo sprawdzić (wystąpienie 0 i 1 w ciągu gwarantuje, że w obrazie wystąpi 1):
ker F = {0,1}

zatem

jeżeli F(f) = F(g) to f-g = f+g {0,1}

To kończy dowód, bo f+1 =/= f i F(f+1) = F(f)

Własność 3:

Dla każdego f ∈ CG(n) istnieje j > i ≥ 0 t. że Fi(f) = Fj(f)

Dowód:

Prosty wniosek ze skończoności zbioru (Z2)n

Arnold zdefinował złożoność ciągu z (Z2)n jako

cplx(f) = min { j>0 | istnieje i ≥ 0 istnieje j > i Fi(f) = Fj(f) }



Z własności 1,2 i 3 przy pewnej dozie pracy (jeśli ktoś nie ma ochoty sam powalczyć - odsyłam do Arnolda) można wydedukować pewne wnioski na temat schematu struktury (może lepiej powiedzieć będzie grafu) odwzorowania F. Piszę "schematu", bo w zależności od n, sama struktura zmienia się bardzo mocno.

Postaram się, dla objaśnić z grubsza co i jak.

Na poniższym rysunku (podobne można znaleźć w pracy Arnolda) przedstawiłem graf odpowiadający odwzorowaniu F dla n=3. W węzłach grafu znajdują się ciągi zero-jedynkowe długości 3 strzałki zaś pokazują jak transformacja F działa na tych ciągach.




Okazuje się, że graf przekształcenia dla różnych n zawsze zbudowany jest według tego samego schematu. Mamy więc:

- zawsze jeden punkt stały 0

- do punktu stałego "przyczepione" jest binarne drzewo o krawędziach skierowanych "do korzenia"

- pozostała cześć grafu rozspaja się na podgrafy, z których każdy posiada cykl o długości > 1

- do każdego elementu należącego do cyklu w podgrafie, "przyczepione" jest drzewo binarne o krawędziach skierowanych "do korzenia", izomorficzne (jeśli, oczywiście, zaniedbać etykiety w węzłach) z drzewem "przyczepionym" do punktu stałego


Można wypowiedzieć dalsze twierdzenia uszczegóławiające informacje o budowie grafu (w szczególności dotyczące długości cykli i głębokości drzew), wspomina o tym również Arnold.



Fenomen bardzo podobny pojawia się w innych grupach skończonych. Arnold odsyła do swojego artykułu, do którego niestety nie mam dostępu w "Uspiechach Matiematiczeskich Nauk"). Ja jednak, zupełnie przypadkowo i w wiele miesięcy po tym jak przeczytałem artykuły Arnolda, natrafiłem na pracę w której dowodzi się, że identyczny schemat budowy ma graf następującego przekształcenia.

Tym razem zaczynamy od liczby pierwszej, a właściwie multplikatywnej grupy niezerowych elementów ciała reszt modulo pewna liczba pierwsza p.

Naszym przekształceniem jest x->x2. Badanie tego przekształcenia (ale i innych przekształceń kwadratowych) jest ściśle związane z testami pierwszości pewnych liczb specjalnej postaci. Dla przekształcenia x->x2, dowodzi się w nietrudny a obficie korzystający z małego twierdzenia Fermata i twierdzenia o pierwiastkach pierwotnych sposób, że struktura grafu jest jest identyczna jak ta u Arnolda.



To przypomniało mi pewną noc spędzoną u moich teściów, kiedym przesadnie objedzony po kolacji próbowałem najpierw czytać a potem, kiedym zgasił światło (małżonka spała smacznie) nie mogąc zasnąć próbowałem sobie udowodnić na jakiś prywatny sposób kawałek prawa wzajemności dla reszt kwadratowych. Mianowicie chodziło o takie



Twierdzenie (Euler):

Niech p będzie liczbą pierwszą. Wtedy równanie x2 = -1 (mod p) ma rozwiązanie wtedy i tylko wtedy gdy p = 1 (mod 4) dla pewnego k.



Dowód (bezsenną nocą):

W jedną stronę jest łatwo. Jeżeli x2=-1 (mod p) ma rozwiązanie to z Małego Twierdzenia Fermata wiemy, że

xp-1 = 1 (mod p)

zatem

(x2)(p-1)/2 = 1 (mod p)

czyli

(-1)(p-1)/2 = 1 (mod p)

więc

(p-1)/2 musi być parzyste.

W drugą stronę jest ciekawiej.

Przyjmijmy, że p = 4k+1 i załóżmy dla rozumowania niewprost, że x2 = -1 nie ma rozwiązania.

Rozważmy Zp* - grupę multiplikatywną ciała Zp (tj. ciała reszt modulo p).

Niech (Zp*)2 = {x2 | x Zp* }

UWAGA!!! zmieniam tu znaczenie górnego indeksu w stosunku do pierwszej części postu (tam bowiem oznaczał potęgę kartezjańską)

Łatwo sprawdzić, że (Zp*)2 ⊂ Zp* jest podgrupą (operacja _2 jest endomorfizmem grup).

Podobnie łatwo widać, że indeks (Zp*)2 w Zp* wynosi 2. Równanie x2 = k (mod p) ma bowiem nie więcej niż dwa rozwiązania i jeśli ma jedno, to posiada też drugie, różne od niego (jeżeli x1 jest rozwiązaniem to p-x1 również, nie może zaś być p-x1 = x1 (mod p) bo wtedy 2x1 = 0 (mod p) co jest niemożliwe).

Rząd grupy (Zp*)2 jest więc parzysty i wynosi (p-1)/2 = 2k.

Rozważymy teraz iterację endomorfizmu _2 w podgrupie (Zp*)2.

Gdyby endomorfizm ten nie był automorfizmem (izomorfizmem na siebie) tej podgrupy, mielibyśmy dla pewnych x, y w Zp*

x2 ≠ y2 (mod p)

i

x4 - y4 = 0 (mod p),

co za tym idzie

(x2 - y2)(x2+y2) = 0 (mod p)

a więc

x2 + y2 = 0 (mod p)


a wtedy x2*(y-1)2 + 1 = 0 (mod p )

i w końcu

(x*y-1)2 = -1 (mod p)

wbrew założeniu.



Przyjrzyjmy się bliżej temu automorfizmowi. Przeprowadza on oczywiście 1 w 1. Dla każdego innego od 1 x mamy dwa możliwe przypadki:

I) x-1 = x2n dla pewnego n

lub

II) x-1 =/= x2n dla wszystkich n


W pierwszym z tych przypadków x22n = x i długość orbity jest parzysta. W drugim, ponieważ (x2k)-1 = (x-1)2k, orbicie x odpowiada równoliczna z nią orbita x-1.

Zatem, zbiór (Zp*)2 \{1} można rozbić na podzbiory z których każdy jest albo orbitą o parzystej długości, albo składa się z dwóch orbit równolicznych. Jego rozmiar jest zatem parzysty. Pamiętajmy, jednak, że to rząd (Zp*)2 (więc rozmiar zbioru o {1} większego) miał być parzysty. Sprzeczność.

Przyglądając się bliżej temu dowodowi, można wydedukować obrazek podobny do tego wyżej, tym razem z odwzorowaniem x->x2 w roli głównej.

Acha, oczywiście mój zawiły dowód powyższego twierdzenia żadną miarą nie jest optymalny. Absolutna klasyka to dowód podany choćby w knolu u Włodka.

2009-01-07

Filozof na czas zamętu

Kryzys finansowy szaleje. Dziś okazało się, że niemal 700 000 ludzi straciło w grudniu w Stanach pracę. Na Bliskim Wschodzie, jak co chwilę, wojna. Po miesiącach skubania Hamas jest pacyfikowany wraz z cynicznie wykorzystywanymi w charakterze żywych tarcz cywilami, przez wojsko izraelskie (które do szczególnie delikatnych w tych sprawach nie należy). Skoro zima się sroży mamy też doroczny taniec z gazem. Straszą katastrofą energetyczną. Tragicznym zrządzeniem losu strategiczne dla Europy zasoby tego surowca są akurat we władaniu Rosji, zdemoralizowanego nieodpowiedzialnego kraju, który wszystkiego - czegóż by więc nie i gazu - używa jako broni politycznej śniąc niekończący się sen o potędze i władzy. Słowem przyszłość maluje się niepewnie i ciężko zdobyć się na optymizm.
W taki czas, jakby szczęśliwym przypadkiem, podczytuję sobie w autobusach (taki mam zwyczaj, poza tym nie da się przez zmrożone szyby kontemplować widoku zmarzniętego miasta) "Rozmyślania" Marka Aureliusza.
Stary cesarz, wychowanek stoików, z wielkim i wiecznie szarpanym niepokojem na rubieżach i intrygą wewnątrz państwem na głowie, pisał sobie coś w rodzaju starożytnego bloga. Pisał dla siebie. Przepowiadał sobie sentencje, cytaty, napominał się, słowem rozmyślał co zawsze jest rozmową z samym sobą. O czym rozmyślał Marek Aureliusz ? Rozmyślał przede wszystkim o niepodległości człowieka, siebie samego. O sile wewnętrznej która jeśli doskonalona pozwala człowiekowi zachować równowagę i zgodę z sobą w największym zamęcie. Sile, która płynie nie tylko z natężenia woli ale bardziej z namysłu nad światem, z poszukiwania proporcji i właściwego znaczenia rzeczy. Rozmyślał o tym co słuszne, co ważne i co nieważne. Nie o obojętności czy nieczułości ale o zrozumieniu nietrwałości postaci świata, w tym również tego złego co nas spotyka.
Marek Aureliusz napomina się - niemal czuć w "Rozmyślaniach" owe wichry namiętności jakie bez woli człowieka targają nim: żądzy sławy bogactwa, zemsty, gniewu i zniecierpliwienia. To znane wszystkim uczucia i reakcje i cesarz pewnie też im ulegał. Ale prawda jest taka, że każdy z tych porywów czyni z człowieka trochę niewolnika, czyni w nim jakieś spustoszenie. Filozofia Marka Aureliusza i wtedy kiedy karci się i napomina i kiedy obserwuje czym jest i jak funkcjonuje to wszystko co nas otacza, mówi nam, że w istocie jesteśmy panami samego siebie. Że to czy ulegamy tym czy innym uczuciom zależy od nas. Drogą, która prowadzi do tego by ową niepodległość, zgodę z sobą uzyskać to zrozumienie tak mechanizmu działania świata (a jego zasadą jest zmiana) jak i doraźności naszych przygód w świecie. Pod spodem jest głęboka wiara - odżywająca u myślicieli religijnych i filozofów na przestrzeni dziejów - w głęboki sens i racjonalność rzeczywistości. W swoisty "najlepszy możliwy świat". Marek Aureliusz nie pozostaje jednak bezkrytycznym panglosistą (ten termin ukuje się nb. w 17 wieków później). Często formułuje swoje myśli w postaci alternatywy: albo świat jest racjonalny i w istocie wszystko, nawet to co dzieje się w nim źle dziać się tak musi i jest w istocie dobre z perspektywy całości, albo jest nieracjonalny, ale wtedy wszystko jest i tak bez sensu - tym mniejsze znaczenie tego co nas spotyka. W każdym jednak przypadku jesteśmy w stanie ocenić nasze własne postępowanie: czy możemy być z niego dumni, czy nie wstydzimy się go, jakie pobudki nami kierują, czy potrafimy przezwyciężyć płoche namiętności. Jeżeli na te pytania potrafimy odpowiedzieć tak - postępujemy zgodnie z sobą, w sposób godny człowieka. To nie przychodzi samo. Wymaga ćwiczeń - po to przecież między innymi te zapiski.
Smutno mi czytać, kiedy cesarz, z cichym chyba żalem przemyconym w lapidarnych zdaniach pisze, że nie jest bardzo bystry i że nie jest filozofem. Bo może i do końca nie jest -jest po prostu mądrym, stroskanym, starającym się trzymać swoich zasad, próbującym zrozumieć świat człowiekiem.
Marek Aureliusz często pisze, wspominając o przemijaniu o zapominaniu, że możni i wielcy swoich czasów nikną w pamięci nadchodzących kolejno pokoleń. Taki los i dobrych i złych, tak jak śmierć jest losem wszystkich ludzi. Jednak tak jego dzieło jak i jego imę przetrwało. Jakieś 300 lat później wielkie państwo którym rządził zniknie rozszarpane przez barbarzyńców, wyrosną nowe religie, pojawią się inne państwa. Ale niemal dwa tysiąclecia później, ktoś w autobusie 114 będzie czytał "Rozmyślania" i czerpał spokój z cesarskich wynurzeń.