A linear-time algorithm for the orbit problem
over cyclic groups
Anthony W. Lin1 and Sanming Zhou2
1

2

Yale-NUS College, Singapore
Department of Mathematics and Statistics, The University of Melbourne, Australia

Abstract. The orbit problem is at the heart of symmetry reduction
methods for model checking concurrent systems. It asks whether two
given configurations in a concurrent system (represented as finite sequences over some finite alphabet) are in the same orbit with respect toa given finite permutation group (represented by their generators) acting
on this set of configurations. It is known that the problem is in general
as hard as the graph isomorphism problem, which is widely believed to
be not solvable in polynomial time. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e.
generated by a single permutation), an important restriction of the orbit
problem. Our main result is a linear-time algorithm for this subproblem.

1

Introduction

Since the inception of model checking, a key challenge in verifying concurrent
systems has always been how to circumvent the state explosion problem due tothe growth in the number of processes. Among others, symmetry reduction [10,14, 18] has emerged to be an effective technique in combatting the state explosion
problem. The essence of symmetry reduction is to identify symmetries in thesystem and avoid exploring states that are “similar” (under these symmetries)
to previously explored states, thereby speeding up model checking.
Every symmetry reduction method has to deal with the following problems:(1) how to identify symmetries in the given system, and (2) how to check that
two configurations are similar under these symmetries. For concurrent systems
with n processes, Problem 1 amounts to searching for a group G of permutations
on [n] := {1, . . . , n} such that the system behaves in an identical way under theaction of permuting the indices of the processes by any π ∈ G. For example,
for a distributed protocol with a ring topology, the group G could be a rotationgroup generated by the “cyclical right shift” permutation RS that maps i 7→ i+1
mod n for each i ∈ [n]. The reader is referred to the recent survey [23] for moredetailed discussions and techniques for handling Problem 1, a computationallydifficult problem in general. Now the group G partitions the state space of the
concurrent system (i.e. Γ n for some finite set Γ ) into equivalence classes called(G-)orbits. Problem 2 is essentially the orbit problem (over finite permutationgroups): given G and two configurations v, w ∈ Γ n , determine whether v and w

are in the same G-orbit. For example, if G is generated by RS with n = 4, thetwo configurations (1, 1, 0, 0) and (0, 0, 1, 1) are in the same orbit.
The orbit problem (OP) was first studied in the context of model checking by
Clarke et al. [10] in which it was shown to be in NP but is as hard as the graphisomorphism problem, which is widely believed to be not solvable in polynomial
time. The difficulty of the problem is due to the fact that the input group G isrepresented by a set S of generators and that the size of G can be exponential
in |S| in the worst case. There is also a closely related variant of OP called theconstructive orbit problem (COP), which asks to compute the lexicographicallysmallest element w ∈ Γ n in the orbit of a given configuration v ∈ Γ n withrespect to a given group G. OP is easily reducible to COP, though the reverse
direction is by no means clear. COP was initially studied in the context ofgraph canonisation by Babai and Luks [3], in which COP was shown to be NPhard (in contrast, whether OP is NP-hard is open). In the context of model
checking, COP was first studied by Clarke et al. [9], in which a number of “easygroups” for which COP becomes solvable in P are given including polynomialsized groups (e.g. rotation groups), the full symmetry group Sn (i.e. containing
all permutations on [n]), and disjoint/wreath products of easy groups (cf. [13]).
In this paper, we consider the orbit problem over cyclic groups (i.e. generated
by a single permutation π ∈ Sn ), which is an important subproblem of OP.
Firstly, an algorithm for this subproblem has immediate applications for OP in
the general case. For example, given a permutation group G with generators
π1 , . . . , πk , we can check if the two configurations v and w are in the same
orbit of the cyclic subgroup generated by any one of πj . [If yes, then v and w
are also in the same G-orbit.] It is also possible to combine cyclic groups withother easy groups from [9] via disjoint/wreath product operators. Secondly, it
subsumes a commonly occurring class of symmetries for concurrent systems: therotation groups. Unlike the case of rotation groups however, the size of cyclic
groups can be exponential in n (see Proposition 3 below), which rules out a naive
enumeration of the group elements. Finally, OP over cyclic groups is intimately
connected to the classical orbit problem over rational matrices [19]: given a
rational n-by-n matrix M and two rational vectors v, w ∈ Qn , determine if there
exists k ∈ N such that Ak v = w. In fact, they coincide when M is restricted topermutation matrices [6], i.e., 0-1 matrices with precisely one column for eachrow with entry 1. To see this, given a permutation π on [n], simply take an n-byn 0-1 matrix A = (A[i, j])1≤i,j≤n such that A[i, j] = 1 iff π(j) = i. The reverse
direction is similar. That OP over cyclic groups is in P follows from Kannan and
Lipton’s celebrated result [19] that OP over rational matrices is in P.
Contributions. In this paper, we provide an algorithm for the orbit problem
over cyclic groups that is simpler than Kannan-Lipton’s algorithm [19] and moreover runs in linear-time in the standard RAM model. To this end, we provide alinear-time reduction to the problem of solvability of systems of linear congruenceequations. The reduction is simple though it exploits subtle connections to thestring searching problem and number-theoretic results like the Erdös-Graham
Lemma [15] concerning solutions of Diophantine equations.

As for the solvability of systems of linear congruence equations, we start off
with an algorithm that runs in linear-time assuming constant-time integer arithmetic operations. However, when we measure the number of bit operations (i.e.
bit complexity model), it turns out that the algorithm runs in time cubic in thenumber of equations in the systems. To address this issue, we restrict the problem to input instances provided by our reduction from the orbit problem. We
offer two solutions. Firstly, we show that the average-case complexity of the algorithm under the bit complexity model is O(log5 n), which is sublinear. Secondly,
we provide another algorithm that uses at most linearly many bit operations in
the worst case (though on average it is worse than the first algorithm).
Organisation. Section 2 contains definitions and basic concepts. We provide
our first algorithm for solving systems of linear congruence equations in Section 3 (Algorithm 1), while we provide our linear-time reduction from the orbit
problem to equations solving in Section 4 (Algorithm 2). Thus far, we assume
that arithmetic operations take constant time. We deal with the issue of bitcomplexity in Section 5. We conclude with future work in Section 6.
Acknowledgment. We thank the anonymous referees for their helpful feedback. Part of the work was done when Lin was at Oxford supported by EPSRC(H026878). Zhou was supported by ARC (FT110100629).

