Proof. \(G\) je izomorfna podgrupi \(\mathop{\mathrm{Sym}}(G)\): \[f \colon G \to \mathop{\mathrm{Sym}}(G), \quad f(g) \colon x \mapsto g \cdot x \quad (x \in G).\] Preslikava \(f\) je injektiven homomorfizem. ◻

Proof. Dokažimo le obstoj, enoličnost sledi iz univerzalne lastnosti prosto generiranih grup.

Vpeljimo abecedo \(A = S \cup \hat S\), kjer je \(\hat S = \{ \hat s \mid s \in S \}\) disjunktna kopija množice \(S\) (njeni elementi igrajo vlogo \(s^{-1}\) za \(s \in S\)).

Naj bo \(A^*\) množica vseh zaporedij (besed) simbolov iz \(A\). Ta vsebuje prazno besedo, ki jo označimo z \(\epsilon\). Besede lahko množimo s konkatenacijo: \(x \cdot y = xy\) za \(x,y \in A^*\).

Uvedimo ekvivalenčno relacijo \(\sim\) na \(A^*\) (krajšanje): za vse \(x,y \in A^*\) in \(s \in S\) zahtevajmo \(x s \hat s y \sim xy\) in \(x \hat s s y \sim xy\).

Naj bo \(F(S) = A^*/\sim\). Konkatenacija inducira množenje na \(F(S)\): \([x] \cdot [y] = [xy]\).

\(F(S)\) je grupa: Enota je \([\epsilon]\), inverze izračunamo induktivno z \([s \cdot x]^{-1} = [x]^{-1} \cdot [\hat s]\) in \([\hat s \cdot x]^{-1} = [x]^{-1} \cdot [s]\) za \(s \in S, x \in A^*\). \(\checkmark\)

\(F(S)\) je prosto generirana s \(S\): Imamo naravno preslikavo \(S \to F(S), s \mapsto [s]\). Naj bo \(\varphi \colon S \to G\) neka preslikava za neko grupo \(G\). Potem \(\varphi\) lahko razširimo do homomorfizma \(\bar \varphi \colon F(S) \to G\) induktivno: \(\bar \varphi([s \cdot x]) = \varphi(s) \cdot \bar \varphi([x])\), \(\bar \varphi([\hat s \cdot x]) = \varphi(s)^{-1} \cdot \bar \varphi([x])\) za \(s \in S, x \in A^*\). \(\checkmark\) ◻

Proof. Po univerzalni lastnosti proste grupe dobimo homomorfizem \(\varphi \colon F(S) \to G\). Ker \(S\) generira \(G\), je \(\varphi\) surjektiven. Privzemimo, da \(\varphi\) ni injektiven. Naj bo \(1 \neq w = s_1 \cdots s_n \in F(S)\) (\(s_i \in S \cup S^{-1}\)) okrajšana beseda minimalne dolžine, ki je v jedru \(\ker \varphi\). Ločimo več primerov glede na dolžino besede.

Če je \(n = 1\):

V tem primeru je \(w = s_1 \in S \cup S^{-1}\). Toda \(\varphi|_{S}\) je injektivna. Protislovje s predpostavko \(\varphi(w) = 1\).

Če je \(n = 2\):

V tem primeru je \(w = s_1 s_2\) in velja \(\varphi(w) = 1\). Torej \(1 = \varphi(s_1 s_2) = s_1 \cdot s_2 \in G\). Torej je \(s_1 \neq s_2^{-1}\) v \(F(S)\),¹¹ medtem ko je \(s_1 = s_2^{-1}\) v \(G\). Od tod sledi \(s_1 \in S \cap S^{-1} \subseteq G\). Protislovje s predpostavko \(S \cap S^{-1} = \emptyset\).

Če je \(n \geq 3\):

Zaporedje elementov \(1, s_1, s_1 s_2, \dots, s_1 s_2 \cdots s_n\) tvori cikel v \(\mathop{\mathrm{Cay}}(G,S)\), saj je \(s_1 s_2 \cdots s_n = \varphi(w) = 1 \in G\). Vsa vozlišča tega cikla so različna med sabo: če je namreč \(s_1 \cdots s_i = s_1 \cdots s_j \in G\) za nek \(i < j\), potem je beseda \(w^\prime = s_1 s_2 \cdots s_i s_{j+1} \cdots s_n \in F(S)\) krajše dolžine kot \(w\), hkrati pa velja \(\varphi(w^\prime) = s_1 s_2 \cdots s_i s_{j+1} \cdots s_n = s_1 s_2 \cdots s_j s_{j+1} \cdots s_n = \varphi(w) = 1\). Protislovje z minimalnostjo dolžine \(w \in \ker \varphi\). Tako res dobimo \(n\)-cikel v grafu \(\mathop{\mathrm{Cay}}(G,S)\). Protislovje s predpostavko, da je \(\mathop{\mathrm{Cay}}(G,S)\) drevo.

 ◻

Proof. Cayleyjevo delovanje je vselej prosto na vozliščih. Preveriti moramo le, kaj se dogaja s povezavami.

Če obstaja \(s \in S, s^2 = 1\):

V tem primeru \(s\) deluje na povezavi \(\{ 1, s \}\) tako, da jo preslika v povezavo \(\{ s, s^2 \} = \{ 1, s \}\). Torej \(s\) fiksira to povezavo, zato delovanje ni prosto. \(\checkmark\)

Če delovanje ni prosto:

Naj bo \(g \in G - \{ 1 \}\), ki fiksira povezavo \(\{ u, v \}\). Velja torej \(\{ u, v \} = \{ g u, g v \}\). Ker je \(u \sim v\), lahko pišemo \(v = u s\) za nek \(s \in S \cup S^{-1} - \{ 1 \}\). Ločimo dva primera.

Če je \(u = gu\) in \(v = gv\):

Sledi \(g = 1\). Protislovje.

Če je \(u = gv\) in \(v = gu\):

V tem primeru velja \(u = gv = gus = vs = u s^2\), zato sledi \(s^2 = 1\). \(\checkmark\)

 ◻

Proof. \(A_x\) je dobro definirana: Če je \(g_1 G_x = g_2 G_x\), potem \(g_2^{-1} g_1 \in G_x\), zato \(g_2^{-1} g_1 .x = x\), torej \(g_2.x = g_1.x\). \(\checkmark\)

\(A_x\) je surjektivna: Velja po definiciji. \(\checkmark\)

\(A_x\) je injektivna: Če je \(g_1.x = g_2.x\), potem \(g_2^{-1}g_1.x=x\), zato \(g_2^{-1}g_1 \in G_x\), torej je \(g_2G_x = g_1G_x\). \(\checkmark\)

Za zadnji del opazujmo množico \(F = \{ (g, x) \mid g \in G, \ x \in X,\ g.x = x \} \subseteq G \times X\). Velja \(|F| = \sum_{g \in G} |X^g| = \sum_{x \in X} |G_x| = \sum_{x \in X} |G|/|G.x| = |G| \sum_{x \in X} 1/|G.x| = |G| \sum_{Y \in G \backslash X} \sum_{x \in Y} 1/|Y| = |G| \cdot |G \backslash X|\). \(\checkmark\) ◻

Proof. Definirajmo preslikavo \(\varphi \colon G \to V, g \mapsto g.x\). Zaradi predpostavke o tranzitivnost in prostosti je \(\varphi\) bijekcija. Torej lahko identificiramo \(G\) in \(V\) prek \(\varphi\).

\(S\) generira \(G\): Naj bo \(g \in G\). Opazujmo neko pot v grafu \(X\) od \(x\) do \(g.x\): \[x_0 = 0, \ x_1 = g_1.x, \ x_2 = g_2.x, \dots, x_n = g_n.x = g.x.\] za neke \(g_i \in G\). Naj bo \(s_j = g_j^{-1} \cdot g_{j+1}\).

Premislimo, da za vsak \(j\) velja \(s_j \in S\): vemo \(x_j \sim x_{j+1}\), zato je \(g_j^{-1}.x_j \sim g_j^{-1}.x_{j+1}\), kar se poenostavi v \(x \sim g_j^{-1}g_{j+1}.x \sim s_j.x\), torej je res \(x \sim s_j.x\).

Zdaj velja \(g = g_n = g_0 g_0^{-1} g_1 g_1^{-1} \cdots g_{n-1}^{-1} g_n = g_0 s_1 s_2 \cdots s_{n-1} = s_1 \cdots s_{n-1}\). Torej res \(S\) generira \(G\). \(\checkmark\)

\(X \cong \mathop{\mathrm{Cay}}(G,S)\): Imamo že bijekcijo med vozlišči obeh grafov, \(\varphi \colon G \to V\). Za \(g,h \in G\) velja \(\varphi(g) \sim \varphi(h)\), če in samo če je \(g.x \sim h.x\), kar je enakovredno \(x \sim g^{-1}h.x\), torej \(g^{-1}h \in S\), to pa je nazadnje enakovredno \(g \sim h\) v \(\mathop{\mathrm{Cay}}(G,S)\). Torej \(\varphi\) inducira izomorfizem grafov \(X\) in \(\mathop{\mathrm{Cay}}(G,S)\). \(\checkmark\) ◻

Proof. Naj \(G\) deluje na grafu \(X\). Naj bo \(\mathcal{T}\) množica vseh poddreves v \(X\), ki vsebujejo največ eno vozlišče iz vsake \(G\)-orbite. Velja \(\mathcal{T} \neq \emptyset\), na primer \(\mathcal{T}\) vsebuje drevo iz enega samega vozlišča. Množica \(\mathcal{T}\) je delno urejena z relacijo inkluzije. Vsaka veriga v \(\mathcal{T}\) ima zgornjo mejo (lahko vzamemo kar unijo dreves v verigi). Po Zornovi lemi zato obstaja maksimalen element v \(\mathcal{T}\): izberimo enega in mu recimo \(T\).

\(T\) je vpeto drevo delovanja: Recimo, da ni. Torej obstaja \(v \in V(X)\), da je \(T \cap G.v = \emptyset\). Premislimo, da obstaja taka izbira \(v\), da je \(v\) soseden nekemu vozlišču v \(T\). Res, ker je \(X\) povezan, obstaja pot \(p\) od nekega vozlišča \(u \in T\) do \(v\). Naj bo \(v^\prime\) prvo vozlišče na \(p\), ki ni v \(T\).

Če \(T \cap G.v^\prime = \emptyset\):

V tem primeru lahko \(v\) nadomestimo z \(v^\prime\). \(\checkmark\)

Sicer:

V tem primeru obstaja \(g \in G\), da je \(g.v^\prime \in T\). Naj bo \(p^\prime\) odsek poti \(p\) od \(v^\prime\) do \(v\). Torej je \(g.p^\prime\) pot od \(g.v^\prime \in T\) do \(g.v\), pri čemer velja \(G.g.v \cap T = G.v \cap T = \emptyset\) po izbiri \(v\). Torej je \(g.p^\prime\) krajša pot kot \(p\) z enako lastnostjo (povezuje \(T\) z vozliščem, katerega orbita ne seka \(T\)). Postopek ponavljamo in na koncu dobimo vozlišče z želeno lastnostjo. \(\checkmark\)

K drevesu \(T\) dodajmo izbrano vozlišče \(v\) in povezavo, ki ga povezuje z drevesom \(T\). Dobimo novo drevo v \(\mathcal{T}\), ki vsebuje \(T\), kar je protislovje z maksimalnostjo drevesa \(T \in \mathcal{T}\). Torej je res \(T\) vpeto drevo delovanja. \(\checkmark\) ◻

Dokaz izreka (prosta \(\Leftrightarrow\) prosto na drevesu). Naj \(G\) deluje prosto na drevesu \(T\). Dokazujemo, da je \(G\) prosta grupa.

Naj bo \(T^\prime\) vpeto drevo delovanja \(G\) na \(T\). Kontraktirajmo drevo \(T^\prime\) v vozlišče, prav tako naredimo z orbitami \(T^\prime\). Na ta način dobimo nov graf \(X\) z:

• vozlišči \(V = \{ g.T^\prime \mid g \in G \}\),

• povezavami \(E = \{ \{ g.T^\prime, h.T^\prime \} \mid g,h \in G, \ \text{$g.T^\prime$ in $h.T^\prime$ sta sosednji} \}\),

kjer sosednost \(g.T^\prime\) in \(h.T^\prime\) pomeni, da sta ti dve drevesi različni in da obstajata \(u \in g.T^\prime\), \(v \in h.T^\prime\) z \(u \sim_T v\).

Za graf \(X\) veljajo naslednje lastnosti:

• Za vsaka različna elementa \(g, h \in G\) je \(g.T^\prime \cap h.T^\prime = \emptyset\). Ta lastnost sledi iz prostosti delovanja in izbire \(T^\prime\).

• Če sta \(g.T^\prime, h.T^\prime\) sosednji, potem med njima obstaja natako ena povezava v \(T\). Ta lastnost velja, ker v \(T\) ni ciklov.

• Graf \(X\) je drevo. Cikel v \(X\) bi nam namreč porodil cikel v \(T\).

• Grupa \(G\) inducirano deluje na \(X\), to delovanje je tranzitivno in prosto na vozliščih \(X\).

Iz zadnje lastnosti po dokazani trditvi sledi, da obstaja \(\tilde S \subseteq G\), da je \(X \cong \mathop{\mathrm{Cay}}(G,\tilde S)\).

\(G\) nima elementov reda \(2\): Če je \(s \in G\) reda \(2\), potem je \(\langle s \rangle\) končna grupa, ki prosto deluje na drevesu \(T\). To ni mogoče, saj ima vsako delovanje končne grupe na drevesu globalno fiksno točko (glej vaje). \(\checkmark\)

Ker v \(\tilde S\) ni elementov reda \(2\), lahko izberemo \(S \subseteq \tilde S\), za katero velja \(S \cap S^{-1} = \emptyset\) in \(\langle S \rangle = \langle \tilde S \rangle = G\). Še vedno je \(\mathop{\mathrm{Cay}}(G,S)\) drevo. Iz trditve v razdelku o Cayleyjevem delovanju zdaj sledi, da \(S\) prosto generira \(G\). ◻

Proof. Naj bo \(F\) prosta grupa in \(G \leq F\). Grupa \(F\) prosto deluje na drevesu, zato tudi \(G\) prosto deluje na drevesu. Iz zadnjega izreka sledi, da je \(G\) prosta. ◻

Proof. Naj \(S\) prosto generira \(F\). Naj bo \(T = \mathop{\mathrm{Cay}}(F,S)\) drevo, na katerem \(F\) deluje prosto s Cayleyjevem delovanjem.

Opazujmo zožitev tega delovanja na podgrupo \(G \leq F\). Naj bo \(T^\prime\) vpeto drevo delovanja \(G\) na \(T\). Za \(f \in V(T) = F\) je orbita \(G.f\) ravno desni odsek \(G\) v \(F\), torej je število vozlišč v \(T^\prime\) enako \(|F:G| = k\).

Po kontrakciji poddreves \(g.T^\prime\) za \(g \in G\) dobimo¹⁵ drevo \(X \cong \mathop{\mathrm{Cay}}(G,S^\prime)\) za nek \(S^\prime \subseteq G\) in grupa \(G\) je prosta ranga \(|S^\prime|\). Pri tem je \(|S^\prime|\) enako polovici¹⁶ števila povezav od \(T^\prime\) do \(g.T^\prime\) za vse \(g \in G\).

Jasno velja \[\sum_{v \in V(T^\prime)} \deg_T(v) = |V(T^\prime)| \cdot 2n = k \cdot 2n.\] Po drugi strani pa lahko zadnjo vsoto izračunamo tako, da najprej upoštevamo notranje povezave v \(T^\prime\), ki jih je natanko \(2 \cdot (k-1)\) (vsako od \(k-1\) povezav v \(T^\prime\) preštejemo dvakrat), in za tem še povezave iz \(T^\prime\) do drugih \(g.T^\prime\) za \(g \in G\), ki jih je natanko \(2 \cdot |S^\prime|\). Sledi \[|S^\prime| = \frac12 (2kn - 2(k-1)) = k(n-1) + 1.\] ◻

