Efficient multiplication algorithms for finite polycyclic groups

by Burkhard H^{}öfling

Technische Universit^{}ät, Institut f^{}ür Geometrie, Pockelsstr. 14, 38106 Braunschweig, Germany

                       e-mail: b.hoefling@tu-bs.de

Abstract: Let G be a finite soluble group given by a reduced confluent polycyclic presentation. Represent group elements by reduced words. Then there exists an algorithm for multiplying two group elements which has subexponential running time and requires polynomial space. Moreover, given the prime factorisation of the group order, the problem of multiplying two group elements is probabilistically polynomial time equivalent to the same problem for p-groups, where p divides the order of G.

Classification (AMS 2000): 20-04, 20D10, 68W40

1. Introduction

A polycyclic presentation 𝒫 of a (necessarily soluble) finite group G is a presentation of the form

⟨ g_{1}, …, g_{n} | g_{i}^{e_{i}} = w_{i,i}, 1 ≤ i ≤ n, g_{j}g_{i} = g_{i}w_{i,j}, 1 ≤ i < j ≤ n ⟩,

where, for 1 ≤ i ≤ j ≤ n, the e_{i} are integers ≥ 2 and the w_{i,j} are words in g_{i+1}, …, g_{n}. Regarding the above relations as rewriting rules g_{i}^{e_{i}} → w_{i,i}, g_{j}g_{i} → g_{i}w_{i,j}, we obtain a Knuth Bendix rewriting system for G with respect to the wreath product ordering; see [11, Section 9.4]. The rewriting process is usually called collection. The resulting reduced expression for g ∈ G with respect to this system is of the form g = g_{1}^{a_{1}} … g_{n}^{a_{n}}, where 0 ≤ a_{i} < e_{i}. We call 𝒫 reduced if the w_{i,j} are reduced; it is consistent if the corresponding Knuth Bendix rewriting system is confluent, that is, if the a_{i} are uniquely defined by g. This is clearly the case if and only if |G| = e_{1} ⋯ e_{n}. In this case, we will refer to g_{1}^{a_{1}} … g_{n}^{a_{n}} as the normal form or reduced form of g. Throughout the article, we will assume that all polycyclic presentations are reduced and consistent.

the process of finding the reduced form of the product w_{1}w_{2}, where w_{1} and w_{2} are reduced words in g_{1}, …, g_{n}, will be called a multiplication with respect to g_{1}, …, g_{n} (or with respect to 𝒫). A (Las Vegas) multiplication algorithm with respect to g_{1}, …, g_{n} is a (Las Vegas) algorithm which carries out such a multiplication. Note that every multiplication algorithm can compute a reduced expression for the inverse of an element, see Lemma 3.3. Using this fact, a multiplication algorithm can be used to reduce any word w in g_{1}, …, g_{n} to its normal form by replacing inverses and multiplying reduced subwords.

The possibly simplest multiplication algorithm consists in collecting the concatenation of the words to be multiplied. When collecting a word, usually several rewriting rules are applicable at each step. The efficiency of collection depends heavily on the strategy used to make a choice, and it is now generally believed that collection from the left is the best such strategy, at least for practical purposes; see [9, 12]. For nilpotent groups and p-groups, more elaborate multiplication algorithms are known; see [10]; note that some authors use the term “collection” in the more general sense of “multiplication”.

While algorithms such as collection from the left work very well in many practical situations, [9] contains easy examples of presentations of cyclic groups of prime power order for which the number of collection steps in any collection algorithm grows exponentially in the composition length of the group. On the other hand, such a group has an obvious presentation such that the number of collection steps only grows linearly in the composition length. This indicates that the performance of a collection algorithm not only depends on the strategy but also on the presentation of a given group G.

Therefore, in the present article, we use the following approach for finding efficient multiplication algorithms. In order to multiply two words which are reduced with respect to 𝒫, compute a presentation 𝒫′ of G for which a fast multiplication algorithm is known. Then translate the words to be multiplied into reduced words with respect to 𝒫′. Multiply then, using the multiplication algorithm for 𝒫′, and translate the result back into a reduced word with respect to 𝒫. Such an approach requires a preprocessing step for computing 𝒫′ and possibly additional information needed for subsequent translations of reduced words. This will be visible in the results below.

In Sections 3 – 5, we let 𝒫′ reflect the structure of the abelian factors in the derived series of G and use a slight variant of collection from the left and obtain Theorem 5.1, which can be summarised as follows. Details about our computational model can be found in Section 2.

Theorem. Let G be a finite soluble group of derived length d and composition length l, and let 𝒫 be a reduced confluent polycyclic presentation of a finite group G. Then there exists a multiplication algorithm such that r multiplications require at most

O((l^{3} log^{2} |G| + r)(Cl log |G|)^{2d} + dlL^{6}) ⊆ e^{C′ log l log log |G|}

bit operations, where C, C′ are suitable constants, and O(dl^{2} log |G|) bits of workspace.

Since the input includes 𝒫 and therefore has a bit length of at least log_{2} |G|, this has the following consequence.

Corollary. For any polycyclic presentation, there exists a multiplication algorithm which has subexponential running time and requires polynomial space.

In Sections 6 – 9, we follow a different approach. We show that the problem of finding an asymptotically fast multiplication algorithm for an arbitrary soluble group reduces to finding such an algorithm for p-groups, provided the prime factorisation of the e_{i} is known. This reduction is carried out in four steps. Proposition 6.1 shows that we may assume the e_{i} to be primes, and by Theorem 6.2, it suffices to consider presentations where a subset of the G_{i} forms a normal series with elementary abelian factors. Then we reduce to multiplications in nilpotent subgroups in Theorem 8.5, and finally from nilpotent subgroups to their Sylow p-subgroups in Theorem 9.1. Putting these results together, we obtain the following result; cf. Corollary 9.3.

Theorem. Let 𝒫 be a reduced confluent polycyclic presentation, and assume that the prime factorisation of each e_{i} is known. Then there exists a Las Vegas multiplication algorithm for 𝒫 which requires an expected number of

O(l^{4}P_{p}(G) + l^{9} log^{5} |G|M_{p}(G) + rl^{3} log^{3} |G|M_{p}(G))

bit operations to perform r multiplications, where l is the composition length of G.

Here, P_{p} and M_{p} are functions modelling the cost of r multiplications in the Sylow p-subgroup of G, one for each prime, where P_{p}(G) is the cost of a preprocessing step and M_{p}(G) is the cost of a subsequent multiplication. A more precise definition of P_{p} and M_{p} can be found in Section 9.

Thus, the question whether there exists a polynomial time multiplication algorithm for 𝒫 is reduced to the case of p-groups and the problem of factorising integers.

Corollary. If there exists a (Las Vegas) multiplication algorithm for p-groups which runs in polynomial time, then there exists a Las Vegas polynomial time multiplication algorithm for any finite soluble group, given prime factorisations of the e_{i}.

Note that it is an open problem whether integers can be factorised in polynomial time. Finding a factorisation of e ∈ ℕ is obviously a prerequisite for reducing to p-groups, for it is equivalent to finding the Sylow subgroups of the cyclic group ⟨ g | g^{e} = 1 ⟩.

The only probabilistic part of the algorithm is the use of the meat-axe algorithm for finding submodules of a reducible matrix group [7, 8].

The bounds obtained above, especially the one in the second theorem, may seem to be too large for practical computations. However, it seems unlikely that in concrete examples, the worst case assumptions leading to them are justified. Indeed, since a multiplication in G is replaced by a large number of multiplications in (usually small) p-subgroups, this may still lead to a reduction of the overall multiplication time. We leave the question of practical usefulness for further investigations.

2. Notation and definitions

Throughout the article, G will be a finite soluble group with reduced confluent polycyclic presentation

⟨ g_{1}, …, g_{n} | g_{i}^{e_{i}} = w_{i,i}, 1 ≤ i ≤ n, g_{j}g_{i} = g_{i}w_{i,j}, 1 ≤ i < j ≤ n ⟩.

