Computation of orders and cycle lengths of
automorphisms of finite solvable groups
arXiv:1707.02368v1 [math.GR] 7 Jul 2017

Alexander Bors∗
July 11, 2017

Abstract
Let G be a finite solvable group, given through a refined consistent polycyclic
presentation, and α an automorphism of G, given through its images of the generators
of G. In this paper, we discuss practical deterministic algorithms for computing the
order of α as well as the cycle length of a given element of G under α. Both algorithms
proceed by recursion over a characteristic series in G with elementary abelian factors
and essentially reduce the respective problem to linear algebra. We give an example
comparing these algorithms to existing methods and also prove that by replacing
certain parts of them by probabilistic counterparts, one can get Las Vegas algorithms
for the two tasks with expected running time subexponential in the input length.

1
1.1

Introduction
Motivation and main results

One of the fundamental ideas in linear algebra, which we will henceforth refer to
as “normalization”, is that in order to deal with an endomorphism ϕ of a finitedimensional vector space V over some field K, given by its representation matrix M
with respect to some basis of V , it is often helpful to first perform a change of basis
to bring the matrix representing ϕ into a nicer form, from which the information on
ϕ in which one is interested can be read off more easily, sometimes even directly.
∗
University of Salzburg, Mathematics Department, Hellbrunner Straße 34, 5020 Salzburg, Austria.
E-mail: alexander.bors@sbg.ac.at
This paper is work for the author’s project J4072-N32 “Affine maps on finite groups”, which is funded
by the Austrian Science Fund (FWF) and will start in the near future; while working on the paper, the
author still enjoyed the support of FWF Project F5504-N26, a part of the Special Research Program
“Quasi-Monte Carlo Methods: Theory and Applications”.
2010 Mathematics Subject Classification: Primary: 20D10, 20D45. Secondary: 12E05, 12E20, 15A21.
Key words and phrases: Finite groups, Polycyclic groups, Computational group theory, Group automorphisms

1

Alexander Bors

Orders and cycle lengths

As an example, we mention the rational canonical form of M , which is particularly
useful for studying the iterated mapping behavior of ϕ (see, for instance, [11] and
[4, Subsection 2.3]). In particular, when K is finite and ϕ is an automorphism of V ,
then the order of ϕ (resp. of the regular matrix M ) can be read off from the rational
canonical form of M modulo factorization of univariate polynomials over K and the
computation of orders (in the sense of [15, Definition 3.2, p. 84]) of univariate monic
irreducible polynomials over K. This yields a practical algorithm for computing
the order of ϕ that is in general much more efficient than the brute-force approach
of iterating ϕ through matrix multiplication until the corresponding representation
matrix becomes the identity matrix.
The aim of this paper is to extend the idea of using normalization for efficient
order computation (and for the similar problem of computing cycle lengths of given
elements under the transformation in question) from vector space automorphisms to
automorphisms α of finite solvable groups G in general. For this, we assume that G
is given through a refined consistent polycyclic presentation (for a detailed account
of the algorithmic theory of polycyclic groups, we refer the reader to [13, Chapter
8]) and α is given through the sequence of α-images of the presentation generators
(which generalizes the matrix representation of vector space automorphisms).
More precisely, in Subsection 1.3, we display two deterministic algorithms in
pseudocode. Algorithm 1 serves to compute the order of an automorphism α of a
finite solvable group G, and Algorithm 2 to compute the cycle length of a given
element g ∈ G under a so-called bijective affine map on G, a permutation on G of
the form x 7→ tα(x), for some fixed t ∈ G and automorphism α of G (note that
with t := 1, this includes all automorphisms of G; we will see in Subsection 2.2 why
it is natural to work with this larger class of transformations on G). The first two
numbered steps in both algorithms are (almost) the same and correspond to our
idea of using “normalization”: replacing the given polycyclic generating sequence
(pcgs) of G by another with respect to which the problem is essentially reduced to
linear algebra. Our first main result, proved in Section 2, is the correctness of these
algorithms:
Theorem 1.1.1. Algorithms 1 and 2 are correct, i.e., they terminate on each input
of the indicated form with the asserted output.

In Section 3, we give examples to illustrate the practicality of both algorithms and
compare them to existing methods and the brute-force iteration approach. For this,
we use an implementation of the algorithms in GAP [9] by the author; the corresponding GAP source code is available from the author’s homepage alexanderbors.wordpress.com/sourcecod
and directly from the author upon request.
The second main result of the paper concerns the complexity of probabilistic
versions of the two algorithms, proved in Section 4:
Theorem 1.1.2. There exist Las Vegas algorithms with expected running time subexponential in the respective input size showing the same output behavior as Algorithms
1 and 2 respectively.
The following two remarks indicate that it is probably very difficult to improve
Theorem 1.1.2:

2

Alexander Bors

Orders and cycle lengths

1. A fundamental obstacle to improving Theorem 1.1.2 by replacing “subexponential” by “polynomial” is the fact that all known algorithms for multiplication
of elements of a finite polycyclic group, written in normal form, have superpolynomial complexity (see [12, Theorem, bottom of p. 2] for the best known
worst-case bounds).
2. Similarly, there are fundamental obstacles to replacing the “Las Vegas” in Theorem 1.1.2 by “deterministic” (and deleting the word “expected”, of course),
as not even for the special case of computing orders of regular matrices M
over finite fields, any deterministic algorithms with subexponential worst-case
complexity are known.

1.2

Notation and terminology

We denote by N the set of natural numbers (including 0) and by N+ the set of
positive integers. The identity function on a set X is denoted by idX . For a prime
power q, the finite field with q elements is denoted by Fq . For a prime element p
of a factorial ring R and x ∈ R, we denote by νp (x) the p-adic valuation of x (the
largest non-negative integer v such that pv divides a, understood to be ∞ if x = 0).
The exponent of a finite group G is denoted by exp(G), and the order of an element
g ∈ G by ord(g); this also applies to automorphisms of G, viewed as elements of the
group Aut(G). For an element t and an automorphism α of a group G, we denote
by At,α the bijective affine map G → G, x 7→ tα(x). At several points, will use the
Kronecker delta δx,y , which is defined to be 1 (i.e., the integer 1 or more generally
the unity element of a ring, depending on the context) if x = y, and 0 otherwise.
For a prime power q, n ∈ N+ and i, j ∈ {1, . . . , n}, we denote by Idn (q) the (n × n)(n)
identity matrix over Fq and by Ei,j (q) the square matrix of dimension n over Fq
whose (k, l)-th entry is δi,k δj,l . Throughout the paper, we will be using much of the
terminology from [5]; in particular, by a pcgs of a finite solvable group G, we always
mean a polycyclic generating sequence refining some composition series of G, i.e.,
such that all relative orders of the pcgs elements are primes (and thus the associated
(consistent) polycyclic presentation of G is reduced). If X is a pcgs of length n of
a polycyclic group G, g ∈ G and k ∈ {1, . . . , n}, then we denote by coeff X (g, k) the
k-th entry in the exponent vector of g with respect to X.
As for our computational model, we use the same assumptions as in [12, Section
2]. We also denote, for a refined consistent polycyclic presentation P representing
a finite solvable group G, by Coll(P ) the maximum max{L(P ), C(P )} of the length
L(P ) of P viewed as an input (which we assume to be at least O(log |G|) and bounded
from above by a polynomial in log |G|) and the minimum number C(P ) ∈ N+ such
that there exists a collection algorithm for P requiring at most C(P ) bit operations
to compute its output (the product of the two input elements in normal form) on
every input. By [12, Theorem, bottom of p. 2], Coll(P ) is at most subexponential in
L(P ).

