Hultman Numbers and Generalized Commuting Probability in Finite Groups

Yonah Cherniavsky Department of Mathematics Ariel University Israel

       yonah@ariel.ac.il

Avraham Goldstein

Borough of Manhattan Community College

The City University of New York

USA

avraham.goldstein.nyc@gmail.com

Vadim E. Levit Department of Computer Sciences Ariel University Israel

                                           levitv@ariel.ac.il

Robert Shwartz Department of Mathematics Ariel University Israel

                                          robertsh@ariel.ac.il

Abstract

Let G be a finite group. We investigate the distribution of the probabilities of the permutation equality

a_{1}a_{2} ⋯ a_{n−1}a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}}

as π varies over all the permutations in S_{n}. The probability

Pr_{π}(G) = Pr(a_{1}a_{2} ⋯ a_{n−1}a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}})

is identical to Pr_{1}^{ω}(G), with

ω = a_{1}a_{2} ⋯ a_{n−1}a_{n}a_{π_{n}}^{−1}a_{π_{n−1}}^{−1} ⋯ a_{π_{2}}^{−1}a_{π_{1}}^{−1},

which was defined and studied by Das and Nath. The notion of commutativity degree, or the probability of a permutation equality a_{1}a_{2} = a_{2}a_{1}, for which n = 2 and π = ⟨2 1⟩, was introduced and assessed by Erdős and Turan in 1968 and by Gustafson in 1973. Gustafson established a relation between the probability of a_{1}, a_{2} ∈ G commuting and the number of conjugacy classes in G. In this work we define several other parameters, which depend only on a certain interplay between the conjugacy classes of G, and compute probabilities of permutation equalities in terms of these parameters. It turns out that for a permutation π, the probability of its permutation equality depends only on the number c(Gr(π)) of alternating cycles in the cycle graph Gr(π) of π. The cycle graph of a permutation was introduced by Bafna and Pevzner, and the number of alternating cycles in it was introduced by Hultman. Hultman numbers are the numbers of different permutations with the same number of alternating cycles in their cycle graphs. We show that the spectrum of probabilities of permutation equalities in a generic finite group, as π varies over all the permutations in S_{n}, corresponds to partitioning n! as the sum of the corresponding Hultman numbers.

1 Introduction

Study of the (commuting probability), i.e., the probability that two random elements in a finite group G commute, is very natural. In 1968 Erdős and Turan [14] proved that

Pr(a_{1}a_{2} = a_{2}a_{1}) > \frac{log(log |G|)}{|G|}.

In the early 1970s, Dixon observed that the commuting probability is ≤ \frac{1}{12} for every finite non-Abelian simple group. (This inequality was submitted as an open problem in the Canadian Mathematical Bulletin 13 (1970), with a solution appearing in 1973.) In 1973, Gustafson [16] proved that the commuting probability is equal to \frac{k(G)}{|G|}, where k(G) is the number of conjugacy classes in G. Based on that result, Gustafson further obtained the upper bound of the commuting probability in a finite non-Abelian group to be \frac{5}{8}. Commuting probability actually attains the upper bound of \frac{5}{8} in many finite groups, including D_{8} and Q_{8}. A significant amount of work has been done in assessing the commuting probability for various special cases of finite groups. For example, Lescot [20] studied the case of dihedral groups. Clifton, Guichard, and Keef [7] studied the case of direct product of dihedral groups. Erovenko and Surg [15] studied the case of wreath products of two Abelian groups. Guralnick and Robinson [17] studied the case of non-solvable groups. Additional information on development of the subject and its applications is found in Dixon [11], Jezernik and Moravec [19], and Lescot, Nguyen, and Yang [21].

Much research concerning probabilistic aspects of finite groups has been done since the introduction of commuting probability. Many of these studies can be regarded as variations of the commuting probability problem. For instance, Erdős and Straus [13] computed the number of ordered k-tuples of elements of a group G that have pairwise commuting elements. Another example is due to Pournakia and Sobhani [24], who determined the probability of the commutator of two random group elements of G being equal to a given element of G. In another example Blackburn, Britnell, and Wildon [2] obtained the probability that two random elements of G are conjugate.

A variation of the commuting probability problem, leading to its generalization, is how to compute the number of balanced G-valued labelings on various finite graphs. Cherniavsky, Goldstein, and Levit [4, 6] computed the number of balanced G-valued labelings on both directed and undirected graphs, when the group G is Abelian. Cherniavsky, Goldstein, Levit, and Shwartz [5] considered a non non-Abelian case.

A different direction in generalization of commuting probability appears in Das and Nath [8, 22]. They studied the probability Pr_{g}^{ω}(G) of the equality

a_{1}a_{2} ⋯ a_{n−1}a_{n}a_{π_{n}}^{−1}a_{π_{n−1}}^{−1} ⋯ a_{π_{2}}^{−1}a_{π_{1}}^{−1} = g

for a fixed element g in a finite group G. The word

a_{1}a_{2} ⋯ a_{n−1}a_{n}a_{π_{n}}^{−1}a_{π_{n−1}}^{−1} ⋯ a_{π_{2}}^{−1}a_{π_{1}}^{−1},

where ω denotes the product a_{1}a_{2} ⋯ a_{n−1}a_{n} vary over all the elements of G. Nath [23] generalized the classical study of the commuting probability for which ω = a_{1}a_{2}a_{1}^{−1}a_{2}^{−1} and g = 1.

In this paper we take a slightly different approach in generalizing the commuting probability. Let

π = ⟨π_{1} π_{2} … π_{n}⟩

be a permutation in S_{n}, written in a shortened form of the two-row notation. We define Pr_{π}(G) as the permutation probability of the equality

a_{1}a_{2} ⋯ a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}}

in G. Notice that Pr_{⟨2 1⟩}(G) is just the commuting probability in G.

Notice also, that the probability

Pr_{π}(G) = Pr(a_{1}a_{2} ⋯ a_{n−1}a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}})

is identical to Pr_{1}^{ω}(G), with

ω = a_{1}a_{2} ⋯ a_{n−1}a_{n}a_{π_{n}}^{−1}a_{π_{n−1}}^{−1} ⋯ a_{π_{2}}^{−1}a_{π_{1}}^{−1},

as Das and Nath [8, 22] have defined it.

In this work we

• obtain a new description of Pr_{π}(G) in terms of non-negative integers c_{i_{1},...,i_{n};j}(G). Integer c_{i_{1},...,i_{n};j}(G) is the number of different ways in which an element from a conjugacy class Ω_{j} ⊂ G can be broken into a product of elements from the conjugacy classes Ω_{1_{1}}, …, Ω_{i_{n}} ⊂ G.

• prove that Pr_{π}(G), for a fixed finite group G, depends only on the number of alternating cycles in the cycle graph Gr(π) of the permutation π.

• show that the spectrum of permutation probabilities in a finite non-Abelian group, as π varies over all the elements of S_{n}, is the partition of n! into a sum of the Hultman numbers \underline{A164652}.

The following three theorems constitute the main finding of this paper

• Theorem 67: Let G be a finite group. Let ϕ ∈ S_{n} be a permutation whose cycle graph Gr(ϕ) contains k alternating cycles. Then

Pr_{ϕ}(G) = Pr^{n+1−k}(G) = Pr(a_{1}a_{2} ⋯ a_{n−k}a_{n+1−k} = a_{n+1−k}a_{n−k} ⋯ a_{2}a_{1}).

• Theorem 68: Let G be a finite non-Abelian group. Let ϕ and θ be two permutations in S_{n}. Then, Pr_{ϕ}(G) = Pr_{θ}(G) if and only if the number of alternating cycles in the cycle graph Gr(θ) equals the number of alternating cycles in the cycle graph of Gr(ϕ). This implies that the spectrum of permutation probabilities in a non-Abelian group G consists of exactly ⌊\frac{n}{2}⌋ + 1 different numbers, each number corresponding to its unique Hultman class of permutations in S_{n}.

• Theorem 69: Let G be a finite group. Then

Pr^{2t}(G) = Pr(a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1})

= Pr(a_{1}a_{2}a_{3}a_{4} ⋯ a_{2t−1}a_{2t} = a_{2}a_{1}a_{4}a_{3} ⋯ a_{2t}a_{2t−1})

= \frac{∑_{x_{1},x_{2},...,x_{t}∈G} |Stab. Prod_{n}(x_{1}, x_{2}, …, x_{t}))|}{|G|^{2t}}

= \frac{1}{|G|^{t}} · ∑_{i_{1},i_{2},...,i_{t},j=1}^{c(G)} \frac{|Ω_{j}| · c_{i_{1},i_{2},...,i_{t};j}^{2}(G)}{|Ω_{i_{1}}| · |Ω_{i_{2}}| · · · · · |Ω_{i_{t}}|}

1.1 Basic definitions and notation

For a natural number n, S_{n} denotes the group of all permutations of n. We usually write a permutation π ∈ S_{n} as

π = ⟨π_{1} π_{2} … π_{n}⟩,

which is commonly known as “the shortened way of the two row notation”. Sometimes, we also use the cyclic notation for a permutation π ∈ S_{n}, in which case we use parentheses and commas. Thus, for example, (θ_{1}, θ_{2}, θ_{3}) represents the cycle permutation θ_{1} ↦ θ_{2} ↦ θ_{3} ↦ θ_{1}. We refer to such cycle permutations as “cycles”.

We use G to denote a finite group. For a finite set S, we denote the size of S by |S|. Two elements g_{1}, g_{2} ∈ G are called conjugate if there exists h ∈ G such that g_{2} = h^{−1}g_{1}h. Conjugacy is an equivalence relation in G. As such, it breaks G into conjugacy classes. Let c(G) denotes The number of conjugacy classes in G. Let Ω_{1}, …, Ω_{c(G)} denotes the conjugacy classes. LetΩ(g) denotes the conjugacy class of g for g ∈ G. The centralizer C_{G}(g) of an element g ∈ G is the set of all elements of G that commute with g. Recall that for every all g ∈ G,

|G| = |Ω(g)| · |C_{G}(g)| .

Let C(G) denotes the set {Ω_{1}, …, Ω_{c(G)}} of all conjugacy classes in G. Let G′ denotes the commutator subgroup of G, which is the minimal subgroup of G containing all elements of G of the form ghg^{−1}h^{−1}, where g, h ∈ G. We use the notation h^{g} to denote g^{−1}hg. To indicate that that g, h ∈ G are conjugate in G we write g ∼ h. The center Z(G) ⊆ G is the subgroup of G, consisting of all elements h ∈ G for which h^{g} = h for all g ∈ G.

Let D_{2n} denotes the dihedral group with 2n elements, let Q_{8} denotes the multiplicative group of unit quaternions, which has 8 elements.

Definition 1. For a sequence (g_{1}, g_{2}, …, g_{n}) of n elements of G, let Stab. Prod_{n}(g_{1}, g_{2}, …, g_{n}) denotes the set of all the sequences (a_{1}, a_{2}, …, a_{n}) of n elements of G such that

a_{1}^{−1}g_{1}a_{1} · a_{2}^{−1}g_{2}a_{2} · · · · · a_{n}^{−1}g_{n}a_{n} = g_{1} · g_{2} · · · · · g_{n}.

Notice that Stab. Prod_{n}(g_{1}, g_{2}, …, g_{n}) is a generalization of the notion of the centralizer of an element g ∈ G. Indeed, Stab. Prod_{1}(g) is just C_{G}(g).

Definition 2. The nonnegative integer c_{i_{1},...,i_{n};j}(G) denotes the number of different ways of breaking a fixed element y ∈ Ω_{j}(G) into a product y = x_{1}x_{2} ⋯ x_{n} of elements x_{1} ∈ Ω_{i_{1}}(G), x_{2} ∈ Ω_{i_{2}}(G), …, x_{n} ∈ Ω_{i_{n}}(G).

The number c_{i_{1},...,i_{n};j}(G) does not depend on the choice of the element y ∈ Ω_{j}(G). Indeed, if we take some other y′ ∈ Ω_{j}(G), then there exists some g ∈ G such that y′ = gyg^{−1} and y = g^{−1}y′g. Then each product y = x_{1}x_{2} ⋯ x_{n} corresponds to the product

y′ = gyg^{−1} = (gx_{1}g^{−1}) · (gx_{2}g^{−1}) · · · · · (gx_{n}g^{−1}),

in which each x′_{t} = (gx_{t}g^{−1}) belongs to the same conjugacy class Ω_{i_{t}}(G) as x_{t}. Vice versa, each product y′ = x′_{1}x′_{2} ⋯ x′_{n} corresponds back to the product

y = g^{−1}y′g = (g^{−1}x′_{1}g) · (g^{−1}x′_{2}g) · · · · · (g^{−1}x′_{n}g).

Thus, we see that the number of such different products is the same for any y and y′ in Ω_{j}(G).

Notice that c_{i_{1},...,i_{n};j}(G) can be zero, and that c_{i;j}(G) = 1 if i = j, and c_{i;j}(G) = 0 if i ≠ j.

Definition 3. Let L_{π}(G) denotes the number of different solutions of the equation

a_{1}a_{2} ⋯ a_{n−1}a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}}

in G. Clearly, Pr_{π}(G) = \frac{L_{π}(G)}{|G|^{n}}.

Definition 4. We define Pr^{n}(G) as Pr_{⟨n n−1 ... 2 1⟩}(G).

For a permutation π ∈ S_{n} define ω(π) as a formal expression a_{1} ⋯ a_{n} · a_{π_{n}}^{−1} ⋯ a_{π_{1}}^{−1}. Then Pr_{π}(G) is identical to Pr_{1}^{ω}(G), which was defined by Das and Nath [8, 9, 22]. Similarly, Pr^{n}(G) is identical to Pr_{1}^{n}(G), as defined by Das and Nath [8, 9, 22]. For further information on calculations, properties, and estimates of Pr_{1}^{ω}(G) and Pr_{1}^{n}(G) we refer the reader to the papers of Das and Nath [8, 9, 22].

Definition 5. Let Spec_{n}(G) denotes the set of all Pr_{π}(G), as π runs over all the permutations from S_{n}.

Definition 6. A finite group G is called generic if for two permutations π, θ ∈ S_{n}, Pr_{π}(G) = Pr_{θ}(G) only if Pr_{π}(H) = Pr_{θ}(H) for every finite non-Abelian group H.

Definition 7. Let Part_{n} denotes the partition of S_{n} into subsets of permutations, for which the permutation equalities have the same probability for every finite group.

For a generic group G, there is a natural isomorphism between the sets Spec_{n}(G) and Part_{n}. We refer to Spec_{n}(G), for a generic group G, as the spectrum of permutation probabilities. Theorem 57 makes use of [10, Thm. 6.8] in order to show that every non-Abelian finite group is generic.

Definition 8. Hall [18] defined two groups G_{1} and G_{2} to be isoclinic if the following three conditions hold

• There exists an isomorphism α from G_{1}/Z(G_{1}) onto G_{2}/Z(G_{2});

• There exists an isomorphism β from the commutator subgroup G′_{1} to the commutator subgroup G′_{2};

• If α(a_{1}Z(G_{1})) = a_{2}Z(G_{2}) and α(b_{1}Z(G_{1})) = b_{2}Z(G_{2}), then

β(a_{1}^{−1}b_{1}^{−1}a_{1}b_{1}) = a_{2}^{−1}b_{2}^{−1}a_{2}b_{2}.

For example, every two Abelian groups are isoclinic. The dihedral group D_{8} and the quaternion group Q_{8} are two non-Abelian groups, which are isoclinic.

Definition 9. Buckley [3] defined two groups G_{1} and G_{2} to be weakly isoclinic if the first two conditions of Definition 8 hold. Namely, if

• There exists an isomorphism α from G_{1}/Z(G_{1}) onto G_{2}/Z(G_{2});

• There exists an isomorphism β from the commutator subgroup G′_{1} to the commutator subgroup G′_{2}.

2 Preliminaries

In the Lemmas 10 and 11 we reproduce well-known group theory results, which are fundamental for our work.

Lemma 10. For any a, b ∈ G we have ab ∼ ba.

Proof. b(ab)b^{−1} = babb^{−1} = ba.

Lemma 11. For any x and y from the same conjugacy class Ω_{i} ⊂ G, there are exactly

\frac{|G|}{|Ω_{i}|} = |C_{G}(x)| = |C_{G}(y)|

different ways to break x into a product x = ab of two elements a, b ∈ G, so that ba = y.

Proof. Since x ∼ y, there exists some b ∈ G such that bxb^{−1} = y. We define a = xb^{−1}. Thus, ab = xb^{−1}b = x and ba = bxb^{−1} = y. For each pair a′, b′ ∈ G, such that a′b′ = x, there exists a unique element g = b′b^{−1} = (a′)^{−1} a in G, such that a′ = ag^{−1} and b′ = gb. Now,

b′a′ = gbag^{−1} = gyg^{−1}.

Hence, the pairs (a′, b′) of elements in G, such that a′b′ = x and b′a′ = y, are in one-to-one correspondence with the elements g from C_{G}(Y). So, the number of pairs of elements a′, b′ ∈ G, such that a′b′ = x and b′a′ = y, is equal to |C_{G}(y)|. But

|C_{G}(y)| = \frac{|G|}{|Ω_{i}|} = |C_{G}(x)|.

The following classical result on commuting probability, which is due to Gustafson [16], follows immediately from Lemmas 10 and 11.

Theorem 12 (Gustafson). Pr^{2}(G) = Pr(a_{1}a_{2} = a_{2}a_{1}) = \frac{c(G)}{|G|}.

Proof. For each x ∈ G there are exactly \frac{|G|}{|Ω(x)|} different ways to write ab = x = ba with a, b ∈ G. Thus, for each Ω_{i} there are |G| different equations ab = x = ba with a, b ∈ G and x ∈ Ω(i). Indeed, there are |Ω(x)| different elements x in Ω_{i}, and for each choice of x, there are \frac{|G|}{|Ω(x)|} different ways to break that x into a product of commuting elements a, b ∈ G. Thus, L_{⟨2 1⟩}(G) = |G| · c(G) and

Pr^{2}(G) = \frac{|G| · c(G)}{|G|^{2}} = \frac{c(G)}{|G|}.

3 Calculation of Spec_{3}(G) and Spec_{4}(G)

We address the general case of permutational equations in the following sections. In this section we study permutational equations for permutations from S_{3} and S_{4}, which is selfcontained and will help to illustrate the general case.

Lemma 13. For any permutation π ∈ S_{n}, with its inverse π^{−1} ∈ S_{n}, the probability Pr_{π}(G) = Pr_{π^{−1}}(G).

Proof. By definition,

Pr_{π}(G) = Pr(a_{1}a_{2} ⋯ a_{n−1}a_{n} = a_{π_{1}}a_{π_{2}} ⋯ a_{π_{n−1}}a_{π_{n}})

Let b_{1} denotes a_{π_{1}}, b_{2} denotes a_{π_{2}}, …, b_{n} denotes a_{π_{n}} . Then a_{1} = b_{(π^{−1})_{1}}, a_{2} = b_{(π^{−1})_{2}}, …, a_{n} = b_{(π^{−1})_{n}}. As a_{1}, a_{2}, …, a_{n} run over all the elements of G, so do b_{1}, b_{2}, …, b_{n}. Thus,