The terms “multiplication”, “reduced form”, “normal word” etc. all refer to 𝒫 (or its generators g_{1}, …, g_{n}, unless specified otherwise. All polycyclic presentations will be assumed reduced and confluent.

Our computational model is based on the following assumptions. The number of bit operations for adding, subtracting and multiplying two nonnegative integers ≤ n is O(log n), O(log n) and O(log^{2} n), respectively. Division with remainder and the Extended Euclidean algorithm require O(log^{2} n) and O(log^{3} n) bit operations, respectively. Storing a nonnegative integer < n requires O(log n) bits, and copying it requires O(log n) bit operations.

We will also assume that a group multiplication in a group H requires at least O(log |H|) bit operations. This agrees with our assumptions on integer arithmetic and allows to ignore the cost of index arithmetic.

Let l_{i} = ⌊log_{2}(e_{i} − 1) + 1⌋ and put L_{k} = ∑_{i=k}^{n} l_{i} and I_{k} = ∑_{i=k}^{n} l_{i}^{3}. We set L = L_{1} and I = I_{1}. Note that L is a lower bound on the input length of a multiplication algorithm for G, since at least L bits are required to store the exponents e_{1}, …, e_{n} Moreover, a word in g_{1}, …, g_{n} requires O(L) bits of storage, so that 𝒫 can be stored using O(n^{2}L) ⊆ O(L^{3}) bits of storage. Clearly, L ∈ O(log |G|) and log |G| ∈ O(L).

3. Variants of collection from the left

If w = g_{i_{1}}g_{i_{2}} … g_{i_{r}} is a word in g_{1}, …, g_{n} which is not reduced, then collection from the left always chooses j minimal such that g_{i_{j}} … g_{i_{k}} is a left hand side of one of the relation in 𝒫 for an integer k ≥ j, and replaces g_{i_{j}} … g_{i_{k}} by the corresponding right hand side.

Easy examples show that the number of bit operations required to reduce a word g_{j}^{b}g_{i}^{a} using collection to the left grows at least linearly in a and b. This leads to performance problems when e_{i} and e_{j} are large. It is well-known that the case when b is large can be handled by fast powering, and that a similar idea, namely computing powers of the conjugation automorphism induced by g_{i}, can be used if a is large; cf. e. g. [5]. The following algorithm uses a similar approach, and it is not difficult to see that all bounds in this section hold with a suitable modification of collection from the left.

3.1 Algorithm. Input: integers i, k such that 1 ≤ i ≤ k ≤ n and such that g_{i} normalises G_{k+1}, reduced

words w_{1}, …, w_{r} ∈ G_{k+1}, a nonnegative integer b = ∑_{j=0}^{m−1} b_{j}2^{j} with b_{i} ∈ { 0, 1 }.

Output: the normal forms v_{l} of w_{l}^{g_{i}^{a−1}}w_{l}^{g_{i}^{a−2}} ⋯ w_{l}, where 1 ≤ l ≤ r.

(1) let x_{k+1} := w_{i,k+1}, …, x_{n} := w_{i,n};

(2) for l = 1, …, r do let u_{l} := w_{l}, v_{l} := 1;

(3) for j = 0, …, m − 1 do

(4) if b_{j} = 1, then

(5) for l = 1, …, r, write v_{l} = g_{k+1}^{a_{k+1}} ⋯ g_{n}^{a_{n}} and replace v_{l} by the normal form of x_{k+1}^{a_{k+1}} ⋯ x_{n}^{a_{n}}u_{l}.

(6) for l = 1, …, r do write u_{l} = g_{k+1}^{a_{k+1}} ⋯ g_{n}^{a_{n}} and let u_{l} be the normal form of x_{k+1}^{a_{k+1}} ⋯ x_{n}^{a_{n}}u_{l};

(7) for l = k + 1, …, n do write x_{j} = g_{k+1}^{a_{k+1}} ⋯ g_{n}^{a_{n}} and let y_{j} be a reduced expression for x_{k+1}^{a_{k+1}} ⋯ x_{n}^{a_{n}}.

(8) for l = k + 1, …, n do let x_{l} := y_{l};

3.2 Lemma. Let i, k be integers with 1 ≤ i ≤ k < n, and assume that g_{i} normalises G_{k+1}. Moreover, let b ∈ ℕ \ { 0 } and m = ⌊log_{2} b⌋ + 1, and assume that w_{1}, …, w_{r} ∈ G_{k+1} are reduced. Then the normal forms of

w_{l}^{g_{i}^{b−1}}w_{l}^{g_{i}^{b−2}} ⋯ w_{l}^{g_{i}}w_{l},  w_{l}w_{l}^{g_{i}} … w_{l}^{g_{i}^{b−1}},  w_{l}^{g_{i}^{b}},

where 1 ≤ l ≤ r, can be computed using O(m(n − k + r)L_{k+1}) multiplications in G_{k+1} and O((n − k + r)L_{k+1}) bits of workspace.

Proof. We only prove the statement for

w_{l}^{g_{i}^{b−1}}w_{l}^{g_{i}^{b−2}} ⋯ w_{l},

for which Algorithm 3.1 is an algorithm, the other statements being similar. To prove the correctness of Algorithm 3.1, it suffices to consider the case when r = 1. Write g = g_{i}, u = u_{1}, v = v_{1}, w = w_{1}. For t ∈ ℕ, let z_{t} := w^{g^{l−1}}w^{g^{l−2}} ⋯ w, and observe that z_{s+t} = (z_{s})^{g^{t}}z_{t} for all s, t ∈ ℕ. Now an easy induction argument shows that at

the beginning of Step (4) of Algorithm 3.1, we have x_{l} = g_{l}^{g^{2^{j}}}, u = z_{2^{j}}, v = z_{s_{j}}, where s_{j} = ∑_{l=0}^{l−1} b_{j}2^{j}, so that

(g_{k+1}^{a_{k+1}} ⋯ g_{n}^{a_{n}})^{g^{2^{j}}} = x_{k+1}^{a_{k+1}} ⋯ x_{n}^{a_{n}}.  (∗)

Evaluating (∗) using fast powering requires at most 2 ∑_{l=k+1}^{n}⌊1 + log_{2} a_{l}⌋ ∈ O(L_{k+1}) multiplications in G_{k+1}. Storing a reduced word requires O(L_{1}) bits. The statement now follows.

In the case of collection to the left, it is well-known that the normal form w of g^{−1}h can be computed at the same cost as the product gw; see also Proposition 3.4 (b). For other multiplication algorithms, this need not be the case, see, e. g. [10, Section 7.1] However, we obtain the following.

3.3 Lemma. Let g, h be normal words in G. Then the normal form of g^{−1}h can be computed using at most n multiplications in G and O(L) bits of workspace.

Proof. Let g = g_{1}^{a_{1}} … g_{n}^{a_{n}}, h = g_{1}^{b_{1}} … g_{n}^{b_{n}} be the normal forms of g and h. Let 0 ≤ c < e_{1} be such that c ≡ b_{1} − a_{1} (mod e_{1}). Compute the normal form g_{1}^{d_{1}} … g_{n}^{d_{n}} of gg_{1}^{c}, using one multiplication in G. Let g^{∗} = g_{2}^{d_{2}} … g_{n}^{d_{n}}, h^{∗} = g_{2}^{b_{1}} … g_{n}^{b_{n}}. In G_{2}, recursively compute a normal form w^{∗} such that (g^{∗})w^{∗} = h^{∗}, at a cost of O(L_{2}) multiplications in G. Then w = g_{1}^{c}w^{∗} is in normal form, and one easily checks that gw = h, observing that d_{1} = b_{1}.

The complexity of the modified version of collection from the left can now be analysed as follows; note that the hypotheses are always satisfied for k = 1.

3.4 Proposition. Let 1 ≤ k ≤ n be such that G_{k+1} ⊴ G and for all i < j ≤ k, w_{i,i} = g_{i+1}^{d_{i,i}}v_{i,i} with 0 ≤ d_{i,i} < e_{i+1} and w_{i,j} = g_{j}v_{i,j}, where the v_{i,i} and v_{i,j} are reduced words in G_{k+1}. Let w ∈ G be a reduced word.

(a) If 1 ≤ i ≤ k < n and 0 ≤ b < e_{i}, then the word wg_{i}^{b} can be reduced to normal form using

O(l_{i}(n − i)L_{k+1} + (L_{i+1} − L_{k+1})(n − k)L_{k+1})

multiplications in G_{k+1} and requiring O((n − i)L_{k+1}) bits of workspace.

(b) If k < n, a multiplication and an inversion in G can be carried out using

O(k(n − k)(L_{1} − L_{k+1})L_{k+1})

multiplications in G_{k+1}, requiring O(nL_{k+1}) bits of workspace.

(c) If k = n, then a multiplication or an inversion in G requires at most

O(nL_{1})

bit operations and O(1) bits of workspace.

Proof. Let “multiplication” mean “multiplication in G_{k+1}”.

(a) An easy induction argument shows that

g_{j}^{g_{i}^{b}} = g_{j}v_{i,j}v_{i,j}^{g_{i}}v_{i,j}^{g_{i}^{2}} ⋯ v_{i,j}^{g_{i}^{b−1}}.

Therefore, by Lemma 3.2, reduced words u_{i+1}, …, u_{k} ∈ G_{k+1} such that g_{j}^{g_{i}^{b}} = g_{j}u_{j} can be computed using at most O(l_{i}(n − i)L_{k+1}) multiplications. Now assume that g_{1}^{a_{1}} … g_{n}^{a_{n}} is a reduced word in G. Then

g_{1}^{a_{1}} … g_{n}^{a_{n}}g_{i}^{b} = g_{1}^{a_{1}} … g_{i−1}^{a_{i−1}}g_{i}^{a_{i}}g_{i}^{b}(g_{i+1}^{g_{i}^{b}})^{a_{i+1}} … (g_{k}^{g_{i}})^{a_{k}}(g_{k+1} … g_{n})^{g_{i}^{b}}
= g_{1}^{a_{1}} … g_{i−1}^{a_{i−1}}g_{i}^{a_{i}}g_{i}^{b}(g_{i+1}u_{i+1})^{a_{i+1}} … (g_{k}u_{k})^{a_{k}}(g_{k+1} … g_{n})^{g_{i}^{b}}
= g_{1}^{a_{1}} … g_{i−1}^{a_{i−1}}g_{i}^{c_{i}}g_{i+1}^{d_{i+1}}v_{i+1}(g_{i+1}u_{i+1})^{a_{i+1}} … (g_{k}u_{k})^{a_{k}}(g_{k+1} … g_{n})^{g_{i}^{b}}

where either c = a_{i} + b < e_{i}, d_{i+1} = 0 and v_{i+1} = 1, or a_{i} + b ≥ e_{i}, c = a + b_{i} − e_{i}, d_{i+1} = d_{i,i}, and v_{i+1} = v_{i,i}.

Let i ≤ j ≤ k, 0 ≤ a, c < e_{j} and u, v ∈ G_{k+1}. Since

g_{j}^{c}v(g_{j}u)^{a} = g_{j}^{a+c}v^{g_{j}^{a}}u^{g_{j}^{a−1}}u^{g_{j}^{a−2}} ⋯ u,

by Lemma 3.2, we obtain a reduced word w ∈ G_{k+1} such that g_{j}^{c}u(g_{j}v)^{a} = g_{j}^{a+c}w using O(l_{j}(n − k)L_{k+1}) multiplications. This also covers O(l_{j}) bit operations required for the addition of a and c. Thus, for j = i + 1, …, k − 1, we use this to replace g_{j}^{d_{j}}v_{j}(g_{j}u_{j})^{a_{j}} by a reduced expression of the form g_{j}^{c_{j}}g_{j+1}^{d_{j+1}}v_{j+1}, where 0 ≤ c_{j} < e_{j}, 0 ≤ d_{j+1} < e_{j+1} and v_{j+1} ∈ G_{k+1}. Therefore, at a cost of O((L_{i+1} − L_{k+1})(n − k)L_{k+1}) multiplications, we obtain

g_{1}^{a_{1}} … g_{n}^{a_{n}}g_{i}^{b} = g_{1}^{a_{1}} … g_{i−1}^{a_{i−1}}g_{i}^{c_{i}} … g_{k−1}^{c_{k−1}}g_{k}^{d_{k}}v_{k}(g_{k+1} … g_{n})^{g_{i}^{b}},

which can be reduced to normal form using O(l_{i}(n−k)L_{k+1}) multiplications. The claim now follows.

(b) Let g = g_{1}^{a_{1}} … g_{n}^{a_{n}} and h = g_{1}^{b_{1}} … g_{n}^{b_{n}} be reduced words. Successively multiplying the first word by g_{1}^{b_{1}}, … g_{n}^{b_{n}} as in (a) and then by the reduced word g_{k+1}^{b_{k+1}} … g_{n}^{b_{n}} ∈ G_{k+1} gives the normal form of the product. This requires

O((L_{1} − L_{k+1})nL_{k+1} + k(n − k)(L_{1} − L_{k+1})L_{k+1})

multiplications, which proves (b). To invert g, we choose h by setting b_{1} ≡ −a_{1} (mod e_{1}), b_{i} ≡ −a_{i} − d_{i−1,i−1} for i = 2, …, k and b_{k+1} = … = b_{n} = 0. If w is the reduced form of gh, then w ∈ G_{k+1}, and the normal form v of its inverse can be found at a cost of O((n − k)L_{k+1}) multiplications by Lemma 3.3. Clearly, g_{1}^{b_{1}} … g_{k}^{b_{k}}v is a reduced expression for the inverse of g.

(c) Note that this implies that G is abelian. Thus, an argument similar to (a) shows that wg_{i}^{b} can be reduced to its normal form using O(L) multiplications in G. The result now follows as in (b).

3.5 Remark. Instead of re-computing the x_{l} in Algorithm 3.1 and related algorithms in Lemma 3.2 each time, one may store them, once they are computed for the first time. This requires O(nL_{1}^{2}) bits of storage. If all necessary x_{j} are known, this reduces the cost in Lemma 3.2 and Proposition 3.4 (a) and (b) to O(mrL_{k+1}), O(l_{i}k + (L_{i+1} − L_{k+1})L_{k+1}), and O(k(L_{1} − L_{k+1})L_{k+1}), respectively. .

4. Rewriting words with respect to polycyclic presentations

Let (h_{1}, …, h_{r}) be a sequence of elements of G and for i = 1, …, r + 1, write H_{i} = ⟨ h_{i}, …, h_{r} ⟩. The sequence (h_{1}, …, h_{r}) is a polycyclic generating sequence of a subgroup H of G if H = H_{1} and for i = 1, …, r, H_{i+1} is a proper normal subgroup of H_{i} such that H_{i}/H_{i+1} is cyclic. The series

H = H_{1} ▷ H_{2} ▷ ⋯ ▷ H_{r} ▷ H_{r+1} = 1

is the polycyclic series of H associated with (h_{1}, …, h_{r}).

Evidently, (g_{1}, …, g_{n}) is a polycyclic generating sequence of G. Conversely, if (h_{1}, …, h_{r}) is a polycyclic generating sequence of H, then there exists a polycyclic presentation of H with generators h_{1}, …, h_{r}.

Let g = g_{1}^{a_{1}} … g_{n}^{a_{n}} with 0 ≤ a_{i} < e_{i}. If g ≠ 1, the depth dp(h) of h ≠ 1 is the least integer i such that a_{i} ≠ 0, the leading coefficient lc(g) is a_{i} and the relative order ro(g) is the integer e_{i}. We put dp(1) = n + 1 and lc(1) = 0.

A polycyclic generating sequence (h_{1}, …, h_{r}) of H is an induced generating sequence of H with respect to 𝒫 if dp(h_{i}) < dp(h_{i+1} for i = 1, …, r.

Let H be a subgroup of G with polycyclic generating sequence h_{1}, …, h_{r}. The following two algorithms serve to rewrite a reduced word w ∈ H in the generators g_{1}, …, g_{n} as a reduced word in h_{1}, …, h_{r}, and may also be used as a membership test for H. For the case when the e_{i} are primes, very similar algorithms are implemented in the computer algebra system GAP [3], but seem not to have been published.

4.1 Algorithm. Input: a polycyclic presentation 𝒫 of G, a polycyclic generating sequence h_{1}, …, h_{r}

of a subgroup H of G, and an element g ∈ G, where h_{1}, …, h_{r} and g are given as normal words in g_{1}, …, g_{n}.

Output: integers c_{1}, …, c_{r}, d_{1}, …, d_{r}, j_{1}, …, j_{n} and normal words h_{1}^{∗}, …, h_{r}^{∗} ∈ G such that

(a) H_{i+1}h_{i}^{∗} = H_{i+1}h_{i}^{c_{i}} and ⟨ H_{i+1}h_{i}^{∗} ⟩ = ⟨ H_{i+1}h_{i} ⟩;

(b) (h_{i}^{∗})^{d_{i}} ∈ H_{i+1}, and if 1 ≤ k < d_{i} and x ∈ H_{i+1}(h_{i}^{∗})^{k}, then dp(x) ≤ dp(h_{i}^{∗}) and |H_{i} : H_{i+1}| = d_{i};

(c) if h_{i}^{∗} ≠ 1, then lc(h_{i}^{∗}) divides ro(h_{i}^{∗}), and if i < j and dp(h_{i}^{∗}) = dp(h_{j}^{∗}), then lc(h_{i}^{∗}) divides lc(h_{j}^{∗}),

(d) j_{l} is the least integer such that dp(h_{j_{l}}^{∗}) = l if such an integer exists, and j_{l} = n+1 otherwise.

where H_{i} = ⟨ h_{i}, …, h_{r} ⟩ for i = 1, …, r + 1.

(1) for d := 1, …, n do let j_{d} := n + 1;

(2) for i := r, r − 1, …, 1 do

(3) let h_{i}^{∗} := h_{i};

(4) let d := dp(h_{i}^{∗}); let j := j_{d};

(5) if j ≤ r then let e := lc(h_{j}^{∗}), h := h_{j}^{∗} else let e := ro(h_{i}^{∗}), h := 1;

(6) call the Extended Euclidean Algorithm to compute 0 ≤ c_{i}, t < ro(h_{i}^{∗}) such that c_{i} lc(h_{i}^{∗}) + te ≡ gcd(lc(h_{i}^{∗}), e) (mod ro(h_{i}^{∗}); let h_{i}^{∗} := h^{t}(h_{i}^{∗})^{c_{i}};

(7) if h_{i}^{∗} ≠ 1 and lc(h_{i}^{∗}) = lc(h), then let h_{i}^{∗} := h^{−1}h_{i}^{∗}; go to (4);

(8) if h_{i}^{∗} ≠ 1 then let d_{i} = e/ lc(h_{i}^{∗}); let j_{d} := i; else let d_{i} = 1;

4.2 Proposition. Algorithm 4.1 is correct and requires O(rL) multiplications in G and O(rI) bit operations. Moreover, the sequence (h_{j_{i}})_{j_{i}≤n} is an induced generating sequence of H.

Proof. If the condition in Step (7) is true, d = dp(h_{i}^{∗}) increases, so that for each i, this can only happen n times. The Extended Euclidean Algorithm requires

O(log^{3} ro(h_{i}^{∗})) = O(l_{d}^{3})

bit operations, and computing the normal form of h^{t}(h_{i}^{∗})^{c_{i}} needs O(l_{d}) multiplications in G. This gives the above bounds on the complexity. By induction on r − i, it is easy to see that properties (a) – (d) of Algorithm 4.1 hold.

The following algorithm uses the output of Algorithm 4.1 to rewrite a reduced word in g_{1}, …, g_{n} as a reduced word in an arbitrary polycyclic generating sequence of a subgroup of G.

4.3 Algorithm (Exponents with respect to polycyclic generating sequence). Input: a polycyclic presentation 𝒫 of G, a polycyclic generating sequence h_{1}, …, h_{r} of

a subgroup H of G, h_{1}^{∗}, …, h_{r}^{∗} ∈ G, integers c_{1}, …, c_{r}, d_{1}, …, d_{r}, j_{1}, …, j_{n} satisfying properties (a) – (d) of Algorithm 4.1, and an element g ∈ G, where h_{1}, …, h_{r} and g are given as normal words in g_{1}, …, g_{n}.

Output: integers a_{1}, …, a_{r} and w ∈ G such that g = h_{1}^{a_{1}} … h_{r}^{a_{r}}w satisfying 0 ≤ a_{i} < d_{i} = |H_{i} : H_{i+1}|, and w = 1 if g ∈ H, where H_{i} = ⟨ h_{i}, …, h_{r} ⟩ for i = 1, …, r + 1.

(1) for i = 1, …, r do

(2) let v := w; let d := dp(v);

(3) while d ≤ n and i < j_{d} ≤ n and lc(h_{j_{d}}^{∗}) divides lc(v) do

(4) let c := e_{d} − lc(v)/ lc(h_{j_{d}}^{∗}); let v := (h_{j_{d}}^{∗})^{c}v; let d := dp(v);

(5) if v ≠ 1, then

(6) if d = dp(h_{i}^{∗}) and lc(h_{i}^{∗}) divides lc(v), then

(7) let a_{i} = c_{i} lc(v)/ lc(h_{i}^{∗}) mod d_{i}; let w := h_{i}^{−a_{i}}w;

(8) else stop.

4.4 Proposition. Algorithm 4.3 is correct and requires O(rL) multiplications in G.

Proof. Note first that for each i, Step (4) of Algorithm 4.3 is executed at most n times, since dp(h_{i}^{∗}) increases. Since c < e_{d}, computing (h_{j_{d}}^{∗})^{c}v requires at most O(l_{d}) multiplications, giving a cost of O(L) for each i. This also covers the cost of O(n + l_{d}) for computing h_{i}^{−a_{i}}w.

It is also clear that g = h_{1}^{a_{1}} … h_{r}^{a_{r}}w with 0 ≤ a_{i} < d_{i}. Therefore it remains to consider the case when w ∈ H. Now assume inductively that w ∈ H_{i} at Step (2). Then at Step (5), v is an element of maximal depth in the coset H_{i+1}v = H_{i+1}w. In particular, w ∈ H_{i+1} if v = 1.

If v ≠ 1, by properties (a) and (b) of Algorithm 4.1, there exists an integer k with 0 ≤ k < d_{i} such that H_{i+1}v = H_{i+1}w = H_{i+1}(h_{i}^{∗})^{k} = H_{i+1}h_{i}^{c_{i}k}. By the minimality of dp(v) and dp(h_{i}^{∗}), we have dp(v) = dp(h_{i}^{∗}), and so lc(v) ≡ k lc(h_{i}^{∗}) (mod ro(h_{i}^{∗})). Since lc(h_{i}^{∗}) divides ro(h_{i}^{∗}), it follows that lc(v) is divisible by lc(h_{i}^{∗}) and k = lc(v)/ lc(h_{i}^{∗}). Thus, we have H_{i+1}w = H_{i+1}h_{i}^{a_{i}}, and so h_{i}^{−a_{i}}w ∈ H_{i+1}, as required.

Algorithm 4.1 and Algorithm 4.3 require that the generators of the polycyclic generating sequence (h_{1}, …, h_{r}) are given as words in the generators of 𝒫. The following result can sometimes be used if the g_{i} are given as reduced words in the h_{i}.

4.5 Proposition. Let (h_{1}, …, h_{n}) be a polycyclic generating sequence of G, and assume that g_{i} = h_{i}h_{i+1}^{a_{i,i+1}}h_{i+2}^{a_{i,i+2}} …, h_{n}^{a_{i,n}} is a reduced word in h_{1}, …, h_{n} for i = 1, …, n.

(a) There exists an algorithm which, given the a_{i,j} above, computes reduced expressions of h_{1}, …, h_{n} at a cost of O(nL) multiplications in G.

(b) Given reduced expressions for the h_{i} as in (a), a reduced word in g_{1}, …, g_{n} can be rewritten as a reduced word in h_{1}, …, h_{n} using O(nL) multiplications in G. The opposite direction requires O(L) multiplications.

Proof. Observe first that ⟨ h_{i}, …, h_{n} ⟩ = ⟨ g_{i}, …, g_{n} ⟩ for i = 1, …, n, so that (h_{1}, …, h_{n}) is, in fact, an induced generating sequence of G.

We show that every h_{i} can be written as a reduced word v_{i} in g_{1}, …, g_{n}. Assume that this is true for h_{i+1}, …, h_{n}. Then h_{i} = g_{i}(h_{i+1}^{a_{i,i+1}} …, h_{n}^{a_{i,n}})^{−1} Replacing each h_{j} on the right hand side by a reduced expression in g_{i+1}, …, g_{n}, a reduced expression for h_{i} in g_{i}, …, g_{n} can be obtained using O(L_{i+1}) multiplications in G, taking into account that the reduced form of an inverse in G_{i+1} requires n − i ∈ O(L) multiplications by Lemma 3.3.

Therefore we obtain reduced expressions of the h_{i} using O(nL) multiplications. Now every reduced word in h_{1}, …, h_{n} can be rewritten as a reduced word in g_{1}, …, g_{n} by substituting reduced expressions for the h_{i} and evaluating, at a cost of O(L) multiplications in G. To rewrite a reduced word in g_{1}, …, g_{n}, observe that we may choose h_{i}^{∗} = h_{i}, d_{i} = e_{i}, c_{i} = 1 in Algorithm 4.3. Thus, Proposition 4.4 gives the result.

Sometimes, a polycyclic presentation is changed by multiplying generators by elements of a small G_{k+1}. In this case, a new presentation can be computed using multiplications in G_{k+1} alone.

4.6 Proposition. Assume that G_{k+1} ◁G and let (h_{1}, …, h_{n}) be a polycyclic generating sequence of G such that h_{i} = g_{i}u_{i} for all i = 1, …, k, where u_{1}, …, u_{k} are reduced words in G_{k+1}, and h_{i} ∈ G_{k+1} for i = k + 1, …, n. Then the following statements hold.

(a) A reduced word in h_{1}, …, h_{n} can be rewritten as a reduced word in g_{1}, …, g_{n} using O(k(L_{1} − L_{k+1})L_{k+1}) multiplications in G_{k+1}.

(b) A reduced word in g_{1}, …, g_{n} be rewritten as a reduced word in h_{1}, …, h_{n} using O(n(L_{1} − L_{k+1})L_{k+1}) multiplications in G_{k+1} and O((n − k)I_{k+1}) bit operations.

(c) A polycyclic presentation of G with generators h_{1}, …, h_{n} can be computed using O(n^{3}(L_{1} − L_{k+1})L_{k+1}) multiplications in G_{k+1} and O((n − k)I_{k+1}) bit operations.

Proof. Let “multiplications” mean “multiplications in G_{k+1}”.

(a) Let h = h_{1}^{a_{1}} … h_{n}^{a_{n}} be a reduced word in h_{1}, …, h_{n} and u ∈ G_{k+1} be reduced words. If i ≤ k, we have

uh_{i}^{a_{i}} = u(g_{i}u_{i})^{a_{i}} = g_{i}^{a_{i}}u^{g_{i}^{a_{i}}}u_{i}^{g_{i}^{a_{i}−1}}u_{i}^{g_{i}^{a_{i}−2}} … u_{i}^{g_{i}}u_{i},  (∗)

so that by Lemma 3.2, a word v ∈ G_{k+1} such that g_{i}^{a_{i}}v is the normal form of uh_{i}^{a_{i}} can be computed using at most O(nl_{i}L_{k+1}) multiplications in G_{k+1}. Thus, the word h = h_{1}^{a_{1}} … h_{k}^{a_{k}} can be rewritten as a reduced word g_{1}^{a_{1}} … g_{k}^{a_{k}w} with w ∈ G_{k+1}. in g_{1}, …, g_{n} at a cost of O(n(L_{1} − L_{k+1})L_{k+1}) multiplications in G_{k+1}. Substituting reduced words for h_{k+1}, …, h_{n}, the word wh_{k+1}^{a_{k+1}} … h_{n}^{a_{n}} can be written as a reduced word in g_{k+1}, …, g_{n} using L_{k+1} multiplications.

(b) Let g = g_{1}^{a_{1}} … g_{n}^{a_{n}} be a reduced word, and for i ≤ k, write h_{i}^{a_{i}} = g_{i}^{a_{i}}v_{i}, where v_{i} ∈ G_{k+1}, taking u = 1 in (∗). Then

h_{1}^{−a_{1}}g = v_{i}^{−1}g_{2}^{a_{2}} … g_{n}^{a_{n}} = g_{2}^{a_{2}} … g_{k}^{a_{k}}(v_{i}^{−1})^{g_{2}^{a_{2}}...g_{k}^{a_{k}}} g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}}.

Continuing like this, we obtain that

\begin{aligned}h_{k}^{−a_{k}} … h_{1}^{−a_{1}}g & = v_{k}^{−1}(v_{k−1}^{−1})^{g_{k}^{a_{k}}} … (v_{2}^{−1})^{g_{3}^{a_{3}}...g_{k}^{a_{k}}} (v_{1}^{−1})^{g_{2}^{a_{2}}...g_{k}^{a_{k}}} g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}} \\ & = v_{k}^{−1}(v_{k−1}^{−1}(… (v_{2}^{−1}(v_{1}^{−1})^{g_{2}^{a_{2}}})^{g_{3}^{a_{3}}} …)^{g_{k−1}^{a_{k−1}}})^{g_{k}^{a_{k}}} g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}} ∈ G_{k+1}. \end{aligned}

