A Strong Generating Test and Short Presentations for Permutation Groups

Gene Cooperman^{∗}x and Larry Finkelstein^{†}

College of Computer Science Northeastern University 360 Huntington Ave. Boston, Mass. 02115

∗ The work of this author was supported in part by the National Science Foundation under grant number CCR-8903952. † The work of this author was supported in part by the National Science Foundation under grant numbers DCR-8603293 and CCR-8903952.

Abstract

The group membership problem for permutation groups is perhaps the most important problem of computational group theory. Solution of this problem seems to depend intrinsically on constructing a strong generating set. Until now, recognizing if a set of generators is strong has been thought to be as hard as constructing a strong generating set from an arbitrary generating set. This paper shows how to verify a strong generating set in O(n^{4}) time, where n is the size of the set on which the group acts. This is faster than the best known algorithms in the literature. The work also leads to related algorithms for discovering all orbit information contained in an arbitrary set of generators S in O(n|S| + n log n) time, and, if S is strong, for finding a presentation with no more than |S|(n − 1) relations. Refinements in the analysis are given for the case in which a small base exists.

1. Introduction.

Let G be a permutation group acting on an n-element set Ω and let G be specified by a list S of generating permutations. A fundamental issue in many computational group theory algorithms, as well as in applications, is deciding if S is a strong generating set. If S has this property, then it is possible to efficiently perform computations such as testing membership of arbitrary permutations in G.

Sims (1971), gave the first efficient algorithm for constructing a strong generating. A good description of Sims’ original idea together with a discussion of implementation issues is given by Butler & Cannon (1982). Other interesting versions which are variations of Sims’ original method are given by Leon (1980), Knuth (1981), and Jerrum (1986). A novel approach due to Babai et al. (1988) has worst case asymptotic running time of O(n^{4} log^{c}(n)) which appears to be the best so far presented, but has not yet been fully implemented.

Sims’ idea is to use the original generating set S to construct a data structure for computing a family U of coset representatives for the subgroups in the point stabilizer sequence of G (relative to a fixed ordering of Ω), which are implied by the generators of S. The algorithm then attempts to discover if U is complete or, equivalently, if S is a strong generating set by attempting to express certain elements g ∈ G, known as Schreier generators, as a product of elements of U of the form

g = u_{i_{k}}u_{i_{k−1}} ⋯ u_{i_{1}}

where u_{i_{j}} ∈ U, u_{i_{j}} fixes the first i_{j} − 1 points of Ω, and u_{i_{j}} moves the i_{j}^{th} point. In this case, we say that g factors through U. If each Schreier generator factors through U, then U is complete. Otherwise, additional generators are added to S, U is updated to reflect the change in S, and new Schreier generators are checked to see whether they factor through U. Usually, U will be complete after only a few additional generators are added to S. However, this can not be assured until one has checked that each Schreier generator can be factored. This checking phase dominates the running time.

Our first result, Theorem 4.3, is a test for whether S is a strong generating set. If S^{(i)} is the subset of S which fixes the first i − 1 points of Ω, and m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|, then our test takes time O(mn|S|+mn^{2} min(m log(n), n−1)). In particular, since m ≤ n−1, our test takes time O(n^{4}). This represents an improvement on the worst case performance for existing tests, which usually require as much time as to construct a strong generating set.

In order to briefly describe the key idea, first let U be a family of coset representatives implied by S for the subgroups in the point stabilizer sequence for G. A traditional test involves checking if each of the O(|S|n^{2}) Schreier generators factors through U. Since factoring requires O(n^{2}) time, this would realize a test in O(|S|n^{4}) time. The novelty of our approach, is the introduction of an alternative set of O(|S|n) generators, called basic generators which can be used in the same way for testing if S is a strong generating set. The reduction in the size of the test set of generators by a factor of O(n) leads to a corresponding reduction in the running time for the test.

Section 3 contains the heart of the proof. It shows that if each basic generator factors through U, then any element of G factors through U as well. This can be proven by purely combinatorial techniques on an abstract group, H, generated by Γ. A factorization of a basic generator yields an equation in G, with the basic generator on the left, and an equivalent factored word on the right. The basic generators can be expressed as words in Γ, and the equivalent factored words can be expressed in terms of coset representatives, each of which may also be expressed as words in Γ. Thus the factorization equations determine a congruence relation on words in Γ. Theorem 3.1 shows, under certain technical hypotheses, that all elements of this abstract group are congruent to factored words.

There is a fundamental connection between building a membership algorithm for permutation groups and deriving a presentation for these groups. The ability to express each element of G in a unique factored form leads fairly directly to a presentation for G. Conversely, some of the more interesting membership algorithms such as the Schreier-Todd-Coxeter-Sims algorithm (Leon, 1980) and the Babai-Luks-Seress algorithm (Babai et al., 1988) explicitly use presentations to incrementally construct a data structure for testing group membership. The approach of this paper toward constructing presentations should be contrasted with the approach of Cannon (1973). Cannon usually finds shorter presentations than those of this paper, but no theoretical bounds are given on the number of relations, and the time for Cannon to compute the presentation is usually longer.

Our second result, Theorem 4.4 and Corollary 4.5, describes a method for constructing short presentations. If S is a strong generating set for G, then we are able to give a presentation for G using |S| generators and (n − 1)|S| relations. Since we can always choose S such that |S| ≤ n − 1, this implies that every permutation group on n letters has a presentation with at most n − 1 generators and (n − 1)^{2} relations. Furthermore, if G has a base of size m, then we can choose S such that |S| ≤ min(n − 1, m log(n)). This represents an improvement over the Babai-Luks-Seress algorithm which can be used to construct a presentation with O(n^{2} log^{c}(n)) relations.

Our third result, presented in section 2, is an algorithm for the construction of a primitive data structure which in turn can be used for the fast computation of two important data structures for storing a family U of coset representatives implied by S for the subgroups of the point stabilizer chain of G. These are the Schreier vector data structure (Sims, 1971) and the labelled branching data structure (Jerrum, 1986). Our algorithm constructs this new data structure in time O(|S|n) using O(|S|n) space. Furthermore, our algorithm returns a subset S′ of S so that U can be derived from S′ as well as S. From there, one can create a Schreier vector data structure in the same O(|S|n), allowing cosets to be accessed in time O(n^{2}) using O(|S|n) storage, or else one can create a labelled branching in time O(n^{2}), allowing cosets to be accessed in time O(n), but using O(n^{2}) storage. An interesting byproduct, is that if it is known beforehand that S is a strong generating set, then we can construct in time O(|S|n), a subset S′ of S which is a strong generating set as well, and which satisfies |S′| ≤ min(n − 1, log |G|).

2. Group Membership Data Structures for Point Stabilizer Sequences.

Let G be a permutation group acting on an n-element set Ω and let α = (α_{1}, α_{2}, …, α_{n}) be an arbitrary ordering of the points of Ω. Let G^{(1)} = G and let G^{(i)}, 1 < i ≤ n, be the subgroup of G consisting of all permutations of G which fixes each of the points α_{1}, α_{2}, …, α_{i−1}. Then the sequence

G = G^{(1)} ⊇ G^{(2)} ⋯ ⊇ G^{(n)} = {e}

is called the point stabilizer sequence of G relative to α. A generating set S for G is a strong generating set if

⟨G^{(i)} ∩ S⟩ = G^{(i)}, 1 ≤ i ≤ n − 1.

For each i, 1 ≤ i ≤ n − 1, let U^{(i)} be a set of elements of G^{(i)} which belong to different cosets of G^{(i+1)}. The set

U = ∪_{i=1}^{n−1}U^{(i)}

is called a family of coset representatives for the point stabilizer sequence of G relative to α. The associated cosets will be referred to as cosets for the point stabilizer sequence. Each set U^{(i)} is in a 1-1 correspondence with a subset of points in the orbit of α_{i} under G^{(i)}, denoted α_{i}^{G^{(i)}}, in the sense that each element of U^{(i)} maps α_{i} to a distinct point of α_{i}^{G^{(i)}}. U is said to be complete if U^{(i)} is a complete set of coset representatives for G^{(i+1)} in G^{(i)} for each i, 1 ≤ i ≤ n − 1. We will always assume that each U^{(i)} contains the identity element.

For each family of coset representatives U there is a uniquely defined function

μ: {(i, j): 1 ≤ i ≤ j ≤ n} → G ∪ {NIL}

dependant on U, with the property that μ(i, i) is the identity element for all i and for i < j, μ(i, j) = NIL or μ(i, j) is an element of U^{(i)} which moves α_{i} to α_{j}.

Given g ∈ Sym(Ω), a fundamental procedure in computational group theory is to attempt to factor g as a unique product of non-identity elements of U in the form,

