PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 99–108 https://doi.org/10.2298/PIM1715099B

THE CYCLE INDEX OF THE AUTOMORPHISM GROUP OF ℤ_{n}

Vladimir Bozovic and Žana Kovijanić Vukićević

Abstract. We consider the group action of the automorphism group U_{n} = Aut(ℤ_{n}) on the set ℤ_{n}, that is the set of residue classes modulo n. Clearly, this group action provides a representation of U_{n} as a permutation group acting on n points. One problem to be solved regarding this group action is to find its cycle index. Once it is found, there appears a vast class of related enumerative and computational problems with interesting applications. We provide the cycle index of specified group action in two ways. One of them is more abstract and hence compact, while another one is basically a procedure of composing the cycle index from some building blocks. However, those building blocks are also well explained and finally presented in a very detailed fashion.

1. Introduction

Let U_{n} = Aut(ℤ_{n}) be the automorphism group of the cyclic additive group of residues modulo n. Throughout this paper, we treat ℤ_{n} interchangeably, merely as a set {0, 1, …, n − 1} or as the additive, cyclic group. However, the context in which it is used will clearly determine its meaning.

As it is well known, U_{n} is isomorphic to the multiplicative group of those integers in ℤ_{n} that are relatively prime to n, i.e.,

U_{n} = {π_{a}: ℤ_{n} ↦ ℤ_{n} | π_{a}(x) = ax (mod n), 1 ⩽ a ⩽ n, (a, n) = 1}.

Based on that isomorphism, a mapping π_{a} ∈ U_{n}, can be identified with an element a ∈ ℤ_{n}, (a, n) = 1. Further, we will be frequently using that convenient isomorphic correspondence, without risk of misconception. Hence, the natural group action of the group U_{n} on the set of elements of ℤ_{n} could be seen as

(x, a) ↦ ax (mod n) (a ∈ U_{n}, x ∈ ℤ_{n}),

Clearly, the automorphism group, U_{n}, represented in the described way is a permutation group acting on n points. Although elementary in its nature, it was a surprising fact that, to the best of our knowledge, the cycle index of the described group action is still missing. We found only one paper, [1], that partially deals with the similar group action, and yet substantially different. Therefore, finding the cycle index, Z_{(U_{n} ,ℤ_{n} )}, of the described group action emerges as the main goal of this paper.

2010 Mathematics Subject Classification: Primary 05E99, Secondary: 20B40, 20C40.

Key words and phrases: cycle index, automorphism group of ℤ_{n}.

Communicated by Zoran Petrović.

Based on somewhat distinct, although complement approaches, we get two forms of the same result. The first one that looks more general, whereas another one is technically more detailed, supplying raw structure of cycle index Z_{(U_{n} ,ℤ_{n} )}.

In the first approach, we get a nice, compact result from Corollary 3.1, while in the second approach, we use the fact of the direct decomposition of an additive Abelian group and corresponding decomposition of its automorphism group.

As n can be decomposed as a product of prime number powers, then we proceed by finding the cycle index Z_{(U_{p^{α}} ,ℤ_{p^{α}} )}, for a prime number p and α ∈ ℕ, as a groundwork for utilization of a known result given in [5], that is an algorithm for finding cycle index of direct product of permutation groups.

Once the cycle index is found, there is a vast class of enumerative and combinatorial problems that could be related to it. For example, one of the classical enumerative, combinatorial “targets" is a number of orbits or equivalence classes of subsets of ℤ_{n}.

2. Preliminaries

In this section, we bring up some basic, auxiliary results, notation and assumptions that will be used in the rest of the paper.

• By natural number we assume positive integer.

• By ⨄ we denote disjoint union of sets.

• The label ϕ will be exclusively used for Euler’s phi function.

• By C_{n} we denote a cyclic group of n elements.

• By Sym(M) we denote the full symmetric group on the set M.

• By ord(g) we denote the order of an element g in a group G. Regarding a topic of group action, we slightly changed definitions of classical

notions and accordingly, introduce new notation.

Definition 2.1 (Type of a permutation). Let P be a set with |P | = n. A permutation π ∈ Sym(P) is of the type (λ_{1}, λ_{2}, …, λ_{n}), iff π can be written as a composition of λ_{i} disjointed cycles of length i, for i = 1, …, n.

Hence, by λ_{i}(π) we mean the number of cycles of length i in the decomposition of π into disjoint cycles. We use the short and symbolic notation

