Twierdzenie Picka, a wzrost grupy wolnej abelowej.

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Twierdzenie Picka, a wzrost grupy wolnej abelowej.

Post autor: xiikzodz » 19 lis 2009, o 15:49

Nie jest to tekst o wzroście grup w ogólności. Taki temat należałoby zupełnie inczaczej rozwinąć. Wyznaczymy (a nie jedynie oszacujemy) funkcję wzrostu dla grupy wolnej i przy pomocy twierdzenia Picka funkcję wzrostu grupy wolnej abelowej rangi 2.

Rozważmy następujące zagadnienie:

Mając dany alfabet, zbiór \(\displaystyle{ n}\)-elementowy \(\displaystyle{ \{x_1,\ldots,x_n\}}\), wyznaczyć liczbę słów długości \(\displaystyle{ m}\) nad tym alfabetem.

Nietrudno zauważyć, że odpowiedzią jest liczba \(\displaystyle{ n^m}\).

Podobne pytanie można zadać w przypadku, gdy alfabetem są generatory pewnej grupy:

Ile różnych elementów grupy można otrzymać wymnażając \(\displaystyle{ m}\) generatorów lub odwrotności generatorów?

Odpowiedź zależy istotnie od grupy, zaś szacowanie liczby w pytaniu jest ważnym narzędziem matematyki drugiej połowy XX-ego wieku.

Różnica pomiędzy słowami a słowami w dowolnej grupie polega na tym, że w grupie słowo \(\displaystyle{ xx^{-1}}\) jest równe słowu \(\displaystyle{ yy^{-1}}\), a oba są równe słowu pustemu - elementowi neutralnemu grupy, dla dowolnych generatorów \(\displaystyle{ x,y}\). W różnych grupach różne słowa bywają utożsamiane. Na przykład w grupach abelowych słowo \(\displaystyle{ aba^{-1}b^{-1}}\) jest równe słowu pustemu, a w grupie izometrii \(\displaystyle{ n}\)-kąta foremnego słowo \(\displaystyle{ so^ns}\) jest równe słowu \(\displaystyle{ (o^{-1})^n}\), gdzie \(\displaystyle{ o}\) oznacza obrót o kąt \(\displaystyle{ 2\pi/n}\) a \(\displaystyle{ s}\) jedną z symetrii własnych wielokąta.

Tutaj zajmiemy się jedynie prostymi przykładami grup. Grupą wolną skończenie generowaną i grupą wolną abelową skończonej rangi (warto zapoznać się z definicjami przed przejściem dalej).

Najpierw trochę rozważań ogólnych.

Przypuśćmy, że zbiór generatorów, \(\displaystyle{ X}\), ma \(\displaystyle{ n}\) elementow. Oznaczmy \(\displaystyle{ X^{-1}=\{x^{-1}:x\in X\}}\).

Zbiór elementów grupy, które można otrzymać ze słów długości m nad alfabetem \(\displaystyle{ X\cup X^{-1}}\) będziemy oznaczać \(\displaystyle{ X_m}\).

Wówczas

\(\displaystyle{ |X_{i+1}|=|X_i\cdot(X\cup X^{-1})|\le|X_i|\cdot|X\cup X^{-1}|=|X_i|\cdot 2n=|X_{i-1}|\cdot(2n)^2=(2n)^{i+2}}\)

czyli

\(\displaystyle{ |X_i|=(2n)^{i+1}}\)

stąd grube naiwne szacowanie.

GRUPA WOLNA SKOŃCZENIE GENEROWANA.

Niech \(\displaystyle{ A_m}\) oznacza liczbę słów długości \(\displaystyle{ m}\) w grupie wolnej o \(\displaystyle{ n}\) generatorach \(\displaystyle{ F_n}\).

Mamy:

\(\displaystyle{ A_m=2n\cdot(2n-1)^{m-1}}\)

\(\displaystyle{ |X_{2i}|=A_0+\sum_{j=1}^iA_{2j}=1+2n\sum_{j=1}^i(2n-1)^{2j-1}=1+\frac{2n}{2n-1}\sum_{j=1}^i(2n-1)^{2j}}\)