Call the last expression v. Inversion in G_{k+1} requires at most n − k multiplications by Lemma 3.3, while by Lemma 3.2, conjugation by a g_{i}^{a_{i}} requires at most O(l_{i}nL_{k+1}) multiplications. Thus, v can be reduced to normal form in g_{k+1}, …, g_{n} using O(n(L_{1} − L_{k+1})L_{k+1}) multiplications. Since (h_{k+1}, …, h_{n}) is a polycyclic generating system of G_{k+1}, by Proposition 4.2 and Proposition 4.4, this word can be rewritten as a normal word in h_{k+1}, …, h_{n} using O((n − k)L_{k+1}) multiplications and O((n − k)I_{k+1}) bit operations.

(c) Let 1 ≤ i ≤ k, then

h_{i}^{p} = (g_{i}u_{i})^{p} = w_{i,i}u_{i}^{g_{i}^{p−1}}u_{i}^{g_{i}^{p−2}} … u_{i}^{g_{i}}u_{i}.

By Lemma 3.2, a reduced expression for h_{i}^{p} in g_{1}, …, g_{n} can be computed using O(nl_{i}L_{k+1}) multiplications. If 1 ≤ i < j ≤ k, then

h_{j}h_{i} = g_{j}g_{i}u_{j}^{g_{i}}u_{i} = g_{i}w_{i,j}u_{j}^{g_{i}}u_{i},