Proof. Sestavimo surjektiven homomorfizem \(\varphi \colon F_r \to S_n = \langle (1 \ 2), (1 \ 2 \ \cdots \ n) \rangle\). Jedro \(\ker \varphi\) je prosta grupa ranga \(n! \cdot (r-1) + 1\), kar raste čez vse meje ko gre \(n \to \infty\). Hkrati \(\ker \varphi\) vsebuje proste grupe vsakega ranga manjšega od \(n! (r - 1) + 1\). ◻

Proof. Naj bo \(G\) končno generirana grupa in naj bo \(H \leq G\) podgrupa končnega indeksa. Naj bo \(G = \langle S \rangle\), \(|S| < \infty\). Naj bo \(\pi \colon F(S) \to G\) surjektiven homomorfizem. Naj bo \(H^\prime = \pi^{-1}(H) \leq F(S)\). Velja \(|F(S) : H^\prime| = |F(S)/\ker \pi : H^\prime/\ker \pi| = |G : H| < \infty\). Torej je \(H^\prime\) končno generirana prosta grupa. Njena slika \(H = \pi(H^\prime)\) je zato tudi končno generirana. ◻

Proof. Naj bo \(F = F(\{ \alpha, \beta \})\) prosto generirana s simboloma \(\alpha, \beta\). Po univerzalni lastnosti dobimo homomorfizem \(\varphi \colon F \to G\), \(\alpha \mapsto a, \beta \mapsto b\). Predpostavimo, da \(\varphi\) ni injektiven. Naj bo torej \(w \in F\) okrajšana beseda v \(\ker \varphi\). Obravnavajmo štiri možnosti glede na začetek in konec besede \(w\).

\(w\) se začne in konča z \(\alpha\):

V tem primeru je \(w = \alpha^{n_0} \beta^{m_1} \alpha^{n_1} \cdots \beta^{m_k} \alpha^{n_k}\) za \(n_i, m_i \in \mathbb{Z}\backslash \{ 0 \}\). Jasno je \(\varphi(w).B = B\), po drugi strani pa po pingpong pogoju velja \[\varphi(w).B = a^{n_0} b^{m_1} a^{n_1} \cdots b^{m_k} a^{n_k}.B \subseteq a^{n_0} b^{m_1} a^{n_1} \cdots b^{m_k}.A \subseteq \cdots \subseteq a^{n_0}.B \subseteq A.\] Protislovje s predpostavko \(B \not\subseteq A\).

\(w\) se začne in konča z \(\beta\):

V tem primeru je konjugirana beseda \(\alpha w \alpha^{-1}\) okrajšana beseda v jedru \(\ker \varphi\), ki je enake oblike kot v prvem primeru. Protislovje.

\(w\) se začne z \(\alpha\) in konča z \(\beta\):

V tem primeru je \(w = \alpha^n w^\prime \beta^m\) za \(n,m \in \mathbb{Z}\backslash \{ 0 \}\). Tako je konjugirana beseda \(\alpha^k w \alpha^{-k} = \alpha^{k+n} w^\prime \beta^m \alpha^{-k}\) okrajšana beseda v \(\ker \varphi\), ki je enake oblike kot v prvem primeru. Protislovje.

\(w\) se začne z \(\beta\) in konča z \(\alpha\):

V tem primeru je \(w^{-1}\) okrajšana beseda v \(\ker \varphi\), ki je kot v tretjem primeru. Protislovje.

 ◻

Proof. Predpostavimo, da je \(G\) rešljiva in da njeno rešljivost opazi veriga \(G = G_1 \unrhd G_2 \unrhd \cdots \unrhd G_n = 1\). Velja torej \([G_i, G_i] \leq G_{i+1}\) za vsak \(i\). Sledi \(G^{(1)} = G_1\), \(G^{(2)} = [G_1, G_1] \leq G_2\), \(G^{(3)} = [G^{(2)}, G^{(2)}] \leq [G_2, G_2] \leq G_3\), …Induktivno sklepamo, da za vsak \(i\) velja \(G^{(i)} \leq G_i\). Zato mora veljati tudi \(G^{(n)} = 1\). ◻

Proof. Naj bo \(G\) rešljiva grupa z \(G^{(n)} = 1\).

Za podgrupo \(H \leq G\) preprost induktiven argument dokaže \(H^{(i)} \leq G^{(i)}\) za vsak \(i\). V posebnem sledi \(H^{(n)} = 1\). \(\checkmark\)

Za \(N \unlhd G\) velja \((G/N)^{(n)} = G^{(n)}N/N = 1\). \(\checkmark\)

Naj bo nazadnje \(K\) še ena rešljiva grupa z \(K^{(m)} = 1\). Naj bo \(E\) razširitev \(K\) z \(G\). Tedaj velja \(E^{(m)}G/G = (E/G)^{(m)} = K^m = 1\), zato je \(E^{(m)} \leq G\). Od tod induktivno sledi \(E^{(m+i)} \leq G^{(i)}\) za vsak \(i\), zato v posebnem velja \(E^{(m+n)} = 1\). \(\checkmark\) ◻

Proof. 1. \(\Rightarrow\) 2.: Imejmo verigo \(G_1 < G_2 < \cdots\) v \(G\). Tedaj ima množica \(\{ G_1, G_2, \dots \}\) po predpostavki maksimalen element. Torej je veriga končna. \(\checkmark\)

2. \(\Rightarrow\) 1.: Uporabimo Zornovo lemo. Ker ima vsaka veriga zgornjo mejo (namreč, zadnji člen verige), obstaja maksimalen element katerekoli množice podgrup. \(\checkmark\)

2. \(\Rightarrow\) 3.: Naj bo \(H \leq G\). Izberimo neko množico generatorjev \(S\) grupe \(H\). Naj bo \(s_1 \in S\) in \(H_1 = \langle s_1 \rangle\). Če je \(H_1 = H\), je \(H\) končno generirana. Predpostavimo zdaj \(H_1 < H\). Naj bo \(s_2 \in S \backslash H_1\) in \(H_2 = \langle s_1, s_2 \rangle\). Če je \(H_2 = H\), je \(H\) končno generirana. Predpostavimo zdaj \(H_1 < H_2 < H\). Postopek nadaljujemo in dobimo naraščajočo verigo podgrup v \(H\). Ker je vsaka veriga v \(G\) končna, se mora ta postopek ustaviti. Torej obstaja \(i \in \mathbb{N}\), da je \(H_i = H\). S tem je \(H = \langle s_1, s_2, \dots, s_i \rangle\). \(\checkmark\)

3. \(\Rightarrow\) 2.: Naj bo \(G_1 < G_2 < \cdots\) neskončna veriga v \(G\). Naj bo \(H = \bigcup_{i \in \mathbb{N}} G_i\). Velja \(H \leq G\), zato je po predpostavki \(H = \langle h_1, \cdots, h_n \rangle\) za neke \(h_i \in H\). Za vsak generator \(h_i\) obstaja člen verige, ki ga vsebuje. Torej obstaja člen verige, recimo \(G_k\), ki vsebuje vse \(h_1, \dots, h_n\). Torej \(G_k \geq H\), zato je \(G_i \leq G_k\) za vsak \(i \in \mathbb{N}\). Veriga je torej končna. Protislovje. \(\checkmark\) ◻

Proof. (\(\Leftarrow\)): Ciklične grupe so noetherske. Tako je najprej \(G_{n-1}\) noetherska. Ker je \(G_{n-2}\) razširitev ciklične grupe \(G_{n-2}/G_{n-1}\) z grupo \(G_{n-1}\), je tudi \(G_{n-2}\) noetherska. Induktivno na ta način sklepamo, da je \(G_i\) noetherska za vsak \(i\). V posebnem je \(G = G_1\) noetherska. \(\checkmark\)

(\(\Rightarrow\)): Bodi \(G\) rešljiva z verigo \(G = G_1 \unrhd G_2 \unrhd \cdots \unrhd G_n = 1\) z abelovimi kvocienti. Ker je \(G\) noetherska, je noetherski tudi vsak člen verige \(G_i\), zato je \(G_i/G_{i+1}\) noetherska, torej je nazadnje \(G_i/G_{i+1}\) končno generirana abelova grupa. Zapišemo jo lahko kot direktno vsoto cikličnih grup: \[G_i/G_{i+1} = C_1 \oplus C_2 \oplus \cdots \oplus C_k.\] Naj bo \(H_\ell = \left( \bigoplus_{j = 1}^\ell C_j \right)G_{i+1} \leq G_i\) delna vsota cikličnih podgrup, dvignjena v grupo \(G_i\). Torej imamo verigo podgrup \[G_{i+1} = H_0 \leq H_1 \leq \cdots \leq H_k = G_i\] s kvocienti \(H_{j+1}/H_j \cong C_{j+1}\). Na ta način lahko v grupi \(G\) originalno verigo med vsakima členoma \(G_{i+1} \unlhd G_i\) pofinimo z vmesnimi podgrupami \(H_j\), tako da so v novi verigi vsi kvocienti ciklični. Torej je \(G\) policiklična. \(\checkmark\) ◻

Proof. Pofinimo \(H\)-verigo s pomočjo \(G\)-verige. Najprej velja \[G = H_1 \unrhd H_2 G_2 \unrhd H_2 G_3 \unrhd \cdots \unrhd H_2 G_n = H_2,\] za tem imamo verigo \[H_2 \unrhd H_3 (G_2 \cap H_2) \unrhd H_3 (G_3 \cap H_2) \unrhd \cdots \unrhd H_3 (G_n \cap H_2) = H_3,\] med splošnima členoma \(H_i \unrhd H_{i+1}\) pa imamo verigo \[H_i \unrhd H_{i+1}(G_2 \cap H_i) \unrhd H_{i+1}(G_3 \cap H_i) \unrhd \cdots \unrhd H_{i+1}(G_n \cap H_i) = H_{i+1}.\] Označimo \(K_{i,j} = H_{i+1}(G_j \cap H_i)\). Tako dobimo \(K\)-verigo, \[G = K_{1,1} \unrhd K_{1,2} \unrhd \cdots \unrhd K_{m,n} = 1,\] ki je pofinitev \(H\)-verige, saj velja \(K_{i,1} = H_i\).

Analogno lahko pofinimo \(G\)-verigo s pomočjo \(H\)-verige. Naj bo \(L_{j,i} = G_{j+1}(H_i \cap G_j)\). Tako dobimo \(L\)-verigo, \[G = L_{1,1} \unrhd L_{1,2} \unrhd \cdots \unrhd L_{n,m} = 1,\] ki je pofinitev \(G\)-verige, saj velja \(L_{j,1} = G_j\).

Obe novi verigi imata enako število členov (\(n\cdot m\)). Za kvociente \(K\)-verige velja \[K_{i,j}/K_{i,j+1} = \frac{H_{i+1}(G_j \cap H_i)}{H_{i+1}(G_{j+1} \cap H_i)} \cong \frac{H_{i+1}(G_j \cap H_i) / H_{i+1}}{H_{i+1}(G_{j+1} \cap H_i) / H_{i+1}}.\] Zdaj uporabimo drugi izrek o izomorfizmu¹⁸, od koder sledi \[K_{i,j}/K_{i,j+1} \cong \frac{(G_j \cap H_i) / (G_j \cap H_{i+1})}{(G_{j+1} \cap H_i) (G_j \cap H_{i+1}) / (G_j \cap H_{i+1})} \cong \frac{G_j \cap H_i}{(G_{j+1} \cap H_i) (G_j \cap H_{i+1})}.\] Zadnja grupa je simetrična glede na menjavo \(G\)-vrste in \(H\)-vrste. Torej bi do enakega rezultata prišli z analizo kvocientov \(L\)-vrste. Od tod sledi \[K_{i,j}/K_{i,j+1} \cong L_{j,i} / L_{j, i + 1}.\] Dokaz je s tem zaključen. ◻

Proof. Po lemi imata vsaki dve verigi pofinitev z enakimi cikličnimi kvocienti (do permutacije natančno). Zato je trditev dovolj dokazati za primer, ko je prva veriga pofinitev druge. Tako pofinitev dobimo z zaporednim vstavljanjem enega novega člena med dva obstoječa: \(G_i < H < G_{i-1}\). Ločimo dva primera.

Če je \(|G_{i-1}/G_i| < \infty\):

V tem primeru ima nova veriga (z dodanim členom \(H\)) enako število neskončnih kvocientov. \(\checkmark\)

Če je \(G_{i-1}/G_i \cong \mathbb{Z}\):

V tem primeru je nujno \(H/G_i \cong \mathbb{Z}\) in \(|G_{i-1}/H| < \infty\). Torej je število neskončnih kvocientov v stari in novi verigi zopet enako. \(\checkmark\)

 ◻

Proof. Indukcija na Hirschovo dolžino. Naj bo \(G = G_1 \unrhd G_2 \unrhd \cdots \unrhd G_n = 1\). Naj bo \(G_i/G_{i+1}\) prvi neskončni kvocient te vrste. Torej je \(|G:G_i| < \infty\). Dovolj bo zato dokazati, da je policiklična grupa \(G_i\) virtualno brez torzije. Brez škode za splošnost lahko torej privzamemo \(i = 1\).

Ker velja \(h(G_2) = h(G) - 1\), po indukciji obstaja \(H \leq G_2\), za katero je \(|G_2 : H| < \infty\) in \(H\) je brez torzije. Privzamemo lahko, da je \(H \unlhd G\).¹⁹ Naj bo \(G/G_2 = \langle x G_2 \rangle\) za nek \(x \in G\). Naj bo \(K = \langle x,H \rangle\).

\(K\) je končnega indeksa v \(G\): Velja \(G = K G_2\), zato je \(|G:K| = |G_2K : K| = |G_2 : G_2 \cap K| \leq |G_2 : H| < \infty\).

\(K\) je brez torzije: Vsak element \(k \in K\) lahko zapišemo kot \(k = x^a h\) za neka \(a \in \mathbb{Z}\) in \(h \in H\). Če je \(k\) torzijski element, potem je \(k^m = 1\), od koder sledi \(H = k^m H = (kH)^m = x^{am} H\), zato je \(x^{am} \in H \leq G_2\). V tem primeru je \(xG_2\) reda največ \(am\) v \(G/G_2 \cong \mathbb{Z}\). Od tod sledi \(a = 0\). Tako je \(k = h \in H\). Ker je \(H\) brez torzije, je slednje sprto s predpostavko, da je \(k\) torzijski element. \(\checkmark\) ◻

Proof. Grupa \([H,K]\) vsebuje vse komutatorje \([x,y]\) za \(x \in X, y \in Y\), zato vsebuje tudi podgrupo edinko, generirano s temi elementi: \(N := \langle\langle[x,y] \mid x \in X, y \in Y \rangle\rangle\). Velja tudi obratna inkluzija. V kvocientu \([H,K]/N\) namreč odsek \(xN\) komutira z \(yN\) za \(x \in X, y \in Y\), zato v tem kvocientu celotna podgrupa \(HN/N\) komutira s podgrupo \(KN/N\). Od tod sledi \([H,K]N = N\), torej je res tudi \([H,K] \leq N\). ◻

Proof. Indukcija na \(i\).

\(i = 1\):

\(\checkmark\)

\(i-1 \to i\):

Velja \(\gamma_i(G) = [\gamma_{i-1}(G), G]\), zato iz zadnje leme in indukcije sledi \[\gamma_i(G) = \langle\langle[x_1, x_2, \dots, x_{i-1}, x_i] \mid x_1, \dots, x_i \in G \rangle\rangle.\] Konjugat komutatorja uteži \(i\) je komutator uteži \(i\), velja namreč \([x_1, \dots, x_i]^g = [x_1^g, \dots, x_i^g]\) za \(g \in G\). Tako je podgrupa, generirana s komutatorji uteži \(i\), edinka v \(G\). S tem je dokaz zaključen. \(\checkmark\)

 ◻

