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