THE COMPLEXITY OF ASCENDANT SEQUENCES IN LOCALLY NILPOTENT GROUPS

CHRIS J. CONIDIS AND RICHARD A. SHORE

Abstract. We analyze the complexity of ascendant sequences in locally nilpotent groups, showing that if G is a computable locally nilpotent group and x_{0}, x_{1}, …, x_{N} ∈ G, N ∈ ℕ, then one can always find a uniformly computably enumerable (i.e. uniformly Σ_{1}^{0}) ascendant sequence of order type ω + 1 of subgroups in G beginning with ⟨x_{0}, x_{1}, …, x_{N}⟩_{G}, the subgroup generated by x_{0}, x_{1}, …, x_{N} in G. This complexity is surprisingly low in light of the fact that the usual definition of ascendant sequence involves arbitrarily large ordinals that index sequences of subgroups defined via a transfinite recursion in which each step is incomputable. We produce this surprisingly low complexity seqeunce via the effective algebraic commutator collection process of P. Hall, and a related purely algebraic Normal Form Theorem of M. Hall for nilpotent groups.

1. Introduction

1.1. Computable Algebra. Computable algebra goes back at least to the work of Kronecker in the 1880s [Kro82]. He showed that every ideal in a computable presentation of ℤ[X_{0}, X_{1}, …, X_{N}], N ∈ ℕ, is computable. Later on, van der Waerden [vdW] showed that there is no universal algorithm for factoring polynomials over all computable fields. After the development of modern computability theory by Alan Turing in the 1930s, computable ring and field theory was first given a more formal treatment by Fröhlich and Shepherdson in [FS56], where they showed that there is a computable field with no computable splitting algorithm. More early contributions to computable ring and field theory followed soon after from Rabin [Rab60], Metakides and Nerode [MN77], and others.

In addition to computable rings and fields, however, mathematicians have been interested in the algorithmic properties of computable groups for the last hundred years. The most important and well-known result from computable group theory is surely the unsolvability of the Word Problem, which is also one of the first problems outside of logic that was shown to be undecidable. Ever since this important result was established

The first author was partially supported by NSERC grant PDF 373817-2009 and a Fields-Ontario Fellowship from the Fields Institute; he would also like to thank the second author for inviting him to Cornell University, where part of this research was carried out. The authors would like to thank the National University of Singapore for inviting them to their 2011 All Summer Graduate School in Logic, where this research was begun. The second author was also partially supported by NSF Grant DMS-0852811 and as a Visiting Professor in the Department of Mathematics and the Institute for Mathematical Sciences at the National University of Singapore with partial funding from the John Templeton Foundation.

by Novikov [Nov55] and Boone [Boo54], both algebraists (i.e. combinatorial group theorists) and logicians (i.e. computability theorists) have been examining the algorithmic and definability properties of groups.

1.2. Computable Group Theory. One of the main objectives of computable group theory is to determine the existence and nature of algorithms that decide local and global properties of groups. Local properties are those pertaining to the elements of a group, while global properties speak about groups as a whole. The three most important decision problems, formulated by Max Dehn in 1911, are the word, conjugacy, and isomorphism problems [Mil91]. The first two problems talk about local properties, while the third problem concerns a global relationship. Some of the motivations for studying these problems come from algebraic topology. Let G be a finitely presented group, and let T be a finite complex with π_{1}(T) = G (i.e. G is the fundamental group of T). Then the word problem for G asks whether or not a product of generators for G is equal to the identity, and is equivalent to deciding whether or not a closed loop in T is contractible. The conjugacy problem for G asks whether or not two products of generators are conjugates in G, and corresponds to determining whether two closed loops in T are freely homotopic. The isomorphism problem asks whether two spaces have the same fundamental groups, and thus gives a method for distinguishing between spaces. Questions such as these and others have been pursued by combinatorial group theorists for the last hundred years. For more information see [Mil91].

In addition to algebraists and combinatorial group theorists, though more recently, logicians and computability theorists have also asked and answered questions about the algorithmic properties of computable groups. But whereas algebraists are usually concerned only with decidability and simply classify things as either decidable or undecidable, logicians and computability theorists have finer hierarchies that can distinguish among undecidable properties as well. These distinctions between various undecidable characteristics and constructions allow logicians to more precisely characterize the complexity of algebraic constructions and extract definability results as corollaries of the computability theory. Some examples of these sorts of theorems can be found in Simpson’s text on reverse mathematics [Sim09], Ash and Knight’s book on computable structures [AK01], as well as recent work of Solomon on ordered groups [Sol99], and a very recent article of Csima and Solomon on nilpotent groups [CS11]. We now turn our attention to the current article, which classifies the complexity of ascendant sequences in locally nilpotent groups in terms of the computability hierarchy.

1.3. Our Paper. This article was first inspired by T. A. Slaman, who, in an informal conversation asked the first author to find some computationally necessarily complicated group-theoretic constructions. The construction of ascendant sequences in locally nilpotent groups seemed like a natural candidate for a complicated construction, because they are sequences of subgroups indexed by arbitrarily large ordinals such that each successor in the sequence depends upon its predecessor in an incomputable way. In other words, ascendant sequences can be thought of as paths of ordinal length through “trees of subgroups.”We restricted ourselves to countable locally nilpotent groups because this is the most general context in which standard computability theory applies and ascendant sequences beginning with finitely generated subgroups always exist (the definition of ascendant subgroup is given in the next section). Indeed, in this context a standard construction uses the fact that the normalizer of any proper subgroup of is a proper extension of the subgroup [Rob96, Theorem 5.2.4]. One then proceeds to build the desired sequence by taking normalizers at successor steps and unions at limits. The process terminates at some countable ordinal since the group is countable and at least one new element is added at every successor stage.

