Story About Growth: How a 30-Year-Old Open Problem Was Solved

May 2, 2017

Moon Duchin and Michael Shapiro’s result proving the rational growth of the Heisenberg group solves a mathematical question which has stood open for thirty years.

Behind the problem solving, there’s a great academic story that spans those 30 years. Learning about this story gave me a wonderful glimpse on the nature of mathematical progress. Allow me to share the story with you.

In this post, I want to focus on the narrative component of the resolution of an open problem. Unnecessary mathematical details to the story will be explored as sidenotes.

Quick Definition of Growth

Let be a group with a symmetric generating set . Define to be the set of spellings with length For example, if , then is a spelling of length 5 because it has five letters in , and is a spelling of length 2 because it has two letters . Notice that the length of the spelling was defined without any underlying group multiplication! .

Denote by the set of all spellings of finite length

There is a natural map from into the group using group multiplication. Under this map, two different spellings may be identified to the same element in the group, for example and the both map to the identity in .

We say that the spellings and map to the same word in . The length of a word is the shortest length of all spellings in mapping to Geometrically, given a Cayley graph of with generating set , the length of is the length of the geodesic from the identity to . . Hence, the length of depends on the underlying generating set .

The growth function of a group is the number of words of length with respect to some alphabet (generating set).

We are interested in the asymptotic behavior of the growth as , and the structure of the growth, also known as its rationality which we will define later.

Note: If you are interested in growth, I wrote a post dedicated to introducing growth intuitively.

1981: Gromov’s Theorem

In 1981, Gromov popularizes growth of groups with his seminal paper showing that the virtually nilpotent groups are the 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 is “finitely many steps away from being abelian”.

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

1980-1984: Hyperbolic Groups and Virtually Abelian Groups Have Rational Growth

Another significant breakthrough of Cannon, Thurston and Gromov soon follows in the early 1980s. They independently show that hyperbolic groups have rational growthGrowth is rational if the associated growth series can be written as a fraction of polynomials. If denotes the growth function at , then the associated generating function, called the growth series is . A growth function is rational if for some polynomials . . Rational growth is a great property because it implies to being able to solve the Word Problem.

The Word Problem is the fundamental problem figuring out is some spelling of a group is equal to the identity. Surprising, this problem is in general intractable, and is equivalent to the Halting problem. Establishing which groups have solvable word problems is a key question in geometric group theory, because it tells us which groups are viable to do computation in. The findings of Cannon, Thurston and Gromov are a huge breakthrough.Rationality implies the word problem because of the following: it is a well-known fact that for some depth , the growth series being rational is equivalent to satisfying a recursion relation, , where the s are some real numbers. Therefore, knowing the number of elements with length becomes a trivial recursive computation, granted we know the base cases. 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. Then, 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 process.

At the same time, Benson establishes the rational growth of virtuallyA group is virtually abelian if it has a abelian subgroup of finite index. abelian groups. This result is vaguely intuitive for me to acceptnot prove because we already know that abelian groups have solvable Word Problem (it’s very easy to check if two elements are equal in an abelian group), so if a group is “abelian enough” in a loose sense, then it makes sense that we can check for the equality of its group elements as well.

1980’s and Beyond: Do Nilpotent Groups Have Rational Growth?

A natural question that arises from these findings is: do nilpotent groups also have rational growth? Recall that a nilpotent group is a group that is “finitely many steps away from being abelian”. Nilpotent groups display interesting geometry in their Cayley graphs, which resemble flat geometry but with a “twist”Someday, I will make figures and they will be better than the one I below. .

If virtually abelian groups, which are “almost abelian” in some sense, have rational growth, then it isn’t far-fetched to ask if the same property applies to these nilpotent groups, which are also “almost abelian” but in a different, “iterated commutator”, sense.

Since all cyclically generated groups are abelian, and the one-step nilpotent groups are also precisely the abelian groups, the simplest example of a nilpotent group would be a two-generated, two-step one given by this presentation

This group is also known as the three-dimensional Heisenberg group over the integers or simply the Heisenberg group. The continuous analogue of this group arises in the description of one-dimensional quantum mechanical systems.

In 1988, Benson’s student Michael Shapiro proves in his PhD dissertation that the Heisenberg group with standard generating set, , has rational growth.

At that point in time, whether the growth of the Heisenberg group with arbitrary generating set is rational remains an open problem.

In 1996, Stoll provides a proof that the five-dimensional Heisenberg group has transcendental growth series in its standard generating set, but rational growth in a certain dual generating set. This establishes that not all nilpotent groups have rational growth. Over fifteen years later, Stoll’s example will be the only known example of a group with both rational and irrational growth series.My collaborator Ayla remarked how surprising it is for the five-dimensional Heisenberg group to have irrational growth under some generating sets because it is in some way two two-dimensional Heisenberg groups glued along their commutator. The exact statement of the five-dimensional Heisenberg group being two two-dimensional Heisenberg group is the following. Recall that is the set of matrices of the form , which can be generated by the set , , , , . Then, can be written as In other words, the two “glued” 3-dimensional Heisenberg groups are generated by and . They are glued by the relation . My perspective on this is that it communicates the fragility of rationality in a geometric way. Taking the cartesian product of two rational groups preserve rationality, but gluing them introduces a fine change in geometry that destroys rationality depending which generating set you choose to look at this geometry. Ayla’s perspective is that this conveys how structured a presentation is.

Meanwhile, Michael Shapiro, the youngest person so far in our story, dedicates himself for a time to computer science and software engineering.

2007-2010: Interlude

In 2007, Bruce Kleiner gives a new and simplified proof of Gromov’s theorem, which was originally quite complicated and relied on infinitary limits.

Three years later in 2010, Yehuda Shalom and Terence Tao give a quantitative version of Gromov’s theorem. Roughly, they found an explicit threshold to check virtual nilpotency for an arbitrary group, and bound the nilpotent step.The exact statement is the following: for some absolute (explicit) constant , the following holds for every finitely generated group and all : if there is some for which the number of elements in a ball of radius in a Cayley graph of is bounded by , then has a index finite subgroup which is nilpotent of step .

2014: Finale

A few years preceeding 2014, Moon Duchin meets Michael Shapiro who had since then stopped working on the problem of whether the three-dimensional Heisenberg group over the integers has rational growth. At Duchin’s insistence, Shapiro and Duchin plunge back into the 30 year-old puzzle. What emerges is a beautiful proof of the rationality of this Heisenberg group for all finite generating set.

Their work also allows them to establish the almost-convexityRoughly, this means that traveling inside the ball of radius is efficient relative to traveling within the sphere of radius , which is a property we expect from convex objects. of the three-dimensional Heisenberg group over the integers. As with rational growth in all generating sets, almost-convexity is a property which was only known to hold for virtually abelian groups and hyperbolic groups prior to Duchin and Shapiro’s discovery.

In the acknowledgements of the preprint, it reads:

MS wishes to thank MD for inviting him on such a grand adventure.

The end …or is it?

2016-2017: My Research (Shameless Plug Edition!)

As previously stated, the growth of the Heisenberg group (of three-dimensions) is rational and in the polynomial range. This impliesKnown implication that I do not know how to prove! Will update this side-note once I do. that the growth function is eventually periodicA function is periodic of period if it cycles through functions such that is defined by . For example, we can define to be of period cycling through . Then and so on. A function is eventually periodic if the periodic behavior starts at some threshold such that for , is periodic. In our case, because the know the growth is in the polynomial range, the growth function must cycle through polynomials.

I am working on a conjecture of how the period of the growth is affected by the choice of generating set.

I think it would be fascinating to see how the geometry of the generating set affects the time and space complexity of computing the growth. I currently believe this phenomenon could be generalizable to other groups whose growth we’d like to compute algorithmically. I’m currently exploring this idea further in the hope of writing a manuscript.

Further Readings

If you haven’t done so, check out my blog post introducing the growth of groups.

I also followed up this post with a short remark on Gromov’s breakthrough.


M. Benson, Growth series of finite extensions of are rational, Invent. Math. 73 (1983), no. 2, 251–269.

M. Duchin & M. Shapiro, Rational growth in the Heisenberg group, Preprint.

Gromov, Mikhail (1981). With an appendix by Jacques Tits. “Groups of polynomial growth and expanding maps”. Inst. Hautes Études Sci. Publ. Math. 53: 53–73. MR 623534.

B. Kleiner, A new proof of Gromov’s theorem on groups of polynomial growth, Jour. of the AMS.

Shalom, Y. & Tao, T. A Finitary Version of Gromov’s Polynomial Growth Theorem Geom. Funct. Anal. (2010) 20: 1502. doi:10.1007/s00039-010-0096-1

M. Stoll, Rational and transcendental growth series for the higher Heisenberg groups. Invent. math. 126, 85–109 (1996).

Special thanks to Eric Hanson and for reading a draft of this article, and to my collaborator Ayla Sánchez for providing insightful technical remarks.

Story About Growth: How a 30-Year-Old Open Problem Was Solved - May 2, 2017 - Hang Lu Su