Pr_{π^{−1}}(G) = Pr(b_{(π^{−1})_{1}}b_{(π^{−1})_{2}} ⋯ b_{(π^{−1})_{n−1}}b_{(π^{−1})_{n}} = b_{1}b_{2} ⋯ b_{n−1}b_{n}) = Pr_{π}(G).

We continue with Lemma 14, which is a particular case, in which n = 1, of a general fact observed by Das and Nath [9] that for

ω_{1} = a_{1}a_{2} ⋯ a_{2n}a_{1}^{−1}a_{2}^{−1} ⋯ a_{2n}^{−1},
ω_{2} = a_{1}a_{2} ⋯ a_{2n+1}a_{1}^{−1}a_{2}^{−1} ⋯ a_{2n+1}^{−1},

and for any g ∈ G, there is an equality Pr_{g}^{ω_{1}}(G) = Pr_{g}^{ω_{2}}(G).

Lemma 14. The probability Pr^{3}(G) = Pr_{⟨3 2 1⟩}(G) = Pr(a_{1}a_{2}a_{3} = a_{3}a_{2}a_{1}) is equal to the probability Pr^{2}(G) = Pr_{⟨2 1⟩}(G) = Pr(a_{1}a_{2} = a_{2}a_{1}) = \frac{|c(G)|}{|G|}.

Proof. For convenience, we rename a_{1} to a, a_{2} to b, and a_{3} to c. Now, from abc = cba we obtain abcb = cbab. Thus, the commutator [cb, ab] = 1. Therefore, if we choose and fix an element b ∈ G, then the other two elements a and c should be chosen in a such way that [ab, cb] = 1.

Hence, for every of choice of an element a ∈ G, we must choose an element c ∈ G in such a way that cb ∈ C_{G}(ab).

Since G is a group, the product ab, as b ∈ G is fixed and a runs over all the elements of G, produces elements x ∈ G, and each x ∈ G is produced exactly one time. Similarly, the product cb, as b ∈ G is fixed and c runs over all the elements of C_{G}(ab) · b^{−1}, produces elements y ∈ C_{G}(ab), and each element y ∈ C_{G}(ab) is produced exactly one time. Since b ∈ G runs over all the elements of G, we get

L_{⟨3 2 1⟩}(G) = |G| · ∑_{y∈G} |C_{G}(y)| = |G|^{2} · |C(G)|.

Dividing Equation 3 by |G|^{3} gives us

Pr_{⟨3 2 1⟩}(G) = \frac{|C(G)|}{|G|} = Pr_{⟨2 1⟩}(G).

We will now prove that for all five nontrivial permutations in S_{3}, their probabilities are the same. Notice that these five permutations have two alternating cycles in their cycle graphs, but the identity permutation in S_{3} has four alternating cycles in its cycle graph. A detailed explanation of cycle graphs and alternating cycles, followed by a clarification of their relevance to probabilities, will be made in Section 4.

Theorem 15. For every nontrivial π ∈ S_{3}, the probability Pr(a_{1}a_{2}a_{3} = a_{π_{1}}a_{π_{2}}a_{π_{3}}) = \frac{c(G)}{|G|}. Thus, the spectrum Spec_{3}(G) is \{\frac{c(G)}{|G|}, 1\}.

Proof. By Lemma 14, Pr(a_{1}a_{2}a_{3} = a_{3}a_{2}a_{1}) = \frac{c(G)}{|G|}. Clearly,

Pr(a_{1}a_{2}a_{3} = a_{2}a_{1}a_{3}) = Pr(a_{1}a_{2} = a_{2}a_{1}) = \frac{c(G)}{|G|}

and

Pr(a_{1}a_{2}a_{3} = a_{1}a_{3}a_{2}) = Pr(a_{2}a_{3} = a_{3}a_{2}) = \frac{c(G)}{|G|}.

To compute Pr(a_{1}a_{2}a_{3} = a_{3}a_{1}a_{2}), notice that if g denotes the product a_{1}a_{2}. Then, as a_{1} and a_{2} run over all the elements of G, their product g will also run over all the elements of G, becoming equal to every element of G exactly |G| times. Thus, the number L(a_{1}a_{2}a_{3} = a_{3}a_{1}a_{2}) of different solutions of the equation a_{1}a_{2}a_{3} = a_{3}a_{1}a_{2} in G is |G| times the number of different solutions of the equation ga_{3} = a_{3}g in G. Hence,

Pr(a_{1}a_{2}a_{3} = a_{3}a_{1}a_{2}) = \frac{|G| · |G| · c(G)}{|G|^{3}} = \frac{c(G)}{|G|}.

By Lemma 13, we get

Pr(a_{1}a_{2}a_{3} = a_{2}a_{3}a_{1}) = Pr(a_{1}a_{2}a_{3} = a_{3}a_{1}a_{2}) = \frac{c(G)}{|G|}.

Obviously, Pr(a_{1}a_{2}a_{3} = a_{1}a_{2}a_{3}) = 1.

We now investigate permutation probabilities for S_{4}.

Lemma 16. For any nontrivial permutation π ∈ S_{4}, if π_{1} = 1 or π_{4} = 4, then Pr_{π}(G) = \frac{c(G)}{|G|}.

Proof. If π_{1} = 1, then the equation a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}} is equivalent to the equation a_{2}a_{3}a_{4} = a_{π_{2}}a_{π_{3}}a_{π_{4}}. By Theorem 15, there are |G|^{2} · c(G) different equations a_{2}a_{3}a_{4} = a_{π_{2}}a_{π_{3}}a_{π_{4}} in G. Each of these equations corresponds exactly to |G| different equations of the form a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}} (since a_{1} can be any element of G). Thus L_{π}(G) = |G|^{3} · c(G) and Pr_{π}(G) = \frac{c(G)}{|G|}. The same argument, but with a_{4} instead of a_{1}, is applied for π_{4} = 4.

Lemma 17. For all nontrivial permutations π ∈ S_{4}, such that π_{i+1} = π_{i} + 1 for some 1 ≤ i ≤ 3, the probability Pr_{π}(G) = \frac{c(G)}{|G|}.

Proof. The condition π_{i+1} = π_{i} + 1 implies that the permutation π keeps two consecutive numbers π_{i} and π_{i} + 1 in their consecutive order. Such are, for example, the permutations ⟨4 3 1 2⟩, ⟨3 4 1 2⟩, ⟨2 3 4 1⟩, and ⟨4 2 3 1⟩, ⟨4 1 2 3⟩. Let g denotes the product a_{π_{i}}a_{π_{i+1}}. Then, as a_{π_{i}} and a_{π_{i+1}} run over all the elements of G, their product g also runs over all the elements of G, becoming equal to each element of G exactly |G| times. By Theorem 14, the equation a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}}, in which we change a_{π_{i}}a_{π_{i+1}}, on both sides, to g, has exactly |G|^{2} · c(G) solutions. But these solutions naturally correspond to |G| different solutions of the equation a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}}. Thus L_{π}(G) = |G|^{3} · c(G) and Pr_{π}(G) = \frac{c(G)}{|G|}.

Lemmas 16 and 17 establish that for fifteen different permutations π in S_{4}, their probabilities equal Pr_{π}(G) = \frac{c(G)}{|G|}. Notice that these fifteen permutations have exactly three alternating cycles in their cycle graphs Gr(π) (see Bafna and Pevzner [1]; Doignon and Labarre [12]). For the identity permutation, which has five alternating cycles in its cycle graph, the probability of the corresponding trivial permutation equation is 1.

The remaining eight permutations in S_{4} have one alternating cycle in their cycle graphs. We will now show that for these eight permutations, the corresponding permutations have the same probability, which, in a generic group, is different both from 1 and from \frac{c(G)}{|G|}.

Theorem 18. For any finite group G we have

Pr^{4}(G) = Pr(a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}) = Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3})

= \frac{∑_{x,y∈G} |Stab. Prod_{2}(x, y)|}{|G|^{4}} = \frac{1}{|G|^{2}} · ∑_{i,k,j=1}^{c(G)} \frac{|Ω_{j}| · c_{i,k;j}^{2}(G)}{|Ω_{i}| · |Ω_{k}|}

= \frac{1}{|G|^{2}} · ∑_{i,k,j=1}^{c(G)} \frac{|Ω_{j}| · c_{i,k;j}(G) · c_{k,i;j}(G)}{|Ω_{i}| · |Ω_{k}|}.

Proof. Notice that for any x, y ∈ G, the set Stab. Prod_{2}(x, y) of all ordered pairs (g, h) of elements of G, such that xy = g^{−1}xgh^{−1}yh, has an alternative description as the set of all the ordered pairs (g ∈ G, f^{−1} ∈ G), such that gxyf = xgfy. Indeed, by setting f = h^{−1}, the equation xy = g^{−1}xgh^{−1}yh becomes xy = g^{−1}xgfyf^{−1}. Multiplying the right by g and the left by f gives us gxyf = xgfy.

Thus, for each fixed ordered pair (x, y) of elements in G, there are exactly |Stab. Prod_{2}(x, y)| different equations gxyf = xgfy with g, h ∈ G. As x and y run over all the elements of G, we obtain that the total number of different equations gxyf = xgfy in

G is ∑_{x,y∈G} |Stab. Prod_{2}(x, y)|.

Dividing the total number of different equations gxyf = xgfy in G by |G|^{4} gives us

Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3}) = \frac{∑_{x,y∈G} |Stab. Prod_{2}(x, y)|}{|G|^{4}}.

Next, consider the equation a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}. Let x denotes the product a_{1}a_{2}, x′ denotes the product a_{2}a_{1}, y denotes the product a_{3}a_{4}, and y′ denotes the product a_{4}a_{3}. The equation a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1} becomes xy = y′x′. By Lemma 10, we have x ∼ x′ and y ∼ y′.

Now consider any x, x′, y, y′ ∈ G, such that x ∼ x′, y ∼ y′, and xy = y′x′. By Lemma 11, there are \frac{|G|}{|Ω(x)|} = |C_{G}(x)| different ways of breaking x into a product a_{1}a_{2} in such a way

that x′ = a_{2}a_{1}. Again, by Lemma 11, there are \frac{|G|}{|Ω(y)|} = |C_{G}(y)| different ways of breaking y into a product a_{3}a_{4} in such a way that y′ = a_{4}a_{3}. Thus, to each fixed equation xy = y′x′ correspond |C_{G}(x)| · |C_{G}(y)| different equations a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}.

Next, for each fixed x, y ∈ G, we count the number of different equations xy = y′x′, where x ∼ x′ and y ∼ y′. Define x′′ = (y^{−1}xy). Thus, we get an equation xy = y(y^{−1}xy) = yx′′. Now, for each equation xy = y′x′, as above, there exist some g, h ∈ G such that y′ = g^{−1}yg and x′ = h^{−1}x′′h. But, for each fixed x, y ∈ G we have |Stab. Prod_{2}(y, x′′)| different elements g, h ∈ G, such that xy = yx′′ = g^{−1}ygh^{−1}x′′h. For each fixed pair g, h ∈ G, such that yx′′ = g^{−1}ygh^{−1}x′′h, a pair g′, h′ ∈ G satisfies (g′)^{−1}yg′ = g^{−1}yg and (h′)^{−1}x′′h′ = h^{−1}x′′h, if, and only if, g′g^{−1} ∈ C_{G}(y) and h′h^{−1} ∈ C_{G}(x′′). Thus, for each fixed x, y ∈ G, there are exactly

\frac{|Stab. Prod_{2}(y, x′′)|}{|C_{G}(y)| · |C_{G}(x′′)|}

different equations xy = y′x′, in which x′ ∼ x and y′ ∼ y. But, |C_{G}(x′′)| = |C_{G}(x)|. Thus, for each fixed ordered pair (x, y) of elements of G, we have

\frac{|Stab. Prod_{2}(y, (y^{−1}xy))|}{|C_{G}(y)| · |C_{G}(x)|}

different equations xy = y′x′. As we showed above, to each of these equations correspond |C_{G}(x)| · |C_{G}(y)| different equations a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}, in which a_{1}a_{2} = x, a_{3}a_{4} = y, a_{2}a_{1} = x′, and a_{4}a_{3} = y′. Thus, to each ordered pair (x, y) of elements of G correspond |Stab. Prod_{2}(y, (y^{−1}xy))| different equations a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}, in which a_{1}a_{2} = x and a_{3}a_{4} = y.

Thus, to find Pr(a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}) we need to sum |Stab. Prod_{2}(y, (y^{−1}xy))| over all x, y ∈ G, and then divide that sum by |G|^{4}. For each fixed y, the product v = y^{−1}xy runs over all the elements of G when x runs over all the elements of G. Thus, summing |Stab. Prod2(y, (y^{−1}xy))| over all x, y ∈ G is the same as summing |Stab. Prod_{2}(y, v)| over all y, v ∈ G. Thus, we obtain

L_{⟨4 3 2 1⟩}(G) = ∑_{y,v∈G} |Stab. Prod_{2}(x, y)|,

and

Pr^{4}(G) = Pr(a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1})

= \frac{∑_{x,y∈G} |Stab. Prod_{2}(x, y)|}{|G|^{4}} = Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3}).

Now, fix an element z in some equivalence class Ω_{j} in G. For each equation xy = z = x′y′ we have exactly

|C_{G}(x)| · |C_{G}(y)| = \frac{|G|^{2}}{|Ω(x)| · |Ω(y)|}

different equations

(a_{1}a_{2})(a_{3}a_{4}) = xy = z = x′y′ = (a_{2}a_{1})(a_{4}a_{3}).

Indeed, there are |C_{G}(x)| different ways to break x into a product a_{1}a_{2} so that a_{2}a_{1} = x′, and there are |C_{G}(y)| different ways to break y into a product a_{3}a_{4} so that a_{4}a_{3} = y′.

Now, there are c_{i,k;j}(G) different ways to break z as a product xy so that x ∈ Ω_{i} and y ∈ Ω_{k}. For each of these c_{i,k;j}(G) different ways, there are c_{i,k;j}(G) different ways to break z as a product x′y′. Thus, for each ordered pair (Ω_{i}, Ω_{k}) of conjugacy classes in G, there are c_{i,k;j}^{2}(G) different equations xy = z = x′y′ with x, x′ ∈ Ω_{i} and y, y′ ∈ Ω_{k}. The number of different equations xy = z = x′y′ with x, x′ ∈ Ω_{i} and y, y′ ∈ Ω_{k} is the same for all z ∈ Ω_{j}.

Taking the sum of the number of different equations a_{1}a_{2}a_{3}a_{4} = z = a_{2}a_{1}a_{4}a_{3}, as z runs over all the elements of G, and dividing it by |G|^{4}, gives us

Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3}) = \frac{1}{|G|^{2}} · ∑_{i,k,j=1}^{c(G)} \frac{|Ω_{j}| · c_{i,k;j}^{2}(G)}{|Ω_{i}| · |Ω_{k}|}.

Finally, fix an element z in some equivalence class Ω_{j} in G. For each equation xy = z = y′x′ we have exactly

|C_{G}(x)| · |C_{G}(y)| = \frac{|G|^{2}}{|Ω(x)| · |Ω(y)|}

different equations

(a_{1}a_{2})(a_{3}a_{4}) = xy = z = y′x′ = (a_{4}a_{3})(a_{2}a_{1}).

Now, there are c_{i,k;j}(G) different ways to break z as a product xy so that x ∈ Ω_{i} and y ∈ Ω_{k}. For each of these c_{k,i;j}(G) different ways, there are c_{i,k;j}(G) different ways to break z as a product x′y′. Thus, for each ordered pair (Ω_{i}, Ω_{k}) of conjugacy classes in G, there are there are c_{i,k;j}(G) · c_{k,i;j}(G) different equations xy = z = y′x′ with x, x′ ∈ Ω_{i} and y, y′ ∈ Ω_{k}.

Taking the sum of the number of different equations a_{1}a_{2}a_{3}a_{4} = z = a_{4}a_{3}a_{2}a_{1}, as z runs over all the elements of G, and dividing it by |G|^{4}, gives us

Pr(a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1}) = \frac{1}{|G|^{2}} · ∑_{i,k,j=1}^{c(G)} \frac{|Ω_{j}| · c_{i,k;j}(G) · c_{k,i;j}(G)}{|Ω_{i}| · |Ω_{k}|}.

To study the other four permutations in S_{4}, we first prove a lemma that is a particular case of Theorem 43.

Lemma 19. Let π ∈ S_{4} be a permutation such that π_{4} + 1 = π_{3} = 2 or π_{4} + 1 = π_{3} = 3. Then the equations

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}},
a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{3}}a_{π_{4}}a_{π_{2}}

have the same number of solutions.

Proof. First, consider the case π_{4} + 1 = π_{3} = 2.

Rewrite the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{2}a_{1}

as

a_{1}a_{π_{2}}^{−1}a_{π_{2}}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{2}a_{1}.

Let a denotes a_{π_{2}}a_{2}. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{2}a_{1}

becomes

a_{1}a_{π_{2}}^{−1}aa_{3}a_{4} = a_{π_{1}}aa_{1},  (1)

in which the variable a_{π_{2}}^{−1} runs over all the elements of G, and for each fixed value of a_{π_{2}}^{−1}, the variable a runs over all the elements of G.

Rewrite the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{2}a_{1}a_{π_{2}}

as