1.3

Our two algorithms
3

Alexander Bors

Orders and cycle lengths

Algorithm 1: Automorphism order computation
input : A finite solvable group G, given through a refined consistent polycyclic
presentation P = hX | Ri together with the (exponent vectors of the)
images of the elements of X under an automorphism α of G.
output: The order of α, i.e., the least common multiple of the cycle lengths of the
permutation α on G.
1

Compute the following (see [13, Subsection 3.1] and our Subsection 4.1 for details):
• another refined consistent polycylic presentation P + = hY | Si, Y = {y1, . . . , yn },
associated with some other pcgs (g1 , . . . , gn ) of G which refines the elementary
abelian nilpotent-central series of G (also called the LG-series of G, see [5, Section
2, p. 1447]), G = G1 > G2 > · · · > Gr > Gr+1 = {1}.
• the sequence of final weights (see [5, Subsubsection 3.1.1, p. 1450]) of the gi with
respect to the LG-series of G.

2

3
4
5
6
7

8

Compute the representation α+ of α on the formal generators yi (corresponding to
the gi ; identify gi and yi henceforth).
for i = 1, . . . , r do
Set li to be the number of elements of Y with final weight i.
P
Pi
Set pi to be the common relative order of the yj with j = i−1
t=1 lt + 1, . . . ,
t=1 lt .
for i = 1, . . . , r do
(i) i
Set Mi = (aj,k )lj,k=1
to be the (regular) (li × li )-matrix over

Pi−1
(i)
Fpi = Z/pi Z = {0, . . . , pi − 1} such that aj,k = coeff Y (α+ (yPi−1
),
t=1 lt + j).
t=1 lt +k
Set oi to be the order of Mi ∈ GLli (pi ), computed as described in Subsection 2.1.

14

Set o := lcmi=1,...,r oi .
Set β + := (α+ )o .
for i = 1, . . . , r − 1 do
P
if at least one of the numbers coeff Y (β + (yj ), k), for j = 1, . . . , it=1 lt and
P
P
k = it=1 lt + 1, . . . , i+1
t=1 lt , is nonzero then
Replace o by o · pi+1 .
Replace β + by (β + )pi+1 .

15

Return o.

9
10
11
12

13

4

Alexander Bors

Orders and cycle lengths

Algorithm 2: Affine map cycle length computation
input : A finite solvable group G, given through a refined consistent polycyclic
presentation P = hX | Ri together with (the exponent vectors of) elements
g, t ∈ G and of the images of the elements of X under an automorphism α
of G.
output: The cycle length of g under A := At,α .
1 Compute the following (see [13, Subsection 3.1] and our Subsection 4.1 for details):
• another refined consistent polycylic presentation P + = hY | Si, Y = {y1, . . . , yn },
associated with some other pcgs (g1 , . . . , gn ) of G which refines the elementary
abelian nilpotent-central series of G (also called the LG-series of G, see [5, Section
2, p. 1447]), G = G1 > G2 > · · · > Gr > Gr+1 = {1}.
• the sequence of final weights (see [5, Subsubsection 3.1.1, p. 1450]) of the gi with
respect to the LG-series of G.
2

3
4
5
6
7
8

Compute the representation α+ of α on the formal generators yi (corresponding to
the gi ; identify gi and yi henceforth) and the Y -normal forms t+ and g + of t and g
respectively.
for i = 1, . . . , r do
Set li to be the number of elements of Y with final weight i.
Pi
P
Set pi to be the common relative order of the yj with j = i−1
t=1 lt .
t=1 lt + 1, . . . ,
Set L := 1.
for i = 1, . . . , r do
(i) i
over
Set Mi to be the (regular) (li × li )-matrix (aj,k )lj,k=1
(i)

Fpi = Z/pi Z = {0, . . . , pi − 1} such that aj,k = coeff Y (α+ (yPi−1
),
t=1 lt +k
9

10

11
12
13

(i)

Pi−1

t=1 lt

+ j).

i
Set ui to be the li -dimensional vector (xj )lj=1
over Fpi such that
P
(i)
i−1
xj = coeff Y ((g + )−1 · t+ · α+ (g + ), t=1 lt + j).
Set Li to be the cycle length of the zero vector in Flpii under the bijective affine
transformation v 7→ Mi v + ui , computed as described in Subsection 2.1.
Replace L by L · Li .
Replace At+ ,α+ by ALt+i ,α+ (that is, replace t+ and α+ accordingly).

Return L.

5

Alexander Bors

Orders and cycle lengths

2 Details on and correctness proofs for Algorithms 1 and 2
2.1 Details on computing orders and cycle lengths in the
elementary abelian case
In this subsection, we give details on how we intend to perform the computation
of the order of Mi in Step 8 of Algorithm 1 and of the cycle length Li in Step
10 of Algorithm 2. This serves two purposes: Firstly, to remove ambiguity from
the pseudocode formulation, and secondly, to prepare for the complexity analysis in
Section 4.
In general, for computing the order of a regular matrix M over a finite prime field
Fp , proceed as follows:
1. Determine the invariant factors P1 , . . . , Ps ∈ Fp [X] of M by bringing M into
rational canonical form using, e.g., the basic algorithm described in [8, Section
12.2, pp. 481f.] or a more efficient version such as the one from [19, Chapter 9].
We note that for our theoretical complexity analysis for both Algorithms 1 and
2, it is sufficient if we use an algorithm that computes in O(nc ) bit operations
(where c > 0 is fixed and n is the dimension of M ) a basis change matrix T
such that T −1 M T is in rational canonical form, and this is true even for the
basic algorithm from [8, Section 12.2]. In the GAP implementations of our two
algorithms, we use an implementation of said algorithm by Hulpke.
Q i
m
2. Factorize the invariant factors in Fp [X], writing Pi = nj=1
Qi,ji,j , with the
Qi,j ∈ Fp [X] irreducible. For the sake of unambiguousness and to make the algorithms deterministic, say we use Berlekamp’s algorithm from [2] for this; for the
later theoretical complexity analysis, we will instead assume that Berlekamp’s
Las Vegas factorization algorithm with expected running time polynomial in
the input size (see [3] and [20, Section 3]) is used.
3. Use the obtained factorizations to compute the orders Oi of the monic polynomials Pi , following the approach given by [15, Theorems 3.8 and 3.9 and p. 87,
below Theorem 3.11]; note that this requires us to factor the integers pdi,j − 1,
where di,j denotes the degree of Qi,j ; in the complexity analysis, we will assume that the general number field sieve (see [17]), which has subexponential
expected running time, is used for this.
4. By [15, pp. 525f.], the Oi are also the orders of the companion matrices of the
Pi , i.e., of the diagonal blocks of the rational canonical form of M . Hence we
can compute the order of M as the least common multiple of the Oi .
It remains to discuss how to compute, for a given prime p, dimension d, regular
(d × d)-matrix M over Fp and vector t ∈ Fdp , the cycle length of the zero vector of
V = Fdp under the bijective affine transformation At,M : V → V, v 7→ M v + t:
1. Use any of the available polynomial-time algorithms to compute a basis change
matrix T such that T −1 M T is in rational canonical form.