and by Lemma 3.2, we obtain a reduced expression in g_{1}, …, g_{n} of the right hand side using O(L_{k+1}) multiplications. In both cases, the right hand side can then be rewritten as a reduced word in the h_{i} using O(nL_{1}L_{k+1}) multiplications by (a).

5. A subexponential collection algorithm

Let d denote the derived length of G. The polycyclic presentation 𝒫 of G exhibits the cycle structure of the derived series of G if there exist integers i_{1}, …, i_{d} such that, for k = 1, …, d, G^{(k)} = G_{i_{k}}, and

G^{(k−1)}/G^{(k)} = ⟨ h_{i_{k}}G^{(k)} ⟩ × ⟨ h_{i_{k}+1}G^{(k)} ⟩ × ⋯ × ⟨ h_{i_{k+1}}G^{(k)} ⟩.

Let M_{der}(G) and W_{der} denote the maximum number of bit operations and bits of workspace required to perform a multiplication in G if 𝒫 exhibits the cycle structure of the derived series of G.

5.1 Theorem. Let d and l denote the derived and composition lengths of G, respectively.

(a)

M_{der}(G) ≤ (ClL)^{2d−1} ≤ e^{C′ log l log L},

where C and C′ are suitable constants, and W_{der} ∈ O(dL).

(b) A polycyclic presentation 𝒫′ exhibiting the cycle structure of the derived series of G can be computed using O(l^{4}L^{3}M_{der}(G) + dlL^{6}) bit operations.

(c) Any reduced word with respect to 𝒫 can be rewritten as a reduced word with respect to 𝒫′ using O(LM_{der}(G)) bit operations; the other direction requires O(nLM_{der}(G) + lI) bit operations.

Proof. (a) Let C ∈ ℝ be such that, for all G and 𝒫 exhibiting the cycle structure of the derived series of G, a multiplication in G can be carried out using at most (CL)^{4} multiplications in G′ if G is not abelian, and using at most ClL bit operations if G is abelian. Such a C exists by (b) and (c) of Proposition 3.4. Induction on d then shows that a multiplication requires (ClL)^{2d−1} bit operations. Note that by [6], we have d ∈ O(log l), from which the second part of the inequality follows.

(b) Assume that 1 ≤ k ≤ n such that 𝒫_{k+1} is a polycyclic presentation of G_{k+1} with generators h_{1}, …, h_{r} such that (h_{1}, …, h_{r}) exhibits the cycle structure of the derived series of G_{k+1}, and that, for k < i ≤ n, g_{k} can be expressed as a reduced word in h_{1}, …, h_{r}. Let “multiplication”, “induced generating sequence”, “normal form” all refer to 𝒫_{k+1}, unless specified otherwise.

Using Algorithm 4.1 and Algorithm 4.3, each h_{j} can be rewritten as a word g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}}, using O(lL_{k+1}) multiplications and O(lI_{k+1}) bit operations. Now

h_{j}g_{k} = g_{k} \underbrace{w_{k,k+1}^{a_{k+1}} … w_{k,n}^{a_{n}}}_{v},

where v is a word in g_{k+1}, …, g_{n}. By substituting words in h_{1}, …, h_{r} for g_{k+1}, …, g_{n} in the w_{k,j} and multiplying, the words w_{k,j} can be rewritten as words in h_{1}, …, h_{r}, from which we obtain a reduced expression of v at a cost of O(L_{k+1}^{2}). In a similar way, we obtain a reduced expression of g_{k}^{e_{k}} = w_{k,k}. Putting h_{0} = g_{k}, this yields a polycyclic presentation 𝒫_{k}^{∗} of G_{k} with generators h_{0}, …, h_{r}

Let g ∈ G_{k+1}, then the normal form of g^{g_{k}}, and hence of a commutator [g, g_{k}] = g^{−1}g^{g_{k}} can be computed using O(L_{k+1}) multiplications by Lemma 3.3 and Lemma 3.2. The normal forms of a commutator [g, h] with h ∈ G_{k+1} and g^{e_{i}} require O(l) and O(l_{i}) multiplications, respectively. This shows that an induced generating sequence (t_{1}, …, t_{s}) for G′_{k} can be computed using O(l^{2}L_{k+1}) multiplications and O(l^{2}I_{k+1}) bit operations.

Next, apply Algorithm 4.1 to the sequence (h_{1}, …, h_{r}, t_{1}, …, t_{s}) to obtain f_{1}, …, f_{r}, defined by f_{i} = |⟨ h_{i}, …, h_{r}, t_{1}, …, t_{s} ⟩ : ⟨ h_{i+1}, …, h_{r}, t_{1}, …, t_{s} ⟩|. This requires O(lL_{k+1}) multiplications and O(lI_{k+1}) bit operations. In addition, let f_{0} = e_{k} and put M = 2f_{0} … f_{r}. Then h_{i}^{f_{i}} = h_{0}^{a_{i,0}} ⋯ h_{r}^{a_{i,r}}G′_{k} for i = 0, …, r. Let B = (b_{i,j})_{0≤i,j≤r}, where b_{i,j} = a_{i,j} if i ≠ j, and let b_{i,i} = (a_{i,i} − f_{i}) mod M. Using a standard algorithm for computing the Smith normal form of B modulo M (see, e. g., [11, Section 8.3]), we compute integral matrices P, D, Q with entries in the range { 0, …, M − 1 } such that det(P) ≡ det(Q) ≡ 1 (mod M) and D is a diagonal matrix (but not necessarily with entries dividing each other) with entries d_{1}, …, d_{r}, such that B ≡ P DQ (mod M), at a cost of O(r^{3} log^{3} M + r^{2} log^{4} M) ⊆ O(L_{k}^{6}) bit operations. If Q = (q_{i,j})_{0≤i,j≤r} and x_{i} = h_{0}^{q_{i,0}} ⋯ h_{r}^{q_{i,r}}, then it follows that x_{i}^{d_{i}} ∈ G′_{k} for i = 0, …, r, and, after removing those x_{i} with d_{i} = 1, the sequence (x_{0}, …, x_{r}, t_{1}, …, t_{s}) is a polycyclic generating sequence of G_{k} such that

G_{k}/G′_{k} = ⟨ x_{0}G′_{k} ⟩ × ⋯ × ⟨ x_{r}G′_{k} ⟩.

In a similar way, we can replace t_{1}, …, t_{s} by a polycyclic generating sequence of G′_{k} exhibiting the cycle structure of G′_{k}. This yields a polycyclic generating sequence y_{1}, …, y_{t} of G_{k} exhibiting the cycle structure of G_{k},where each y_{i} is given as a reduced word in h_{0}, …, h_{r}. Now Proposition 3.4 shows that a multiplication with respect to 𝒫_{k}^{∗} of two reduced words in the generators h_{0}, …, h_{r} can be performed at a cost of O(l_{k}lL_{k+1}) multiplications with respect to 𝒫_{k+1}. This allows to compute y_{j}y_{i} and y_{i}^{e} as reduced words in h_{0}, …, h_{r}, where e = |⟨ y_{i}, …, y_{t} ⟩ : ⟨ y_{i+1}, …, y_{t} ⟩|. Using Algorithm 4.1 and Algorithm 4.3, a reduced word in h_{0}, …, h_{r}, can be rewritten in the generators y_{1}, …, y_{t}, at a cost of O(l^{2}l_{k}L_{k}^{2}) multiplications and O(lI) bit operations. In this way, a presentation of G_{k} with generators y_{1}, …, y_{t}, and each g_{i} (which can be written as a word in h_{0}, …, h_{r}) can be written as a word in y_{1}, …, y_{t}. Thus, using O(l^{4}L^{3}) multiplications and O(dL^{6}) bit operations, this allows to replace k by k − 1 in our initial assumption, and we may repeat the above procedure if k > 1. We let 𝒫′ = 𝒫_{1}.

(c) Let h_{1}, …, h_{r} be the generators of 𝒫′. Substituting reduced expressions in h_{1}, …, h_{r} for g_{1}, …, g_{n} and multiplying with respect to 𝒫′ yields a reduced word in h_{1}, …, h_{r}, using O(L) such multiplications. By Algorithm 4.1 and Algorithm 4.3, any reduced expression in h_{1}, …, h_{r} can be rewritten as a reduced expression in g_{1}, …, g_{n} using O(lL) multiplications with respect to 𝒫′ and O(lI) bit operations.

6. Reduction to elementary abelian normal series

A polycyclic generating sequence (h_{1}, …, h_{n}) of G refines a series