2

Preliminaries

General Notations: We use log (resp. ln) to denote the logarithm function
in base 2 (resp. natural logarithm). We use the standard interval notations todenote a subset of integers within that interval. For example, [i, j) denotes theset {k ∈ Z : i ≤ k < j}. Likewise, for each positive integer n, we use [n] todenote the set {1, . . . , n}. We shall also extend arithmetic operations to sets ofnumbers in the usual way: whenever S1 , S2 ⊆ Z, we define S1 + S2 := {s1 + s2 :s1 ∈ S1 , s2 ∈ S2 } and S1 S2 := {s1 × s2 : s1 ∈ S1 , s2 ∈ S2 }. In the context
of arithmetic over 2Z , we will treat a number n ∈ N as the singleton set {n}.
That way, for a, b ∈ N, the notation a + bZ refers to the arithmetic progression{a + bc : c ∈ Z}, where a (resp. b) is called the offset (resp. period ) of thearithmetic progression. Likewise, for a subset S ⊆ N, we use gcd(S) to denotethe greatest common divisor of S.
We will use standard notations from formal language theory. Let Γ be analphabet whose elements are called letters. A word (or a string) w over Γ is a
finite sequence of elements from Γ . We use Γ ∗ to denote the set of all words over
Γ . The length of w is denoted by |w|. Given a word w = a1 . . . an , the notation
w[i, j] denotes the subword ai . . . aj . For a sequence σ = i1 , . . . , ik ∈ [n]∗ ofdistinct indices of w, we write w[σ] to denote the word ai1 . . . aik . We also define
RS(w) to be an a1 a2 . . . an−1 , i.e., the word w cyclically right-shifted.
Number Theory: We will use the following basic result (cf. [11]).
Proposition 1 (Chinese Remainder Theorem). Let n1 , . . . , nk be pairwiseQrelatively prime positive integers, and n = ki=1 ni . The ring Zn and the directproduct of rings Zn1 × · · · × Znk are isomorphic under the function σ : Z →Zn1 × · · · × Znk with σ(x) := (x mod n1 , . . . , x mod nk ) for each x ∈ Z.

Groups: We briefly recall basic concepts from group theory and permutationgroups (cf. see [7]). A group G is a pair (S, ·), where S is a set and · : (S ×S) → S
is a binary operator satisfying: (i) associativity (i.e. g1 · (g2 · g3 ) = (g1 · g2 ) · g3 ),(ii) the existence of a (unique) identity element e ∈ S such that g · e = e · g = g
for all g ∈ S, and (iii) closure under inverse (i.e. for each g ∈ G, there exists
g −1 ∈ G such that g · g −1 = g −1 · g = e). When it is clear from the context, we
will write g · g ′ as gg ′ . The order ord(G) of the group G is defined to be |S|.
This paper concerns only finite groups, i.e., groups G with ord(G) = |S| ∈ N.
For each n ∈ N, we define g n by induction: (i) g 0 = e, and (ii) g n = g n−1 · g.
The order ord(g) of g ∈ G is the least positive integer n such that g n = e.
A subgroup H of G = (S, ·) (denoted as H ≤ G) is any group (S ′ , ·H ) suchthat S ′ ⊆ S and ·H and · agree on S ′ . Given any subset X ⊆ S, the subgroupof G generated by X is defined to be the subgroup hXi := (S ′ , ·h ) of G each ofwhose elements can be expressed as a finite product of elements of X and theirinverses. If H = hXi, then X is said to generate H. A cyclic group is a group
generated by a singleton set X = {g}.
An action of a group G = (S, ·) on a set Y is a function × : S × Y → Y suchthat for all g, h ∈ S and y ∈ Y : (1) (gh) × y = g × (h × y), and (2) e × y = y.
The (G-)orbit containing y, denoted Gy, is the subset {g × y : g ∈ G} of Y . The
action × partitions the set Y into G-orbits. When the meaning is clear, we shallomit mention of the operator ×, e.g, condition (2) above becomes ey = y.
Permutation Groups. A permutation on [n] is any bijection π : [n] → [n].
The set of all permutations on [n] forms the (nth) full symmetry group Sn under functional composition. We shall use the notation Id to denote the identity
element of each Sn . A word w = a0 . . . ak−1 ∈ [n]∗ containing distinct elementsof [n] (i.e. ai 6= aj if i 6= j) can be used to denote the permutation that maps
ai 7→ ai+1 mod k for each i ∈ [0, k) and fixes other elements of [n]. In this case, w
is called a cycle, which we will often write in the standard notation (a0 , . . . , ak−1 )so as to avoid confusion. Observe that w and RS(w) represent the same cycle c.
We will however fix a particular ordering to represent c (e.g. the word provided as
input to the orbit problem). For this reason, if v ∈ Γ n for some alphabet Γ , thenotation v[c] is well-defined (see General Notations above), which means projections of v onto elements with indices in c, e.g., if v = (1, 1, 1, 0) and c = (1, 4, 2),
then v[c] = (1, 0, 1). Any permutation can be written as a composition of disjoint
cycles [7]. Each subgroup G = (S, ·) of Sn acts on the set Γ n (over any finite
alphabet Γ ) under the group action of permuting indices, i.e., for each π ∈ S
and v = (a1 , . . . , an ) ∈ Γ n , we define πv := (aπ(1) , . . . , aπ(n) ).
Complexity Analysis: We will assume that permutations will be given in the
input as a composition of disjoint cycles. It is easy to see that permutations canbe converted back and forth in linear time from such representations and therepresentations of permutations as functions. The size knk of a number n ∈ N is
defined to be the length of the binary representation of n, which is ⌊log n⌋ + 1.
P
The size kck of a cycle c = (a1 , . . . , ak ) on [n] is defined to be ki=1 kai k (incontrast, the length |c| of c is k). For a permutation
Pm π = c1 · · · cm where eachci is a cycle, the size kπk of π is defined to be i=1 kci k. We will use standard
asymptotic notations from analysis of algorithms (big-O and little-o), cf. [11].
We also use the standard ∼ notation: f (n) ∼ g(n) iff limn→∞ f (n)/g(n) = 1.
We will use the standard RAM model that is commonly used when analysing
the complexity of algorithms (cf. [11]). In Sections 3 and 4, we will assume that
integer arithmetic takes constant time. Later in Section 5, we will use the bitcomplexity model (cf. [11]), wherein the running time is measured in the numberof bit operations.