6

Alexander Bors

Orders and cycle lengths

2. The cycle length of the zero vector under At,M then is the same as its cycle length under AT −1 t,T −1 M T , which in turn is the least common multiple of
the cycle lengths of the zero vector in the subspaces of V corresponding to
the companion matrix blocks of T −1 M T under the respective restrictions of
AT −1 t,T −1 M T . It therefore suffices to consider the case where M is the companion matrix of a monic polynomial P ∈ Fp [X].
3. In that case, the action of M on Fdp is isomorphic to the one of the multiplication by X modulo P on the quotient algebra Fp [X]/(P ), with an isomorphism
P
l
given by the map πP : (a1 , . . . , ad ) 7→ d−1
l=0 al+1 X + (P ). Hence we will actually compute the cycle length of the zero element (P ) ∈ Fp [X]/(P ) under the
bijective affine map F + (X) 7→ πP (t) + XF + (P ) on Fp [X]/(P ).
Q
m
4. To this end, factor P in Fp [X], yielding P = nj=1 Qj j with Qj ∈ Fp [X] irreP
m
l
ducible. Set Rj := Qj j and, writing t = (t1 , . . . , td ), set S := d−1
l=0 tl+1 X ∈
Fp [X]. Then by the Chinese Remainder Theorem, the cycle length of the zero
vector under A is the least common multiple of the cycle lengths of the zero vectors in the quotients Fp [X]/(Rj ) under F 7→ S + XF + (Rj ), for j = 1, . . . , n. It
therefore suffices to consider the case where P = Qm is a power of an irreducible
polynomial Q ∈ Fp [X].
5. In that case, if S = 0, then the cycle length clearly is 1, so assume that S 6= 0.
Consider the affine map A : F 7→ X · F + S on Fp [X]. By induction on n ∈ N, it
is easy to show that An (0) = S · (1 + X + · · · + X n−1 ), so the cycle length on the
quotient algebra Fp [X]/(Qm ) in which we are interested is the smallest n ∈ N+
such that S(1 + X + · · · + X n−1 ) ≡ 0 (mod Qm ), which by multiplying both
congruence sides by X − 1 is equivalent to S · (X n − 1) ≡ 0 (mod Qm+δQ,X−1 ).
Set v := νQ (S), and note that 0 ≤ v < m. The last congruence is equivalent to
X n − 1 ≡ 0 (mod Qm−v+δQ,X−1 ), and the smallest such n ∈ N+ is by definition
just the order of the polynomial Qm−v+δQ,X−1 , which we compute following [15]
as mentioned before.

2.2

Automorphisms restricted to cosets

The following result, which is essentially [4, Lemma 2.1.3(1)], will be used in the
correctness proofs for both algorithms:
Lemma 2.2.1. Let G be a finite group, t ∈ G, α an automorphism of G, H an
α-invariant subgroup of G, and set A := At,α . Then if xH is a left coset of H
in G such that A[xH] = xH, say A(x) = xh0 with h0 ∈ H, then for all h ∈ H,
A(xh) = xh0 α(h) = x Ah0 ,α|H (h). In particular, the cycle length of x under A then
equals the cycle length of 1G = 1H under the bijective affine map Ah0 ,α|H .
In other words, in the setting of Lemma 2.2.1, the action of A on the coset xH is
isomorphic to the action of Ah0 ,α|H on H. As noted in [4, Remark 2.1.4(1)] already,
even if t = 1, i.e., if A = α is an automorphism of G, we do not necessarily have
h0 = 1, so the affine map on H describing the action of α on xH is in general still

7

Alexander Bors

Orders and cycle lengths

only an affine map, which is why it is more natural to work with affine maps in
situations where Lemma 2.2.1 is used.
We also note the following consequence of Lemma 2.2.1 (see also [14, proof of
Theorem 2]), which will be used in the correctness proof of Algorithm 1:
Lemma 2.2.2. Let G be a finite group, α an automorphism of G, p a prime, N
an α-invariant normal subgroup of G with exp(N ) = p. Assume that the restriction
α|N and the automorphism α̃ of G/N induced by α are the identity on N and G/N
respectively. Then either α = idG or α is of order p.
Proof. By the assumption that α̃ = idG/N , α restricts to a permutation on each
coset xN of N in G, and by the assumption that α|N = idN and Lemma 2.2.1, this
permutation on xN is isomorphic to the left translation by a fixed element on N .
Hence as N has exponent p, each such restriction of α is either trivial or has order
p, and so α as a whole is either trivial or has order p.

2.3

Correctness of Algorithm 1

