Boundedly generated group

Last updated May 04, 2024

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 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.
Bounded generation goes to extension: if a group G has a normal subgroup N such that both N and G/N are boundedly generated, then so is G itself.
Any quotient group of a boundedly generated group is also boundedly generated.
A finitely generated torsion group must be finite if it is boundedly generated; equivalently, an infinite finitely generated torsion 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·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₂(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 counterexamples

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 torsion 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 torsion groups were constructed by Aleshin, Olshanskii, and Grigorchuk, using automata. Consequently, free groups of rank at least two are not boundedly generated.

Symmetric 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

where e is Euler's number (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 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 }\,d\alpha ,

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

f_{\alpha }(g)=\lim _{n\rightarrow \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 yield an infinite-dimensional family of pseudocharacters (see 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ⁿ as n tends to ±∞. Furthermore, gⁿ·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ⁿ·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-orbits of the fixed points h_i^±∞, the fixed points of the h_i and all their conjugates. Since X is uncountable, there is an element of g with fixed points outside X₀ and a point w outside X₀ different from these fixed points. Then for some 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ⁿ·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.

Related Research Articles

In abstract algebra, a cyclic group or monogenous group is a group, denoted C_n, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a generator of the group.

In the mathematical disciplines of topology and geometry, an orbifold is a generalization of a manifold. Roughly speaking, an orbifold is a topological space which is locally a finite group quotient of a Euclidean space.

In mathematics, specifically group theory, the free product is an operation that takes two groups G and H and constructs a new group G ∗ H. The result contains both G and H as subgroups, is generated by the elements of these subgroups, and is the “universal” group having these properties, in the sense that any two homomorphisms from G and H into a group K factor uniquely through a homomorphism from G ∗ H to K. Unless one of the groups G and H is trivial, the free product is always infinite. The construction of a free product is similar in spirit to the construction of a free group.

In the mathematical subject of geometric group theory, the growth rate of a group with respect to a symmetric generating set describes how fast a group grows. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length n.

In mathematics, a hyperbolic metric space is a metric space satisfying certain metric relations between points. The definition, introduced by Mikhael Gromov, generalizes the metric properties of classical hyperbolic geometry and of trees. Hyperbolicity is a large-scale property, and is very useful to the study of certain infinite groups called Gromov-hyperbolic groups.

In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov. The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.

In mathematics, a matrix group is a group G consisting of invertible matrices over a specified field K, with the operation of matrix multiplication. A linear group is a group that is isomorphic to a matrix group.

In mathematics, the Tits alternative, named after Jacques Tits, is an important theorem about the structure of finitely generated linear groups.

In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In mathematics, the ping-pong lemma, or table-tennis lemma, is any of several mathematical statements that ensure that several elements in a group acting on a set freely generates a free subgroup of that group.

In the mathematical subject of group theory, the Stallings theorem about ends of groups states that a finitely generated group $has more than one end if and only if the group admits a nontrivial decomposition as an amalgamated free product or an HNN extension over a finite subgroup. In the modern language of Bass-Serre theory the theorem says that a finitely generated group has more than one end if and only if admits a nontrivial action on a simplicial tree with finite edge-stabilizers and without edge-inversions.$

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem.

In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group in terms of the length of that relation. The growth type of the Dehn function is a quasi-isometry invariant of a finitely presented group. The Dehn function of a finitely presented group is also closely connected with non-deterministic algorithmic complexity of the word problem in groups. In particular, a finitely presented group has solvable word problem if and only if the Dehn function for a finite presentation of this group is recursive. The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic isoperimetric inequality for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a minimal surface in a Riemannian manifold in terms of the length of the boundary curve of that surface.

In mathematics, the concept of a relatively hyperbolic group is an important generalization of the geometric group theory concept of a hyperbolic group. The motivating examples of relatively hyperbolic groups are the fundamental groups of complete noncompact hyperbolic manifolds of finite volume.

In the mathematical subject of group theory, a one-relator group is a group given by a group presentation with a single defining relation. One-relator groups play an important role in geometric group theory by providing many explicit examples of finitely presented groups.

In the mathematical subject of group theory, a co-Hopfian group is a group that is not isomorphic to any of its proper subgroups. The notion is dual to that of a Hopfian group, named after Heinz Hopf.

In the mathematical subject of group theory, the Howson property, also known as the finitely generated intersection property (FGIP), is the property of a group saying that the intersection of any two finitely generated subgroups of this group is again finitely generated. The property is named after Albert G. Howson who in a 1954 paper established that free groups have this property.

In the mathematical subject of geometric group theory, an acylindrically hyperbolic group is a group admitting a non-elementary 'acylindrical' isometric action on some geodesic hyperbolic metric space. This notion generalizes the notions of a hyperbolic group and of a relatively hyperbolic group and includes a significantly wider class of examples, such as mapping class groups and Out(F_n).

In geometric group theory, a discipline of mathematics, subgroup distortion measures the extent to which an overgroup can reduce the complexity of a group's word problem. Like much of geometric group theory, the concept is due to Misha Gromov, who introduced it in 1993.

References

Carter, David & Keller, Gordon (1984). "Elementary expressions for unimodular matrices". Communications in Algebra. 12 (4): 379–389. doi:10.1080/00927878408823008.

Epstein, David & Fujiwara, Koji (1997). "The second bounded cohomology of word-hyperbolic groups". Topology. 36 (6): 1275–1289. doi:10.1016/S0040-9383(96)00046-8.

Ghys, Etienne & Barge, Jean (1988). "Surfaces et cohomologie bornée". Inventiones Mathematicae. 92 (3): 509–526. Bibcode:1988InMat..92..509B. doi:10.1007/BF01393745. S2CID 123573552.

Grigorchuk, R.I. (1980). "On Burnside's problem on periodic groups". Functional Anal. Appl. 14: 41–43. doi:10.1007/BF01078416. S2CID 120470429.

Grigorchuk, R.I. (1994). "Some results in bounded cohomology". London Mathematical Society Lecture Note Series. 224: 111–163. ISBN 0-521-46595-8.

Landau, Edmund (1974). Handbuch der Lehrer von der Verteilung der Primzahlen, Vol. I. Chelsea. ISBN 0-8284-0096-2. (see pages 222-229, also available on the Cornell archive)

Lubotzky, Alexander; Segal, Dan (2003). Subgroup growth. Progress in Mathematics. Birkhäuser. ISBN 3-7643-6989-2..

Polterovich, Leonid & Rudnick, Zeev (2004). "Stable mixing for cat maps and quasi-morphisms of the modular group". Erg. Th. & Dynam. Syst. 24 (2): 609–619. arXiv: math/0009143 . doi:10.1017/S0143385703000531. S2CID 16061963.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.