g = μ(i_{k}, j_{k}) ⋯ μ(i_{2}, j_{2})μ(i_{1}, j_{1}),

where i_{k} > ⋯ > i_{2} > i_{1}. If g can be written in this form, then we say that g factors through U.

Procedure Factor. Input: An element g ∈ S_{n} and a family of coset representatives U for the point stabilizer sequence relative to an ordering α for G. Output: TRUE if g factors through U and FALSE otherwise.

Initialize h to g

For i ← 1 to n − 1 do

Let j be such that α_{j} = α_{i}^{h}
If α_{j} ≠ α_{i} then

If μ(i, j) ≠ NIL then

Set h ← hμ(i, j)^{−1} Else return(FALSE)

Return(TRUE)

If U is complete, then Factor returns true if and only if g ∈ G. This provides an effective membership test.

It is evident from this discussion that it is crucial to have an efficient method for representing a family of coset representatives for G. Several interesting methods have emerged over the last two decades which represent a balance in the use of time and space. The least space efficient method is to store the family of coset representatives in an n × n matrix in which the (i, j) entry is set either to an element of U^{(i)} which moves α_{i} to α_{j} or to NIL if no such element exists. In this case, O(n^{2}) permutations are stored, but a given element of U can be recovered in constant time. In the case where G has a small base, the most space efficient method in practice is the Schreier vector data structure due to Sims (1971). This data structure stores words (or equivalently, pointers) in the generators. However, in this case, the algorithm used to construct a specific coset representative may require as many as n − 1 multiplies in the worst case. An interesting alternative was described by Jerrum (1986) and will be referred to as a labelled branching.

One can easily conceptualize the Schreier vector data structure for G as a sequence of directed labelled trees, denoted Schreier(i), 1 ≤ i ≤ n − 1, rooted at i. The nodes of Schreier(i) are the indices j such that α_{j} is in the orbit α_{i}^{G^{(i)}} and whose edges are of the form (j, k) with label s ∈ S ∩ G^{(i)} where α_{j}^{s} = α_{k}. Given j ∈ Schreier(i), one can construct a coset representative p ∈ G^{(i)} which moves α_{i} to α_{j} by simply taking the product of the edge labels along the path from i to j. A good description of implementation issues for this data structure is given in Butler & Cannon (1982).

Formally, a branching on Ω is a directed forest with vertices 1, …, n. A branching B is said to be a labelled branching for G relative to α, if each edge (i, j) is labelled by a permutation σ_{ij} so that the following property holds:

(i) σ_{ij} ∈ G^{(i)} and moves α_{i} to α_{j}.

(ii) The set of edge labels of B generate G.

A labelled branching B is said to be complete if the following additional property holds:

(iii) If α_{k} is in the G^{(i)} orbit of α_{i}, then there is a path in B from i to k.

The definitions are equivalent to those of Jerrum, although Jerrum does not use the word complete, and defines the branching and labels as independent data structures.

Criterion (iii) ensures that the edge labels of B form a strong generating set for G relative to the ordering α. This means that the set of edge labels of B which fix α_{1}, α_{2}, ⋯, α_{i−1} generates G^{(i)}. Criterion (iii) further ensures that we can find representatives for all cosets of the point stabilizer sequence of G with elements of the form, σ_{i_{0}i_{1}}σ_{i_{1}i_{2}} … σ_{i_{k−1}i_{k}}, for some sequence, i_{0} < i_{1} < i_{2} < ⋯ < i_{k}. Rather than actually storing the edge labels of B, we store node labels τ[i] for each node α_{i}. We define τ[i] to be the product of the edge labels along the path from r to α_{i} where node r is the root of the subtree of B containing α_{i}. (If r = α_{i} then τ[i] is the identity.) It then follows that the product of edge labels from node α_{i} to node α_{j} may be realized as the single permutation multiply τ[i]^{−1}τ[j]. In particular, when B is complete, each coset entry for the point stabilizer sequence can be computed at the cost of one inversion and one multiplication.

These methods for representing a family of coset representatives for the point stabilizer sequence have the following features in common: they use an underlying data structure together with a simple algorithm for recovering a specific coset representative. In the algorithms to be presented, it will be convenient for us to express our ideas without reference to a specific data structure. Furthermore, in the course of attempting to construct a strong generating set, we may only know a subset of a complete family of coset representatives. With this in mind, we define a group membership data structure for G, to be an ordered pair (G, μ) where G is a data structure which is used to define a family of coset representatives U for the point stabilizer sequence of G relative to a fixed ordering α (usually not mentioned). μ is a function defined in terms of G which is consistent with the definition of μ above.

As an example of a group membership data structure, consider the pair (B, μ) where B is a labelled branching for G and μ(i, j) = τ[i]^{−1}τ[j] if there is a path in B from α_{i} to α_{j} and NIL otherwise. It is straightforward to interpret the other data structures in this form. We shall later introduce, in conjunction with our strong generating test, a group membership data structure which is a cross between the Schreier vector data structure and labelled branchings.

(G, μ) is said to be complete if G defines a complete family of coset representatives for G. In this case, the set of points {α_{i}: ∃j, j > i, μ(i, j) ≠ NIL} forms a base for G. A base has the property that only the identity of G fixes each element of the base.

2.1. Fast Augmentation Algorithms.

Let S be a generating set for G. Define S^{(i)} = S ∩ G^{(i)} for 1 ≤ i ≤ n − 1. (G, μ) is fully augmented with respect to S if the following condition holds:

For each α_{j} ∈ α_{i}^{⟨S^{(i)}⟩} such that 1 ≤ i ≤ n − 1, μ(i, j) ∈ ⟨S^{(i)}⟩, and μ(i, j) = NIL otherwise.

In particular, if S is a strong generating set for G, then a group membership data structure fully augmented for S must define a complete family of coset representatives of G.

Two important issues which emerge in many permutation group algorithms are the construction of a group membership data structure (G, μ) fully augmented for S and the elimination from S of redundant generators. We say that S has redundant generators if there is a strict subset S′ of S so that (G, μ) is fully augmented for S′ as well. In this case, S and S′ have the same orbit information for the point stabilizer sequence, i.e., α_{i}^{⟨S^{(i)}⟩} = α_{i}^{⟨S^{′(i)}⟩}, 1 ≤ i ≤ n − 1 If S is a strong generating set, then S′ will also be a strong generating set. On the other hand if S is not known to be a strong generating, then there is no guarantee that S′ will even generate G.

In this section, we describe a fast algorithm for solving both problems simultaneously. We will describe a procedure Augment which has input S and returns the reduced generating set S′. Augment also returns two data structures I and parent which are used to store the orbit information for α_{i}^{⟨S^{(i)}⟩} = α_{i}^{⟨S^{′(i)}⟩}, 1 ≤ i ≤ n − 1. Once I and parent have been constructed, it will be possible to efficiently create a labelled branching and Schreier vector data structure. This is accomplished in Procedures Build-Branch and Build-Schreier-Vector which are described in sections 2.1.2 and 2.1.3 respectively.

Our main result can be summarized in the following theorem.

Theorem 2.1. Let S be a generating set for G and let S′ be the subset of S returned by Augment. Let m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|.

(i) If S is a strong generating set, then S′ is as well and |S′| ≤ min(n − 1, log(|G|)).

(ii) A Schreier vector data structure fully augmented for both S and S′ can be constructed in time O(|S|n + n log(n)) using O(|S|n) space.

(iii) A labelled branching fully augmented for both S and S′ can be constructed in time O(|S|n+n^{2}) using O(|S|n + n^{2}) space.

The following result is an immediate corollary to Theorem 2.1(i) and the fact that log(|G|) = log ∏_{i} |U^{(i)}| = ∑_{i} log |U^{(i)}| ≤ m log(n), when U is complete. It will be of use in the strong generating

test.

Corollary 2.2. If m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|, then either (i) There exists a subset S′ of S so that |S′| ≤ min(n − 1, m log(n)) and both S′ and S generate

the same orbit information for the point stabilizer sequence, or

(ii) S is not a strong generating set.

2.2. Procedure Augment.

For simplicity, assume that α is the identity permutation for the remainder of Section 2. The two important data structures created by Procedure Augment are I and parent. I is an acyclic (undirected) graph with each edge {i, j} labelled by two elements: an element σ_{ij} ∈ S ∪ S^{−1} which moves i to j and σ_{ji} = σ_{ij}^{−1}. If k = min(i, j), then we do not require that σ_{ij} ∈ ⟨S^{(k)}⟩. parent is an array of length n whose entries define the forest structure for a labelled branching fully augmented for S. The set S′ will emerge as the subset of S used to label the edges of I.