a_{1}a_{π_{2}}a_{π_{2}}^{−1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{2}a_{1}a_{π_{2}}.

Let a denotes a_{1}a_{π_{2}}. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{2}a_{1}a_{π_{2}}

becomes

aa_{π_{2}}^{−1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{2}a,  (2)

in which the variable a_{π_{2}}^{−1} runs over all the elements of G, and for each fixed value of a_{π_{2}}^{−1}, the variable a runs over all the elements of G.

Now, Equation 1 is obtained from Equation 2 by renaming a to a_{1} and renaming a_{2} to a. Thus, they have the same number of solutions.

Finally, consider the case π_{4} + 1 = π_{3} = 3.

Rewrite the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{3}a_{2}

as

a_{1}a_{2}a_{π_{2}}^{−1}a_{π_{2}}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{3}a_{2}.

Let a denotes a_{π_{2}}a_{3}. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{3}a_{2}

becomes

a_{1}a_{2}a_{π_{2}}^{−1}aa_{4} = a_{π_{1}}aa_{2},  (3)

in which the variable a_{π_{2}}^{−1} runs over all the elements of G, and for each fixed value of a_{π_{2}}^{−1}, the variable a runs over all the elements of G.

Rewrite the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{3}a_{2}a_{π_{2}}

as

a_{1}a_{2}a_{π_{2}}a_{π_{2}}^{−1}a_{3}a_{4} = a_{π_{1}}a_{3}a_{2}a_{π_{2}}.

Let a denotes a_{2}a_{π_{2}}. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{3}a_{2}a_{π_{2}}

becomes

a_{1}aa_{π_{2}}^{−1}a_{3}a_{4} = a_{π_{1}}a_{3}a,  (4)

in which the variable a_{π_{2}}^{−1} runs over all the elements of G, and for each fixed value of a_{π_{2}}^{−1}, the variable a runs over all the elements of G.

Now, Equation 3 is obtained from Equation 4 by renaming a into a_{2} and renaming a_{3} into a. Thus, they have the same number of solutions.

The following corollary of Lemma 19 provides examples of the x−−y exchange operation, which will be introduced in Definition 33. It also illustrates the notion of the x−−y exchange orbit, which will be introduced in Definition 42, and demonstrates how the 3 − cycle of Proposition 38 works.

Corollary 20. The equations

a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1},
a_{1}a_{2}a_{3}a_{4} = a_{4}a_{2}a_{1}a_{3},
a_{1}a_{2}a_{3}a_{4} = a_{4}a_{1}a_{3}a_{2}

have the same number of solutions.

Proof. For permutation π = ⟨4 3 2 1⟩ we have π_{4} + 1 = π_{3} = 2. Thus, by Lemma 19, the permutation equation of the permutation ⟨4 2 1 3⟩ has the same number of solutions as the permutation equation of π.

For permutation θ = ⟨4 1 3 2⟩ we have π_{4} + 1 = π_{3} = 3. Thus, by Lemma 19, the permutation equation of the permutation ⟨4 3 2 1⟩ has the same number of solutions as the permutation equation of θ.

The following corollary is based on Lemma 13, since ⟨4 2 1 3⟩^{−1} = ⟨3 2 1 4⟩ and ⟨4 1 3 2⟩^{−1} = ⟨2 4 3 1⟩.

Corollary 21. (i) The equations

a_{1}a_{2}a_{3}a_{4} = a_{4}a_{2}a_{1}a_{3},
a_{1}a_{2}a_{3}a_{4} = a_{3}a_{2}a_{1}a_{4}

have the same number of solutions.

(ii) The equations

a_{1}a_{2}a_{3}a_{4} = a_{4}a_{1}a_{3}a_{2},
a_{1}a_{2}a_{3}a_{4} = a_{2}a_{4}a_{3}a_{1}

have the same number of solutions.

To study the remaining two permutation in S_{4}, we first prove the following.

Lemma 22. Let π ∈ S_{4} be a permutation such that for some i ∈ {1, 2}, π_{i} + 1 = π_{i+2} and π_{i+1} = π_{i} − 2. Let j ∈ {1, 2, 3, 4} be such an integer that pi_{j} = π_{i} − 1. Let θ ∈ S_{4} be obtained from π by interchanging π_{i} and π_{j}. Then the equations

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}},
a_{1}a_{2}a_{3}a_{4} = a_{θ_{1}}a_{θ_{2}}a_{θ_{3}}a_{θ_{4}}

have the same number of solutions.

Proof. First, for permutations in S_{4}, the only option for the integer j is a unique element in {1, 2, 3, 4}, which is different from all three integers i, i + 1, i + 2. Similarly, the only option for the value p_{i}, for π ∈ S_{4}, is 3, and for the value p_{j} is 2.

For simplicity of dealing with the indices, we will consider the cases j = 1, i = 2, and j = 4, i = 1 separately. Even though the permutation π ∈ S_{4} is uniquely determined in each of these two cases, we will use the notation π_{i} = x, π_{i+1} = y, π_{i+2} = x+1, and π_{j} = y+1. This is done to illustrate both the x − −y cyclic operation, which will be introduced in Definition 44, and the proof of the Theorem 52. Additionally, this proof, in which the x, y, x + 1, y + 1 notation is used, can be adopted for a more general case of substrings in a longer string, which is the case for certain permutations in S_{n} with n > 4. An example of a substring of that type in a longer string, for which this proof works, will be provided at the end of the proof.

First, let j = 4, i = 1. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}}

can be written as

a_{y}a_{y+1}a_{x}a_{x+1} = a_{x}a_{y}a_{x+1}a_{y+1}  (5)

Similarly, the equation

a_{1}a_{2}a_{3}a_{4} = a_{θ_{1}}a_{θ_{2}}a_{θ_{3}}a_{θ_{4}}

can be written as

a_{y}a_{y+1}a_{x}a_{x+1} = a_{y+1}a_{y}a_{x+1}a_{x}  (6)

Now, define c = a_{x}a_{x+1} and d = a_{y}a_{x}^{−1}, and insert them into Equation 5 as follows

da_{x}a_{y+1}c = a_{x}dca_{y+1}  (7)

Notice that as random variables a_{y}, a_{x}, a_{x+1} run over all the elements of G, so do random variables a_{x}, c, d. Similarly, as random variables a_{x}, c, d run over all the elements of G, so do random variables a_{y}, a_{x}, a_{x+1}. Thus, there is a one-to-one correspondence between the solutions of Equation 5 and the solutions of Equation 7. But Equation 7 is obtained from Equation 6 by renaming a_{y} to d and a_{x+1} to c. Thus, Equation 7 and Equation 6, after renaming the variables, have the same solutions.

Second, let j = 1, i = 2. Then the equation

a_{1}a_{2}a_{3}a_{4} = a_{π_{1}}a_{π_{2}}a_{π_{3}}a_{π_{4}}

can be written as

a_{y}a_{y+1}a_{x}a_{x+1} = a_{y+1}a_{x}a_{y}a_{x+1}  (8)

Similarly, the equation

a_{1}a_{2}a_{3}a_{4} = a_{θ_{1}}a_{θ_{2}}a_{θ_{3}}a_{θ_{4}}

can be written as

a_{y}a_{y+1}a_{x}a_{x+1} = a_{x}a_{y+1}a_{y}a_{x+1}  (9)

Now, define c = a_{x}a_{x+1} and d = a_{y}a_{x}^{−1}, and insert them into Equation 8 as follows

da_{x}a_{y+1}c = a_{x}a_{y+1}dc  (10)

Again, there is a one-to-one correspondence between the solutions of Equation 8 and the solutions of Equation 10, but Equation 10 is obtained from Equation 9 by renaming a_{y} to d and a_{x+1} to c. Thus, Equation 10 and Equation 9, after renaming the variables, have the same solutions.

Obviously, for our purpose in this section, the case j = 1, i = 2 is of no interest, since multiplication of Equation 8 by a_{x+1}^{−1} on the right reduces it to a permutational equation for a permutation in S_{3}. However, it illustrates how the x − −y cyclic operation works, when a_{y}a_{y+1}a_{x}a_{x+1} and a_{y+1}a_{x}a_{y}a_{x+1} are just substrings in a longer string, which is the case for certain permutations in S_{n} with n > 4. For example, the proof we provided here adapts to show that the equations a_{1}(a_{2}a_{3}a_{4}a_{5})a_{6} = a_{6}(a_{3}a_{4}a_{2}a_{5})a_{1} and a_{1}(a_{2}a_{3}a_{4}a_{5})a_{6} = a_{6}(a_{4}a_{3}a_{2}a_{5})a_{1} have the same number of solutions.

Corollary 23. (i) The equations

a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3},
a_{1}a_{2}a_{3}a_{4} = a_{3}a_{1}a_{4}a_{2}

have the same number of solutions.

(ii) The equations

a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3},
a_{1}a_{2}a_{3}a_{4} = a_{2}a_{4}a_{1}a_{3}

have the same number of solutions.

Proof. The case of j = 4, i = 1 in Lemma 22 corresponds to y = 1, y + 1 = 2, x = 3, x+1 = 4. Thus, the equations of the permutations π = ⟨3 1 4 2⟩ and θ = ⟨2 1 4 3⟩ have the same number of solutions. Specifically, Equation 5 is

a_{1}a_{2}a_{3}a_{4} = a_{3}a_{1}a_{4}a_{2}

and Equation 6 is

a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3}.

By Lemma 22, they have the same number of solutions.

Since ⟨2 4 1 3⟩ = ⟨3 1 4 2⟩^{−1}, the equations

a_{1}a_{2}a_{3}a_{4} = a_{3}a_{1}a_{4}a_{2},
a_{1}a_{2}a_{3}a_{4} = a_{2}a_{4}a_{1}a_{3}

have, by Lemma 13, the same number of solutions.

Thus, we obtain the following.

Theorem 24. The permutations

⟨4 3 2 1⟩, ⟨2 1 4 3⟩, ⟨4 2 1 3⟩, ⟨4 1 3 2⟩, ⟨3 2 1 4⟩, ⟨2 4 3 1⟩,
⟨3 1 4 2⟩, ⟨2 4 1 3⟩

in S_{4} have the same probabilities.

Proof. This theorem follows from Theorem 18 and Corollaries 20, 21, and 23.

In Theorem 57 we will show that every finite non-Abelian group is generic. Thus,

Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{3}a_{4}) ≠ Pr(a_{1}a_{2}a_{3}a_{4} = a_{4}a_{3}a_{2}a_{1})  (11)

for every finite non-Abelian group G. Since both probabilities, appearing in Equation 11, cannot be equal to 1 in a non-Abelian group, it will Imply that the spectrum of probabilities, for permutations in S_{4}, consists of three different values. But now, in the Example 25, we explicitly compute Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{3}a_{4}) = Pr^{2}(G) and Pr(a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3}) = Pr^{4}(G) for the groups G = D_{8} and G = Q_{8}. These probabilities, for both G = D_{8} and G = Q_{8}, are different. This permits us to avoid using Theorem 57 in establishing Lemma 26. In Example 58 we will perform the same calculations for the general case of Pr^{2n}(G). Results, similar to our calculations of Pr^{2}(G) and Pr^{4}(G) for G = D_{8} and G = Q_{8}, but in a much more general form and for a larger variety of groups, were obtained in [8, 22].

Example 25. Both G = D_{8} and G = Q_{8} have five conjugacy classes. Thus, Pr^{2}(G) = \frac{5}{8} for both of these groups. For both D_{8} and Q_{8}, the center consists of the identity 1 and another element c, such that c^{2} = 1. For both of these groups, the factor of the group by its center is the Abelian group K_{4} = Z_{2} × Z_{2}. This means that if for some x, y ∈ G, xy ≠ yx, then xy = cyx. Hence, the equation a_{1}a_{2}a_{3}a_{4} = a_{2}a_{1}a_{4}a_{3} is satisfied either if a_{1}a_{2} = a_{2}a_{1} and a_{3}a_{4} = a_{4}a_{3}, or if a_{1}a_{2} = ca_{2}a_{1} and a_{3}a_{4} = ca_{4}a_{3}. The first option has the probability \frac{5}{8} · \frac{5}{8} = \frac{25}{64}. The second option has the probability \frac{3}{8} · \frac{3}{8} = \frac{9}{64}. Thus, Pr^{4}(G) = \frac{25}{64} + \frac{9}{64} = \frac{17}{32}. Notice that Pr^{4}(G) < Pr^{2}(G).

Now we may conclude with the following.

Theorem 26. For a generic finite non-Abelian group G, the spectrum of permutation probabilities over S_{4} consists of only three probabilities

Spec_{4}(G) = \{1, Pr^{2}(G) = \frac{|c(G)|}{|G|}, Pr^{4}(G)\}

Notice that the calculations for G = D_{8} and G = Q_{8} show that the three probabilities belonging to Spec_{4}(G) are pairwise different for these two groups.

From the results of this section it is evident that permutational equalities of any two permutations from S_{2}, S_{3}, or S_{4} have the same probability if they have the same number of alternating cycles in their cycle graphs. Consequently, the number of different permutations, corresponding to each probability in Spec_{2}(G), Spec_{3}(G), or Spec_{4}(G), is precisely the Hultman number S_{H}(n, k), where n = 2, 3, 4 and k is the number of alternating cycles in the cycle graphs of these permutations. In the following sections we extend the observations and calculations of this section to S_{n}.

4 Probabilities of permutation equations, number of alternating cycles, and Hultman decomposition

For the information on cycle graphs, decomposition to alternating cycles, and Hultman numbers, as well as many other related definitions and notions, we refer to Doignon and Labarre [12] and the On-Line Encyclopedia of Integer Sequences [25]. Here we briefly review these notions.

Definition 27. The cycle graph Gr(ϕ) of a permutation ϕ ∈ S_{n} is the bi-colored directed graph with n + 1 vertices ϕ_{0} = 0, ϕ_{1}, …, ϕ_{n}, whose edge set consists of

• black edges ϕ_{n} → ϕ_{n−1}, ϕ_{n−1} → ϕ_{n−2}, …, ϕ_{1} → ϕ_{0}, ϕ_{0} → ϕ_{n}, and

• grey edges 0 −−→ 1, 1 −−→ 2, …, (n − 1) −−→ n, n −−→ 0.

The set of black and grey edges is decomposed in a unique way into edge-disjoint alternating cycles in which the black and the grey edges alternate. It is called the decomposition of Gr(ϕ) into alternating cycles.

Definition 28. The Hultman number S_{H}(n, k) is a nonnegative integer that counts the number of permutations in S_{n}, whose cycle graph decomposes into k alternating cycles.

Let S(1 + n) denotes the group of all permutations of the set {0, 1, 2, …, n}.

Definition 29. Let ϕ^{•} denotes the n + 1-cycle in a permutation ϕ ∈ S_{n}.

ϕ_{n} → ϕ_{n−1} → ϕ_{n−2} → ⋯ → ϕ_{1} → ϕ_{0} → ϕ_{n}

in S(1 + n), which is the n + 1-cycle, composed of the black arrows of Gr(ϕ).

We will use the cyclic notation (ϕ_{0}, ϕ_{n}, ϕ_{n−1}, …, ϕ_{2}, ϕ_{1}) for ϕ^{•}. Notice that there is a trivial one-to-one correspondence between all the permutations of S_{n} and all the n+1-cycles in S(1+n). Namely, the entries of a n+1-cycle, starting from the one after 0, are interpreted as the entries of the permutation, but read backwards, written in the shortened way of the two-row notation. Thus, for any n + 1-cycle C in S(1 + n), we can easily obtain the unique permutation ϕ ∈ S_{n}, for which the n + 1-cycle C is its black cycle ϕ^{•}.

Definition 30. For a permutation ϕ ∈ S_{n} we define the corresponding permutation ϕ^{∘} ∈ S(1 + n) to be ϕ^{•} · (0, 1, …, n).

Notice that ϕ^{∘} cannot contain m ↦ (m + 1) for any m = 0, 1, …, n, since m ↦ (m + 1) is i −−→ (i + 1) → (i + 1), but an (n + 1)-cycle ϕ^{•} cannot contain (i + 1) → (i + 1).

Theorem 31 (Doignon and Labarre’s theorem 8). There is a natural one-to-one correspondence between the cycles in the cycle decomposition of the permutation ϕ^{∘} and the alternating cycles in Gr(ϕ).

Therefore, there is a unique way to decompose a permutation into alternating cycles.

Definition 32. We define H(S_{n}) as a partition of S_{n} into pairwise disjoint sets containing permutations with the same number of alternating cycles in their cycle graph.

Now we are going to introduce two operations, x − −y exchange operation in Definition 33 and x − −y cyclic operation in Definition 44, which transform permutations in S_{n}. Next, we show that these two operations do not change the number of alternative cycles in the cycle graph of a permutation. After that, we demonstrate that these two operations do not change the probabilities of the permutation equations. Finally, we prove that any two permutations that have the same number of alternating cycles in their cycles graphs, can be connected to each-other by performing a finite number of these operations. This establishes that any two permutations with the same number of alternating cycles in their cycle graphs, have the same probabilities of their permutation equalities.

4.1 Exchange operation

Let ϕ ∈ S_{n} be a permutation. We augment ϕ by defining ϕ_{0} = 0.

Definition 33. Let 0 ≤ x = ϕ_{j}, y = ϕ_{i}, w, z ≤ n, for some 0 ≤ i, j ≤ n, be four integers, such that

z → x −−→ x + 1 → y

and

y → w

appear in some alternating cycles of Gr(ϕ). The black arrow x + 1 → y implies that x + 1 = ϕ_{i+1}. The black arrow z → x implies that z = ϕ_{j+1}. The black arrow y → w implies that w = ϕ_{i−1}. All the arithmetic is performed modulo n + 1. The x − −y exchange operation is defined as follows (compare it to Lemma 19)

• if x = w or if y = z, then the x − −y exchange operation does not change ϕ;

• if y = ϕ_{0} = 0, then the x − −y exchange operation changes

⟨ϕ_{1} = (x + 1) … ϕ_{j−1} ϕ_{j} = x ϕ_{j+1} = z … ϕ_{n} = w⟩

to

⟨ϕ_{j+1} = z ϕ_{j+2} … ϕ_{n} = w ϕ_{1} = (x + 1) … ϕ_{j−1} ϕ_{j} = x⟩;

• if x = ϕ_{0} = 0, then the x − −y exchange operation changes

⟨ϕ_{1} = z … ϕ_{i−1} = w ϕ_{i} = y ϕ_{i+1} = 1 … ϕ_{n}⟩

to

⟨ϕ_{i} = y ϕ_{1} = z … ϕ_{i−1} = w ϕ_{i+1} = 1 … ϕ_{n}⟩;

• if 1 < i + 1 < j, then the x − −y exchange operation changes

⟨ϕ_{1} … ϕ_{i−1} = w ϕ_{i} = y ϕ_{i+1} = (x + 1) … ϕ_{j} = x ϕ_{j+1} = z … ϕ_{n}⟩

to

⟨ϕ_{1} … ϕ_{i−1} = w ϕ_{i+1} = (x + 1) … ϕ_{j} = x ϕ_{i} = y ϕ_{j+1} = z … ϕ_{n}⟩;

• if 0 < j < i, then the x − −y exchange operation changes

⟨ϕ_{1} … ϕ_{j} = x ϕ_{j+1} = z … ϕ_{i−1} = w ϕ_{i} = y ϕ_{i+1} = (x + 1) … ϕ_{n}⟩

to

⟨ϕ_{1} … ϕ_{j} = x ϕ_{i} = y ϕ_{j+1} = z … ϕ_{i−1} = w ϕ_{i+1} = (x + 1) … ϕ_{n}⟩.

Let us consider several examples of the x − −y exchange operation.

Example 34. Let ϕ = ⟨4 1 6 2 5 7 3⟩. We perform the 5 − −1 exchange operation on ϕ. Here x = 5 = ϕ_{5} and y = 1 = ϕ_{2}. Hence, z = ϕ_{6} = 7 and w = ϕ_{1} = 4. The fact that x + 1 = 6 = ϕ_{3} causes the condition x + 1 → y to be satisfied. The condition x + 1 → y is what makes the x − −y exchange operation possible. Now, i = 2 and j = 5. Thus, 1 < i+1 < j and we get that the 5−−1 exchange operation changes ϕ to ⟨4 6 2 5 1 7 3⟩.