3

Solving a system of modular arithmetic equations

Recall that a linear congruence equation is a relation of the form x ≡ a (mod b),
where a, b ∈ N, whose solution set is denoted by [[x ≡ a (mod b)]] V= a + bZ. A
msystem of linear congruence equations is a relation of the form Vi=1 x ≡ aim(mod bi ). The set of solutions
Tm x ∈ Z to this system is denoted by [[ i=1 x ≡ ai(mod bi )]], which equals i=1 [[x ≡ ai (mod bi )]]. The system is soluble / solvable
if the solution set is nonempty. We use false to denote x ≡ 0 (mod 2) ∧ x ≡ 1(mod 2), which is not solvable. The following proposition provides a fast symbolic
method for computing solutions to systems of linear congruences.
Proposition 2. For any solvable system of linear congruence equations ϕ(x) :=Vmi=1 x ≡ ai (mod bi ), we have [[ϕ(x)]] = [[x ≡ a (mod b)]] for some a, b ∈ Z.
Furthermore, there exists an algorithm which computes a, b in linear time.
This proposition is in fact a rather easy corollary of the following result in algorithmic number theory about solving more general linear congruence equationsof the form ax ≡ b (mod n).
Lemma 1 (Linear Congruence Theorem; see [11, Chapter 31.4]). The
equation ax ≡ b (mod n) is solvable for the unknown x iff d|b, where d =gcd(a, n). Furthermore, if it is solvable, then the set of solutions equals x0 +(n/d)Z, for some x0 ∈ [0, n/d) that can be computed in time O(log n).
This algorithm made use of the Extended Euclidean algorithm, which explains
the O(log n) time complexity (see [11]). Algorithm 1 witnesses the linear-timealgorithm claimed in Proposition 2. The algorithm sequentially goes througheach equation x ≡ ai (mod bi ), while keeping the solution to the subsystemVj
i=1 x ≡ ai (mod bi ) at jth iteration as an arithmetic progression a + bZ, forsome a, b ∈ Z. Before we go through any equation, the set of solutions to theempty system of equations
is a + bZ with a = 0 and b = 1. At the jth iteration,
Vj−1
we assume that [[ i=1 x ≡ ai (mod bi )]] = a + bZ for some a, b ∈ Z. We replace
x in the equation x ≡ aj (mod bj ) by a + by for an unknown y, which resultsin the new equation ϕ(x) := by ≡ ai − a (mod bi ). Lemma 1 gives an answer to[[ϕ]] as either ∅ or a′ + b′ Z, for some a′ ∈ [0, bi ) and b′ ∈ [1, bi ]. We substitute thisVjsolution set back to x, which gives [[ i=1 x ≡ ai (mod bi )]] = (a′ b + a) + bb′ Z,
which justifies the assignments a := a′ b + a and b := bb′ .

Algorithm 1 Solving a system of modular arithmetic equations

Vm
Input: A system of modular
Vm arithmetic equations i=1 x ≡ ai (mod bi )Output: Solution set [[ i=1 x ≡ ai (mod bi )]] as ∅ or an arithmetic progression a + bZ.
a := 0; b := 1;for i = 1, . . . , m doϕ(y) := by ≡ ai − a (mod bi );Apply algorithm from Lemma 1 on ϕ returning either ∅ or a′ + b′ Z for [[ϕ]];if [[ϕ]] = ∅ then return NO else a := a′ b + a; b := bb′ end if
end forreturn a + bZ;

As for the time complexity of the algorithm, at jth iteration the algorithm
invokes the algorithm from Lemma 1, which P
runs in time O(log bj ). Therefore,mthe total running time of our algorithm is O( j=1 log bj ), i.e., linear in the sizePm
j=1 (log aj + log bj ) of the input.

Remark 1. The numberPof bits that is used to maintain a and b in the worstmcase is linear in the size j=1 (log aj + log bj ) of the input. This justifies treating
a single arithmetic operation as a constant-time operation. We will address theissue of bit complexity in Section 5.

4

Reducing to solving a system of linear congruenceequations

In this section, we prove the main result of the paper.
Theorem 1. There is a linear-time algorithm for solving the orbit problem when
the acting group is cyclic.
This algorithm is a linear-time reduction from the orbit problem over cyclic
groups to solving a system of linear congruence equations, which will allow us
to use results from the previous section.
Before we proceed to the algorithm, the following proposition shows why thenaive algorithm that checks whether g i (v) = w, for a given permutation g ∈ Sn
and for each i ∈ [0, ord(g)), actually runs in exponential time.
Proposition 3. There exists a sequence {Gi }∞i=1 of cyclic groups Gi = hgi i suchthat ord(gi ) is exponential in the size kgi k of the permutation gi .
Proof. Let pn denote the nth prime. The Prime Number Theorem states thatpn ∼ n log n (cf. [17]). For each i ∈ Z>0 , we define a cycle ci of length pi by
induction on i. For i = 1, let c1 = (1, 2). Suppose that ci−1 = (j, . . . , k). In
this case, we define ci to be the cycle (k + 1, . . . , k + pi ). To define the sequencei{gi }∞
i=1 of permutations, simply let gi = Πj=1 ci . For example, we have g3 =(1, 2)(3, 4, 5)(6, 7, 8, 9, 10). Since ci ’s are disjoint, the order ord(gi ) of gi is thesmallest positive integer k such that ckj = Id for all j ∈ [i]. If Sj denotes the setof integers k satisfying ckj = Id, then ord(gi ) is precisely the smallest positive