We will use two intermediate data structures, component and orbit, which are arrays of size n. The value of component is an index into the orbit array. orbit is an array whose elements are structures with the fields link, root, and members. Augment proceeds in a bottom up fashion decrementing i from n−1 downto 1. After the i^{th} iteration, the connected components of I represent the orbits of ⟨S^{(i)}⟩, orbit[component[j]].members is a linked list of the nodes in the orbit containing j and orbit[component[j]].link is a temporary link pointer used to merge orbits. For two nodes j, k ∈ Ω, orbit[component[j]] = orbit[component[k]] if and only if component[j] = component[k]. Since the orbit members are represented as linked lists, two orbits’ members can be merged in constant time. Since a node is a member of at most one orbit at any time, the total space for storing all orbit members should not exceed O(n) (assuming constant space to store one node). orbit[component[j]].root is the smallest node in the ⟨S^{(i)}⟩ orbit containing j, and the product of the edge labels along the path from orbit[component[j]].root to j represents an element of ⟨S^{(i)}⟩ which moves orbit[component[j]].root to j. In particular, since orbit[component[i]].root = i, we will be able to set parent[j] for all nodes, j > i such that parent[j] ≥ i.

Procedure Augment. Input: A generating set S for G. Output: I, parent and S′ as described. Intermediate data structures: component and orbit. Auxiliary Functions: Merge-Orbits.

[Initialize I, orbit , component and the parent array.] Initialize parent. (∀i, parent[i] ← NIL) Initialize I to a trivial labelled graph on Ω Initialize S′ ← ∅ Set component[n] ← n Set orbit[n].members ← {n}, orbit[n].root ← n For i ← n − 1 downto 1 do

Set component[i] ← i

Set orbit[i].members ← {i}, orbit[i].root ← i If S^{(i)} − S^{(i+1)} ≠ ∅ then

For j ≥ i, set orbit[j].link ← NIL For ρ ∈ S^{(i)} − S^{(i+1)} do

[Merge components of I under ρ.] For j ← i to n − 1 do

Set k ← j^{ρ}

If component[k] ≠ component[j] then [ρ is a new element of the reduced generating set.] Set S′ ← S′ ∪ {ρ} [Update parent.] If i ∈ {orbit[component[j]].root, orbit[component[k]].root} then

Let p ∈ {orbit[component[j]].root, orbit[component[k]].root} − {i} For p′ ∈ orbit[component[p]].members such that parent[p′] = NIL do

Set parent[k′] ← i in B [σ_{jk} and σ_{kj} should just point to ρ and ρ^{−1}, requiring constant time.] Add edge {j, k} to I, set σ_{jk} ← ρ and σ_{kj} ← ρ^{−1} Set orbit[component[j]].link ← orbit[component[j]].link ∪ component[k]

If S^{(i)} − S^{(i+1)} ≠ ∅, then Merge-Orbits(i) Return(S′, I, parent)

Procedure Merge-Orbits.Input: Level, i. Side Effects: I is modified so that all components with link pointer connecting them are destructively merged into a single component.

For j ← i to n − 1 do

Set closed[j] ← NIL For j ← i to n − 1 do

If closed[component[j]] = NIL then [Search through all components linked to j in time proportional to number of links] Set openset ← {component[j]} For k ∈ openset do

Set openset ← openset − {k} Set closed[k] ← j For ℓ ∈ orbit[k].link do If closed[ℓ] = NIL then

Set openset ← openset ∪ {ℓ}

For j ← i to n − 1 do

If closed[j] ≠ NIL then

[Merge component j with component closed[j]] [The union is done by connecting linked lists in constant time.] Set orbit[closed[j].members] ← orbit[closed[j].members] ∪ orbit[j].members Set orbit[j].root ← orbit[closed[j].root] [Update component.] For k ∈ orbit[j].members do

Set component[k] ← j Set orbit[j].members ← NIL

We first prove certain facts about I, parent and orbit which are necessary for the proof of Theorem 2.1. We inductively define j to be a descendant of i if j = i or if parent[j] is a descendant of i. The following result is easily seen by induction, and the proof is omitted.

Lemma 2.3. After the i^{th} iteration, but before the i − 1^{st} iteration, the following properties hold for I, B and orbit.

(i) I is acyclic.

(ii) For each j ≥ i, orbit[component[j]].root is the smallest point in the ⟨S^{(i)}⟩ orbit containing j, there is a unique path in I from orbit[component[j]].root to j, and the product of the edge labels along this path is an element of ⟨S^{′(i)}⟩ which moves orbit[component[j]].root to j.

(iii) parent[j] = i if and only if j is in orbit[component[i]].members for each k such that i < k < j, but k is not in orbit[component[i]].members.

(iv) orbit[component[j]].root = i if and only if j is a descendant of i and parent[i] = NIL.

The next result is an immediate corollary to Lemma 2.3(ii)-(iv).

Lemma 2.4. The parent array determines a forest structure which is the same as that for a labelled branching fully augmented for both S and S′.

Lemma 2.5. Augment requires O(|S|n) time and O(|S|n) space.

Proof: Only the time bound is discussed, since the space bound is clear. Each generator ρ ∈ S is applied to each point of Ω only during that iteration of i for which ρ ∈ S^{(i)} − S^{(i+1)}. Thus there are at most |S| non-trivial iterations. These |S| iterations take time O(|S|n).

Each time a new generator ρ is added to S′, the components of I are merged in order to be compatible with the action of ρ. It takes O(n) work to decide which components of I need to be merged, and each merger requires constant time to update the fields of orbit. Further, since each orbit can be merged into orbit[component[i]] at most once by a given ρ, checking orbit[component[j]].members, j ≠ i for nodes with parent set to NIL can cost at most O(n) time. Since S′ is a subset of S, the total time for Augment, aside from the time to update component is O(|S|n).

Finally, the cost of updating component over all calls to Merge-Orbits is at most O(|S|n). This is clear since Merge-Orbits is called at most |S| times, and does O(n) work.

Proof of Theorem 2.1(i) We are given that S is a strong generating set for G and must show that S′ is a strong generating set for G and |S′| ≤ min(n − 1, log(|G|)). The first assertion is an immediate consequence of Lemma 2.4.

To prove that |S′| ≤ min(n − 1, log(|G|)), first observe that S′ is enlarged in Augment, only when two orbits are merged. Hence, |S′| ≤ n − 1. It suffices, therefore to show that |S′| ≤ log(|G|).

Now

|G| = ∏_{i} |i^{G^{(i)}}|, i a base point,

implies that

log(|G|) = ∑_{i} log(|i^{G^{(i)}}|), i a base point.

Therefore our assertion can be reduced to showing that for each base point i, Augment will add at most log(|i^{G^{(i)}}|) elements of S to S′.

Consider what happens when the main for loop is considering the base point i. At the beginning of the loop, we know that ⟨S′⟩ = G^{(i+1)} and the orbit of ⟨S′⟩ which contains i consists of {i}. Since S is a strong generating set, each new element ρ ∈ S^{(i)} − S^{(i+1)} added to S′ must enlarge ⟨S′⟩ but not enlarge ⟨S′ ∩ G^{(i+1)}⟩ = ⟨S ∩ G^{(i+1)}⟩ = G^{(i+1)}. Hence |i^{⟨S′∪{ρ}⟩}| > |i^{⟨S′⟩}|. Since ⟨S′⟩ ⊆ G^{(i+1)}, |i^{⟨S′∪{ρ}⟩}| = [⟨S′ ∪ {ρ}⟩: ⟨S′⟩]|i^{⟨S′⟩}|. This implies [⟨S′ ∪ {ρ}⟩: ⟨S′⟩] > 1. However, since the index is an integer, it is at least two. Therefore, each time we add a generator to S′, we at least double the size of i^{⟨S′⟩}. Since we stop when i^{⟨S′⟩} = i^{G^{(i)}}, it follows that at most log(|i^{G^{(i)}}|) elements of S^{(i)} − S^{(i+1)} can be added to S′ as required.

Remarks. directions.

(i) If the procedure is being used as part of a strong generating test, then it can be used to immediately recognize that certain generating sets are not strong. If i^{⟨S′⟩} does not grow by an integer factor, then S can not be a strong generating set. Further, if at the ith level a newly added generator ρ ∈ S′ ∩ (S^{(i+1)} − S^{(i)}) does not merge orbit[component[i]], then S is not a strong generating set. These tests are not sufficient, since the two permutations, (1 2) and (1 2 3 4), are not a strong generating set, but would not be rejected by the above tests.