Example 35. Let ϕ = ⟨4 1 6 2 5 7 3⟩. We perform the 4 − −2 exchange operation on ϕ. Here x = 4 = ϕ_{1} and y = 2 = ϕ_{4}. Hence, z = ϕ_{2} = 1 and w = ϕ_{3} = 6. The fact that x + 1 = 5 = ϕ_{5} causes the condition x + 1 → y to be satisfied. The condition x + 1 → y is what makes the x − −y exchange operation possible. Now, i = 4 and j = 1. Thus, 0 < j < i and we get that the 4 − −2 exchange operation changes ϕ to ⟨4 2 1 6 5 7 3⟩.

Example 36. Let ϕ = ⟨4 6 1 2 5 7 3⟩. We perform the 0 − −6 exchange operation on ϕ. Here x = 0 = ϕ_{0} and y = 6 = ϕ_{2}. Hence, z = ϕ_{1} = 4 and w = ϕ_{5} = 5. The fact that x+1 = 1 = ϕ_{3} causes the condition x+1 → y to be satisfied. The condition x+1 → y is what makes the x − −y exchange operation possible. Now, i = 2 and j = 0. Since x = ϕ_{0} = 0, we get that the 0 − −6 exchange operation changes ϕ to ⟨6 4 1 2 5 7 3⟩.

Example 37. Let ϕ = ⟨4 1 6 3 5 7 2⟩. We perform the 3 − −0 exchange operation on ϕ. Here x = 3 = ϕ_{4} and y = 0 = ϕ_{0}. Hence, z = ϕ_{5} = 5 and w = ϕ_{7} = 2. The fact that x+1 = 4 = ϕ_{1} causes the condition x+1 → y to be satisfied. The condition x+1 → y is what makes the x − −y exchange operation possible. Now, i = 0 and j = 4. Since y = ϕ_{0} = 0, we get that the 3 − −0 exchange operation changes ϕ to ⟨5 7 2 4 1 6 3⟩.

Notice that after completing the x − −y exchange operation on ϕ, y → x −−→ x + 1 → w and z → y will appear in the alternating cycles of the cycle graph of the new permutation.

Proposition 38. Let ϕ and θ be two different permutations in S_{n}, such that θ is obtained from ϕ by an x − −y exchange operation. Then θ^{•} is obtained from ϕ^{•} by multiplying ϕ^{•} on the left by the 3−cycle (x, y, w) ∈ S(1 + n). Namely,

θ^{•} = (x, y, w) · ϕ^{•}.

Proof. Since the x − −y exchange operation was permissible on ϕ, and since this operation changed ϕ, the cycle ϕ^{•} must be of the form (x+1, y, w, …, z, x, …). Indeed, (x+1) → y → w and z → x cannot intersect, since θ ≠ ϕ. Here we are using the cyclic notation, in which the cycles can be written starting from any entry. Now,

(x, y, w) · ϕ^{•} = (x + 1, w, …, z, y, x, …).

To construct θ we need to rewrite the cycle (x + 1, w, …, z, y, x, …), starting from 0. Then the cycle will become (0, θ_{n}, …, θ_{1}), which permits us to obtain θ = ⟨θ_{1} … θ_{n}⟩. When we rewrite the cycle (x + 1, w, …, z, y, x, …), starting from 0, we can have four different cases

• if y = 0, then the cycle, after rewriting, becomes (y = 0, x, …, x + 1, w, …, z);

• if x = 0, then the cycle, after rewriting, becomes (x = 0, …, x + 1 = 1, w, …, z, y);

• if 1 < i + 1 < j, then the cycle, after rewriting, becomes (0, …, z, y, x, …, x + 1, w, …);

• if 1 < j < i, then the cycle, after rewriting, becomes (0, …, x + 1, w, …, z, y, x, …).

In all these four cases we obtain the exact θ, which is described in Definition 33 as the result of the x − −y exchange operation.

Notice that the inverse of an x − −y exchange operation is not, in general, an x − −y exchange operation. Indeed, θ^{•} might not contain (w + 1) → y → x, which is required to perform a w − −x exchange operation on θ and obtain ϕ.

Proposition 39. Let θ ≠ ϕ be a permutation obtained from ϕ by some x − −y exchange operation. Then the cyclic presentation of θ^{∘} is obtained from the cyclic presentation of ϕ^{∘} by relocating x from the place after (z − 1) and before y to the place after (y − 1) and before w; i.e., the cycle of ϕ^{∘} of the form (…, z − 1, x, y, …) becomes (…, z − 1, y, …), and the cycle of ϕ^{∘} of the form (…, y − 1, w, …) becomes (…, y − 1, x, w, …). This, in particular, implies that θ^{∘} and ϕ^{∘} have the same number of cycles in their cyclic decompositions.

Proof. By Proposition 38, θ^{•} = (x, y, w) · ϕ^{•}. This implies that

θ^{∘} = θ^{•} · (0, 1, …, n) = (x, y, w) · ϕ^{•} · (0, 1, …, n) = (x, y, w) · ϕ^{∘}

Now, multiplication of ϕ^{∘} on the left by (x, y, w) removes x from the cycle (…, z − 1, x, y, …) and places it in the cycle (…, y − 1, w, …) between y − 1 and w. Thus, z −1, instead of going to x, now goes to y. And x, instead of going to y, now goes to w. And y − 1, instead of going to w, now goes to x. No other changes are done by multiplication of ϕ^{∘} from the left by 3−cycle (x, y, w).

Recall that Bafna and Pevzner [1], for 1 ≤ i < j < k ≤ n + 1, defined the permutation ρ(i, j, k) to be

ρ(i, j, k) = ⟨1 … (i − 1) j … (k − 1) i … (j − 1); k … n⟩.  (12)

Next, for a permutation ϕ ∈ S_{n}, Bafna and Pevzner defined a block-transposition, which exchanges places of the blocks i … (j − 1) and j … (k − 1) inside ϕ, to be ϕ · ρ(i, j, k). For any three pairwise different integers 1 ≤ i, j, k ≤ n one can define

ρ(i, j, k) = ρ(i, k, j) = ρ(j, i, k) = ρ(j, k, i) = ρ(k, i, j) = ρ(k, j, i).

Since in one of these six expressions, i, j, k are placed in the increasing order, which makes that expression well-defined by Equation 12, all six expressions are now well-defined and represent the same permutation ρ(i, j, k). Finally, if two or more of the three integers 1 ≤ i, j, k ≤ n + 1 are equal, ρ(i, j, k) is defined as an identity permutation. Now ρ(i, j, k) is defined for any three integers 1 ≤ i, j, k ≤ n + 1 and represents an appropriate blocktransposition. Clearly, if two or more of the three integers 1 ≤ i, j, k ≤ n are equal, at least one of the blocks is empty, which corresponds to no change performed to ϕ. Now we can relate our x − −y exchange operation to the block-transpositions.

Remark 40. Let ϕ be a permutation in S_{n}, extended by ϕ_{0} = 0, such that for some 0 ≤ ϕ_{j} = x, ϕ_{i} = y ≤ n, ϕ_{i+1} = x + 1. Then performing the x − −y exchange operation is a block-transposition, for which the permutation ρ is selected as follows

• if x = j = 0, then select ρ(1, i, i + 1);

• if y = i = 0, then select ρ(1, j + 1, n + 1);

• in all other cases select ρ(i, i + 1, j + 1).

Lemma 2.1 in Bafna and Pevzner’s work [1] asserts that a block-transformation can either increase by two, or decrease by two, or keep unchanged the number of alternating cycles in the cycle graph of a permutation. We now show that an x − −y exchange operation does not change the number of alternating cycles in the cycle graph of a permutation.

Lemma 41. Let a permutation θ ∈ S_{n} be obtained from a permutation ϕ ∈ S_{n} by an x − −y exchange operation. Then θ and ϕ have the same number of alternating cycles in their cycle graphs Gr(θ) and Gr(ϕ).

Proof. The lemma directly follows from Proposition 39 and Theorem 31. However, we produce an alternative proof, based on Bafna and Pevzner’s analysis of blocktransformations.

Notice that the edges, which appear in Gr(ϕ) and which do not appear in Gr(θ), are precisely the three black edges ϕ_{i} = y → w = ϕ_{i−1}, ϕ_{i+1} = x + 1 → y = ϕ_{i}, and ϕ_{j+1} = z → x = ϕ_{j}.

Similarly, the edges, which appear in Gr(θ) and which do not appear in Gr(ϕ), are precisely the three black edges ϕ_{i+1} = x + 1 → w = ϕ_{i−1}, ϕ_{j+1} = z → y = ϕ_{i}, and ϕ_{i} = y → x = ϕ_{j}.

Since the black edges ϕ_{i+1} = x + 1 → y = ϕ_{i} and ϕ_{j+1} = z → x = ϕ_{j} belong to the same alternating cycle in Gr(ϕ), the above-mentioned three black edges y → w, x + 1 → y, and z → x belong to, at most, two alternating cycles in Gr(ϕ). Similarly, since the black edges ϕ_{i+1} = x + 1 → w = ϕ_{i−1} and ϕ_{i} = y → x = ϕ_{j} belong to the same alternating cycle in Gr(θ), the above-mentioned three black edges x + 1 → w, z → y, and y → x belong to, at most, two alternating cycles in Gr(ϕ).

In the proof of Lemma 2.1 in Bafna and Pevzner’s work [1],it is shown that if Gr(ϕ) and Gr(θ) differ by exactly three black edges, which in both graphs Gr(ϕ) and Gr(θ) belong to one or two alternating cycles, then Gr(ϕ) and Gr(θ) have the same number of alternating cycles.

Definition 42. We say that the permutations ϕ, θ ∈ S_{n} are in the same “x − −y exchange orbit” if there exist some permutations τ_{1}, …, τ_{k} ∈ S_{n} such that τ_{1} = ϕ, τ_{k} = θ, and, for each i = 1, …, k − 1, either τ_{i} can be obtained from τ_{i+1} by an x − −y exchange operation, or τ_{i+1} can be obtained from τ_{i} by an x − −y exchange operation.

Notice that according to Definition 42, ϕ, θ ∈ S_{n} can be in the same x − −y exchange orbit, while neither of them can be obtained from the other by performing x − −y exchange operations.

Theorem 43. Let ϕ, θ ∈ S_{n} be two permutations such that θ is obtained from ϕ by an x−−y exchange operation. Then

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Proof. Compare this proof with the proof of Lemma 19 above. If x = y then θ = ϕ and the theorem follows. Hence, we assume that x ≠ y.

First, we consider the case when x, x + 1, w, y, z are all different than 0. In that case, the requirement that z → x −−→ x + 1 → y and y → w are present in Gr(ϕ) implies that the product a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}} contains sub-products a_{w}a_{y}a_{x+1} and a_{x}a_{z}. These two sub-products a_{w}a_{y}a_{x+1} and a_{x}a_{z} can “overlap” if and only if z = w. By overlapping we mean that they have a common piece. For example, if z = w then a_{z} = a_{w} is the overlap of these two products.

If the sub-product a_{w}a_{y}a_{x+1} appears in the product a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}} before the sub-product a_{x}a_{z}, then z ≠ w. In that case, we rewrite the equation

a_{1} ⋯ a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−2}}a_{w}a_{y}a_{x+1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n}}

as

a_{1} ⋯ a_{x}a_{y}^{−1}(a_{y}a_{x+1})a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−2}}a_{w}(a_{y}a_{x+1})a_{ϕ_{i+2}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n}} (13)

Similarly, the fact that y → x −−→ x+1 → w and z → y are present in Gr(θ), implies that the product a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}} contains sub-products a_{x}a_{y}a_{z} and a_{w}a_{x+1}. These two sub-products can “overlap” if and only if either x = w or z = x + 1. But ϕ_{j+1} = z = x + 1 = ϕ_{i+1} would imply i = j and ϕ_{j} = x = y = ϕ_{i}. Thus, θ = ϕ. If x = w, then θ = ϕ by Definition 33. So, we can assume that a_{w}a_{y}a_{x+1} and a_{x}a_{z} do not overlap. Again, we rewrite the equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{θ_{1}} ⋯ a_{θ_{i−2}}a_{w}a_{x+1}a_{θ_{i+1}} ⋯ a_{θ_{j−2}}a_{x}a_{y}a_{z}a_{θ_{j+2}} ⋯ a_{θ_{n}}

as

a_{1} ⋯ a_{x−1}(a_{x}a_{y})a_{y}^{−1}a_{x+1} ⋯ a_{n} = a_{θ_{1}} ⋯ a_{θ_{i−2}}a_{w}a_{x+1}a_{θ_{i+1}} ⋯ a_{θ_{j−2}}(a_{x}a_{y})a_{z}a_{θ_{j+2}} ⋯ a_{θ_{n}} . (14)

Notice that as the random variable a_{y} runs over all the elements of G, so does its inverse a_{y}^{−1}. Also, for each choice of a_{y}, as the random variable a_{x} runs over all the elements of G, so does the random variable b = (a_{x}a_{y}). Similarly, for each choice of a = a_{y}^{−1}, as the random variable a_{x+1} runs over all the elements of G, so does the random variable c = (a_{y}a_{x+1}).

We show now that Equations 13 and 14, up to renaming variables, are identical. We regard b = (a_{x}a_{y}) as one variable. Similarly, we regard c = (a_{y}a_{x+1}) as one variable. Notice that the left sides of Equations 13 and 14 have n + 1 variables in each, and their right sides have n − 1 variables in each. Both left sides have the variables a_{1}, …, a_{x−1} in place of 1, …, x − 1, respectively, and the variables a_{x+2}, …, a_{n} in place of x + 3, …, n + 1, respectively.

Notice that for all 1 ≤ r ≤ i − 1, ϕ_{r} = θ_{r} and a_{ϕ_{r}} = a_{θ_{r}}. Similarly, for all j + 1 ≤ r ≤ n, ϕ_{r} = θ_{r} and a_{ϕ_{r}} = a_{θ_{r}}. For i+1 ≤ r ≤ j −2, ϕ_{r+1} = θ_{r} and a_{ϕ_{r+1}} = a_{θ_{r}}. Thus, the right sides of Equations 13 and 14 carry the same variables in place of 1, …, i − 1 and i + 1, …, j − 2 and j, …, n − 1.

The random variable a_{x} appears in the x-th place on the left side of Equation 13 and in the (j − 1)-th place on its right side. Similarly, the random variable b = (a_{x}a_{y}) appears in the x-th place on the left side of Equation 14 and in the (j − 1)-th place on its right side.

The inverse a_{y}^{−1} of the random variable a_{y} appears in the (x + 1)-th place on the left side of Equation 13 and does not appear on its right side. Similarly, the inverse a_{y}^{−1} of the random variable a_{y} appears in the (x + 1)-th place on the left side of Equation 14 and does not appear its right side. The random variable a_{y} cannot appear in the x-th, (x + 1)-th, or (x + 2)-th place on the left side of Equation 13 or of Equation 14. Since the rest of the places of the left sides of Equations 13 and 14 carry the same variables, a_{y} must appear in the same place in both left sides. The right sides of Equations 13 and 14 do not contain a_{y}.

The random variable c = (a_{y}a_{x+1}) appears in the (x + 2)-th place on the left side of Equation 13 and on the i-th place on its right side. Similarly, the random variable a_{x+1} appears in the (x + 2)-th place on the left side of Equation 14 and in the i-th place on its right side.

Thus, Equations 13 and 14, up to renaming variables, are identical. This implies that they have the same number of solutions. This, in its turn, implies that

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Now, assume that the sub-product a_{x}a_{z} appears in the product a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}} before the sub-product a_{w}a_{y}a_{x+1}. Then, if z = w, then a_{z} is the same as a_{w}, and we have the subproduct a_{x}a_{w}a_{y}a_{x+1} inside the product a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}. In that case, the x − −y exchange operation only exchanges the places of a_{w} and a_{y}. We rewrite the equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−3}}a_{x}a_{w}a_{y}a_{x+1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}}

as

a_{1} ⋯ a_{x−1}a_{x}a_{y}^{−1}(a_{y}a_{x+1})a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−3}}a_{x}a_{w}(a_{y}a_{x+1})a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}}.  (15)

The equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{θ_{1}} ⋯ a_{θ_{i−3}}a_{x}a_{y}a_{w}a_{x+1}a_{θ_{i+2}} ⋯ a_{θ_{n}}

is identical to the equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−3}}a_{x}a_{y}a_{w}a_{x+1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}},

which we rewrite as

a_{1} ⋯ a_{x−1}(a_{x}a_{y})a_{y}^{−1}a_{x+1}a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{i−3}}(a_{x}a_{y})a_{w}a_{x+1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}}.  (16)

Again, the random variable a_{y} and its inverse a_{y}^{−1} appear in the same places in both Equations 15 and 16. The random variable c = (a_{x}a_{y}) in Equation 16 plays the role of the random variable a_{x} in the Equation 15. The random variable a_{x+1} in Equation 16 plays the role of the random variable b = (a_{y}a_{x+1}) in Equation 15. Thus, Equations 15 and 16, up to renaming variables, are identical. This implies that they have the same number of solutions. This, in its turn, implies that

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

If z ≠ w, then we rewrite the equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{w}a_{y}a_{x+1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}}

as

a_{1} ⋯ a_{x−1}a_{x}a_{y}^{−1}(a_{y}a_{x+1})a_{x+2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{w}(a_{y}a_{x+1})a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}} . (17)

Similarly, we rewrite the equation

a_{1} ⋯ a_{x−1}a_{x}a_{x+1}a_{x+2} ⋯ a_{n} = a_{θ_{1}} ⋯ a_{θ_{j−1}}a_{x}a_{y}a_{z}a_{θ_{j+3}} ⋯ a_{w}a_{x+1}a_{θ_{i+2}} ⋯ a_{θ_{n}}

as

a_{1} ⋯ a_{x−1}(a_{x}a_{y})a_{y}^{−1}a_{x+1}a_{x+2} ⋯ a_{n} = a_{θ_{1}} ⋯ a_{θ_{j−1}}(a_{x}a_{y})a_{z}a_{θ_{j+3}} ⋯ a_{w}a_{x+1}a_{θ_{i+2}} ⋯ a_{θ_{n}} . (18)

Comparison of Equations 17 and 18, shows that, similarly to Equations 13 and 14, and Equations 15 and 16, which we compared in detail above, a certain renaming of variables in Equation 18 transforms it into Equation 17. Thus, again

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Now, we consider the case when x = ϕ_{0} = θ_{0} = 0. In this case y = ϕ_{i} = θ_{1}, z = ϕ_{1} = θ_{2}, ϕ_{2} = θ_{3}, …, ϕ_{i−1} = θ_{i} = w, x + 1 = ϕ_{i+1} = θ_{i+1} = 1, and ϕ_{i+2} = θ_{i+2}, …, ϕ_{n} = θ_{n}. We rewrite the equation

a_{1}a_{2} ⋯ a_{n} = a_{z}a_{ϕ_{2}} ⋯ a_{ϕ_{i−2}}a_{w}a_{y}a_{1}a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}}

as

(a_{y}a_{1})a_{2} ⋯ a_{n} = a_{y}a_{z}a_{ϕ_{2}} ⋯ a_{ϕ_{i−2}}a_{w}(a_{y}a_{1})a_{ϕ_{i+2}} ⋯ a_{ϕ_{n}},  (19)