T
integer in the set ij=1 Sj . It is easy to see that Sj = pj Z, which is the set ofsolutions to the linear congruence equation x ≡ 0 (mod pj ). Therefore, by theTi
Chinese Remainder Theorem (cf. Propositon 1), the set j=1 Sj coincides withQi
the arithmetic progression ti Z with ti := j=1 pj . This implies that ord(gi ) = ti .
Now the number ti is also known as the ith primorial number [1] with ti ∼e(1+o(1))i log i , which isPa corollary
Pi of the Prime Number Theorem. On the other
hand, the size of gi is (i) := j=1 pi , which is known to be ∼ 12 i2 ln i (cf. [4]).
Therefore, ord(gi ) is exponential in kgi k as desired.
⊓⊔
Algorithm 2 Reduction to system of modular arithmetic equations
Input: A permutation g = c1 · · · cm ∈ Sn , a finite alphabet Γ , and v, w ∈ Γ n .
Output: A system of modular arithmetic equations, which is satisfiable iff ∃i ∈ N :g i (v) = w.
// First solve for each individual cycle
for all i = 1, . . . , m do
Compute the length |ci | of the cycle ci ;Compute an ordered list Si′ ⊆ [0, |ci |) of numbers r with cri (v[ci ]) = w[ci ];if Si′ = ∅ then return false end if
if |Si′ | = 1 then let ai be the member of Si ; bi := |ci |; end if
if |Si′ | > 1 then ai := min(Si′ ); a′i := min(Si′ \ {ai }); bi := a′i − ai ; end if
end for// Now for each i ∈ [1, m] we have a modularVarithmetic equation x ≡ ai (mod bi )return YES iff there exists x ∈ N satisfying m
i=1 x ≡ ai (mod bi )Our linear-time reduction that witnesses Theorem 1 is given in Algorithm
2. In this algorithm, the acting group is G = hgi with g ∈ Sn , expressed as acomposition of disjoint cycles in a standard way, say, g = c1 c2 · · · cm where each ci
is a cycle. Also part of the input is two strings v = v1 . . . vn , w = w1 . . . wn ∈ Γ nover a finite alphabet Γ . The orbit problem is to check whether f (v) = w forsome f ∈ G, i.e., f = g r for some r ∈ N. Since ci ’s are pairwise disjoint cycles,
the question reduces to checking if there exists r ∈ N such that∀i ∈ [1, m] : (cri v)[ci ] = w[ci ](∗)

In other words, for each i ∈ [1, m], applying the action cri to v gives us w whenrestricted to the indices in ci . Essentially, Algorithm 2 sequentially goes througheach cycle ci and computes the set Si of solutions r to (cri v)[ci ] = w[ci ] as the setof solutions to the linear congruence equation x ≡ ai (mod bi ). Therefore, the setof solutionsVto (*) is precisely the set of solutions to the system of congruencemequations i=1 x ≡ ai (mod bi ). In the following, we will provide the detailsof each individual step of Algorithm 2. We will also use the following running
example to illustrate the algorithm: c = (6, 5, 7, 3, 2, 1), v = 010001111, andw = 101110001, where the positions in v and w that are modified by c areunderlined.
Step 1: Computing the length of cycles. This is the same as how to computethe length of a list. Therefore, computing the length |ci | can be done in timeO(kci k).

Step 2: Computing representatives Si′ ⊆ [0, |ci |) for Si . During this step,
we collect a subset of numbers h ∈ [0, |ci |) such that chi (v[ci ]) = w[ci ]. A
quadratic algorithm for this is easy to come up with: sequentially go throughh ∈ [0, |ci |) while computing the current chi , and save h if chi (v[ci ]) = w[ci ] holds.
One way to obtain a linear-time algorithm is to reduce our problem to the string
searching problem: given a “text” T ∈ Σ ∗ (over some finite alphabet Σ) anda “pattern” P ∈ Σ ∗ , find all positions i in T such that T [i, i + |P |] = P . This
problem is solvable in linear-time by Knuth-Morris-Pratt (KMP) algorithm (e.g.
see [11]).
We now show how to reduce our problem to the string searching problem in
linear time. Suppose that c := ci = (j1 , . . . , jk ). We have v[c] = vj1 . . . vjk andw[c] = wj1 . . . wjk .
Lemma 2. (cv)[c] = RS(v[c]).
In other words, if Dom(c) = {j1 , . . . , jk }, the effect of c on v when restricted
to Dom(c) coincides with applying a cyclical right shift on the string [c]. Following our running example, it is easy to check that [c] = 101010 and (cv)[c] =RS(v[c]) = 010101.
Proof (of Lemma 2). Let u = u1 . . . uk := (cv)[c] and u = u′1 . . . u′k := RS(v[c]).
It suffices to show that ut = u′t for all t ∈ Zk . By definition of RS, it follows
that u′t = vjt−1 . Now suppose that v′ = v1′ . . . vn′ := cv. Thenvj
if j ∈/ Dom(c)′vj :=vj ′ if j ∈ Dom(c) and, for some t ∈ Zk , j = jt+1 and j ′ = jt .
So, we have ut = ((cv)[c])[t] = (v′ [c])[t] = vj′ t = vjt−1 . This proves that ut = u′t .
⊓⊔Lemma 3. For each r ∈ N, we have (cr v)[c] = RSr (v[c]).