Via hyperarithmetic theoretic techniques we soon realized that there is a single computable ordinal β such that, for any computable locally nilpotent group, all such sequences can be computed from ∅^{(β)} – i.e. the β^{th} iteration of Turing’s Halting Set. This ruled out the possibility of ascendant sequences being Π_{1}^{1}-complete, but left open the interesting question of determining the least ordinal β with this property. At this point it seemed to the authors that β = ω and that we could prove this by constructing a locally nilpotent group G containing an ascendant sequence of subgroups of length ω + 1 = {0, 1, 2, …, ω}^{1}, H_{0} ◁ H_{1} ◁ ⋯ ◁ H_{n} ◁ ⋯, n ∈ ω, H_{ω} = ∪_{n∈ω}G_{n} = G, and a computable function f : ω → ω such that for all n ∈ ω, H_{f(n)} computes the n^{th} iteration of Turing’s Halting Set, denoted ∅^{(n)}. We made some attempts at constructing such a sequence, but were ultimately unsuccessful.

We then came across a (computable) construction of P. Hall from the 1920s, and a related purely algebraic theorem of M. Hall from the 1950s about nilpotent groups, that revealed a beautiful interaction between algebra and computability and showed that, in fact, ascendant sequences in computable locally nilpotent groups that begin with finitely generated groups are uniformly computably enumerable.^{2} In other words, if G is a computable locally nilpotent group, then there is a uniform algorithm that, for every finite sequence of elements g_{0}, g_{1}, …, g_{n} ∈ G, n ∈ ω, enumerates an ascendant sequence of subgroups in G beginning with the cyclic subgroup generated by g_{0}, …, g_{n}. This result is quite remarkable, given that on the surface ascendant sequences seem very complicated because their definitions are given by transfinite induction on ordinals. In other words, it is the extent of our failure in achieving Slaman’s goal and producing a complicated group theoretic construction that makes this article interesting.

1.3.1. The plan of this paper. The next section introduces the basic definitions and notation that we will use throughout this article. In Section 3 we describe the purely algebraic commutator collection process of P. Hall, and a related theorem of M. Hall concerning nilpotent groups. These are the key to our analysis of the complexity of ascendant sequences in locally nilpotent groups. Finally, in Section 4 we use these results along with some computable analysis of nilpotent groups to prove our main theorem that says ascendant sequences in locally nilpotent groups beginning with finitely generated subgroups are uniformly computably enumerable. Also, we should point out that, although we will work primarily with computable locally nilpotent groups, all of our computability theoretic results relativize to arbitrary locally nilpotent groups.

1Here ω = {0, 1, 2, …} denotes the natural numbers.

2Recall that a set A ⊆ ℕ is computably enumerable whenever there is a finite algorithm that lists the elements of A, not necessarily in order.

2. Preliminaries and Definitions

2.1. Computability Theory. Our terminology and notation mainly follows [Soa87, Soa]. We use ω = {0, 1, 2, …} to denote the set of natural numbers. We say that a computable function φ : ω → ω is total if its domain is all of ω, and we say that φ is partial otherwise. Fix a computable listing {φ_{e}}_{e∈ω} of the partial computable functions; then the Halting Set (i.e. Turing’s Halting Set) is defined as ∅′ = {e ∈ ω : φ_{e}(e) halts}. We say that a set A ⊆ ω is computably enumerable whenever A is the range of some partial computable function φ, i.e. a set A ⊆ ω is computably enumerable if and only if there is a computable algorithm that can list the elements of A (not necessarily in order). It is well-known (and not difficult to verify) that ∅′ is computably enumerable. From the definition it easily follows that a set A ⊆ ω is computably enumerable if and only if it is Σ_{1}^{0}-definable, i.e. if and only if it can be defined via finitely many existential quantifiers (ranging over natural numbers) over a computable predicate. All of these definitions can be relativized to an arbitrary incomputable oracle set X ⊆ ω. For more information on oracle computability and related notions consult [Soa87, Chapter III]. Let A, B ⊆ ω. We write A ≤_{T} B to mean that B computes A, and we write A ≡_{T} B to mean that A ≤_{T} B and B ≤_{T} A. It is not difficult to check that ≡_{T} is an equivalence relation on 2^{ω}; the resulting equivalence classes are known as Turing degrees.

Let 2^{<ω} denote the set of finite strings of 0s and 1s that we think of as a binary tree with root λ–the empty string. For all σ, τ ∈ 2^{<ω} we write σ ⊆ τ to mean that σ is an initial segment of τ. We say that ⊆ 2^{<ω} is a tree whenever T is downward closed under ⊆, i.e. whenever for all σ ∈ T we have that, for all τ ⊆ σ, τ ∈ T. Fix a computable coding of the elements of 2^{<ω} as natural numbers; then we may speak of computable sets of strings and trees in 2^{<ω} in the obvious way. We say that a set A ⊆ ω is of PA Turing degree whenever we have that for every infinite computable tree T there is an A-computable infinite binary string all of whose finite initial segments belong to T.^{3} These sets are always incomputable and, indeed, have significant computational strength. A set is of PA Turing degree if and only if it can compute a complete and consistent extension of Peano Arithmetic, and this is the source of their name. It is also well-known that there exist computably enumerable sets, A, B ⊆ ω, such that any set C ⊆ ω for which A ⊆ C and C ∩ B = ∅ is of PA Turing degree. We will use this characterization of PA sets and the (well-known) fact that ω \ (A ∪ B) is infinite in the proof of Theorem 4.4 below. If a set A ⊆ ω is both of PA and computably enumerable Turing degree, then A ≡_{T} ∅′. This is known as Arslanov’s Completeness Criterion; see [Soa87, Theorem V.5.1] for more details.

Definition 2.1. A computable group is a group coded as a computable subset of the natural numbers ω such that the corresponding multiplication and inverse operations on ω are given by computable functions. We will make no distinction between the abstract group G and its coding as a subset of ω.

3It is well-known and not difficult to prove that every infinite binary-branching tree has an infinite path; this is known as Weak König’s Lemma.

2.2. Group Theory. We assume that the reader is familiar with the very basics of group theory; for more information consult [DF99] or [Lan93]. If G is a group then we will use either 1_{G} or simply 1 (when there is no confusion about G) to denote the identity element of G.