(ii) One may wish to use Procedure Augment to discover a small reduced generating set for S with the same orbit information as for S, even in the case that S is not strong. In that case, the loop for ρ ∈ S^{(i)} − S^{(i+1)} should be replaced by two successive loops. The first loop should add to S′ only those ρ that enlarge orbit[component[i]], although those ρ should continue to be used to merge all possible orbits. The second loop should add to S′ the remaining ρ that merge orbits.

2.3. Construction of a Fully Augmented Schreier Vector.

For each point i such that S^{(i)} −S^{(i+1)} ≠ ∅, Schreier(i) can be constructed by a simple breadth first search from node i using the descendants of i. We will use the array backptr and svector as in (Butler & Cannon (1982)) to describe the tree. Of course, this code would have to be executed for each point i as above.

Procedure Build-Schreier-Vector Input: I, parent, and i such that parent[i] = NIL and S^{(i)} − S^{(i+1)} ≠ ∅. Output: Schreier(i) as described by svector and backptr.

For i ← 1 to n do

Set svector[i] ← identity and backptr[i] ← −1

[Compute descendants of i.] Set descendant[i] ← TRUE For j ← i + 1 to n do

Set descendant[j] ← NIL For j ← i + 1 to n do

If parent[j] ≠ NIL and descendant[parent[j]] = TRUE then set descendant[j] ← TRUE [Use breadth first search in I to compute backptr and svector.] Set open set ← {i} For j ∈ open set do

Remove j from open set and set descendant[j] ← NIL

Let J be the set of nodes adjacent to j in I

For each k ∈ J such that descendant[k] = TRUE do

Set svector[k] ← σ_{jk}, backptr[k] ← j and add k to open set

Return(svector, backptr)

Lemma 2.6. Build-Schreier-Vector correctly computes svector and backptr for Schreier(i).

Proof: It is clear by induction that there is a path in I from i to k through j. Since i is a root node, Lemma 2.3(ii) implies that the path is unique, and svector[k] ∈ G^{(i)}. Finally, svector[k] moves j to k by definition of σ_{jk}. The correctness of backptr follows trivially by induction.

Proof of Theorem 2.1(ii).

We will show that the construction of the m Schreier vectors takes time O(mn). Recalling that m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|, it is clear that m ≤ |S|, and so the O(mn) time to construct the Schreier vectors is within the bound of O(|S|n) required to build I and parent. This will prove the result.

It is clear that initializing backptr, svector and descendant takes time O(n). The key to showing that the breadth first search takes O(n) time is the fact that I is acyclic. The sum of the sizes of the sets J computed for each node j visited is at most twice the number of edges of I. So, Schreier(i) can be built in linear time for each of the m points, i.

2.4. Construction of a Fully Augmented Labelled Branching.

We will present an algorithm which shows how to use I and parent to obtain a labelled branching B which is fully augmented for S and S′. By Lemma 2.4, parent can be used to fill in the parent fields for the nodes of B. Thus, it suffices to construct an array of permutations τ which can be used to complete the construction of B.

Procedure Build-Branching Input: I and parent. Output: A labelled branching, B, with node labels, τ. Local Variables: descendants is an array of length n.

[Set the forest structure of B according to the parent array.]

Let B be the trivial forest

Use parent to construct the parent fields for each node of B.

[Initialize τ.] For j ← 1 to n do

If parent[j] = NIL then set τ[j] ← identity For i ← n downto 1 such that (S^{(i)} − S^{(i+1)}) ≠ ∅ and parent[i] = NIL do

[Compute descendants of i.] Set descendant[i] ← TRUE For j ← i + 1 to n do

Set descendant[j] ← NIL For j ← i + 1 to n do

If parent[j] ≠ NIL and descendant[parent[j]] = TRUE then set descendant[j] ← TRUE [Use breadth first search in I to compute τ[j].] Set open set ← {i} For j ∈ open set do

Remove j from open set and set descendant[j] ← NIL

Let J be the set of nodes adjacent to j in I

For each k ∈ J such that descendant[k] = TRUE do Set τ[k] ← τ[j]σ_{jk} and add k to open set

Lemma 2.7. Build-Branching correctly computes the τ fields of B.

Proof: Let r be an arbitrary root of B, i.e. parent[r] = NIL. Then by Lemma 2.3(iv), at the end of the r^{th} iteration, the connected component R^{(r)} of I containing r consists of all nodes of B which are descendants of r. If R is the connected component containing r after I has been completely built, then R^{(r)} is a connected subgraph of R. In particular, the breadth first search used to construct τ[i] for each descendant i of r searches precisely through R^{(r)}. Thus if i is a descendant of r in B, then i is a node of R^{(r)} and the procedure will fill in τ[i] with an element which moves r to i.

It remains to show that if i and j are descendants of r, with i = parent[j] , then τ[i]^{−1}τ[j] ∈ G^{(i)}. By Lemma 2.3(ii), there are unique simple paths in I from r to i and j. Since I, and more specifically R, is acyclic, there is a unique descendant k with the property that k is the intersection of the three simple paths, from r to i, from r to j, and from i to j. If we denote by ρ_{uv} the product of the edge labels along the path from u to v in I, then it follows from the construction of τ, that τ[i] = τ[k]ρ_{ki} and τ[j] = τ[k]ρ_{kj}. Thus

τ[i]^{−1}τ[j] = (τ[k]ρ_{ki})^{−1}(τ[k]ρ_{kj}) = ρ_{ki}^{−1}ρ_{kj} = ρ_{ij}.

But ρ_{ij} ∈ G^{(i)} by Lemma 2.3(ii),(iv). Thus the entries for the τ fields of B have the correct properties.

Proof of Theorem 2.1(ii). It is clear that the construction of the τ fields for B in Build-Branching takes time O(n^{2}). Since the initial construction of I and parent takes time O(|S|n) by Lemma 2.5, it then follows that the final construction of a labelled branching fully augmented for S can be constructed in time O(|S|n + n^{2}) using the procedure Build-Branching.

3. Factorization in Monoids.

In this section, we extend the notion of factorization in permutation groups to a class of general monoids to be called path monoids. We will give sufficient conditions for a monoid in this class to be factorizable. Informally, this means that every element can be expressed by a word in “factored form”. To do this will require introduction of the concepts of path monoids and path products on a path monoid. Our results on monoids will have important implications for both a strong generating test and presentations of finite permutation groups.

A path monoid is a finitely generated monoid, H, with associated 5-tuple (Γ, n, h, U, f). Γ is a finite set of generators for H, with associated generator index map,

h: Γ → Z^{+} × Z^{+},

and maximum index, n, such that if γ ∈ Γ and h(γ) = (i, j), then 1 ≤ i < j ≤ n. We allow the possibility that h(γ) = h(γ′) for γ ≠ γ′.

Given a path monoid, H, we define a chain of submonoids,

H = H^{(1)} ⊇ H^{(2)} ⊇ ⋯ ⊇ H^{(n)} = {ϵ},

where ϵ is the identity element. This is done by setting H^{(i)} = ⟨Γ^{(i)}⟩, where

Γ^{(i)} = {γ | h(γ) = (r, s), and i ≤ r < s ≤ n}.

Considering the above chain of monoids as a formal analogue of the point stabilizer sequence for a permutation group, leads us to the generalization of a family of coset representatives for the point stabilizer sequence. The subset U ⊆ H is said to be the set of path products for the path monoid, H, with associated path product index map,

f: U → Z^{+} × Z^{+},

such that the following holds:

(i) f is one-one, and for all ρ ∈ U, if f(ρ) = (i, j) then 1 ≤ i < j ≤ n. (The ρ ∈ U will be denoted ρ_{ij}.)

(ii) If ρ_{ij} ∈ U, then ρ_{ij} ∈ H^{(i)} − H^{(i+1)} .

(iii) If ρ_{ij}, ρ_{jk} ∈ U, then there exists a path product ρ_{ik} ∈ U.

(iv) If ρ_{ik} ∈ U, ρ_{jk} ∈ U and i < j, then there exists a path product ρ_{ij} ∈ U.

Let U be the set of path products. An atomic path product is a path product ρ_{ik}, such that there is no path product ρ_{jk} with i < j < k. It is easy to show using property (iv) that for any path product, ρ_{ij}, there are atomic path products ρ_{i_{0}i_{1}}, ρ_{i_{1}i_{2}}, …, ρ_{i_{m−1}i_{m}} ∈ U with i = i_{0} and j = i_{m}. We define U^{(k)} = U ∩ (H^{(k)} − H^{(k+1)}). Hence, U^{(k)} consists of all elements of U of the form ρ_{km}, k < m. A factored element is the identity or any element of the form

ρ_{i_{k}j_{k}}ρ_{i_{k−1}j_{k−1}} … ρ_{i_{1}j_{1}}, 1 ≤ i_{1} < i_{2} … < i_{k} < n.