Lemma 3 can easily be proven by induction using Lemma 2 (see full version).
Lemma 3 implies that the set S := Si ⊆ N of solutions r to the equation(cri v)[ci ] = w[ci ] is a finite union of arithmetic progressions of the form a + kZ,
where k = |ci | and a ∈ [0, k). This is simply because RSr+k (v[ci ]) = RSr (v[ci ]).
We will finitely represent S by the offsets a’s and the unique period k in thesearithmetic progressions.
We now show how to compute the offsets for S in linear time by a linear-time
reduction to the string searching problem. Define the text T := v[c]v[c] and thepattern P := w[c]. Observe that, for each r ∈ [0, k), P is matched at position r
in T iff RSr−1 (v[c]) = w[c]. Therefore, after running the KMP algorithm withthe solution set S ′ , the offsets for S will be {r − 1 : r ∈ S ′ }. Solvability for eachindividual equation amounts to checking that, for each cycle ci , the set Si ofsolutions for the corresponding equation is nonempty.
Example 1. Continuing with our running example, it follows that T = v[c]v[c] =101010101010 and P = w[c] = 010101. We see that P matches T at positions
S ′ = {2, 4, 6}. This implies that the set S of solutions r ∈ Z to the equation(cr v)[c] = w[c] is (1 + 6Z) ∪ (3 + 6Z) ∪ (5 + 6Z). Observe that, for each ci , this step takes
going
Pmtime O(kci k). Therefore,Pmthrough all the ci ’s, this step takes time
O(kc
k)
=
O
(
kc
k) =
i
i
i=1
i=1
O(kgk), i.e., linear in input size.
Step 3: Representing Si as a single arithmetic progression. In the previous step, we have computed the representatives for Si in [0, |ci |). This onlyshows that Si is a finite union of arithmetic progressions, which cannot in general be expressed as the set of solutions to a linear congruence equation. In thisstep, we show that Si can be represented as a single arithmetic progression andfurthermore justify why the last three lines in Algorithm 2 computes Si .
Lemma 4 (Normal Form). For each i = 1, . . . , m, either Si = ∅ or Si =ai + bi Z for some ai , bi ∈ [0, |ci |) where bi divides |ci |. In the case when |Si′ | > 1,
we have ai = p1 and bi = p2 − p1 , where p1 < p2 are the smallest numbers in Si′ .
Furthermore, we may compute the pair (ai , bi ) of numbers in time O(kci k).
To prove this lemma, we will use the following number-theoretic result by Erdös
and Graham [15]. [Also see the formulation in [8, 22], in which the result wasapplied in automata theory.]
Proposition
4. Let 0 < p1 < . . . < ps ≤ k be natural numbers. Then, the set
Ps
X := { i=1 pi xi : x1 , . . . , xs ∈ N} ⊆ N coincides with the set S ∪(a+ bN), where
S ⊆ N contains no numbers bigger than k 2 , and a is the least integer bigger thank 2 that is a multiple of b := gcd(p1 , . . . , ps ).
Proof (of Lemma 4). We use the shorthand S (resp. c) fori (resp. ci ). From StepSSs2, we know that S is a union of arithmetic progressions j=1 (pj + kZ), for somepj ∈ [0, k) and k = |c|. Without loss of generality, we assume that p1 < · · · < ps .
If s ∈ {0, 1}, then we are done. Suppose now that s > 1. Let v[c] = d1 . . . dk andw[c] = d′1 . . . d′k . In this case, thanks to Lemma 3, it is the case that for eachj ∈ [1, s] and l ∈ [1, k], we have dl+pj mod k = d′l . Let ∆ := {ph′ − ph : ∀h < h′ ∈[1, s]}∪{k} be the set of all differences in the offsets of the arithmetic progressions
union the set {k} containing the common period. By transitivity of ‘=’, it follows
that dl mod k = dl+δ mod k for each l ∈ [0, k) and δ ∈ ∆. Again, by transitivityof ‘=’, it follows thatPdl mod k = dl+σ mod k for each l ∈ [0, k) and each numbers
σ in the set X := {( i=1 pi xi ) + kxs+1 : x1 , . . . , xs+1 ∈ N}. By Proposition 4,
we have X = S ∪ (a + bN) where S ⊆ [0, k 2 ] and a is the least integer bigger thank 2 that is a multiple of b := gcd(∆). Observe also that b divides all numbers in S
and so we have dl = dl′ for each l, l′ ∈ [0, k) with l ≡ l′ (mod b). In other words,
we have v = |v′ .{z. . v}′ , where v′ = d1 . . . db . Since RSp1 (v[c]) = w[c], it follows
k/b times

that, for each q ∈ N, RSp1 +bq (v[c]) = RSp1 (RSbq (v[c])) = RSp1 (v[c]) = w[c].
Therefore, we have S ⊆ p1 + bN. On the other hand, since b divides k andeach number in {pj − p1 : j ∈ [2, s]}, we also have S ⊇ p1 + bN. This gives us
S = p1 + bN.
From Step 2, we have computed the set S ′ := S ∩ [0, |c|). If S ′ = ∅, we also
knew that Si = ∅. If S ′ = {p} is a singleton, we have S = p + kZ. If |S ′ | > 1, we
find the two smallest numbers p1 < p2 in S ′ . It follows that S = p1 + (p2 − p1 )Z.

Observe that this takes time O(kck). [In fact, it is only linear in the size of thetwo smallest numbers since we ignore the rest of the members of S ′ .]⊓⊔Example 2. Continuing with our running example, we have S = (1 + 6Z) ∪ (3 +6Z) ∪ (5 + 6Z) = 1 + 2Z. 
The last three lines in Algorithm 2 runs in constant time since determining
whether |Si | = 0, |Si | = 1, or |Si | > 1 requires the algorithm to explore only aconstant number of elements in Si .
Summing up. To sum up, the time spent computing the linear congruenceequation x ≡ ai P
(mod bi ) for each i ∈ [1, m] is O(kci k). Therefore, our reductionmruns in time O( i=1 kci k) = O(kgk), which is linear in input size. Therefore,
invoking Proposition 2 on the resulting system of linear congruence equations,
we obtain the set of solutions to (*) in linear time.
Example 3. Let us continue with our running example. Let
g1 := c(4, 8) = (6, 5, 7, 3, 2, 1)(4, 8),