Proof. Dokažimo, da je za vsak \(i\) grupa \(\gamma_i(G)/\gamma_{i+1}(G)\) končna. Od tod bo sledilo, da je tudi \(G\) končna. Naj bo \(G= \langle X \rangle\) z lastnostjo \(x^N = 1\) za vse \(x \in X\). Grupa \(\gamma_i(G)/\gamma_{i+1}(G)\) je generirana s komutatorji uteži \(i\) z vnosi iz množice \(X \gamma_{i+1}(G)/\gamma_{i+1}(G)\). Za vsak tak komutator \([x_1, \dots, x_i] \gamma_{i+1}\) velja \[\left( [x_1, \dots, x_i] \gamma_{i+1} \right)^N = [x_1, \dots, x_{i-1}, x_i^N] \gamma_{i+1}(G) = \gamma_{i+1}(G),\] kjer smo v prvi enakosti uporabili drugo komutatorsko identiteto. Tako je abelova grupa \(\gamma_i(G)/\gamma_{i+1}(G)\) generirana s končno mnogo elementi reda kvečjemu \(N\), torej je končna. ◻

Proof. Imejmo ekvivalentni razširitvi \(N \xrightarrow{\iota} G \xrightarrow{\pi} Q\) in \(N \xrightarrow{\bar \iota} \bar G \xrightarrow{\bar \pi} Q\) z izomorfizmom \(\beta \colon G \to \bar G\) in s pripadajočima delovanjema \(\chi, \bar \chi \colon Q \to \mathop{\mathrm{Aut}}(N)\). Izberimo prerezno funkcijo \(\tau \colon Q \to G\) za \(\pi\). Tedaj je \(\beta \circ \tau \colon Q \to \bar G\) prerezna funkcija za \(\bar \pi\). Za \(n \in N\) in \(q \in Q\) velja \[\chi(q)(n) = {}^{\tau(q)} n\] in \[\bar \chi(q)(n) = {}^{\beta(\tau(q))} n = \beta(\tau(q)) n \beta(\tau(q))^{-1}.\] Ker je \(\beta |_N = \mathop{\mathrm{id}}_N\), je zadnji element enak \[\beta(\tau(q)) \beta(n) \beta(\tau(q))^{-1} = \beta({}^{\tau(q)} n) = \beta(\chi(q)(n)) = \chi(q)(n).\] Tako je res \(\chi = \bar \chi\). ◻

Proof. Za \(\tau\) lahko vzamemo funkcijo \(q \mapsto (1,q)\) za \(q \in Q\). ◻

Proof. Naj bo \(G = \langle X \rangle = \langle Y \rangle\) za neki končni množici \(X, Y\). Definirajmo \[A = \max \left\{ \max \{ \ell_Y(x) \mid x \in X \}, \max \{ \ell_X(y) \mid y \in Y \} \right\}.\] Torej za \(g \in G\) velja \(\ell_X(g) \leq A \cdot \ell_Y(g)\) in \(\ell_Y(g) \leq A \cdot \ell_X(g)\). Od tod sledi \(\sigma_{G, Y}(n) \leq \sigma_{G,X}(An)\) in \(\sigma_{G,X}(n) \leq \sigma_{G,Y}(An)\), torej je \(\sigma_{G,Y} \sim \sigma_{G,X}\). Enako velja za \(\beta_{G,X}\), \(\beta_{G,Y}\). ◻

Proof. (\(\Rightarrow\)): Število \(\beta_{G,S}(n)\) izračunamo tako, da naštejemo vse besede dolžine kvečjemu \(n\) s črkami \(S \cup S^{-1}\) in z danim algoritmom za reševanje besednega problema preverimo, katere med njimi so enake. \(\checkmark\)

(\(\Leftarrow\)): Grupo \(G\) predstavimo kot \(G = F(S)/\langle\langle R \rangle\rangle\). Elementi grupe \(\langle\langle R \rangle\rangle\) so produkti konjugatov relacij v \(R\) in njihovih inverzov. Teh elementov je števno mnogo in jih lahko uredimo v vrsto. Ko beremo to vrsto, torej naštevamo ravno vse besede v \(F(S)\), ki so trivialne v \(G\).

Opazujmo besedo \(w \in (S \cup S^{-1})^*\). Ločimo dva primera.

Če je \(w=1\) v \(G\):

V tem primeru bomo z naštevanjem elementov \(\langle\langle R \rangle\rangle\) slej kot prej v seznamu naleteli na \(w\) in s tem dobili zagotovilo, da je res \(w = 1\) v \(G\).

Če je \(w \neq 1\) v \(G\):

V tem primeru se beseda \(w\) nikdar ne pojavi v vrsti \(\langle\langle R \rangle\rangle\). Z naštevanjem elementov vrste se torej ne bomo mogli v končnem času²⁸ odločiti, ali je \(w \neq 1\).

Če je \(w = 1\) v \(G\), potem je torej postopek naštevanja besed iz \(\langle\langle R \rangle\rangle\) algoritem, ki ugotovi, da je res \(w = 1\) v \(G\). Če je \(w \neq 1\), pa ta postopek ne deluje dobro in ga moramo še malo prilagoditi. Za to uporabimo izračunljivo funkcijo rasti \(\beta_{G,S}\).

Naj bo \(n\) dolžina besede \(w \in (S \cup S^{-1})^*\). Najprej sestavimo množico \(\mathcal{B}\) vseh besed dolžine kvečjemu \(n\) v \(S \cup S^{-1}\). Po tem začnemo postopek naštevanja elementov \(\langle\langle R \rangle\rangle\). Če sta kakšna dva elementa \(x,y\) množice \(\mathcal{B}\) enaka, potem bomo to opazili z naštevanjem elementov \(\langle\langle R \rangle\rangle\), saj bomo slej kot prej naleteli na element \(x y^{-1}\). Torej bomo z naštevanjem eleemntov \(\langle\langle R \rangle\rangle\) slej kot prej (v končnem času) identificirali dovolj elementov množice \(\mathcal{B}\), da nam bo ostalo natanko \(\beta_{G,S}(n)\) besed, ki so vse različne v \(G\). Po tem z naštevanjem dodatnih elementov \(\langle\langle R \rangle\rangle\) ne bomo več našli nobene enakosti med besedami, saj bi sicer dobili manj kot \(\beta_{G,S}(n)\) elementov dolžine kvečjemu \(n\) v \(G\). Na tej točki zato pogledamo, kaj se je pri postopku zgodilo z besedo \(w \in \mathcal{B}\). Če smo kadarkoli tekom postopka identificirali \(w\) s trivialno besedo, potem je seveda \(w = 1\) v \(G\). Če pa do te zadnje točke besede \(w\) nismo identificirali s trivialno besedo \(1\), potem imamo zagotovilo, da velja \(w \neq 1\) v \(G\). ◻

Proof. Označimo limito v lemi z \(L\). Ker je \(\beta_{G,S}(n) \geq \sigma_{G,S}(n)\), je jasno \(L \geq \omega_S(G)\). Za obratno neenakost izberimo poljuben \(\epsilon > 0\). Tedaj velja \(\sigma_{G,S}(n) \leq (\omega_S(G) + \epsilon)^n\) za vse dovolj velike \(n\), od koder sledi \(\beta_{G,S}(n) \leq C + n \cdot (\omega_S(G) + \varepsilon)^n\) za neko konstanto \(C\) in za vse \(n \in \mathbb{N}\). Tako dobimo \(L \leq \omega_S(G) + \varepsilon\). Ker je bil \(\varepsilon\) poljuben, je dokaz zaključen. ◻

Proof. Naj bo \(G = \langle S \rangle, H = \langle T \rangle\). Naj bo \(C = \max \{ \ell_S(t) \mid t \in T \}\). Tedaj je \(\beta_{H,T}(n) \leq \beta_{G,S}(Cn)\). Očitno je tudi \(\beta_{G/N, SN/N}(n) \leq \beta_{G,S}(n)\). Trditev sledi. ◻

Proof. Rastne funkcije obravnavajmo le do ekvivalence natančno. Pišimo jih zato kar kot \(\beta_G, \beta_H, \beta_{G/N}\). Vemo že \(\beta_H, \beta_{G/N} \preceq \beta_G\). Dokaz trditve sloni na naslednjih dveh pomožnih trditvah.

\(\beta_G \preceq \beta_H\): Označimo \(C = \max \{ \ell_S(r) \mid r \in R \}\). Naj bo \(g \in B_{G,S}(n)\). Pišemo lahko \(g = rh\) za neka \(r \in R\), \(h \in H\). Sledi \(\ell_S(h) \leq \ell_S(g) + \ell_S(r) \leq n + C\). Zato velja tudi \(\ell_U(h) \leq \ell_S(h) \leq n + C\), torej je \(h \in B_{H,U}(n+C)\). Tako smo izpeljali neenakost \(\beta_{G,S}(n) \leq |R| \cdot \beta_{H,U}(n+C) \leq |G:H| \cdot \beta_{H,U}((C+1)n)\). Tako je res \(\beta_G \preceq \beta_H\). \(\checkmark\)

\(\beta_G \preceq \beta_{G/N}:\) Naj bo \(G/N = \langle X \rangle\). Za vsak \(x \in X\) izberimo dvig \(\tilde x \in G\), torej \(x = \tilde x N\). Naj bo \(Y = \{ \tilde x \mid x \in X \} \cup N\). Velja \(G = \langle Y \rangle\). Za vsak \(g \in B_{G,Y}(n)\) velja \(gN \in B_{G/N, Y}(n)\), torej lahko pišemo \(gN = x_1 \cdots x_k\) za nek \(k \leq n\). To pomeni \(g = \tilde x_1 \cdots \tilde x_k n\) za nek \(n \in N\). Tako je \(\beta_{G,Y}(n) \leq \beta_{G/N,X}(n) \cdot |N|\), zato je res \(\beta_G \preceq \beta_{G/N}\). \(\checkmark\)

\(\Omega(H) > 1 \Rightarrow \Omega(G) > 1\): Naj bo \(S \subseteq G\) neka generirajoča množica grupe \(G\). Po drugi pomožni trditvi obstaja \(U \subseteq H\), tako da je \(\langle U \rangle = H\) in za vsak \(h \in H\) velja \(\ell_U(h) \leq \ell_S(h)\). Po konstrukciji množice \(U\) za vsak \(u \in U\) velja \(\ell_S(u) \leq 2 \cdot \max \{ \ell_S(r) \mid r \in R \} + 1\), zato po prvi pomožni trditvi velja \(\ell_S(u) < 2 |G:H| + 1\). Tako velja \(\beta_{H,U}(n) \leq \beta_{G,S}(n \cdot (2|G:H| + 1))\). Hkrati je \(\beta_{H,U}(n) \geq A c^n\), kjer je \(c = \Omega(H) > 1\) odvisna le od \(H\), konstanta \(A\) pa je morda odvisna od \(U\). Od tod izpeljemo, da za vsak \(n \in \mathbb{N}\) velja \[\beta_{G,S}(n \cdot (2 |G:H| + 1)) \geq A c^n,\] zato za neskončno mnogo naravnih števil \(m\) velja \[\beta_{G,S}(m) \geq A c^{\frac{m}{2 |G:H| + 1}}.\] S tem je \(\omega_S(G) \geq c^{\frac{1}{2 |G:H| + 1}}\), kar implicira \(\Omega(G) \geq \Omega(H)^{\frac{1}{2|G:H| + 1}} > 1\). \(\checkmark\) ◻

Proof. Dokažimo le prvi del trditve glede pogrup, drugi del glede kvocientov je mnogo lažji.

Naj bo \(H = \langle T \rangle\), \(G = \langle S \rangle\), privzamemo lahko \(T \subseteq S\). Označimo \(S = \{ s_1, s_2, \dots, s_m \}\). Opazujmo odseke \(H\) v \(G\). Začnemo z odsekom \(s_1 H\); označimo \(x_1 = s_1\), opazujemo torej odsek \(x_1 H\). Ker je \(|G:H| = \infty\), mora vsaj en generator \(s_i\) premakniti \(s_1H\) v nek drugo odsek \(s_i s_1 H\); označimo \(x_2 = s_i s_1\), dobimo torej odsek \(x_2 H\). Postopek generiranja novih odsekov nadaljujemo na ta način, tako dobimo paroma različne odseke \(x_i H\) za \(i \in \mathbb{N}\). Pri tem po konstrukciji velja \(\ell_S(x_i) \leq i\). Tako za vsak \(n \in \mathbb{N}\) dobimo injektivno preslikavo \[\{ x_1, x_2, \dots, x_n \} \times B_{H,T}(n) \to B_{G,S}(2n), \quad (x_i, h) \mapsto x_i \cdot h.\] Od tod sledi \(n \cdot \beta_{H,T}(n) \leq \beta_{G,S}(2n)\), kar implicira \(1 + \deg(H) \leq \deg(G)\). ◻

Proof. Naj bo \(G\) končno generirana nilpotentna grupa. V posebnem je \(G\) policiklična. Z indukcijo na Hirschovo dolžino \(h(G)\) bomo dokazali, da je \(G\) polinomske rasti.

Baza indukcije je \(h(G) = 0\). V tem primeru je grupa \(G\) končna, torej je polinomske rasti. \(\checkmark\)

Naj ima zdaj \(G\) verigo podgrup \(G = G_1 \unrhd G_2 \unrhd \cdots \unrhd G_r \unrhd G_{r+1} = 1\) s cikličnimi kvocienti, torej za vsak \(i\) lahko pišemo \(G_i = \langle G_{i+1}, x_i \rangle\) za nek \(x_i \in G\). Naj bo \(X = \{ x_1, \dots, x_r \}\). Velja \(G = \langle X \rangle\).

Če je \(|G : G_2| < \infty\), potem lahko preidemo na grupo \(G_2\), pri čemer sta funkciji rasti grup \(G\) in \(G_2\) ekvivalentni. Brez škode lahko torej privzamemo, da je \(G/G_2 \cong \mathbb{Z}\). S tem je \(h(G_2) = h(G) - 1\), zato ima po indukciji grupa \(G_2\) polinomsko rast.

Ocenimo vrednost \(\beta_{G,X}(n)\) za poljuben \(n \in \mathbb{N}\). V ta namen izberimo \(x \in B_{G,X}(n)\), ki ga lahko zapišemo v obliki \(x = y_1 y_2 \dots y_n\), kjer je \(y_i \in X \cup X^{-1}\). Ta element bomo prepisali v obliko \(x = x_1^e \cdot z\) za neka \(e \in \mathbb{Z}, z \in G_2\), in sicer z uporabo naslednjega postopka.

Korak 1:

V besedi \(y_1 y_2 \dots y_n\) poiščemo pojavitev simbola \(x_1\) ali \(x_1^{-1}\), ki je desno od nekega drugega simbola iz množice \(X \cup X^{-1}\), recimo mu \(s\).²⁹ Tak par zamenjamo z izrazom \(x_1^{\pm 1} s [s, x_1^{\pm 1}]\). Na ta način smo element \(x_1^{\pm 1}\) prestavili z desne na levo od \(s\). Zdaj element \(x_1^{\pm 1}\) še naprej potiskamo na levo, dokler levo od njega ni nobenih drugih generatorjev iz množice \(X \cup X^{-1}\).

Korak 2:

V novi besedi poiščemo še kakšno drugo morebitno pojavitev simbola \(x_1\) ali \(x_1^{-1}\), ki še ni zbrana na začetku besede. Naj bo \(s\) simbol, ki je zapisan levo od \(x_1^{\pm 1}\). Pri tem je \(s \in X \cup X^{-1} \cup [X^{\pm 1},X^{\pm 1}]\). Tako pojavitev zopet zamenjamo z \(x_1^{\pm 1} s [s, x_1^{\pm 1}]\).³⁰ Zdaj element \(x_1^{\pm 1}\) še naprej potiskamo na levo, dokler pred njim ni niti drugih generatorjev niti komutatorjev.