H = H_{1} ▷ H_{2} ▷ ⋯ ▷ H_{r} = 1

of the subgroup H of G if there exist j_{1}, …, j_{r} such that H_{i} = ⟨ h_{j_{i}}, …, h_{n} ⟩ for i = 1, …, r.

In this section, we reduce the problem of multiplying with respect to 𝒫 to the case when 𝒫 refines an elementary abelian normal series. This implies that the e_{i} are all primes. We proceed in two steps, first showing that we may assume that the e_{i} are primes. Note that these results can also be deduced from Theorem 5.1, albeit with a significantly worse bound on the cost.

Assume that P, M, P_{comp}, M_{comp}, P_{elab} and M_{elab} are functions such that the maximum number of bit operations required for r multiplications in G is in O(P(G) + rM(G)) for any 𝒫, that it is in O(P_{comp}(G) + rM_{comp}(G)) when the G_{i} form a composition series of G, and in O(P_{elab}(G) + rM_{elab}(G)) when the G_{i} refine an elementary abelian series of G.

6.1 Proposition. Assume that for each e_{i}, the prime factorisation is given. Then a polycyclic presentation 𝒫′ whose associated polycyclic series is a composition series of G and such that the generators of 𝒫′ are powers of those of 𝒫 can be computed using O(nP_{comp}(G) + nL^{2}M_{comp}(G) + n^{2}I) bit operations. Moreover, a reduced word with respect to 𝒫 can be converted into a reduced word with respect to 𝒫′ and vice versa using O(I) bit operations. Thus, we may choose P(G) = nP_{comp}(G)+nL^{2}M_{comp}(G)+n^{2}I and M(G) = I + M_{comp}(G).

Proof. Let 𝒫_{n+1} be the empty presentation, and assume that we have defined a polycyclic presentation 𝒫_{k+1} of G_{k+1} whose associated series is a composition series of G_{k+1}s. such that the generators of 𝒫_{k+1} are powers of g_{k+1}, …, g_{n}. Let e_{k} = p_{k,1} ⋯ p_{k,r} be a prime factorisation of e_{k}. As generators for 𝒫_{k}, we choose

h_{1} = g_{k}, h_{2} = g_{k}^{p_{k,1}}, h_{3} = g_{k}^{p_{k,1}p_{k,2},...,h_{r}} = g_{k}^{p_{k,1}···p_{k,r−1}},

together with the generators h_{r+1}, …, h_{s} of 𝒫_{k+1}. If 0 ≤ a < e_{k}, write

a = a_{1} + p_{k,1}(a_{2} + p_{k,2}(a_{3} + …))

with 0 ≤ a_{i} < p_{k,i} for i = 1, …, r, at a cost of O(rl_{k}^{2}) ⊆ O(l_{k}^{3}) bit operations. Moreover, a can be computed from the a_{i} at the same cost. Therefore, a reduced word in generators h_{r+1}, …, h_{s} can be converted into a reduced word in generators g_{k}, …, g_{n} and back at a cost of O(I_{k}) bit operations.

To obtain the relations of 𝒫_{k}, we take the set of relations of 𝒫_{k+1} and add relations h_{j}h_{i} = h_{i}h_{j}, 1 ≤ i < j < r, h_{i}^{p_{k,i}} = h_{i+1} if i < r, and for 1 ≤ i ≤ r < j ≤ s, we add relations h_{j}h_{i} = h_{i}v_{i,j}, where v_{r,r} and the v_{i,j} are reduced words in h_{r+1}, …, h_{s} obtained as follows. Firstly, v_{r,r} is w_{k,k}, rewritten as a reduced word in h_{r+1}, …, h_{s}, and if r < j ≤ s and h_{j} = g_{m}^{a} with 0 ≤ a < e_{m}, we obtain v_{1,j} by rewriting w_{k,m} as a reduced word in h_{r+1}, …, h_{s} and taking its ath power. If 1 ≤ i < r and v_{i,j} is known for all j, then Lemma 3.2 can be used to compute

v_{i+1,j} = h_{j}^{h_{i}^{p_{k,i}}}

for all j at a cost of O(log p_{k,i}(n − k)L_{k+1}) multiplications with respect to 𝒫_{k+1}. Thus, at a total cost of O(l_{k}(n−k)L_{k+1} such multiplications and O((n−k)I_{k}) bit operations, we obtain 𝒫_{k} from 𝒫_{k+1}. The total cost of computing 𝒫′ = 𝒫_{1} can thus be bounded by O(nL^{2}M_{comp} + n^{2}I) bit operations. Consequently, a multiplication with respect to 𝒫 can be carried out by computing 𝒫′, translating the words into reduced words with respect to 𝒫′, performing the multiplication with respect to 𝒫′, and translating the result back into a reduced word with respect to 𝒫.

Now we can prove the main result of this section. The proof is similar to that of Theorem 5.1 but gives a sharper bound on the cost involved.

6.2 Theorem. Assume that e_{1}, …, e_{n} are primes. Then a polycyclic presentation 𝒫′ for G refining a normal series of G with elementary abelian factors can be computed using O(nP_{elab} + n^{4}LM_{elab}(G) + n^{4}I) bit operations. Converting r reduced words in g_{1}, …, g_{n} into reduced words in the generators of 𝒫′ requires O(P_{elab}(G)+rLM_{elab}(G)) bit operations, and the other direction requires O(P_{elab}(G) + rnLM_{elab}(G) + nI) bit operations. Therefore we may choose P_{comp}(G) = nP_{elab} + n^{4}LM_{elab}(G) + n^{4}I and M_{comp}(G) = nLM_{elab}(G).

Proof. Suppose that 𝒫_{k+1} is a polycyclic presentation of G_{k+1} with generators h_{k+1}, …, h_{n}, and that (h_{k+1}, …, h_{n}) refines a normal series with elementary abelian factors of G_{k+1}. Moreover, assume that we have computed reduced expressions in h_{k+1}, …, h_{n} for g_{k}, …, g_{n}. Let “multiplication”, “polycyclic generating sequence”, “normal form” all refer to 𝒫_{k+1}, unless specified otherwise.

Let g, h ∈ G_{k+1}, then the normal form of a commutator [g, g_{k}] = g^{−1}g^{g_{k}} can be computed using O(L_{k+1}) multiplications by Lemma 3.3 and Lemma 3.2. The same holds for [g, h], g_{k}^{p_{k}} and g^{p_{i}}. Therefore an induced generating sequence (t_{1}, …, t_{r}) for H = G′_{k}G_{k}^{p_{k}} can be computed using O((n−k)^{2}L_{k+1}) multiplications and O((n−k)^{2}I_{k+1}) bit operations.

After deleting those h_{i} with dp(h_{i}) = dp(t_{j}) for some j, the sequence

(g_{k}, h_{k+1}, …, h_{n}, t_{1}, …, t_{r})

is a polycyclic generating sequence of G_{k} refining the series G_{k} ▷ H ⊵ 1. If H ≠ 1, then we obtain a polycyclic generating sequence of G refining the sequence G_{k}▷H▷H′H^{p} ⊵ 1, where p = ro(x_{l}). Continuing like this, at a cost of O((n−k)^{3}(L_{k+1}M_{elab}(G_{k+1})+I_{k+1})), we obtain a polycyclic generating sequence (g_{k}, y_{k+1}, …, y_{n}) refining a normal series of G_{k} with elementary abelian factors.

Now by Lemma 3.2, the normal form of y_{j}^{g_{k}} can be computed using O((n − k)L_{k+1}) multiplications. To obtain the normal form of g_{k}^{p_{k}}, we substitute the normal forms of g_{k+1}, …, g_{n} into w_{k,k} and multiply, at a cost of O(L_{k+1}) multiplications. Normal forms of y_{j}^{y_{i}} and y_{j}^{ro(y_{j})} can be computed in a straightforward way, using O(n − k) and O(log ro(y_{j})) multiplications, respectively. By Proposition 4.4, each of these normal words can be rewritten as a normal word in y_{k+1}, …, y_{n} using

O((n − k)^{3} + (n − k)L_{k+1}) ⊆ O((n − k)^{2}L_{k+1})

multiplications and O((n − k)^{3} + (n − k)I_{k+1}) bit operations. The same holds for the normal forms of g_{k+1}, …, g_{n}. Thus, a polycyclic presentation 𝒫_{k} of G_{k} with generators g_{k}, y_{k+1}, …, y_{n} can be computed using

O((n − k)^{3}(L_{k+1}M_{elab}(G_{k+1}) + I_{k+1}))

bit operations, thus allowing to replace k by k − 1 in our initial assumption, and to repeat the above if k > 0.

The remaining statements follow as in the proof of Theorem 5.1.

6.3 Remark. In a similar way, a polycyclic presentation refining the derived series of G can be computed using only operations in groups having such a polycyclic presentations, the number of such operations being polynomial in L_{1}. If G is nilpotent, then “derived series” may be replaced by “lower central series”, or by “lower p-central series” if G is a p-group. The bounds on the cost remain the same in all cases.

7. Exhibited supplements

While the bounds obtained in Theorem 5.1 may be of some theoretical interest, they are usually far too bad to reflect empirical results. One of the main reasons seems to be that the multiplications in G_{k+1} used for the estimates in Proposition 3.4 and Theorem 5.1 do not actually take place in the whole of G_{k+1}, but in much smaller subgroups of G. This gives rise to the following definition.

Let (h_{1}, …, h_{r}) be a polycyclic generating sequence of G. Assume that H is a subgroup of G and let { i | h_{i} ∈ H } = { i_{1}, …, i_{s} }, where 1 ≤ i_{1} < i_{2} < ⋯ < i_{s} ≤ r. The subgroup H of G is exhibited by (h_{1}, …, h_{r}) if (h_{i_{1}}, …, h_{i_{s}}) is a polycyclic generating sequence of H. It is easy to see that the polycyclic presentation of H with generators (h_{i_{1}}, …, h_{i_{s}}) is the restriction to H of the polycyclic presentation of G with generators h_{1}, …, h_{r}. Obviously, G and the G_{i} are exhibited by (g_{1}, …, g_{n}).

Moreover, if H is an exhibited subgroup of G and 1 ≤ i ≤ r, then the subgroups H∩ < h_{i}, …, h_{r} > is exhibited as well. More generally, it is not difficult to prove that intersections of subgroups exhibited by (h_{1}, …, h_{r}) are exhibited by (h_{1}, …, h_{r}).

The following result indicates the role that exhibited subgroups play in multiplication algorithms.

7.1 Proposition. Assume that H is an exhibited subgroup of G, and that there exists k ≤ n such that G_{k+1} ⊴ G with G = HG_{k+1}. Then a multiplication in G can be carried out using one multiplication in H and O((L_{1}−L_{k+1})(n−k)L_{k+1}) multiplications in G_{k+1}.

Proof. Let g = g_{1}^{a_{1}} … g_{n}^{a_{n}}, h = g_{1}^{b_{1}} … g_{n}^{b_{n}} be reduced words in G and write

g_{1}^{a_{1}} … g_{n}^{a_{n}}g_{1}^{b_{1}} … g_{n}^{b_{n}} = \underbrace{g_{1}^{a_{1}} … g_{k}^{a_{k}}g_{1}^{b_{1}} … g_{k}^{b_{k}}}_{∈H} \underbrace{(g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}})^{g_{1}^{b_{1}}...g_{k}^{b_{k}}} g_{k+1}^{b_{k+1}} … g_{n}^{b_{n}}}_{∈G_{k+1}}

Reducing the word g_{1}^{a_{1}} … g_{i−1}^{a_{i−1}}g_{1}^{b_{1}} … g_{i−1}^{b_{i−1}} in H into normal form g_{1}^{c_{1}} … g_{n}^{c_{n}} requires one multiplication in H.

By Lemma 3.2, the expression

