Boundedly generated group

In mathematics, a group is called boundedly generated if it can be expressed as a finite product of cyclic subgroups. The property of bounded generation is also closely related with the congruence subgroup problem (see harvnb|Lubotzky|Segal|2003).

Definitions

A group "G" is called "boundedly generated" if there exists a finite subset "S" of "G" and a positive integer "m" such that every element "g" of "G" can be represented as a product of at most "m" powers of the elements of "S": : $g\; =\; s\_1^\{k\_1\}\; cdots\; s\_m^\{k\_m\},$ where $s\_i\; in\; S$ and $k\_i$ are integers.

The finite set "S" generates "G", so a boundedly generated group is finitely generated.

An equivalent definition can be given in terms of cyclic subgroups. A group "G" is called "boundedly generated" if there is a finite family "C"₁, …, "C"_"M" of not necessarily distinct cyclic subgroups such that "G" = "C"₁…"C"_"M" as a set.

Properties

* Bounded generation is unaffected by passing to a subgroup of finite index: if "H" is a finite index subgroup of "G" then "G" is boundedly generated if and only if "H" is boundedly generated.
* Any quotient group of a boundedly generated group is also boundedly generated.
* A finitely generated periodic group must be "finite" if it is boundedly generated; equivalently, an "infinite" finitely generated periodic group is not boundedly generated.

A "pseudocharacter" on a discrete group "G" is defined to be a real-valued function "f" on a "G" such that : "f"("gh") − "f"("g") − "f"("h") is uniformly bounded and "f"("g"^"n") = "n"·"f"("g").

* The vector space of pseudocharacters of a boundedly generated group "G" is finite dimensional.

Examples

* If "n" ≥ 3, the group "SL"_"n"(Z) is boundedly generated by its "elementary subgroups," formed by matrices differing from the identity matrix only in one off-diagonal entry. In 1984, Carter and Keller gave an elementary proof of this result, motivated by a question in algebraic K-theory.
* A free group on at least two generators is not boundedly generated (see below).
* The group "SL"_"2"(Z) is not boundedly generated, since it contains a free subgroup with two generators of index 12.
* A Gromov-hyperbolic group is boundedly generated if and only if it is "virtually cyclic" (or "elementary"), i.e. contains a cyclic subgroup of finite index.

Free groups are not boundedly generated

Several authors have stated in the mathematical literature that it is obvious that finitely generated free groups are not boundedly generated. This section contains various obvious and less obvious ways of proving this. Some of the methods, which touch on bounded cohomology, are important because they are geometric rather than algebraic, so can be applied to a wider class of groups, for example Gromov-hyperbolic groups.

Since for any "n" ≥ 2, the free group on 2 generators "F"₂ contains the free group on "n" generators "F"_"n" as a subgroup of finite index (in fact "n" – 1), once one non-cyclic free group on finitely many generators is known to be not boundedly generated, this will be true for all of them. Similarly, since "SL"₂(Z) contains "F"₂ as a subgroup of index 12, it is enough to consider "SL"₂(Z). In other words, to show that no "F"_"n" with "n" ≥ 2 has bounded generation, it is sufficient to prove this for one of them or even just for "SL"₂(Z) .

Burnside couterexamples

Since bounded generation is preserved under taking homomorphic images, if a single finitely generated group with at least two generators is known to be not boundedly generated, this will be true for the free group on the same number of generators, and hence for all free groups. To show that no (non-cyclic) free group has bounded generation, it is therefore enough to produce one example of a finitely generated group which is not boundedly generated, and any finitely generated infinite periodic group will work. The existence of such groups constitutes Golod and Shafarevich's negative solution of the generalized Burnside problem in 1964; later, other explicit examples of infinite finitely generated periodic groups were constructed by Aleshin, Olshanskii, and Grigorchuk, using automata. Consequently, free groups of rank at least two are not boundedly generated.

ymmetric groups

The symmetric group "S"_"n" can be generated by two elements, a 2-cycle and an "n"-cycle, so that it is a quotient group of "F"₂. On the other hand, it is easy to show that the maximal order "M"("n") of an element in "S"_"n" satisfies

: log "M"("n") ≤ n/e

(Edmund Landau proved the more precise asymptotic estimate log "M"("n") ~ ("n" log "n")^1/2). In fact if the cycles in a cycle decomposition of a permutation have length "N"₁, ..., "N"_"k" with "N"₁ + ··· + "N"_"k" = "n", then the order of the permutation divides the product "N"₁ ···"N"_"k", which in turn is bounded by ("n"/"k")^"k", using the inequality of arithmetic and geometric means. On the other hand, ("n"/"x")^"x" is maximized when "x"="e". If "F"₂ could be written as a product of "m" cyclic subgroups, then necessarily "n"! would have to be less than or equal to "M"("n")^"m" for all "n", contradicting Stirling's asymptotic formula.

Hyperbolic geometry

There is also a simple geometric proof that that "G" = "SL"₂(Z) is not boundedly generated. It acts by Möbius transformations on the upper half-plane H, with the Poincaré metric. Any compactly supported 1-form α on a fundamental domain of "G" extends uniquely to a "G"-invariant 1-form on H. If "z" is in H and γ is the geodesic from "z" to "g"("z"), the function defined by :$F(g)equiv\; F\_\{alpha,z\}(g)=int\_\{gamma\},\; alpha$