Definition 2.2. Let G be a group, let x_{0}, x_{1}, …, x_{m} ∈ G, and let H_{0}, H_{1}, …, H_{n} ⊆ G, n, m ∈ ω. Then we write ⟨x_{0}, x_{1}, …, x_{m}⟩, or sometimes ⟨x_{0}, x_{1}, …, x_{m}⟩_{G} to avoid confusion, to mean the subgroup of G generated by {x_{0}, x_{1}, …, x_{n}} ⊆ G. Similarly, we write ⟨H_{0}, H_{1}, …, H_{n}⟩ or ⟨H_{0}, H_{1}, …, H_{n}⟩_{G} to mean the subgroup of G generated by H_{0} ∪ H_{1} ∪ ⋯ ∪ H_{n} ⊆ G. From these definitions it follows that if G is a countable group (coded as a subset of natural numbers) and H ⩽ G is a subgroup of G generated by K ⊆ H, then H is computably enumerable relative to K (and G), i.e. H is Σ_{1}^{0}-definable relative to K (and G), with the precise Σ_{1}^{0} definition being given by

H = {h ∈ G : (∃n ∈ ω)(∃k_{1}, k_{2}, …, k_{n} ∈ K)[∏_{i=1}^{n} k_{i} = h]}.

Definition 2.3. Let G be a group, A, B ⊆ G, and x, y ∈ G. Define [x, y] = x^{−1}y^{−1}xy, i.e. the commutator of x and y, and define [A, B] to be the subgroup of G generated by elements of the form [a, b], a ∈ A, b ∈ B. Recall that G is said to be abelian or commutative whenever [G, G] = {1_{G}}. Also recall that Z(G) denotes the center of G, i.e. for any group G, Z(G) is the unique largest subgroup of G such that [Z(G), G] = [G, Z(G)] = {1_{G}}.

Definition 2.4. Let G be a group. The lower central series of G, {G_{k}}_{k∈ω}, is given by G_{0} = G, and G_{k+1} = [G, G_{k}] for all k ∈ ω. We say that G is class r nilpotent, r ∈ ω, whenever r ∈ ω is least such that G_{r} = {1_{G}}, and in this case we will index the terms of this finite series in increasing order. It is obvious that for all k ∈ ω the quotient group G_{k}/G_{k+1} is abelian. We say that G is nilpotent when it is nilpotent of some class r ∈ ω. G is locally nilpotent whenever every finitely generated subgroup of G is nilpotent.

Let G be a group, and let H be a subgroup of G. Then we write H ◁ G to mean that H is normal in G.

Definition 2.5. Let G be a group and let H be a subgroup of G, i.e. H ⩽ G. Then we say that H is subnormal, i.e. H is a subnormal subgroup of G, whenever there is a finite sequence of subgroups H = H_{0}, H_{1}, …, H_{n} = G, n ∈ ω, such that

H_{0} ◁ H_{1} ◁ H_{2} ◁ ⋯ ◁ H_{n}.

We say that H is ascendant, i.e. that H is an ascendant subgroup of G, whenever there exists an ordinal α and a collection of subgroups {H_{β}}_{β≤α} such that:

(1) H_{0} = H;

(2) H_{α} = G;

(3) H_{β} ◁ H_{β+1}, for all β < α; and (4) H_{ρ} = ∪_{τ<ρ}H_{τ} for all limit ordinals ρ ≤ α.

Any sequence of subgroups of the form {H_{β}}_{β<α}, for some ordinal α, satisfying (1)-(4) above is called an ascendant sequence.

Definition 2.6. Let G be a group. We say that G is Baer, i.e. G is a Baer group, whenever G is generated by all of its subnormal finitely generated abelian subgroups. This is equivalent to saying that every cyclic subgroup of G is subnormal [Rob11a, Lemma 2.34]. We say that G is Gruenberg, i.e. G is a Gruenberg group, whenever G is generated by all of its ascendant finitely generated abelian subgroups. This is equivalent to saying that every cyclic subgroup of G is ascendant [Rob11a, Lemma 2.34].

It is well-known [Rob11a, page 61] that all Baer groups are Gruenberg, and that all Gruenberg groups are locally nilpotent. If G is countable then it is also known that G is locally nilpotent if and only if G is Gruenberg [Rob11b, page 21]. An example of an uncountable locally nilpotent group that is not Gruenberg was given by Kargapolov [Kar63], and independently by Kovács and Neumann (unpublished); see [Rob11b, pages 21-3] for more details.

3. Hall’s Collection Process and its Computability Theoretic Consequences

We begin this section with a discussion of P. Hall’s commutator collection process. Although the process was first developed by P. Hall [Hal34], we are mostly interested in a consequence of it that was discovered decades later by M. Hall [Hal50] in the context of nilpotent groups. Hall’s collection process and its consequences have been used recently by other logicians and computability theorists to analyze nilpotent groups; see [CS11, GSW03] for example. For more information on the collection process and its consequences, see [Hal34, Hal50, Hal59] and [CS11, Section 2]. Later on in this section we will use Hall’s collection process to deduce some useful computability theoretic facts about locally nilpotent groups.

3.1. Hall’s Collection Process. Fix a finitely generated (countable) nilpotent group G of rank r ∈ ω, and a finite sequence of generators for G, x_{0}, x_{1}, …, x_{m}. Recall that {G_{n}}_{n=0}^{r} denotes the lower central series of G and is indexed as an increasing sequence of subgroups with G_{0} = {1_{G}} and G_{r} = G. Define the iterated commutator denoted by [z_{0}, z_{1}, …, z_{k}], z_{i} ∈ G, 0 ≤ i ≤ k, recursively via

[z_{0}, z_{1}, …, z_{n}] = [z_{0}, [z_{1}, …, z_{n}]] ∈ G, n ∈ ω, n ≥ 1.

We will now describe Hall’s collection process [Hal34], which is a general computable procedure for generating a set of basic commutators with assigned weights and orderings. We think of commutators as symbols corresponding to elements of G, but two commutators may correspond to the same group element. Denote the weight of a basic commutator c by w(c) ∈ ω.

First define the set of symbols X = {x_{0}, x_{1}, …, x_{m}} to be the basic commutators of weight one, and order these commutators via their index x_{0} <_{1} x_{1} <_{1} ⋯ <_{1} x_{m}. We say that c = [a, b] is a basic commutator of weight k + 1 whenever