in which the random variable a_{1} is omitted, and for each fixed value of a_{y}, as a_{1} runs over all the elements of G, so does the random variable b = (a_{y}a_{1}).

Now, compare Equation 19 with the equation

a_{1}a_{2} ⋯ a_{n} = a_{y}a_{z}a_{θ_{3}} ⋯ a_{θ_{i−1}}a_{w}a_{1}a_{θ_{i+2}} ⋯ a_{θ_{n}}.  (20)

Clearly, renaming b = (a_{y}a_{1}) to a_{1} turns Equation 19 to Equation 20. Thus, again

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Now we consider the case when x = n. In that case x + 1 = 0 = ϕ_{0} = θ_{0}, y = ϕ_{n} and w = ϕ_{n−1} = θ_{n}. Observe, that in that case the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

is

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{j−1}}a_{n}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−2}}a_{w}a_{y}.  (21)

Similarly, the equation

a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}

in that case becomes

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{j−1}}a_{n}a_{y}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−2}}a_{w},

which we rewrite as

a_{1}a_{2} ⋯ (a_{n}a_{y}) = a_{ϕ_{1}} ⋯ a_{ϕ_{j−1}}(a_{n}a_{y})a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−2}}a_{w}a_{y}.  (22)

Again, the random variable b = (a_{n}a_{y}) in Equation 22 plays the role of the random variable a_{n} in Equation 21. Thus, again

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Finally, we consider the case when y = 0 = ϕ_{0} = θ_{0}. In this case x + 1 = ϕ_{1} and w = ϕ_{n}. Thus, the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

becomes

a_{1}a_{2} ⋯ a_{n} = a_{x+1}a_{ϕ_{2}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−1}}a_{w}.

On the other hand, the equation

a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}

becomes

a_{1}a_{2} ⋯ a_{n} = a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−1}}a_{w}a_{x+1}a_{ϕ_{2}} ⋯ a_{ϕ_{j−1}}a_{x}.

Let

r = a_{x}, s = a_{x+1}, A = a_{1} ⋯ a_{x−1}, B = a_{x+2}a_{x+3} ⋯ a_{n}, P = a_{ϕ_{2}} ⋯ a_{ϕ_{j−1}},

and Q = a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−1}}a_{w}. Then

a_{1}a_{2} ⋯ a_{n} = a_{x+1}a_{ϕ_{2}} ⋯ a_{ϕ_{j−1}}a_{x}a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−1}}a_{w}

becomes

ArsB = sP rQ,

and

a_{1}a_{2} ⋯ a_{n} = a_{z}a_{ϕ_{j+2}} ⋯ a_{ϕ_{n−1}}a_{w}a_{x+1}a_{ϕ_{2}} ⋯ a_{ϕ_{j−1}}a_{x}

becomes

ArsB = QsP r.

But Pr(ArsB = sP rQ) is the same as Pr(rArsB = rsP rQ), which is the same as Pr(γAθB = θP γQ), where γ = r, θ = rs, which, in its turn, is the same as Pr(γAθBQ^{−1}γ^{−1} = θP). Notice that since the random element s does not appear in the last equation, we regard θ = rs as a random element from G. And γAθBQ^{−1}γ^{−1} = θP is equivalent to saying that AθBQ^{−1} is conjugate to θP.

Similarly, Pr(ArsB = QsP r) is the same as Pr(ArsBs = QsP rs), which is the same as Pr(AθBγ = QγP θ), where γ = s, θ = rs, which, in turn, is the same as Pr(γ^{−1}Q^{−1}AθBγ = P θ). Again, we regard θ = rs as a random element from G. And γ^{−1}Q^{−1}AθBγ = P θ is equivalent to saying that Q^{−1}AθB is conjugate to P θ.

Finally, notice that θP = θ(P θ)θ^{−1} is conjugate to P θ, and AθBQ^{−1} = Q(Q^{−1}AθB)Q−1 is conjugate to Q^{−1}AθB. Thus, AθBQ^{−1} is conjugate to θP if and only if Q^{−1}AθB is conjugate to P θ. Thus,

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

4.2 Cyclic operation

Now we define and discuss x−−y cyclic operation. This material is illustrated by Lemma 22 above. Let ϕ ∈ S_{n} be a permutation such that ϕ^{•} ∈ S(1+n) contains some (x+1) → y → x. In other words, for some 0 ≤ i ≤ n, we have ϕ_{i} = x, ϕ_{i+1} = y, and ϕ_{i+2} = y. Notice that if x = n, the condition (x + 1) → y → x becomes 0 = ϕ_{0} → y = ϕ_{n} → n = ϕ_{n−1}.

Definition 44. The x − −y cyclic operation on the permutation ϕ is defined as follows

• If y = x + 2, then the x − −y cyclic operation does not do anything to ϕ;

• If y > x + 2, then in the long cycle ϕ^{•} we replace x + 1 by y − 1 and replace each t = x + 2, …, y − 1 by t − 1. In other words, the x − −y cyclic operation changes ϕ^{•} to

(y − 1, y − 2, …, x + 2, x + 1)^{−1} · ϕ^{•} · (y − 1, y − 2, …, x + 2, x + 1)
= ϕ^{•}^{(y−1,y−2,...,x+2,x+1)};

• If y = x − 1, then the x − −y cyclic operation does not do anything to ϕ;

• If y < x − 1, then in the long cycle ϕ^{•} we replace x by y + 1 and replace each t = y + 1, …, x − 1 by t + 1. In other words, the x − −y cyclic operation changes ϕ^{•} to

(y + 1, y + 2, …, x − 1, x)^{−1} · ϕ^{•} · (y + 1, y + 2, …, x − 1, x) = ϕ^{•}^{(y+1,y+2,...,x−1,x)}.

Since we can easily restore any permutation θ ∈ S_{n} from its corresponding long cycle θ^{•} ∈ S(1 + n), Definition 44 unambiguously describes what an x − −y cyclic operation does to a permutation ϕ ∈ S_{n}. The fact that an x − −y cyclic operation always produces a long cycle in S(1 + n), is straightforward from the definition.

The requirement that ϕ^{•} ∈ S(1 + n) must contain (x + 1) → y → x, implies that the permutation ϕ^{∘} = ϕ^{•} · (0, 1, …, n) has a cycle that contains (x ↦ y) = (x −−→ x + 1 → y), and a cycle that contains (y − 1 ↦ x) = (y − 1 −−→ y → x). Thus, ϕ^{∘} has a cycle, which contains y − 1 ↦ x ↦ y.

Let us consider several examples of x − −y cyclic operations.

Example 45. Let ϕ = ⟨6 5 3 1 4 2⟩. Then ϕ^{•} = (0, 2, 4, 1, 3, 5, 6). We can perform a 1 − −4 cyclic operation on ϕ to obtain a new permutation θ. Since y = 4 > x + 1 = 2, we get θ^{•} = (0, 3, 4, 1, 2, 5, 6). Hence, θ = ⟨6 5 2 1 4 3⟩.

Example 46. Let ϕ = ⟨4 1 5 2 6 3⟩. Then ϕ^{•} = (0, 3, 6, 2, 5, 1, 4). We can perform a 5 − −2 cyclic operation on ϕ to obtain a new permutation θ. Since y = 2 < x = 5, we get θ^{•} = (0, 4, 6, 2, 3, 1, 5). Hence, θ = ⟨5 1 3 2 6 4⟩.

Example 47. Let ϕ = ⟨4 1 5 2 6 3⟩. Then ϕ^{•} = (0, 3, 6, 2, 5, 1, 4). We can perform a 0 − −4 cyclic operation on ϕ to obtain a new permutation θ. Since y = 4 > x + 1 = 1, we get θ^{•} = (0, 2, 6, 1, 5, 3, 4). Hence, θ = ⟨4 3 5 1 6 2⟩.

Example 48. Let ϕ = ⟨4 1 5 2 6 3⟩. Then ϕ^{•} = (0, 3, 6, 2, 5, 1, 4). We can perform a 6 − −3 cyclic operation on ϕ to obtain a new permutation θ. Since y = 3 < x = 6, we get θ^{•} = (0, 3, 4, 2, 6, 1, 5). Hence, θ = ⟨4 3 5 1 6 2⟩.

Example 49. Let ϕ = ⟨4 1 5 2 6 3⟩. Then ϕ^{•} = (0, 3, 6, 2, 5, 1, 4). We can perform a 3 − −0 cyclic operation on ϕ to obtain a new permutation θ. Since y = 0 < x = 3, we get θ^{•} = (0, 1, 6, 3, 5, 2, 4). Hence, θ = ⟨4 2 5 3 6 1⟩.

We now describe the transformation of ϕ^{∘} under an x − −y cyclic operation. First, write ϕ^{∘} in the cyclic notation. Let ϕ^{∘} consist of k cycles C_{1}, …, C_{k} of lengths h_{1}, …, h_{k}, respectively. We think of these cycles as consisting of boxes

C_{1} = B_{1,1} ↦ B_{1,2} ↦ ⋯ B_{1,h_{1}} ↦ B_{1,1}, …, C_{k} = B_{k,1} ↦ B_{k,2} ↦ ⋯ B_{k,h_{k}} ↦ B_{k,1}.

Each box in each cycle contains inside it one element of ϕ^{∘}. Let B_{k(z),h(z)} denotes the box that contains it for every element z ∈ ϕ^{∘}. The requirement that ϕ^{•} contains (x+1) → y → x, asserts that k(y − 1) = k(x) = k(y) and h(y − 1) + 2 = h(x) + 1 = h(y). Let |B_{i,j}| denote its content for each box B_{i,j}. We now fix the labeling of the boxes and start transforming their contents. At any stage of the transformation, we permit the boxes to contain a single element, two elements z_{1} ↦ z_{2} with an arrow between them, or no elements. The last case, namely that of a box with no elements in it, we permit only in a cycle in which at least one of its remaining boxes is not empty. When we read a cycle, we treat an empty box as if it, together with the arrow following it, are deleted. Thus, we regard a cycle containing an empty box as if the arrow ↦ goes directly from the content of the first nonempty box before the empty one, to the content of the first nonempty box following the empty one.

Lemma 50. Let θ ∈ S_{n} be obtained from ϕ ∈ S_{n} by an x − −y cyclic operation. Then the x − −y cyclic operation transforms ϕ^{∘} to θ^{∘} as follows

• If y = x + 2 or y = x − 1, then θ^{∘} = ϕ^{∘};

• If y > x + 2, then perform the following steps

1. Inside the box B_{k(x+1),h(x+1)} replace x + 1 by y − 1 ↦ x. In other words, in the cycle C_{k(x+1)}, the piece |B_{k(x+1),h(x+1)−1}| ↦ x + 1 ↦ |B_{k(x+1),h(x+1)+1}| becomes |B_{k(x+1),h(x+1)−1}| ↦ y − 1 ↦ x ↦ |B_{k(x+1),h(x+1)+1}|;

2. Inside each box B_{k(t),h(t)}, for all t = x + 2, …, y − 1, replace t by t − 1;

3. Delete the element x from the box B_{k(x),h(x)}. The box B_{k(x),h(x)} is now empty. Notice that the box before B_{k(x),h(x)} is B_{k(y−1),h(y−1)}, and it now contains y−2. The box after B_{k(x),h(x)} is B_{k(y),h(y)}, and it still contains y. Thus, we obtain y − 2 ↦ y in the cycle C_{k(x)}.

• If y < x − 1, then perform the following steps 1. Inside the box B_{k(x−1),h(x−1)} replace x − 1 by x ↦ y. In other words, in the

cycle C_{k(x−1)}, the piece |B_{k(x−1),h(x−1)−1}| ↦ x − 1 ↦ |B_{k(x−1),h(x−1)+1}| becomes |B_{k(x−1),h(x−1)−1}| ↦ x ↦ y ↦ |B_{k(x−1),h(x−1)+1}|;

2. Inside each box B_{k(t),h(t)}, for all t = y, …, x − 2, replace t by t + 1;

3. Delete the element x from the box B_{k(x),h(x)}. The box B_{k(x),h(x)} is now empty. Notice that the box before B_{k(x),h(x)} is B_{k(y−1),h(y−1)}, and it still contains y − 1. The box after B_{k(x),h(x)} is B_{k(y),h(y)}, and it now contains y + 1. Thus, we obtain y − 1 ↦ y + 1 in the cycle C_{k(x)}.

In particular, the number of cycles in the cyclic decompositions of θ^{∘} and of ϕ^{∘} is the same.

Proof. We start by investigating the effect of replacements of elements in ϕ^{•} on ϕ^{∘}. First, notice that when in a piece c → a → d we replace an element a by an element b, b replaces a in two black arrows − in the beginning of the black arrow a → d, and also the end of the black arrow c → a. We study these two replacements separately.

• The replacement of a by b in the end of the black arrow → a transforms (c − 1) −−→ c → a, which, in ϕ^{∘}, is the arrow (c−1) ↦ a, to (c−1) −−→ c → b, which is (c−1) ↦ b. To indicate that b element of ϕ^{∘} is post the replacement of a by b in → a, we mark it as b́. Thus, we say that the replacement of c → a by c → b́ transforms (c − 1) −−→ c → a, which is (c − 1) ↦ a to (c − 1) −−→ c → b́, which is (c − 1) ↦ b́. From b́ we draw a grey arrow b́ −−→ (b + 1). If, at this point, the original element b of ϕ^{•} is still not replaced in → b, we regard that original b as deleted, and do not use it in any further replacements, marking, or arrow-drawing, except the future replacement of b in → b, which eliminates that original b;

• The replacement of a by b in the beginning of the black arrow a → transforms (a−1) −−→ a → d, which, in ϕ^{∘}, is the arrow (a−1) ↦ d, to (b−1) −−→ b → d, which is (b−1) ↦ d. To indicate that b element of ϕ^{∘} is post the replacement of a by b in a →, we mark it as b̈. Since this replacement replaces (a − 1) in (a − 1) ↦ of ϕ^{∘} by (b − 1), we also mark (b − 1) as ` (b − 1). Thus, we say that the replacement of a → d by b̈ → d transforms (a − 1) −−→ a → d, which is (a − 1) ↦ d, to ` (b − 1) −−→ b̈ → d, which is ` (b − 1) ↦ d. If, at this point, the original element b of ϕ^{•} is still not replaced in b →, we regard that original b as deleted, and do not use it in any further replacements, marking, or arrow-drawing, except the future replacement of b in b →, which eliminates that original b;

• If we need to mark b as both b́ and b̀, we write b̂;

• If we need to mark b as both b́ and b̈, we write b⃗;

• If we need to mark b as both b̀ and b̈, we write b̃; • If we need to mark b as b́ and b̀ and b̈, we write b̌.

Notice that our notation permits us to study the effect of replacements of elements in ϕ^{•} on ϕ^{∘} in several steps. Namely, if we have to replace elements a_{1}, …, a_{m} by elements b_{1}, …, b_{m}, we do not have to perform all the 2m replacements in the black arrows at once. Instead, we can perform these 2m replacements in several steps, each time marking the elements as described above. The final ϕ^{∘}, after we perform all the 2m replacements, will be the same, regardless of the selection of intermediate steps. Now we are ready to start our investigation

If y > x + 2, then the x − −y cyclic operation, applied to ϕ^{•}, replaces x + 1 by y − 1, and replaces each t, for t = x + 2, …, y − 1, by t − 1. Thus, y → x remains untouched by the x − −y cyclic operation. This implies that θ^{∘} contains y − 1 ↦ x. Notice that our marking notation implies that after all the replacements in ϕ^{•}, ϕ^{•} will contain x̀ instead of x and ť instead of t, for all t = x + 1, …, y − 2, and (y − 1) instead of (y − 1). Altogether, we need to perform 2(y − x − 1) replacements in the black arrows of ϕ^{•}.

At the first step, we perform the following four replacements

1. Replacement of (x + 2) by ¨ (x + 1) in the black arrow (x + 2) →. This changes x to x̀;

2. Replacement of (x + 1) by (y − 1) in the black arrows → (x + 1) and (x + 1) →. This changes (y − 2) to ` (y − 2);

3. Replacement of (y − 1) by ˆ (y − 2) in the arrow → (y − 1).

If ϕ^{∘} contains (x + 1) ↦ (y − 1), then, according to our notation, the original ϕ^{•} takes u = |B_{k(x+1),h(x+1)−1}| + 1 to x + 1. Indeed, in the original ϕ^{∘} we must have an alternating path

(u − 1) −−→ u → (x + 1) −−→ (x + 2) → (y − 1) −−→ y → x −−→ (x + 1) → y, (23)

which is

(u − 1) ↦ (x + 1) ↦ (y − 1) ↦ x ↦ y.

The four replacements of our first step transform Equation 23 to

(u − 1) −−→ u → (y − 1) −−→ y → x̀ −−→ ¨ (x + 1) → ˆ (y − 2) −−→ (y − 1) → y, (24)

which is

(u − 1) ↦ (y − 1) ↦ x̀ ↦ ˆ (y − 2) ↦ y.

Notice that all four replacements in the black arrows appear in path 24. Thus, these four replacements correspond to the replacement of x + 1 by (y − 1) ↦ x̀ inside the box B_{k(x+1),h(x+1)}, deletion of x from the box B_{k(x),h(x)}, and replacement of y − 1 by ˆ (y − 2) in the box B_{k(y−1),h(y−1)}.

If ϕ^{∘} does not contain (x + 1) ↦ (y − 1) then, according to our notation, the original ϕ^{•} takes u = |B_{k(x+1),h(x+1)−1}| + 1 to x + 1, takes x + 2 to v = |B_{k(x+1),h(x+1)+1}|, and takes p = |B_{k(y−1),h(y−1)−1} + 1| to (y − 1). Indeed, in the original ϕ^{∘} we must have an alternating path

(u − 1) −−→ u → (x + 1) −−→ (x + 2) → v,  (25)

which is

(u − 1) ↦ (x + 1) ↦ v,

and an alternative path

(p − 1) −−→ p →→ (y − 1) −−→ y → x −−→ (x + 1) → y,  (26)

which is

(p − 1) ↦ (y − 1) ↦ x ↦ y.

The four replacements of the first step transform path 25 to

(u − 1) −−→ u → (y − 1) −−→ y → x̀ −−→ ¨ (x + 1) → v,  (27)

which is

(u − 1) ↦ (y − 1) ↦ x̀ ↦ v,

and transforms path 26 to

(p − 1) −−→ p → ˆ (y − 2) −−→ (y − 1) → y,  (28)

which is

(p − 1) ↦ ˆ (y − 2) ↦ y.

Notice that all four replacements in the black arrows appear in paths 27 and 28. Thus, these four replacements correspond to the replacement of x + 1 by y⃗ − 1 ↦ x̀ inside the box B_{k(x+1),h(x+1)}, deletion of x from the box B_{k(x),h(x)}, and replacement of y − 1 by ˆ (y − 2) in the box B_{k(y−1),h(y−1)}.

At the second step, we perform the following two replacements

1. Replacement of (x + 2) by (x + 1) in the black arrow → (x + 2);