(g_{k+1}^{c_{k+1}} … g_{n}^{c_{n}}) (g_{k+1}^{a_{k+1}} … g_{n}^{a_{n}})^{g_{1}^{b_{1}}...g_{k}^{b_{k}}} (g_{k+1}^{b_{k+1}} … g_{n}^{b_{n}})

can be reduced to its normal form g_{i}^{c′_{i}} ⋯ g_{n}^{c′_{n}} using at most O((L_{1} −L_{k})(n−k +1)L_{k+1}) multiplications in G_{k+1}. Clearly, g_{1}^{c_{1}} … g_{i−1}^{c_{i−1}}g_{i}^{c′_{i}} … g_{n}^{c′_{n}} is a reduced expression for gh.

7.2 Remark. The multiplication algorithm outlined in the proof of Proposition 7.1 is very similar to collection from the left if fast powering and fast conjugation are used. The main difference is that when collection from the left, a carry word g_{i}^{c_{i}} … g_{n}^{c_{n}} occurs whenever a g_{i}^{b_{i}} is moved across a word in G_{k+1}. However, the bound on the cost in Proposition 7.1 remains the same.

In order to exploit Proposition 7.1 to obtain an efficient multiplication algorithm, it is important to choose G_{k+1} in such a way that a multiplication in G_{k+1} is cheap. The following proposition illustrates the idea which we will be using. The N_{i} which we will choose are terms of a chief series, so that H will complement one of the factors.

7.3 Proposition. Let 1 = N_{0} ◁ N_{1} ◁ ⋯ ◁ N_{r} = G be a normal series of G with nilpotent factors. Then there exist a subgroup H of G and k ∈ { 1, …, r } such that N_{k} is nilpotent and G = HN_{k}. Moreover, we also have G = HK for some Sylow subgroup K of N_{r}.

Proof. The statement certainly holds if G = 1. Therefore assume that G ≠ 1 and let k be minimal such that N_{k} ≰ Φ(G). Then there exists a maximal subgroup H of G satisfying HN_{k} = G. Moreover, since N_{k−1} ≤ Φ(G) and N_{k}/N_{k−1} is nilpotent, also N_{k} is nilpotent; see, e. g. [2, A, 9.3 (c)]. Since N_{k} ≰ Φ(G), there exists a Sylow subgroup K of N_{r} such that K ≰ Φ(G). Clearly, K ⊴ G and HK = G.

The following algorithm uses ideas very similar to Algorithm 3.1.

7.4 Algorithm PowerSum. Input: an n × n matrix M over a ring R with multiplicative identity, an integer

k = ∑_{j=0}^{m−1} b_{j}2^{j} with b_{j} ∈ { 0, 1 } Output: S = ∑_{i=0}^{k−1} M^{i}

(1) let S := 1_{n}; T := 1_{n};

(2) for i = 0, …, m − 1 do

(3) let T := (T (M − 1) + 2)T;

(4) if b_{i} = 1, then S := (T (M − 1) + 1)S + T;

7.5 Lemma. Algorithm 7.4 is correct and requires O(m) multiplications and additions of n × n matrices over R, and thus O(n^{3}m) multiplications and additions in R.

Proof. Write S_{r} = ∑_{i=0}^{k−1} M^{i} and observe that M^{r} = (M − 1)S_{r} + 1 and S_{r+s} = M^{r}S_{s} + S_{r} for r, s ∈ ℕ \ { 0 }. This shows that at the beginning of Step (3), T = S_{2^{i}} and S = S_{k_{i}}, where k_{i} = ∑_{j=0}^{i} b_{j}2^{j}.

Now we are ready to prove that complements of elementary abelian factors can be found using mere linear algebra.

7.6 Theorem. Let 0 ≤ k ≤ n be such that G_{k+1} is an elementary abelian normal subgroup of G of exponent p. Then, using

O(k(n − k) log^{3} p + k^{4}(n − k)^{3} log^{2} p + k^{2}(n − k)^{3}(L_{1} − L_{k+1}) log^{2} p)

bit operations, it can be tested whether a complement H to G_{k+1} exists in G, and in this case, elements u_{1}, …, u_{k} ∈ G_{k+1} can be computed such that (g_{1}u_{1}, …, g_{k}u_{k}) is an induced generating sequence of H, and thus H is exhibited by the polycyclic generating sequence

(g_{1}u_{1}, …, g_{k}u_{k}, g_{k+1}, …, g_{n}).

Proof. Following [1, Section 3], G_{k+1} is complemented in G if, and only if, there exist u_{1}, …, u_{k} ∈ G_{k+1} such that h_{1} = g_{1}u_{1}, …, h_{k} = g_{k}u_{k} satisfy a set of defining relations for G/G_{k+1} in the generators G_{k+1}g_{1}, …, G_{k+1}g_{k}. Such a set of defining relations can be easily derived from the polycyclic presentation of G, by replacing g_{i} by G_{k+1}g_{i} throughout.

Now let 1 ≤ i < j ≤ k and write g_{j}g_{i} = g_{1}^{a_{1}} … g_{k}^{a_{k}}u with u ∈ G_{k+1} and reduced right hand side, then

h_{j}h_{i} = g_{j}g_{i}u_{j}^{g_{i}}u_{i} = g_{1}^{a_{1}} … g_{k}^{a_{k}}uu_{j}^{g_{i}}u_{i}.  (∗)

Moreover, putting

u_{i}^{∗} = u_{1}^{g_{1}^{a_{1}−1}} … u_{1}^{g_{1}}u_{1},

we obtain

\begin{aligned}h_{1}^{a_{1}} … h_{k}^{a_{k}} & = (g_{1}u_{1})^{a_{1}}(g_{2}u_{2})^{a_{2}} … (g_{k}u_{k})^{a_{k}} \\ & = g_{1}^{a_{1}}u_{1}^{∗}g_{2}^{a_{2}}u_{2}^{∗} … g_{k}^{a_{k}}u_{k}^{∗} \\ & = g_{1}^{a_{1}}g_{2}^{a_{2}} … g_{k}^{a_{k}}(u_{1}^{∗})^{g_{2}^{a_{2}}...g_{k}^{a_{k}}} (u_{2}^{∗})^{g_{3}^{a_{3}}...g_{k}^{a_{k}}} … (u_{k−1}^{∗})^{g_{k}^{a_{k}}} u_{k}^{∗} \end{aligned}  (∗∗)

Equating (∗) and (∗∗), the u_{j} have to satisfy

uu_{j}^{g_{i}}u_{i} = (u_{1}^{∗})^{g_{2}^{a_{2}}...g_{k}^{a_{k}}} (u_{2}^{∗})^{g_{3}^{a_{3}}...g_{k}^{a_{k}}} … (u_{k−1}^{∗})^{g_{k}^{a_{k}}} u_{k}^{∗}.  (∗∗∗)

With respect to the basis g_{k+1}, …, g_{n} of G_{k+1} (viewed as a 𝔽_{p}-vector space), write u_{j} = (x_{j,k+1}, …, x_{j,n}). If k < l ≤ n, then g_{l}^{g_{i}} = (e_{l,k+1}, …, e_{l,k+1}) with respect to that basis, so that the action of g_{i} on u_{l} can be described by multiplying the vector by the matrix E = (e_{l,m}), which can be read off the presentation of G. Note that u_{l}^{∗} corresponds to

(x_{l,k+1}, …, x_{l,n})(E^{a_{1}−1} + E^{a_{1}−2} + ⋯ + E + 1)

By Lemma 7.5, the matrix E^{a_{1}−1} + E^{a_{1}−2} + ⋯ + E + 1 can be computed using O(log a_{i}(n − k)^{3} log^{2} p) bit operations. Thus, computing matrices corresponding to the action of g_{k}^{a_{k}}, g_{k−1}^{a_{k−1}}g_{k}^{a_{k}}, …, g_{2}^{a_{2}} … g_{k}^{a_{k}} in that order, a linear expression of the coefficients of the right hand side of (∗∗∗) can be obtained using O((L_{1}−L_{k+1})(n−k)^{3} log^{2} p) bit operations. The same is true for the left hand side. Comparing coefficients leads to n − k linear equations in x_{l,m}, 1 ≤ l ≤ k < m ≤ n.

Similarly, if 1 ≤ i ≤ k, write g_{i}^{p_{i}} = g_{1}^{a_{1}} … g_{k}^{a_{k}}u, where the right hand side is reduced with u ∈ G_{k+1}. Then h_{i}^{p_{i}} = g_{i}^{p_{i}}u^{∗∗}u, where u^{∗∗} = u_{i}^{p_{i}−1}u_{i}^{p_{i}−2} … u_{i}. This leads to

u^{∗∗}u = (u_{1}^{∗})^{g_{2}^{a_{2}}...g_{k}^{a_{k}}} (u_{2}^{∗})^{g_{3}^{a_{3}}...g_{k}^{a_{k}}} … (u_{k−1}^{∗})^{g_{k}^{a_{k}}} u_{k}^{∗},

and thus to n − k linear equations, at a cost of O((n − k)^{2}(L_{1} − L_{k+1}) log^{2} p) bit operations.

Thus, at a total cost of O(k^{2}(L_{1} − L_{k+1})(n − k)^{3} log^{2} p) bit operations, we obtain a system of \frac{1}{2}k(k+1)(n−k) equations in k(n−k) variables. Gaussian elimination requires at most O(k(n − k) log^{3} p + k^{4}(n − k)^{3} log^{2} p) bit operations to solve the system, or to deduce that none exists.

7.7 Remark. As in [1, Section 3], the algorithm outlined in the proof of Theorem 7.6 can also be used to compute the set of all complements, or of one representative of each conjugacy class complements of G_{k+1} in G. The cost for computing an induced generating sequence for each additional complement is polynomial in k, n − k and log p; however, trivial examples show that the number of complements or representatives need not.

8. Reduction to the nilpotent case

In order to prove the main result of this section, we will need some technical results.

8.1 Lemma. Assume that G_{k+1} is an elementary abelian normal subgroup of G of exponent p, and that N_{1} < N_{2} < ⋯ < N_{r} ≤ G_{k+1} are subgroups of G given by polycyclic generating sequences.

(a) Using

O((n − k) log^{3} p + k(n − k)^{3} log^{2} p + k^{2}(n − k)^{2} log^{2} p)

bit operations, a polycyclic presentation of G with generators g_{1}, …, g_{k}, h_{k+1}, …, h_{n} can be computed such that G_{k+1} = ⟨ h_{k+1}, …, h_{n} ⟩, U = ⟨ h_{r+1}, …, h_{n} ⟩ and V = ⟨ h_{s+1}, …, h_{n} ⟩.

(b) Converting r reduced words in g_{1}, …, g_{k}, h_{k+1}, …, h_{n} into reduced words in g_{1}, …, g_{n} requires O(r(n − k)^{2} log^{2} p) bit operations; for the opposite direction, O((n − k) log^{3} p + (n − k)^{3} log^{2} p + r(n − k)^{2} log^{2} p) bit operations are required.

Proof. We consider G_{k+1} as a vector space with basis g_{k+1}, …, g_{n} over 𝔽_{p}, so that polycyclic generating sequences of its subgroups correspond to bases of subspaces. Now extend a basis of N_{1} to a basis of N_{2}, then on to N_{3}, and so forth, and finally to one of G_{k+1}, and let h_{k+1}, …, h_{n} be the corresponding polycyclic generating system of G_{k+1}. Computing such a basis requires n − k inverses and (n − k)^{3} multiplications modulo p, and thus O((n − k) log^{3} p + (n − k)^{3} log^{2} p) bit operations.

Now (g_{1}, …, g_{k}, h_{k+1}, …, h_{n}) is a polycyclic generating sequence of G, and any reduced word in g_{1}, …, g_{k}, h_{k+1}, …, h_{n} can be rewritten as a word in g_{1}, …, g_{n} at the cost of a matrix multiplication, requiring O((n − k)^{2} log^{2} p) bit operations. To convert reduced words in g_{1}, …, g_{k}, h_{k+1}, …, h_{n}, the inverse matrix has to be computed, at a cost of O((n − k) log^{3} p + (n − k)^{3} log^{2} p) bit operations. Rewriting each word then requires O((n − k)^{2} log^{2} p) bit operations. This proves (b).

