Introducing Growth of Groups
March 14, 2017
The growth of a group is an aesthetically pleasing large-scale property that is borderline geometric and algorithmic.
I will give an overview on the research on growth by historical and intuitive examples.
- Dehn’s Three Decision Problems
- Gauss Circle Problem - Round Counting
- Changing the Norm - Pointy Counting (Optional)
- Growth of Groups
- Types of Growth: How Fast? How Regular?
- The Curious Nilpotent Regime
- Sources and Additional Material
- More: About Intermediate Growth
I want to introduce you to the particularly beautiful group counting problem of how many elements can be spelled with letters?
The growth function of a group is a large-scale geometric property that is connected to two out of three of Dehn’s decision problems: the isomorphism problem and the Word problem.
Dehn’s Three Decision Problems
In 1911, the mathematician Max Dehn proposed three fundamental decision problems in group theory.
- The Word Problem: whether there is a procedure to determine whether two words in a group represent the same element.
- The Conjugacy Problem: whether there is a procedure to determine whether two words are conjugate to each other in a group.
- The Isomorphism Problem: whether there is procedure to determine whether two groups are isomorphic.
Dehn’s three questions are remarkable in that they precede by many years the formalization of “procedure” as “algorithm” by Church, Turing, et al. Source.
It is known by the work of Boone and Novikov in the 1954 that these three problems are undecidable.A problem is decidable if there exists a computable function giving an exact answer for any instance of a problem, undecidable when no computable function that can give an answer to every instance there exists. Source. The construction is not so direct as the Markov-Post construction and involves starting with free groups and performing a number of HNN-extensions and/or free products with amalgamation. Source Studying which groups have procedures and why is still an active area of research. I will be talking about growth, a property of groups which gives us some partial resolution to the Word problem and the isomorphism problem in terms of classifying groups.
Gauss Circle Problem - Round Counting
Given a circle of radius centered at the origin of the lattice , how does the number of points in the circle grow as ?
Let be the number of lattice points contained in the circle. A reasonable first guess is to count the lattice points with a Riemann sum. Indeed, the number of lattice points roughly corresponds to the number of unit squares contained in the circle. going to infinity is like “zooming out” on the lattice while keeping the size of the circle constant, and hence, as , the unit area becomes an infinitesimal area element.
Let be the error term of our approximation. Then, a reasonable guess is that the area grows as
Remarking that the “fuzzy” part of our approximation comes at the boundary of the circle, we can arrive at Gauss’ conclusion in 1801 that the error term is at most linear,
Nowadays, it is conjectured that
which is also the optimal bound, as proven by Hardy and Landau.
Changing the Norm - Pointy Counting (Optional)
How the ball which encloses our vertices changes with the norm.
Our counting function for the Gauss circle was implicitly defined as the intersection of and the closed Euclidean () ball of radius centered at the origin,
We could also define a counting function for the Gauss circle with the -norm instead of the -norm as we did previously, and the resulting ball would be a rhombus. Denoting the -ball of radius with , we may define a new counting function by
This new counting problem actually has a very neat solution given by Pick’s Theorem which generalizes to all polygons.
Pick tells us that the area of a polygon inside can be given in terms of its lattice points in the interior of the polygon and the number of lattice points on the boundary.
Example of a polygon inside a lattice. The red vertices are the lattice points and the green verticles are the boundary points of our polygon.
Since the number of lattice points of our (in our case, this is the rhombus of base and height ) is what we are interested in here, we may manipulate picks formula to look like:
Let’s verify this equation when . Our rhombus with base and height 1 indeed satisfies Pick’s theoremVerify that , and in this case. .
As we rescale the our rhombus by , area gets rescaled by a factor of and the boundary by a linear factor of (an easy way to see this is to ‘unwind’ the boundary into a line). Therefore, our counting function is given by the following:
and substituing our findings from the case, this gives us the full solution to our counting problem
The takeaway here is that the “round counting” Gauss circle problem is a challenging one, while the “pointy counting” problem, which is to count the number of lattice points contained in and on a n-dilate of a polygon, is fairly straightforward one in comparisonFor the curious, what we just did associating the -dilate of a 2-dimensional polytope with a polynomial has an analogue in d-dimensions, given by the theory of Ehrhart polynomials. .
Growth of Groups
In the previous, we swapped the metric associated with the -ball from the -norm to the -norm, and obtained a whole new counting problem.
We can also swap the lattice for a Cayley graph of group!
A Cayley graph is constructed from a group by choosing a generating set .
- Each element is assigned a vertex.
- Any is assigned different directed edge identification (often represented by an arrow).
- For any , , the vertices corresponding to and are joined by the directed edge . Going the opposite direction from the edge corresponds to right multiplication by .
Let’s look at examples:
Cayley graphs encode all the information contained in a group, because it tells us about all the elements in the group, and how to multiply them together. To figure out what multiplies to in the group with generating set , we start at in the graph, then follow the path given by the decomposition of into its generators .
A Cayley graph is also equipped with a word metric, denoted by assigning the length to each edgeThe subscript of is in the notation to emphasize how the distance is totally dependent on the chosen generating set , which are precisely the edges in the Cayley graph. .
In our Cayley graph of with standard generators :
- the word-metric ball of radius 0 contains only the point ,
- the ball of radius 1 contains every point that is at most an edge away from the origin, ,
- the ball of radius 2 contains the points that are at most two edges away from the origin,
- and so on.
We can now remark that the ball of radius defined by the word metric is a rhombus of base and height . Thus, this this word metric ball definition on exactly coincides with the -norm on !
The growth function of a group with a generating set is the number of vertices of the Cayley graph contained in the ball of radius .
If we denote the growth function by being poor notation here because our group is , then the growth function is precisely
Punchline: because the Cayley graph of is precisely its lattice representation, and because the -norm on is exactly the word metric under standard generators, the growth of under standard generators is just the counting function!
Types of Growth: How Fast? How Regular?
There are two crucial and orthogonal properties to the classification of growth in groups.
The first one, the growth rate, is a familiar concept from calculus. The second one, the rationality of the growth, uses generating functions.
Growth Rate and the Classification Problem
The first one is a familiar one from calculus. The growth rate of a group quantifies how fast a group grows as .
The growth rate of the free group on two elements we saw earlier is exponential as its Cayley graphs will always be a tree with many splittings, independently of the choice of generating setI’m being handwavy here because I can’t think of an actual formal argument right now. Let me know if you know one! .
On the other hand, the growth function of with standard generating set was found to be a polynomial of degree 2 using Pick’s theorem, and in fact, it can be proven using the Pick’s theorem that the growth function of is always a polynomial of degree 2 regardless of generating set. We say that the growth of is polynomial.
Notice that we say “how fast a group grows”, and do not specify the generating set. This is because changing the generating set induces a quasi-isometry, which for our purposes is a transformation that does not distort distance by more than an affine transformation. Because an affine transformation does not change the large-scale asymptotitc behavior of a function (exponential, polynomial), we can truly talk about the growth of a group.
One might wonder if exponential growth and polynomial growth stems from some underlying geometry of groups, such that all tree-like groups (known as hyperbolic groups) grow exponentially, and all abelian groups grow polynomially. The answer is affirmative. In fact, we have an even stronger answer.
A 1981 theorem of Gromov states that the virtually nilpotent group are exactly the groups with growth in the polynomial range.
A group is nilpotent if there is an such that for arbitrary elements of , the iterated commutator Recall that the commutator of is denoted by , and can be thought of as measuring the failure to commute. Our object denotes iterated commutators (commutators of commutators of…commutators)! . Abelian groups are nilpotent groups of step 1, as their commutators are the identity after one iteration. Non-examples of nilpotent groups would be free groups. In some sense, a nilpotent group is a group that “finitely many steps away from being abelian”.
A great example of a nilpotent group is the Heisenberg group given by the presentation
It is a nilpotent group of step , because while its commutator does not vanish, it commutes with everythingby definition of being central . Thus, the commutator of the commutator must vanish.
A group is virtually nilpotent if it has a nilpotent subgroup of finite index. Since we care about the asymptotic behaviour of growth, we focus on infinite groups as otherwise the growth is simply constant as . Thus, assuming the a group is infinite, a group is virtually nilpotent if its nilpotency is “significant enough”.
A group has growth in the polynomial range if its growth function satisfies for some degree the relation
note that the limit is allowed not to exists, which happens when the growth function is a polynomial with periodic coefficients For example if for odd, and for even. .
Gromov’s theorem was remarkable in that it completely classified the growth rate of an enourmous class of groupsSome trivia: In 2007, Bruce Kleiner gave a new and simplified proof. Three years later in 2010, Yehuda Shalom and Terence Tao gave a quantitative version of Gromov’s theorem. . While the classification of finite groups has been done in the last century, the classification of infinite groups is still in progress, and notoriously difficult. There are uncountably many infinite groups, and Dehn’s isomorphism problem (given two groups, figure out whether they are isomorphic) is algorithmically undecidable.
Justly, Gromov’s breakthrough induced a spur of activity and interest in the growth of groups, which continues to this day.
Rationality and the Word Problem
Consider the Fibonnaci-style sequence of rational numbers , which satisfies the famous recursion
We can associate to its generating function given by the formal power series
From the recursion, we find that
and factoring the gives us
Because the generating function of our sequence can be written as a ratio of two polynomials, we say that has rational growth.
It is a well-known fact that a sequence is rational if and only if it satisfies a Fibonnaci-style recursion of integer coefficients and finite depth
The rationality of a sequence has nothing to do with its growth rate. Indeed, the sequence
has rational growth, while the generating function based on the sequence of digits of ,
which is bounded away from the rational sequence
cannot be rational, otherwise for some polynomial
Thus, two sequences having the same growth rate do not necessarily share this rationality property.
We can easily apply this framework to growth functions of groups by viewing as the sequence We use for ball count, viewing as the number of points inside the ball of radius under the word metric of the Cayley graph. . Just as the rationality of a sequence can be destroyed by adding in a bounded sequence, changing the generating set, which induces an essentially affine change in our growth function, can destroy rationality. While growth rate is independent of choice of generators, rationality does depend on the choice of generators.
This begs the question which groups have rational growth, and in what generators?
Or perhaps, why do we care at all?
Essentially, rationality allows us to construct the growth of a group using very little initial information, and leads to a halting condition for the word problem.
The growth of a group gives us the number of words of length , and so a simple substraction We use for sphere count. denotes the discrete sphere of radius . gives the number of group elements which are exactly of length .
Then, for a spelling of length , since we know about many words (equivalence class of spellings) there are, we can compare every spelling with one another. Suppose there are such equivalence classes of spellings. Inserting relations for two spellings of the same equivalence class, these two spellings will end up equal after a finite amount of steps. Otherwise, if the two spellings happen to be in different equivalence classes, then the process of determining they are equal by using the relations will not terminate. Nonetheless, the overall process will terminate because eventually, spellings will reveal themselves to be the same, and this is when we decide to terminate the processThanks to Felix Bauckholt for helping me clarify this! .
In 1980s, it was shown by Cannon, Thurston, Gromov and Benson that if the group is flat (virtually abelian) or hyperbolic, then the growth is rational under all generating sets.
The Curious Nilpotent Regime
Recall that we introduces three geometric regimes: the hyperbolic regime, which captures the tree-likeness of free groups, the flat regime, which captures abelian groups, and the nilpotent regime, which a flat regine with some twist.
Curiously, the nilpotent regime shares with abelian groups a polynomial growth rate, but is somewhere in between rational and transcendental when it comes to growth structure.
A concrete example is the discrete Heisenberg group of dimension 5, denoted
not to be confused with the Heisenberg group of dimension 3Confusingly also called the Heisenberg group.
which we have also seen presented as
has transcendental growth in its standard generating set, but rational growth in a generating set called cubical.
In contrast, the Heisenberg group of dimension 3 has rational growth in all of its generators, a fact that has only been proven very recently by Moon Duchin and Michael Shapiro.
Currently, little is known about these nilpotent groups and they are according to Duchin a very underappreciated area of study ;).
Update: I have made a follow-up post on how a 30-year-old open problem in growth was solved. The post focuses on the narrative of the breakthrough. Check it out here!
Sources and Additional Material
My supervisor Moon Duchin has excellent material on the topic. I highly recommend the following:
- AMS Notices article
- Lecture series given at the Institute of Advanced Studies.
Groups of Intermediate Growth: an Introduction for Beginners by Grigorchuk and Pak settles the question whether there are groups with growth rate faster than polynomial but slower than exponential. Also a great read I should read!
There is this great REU paper by George Hyun on Hyperbolicity and the Word Problem which I’m looking forward to reading!
For those who have a good amount of background on this topic, I am also trying to read A Short Course in Geometric Group Theory by D. Neumann and Michael Shapiro. Although written in 1996, I am finding it to be a treasure trove of concepts for the literature on growth today. I am far from being able to catch every concept that is referred to, and would love to acquire a reading buddy to discuss these concepts with me :).
As always, feel free to email me if you have any questions, or want to start a discussion on the topic.
Many thanks for Felix Bauckholt for proofreading this and giving insightful feedback!
More: About Intermediate Growth
You may wonder if there is growth in the intermediate range, i.e. between polynomial and exponential. The answer is affirmative.
Define a function to be superpolynomial if
This captures the behaviour that “”.
Define a function to be subexponential if
This captures the behaviour that “”.
A function has intermediate growth if it has both superpolynomial and subexponential growth.
An example of this is the function .
In their paper Groups of Intermediate Growth: an Introduction for Beginners Rostislav Grigorchuk and Igor Pak construct a group of intermediate growth by looking at the group of automorphisms acting on a tree. I highly recommend this paper, a gem written at an accessible level.Honestly I should sit down and read it in full myself.
It is conjectured by Pak and Grigorchuk that there are no finitely presented groups with intermediate growth – meaning this whether a finitely presented group either has polynomial or exponential growth is an open problem!I don’t know if I’m up to date though!