(i) a and b are basic commutators of weight ≤ k and w(a) + w(b) = k + 1; (ii) b <_{k} a; and (iii) If a is a basic commutator of the form [y, z] then z ≤_{k} y.

Now, we define an ordering <_{k+1} on basic commutators, c_{0} = [a_{0}, b_{0}], c_{1} = [a_{1}, b_{1}], of weight ≤ k + 1 via c_{0} <_{k+1} c_{1} whenever

(a) w(c_{0}), w(c_{1}) ≤ k and c_{0} <_{k} c_{1};

(b) w(c_{0}) ≤ k and w(c_{1}) = k + 1; or else

(c) w(c_{0}) = w(c_{1}) = k + 1 and (a_{0}, b_{0}) <_{k}^{lex} (a_{1}, b_{1}), where <_{k}^{lex} is the lexicographic ordering on the pairs of elements of weight k induced by the ordering <_{k}.

It is not difficult to see that the finitely many commutators in G of weight k ∈ ω and their corresponding group elements are computable, uniformly in G, k ∈ ω, and x_{0}, x_{1}, …, x_{n} ∈ G. This easy observation is all the computability theoretic content that we will essentially use from Hall’s collection process. In the next subsection we will use Hall’s collection process and a result of M. Hall [Hal50] to establish some computability theoretic facts about the definability of chains of subgroups in computable nilpotent groups.

3.2. Hall’s Normal Form Theorem and its Consequences. For our purposes the following theorem is the most important algebraic fact about finitely generated nilpotent groups, and we will use it and its computability theoretic consequences to prove our main theorem below. Fix G as in the previous subsection. The following is actually an easy consequence of M. Hall’s Normal Form Theorem [Hal50, Theorem 4.1], although we will refer to it as Hall’s Normal Form Theorem. Its statement is based on the commutator collection process of P. Hall [Hal34] given in the last subsection. We refer the reader to either [Hal50] or [CS11, Section 2] for more details on Hall’s Normal Form Theorem.

Theorem 3.1 (Normal Form Theorem, M. Hall [Hal50]). The following two properties hold for G:

(1) r ∈ ω is the least number such that all commutators in G of weight r are trivial; and

(2) For each 0 ≤ n ≤ r, G_{n} is generated by the finitely many (uniformly computable) basic commutators of weight n.

The following is a direct computability theoretic consequence of Hall’s theorem above.

Corollary 3.2. Let G be a computable locally nilpotent group and let x_{0}, x_{1}, …, x_{n} ∈ G, n ∈ ω, be given. Then the lower central series of X_{n} = ⟨x_{0}, x_{1}, …, x_{n}⟩ ⩽ G is computably enumerable, i.e. Σ_{1}^{0}, uniformly in x_{0}, x_{1}, …, x_{n}.

Proof. First of all, note that, via Hall’s collection process, the basic commutators of weight 0 ≤ k ≤ r are uniformly computable in k and x_{0}, x_{1}, …, x_{n}. The corollary now follows from Theorem 3.1 above and the fact that finitely generated subgroups are computably enumerable, uniformly in their generators. □

We will now use Hall’s collection process and Theorem 3.1/Corollary 3.2 above to deduce some more useful algorithmic corollaries of computable locally nilpotent groups.

Lemma 3.3. Let G be a nilpotent group of rank r ∈ ω with lower central series

G_{0} = {1_{G}} ◁ G_{1} ◁ ⋯ ◁ G_{r} = G,

and let H ⩽ G. Then we have that

H = H_{0} ◁ H_{1} ◁ H_{2} ◁ ⋯ ◁ H_{r} = G,

where H_{k} = ⟨H, G_{k}⟩, 0 ≤ k ≤ r.

Proof. The proof is by induction on r ∈ ω. If r = 0 then G is the trivial group and we are done. If r = 1 then G is abelian and the theorem easily follows since in this case G_{1} = G. Now, suppose that theorem is true for all nilpotent groups of rank less than some r > 1, r ∈ ω, and assume that we are given a nilpotent group G of rank r. There are two cases to consider. The first case says that H ⩽ G_{1}. In this case it follows that H_{k} ◁ H_{k+1}, 0 ≤ k < r, since G_{1} ⩽ Z(G).

The second case says that H ⩽̸ G_{1}. In this case we consider the group \overline{G} = G/G_{1}, which is nilpotent of rank r − 1. Let \overline{H} be the nontrivial image of H ⩽ G under the canonical homomorphism φ : G → G/G_{1}, and let \{\overline{G}_{k}\}_{0≤k≤r} denote the lower central series of \overline{G} (indexed in increasing order). Then, for each 0 ≤ k < r, we have that G_{k+1} = φ^{−1}(\overline{G}_{k}). Also, by the induction hypothesis, it follows that

\overline{H} = \overline{H}_{0} ◁ \overline{G} \overline{H}_{1} ◁ \overline{G} ⋯ ◁ \overline{G} \overline{H}_{r−1} = \overline{G},

where \overline{H}_{k} = ⟨\overline{H}, \overline{G}_{k}⟩\overline{G}, for all 0 ≤ k < r. Now, by elementary group theory we have that H_{k} = ⟨H, G_{k}⟩_{G} = φ^{−1}(\overline{H}_{k−1}), for all 0 < k ≤ r, and, since G_{1} ⩽ Z(G), it follows that H_{k} ◁ H_{k+1}, for all 0 ≤ k < r. □

The following is a computability-theoretic consequence of the previous lemma that we will use in the next section.

Corollary 3.4. Let G be a computable locally nilpotent group, and let x_{0}, x_{1}, …, x_{n} ∈ G, n ∈ ω. Let r ∈ ω be the nilpotence rank of G_{0} = ⟨x_{0}, x_{1}, …, x_{n}⟩ ⩽ G, and let H = ⟨x_{0}, x_{1}, …, x_{n−1}⟩ ⩽ G_{0}. Then the series

H = H_{0} ◁ H_{1} ◁ H_{2} ◁ ⋯ ◁ H_{r} = G