In order to compute a polycyclic presentation of G with generators

g_{1}, …, g_{k}, h_{k+1}, …, h_{n},

proceed as follows. For relations g_{i}^{e_{i}} = w_{i,i} and g_{j}^{g_{i}} = w_{i,j}, rewrite the w_{i,j} as words in g_{1}, …, g_{k}, h_{k+1}, …, h_{n} to obtain a right hand side in the new generators. Right hand sides of relations whose left hand side is of the form h_{j}^{g_{i}} can be found by conjugating the matrix action of g_{i} on g_{k+1}, …, g_{n} by the matrix affording the base change from g_{k+1}, …, g_{n} to h_{k+1}, …, h_{n}. Note that h_{j}^{p} = 1 = h_{j}^{h_{i}} for all i, j with k < i, j ≤ n. Thus, the total cost of computing a polycyclic presentation with generators g_{1}, …, g_{k}, h_{k+1}, …, h_{n} is O((n − k) log^{3} p + k(n − k)^{3} log^{2} p + k^{2}(n − k)^{2} log^{2} p).

Next, we extend Theorem 7.6 to arbitrary elementary abelian factors.

8.2 Proposition. Let 0 ≤ k < m ≤ n be integers such that G_{k+1} and G_{m+1} are normal G such that G_{k+1}/G_{m+1} elementary abelian of prime exponent p. Then there exists an algorithm which, at a cost of

O(((m − k)^{6} + k^{4}(m − k)^{3} + k^{2}(m − k)^{3}(L_{1} − L_{k+1}))(I_{k+1} − I_{m+1}))

bit operation, either computes integers l, r with k ≤ l < r ≤ m, and a polycyclic generating sequence

(g_{1}u_{1}, …, g_{k}u_{k}, u_{k+1}, …, u_{m}, g_{m+1}, …, g_{n})

of G such that

(g_{1}u_{1}, …, g_{k}u_{k}, u_{k+1}, …, u_{l}, u_{r+1}, …, u_{m}, g_{m+1}, …, g_{n})

is a polycyclic generating sequence of a maximal subgroup H of G and U/V is a chief factor of G avoided by H, where U = ⟨ u_{l+1}, …, u_{n} ⟩ and V = ⟨ u_{r+1}, …, u_{n} ⟩, or proves that G_{k+1}/G_{m+1} ≤ Φ(G/G_{m+1}).

Proof. Note that a polycyclic presentation of G/G_{m+1} can be read off 𝒫 (simply by deleting g_{m+1}, …, g_{n} from the set of generators and each relation), and a polycyclic generating sequence of G/G_{m+1} with the above property can be translated into one of G exhibiting H by appending g_{m+1}, …, g_{n}. Thus, we may assume that m = n.

We consider G_{k+1} as an 𝔽_{p}G-module. Repeated application of the Meat-Axe algorithm [7, 8] yields an 𝔽_{p}G-composition series of the 𝔽_{p}G-module G_{k+1}, at an expected cost of

O((m − k)^{7} log^{2} p + (m − k)^{4} log(m − k) log^{3} p + k(m − k)^{4} log^{2} p)
⊆ O((m − k)^{6}(L_{k+1} − L_{m+1}))

bit operations. (See Remark 8.3 below.) This yields a polycyclic generating sequence (u_{k+1}, …, u_{n}) of G_{k+1} refining a G-composition series

1 = N_{0} ◁ N_{1} ◁ ⋯ N_{r} = G_{k+1}

of G_{k+1}. Using Lemma 8.1, at a cost of

O((m − k) log^{3} p + k(m − k)^{3} log^{2} p + k^{2}(m − k)^{2} log^{2} p)

bit operations, we compute a presentation with generators g_{1}, …, g_{k}, x_{k+1}, …, x_{n}.

For i = 1, …, r, we use Theorem 7.6 to test whether N_{i}/N_{i−1} has a complement H/N_{i+1} in G_{k+1}/N_{i−1}, at a total cost of

O(k(m − k)^{2} log^{3} p + k^{4}(m − k)^{4} log^{2} p + k^{2}(m − k)^{4}(L_{1} − L_{k+1}) log^{2} p).

If no such complement exists, then by [2, A, 9.10], we have N_{i}/N_{i−1} ≤ Φ(G/N_{i−1}) for all i. Therefore, by [2, A, 9.2 (e)], G_{k+1} is contained in the Frattini subgroup of G, and the proof is complete.

Therefore, let i be minimal such that N_{i}/N_{i−1} is complemented in G/N_{i+1}, and let l, r be such that N_{i} = ⟨ x_{l+1}, …, x_{n} ⟩ and N_{i+1} = ⟨ x_{r+1}, …, x_{n} ⟩. By Theorem 7.6, there exist reduced words v_{1}, …, v_{k} in the generators x_{k+1}, …, x_{n} such that

(g_{1}v_{1}, …, g_{k}v_{k}, x_{k+1}, …, x_{n})

is a polycyclic generating sequence of G such that

(g_{1}v_{1}, …, g_{k}v_{k}, x_{k+1}, …, x_{l}, x_{r+1}, …, x_{n})

is a polycyclic generating sequence of H.

Finally, v_{1}, …, v_{k} can be rewritten as reduced words u_{1}, …, u_{k} in g_{k+1}, …, g_{n} by substituting reduced expressions of u_{k+1}, …, u_{n}, at a cost of O(k(n − k)^{2} log^{2} p) bit operations. Using (m − k) log^{3} p ∈ O(L_{k+1} − L_{m+1}), we obtain the bound on the cost stated in the proposition.

8.3 Remark. The only probabilistic part of the above algorithm is the use of the Meat-Axe algorithm. Selecting evenly distributed random elements in the relevant matrix algebra seems to require the computation of a basis of that algebra, at a cost of O((m − k)^{6} log^{2} p + (m − k)^{2} log^{3} p) bit operations. The remainder of the algorithm consists of computing the characteristic polynomial f of such a random element A, at a cost of O((m − k)^{3} log^{2} p + (m − k) log^{3} p), factoring that polynomial, at an expected cost of O((m − k)^{3} log(m − k) log^{3} p) [4], finding a nontrivial vector in the nullspace of g(A) using Gaussian elimination, where g is an irreducible factor of f, at a cost of O((m − k) log^{3} p + (m − k)^{4} log^{2} p), and computing submodules generated by a single vector, at the cost of k(m − k)^{3} log^{2} p + (m − k) log^{3} p). This gives an expected running time of

O((m − k)^{6} log^{2} p + (m − k)^{3} log(m − k) log^{3} p + k(m − k)^{3} log^{2} p).

Note that r elements sufficient for practical purposes can be obtained by multiplying and adding a certain number of randomly selected generators, at the cost of O((m − k)^{3} log^{2} p), essentially reducing the above estimate to

O((m − k) log^{3} p + (m − k)^{4} log^{2} p).

In order to apply Proposition 8.2 to an exhibited subgroup, the next lemma will prove useful.

8.4 Lemma. Let 0 ≤ k ≤ m ≤ n be such that G_{k+1} and G_{m+1} are normal subgroups of G, and such that G_{k+1}/G_{m+1} is elementary abelian of exponent p. Assume that H is a subgroup exhibited by (g_{1}, …, g_{n}), and write J = { i | g_{i} ∈ H }. Let h_{1}, …, h_{n} ∈ G be such that h_{i} = g_{i} if i ∉ J or i > m, such that h_{i} = g_{i}x_{i} if i ∈ J and i ≤ k, where x_{i} ∈ H ∩ G_{k+1}, and such that G_{k+1} ∩ H = ⟨ h_{j} | j ∈ J, j > k ⟩. Then (h_{1}, …, h_{n}) is a polycyclic generating sequence of G. More generally, if E ≥ H ∩ G_{k+1} is exhibited by 𝒫 and J = { i | g_{i} ∈ E }, then (h_{i})_{i∈J} is a polycyclic generating sequence of E.

Proof. We first show that (h_{1}, …, h_{n}) is a polycyclic generating sequence of G. Put H_{i} = ⟨ h_{i}, …, h_{n} ⟩. As G_{k+1}/G_{m+1} is a 𝔽_{p}-vector space with basis

{ G_{m+1}g_{j} | k < j ≤ m },

the factor space G_{k+1}/(G_{k+1} ∩ H) has a basis

{ (G_{k+1} ∩ H)g_{i} | k < i ≤ m, i ∉ J } = { (G_{k+1} ∩ H)h_{i} | k < i ≤ m, i ∉ J }.

Moreover,

{ G_{m+1}g_{i} | k < i ≤ m, i ∈ J }

is a basis of (G_{k+1} ∩ H)/G_{m+1}, and since

{ G_{m+1}h_{i} | k < i ≤ m, i ∈ J }

generates (G_{k+1} ∩ H)/G_{m+1}, it follows that it is likewise a basis. As H_{i} = G_{i} if i ≤ k or i > m, this shows that

G = H_{1} ▷ H_{2} ▷ ⋯ ▷ H_{n} ▷ H_{n+1} = 1

is a series with cyclic factors, with |H_{i} : H_{i+1}| = |G_{i} : G_{i+1}| for all i, and (h_{1}, …, h_{n}) is a polycyclic generating sequence.

Since E contains H ∩G_{k+1}, we have g_{i} ∈ E if, and only if, h_{i} ∈ E for all i. Therefore E is also exhibited by (h_{1}, …, h_{n}).

We are now ready to prove the main result of this section: the reduction of a multiplication in a finite soluble group to multiplications in nilpotent subgroups. To formulate the result, let P_{nilp} and M_{nilp} be functions such that r multiplications in an arbitrary nilpotent subgroup N of G given by a polycyclic presentation refining an elementary abelian normal series of N can be carried out using P_{nilp}(G) + rM_{nilp}(G) bit operations.

8.5 Theorem. Assume that 𝒫 refines a normal series with elementary abelian factors. Then there exists a Las Vegas algorithm which, at an expected cost of O(nP_{nilp} + n^{6}L^{4}M_{nilp} + n^{9}I + n^{7}LI) bit operations, computes a polycyclic presentation 𝒫′ of G such that r multiplications with respect to 𝒫′ require at most O(nP_{nilp} + rn^{2}L^{2}M_{nilp}(G)) bit operations. Moreover, r normal words in the generators of 𝒫′ can be written as a normal word with respect to 𝒫 at a cost of O(nP_{nilp} + rnLM_{nilp} + nI) bit operations, and a normal word in the generators of 𝒫 can be written as a normal word with respect to 𝒫′ at a cost of O(nP_{nilp} + rLM_{nilp}) bit operations. Therefore, we may choose P_{elab} = nP_{nilp} + n^{6}L^{4}M_{nilp} + n^{9}I + n^{7}LI and M_{elab} = nLM_{nilp}.

Proof. Denote the terms of an elementary abelian series of G refined by 𝒫 by

1 = L_{0} ◁ L_{1} ◁ ⋯ ◁ L_{t} = G.

We construct polycyclic presentations 𝒫_{0}, 𝒫_{1}, …, 𝒫_{n} as follows. Let 𝒫_{0} = 𝒫, H_{0} = G and N_{0} = 1. Now assume that 𝒫_{i} has generators h_{1}, …, h_{n} exhibiting subgroups H_{i}, N_{1}, …, N_{i} such that for j = 1, …, i, N_{j} is normalised by N_{j+1}, …, N_{i} and H_{i}, all N_{j} are nilpotent, H_{i} ∩ N_{j} is a term of the polycyclic series defined by 𝒫_{i}, and G = H_{i}N_{i}N_{i−1} … N_{1}. Moreover, assume that reduced expressions of g_{1}, …, g_{n} in the generators of 𝒫_{i} are known.