ctype(π) = ∏_{i=1}^{n} x_{i}^{λ_{i} (π)}

to mean that there are λ_{i}(π) cycles of length i in the decomposition of π in product of disjoint cycles. Note that variable x_{i} has only formal meaning, referring to the cycle of the length i.

THE CYCLE INDEX OF THE AUTOMORPHISM GROUP OF ℤ_{n} 101

Definition 2.2 (Partial Cycle Index). Let P be a set of |P | = n elements and let Γ be a subset of finite permutation group G_{P} acting on P. The partial cycle index of a subset Γ ⊆ G_{P} is defined as a polynomial in n indeterminates x_{1}, …, x_{n}, defined by

Z_{(Γ,P)} (G_{P}) := \frac{1}{|G_{P}|}∑_{π∈Γ} ctype(π) = \frac{1}{|G_{P}|}∑_{π∈Γ} ∏_{i=1}^{n} x_{i}^{λ_{i} (π)} .

When Γ = G_{P}, then Z_{(G_{P} ,P)}(G_{P}) is called the cycle index of G_{P} on P, or shortly Z_{(G_{P} ,P)}.

It should be emphasized that the natural number n, in the previous definition, is the upper limit regarding the number of indeterminates of cycle index polynomial. The actual number of indeterminates that could appear in the cycle index polynomial is λ(n), that is the maximal order among of all orders of elements in G_{P}.

Directly from the previous definition, we have this simple observation.

Lemma 2.1. Let G_{P} be a permutation group acting on a set P of n elements and let Γ = {Γ_{i} ⊆ G_{P} | 1 ⩽ i ⩽ k, k ∈ N} be a partition of the set of elements of G_{P}. Then, the cycle index of G_{P} on P is Z_{(G_{P} ,P)} = ∑ _{i=1}^{k} Z_{(Γ_{i} ,G_{P} )} (G_{P}).

Proof. It is a direct consequence of Definition 2.1 and the fact that G_{P} is disjoint union of Γ_{i}, i = 1, 2, …, k, i.e., G_{P} = ⨄ _{i=1}^{k} Γ_{i}. □

This notion of partial cycle index will be helpful later. Let us introduce the notion of (r, k)-coprime residue set in ℤ_{n}.

Definition 2.3. Let n be a natural integer and let k be a divisor of n. Denote by r a natural integer less than k and coprime with k. The set of integers

U_{n}^{r}(k) = {x ∈ U_{n} | x ≡ r (mod k)}

is called (r, k)-coprime residue set in ℤ_{n}.

We prove that any (r, k)-coprime set in ℤ_{n} is not empty. It is essentially restatement and slight modification of the result given in Lemma 2, page 32, [6]. This result will be helpful later, in the characterization of orbits of the examined group action.

Lemma 2.2. Let r, k, l, n be natural numbers such that gcd(r, k) = 1, r < k and n = kl. Then the (r, k)-coprime set U_{n}^{r}(k) is nonempty.

Proof. We prove for given r, k and n and gcd(r, k) = 1, there exists t such that gcd(r + kt, n) = 1 Let p_{i}^{v_{i}} be a prime power dividing n. Then, there exists t_{i} such that gcd(r + kt_{i}, p_{i}^{v_{i}} ) = 1. Namely, if p_{i} | k, then p_{i} ∤ r and t_{i} = 0 suffices. If p_{i} ∤ k, than any number t_{i} such that t_{i} ≢ −r/k (mod p_{i}) will work.

By Chinese Reminder Theorem, there exists t such that t ≡ t_{i} (mod p_{i}) and gcd(r + kt, n) = 1. We need to prove that there exists x ∈ U_{n} such that x ≡ r (mod k). Let x ≡ r + kt (mod n). Since k | n then x ≡ r (mod k). Also, it is easy to see that gcd(x, n) = 1 and therefore x ∈ U_{n}. □

We introduce, without proof, the following textbook lemma.

Lemma 2.3. Let C_{n} = ⟨a⟩ be a cyclic group of n elements and let d be a natural number such that d | n. By A_{d} denote the set of all elements of C_{n} of order d. Then

A_{d} = \{a^{\frac{n}{d} t} | t ∈ ℕ and gcd(t, d) = 1\}.

Hence, |A_{d}| = ϕ(d). Also, C_{n} = ⨄ _{d|n} A_{d}.

