szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta
PostNapisane: 19 lis 2009, o 16:49 
Użytkownik

Posty: 1874
Lokalizacja: Lost Hope
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 n-elementowy \{x_1,\ldots,x_n\}, wyznaczyć liczbę słów długości m nad tym alfabetem.

Nietrudno zauważyć, że odpowiedzią jest liczba 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 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 xx^{-1} jest równe słowu yy^{-1}, a oba są równe słowu pustemu - elementowi neutralnemu grupy, dla dowolnych generatorów x,y. W różnych grupach różne słowa bywają utożsamiane. Na przykład w grupach abelowych słowo aba^{-1}b^{-1} jest równe słowu pustemu, a w grupie izometrii n-kąta foremnego słowo so^ns jest równe słowu (o^{-1})^n, gdzie o oznacza obrót o kąt 2\pi/n a 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, X, ma n elementow. Oznaczmy 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 X\cup X^{-1} będziemy oznaczać X_m.

Wówczas

|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

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

stąd grube naiwne szacowanie.

GRUPA WOLNA SKOŃCZENIE GENEROWANA.

Niech A_m oznacza liczbę słów długości m w grupie wolnej o n generatorach F_n.

Mamy:

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

|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}

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

Analogicznie

|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 n generatorach.

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

Można jednak znacznie prościej.

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

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

Oznaczmy:

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

Teraz już łatwo wypisać |X_i|. Tak, jak poprzednio oddzielnie dla parzystych i nieparzystych. Mamy:

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

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

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

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

i+\frac b2-1

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

b=4m

zatem wewnętrznych punktów kratowych jest

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

Nas interesuje liczba:

A(m)=b+i=2m^2+2m+1.

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

|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

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

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

Pozostaje uogólnić na przypadek n-wymiarowy...
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Twierdzenie chińskie o resztach  mol_ksiazkowy  0
 Definicja ciągu wg Cauch'ego i twierdzenie o 3 ciagach  pawel.l89  0
 problem z zastosowaniem twierdzenie de L'hospitala  thepunisher92pl  7
 "Odwrócone" twierdzenie Bolzano - Weierstrassa  Hendra  1
 twierdzenie Ptolemeusza  barteksiedem  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl