# Algorithm for Finitely Presented Torsion-Free Nilpotent Groups

I am studying some finitely presented, torsion-free and nilpotent groups $G$ and need to consider the following question:

Let $H$ be a subgroup of $G$ and suppose that $H$ is generated by $h_1,\cdots,h_t$.

1. Is there any algorithm finding a minimal generating set $A$ of $H$? By $A$ being a minimal generating set of $H$ I mean $A$ generates $H$ and any proper subset of $A$ does not generate $H$.
2. Is the cardinality of $A$ unique? If yes, is there any algorithm (I mean one which is easier than the one in my first question, if the answer to my first question is "yes") finding the cardinality of $A$?

I am aware that there is a paper studying algorithms of nilpotent groups: Some general algorithms. II. Nilpotent groups. But I am not an expert in computational group theory and I find the paper difficult to understand. Can any one help me by providing an Easy-to-Read Version of the algorithm, given that my groups are finitely presented, torsion-free and nilpotent?

• The answer to 2 is no even in the infinite cyclic group. – Derek Holt Sep 11 '13 at 9:43
• If you really want to do some calculations of this type, I would recommend that you try the GAP package "Polycyclic". – Derek Holt Sep 11 '13 at 9:46

Given two finitely generated groups $H\subset G$, there is a notion of distortion function $\Delta(n)$ which measures the "rate of distortion of the word metric of $H$ with respect to the word metric of $G$". It is proven in

B. Farb, The extrinsic geometry of subgroups and the generalized word problem, Proceedings of the London Math. Society, 3, 68, No. 3, 1994, 577-593.

that $\Delta$ is bounded above by a recursive function if and only if the membership problem (also known as generalized word problem) for the subgroup $H$ is decidable. In other words, there exists an algorithm which would test whether given element $g\in G$ (written in terms of generators of $G$) belongs to $H$ or not.

On the other hand, in the case of finitely generated nilpotent groups $G$, all subgroups $H\subset G$ have at most polynomial distortion, you can find some explicit bounds in

D. Osin, Distortions of subgroups in nilpotent groups, Comm. Algebra 29 (2001), 5439-5463.

Now, if you believe in these two results, you see that the membership problem for subgroups of every finitely generated nilpotent group is decidable.

Using this result, here is an algorithm for finding a minimal generating set for a subgroup $H\subset G$ of a finitely-generated nilpotent group $G$ (the subgroup $H$ is of course also nilpotent). I assume that the subgroup $H$ is given in terms of a finite generating set $S=\{h_1,...,h_k\}$. Define the subgroup $H_1\subset H$ generated by elements $h_2,...,h_k$ and use the above algorithm to test if $h_1$ belongs to $H_1$. If it does, then remove $h_1$ from the generating set since $H=H_1$. (In this case, the number of generators drops, and we can continue recursively.) If $h_1\notin H_1$, then repeat the same procedure for the element $h_{2}$ and the subgroup $H_{2}$ generated by $h_1, h_3, h_4,...,h_k$. Continue in this fashion. If $h_i\notin H_i$ for every $i=1,...,k$, then the set $S$ is a minimal generating set of $H$.

Question 2. Consider the infinite cyclic group $G={\mathbb Z}$ and its generating set $\{2, 3\}$. Clearly, this generating set is minimal and has cardinality $2$. On the other hand, the there is also a minimal generating set $\{1\}$ of cardinality $1$. Thus, even in this case, the cardinality of a minimal generating set is not unique.

• Thank you so much! For Question 2, is there any way to find the rank of $H$, which is defined as the minimal cardinality of generating sets of $H$? – Zuriel Sep 11 '13 at 9:26
• And also, in your answer, how to test if $h_1\in H_1$? – Zuriel Sep 11 '13 at 9:38
• @Zuriel: To test for $h_1\in H_1$ use the solution of the membership problem as explained in the answer. – Moishe Kohan Sep 11 '13 at 11:42