g2 := c(4, 8, 9) = (6, 5, 7, 3, 2, 1)(4, 8, 9).

Then, running Algorithm 2 on g1 yields the system x ≡ 1 (mod 2) ∧ x ≡ 1(mod 2), which is equivalent to x ≡ 1 (mod 2). Running Algorithm 2 on g2
yields the system x ≡ 1 (mod 2) ∧ x ≡ 1 (mod 3). Both systems are solvable. 
Remark 2. At this stage, the reader might wonder whether the Normal Form
Lemma (cf. Lemma 4) is necessary. For example, without this lemma one could
directly convert the orbit problem over cyclic groups into satisfiability of positive
boolean formulas (i.e. involving both disjunctions and conjunctions) where each
proposition is interpreted as a linear congruence equation. [This can be construed
as adding the power of disjunction to systems of linear congruence equations.]
Unfortunately, it is not difficult to show that the resulting satisfiability problem
is NP-complete using the techniques of Gödel numbering (cf. [16, 21]).

5

Making do with linearly many bit operations

Thus far, we have assumed that arithmetic operations take constant time. In
this section, since Algorithm 1 makes a substantial use of basic arithmetic operations, we will revisit this assumption. It turns out that, although our reduction(Algorithm 2) to solving a system of linear congruence equations runs in linear
time in the bit complexity model, the algorithm for solving the system of equations (Algorithm 1) uses at least a cubic number of arithmetic operations. The
main results in this section are two-fold: (1) on inputs given by our reduction,
Algorithm 1 runs in sublinear time (more precisely, O(log5 n)) on average inthe bit complexity model, and (2) there exists another algorithm for solving asystem of linear congruence equations (with numbers in the input represented
in unary) that runs in linear time in the bit complexity model in the worst case.
We begin with two lemmas that provide the running time of Algorithm 2and Algorithm 1 in the bit complexity model.