2. Replacement of (x + 3) by ¨ (x + 2) in the black arrow (x + 3) →. This changes (x + 1) to ˇ (x + 1);

According to our notation, ϕ^{•}, modified by the first step, takes u = |B_{k(x+2),h(x+2)−1}| + 1 to x + 2 and takes x + 2 to v = |B_{k(x+2),h(x+2)+1}|. Indeed, after the first step, in ϕ^{∘} we must have an alternating path

(u − 1) −−→ u → (x + 2) −−→ (x + 3) → v,  (29)

which is

(u − 1) ↦ (x + 2) ↦ v.

The two replacements of the second step transform path 29 to

(u − 1) −−→ u → ˇ (x + 1) −−→ ¨ (x + 2) → v,  (30)

which is

(u − 1) ↦ ˇ (x + 1) ↦ v.

Notice that both replacements in the black arrows appear in path 30. Thus, these two replacements correspond to the replacement of x + 2 by ˇ (x + 1) inside the box B_{k(x+2),h(x+2)}.

At the third step, we perform the following two replacements

1. Replacement of (x + 3) by (x + 2) in the black arrow → (x + 3);

2. Replacement of (x + 4) by ¨ (x + 3) in the black arrow (x + 4) →. This changes (x + 2) to ˇ (x + 2);

According to our notation, ϕ^{•}, modified by the first and second steps, takes u = |B_{k(x+3),h(x+3)−1}| + 1 to x + 3 and takes x + 3 to v = |B_{k(x+3),h(x+3)+1}|. Indeed, after the second step, in ϕ^{∘} we must have an alternating path

(u − 1) −−→ u → (x + 3) −−→ (x + 4) → v,  (31)

which is

(u − 1) ↦ (x + 3) ↦ v.

The two replacements of the third step transform path 31 to

(u − 1) −−→ u → ˇ (x + 2) −−→ ¨ (x + 3) → v,  (32)

which is

(u − 1) ↦ ˇ (x + 2) ↦ v.

Notice that both replacements in the black arrows appear in path 32. Thus, these two replacements correspond to the replacement of x + 3 by ˇ (x + 2) inside the box B_{k(x+3),h(x+3)}.

We continue that way until at the last step we perform the following two replacements

1. Replacement of ` (y − 2) by (y − 3) in the black arrow → (y − 2);

2. Replacement of (y − 1) by ˇ (y − 2) in the black arrow (y − 1) →. This changes (y − 3) to y̌ − 3);

According to our notation, ϕ^{•}, modified by all the previous steps, takes u = |B_{k(y−2),h(y−2)−1}| + 1 to ` (y − 2) and takes y − 1 to v = |B_{k(y−2),h(y−2)+1}|. Indeed, after the previous step, in ϕ^{∘} we must have an alternating path

(u − 1) −−→ u → ` (y − 2) −−→ (y − 1) → v,  (33)

which is

(u − 1) ↦ ` (y − 2) ↦ v.

The two replacements of the last step transform path 33 to

(u − 1) −−→ u → ˇ (y − 3) −−→ ˇ (y − 2) → v,  (34)

which is

(u − 1) ↦ ˇ (y − 3) ↦ v.

Notice that both replacements in the black arrows appear in path 34. Thus, these two replacements correspond to the replacement of ỳ − 2 by y̌ − 3 inside the box B_{k(y−2),h(y−2)}, and to change of ˆ (y − 2) in the box B_{k(y−1),h(y−1)} to ˇ (y − 2).

At this point, we performed all the 2(y − x − 1) replacements in the black arrows of ϕ^{•}. Our marking notation makes it easy to verify that all the required replacements in ϕ^{•} were performed correctly. Thus the lemma is proved for y > x + 2. The proof for y < x − 1 is done in a similar way, by using the same marking notation and performing the replacements in steps.

Definition 51. We say that the permutations ϕ, θ ∈ S_{n} are in the same “x − −y cyclic orbit” if there exist some permutations τ_{1}, …, τ_{k} ∈ S_{n} such that τ_{1} = ϕ, τ_{k} = θ, and, for each i = 1, …, k − 1, either τ_{i} can be obtained from τ_{i+1} by an x − −y cyclic operation or τ_{i+1} can be obtained from τ_{i} by an x − −y cyclic operation.

Notice that according to Definition 51, ϕ, θ ∈ S_{n} can be in the same x − −y exchange orbit, while neither of them can be obtained from the other one by performing x − −y cyclic operations.

Theorem 52. Let ϕ, θ ∈ S_{n} be two permutations such that θ is obtained from ϕ by an x−−y cyclic operation. Then

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Proof. We consider four different possible cases, and prove the theorem for each of them

Case 1 is when x ≠ 0, n and y ≠ 0. In this case, there exists some k, 1 ≤ k ≤ n − 2, such that ϕ_{k} = x, ϕ_{k+1} = y, and ϕ_{k+2} = x + 1. Hence, the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

is of the form

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{k−1}}a_{x}a_{y}a_{x+1}a_{ϕ_{k+3}} ⋯ a_{ϕ_{n}}  (35)

If y > x, then Equation 35 is equivalent to

a_{1} ⋯ (a_{x}a_{x+1}) ⋯ a_{y} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{k−1}}(a_{x}a_{x+1})(a_{x+1}^{−1}a_{y}a_{x+1})a_{ϕ_{k+3}} ⋯ a_{ϕ_{n}}.  (36)

We define • b_{t} = a_{t} for all t < x and t > y;

• b_{x} = a_{x}a_{x+1};

• b_{t} = a_{t+1} for all x + 1 < t < y − 1;

• b_{y−1} = a_{x+1};

• b_{y} = a_{x+1}^{−1}a_{y}. Next, b_{y−1} = a_{x+1} and b_{y} = a_{x+1}^{−1}a_{y} imply

• b_{y−1}b_{y} = a_{y};

• b_{y}b_{y−1} = a_{x+1}^{−1}a_{y}a_{x+1}. As random variables a_{1}, …, a_{n} run over all elements of G, so do random elements

b_{1}, …, b_{n}. Now, the Equation 36 is equivalent to the equation

b_{1}b_{2} ⋯ b_{n} = b_{θ_{1}}b_{θ_{2}} ⋯ b_{θ_{k−1}}b_{x}b_{y}b_{y−1}b_{θ_{k+3}} ⋯ b_{θ_{n}},  (37)

where • θ_{t} = ϕ_{t} for all such t, for which 1 ≤ ϕ_{t} ≤ x or y ≤ ϕ_{t} ≤ n;

• θ_{t} = y − 1 for the t, for which ϕ_{t} = x + 1;

• θ_{t} = ϕ_{t} − 1 for all such t, for which x + 1 < ϕ_{t} < y. This proves the theorem for the subcase y > x of the first case. If y < x, then Equation 35 is equivalent to

a_{1} ⋯ a_{y} ⋯ (a_{x}a_{x+1}) ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{k−1}}(a_{x}a_{y}a_{x}^{−1})(a_{x}a_{x+1})a_{ϕ_{k+3}} ⋯ a_{ϕ_{n}}.  (38)

We define • b_{t} = a_{t} for all t < y and t > x + 1;

• b_{x+1} = a_{x}a_{x+1};

• b_{t} = a_{t−1} for all y + 1 < t < x; • b_{y+1} = a_{x};

• b_{y} = a_{y}a_{x+1}^{−1}. Next, b_{y+1} = a_{x} and b_{y} = a_{y}a_{x+1}^{−1} imply

• b_{y}b_{y+1} = a_{y};

• b_{y+1}b_{y} = a_{x}a_{y}a_{x}^{−1}. As random variables a_{1}, …, a_{n} run over all elements of G, so do random elements

b_{1}, …, b_{n}. Now, Equation 38 is equivalent to the equation

b_{1}b_{2} ⋯ b_{n} = b_{θ_{1}}b_{θ_{2}} ⋯ b_{θ_{k−1}}b_{y+1}b_{y}b_{x+1}b_{θ_{k+3}} ⋯ b_{θ_{n}},  (39)

where • θ_{t} = ϕ_{t} for all such t, for which 1 ≤ ϕ_{t} ≤ x or x + 1 ≤ ϕ_{t} ≤ n;

• θ_{t} = y + 1 for the t, for which ϕ_{t} = x;

• θ_{t} = ϕ_{t} + 1 for all such t, for which y < ϕ_{t} < x. This proves the theorem for the subcase y < x of the first case. Case 2 is when x = 0 = ϕ_{0}. In this case, ϕ_{1} = y and ϕ_{2} = 1. Hence, the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

is of the form

a_{1}a_{2} ⋯ a_{n} = a_{y}a_{1}a_{ϕ_{3}} ⋯ a_{ϕ_{n}}  (40)

Multiplying Equation 40 from the left by a_{1}^{−1} gives us

a_{2} ⋯ a_{n} = (a_{1}^{−1}a_{y}a_{1})a_{ϕ_{3}} ⋯ a_{ϕ_{n}}  (41)

We define • b_{t} = a_{t} for all t > y;

• b_{t} = a_{t+1} for all 1 ≤ t < y − 1;

• b_{y−1} = a_{1};

• b_{y} = a_{1}^{−1}a_{y}. Next, b_{y−1} = a_{1} and b_{y} = a_{1}^{−1}a_{y} imply

• b_{y−1}b_{y} = a_{y}; • b_{y}b_{y−1} = a_{1}^{−1}a_{y}a_{1}.

As random variables a_{1}, …, a_{n} run over all elements of G, so do random elements b_{1}, …, b_{n}.

Now, Equation 41 is equivalent to the equation

b_{1} ⋯ b_{n} = b_{y}b_{y−1}b_{θ_{3}} ⋯ b_{θ_{n}},  (42)

where

• θ_{t} = ϕ_{t} for all such t, for which ϕ_{t} ≥ y;

• θ_{t} = y − 1 for the t, for which ϕ_{t} = 1;

• θ_{t} = ϕ_{t} − 1 for all such t, for which 2 ≤ ϕ_{t} ≤ y − 1.

This proves the theorem for the second case. Case 3 is when x = n. In this case, x + 1 = 0 = ϕ_{0}, ϕ_{n} = y and ϕ_{n−1} = x = n. Hence,

the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

is of the form

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}} ⋯ a_{ϕ_{n−2}}a_{n}a_{y}  (43)

We apply the inverse map inv(g) = g^{−1} to both sides of Equation 43 and obtain

a_{n}^{−1}a_{n−1}^{−1} ⋯ a_{1}^{−1} = a_{y}^{−1}a_{n}^{−1}a_{ϕ_{n−2}}^{−1} ⋯ a_{ϕ_{1}}^{−1}  (44)

Define c_{n+1−i} = a_{i}^{−1} and ϕ′_{i} = n + 1 − ϕ_{n+1−i}, for all i = 1, …, n. Define x′ = 0 and y′ = n + 1 − y. Then Equation 44 becomes

c_{1}c_{2} ⋯ c_{n} = c_{ϕ′_{1}}c_{ϕ′_{2}} ⋯ c_{ϕ′_{n}},  (45)

in which ϕ′_{1} = y′ and ϕ′_{2} = 1. We apply x′ − −y′ cyclic operation to ϕ′. In the study of Case 2, above, we showed that Equation 45 is equivalent to the equation

b_{1} ⋯ b_{n} = b_{y′}b_{y′−1}b_{θ′_{3}} ⋯ b_{θ′_{n}},  (46)

where

• θ′_{t} = ϕ′_{t} = n + 1 − ϕ_{n+1−t} for all such t, for which n + 1 − ϕ_{n+1−t} = ϕ′_{t} ≥ y′ = n + 1 − y;

• θ′_{t} = y′ − 1 = n − y for the t, for which n + 1 − ϕ_{n+1−t} = ϕ′_{t} = 1;

• θ′_{t} = ϕ′_{t}−1 = n−ϕ_{n+1−t} for all such t, for which 2 ≤ n+1−ϕ_{n+1−t} = ϕ′_{t} ≤ y′−1 = n−y.

Next, we apply the inverse map inv(g) = g^{−1} to both sides of the Equation 46 and obtain

b_{n}^{−1} ⋯ b_{1}^{−1} = b_{θ′_{n}}^{−1} ⋯ θ′_{3}−1b_{y′−1}^{−1}b_{y′}^{−1}.  (47)

Define d_{n+1−i} = b_{i}^{−1} and θ_{i} = n + 1 − θ′_{n+1−i}, for all i = 1, …, n. Then the Equation 47 becomes

d_{1} ⋯ d_{n} = d_{θ_{1}}b_{θ_{2}} ⋯ d_{θ_{n−2}}, d_{y−1}d_{y}.  (48)

Here

• θ_{t} = n+1−θ′_{n+1−t} = n+1−ϕ′_{n+1−t} = ϕ_{t} for all such t, for which ϕ_{t} = n+1−ϕ′_{n+1−t} ≤ n + 1 − y′ = y;

• θ_{t} = n + 1 − θ′_{n+1−t} = n + 1 − (n − y) = y + 1 the t, for which ϕ_{t} = n + 1 − ϕ′_{n+1−t} = n + 1 − 1 = n;

• θ_{t} = n + 1 − θ′_{n+1−t} = n + 1 − (ϕ′_{n+1−t} − 1) = ϕ_{t} + 1 for y + 1 = n + 1 − (n − y) ≤ ϕ_{t} = n + 1 − ϕ′_{n+1−t} ≤ n + 1 − 2 = n − 1.

This proves the theorem for Case 3. Case 4 is when y = 0 = ϕ_{0}. In this case, ϕ_{1} = x + 1 and ϕ_{n} = x. Hence, the equation

a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}

is of the form

a_{1}a_{2} ⋯ a_{n} = a_{x+1}a_{ϕ_{2}} ⋯ a_{ϕ_{n−1}}a_{x}  (49)

Multiplying Equation 49 on the left by a_{x} gives us

a_{x}a_{1}a_{2} ⋯ a_{x−1}(a_{x}a_{x+1}) ⋯ a_{n} = (a_{x}a_{x+1})a_{ϕ_{2}} ⋯ a_{ϕ_{n−1}}a_{x}  (50)

We define • b_{t} = a_{t} for all t > x + 1;

• b_{x+1} = a_{x}a_{x+1}

• b_{t} = a_{t−1} for all 1 < t ≤ x;

• b_{1} = a_{x}. As random variables a_{1}, …, a_{n} run over all elements of G, so do random elements

b_{1}, …, b_{n}. Finally, the Equation 50 is equivalent to the equation

b_{1} ⋯ b_{n} = b_{x+1}b_{θ_{2}} ⋯ b_{θ_{n−1}}b_{1},  (51)

where • θ_{t} = ϕ_{t} for all such t, for which ϕ_{t} > x;

• θ_{t} = 1 for the t, for which ϕ_{t} = x;

• θ_{t} = ϕ_{t} + 1 for all such t, for which 1 ≤ ϕ_{t} < x. This proves our theorem for Case 4.

4.3 Main results

Definition 53. Two permutations ϕ, θ ∈ S_{n} are called “x − −y equivalent” if there exist some permutations ϕ = τ_{1}, …, θ = τ_{k} ∈ S_{n} such that τ_{i} and τ_{i+1}, for each i = 1, …, k − 1, are in the same x − −y exchange orbit or in the same x − −y cyclic orbit.

Theorem 54. If θ and ϕ are x−−y equivalent, then Gr(ϕ) and Gr(θ) have the same number of alternating cycles.

Proof. Since θ and ϕ are x − −y equivalent, there exist some permutations ϕ = τ_{1}, …, θ = τ_{k} ∈ S_{n} such that τ_{i} and τ_{i+1}, for each i = 1, …, k − 1, are in the same x − −y exchange orbit or in the same x − −y cyclic orbit. For each t = 1, …, k − 1, if τ_{i} and τ_{i+1} are in the same x − −y exchange orbit, then, by Lemma 41, Gr(τ_{i}) and Gr(τ_{i+1}) have the same number of alternating cycles. Else, if τ_{i} and τ_{i+1} are in the same x−−y cyclic orbit, then, by Lemma 41, τ_{i}^{∘} and τ_{i+1}^{∘} have the same number of cycles in their cyclic decompositions. Now, Theorem 31 asserts, that Gr(τ_{i}) and Gr(τ_{i+1}) have the same number of alternating cycles. Hence, Gr(ϕ) and Gr(θ) have the same number of alternating cycles.

Theorem 55. If θ and ϕ are x − −y equivalent, then

Pr(a_{1}a_{2} ⋯ a_{n} = a_{ϕ_{1}}a_{ϕ_{2}} ⋯ a_{ϕ_{n}}) = Pr(a_{1}a_{2} ⋯ a_{n} = a_{θ_{1}}a_{θ_{2}} ⋯ a_{θ_{n}}).

Proof. Since θ and ϕ are x − −y equivalent, there exist some permutations ϕ = τ_{1}, …, θ = τ_{k} ∈ S_{n} such that τ_{i} and τ_{i+1}, for each i = 1, …, k − 1, are in the same x − −y exchange orbit or in the same x − −y cyclic orbit. For each t = 1, …, k − 1, if τ_{i} and τ_{i+1} are in the same x − −y exchange orbit, then, by Theorem 43, Pr_{τ_{i}}(G) = Pr_{τ_{i+1}}(G). Else, if τ_{i} and τ_{i+1} are in the same x − −y cyclic orbit, then, by Theorem 52, Pr_{τ_{i}}(G) = Pr_{τ_{i+1}}(G).

At this point, we proceed to show that in a finite non-Abelian group G two permutation equalities have the same probability if, and only if, their permutations have the same number of alternating cycles. The “only if” part implies that every finite non-Abelian group G is generic. This part immediately follows from a stronger result, stated in Theorem 6.8 due to Das and Nath [10].

Theorem 56 (Theorem 6.8 of Das and Nath). For any finite non-Abelian group G, Pr^{2n+2}(G) < Pr^{2n}(G).

Theorem 57. Every finite non-Abelian group is generic.

Proof. Let ϕ ∈ S_{n} have k alternating cycles in its cycle graph Gr(ϕ), and θ ∈ S_{n} have t alternating cycles in its cycle graph Gr(θ). Then, by Theorem 67, Pr_{ϕ}(G) = Pr^{2k}(G) and Pr_{θ}(G) = Pr^{2t}(G). Thus, by Theorem 56, Pr_{ϕ}(G) = Pr_{θ}(G) only if k = t.

We illustrate Theorem 57 by the following example, which is a generalization of Example 25.

Example 58. Let the group G be D_{8} or Q_{8}. Then

Pr(a_{1}a_{2}a_{3}a_{4} ⋯ a_{2k−1}a_{2k}a_{2k+1}a_{2k+2} ⋯ a_{2n} = a_{2}a_{1}a_{4}a_{3} ⋯ a_{2k}a_{2k−1}a_{2k+1}a_{2k+2} ⋯ a_{n})

is equal to

(\frac{5}{8})^{k} + \frac{k!}{2!(k − 2)!} (\frac{5}{8})^{k−2} (\frac{3}{8})^{2} + \frac{k!}{4!(k − 4)!} (\frac{5}{8})^{k−4} (\frac{3}{8})^{4} + ….  (52)