Let Ω_{n}^{d}, where d | n, be the set of elements of additive order d in the ℤ_{n}. Then, according to Lemma 2.3, we have ℤ_{n} = ⨄ _{d|n} Ω_{n}^{d} and |Ω_{n}^{d}| = ϕ(d). The partition of ℤ_{n}, we just specified, will play an important role in the analysis of the group action, we are dealing with.

3. Cycle index of U_{n} – general case

As pointed in Introduction, we consider the natural group action of the group U_{n} on the set of elements of ℤ_{n}, given by (x, a) ↦ ax (mod n) (a ∈ U_{n}, x ∈ ℤ_{n}).

Based on the results from the previous section, we prove that the typical orbit of the aforementioned group action is actually Ω_{n}^{d}.

Lemma 3.1. Let d, n be natural numbers, such that d | n. Then

Ω_{n}^{d} = \frac{n}{d} · U_{d} = \{ \frac{n}{d} t | 1 ⩽ t ⩽ d and gcd(t, d) = 1\}.

Also, Ω_{n}^{d} is an orbit under the action of the group U_{n} on ℤ_{n}.

Proof. The first fact of the claim is a trivial consequence of Lemma 2.3, so we have Ω_{n}^{d} = \frac{n}{d} · U_{d}. We prove that Ω_{n}^{d} is an orbit in the action of U_{n} on ℤ_{n}.

Let x and y be elements of order d. Then we have x = (n/d)k_{1} and y = (n/d)k_{2} where k_{1}, k_{2} ∈ U_{d}. Therefore, there exists k ∈ U_{d} and k_{1} = kk_{2}.

On the other hand, Lemma 2.2 claims that U_{n}^{k}(d) is nonempty, i.e., the existence of an element h ∈ U_{n} such that h ≡ k (mod d). Clearly k_{1} ≡ hk_{2} (mod d). By multiplying both sides by (n/d), we have x ≡ hy (mod n). Thus, U_{n} is transitive on the set of elements of (additive) order d. □

Let a, d be natural numbers such that gcd(a, d) = 1. Denote by o_{d}(a) the order of a with respect to modulo d, i.e., o_{d}(a) = min{k ∈ ℕ | a^{k} ≡ 1 (mod d)}.

The following lemma has the key role in the description of how the mapping π_{a} : ℤ_{n} ↦ ℤ_{n} , defined as π_{a}(x) = ax (mod n), acts on an orbit Ω_{n}^{d}.

Lemma 3.2. Let d, n, a be natural numbers such that d | n and gcd(a, n) = 1. Consider τ = π_{a} |_{Ω_{n}^{d}} , that is restriction of the mapping π_{a} : ℤ_{n} ↦ ℤ_{n}, defined as π_{a}(x) = ax (mod n), on Ω_{n}^{d}. In other words, τ(x) = ax (mod n), where x ∈ Ω_{n}^{d}.

Then, τ is a permutation of Ω_{n}^{d} and ctype(τ) = x_{k}^{m}, where k = o_{d}(a), m = \frac{ϕ(d)}{k} .

Proof. We know, from Lemma 3.1, that Ω_{n}^{d} is an orbit of π_{a}, so we conclude that τ : Ω_{n}^{d} ↦ Ω_{n}^{d}. Since, π_{a} is a bijection, then τ is certainly injection on Ω_{n}^{d}. However, Ω_{n}^{d} is a finite set, so τ must be a bijection.

According to Lemma 3.1, an arbitrary element c ∈ Ω_{n}^{d} is of the form c = \frac{n}{d}v, where gcd(v, d) = 1. Let us consider the cycle that c belongs to, considering the mapping τ. Suppose that s is the length of the cycle (c ↦ ac ↦ a^{2}c ↦ ⋯↦ a^{s−1} c).

From a^{k}v ≡ v (mod d) it follows (a^{k} − 1)v = dt, for some t ∈ ℤ. Therefore, (a^{k} − 1)\frac{n}{d}v = nt, that means a^{k}c ≡ c (mod n). Since s is the least number such that a^{s}c ≡ c (mod n), then s ⩽ k.

On the other hand, from a^{s}c ≡ c (mod n), it follows a^{s}v ≡ v (mod d). Since gcd(v, d) = 1, we conclude a^{s} ≡ 1 (mod d). However, k = o_{d}(a) and thus k ⩽ s, so we finally get k = s. Since c is an arbitrary element in Ω_{n}^{d}, we conclude that every cycle of τ is of the same length k = o_{d}(a). □