given by Lemma 3.3 above is computably enumerable, i.e. Σ_{1}^{0}, uniformly in x_{0}, x_{1}, …, x_{n−1}, x_{n}.

Proof. First of all, since G is locally nilpotent it follows that r ∈ ω is uniformly computable in x_{0}, x_{1}, …, x_{n} ∈ G; to compute r simply search for the least number w ∈ ω such that all the (finitely many and uniformly computable in x_{0}, x_{1}, …, x_{n}) basic commutators of weight w are trivial. The rest of the proof follows the same basic reasoning as that of Corollary 3.2 above. □

4. Our Main Results

Let G be a group of cardinality κ. It is clear that any ascendant sequence of subgroups in G must have index strictly less than κ^{+}, otherwise the cardinality of G would be strictly greater than κ. On the other hand, there are well-known examples of countable Gruenberg groups G containing elements x ∈ G such that there is no finite ascendant sequence beginning with the cyclic group ⟨x⟩ [KO10, page 243], and hence every ascendant sequence beginning with ⟨x⟩ has order type at least ω + 1. Recall that, since G is Gruenberg, a countable ascendant sequence beginning with ⟨x⟩ always exists. Also recall that all locally nilpotent groups are Gruenberg, and that these two notions coincide for countable groups.

The following theorem says that in a countable locally nilpotent group G every ascendant sequence beginning with the cyclic group ⟨x⟩ ⩽ G, x ∈ G, can be chosen to have order type ω + 1, the smallest possible order type. We do not know (although it might be known) if this result can be extended to higher cardinalities; the obstruction to doing so comes from the inherently finite nature of local nilpotence.

Theorem 4.1. Let G be a countable locally nilpotent group, and let a ∈ G. Then there is an ascendant sequence of subgroups of order type ω + 1 beginning with the cyclic subgroup ⟨a⟩ ⩽ G.

Proof. Let {g_{n} : n ∈ ω} be a countable listing of the elements of G with g_{0} = a. We will construct the ascendant sequence {H_{s} : s ∈ ω} recursively in countably many stages s ∈ ω. At stage s = 0 we define n_{0} = 0 ∈ ω and set H_{0} = H_{n_{0}} = ⟨a⟩ as required by the theorem. At stage s + 1 > 0, s ∈ ω, assume that we are given a number n_{s} ∈ ω and a finite sequence of subgroups {H_{n} : 0 ≤ n ≤ n_{s}} such that for all 0 ≤ n < n_{s} we have that H_{n} ◁ H_{n+1} and H_{n_{s}} = ⟨g_{0}, …, g_{s}⟩.

Now, set H = ⟨H_{n_{s}}, g_{s+1}⟩, and note that (by induction) H = ⟨g_{0}, g_{1}, …, g_{s}, g_{s+1}⟩. Thus H is nilpotent since G is locally nilpotent. Now, if r ∈ ω is the nilpotence rank of H, then Lemma 3.3 above says that we can extend the ascendant sequence {H_{n} : 0 ≤ n ≤ n_{s}} in the subgroup H_{n_{s}} to a larger ascendant sequence {H_{n} : 0 ≤ n ≤ n_{s} + r} in H such that H = H_{n_{s}+r}. Now, we finally set n_{s+1} = n_{s} + r and proceed to the next stage. This ends our construction of {H_{s} : s ∈ ω}. Set H_{ω} = G.

By our construction of {H_{s} : s ∈ ω} it is clear that for each s ∈ ω we have that H_{s} ◁ H_{s+1}, so all that we really need to verify is that ∪_{s∈ω}H_{s} = G. But this follows from the fact that, by our construction of {H_{s}}_{s∈ω}, we have that g_{s} ∈ H_{s}, for all s ∈ ω. □

The following is the main theorem of this article. It gives an unexpectedly low upper bound on the algorithmic and definability complexity of ascendant sequences in computable locally nilpotent groups.

Theorem 4.2. Let G be a computable locally nilpotent group, and let a ∈ G. Then there is an ascendant sequence of subgroups

⟨a⟩ = H_{0} ◁ H_{1} ◁ ⋯ ◁ H_{n} ◁ ⋯ H_{ω} = ∪_{n∈ω}H_{n} = G

that is uniformly computably enumerable, i.e. uniformly Σ_{1}^{0}-definable with respect to the index n ∈ ω + 1 and a ∈ G.

Proof. The proof of the current theorem is essentially a computability-theoretic analog of the proof of the previous theorem, as follows.

Let g_{0}, g_{1}, …, g_{k}, … ∈ G, k ∈ ω, be a computable listing of the elements of G with g_{0} = a, and let (·, ·) : ω×ω → ω be a computable pairing function, as described in [Soa87, Notation I.3.6]. We will think of the sequence {H_{n} : n ∈ ω +1} as being given by a single computably enumerable array of elements H ⊆ (ω + 1) × G such that the n^{th} row of H, i.e. H^{⟨n⟩} = {(n, x) : x ∈ G} ⊆ H, n ∈ ω + 1, is equal to H_{n}. Now, to prove the theorem it suffices to give an algorithm that for each n ∈ ω, enumerates (n, x) ∈ (ω + 1) × G into H so that

(1) H_{0} = ⟨a⟩;

(2) H_{ω} = G; and

(3) for all n ∈ ω, n > 0, we have that H^{⟨n⟩} = H_{n} = {(n, x) : x ∈ G} and H_{n−1} ◁ H_{n}.

We will now give a stage-by-stage definition of such an algorithm.