If H_{i} = 1, let 𝒫_{i+1} = 𝒫_{i} and H_{i+1} = N_{i+1} = 1. Otherwise, restrict 𝒫_{i} to H_{i} to obtain a polycyclic presentation \overline{𝒫} _{i} of H_{i} with generators x_{1}, …, x_{m}. This restriction refines the series with terms H_{i} ∩ N_{j}, H_{i} ∩ L_{k}, where 1 ≤ j ≤ i and 1 ≤ k ≤ t. Denote this series by

1 = M_{0} ◁ M_{1} ◁ ⋯ ◁ M_{s} = H_{i}.

Starting with k = 1, use Proposition 8.2 to test whether M_{k}/M_{k−1} ≤ Φ(H_{i}/M_{k−1}). If this is the case, then also M_{k} ≤ Φ(H_{i}), see, e. g. [2, A, 9.2 (e)]. Thus, we may replace k by k − 1 until we obtain a polycyclic generating sequence y_{1}, …, y_{m} of H_{i} likewise refining the series with terms H_{i} ∩ K_{j}, H_{i} ∩ L_{k}, where 1 ≤ j ≤ i and 1 ≤ k ≤ t. Moreover, Proposition 8.2 yields a term N_{i+1} ≤ M_{k} of the polycyclic series defined by (y_{1}, …, y_{m}) and a subgroup H_{i+1} of H_{i} exhibited by (y_{1}, …, y_{m}) such that H_{i+1}M_{k} = H_{i}. The expected total cost is O(n^{8}I + n^{6}LI) bit operations. Since since H_{i} normalises N_{1}, …, N_{i}, the same is true for H_{i+1} and N_{i+1}. By construction, H_{i+1} also normalises N_{i+1}. Let l be such that L_{l−1} ∩ H_{i} ≤ M_{k−1} < M_{k} ≤ L_{l}. As L_{l}/L_{l−1} is (elementary) abelian and M_{k−1} ≤ Φ(H_{i}), it follows from [2, A, 9.3 (c)] that K_{i+1} = L_{l} ∩ H_{i} and N_{i+1} are nilpotent. For j = i, …, 1, let K_{j} = K_{j+1}N_{j} ⊴ H_{j}, and observe that K_{j+1} normalises N_{j}, and that the N_{j} are terms in the polycyclic sequence defined by the restriction of 𝒫_{i} to H_{j}. By Proposition 7.1, a multiplication in K_{j} can be carried out using one multiplication in K_{j+1} and O(nL^{2}) multiplications in N_{j}. Since L_{l} ≤ K_{1}, it follows that a multiplication in L_{l} requires O(nP_{nilp} + n^{2}L^{2}M_{nilp}) bit operations.

We now define a sequence (h′_{1}, …, h′_{n}) of G by replacing the x_{i} among the generators of 𝒫_{i} by the corresponding y_{i}, and by keeping the others. By Lemma 8.4, (h′_{1}, …, h′_{n}) is a polycyclic generating sequence of G.

Using Proposition 4.6, the associated polycyclic presentation 𝒫_{i+1} can be computed at a cost of O(n^{3}L^{2}) multiplications in L_{l} and O(nI) bit operations. We obtain reduced expressions of g_{1}, …, g_{n} in (h′_{1}, …, h′_{n}) at a cost of O(n^{2}L^{2}) multiplications in L_{l} and O(n^{2}I) bit operations. By Proposition 8.2, N_{i+1}/N_{i+1} ∩ H_{i+1} is a chief factor of H_{i}. Therefore if j ≤ i, either N_{j} ∩ H_{i} ≤ N_{i+1} ∩ H_{i+1}, or N_{i+1} ≤ N_{j}. In the first case, the h_{i} ∈ N_{j} are the same as the h′_{i} in N_{j}, and therefore N_{j} is exhibited by (h′_{1}, …, h′_{n}). In the second case, the same result follows from Lemma 8.4. This shows that 𝒫_{i+1} has the required properties.

Finally, by the above argument, a multiplication in 𝒫′ = 𝒫_{n} can be carried out using O(nP_{nilp} + (n^{2}L^{2}M_{nilp}) bit operations, while the computation of 𝒫′ requires

O(nP_{nilp} + n^{9}I + n^{7}LI + n^{6}L^{4}M_{nilp})

bit operations.

Reduction to p-groups and conclusions  25

9. Reduction to p-groups and conclusions

Finally, we show that the problem of computing in a nilpotent group G can be reduced to computing in p-groups, where p ranges over all primes dividing the order of G.

Let 𝒮 be a set of Sylow subgroups of G containing exactly one p-Sylow subgroup for each prime dividing the order of G. We define

P_{p}(G) = ∑_{P ∈𝒮} P_{elab}(P) and M_{p}(G) = ∑_{P ∈𝒮} M_{elab}(P).

9.1 Theorem. Let G be a nilpotent group. Then a polycyclic presentation 𝒫′ of G having the same associated polycyclic series as 𝒫 and exhibiting each Sylow subgroup of G can be computed using

O(nP_{p}(G) + n^{2}I + LI + n^{4}L^{2}M_{p}(G))

bit operations. Moreover, a reduced word in g_{1}, …, g_{n} can be translated into a reduced word with respect to 𝒫′ using O(L) multiplications with respect to 𝒫′, and a reduced word with respect to 𝒫′ can be translated into a reduced word in g_{1}, …, g_{n} using O(nL) multiplications with respect to 𝒫′. Thus, we may choose P_{nilp} = nP_{p}(G) + n^{2}I + LI + n^{4}L^{2}M_{p}(G) and M_{nilp}(G) = nLM_{p}(G).

Proof. Let i ≥ 1 be such that the Sylow subgroups of G_{i+1} are exhibited by (g_{i+1}, …, g_{n}), and let p = p_{i}.

By hypothesis, the order of g_{j} is a power of p_{j} if i < j ≤ n, and elements of G_{i+1} of coprime order commute. Therefore, at a cost of O((n − i)L_{i+1}) bit operations per relation, or a total of O((n − i)^{2}L_{i+1}) bit operations, we may temporarily re-order g_{i+1}, …, , g_{n} such that p_{j} ≠ p if i < j ≤ m and p_{j} = p if m < j ≤ n, for a suitable integer m. Thus, G_{m+1} is a p-Sylow subgroup of G_{i+1}.

Let g = g_{i}, w = w_{i,i}(= g^{p}), j = i + 1.

As in the proof of Theorem 7.6, the relation g^{p} = w suffices to compute an element u ∈ G_{j} such that H/G_{j+1} = ⟨ G_{j+1}, gu ⟩/G_{j+1} is a complement of G_{j}/G_{j+1} in ⟨ g, G_{j} ⟩/G_{j+1}; this requires O(l_{j}^{3} +l_{i}l_{j}^{2}) bit operations. If j < m, we replace j by j +1, g by gu and w by the normal form of u^{g^{p−1}}u^{g^{p−2}} … uw. Note that the latter can be computed at a cost of O(nl_{i}L_{j+1}) multiplications in L_{j+1} by Lemma 3.2. Thus, we arrive at an induced generating sequence g_{1}, …, g_{i−1}, g_{i}v, g_{i+1}, …, g_{n} with v ∈ G_{i+1}, such that (g_{i}v)^{p} ∈ G_{m+1}. Therefore ⟨ G_{m+1}, g_{i}v ⟩ is a Sylow p-subgroup of G_{i}. By Proposition 4.6, a polycyclic presentation with generators g_{1}, …, g_{i−1}, g_{i}v, g_{i+1}, …, g_{n} can be computed using O((n − i)^{3}L_{i+1}^{2}) multiplications in G_{i+1} and O((n − i)I_{i+1}) bit operations.

Since the Sylow q-subgroups of G_{i+1} coincide with those of G_{i} if q ≠ p, we have obtained a polycyclic presentation of G exhibiting all Sylow subgroups of G_{i}, at a cost of O((n + l_{i})I_{i+1}) bit operations and O(n^{3}L_{i+1}^{2}) multiplications L_{i+1}. By hypothesis, each of these can be carried out using ∑_{p||G|} f(|G|_{p})) bit operations, multiplying subwords in Sylow subgroups. Using the fact that there are only n possible values for i, we the first result follows. Note that a reduced word with respect to 𝒫′ can be translated into a reduced word with respect to 𝒫 and back at a cost of O(nL) multiplications and O(L) multiplications with respect to 𝒫′, respectively, by Proposition 4.5.

9.2 Remark. Note that the algorithm outlined in the proof of Theorem 9.1 does not change the polycyclic series associated to 𝒫. Therefore, in the proof of Theorem 8.5, it is possible to replace the restriction of 𝒫_{i} to L_{l} ∩ H_{i} by the polycyclic generating sequence produced by Theorem 9.1, at no further cost. Let π be a set of primes. Then the restriction of 𝒫′ to any N_{i} exhibits the (unique) Hall π-subgroup (N_{i})_{π} of N_{i}. As a consequence, multiplications in the N_{i} reduce to computations in their Sylow subgroups. Moreover, since N_{i} normalises N_{j} if i > j, then also (N_{i})_{π} normalises (N_{j})_{π}, so that (N_{n})_{π}(N_{n−1})_{π} … (N_{1})_{π} is a Hall π-subgroup of G exhibited by 𝒫′. It is now easy to see that these Hall subgroups form a Hall system of G. (For a definition of Hall systems, see, e. g. [2, I, 4.1].)

The results of Sections 6 – 9 can now be summarised as follows.

9.3 Corollary. Let 𝒫 be an arbitrary polycyclic presentation, and assume that the prime factorisation of each e_{i} is known. Then r multiplications with respect to p can be carried out using an expected number of

O(n^{4}P_{p}(G) + l^{9}L^{5}M_{p}(G) + rl^{3}L^{3}M_{p}(G))

bit operations, where l is the composition length of G.

Proof. This follows by substituting the functions for P, M, P_{comp}, M_{comp}, P_{elab}, M_{elab}, P_{nilp}, and M_{nilp} given in Proposition 6.1, Theorem 6.2, Theorem 8.5, and Theorem 9.1 into each other and using the obvious inequalities n ≤ l ≤ L, I ≤ L^{3}.

References

1. Celler, F., Neub^{}üser, J., and Wright, C. R. B.: Some remarks on the computation of complements and normalizers in soluble groups. Acta Appl. Math. 21 (1990), 57–76.

2. Doerk, K. and Hawkes, T.: Finite soluble groups. de Gruyter, Berlin, 1992.

3. The GAP Group: GAP — Groups, Algorithms, and Programming, Version 4.3 .

    St Andrews, Aachen, 2002, http://www-gap.dcs.st-and.ac.uk/~gap.

4. von zur Gathen, J. and Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge, 1999.

5. Gebhardt, V.: Efficient collection in infinite polycyclic groups. To appear in J. Symbolic Comp.

6. Glasby, S. P.: The composition and derived lengths of a soluble group. J. Algebra 120 (1989), 406–413.

7. Holt, D. F. and Rees, S.: Testing modules for irreducibility. J. Austral. Math. Soc. Ser. A 57 (1994), 1–16.

8. Ivanyos, G. and Lux, K.: Treating the exceptional cases of the MeatAxe. Experiment. Math. 9 (2000), 373–381.

9. Leedham-Green, C. R. and Soicher, L.: Collection from the left and other strategies. J. Symbolic Comp. 9 (1990), 665–675.

10. Leedham-Green, C. R. and Soicher, L.: Symbolic collection using Deep Thought. LMS J. Comput. Math. 1 (1998), 9–24.

11. Sims, C. C.: Computation with Finitely Presented Groups,. Cambridge University Press, 1994.

12. Vaughan-Lee, M. R.: Collection from the Left. Journal of Symbolic Comp. 9 (1990), 725–733.