Korak \(i\):

V novi besedi poiščemo še kakšno drugo morebitno pojavitev simbola \(x_1\) ali \(x_1^{-1}\), ki še ni zbrana na začetku besede. To pojavitev potiskamo na levo z enakim postopkom, kot je opisan v prejšnjih korakih, in sicer zamenjamo vrstni red komutatorja uteži največ \(i\) z \(x_1^{\pm 1}\), pri čemer uvedemo nov komutator uteži največ \(i+1\) z vnosi iz množice \(X \cup X^{-1}\).

Te korake izvajamo tako dolgo, dokler niso vse pojavitve \(x_1\) in \(x_1^{-1}\) zbrane na levi strani besede. Na ta način dobimo želen zapis \(x = x_1^e \cdot z\) za neka \(e \in \mathbb{Z}, z \in G_2\). Pri tem lahko \(e\) in \(\ell_X(z)\) omejimo na naslednji način.

• Ker je \(x \in B_{G,X}(n)\), sledi \(|e| \leq n\), zato imamo največ \(2n+1\) možnosti za \(e\).

• Po Koraku 1 imamo največ \(n\) komutatorjev uteži \(2\).

• Po Koraku 2 imamo največ \(n\) komutatorjev uteži \(3\) in največ \(n+n = 2n\) komutatorjev uteži \(2\).³¹

• Po Koraku 3 imamo največ \(n\) komutatorjev uteži \(4\), največ \(n + 2n = 3n\) komutatorjev uteži \(3\) in največ \(2n + n = 3n\) komutatorjev uteži \(2\).

• Po Koraku \(i\) imamo največ \(\binom{i}{k-1} \cdot n\) komutatorjev uteži \(k\).

Število izvedenih korakov je največ \(n\). Hkrati je grupa \(G\) nilpotentna, recimo razreda nilpotentnosti \(c\), zato so vsi komutatorji uteži vsaj \(c+1\) trivialni v \(G\). Tako je po zadnjem koraku (Koraku \(n\)) element \(x = x_1^e z\) zapisan kot produkt \(x_1^e\) in produkt največ \(\binom{n}{k-1} \cdot n\) komutatorjev uteži \(k\) za vse \(k = 1, \dots, c\). Velja \(\binom{n}{k-1} \cdot n \leq n^k\), zato je \(z\) zapisan kot produkt največ \(n + n^2 + \cdots + n^c\) komutatorjev uteži kvečjemu \(c\) z vnosi iz \(X \cup X^{-1}\). Vsak od teh komutatorjev uteži vsaj \(2\) je element podgrupe \(G_2 = \langle x_2, \dots, x_r \rangle\), saj je \(G/G_2\) abelova grupa. Naj bo \[A = \max \{ \ell_{\{ x_2, \dots, x_r \}}(k) \mid \text{$k \in G_2$ je komutator uteži $\leq c$ z vnosi iz $X \cup X^{-1}$}\}.\] Tako za vsak dovolj velik \(n\) velja \[\ell_{\{ x_2, \dots, x_r \}}(z) \leq n + A(n^2 + \cdots + n^c) < A n^{c+1}.\] Nazadnje torej velja \[\beta_{G,X}(n) \leq (2n+1) \cdot \beta_{G_2, \{ x_2, \dots, x_r \}}(A n^{c+1}).\] Ker je \(\beta_{G_2, \{ x_2, \dots, x_r \}}\) po indukcijski predpostavki polinom, je torej funkcija \(\beta_{G,X}\) omejena s polinomom, zato je \(G\) polinomske rasti. ◻

Trditev implicira izrek. Naj bo \(G\) končno generirana rešljiva grupa podeksponentne rasti. Po trditvi je \(G^{(2)}\) tudi končno generirana rešljiva grupa podeksponentne rasti, prav take so induktivno zato tudi vse podgrupe \(G^{(i)}\) grupe \(G\). Torej so kvocienti izvedene vrste \(G^{(i)}/G^{(i+1)}\) končno generirane abelove grupe, zato so policiklični. Tako je tudi \(G\) policiklična grupa. ◻

Dokaz trditve (podeksponentna \(\Rightarrow\) izvedena k.g.). Ker je grupa \(G/[G,G]\) končno generirana abelova grupa, je policiklična. Zato bo dovolj dokazati, da za vsako podgrupo edinko \(N \unlhd G\) s cikličnim kvocientom \(G/N\) velja, da je \(N\) končno generirana.

Če je \(|G:N| < \infty\), potem je jasno \(N\) končno generirana. Privzemimo zdaj, da je \(G/N = \langle x N \rangle \cong \mathbb{Z}\) za nek \(x \in G\). Naj bo \(G = \langle x_1, \dots, x_d \rangle\). Vsakega od generatorjev lahko zapišemo kot \(x_i = x^{e_i} y_i\) za neka \(e_i \in \mathbb{Z}\), \(y_i \in N\). Jasno je \(\langle\langle y_1, \dots, y_d \rangle\rangle\leq N\). Hkrati je kvocientna grupa \(G/\langle\langle y_1, \dots, y_d \rangle\rangle\) generirana z odsekom elementa \(x\). Torej je \(G/\langle\langle y_1, \dots, y_d \rangle\rangle\) neskončna ciklična grupa s kvocientom \(G/N \cong \mathbb{Z}\). To je mogoče le v primeru \(N = \langle\langle y_1, \dots, y_d \rangle\rangle\).

Za vsak \(i = 1, 2, \dots, d\) definirajmo \(K_i = \langle \{ x^{n} y_i x^{-n} \mid n \in \mathbb{Z}\} \rangle \leq N\). Grupa \(\langle K_1, \dots, K_d \rangle\) je edinka v \(G\), ki je vsebovana v \(N\), hkrati pa vsebuje vse \(y_1, \dots, y_d\). Zato je \(\langle K_1, \dots, K_d \rangle = N\).

Za vsak \(i\) je grupa \(K_i\) končno generirana: Opazujmo elemente \[x y_i^{\alpha_1} x y_i^{\alpha_2} \cdots x y_i^{\alpha_n} \in G,\] kjer je \(\alpha_j \in \{ 0, 1 \}\). Vseh takih besed je \(2^n\), vsaka od njih je dolžine kvečjemu \(2n\). Iz predpostavke o podeksponentni rasti sta zato za dovolj velik \(n\) dve taki besedi enaki v \(G\). Naj bo \(n_0\) najmanjše naravno število, pri katerem se to zgodi. Velja torej \[\prod_{j = 1}^{n_0} x y_i^{\alpha_j} = \prod_{j = 1}^{n_0} x y_i^{\beta_j}\] za neke \(\alpha_j, \beta_j \in \{ 0, 1 \}\). Uvedimo oznako \(y_i^{[k]} = x^k y_i x^{-k}\). Velja torej \[\prod_{j = 1}^{n_0} \left( y_i^{[j]} \right)^{\alpha_j} = \prod_{j = 1}^{n_0} \left( y_i^{[j]} \right)^{\beta_j}.\] Zaradi minimalnosti \(n_0\) je pri tem \(\alpha_{n_0} \neq \beta_{n_0}\), od koder sledi \[y_i^{[n_0]} \in \langle y_i^{[1]}, y_i^{[2]}, \dots, y_i^{[n_0 - 1]} \rangle.\] Zdaj lahko izpeljemo \[\begin{aligned} y_i^{[n_0 + 1]} \in x \langle y_i^{[1]}, y_i^{[2]}, \dots, y_i^{[n_0 - 1]} \rangle x^{-1} &= \langle y_i^{[2]}, y_i^{[3]}, \dots, y_i^{[n_0]} \rangle \\ &\leq \langle y_i^{[1]}, y_i^{[2]}, \dots, y_i^{[n_0 - 1]} \rangle.\end{aligned}\] Induktivno sledi, da za vsak \(n \geq n_0\) velja \(y_i^{[n]} \in \langle y_i^{[1]}, y_i^{[2]}, \dots, y_i^{[n_0 - 1]} \rangle\). Analogno lastnost lahko izpeljemo za vse dovolj majhne negativne vrednosti \(n\).³⁴ Torej obstaja \(N_0\), da za vsak \(n \in \mathbb{Z}\) velja \[y_i^{[n]} \in \langle y_i^{[- N_0]}, y_i^{[-N_0 + 1]}, \dots, y_i^{[N_0]} \rangle.\] S tem je \(K_i = \langle \{ y_i^{[n]} \mid n \in \mathbb{Z}\} \rangle = \langle y_i^{[- N_0]}, y_i^{[-N_0 + 1]}, \dots, y_i^{[N_0]} \rangle\), torej je \(K_i\) res končno generirana grupa. ◻

Proof. Naj bo \(G\) policiklična grupa podeksponentne rasti. Po potrebi \(G\) zamenjamo s podgrupo končnega indeksa, tako da bo \(G\) imela edinko \(H \unlhd G\) z \(G/H = \langle x H \rangle \cong \mathbb{Z}\) za nek \(x \in G\) in torej \(h(H) < h(G)\). Po indukciji na Hirschovo dolžino lahko predpostavimo, da je \(H\) virtualno nilpotentna. Torej obstaja nilpotentna podgrupa \(N \leq H\) končnega indeksa v \(H\). Po potrebi \(N\) zamenjamo s presekom vseh podgrup indeksa \(|H:N|\) v \(H\) in zato lahko predpostavimo, da vsak avtomorfizem \(H\) ohranja \(N\), torej v posebnem velja \(N \unlhd G\).

Opazujmo podgrupo \(N \langle x \rangle \leq G\). Velja \(G/N = H/N \cdot \langle x \rangle N/N\), zato je \(|G:N\langle x \rangle| \leq |H:N| < \infty\). Hkrati je \(N\langle x \rangle/N \cong \langle x \rangle/(\langle x \rangle \cap N) = \langle x \rangle \cong \mathbb{Z}\). Brez škode lahko zato grupo \(G\) nadomestimo z grupo \(N \langle x \rangle\) in torej predpostavimo, da je \(G\) razširitev grupe \(\langle x \rangle \cong \mathbb{Z}\) z nilpotentno grupo \(N\). Radi bi našli nilpotentno podgrupo končnega indeksa v \(G\). V ta namen dokažimo naslednjo pomožno trditev.

V trditvi element \(x^k\) deluje s konjugiranjem na \(N_i\), torej deluje tudi na kvocientu \(N_i/N_{i+1}\). Trivialnost tega delovanja pomeni, da za vsak \(n \in N_i\) velja \(x^k n x^{-k} N_{i+1} = n N_{i+1}\), kar je enakovredno \([x^k, N_i] \subseteq N_{i+1}\).

Pomožna trditev implicira izrek: Res, naj bo \(K = N\langle x^k \rangle\). Tedaj je vrsta \(K \unrhd N_1 \unrhd N_2 \unrhd \cdots \unrhd N_\ell = 1\) centralna, saj iz komutatorskih identitet sledi \([K, N_i] \subseteq [N, N_i][x^k, N_i] \subseteq N_{i+1} \cdot N_{i+1} \subseteq N_{i+1}\). Tako je grupa \(K\) nilpotentna. Hkrati je \(|G:K| = |\langle x \rangle : \langle x^k \rangle| = k\). \(\checkmark\)

Dokaz pomožne trditve: Grupa \(N\) je nilpotentna, zato ima centralno vrsto \(N = N_1 \geq N_2 \geq \cdots \geq 1\), za katero velja celo \(N_i \unlhd G\),³⁷ vzamemo lahko na primer kar \(N_i = \gamma_i(N)\). Med vsemi vrstami izberimo tako, ki ima maksimalno število neskončnih kvocientov.³⁸ Dobljeno vrsto lahko po potrebi še pofinimo in predpostavimo, da so vsi kvocienti bodisi končni bodisi proste abelove grupe. Dobljeno vrsto označimo z \(N = N_1 \geq N_2 \geq \cdots \geq N_\ell = 1\). Dokazali bomo, da ima slednja vrsta želeno lastnost iz pomožne trditve. Pred tem zabeležimo še eno lastnost te vrste. Po maksimalnosti izbire vrste je za vsako edinko \(M \unlhd G\), za katero je \(N_{i+1} \leq M \leq N_i\), vsaj ena od grup \(M/N_{i+1}\), \(N_i/M\) končna.

Za dokaz pomožne trditve bo za vsak \(1 \leq i \leq \ell\) dovolj najti \(k_i \in \mathbb{Z}\), tako da element \(x^{k_i}\) deluje trivialno na \(N_i/N_{i+1}\). Potem lahko namreč vzamemo \(k = \prod_{i = 1}^\ell k_i\). Pribijmo zato nek \(i\) in opazujmo \(N_i/N_{i+1}\). Če je slednja grupa končna, potem lahko vzamemo \(k_i = |\mathop{\mathrm{Aut}}(N_i/N_{i+1})| < \infty\). Predpostavimo zdaj, da je \(N_i/N_{i+1}\) prosta abelova grupa ranga \(r\) za nek \(r \in \mathbb{N}\). To grupo obravnavajmo kot modul \(M\) nad polinomskim kolobarjem \(\mathbb{Z}[X]\), kjer naj \(X\) deluje kot \(x\). Razširimo \(M\) do vektorskega prostora \(V = \mathbb{Q}\otimes_\mathbb{Z}M\).

Endomorfizme \(\mathop{\mathrm{End}}_{\mathbb{Q}[X]}(V)\) obravnavamo kot podmnožico \(\mathop{\mathrm{End}}_\mathbb{Q}(V)\), kar lahko z izbiro baze prostora \(V\) identificiramo s kolobarjem matrik \(\mathop{\mathrm{Mat}}_r(\mathbb{Q})\). Naj bo \(\alpha \in \mathop{\mathrm{End}}_{\mathbb{Q}[X]}(V)\), ki ustreza delovanju \(x\) na \(M = N_i/N_{i+1}\). Torej lahko \(\alpha\) vidimo kot matriko v \(\mathop{\mathrm{Mat}}_r(\mathbb{Z})\). Ta matrika je ničla svojega karakterističnega polinoma \(p \in \mathbb{Z}[\lambda]\).⁴⁰ Naj bo \(F\) podobseg obsega \(\mathop{\mathrm{End}}_{\mathbb{Q}[X]}(V)\), generiran z elementom \(\alpha\). Torej je \(F/\mathbb{Q}\) razširitev polj z elementom \(\alpha\), ki je ničla polinoma \(p\) s celimi koeficienti. Zato lahko \(F\) vložimo v \(\mathbb{C}\), in sicer tako, da izberemo eno ničlo \(\alpha_0 \in \mathbb{C}\) polinoma \(p\) in preslikamo \(\alpha \mapsto \alpha_0\).⁴¹

Premislimo, da število \(\alpha_0 \in \mathbb{C}\) zadošča zgornjim pogojem. Od tod bo sledilo, da obstaja \(k \in \mathbb{N}\), da je \(\alpha_0^k = 1\), zato je \(\alpha^k = \mathop{\mathrm{id}}_V\) in torej \(x^k\) deluje trivialno na \(N_i/N_{i+1}\), kar smo želeli preveriti. V ta namen predpostavimo, da \(\alpha_0\) ne zadošča pogojem leme. Torej je nujno \(|\alpha_0| > 1\). Po potrebi nadomestimo \(x\) in \(\alpha_0\) z njuno potenco, da bo veljalo celo \(|\alpha_0| > 2\). Izberimo \(0 \neq v \in M\), ki mu ustreza \(y \in N_i/N_{i+1}\). Označimo \(y^{[n]} = x^n.y\) za \(n \in \mathbb{N}_0\). Iz predpostavke o podeksponentni rasti zdaj kot v dokazu trditve (podeksponentna \(\Rightarrow\) izvedena k.g.) sledi, da obstaja \(n_0 \in \mathbb{N}\), za katerega je \[y^{[n_0]} = \sum_{i = 0}^{n_0 - 1} c_i y^{[i]}\] za neke \(c_i \in \mathbb{Z}\), \(|c_i| \leq 1\). To enakost lahko zapišemo kot \[\alpha^{n_0}(v) = \left( \sum_{i = 0}^{n_0 - 1} c_i \alpha^i \right)(v).\] S tem ima endomorfizem \(\alpha^{n_0} - \sum_{i = 0}^{n_0 - 1} c_i \alpha^i \in \mathop{\mathrm{End}}_{\mathbb{Q}[X]}(V)\) netrivialno jedro. (Schurova lema) zato implicira, da je ta element trivialen. Od tod izpeljemo protislovje \[|\alpha_0^{n_0}| = \left| \sum_{i = 0}^{n_0 - 1} c_i \alpha_0^i \right| \leq \sum_{i = 0}^{n_0 - 1} |\alpha_0|^i = \frac{|\alpha_0|^{n_0} - 1}{|\alpha_0| - 1} < |\alpha_0|^{n_0},\] kjer smo v zadnji neenakosti upoštevali \(|\alpha_0| > 2\). Dokaz pomožne trditve je s tem zaključen. ◻