At stage s = 0 begin enumerating (0, ⟨a⟩) and (ω, G) into H, and set n_{0} = 0 ∈ ω. At a stage s + 1 > 0, s ∈ ω, assume that we are given a number n_{s} ∈ ω such that we have already begun enumerating H_{n}, n ∈ {ω, 0, 1, …, n_{s}}, and that H_{n_{s}} = ⟨g_{0}, g_{1}, …, g_{s}⟩. Now, set H = ⟨H_{n_{s}}, g_{s+1}⟩ = ⟨g_{0}, …, g_{s}, g_{s+1}⟩, and uniformly compute the nilpotence rank, r_{s} ∈ ω, of H – i.e. r_{s} is the least number such that the finitely many and uniformly computable basic commutators in the generators g_{0}, …, g_{s+1} of weight r_{s} are trivial. Now, Corollary 3.4 above says that there are computably enumerable subgroups {H_{k} : n_{s} < k ≤ n_{s} + r_{s}}, given uniformly in the generators g_{0}, …, g_{s+1}, such that H_{k−1} ◁ H_{k} for all n_{s} < k ≤ n_{s} + r_{s}. Begin (uniformly) enumerating these subgroups at stage s + 1 and proceed to the next stage. This ends the construction of {H_{n} : n ∈ ω + 1}; note that this construction is uniform in a ∈ G.

The verification that {H_{n} : n ∈ ω + 1} is indeed an ascendant sequence is similar to that of the previous theorem, and is left to the reader. □

Corollary 4.3. Let G be a computable locally nilpotent group, and let a_{0}, a_{1}, …, a_{N} ∈ G, N ∈ ω. Then there is an ascendant sequence of subgroups

⟨a_{0}, …, a_{N}⟩ = H_{0} ◁ H_{1} ◁ ⋯ ◁ H_{n} ◁ ⋯ H_{ω} = ∪_{n∈ω}H_{n} = G

that is uniformly computably enumerable, i.e. uniformly Σ_{1}^{0}-definable with respect to n ∈ ω + 1, l ∈ ω, and a_{0}, a_{1}, …, a_{l}.

Proof. The proof is almost identical to that of the previous theorem, and is left to the reader. □

The following theorem,via Corollary 4.7 and Theorem 4.8, essentially says that the previous theorem is sharp (in a strong way) and precisely characterizes the best possible general upper bound on the complexity of ascendant sequences beginning with finitely generated subgroups in computable locally nilpotent groups as computably enumerable, or Σ_{1}^{0}-definable.

Theorem 4.4. There is a nonsimple abelian group G such that every proper nontrivial subgroup of G is of PA Turing degree.

Proof. The proof is very similar to that of [DHK^{+}07, Theorem 1.5], but instead of working with a vector space over an infinite field we work with abelian groups, i.e. ℤ-modules. If G is an abelian group, we write 0 to denote its identity element, we write + to denote the group operation on G, and for all k ∈ ℤ and g ∈ G we write k · g to denote \underbrace{g + g + ⋯ + g}_{k} ∈ G. In other words we think of G as a ℤ-module and use the corre-

sponding notation.

First, fix disjoint computably enumerable sets A, B ⊆ ω such that any set C ⊆ ω satisfying A ⊆ C and B ∩ C = ∅ is of PA Turing degree. Recall that ω \ (A ∪ B) is infinite. Let G^{∞} denote a computable presentation of the free abelian group on countably many (ordered) generators e_{0} ≺ e_{1} ≺ e_{2} ≺ ⋯ in which the ℤ-linear dependence relation is uniformly computable and (more generally) all finitely generated subgroups of G^{∞} are computable, uniformly in their generators. Let 0 = g_{0} ≺ g_{1} ≺ g_{2} ≺ ⋯ be a computable listing of the elements of G^{∞}. For all g = ∑_{k=0}^{n_{g}} z_{k} · e_{k} ∈ G, n_{g} ∈ ω, z_{k} ∈ ℤ, let

supp(g) = {0 ≤ k ≤ n_{g} : z_{k} ≠ 0} ⊆ ω,

and let g : ω^{3} → ω denote a computable injection such that g(i, j, n) > max(supp(g_{i}) ∪ supp(g_{j})) for every i, j, n ∈ ω. We will construct a computable subgroup H ◁ G^{∞}, and let G = G^{∞}/H (recall that G is abelian, so that H is automatically normal).

We will satisfy the following requirements for all i, j ∈ ω such that g_{i}, g_{j} ∉ H:

R_{i,j,n}: (i) If n ∉ A ∪ B, then for all h ∈ H and k ∈ ℤ we have that k · g_{i} ≠ e_{g(i,j,n)} and

k · g_{k} ≠ e_{g(i,j,n)};

(ii) If n ∈ A, then e_{g(i,j,n)} − k · g_{i} ∈ H for some 0 ≠ k ∈ ℤ; and
(iii) If n ∈ B, then e_{g(i,j,n)} − k · g_{j} ∈ H for some 0 ≠ k ∈ ℤ.

We will now construct a uniformly computable increasing sequence of finite subsets,

H_{0} ⊆ H_{1} ⊆ H_{2} ⊆ ⋯ ⊆ H_{s} ⊆ ⋯ ⊆ G^{∞}

in stages s ∈ ω, such that the desired subgroup H = ∪_{s∈ω}H_{s}. Simultaneously, we will construct a computable function f : ω^{4} → {0, 1} such that f(i, j, n, s) = 1 if and only if we have acted to satisfy requirement R_{i,j,n} by stage s of the construction of H, i.e. by the time we have constructed H_{s}. We will ensure that for all m ∈ ω we have that g_{m} ∈ H if and only if g_{m} ∈ H_{m}, which will ensure that H = ∪_{s∈ω}H_{s} computable.

Now, let H_{0} = {g_{0} = 0} and f(i, j, n, s) = 0, for all i, j, n, s ∈ ω such that s = 0. Suppose now that s > 0 and we have constructed the finite sets H_{0} ⊆ H_{1} ⊆ ⋯ ⊆ H_{s} ⊂ G^{∞} and defined f(i, j, n, t) for all 0 ≤ t ≤ s. Suppose also that, for all i, j, n, s ∈ ω such that g_{i}, g_{j} ∉ ⟨H_{s}⟩, we have:

(a) If f(i, j, n, s) = 0 then part (i) of R_{i,j,n} is holds;

(b) If f(i, j, n, s) = 1 and n ∈ A_{s} then part (ii) of R_{i,j,n} holds; and

(c) If f(i, j, n, s) = 1 and n ∈ B_{s} then part (iii) of R_{i,j,n,s} holds.