Corollary 3.1. Let n, a be natural numbers such that d | n and gcd(a, n) = 1. Then the bijection π_{a} : ℤ_{n} ↦ ℤ_{n}, defined as π_{a}(x) = ax (mod n), has cyclic structure ctype(a) = ∏ _{d|n} x_{o_{d} (a)}^{ϕ(d) /o_{d} (a)} .

Accordingly, the cycle index of U_{n}, acting on the set ℤ_{n}, is

(3.1)  Z_{(U_{n} ,ℤ_{n} )} = \frac{1}{ϕ(n)} ∑_{a∈U_{n}} ∏_{d|n} xo_{d} (a)^{\frac{ϕ(d)}{o_{d} (a)}} .

We should notice that the number of indeterminates in the polynomial Z_{(U_{n} ,ℤ_{n} )} is actually equal to the maximal multiplicative order among elements in U_{n}, that is λ(n) = max{o_{n}(a) | a ∈ U_{n}}.

In number theory, λ is known as Charmichael’s lambda function. As it is principally analysed and resolved in [8], for a natural number n represented as a product of powers of prime numbers n = ∏ _{i=1}^{k} p_{i}^{e_{i}} , we have that λ(n) is equal to the least common multiplier of λ(p_{i}^{e_{i}} ), for i = 1, …, k. Thus,

λ(n) = lcm(λ(p_{1}^{e_{1}} ), λ(p_{2}^{e_{2}} ), …, λ(p_{k}^{e_{k}} )),

where