Proof. Dokažimo le 1. točko, dokaz 2. in 3. točke je podobne zahtevnosti (glej vaje).

\((\Leftarrow)\): Če je \(\mathcal{F}^\prime\) filter z lastnostjo \(\mathcal{F}^\prime \supsetneq \mathcal{F}\), potem obstaja \(A \subseteq S\), da je \(A \in \mathcal{F}^\prime \backslash \mathcal{F}\). Zato je po predpostavki \(S \backslash A \in \mathcal{F}\), s tem pa velja \(\emptyset = (S \backslash A) \cap A \in \mathcal{F}^\prime\). Protislovje. Torej je \(\mathcal{F}\) res maksimalen filter.

\((\Rightarrow)\): Naj za neko množico \(A \subseteq S\) velja \(A \notin \mathcal{F}\) in \(S \backslash A \notin \mathcal{F}\). Naj bo \(\mathcal{G}= \{ B \subseteq S \mid \exists F \in \mathcal{F}\colon \ F \cap A \subseteq B \}\).

Jasno je \(\mathcal{G}\supseteq \mathcal{F}\) in \(A \in \mathcal{G}\backslash \mathcal{F}\). Dokažimo, da je \(\mathcal{G}\) filter. To bo protislovje z maksimalnostjo filtra \(\mathcal{F}\).

• Če je \(\emptyset \in \mathcal{G}\), potem je \(F \cap A = \emptyset\) za nek \(F \in \mathcal{F}\). Od tod sledi \(F \subseteq S \backslash A\), zato je \(S \backslash A \in \mathcal{F}\). Protislovje. \(\checkmark\)

• Naj bosta \(G_1, G_2 \in \mathcal{F}\). Potem je \(F_1 \cap A \subseteq G_1\) in \(F_2 \cap A \subseteq G_2\) za neka \(F_1, F_2 \in \mathcal{F}\). Sledi \(F_1 \cap F_2 \cap A \subseteq G_1 \cap G_2\) in \(F_1 \cap F_2 \in \mathcal{F}\), zato je \(G_1 \cap G_2 \in \mathcal{G}\). \(\checkmark\)

• Naj bo \(G \in \mathcal{G}\) in \(H \supseteq G\). Potem je \(F \cap A \subseteq G \subseteq H\) za nek \(F \in \mathcal{F}\), zato je \(H \in \mathcal{G}\). \(\checkmark\)

 ◻

Proof. 1. Naj bosta \(x \neq y\) različni \(\mathcal{U}\)-limiti zaporedja \(\{ x_n \}_{n \in \mathbb{N}}\). Po predpostavki o Hausdorffovosti obstajata \(U,V \subseteq_o T\), da velja \(U \cap V = \emptyset\), \(x \in U\), \(y \in V\). Sledi \(I(U) \cap I(V) = \emptyset\), zato množici \(I(U), I(V)\) ne moreta obe pripadati \(\mathcal{U}\). Protislovje.

2. Denimo, da zaporedje \(\{ x_n \}_{x \in \mathbb{N}}\) nima \(\mathcal{U}\)-limite. Torej ima vsak \(y \in T\) odprto okolico \(U_y \subseteq_o T\), da je \(I(U_y) \notin \mathcal{U}\). Po predpostavki o kompaktnosti obstajajo \(y_1, \dots, y_k \in T\), da je \(T = \bigcup_{i = 1}^k U_{y_i}\). Hkrati za vsak \(i\) velja \(I(U_{y_i})^c = \{ n \in \mathbb{N}\mid x_n \notin U_{y_i} \} \in \mathcal{U}\), zato je \(\bigcap_{i = 1}^k I(U_{y_i})^c \in \mathcal{U}\). V posebnem je zadnji presek neprazen, torej obstaja \(i_0 \in \mathbb{N}\), da je \(x_{i_0} \notin U_{y_i}\) za vsak \(i\). Protislovje, saj množice \(U_{y_i}\) pokrijejo ves \(T\). ◻

Proof. \((\Rightarrow)\): Naj bo \(x = \lim_\mathcal{U}x_n\). Naj bo \(\{ U_i \}_{i \in \mathbb{N}}\) padajoča baza odprtih okolic točke \(x\). Velja \(I(U_1) \in \mathcal{U}\), zato je v posebnem \(I(U_1) \neq \emptyset\), torej obstaja \(n_1 \in \mathbb{N}\), da je \(x_{n_1} \in U_1\). Ker ultrafilter \(\mathcal{U}\) vsebuje kokončni filter, induktivno za vsak \(i > 1\) velja \(I(U_i) \cap \{ 1,2,\dots,n_{i-1} \}^c \in \mathcal{U}\), zato obstaja \(n_i \in \mathbb{N}\), da je \(n_i > n_{i-1}\) in \(x_{n_i} \in U_i\). Torej je \(\lim_{i \to \infty} x_{n_i} = x\). \(\checkmark\)

\((\Leftarrow)\): Naj bo \(x\) stekališče zaporedja \(\{ x_n \}_{n \in \mathbb{N}}\). Naj bo \(\{ U_i \}_{i \in \mathbb{N}}\) padajoča baza odprtih okolic točke \(x\). Ker je \(x\) stekališče, je \(I(U_1) \neq \emptyset\), torej obstaja \(n_1 \in \mathbb{N}\), da je \(x_{n_1} \in U_1\). Induktivno za vsak \(i > 1\) obstaja \(n_i \in \mathbb{N}\), da je \(x_{n_i} \in U_i\) in \(n_i > n_{i-1}\). Naj bo \(G = \{ I(U_i) \backslash \{ 1, 2, \dots, n_{i-1} \} \mid i \in \mathbb{N}\}\). Uporabimo (osnovne lastnosti ultrafiltrov) in sklepamo, da obstaja ultrafilter \(\mathcal{U}\supseteq G\). S tem je \(x = \lim_\mathcal{U}x_n\). Hkrati ultrafilter \(\mathcal{U}\) ni glavni, saj za vsak \(k \in \mathbb{N}\) za dovolj velik \(i\) velja \(k \notin I(U_i) \backslash \{ 1,2,\dots,n_{i-1} \}\). ◻

Proof. Homogenost: Asimptotski stožec identificiramo z množico odsekov \(\mathsf{ZZR}/\mathsf{ZZR}_0\). Na tej množici deluje grupa \(\mathsf{ZZR}\) z levim množenjem: \(\{ z_n \}_{n \in \mathbb{N}}. \{ x_n \}_{n \in \mathbb{N}}\mathsf{ZZR}_0 = \{ z_n \cdot x_n \}_{n \in \mathbb{N}} \mathsf{ZZR}_0\). To delovanje je tranzitivno, saj je \(\{ y_n x_n^{-1} \}_{n \in \mathbb{N}}. \{ x_n \}_{n \in \mathbb{N}}\mathsf{ZZR}_0 = \{ y_n \}_{n \in \mathbb{N}} \mathsf{ZZR}_0\). \(\checkmark\)

Povezanost s potmi:

Lokalna povezanost: Naj bo \(\alpha = [\{ x_n \}_{n \in \mathbb{N}}] \in K\) in naj bo \(\gamma\) pot kot v pomožni trditvi. Po konstrukciji za vsak \(t \in [0,1]\) velja \(d(\gamma(t), 1) \leq d(\alpha, 1) \cdot t\), zato je slika \(\gamma\) v celoti vsebovana v krogli \(B_K(d(\alpha, 1))\)⁵⁵. Iz pomožne trditve zato sledi, da je notranjost krogle \(B_K(d(\alpha, 1))\) povezana. Ker je prostor \(K\) homogen, od tod sledi lokalna povezanost prostora \(K\). \(\checkmark\)

Polnost: (glej vaje) ◻

Proof. Za \(g \in G\) in \(r \in \mathbb{R}\) označimo največji možni premik⁵⁸ elementa \(g\) na krogli polmera \(r\) kot \[D(g,r) = \max \{ d(a,g \cdot a) \mid a \in B_{G,S}(r) \} = \max \{ \ell_S(a^{-1} g a) \mid a \in B_{G,S}(r) \}.\]

Elementi \(g \in G\) z lastnostjo \(|g^G| < \infty\) se imenujejo FC-elementi.⁵⁹ Ti elementi tvorijo podgrupo edinko v \(G\).

Z vsem naštetim lahko nazadnje dokažemo izrek (o delovanju \(\Phi\)). Po predpostavki je \(|\mathop{\mathrm{im}}\Phi| = |G : \ker \Phi| < \infty\). Torej je jedro \(\ker \Phi\) končno generirana grupa, označimo \(\ker \Phi = \langle y_1, \dots, y_d \rangle\). Naj bo \(O_{C^\prime, \epsilon^\prime} \subseteq \mathop{\mathrm{Isom}}(K)\) poljubna bazna okolica identitete \(\mathop{\mathrm{id}}_K\) in naj bo \(C = 2 C^\prime\), \(\epsilon = \epsilon^\prime/2\). Dokaz bomo izvedli v zaporedju večih korakov.

• Predpostavimo najprej, da je vsak generator \(y_j\) FC-element. V tem primeru je \(|y_j^{\ker \Phi}| < \infty\), zato je centralizator \(C_{\ker \Phi}(y_j)\) končnega indeksa v \(\ker \Phi\) za vsak \(j\). Od tod sledi, da je tudi \(Z(\ker \Phi) = \bigcap_{j = 1}^d C_{\ker \Phi}(y_j)\) končnega indeksa v \(\ker \Phi\). To pomeni, da je grupa \(\ker \Phi\) virtualno abelova. Protislovje. Torej FC-elementi tvorijo pravo podgrupo v \(\ker \Phi\), zato lahko po morebitni menjavi generatorjev grupe \(\ker \Phi\) predpostavimo, da celo⁶⁰ \[\text{noben od $y_j$ ni FC-element.}\]

• Fiksirajmo \(r \in \mathbb{N}\). Opazujmo množico \[\begin{aligned} Y_t &= \{ y \in \ker \Phi \mid D(y^{-1} y_t y, Cr) \leq \epsilon r \} \\ &= \{ y \in \ker \Phi \mid \forall a \in B_{G,S}(Cr) \colon \ \ell_S(a^{-1} y^{-1} y_t y a) \leq \epsilon r \} \\ &= \{ y \in \ker \Phi \mid \forall a \in B_{G,S}(Cr) \colon \ y_t^{ya} \in B_{G,S}(\epsilon r) \}. \end{aligned}\] Množica \(\{ y_t^{ya} \mid y \in Y_t, \ a \in B_{G,S}(Cr) \}\) je torej končna, saj je vsebovana v \(B_{G,S}(\epsilon r)\). Zato je tudi množica odsekov \(C_t = \{ C_{\ker \Phi}(y_t) ya \mid y \in Y_t, \ a \in B_{G,S}(Cr) \}\) končna. Ker \(y_t\) ni FC-element, je vsak centralizator \(C_{\ker \Phi}(y_t)\) neskončnega indeksa v \(\ker \Phi\), zato po zadnji pomožni trditvi \(\ker \Phi\) ni unija odsekov iz \(C_1 \cup \cdots \cup C_d\). Tako obstaja element \(z_r \in \ker \Phi\), ki ne pripada nobenemu odseku iz \(C_t\). V posebnem od tod sledi, da za vsak \(t\) velja \(z_r \notin Y_t\), se pravi \[\text{za vsak $t$ velja $D(z_r^{-1} y_t z_r, Cr) > \epsilon r$.}\]

• Zapišimo element \(z_r\) kot besedo v \(y_1, \dots, y_d\) in naj bo \(x_r\) najkrajša predpona besede, za katero za nek \(t\) velja \(D(x_r^{-1} y_t x_r, Cr) > \epsilon r\). Izberimo en tak \(t = t(r)\).⁶¹ Za vsak \(i = 1, \dots, d\) naj bo \(S(i) = \{ r \mid t(r) = i \}\). Velja \(S(1) \cup \cdots \cup S(d) = \mathbb{N}\). Torej obstaja \(i_0\), da je \(S(i_0) \in \mathcal{U}\). Torej velja \[\text{$D(x_r^{-1} y_{i_0} x_r, Cr) > \epsilon r$ za vse $r$ iz neke množice v $\mathcal{U}$.}\]

• Po prvi pomožni trditvi za vse \(r\) iz neke množice v \(\mathcal{U}\) velja \(D(y_t, r) < \epsilon r\) za vsak \(t\). Od tod sledi, da je \(x_r \neq 1\), torej lahko pišemo \(x_r = w_r \cdot y\) za nek \(y \in \{ y_1^{\pm 1}, \dots, y_d^{\pm 1} \}\) in krajšo besedo \(w_r\). Iz tretje pomožne trditve zdaj sledi \[D(x_r^{-1} y_t x_r, Cr) = D(y^{-1} w_r^{-1} y_t w_r y, Cr) \leq D(w_r^{-1} y_t w_r, Cr) + 2 \ell_S(y).\] Naj bo \(\ell = \max \{ \ell_S(y_i) \mid i = 1, \dots, d \}\). Torej⁶² \[\text{za vse $r$ iz neke množice v $\mathcal{U}$ je } D(x_r^{-1} y_t x_r, Cr) \leq \epsilon r + 2 \ell \text{ za vsak $t$.}\]

• Za vse \(r\) iz neke množice v \(\mathcal{U}\) torej velja neenakost \[\epsilon r < D(x_r^{-1} y_{i_0} y_r, Cr) \leq \epsilon r + 2 \ell,\] od koder sledi \[\lim_\mathcal{U}\frac{D(x_r^{-1} y_{i_0} x_r, Cr)}{r} = \epsilon. \quad (*)\]

• Za poljuben element \(w \in \ker \Phi\) opazujmo zaporedje \(\{ x_r^{-1} w x_r \}_{r \in \mathbb{N}}\) v grupi \(G\). Zapišimo \(w\) kot besedo v generatorjih \(y_1, \dots, y_d\) dolžine \(m\). Velja \[\ell_S(x_r^{-1} w x_r) \leq D(x_r^{-1} w x_r, Cr) \leq m \cdot \max \{ D(x_r^{-1} y_i x_r, Cr) \mid i = 1, \dots, d \}.\] Za vse \(r\) iz neke množice \(U \in \mathcal{U}\) zato velja \[\ell_S(x_r^{-1} w x_r) \leq m \epsilon r + 2 m \ell.\] Definirajmo zaporedje \(\{ X_r(w) \}_{r \in \mathbb{N}}\) na naslednji način: \[X_r(w) = \begin{cases} x_r^{-1} w x_r; & r \in U \\ 1; & r \in \mathbb{N}\backslash U. \end{cases}\] Zaporedji, ki se na množici v \(\mathcal{U}\) ujemata, imata enako \(\mathcal{U}\)-limito, zato velja \[d(\{ X_r(w) \}_{r \in \mathbb{N}}, \{ x_r^{-1} w x_r \}_{r \in \mathbb{N}}) = 0 \quad \text{in} \quad \{ X_r(w) \}_{r \in \mathbb{N}} \in \mathsf{ZZR}.\]