Lemma 5. Algorithm 2 runs in linear time in the bit complexity model.
Proof. On ith iteration, the number |ci | is stored in binary counter and can becomputed by counting upwards from 0 and incrementing by 1 as we go throughthe elements in ci . Although a single increment by 1 might take O(|ci |) bit
operations in the worst case (since we have to propagate the carry bit), it is
known (e.g. see [11, Chapter 17, p. 454]) that the entire sequence of operations actually takes time O(|ci |). Finally, since addition and substraction of two
numbers can easily be performed in O(β) time on numbers that use at most β
bits, the operation bi := a′i − ai on the last line of the iteration takes at mostO(logaccounting for all the cycles, the algorithm takes
Pm
Pm |ci |) time. Therefore,kck)= O(kgk), which is linear in the input size.
⊓
⊔
O(kc
k)
=
O(
i
i
i=1
i=1
Vm
Lemma 6. On an input i=1 x ≡ ai (mod bi ) with N = max{bi : i ∈ [1, m]},Algorithm 1 uses at most m log N bits to store any numeric variables. Furthermore, the algorithm runs in time O(m3 log2 N ) in the bit complexity model.
Proof. On ith iteration, the number of bits used to store a and b grow by atmost log bi . On the other hand, the invariant that a′ , b′ ∈ [0, bi ) is always maintained on the ith iteration and so they only need at most log N bits to represent
throughout the algorithm. Hence, the algorithm uses M = O(m log N ) bits tostore a, b, a′ , and b′ . Extended Euclidean Algorithm runs in time O(M 2 ) on
inputs where each number uses at most M bits (cf. [11, Problem 31-2]), which
also bounds the time it takes on each iteration. Therefore, the algorithm takes
at most O(mM 2 ) = O(m3 log2 N ) in the bit complexity model.
⊓⊔
We now provide an average case analysis of the running time of Algorithm
1 on system of linear congruence equations given by our reduction. The input
to the orbit problem over cyclic groups includes a permutation g ∈ Sn and two
vectors v, w ∈ Γ n . We briefly recall the setting of average-case analysis (cf.
[20]). Let ΠN be the set of all inputs to the algorithm of size N . Likewise, letΣN be the sum of the costs (i.e. running time) of the algorithm on all inputsof size P
N . Hence, if ΠN,k is the cost of the algorithm on input of size N , thenΣN = k kΠN,k . The average case complexity of the algorithm is defined to beΣN /ΠN .
Theorem 2. The expected running time of Algorithm 1 in the bit complexity
model on inputs provided by Algorithm 2 is O(log5 n).
Proof. The size of a single permutation g ∈ Sn is O(n) and additionally Πn =|Sn | = n!. Suppose that g has k cycles (say, g = c1 · · · ck ). Then, Algorithm 2
Vproduces a system of equations ki=1 x ≡ ai (mod bi ), where ai , bi ∈ [0, |ci |).
By Lemma 6, Algorithm 1 takes O(k 3 log2 n) time in the bit complexity model,
since N := max{bi : i ∈ [1, m]} ≤ n. In addition, the number of permutations
in Sn with k cycles
 is precisely the definition of theunsigned Stirlingnumber

Pn
n
n
2
3
of the first kind
. Therefore, we have Σn = O
(k
log
n)
=
k=1
k
k

 
 

Pn
Pn
n
1
3 n
k
∼
O log2 n k=1 k 3. Therefore, it suffices to show that n!
k=1kkc log3 n for a constant c. The proof can be found in the full version.
⊓⊔
Finally, we will now give our final main result of this section.
Theorem 3. There exists a linear-time algorithm in the bit complexity model
for solving a system of linear congruence equations when the input numbers are
represented in unary.
V
We now provide an algorithm that witnesses the above theorem. Let mi=1 x ≡ ai(mod bi ) be the given system of equations. With unary representation of numbers, the size Ni of the equation x ≡ ai (mod bi ) is ai + bi . We use n to denotethe total number of bits in the system of equations. Initially, we compute a binary representation of all the numbers ai ’s, bi ’s, and n as in the proof of Lemma
5, which takes linear time. Next we factorise all the numbers bi into a producteiti1
of distinct prime powers pjei1· · · pjit i , where pj stands for the jth prime andi√all eij ’s are positive integers. This can be done in time O( Ni log2 Ni ). To obtain this time bound, we can use any unconditional 3 deterministic factorisation
methods like Strassen’s algorithm, whose complexity was shown in [5] (cf. alsosee [12]) to be O(f (N 1/4 log N )) for factoring a number N , where f (M ) is thenumber of bit operations required to multiply two numbers with M bits. The
standard (high-school) multiplication algorithm runs in quadratic time giving us
f (M ) = O(M 2 ), which suffices for our purposes. This shows that Strassen’s algorithm runs in time O(N 1/2 log2 N ). [In practice, do factoring using the general
number field sieve (cf. [11]), which performs extremely well in practice, though
its complexity requires some unproven number-theoretic assumptions.]
Next, following Chinese Remainder Theorem (CRT), we compute zij := aiemod pijij for each j ∈ [1, ti ]. Let us analyse the time complexity for performing
this. Each zij can be computed by a standard algorithm (e.g. see [11]) in timeequadratic in the number of bits used to represent ai and pijij . Since each of thesenumbers use at most log Ni bits, each zi can be computed in time O(log2 Ni ),which is o(Ni ). In addition, since eij > 1 for each j ∈ [1, ti ], it follows that ti =O(log Ni ). This means that the total time it takes to compute {zij : j ∈ [1, ti ]}3
is O(log
Pm Ni3), which is also o(Ni ). So, computing this for all i ∈ [1, m] takes timeO( i=1 log Ni ), which is at most linear in the input size.
In summary, for each i ∈ [1, m], we obtained the following system of equations, which is equivalent to x ≡ ai (mod bi ) by CRT:x ≡ zi1

ei1)(mod pi1∧······∧x ≡ ziti

eit(mod piti i )(Ei )The final step is to determine if there exists a number x ∈ N that satisfies
each (Ei ), for all i ∈ [1, m]. Loosely, we will go through all the equations andmakes sure that there is no conflict between any two equations whose periods
are powers of the same prime number, i.e., x ≡ a (mod b) and x ≡ a′ (mod b′ )3This means that the bound does not depend on any number-theoretic assumptions.

′such that b = pi and b′ = pi for some prime p and i, i′ ∈ Z>0 . In order to achieve
this in linear-time in the bit complexity model, one has to store these equationsin the memory (in the form of lookup tables) and carefully perform the lookup
operations while looking for a conflict. To this end, we first compute pmax =max{pij : i ∈ [1, m], j ∈ [1, ti ]} and emax = max{eij : i ∈ [1, m], j ∈ [1, tj ]}.
Lemma 7. pmax and emax can be computed using O(n) many bit operations.
Proof. The algorithm for computing pmax and emax is a slight modification of
the standard algorithm that computes the maximum number in a list, which
sequentially goes through the list n1 , . . . , nm while keeping the maximum number
nmax in the sublist explored so far. To ensure linear-time complexity, we have to
make sure that when comparing the values of ni and nmax , we explore at most ni
bits of nmax (since nmax is possibly much larger than ni ). This is easily achievableby assuming binary representation of these numbers without redundant leading
0s, e.g., the number 5 will be represented as 101, not 0101 or 00000101. Thatway, we will only need to inspect log(ni )Pbits from nmax on the ith iteration,mwhich will give a total running time of O( i=1 log(ni )), which is linear in input
size.
⊓
⊔
Next, keep one 1-dimensional array A and one 2-dimensional array B:
A[1, . . . , pmax ]B[1, . . . , pmax ][1, . . . , emax ].

A[k] and B[k][e] will not be defined when k is not a prime number. We will use
A[k] as a flag indicating whether some equation of the form x ≡ z (mod k e )has been visited, in which case A[k] will contain (z, e). In this case, we will use′
B[k][e′ ] (with e′ ≤ e) to store the value of z mod k e .
We now elaborate how A and B are used when iterating over the equationsin the system. Sequentially go through each system (Ei ) of equations. For eachei ∈ [1, m], sequentially go through each equation x ≡ zij (mod pijij ), for eachj ∈ [1, ti ], and check if A[pij ] is defined. If it is not defined, set A[pij ] := (zij , eij )and compute B[pij ][l] = zij mod pl for each l ∈ [1, eij ]. If it is defined (say,A[pij ] = (z, e)), then we analyse the constraints x ≡ z (mod peij ) and x ≡ zije(mod pijij ) simultaneously. We compare e and eij resulting in three cases:
Case 1. e = eij . In this case, make sure that z = zij otherwise the two equations(and, hence, the entire system) cannot be satisfied simultaneously.
Case 2. e < eij . In this case, make sure that zij ≡ z (mod peij ) (otherwise,
unsatisfiable) and assign A[pij ] := (zij , eij ). For each l ∈ [1, eij ], update
B[pij ][l] := zij mod plij .
eCase 3. e > eij . In this case, make sure that zij ≡ z (mod pijij ) (otherwise,
unsatisfiable).
We now analyse the running time of this final step (i.e. when scanning throughthe subsystem (Ei )). To this end, we measure the time it takes to process eacheequation x ≡ zij (mod pijij ). There are two cases, which we will analyse in turn.

(Case I): when A[pij ] is not defined. In this case, setting A[pij ] takes constantetime, while setting B[pij ][l] for all l ∈ [1, eij ] takes O(eij × (log zij + log pijij )2 )since computing a mod b can be done in time quadratic in log(a) + log(b). Sinceeij ≤ log Ni and zij , pij ≤ Ni , this expression can be simplified to O(log Ni ×log2 (zij Ni pij )) = O(log3 Ni ).
(Case II): when A[pij ] is already defined, e.g., A[pij ] = (z, e). In this case,we will compare the values of e and eij . To ensure linear-time complexity, we
will make sure that at most log(eij ) bits from e are read by using the trick fromthe proof of Lemma 7. For Case 1, we will need extra O(log zij ) = O(log Ni )time steps. For Case 2, we have 0 ≤ z ≤ peij and computing zij mod peij canbe done in time O(log2 Ni ) as before. Updating B[pij ][l] for all l ∈ [1, eij ] takes
O(log3 Ni ) as in the previous paragraph. For Case 3, since e > eij , we may accessethe value of z mod pijij from B[pij ][eij ] in constant time and compare this withe
the value of zij . Since z ∈ [0, pijij ), this takes time O(log Ni ).
In summary, either case takes time at most O(log3 Ni ). Therefore,
accountPti
ing for the entire subsystem (Ei ), the algorithm incurs O( j=1
log3 Ni ) =O(log4 Ni ) time steps. Hence,
for all of the subsystems Ei (i ∈ [1, m])
Paccounting
4
the algorithm takes time O( mlog
N),i which is linear in the size of the input.
i=1
This completes the proof of Theorem 3.
Remark 3. The purpose of the 2-dimensional array B above is to avoid superlinear
Vm time complexity for Case 3. We can imagine a system of linear equations
i=1 x ≡ ai (mod bi ), where a1 and b1 are substantially larger than the otherai ’s and bi ’s (i ∈ [2, m]). In this case, without the lookup table B, checking
whether ai ≡ a1 (mod bi ) in Case 3 will require the algorithm to inspect theentire value of a1 , which prevents us from bounding the time complexity in termsof ai and will yield a superlinear time complexity for our algorithm.

6

Future work

We mention several future research avenues. Firstly, can we extend polynomialsolvability to any fixed number k ∈ Z>0 of group generators? The polynomialtime reduction in [10] from the graph isomorphism problem to the orbit problem
requires an unbounded number of generators. In addition, the generalisation of
the orbit problem over rational matrices to any fixed number k of matrices
viewed as generators of (semi)groups is undecidable even when k = 3, 4, though
results on polynomial-time solvability (hence, decidability) exist when the matrices commute (see [2] and references therein). So, polynomial-time solvability
does not follow from the corresponding problem over matrices. The second problem concerns the constructive orbit problem over cyclic groups. Due to the lackof a target configuration w ∈ Γ n , our technique does not seem to apply directlyin this case. In particular, we cannot simply use w ∈ Γ n that is derived from the
input configuration v ∈ Γ n by separately finding the lexicographically minimum
parts for each cycle in the given permutation, since this might render the systemof equations insoluble.

References
1. http://oeis.org/A002110. Primorial Numbers (The On-Line Encyclopedia ofInteger Sequences).
2. L. Babai, R. Beals, J.-Y. Cai, G. Ivanyos, and E. M. Luks. Multiplicative equations
over commuting matrices. In SODA, pages 498–507, 1996.
3. L. Babai and E. M. Luks. Canonical labeling of graphs. In STOC, pages 171–183,
1983.
4. E. Bach and J. Shallit. Algorithmic Number Theory, volume 1 of Foundations ofComputing. The MIT Press, 1996.
5. A. Bostan, P. Gaudry, and É. Schost. Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier-Manin Operator.
SIAM J. Comput., 36(6):1777–1806, 2007.
6. R. A. Brualdi. Combinatorial matrix classes. Encyclopedia of Mathematics and
Its Applications 108. Cambridge University Press, 2006.
7. P. J. Cameron. Permutation Groups. London Mathematical Society Student Texts.
Cambridge University Press, 1999.
8. M. Chrobak. Finite automata and unary languages. Theor. Comput. Sci.,
47(3):149–158, 1986.
9. E. M. Clarke, E. A. Emerson, S. Jha, and A. P. Sistla. Symmetry reductions
inmodel checking. In CAV, pages 147–158, 1998.
10. E. M. Clarke, S. Jha, R. Enders, and T. Filkorn. Exploiting symmetry in temporal
logic model checking. Formal Methods in System Design, 9(1/2):77–104, 1996.
11. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
12. E. Costa and D. Harvey. Faster deterministic integer factorization. CoRR,
abs/1201.2116, 2012.
13. A. F. Donaldson and A. Miller. On the constructive orbit problem. Ann. Math.
Artif. Intell., 57(1):1–35, 2009.
14. E. A. Emerson and A. P. Sistla. Symmetry and model checking. Formal Methods
in System Design, 9(1/2):105–131, 1996.
15. P. Erdös and R. L. Graham. On a linear diophantine problem of Frobenius. Acta
Arithm., 21:399–408, 1972.
16. S. Göller, R. Mayr, and A. W. To. On the computational complexity of verifying
one-counter processes. In LICS, pages 235–244, 2009.
17. G. H. Hardy and E. M. Wright. An Introduction to The Theory of Numbers. OUP
Oxford, 6 edition, 2008.
18. C. N. Ip and D. L. Dill. Better verification through symmetry. Formal Methods in
System Design, 9(1/2):41–75, 1996.
19. R. Kannan and R. J. Lipton. Polynomial-time algorithm for the orbit problem. J.
ACM, 33(4):808–821, 1986.
20. R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms.
Addison-Wesley Professional, 2 edition, 2013.
21. L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time:
Preliminary report. In STOC, pages 1–9, 1973.
22. A. W. To. Unary finite automata vs. arithmetic progressions. Inf. Process. Lett.,
109(17):1010–1014, 2009.
23. T. Wahl and A. F. Donaldson. Replication and abstraction: Symmetry in automated formal verification. Symmetry, 2:799–847, 2010.