An element in a path monoid H is factorizable under a congruence relation ≡ if it is congruent to a factored element. By a congruence relation, we mean an equivalence relation on H satisfying the substitution axiom,

(S) If v, w, w′, x ∈ H and w ≡ w′, then vwx ≡ vw′x.

The path monoid is factorizable under ≡ if each element of H is factorizable under H.

Next, the slightly stronger hypothesis of proper factorizability is introduced. For w ∈ H, let i be the largest integer such that w ∈ H^{(i)} . w is said to properly factor if w is congruent to a factored element of H^{(i)} . Proper factorization is stronger than congruence to a general factored element of H. Since H^{(n)} = {e}, the identity element is considered to be properly factored. H is properly factorizable if each element of H can be properly factored.

Example 1.

An important example of a path monoid is a finite permutation group, G, with an associated 5-tuple (S, n, h_{G}, U^{∗}, f_{G}). S is a finite set of generators not containing the identity. The maximum index is n, the number of points on which G acts. Let h_{G}: S → Z^{+} × Z^{+} be the generator index map for G defined by h_{G}(g) = (i, j) where g ∈ G^{(i)} − G^{(i+1)} and j = i^{g}.

Let U be a family of coset representatives for the point stabilizer sequence (not necessarily complete) and let U^{∗} = U − {e}. Further, suppose i^{U^{(i)}} = i^{⟨S∩G^{(i)}⟩}. Then U^{∗} is a set of path products for G, with path product index map f_{G}: U^{∗} → Z^{+} × Z^{+} , defined by f_{G}(p) = (i, j), for p ∈ U^{∗}, p ∈ G^{(i)} and i < j = i^{p}.

Note that group equality is a congruence relation. If S is a strong generating set, then U is complete and so every element of G can be expressed as a factored element in U. In that case, G is factorizable under = and is in fact properly factorizable. Also, whenever G is factorizable under =, every element can be expressed as a word in unique factored form.

Remark. Let (G , μ) be a group membership data structure for G and let U be the family of coset representatives for the point stabilizer sequence of G defined by G. Then (G , μ) is fully augmented for S if and only if the condition i^{U^{(i)}} = i^{⟨S∩G^{(i)}⟩} is satisfied for each i, 1 ≤ i ≤ n − 1.

Example 2.

We next show how a path monoid with m generators induces a path monoid structure on the free monoid on m generators. The induced structure is determined by the choice of a map between the two generating sets. Let G be a path monoid with 5-tuple (S, n, h_{G}, U, f_{G}). Let Γ be a finite set, with one-one and onto map, η: Γ → S, and let H be the free monoid on Γ. η induces a path monoid structure on H with associated 5-tuple (Γ, n, h_{H}, U, f_{H}). h_{H} is a generator index map, h_{H}: Γ → Z^{+} × Z^{+} , such that h_{H} = h_{G} ∘ η. The maximum index, n, is the same for G and H. If we extend η to an epimorphism from H onto G, then η maps H^{(i)} onto G^{(i)} for 1 ≤ i ≤ n.

To define U, let p_{ij} be an arbitrary element of U ∩ (G^{(i)} − G^{(i+1)}) and let p_{ij} = s_{i_{1}}s_{i_{2}} … s_{i_{ℓ}}, where each s_{i_{k}} ∈ S ∩ G^{(i)} (otherwise condition (ii) of the definition of path products would be violated). The representation of p_{ij} in this form need not be unique, but such a representation does exist and once chosen, will remain fixed. Define U = η′(U) where η′(p_{ij}) = ρ_{ij} is defined by replacing each s_{i_{k}} in the above representation for p_{ij} by the unique element γ_{ik} = η^{−1}(s_{i_{k}}) ∈ Γ. Note that η ∘η′ is the identity map on U. Given this definition, we can then define f_{H} = f_{G} ∘η. In particular, f_{H}(ρ_{ij}) = f_{G}(p_{ij}). It is straightforward to show that conditions (ii)-(iv) of the definition of path product are satisfied for U and f_{H}. For example, (ii) follows from the fact that η maps each H^{(i)} onto G^{(i)} and that η(ρ_{ij}) = p_{ij} ∈ G^{(i)} − G^{(i+1)} .

Next, assume that G is factorizable under = and that each element of G can be written in unique form as a factored element. This, for example is the case where G is a permutation group as in Example 1. Let ≡_{H} be the congruence relation defined by x ≡_{H} y for x, y ∈ H if η(x) = η(y). Extend η′ from a map of U into H to a map of G into H by writing each g ∈ G in factored form g = p_{i_{k}j_{k}}p_{i_{k−1}j_{k−1}} … p_{i_{1}j_{1}} where i_{k} > i_{k−1} > … i_{1} and each p_{i_{ℓ}j_{ℓ}} ∈ U and then setting η′(g) = η′(p_{i_{k}j_{k}})η′(p_{i_{k−1}j_{k−1}}) … η′(p_{i_{1}j_{1}}). Clearly η′ is well defined and η′(g) is a factored element in H. In particular, for each x ∈ H, x ≡_{H} η′(η(x)) and η′(η(x)) is a factored element of H. Thus H is factorizable under ≡_{H} if G is factorizable under =. Similarly H is properly factorizable under ≡_{H} if G is properly factorizable under =.

Our main result is that, subject to certain additional conditions which will usually be satisfied in our applications, H is properly factorizable if and only if a certain set of elements, called basic generators is properly factorizable. The set of basic generators, denoted T , consists of all products of the form:

(T_{1}) ρ_{ij}γ, γ ∈ Γ^{(j+1)} , and ρ_{ij} is an atomic path product, or
(T_{2}) ρ_{ij}γ, γ ∈ Γ, h(γ) = (k, l), an atomic path product ρ_{ii_{1}} exists with i ≤ k < i_{1} , and either i_{1} = j or there exists a path product ρ_{i_{1}j}.

Remark. In fact the basic generators are precisely those words, w, on Γ such that w is not a factored word, and every proper subword of w is a factored word.

Theorem 3.1. Let H be a path monoid with 5-tuple (Γ, n, h, U, f) and let ≡ be a congruence relation in H. Assume that the following conditions hold:

(i) For every γ ∈ Γ such that h(γ) = (i, j), there is a path product ρ_{ij} ∈ U such that γ ≡ yρ_{ij} for some y ∈ H^{(i+1)} .

(ii) If ρ_{ij}, ρ_{jk} ∈ U, then ρ_{ij}ρ_{jk} ≡ yρ_{ik} for some y ∈ H^{(i+1)} .

(iii) If ρ_{ik}, ρ_{jk} ∈ U and i < j, then ρ_{ik} ≡ yρ_{ij}ρ_{jk} for some y ∈ H^{(i+1)} .

(iv) Each basic generator is properly factorizable, and

(v) If ρ_{ij}γ is a basic generator of the form T_{1} , then ρ_{ij}γ ≡ yρ_{ij} where y ∈ H^{(i+1)} is a factored element.

Then, H is properly factorizable under ≡.

We require three preliminary results, all of which are proved within the context of the hypotheses of Theorem 3.1. Let λ_{i}(g) be the length of the shortest word in Γ^{(i)} which equals g. If g is the identity, then λ_{i}(g) = 0 for all i. We shall refer to λ_{i}(g) as the length of g with respect to Γ^{(i)} , or the length of g where it is clear with respect to which monoid. We will also say g is shorter than h if λ_{i}(g) < λ_{i}(h). Many of the results will be proven by induction on this length.

Lemma 3.2. Let ρ_{ij} be a path product and let w ∈ H^{(j+1)} . Then ρ_{ij}w ≡ yρ_{ij}, for some y ∈ H^{(i+1)} .

Proof. Assume the lemma does not hold, and ρ_{ij} and w form a counter-example for which the difference j − i is minimal, and λ_{j+1}(w) is minimal subject to fixing i and j. We first consider the case in which ρ_{ij} is an atomic path product. The result clearly holds for λ_{j+1}(w) = 0 (w the identity). If w ∈ Γ^{(j+1)} , then ρ_{ij}w is a basic generator, and by hypothesis (v), ρ_{ij}w ≡ y′ρ_{ij}. Otherwise, let w = γw′ for γ ∈ Γ^{(j+1)} , w′ ∈ H^{(j+1)} , and λ_{j+1}(w′) = λ_{j+1}(w) − 1. Then ρ_{ij}w = ρ_{ij}γw′ ≡ y′ρ_{ij}w′ ≡ y′y′′ρ_{ij}, where y′, y′′ ∈ H^{(j+1)} . The last equivalence follows because the length of w′ is one less than that of w, and so ρ_{ij}w′ cannot be a counter-example to the lemma. The result now follows by setting y = y′y′′.