The last summand in the sum 52 is (\frac{3}{8})^{k}, for even k, or (\frac{5}{8}) k (\frac{3}{8})^{k−1}, for odd k. Indeed, in order for the equation

a_{1}a_{2}a_{3}a_{4} ⋯ a_{2k−1}a_{2k}a_{2k+1}a_{2k+2} ⋯ a_{n} = a_{2}a_{1}a_{4}a_{3} ⋯ a_{2k}a_{2k−1}a_{2k+1}a_{2k+2} ⋯ a_{n}

to hold, an even number of the inverted pairs a_{j+1}a_{j} must be equal to ca_{j}a_{j+1}, where c is the nontrivial element from the center of G. All the other inverted pairs a_{j+1}a_{j} must be equal to a_{j}a_{j+1}. But, for each 2t where 0 ≤ 2t ≤ k, there are \frac{k!}{(2t)!(k−2t)!} different choices of 2t inverted pairs, for which a_{j+1}a_{j} = ca_{j}a_{j+1}. Now, Pr(a_{j+1}a_{j} = a_{j}a_{j+1}) = \frac{5}{8} and Pr(a_{j+1}a_{j} = ca_{j}a_{j+1}) = 1 − \frac{5}{8} = \frac{3}{8}. This justifies the sum 52. A direct computation now shows that for different values of k we get different probabilities for the corresponding permutation equalities.

Next, we prove Theorem 66, which, for even n, asserts the opposite direction of the statement of Theorem 54. This, in turn, permits us to prove Theorem 67, in which the “if” part of the above statement is asserted. In order to prove Theorem 66, we need the following several technical lemmas.

Definition 59. Let ϕ be a permutation in S_{n}. Let i be any nonnegative integer smaller than n + 1. We define the permutation ϕ +_{i} 2 ∈ S_{n+2} as follows

• μ_{t} = ϕ_{t} for t = 1, …, i;

• μ_{i+1} = n + 2;

• μ_{i+2} = n + 1;

• μ_{t} = ϕ_{t−2} for t = i + 3, …, n + 2.

Notice that for i = n, our definition implies ϕ +_{i} 2 = ⟨ϕ_{1} … ϕ_{n} n + 2 n + 1⟩, and, for i = 0, it implies ϕ +_{i} 2 = ⟨n + 2 n + 1 ϕ_{1} … ϕ_{n}⟩. Observe that for all 0 ≤ i ≤ n,

(ϕ +_{i} 2)^{•} = (ϕ_{i}, n + 1, n + 2) · ϕ^{•} = (ϕ_{i}, ϕ_{i−1}, …, ϕ_{0}, ϕ_{n}, …, ϕ_{i+1}, n + 1, n + 2).

Lemma 60. Let ϕ be a permutation in S_{n}, i ≤ n be a nonnegative integer, and μ = ϕ +_{i} 2 ∈ S_{n+2}. Then Gr(ϕ) and Gr(μ) have the same number of alternating cycles.

Proof. From μ^{•} = (ϕ_{i}, n + 1, n + 2) · ϕ^{•} we obtain

μ^{∘} = μ^{•} · (0, 1, …, n, n + 1, n + 2) = (ϕ_{i}, n + 1, n + 2) · ϕ^{•} · (0, n + 1, n + 2) · (0, 1, …, n)

Now, ϕ^{∘} always contains (ϕ_{i+1} − 1) ↦ ϕ_{i} and n ↦ ϕ_{n}. When ϕ_{i+1} = 0 = ϕ_{0}, i = n and ϕ_{i+1} − 1 = n. Thus, (ϕ_{i+1} − 1) ↦ ϕ_{i} is identical to n ↦ ϕ_{n}. With regard to μ^{∘}, the following holds

• If ϕ_{i+1} ≠ 0 then μ^{∘} contains (ϕ_{i+1} − 1) ↦ (n + 1) ↦ ϕ_{i} and n ↦ (n + 2) ↦ ϕ_{n}. For all j ≠ ϕ_{i+1} − 1, n, n + 1, andn + 2, the piece μ_{j} ↦ μ_{k} of μ^{∘} is identical to the piece ϕ_{j} ↦ ϕ_{k} of ϕ^{∘};

• If ϕ_{i+1} = 0 then μ^{∘} contains (ϕ_{i+1} − 1) = n ↦ (n + 2) ↦ (n + 1) ↦ ϕ_{i} = ϕ_{n}. For all j ≠ n, n + 1, andn + 2, the piece μ_{j} ↦ μ_{k} of μ^{∘} is identical to the piece ϕ_{j} ↦ ϕ_{k} of ϕ^{∘}.

This shows that μ^{∘} and ϕ^{∘} have the same number of cycles in their cyclic decomposition. Hence, by Theorem 31, Gr(μ) and Gr(ϕ) have the same number of alternating cycles.

Lemma 61. Let ϕ be a permutation in S_{n}. Let i ≤ n and j ≤ n be two nonnegative integers. Let μ = ϕ +_{i} 2 ∈ S_{n+2} and τ = ϕ +_{j} 2 ∈ S_{n+2}. Then the permutations τ and μ in S_{n+2} are x − −y equivalent.

Proof. If i = j then τ = μ and our lemma trivially follows. If i ≠ j, we can assume that i > j. Since μ^{•} = (ϕ_{i}, n + 1, n + 2) · ϕ^{•}, the x − −y exchange operation, where x = n + 1 and y = ϕ_{i}, by Proposition 38, produces a permutation θ ∈ S_{n+2}, for which

θ^{•} = (n + 1, ϕ_{i}, ϕ_{i−1}) · (ϕ_{i}, n + 1, n + 2) · ϕ^{•}
= (ϕ_{i−1}, n + 1, n + 2) · ϕ^{•} = (ϕ_{i−1}, ϕ_{i−2}, …, ϕ_{0}, ϕ_{n}, …, ϕ_{i}, n + 1, n + 2).

Thus, consecutively performing on μ i − j x − −y exchange operations, in which x = n + 1 and y = ϕ_{i}, ϕ_{i+1}, …, ϕ_{j−1}, produces the permutation τ.

Lemma 62. Let ϕ, θ be x − −y equivalent permutations in S_{2t}. Then any two permutations μ = ϕ +_{i} 2 ∈ S_{2t+2} and τ = θ +_{j} 2 ∈ S_{2t+2} are x − −y equivalent in S(2t + 2).

Proof. It is sufficient to prove that for any permutation θ ∈ S_{2t}, which is obtained from ϕ ∈ S_{2t} by one x − −y exchange operation or one x − −y cyclic operation, there exist some nonnegative integers q and k, such that the permutation μ = ϕ +_{q} 2 ∈ S_{2t+2} is x − −y equivalent to the permutation τ = θ +_{k} 2 ∈ S_{2t+2}. Indeed, our lemma then follows, based on Definition 53 and Lemma 61.

We start by considering the situation when θ was obtained from ϕ by one x−−y exchange operation. In this case, we set q to be equal to k. An x − −y exchange operation on ϕ, by Proposition 38, produces θ, such that θ^{•} = (x, y, z) · ϕ^{•}.

If t = 1 then ϕ = θ and our lemma follows from Lemma 61 . If t ≥ 2 we select any k such that ϕ_{k} ∉ {x, y, z}. Then the sets {x, y, z} and {ϕ_{k}, 2t + 1, 2t + 2} do not intersect. Then applying the same x − −y exchange operation on μ produces a permutation τ, such that

τ^{•} = (x, y, z) · μ^{•} = (x, y, z) · (ϕ_{k}, 2t + 1, 2t + 2) · ϕ^{•}
= (ϕ_{k}, 2t + 1, 2t + 2) · (x, y, z) · ·ϕ^{•} = (ϕ_{k}, 2t + 1, 2t + 2) · θ^{•}.

The cycles (x, y, z) and (ϕ_{2t}, 2t+1, 2t+2) in the equation commute, because the sets {x, y, z} and {ϕ_{2t}, 2t + 1, 2t + 2} do not intersect. Thus, τ is exactly θ +_{k} 2 ∈ S_{2t+2}.

We conclude by considering the situation when θ was obtained from ϕ by one x − −y cyclic operation. It is evident from Definition 44, that the x − −y cyclic operation, applied on θ, does not affect the (2t + 1) → (2t + 2) piece in the (2t + 3)-cycle μ^{•}, since both 2t + 1 and 2t + 2 are strictly greater than x and greater than y. Thus, performing an x − −y cyclic operation on μ = ϕ +_{q} 2 ∈ S_{2t+2} produces a (2t + 3)-cycle τ^{•}, which contains some θ_{k+1} → (2t + 1) → (2t + 2) → θ_{k}. This Shows that τ = θ +_{k} 2 ∈ S_{2t+2}.

Let ϕ be a permutation in S_{2t}, with ϕ_{2t} = 2t − 1 and ϕ_{2t−1} = 2t. Let a be a nonnegative integer, smaller than 2t + 1. Let θ ∈ S_{2t} be defined by θ_{χ+i} = (ϕ_{i} + a) mod (2t + 1), where χ is such that ϕ_{χ} = −a. For a = 0 we have θ = ϕ. Notice that

ϕ^{•} = (ϕ_{2t−2}, ϕ_{2t−3}, …, ϕ_{1}, ϕ_{0} = 0, 2t − 1, 2t)

and

θ^{•} = (ϕ_{2t−2} + a, ϕ_{2t−3} + a, …, ϕ_{1} + a, ϕ_{0} + a = a, 2t − 1 + a = a − 2, 2t + a = a − 1).

Here all indices and all elements are modulo 2t + 1.

Lemma 63. The permutations ϕ and θ are x − −y equivalent.

Proof. The lemma is trivial for a = 0. Assume, by induction hypothesis, that the lemma holds for a. We prove our lemma for a + 2. This, by induction, implies our lemma for all a + 2, a + 4, a + 6, . . .. Since a + 1 = a + 2t + 2 modulo 2t + 1, this implies our lemma for a + 1.

For all q = 1, …, 2t − 2, let j_{q} be such that ϕ_{j_{q}} = 2t − 1 − q. Since θ^{•} contains (a − 2) → (a − 1), we can perform the (a − 3) − −(a − 1) exchange operation on θ. Recall that all the calculations are carried modulo 2t + 1. Thus, for example, −1 = 2t, −2 = 2t − 1, and −3 = 2t − 2. This (a − 3) − −(a − 1) exchange operation produces the permutation ρ[1] such that

ρ[1]^{•} = (ϕ_{2t−2} + a, ϕ_{2t−3} + a, …, ϕ_{j_{1}−1} + a, 2t + a = a − 1, ϕ_{j_{1}} + a = a − 3, …,
…, ϕ_{1} + a, ϕ_{0} + a = a, 2t − 1 + a = a − 2).

Since ρ[1]^{•} contains (a − 1) → (a − 3), we can perform the (a − 2) − −(a − 3) exchange operation on ρ[1]. This (a − 2) − −(a − 3) exchange operation produces the permutation ϱ[1] such that

ϱ[1]^{•} = (ϕ_{2t−2} + a, ϕ_{2t−3} + a, …, ϕ_{j_{1}−1} + a, 2t + a = a − 1, ϕ_{j_{1}+1} + a, …,
…, ϕ_{1} + a, ϕ_{0} + a = a, ϕ_{j_{1}} + a = a − 3, 2t − 1 + a = a − 2).

Since ϱ[1]^{•} contains (a − 3) → (a − 2), we can perform the (a − 4) − −(a − 2) exchange operation on ϱ[1]. This (a − 4) − −(a − 2) exchange operation produces the permutation ρ[2] such that ρ[2]^{•} contains (a − 2) → (a − 4). Thus, we perform an (a − 3) − −(a − 4) exchange operation on ρ[2] and obtain ϱ[2]. Notice that ϱ[1]^{•} is obtained from

θ^{•} = (ϕ_{2t−2} + a, ϕ_{2t−3} + a, …, ϕ_{1} + a, ϕ_{0} + a = a, 2t − 1 + a = a − 2, 2t + a = a − 1)

by adding 2 to θ_{χ+j_{1}} = ϕ_{j_{1}} + a = a − 3 and to θ_{χ+j_{2}} = ϕ_{j_{2}} + a = a − 4, and subtracting 2 from 2t − 1 + a = a − 2 and 2t + a = a − 1. Continuing this way, we produce permutations ϱ[3], …, ϱ[2t − 2]. Now,

ϱ[2t − 2]^{•} = (ϕ_{2t−2} + a + 2, ϕ_{2t−3} + a + 2, …, ϕ_{1} + a + 2, ϕ_{0} + a
= a, 2t − 1 + a − [2t − 2]
= a + 1, 2t + a − [2t − 2]
= a + 2).

Finally, we perform an a−−(a+2) exchange operation on ϱ[2t−2] and obtain the permutation ζ, for which

ζ^{•} = (ϕ_{2t−2} + a + 2, ϕ_{2t−3} + a + 2, …, ϕ_{1} + a + 2, ϕ_{0} + a + 2
= a + 2, 2t − 1 + a + 2
= a, 2t + a + 2
= a + 1).

Thus, we proved the lemma for a + 2.

Lemma 64. Any permutation ϕ ∈ S_{2t}, such that ϕ^{•} = (…, a, b, a − 1, …), where a and b are between 0 and 2t, is x − −y equivalent to some permutation θ ∈ S_{2t}, such that

θ^{•} = (θ_{2t−2}, θ_{2t−3}, …, θ_{1}, θ_{0} = 0, 2t − 1, 2t).

Proof. First, we show, that ϕ is x−−y equivalent to some ρ ∈ S_{2t}, such that ρ^{•} contains some k → k+1. Indeed, if b = a+1, then we let k = b. Otherwise, if b > a+1, then an (a−1)−−b cyclic operation on ϕ produces permutation ρ, such that ρ^{•} = (…, b − 1, b, a − 1, …). Thus, we set k = b − 1. And if b < a − 1, then an (a − 1) − −b cyclic operation on ϕ produces permutation ρ, such that ρ^{•} = (…, a, b, b + 1, …). Thus, we set k = b.

Next, let i, j be such that, in ρ^{•}, ρ_{i} → k and ρ_{j} = k + 2. If i = j, then we set ϱ = ρ. Otherwise, a consecutive performance of k−−ρ_{i}, k−−ρ_{i+1}, …, k−−ρ_{j} exchange operations, just like in the proof of Lemma 61, produces a permutation ϱ = (…, k + 2, k, k + 1, …).

Lemma 63 now establishes that ϱ, and, hence, ϕ, is x − −y equivalent to θ.

Lemma 65. Let ϕ ∈ S_{2t} be a permutation, different than the identity. Then ϕ is x − −y equivalent to some permutation θ ∈ S_{2t}, such that

θ^{•} = (θ_{2t−2}, θ_{2t−3}, …, θ_{0}, 2t − 1, 2t).

Proof. There exists some number a between 0 and 2t, such that ϕ^{•} does not contain a → (a − 1). Otherwise, ϕ is the identity permutation. Now, let ϕ^{•} contain some path

a → b_{1} → b_{2} → ⋯ → b_{k} → (a − 1),  (53)

where k ≥ 1. First, assume that k ≥ 2. Then we look for b(i), where 1 ≤ i ≤ k−1, such that (b(i)−1) ∉ {b(1), …, b(k)}. If we find such a b(i), we perform the (b(i) − 1) − −b_{i+1} exchange operation on ϕ, which shortens the path 53 to

a → b_{1} → ⋯ → b_{i} → b_{i+2} → ⋯ → b_{k} → (a − 1).

If we do not find such a b(i), then (b(k) − 1) ∉ {b(1), …, b(k)}. In this case, we perform the (a − 1) − −b(1) exchange operation on ϕ, which changes the path 53 to

a → b_{2} → ⋯ → b_{k} → b_{1} → (a − 1).

Now we perform the (b(k) − 1) − −b_{1} exchange operation, which shortens the path 53 to

a → b_{2} → ⋯ → b_{k−1} → b_{1} → (a − 1).

By repeating the argument of shortening the path 53, we can assume that k = 1. The lemma now follows from Lemma 64.

Theorem 66. If two permutations ϕ and θ in S_{2t} have the same number of alternating cycles in their cycle graphs Gr(ϕ) and Gr(θ), then they are x − −y equivalent.

Proof. We prove the theorem by induction on t.

Basic step. For t = 1 we only have one permutation ⟨2 1⟩ ∈ S_{2} with one alternating cycle in its cycle graph, and one permutation ⟨1 2⟩ ∈ S_{2} with two alternating cycles in its cycle graph. Hence, the proof is completed for t = 1.

Induction. Assume that the induction hypothesis is true for t. We will now prove it for t + 1.

If Gr(ϕ) and Gr(θ) have only one alternating cycle, then ϕ = θ is the identity permutation, and the proof is finished.

Otherwise, by Lemma 65, there exist permutations μ and τ in S_{2t+2} such that

μ^{•} = (μ_{2t}, μ_{2t−1}, …, μ_{0}, 2t + 1, 2t + 2),
τ^{•} = (τ_{2t}, τ_{2t−1}, …, τ_{0}, 2t + 1, 2t + 2),

and μ is x − −y equivalent to ϕ, τ is x − −y equivalent to θ.

By Lemma 60, the permutations ρ = ⟨μ_{1} μ_{2} … μ_{2t−1} μ_{2t}⟩ and ϱ = ⟨τ_{1} τ_{2} … τ_{2t−1} τ_{2t}⟩ in S_{2t} have the same number of alternating cycles in their cycle graphs as the permutations μ and τ, which, in turn, by Theorem 54, have the same number of alternating cycles in their cycle graphs as the permutations ϕ and θ. Now we apply the induction hypothesis to obtain that ρ and ϱ are x − −y equivalent in S_{2t}. This, by Lemma 62, establishes that μ and τ are x − −y equivalent in S_{2t+2}. Thus, ϕ and θ are x − −y equivalent in S_{2t+2}, which completes the proof.

At this point we are ready to state and prove the two main findings. They generalize the observation, made at the end of the previous section, that the probability of a permutation equality in a fixed finite group G depends only on the number of the alternating cycles in the cycle graph of the permutation.

Theorem 67. Let ϕ ∈ S_{n} be a permutation such that Gr(ϕ) contains k alternating cycles. Then, for all positive k ≤ n,

Pr_{ϕ}(G) = Pr^{n+1−k}(G) = Pr(a_{1}a_{2} ⋯ a_{n−k}a_{n+1−k} = a_{n+1−k}a_{n−k} ⋯ a_{2}a_{1})

Since, as shown in [12], n − k must be an odd number, k ≤ n implies k ≤ n − 1. If k > n then k = n + 1 and ϕ is the identity permutation, which implies Pr_{ϕ}(G) = 1.

Proof. If n is an even number then, by Theorem 66, the permutations ϕ and ⟨a_{n+1−k} … a_{1} a_{n+2−k} … a_{n}⟩, both having k alternating cycles in their cycle graphs, are x − −y equivalent in S_{n}. Next, Theorem 55 asserts that Pr_{ϕ}(G) = Pr^{n+1−k}(G).