• Zaporedje zmerne rasti \(\{ X_r(w) \}_{r \in \mathbb{N}}\) lahko z desne pomnožimo z drugimi zmernimi zaporedji in na ta način dobimo izometrijo asimptotskega stožca \(\mathsf{ZZR}/\mathsf{ZZR}_0 = K\). To izometrijo označimo s \(\varphi(w)\). Imamo torej homomorfizem grup \[\varphi \colon \ker \Phi \to \mathop{\mathrm{Isom}}(K).\]

• Kot v dokazu prve pomožne trditve zdaj iz lastnosti \((*)\) sledi, da zaporedje \(\{ X_r(y_{i_0}) \}_{r \in \mathbb{N}}\) deluje netrivialno z levim množenjem na \(K\). Torej je \(\varphi(y_{i_0}) \neq \mathop{\mathrm{id}}_K\).

• Naj bo \(\alpha = \{ a_r \}_{r \in \mathbb{N}} \in \mathsf{ZZR}\) z \([\alpha] \in B_K(C/2)\). Za vse \(r\) iz neke množice v \(\mathcal{U}\) velja torej \(a_r \in B_{G,S}(Cr)\). Od tod sledi \[\begin{aligned} d(\varphi(y_{i_0}).[\alpha], [\alpha]) &= d(\{ X_r(y_{i_0})\}_{r \in \mathbb{N}}, \{ a_r \}_{r \in \mathbb{N}}) \\ &= \lim_\mathcal{U}\frac{d(X_r(y_{i_0}) a_r, a_r)}{r} \\ &\leq \lim_\mathcal{U}\frac{D(X_r(y_{i_0}), Cr)}{r} \\ &= \lim_\mathcal{U}\frac{D(x_r^{-1} y_{i_0} x_r, Cr)}{r} \\ &= \epsilon. \end{aligned}\] Torej je \(\varphi(y_{i_0}) \in O_{C/2, 2\epsilon} = O_{C^\prime, \epsilon^\prime}\). S tem je dokaz zaključen.

 ◻

Proof. Podajmo le idejo dokaza, da je topološka dimenzija prostora \(X\) vselej manjša ali enaka Hausdorffovi dimenziji.⁶³ Ekvivalentno, če je \(X\) topološki prostor z \(\mu_{d+1}(X) = 0\), potem je \(X\) dimenzije kvečjemu \(d\). Dokazujemo z indukcijo na \(d\).

Naj bo \(x \in X\) poljubna točka. Za vsak \(r > 0\) opazujmo rob krogle okoli \(x\), se pravi sfero \(S(r) \subseteq X\) s središčem v \(x\) in polmerom \(r\). Dovolj bo dokazati, da za nek \(r\) velja \(\mu_d(S(r)) = 0\), izrek od tod sledi induktivno.

Ker velja \(\mu_{d+1}(X) = 0\), obstaja zaporedje števnih pokritij \(\{ U_i^n \}_i\) množice \(X\) za \(n = 1, 2, \dots\), tako da je \[\lim_{n \to \infty} \sum_i \mathop{\mathrm{diam}}(U_i^n)^{d+1} = 0.\] Iz pomožne trditve zdaj sledi \[\lim_{n \to \infty} \int_{0}^\infty \sum_i \mathop{\mathrm{diam}}(S(r) \cap U_i^n)^d \ dr = 0.\] Torej obstaja podzaporedje⁶⁴ zaporedja pokritij \(\{ U_i^{n_k} \}_i\) za \(k = 1, 2, \dots\), da za nek⁶⁵ \(r > 0\) velja \[\lim_{k \to \infty} \sum_i \mathop{\mathrm{diam}}(S(r) \cap U_i^{n_k})^d = 0.\] Od tod sledi \(\mu_d(S(r)) = 0\). ◻

Proof. Naj bo \(k(\epsilon) \cdot \epsilon^d < C\) za nek \(C > 0\) neodvisen od \(\epsilon\). Izberimo \(e > d\). Tedaj je \[\mu_e(X) = \lim_{\epsilon \to 0} \inf_{\{ U_i \}_i } \sum_i (\mathop{\mathrm{diam}}U_i)^e \leq \lim_{\epsilon \to 0} k(\epsilon) \cdot (\epsilon)^e \leq \lim_{\epsilon \to 0} C \epsilon^{e-d} = 0.\] ◻

Proof. Naj bo \(\epsilon > 0\) in \(\mathcal{U}\) ultrafilter na \(\mathbb{N}\), oba zaenkrat še nedoločena. Zaradi homogenosti \(K\) lahko predpostavimo, da je \(B = B_K(1)\).

Naj bodo \(x_1, \dots, x_k \in B\) elementi z \(d(x_i, x_j) > 2\epsilon\) za \(i \neq j\). Naj bo \(x_i = [\{ g_{i,n} \}_{n \in \mathbb{N}}]\) za neke \(g_{i,n} \in G\). Ker je \(x_i \in B\), velja \(\lim_\mathcal{U}d(g_{i,n}, 1)/n \leq 1\), zato za vse \(n\) iz neke množice \(M \in \mathcal{U}\) velja \(d(g_{i,n}, 1) \leq (1+\epsilon)n\).

Za vsaka \(i \neq j\) in naj bo \[N(i,j,\epsilon) = \{ n \in \mathbb{N}\mid d(g_{i,n}, g_{j,n}) > 2 \epsilon n \}.\] Ker je \(d(x_i, x_j) > 2 \epsilon\), velja \(N(i,j,\epsilon) \in \mathcal{U}\), zato je tudi \[N(\epsilon) := \bigcap_{i \neq j} U(i,j,\epsilon) \in \mathcal{U}.\]

Izberimo \(r \in \mathbb{N}\) z lastnostjo \(2^{-r} < \epsilon \leq 2^{-r+1}\). Naj bo \(n \in \mathbb{N}\), \(n > r\), z lastnostjo \(2^n \in N(\epsilon)\). V globini \(2^n\) velja \[d(g_{i, 2^n}, g_{j, 2^n}) > 2^{n+1} \epsilon > 2^{n+1-r} = 2 \cdot 2^{n-r},\] zato so krogle \(g_{i,2^n} \cdot B_{G,S}(2^{n-r})\) polmera \(2^{n-r}\) okoli točk \(g_{i, 2^n}\) disjunktne za \(i = 1, \dots, k\). Od tod sledi \[\left| \bigcup_{i = 1}^k g_{i,2^n} \cdot B_{G,S}(2^{n-r}) \right| = k \cdot \beta_{G,S}(2^{n-r}).\] Hkrati za vsak \(i\) velja \[g_{i,2^n} \cdot B_{G,S}(2^{n-r}) \subseteq B_{G,S}(2^{n-r} + d(g_{i, 2^n}, 1)) \subseteq B_{G,S}(2^{n-r} + (1+\epsilon) 2^n),\] slednja krogla pa je vsebovana v \(B_{G,S}(2^{n+1})\) za dovolj majhen \(\epsilon\).⁶⁶ Od tod sledi neenakost \[k \cdot \beta_{G,S}(2^{n-r}) \leq \beta_{G,S}(2^{n+1})\] za vse \(n > r\), za katere je \(2^n \in N(\epsilon)\), pri tem pa je \(r = r(\epsilon)\) fiksen.

Iz pomožne trditve in zadnje neenakosti pred njo izpeljemo⁶⁷ \[k \cdot \beta_{G,S}(2^{n-r}) \leq \beta_{G,S}(2^{n+1}) \leq 2^{(r+1)(d+1)} \cdot \beta_{G,S}(2^{n-r}),\] kar implicira \(k \leq 2^{(r+1)(d+1)} \leq \left( \frac{4}{\epsilon} \right)^{d+1}\). Dokaz je s tem zaključen. ◻

Proof. Končna dimenzija: Dimenzija je lokalna topološka lastnost, zato je dovolj dokazati, da je dimenzija krogle \(B = B_K(1)\) končna. V ta namen izberimo maksimalno število točk \(x_1, \dots, x_k \in B\) z lastnostjo \(d(x_i, x_j) > 2 \epsilon\) za vse \(i \neq j\). Iz zadnje trditve sledi \(k \leq ( 4/\epsilon )^{d+1}\). Torej lahko \(B\) pokrijemo z \((4/\epsilon)^{d+1}\) kroglami polmera \(2 \epsilon\).⁶⁸ Iz trditve (krogle in Hausdorffova dimenzija) sledi \(\dim_H(B) \leq d+1\), s tem pa iz izreka (Szpilrajn 1937) sklepamo, da je \(B\) končne dimenzije. \(\checkmark\)

Lokalna kompaktnost: Dovolj je dokazati, da je vsaka krogla \(B \subseteq K\) kompaktna. Naj bo \(\{ x_n \}_{n \in \mathbb{N}}\) zaporedje v \(B\). Za vsak \(i\) pokrijmo \(B\) s \(k_i\) kroglami polmera kvečjemu \(2^{-i}\).⁶⁹ Izberimo podzaporedje, ki v celoti leži v eni od krogel polmera kvečjemu \(1\). Po tem izberimo podzaporedje, ki v celoti leži v eni od krogel polmera kvečjemu \(\frac12\). Po tem izberimo podzaporedje, ki v celoti leži v eni od krogel polmera kvečjemu \(\frac14\). …Nazadnje vzemimo podzaporedje, ki sestoji iz prvih členov vseh teh podzaporedij. Po konstrukciji je to Cauchyjevo zaporedje. Iz polnosti \(K\) torej sledi, da ima \(\{ x_n \}_{n \in \mathbb{N}}\) konvergentno podzaporedje. \(\checkmark\) ◻

Proof. Uporabimo izrek (Montgomery–Zippin 1955) za asimptotski stožec \(K\). Naj bo \(\Gamma = \mathop{\mathrm{Isom}}(K)\), opremljena s strukturo Liejeve grupe s končno mnogo komponentami. Torej obstaja abelova edinka \(Z \unlhd \Gamma\), da se \(\Gamma/Z\) vloži v \(\mathop{\mathrm{GL}}_k(\mathbb{C})\) za nek \(k\). Naj bo \(\Phi \colon G \to \Gamma\) delovanje grupe \(G\) na asimptotskem stožcu in naj bo \(L = \Phi^{-1}(Z)\). Velja \(L \unlhd G\) in \(L/\ker \Phi\) je abelova grupa. Obravnavajmo več primerov glede na indeks \(L\) oziroma \(\ker \Phi\) v \(G\).

Če je \(|G : L| = \infty\):

V tem primeru ima \(G\) epimorfno sliko \(G/L\), ki se s \(\Phi\) vloži v \(\Gamma/Z\), ta pa se vloži v \(\mathop{\mathrm{GL}}_k(\mathbb{C})\). Vzamemo lahko torej \(C = G\) (1. točka). \(\checkmark\)

Če je \(|G : L| < \infty\) in \(|G : \ker \Phi| = \infty\):

V tem primeru ima \(L\) epimorfno sliko \(L/\ker\Phi\), ki je končno generirana neskončna abelova grupa, zato ima epimorfno sliko \(\mathbb{Z}\). Slednja grupa se vloži v \(\mathop{\mathrm{GL}}_1(\mathbb{C})\). Vzamemo lahko torej \(C = L\) (1. točka). \(\checkmark\)

Če je \(|G : \ker \Phi| < \infty\):

V tem primeru je \(\mathop{\mathrm{im}}\Phi\) končna. Če je \(\ker \Phi\) virtualno abelova grupa, ima torej edinko končnega indeksa z epimorfno sliko \(\mathbb{Z}\), ki se vloži v \(\mathop{\mathrm{GL}}_1(\mathbb{C})\). Vzamemo lahko torej \(C = \ker \Phi\) (1. točka). \(\checkmark\)Sicer pa po izreku (o delovanju \(\Phi\)) sledi, da za vsako okolico \(O\) identitete \(\mathop{\mathrm{id}}_K\) najdemo homomorfizem \(\varphi_O \colon \ker \Phi \to \mathop{\mathrm{Isom}}(K)\) z lastnostjo \(|\mathop{\mathrm{im}}\varphi_O \cap O| > 1\). Po lastnosti (brez malih redov) lahko za vsak \(n \in \mathbb{N}\) izberemo okolico \(O_n\), ki ne vsebuje elementov reda kvečjemu \(n\). Slika \(\mathop{\mathrm{im}}\varphi_{O_n}\) tako vsebuje netrivialen element reda večjega od \(n\), zato je \(|\mathop{\mathrm{im}}\varphi_{O_n}| > n\). Vzamemo lahko torej \(C = \ker \Phi\) (2. točka). \(\checkmark\)

 ◻

Proof. Naj bo \(C\) kot v zadnji posledici.

1. Naj bo \(\alpha \colon C \to D\) epimorfizem za neko neskončno grupo \(D \leq \mathop{\mathrm{GL}}_k(\mathbb{C})\). Grupe \(G\), \(C\) in \(D\) so polinomske rasti, zato je \(D\) virtualno nilpotentna. Torej obstaja podgrupa \(E \leq D\) končnega indeksa v \(D\) in zato tudi končnega indeksa v \(G\), za katero je \(E/\ker \alpha\) nilpotentna in neskončna podgrupa \(\mathop{\mathrm{GL}}_k(\mathbb{C})\). Naj bo \(k \in \mathbb{N}\) največje število, za katero je \(|E : E^{(k)}| < \infty\). Tedaj je grupa \(E^{(k)}\) končnega indeksa v \(G\), njen kvocient \(E^{(k)}/E^{(k+1)}\) pa je neskončna končno generirana abelova grupa. Vzamemo lahko torej \(H = E^{(k)}\). \(\checkmark\)

2. Naj bo \(\varphi_n \colon C \to \Gamma\) homomorfizem z \(|\mathop{\mathrm{im}}\varphi_n| > n\) za vsak \(n \in \mathbb{N}\). Naj bo \(Z \unlhd \Gamma\) abelova edinka, za katero se \(\Gamma/Z\) vloži v \(\mathop{\mathrm{GL}}_k(\mathbb{C})\). Naj bo \(L_n = \varphi_n^{-1}(Z)\). Torej se grupa \(C/L_n\) vloži v \(\Gamma/Z\), slednja pa se vloži v \(\mathop{\mathrm{GL}}_k(\mathbb{C})\).

Izrek (Jordan 1878) zagotovi obstoj podgrupe \(K_n \leq C\) omejenega indeksa⁷⁰ v \(C\), za katero je \(K_n \geq L_n\) in \(K_n/L_n\) je abelova grupa. Ker ima grupa \(C\) le končno mnogo podgrup danega indeksa, je torej za neskončno mnogo vrednosti \(n\) grupa \(K_n\) enaka neki fiksni podgrupi \(K \leq G\). Za neskončno mnogo naravnih števil \(n\) je torej grupa \(K/L_n\) abelova.

Če so velikosti grup \(|K/L_n|\) neomejene, ima grupa \(K\) poljubno velike abelove kvociente. Ker je tudi končno generirana, sledi \(|K/K^{(2)}| = \infty\). V tem primeru lahko vzamemo \(H = K\). \(\checkmark\)

Predpostavimo zdaj, da so velikosti grup \(|K/L_n|\) omejene, ko \(n\) preteče neko neskončno podmnožico naravnih števil. Ker ima \(K\) le končno mnogo podgrup danega indeksa, je za neskončno mnogo vrednosti \(n\) grupa \(L_n\) enaka neki fiksni podgrupi \(L \leq K\). Ker je \(|\mathop{\mathrm{im}}\varphi_n| \geq n\) in \(|C : L| < \infty\), sledi \(\limsup_{n \to \infty} |L/\ker \varphi_n| = \infty\). Grupa \(L/ \ker \varphi_n\) je abelova, saj se vloži v \(Z\). Torej ima \(L\) poljubno veliko abelove kvociente. Ker je tudi končno generirana, sledi \(|L:L^{(2)}| = \infty\). Vzamemo lahko torej \(H = L\). \(\checkmark\) ◻