Next, consider the case in which ρ_{ij} is non-atomic, and ρ_{ij} = ρ_{ii′}ρ_{i′j} for i < i′ < j. Hypothesis (iii) yields ρ_{ij}w ≡ y′ρ_{ii′}ρ_{i′j}w for some y′ ∈ H^{(i+1)} . Since j − i′ < j − i, ρ_{i′j}w is not a counterexample, and y′ρ_{ii′}ρ_{i′j}w ≡ y′ρ_{ii′}zρ_{i′j} for z ∈ H^{(i′+1)} . Since i′ − i < j − i, ρ_{ii′}z is not a counterexample and therefore, ρ_{ii′}z ≡ z′ρ_{ii′}, for z′ ∈ H^{(i+1)} . Finally, using hypothesis (ii), we have ρ_{ij}w ≡ y′z′ρ_{ii′}ρ_{i′j} ≡ y′z′z′′ρ_{ij} for some v′ ∈ H^{(i+1)} . The result now follows by setting y = y′z′z′′.

Lemma 3.3. Given a path product ρ_{ij} and generator γ for H with h(γ) = (j, k), there exist y ∈ H^{(i+1)} and path product, ρ_{ik}, such that ρ_{ij}γ ≡ yρ_{ik}.

Proof. There is a w ∈ H^{(j+1)} ⊆ H^{(i+1)} and w′, w′′ ∈ H^{(i+1)} such that ρ_{ij}γ ≡ ρ_{ij}wρ_{jk} ≡ w′ρ_{ij}ρ_{jk} ≡ w′w′′ρ_{ik}. The three steps follow respectively from hypothesis (i), Lemma 3.2, and hypothesis (ii). The result follows by setting y = w′w′′.

The next result is the key to the proof of Theorem 3.1.

Lemma 3.4. Let ρ_{ij} ∈ U and w ∈ H^{(i)} . Then ρ_{ij}w ≡ yρ, where y ∈ H^{(i+1)} and either ρ is the identity or ρ = ρ_{ip} for some path product ρ_{ip} ∈ U.

Proof. The proof is by induction on the length of w. If λ_{i}(w) = 0 (w is the identity) then the result is clearly true. Assume therefore that λ_{i}(w) > 0 and that the result is true for w̃ ∈ H^{(i)} such that λ_{i}(w̃) < λ_{i}(w). Set w = γw′, where γ ∈ Γ^{(i)} , w′ ∈ H^{(i)} and λ_{i}(w′) = λ_{i}(w) − 1.

Case I. Suppose first that h(γ) = (j, s) for some s. By Lemma 3.3, ρ_{ij}w = ρ_{ij}γw′ ≡ zρ_{is}w′ where z ∈ H^{(i+1)} . Since w′ is shorter than w, the induction hypothesis is satisfied and we may write ρ_{is}w′ ≡ z′ρ where either ρ is the identity or ρ = ρ_{ip} for some path product ρ_{ip}, and z′ ∈ H^{(i+1)} . Thus ρ_{ij}w ≡ zz′ρ where zz′ ∈ H^{(i+1)} and the result follows with y = zz′.

Case II. Next, suppose that h(γ) = (r, s) with j < r. Then by Lemma 3.2, ρ_{ij}γ ≡ zρ_{ij} for some z ∈ H^{(i+1)} . Hence ρ_{ij}w ≡ zρ_{ij}w′. Since w′ is shorter than w, the induction hypothesis is satisfied and the proof follows as in the previous case.

Case III. We may therefore assume that h(γ) = (r, s) with j > r. This is the hard case. Since w ∈ H^{(i)} by assumption, r ≥ i. As observed earlier, if ρ_{ij} is an arbitrary path product, then there exists a sequence of atomic path products ρ_{i_{0}i_{1}}, ρ_{i_{1}i_{2}}, …, ρ_{i_{m−1}i_{m}} ∈ U with i = i_{0} and j = i_{m}. Since i ≤ r < j, there exists a unique index i_{p} such that i_{p} ≤ r < i_{p+1} . Set q = i_{p}. Then the path product ρ_{qj} exists (by a simple consequence of the axioms for path products) and so ρ_{qj}γ is a basic generator of type T_{2} . If i < q, then by hypothesis (iii), ρ_{ij} ≡ v′ρ_{iq}ρ_{qj} for some v′ ∈ H^{(i+1)} . Otherwise, i = q. We can combine both cases by writing

ρ_{ij}γw′ ≡ v′ρ′ρ_{qj}γw′,

where either ρ′ = ρ_{iq} ∈ U, or ρ′ is the identity in the case that i = q. Since basic generators properly factor by hypothesis (iv), ρ_{qj}γ ≡ y′ρ′′ where either y′ρ′′ is the identity or, for some q′ ≥ q, ρ′′ = ρ_{q′j′} and y′ is a factored element in H^{(q′+1)} . Hence

ρ_{ij}γw′ ≡ v′ρ′y′ρ′′w′.

If ρ′ or ρ′′ is the identity, the proof can be completed as follows. If ρ′ and ρ′′ are both the identity, then ρ_{ij}γ ≡ v′y′w′, v′y′ ∈ H^{(i+1)} . If w′ ∈ H^{(i+1)} , then the result follows. Otherwise, w′ has the form w′ = uγ′u′, where u ∈ H^{(i+1)} , γ′ ∈ Γ^{(i)} − Γ^{(i+1)} , and u′ ∈ H^{(i)} satisfies λ_{i}(u′) < λ_{i}(w′) < λ_{i}(w). By hypothesis (i), we may write w′ ≡ u′′ρ_{ij_{1}}u′ with u′′ ∈ H^{(i+1)} . The induction hypothesis applies to ρ_{ij_{1}}u′ and the proof may be completed as before. If ρ′ is the identity and ρ′′ = ρ_{q′j′}, q < q′, then ρ_{ij}γw′ ≡ v′y′ρ′_{q′j′}w′ ≡ yw′, where y′ ∈ H^{(i+1)} and the proof follows as in the preceding case. Finally, if ρ′ = ρ_{iq} and ρ′′ is the identity, then ρ_{ij}γw′ ≡ v′ρ_{iq}y′w′. The proof then follows as in previous cases.

Thus we may assume that both ρ′ and ρ′′ are not the identity, and so

ρ_{ij}γw′ ≡ v′ρ_{iq}y′ρ_{q′j′}w′,

where q ≤ q′ and y′ ∈ H^{(q′+1)} . It follows from Lemma 3.2, that ρ_{iq}y′ ≡ y′′ρ_{iq} where y′′ ∈ H^{(i+1)} and therefore,

ρ_{ij}γw′ ≡ v′y′′ρ_{iq}ρ_{q′j′}w′.

If q = q′, then by hypothesis (ii), we may concatenate the path products to obtain

ρ_{ij}γw′ ≡ v′y′′v′′ρ_{ij′}w′

for v′′ ∈ H^{(i+1)} . Otherwise, q < q′ and by Lemma 3.2, ρ_{iq}ρ_{q′j′} ≡ y′′′ρ_{iq} which yields

ρ_{ij}γw′ ≡ v′y′′y′′′ρ_{iq}w′

for y′′′ ∈ H^{(i+1)} . In either of the above instances, we may write

ρ_{ij}γw′ ≡ zρ_{ip}w′

where z ∈ H^{(i+1)} . Since, w′ is shorter than w = γ_{rs}w′, the induction hypothesis is satisfied and we may complete the proof as before.

Proof of Theorem 3.1. We will prove the result by induction on H^{(i+1)} as i goes from n − 1 down to 0. In the base case, H^{(n)} contains only the identity and the result clearly holds.

Let 0 ≤ i < n and assume that all elements of H^{(i+1)} can be properly factored. We will show that an arbitrary element w of H^{(i)} − H^{(i+1)} can be properly factored.

Let w = w′γw′′ for w′ ∈ H^{(i+1)} , γ ∈ Γ^{(i)} − Γ^{(i+1)} , and w′′ ∈ H^{(i)} . By hypothesis (i), γ ≡ yρ_{ik} for some y ∈ H^{(i+1)} . Hence, w ≡ w′yρ_{ik}w′′. By Lemma 3.4, ρ_{ik}w′′ ≡ y′ρ_{mp} for y′ ∈ H^{(i+1)} and m ≥ i (or ρ_{mp} the identity). So, w ≡ w′yy′ρ_{mp}. If m > i or ρ_{mp} is the identity, then w′yy′ρ_{mp} ∈ H^{(i+1)} can be properly factored by induction.

If m = i, then w′yy′ ∈ H^{(i+1)} can be properly factored by the induction hypothesis, and it is congruent to a factored element, z ∈ H^{(i+1)} . Since m = i, zρ_{mp} is a factored element, and w is properly factorizable. So H is properly factorizable.

