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 (Z₂)ⁿ

Rozważmy teraz trzy operacje

S,I,F: (Z₂)ⁿ -> (Z₂)ⁿ

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 Z₂.

Operacja F ma ciekawe własności:

Własność 1.

F((Z₂)ⁿ) = {f∈(Z₂)ⁿ | #f^--1({1}) jest parzyste}

Dowód:

Niech G: (Z₂)ⁿ-> Z₂ 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: (Z₂)ⁿ->(Z₂)ⁿbę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:

f∈F((Z₂)ⁿ) ⇒ #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 Fⁱ(f) = F^j(f)

Dowód:

Prosty wniosek ze skończoności zbioru (Z₂)ⁿ

Arnold zdefinował złożoność ciągu z (Z₂)ⁿ jako

cplx(f) = min { j>0 | istnieje i ≥ 0 istnieje j > i Fⁱ(f) = F^j(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->x². 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->x², 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 x² = -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 x²=-1 (mod p) ma rozwiązanie to z Małego Twierdzenia Fermata wiemy, że

x^p-1 = 1 (mod p)

zatem

(x²)^(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 x² = -1 nie ma rozwiązania.

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

Niech (Z_p^*)² = {x² | x ∈ Z_p^* }

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

Łatwo sprawdzić, że (Z_p^*)² ⊂ Z_p^* jest podgrupą (operacja _² jest endomorfizmem grup).

Podobnie łatwo widać, że indeks (Z_p^*)² w Z_p^* wynosi 2. Równanie x² = 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 x₁ jest rozwiązaniem to p-x₁ również, nie może zaś być p-x₁ = x₁ (mod p) bo wtedy 2x₁ = 0 (mod p) co jest niemożliwe).

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

Rozważymy teraz iterację endomorfizmu _² w podgrupie (Z_p^*)².

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

x² ≠ y² (mod p)

i

x⁴ - y⁴ = 0 (mod p),

co za tym idzie

(x² - y²)(x²+y²) = 0 (mod p)

a więc

x² + y² = 0 (mod p)


a wtedy x²*(y^-1)² + 1 = 0 (mod p )

i w końcu

(x*y^-1)² = -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 = x²ⁿ dla pewnego n

lub

II) x^-1 =/= x²ⁿ dla wszystkich n


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

Zatem, zbiór (Z_p^*)² \{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 (Z_p^*)² (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->x² 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.