λ(p^{e}) = \{ \begin{matrix}ϕ(p^{e}) & if p an odd prime, e ⩾ 1 \\ ϕ(2^{e}) & if p = 2, e ⩽ 2 \\ 2^{e−2} & if p = 2, e > 2. \end{matrix}

Therefore, only indeterminates x_{1}, x_{2}, …, x_{λ(n)} appear in the cycle index Z_{(U_{n} ,ℤ_{n} )}.

4. Cycle index of U_{p^{m}}

In this section, we present a more comprehensive look over the cycle index of the group U_{p^{m}} acting on ℤ_{p^{m}} . Since the algebraic structure of U_{p^{m}} differs in two basic cases: when p = 2 and when p is an odd prime number, we will consider both in the course of finding cycle index of U_{n}.

Once a cycle index of U_{p^{m}} , for a prime number p, is found, it will serve as a building block for compounding cycle index of U_{n}, where n is naturally represented as a product of powers of prime numbers.

4.1. Cycle index of U_{2^{m}} . We start with the case of U_{2^{m}} acting on ℤ_{2^{m}} . First of all, we need to determine how elements of U_{2^{m}} look like, considering the fact that it is not a cyclic group for m ⩾ 3, but direct product C_{2} × C_{2^{m−2}} . Still, there is a way for all elements of U_{2^{m}} to be represented in a functional form.

Definition 4.1. An integer a is said to be a semi-primitive root modulo n if the order of a modulo n is equal to ϕ(n)/2, where ϕ is the Euler function.

It is shown in [9] that 3 is a semi-primitive root modulo 2^{m}. Thus, the order of 3 modulo 2^{m} is 2^{m−2} , for any integer m ⩾ 3 and

U_{2^{m}} = {±3^{i} (mod 2^{m}) : i = 1, …, 2^{m−2} }.

Then, the following lemma is just rewording of the previous fact.

Lemma 4.1. For an arbitrary element w ∈ U_{2^{m}} , if m ⩾ 3, there exists a unique pair (a, b), a ∈ {0, 1} and b ∈ {0, 1, …, 2^{m−2} − 1} such that w = (−1)^{a}3^{b}.

It might be useful to mention that 5 is also a semi-primitive for U_{2^{m}} , m ⩾ 3. The following corollaries are either obvious or direct consequences of Lemma 4.1.

Corollary 4.1. Let a = 3^{2^{s} r}, d = 2^{l}, where s ⩾ 0, r = 1, 3, …, 2^{m−2−s} − 1, l ⩾ 1. Then

o_{d}(a) = \{ \begin{matrix}1 & if l = 1; s ⩾ 0, \\ 2 & if l = 2; s = 0, \\ 1 & if l = 2; s ⩾ 1, \\ 2^{l−2−s} & if l ⩾ 3; s < l − 2, \\ 1 & if l ⩾ 3; s ⩾ l − 2. \end{matrix}

Corollary 4.2. Let a = −3^{2^{s} r}, d = 2^{l}, where s ⩾ 0, r = 1, 3, …, 2^{m−2−s} − 1,

l ⩾ 1. Then

o_{d}(a) = \{ \begin{matrix}1 & if l = 1; s ⩾ 0, \\ 1 & if l = 2; s = 0, \\ 2 & if l = 2; s ⩾ 1, \\ 2^{l−2−s} & if l ⩾ 3; s < l − 2, \\ 2 & if l ⩾ 3; s ⩾ l − 2. \end{matrix}

Lemma 4.2. Let us consider

Γ_{1} = {3^{2^{s} r} | s = 0, 1, …, m − 3, r = 0, 1, 3, …, 2^{m−2−s} − 1}

as a subset of the group U_{2^{m}} , for m ⩾ 3. Then, the partial cycle index of this set is

Z_{(Γ_{1} ,ℤ_{2^{m}} )} (U_{2^{m}} ) = \frac{1}{2^{m−1}} ( x_{1}^{2^{m}} + 2^{m−3} x_{1}^{2}x_{2} ∏_{l=3}^{m} x_{2^{l−2}}^{2} + ∑_{t=0}^{m−4} 2^{t}x_{1}^{2^{m−1−t}} ∏_{i=0}^{t} x_{2^{i+1}}^{2^{m−2−t}} ) .

Proof. Since all orbits of the multiplicative action of the group U_{2^{m}} on ℤ_{2^{m}} are of the form Ω_{2^{m}}^{2^{l}} , where 0 ⩽ l ⩽ m, it is important to find out the behaviour of particular mappings x ↦ 3^{2^{s} r} x (mod n), where x ∈ ℤ_{2^{m}} , on those orbits. As stated before, we are interested in ctypes of those mappings on Ω_{2^{m}}^{2^{l}} . In order to find ctype of the mappings 3^{2^{s} r} is restricted on orbit Ω_{2^{m}}^{2^{l}} , we use the results of Corollary 4.1.

Firstly, all elements from Γ_{1} are fixing Ω_{2^{m}}^{1} = {0} and Ω_{2^{m}}^{2} = {2^{m−1} } as one-element orbits.

By considering parameter l in the result of Corollary 4.1, we distinguish two major cases: when l < 3 and when l ⩾ 3. Accordingly, the orbits

Ω_{2^{m}}^{1} = {0}, Ω_{2^{m}}^{2} = {2^{m−1} }, Ω_{2^{m}}^{2^{2}} = {2^{m−2} , 2^{m} − 2^{m−2} }

should be treated separately. For example, for the mappings of the form 3^{r}, where r = 1, 3, …, 2^{m−2−s} − 1, we have ctype(3^{r}) = x_{1}^{2}x_{2} ∏ _{l=3}^{m} x_{2^{l−2}}^{2} .

The total number of these mappings from Γ_{1} is 2^{m−3} . For those mappings from Γ_{1} of the form 3^{2^{s} r}, when s ⩾ 1, we have

ctype(3^{2^{s} r}) = x_{1}^{4} ∏_{l=3}^{s+2} x_{1}^{2^{l−1}} ∏_{l=s+3}^{m} x_{2^{l−2−s}}^{2^{s+1}} = x_{1}^{2^{s+2}} ∏_{l=s+3}^{m} x_{2^{l−2−s}}^{2^{s+1}} .

The total number of these elements is 2^{m−3−s} . Clearly, for r = 0, we get identity and ctype of it is x_{1}^{2^{m}} .

Finally, by adding all them together, after some elementary algebraic manipulation, we get a partial cycle index of the subset Γ_{1}

Z_{(Γ_{1} ,ℤ_{2^{m}} )} (U_{2^{m}}) = \frac{1}{2^{m−1}} (x_{1}^{2^{m}} +2^{m−3} x_{1}^{2}x_{2} ∏_{l=3}^{m} x_{2^{l−2}}^{2} +∑_{t=0}^{m−4} 2^{t}x_{1}^{2^{m−1−t}}  ∏_{i=0}^{t} x_{2^{i+1}}^{2^{m−2−t}} ) . □

Lemma 4.3. Let us consider

Γ_{2} = −{3^{2^{s} r} | s = 0, 1, …, m − 3, r = 0, 1, 3, …, 2^{m−2−s} − 1},

as a subset of the group U_{2^{m}} , for m ⩾ 3. Then, the partial cycle index of this set, Z_{(Γ_{2} ,ℤ_{2^{m}} )} (U_{2^{m}} ), is

\frac{1}{2^{m−1}} ( x_{1}^{2}x_{2}^{2^{m} −2} + 2^{m−3} x_{1}^{4} ∏_{l=3}^{m} x_{2^{l−2}}^{2} + x_{1}^{2} ∑_{t=0}^{m−4} 2^{t}x_{2}^{2^{m−t−1} −1} ∏_{i=1}^{t} x_{2^{i+1}}^{2^{m−t−2}} ).

Proof. Similarly, as in the proof of Lemma 4.2, we use the result from Corollary 4.2. Note that ctype(−1) = x_{1}^{2}x_{2}^{2^{m} −2} . By using the same type of reasoning used to prove Lemma 4.2, we get the result. □

Corollary 4.3. Let Γ_{1} and Γ_{2} be subsets of the group U_{2^{m}} , m ⩾ 3, as introduced in Lemmas 4.2 and 4.3. Then U_{2^{m}} = Γ_{1} ⊎ Γ_{2}.

Proof. According to Lemma 4.1, every number from U_{2^{m}} , if not −1 or 1, has the form (−1)^{a}3^{2^{s} r} where a ∈ {0, 1}, s ∈ {0, 1, …, m − 3} and r is an odd number, so Γ_{1} ∪ Γ_{2} = U_{2^{m}} . Also, from the same lemma it follows that Γ_{1} ∩ Γ_{2} = ∅. Hence, Γ_{1} ⊎ Γ_{2} is a disjoint union and equal to U_{2^{m}} . □

Lemma 4.4. The cycle index Z = Z_{(U_{2^{m}} ,ℤ_{2^{m}} )} of the permutation group U_{2^{m}} acting on ℤ_{2^{m}} is

Z = x_{1}^{2} if m = 1,
Z = \frac{1}{2}(x_{1}^{4} + x_{1}^{2}x_{2}) if m = 2,
Z = \frac{1}{2^{m−1}} (Z_{1} + Z_{2}) if m ⩾ 3, where
Z_{1} = x_{1}^{2^{m}} + 2^{m−3} x_{1}^{2}x_{2} ∏_{l=3}^{m} x_{2^{l−2}}^{2} + ∑_{t=0}^{m−4} 2^{t}x_{1}^{2^{m−1−t}}  ∏_{i=0}^{t} x_{2^{i+1}}^{2^{m−2−t}} ,

Z_{2} = x_{1}^{2}x_{2}^{2^{m} −2} + 2^{m−3} x_{1}^{4} ∏_{l=3}^{m} x_{2^{l−2}}^{2} + x_{1}^{2} ∑_{t=0}^{m−4} 2^{t}x_{2}^{2^{m−t−1} −1} ∏_{i=1}^{t} x_{2^{i+1}}^{2^{m−t−2}} .

Proof. The claim follows trivially for m = 1 and m = 2. For the case m ⩾ 3, we use the results given in Lemmas 4.2 and 4.3, combined with the fact given in Corollary 4.3, that U_{2^{m}} = Γ_{1} ⊎ Γ_{2}. □

4.2. Cycle index od U_{p^{m}} , where p is an odd, prime number. The following lemma considers the case of U_{p^{m}} , where p is an od prime number. As it has been already noted, this group is cyclic and consequently, it is much easier to find its cycle index.

Lemma 4.5. Let p be an odd prime. The cycle type of the permutation group U_{p^{m}} acting on ℤ_{p^{m}} is

Z_{(U_{p^{m}} ,ℤ_{p^{m}} )} = \frac{1}{ϕ(p^{m})} ∑_{k=1}^{ϕ(p^{m} )} ∏_{i=0}^{m} x_{u(i,k)}^{v(i,k)} ,

where v(i, k) = (ϕ(p^{i}), k) and u(i, k) = \frac{ϕ(p^{i})}{v(i, k)}.

Proof. It is well known that in the case of an odd prime p, the automorphism group U_{p^{m}} is cyclic [10]. Let β be a generator of U_{p^{m}} . Then, ord(β) = ϕ(p^{m}). It is an elementary fact that in an arbitrary group G and g ∈ G, such that ord(g) = n it holds that ord(g^{k}) = n/(k, n).

Since o_{p^{i}} (β) = ϕ(p^{i}), for i = 0, 1, …, m, we conclude that

o_{p^{i}} (β^{k}) = \frac{ϕ(p^{i})}{(k, ϕ(p^{i}))}, for i = 0, 1, …, m.

Now, the claim follows directly from (3.1). □

4.3. Cycle index of direct product of permutation groups. Since we found the cycle indices of all groups U_{p^{m}} when p is a prime number, there is a natural question if there exists a way to combine them together in order to obtain the cycle index of U_{n}, where n is the product of those prime power components. Hence, we need something like the cycle index of the direct product of permutation groups.

Let G_{1}, G_{2} be permutation groups acting on sets X_{1}, X_{2} respectively. Let G = G_{1} × G_{2} and X = X_{1} × X_{2} be the direct product of corresponding groups and sets. For an element x = (x_{1}, x_{2}) of X and an element g = (g_{1}, g_{2}) of G, we define the action of g on x by (g, a) ↦ (g_{1}x_{1}, g_{2}x_{2}).

Evidently, G is a permutation group on X. Let P and Q be polynomials

P (x_{1}, x_{2}, …, x_{u}) = ∑ a_{i_{1} i_{2} ...i_{u}} x_{1}^{i_{1}} x_{2}^{i_{2}} …x_{u}^{i_{u}} ,
Q(x_{1}, x_{2}, …, x_{v}) = ∑ b_{j_{1} j_{2} ...j_{v}} x_{1}^{j_{1}} x_{2}^{j_{2}} …x_{v}^{j_{v}}

In [5] the following product operator was defined

P ⊛ Q = ∑ a_{i_{1} i_{2} ...i_{u}} b_{j_{1} j_{2} ...j_{v}} ∏_{\begin{matrix}1⩽l⩽u \\ 1⩽m⩽v \end{matrix}} (x_{l}^{i_{1}} ⊛ x_{m}^{j_{m}} ),

where x_{l}^{i_{1}} ⊛ x_{m}^{j_{m}} = x_{lcm (l,m)}^{i_{1} j_{m} gcd (l,m)} .

We need the following lemma. For proof, see [1, 5].

Lemma 4.6. The cycle index of the natural action of permutation group G_{1}×G_{2} on X_{1} × X_{2} induced by actions G_{1} on X_{1} and G_{2} on X_{2} can be expressed as:

Z_{(G_{1} ×G_{2} ,X_{1} ×X_{2} )} = Z_{(G_{1} ,X_{1} )} ⊛ Z_{(G_{2} ,X_{2} )} .

Let n = ∏ _{i=1}^{s} p_{i}^{α_{i}} . Applying the ring isomorphism ℤ_{n} ≅ ⨁ _{i=1}^{s} ℤ_{p_{i}^{α_{i}}} , it follows that U_{n} ≅ ⨁ _{i=1}^{s} U_{p_{i}^{α_{i}}} . Hence, according to Lemma 4.6, we have

Z_{(U_{n} ,ℤ_{n} )} = Z_{(U_{p{α_{1} \atop 1}} ,ℤ_{p{α_{1} \atop 1}} )} ⊛ Z_{(U_{p{α_{2} \atop 2}} ,ℤ_{p{α_{2} \atop 2}} )} ⊛ ⋯⊛ Z_{(U_{p{αs \atop s}} ,ℤ_{p{αs \atop s}} )}.

Since the cycle indices of prime power components are given in Lemmas 4.4 and 4.5, the cycle index Z_{(U_{n} ,ℤ_{n} )} can be calculated as above.

Example 4.1. Let us find the cycle index of U_{60}. From Lemmas 4.4 and 4.5, we know that

Z_{(U_{2^{2}} ,ℤ_{2^{2}} )} = \frac{1}{2}(x_{1}^{4}+x_{1}^{2}x_{2}), Z_{(U_{3} ,ℤ_{3} )} = \frac{1}{2}(x_{1}^{3}+x_{1}x_{2}), Z_{(U_{5} ,ℤ_{5} )} = \frac{1}{4}(x_{1}^{5}+2x_{1}x_{4}+x_{1}x_{2}^{2}).

Therefore, and according to Lemma 4.6 Z_{(U_{60} ,ℤ_{60} )} = Z_{(U_{2^{2}} ,ℤ_{2^{2}} )} ⊛Z_{(U_{3} ,ℤ_{3} )} ⊛Z_{(U_{5} ,ℤ_{5} )}.

Firstly, we calculate the product of the first two cycle indices, that actually is Z_{(U_{12} ,ℤ_{12} )}. So,

Z_{(U_{12} ,ℤ_{12} )} = Z_{(U_{2^{2}} ,ℤ_{2^{2}} )} ⊛ Z_{(U_{3} ,ℤ_{3} )}

= \frac{1}{2}(x_{1}^{4} + x_{1}^{2}x_{2}) ⊛ \frac{1}{2}(x_{1}^{3} + x_{1}x_{2}) = \frac{1}{4}(x_{1}^{12} + x_{1}^{4}x_{2}^{4} + x_{1}^{2}x_{2}^{5} + x_{1}^{6}x_{2}^{3}).

Finally, we get

Z_{(U_{60} ,ℤ_{60} )} = Z_{(U_{12} ,ℤ_{12} )} ⊛ Z_{(U_{5} ,ℤ_{5} )}

= \frac{1}{4}(x_{1}^{12} + x_{1}^{4}x_{2}^{4} + x_{1}^{2}x_{2}^{5} + x_{1}^{6}x_{2}^{3}) ⊛ \frac{1}{4}(x_{1}^{5} + 2x_{1}x_{4} + x_{1}x_{2}^{2})

= \frac{1}{16}(x_{1}^{60} + 2x_{1}^{4}x_{2}^{4}x_{4}^{12} + x_{1}^{4}x_{2}^{28} + 2x_{1}^{2}x_{2}^{5}x_{4}^{12} + x_{1}^{2}x_{2}^{29} + 2x_{1}^{6}x_{2}^{3}x_{4}^{12}

+ x_{1}^{6}x_{2}^{27} + 2x_{1}^{12}x_{4}^{12} + x_{1}^{12}x_{2}^{24} + x_{1}^{10}x_{2}^{25} + x_{1}^{20}x_{2}^{20} + x_{1}^{30}x_{2}^{15}).

Certainly, the same result could be obtained by a simple application of (3.1).

5. Conclusions

We studied the group action of the automorphism group U_{n} = Aut(ℤ_{n}) on the set ℤ_{n}, that is the set of residue classes modulo n. The main goal of the paper was to find the cycle index of that action. Based on some elementary number theory and algebraic techniques, we get a nice, compact result in Corollary 3.1. Also, in Lemmas 4.4 and 4.5, we provided a technically more detailed look at the building blocks of cycle index of the studied group action.

In the further research, as we announced in Introduction, it could be interesting to examine some combinatorial problems such as a problem of finding the number of orbits or equivalence classes of subsets of ℤ_{n}. Namely, there is a natural way to induce the discussed group action on the set O_{k}, standing for the set of all subsets of ℤ_{n} of size k ⩽ n and then the task could be principally resolved by Pólya’s theory application as in [3, 11, 12].

It is worth mentioning that the number of orbits of sets of O_{k} is related to the problem of factorizations of Abelian groups into the direct product of subsets that is examined in [2, 4, 7]. Hence, it seems that some further research in this topic could be very fruitful.

References

1. W. Wei, J. Xu, Cycle index of direct product of permutation groups and number of equivalence classes of subsets of Z_{v}, Discrete Math. 123(1–3) (1993), 179–188.

2. V. Božović, N. Pace, Factorization of groups using free mappings, J. Algebra Appl. 7 (2008), 647–662.

3. N. G. De Bruijn, A survey of generalizations of Pólya’s enumeration theorem, Nieuw Arch. Wiskd., III. Ser. 19 (1971), 89–112.

4. A. D. Sands, On the factorization of finite groups, J. Lond. Math. Soc. 2 (1974), 627–631.

5. M. A. Harrison, R. G. High, On the cycle index of a product of permutation groups, J. Comb. Theory 4 (1968), 277–299.

6. H. Cohn, Advanced Number Theory, Dover, 1980.

7. S. Szabó, Topics in Factorization of Abelian Groups, Birkhäuser, 2004.

8. R. D. Carmichael, The Theory of Numbers, Wiley, 1914.

9. C. F. Gauss, A. A. Clarke, Disquisitiones Arithemeticae, Springer, 1986.

10. H. J. Zassenhaus, The Theory of Groups, Dover, 1958.

11. G. Pólya, R. C. Read, Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987.

12. N. G. De Bruijn, Pólya Theory of Counting, E. F. Wiley, 1964, 144–184.

Faculty of Natural Sciences and Mathematics (Received 15 03 2016) University of Montenegro (Revised 06 11 2016) Podgorica Montenegro

   vladimirb@ac.me, vladobozovic@gmail.com
   zanak@rc.pmf.ac.me