Remark. Note that our use of the congruence relation was always to replace a basic generator by a factored word. Hence, one could define a rewriting system on a free monoid, whose rewrite rules each consist of a basic generator on the left hand side, and a factored word congruent to it on the right hand side. Under this interpretation, Theorem 3.1 gives sufficient conditions for existence of a complete rewriting system in which every word of a free monoid reduces to a factored word.

We conclude this section with a bound on the number of basic generators which will be useful in section 4.

Proposition 3.5. The number of basic generators is at most (n − 1)|Γ|.

Proof. Each basic generator has the form ρ_{ij}γ, where ρ_{ij} is a path product and γ is a generator for a path monoid. We will show that each ordered pair (j, γ) uniquely determines at most one basic generator, ρ_{ij}γ. This immediately yields the bound on the number of relations, since 2 ≤ j ≤ n.

We first observe that for each j, there exists at most one atomic path product of the form ρ_{ij}. In fact, if i ≠ i′ and ρ_{i′j} is also an atomic path product, then, assume without loss of generality that i < i′. It follows from condition (iv) of the definition of path products, that there exists a path product ρ_{ii′}. This contradicts ρ_{ij} being atomic.

There are two cases to consider, according to whether or not γ ∈ Γ^{(j+1)} . If γ ∈ Γ^{(j+1)} , then any basic generator, ρ_{ij}γ, must be of type T_{1} , and ρ_{ij} must be atomic. Since for each j there is at most one atomic path product, there is at most one basic generator of the form ρ_{ij}γ.

In the second case, ρ_{ij}γ must be of type T_{2} . Let h(γ) = (k, l), and note that j > k. Assume that there are two distinct indices, i and i′, determining distinct basic generators: ρ_{ij}γ and ρ_{i′j}γ. Let ρ_{ii_{1}} be an atomic path product such that i ≤ k < i_{1} and either the path product ρ_{i_{1}j} exists or i_{1} = j. Let ρ_{i′i′_{1}} be a second atomic path product satisfying the analogous conditions.

We claim that i_{1} ≠ i′_{1} . To see, observe that if i_{1} = i′_{1} and i < i′, then condition (iv) of the definition of path products implies that the path product ρ_{ii′} exists. This contradicts the assumption that ρ_{ii_{1}} is atomic. A similar contradiction is obtained if we assume that i_{1} = i′_{1} and i′ < i.

Thus, without loss of generality, we may assume that i_{1} < i′_{1} . We first establish that the path product ρ_{i_{1}i′_{1}} exists. This is clear if i′_{1} = j. Otherwise, i_{1} < i′_{1} < j and ρ_{i_{1}j} and ρ_{i′_{1}j} are path products implies, together with condition (iv) of the definition of path products, that such a path product exists. Now, ρ_{i′i′_{1}} is atomic implies that i_{1} ≤ i′. But then, i ≤ k < i_{1} ≤ i′ contradicts the fact that i′ ≤ k as well. This concludes that there is at most one basic generator ρ_{ij}γ of type T_{2} associated with (j, γ).

4. Applications to Permutation Groups.

The main goal of this section is the application of Theorem 3.1 to obtain both a presentation for a permutation group and a criterion for deciding when a set of generators forms a strong generating set.

Let S be a generating set for the permutation group G, let (G , μ) be a group membership data structure for G, fully augmented for S, and let U be the family of coset representatives for the point stabilizer sequence of G defined by G. We can consider G as a path monoid with associated 5-tuple (S, n, h_{G}, U^{∗}, f_{G}) as in Example 1 of section 3. We do not require that U be complete. Let S^{(i)} = S ∩ G^{(i)} , 1 ≤ i ≤ n − 1. Let T = T_{1} ∪ T_{2} be the set of basic generators for U and S.

(T_{1}) p_{ij}g, g ∈ S^{(j+1)} , and p_{ij} is an atomic path product, or
(T_{2}) p_{ij}g, h(g) = (k, l), an atomic path product p_{ii_{1}} exists with i ≤ k < i_{1} , and either i_{1} = j or there exists a path product p_{i_{1}j},

where each g ∈ S and each p_{ij} ∈ U.

The conditions of Theorem 3.1 may then be expressed as follows.

(R_{1}) If g ∈ S^{(i)} − S^{(i+1)} , then there exists a coset representative p_{ij} ∈ U^{∗} such that g = wp_{ij} where w ∈ ⟨S^{(i+1)}⟩.

(R_{2}) If p_{ij}, p_{jk} ∈ U^{∗}, then p_{ij}p_{jk} = wp_{ik} where w ∈ ⟨S^{(i+1)}⟩.

(R_{3}) If p_{ik}, p_{jk} ∈ U^{∗} and i < j, then p_{ik} = wp_{ij}p_{jk} where w ∈ ⟨S^{(i+1)}⟩.

(R_{4}) Every element of T factors with respect to U.

Theorem 4.1. If hypotheses R_{1} –R_{4} hold in G, then S is a strong generating set.

Proof. Condition 5 of Theorem 3.1 follows immediately from condition R_{4} and the fact that G is a permutation group. Thus, Theorem 3.1 applies, and G is properly factorizable. Hence, all elements of G properly factor. This means that if g ∈ G^{(i)} , then g ∈ ∪_{k=i}^{n−1}U^{(k)} ⊆ ⟨S^{(i)}⟩. Thus S is a strong generating set.

It is important, from the point of view of an efficient implementation of the strong generating test, that the following property be satisfied for U.

(P) p_{ij}p_{jk} = p_{ik}, ∀p_{ij}, p_{jk} ∈ U^{∗}

If (P) holds, then conditions (R_{2}) and (R_{3}) will always be true. The main advantage in using a labelled branching for G is to take advantage of the fact that (P) will then hold for U^{∗}. In section 5 we will describe a space-efficient group membership data structure in which (P) holds for U^{∗} and which is comparable in space requirements to the Schreier vector data structure.

Strong Generating Test. Input: A generating set S for G. Output: A reduced strong generating set S′ if S is a strong generating set and FALSE otherwise. Let m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|.

(1) Let S′ be a subset of S such that |S′| ≤ min(n−1, m log(n)) and both S′ and S generate the same orbit information for the point stabilizer sequence. If such a subset S′ does not exist return FALSE. (Procedure Augment is an efficient way to either find such an S′ or conclude that no such subset exists.)

(2) Build a labelled branching B which is fully augmented for S′ and let U^{∗} be the set of path products of B. This gives rise to the path monoid described by the 5-tuple (S′, n, h_{G}, U^{∗}, f_{G}). (Procedure Build-Branching is an efficient method for constructing B when used in conjunction with Augment.)

(3) If any element of S does not factor through U, then return FALSE. (This guarantees that S′ generates G.)

(4) If every basic generator factors through U, then return TRUE. Otherwise return FALSE. Here the basic generators are computed using the 5-tuple (S′, n, h_{G}, U^{∗}, f_{G}) for the path monoid G.

Theorem 4.2. Let G be a permutation group on an n-element set and let S be set of generating permutations for G. Let m = |{i: S^{(i)} −S^{(i+1)} ≠ ∅}|. Then it is possible to test in time O(mn|S|+ mn^{2} min(m log(n), n − 1)) if S is a strong generating set for G.

Proof: We first show that the strong generating test is correct. Step 1 is justified by Corollary 2.2. Thus either S′ can be found which satisfies the stated conditions or S is not a strong generating set. In the case where S′ is found, S is a strong generating set for G if and only if S′ is as well. In Step 3, if g ∈ S does not factor through U, then S′ is not a strong generating set for G, hence neither is S. This justifies returning FALSE at this point. Otherwise, if Step 3 succeeds, then we know that S′ generates G. Thus if Steps 1-3 succeed, then G is a path monoid with associated 5-tuple (S′, n, h_{G}, U^{∗}, f_{G}). Moreover, we know that (R_{1}) is satisfied because each g ∈ S′ factors through U, and (R_{2}) and (R_{3}) are satisfied since U^{∗} arises as the set of path products for a labelled branching. Thus, by Theorem 4.1, it suffices to test if each basic generator factors through U and this is precisely what is accomplished in Step 4.

For the purpose of computing the running time, we will assume that the Strong Generating Test succeeds. Step 1 takes time O(|S|n) by Lemma 2.5. Furthermore, if this step succeeds, then we know that |S′| ≤ min(m log(n), n − 1). It takes O(n^{2}) time to construct B using Build-Branching by Theorem 2.1(iii). Since B has m internal nodes, each call to Procedure Factor using the labelled branching data structure to store U takes time O(mn). Thus Step 3 takes time O(mn|S|). Finally, by Proposition 3.5, there are at most min(m log(n), n − 1)n basic generators. Thus testing, in Step 4, whether each factors through U takes time O(min(m log(n), n − 1)mn^{2}). The result now follows by accumulating the worst case times for each step.