Dokaz izreka Gromova. Naj bo \(G\) grupa polinomske rasti stopnje kvečjemu \(d\). Dokazujemo z indukcijo na \(d\). Bazni primer \(d = 0\) je mogoče le, ko je grupa \(G\) končna in v tem primeru izrek seveda velja. Predpostavimo zdaj, da izrek velja za vse grupe stopnje kvečjemu \(d-1\). Po zadnji trditvi obstaja podgrupa \(H \leq G\) končnega indeksa v \(G\) in \(N \unlhd H\), da je \(\mathbb{Z}\cong H/N = \langle hN \rangle\) za nek \(h \in H\). Po dokazu trditve (podeksponentna \(\Rightarrow\) izvedena k.g.) je \(N\) končno generirana, hkrati pa je \(\deg(N) \leq d-1\). Po indukciji zato obstaja nilpotentna podgrupa \(K \leq N\) končnega indeksa v \(N\). Po potrebi \(K\) nadomestimo s presekom vseh podgrup v \(N\) indeksa \(|N:K|\), zato lahko predpostavimo, da je \(K \unlhd H\). Naj bo \(C = \langle K, h \rangle \leq H\). Velja \(H/K = C/K \cdot N/K\), zato je \(C\) končnega indeksa v \(H\) in s tem tudi v \(G\). Grupa \(C\) je razširitev \(\mathbb{Z}\) z nilpotentno grupo \(K\), torej je \(C\) rešljiva. Ker je \(C\) polinomske rasti, od tod sledi, da je \(C\) virtualno nilpotentna. Dokaz je s tem zaključen. ◻

Proof. Predpostavimo, da \(w = x_1 x_2 \dots x_k\) ni alternirajoča. To je možno le v dveh primerih.

Če za nek \(i\) velja \(x_i = x_{i+1}\):

V tem primeru je \(x_i x_{i+1} = x_i^2 = 1\). Beseda \(w^\prime = x_1 \cdots x_{i-1} x_{i+2} \cdots x_k\) zato predstavlja element \(g\) in je krajše dolžine kot \(\ell(g)\). Protislovje.

Če za nek \(i\) velja \(x_i, x_{i+1} \in \{b,c,d\}\):

Ker velja \(bc = d, bd=c, cd = b\), je v tem primeru \(y := x_i x_{i+1} \in \{b,c,d\}\). Beseda \(w^\prime = x_1 \cdots x_{i-1} y x_{i+2} \cdots x_k\) zato predstavlja element \(g\) in je krajše dolžine kot \(\ell(g)\). Protislovje.

 ◻

Proof. Opazujmo vložitev \(\rho\colon H \to \Gamma \times \Gamma\). Za vsak \(g \in \Gamma\) obstaja \(x \in H\), da je \(x_0 = g\), se pravi \(\rho(x) = (g, x_1)\). Hkrati je \(\rho(ada) = (b,1)\), kar po konjugiranju z \(x\) postane \(\rho((ada)^x) = (b,1)^{\rho(x)} = (b^g, 1)\). Naj bo \(B = \langle\langle b \rangle\rangle\leq G\). Torej slika \(\mathop{\mathrm{im}}\rho\) gotovo vsebuje grupo \(B \times 1 \leq \Gamma \times \Gamma\). Podobno dobimo \(\mathop{\mathrm{im}}\rho\geq 1 \times B\) in s tem \(\mathop{\mathrm{im}}\rho\geq B \times B\).

Iz pomožne trditve sledi \(|\Gamma \times \Gamma : \mathop{\mathrm{im}}\rho| \leq 64\). Tako ima grupa \(\Gamma\) podgrupo končnega indeksa \(H\), ki je izomorfna podgrupi končnega indeksa \(\mathop{\mathrm{im}}\rho\) grupe \(\Gamma \times \Gamma\). ◻

Proof. Predpostavimo, da je \(\Gamma\) polinomske rasti. Potem je tudi \(\Gamma \times \Gamma\) polinomske rasti. Iz zadnje trditve zdaj sledi \(\deg(\Gamma) = \deg(\Gamma \times \Gamma)\). Toda \(\deg(\Gamma \times \Gamma) = 2 \cdot \deg(\Gamma)\) (glej vaje). Od tod sledi \(\deg(\Gamma) = 0\), kar je mogoče le, če je \(\Gamma\) končna. Protislovje. ◻

Proof. Zapišimo \(x\) kot najkrajši možen alternirajoč produkt elementov \(u\) in \(ava\) za \(u,v \in \{ b,c,d \}\). Naj bo število uporabljenih faktorjev enako \(2k+r\) za \(r \in \{0, 1\}\). Torej je \(x\) produkt \(k\) parov oblike \(u \cdot ava\) ali \(ava \cdot u\) z morebitnim dodatnim faktorjem na koncu. Vsak tak par je dolžine kvečjemu \(4\), s preslikavo \(\rho\) pa se preslika v dva elementa dolžine kvečjemu \(2\). Torej v primeru \(r = 0\) velja \(\ell(x) = 4k\) in \(\ell(x_0), \ell(x_1) \leq 2k\), v primeru \(r = 1\) pa velja \(\ell(x_0), \ell(x_1) \leq 2k+1\). ◻

Proof. Vemo že, da velja \(\ell(x_0) + \ell(x_1) \leq \ell(x) + 1\). Naj bo \(\ell_b(x)\) število pojavitev črke \(b\) v besedi \(x\), zapisani alternirajoče z dolžino \(\ell(x)\). Analogno definiramo \(\ell_c(x), \ell_d(x)\).

• Vsaka pojavitev črke \(d\) ali \(ada\) v besedi \(x\) postane \(1\) v natanko enem od \(x_0, x_1\). Od tod sklepamo⁷⁴ \[\ell(x_0) + \ell(x_1) \leq \ell(x) + 1 - \ell_d(x)\] in zatorej \[\begin{aligned} \ell(x_{000}) + \cdots + \ell(x_{111}) &\leq (\ell(x_{00}) + 1) + \cdots + (\ell(x_{11}) + 1) \\ &\leq (\ell(x_0) + 1) + (\ell(x_1) + 1) + 4 \\ &\leq \ell(x) + 7 - \ell_d(x). \end{aligned}\]

• Vsaka pojavitev \(c\) ali \(aca\) v besedi \(x\) postane \(d\) v natanko enem od \(x_0, x_1\).⁷⁵ Od tod sklepamo \[\begin{aligned} \ell(x_{00}) + \cdots + \ell(x_{11}) &\leq \ell(x_0) + 1 + \ell(x_1) + 1 - \ell_c(x) \\ &\leq \ell(x) + 3 - \ell_c(x)\end{aligned}\] in zatorej \[\begin{aligned} \ell(x_{000}) + \cdots + \ell(x_{111}) &\leq (\ell(x_{00}) + 1) + \cdots + (\ell(x_{11}) + 1) \\ &\leq \ell(x) + 7 - \ell_c(x).\end{aligned}\]

• Vsaka pojavitev \(b\) ali \(aba\) v besedi \(x\) postane \(c\) v natanko enem od \(x_0, x_1\). Od tod sklepamo \[\begin{aligned} \ell(x_{000}) + \cdots + \ell(x_{111}) &\leq (\ell(x_{00}) + 1) + \cdots + (\ell(x_{11}) + 1) - \ell_b(x) \\ &\leq \ell(x) + 7 - \ell_b(x). \end{aligned}\]

Velja \(\ell_b(x) + \ell_c(x) + \ell_d(x) \geq \frac12 (\ell(x) - 1)\), zato je \(\ell_u(x) \geq \frac16 \ell(x) - 1\) za nek \(u \in \{ b,c,d\}\). Iz zgornjih neenakosti zato v vsaki od treh možnosti za \(u\) sledi \[\ell(x_{000}) + \cdots + \ell(x_{111}) \leq \ell(x) + 7 - \ell_u(x) \leq \frac56 \ell(x) + 8.\] ◻

Proof. Naj bo \(\omega = \omega_{\{ a,b,c,d \}}(\Gamma)\). Dokazati želimo, da je \(\omega = 1\).

Najprej prevedimo problem na grupo \(L\). Naj bo \(R\) množica predstavnikov odsekov \(L\) v \(\Gamma\). Torej je \(\Gamma = L \cdot R\). Naj bo \(M = \max \{ \ell(r) \mid r \in R \}\). Izberimo poljuben \(x \in B_{\Gamma}(n)\). Zapišemo ga lahko kot \(x = yz\) za neka \(y \in L, z \in R\). Pri tem velja \(\ell(y) \leq \ell(x) + \ell(z) \leq n + M\). Torej je \[\beta_\Gamma(n) \leq |\Gamma : L| \cdot |\{ y \in L \mid \ell(y) \leq n+M \}| \leq 128 \cdot |L \cap B_\Gamma(n+M)|.\]

Oceniti moramo torej še \(|L \cap B_\Gamma(n+M)|\). V ta namen izberimo poljuben \(x \in L \cap B_\Gamma(m)\) za nek \(m \in \mathbb{N}\). Naj bo \(m_{ijk} = \ell(x_{ijk})\) za \(i,j,k \in \{0,1\}\). Število možnosti za 8-terico elementov \((x_{000}, \dots, x_{111})\) je enako kvečjemu \(\beta_\Gamma(m_{000}) \cdots \beta_\Gamma(m_{111})\). Po definiciji \(\omega\) za vsak \(\epsilon > 0\) velja \(\beta_\Gamma(n) \leq A \cdot (\omega + \epsilon)^n\) za vsak \(n\) in neko konstanto \(A\). Torej je število možnosti za \((x_{000}, \dots, x_{111})\) in s tem za \(x \in L \cap B_\Gamma(m)\) kvečjemu \[A^8 \cdot (\omega + \epsilon)^{m_{000} + \cdots + m_{111}} \leq A^8 \cdot (\omega + \epsilon)^{\frac56 m + 8} \\ \leq C \cdot (\omega + \epsilon)^{\frac56 m}\] za neko konstanto \(C\), kjer smo v prvi neenakosti uporabili lemo (o krajšanju dolžin).

Za vsak \(n \in \mathbb{N}\) nazadnje torej velja \[\beta_\Gamma(n) \leq 128 \cdot C \cdot (\omega + \epsilon)^{\frac56 (n+M)}.\] Hkrati po definiciji \(\omega\) velja \(\beta_\Gamma(n) \geq C^\prime \cdot (\omega - \epsilon)^n\) za neko konstanto \(C^\prime\). Uporabimo \(n\)-ti koren, izlimitiramo \(n \to \infty\) in dobimo \[\omega - \epsilon \leq (\omega + \epsilon)^{\frac56}.\] Ker je bil \(\epsilon\) poljuben, sledi \(\omega = \omega^{\frac56}\), zato je \(\omega = 1\). ◻

Proof. Zgornja meja: Dokaz je v tem primeru bolj natančna različica dokaza zadnjega izreka. Iz leme (o krajšanju dolžin) sledi, da za nek \(x_{ijk}\) velja \(\ell(x_{ijk}) \leq \frac{5}{48} \ell(x) + 1\). Za element \(x_{ijk}\) imamo torej največ \(\beta_\Gamma(\frac{5}{48} \ell(x) + 1)\) možnosti. Za vse druge elemente množice \(\{ x_{000}, \dots, x_{111} \} \backslash \{ x_{ijk} \}\) pa imamo največ \(\beta_\Gamma(\frac18 \ell(x) + 1)\) možnosti.⁷⁶ Po submultiplikativnosti rastne funkcije velja \[\beta_\Gamma \left( \frac18 \ell(x) + 1 \right) \leq \beta_\Gamma \left( \frac{1}{48} \ell(x) + 1 \right)^6.\] Vseh možnosti za \(8\)-terico \((x_{000}, \dots, x_{111})\) je torej kvečjemu⁷⁷ \[8 \cdot \beta_\Gamma \left( \frac{1}{48} \ell(x) + 1 \right)^{6 \cdot 7 + 5}.\] Kot v dokazu zadnjega izreka od tod sledi \[\beta_\Gamma(n) \leq 128 \cdot |L \cap B_\Gamma(n+M)| \leq C \cdot \beta_\Gamma\left(\frac{1}{48} n + C\right)^{47}\] za neko konstanto \(C\). To neenakost zdaj iteriramo. V naslednjem koraku dobimo \[\begin{aligned} \beta_\Gamma(n) &\leq C \cdot \left( C \cdot \beta_\Gamma\left(\frac{1}{48} \left( \frac{1}{48} n + C \right) + C\right)^{47}\right)^{47} \\ &= C^{1 + 47} \cdot \beta_\Gamma \left( \frac{1}{48^2} n + C \left(1 + \frac{1}{48}\right) \right)^{47^2},\end{aligned}\] po \(t\) korakih pa dobimo neenakost \[\beta_\Gamma(n) \leq C^{1 + 47 + 47^2 + \cdots + 47^{t-1}} \cdot \beta_\Gamma \left( \frac{1}{48^t} n + C \left( 1 + \frac{1}{48} + \frac{1}{48^2} + \cdots + \frac{1}{48^{t-1}} \right) \right)^{47^t}.\] Izberimo \(t = \lceil \log_{48} n \rceil\). Tedaj je \(n/48^t \leq 1\), zato iz zadnje neenakosti dobimo \[\beta_\Gamma(n) \leq C^{47^t} \cdot \beta_\Gamma(D)^{47^t} = E^{47^t}\] za neki konstanti \(D, E\). Po izbiri \(t\) od tod nazadnje sledi \[\beta_\Gamma(n) \leq E^{47^{\log_{48} n + 1}} = e^{47 \cdot \log E \cdot 47^{\frac{\log n}{\log 48}}} \sim e^{n^{\log_{48} 47}},\] torej v izreku lahko vzamemo \(q = \log_{48} 47 < 1\). \(\checkmark\)

Spodnja meja: Dokaz je v tem primeru kombinacija samopodobnosti grupe \(\Gamma\) in zgornjega iterativnega argumenta. Funkcija \(\beta_\Gamma\) je ekvivalentna funkciji \(\beta_{\Gamma \times \Gamma}\). Hkrati za \(S = \{ a,b,c,d \}\) velja \(\beta_{\Gamma \times \Gamma, S \times 1 \cup 1 \times S \cup S \times S} = \beta_{\Gamma}^2\). Torej obstaja konstanta \(C > 1\), da je \[\beta_\Gamma(n)^2 \leq C \cdot \beta_\Gamma(Cn).\] To neenakost zdaj iteriramo. V naslednjem koraku dobimo \[\beta_\Gamma(n) \geq \frac{1}{C} \beta_\Gamma \left(\frac{n}{C}\right)^2,\] po \(t\) korakih pa dobimo neenakost \[\beta_\Gamma(n) \geq \frac{1}{C^{1 + 2 + 4 + \cdots + 2^{t-1}}} \cdot \beta_\Gamma \left( \frac{n}{C^t} \right)^{2^t} \geq \left( \beta_\Gamma \left( \frac{n}{C^t} \right) / C \right)^{2^t}.\] Izberimo \(t = \lfloor \log_C \frac{n}{m} \rfloor\) za nek dovolj velik \(m\), za katerega je \(\beta_\Gamma(m) > C\). Tedaj je \(C^t < \frac{n}{m}\), zato je \(\beta_\Gamma(n/C^t) > \beta_\Gamma(m)\). Iz zadnje neenakosti tako dobimo \[\beta_\Gamma(n) \geq \left( \beta_\Gamma(m)/C \right)^{2^t} = D^{2^t}\] za neko konstanto \(D > 1\). Po izbiri \(t\) od tod nazadnje sledi \[\beta_\Gamma(n) \geq D^{2^{\log_C{\frac{n}{m}} - 1}} \geq e^{\frac12 \cdot \log D \cdot 2^{-\log_C m} \cdot n^{\log_C 2}} \sim e^{n^{\log_C 2}},\] torej v izreku lahko vzamemo \(q = \log_C 2\). \(\checkmark\) ◻