satisfies the first condition for a pseudocharacter since by the Stokes theorem :$F(gh)\; -\; F(g)-F(h)\; =\; int\_\{Delta\},\; dalpha,$

where Δ is the geodesic triangle with vertices "z", "g"("z") and "h"^-1("z"), and geodesics triangles have area bounded by π. The homogenized function

:$f\_alpha(g)\; =\; lim\_\{n\; ightarrow\; infty\}\; F\_\{alpha,z\}(g^n)/n$

defines a pseudocharacter, depending only on α. As is well known from the theory of dynamical systems, any orbit ("g"^"k"("z")) of a hyperbolic element "g" has limit set consisting of two fixed points on the extended real axis; it follows that the geodesic segment from "z" to "g"("z") cuts through only finitely many translates of the fundamental domain. It is therefore easy to choose α so that "f"_α equals one on a given hyperbolic element and vanishes on a finite set of other hyperbolic elements with distinct fixed points. Since "G" therefore has an infinite-dimensional space of pseudocharacters, it cannot be boundedly generated.

Dynamical properties of hyperbolic elements can similarly be used to prove that any non-elementary Gromov-hyperbolic group is not boundedly generated.

Brooks pseudocharacters

Robert Brooks gave a combinatorial scheme to produce pseudocharacters of any free group "F"_"n"; this scheme was later shown to yieldan infinite-dimensional family of pseudocharacters (see harvnb|Grigorchuk|1994). Epstein and Fujiwara later extended these results to all non-elementary Gromov-hyperbolic groups.

Gromov boundary

This simple folklore proof uses dynamical properties of the action of hyperbolic elements on the Gromov boundary of a Gromov-hyperbolic group. For the special case of the free group "F"_"n", the boundary (or space of ends) can be identified with the space "X" of semi-infinite reduced words

:"g"₁ "g"₂ ···

in the generators and their inverses. It gives a natural compactification of the tree, given by the Cayley graph with respect to the generators. A sequence of semi-infinite words converges to another such word provided that the initial segments agree after a certain stage, so that "X" is compact (and metrizable). The free group acts by left multiplication on the semi-infinite words. Moreover any element "g" in "F"_"n" has exactly two fixed points "g"^±∞, namely the reduced infinite words given by the limits of "g"^"n" as "n" tends to ±∞. Furthermore "g"^"n"·"w" tends to "g"^{±∞ as "n" tends to ±∞ for any semi-infinite word "w"; and more generally if "w"_"n" tends to "w"≠ "g" ±∞, then "g""n"·"w"_"n" tends to "g"+∞ as "n" tends to ∞.}

If "F"_"n" were boundedly generated, it could be written as a product of cyclic groups "C"_"i"generated by elements "h"_"i". Let "X"₀ be the countable subset given by the finitely many "F"_"n"-orbitsof the fixed points "h"_"i" ^±∞, the fixed points of the "h"_"i" and all their conjugates. Since "X" is uncountable, thereis an element of "g" with fixed points outside "X"₀ and a point "w" outside "X"₀ different from these fixed points. Then forsome subsequence ("g"_m) of ("g"ⁿ)

:"g"_"m" = "h"₁^"n"("m",1) ··· "h"_"k"^"n"("m","k"), with each "n"("m","i") constant or strictly monotone.

On the one hand, by successive use of the rules for computing limits of the form "h"^"n"·"w"_"n", the limit of the right hand side applied to "x" is necessarily a fixed point of one of the conjugates of the "h"_"i"'s. On the other hand, this limit also must be "g"^+∞, which is not one of these points, a contradiction.

References

*cite journal
author = Carter, David and Keller, Gordon|title= Elementary expressions for unimodular matrices|journal= Comm. Alg.|volume=12|year=1984|pages=379–389|doi= 10.1080/00927878408823008

*cite journal
author= Epstein, David and Fujiwara, Koji| title = The second bounded cohomology of word-hyperbolic groups| journal=Topology|volume=36|year=1997|pages=1275–1289| doi = 10.1016/S0040-9383(96)00046-8

*cite journal | author= Ghys, Etienne and Barge, Jean| title= Surfaces et cohomologie bornée| journal=Inventiones mathematicae| year=1988|volume=92
pages=509–526| doi= 10.1007/BF01393745

*cite journal
author=Grigorchuk, R.I.| title=On Burnside's problem on periodic groups|journal= Functional Anal. Appl.|volume= 14|year =1980|pages=41–43

*cite journal
author= Grigorchuk, R.I.|title=Some results in bounded cohomology |journal =London Mathematical Society Lecture Note Series|volume=224|year =1994|pages=111–163
id = ISBN 0521465958

*cite book
author = Landau, Edmund |title =Handbuch der Lehrer von der Verteilung der Primzahlen, Vol. I|publisher =Chelsea|year= 1974| id = ISBN 0828400962 (see pages 222-229, also available on the Cornell archive)

*citation
last = Lubotzky|first=Alexander|last2=Segal|first2= Dan | title = Subgroup growth | series= Progress in Mathematics| publisher=Birkhäuser|year=2003
id= ISBN 3764369892.

*cite journal | author = Polterovich, Leonid and Rudnick, Zeev| title= Stable mixing for cat maps and quasi-morphisms of the modular group| year=2004| journal = Erg. Th. & Dynam. Syst.| volume=24|pages=609–619| doi= 10.1017/S0143385703000531