Now, check whether there is a triple ⟨i, j, n⟩ < s such that (1) {g_{i}} ∪ H_{s} is ℤ-linearly independent;

(2) {g_{j}} ∪ H_{s} is ℤ-linearly independent;

(3) n ∈ A_{s} ∪ B_{s}; and

(4) h(i, j, n, s) = 0.

If no such triple exists and g_{s+1} ∉ ⟨H_{s}⟩, then let H_{s+1} = H_{s} ∪ {g_{s+1}}. Otherwise, if no such triple exists and g_{s+1} ∈ ⟨H_{s}⟩, then let H_{s+1} = H_{s}.

Now suppose that there exists a triple ⟨i, j, n⟩ as above, and fix the least such triple. First, if n ∈ A, then find the least (under some computable coding of integers) k ∈ ℤ such that g_{l} ∉ ⟨H_{s} ∪ {e_{g(i,j,n)} − k · g_{i}}⟩ for all 0 ≤ l ≤ s such that g_{l} ∉ H_{s}. The existence of such a k ∈ ℤ follows from Lemma 4.5 below and the fact that ℤ is infinite. Now, let H′_{s} = H_{s} ∪ {e_{g(i,j,n)} − k · g_{i}} and define f(i, j, n, s + 1) = 1. On the other hand, if n ∈ B, then repeat this action with g_{j} replacing g_{i}. Finally, if g_{s+1} ∈ ⟨H′_{s}⟩ then let H_{s+1} = H_{s} ∪ {g_{s+1}}; otherwise let H_{s+1} = H′_{s}. Also, let f(i, j, n, s + 1) = h(i, j, n, s) for all other i, j, n ∈ ω. Lemma 4.6 below says that our inductive hypotheses are maintained throughout the construction, hence our construction is valid.

Recall that H is a computable normal subgroup of G, since we ensured that for all s ∈ ω, g_{s} ∈ H if and only if g_{s} ∈ H_{s}. Now, let G = G^{∞}/H and note that G is computable since H is computable. The elements of G are given by <_{ω}-least representatives, which is a computable subset of G^{∞}. For any g ∈ G^{∞} we let \overline{g} ∈ G be the image of g under the canonical homomorphism G^{∞} → G. Now, suppose that W is a nontrivial proper subgroup of G, and let W_{0} be such that W = W_{0}/H. Then, since H is computable it follows that W_{0} is a W -computable subgroup of G^{∞}, such that H ⩽ W_{0} ⩽ G^{∞}. Let i, j ∈ ω be such that g_{i} ∈ W_{0} and g_{j} ∉ W_{0}, and define

S = {n ∈ ω : e_{g(i,j,n)} ∈ W_{0}}.

It follows that S ≤_{T} W_{0} ≡_{T} W, that A ⊆ S, and that B ∩ S = ∅. Therefore, S has PA Turing degree, as required. Finally, note that G is not finitely generated, since X = \{\overline{e}_{g(i,j,n)} : n ∈ ω \ (A ∪ B)\} generates a free subgroup of G, since no generator of H mentions any e_{g(i,j,n)} ∈ G^{∞}, n ∈ ω. It follows that any generating set for G must include X, and since ω \ (A ∪ B) is infinite it follows that G is not finitely generated. Therefore, G is not simple. □

The following two technical algebraic lemmas are written in the context of the proof of the previous theorem. These lemmas correspond to [DHK^{+}07, Lemma 2.4] and [DHK^{+}07, Lemma 2.6], respectively.

Lemma 4.5. Suppose that conditions (1)–(4) hold for some triple ⟨i, j, n⟩ at stage s > 2. Then, for each 0 ≤ t ≤ s such that g_{t} ∉ H_{s}, there is at most one number k_{t} ∈ ℤ such that g_{t} ∈ ⟨H_{s} ∪ {e_{g(i,j,n)} − k_{t} · g_{i}}⟩. The same is obviously true with the last occurrence of g_{i} replaced by g_{j}, since our hypotheses on i and j are symmetric.

Proof. Let e = e_{g(i,j,n)}. Now suppose, for a contradiction, that there is some 0 ≤ t ≤ s with g = g_{t} ∉ H_{s} and two distinct numbers k_{1}, k_{2} ∈ ℤ, and corresponding h_{1}, h_{2} ∈ ⟨H_{s}⟩ such that both

g = e − k_{1} · g_{i} + h_{1}

and

g = e − k_{2} · g_{i} + h_{2}

hold. Subtracting these two equations from each other and rearranging terms yields the equality

h_{1} − h_{2} = (k_{1} − k_{2}) · g_{i},

which violates condition (1) above, a contradiction. □

Lemma 4.6. The inductive hypotheses (i)–(iii) are maintained throughout the construction of H.

Proof. First of all, by our construction of H it is easy to check that each finite set H_{s}, s ≥ 2, consists of (finitely many) linear combinations of finitely many elements of the form e_{g(i,j,n)} − k · g_{i} or e_{g(i,j,n)} − k · g_{j}, 0 ≠ k ∈ ℤ, but never both. Fix s ≥ 2 and let X = {x_{0}, …, x_{l}} ⊂ G^{∞}, 0 ≤ l ≤ s, l ∈ ω, be such a generating set for H_{s}, and for all 0 ≤ r ≤ l suppose that

x_{r} = e_{g(i_{r},j_{r},n_{r})} − k_{r} · g_{z}, z ∈ {i_{r}, j_{r}}.

To prove the lemma it suffices to show that for any given triple ⟨i, j, n⟩ that is not equal to any ⟨i_{r}, j_{r}, n_{r}⟩, 0 ≤ r ≤ l, we have that x = e_{g(i,j,n)} − k · g_{i} ∉ ⟨X⟩, for any k ∈ ℤ. The proof is easy, and by contradiction. Suppose (for a contradiction) that x ∈ ⟨X⟩, i.e. there exists R ⊆ {0, …, l} and a sequence of nonzero integers ⟨c_{r} : r ∈ R⟩ such that

x = ∑_{r∈R} c_{r}x_{r}.