Proof. Naj bo \(\mu\) desno translacijsko invariantna mera, ki opazi amenabilnost \(G\). Definirajmo novo mero \(\nu\) s predpisom \(\nu(A) = \int_G \mu(x \cdot A) \ d\mu(x)\). Trdimo, da je \(\nu\) iskana mera. Preverimo le, da je \(\nu\) levo in desno translacijsko invariantna. Z uporabo desne invariantnosti mere \(\mu\) izpeljemo, da za vsak \(y \in G\) velja \[\begin{aligned} \nu(y \cdot A) &= \int_G \mu(x \cdot y \cdot A) \ d \mu(x) \\ &= \inf_\Delta \sum_i \mu(\{ x \in G \mid a_{i-1} \leq \mu(x \cdot y \cdot A) < a_i \}) a_i \\ &= \inf_\Delta \sum_i \mu(\{ x \in G \mid a_{i-1} \leq \mu(x \cdot A) < a_i \} \cdot y^{-1}) a_i \\ &= \inf_\Delta \sum_i \mu(\{ x \in G \mid a_{i-1} \leq \mu(x \cdot A) < a_i \}) a_i \\ &= \int_G \mu(x\cdot A) \ d \mu(x) = \nu(A)\end{aligned}\] in \[\nu(A \cdot y) = \int_G \mu(x \cdot A \cdot y) \ d \mu(x) = \int_G \mu(x \cdot A) \ d\mu(x) = \nu(A).\] ◻

Proof. Zaprtost za podgrupe: Naj bo \(H \leq G\), kjer je \(G\) amenabilna. Izberimo neko množico predstavnikov odsekov \(H\) v \(G\), recimo ji \(R\). Naj bo \(A \subseteq H\). Definirajmo \(\mu_H(A) = \mu(R \cdot A)\). Na ta način dobimo želeno mero na \(H\). \(\checkmark\)

Zaprtost za kvociente: Naj bo \(N \unlhd G\), kjer je \(G\) amenabilna. Naj bo \(A \subseteq G/N\), torej \(A = \{ x_{\alpha}N \}_{\alpha}\). Definirajmo \(\mu_{G/N}(A) = \mu(\bigcup_{\alpha} x_\alpha N)\). Na ta način dobimo želeno mero na \(G/N\). \(\checkmark\)

Zaprtost za razširitve: Naj bo \(N \unlhd G\), kjer sta \(N\) in \(G/N\) amenabilni z merama \(\nu\) in \(\sigma\). Naj bo \(A \subseteq G\). Definirajmo \(f_A \colon G/N \to \mathbb{R}\), \(xN \mapsto \nu(N \cap xA)\). Definirajmo \(\mu(A) = \int_{G/N} f_A \ d \sigma\). Na ta način dobimo želeno mero na \(G\). Preverimo le levo translacijsko invariantnost. Za \(y \in G\) velja⁸¹ \[\begin{aligned} \mu(yA) &= \int_{G/N} f_{yA}(xN) \ d \sigma(xN) \\ &= \int_{G/N} \nu(N \cap xyA) \ d \sigma(xN) \\ &= \int_{G/N} \nu(N \cap xA) \ d \sigma(xN) \\ &= \int_{G/N} f_A(xN) \ d \sigma(xN) = \mu(A).\end{aligned}\]

Končne in abelove grupe: Končne grupe so jasno opremljene z ustrezno mero. Prav tako velja za grupo \(\mathbb{Z}\). Od tod in že dokazanih zaprtosti amenabilnosti sledi, da so končno generirane abelove grupe tudi amenabilne. Za neskončno generirane grupe se moramo malo bolj potruditi.

 ◻

Proof. Dokazali bomo le implikacijo iz leve v desno. Za dokaz obratne implikacije bi potrebovali kar nekaj funkcionalne analize, zato ga izpustimo.

Naj bo \(X_n\) Følnerjevo zaporedje v \(G\). Amenabilnost dokažemo kot v zgledu grupe \(\mathbb{Z}\). Izberimo neglavni ultrafilter \(\mathcal{U}\) na \(\mathbb{N}\). Za \(A \subseteq G\) naj bo \(A_n = A \cap X_n\). Definirajmo \(\mu(A) = \lim_\mathcal{U}|A_n|/|X_n|\). To je želena mera na \(G\). Preverimo le desno translacijsko invarianco z elementom \(s \in S\). Velja \(|As \cap X_n| = |A \cap X_n s^{-1}|\) in \(A \cap X_n s^{-1} \subseteq A_n \cup \partial X_n\),⁸³ od koder sledi \[\frac{|As \cap X_n|}{|X_n|} \leq \frac{|A_n|}{|X_n|} + \frac{|\partial X_n|}{|X_n|}.\] V limiti je zato \(\mu(As) \leq \mu(A) + 0\). Od tod zdaj izpeljemo še drugo neenakost \(\mu(A) = \mu(Ass^{-1}) \leq \mu(As)\). S tem je res \(\mu(As) = \mu(A)\). ◻

Proof. Opazujmo množice \(X_n = B_{G,S}(n)\). Velja \(|X_n| = \beta_{G,S}(n)\) in \(|\partial X_n| = \beta_{G,S}(n+1) - \beta_{G,S}(n)\). Ker je \(G\) podeksponentne rasti, velja \[1 = \lim_{n \to \infty} \beta_{G,S}(n)^{1/n} \geq\footnote{Konvergenčni radij vrste $\sum_n \beta_{G,S}(n) x^n$ je enak $1$.} \liminf_{n \to \infty} \frac{\beta_{G,S}(n+1)}{\beta_{G,S}(n)} \geq 1,\] zato je \(\liminf_{n \to \infty} |\partial X_n|/|X_n| = 1 - 1 = 0\). Torej ima \(\{ X_n \}_{n \in \mathbb{N}}\) Følnerjevo podzaporedje. ◻

Proof. Dokazali bomo le implikacijo iz leve v desno, ki pojasni, da so paradoksalne grupe res protislovne v primeru, ko lahko merimo velikosti podmnožico z neko mero.

Naj bo \(G\) paradoksalna grupa, torej \[G = \bigoplus_{i=1}^n A_i \oplus \bigoplus_{j = 1}^m B_j, \quad G = \bigoplus_{i=1}^n x_i A_i = \bigoplus_{j = 1}^m y_j B_j.\] Predpostavimo, da je \(G\) amenabilna z normalizirano mero \(\mu\). Velja \[1 = \mu(G) = \sum_{i = 1}^n \mu(A_i) + \sum_{j = 1}^m \mu(B_j)\] in hkrati \[1 = \mu(G) = \sum_{i = 1}^n \mu(x_i A_i) = \sum_{i = 1}^n \mu(A_i), \quad 1 = \mu(G) = \sum_{j = 1}^m \mu(y_j B_j) = \sum_{j = 1}^m \mu(B_j),\] od koder izpeljemo protislovje \(1 = 1+1\). ◻

Proof. Naj bo \(G\) paradoksalna grupa, torej \[G = \bigoplus_{i=1}^n A_i \oplus \bigoplus_{j = 1}^m B_j, \quad G = \bigoplus_{i=1}^n x_i A_i = \bigoplus_{j = 1}^m y_j B_j.\] Izberimo en element iz vsake orbite delovanja \(G\) na \(X\), vsi ti predstavniki naj tvorijo množico \(R\). Tedaj zaradi prostosti delovanja velja \[X = \bigoplus_{i = 1}^n A_i.R \oplus \bigoplus_{j = 1}^m B_j.R = \bigoplus_{i = 1}^n x_iA_i . R = \bigoplus_{j = 1}^m y_jB_j . R,\] torej je \(X\) res \(G\)-paradoksalna. ◻

Proof. Naj bo \(G =\langle S \rangle\). Izrek (enakomerna Titsova alternativa) zagotovi \(N = N(d)\), za katerega obstajata \(a,b \in S^N\), da je \(\langle a,b \rangle \cong F_2\). Torej je \[\omega_S(G) = \lim_{n \to \infty} \sqrt[n]{\beta_{G,S}(n)} = \lim_{n \to \infty} \sqrt[nN]{\beta_{G,S}(nN)}\] Ker je \(\beta_{G,S^N}(n) = \beta_{G,S}(nN)\), je zadnja limita enaka \[\lim_{n \to \infty} \sqrt[nN]{\beta_{G, S^N}(n)} = \sqrt[N]{\omega_{S^N}(G)} \geq \sqrt[N]{\omega_{\{a,b \}}(G)} \geq \sqrt[N]{3} > 1+ \epsilon.\] ◻

Proof. Obravnavajmo \(W\) in \(W \; wr. \;A\) kot podgrupi \(\mathop{\mathrm{Sym}}(P^*)\). Iz zadnjega zgleda je razvidno, da velja \(\varphi_1(A), \varphi_2(\bar A) \leq W \; wr. \;A\), zato je \(W \leq W \; wr. \;A\). Dokazati moramo še obratno vsebovanost.

Izberimo poljubna \(a,b \in A\). Tedaj je \([\bar a, \bar b^y] \in \langle A, \bar A \rangle = W\). Velja \[(p_1p_2\cdots p_n).[\bar a, \bar b^y] = (p_1 \cdots p_n).\bar a^{-1} \cdot y^{-1} \bar b^{-1} y \cdot \bar a \cdot y^{-1} \bar b y.\] Zadnji element je enak \[\begin{cases} \mathbf{1}\cdots \mathbf{1}\mathbf{2}(p_{m+1}.a^{-1})p_{m+2}\cdots p_n. y^{-1} \bar b^{-1} y \bar a y^{-1} \bar b y; & p_1 = \cdots = p_{m-1} = \mathbf{1}, \ p_m = \mathbf{2}\\ (p_1\cdots p_n).y^{-1} \bar b^{-1} y \cdot \bar a \cdot y^{-1} \bar b y; & \text{sicer,} \end{cases}\] kar se poenostavi do \[\begin{cases} \mathbf{1}\cdots \mathbf{1}\mathbf{2}(p_{m+1}.[a,b])p_{m+2}\cdots p_n; & p_1 = \cdots = p_{m-1} = \mathbf{1}, \ p_m = \mathbf{2}, \ m > 1 \\ \mathbf{2}p_2 p_3 \cdots p_n; & p_1 = \mathbf{2}\\ p_1\cdots p_n; & \text{sicer.} \end{cases}\] Torej je \({\textbf [} [\bar a, \bar b], 1, 1, 1, 1, 1, 1 {\textbf ]} = [\bar a, \bar b^y] \in W\). Ni težko preveriti, da velja \(A = [A,A]\), zato od tod izpeljemo \({\textbf [} \bar A, 1, 1, 1, 1, 1, 1 {\textbf ]} \leq W\). Podobno z opazovanjem elementa \([\bar a, \bar b^x]\) dobimo vsebovanost \({\textbf [} 1, A, 1, 1, 1, 1, 1 {\textbf ]} \leq W\).

Naj bo \(t \in A\) in označimo \(p = t.\mathbf{1}\in P\). Tedaj je \[(p p_2 \cdots p_n).t^{-1} {\textbf [} \bar a, 1, 1, 1, 1, 1, 1 {\textbf ]} t = \mathbf{1}(p_2 \cdots p_n.\bar a).t = p(p_2 \cdots p_n.\bar a),\] torej je \(t^{-1} {\textbf [} \bar a, 1, 1, 1, 1, 1, 1 {\textbf ]} t = {\textbf [} 1, \dots, 1, \bar a, 1, \dots, 1 {\textbf ]}\), kjer v zadnjem elementu \(\bar a\) stoji na poziciji \(p\).

S konjugiranjem z ustreznim elementom \(A\) torej izpeljemo, da \(W\) vsebuje \({\textbf [} 1, \dots, 1, A, 1, \dots, 1 {\textbf ]}\) in \({\textbf [} 1, \dots, 1, \bar A, 1, \dots, 1 {\textbf ]}\), od koder sledi, da \(W\) vsebuje celo \({\textbf [} W, W, \dots, W {\textbf ]}\). Ker seveda \(W\) vsebuje tudi \(A\), nazadnje izpeljemo želeno vsebovanost \({\textbf [} W, W, \dots, W {\textbf ]} \rtimes A = W \; wr. \;A \leq W\). ◻

Ideja dokaza. Trdimo, da grupa \(W\) vsebuje prosti monoid na dveh generatorjih. Izberimo \(u,v \in A\), \(u \neq v\), z lastnostjo \(\mathbf{1}.u = \mathbf{1}.v = \mathbf{2}\), \(\mathbf{2}.u = \mathbf{2}.v = \mathbf{1}\). Naj bo \(a = \bar u u\) in \(b = \bar v v\). Tedaj \(a\) in \(b\) generirata prosti monoid, saj nobena netrivialna beseda v \(a,b\) ne deluje trivialno na \(P^*\). Dokaz tega dejstva izpustimo. ◻

Ideja dokaza. Naj bo \(w\) beseda s črkami v \(S^\prime\). Predstavimo jo v obliki \({\textbf [} w_1, \dots, w_7 {\textbf ]} \sigma\) za neke besede \(w_i\) s črkami v \(S\) in \(\sigma \in \mathop{\mathrm{Sym}}(P)\). Podobno kot pri Grigorčukovi grupi zdaj analiziramo, kakšne so dolžine besed \(w_i\) v odvisnosti od strukture \(w\) in kakšna krajšanja se zgodijo v vsaki od besed \(w_i\). ◻

Dokaz \(\Omega(W) = 1\). Naj bo \(S_0 = \{ a, b, c \}\) generirajoča množica grupe \(W\) iz prve trditve prejšnjega razdelka. Ker so vsi elementi \(S_0\) reda \(2\), je \(\beta_{W,S_0}(n) \leq 3 \cdot 2^{n-1}\), zato je \(\omega_{S_0}(W) \leq 2\).

Naj bo \(S_{i+1} = S_i^\prime\) za \(i \geq 0\), kjer uporabljamo drugo lastnost iz trditve v zadnjem razdelku. Velja \[\langle S_0 \rangle = W, \ \langle S_1 \rangle = W \; wr. \;A \cong W, \ \langle S_2 \rangle = (W \; wr. \;A) \; wr. \;A \cong W \; wr. \;A \cong W, \dots\] Po ustrezni identifikaciji v \(\mathop{\mathrm{Sym}}(P^*)\) lahko torej množice \(S_i\) vidimo kot generirajoče množice grupe \(W\).

Naj bo \(\Lambda_0 = 2\). Za \(i \geq 0\) naj bo \(\eta_i \in (0, \frac12)\) enolična rešitev enačbe \[\frac{30^{\eta_i}}{\eta_i^{\eta_i} (1 - \eta_i)^{1 - \eta_i}} = \Lambda_i^{1 - \eta_i}.\] Za tem definirajmo še \(\Lambda_{i+1} = \Lambda_i^{1 - \eta_i} > 1\). Ni težko preveriti, da za vsak \(i\) velja \(0 < \eta_{i+1} < \eta_i\), zato obstaja limita \(\eta = \lim_{i \to \infty} \eta_i \geq 0\). Podobno za vsak \(i\) velja \(1 < \Lambda_{i+1} < \Lambda_i\), zato obstaja limita \(\Lambda = \lim_{i \to \infty} \Lambda_i \geq 1\).

Iz definicije \(\eta_i\) in \(\Lambda_i\) sledi enakost \(\Lambda^{1-\eta} = \Lambda\), kar implicira \(\Lambda = 1\) ali \(\eta = 0\). V slednjem primeru sledi \(\Lambda = 1\), torej v obeh primerih sklepamo \(\Lambda = 1\). Hkrati po zadnji trditvi za vsak \(i\) velja neenakost \(\omega_{S_i}(W) \leq \Lambda_i\). Od tod sledi \(\Omega(W) \leq \lim_{i \to \infty} \omega_{S_i}(W) = 1\). Dokaz je zaključen. ◻