\(\displaystyle{ =1+\frac{2n}{2n-1}((2n-1)^{2i+1}-(2n-1)^2)=2n(2n-1)^{2i}-2n(2n-1)+1}\)

Analogicznie

\(\displaystyle{ |X_{2i+1}|=\sum_{j=0}^iA_{2j+1}=\sum_{j=0}^i2n(2n-1)^{2j}=2n((2n-1)^{2i+1}-1)}\)

GRUPA WOLNA ABELOWA SKOŃCZONEJ RANGI

Teraz nieco o przypadku wolnej grupy abelowej o \(\displaystyle{ n}\) generatorach.

Nie stanowi większego problemu wypisać \(\displaystyle{ |X_i|}\) w posaci sumy ze współczynnikami dwumianowymi, ale nie potrafię takiej sumy zwinąć.

Można jednak znacznie prościej.

W przestrzeni \(\displaystyle{ \mathbb{R}^n}\) rozważmy normę \(\displaystyle{ \|(t_1,\ldots,t_n)\|_1=\sum|t_j|}\).

Niech \(\displaystyle{ B(0,r)}\) będzie domkniętą kulą w \(\displaystyle{ \mathbb{R}^n}\) w tej normie.

Oznaczmy:

\(\displaystyle{ A(r)}\) - zbiór punktów kratowych należących do \(\displaystyle{ B(0,r)}\).

Teraz już łatwo wypisać \(\displaystyle{ |X_i|}\). Tak, jak poprzednio oddzielnie dla parzystych i nieparzystych. Mamy:

\(\displaystyle{ |X_{2i}|=\sum_{j=0}^i|A(2j)|}\)

\(\displaystyle{ |X_{2i+1}|=\sum_{j=0}^i|A(2j+1)|}\).

Wyznaczanie wartości \(\displaystyle{ |A(m)|}\) łatwo sprowadzić do wyznaczenia liczby punktów kratowych w sympleksie rozpiętym na wektorach \(\displaystyle{ m\cdot e_i}\), gdzie \(\displaystyle{ e_i}\) są wektorami standardowej bazy. Oszacowanie \(\displaystyle{ |A(m)|}\) z góry łatwo otrzymać z objętości kuli jednostkowej w normie \(\displaystyle{ \|.\|_1}\), a ta jest prosta do wyznaczenia.

Gdy \(\displaystyle{ n=2}\) moce zbiorów \(\displaystyle{ A(m)}\) można wyznaczyć dokładnie i elegancko. Pole \(\displaystyle{ B(0,m)}\) w tym przypadku wynosi \(\displaystyle{ 2m^2}\) i na mocy twierdzenia Picka jest ono równe:

\(\displaystyle{ i+\frac b2-1}\)

gdzie i to liczba punktów kratowych we wnętrzu \(\displaystyle{ B(0,m)}\), zaś b to liczba punktów kratowych na brzegu \(\displaystyle{ B(0,m)}\). Kratowych punktów brzegowych jest

\(\displaystyle{ b=4m}\)

zatem wewnętrznych punktów kratowych jest

\(\displaystyle{ i=2m^2-\left(\frac b2-1\right)=2m^2-2m+1}\).

Nas interesuje liczba:

\(\displaystyle{ A(m)=b+i=2m^2+2m+1}\).

Ostatecznie więc w przypadku dwuwymiarowym, czyli grupy wolnej abelowej rangi 2:

\(\displaystyle{ |X_{2i}|=\sum_{j=0}^i|A(2j)|=\sum_{j=0}^i(4j^2+4j+1)=\frac{2i(i+1)(2i+1)}{3}+2i(i+1)+i+1}\)

\(\displaystyle{ |X_{2i+1}|=\sum_{j=0}^i|A(2j+1)|=\sum_{j=0}^i(2(2j+1)^2+2(2j+1)+1)=}\)

\(\displaystyle{ =\frac{4i(i+1)(2i+1)}{3}+6i(i+1)+5(i+1)}\).

Pozostaje uogólnić na przypadek \(\displaystyle{ n}\)-wymiarowy...

ODPOWIEDZ