In this case we must have that g(i, j, n) ∈ ∪_{r∈R}supp(x_{r}). Also, since g is injective and ⟨i, j, n⟩ is distinct from any of the ⟨i_{r}, j_{r}, n_{r}⟩, 0 ≤ r ≤ l, it follows that there exists 0 ≤ r_{0} ≤ l such that g(i, j, n) ∈ supp(g_{z}), z ∈ {i_{r_{0}}, j_{r_{0}}}. Now it follows that g(i_{r_{0}}, j_{r_{0}}, n_{r_{0}}) > max supp(g_{z}) and hence

max ⋃_{r∈R} supp(x_{r}) > g(i, j, n) > max supp(g_{i}) ∪ supp(g_{j}).

Finally, if r_{0} ∈ R is chosen such that max ∪_{r∈R}supp(x_{r}) = max supp(x_{r_{0}}), then by our construction of g it follows that r_{0} is the only r ∈ R for which g(i_{r_{0}}, j_{r_{0}}, n_{r_{0}}) ∈ supp(x_{r}). But, by the displayed equation above, this means that c_{r_{0}} = 0, a contradiction. □

Corollary 4.7. There exists a nonsimple abelian group G such that every nontrivial finitely generated subgroup of G computes ∅′.

Proof. Let G be as in Theorem 4.4 above. Then every nontrivial finitely generated subgroup H of G is proper (since we showed that G is not finitely generated), computably enumerable, and of PA Turing degree. It is well-known that all such sets H compute ∅′ (this fact is known as Arslanov’s Completeness Criterion; see [Soa87, Theorem V.5.1] for more details). □

Theorem 4.8. There is an abelian (and therefore nilpotent) group G such that for all g_{0}, …, g_{N} ∈ G, N ∈ ω, every ascendant sequence in G beginning with ⟨g_{0}, …, g_{N}⟩ computes ∅′.

Proof. Let G be as in Corollary 4.7 and Theorem 4.4 above and note that every ascendant sequence in G beginning with the finitely generated subgroup X = ⟨g_{0}, …, g_{N}⟩ contains X, which computes ∅′ via Corollary 4.7 above. □

We end with the following interesting open (and purely group theoretic) question related to Theorem 4.1 above. To the best of our knowledge the answer is unknown.

Question 4.9. Let G be a locally nilpotent group of cardinality κ > ω, and let a ∈ G. Is there necessarily an ascendant sequence in G beginning with ⟨a⟩ of length at most κ + 1?

References

[AK01] C. J. Ash and J. F. Knight. Computable structures and the hyperarithmetical hierarchy. Elsevier, 2001.

[Boo54] W. W. Boone. Certain simple unsolvable problems in group theory, i. Nederl. Wetensch Proc. Ser. A, 57:231–237, 1954.

[CS11] B.F. Csima and D.R. Solomon. The complexity of central series in nilpotent computable groups. Ann. Pure App. Log., 162:667–678, 2011.

[DF99] D.S. Dummit and R.M. Foote. Abstract Algebra. John Wiley & Sons, 1999. [DHK^{+}07] R. Downey, D. Hirschfeldt, A. Kach, S. Lempp, J. Mileti, and A. Montalban. Subspaces of

computable vector spaces. J. Algebra, 314:888–894, 2007.

[FS56] A. Frölich and J.C. Shepherdson. Effective procedures in field theory. Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 248:407– 432, 1956.

[GSW03] R. Göbel, S. Shelah, and L. Wallutis. On universal and epi-universal locally nilpotent groups. Ill. J. Math., 47:223–236, 2003.

[Hal34] P. Hall. A contribution to the theory of groups of prime power order. Proc. Lon. Math. Soc., 36:29–95, 1934.

[Hal50] M. Hall. A basis for free lie rings and higher commutators in free groups. Proc. Amer. Math. Soc., 6:575–581, 1950.

[Hal59] M. Hall. The theory of groups. Macmillan, New York, 1959.

[Kar63] M. I. Kargapolov. Generalized soluble groups. Algebra i Logika, 2:19–28, 1963.

[KO10] L. A. Kurdachenko and J. Otal. Groups with families of generalized normal subgroups. Monografias de la Real Academia de Ciencias de Zaragoza, 33:241–254, 2010.

[Kro82] L. Kronecker. Grundzüge einer arithmetischen theorie der algebraischen groössen. J. Reine Angew. Math., 92:1–122, 1882.

[Lan93] S. Lang. Algebra. Springer-Verlag, 1993.

[Mil91] C. F. Miller. Decision problems for groups – survey and reflections. In Algorithms and Classification in Combinatorial Group Theory, pages 1–60, 1991.

[MN77] G. Metakides and A. Nerode. Recursively enumerable vector spaces. Ann. Math. Logic, 11:147–171, 1977.

[Nov55] P. S. Novikov. On the unsolvability of the word problem in group theory. Trudy Math. Inst. Steklov, 44:1–143, 1955.

[Rab60] M.O. Rabin. Computable algebra, general theory and theory computable fields. Trans. Amer. Math. Soc., 95:341–360, 1960.

[Rob96] D. J. S. Robinson. A course in the theory of groups. Springer-Verlag, New York, 1996.

[Rob11a] D. J. S. Robinson. Finiteness conditions and generalized soluble groups, vol. 1, second edition. Springer-Verlag, Berlin, 2011.

[Rob11b] D. J. S. Robinson. Finiteness conditions and generalized soluble groups, vol. 2, second edition. Springer-Verlag, Berlin, 2011.

[Sim09] S.G. Simpson. Subsystems of Second Order Arithmetic, second edition. Cambridge University Press, 2009.

[Soa] R.I. Soare. Computability theory and applications. Springer-Verlag, to appear.

[Soa87] R.I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, 1987.

[Sol99] D. R. Solomon. Ordered groups: a case study in reverse mathematics. Bull. Symb. Log., 5:45–58, 1999.

[vdW] B.L. van der Waerden. Algebra, vol. 1. Springer-Verlag, 2003.

Department of Pure Mathematics, University of Waterloo, Waterloo, ON N2L 3G1, Canada

Department of Mathematics, Cornell University, Ithaca, NY 14853-4201, USA