Corollary 4.3. Let G be a permutation group on an n-element set and let S be set of generating permutations for G. Then it is possible to test in time O(|S|n + n^{4}) if S is a strong generating set.

Remarks.

(i) Theorem 4.2 has been used to give an algorithm for completing a labelled branching for a permutation group (Cooperman et al. 1989), which in computer experiments, runs substantially faster than Jerrum’s original algorithm (Jerrum 1986).

(ii) The set of basic generators for the the path monoid G with 5-tuple (S, n, h_{G}, U^{∗}, f_{G}) can be identified with a subset of the Schreier generators formed from the point stabilizer sequence in a natural way. For fixed i, if p_{ij} ∈ U^{(i)}, i < j and g ∈ S^{(i)} such that p_{ij}g is a basic generator, then p_{ij}g corresponds to the Schreier generator p_{ij}gp^{−1} where p ∈ U^{(i)} is the unique element which moves i to i^{p_{ij}g}.

Next, we apply Theorem 3.1 to the construction of presentations. Let G be a permutation group on an n-element set and let S be strong generating set for G and let U be a complete family of coset representatives for the point stabilizer sequence. G is a path monoid as described in Example 1 of section 3, with associated 5-tuple (S, n, h_{G}, U^{∗}, f_{G}). Let Γ be a finite set, with one-one and onto map, η: Γ → S and let H be the free monoid on Γ. Then G induces a path monoid on H, with associated 5-tuple, (Γ, n, h_{H}, U, f_{H}), as in Example 2 of section 3. Assume that η has been extended to an epimorphism from H onto G and that η′ is given as in Example 2. Then it was shown that if G is properly factorizable under =, then H is properly factorizable under the congruence relation ≡_{H} defined by x ≡_{H} y if η(x) = η(y). In this case, η′ is defined on all of G and η ∘ η′ is the identity on G.

Define w_{H}: H → H by w_{H} = η′ ∘ η. Then, as shown in Example 2, x ≡_{H} w_{H}(x) and w_{H}(x) is in factored form. Let R be the following set of equations on H with T the set of basic generators.

(R_{1} ) ∀γ ∈ Γ, γ = w_{H}(γ)

(R_{2} ) ∀ρ_{ij}, ρ_{jk} ∈ U, ρ_{ij}ρ_{jk} = w_{H}(ρ_{ik})

(R_{3} ) ∀ρ_{ik}, ρ_{jk} ∈ U, i < j, ρ_{ik} = w_{H}(ρ_{ij}ρ_{jk})

(R_{4} ) ∀τ ∈ T , τ = w_{H}(τ)

Theorem 4.4. A presentation for G is given by generators Γ and relations R.

Proof. By the definition of η and ≡_{H} in Example 2 of section 3, η can be used to define an isomorphism

\overline{η}: H/≡_{H} → G.

In particular, each ≡_{H} -class of H contains a unique factored word of H.

Let ≡_{R} be the congruence relation on H defined by closure under R and the substitution axiom. We will use Theorem 3.1 to prove that ≡_{H} and ≡_{R} are the same. First observe that ≡_{H} is a refinement of ≡_{R}, since η(x) = η(y) for each equation x = y given by R_{1} -R_{4} . In order to prove equality, it suffices to show that |H/≡_{R}| ≤ |H/≡_{H}|. This in turn will follow directly once we have shown that H is properly factorizable under ≡_{R}.

If p_{ij}g ∈ G is a basic generator of type T_{1} , then g ∈ ⟨S^{(i+1)}⟩ and p_{ij}g moves i to j. Since U is a complete family of coset representatives, G is properly factorizable, and p_{ij}g = wp_{ij}, where w ∈ G^{(i+1)} is properly factorizable. Therefore, η′(p_{ij}g) = η′(wp_{ij}) = ωρ_{ij}, where ω ∈ H^{(i+1)} is in factored form. So, R_{4} implies

(R_{5} ) ρ_{ij}γ≡_{R}ω′ρ_{ij} ∈ H^{(i)} where ρ_{ij}γ is a basic generator of type T_{1} and ω′ ∈ H^{(i+1)} is in factored form.

Since R_{1} -R_{5} correspond to conditions (i)-(v) of Theorem 3.1, it follows that H is properly factorizable under ≡_{R}. Hence, ≡_{H}= ≡_{R}.

We conclude that H/≡_{R} is isomorphic to G. Since H/≡_{H} is a group, it follows directly that H/≡_{R} is isomorphic to the finitely presented group given by generators Γ and relations R. This completes the proof.

Corollary 4.5. If G has a base of size m, then G has a presentation at most min(n−1, m log(n)) generators and min((n − 1)^{2}, (n − 1)m log(n)) relations.

Proof. Let B be a complete labelled branching for G. By Theorem 2.1(i), there is a subset S of the set of edge labels of B which is a strong generating set for G with |S| ≤ min(n − 1, m log(n)). If we use S for our generating set for G and B to define U, then R_{1} –R_{3} are trivially true under equality in H. Thus by Theorem 4.4, there is a presentation for G with at most |S| generators and with |T | relations where T is the number of basic generators for G viewed as a path monoid with 5-tuple (S, n, h_{G}, U^{∗}, f_{G}). But |T | ≤ (n − 1)|S| by Proposition 3.5 and the result follows.

Babai et al. (1988) give a new group membership algorithm with worst case running time of O(n^{4} log^{c}(n)). As an outgrowth of their work, they are able to show that any permutation group on n-elements has a presentation with O(n^{2} log^{c}(n)) relations. Corollary 4.5 represents an improvement in their result.

5. A Space-Efficient Strong Generating Test.

In this section, we specialize the strong generating test to the case where the generating set S for G has small cardinality in comparison to the degree n. In particular, if

m = |{i: S^{(i)} − S^{(i+1)} ≠ ∅}|,

then m ≪ n.

Let (G , μ) be a group membership data structure for G which is fully augmented for S and let U be the family of coset representatives for the point stabilizer sequence of G used to construct G. As discussed in section 4, in viewing G as a path-monoid with 5-tuple (S, n, h_{G}, U^{∗}, f_{G}), an efficient implementation of the strong generating test, requires that property (P) be satisfied by U^{∗}.

(P) p_{ij}p_{jk} = p_{ik}, ∀p_{ij}, p_{jk} ∈ U^{∗}

If (P) holds, then conditions (R_{2}) and (R_{3}) of section 4, will always be true. If |S| is small, in comparison to n, then the Schreier vector data structure is an attractive alternative to a labelled branching from the point of view of saving space. However, (P) is unlikely to hold in this case, unless certain modifications are made. Thus our first step is to describe a new group membership data structure (G , μ) for which (P) holds and which requires only O(mn) storage, in comparison to O(n^{2}) storage for a labelled branching.

Let S be Schreier vector data structure for G fully augmented for S and let parent be the array which defines the graph structure for a labelled branching for G fully augmented for S. S and parent can be built using Augment and Build-Schreier-Vector, respectively. Denote by σ_{ij} an element of ⟨S^{(i)}⟩ computed from Schreier(i) which moves i to j, where j ∈ i^{⟨S^{(i)}⟩} and i < j. Let τ be the following array. Set τ[i] = NIL for each leaf node i. For each root node r, set τ[r] to the identity and then by induction, for each interior node j which is not a root, set τ[j] = τ[i]σ_{ij} where i = parent[j]. Note that τ requires only mn storage as opposed to n^{2} storage required for the labelled branching B defined in section 2.

We define the group membership data structure (G , μ) by setting G = (S , parent, τ) and using the following algorithm to evaluate μ(i, j) for i < j.

If j is a descendant of i then If j is an interior node then return(τ[i]^{−1}τ[j]) Else let k = parent[j]

If i = k then return(σ_{kj})
Else return(τ[i]^{−1}τ[k]σ_{kj})

Else return(NIL)

If the cost of computing a coset representative directly from the Schreier data structure is c, then the cost based on this hybrid structure will be c + O(n). If j is a leaf node, the cost will usually be dominated by the original cost c.

The following result is a direct consequence of Theorem 2.1 and the fact that the computation of each σ_{ij} using S takes time O(n^{2}).

Lemma 5.1. It takes O(mn^{2} +|S|n) time to construct (G , μ) and O(n^{2}) time to evaluate μ(i, j).

It is trivial to show that if U is the family of coset representatives for the point stabilizer sequence defined by (G , μ) and if G is viewed as a path monoid with associated 5-tuple