If n is odd then define ρ ∈ S_{n+1} by ρ = ⟨ϕ_{1} … ϕ_{n} (n + 1)⟩. Notice that Gr(ρ) contains the same k alternating cycles as Gr(ϕ) plus one additional alternating cycle (n + 1) −−→ 0 → (n+1), which is (n+1) ↦ (n+1). Since n+1 is even, Pr_{ϕ}(G) = Pr_{ρ}(G) = Pr^{n+2−(k+1)}(G) = Pr^{n+1−k}(G).

Theorem 68. Let G be a finite non-Abelian group. Let ϕ and θ be two permutations in S_{n}. Then, Pr_{ϕ}(G) = Pr_{θ}(G) if, and only if, the number of the alternating cycles in the cycle graph Gr(ϕ) equals the number of alternating cycles in the cycle graph Gr(θ). Thus, the spectrum of probabilities of permutation equalities for permutations from S_{n} in a finite non-Abelian group G consisting of exactly ⌊\frac{n}{2}⌋ + 1 different numbers, each number corresponding to its unique Hultman class of permutations in S_{n}.

Proof. This theorem follows trivially from Theorem 67 and Theorem 57.

5 Two explicit formulae for Pr^{2t}(G)

We provide two explicit formulae for Pr^{2t}(G). Our first formula expresses Pr^{2t}(G) in terms of Stab. Prod_{t}(x_{1}, x_{2}, …, x_{t}). Our second formula expresses Pr^{2t}(G) in terms of c_{i_{1},...,i_{t};j}(G). These results constitute a generalization of what was shown in Theorem 18 for permutations in S_{4}.

Theorem 69. Let G be a finite group. Then

Pr(a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}) = \frac{∑_{x_{1},x_{2},...,x_{t}∈G} |Stab. Prod_{t}(x_{1}, x_{2}, …, x_{t})|}{|G|^{2t}}  (54)

Pr(a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}) = \frac{1}{|G|^{t}} · ∑_{i_{1},i_{2},...,i_{t},j=1}^{c(G)} \frac{|Ω_{j}| · c_{i_{1},i_{2},...,i_{t};j}^{2}(G)}{|Ω_{i_{1}}| · |Ω_{i_{2}}| · · · · · |Ω_{i_{t}}|}  (55)

Proof. Let us consider a generic equation

a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}.

Let x_{i} denotes the product a_{2i−1}a_{2i} for all i = 1, …, t. Let x′_{i} denotes the product a_{2i}a_{2i−1}. Notice that by Lemma 10, we have x_{i} ∼ x′_{i}.

The equation

a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}

then becomes

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1}.

Now, consider any equation

x_{1}, …, x_{n}, x′_{1}, …, x′_{n} ∈ G,

such that x_{i} ∼ x′_{i} for all i = 1, …, t. Then, by Lemma 11, there are exactly \frac{|G|}{|Ω_{x_{i}}|} = |C_{G}(x_{i})| different ways to break each x_{i} into a product a_{2i−1}a_{2i} in such a way that x′_{i} = a_{2i}a_{2i−1}. Thus, to each fixed equation

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1}

corresponds to

|C_{G}(x_{1})| · |C_{G}(x_{2})| · · · · · |C_{G}(x_{t})|

different equations

a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}.

Notice that for any fixed elements x_{1}, x_{2}, …, x_{t} ∈ G, we can define an element

x′′_{1} = (x_{2}x_{3} ⋯ x_{t})^{−1}x_{1}(x_{2}x_{3} ⋯ x_{t}) = x_{t}^{−1} ⋯ x_{3}^{−1}x_{2}^{−1}x_{1}x_{2}x_{3} ⋯ x_{t}

and obtain an equation

x_{1}x_{2} ⋯ x_{t} = x_{t}x_{t−1} ⋯ x_{2}x′′_{1}.

Now, for any general equation

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1},

in which x_{i} ∼ x′_{i} for all i, there exist some elements g_{1}, g_{2}, …, g_{t} ∈ G, such that x′_{1} = g_{1}x′′_{1}g_{1}^{−1} and, for all i = 2, 3, …, t, x′_{i} = g_{i}x_{i}g_{i}^{−1}.

Thus, if we select and fix elements x_{1}, x_{2}, …, x_{t} ∈ G, we will have

\frac{|Stab. Prod_{t}(x_{t}, …, x_{2}, x′′_{1})|}{|C_{G}(x_{t})| · · · · · |C_{G}(x_{2})| · |C_{G}(x′′_{1})|}

different equations

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1},

in which x′_{i} ∼ x_{i} and for all i. Indeed, every ordered t-tuple

(g_{t}, g_{t−1}, …, g_{2}, g′′_{1}) ∈ Stab. Prod_{t}(x_{t}, …, x_{2}, x′′_{1}),

by setting x′_{i} = g_{i}x_{i}g_{i}^{−1}, for all i = t, …, 2, and x′_{1} = g_{1}x′′_{1}g_{1}^{−1}, produces an equation

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1}.

And any two of these equations produced from the equation x_{1}x_{2} ⋯ x_{t} = x_{t}x_{t−1} ⋯ x_{2}x′′_{1} are identical if, and only if, g_{i} ∈ C_{G}(x_{i}), for all i = t, …, 2 and g_{1} ∈ C_{G}(x′′). Now, |C_{G}(x′′_{1})| = |C_{G}(x_{1})|. Thus, for each fixed ordered t-tuple (x_{1}, x_{2}, …, x_{t}) of elements of G we have

\frac{|Stab. Prod_{t}(x_{t}, …, x_{2}, x′′_{1})|}{|C_{G}(x_{t})| · · · · · |C_{G}(x_{2})| · |C_{G}(x_{1})|}

different equations

x_{1}x_{2} ⋯ x_{t} = x′_{t}x′_{t−1} ⋯ x′_{1}.

As we showed above, to each of these equations correspond

|C_{G}(x_{1})| · |C_{G}(x_{2})| · · · · · |C_{G}(x_{t})|

different equations

a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}.

Thus to each ordered t-tuple (x_{1}, x_{2}, …, x_{t}) of elements of G correspond |Stab. Prod_{t}(x_{t}, …, x_{2}, x′′_{1})| different equations

a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1}.

Hence, to find

Pr(a_{1}a_{2} ⋯ a_{2t} = a_{2t}a_{2t−1} ⋯ a_{1})

we need to sum |Stab. Prod_{t}(x_{t}, x_{t−1}, … x_{2}, x′′_{1})|, as x_{1}, x_{2}, …, x_{t} run over all elements of G.

Since x_{1}, x_{2}, …, x_{n} run over all the elements of G, and for each fixed x_{1}, …, x_{n−1} there is a one-to-one correspondence between x′′_{1} and x_{1}, the sum remains the same if we sum |Stab. Prod_{t}(x_{t}, x_{t−1}, …, x_{2}, x_{1})|, as x_{1}, x_{2}, …, x_{t} run over all elements of G. That proves Equation 54.

Now, select and fix an element z in an equivalence class Ω_{j} of G. Let x_{1}, …, x_{t}, x′_{1}, …, x′_{t} ∈ G be such, that x_{i} ∼ x′_{i} for all i, and

x_{1}x_{2} ⋯ x_{t} = z = x′_{1}x′_{2} ⋯ x′_{t}.  (56)

For each i = 1, …, t, there are |C_{G}(x_{i})| different ways to break x_{i} into a product a_{2i−1}a_{2i} so that a_{2i}a_{2i−1} = x′_{i}. Hence, for each (fixed) Equation 56 we have exactly |C_{G}(x_{1})| · |C_{G}(x_{2})| · ⋯ |C_{G}(x_{t})| different equations

(a_{1}a_{2})(a_{3}a_{4}) ⋯ (a_{2t−1}a_{2t}) = x_{1}x_{2} ⋯ x_{t}
= z = x′_{1}x′_{2} ⋯ x′_{t} = (a_{2}a_{1})(a_{4}a_{3}) ⋯ (a_{2t}a_{2t−1}).

But,

|C_{G}(x_{1})| · |C_{G}(x_{2})| · · · · · |C_{G}(x_{t})| = \frac{|G|^{t}}{|Ω(x_{1})| · |Ω(x_{2})| · · · · · |Ω(x_{t})|}.

Now, for z ∈ Ω_{j} there are c_{i_{1},i_{2},...,i_{t};j}(G) different ways to write z as a product x_{1}x_{2} ⋯ x_{t}, where x_{i} ∈ Ω_{i} for all i = 1, …, t, and c_{i_{1},i_{2},...,i_{t};j}(G) different ways to write z as a product x′_{1}x′_{2} ⋯ x′_{t}, where x′_{i} ∈ Ω_{i} for all i = 1, …, t. Thus, for each z ∈ Ω_{j} there are c_{i_{1},i_{2},...,i_{t};j}^{2}(G) different equations of the form

x_{1}x_{2} ⋯ x_{t} = z = x′_{1}x′_{2} ⋯ x′_{t},

in which x_{i}, x′_{i} ∈ Ω_{i} for all i = 1, …, t. Thus, for each z ∈ Ω_{j} there are

|G|^{t} · ∑_{i_{1},i_{2},...,i_{t}=1}^{c(G)} \frac{c_{i_{1},i_{2},...,i_{t};j}^{2}(G)}{|Ω_{i_{1}}| · |Ω_{i_{2}}| · · · · · |Ω_{i_{t}}|}

different equations of the form

(a_{1}a_{2})(a_{3}a_{4}) ⋯ (a_{2t−1}a_{2t}) = z = (a_{2}a_{1})(a_{4}a_{3}) ⋯ (a_{2t}a_{2t−1}).

We make z run over all the elements of G and obtain

Pr(a_{1}a_{2} ⋯ a_{2t−1}a_{2t} = a_{2}a_{1} ⋯ a_{2t}a_{2t−1}) = \frac{1}{|G|^{t}} · ∑_{i_{1},i_{2},...,i_{t},j=1}^{c(G)} \frac{|Ω_{j}| · c_{i_{1},i_{2},...,i_{t};j}^{2}(G)}{|Ω_{i_{1}}| · |Ω_{i_{2}}| · · · · · |Ω_{i_{t}}|}.

Since both permutations ϕ = ⟨2t 2t − 1 … 1⟩ and θ = ⟨2 1 4 3 … 2t 2t − 1⟩ have exactly one alternating cycle in their cycle graphs Gr(ϕ) and Gr(θ), Equation 55 follows from Theorem 68.

6 Conclusion

In conclusion, we recall two known results. The first result relates Pr^{2t}(G) to the commutator subgroup G′ and the quotient group G/Z(G), and the second result relates Pr^{2t}(G) to the notion of isoclinism of groups. We give a counter-example to the opposite direction of the second result. We conjecture a weaker form of the opposite direction of the second result. Finally, we give an example, demonstrating that the isoclinism in the second result cannot be replaced by weak isoclinism. From that it follows that the opposite direction of our conjecture is false.

Theorem 70. The first result, established by Das and Nath [9], is

lim_{t→∞} Pr^{2t}(G) = \frac{1}{|G′|}.

Theorem 71. The second result, established by Das and Nath [9] If two finite groups G_{1} and G_{2} are isoclinic, then Pr^{2t}(G_{1}) = Pr^{2t}(G_{2}) for all t = 1, 2, . . ..

For example, every two Abelian groups are isoclinic. Clearly, Pr^{2t}(G) = 1 for all t, for every Abelian group. The dihedral group D_{8} and the quaternion group Q_{8}, both of order 8, are isoclinic. As we showed in Example 58, Pr^{2t}(D_{8}) = Pr^{2t}(Q_{8}) for every t ≥ 1.

Now, notice that the opposite direction of the second result is not true. Two finite groups G_{1} and G_{2}, for which Pr^{2t}(G_{1}) = Pr^{2t}(G_{2}) for all t = 1, 2, …, do not have to be isoclinic. For example, the groups

G_{1} =⟨a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6} : a_{1}^{2} = a_{4}, a_{4}^{2} = a_{6}, a_{2}^{2} = a_{3}^{2} = a_{5}^{2} = a_{6}^{2} = 1,
[a_{1}, a_{2}] = a_{3}, [a_{1}, a_{3}] = [a_{2}, a_{4}] = a_{5},
[a_{1}, a_{5}] = [a_{2}, a_{5}] = [a_{3}, a_{5}] = [a_{2}, a_{3}] = [a_{3}, a_{4}] = [a_{2}, a_{6}] = [a_{3}, a_{6}] = 1⟩

and

G_{2} =⟨a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6} : a_{1}^{2} = a_{2}^{2} = a_{3}^{2} = a_{4}^{2} = a_{5}^{2} = a_{6}^{2} = 1,
[a_{1}, a_{2}] = a_{6}, [a_{1}, a_{3}] = [a_{2}, a_{4}] = a_{5},
[a_{1}, a_{4}] = [a_{1}, a_{5}] = [a_{1}, a_{6}] = [a_{2}, a_{3}] = [a_{2}, a_{5}] = [a_{2}, a_{6}]
= [a_{3}, a_{4}] = [a_{3}, a_{5}] = [a_{3}, a_{6}] = [a_{4}, a_{5}] = [a_{4}, a_{6}] = [a_{5}, a_{6}] = 1⟩,

both of the order 64, are not isoclinic, not even weakly isoclinic. Indeed, G_{1}/Z(G_{1}) is a non-Abelian group of order 16, while G_{2}/Z(G_{2}) is an Abelian group of order 16. The fact that Pr^{2t}(G_{1}) = Pr^{2t}(G_{2}), for every t ≥ 1, is verifiable by a direct calculation.

From Theorem 70 it follows that, if for two finite groups G_{1} and G_{2} we have Pr^{2t}(G_{1}) = Pr^{2t}(G_{2}) for every t ≥ 1, then |G′_{1}| = |G′_{2}|. That motivates the following conjecture, which, together with |G′_{1}| = |G′_{2}|, is a weaker form of the opposite direction of the second result.

Conjecture 72. Let G_{1} and G_{2} are two finite groups, such that Pr^{2t}(G_{1}) = Pr^{2t}(G_{2}) for every t ≥ 1. Then |G_{1}/Z(G_{1})| = |G_{2}/Z(G_{2})|.

The groups G_{2} and G_{3} = D_{8} × D_{8} give a counterexample to the opposite direction of Conjecture 72. Moreover, G′_{2} is isomorphic to G′_{3}|, and G_{2}/Z(G_{2}) is isomorphic to G_{3}/Z(G_{3})|. Thus, G_{2} and G_{3} are weakly isoclinic. However, Pr^{2}(G_{2}) = \frac{22}{64} ≠ \frac{25}{64} = Pr^{2}(G_{3}). Hence, by Theorem 71, G_{2} and G_{3} are not isoclinic.

7 Acknowledgments

We thank both referees for their helpful remarks that gave us an opportunity to significantly improve the presentation of the paper. Our special gratitude is to the referee that paid attention to fruitful connections between block transpositions due to Bafna and Pevzner [1] and the x − −y exchange operation defined in this paper.

References

[1] V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11 (1998) 224–240.

[2] S. R. Blackburn, J. R. Britnell, and M. Wildon, The probability that a pair of elements of a finite group are conjugate, J. Lond. Math. Soc. 86 (2012) 755–778.

[3] S. M. Buckley, Isoclinism and weak isoclinism invariants, preprint,

http://archive.maths.nuim.ie/staff/sbuckley/Papers/gp_isoc.pdf, 2014.

[4] Y. Cherniavsky, A. Goldstein, and V. E. Levit, Groups of balanced labelings on graphs, Discrete Math. 320 (2014) 15–25.

[5] Y. Cherniavsky, A. Goldstein, V. E. Levit, and R. Shwartz, Enumeration of balanced finite group valued functions on directed graphs, Inform. Process. Lett. 116 (2016) 484–488.

[6] Y. Cherniavsky, A. Goldstein, and V. E. Levit, Balanced Abelian group-valued functions on directed graphs, Ars Math. Contemporanea 13 (2017) 307–315.

[7] C. Clifton, D. Guichard, and P. Keef, How commutative are direct products of dihedral groups?, Math. Mag. 84 (2011) 137–140.

[8] A. K. Das and R. K. Nath, A generalization of commutativity degree of finite groups, Comm. Algebra 40 (2012) 1974–1981.

[9] A. K. Das and R. K. Nath, A survey on the estimation of commutativity in finite groups, Southeast Asian Bull. Math. 37 (2013) 161–180.

[10] A. K. Das and R. K. Nath, On generalized commutativity degree of a finite group, Rocky Mountain J. Math. 41 (2011) 1987–2000.

[11] J. Dixon, Probabilistic group theory, C. R. Math. Acad. Sci. Soc. R. Can. 24 (2002) 1–15.

[12] J. P. Doignon and A. Labarre, On Hultman numbers, J. Integer Seq. 10 (2007), Article 07.6.2.

[13] P. Erdős and E. G. Straus, How abelian is a finite group?, Linear Multilinear Algebra 3 (1976) 307–312.

[14] P. Erdős and P. Turan, On some problems of statistical group theory, Acta Math. Acad. Sci. Hungar. 19 (1968) 413–435.

[15] I. V. Erovenko and B. Surg, Commutativity degrees of wreath products of finite abelian groups, Bull. Aust. Math. Soc. 77 (2008) 31–36.

[16] W. H. Gustafson, What is the probability that two group elements commute?, Amer. Math. Monthly 80 (1973) 1031–1034.

[17] R. M. Guralnick and G. R. Robinson, On the commuting probability in finite groups, J. Algebra 300 (2006) 509–528.

[18] P. Hall, The classification of prime-power groups, J. Reine Angew. Math. 182 (1940) 130–141.

[19] U. Jezernik and P. Moravec, Universal commutator relations, Bogomolov multipliers, and commuting probability, J. Algebra 428 (2015) 1–25.

[20] P. Lescot, Central extensions and commutativity degrees, Comm. Algebra 29 (2001) 4451–4460.

[21] P. Lescot, H. N. Nguyen, and Y. Yang, On the commuting probability and supersolvability of finite groups, Monatsh. Math. 174 (2014) 567–576.

[22] R. K. Nath and A. K. Das, On generalized commutativity degree of a finite group, Rocky Mountain J. Math. 41 (2011) 1987–2000.

[23] R. K. Nath, Some New Directions in Commutativity Degree of Finite Groups: Recent Developments, Lambert Academic Publishing, 2011.

[24] M. R. Pournakia and R. Sobhani, Probability that the commutator of two group elements is equal to a given element, J. Pure Appl. Algebra 212 (2008) 727–734.

[25] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences,

    http://www.oeis.org.

2010 Mathematics Subject Classification: Primary 20P05; Secondary 20F12, 20B05, 05A05, 20D60. Keywords: commuting probability, Hultman number, cycle graph of a permutation, isoclinism, finite group.

(Concerned with the sequence \underline{A164652}.)

Received December 17 2015; revised versions received March 29 2017; October 31 2017. Published in Journal of Integer Sequences, November 22 2017.

Return to Journal of Integer Sequences home page.