As in the description of Algorithm 1, let G = G1 > G2 > · · · > Gr > Gr+1 = {1}
denote the elementary abelian nilpotent-central series of G, and for i = 1, . . . , r,
denote by Vi := Gi /Gi+1 the i-th factor in the series, a finite elementary abelian
group. Then li , defined in Step 4, is the length of the pcgs of Vi induced by Y , so li
is the dimension of the vector space Vi , and pi , defined in Step 5, is the exponent of
Vi (i.e., the characteristic/cardinality of the associated finite prime field).
We note that ord(α) = ord(α+ ), and so we argue that the algorithm outputs
ord(α+ ). The matrix Mi , defined in Step 7, represents the automorphism α+
i of Vi
P
P
. As
)
with
respect
to
the
F
-basis
y
,
.
.
.
,
y
induced by α+ (i.e., by α+
i−1
i
pi
|Gi
t=1 lt
t=1 lt +1
each of the functions Aut(G) → Aut(Vi ), γ 7→ γi , is a group homomorphism, each oi
(defined in Step 8) divides ord(α+ ), so o (defined in Step 9) also divides ord(α+ ),
whence ord(α+ ) = o · ord((α+ )o ) = o · ord(β + ).
The last for-loop (ranging from Steps 11–14) serves to compute ord(β + ) (with
+
β as defined in Step 10) step by step, updating the values of the variables o and
β + along the way so that at the end of the loop, the value of o will be ord(α+ ). At
the beginning of the i-th step of the loop, (the value of) o is a divisor of ord(α+ )
such that the automorphism of G/Gi+1 induced by (α+ )o and the automorphism of
o
+
+ o
Gi+1 /Gi+2 induced by (α+
|Gi+1 ) are both trivial, and the value of β is (α ) . Then
precisely one of the following two cases occurs:
• β + is also trivial modulo Gi+2 , so that neither of the two variables needs to be
updated for the next loop step.
• β + is nontrivial modulo Gi+2 . In that case, by Lemma 2.2.2, applied to the
group G/Gi+2 , the order of the automorphism of G/Gi+2 induced by β + is
equal to exp(Gi+1 /Gi+2 ) = exp(Vi+1 ) = pi+1 , so that for the next loop step, o
must be replaced by o · pi+1 and β + by (β + )pi+1 .
The if clause in Step 12 tests whether the second case occurs and if so, updates
o and β + as described above. Note that by assumption, each of the generators

8

Alexander Bors

Orders and cycle lengths

, . . . , yPi+1 lt is certainly fixed modulo Gi+2 by β + , which explains the range
t=1
P
for j in the if clause, and that for k = 1, . . . , it=1 lt , coeff Y (β + (yj ), k) equals δk,j
P
by assumption, whereas the coefficient values for k > i+1
t=1 lt do not matter for the
+
question whether β is trivial modulo Gi+2 , which explains the range for k.
yPi

t=1 lt +1

2.4

Correctness of Algorithm 2

We use the notation from the first paragraph of the correctness proof for Algorithm
1 and note that the statements on li and pi from there apply here as well.
The cycle length of g under At,α is the same as that of g+ under A := At+ ,α+
(with t+ and α+ as defined in Step 2), so we compute the latter.
At the beginning of the i-th step of the last for-loop (Steps 7–12), L is a divisor
of the cycle length of g+ under A such that g+ is a fixed point of AL modulo Gi (i.e.,
AL (g+ ) = g + · gi with gi ∈ Gi ) and t+ , α+ are such that AL = At+ ,α+ . At the end of
the loop step, we want the analogous situation with i replaced by i + 1, that is, we
want to find the smallest Li ∈ N+ such that AL·Li (g+ ) = g + · gi+1 with gi+1 ∈ Gi+1 .
To this end, we use Lemma 2.2.1 to translate the action of AL = At+ ,α+ on g+ Gi
into the action of Bi := Agi ,α+ on Gi . Note that since the isomorphism transforming
|Gi

the two actions into each other is just a left translation by a fixed element in both
directions (namely by g+ resp. (g+ )−1 ), our problem is equivalent to finding the
smallest Li ∈ N+ such that the cycle of 1 ∈ Gi under Bi is trivial modulo Gi+1 , so
we study the induced action of Bi on Vi = Gi /Gi+1 .
As in Algorithm 1, the matrix Mi from Step 8 represents the induced action of
α+ on Vi , and since gi = (g + )−1 · At+ ,α+ (g+ ) by definition, the vector ui from Step
9 is the projection of t+ to Vi , so the Li which we want to compute is just the cycle
length of 0 ∈ Flpi under v 7→ Mi v + ui , whence Step 10.
So at the end of the last loop step (and thus in Step 13), L divides the cycle length
of g+ under A while at the same time, g + is a fixed point of A modulo Gr+1 = {1},
hence a fixed point full stop. Therefore, L is equal to the cycle length which we want
to find.

3

Exemplary comparison to existing methods

All computations referred to in this section were carried out with GAP [9] on the
author’s notebook, which uses an Intel Core i7-6700HQ processor and has 16GB of
RAM.
We consider a certain refined consistent polycyclic presentation of the following group G of order 1941 : G = (Z/19Z)16 ⋊ϕ (Z/19Z)25 , where ϕ : (Z/19Z)25 →
Aut((Z/19Z)16 ) = GL16 (19) sends the i-th standard generator of (Z/19Z)25 to the
(16)
matrix Id16 (19) + E3+⌈i/5⌉,11+f (i,5)(19) , where f (i, 5) denotes the residue class representative of i modulo 5 from the set {1, . . . , 5}. In particular, the conjugation action
ϕ of the complement (Z/19Z)25 on the normal subgroup (Z/19Z)16 is faithful and
unipotent. In the rest of this section, by “the normal subgroup”, we mean the normal subgroup (Z/19Z)16 of G, and by “the complement”, we mean the semidirect

9

Alexander Bors

Orders and cycle lengths

complement (Z/19Z)25 to the normal subgroup in G as exhibited by the definition
of G.
The concatenation of the sequences of standard generators of the complement
and the normal subgroup (in this order) is a pcgs of G, and we denote the pc group
in GAP represented by the polycyclic presentation associated with this pcgs by G1 .
We also consider a certain automorphism α of G, defined as follows: Consider
the primitive polynomials P1 = X 3 + X + 4, P2 = X 5 + X + 9 ∈ F19 [X], read off
from [10, Supplement]. Denote the companion matrix of Pi by Mi , for i = 1, 2. The
block diagonal matrix M ∈ GL16 (19) whose four diagonal blocks are, in this order,
M1 , M2 , M1 , M2 is readily checked to normalize the image of ϕ, and so M , viewed
as an element of the holomorph H of the normal subgroup, normalizes G ≤ H. We
define α as the automorphism of G induced by conjugation by M . Note that α has
order lcm(193 − 1, 195 − 1) = 943393338. The representation of α on the generators
of G1 will be denoted by α1 .
The pc group G1 and automorphism α1 are very “benign”: The group presentation exhibits the above semidirect product decomposition, and for iterating α1 ,
one can just iterate the restrictions of α1 to the first 25 and the last 16 generators
separately. Hence an iteration of α1 essentially just consists of two separate matrix
multiplications over F19 . We want a more “malicious” refined consistent polycyclic
presentation of G to illustrate that in contrast to our algorithms, the running time of
the standard (i.e., already implemented in GAP) algorithms for automorphism order
and cycle length computation depends heavily on the choice of refined consistent
polycyclic presentation for the group in question.
For making the presentation more complicated, the author proceeded in two steps.
First, he chose transformation matrices T1 ∈ GL16 (19) and T2 ∈ GL25 (19) at random
and stored the drawn samples. We do not give the stored matrices here, but they
can be read off from lines 165–184 and 188–291 of the corresponding source code copy
available from the author’s homepage, alexanderbors.wordpress.com/sourcecode/pcautordexample.
The first 25 and last 16 generators of G, forming F19 -bases of the complement and
the normal subgroup respectively, were then replaced by their images under T2 and
T1 respectively, yielding another pcgs of G with associated pc group G2 and αrepresentation α2 . Note that in G2 , both the conjugation actions of the complement
generators on the normal subgroup and the representation of α2 are more complicated (i.e., not given by upper triangular matrices resp. by a diagonal block matrix
with companion matrices as blocks), but α2 still leaves both the normal subgroup
and the complement invariant.
For the second step, the author chose a vector v ∈ F16
19 not fixed by the image of ϕ
(i.e., such that the last 5 entries of the vector are not all zero) at random; the stored
transformed vector T1−1 v can be read off from source code lines 468–472. The second
modification step then consisted of replacing the complement C generator-wise by its
conjugate xCx−1 , where x is the element of the normal subgroup represented with
respect to the original (resp. the new) generators by the coordinate vector v (resp. by
T1−1 v). Note that this new complement is not α-invariant anymore. The pc group
associated with this new pcgs is denoted by G3 , and the corresponding representation
of α by α3 .

10

Alexander Bors

Orders and cycle lengths

Finally, the author chose an element g ∈ G at random and determined the corresponding representations of g as an element of Gi , i = 1, 2, 3, see source code lines
559–587. This is to test the algorithms for cycle length computation, and we note that
given the order of α, g has the maximum possible cycle length ord(α) = 943393338
under α.
In Table 1 below, we summarize the (sometimes estimated) running times of different algorithms for computing the order of αi and the cycle length of gi under αi ,
which were read off by evaluating GAP’s global variable time after an algorithm call
(and restarting GAP for each computation to avoid a bias in measurements due to
GAP’s feature of accessing results from its cache to speed some computations up). In
the table, Alg1,1 denotes GAP’s built-in algorithm for computing the order of an automorphism, called via Order, Alg1,2 is our Algorithm 1 from this paper, and Alg1,3
is the algorithm which simply iterates the automorphism until the iterate becomes
trivial. Similarly, Alg2,1 is GAP’s built-in procedure for computing orbit lengths under group actions, called via OrbitLength (note that this requires to form an internal
representation of the cyclic group generated by the automorphism in question), Alg2,2
is our Algorithm 2, and Alg2,3 is the algorithm iterating the automorphism on the
group element until the cycle length is detected. We programmed Alg1,3 and Alg2,3 so
that they print an iteration counter at the beginning of each loop iteration, allowing
us to read off the number of iterations in the first minute after start, which we used
to calculate an estimate for the total running time (assuming that a year consists of
365.25 days). Furthermore, we decided to stop the computations for Alg1,1 (α3 ) after
they had gone on for 12 hours, and all three computations by Alg2,1 eventually ran
out of memory (we suppose this is because it tries to compute the actual orbit/cycle
of size 943393338), so we cannot give any running time for those.

Function call
Alg1,1 (α1 )
Alg1,2 (α1 )
Alg1,3 (α1 )
Alg1,1 (α2 )
Alg1,2 (α2 )
Alg1,3 (α2 )
Alg1,1 (α3 )
Alg1,2 (α3 )
Alg1,3 (α3 )

Running time
2.469 sec
0.219 sec
∼ 46.6 days
30.688 sec
0.750 sec
∼ 107.2 days
> 12 hours
0.750 sec
∼ 179.4 years

Function call
Alg2,1 (α1 , g1 )
Alg2,2 (α1 , g1 )
Alg2,3 (α1 , g1 )
Alg2,1 (α2 , g2 )
Alg2,2 (α2 , g2 )
Alg2,3 (α2 , g2 )
Alg2,1 (α3 , g3 )
Alg2,2 (α3 , g3 )
Alg2,3 (α3 , g3 )

Running time
RAM too small
3.562 sec
∼ 7.5 hours
RAM too small
16.188 sec
∼ 2.5 days
RAM too small
16.250 sec
∼ 4.2 years

Table 1: Running times overview.

11

Alexander Bors

4

Orders and cycle lengths

Theoretical complexity considerations

4.1

Complexity analysis for the “normalization”

The most demanding part in the complexity analysis of both our algorithms lies in
Steps 1 and 2, the passage to a “nicer” presentation of G. An algorithm for computing
a pcgs refining the LG-series is described in [5, Subsection 3.1]. We will show that
following that approach with some modifications yields:
Theorem 4.1.1. There exists a polynomial Q(X) ∈ N[X] and algorithms carrying
out the computations from Steps 1 and 2 in the pseudocode of Algorithms 1 and 2 in
at most Q(Coll(P )) bit operations.
As Coll(P ) is subexponential in the length of the presentation P by [12, Theorem,
bottom of p. 2], this shows in particular that the complexity of Steps 1 and 2 in the
two algorithms is subexponential in the input length.
For the proof of Theorem 4.1.1, we require several lemmata concerning the theoretical complexity of basic problems, such as computing powers of elements and
automorphisms of finite polycyclic groups. To the author’s knowledge, none of these
complexity analyses has been published before, so we give them here.
Lemma 4.1.2. There are polynomials Q1 (x, y), Q3 (x, y) ∈ N[x, y], Q2 (x) ∈ N[x]
such that the following hold for every refined consistent polycyclic presentation P =
hx1 , . . . , xn | Ri representing the group G:
1. For every g ∈ G and all e ∈ Z, (the exponent vector of ) ge can be computed
from (the one of ) g in Q1 (Coll(P ), log |e|) many bit operations.
2. For all automorphisms α1 , α2 ∈ Aut(G) (given on the generators from P ), the
composition α1 ◦ α2 can be computed in Q2 (Coll(P )) many bit operations.
3. For every α ∈ Aut(G) and all e ∈ N, the iterate αe can be computed in
Q3 (Coll(P ), log e) many bit operations.
Proof. For (1): If e ≥ 0, use a square-and-multiply approach. First, compute and
⌊log e⌋
store g, g2 , g4 , . . . , g 2 2 ; in each iteration step, the collection algorithm is called
once for squaring and one moves a marker along the given binary digit expansion
of e one step further so that one knows when to stop the iterated squaring. This
requires O(log e · Coll(P )) many bit operations. Afterward, read the digits of e one
after the other and multiply the corresponding powers of g computed before, which
also requires O(log e · Coll(P )) many bit operations.
ei
e
If e < 0, then first compute g −1 . Note that if g = xi11 · · · ximim with 1 ≤ i1 < i2 <
p

−e

pi −ei

· · · < im ≤ n and all eij > 0, then g −1 = ximim im · · · xi1 1 1 , where pij denotes the
relative order of xij , and each of the m factors/powers in this product can be viewed
as the normal form of a group element. Hence we can compute g−1 by n−1 ≤ Coll(P )
calls of the collection algorithm for P after computing the n ≤ Coll(P ) differences
pij − eij of numbers with binary digit expansion length at most Coll(P ); altogether,
this takes O(Coll(P )2 ) bit operations. After this, just raise g−1 to the (−e)-th power
as in the previous paragraph, requiring O(log |e| · Coll(P )) bit operations.

12

Alexander Bors

Orders and cycle lengths
e

(i)

(i)

For (2): By assumption, we can read off α2 (xi ) = x11 · · · xenn in normal form
(i)

(i)

directly from the input, for i = 1, . . . , n. Then (α1 ◦α2 )(xi ) = α1 (x1 )e1 · · · α1 (xn )en ,
(i)
which can be computed in n·Q1 (Coll(P ), maxj log ej ) ≤ Coll(P )·Q1 (Coll(P ), Coll(P ))
bit operations, so overall, we need at most Coll(P )2 · Q1 (Coll(P ), Coll(P )) bit operations for computing α1 ◦ α2 on the generators x1 , . . . , xn .
For (3): Similar to (1), using (2) for each squaring step and for the subsequent
f
composition of suitable powers of the form α2 ; with this strategy, one can compute
αe in O(log e · Q2 (Coll(P ))) bit operations.
The next lemma discusses the complexity of transforming the polycyclic presentation and automorphism/group elements under an “elementary transformation step”
of the associated pcgs; Steps 1 and 2 in Algorithms 1 and 2 essentially consist of a
sequence of applications such elementary steps, similarly to [5, Subsection 3.1].
Lemma 4.1.3. There are polynomials Q4 (x), Q5 (x), Q6 (x) ∈ N[x] such that the following holds for every refined consistent polycyclic presentation P = hX | Ri representing the finite group G, with X = (x1 , . . . , xn ), and every g ∈ G \ {1}, say of depth
d:
1. For every h ∈ G, the exponent vector of h with respect to Xg can be computed
in Q4 (Coll(P )) bit operations.
2. The refined consistent polycyclic presentation associated with the pcgs Xg :=
(y1 , . . . , yn ) with yi = xi if i 6= d and yd = g can be computed in Q5 (Coll(P ))
bit operations.
3. For every α ∈ Aut(G), the representation of α on the elements of Xg (with
the images written in Xg -normal form) can be computed in Q6 (Coll(P )) bit
operations.
Proof. For (1): Write g = xedd · k with depth(k) > depth(g) and ed ∈ {1, . . . , pd − 1},
where pd is the relative order of xd . First, compute, using the extended Euclidean
algorithm, the unique l ∈ {1, . . . , pd − 1} such that l · ed ≡ 1 (mod pd ); this can
be done in a number of bit operations that is polynomial in log pd ≤ Coll(P ). Denote by U the subgroup of G generated by xd+1 , . . . , xn , which is normalized by
g. Compute the X-normal forms of the powers g pd =: u, gl and g−l (requiring
O(Q1 (Coll(P ), Coll(P )) bit operations), the automorphism γ of U induced by conjugation by gl (using O(Coll(P )2 ) bit operations) and the powers γ 2 , γ 3 , . . . , γ pd −1
(requiring O(Coll(P ) · Q3 (Coll(P ), Coll(P ))) bit operations). Compute then the Xnormal form of td := g −l xd (using O(Q1 (Coll(P ), Coll(P ))+Coll(P )) bit operations),
which involves only powers of the xj for j > d, so that we can directly read off the
Xg -normal form of xd from the equality xd = gl td . To bring h = xf11 · · · xfnn into Xg normal form, note that by substituting the now known Xg -normal form expression
of each xj into this expression, we get
f

f

d+1
h = y1f1 · · · yd1d−1 (ydl t′d )fd yd+1
· · · ynfn

13

Alexander Bors

Orders and cycle lengths
f

(l·fd ) mod pd

d−1
yd
= y1f1 · · · yd−1

f

d+1
· · · ynfn ,
(u′ )⌊l·fd /pd ⌋ γ fd (t′d ) · · · γ(t′d )t′d yd+1

where u′ resp. t′d is obtained from u resp. td by replacing each occurrence of xj
(with j > d necessarily) by yj . Since yj = xj for j > d, we can bring the segment
(l·f ) (mod pd )
to the right of yd d
in the last expression above into Xg -normal form in
O(Coll(P ) · (Q1 (Coll(P ), Coll(P )) + Coll(P ))) bit operations by successive calls of
the exponentiation and collection algorithm for P , thus arriving at the Xg -normal
form of h.
For (2) and (3): These are clear from (1).
Next, we consider the complexity of computing an induced pcgs of a subgroup H
given a generating subset of H. We follow the approach in [13, Subsection 8.3.1].
Lemma 4.1.4. There is a polynomial Q7 (x, y) ∈ N[x, y] such that for any finite
solvable group G, given through a refined consistent polycyclic presentation P = hX |
Ri, and any subgroup U ≤ G, given through a generating subset {u1 , . . . , ut }, one
can compute an X-induced pcgs for H in Q7 (Coll(P ), t) bit operations.
Proof. Consider the algorithm InducedPolycyclicSequence from [13, p. 294],
which uses the algorithm Sift from loc.cit. as a subroutine. For Sift, it is immediate
to check that a single call of it always only uses O(Coll(P ) · (Q1 (Coll(P ), Coll(P )) +
Coll(P ))) bit operations. Likewise, it is easy to check that a single iteration of
the unique while-loop in InducedPolycyclicSequence only uses a number of
bit operations that is polynomial in Coll(P ). But the total number of iterations is
also bounded by a polynomial expression in Coll(P ) and t, since whenever the ifclause in line 7 is satisfied (which causes G to be n elements larger at the end of the
iteration step than at the beginning of the step), an entry 1 in Z is replaced by a
nontrivial element of G, which can happen at most n times, whence the total number
of iterations of the loop is O(t + Coll(P )2 ).
Consider now the following modified version of the algorithm ModifyPcgs from
[5, p. 1451]:

14

Alexander Bors

Orders and cycle lengths

Algorithm 3: ModifyByElement
input : A finite solvable group G, given through a refined consistent polycyclic
presentation hx1 , . . . , xn | Ri, together with a sequence (w1 , . . . , wn ) of
numbers that are admissible weights for the xi with respect to some fixed
normal series G = N1 ⊲ · · · ⊲ Nl ⊲ Nl+1 = {1} of G; an element
g ∈ G \ {1}, say of depth d, an admissible weigth u for g, an automorphism
α of G and a tuple (h1 , . . . , hr ) of elements of G.
output: A refined consistent polycyclic presentation hy1, . . . , yn | Si associated with
some pcgs (y1 , . . . , yn ) of G and a modified weight sequence (w1′ , . . . , wn′ )
such that wi′ is still an admissible weight for yi , and such that g and each
xi can be written as words in the yi for those i where wi′ ≥ u or wi′ ≥ wi
respectively; moreover, the output contains the representation of α and the
elements h1 , . . . , hr with respect to the new pcgs (y1 , . . . , yn ).
ed
1 Write g = xd · k with ed ∈ {1, . . . , pd − 1}, pd the relative order of xd , and k a
product of powers of xd+1 , . . . , xn .
2 if wd < u then
transform hx1 , . . . , xn | Ri 7→ hy1 , . . . , yn | Si and α 7→ α′ , hi 7→ h′i under the
replacement of xd by g in X as in Lemma 4.1.3, and replace wd in the weight
sequence by u.
3 Call ModifyByElement on hy1 , . . . , yn | Si, (w1 , . . . , wd−1 , u, wd , . . . , wn ), k,
min{u, wd}, α′ , (h′1 , . . . , h′r ).
Note that unlike ModifyPcgs, this algorithm does not loop over all prime-power
components of g, so the pcgs from the output may not be a prime-power pcgs even if
the input pcgs is one. The author considered this simplification when encountering
difficulties proving that the original ModifyPcgs has theoretical worst-case complexity bounded by a polynomial in Coll(hx1 , . . . , xn | Ri); for our ModifyByElement,
proving this is straightforward using Lemma 4.1.3. The price we pay for this simplification is that we cannot proceed completely analogously to [5, Subsection 3.1], but
this will not be a problem. We note the following analogue of [5, Lemma 8], which
will be the basis for our further arguments:
Lemma 4.1.5. Let G be a finite solvable group, given through a refined consistent
polycyclic presentation P , let G = N1 ⊲N2 ⊲· · ·⊲Nl ⊲Nl+1 = {1} be a normal series in
G and Yj , j = 2, . . . , l, an induced pcgs of Nj (whose entries are given in X-normal
form). Finally, let P ′ be the refined consistent polycyclic presentation obtained by
successively modifying P (with initial admissible weight sequence (1, . . . , 1)) by each
element of Yj with admissible weight uj = j for j = 2, . . . , l. Then P ′ is the polycyclic
presentation associated with a pcgs Y of G such that for j = 1, . . . , l, the sequence of
entries in Y that are displayed in the final output to have admissible weight at least j
form a pcgs for Nj ; in particular, that pcgs Y exhibits the normal series. Moreover,
the described modifications together require at most Q8 (Coll(P )) bit operations, for
some fixed polynomial Q8 (x) ∈ N[x].
Proof. Since, unlike in [5, Lemma 8], we assume that each pcgs of each Nj is in-

15

Alexander Bors

Orders and cycle lengths

duced (which, in view of Lemma 4.1.4, is w.l.o.g. for the purposes of our theoretical
complexity analysis), the proof here is even simpler than the one of [5, Lemma 8],
because modifying by an induced pcgs (with admissible weights as specified) really
just means replacing each entry of the original pcgs which has the same depth as one
of the entries of the induced pcgs by that (unique) entry, which clearly results in a
pcgs exhibiting N2 in the case l = 2, and as in [5, proof of Lemma 8], the general
case follows from this by induction.
As for the existence of Q8 (x), note that we can avoid having to call collection
algorithms for the modified presentations along the way (which may have varying
complexity, possibly not bounded by T (Coll(P )) for a fixed polynomial T (x) ∈ N[x])
by keeping protocol of what the currently considered modified pcgs is in terms of the
original pcgs (with which P is associated), allowing us to replace a call of a collection algorithm of a modified presentation by O(Coll(P )) substitutions, followed by
O(Coll(P )) calls of the collection and the group element exponentiation algorithm
(see Lemma 4.1.2(1)) for P and a final call of Sift resp. its variant ConstructiveMembershipTest ([13, p. 296]) to translate the computed product back to its
normal form w.r.t. the modified pcgs.
As a final preparation for the proof of Theorem 4.1.1, we note:
Lemma 4.1.6. There is a polynomial Q9 (x) ∈ N[x] such that for any finite solvable
group G, given through a refined consistent polycyclic presentation P = hX | Ri, one
can compute the following in Q9 (Coll(P )) bit operations:
• the length r of the LG-series in G,
• tuples S1 , . . . , Sr of elements of G in X-normal form such that for i = 1, . . . , r
Si is an induced pcgs of the i-th term Gi in the LG-series G = G1 ⊲ G2 ⊲ · · · ⊲
Gr ⊲ Gr+1 = {1} of G.
Proof. This follows from the approach described in [13, Section 8.5] combined with
Lemmata 4.1.2 and 4.1.4.
Proof of Theorem 4.1.1. By Lemmata 4.1.5 and 4.1.6, there is an R(x) ∈ N[x] (not
depending on G) such that we can pass in R(Coll(P )) bit operations to a representation of G (and the associated data such as α) where the pcgs exhibits the LG-series
of G, along with the corresponding sequence of final weights. By [5, Lemma 5], to
get a representation where the pcgs even refines that series, we just have to order
the pcgs entries by increasing weight (preserving the order among entries with the
same weight), which can be done in a number of bit operations that is polynomial in
the input length, in particular polynomial in Coll(P ).

4.2
2

Complexity analysis for the rest of Algorithms 1 and

Note that we have already given details on how to carry out the computations in the
remaining steps of the two algorithms in Subsection 2.1.

16

Alexander Bors

Orders and cycle lengths

For Algorithm 1, the coefficients of the matrices Mi from Step 7 can be read off
directly from the representation of α+ . Moreover, the number r and the dimension
of each Mi is bounded from above by the composition length of G, hence also by
the input length L(P ). As noted in Subsection 2.1, we can transform each Mi into
rational canonical form within O(Lc ) bit operations (where, by [19, pp. 4 and 140],
c may be chosen as 2.4) and directly read off the invariant factors Pi from it. Before trying to factorize Pi with Berlekamp’s Las Vegas algorithm from [3], we first
test whether it is irreducible using Rabin’s algorithm, see [18, Lemma 1]; note that
this requires us to first determine the prime factors of deg Pi , which we can do in
expectedly subexponentially many bit operations by using a combination of the AKS
algorithm [1] and the general number field sieve. As long as there is a factor in the
intermediate factorizations of Pi which is found to be reducible by Rabin’s algorithm,
we use Berlekamp’s algorithm to split that factor up further in expectedly polynomially many bit operations. This combination of irreducibility testing and, where
applicable, searching for smaller factors needs to be applied at most deg Pi ≤ L(P )
many times until Pi has been fully factored. As noted in Subsection 2.1, computing
the order of each irreducible factor F of Pi (from which it is easy to compute the
order of Pi itself) requires us to factor numbers of the form pd − 1, all bounded
from above by |G|, which we do in expectedly subexponentially (in log |G|, hence
also in L(P )) many bit operations as described before. Afterward, we only need to
compute at most polynomially many powers of F to exponents that are divisors of
the factored number pd − 1, which only requires polynomially many bit operations.
After computing each oi and their least common multiple o (see Step 9), we compute
β + = (α+ )o directly with regard to Y , using the square and multiply approach from
Lemma 4.1.2(1) with respect to the collection algorithm of P + , which is okay since
the (subexponential) bound given in [12, Theorem, p. 2] only depends on parameters
of the abstract group G. The same holds for the potential further exponentiations of
the automorphism β + in Step 14.
We leave it to the inclined reader to check that the complexity analysis of Steps 3–
13 of Algorithm 2 is straightforward using the description from Subsection 2.1 and the
details on certain computations already given in the previous paragraph (for Step 12,
use a square-and-multiply approach and the formula At1 ,α1 ◦ At2 ,α2 = At1 α1 (t2 ),α1 ◦α2 ).

5

Concluding remarks

We conclude with some remarks on computational problems related to the ones
discussed in this paper. In Subsection 5.1, we present a problem that is probably
computationally hard, and in Subsection 5.2, we talk about other problems for which
subexponential-time algorithms can be given.

5.1

Contrast to the cycle membership problem

In the context of this paper, the following problem, which we call the “cycle membership problem” may also be considered interesting: Given a finite solvable group
G, an automorphism α of G and elements g1 , g2 ∈ G, decide if g2 lies on the circle of

17

Alexander Bors

Orders and cycle lengths

g1 under α, i.e., whether there exists n ∈ Z such that αn (g1 ) = g2 . We now briefly
discuss a connection between this problem and the discrete logarithm problem which
indicates that the cycle membership problem is probably hard in general, even for
the special case G = Z/pZ, p a prime.
Assume that we have an efficient algorithm (say, requiring o(|G|), for |G| → ∞,
bit operations, which is asymptotically better than the obvious brute-force approach)
for solving the cycle membership problem. Then in particular, we have an efficient
(requiring o(p), for p → ∞, bit operations) algorithm to decide for a given triple
(p, a, b), where p is a prime and a, b ∈ {1, . . . , p − 1}, whether b is a power of a
modulo p. We claim that we then also have an efficient algorithm for the following
promise problem, which is a restricted version of the discrete logarithm problem: For
a given triple (p, a, b) as above, but where additionally, the multiplicative order of
a modulo p is a power of 2, decide whether b is a power of a modulo b and if so,
output the unique e ∈ {0, . . . , ordp (a) − 1} such that b ≡ ae (mod p). Indeed, writing
the multiplicative order of a modulo p as 2o with o ∈ N, if b is a power of a modulo
p, then all f ∈ N such that b ≡ af (mod p) are congruent modulo 2o , and hence
their first o binary digits (starting to count from the ones digit) coincide. So if we
assume, aiming for a recursive approach, that we know already the first i such digits
c0 , . . . , ci−1 for
some i ∈ {0, . . . , o−1}, then we can find out the next digit by deciding
Pi−1
j
i+1
whether b · d j=0 cj 2 , d the multiplicative inverse of a modulo p, is a power of a2
modulo p. We can stop this loop (knowing that the number of digits we have found
is precisely o and that they therefore comprise the significant digits of e) as soon as
i
a2 ≡ 1 (mod p).

5.2 Computational problems in the context of finite dynamical systems
A finite dynamical system (FDS ) is a finite set S together with a function f : S → S.
People working on FDSs (S, f ) are usually interested in the behavior of f under iteration; an important special case with many applications is when S = kn is a Cartesian
power of a finite field k and f : kn → kn is written as a polynomial function (see,
for instance, [7], which includes several references concerning applications in natural
sciences such as biology, and [16], which discusses potential cryptographic applications). Several computational problems in the context of FDSs are also interesting
to study, such as the following, given an FDS (S, f ) and an element s ∈ S:
• Compute the size of the orbit of s under f , i.e., compute |{f n (s) | n ∈ N}|.
• Decide whether s is periodic under f , i.e., whether f n (s) = s for some n ∈ N+ .
• Compute the preperiod length of s under f , i.e., compute the smallest t ∈ N
such that f t(s) is periodic.
Our Algorithm 2 solves the first problem in the special case where S is a (finite)
solvable group G and f is a bijective affine map of G. Without giving a detailed
analysis, we note that the other two problems for (S, f ) = (G, ϕ), a finite solvable
group together with an endomorphism, admit deterministic solution algorithms with

18

Alexander Bors

Orders and cycle lengths

complexity polynomial in Coll(P ), P the refined consistent polycyclic presentation
through which G is given. This is because by [6, Theorem 4.2], the preperiod length
of any g ∈ G under ϕ is at most ⌊log2 |G|⌋, and in particular, the subgroup of G
consisting of the periodic points of ϕ is just the image of ϕ⌊log2 |G|⌋ .

6

Acknowledgements

The author would like to thank Alexander Hulpke for providing his GAP implementation of the algorithm from [8, Section 12.2, pp. 481f.], which is used in the author’s
GAP implementations of Algorithms 1 and 2.

References
[1] M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, Ann. of Math. 160(2)
(2004), 781–793.
[2] E.R. Berlekamp, Factoring polynomials over finite fields, Bell Syst. Tech. J. 46
(1967), 1853–1859.
[3] E.R. Berlekamp, Factoring polynomials over large finite fields, Math. Comput. 24
(1970), 713–735.
[4] A. Bors, Classification of finite group automorphisms with a large cycle,
Comm. Algebra 44(11) (2016), 4823–4843.
[5] J.J. Cannon, B. Eick and C.R. Leedham-Green, Special polycyclic generating
sequences for finite soluble groups, J. Symb. Comput. 38 (2004), 1445–1460.
[6] A. Caranti, Quasi-inverse endomorphisms, J. Group Theory 16(5) (2013), 779–
792.
[7] O. Colón-Reyes, A.S. Jarrah, R. Laubenbacher and B. Sturmfels, Monomial dynamical systems over finite fields, Complex Systems 16(4) (2006), 333–342.
[8] D.S. Dummit and R.M. Foote, Abstract Algebra, Hoboken (John Wiley & Sons,
Inc.), 3rd. edn. 2004.
[9] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.8.6
(2016), http://www.gap-system.org.
[10] T. Hansen and G. L. Mullen, Primitive polynomials over finite fields,
Math. Comput. 59(200) (1992) 639–643, S47–S50.
[11] R.A. Hernández-Toledo, Linear Finite Dynamical Systems, Comm. Algebra
33(9) (2005), 2977–2989.

19

Alexander Bors

Orders and cycle lengths

[12] B.
Höfling,
Efficient
multiplication
for
finite
polycyclic
groups,
preprint
http://www.icm.tu-bs.de/~bhoeflin/preprints/collect.pdf.

algorithms
(2004),

[13] D.F. Holt, B. Eick and E.A. O’Brien, Handbook of Computational Group Theory,
Boca Raton (Chapman & Hall/CRC), 2005.
[14] M.V. Horoševskiı̆, On automorphisms of finite groups, Math. USSR Sb. 22(4)
(1974), 584–594.
[15] R. Lidl and H. Niederreiter, Finite Fields, Cambridge (Cambridge University
Press), 1997.
[16] A. Ostafe and I.E. Shparlinski, Pseudorandom numbers and hash functions from
iterations of multivariate polynomials, Cryptogr. Commun. 2(1) (2010), 49–67.
[17] C. Pomerance, A Tale of Two Sieves, Notices Amer. Math. Soc. 43 (1996),
1473–1485.
[18] M.O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9(2)
(1980), 273–280.
[19] A. Storjohann, Algorithms for Matrix Canonical Forms, PhD thesis (ETH
Zurich), 2000.
[20] J. von zur Gathen and D. Panario, Factoring polynomials over finite fields: a
survey, J. Symb. Comput. 31 (2001), 3–17.

20

