Introduction
A discrete dynamical system is a pair ( S , f ) (S,f) ( S , f ) , where the state space S S S is a finite set and f f f is a self map of S S S . The iteration of the function f f f determines the evolution of each state of the state space S S S in a discrete time [10 ] . Associated with the discrete dynamical system ( S , f ) (S,f) ( S , f ) is a directed graph G f ( S ) \mathcal{G}_f(S) G f ( S ) , known as the functional graph of f f f over S S S , with vertex set V = S V=S V = S and directed edges E = { ( x , f ( x ) ) ∣ x ∈ S } E=\{(x,f(x))\mid x\in S\} E = {( x , f ( x )) ∣ x ∈ S } . This digraph is a visual representation of the evolution of each state of S S S under the function f f f .
Flajolet and Odlyzko [6 ] determined the asymptotic behavior of the functional graph associated with the discrete dynamical system ( S , f ) (S,f) ( S , f ) , where f f f is a function selected uniformly at random. They obtain stochastic parameters, such as the expectation for cycle length, number of connected components and number of cycles of a given length for a function taken with uniform probability from the set S S S^{S} S S of all self maps of S S S . The same statistical properties for random permutations can be found in [19 ] . Therefore, obtaining such parameters for a smaller set of functions is a natural way to compare their dynamical behavior to those of a truly random function. Many function families over finite structures have been investigated in that sense [11 , 15 , 16 , 17 ] .
The case where the state space S S S is a finite field is particularly important due to its diverse applications in areas such as cybersecurity [3 , 14 ] , pseudorandom number generation [5 , 13 , 20 , 22 ] and biology [1 , 7 ] . Within this setting, dynamical systems induced by permutations are often sought out for being building blocks in cryptographic protocols. In this case, the functional graph consists exclusively of disjoint cycles, so that its dynamical behavior is completely determined by its cycle structure. Consequently, the number and lengths of cycles provide natural parameters for studying and comparing families of permutations over finite fields.
In this paper, we investigate stochastic properties of the functional graphs of two families of permutations: affine permutations over the finite cyclic group of order p e p^{e} p e and generalized cyclotomic permutations over finite fields. Introduced by Niederreiter and Winterhof [12 ] and Wang [21 ] , generalized cyclotomic mappings (or GCMs) of index d d d are a generalization of monomial maps. Let q q q be a prime power and d d d a divisor of q − 1 q-1 q − 1 . An index d d d GCM of the finite field F q \mathbb{F}_{q} F q is any function f : F q → F q f:\mathbb{F}_{q}\to\mathbb{F}_{q} f : F q → F q that satisfies f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 and agrees with a monomial function when restricted to each of the d d d cosets of the unique index d d d subgroup of F q ∗ \mathbb{F}_{q}^{*} F q ∗ . A generalized cyclotomic permutation (or GCP) is a bijective GCM. The functional graphs of index d d d GCMs are described by Bors, Panario and Wang in [2 ] .
Clearly, any monomial permutation over F q \mathbb{F}_{q} F q is an index 1 GCP. Their functional graph, described in [4 ] , is highly dependent on the divisors of q − 1 q-1 q − 1 . However, any permutation of F q \mathbb{F}_{q} F q that fixes 0 is a GCP of index q − 1 q-1 q − 1 . Thus, a randomly selected GCP is essentially a random permutation of F q ∗ \mathbb{F}_{q}^{*} F q ∗ . A natural question is how the cycle statistics of GCPs change as the index increases, and how far from q − 1 q-1 q − 1 the index can be while maintaining cycle statistics comparable to those of uniformly random permutations.
We obtain a group isomorphism through discrete logarithm between the index d d d subgroup of F q ∗ \mathbb{F}_{q}^{*} F q ∗ and the additive group Z s \mathbb{Z}_{s} Z s , where s = q − 1 d s=\frac{q-1}{d} s = d q − 1 . We then obtain the expected number of cycles and the expected length of the cycle that contains a random element in the functional graph of a randomly selected generalized cyclotomic permutation in terms of the same expectations for affine permutations over Z s \mathbb{Z}_s Z s .
Moreover, we determine explicit closed formulas for these expectations in affine permutations over Z p e \mathbb{Z}_{p^e} Z p e , where p p p is a prime and e e e is a positive integer. When p e p^e p e divides q − 1 q-1 q − 1 , we consider index d = q − 1 p e d=\frac{q-1}{p^e} d = p e q − 1 GCPs. The exponent e e e provides a natural parameter for controlling the size of d d d , and consequently its distance from the maximal possible index q − 1 q-1 q − 1 . We derive the expectations for GCPs of this particular index and observe their asymptotics as e e e grows. Finally, we provide a comparison between these expectations with the corresponding expectations for uniformly random permutations over a set of the same size.
We end this section by providing the structure of the paper. In Section 3, we describe the dynamical behavior of GCMs, determined by Bors, Panario and Wang in [2 ] . In Section 4, we derive a formula for the two statistical properties of index d d d GCPs in terms of the corresponding properties for affine permutations over Z s \mathbb{Z}_s Z s . In Section 5, we present Deng’s [4 ] characterization of functional graphs of affine maps over the finite cyclic group Z s \mathbb{Z}_s Z s . Using this characterization, in Section 6 we derive the stochastic parameters for affine permutations over Z p e \mathbb{Z}_{p^e} Z p e . In Section 7, we provide a comparison between the properties from affine permutations over Z p e \mathbb{Z}_{p^e} Z p e and GCPs against the corresponding expectations for random permutations. In Section 8, we conclude the paper by summarizing our findings and presenting problems for future research.
Preliminary properties
In this section we present a list of lemmas needed in the proofs of our main results.
Throughout the paper, p p p is a prime, [ a , b ] [a,b] [ a , b ] is the set of nonnegative integers greater or equal to a a a and smaller or equal to b b b , Z n \mathbb{Z}_n Z n is the finite additive group of integers modulo n n n and ord n ( a ) \operatorname{ord}_n(a) ord n ( a ) is the smallest positive integer k k k such that a k ≡ 1 ( m o d n ) a^k \equiv1 \pmod{n} a k ≡ 1 ( mod n ) , for a a a coprime with n n n . Moreover, we define ν p ( a ) \nu_p(a) ν p ( a ) as the greatest k ∈ Z k \in\mathbb{Z} k ∈ Z such that p k p^k p k divides a a a and set ν p ( 0 ) = ∞ \nu_p(0)=\infty ν p ( 0 ) = ∞ .
Lemma 2.1 (Lifting The Exponent Lemma [9 ] ). Let x x x and n n n be integers, and p p p be a prime.
If p p p is an odd prime and ν p ( x − 1 ) > 0 \nu_p(x-1)>0 ν p ( x − 1 ) > 0 , then ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) \nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n) ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) .
If p = 2 p=2 p = 2 and n n n is odd, then ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) = 0 \nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n)=0 ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) = 0 .
If p = 2 p=2 p = 2 , n n n is even and x ≡ 1 ( m o d 4 ) x\equiv1 \pmod{4} x ≡ 1 ( mod 4 ) , then ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) \nu_p(x^n-1)-\nu_p(x-1)=\nu_p(n) ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( n ) .
If p = 2 p=2 p = 2 , n n n is even and x ≡ 3 ( m o d 4 ) x\equiv3 \pmod{4} x ≡ 3 ( mod 4 ) , then ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( x + 1 2 ) + ν p ( n ) \nu_p(x^n-1)-\nu_p(x-1)=\nu_p\left(\frac{x+1}{2}\right)+\nu_p(n) ν p ( x n − 1 ) − ν p ( x − 1 ) = ν p ( 2 x + 1 ) + ν p ( n ) .
Lemma 2.2. Let p p p be a prime, j j j a nonnegative integer, k k k a positive integer and i ∈ [ 1 , p − 1 ] i\in[1,p-1] i ∈ [ 1 , p − 1 ] . If p p p is odd, d = ord p ( i ) d=\operatorname{ord}_p(i) d = ord p ( i ) and t = ν p ( ( j p + i ) d − 1 ) t=\nu_p((jp+i)^d-1) t = ν p (( j p + i ) d − 1 ) , then ord p k ( j p + i ) = d ⋅ p max { 0 , k − t } \operatorname{ord}_{p^k}(jp+i)=d\cdot p^{\max\{0,k-t\}} ord p k ( j p + i ) = d ⋅ p m a x { 0 , k − t } .
If p = 2 p=2 p = 2 , then ord 2 k ( 4 j + 1 ) = 2 max { 0 , k − 2 − ν 2 ( j ) } \operatorname{ord}_{2^k}(4j+1)=2^{\max\{0,k-2-\nu_2(j)\}} ord 2 k ( 4 j + 1 ) = 2 m a x { 0 , k − 2 − ν 2 ( j )} . Moreover, ord 2 ( 4 j + 3 ) = 1 \operatorname{ord}_2(4j+3)=1 ord 2 ( 4 j + 3 ) = 1 and, for all k > 1 k>1 k > 1 , ord 2 k ( 4 j + 3 ) = 2 max { 1 , k − 2 − ν 2 ( j + 1 ) } \operatorname{ord}_{2^k}(4j+3)=2^{\max\{1,k-2-\nu_2(j+1)\}} ord 2 k ( 4 j + 3 ) = 2 m a x { 1 , k − 2 − ν 2 ( j + 1 )} .
Proof. Let p p p be an odd prime. For k = 1 k=1 k = 1 , we have that j p + i ≡ i ( m o d p ) jp+i\equiv i\pmod{p} j p + i ≡ i ( mod p ) , thus ord p ( j p + i ) = ord p ( i ) = d \operatorname{ord}_p(jp+i)=\operatorname{ord}_p(i)=d ord p ( j p + i ) = ord p ( i ) = d . Moreover, since p p p divides p k p^k p k we have that ord p k ( j p + i ) = d ⋅ r \operatorname{ord}_{p^k}(jp+i)=d\cdot r ord p k ( j p + i ) = d ⋅ r , for some positive integer r r r . Hence, by Lemma 2.1, if k > 1 k>1 k > 1 we have that
ν p ( ( j p + i ) ord p k ( j p + i ) − 1 ) = ν p ( ( j p + i ) d ⋅ r − 1 ) = ν p ( ( j p + i ) d − 1 ) + ν p ( r ) ≥ k . \nu_p\left((jp+i)^{\operatorname{ord}_{p^k}(jp+i)}-1\right)=\nu_p\left((jp+i)^{d\cdot r}-1\right)=\nu_p\left((jp+i)^d-1\right)+\nu_p(r)\geq k. ν p ( ( j p + i ) ord p k ( j p + i ) − 1 ) = ν p ( ( j p + i ) d ⋅ r − 1 ) = ν p ( ( j p + i ) d − 1 ) + ν p ( r ) ≥ k .
This implies that r r r is the minimal positive integer that satisfies ν p ( r ) ≥ k − t \nu_p(r)\geq k-t ν p ( r ) ≥ k − t . Hence r = p max { 0 , k − t } r=p^{\max\{0,k-t\}} r = p m a x { 0 , k − t } .
For p = 2 p=2 p = 2 , from Lemma 2.1, we have that ord 2 k ( 4 j + 1 ) \operatorname{ord}_{2^k}(4j+1) ord 2 k ( 4 j + 1 ) is the minimal nonnegative integer r r r that satisfies
ν 2 ( ( 4 j + 1 ) r − 1 ) = ν 2 ( 4 j ) + ν 2 ( r ) ≥ k . \nu_2\left((4j+1)^r-1\right)=\nu_2(4j)+\nu_2(r)\geq k. ν 2 ( ( 4 j + 1 ) r − 1 ) = ν 2 ( 4 j ) + ν 2 ( r ) ≥ k .
Hence, we get that ord 2 k ( 4 j + 1 ) = 2 max { 0 , k − 2 − ν 2 ( j ) } \operatorname{ord}_{2^k}(4j+1)=2^{\max\{0,k-2-\nu_2(j)\}} ord 2 k ( 4 j + 1 ) = 2 m a x { 0 , k − 2 − ν 2 ( j )} .
For 4 j + 3 4j+3 4 j + 3 , we have trivially that ord 2 ( 4 j + 3 ) = 1 \operatorname{ord}_2(4j+3)=1 ord 2 ( 4 j + 3 ) = 1 . If k > 1 k>1 k > 1 , the multiplicative order of any odd integer in Z 2 k \mathbb{Z}_{2^k} Z 2 k is a power of 2, since it divides 2 k − 1 2^{k-1} 2 k − 1 , the cardinality of the multiplicative group of Z 2 k \mathbb{Z}_{2^k} Z 2 k . Moreover, we observe that ν 2 ( ( 4 j + 3 ) − 1 ) = 1 \nu_2((4j+3)-1)=1 ν 2 (( 4 j + 3 ) − 1 ) = 1 , hence ord 2 k ( 4 j + 3 ) > 1 \operatorname{ord}_{2^k}(4j+3)>1 ord 2 k ( 4 j + 3 ) > 1 . Therefore, from Lemma 2.1 we get that ord 2 k ( 4 j + 3 ) \operatorname{ord}_{2^k}(4j+3) ord 2 k ( 4 j + 3 ) is the minimal positive integer r r r that satisfies
ν 2 ( ( 4 j + 3 ) 2 r − 1 ) = 2 + ν 2 ( j + 1 ) + r ≥ k . \nu_2\left((4j+3)^{2^r}-1\right)=2+\nu_2(j+1)+r\geq k. ν 2 ( ( 4 j + 3 ) 2 r − 1 ) = 2 + ν 2 ( j + 1 ) + r ≥ k .
Thus, we conclude that ord 2 k ( 4 j + 3 ) = 2 max { 1 , k − 2 − ν 2 ( j + 1 ) } \operatorname{ord}_{2^k}(4j+3)=2^{\max\{1,k-2-\nu_2(j+1)\}} ord 2 k ( 4 j + 3 ) = 2 m a x { 1 , k − 2 − ν 2 ( j + 1 )} .
The following lemma is known as Hensel’s lifting lemma.
Lemma 2.3. [8 Chapter 5, Theorem 3] If f ( x ) ∈ Z [ x ] f(x)\in\mathbb{Z}[x] f ( x ) ∈ Z [ x ] and a ∈ Z p a\in\mathbb{Z}_p a ∈ Z p satisfies f ( a ) ≡ 0 ( m o d p ) f(a)\equiv0\pmod{p} f ( a ) ≡ 0 ( mod p ) and f ′ ( a ) ≢ 0 ( m o d p ) f'(a)\not\equiv0\pmod{p} f ′ ( a ) ≡ 0 ( mod p ) , then there is a unique α k ∈ Z p k \alpha_k\in\mathbb{Z}_{p^k} α k ∈ Z p k such that f ( α k ) ≡ 0 ( m o d p k ) f(\alpha_k)\equiv0\pmod{p^k} f ( α k ) ≡ 0 ( mod p k ) and α k ≡ a ( m o d p ) \alpha_k\equiv a\pmod{p} α k ≡ a ( mod p ) .
Lemma 2.4. If p p p is a prime and e > 1 e>1 e > 1 a positive integer, then
∑ j = 1 p e − 1 ν p ( j ) = p e − 1 p − 1 − e . \sum_{j=1}^{p^{e}-1} \nu_p(j)=\frac{p^{e}-1}{p-1}-e. j = 1 ∑ p e − 1 ν p ( j ) = p − 1 p e − 1 − e . Proof. For any prime p p p and r ∈ [ 0 , e − 1 ] r\in[0,e-1] r ∈ [ 0 , e − 1 ] , there are p e − r − p e − r − 1 p^{e-r}-p^{e-r-1} p e − r − p e − r − 1 integers j j j in Z p e − 1 \mathbb{Z}_{p^{e-1}} Z p e − 1 with ν p ( j ) = r \nu_p(j)=r ν p ( j ) = r . Thus, we obtain
∑ j = 1 p e − 1 ν p ( j ) = ∑ r = 0 e − 1 r ( p e − r − p e − r − 1 ) = p e − 1 p − 1 − e . \sum_{j=1}^{p^{e}-1}\nu_p(j)=\sum_{r=0}^{e-1}r\left(p^{e-r}-p^{e-r-1}\right)=\frac{p^{e}-1}{p-1}-e. j = 1 ∑ p e − 1 ν p ( j ) = r = 0 ∑ e − 1 r ( p e − r − p e − r − 1 ) = p − 1 p e − 1 − e .
Generalized Cyclotomic Mappings
We begin by summarizing some of the results presented in [2 ] that determine the dynamical behavior of generalized cyclotomic mappings. Let q q q be a prime power, d d d a divisor of q − 1 q-1 q − 1 and s = q − 1 d s=\frac{q-1}{d} s = d q − 1 . For any primitive element ξ \xi ξ of F q ∗ \mathbb{F}_q^* F q ∗ , let C 0 = { ξ j d ∣ j ∈ [ 0 , s − 1 ] } C_0=\{\xi^{jd}\mid j\in[0,s-1]\} C 0 = { ξ j d ∣ j ∈ [ 0 , s − 1 ]} be the unique index d d d subgroup of F q ∗ \mathbb{F}_q^* F q ∗ . For i ∈ [ 0 , d − 1 ] i\in[0,d-1] i ∈ [ 0 , d − 1 ] , let C i = ξ i C 0 C_i=\xi^iC_0 C i = ξ i C 0 be the d d d cosets of C 0 C_0 C 0 . A generalized cyclotomic mapping of F q \mathbb{F}_q F q of index d d d is any function f f f that satisfies
f ( x ) = { m 0 x a 0 if x ∈ C 0 , m 1 x a 1 if x ∈ C 1 , ⋮ ⋮ m d − 1 x a d − 1 if x ∈ C d − 1 , 0 if x = 0. f(x)=
\begin{cases}
m_0x^{a_0} & \text{if }x\in C_0,\\
m_1x^{a_1} & \text{if }x\in C_1,\\
\vdots& \vdots\\
m_{d-1}x^{a_{d-1}} & \text{if }x\in C_{d-1},\\
0 & \text{if }x=0.
\end{cases} f ( x ) = ⎩ ⎨ ⎧ m 0 x a 0 m 1 x a 1 ⋮ m d − 1 x a d − 1 0 if x ∈ C 0 , if x ∈ C 1 , ⋮ if x ∈ C d − 1 , if x = 0.
where m i ∈ F q ∗ m_i\in\mathbb{F}_q^* m i ∈ F q ∗ and a i ∈ [ 0 , q − 2 ] a_i\in[0,q-2] a i ∈ [ 0 , q − 2 ] . We have that f f f induces a unique coset map f ˉ : [ 0 , d − 1 ] → [ 0 , d − 1 ] \bar{f}:[0,d-1]\to[0,d-1] f ˉ : [ 0 , d − 1 ] → [ 0 , d − 1 ] on the indices of the d d d cosets such that f ( C i ) ⊆ C f ˉ ( i ) f(C_i)\subseteq C_{\bar{f}(i)} f ( C i ) ⊆ C f ˉ ( i ) . We are interested in the case when f f f is a generalized cyclotomic permutation (GCP). This implies that m i m_i m i is nonzero for every i ∈ [ 0 , d − 1 ] i\in[0,d-1] i ∈ [ 0 , d − 1 ] and the connected component generated that contains zero is always a cycle of length one (also known as a fixed point). Thus, we omit the case x = 0 x=0 x = 0 and consider only the restriction of f f f to F q ∗ \mathbb{F}_q^* F q ∗ hereafter.
Let GCP ( d , F q ∗ ) \operatorname{GCP}(d,\mathbb{F}_q^*) GCP ( d , F q ∗ ) be the set of all generalized cyclotomic permutations of index d d d over F q ∗ \mathbb{F}_q^* F q ∗ . If f ∈ GCP ( d , F q ∗ ) f\in\operatorname{GCP}(d,\mathbb{F}_q^*) f ∈ GCP ( d , F q ∗ ) , the induced coset map f ˉ \bar{f} f ˉ of f f f is a permutation of the set [ 0 , d − 1 ] [0,d-1] [ 0 , d − 1 ] . Therefore, hereafter we denote by σ f ∈ S d \sigma_f \in S_d σ f ∈ S d the representation of f ˉ \bar{f} f ˉ as the element of the symmetric group S d S_d S d written as a product of disjoint cycles.
Writing m i = ξ b i m_i=\xi^{b_i} m i = ξ b i , for some integer b i ∈ [ 0 , q − 2 ] b_i \in[0,q-2] b i ∈ [ 0 , q − 2 ] , we rewrite f f f as a function acting on the exponent of the element’s representation as a power of the primitive element ξ \xi ξ .
f ( ξ t ) = { ξ a 0 t + b 0 if ξ t ∈ C 0 , ξ a 1 t + b 1 if ξ t ∈ C 1 , ⋮ ⋮ ξ a d − 1 t + b d − 1 if ξ t ∈ C d − 1 . f(\xi^t)=
\begin{cases}
\xi^{a_0t+b_0} & \text{if } \xi^t \in C_0,\\
\xi^{a_1t+b_1} & \text{if } \xi^t \in C_1,\\
\vdots& \vdots\\
\xi^{a_{d-1}t+b_{d-1}} & \text{if } \xi^t \in C_{d-1}.
\end{cases} f ( ξ t ) = ⎩ ⎨ ⎧ ξ a 0 t + b 0 ξ a 1 t + b 1 ⋮ ξ a d − 1 t + b d − 1 if ξ t ∈ C 0 , if ξ t ∈ C 1 , ⋮ if ξ t ∈ C d − 1 .
For each i ∈ [ 0 , d − 1 ] i \in[0,d-1] i ∈ [ 0 , d − 1 ] , we define f i ( t ) = a i t + b i f_i(t)=a_i t+b_i f i ( t ) = a i t + b i .
Proposition 3.1. Let σ \sigma σ be any element of S d S_d S d . There are ( s ⋅ φ ( s ) ) d (s \cdot\varphi(s))^d ( s ⋅ φ ( s ) ) d generalized cyclotomic permutations of index d d d over F q \mathbb{F}_q F q with induced coset map σ \sigma σ .
Proof. Let σ ∈ S d \sigma\in S_d σ ∈ S d and f f f be a generalized cyclotomic permutation of index d d d over F q \mathbb{F}_q F q with induced coset map σ f = σ \sigma_f=\sigma σ f = σ . We observe that f f f is a permutation only if it is a bijection between C i C_i C i and C σ ( i ) C_{\sigma(i)} C σ ( i ) , for every i ∈ [ 0 , d − 1 ] i \in[0,d-1] i ∈ [ 0 , d − 1 ] . Each f i f_i f i induces the map
t ↦ a i t + a i i + b i − σ ( i ) d = a i t + c i t \mapsto a_i t+\frac{a_i i+b_i-\sigma(i)}{d}=a_i t+c_i t ↦ a i t + d a i i + b i − σ ( i ) = a i t + c i
in Z s \mathbb{Z}_s Z s , which is completely determined by a i a_i a i and c i c_i c i modulo s s s and is bijective if and only if gcd ( a i , s ) = 1 \gcd(a_i,s)=1 g cd( a i , s ) = 1 . Therefore, we conclude that f f f is a permutation if and only if each a i a_i a i is invertible modulo s s s , and there are ( s ⋅ φ ( s ) ) d (s \cdot\varphi(s))^d ( s ⋅ φ ( s ) ) d such maps.
:::
Corollary 3.1. There are d ! ⋅ ( s ⋅ φ ( s ) ) d d! \cdot(s \cdot\varphi(s))^d d ! ⋅ ( s ⋅ φ ( s ) ) d generalized cyclotomic permutations of index d d d .
Stochastic properties of GCPs
For any finite set S S S and map f f f defined over S S S , we denote by N ( f , S ) \mathcal{N}(f,S) N ( f , S ) the number of cycles in G f ( S ) \mathcal{G}_f(S) G f ( S ) , L ( f , S ) \mathcal{L}(f,S) L ( f , S ) the set of lengths of cycles in G f ( S ) \mathcal{G}_f(S) G f ( S ) and, for ℓ ∈ L ( f , S ) \ell\in\mathcal{L}(f,S) ℓ ∈ L ( f , S ) , N ℓ ( f , S ) \mathcal{N}_{\ell}(f,S) N ℓ ( f , S ) is the number of cycles of length ℓ \ell ℓ in G f ( S ) \mathcal{G}_f(S) G f ( S ) . Finally, for x ∈ S x \in S x ∈ S let ℓ x ( f , S ) \ell_x(f,S) ℓ x ( f , S ) be the length of the cycle that contains x x x in G f ( S ) \mathcal{G}_f(S) G f ( S ) .
Let AP ( Z s ) \operatorname{AP}(\mathbb{Z}_s) AP ( Z s ) be the set of all affine permutations over Z s \mathbb{Z}_s Z s . We now establish the precise relationship between cycles generated by elements in AP ( Z s ) \operatorname{AP}(\mathbb{Z}_s) AP ( Z s ) and those generated by elements of GCP ( d , F q ∗ ) \operatorname{GCP}(d,\mathbb{F}_q^*) GCP ( d , F q ∗ ) . We determine the expected cycle length of a random element and expected number of cycles of a randomly selected index d d d generalized cyclotomic permutation in terms those same properties for affine functions over Z s \mathbb{Z}_s Z s .
Let f ∈ GCP ( d , F q ∗ ) f\in\operatorname{GCP}(d,\mathbb{F}_q^*) f ∈ GCP ( d , F q ∗ ) with coset map σ f \sigma_f σ f . We define C ( σ f ) \mathcal{C}(\sigma_f) C ( σ f ) as the set of all cyclically ordered subsets Λ = ( λ 0 , … , λ n − 1 ) \Lambda=(\lambda_0,\ldots,\lambda_{n-1}) Λ = ( λ 0 , … , λ n − 1 ) of the integers [ 0 , d − 1 ] [0,d-1] [ 0 , d − 1 ] , for all n ∈ [ 1 , d ] n\in[1,d] n ∈ [ 1 , d ] , such that ( λ 0 … λ n − 1 ) (\lambda_0\ldots\lambda_{n-1}) ( λ 0 … λ n − 1 ) is a cycle in σ f \sigma_f σ f . For Λ ∈ C ( σ f ) \Lambda\in\mathcal{C}(\sigma_f) Λ ∈ C ( σ f ) , let C Λ = ⋃ λ ∈ Λ C λ C_\Lambda=\bigcup_{\lambda\in\Lambda}C_\lambda C Λ = ⋃ λ ∈ Λ C λ . If n n n is a positive integer, we define the n n n th iteration of f f f as f ( 1 ) ( x ) = f ( x ) f^{(1)}(x)=f(x) f ( 1 ) ( x ) = f ( x ) and f ( n ) ( x ) = f ( f ( n − 1 ) ( x ) ) f^{(n)}(x)=f(f^{(n-1)}(x)) f ( n ) ( x ) = f ( f ( n − 1 ) ( x )) , for n > 1 n>1 n > 1 .
In general, if G g ( S ) \mathcal{G}_g(S) G g ( S ) and G h ( R ) \mathcal{G}_h(R) G h ( R ) are functional graphs associated with the functions g g g over S S S and h h h over R R R respectively, then G g ( S ) \mathcal{G}_g(S) G g ( S ) and G h ( R ) \mathcal{G}_h(R) G h ( R ) are isomorphic graphs if there is a bijection ϕ \phi ϕ between S S S and R R R such that ϕ − 1 ( g ( ϕ ( a ) ) ) = h ( a ) \phi^{-1}(g(\phi(a)))=h(a) ϕ − 1 ( g ( ϕ ( a ))) = h ( a ) , for any a ∈ R a\in R a ∈ R . This means that the graphs G g ( S ) \mathcal{G}_g(S) G g ( S ) and G h ( R ) \mathcal{G}_h(R) G h ( R ) are equal up to relabeling of vertices.
Proposition 4.1. Let f ∈ GCP ( d , F q ∗ ) f\in\operatorname{GCP}(d,\mathbb{F}_q^*) f ∈ GCP ( d , F q ∗ ) with coset map σ f \sigma_f σ f . Then
N ( f , F q ∗ ) = ∑ Λ ∈ C ( σ f ) N ( A Λ , Z s ) \mathcal{N}(f,\mathbb{F}_q^*)=\sum_{\Lambda\in\mathcal{C}(\sigma_f)}\mathcal{N}(A_\Lambda,\mathbb{Z}_s) N ( f , F q ∗ ) = Λ ∈ C ( σ f ) ∑ N ( A Λ , Z s ) and
∑ ℓ ∈ L ( f , F q ∗ ) ℓ 2 N ℓ ( f , F q ∗ ) = ∑ Λ ∈ C ( σ f ) ∣ Λ ∣ 2 ∑ ℓ ∈ L ( A Λ , Z s ) ℓ 2 N ℓ ( A Λ , Z s ) \sum_{\ell\in\mathcal{L}(f,\mathbb{F}_q^*)}\ell^2\mathcal{N}_\ell(f,\mathbb{F}_q^*)=\sum_{\Lambda\in\mathcal{C}(\sigma_f)}|\Lambda|^2\sum_{\ell\in\mathcal{L}(A_\Lambda,\mathbb{Z}_s)}\ell^2\mathcal{N}_\ell(A_\Lambda,\mathbb{Z}_s) ℓ ∈ L ( f , F q ∗ ) ∑ ℓ 2 N ℓ ( f , F q ∗ ) = Λ ∈ C ( σ f ) ∑ ∣Λ ∣ 2 ℓ ∈ L ( A Λ , Z s ) ∑ ℓ 2 N ℓ ( A Λ , Z s ) where A Λ ( t ) = f λ n − 1 ∘ ⋯ ∘ f λ 0 ( λ 0 + t d ) − λ 0 d A_\Lambda(t)=\frac{f_{\lambda_{n-1}}\circ\cdots\circ f_{\lambda_0}(\lambda_0+td)-\lambda_0}{d} A Λ ( t ) = d f λ n − 1 ∘ ⋯ ∘ f λ 0 ( λ 0 + t d ) − λ 0 for any Λ = ( λ 0 , … , λ n − 1 ) ∈ C ( σ f ) \Lambda=(\lambda_0,\ldots,\lambda_{n-1})\in\mathcal{C}(\sigma_f) Λ = ( λ 0 , … , λ n − 1 ) ∈ C ( σ f ) .
Proof. Every cycle in the functional graph of f f f is contained in a set C Λ C_\Lambda C Λ , for some Λ ∈ C ( σ f ) \Lambda\in\mathcal{C}(\sigma_f) Λ ∈ C ( σ f ) . If Λ = ( λ 0 , … , λ n − 1 ) ∈ C ( σ f ) \Lambda=(\lambda_0,\ldots,\lambda_{n-1})\in\mathcal{C}(\sigma_f) Λ = ( λ 0 , … , λ n − 1 ) ∈ C ( σ f ) , then the n n n th iteration of f f f is a permutation of C λ 0 C_{\lambda_0} C λ 0 . Moreover, the bijection ι λ i : Z s → C λ i \iota_{\lambda_i}:\mathbb{Z}_s\to C_{\lambda_i} ι λ i : Z s → C λ i , t ↦ ζ λ i + d t t\mapsto\zeta^{\lambda_i+dt} t ↦ ζ λ i + d t creates a commutative diagram
\begin{begin{CD}
C_{\lambda_0} @>{f^{(n)}}>> C_{\lambda_0}\\
@V{\iota_{\lambda_0}^{-1}}VV @AA{\iota_{\lambda_0}}A\\
\mathbb{Z}_s @>{A_\Lambda}>> \mathbb{Z}_s
\end{begin{CD}}}
where A Λ ( t ) = f λ n − 1 ∘ ⋯ ∘ f λ 0 ( λ 0 + t d ) − λ 0 d A_\Lambda(t)=\frac{f_{\lambda_{n-1}}\circ\cdots\circ f_{\lambda_0}(\lambda_0+td)-\lambda_0}{d} A Λ ( t ) = d f λ n − 1 ∘ ⋯ ∘ f λ 0 ( λ 0 + t d ) − λ 0 . Hence, there is a one to one correspondence between the cycles generated by A Λ A_\Lambda A Λ and the cycles generated by f f f in C Λ C_\Lambda C Λ . In addition, each cycle of length ℓ \ell ℓ in the functional graph of A Λ A_\Lambda A Λ corresponds to a cycle of length n ⋅ ℓ n\cdot\ell n ⋅ ℓ in the functional graph of f f f .
Moreover, for any circular permutation ( λ j … λ j − 1 ) (\lambda_j\ldots\lambda_{j-1}) ( λ j … λ j − 1 ) of ( λ 0 … λ n − 1 ) (\lambda_0\ldots\lambda_{n-1}) ( λ 0 … λ n − 1 ) , where the indices are taken modulo n n n , taking the bijection ϕ ( t ) = f λ j ∘ ⋯ ∘ f λ n − 1 ( λ j + t d ) \phi(t)=f_{\lambda_j}\circ\cdots\circ f_{\lambda_{n-1}}(\lambda_j+td) ϕ ( t ) = f λ j ∘ ⋯ ∘ f λ n − 1 ( λ j + t d ) , we have that the functional graph of
f λ j ∘ ⋯ ∘ f λ j − 1 ( λ j − 1 + t d ) − λ j − 1 d \frac{f_{\lambda_j}\circ\cdots\circ f_{\lambda_{j-1}}(\lambda_{j-1}+td)-\lambda_{j-1}}{d} d f λ j ∘ ⋯ ∘ f λ j − 1 ( λ j − 1 + t d ) − λ j − 1
over Z p e \mathbb{Z}_{p^{e}} Z p e is isomorphic to the graph of G A Λ ( Z s ) \mathcal{G}_{A_{\Lambda}}(\mathbb{Z}_{s}) G A Λ ( Z s ) . Since this goes for every Λ ∈ C ( σ f ) \Lambda\in C(\sigma_f) Λ ∈ C ( σ f ) , the result follows.
Proposition 4.2. Let d d d be a divisor of q − 1 q-1 q − 1 and set s = q − 1 d s=\frac{q-1}{d} s = d q − 1 . Let g ( t ) = a t + b ∈ A P ( Z s ) g(t)=at+b\in AP(\mathbb{Z}_{s}) g ( t ) = a t + b ∈ A P ( Z s ) , n ∈ [ 1 , d ] n\in[1,d] n ∈ [ 1 , d ] and Λ = ( λ 0 , … , λ n − 1 ) \Lambda=(\lambda_0,\ldots,\lambda_{n-1}) Λ = ( λ 0 , … , λ n − 1 ) be a cyclically ordered subset of [ 0 , d − 1 ] [0,d-1] [ 0 , d − 1 ] . The number of generalized cyclotomic permutations of index d d d that generate a cycle in the cosets with index in Λ \Lambda Λ and have induced map A Λ ( t ) = g ( t ) A_{\Lambda}(t)=g(t) A Λ ( t ) = g ( t ) is
( d − n ) ! ( s φ ( s ) ) d − 1 . (d-n)!(s\varphi(s))^{d-1}. ( d − n )! ( s φ ( s ) ) d − 1 .
Proof. For fixed Λ = ( λ 0 … λ n − 1 ) \Lambda=(\lambda_0\ldots\lambda_{n-1}) Λ = ( λ 0 … λ n − 1 ) and A Λ A_{\Lambda} A Λ , the map A Λ A_{\Lambda} A Λ is determined by the n n n maps f λ i ( t ) f_{\lambda_i}(t) f λ i ( t ) , for λ i ∈ Λ \lambda_i\in\Lambda λ i ∈ Λ . Choosing n − 1 n-1 n − 1 of them arbitrarily among the s φ ( s ) s\varphi(s) s φ ( s ) choices, the last one is uniquely determined modulo s s s by the fixed map A Λ A_{\Lambda} A Λ . For the remaining d − n d-n d − n cosets, there are ( d − n ) ! (d-n)! ( d − n )! choices for the coset permutation and s φ ( s ) s\varphi(s) s φ ( s ) choices for each of the d − n d-n d − n maps.
Theorem 4.1. Let q q q be a prime power, d d d a divisor of q − 1 q-1 q − 1 and set s = q − 1 d s=\frac{q-1}{d} s = d q − 1 . If f f f and x x x are selected uniformly at random from the sets GCP ( d , F q ∗ ) \operatorname{GCP}(d,\mathbb{F}_q^*) GCP ( d , F q ∗ ) and F q ∗ \mathbb{F}_q^* F q ∗ , respectively, then
E [ N ( f , F q ∗ ) ] = H d ⋅ E [ N ( g , Z s ) ] and E [ ℓ x ( f , F q ∗ ) ] = d + 1 2 E [ ℓ t ( g , Z s ) ] \mathbb{E}[\mathcal{N}(f,\mathbb{F}_q^*)]=H_d\cdot\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)] \quad\text{and}\quad\mathbb{E}[\ell_x(f,\mathbb{F}_q^*)]=\frac{d+1}{2}\mathbb{E}[\ell_t(g,\mathbb{Z}_s)] E [ N ( f , F q ∗ )] = H d ⋅ E [ N ( g , Z s )] and E [ ℓ x ( f , F q ∗ )] = 2 d + 1 E [ ℓ t ( g , Z s )] where g g g and t t t are uniformly distributed over A P ( Z s ) AP(\mathbb{Z}_s) A P ( Z s ) and Z s \mathbb{Z}_s Z s , respectively, and H d H_d H d is the d d d th harmonic number.
Proof. There are ( d n ) ( n − 1 ) ! \binom{d}{n}(n-1)! ( n d ) ( n − 1 )! cyclically ordered subsets of [ 0 , d − 1 ] [0,d-1] [ 0 , d − 1 ] , for each n ∈ [ 1 , d ] n\in[1,d] n ∈ [ 1 , d ] . From Propositions 4.1 and 4.2 , each cyclically ordered subset Λ \Lambda Λ and fixed affine function A Λ A_{\Lambda} A Λ occurs on ( d − n ) ! ( s ⋅ φ ( s ) ) d − 1 (d-n)!(s\cdot\varphi(s))^{d-1} ( d − n )! ( s ⋅ φ ( s ) ) d − 1 GCPs. Thus, we have that
∑ f ∈ GCP ( d , F q ∗ ) N ( f , F q ∗ ) = ∑ n = 1 d ( d n ) ( n − 1 ) ! ( d − n ) ! ( s φ ( s ) ) d − 1 ∑ g ∈ A P ( Z s ) N ( g , Z s ) = d ! ( s φ ( s ) ) d − 1 H d ∑ g ∈ A P ( Z s ) N ( g , Z s ) . \begin{aligned}
\sum_{f\in\operatorname{GCP}(d,\mathbb{F}_q^*)}\mathcal{N}(f,\mathbb{F}_q^*)=
\sum_{n=1}^{d}\binom{d}{n}(n-1)!(d-n)!(s\varphi(s))^{d-1}
\sum_{g\in AP(\mathbb{Z}_s)}\mathcal{N}(g,\mathbb{Z}_s) \\
&=d!(s\varphi(s))^{d-1}H_d
\sum_{g\in AP(\mathbb{Z}_s)}\mathcal{N}(g,\mathbb{Z}_s).
\end{aligned} f ∈ GCP ( d , F q ∗ ) ∑ N ( f , F q ∗ ) = n = 1 ∑ d ( n d ) ( n − 1 )! ( d − n )! ( s φ ( s ) ) d − 1 g ∈ A P ( Z s ) ∑ N ( g , Z s ) = d ! ( s φ ( s ) ) d − 1 H d g ∈ A P ( Z s ) ∑ N ( g , Z s ) .
Dividing by ∣ GCP ( d , F q ∗ ) ∣ = d ! ( s φ ( s ) ) d |\operatorname{GCP}(d,\mathbb{F}_q^*)|=d!(s\varphi(s))^d ∣ GCP ( d , F q ∗ ) ∣ = d ! ( s φ ( s ) ) d , the first expectation follows. Moreover, we have that
∑ f ∈ GCP ( d , F q ∗ ) ∑ ℓ ∈ L ( f , F q ∗ ) ℓ 2 N ℓ ( f , F q ∗ ) = ∑ f ∈ GCP ( d , F q ∗ ) ∑ Λ ∈ C ( σ f ) ∣ Λ ∣ 2 ∑ ℓ ∈ L ( A Λ , Z s ) ℓ 2 N ℓ ( A Λ , Z s ) = ∑ n = 1 d ( d n ) ( n − 1 ) ! ( d − n ) ! ( s φ ( s ) ) d − 1 n 2 ∑ g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ℓ 2 N ℓ ( g , Z s ) = d ! ( s φ ( s ) ) d − 1 ∑ n = 1 d n ∑ g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ℓ 2 N ℓ ( g , Z s ) = d ( d + 1 ) 2 d ! ( s φ ( s ) ) d − 1 ∑ g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ℓ 2 N ℓ ( g , Z s ) . \begin{aligned}
\sum_{f\in\operatorname{GCP}(d,\mathbb{F}_q^*)}\sum_{\ell\in\mathcal{L}(f,\mathbb{F}_q^*)}\ell^2\mathcal{N}_{\ell}(f,\mathbb{F}_q^*)
&=\sum_{f\in\operatorname{GCP}(d,\mathbb{F}_q^*)}\sum_{\Lambda\in\mathcal{C}(\sigma_f)}|\Lambda|^2\sum_{\ell\in\mathcal{L}(A_\Lambda,\mathbb{Z}_s)}\ell^2\mathcal{N}_{\ell}(A_\Lambda,\mathbb{Z}_s)\\
&=\sum_{n=1}^{d}\binom{d}{n}(n-1)!(d-n)!(s\varphi(s))^{d-1}n^2\sum_{g\in\operatorname{AP}(\mathbb{Z}_s)}\sum_{\ell\in\mathcal{L}(g,\mathbb{Z}_s)}\ell^2\mathcal{N}_{\ell}(g,\mathbb{Z}_s)\\
&=d!(s\varphi(s))^{d-1}\sum_{n=1}^{d}n\sum_{g\in\operatorname{AP}(\mathbb{Z}_s)}\sum_{\ell\in\mathcal{L}(g,\mathbb{Z}_s)}\ell^2\mathcal{N}_{\ell}(g,\mathbb{Z}_s)\\
&=\frac{d(d+1)}{2}d!(s\varphi(s))^{d-1}\sum_{g\in\operatorname{AP}(\mathbb{Z}_s)}\sum_{\ell\in\mathcal{L}(g,\mathbb{Z}_s)}\ell^2\mathcal{N}_{\ell}(g,\mathbb{Z}_s).
\end{aligned} f ∈ GCP ( d , F q ∗ ) ∑ ℓ ∈ L ( f , F q ∗ ) ∑ ℓ 2 N ℓ ( f , F q ∗ ) = f ∈ GCP ( d , F q ∗ ) ∑ Λ ∈ C ( σ f ) ∑ ∣Λ ∣ 2 ℓ ∈ L ( A Λ , Z s ) ∑ ℓ 2 N ℓ ( A Λ , Z s ) = n = 1 ∑ d ( n d ) ( n − 1 )! ( d − n )! ( s φ ( s ) ) d − 1 n 2 g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ∑ ℓ 2 N ℓ ( g , Z s ) = d ! ( s φ ( s ) ) d − 1 n = 1 ∑ d n g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ∑ ℓ 2 N ℓ ( g , Z s ) = 2 d ( d + 1 ) d ! ( s φ ( s ) ) d − 1 g ∈ AP ( Z s ) ∑ ℓ ∈ L ( g , Z s ) ∑ ℓ 2 N ℓ ( g , Z s ) .
Dividing by ∣ F q ∗ ∣ ⋅ ∣ GCP ( d , F q ∗ ) ∣ = ( q − 1 ) d ! ( s φ ( s ) ) d |\mathbb{F}_q^*|\cdot|\operatorname{GCP}(d,\mathbb{F}_q^*)|=(q-1)d!(s\varphi(s))^d ∣ F q ∗ ∣ ⋅ ∣ GCP ( d , F q ∗ ) ∣ = ( q − 1 ) d ! ( s φ ( s ) ) d the second expectation follows.
This determines the precise relation between the expectations for affine maps over Z s \mathbb{Z}_s Z s and for GCPs over F q ∗ \mathbb{F}_q^* F q ∗ . In the next sections, we derive a closed-form expression for these expectations on affine maps over Z s \mathbb{Z}_s Z s , when s s s is a prime power and provide a comparison with random permutations.
Affine functions over finite cyclic groups
The dynamical behavior of any nonzero monomial function over F q ∗ \mathbb{F}_q^* F q ∗ is isomorphic via discrete logarithm to the behavior of an affine function over the additive group Z q − 1 \mathbb{Z}_{q-1} Z q − 1 . More precisely, if ξ \xi ξ is a primitive element of F q ∗ \mathbb{F}_q^* F q ∗ , a ∈ [ 0 , q − 1 ] a\in[0,q-1] a ∈ [ 0 , q − 1 ] and m = ξ b ∈ F q ∗ m=\xi^b\in\mathbb{F}_q^* m = ξ b ∈ F q ∗ , then the functional graphs of f ( x ) = m x a f(x)=mx^a f ( x ) = m x a over F q ∗ \mathbb{F}_q^* F q ∗ and g ( x ) = a t + b g(x)=at+b g ( x ) = a t + b over Z q − 1 \mathbb{Z}_{q-1} Z q − 1 are isomorphic through the bijection ϕ : Z q − 1 → F q ∗ \phi:\mathbb{Z}_{q-1}\to\mathbb{F}_q^* ϕ : Z q − 1 → F q ∗ given by ϕ ( t ) = ξ t \phi(t)=\xi^t ϕ ( t ) = ξ t .
The functional graph of affine functions over finite cyclic groups is completely described by Deng in [4 ] . In this section, we summarize some of his findings.
Definition 5.1. [4 Formula (1)] Let G 1 , … , G k \mathcal{G}_1,\ldots,\mathcal{G}_k G 1 , … , G k be directed graphs. We define ∏ i = 1 k G i \prod_{i=1}^{k}\mathcal{G}_i ∏ i = 1 k G i as the directed graph with vertex set V = { ( v 1 , … , v k ) ∣ v i ∈ G i , i ∈ [ 1 , k ] } V=\{(v_1,\ldots,v_k)\mid v_i\in\mathcal{G}_i,i\in[1,k]\} V = {( v 1 , … , v k ) ∣ v i ∈ G i , i ∈ [ 1 , k ]} and edges from ( v 1 , … , v k ) (v_1,\ldots,v_k) ( v 1 , … , v k ) to ( w 1 , … , w k ) (w_1,\ldots,w_k) ( w 1 , … , w k ) if and only if v i v_i v i is directed to w i w_i w i in G i \mathcal{G}_i G i , for all i ∈ [ 1 , k ] i\in[1,k] i ∈ [ 1 , k ] .
For a family of maps g i : S i → S i g_i:S_i\to S_i g i : S i → S i , with i ∈ [ 1 , k ] i\in[1,k] i ∈ [ 1 , k ] , we define ⨂ i = 1 k g i : ∏ i = 1 k S i → ∏ i = 1 k S i \bigotimes_{i=1}^{k}g_i:\prod_{i=1}^{k}S_i\to\prod_{i=1}^{k}S_i ⨂ i = 1 k g i : ∏ i = 1 k S i → ∏ i = 1 k S i as the map ( a 1 , … , a k ) ↦ ( g 1 ( a 1 ) , … , g k ( a k ) ) (a_1,\ldots,a_k)\mapsto(g_1(a_1),\ldots,g_k(a_k)) ( a 1 , … , a k ) ↦ ( g 1 ( a 1 ) , … , g k ( a k )) . Then, from the previous definition, its functional graph is given by G ⨂ i = 1 k g i ( ∏ i = 1 k S i ) = ∏ i = 1 k G g i ( S i ) \mathcal{G}_{\bigotimes_{i=1}^{k}g_i}\left(\prod_{i=1}^{k}S_i\right)=\prod_{i=1}^{k}\mathcal{G}_{g_i}(S_i) G ⨂ i = 1 k g i ( ∏ i = 1 k S i ) = ∏ i = 1 k G g i ( S i ) .
Definition 5.2. For any positive integer n n n , we denote by Cyc ( n ) \operatorname{Cyc}(n) Cyc ( n ) the directed graph composed of a cycle with n n n vertices. The directed graph G = ⨁ i = 0 k r i ⋅ Cyc ( n i ) \mathcal{G}=\bigoplus_{i=0}^{k}r_i\cdot\operatorname{Cyc}(n_i) G = ⨁ i = 0 k r i ⋅ Cyc ( n i ) is the graph composed by r i r_i r i copies of Cyc ( n i ) \operatorname{Cyc}(n_i) Cyc ( n i ) , for any nonnegative integers r i r_i r i and positive integers n i n_i n i , i ∈ [ 0 , k ] i\in[0,k] i ∈ [ 0 , k ] .
Lemma 5.1. [4 Lemma 1] If n 1 n_1 n 1 and n 2 n_2 n 2 are positive integers, the graph Cyc ( n 1 ) × Cyc ( n 2 ) \operatorname{Cyc}(n_1)\times\operatorname{Cyc}(n_2) Cyc ( n 1 ) × Cyc ( n 2 ) is isomorphic to gcd ( n 1 , n 2 ) ⋅ Cyc ( lcm ( n 1 , n 2 ) ) \gcd(n_1,n_2)\cdot\operatorname{Cyc}(\operatorname{lcm}(n_1,n_2)) g cd( n 1 , n 2 ) ⋅ Cyc ( lcm ( n 1 , n 2 )) .
Moreover, for affine maps over Z s \mathbb{Z}_s Z s we have the following.
Lemma 5.2. [4 Theorem 2] Let s = p 1 e 1 ⋯ p k e k s=p_1^{e_1}\cdots p_k^{e_k} s = p 1 e 1 ⋯ p k e k and f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b , for some a , b ∈ Z a,b\in\mathbb{Z} a , b ∈ Z . Then
G f ( Z s ) = ∏ i = 1 k G f ( Z p i e i ) . \mathcal{G}_f(\mathbb{Z}_s)=\prod_{i=1}^{k}\mathcal{G}_f(\mathbb{Z}_{p_i^{e_i}}). G f ( Z s ) = i = 1 ∏ k G f ( Z p i e i ) .
This lemma combines Definition 5.1 with the Chinese Remainder Theorem and allows us to determine the behavior of G f ( Z s ) \mathcal{G}_f(\mathbb{Z}_s) G f ( Z s ) by studying the behavior of G f ( Z p i e i ) \mathcal{G}_f(\mathbb{Z}_{p_i^{e_i}}) G f ( Z p i e i ) , for every p i e i p_i^{e_i} p i e i in the prime decomposition of s s s .
We recall that when f f f is a permutation, its functional graph is composed of cycles with no attached trees. Hence, its description is given by the number of cycles of each length.
Theorem 5.1. [4 Lemmas 3 and 7] Let p p p be a prime and e e e be a positive integer. For a , b ∈ Z a,b\in\mathbb{Z} a , b ∈ Z , the affine function f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b is a permutation over Z p e \mathbb{Z}_{p^e} Z p e if and only if gcd ( a , p ) = 1 \gcd(a,p)=1 g cd( a , p ) = 1 . In that case, the functional graph of f f f over Z p e \mathbb{Z}_{p^e} Z p e is given by the following two cases.
If ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) , then
G f ( Z p e ) = ⨁ i = 1 ord p e ( a ) n i ⋅ Cyc ( i ) , \mathcal{G}_f(\mathbb{Z}_{p^e})=\bigoplus_{i=1}^{\operatorname{ord}_{p^e}(a)}n_i\cdot\operatorname{Cyc}(i), G f ( Z p e ) = i = 1 ⨁ ord p e ( a ) n i ⋅ Cyc ( i ) , where n i = 1 i ∑ d ∣ i μ ( d ) gcd ( p e / d , a i / d − 1 ) n_i=\frac{1}{i}\sum_{d\mid i}\mu(d)\gcd(p^{e/d},a^{i/d}-1) n i = i 1 ∑ d ∣ i μ ( d ) g cd( p e / d , a i / d − 1 ) .
If ν p ( a − 1 ) > ν p ( b ) \nu_p(a-1)>\nu_p(b) ν p ( a − 1 ) > ν p ( b ) , then
G f ( Z p e ) = p e − s × Cyc ( p s ) , \mathcal{G}_f(\mathbb{Z}_{p^e})=p^{e-s}\times\operatorname{Cyc}(p^s), G f ( Z p e ) = p e − s × Cyc ( p s ) , where
p s = { p e − ν p ( b ) if p ≠ 2 or ν p ( a − 1 ) > 1 , 2 if p = 2 , ν p ( a − 1 ) = 1 and e + 1 ≤ ν 2 ( a 2 − 1 ) , 2 e + 2 − ν p ( a 2 − 1 ) if p = 2 , ν p ( a − 1 ) = 1 and e + 1 > ν 2 ( a 2 − 1 ) . p^s=
\begin{cases}
p^{e-\nu_p(b)} & \text{if }p\ne2\text{ or }\nu_p(a-1)>1,\\
2 & \text{if }p=2,\ \nu_p(a-1)=1\text{ and }e+1\le\nu_2(a^2-1),\\
2^{e+2-\nu_p(a^2-1)} & \text{if }p=2,\ \nu_p(a-1)=1\text{ and }e+1>\nu_2(a^2-1).
\end{cases} p s = ⎩ ⎨ ⎧ p e − ν p ( b ) 2 2 e + 2 − ν p ( a 2 − 1 ) if p = 2 or ν p ( a − 1 ) > 1 , if p = 2 , ν p ( a − 1 ) = 1 and e + 1 ≤ ν 2 ( a 2 − 1 ) , if p = 2 , ν p ( a − 1 ) = 1 and e + 1 > ν 2 ( a 2 − 1 ) .
In the first case, we have that n i n_i n i is zero for some choices of i ∈ [ 1 , ord p e − 1 ( a ) ] i \in[1,\operatorname{ord}_{p^{e-1}}(a)] i ∈ [ 1 , ord p e − 1 ( a )] . The following result by Sha provides an alternative way to determine the cycle lengths in the functional graph of f f f when ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1) \le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) .
Theorem 5.2. [18 Proposition 2.6] Let p p p be a prime and e e e be a positive integer. Let f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b be such that gcd ( a , p ) = 1 \gcd(a,p)=1 g cd( a , p ) = 1 and ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1) \le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) . Then
G f ( Z p e ) = ⨁ k = 0 e φ ( p k ) ord p k ( a ) × Cyc ( ord p k ( a ) ) \mathcal{G}_f(\mathbb{Z}_{p^e})=\bigoplus_{k=0}^{e}\frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(a)}\times\operatorname{Cyc}(\operatorname{ord}_{p^k}(a)) G f ( Z p e ) = k = 0 ⨁ e ord p k ( a ) φ ( p k ) × Cyc ( ord p k ( a )) and the total number of cycles in G f ( Z p e ) \mathcal{G}_f(\mathbb{Z}_{p^e}) G f ( Z p e ) is ∑ j = 0 e φ ( p j ) ord p j ( a ) \sum_{j=0}^{e}\frac{\varphi(p^j)}{\operatorname{ord}_{p^j}(a)} ∑ j = 0 e ord p j ( a ) φ ( p j ) , where ord p 0 ( a ) = 1 \operatorname{ord}_{p^0}(a)=1 ord p 0 ( a ) = 1 .
The drawback of this notation is that we might have ord p k ( a ) = ord p r ( a ) \operatorname{ord}_{p^k}(a)=\operatorname{ord}_{p^r}(a) ord p k ( a ) = ord p r ( a ) for some k ≠ r k \ne r k = r .
Stochastic properties of affine maps over Z p e \mathbb{Z}_{p^e} Z p e
Although there is extensive research on the dynamical behavior of the maps in AP ( Z s ) \operatorname{AP}(\mathbb{Z}_s) AP ( Z s ) , including the complete characterization of cycle and tree decomposition, in this section we provide new closed-form expressions for two stochastic properties of their functional graphs in the case where s s s is a prime power.
Let p p p be a prime and e e e a positive integer. The expectation for the number of cycles of f ∈ AP ( Z p e ) f \in\operatorname{AP}(\mathbb{Z}_{p^e}) f ∈ AP ( Z p e ) selected uniformly at random is determined by
E [ N ( f , Z p e ) ] = 1 ∣ AP ( Z p e ) ∣ ∑ f ∈ AP ( Z p e ) N ( f , Z p e ) . \mathbb{E}[\mathcal{N}(f,\mathbb{Z}_{p^e})]=\frac{1}{|\operatorname{AP}(\mathbb{Z}_{p^e})|}\sum_{f\in\operatorname{AP}(\mathbb{Z}_{p^e})}\mathcal{N}(f,\mathbb{Z}_{p^e}). E [ N ( f , Z p e )] = ∣ AP ( Z p e ) ∣ 1 f ∈ AP ( Z p e ) ∑ N ( f , Z p e ) .
The expectation for the length of the cycle that contains x ∈ Z p e x \in\mathbb{Z}_{p^e} x ∈ Z p e in the functional graph of f ∈ AP ( Z p e ) f \in\operatorname{AP}(\mathbb{Z}_{p^e}) f ∈ AP ( Z p e ) , where x x x and f f f are selected uniformly at random, is determined by
E [ ℓ x ( f , Z p e ) ] = 1 p e ⋅ ∣ AP ( Z p e ) ∣ ∑ f ∈ AP ( Z p e ) ∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) . \mathbb{E}[\ell_x(f,\mathbb{Z}_{p^e})]=\frac{1}{p^e\cdot|\operatorname{AP}(\mathbb{Z}_{p^e})|}\sum_{f\in\operatorname{AP}(\mathbb{Z}_{p^e})}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e}). E [ ℓ x ( f , Z p e )] = p e ⋅ ∣ AP ( Z p e ) ∣ 1 f ∈ AP ( Z p e ) ∑ ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) .
Since the number of affine permutations over Z p e \mathbb{Z}_{p^e} Z p e is p e ⋅ φ ( p e ) = p 2 e − 1 ( p − 1 ) p^e\cdot\varphi(p^e)=p^{2e-1}(p-1) p e ⋅ φ ( p e ) = p 2 e − 1 ( p − 1 ) , to calculate the expectations we need to determine the value for each of the sums. We begin with the case where p = 2 p=2 p = 2 .
Stochastic properties for p = 2 p=2 p = 2
Theorem 6.1.
∑ f ∈ AP ( Z 2 e ) N ( f , Z 2 e ) = ( e 2 + 3 e + 8 ) 2 2 e − 4 . \sum_{f\in\operatorname{AP}(\mathbb{Z}_{2^e})}\mathcal{N}(f,\mathbb{Z}_{2^e})=(e^2+3e+8)2^{2e-4}. f ∈ AP ( Z 2 e ) ∑ N ( f , Z 2 e ) = ( e 2 + 3 e + 8 ) 2 2 e − 4 .
Proof. We begin with the trivial case e = 1 e=1 e = 1 , where there are only two affine maps: the identity and x ↦ x + 1 x\mapsto x+1 x ↦ x + 1 . The first generates two cycles and the second generates one cycle. Therefore the total sum of cycles is 3.
Let f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b be an affine permutation of Z 2 e \mathbb{Z}_{2^e} Z 2 e . When e = 2 e=2 e = 2 , we have a ∈ { 1 , 3 } a\in\{1,3\} a ∈ { 1 , 3 } . If a = 3 a=3 a = 3 , then ν 2 ( a − 1 ) ≤ ν 2 ( b ) \nu_2(a-1)\leq\nu_2(b) ν 2 ( a − 1 ) ≤ ν 2 ( b ) if and only if b ∈ { 0 , 2 } b\in\{0,2\} b ∈ { 0 , 2 } . In those cases, we have
∑ k = 0 2 φ ( p k ) ord 2 k ( 3 ) = 3 \sum_{k=0}^{2}\frac{\varphi(p^k)}{\operatorname{ord}_{2^k}(3)}=3 k = 0 ∑ 2 ord 2 k ( 3 ) φ ( p k ) = 3
cycles in each map. If b ∈ { 1 , 3 } b\in\{1,3\} b ∈ { 1 , 3 } , each function generates 2 cycles. When a = 1 a=1 a = 1 , either b = 0 b=0 b = 0 and we have 2 2 2^2 2 2 cycles, or ν 2 ( a − 1 ) > ν 2 ( b ) \nu_2(a-1)>\nu_2(b) ν 2 ( a − 1 ) > ν 2 ( b ) and there are 2 ν 2 ( b ) 2^{\nu_2(b)} 2 ν 2 ( b ) cycles. Therefore, sum of the number of cycles is
6 + 4 + 4 + ∑ b ∈ Z 4 ∖ { 0 } 2 ν 2 ( b ) = 18. 6+4+4+\sum_{\substack{b\in\mathbb{Z}_4\setminus\{0\}}}2^{\nu_2(b)}=18. 6 + 4 + 4 + b ∈ Z 4 ∖ { 0 } ∑ 2 ν 2 ( b ) = 18.
For e ≥ 3 e\geq3 e ≥ 3 , we split the choices of a a a into two cases: either a = 4 j + 3 a=4j+3 a = 4 j + 3 or a = 4 j + 1 a=4j+1 a = 4 j + 1 , for some j ∈ [ 0 , 2 e − 2 − 1 ] j\in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] . In the first case, we have that ν 2 ( a − 1 ) = 1 \nu_2(a-1)=1 ν 2 ( a − 1 ) = 1 . Therefore, ν 2 ( a − 1 ) > ν 2 ( b ) \nu_2(a-1)>\nu_2(b) ν 2 ( a − 1 ) > ν 2 ( b ) if and only if ν 2 ( b ) = 0 \nu_2(b)=0 ν 2 ( b ) = 0 and there are 2 e − 1 2^{e-1} 2 e − 1 elements b ∈ Z 2 e b\in\mathbb{Z}_{2^e} b ∈ Z 2 e with that property. Moreover, from Lemma 2.1 we obtain that ν 2 ( a 2 − 1 ) = 3 + ν 2 ( j + 1 ) ≤ e + 1 \nu_2(a^2-1)=3+\nu_2(j+1)\leq e+1 ν 2 ( a 2 − 1 ) = 3 + ν 2 ( j + 1 ) ≤ e + 1 . We observe that for each r ∈ [ 0 , e − 3 ] r\in[0,e-3] r ∈ [ 0 , e − 3 ] there are 2 e − 3 − r 2^{e-3-r} 2 e − 3 − r integers j ∈ [ 0 , 2 e − 2 − 1 ] j\in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] with ν 2 ( j + 1 ) = r \nu_2(j+1)=r ν 2 ( j + 1 ) = r and one such that ν 2 ( j + 1 ) = e − 2 \nu_2(j+1)=e-2 ν 2 ( j + 1 ) = e − 2 . Hence, Theorem 5.1 implies that the sum of the number of cycles generated by those maps is equal to
∑ j = 0 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) = 0 2 ν 2 ( j + 1 ) + 1 = 2 2 e − 2 + 2 e − 1 ∑ r = 0 e − 3 2 e − 2 = 2 2 e − 2 + ( e − 2 ) 2 2 e − 3 = e 2 2 e − 3 . (1) \sum_{j=0}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb{Z}_{2^e}\\\nu_2(b)=0}}2^{\nu_2(j+1)+1}
=2^{2e-2}+2^{e-1}\sum_{r=0}^{e-3}2^{e-2}
=2^{2e-2}+(e-2)2^{2e-3}
=e2^{2e-3}. \tag*{(1)} j = 0 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) = 0 ∑ 2 ν 2 ( j + 1 ) + 1 = 2 2 e − 2 + 2 e − 1 r = 0 ∑ e − 3 2 e − 2 = 2 2 e − 2 + ( e − 2 ) 2 2 e − 3 = e 2 2 e − 3 . (1)
For any other b ∈ Z 2 e b\in\mathbb{Z}_{2^e} b ∈ Z 2 e , the sum of the number of cycles is given by
∑ j = 0 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) ≥ 1 ∑ k = 0 e φ ( 2 k ) ord 2 k ( 4 j + 3 ) = ∑ j = 0 2 e − 2 − 1 2 e − 1 ( 2 + ∑ k = 2 e 2 k − 1 2 max { 1 , k − 2 − ν 2 ( j + 1 ) } ) = 2 2 e − 2 + 2 e − 1 ( ∑ j = 0 2 e − 2 − 1 ∑ k = 0 e − 2 2 min { k , ν 2 ( j + 1 ) + 1 } ) . \begin{aligned}
\sum_{j=0}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb{Z}_{2^e}\\\nu_2(b)\geq1}}\sum_{k=0}^{e}\frac{\varphi(2^k)}{\operatorname{ord}_{2^k}(4j+3)}
=\sum_{j=0}^{2^{e-2}-1}2^{e-1}\left(2+\sum_{k=2}^{e}\frac{2^{k-1}}{2^{\max\{1,k-2-\nu_2(j+1)\}}}\right) \\
&=2^{2e-2}+2^{e-1}\left(\sum_{j=0}^{2^{e-2}-1}\sum_{k=0}^{e-2}2^{\min\{k,\nu_2(j+1)+1\}}\right).
\end{aligned} j = 0 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) ≥ 1 ∑ k = 0 ∑ e ord 2 k ( 4 j + 3 ) φ ( 2 k ) = j = 0 ∑ 2 e − 2 − 1 2 e − 1 ( 2 + k = 2 ∑ e 2 m a x { 1 , k − 2 − ν 2 ( j + 1 )} 2 k − 1 ) = 2 2 e − 2 + 2 e − 1 j = 0 ∑ 2 e − 2 − 1 k = 0 ∑ e − 2 2 m i n { k , ν 2 ( j + 1 ) + 1 } .
For each r ∈ [ 0 , e − 3 ] r \in[0,e-3] r ∈ [ 0 , e − 3 ] , there are 2 e − 3 − r 2^{e-3-r} 2 e − 3 − r integers j ∈ [ 0 , 2 e − 2 − 1 ] j \in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] such that ν 2 ( j + 1 ) = r \nu_2(j+1)=r ν 2 ( j + 1 ) = r and ν 2 ( j + 1 ) = e − 2 \nu_2(j+1)=e-2 ν 2 ( j + 1 ) = e − 2 if and only if j = 2 e − 2 − 1 j=2^{e-2}-1 j = 2 e − 2 − 1 . Thus, we get
2 2 e − 2 + 2 e − 1 ∑ k = 0 e − 2 2 min { k , e − 1 } + 2 e − 1 ∑ r = 1 e − 2 ∑ k = 0 e − 2 2 e − 2 − r + min { k , r } = 2 2 e − 2 + 2 e − 1 ( 2 e − 1 − 1 ) + 2 e − 1 ∑ r = 1 e − 2 ( ∑ k = 0 r − 1 2 e − 2 − r + k + ∑ k = r e − 2 2 e − 2 ) = 2 2 e − 1 − 2 e − 1 + 2 e − 1 ∑ r = 1 e − 2 ( 2 e − 2 − 2 e − 2 − r + ( e − 1 − r ) 2 e − 2 ) = 2 2 e − 1 − 2 e − 1 + ( e 2 − e − 2 ) 2 2 e − 4 − 2 e − 1 ( 2 e − 2 − 1 ) = ( e 2 − e + 4 ) 2 2 e − 4 . (2) \begin{aligned}
2^{2e-2}+2^{e-1}\sum_{k=0}^{e-2}2^{\min\{k,e-1\}}+2^{e-1}\sum_{r=1}^{e-2}\sum_{k=0}^{e-2}2^{e-2-r+\min\{k,r\}}
&=2^{2e-2}+2^{e-1}(2^{e-1}-1)+2^{e-1}\sum_{r=1}^{e-2}\left(\sum_{k=0}^{r-1}2^{e-2-r+k}+\sum_{k=r}^{e-2}2^{e-2}\right)\\
&=2^{2e-1}-2^{e-1}+2^{e-1}\sum_{r=1}^{e-2}\left(2^{e-2}-2^{e-2-r}+(e-1-r)2^{e-2}\right)\\
&=2^{2e-1}-2^{e-1}+(e^2-e-2)2^{2e-4}-2^{e-1}(2^{e-2}-1)\\
&=(e^2-e+4)2^{2e-4}. \tag*{(2)}
\end{aligned} 2 2 e − 2 + 2 e − 1 k = 0 ∑ e − 2 2 m i n { k , e − 1 } + 2 e − 1 r = 1 ∑ e − 2 k = 0 ∑ e − 2 2 e − 2 − r + m i n { k , r } = 2 2 e − 2 + 2 e − 1 ( 2 e − 1 − 1 ) + 2 e − 1 r = 1 ∑ e − 2 ( k = 0 ∑ r − 1 2 e − 2 − r + k + k = r ∑ e − 2 2 e − 2 ) = 2 2 e − 1 − 2 e − 1 + 2 e − 1 r = 1 ∑ e − 2 ( 2 e − 2 − 2 e − 2 − r + ( e − 1 − r ) 2 e − 2 ) = 2 2 e − 1 − 2 e − 1 + ( e 2 − e − 2 ) 2 2 e − 4 − 2 e − 1 ( 2 e − 2 − 1 ) = ( e 2 − e + 4 ) 2 2 e − 4 . (2)
When a = 4 j + 1 a=4j+1 a = 4 j + 1 and j ≠ 0 j \ne0 j = 0 , we have that ν 2 ( a − 1 ) = ν 2 ( j ) + 2 \nu_2(a-1)=\nu_2(j)+2 ν 2 ( a − 1 ) = ν 2 ( j ) + 2 . Hence, the sum of the number of cycles generated by those functions is given by
∑ j = 1 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) < ν 2 ( j ) + 2 2 ν 2 ( b ) + ∑ j = 1 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) ≥ ν 2 ( j ) + 2 ∑ k = 0 e φ ( 2 k ) ord 2 k ( 4 j + 1 ) . \sum_{j=1}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb Z_{2^e}\\ \nu_2(b)<\nu_2(j)+2}}2^{\nu_2(b)}
+\sum_{j=1}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb Z_{2^e}\\ \nu_2(b)\ge\nu_2(j)+2}}\sum_{k=0}^{e}\frac{\varphi(2^k)}{\operatorname{ord}_{2^k}(4j+1)}. j = 1 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) < ν 2 ( j ) + 2 ∑ 2 ν 2 ( b ) + j = 1 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) ≥ ν 2 ( j ) + 2 ∑ k = 0 ∑ e ord 2 k ( 4 j + 1 ) φ ( 2 k ) .
In the first summand, instead of summing over b b b , we sum over t = ν 2 ( b ) t=\nu_2(b) t = ν 2 ( b ) . Thus, using Lemma 2.4 we obtain
∑ j = 1 2 e − 2 − 1 ∑ t = 0 ν 2 ( j ) + 1 2 e − 1 − t = 2 e − 1 ∑ j = 1 2 e − 2 − 1 ( ν 2 ( j ) + 2 ) = 3 ⋅ 2 2 e − 3 − ( e + 1 ) 2 e − 1 . (3) \sum_{j=1}^{2^{e-2}-1}\sum_{t=0}^{\nu_2(j)+1}2^{e-1-t}
=2^{e-1}\sum_{j=1}^{2^{e-2}-1}(\nu_2(j)+2)
=3\cdot2^{2e-3}-(e+1)2^{e-1}. \tag*{(3)} j = 1 ∑ 2 e − 2 − 1 t = 0 ∑ ν 2 ( j ) + 1 2 e − 1 − t = 2 e − 1 j = 1 ∑ 2 e − 2 − 1 ( ν 2 ( j ) + 2 ) = 3 ⋅ 2 2 e − 3 − ( e + 1 ) 2 e − 1 . (3)
In the second summand, we observe that the term is independent of b b b and, for each r r r , there are 2 e − r − 2 2^{e-r-2} 2 e − r − 2 choices of b ∈ Z 2 e b\in\mathbb Z_{2^e} b ∈ Z 2 e such that ν 2 ( b ) ≥ r + 2 \nu_2(b)\ge r+2 ν 2 ( b ) ≥ r + 2 . Summing over r = ν 2 ( j ) r=\nu_2(j) r = ν 2 ( j ) and using Lemma 2.2 we get
∑ r = 0 e − 3 2 2 e − 5 − 2 r ( 1 + ∑ k = 1 e 2 k − 1 2 max { 0 , k − 2 − r } ) = 2 2 e − 3 − 2 3 + ∑ r = 1 e − 2 ( ∑ k = 0 r 2 2 e − 3 − 2 r + k + ∑ k = r + 1 e − 1 2 2 e − 3 − r ) = 2 2 e − 3 − 2 3 + ∑ r = 1 e − 2 2 2 e − 2 − r − 2 2 e − 3 − 2 r + ( e − r − 1 ) 2 2 e − 3 − r = ( e − 1 ) 2 2 e − 3 − 2 e − 1 . (4) \begin{aligned}
\sum_{r=0}^{e-3}2^{2e-5-2r}\left(1+\sum_{k=1}^{e}\frac{2^{k-1}}{2^{\max\{0,k-2-r\}}}\right)
=\frac{2^{2e-3}-2}{3}+\sum_{r=1}^{e-2}\left(\sum_{k=0}^{r}2^{2e-3-2r+k}+\sum_{k=r+1}^{e-1}2^{2e-3-r}\right) \\
&=\frac{2^{2e-3}-2}{3}+\sum_{r=1}^{e-2}2^{2e-2-r}-2^{2e-3-2r}+(e-r-1)2^{2e-3-r} \\
&=(e-1)2^{2e-3}-2^{e-1}. \tag*{(4)}
\end{aligned} r = 0 ∑ e − 3 2 2 e − 5 − 2 r ( 1 + k = 1 ∑ e 2 m a x { 0 , k − 2 − r } 2 k − 1 ) = 3 2 2 e − 3 − 2 + r = 1 ∑ e − 2 ( k = 0 ∑ r 2 2 e − 3 − 2 r + k + k = r + 1 ∑ e − 1 2 2 e − 3 − r ) = 3 2 2 e − 3 − 2 + r = 1 ∑ e − 2 2 2 e − 2 − r − 2 2 e − 3 − 2 r + ( e − r − 1 ) 2 2 e − 3 − r = ( e − 1 ) 2 2 e − 3 − 2 e − 1 . (4)
When j = 0 j=0 j = 0 , that is, a = 1 a=1 a = 1 , we have that ν 2 ( b ) ≥ ν 2 ( a − 1 ) \nu_2(b) \ge\nu_2(a-1) ν 2 ( b ) ≥ ν 2 ( a − 1 ) if and only if b = 0 b=0 b = 0 . In that case we have the identity function and 2 e 2^e 2 e cycles. In any other case we have 2 ν 2 ( b ) 2^{\nu_2(b)} 2 ν 2 ( b ) cycles. Hence, we have
2 e + ∑ b ∈ Z 2 e ∖ { 0 } 2 ν 2 ( b ) = 2 e + ∑ t = 0 e − 1 2 e − t − 1 2 e − 1 = 2 e + e 2 e − 1 = ( e + 2 ) 2 e − 1 (5) 2^e+\sum_{b\in\mathbb{Z}_{2^e}\setminus\{0\}}2^{\nu_2(b)}=2^e+\sum_{t=0}^{e-1}2^{e-t-1}2^{e-1}=2^e+e2^{e-1}=(e+2)2^{e-1} \tag*{(5)} 2 e + b ∈ Z 2 e ∖ { 0 } ∑ 2 ν 2 ( b ) = 2 e + t = 0 ∑ e − 1 2 e − t − 1 2 e − 1 = 2 e + e 2 e − 1 = ( e + 2 ) 2 e − 1 (5)
Adding (6.1), (6.2), (6.3), (6.4) and (6.5) we obtain that the sum of the number of cycles of affine permutations over Z 2 e \mathbb{Z}_{2^e} Z 2 e is
( e 2 + 3 e + 8 ) 2 2 e − 4 . (e^2+3e+8)2^{2e-4}. ( e 2 + 3 e + 8 ) 2 2 e − 4 .
Theorem 6.2. The expectation for the number of cycles of a map f ∈ A P ( Z 2 e ) f\in AP(\mathbb{Z}_{2^e}) f ∈ A P ( Z 2 e ) selected uniformly at random is
E [ N ( f , Z 2 e ) ∣ f ∈ A P ( Z 2 e ) ] = e 2 + 3 e + 8 8 . \mathbb{E}[N(f,\mathbb{Z}_{2^e})\mid f\in AP(\mathbb{Z}_{2^e})]=\frac{e^2+3e+8}{8}. E [ N ( f , Z 2 e ) ∣ f ∈ A P ( Z 2 e )] = 8 e 2 + 3 e + 8 .
Proof. The total number of affine permutations in Z 2 e \mathbb{Z}_{2^e} Z 2 e is φ ( 2 e ) ⋅ 2 e = 2 2 e − 1 \varphi(2^e)\cdot2^e=2^{2e-1} φ ( 2 e ) ⋅ 2 e = 2 2 e − 1 and, from Theorem 6.1, the total number of cycles generated by affine permutations is ( e 2 + 3 e + 8 ) 2 2 e − 4 (e^2+3e+8)2^{2e-4} ( e 2 + 3 e + 8 ) 2 2 e − 4 . Thus, the expectation for the number of cycles is given by
1 ∣ A P ( Z 2 e ) ∣ ∑ f ∈ A P ( Z 2 e ) N ( f , Z 2 e ) = ( e 2 + 3 e + 8 ) 2 2 e − 4 2 2 e − 1 = e 2 + 3 e + 8 8 . \frac{1}{|AP(\mathbb{Z}_{2^e})|}\sum_{f\in AP(\mathbb{Z}_{2^e})}\mathcal{N}(f,\mathbb{Z}_{2^e})=\frac{(e^2+3e+8)2^{2e-4}}{2^{2e-1}}=\frac{e^2+3e+8}{8}. ∣ A P ( Z 2 e ) ∣ 1 f ∈ A P ( Z 2 e ) ∑ N ( f , Z 2 e ) = 2 2 e − 1 ( e 2 + 3 e + 8 ) 2 2 e − 4 = 8 e 2 + 3 e + 8 .
Theorem 6.3.
∑ f ∈ A P ( Z 2 e ) ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 2 e 18 ( 2 2 e + 2 + 6 e + 5 ) . \sum_{f\in AP(\mathbb{Z}_{2^e})}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{2^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{2^e})=\frac{2^{2e}}{18}(2^{2e+2}+6e+5). f ∈ A P ( Z 2 e ) ∑ ℓ ∈ L ( f , Z 2 e ) ∑ ℓ 2 N ℓ ( f , Z 2 e ) = 18 2 2 e ( 2 2 e + 2 + 6 e + 5 ) . Proof. For any prime power p e p^e p e and affine permutation f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b over Z p e \mathbb{Z}_{p^e} Z p e , if ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) , Theorem 5.2 implies that
∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = ∑ k = 0 e φ ( p k ) ord ( a ) p k . (6) \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{2^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{2^e})=\sum_{k=0}^{e}\varphi(p^k)\frac{\operatorname{ord}(a)}{p^k}. \tag*{(6)} ℓ ∈ L ( f , Z 2 e ) ∑ ℓ 2 N ℓ ( f , Z 2 e ) = k = 0 ∑ e φ ( p k ) p k ord ( a ) . (6)
If ν p ( a − 1 ) > ν p ( b ) \nu_p(a-1)>\nu_p(b) ν p ( a − 1 ) > ν p ( b ) , Theorem 5.1 implies that
∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = p e + s , \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{2^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{2^e})=p^{e+s}, ℓ ∈ L ( f , Z 2 e ) ∑ ℓ 2 N ℓ ( f , Z 2 e ) = p e + s ,
where s s s depends on ν p ( b ) \nu_p(b) ν p ( b ) and ν p ( a 2 − 1 ) \nu_p(a^2-1) ν p ( a 2 − 1 ) . We now follow the same structure as the proof of Theorem 6.1 .
When p = 2 p=2 p = 2 , if e = 1 e=1 e = 1 the only affine permutations are the identity and x ↦ x + 1 x\mapsto x+1 x ↦ x + 1 . Thus
∑ f ∈ AP ( Z 2 ) ∑ ℓ ∈ L ( f , Z 2 ) ℓ 2 N ℓ ( f , Z 2 ) = 1 ⋅ 2 + 4 ⋅ 1 = 6. \sum_{f\in\operatorname{AP}(\mathbb{Z}_2)}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_2)}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_2)=1\cdot2+4\cdot1=6. f ∈ AP ( Z 2 ) ∑ ℓ ∈ L ( f , Z 2 ) ∑ ℓ 2 N ℓ ( f , Z 2 ) = 1 ⋅ 2 + 4 ⋅ 1 = 6.
When e = 2 e=2 e = 2 , we have a ∈ { 1 , 3 } a\in\{1,3\} a ∈ { 1 , 3 } . If a = 3 a=3 a = 3 , then ν 2 ( a − 1 ) ≤ ν 2 ( b ) \nu_2(a-1)\leq\nu_2(b) ν 2 ( a − 1 ) ≤ ν 2 ( b ) if and only if b ∈ { 0 , 2 } b\in\{0,2\} b ∈ { 0 , 2 } . In each of those cases, we have ∑ k = 0 2 φ ( p k ) ord 2 k ( 3 ) = 6 \sum_{k=0}^{2}\varphi(p^k)\operatorname{ord}_{2^k}(3)=6 ∑ k = 0 2 φ ( p k ) ord 2 k ( 3 ) = 6 . If b ∈ { 1 , 3 } b\in\{1,3\} b ∈ { 1 , 3 } , we have p e + s = 2 3 = 8 p^{e+s}=2^3=8 p e + s = 2 3 = 8 . When a = 1 a=1 a = 1 , either b = 0 b=0 b = 0 and we have 2 2 2^2 2 2 cycles of length 1, or ν 2 ( a − 1 ) > ν 2 ( b ) \nu_2(a-1)>\nu_2(b) ν 2 ( a − 1 ) > ν 2 ( b ) and 2 e + s = 2 2 e − ν 2 ( b ) 2^{e+s}=2^{2e-\nu_2(b)} 2 e + s = 2 2 e − ν 2 ( b ) . Therefore, we obtain
∑ f ∈ AP ( Z 2 2 ) ∑ ℓ ∈ L ( f , Z 2 2 ) ℓ 2 N ℓ ( f , Z 2 2 ) = 12 + 16 + 4 + ∑ b ∈ Z 4 ∖ { 0 } 2 4 − ν 2 ( b ) = 72. \sum_{f\in\operatorname{AP}(\mathbb{Z}_{2^2})}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{2^2})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{2^2})=12+16+4+\sum_{b\in\mathbb{Z}_4\setminus\{0\}}2^{4-\nu_2(b)}=72. f ∈ AP ( Z 2 2 ) ∑ ℓ ∈ L ( f , Z 2 2 ) ∑ ℓ 2 N ℓ ( f , Z 2 2 ) = 12 + 16 + 4 + b ∈ Z 4 ∖ { 0 } ∑ 2 4 − ν 2 ( b ) = 72.
For e ≥ 3 e\geq3 e ≥ 3 , if a = 4 j + 3 a=4j+3 a = 4 j + 3 and ν 2 ( b ) = 0 \nu_2(b)=0 ν 2 ( b ) = 0 , for some j ∈ [ 0 , 2 e − 2 − 1 ] j\in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] , then r = ν 2 ( j + 1 ) r=\nu_2(j+1) r = ν 2 ( j + 1 ) and we have 2 r + 1 2^{r+1} 2 r + 1 cycles of length 2 e − r − 1 2^{e-r-1} 2 e − r − 1 . Thus,
∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 2 e − r − 1 . \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{2^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{2^e})=2^{2e-r-1}. ℓ ∈ L ( f , Z 2 e ) ∑ ℓ 2 N ℓ ( f , Z 2 e ) = 2 2 e − r − 1 .
There are 2 e − 1 2^{e-1} 2 e − 1 choices of b b b such that ν 2 ( b ) = 0 \nu_2(b)=0 ν 2 ( b ) = 0 and 2 e − 3 − r 2^{e-3-r} 2 e − 3 − r choices of j j j with ν 2 ( j + 1 ) = r \nu_2(j+1)=r ν 2 ( j + 1 ) = r , for each r ∈ [ 0 , e − 3 ] r\in[0,e-3] r ∈ [ 0 , e − 3 ] , and one with ν 2 ( j + 1 ) = e − 2 \nu_2(j+1)=e-2 ν 2 ( j + 1 ) = e − 2 . Hence, we have
∑ j = 0 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) = 0 2 2 e − ν 2 ( j + 1 ) − 1 = 2 e − 1 ( 2 2 e − ( e − 2 ) − 1 + ∑ r = 0 e − 3 2 e − 3 − r 2 2 e − r − 1 ) = 2 4 e − 3 + 2 2 e 3 . (7) \sum_{j=0}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb{Z}_{2^e}\\\nu_2(b)=0}}2^{2e-\nu_2(j+1)-1}
=2^{e-1}\left(2^{2e-(e-2)-1}+\sum_{r=0}^{e-3}2^{e-3-r}2^{2e-r-1}\right)
=\frac{2^{4e-3}+2^{2e}}{3}. \tag*{(7)} j = 0 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) = 0 ∑ 2 2 e − ν 2 ( j + 1 ) − 1 = 2 e − 1 ( 2 2 e − ( e − 2 ) − 1 + r = 0 ∑ e − 3 2 e − 3 − r 2 2 e − r − 1 ) = 3 2 4 e − 3 + 2 2 e . (7)
If a = 4 j + 3 a=4j+3 a = 4 j + 3 and ν 2 ( b ) > 0 \nu_2(b)>0 ν 2 ( b ) > 0 , then
∑ j = 0 2 e − 2 − 1 ∑ b ∈ Z 2 e ν 2 ( b ) ≥ 1 ∑ k = 0 e φ ( p k ) ord p k ( 4 j + 3 ) = 2 e − 1 ∑ r = 0 e − 3 2 e − 3 − r ( 2 + ∑ k = 2 e 2 k − 1 2 max { 1 , k − 2 − r } ) + 2 e − 1 ( 2 + ∑ k = 2 e 2 k ) . \sum_{j=0}^{2^{e-2}-1}\sum_{\substack{b\in\mathbb{Z}_{2^e}\\\nu_2(b)\geq1}}\sum_{k=0}^{e}\varphi(p^k)\operatorname{ord}_{p^k}(4j+3)
=2^{e-1}\sum_{r=0}^{e-3}2^{e-3-r}\left(2+\sum_{k=2}^{e}2^{k-1}2^{\max\{1,k-2-r\}}\right)
+2^{e-1}\left(2+\sum_{k=2}^{e}2^k\right). j = 0 ∑ 2 e − 2 − 1 b ∈ Z 2 e ν 2 ( b ) ≥ 1 ∑ k = 0 ∑ e φ ( p k ) ord p k ( 4 j + 3 ) = 2 e − 1 r = 0 ∑ e − 3 2 e − 3 − r ( 2 + k = 2 ∑ e 2 k − 1 2 m a x { 1 , k − 2 − r } ) + 2 e − 1 ( 2 + k = 2 ∑ e 2 k ) .
The second term comes from the unique j j j such that ν 2 ( j + 1 ) = e − 2 \nu_2(j+1)=e-2 ν 2 ( j + 1 ) = e − 2 , and it is equal to 2 2 e − 2 e 2^{2e}-2^e 2 2 e − 2 e . In the first term, we have that
2 + ∑ k = 2 e 2 k − 1 2 max { 1 , k − 2 − r } = 2 + ∑ k = 2 r + 3 2 k + ∑ k = r + 4 e 2 2 k − r − 3 = 2 + 2 r + 4 − 4 + 2 2 e − r − 1 − 2 r + 5 3 = 2 2 e − r − 1 + 2 r + 4 − 6 3 . \begin{aligned}
2+\sum_{k=2}^{e}2^{k-1}2^{\max\{1,k-2-r\}}&=2+\sum_{k=2}^{r+3}2^k+\sum_{k=r+4}^{e}2^{2k-r-3}\\
&=2+2^{r+4}-4+\frac{2^{2e-r-1}-2^{r+5}}{3}\\
&=\frac{2^{2e-r-1}+2^{r+4}-6}{3}.
\end{aligned} 2 + k = 2 ∑ e 2 k − 1 2 m a x { 1 , k − 2 − r } = 2 + k = 2 ∑ r + 3 2 k + k = r + 4 ∑ e 2 2 k − r − 3 = 2 + 2 r + 4 − 4 + 3 2 2 e − r − 1 − 2 r + 5 = 3 2 2 e − r − 1 + 2 r + 4 − 6 .
Multiplying by 2 2 e − 4 − r 2^{2e-4-r} 2 2 e − 4 − r and summing over r r r we get
∑ r = 0 e − 3 2 2 e − 4 − r 2 2 e − r − 1 + 2 r + 4 − 6 3 = ∑ r = 0 e − 3 2 4 e − 2 r − 5 + 2 2 e − 3 − 3 ⋅ 2 2 e − 3 − r 3 = 1 3 ( 2 4 e − 3 − 2 2 e + 1 3 + ( e − 2 ) 2 2 e − 3 ( 2 2 e − 2 − 2 e ) ) . \begin{aligned}
\sum_{r=0}^{e-3}2^{2e-4-r}\frac{2^{2e-r-1}+2^{r+4}-6}{3}
&=\sum_{r=0}^{e-3}\frac{2^{4e-2r-5}+2^{2e-3}-3\cdot2^{2e-3-r}}{3}\\
&=\frac{1}{3}\left(\frac{2^{4e-3}-2^{2e+1}}{3}+(e-2)2^{2e}-3(2^{2e-2}-2^e)\right).
\end{aligned} r = 0 ∑ e − 3 2 2 e − 4 − r 3 2 2 e − r − 1 + 2 r + 4 − 6 = r = 0 ∑ e − 3 3 2 4 e − 2 r − 5 + 2 2 e − 3 − 3 ⋅ 2 2 e − 3 − r = 3 1 ( 3 2 4 e − 3 − 2 2 e + 1 + ( e − 2 ) 2 2 e − 3 ( 2 2 e − 2 − 2 e ) ) .
Adding both terms, we get
1 9 ( 9 ( 2 2 e − 2 e ) + 2 4 e − 3 − 2 2 e + 1 + 3 ( e − 2 ) 2 2 e − 9 ( 2 2 e − 2 − 2 e ) ) , \frac{1}{9}\left(9(2^{2e}-2^e)+2^{4e-3}-2^{2e+1}+3(e-2)2^{2e}-9(2^{2e-2}-2^e)\right), 9 1 ( 9 ( 2 2 e − 2 e ) + 2 4 e − 3 − 2 2 e + 1 + 3 ( e − 2 ) 2 2 e − 9 ( 2 2 e − 2 − 2 e ) ) ,
which simplifies to
2 2 e − 3 9 ( 2 2 e + 24 e − 10 ) . (8) \frac{2^{2e-3}}{9}\left(2^{2e}+24e-10\right). \tag*{(8)} 9 2 2 e − 3 ( 2 2 e + 24 e − 10 ) . (8)
For a = 4 j + 1 a=4j+1 a = 4 j + 1 and j ≠ 0 j\ne0 j = 0 , let r = ν 2 ( j ) r=\nu_2(j) r = ν 2 ( j ) . If ν 2 ( b ) = t < r + 2 \nu_2(b)=t<r+2 ν 2 ( b ) = t < r + 2 , then 2 e + s = 2 2 e − t 2^{e+s}=2^{2e-t} 2 e + s = 2 2 e − t . There are 2 e − t − 1 2^{e-t-1} 2 e − t − 1 elements b b b with ν 2 ( b ) = t \nu_2(b)=t ν 2 ( b ) = t , for t ∈ [ 0 , e − 1 ] t\in[0,e-1] t ∈ [ 0 , e − 1 ] . Moreover, there are 2 e − r − 3 2^{e-r-3} 2 e − r − 3 integers j ∈ [ 0 , 2 e − 2 − 1 ] j\in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] with ν 2 ( j ) = r \nu_2(j)=r ν 2 ( j ) = r , for r ∈ [ 0 , e − 3 ] r\in[0,e-3] r ∈ [ 0 , e − 3 ] . Thus, we have
∑ r = 0 e − 3 2 e − r − 3 ∑ t = 0 r + 1 2 e − t − 1 2 2 e − t = ∑ r = 0 e − 3 2 e − r − 4 ∑ t = 0 r + 1 2 2 e − 2 t = ∑ r = 0 e − 3 2 e − r − 4 ( 2 2 e + 2 − 2 2 e − 2 r − 2 3 ) = 1 3 ( 2 4 e − 1 − 2 3 e + 1 + 2 4 e − 3 − 2 e + 3 7 ) = 9 7 2 4 e − 3 − 1 3 2 3 e + 1 + 1 21 2 e + 3 . (9) \begin{aligned}
\sum_{r=0}^{e-3}2^{e-r-3}\sum_{t=0}^{r+1}2^{e-t-1}2^{2e-t}
&=\sum_{r=0}^{e-3}2^{e-r-4}\sum_{t=0}^{r+1}2^{2e-2t}\\
&=\sum_{r=0}^{e-3}2^{e-r-4}\left(\frac{2^{2e+2}-2^{2e-2r-2}}{3}\right)\\
&=\frac{1}{3}\left(2^{4e-1}-2^{3e+1}+\frac{2^{4e-3}-2^{e+3}}{7}\right)\\
&=\frac{9}{7}2^{4e-3}-\frac{1}{3}2^{3e+1}+\frac{1}{21}2^{e+3}. \tag*{(9)}
\end{aligned} r = 0 ∑ e − 3 2 e − r − 3 t = 0 ∑ r + 1 2 e − t − 1 2 2 e − t = r = 0 ∑ e − 3 2 e − r − 4 t = 0 ∑ r + 1 2 2 e − 2 t = r = 0 ∑ e − 3 2 e − r − 4 ( 3 2 2 e + 2 − 2 2 e − 2 r − 2 ) = 3 1 ( 2 4 e − 1 − 2 3 e + 1 + 7 2 4 e − 3 − 2 e + 3 ) = 7 9 2 4 e − 3 − 3 1 2 3 e + 1 + 21 1 2 e + 3 . (9)
If v 2 ( b ) = t ≥ r + 2 v_2(b)=t\ge r+2 v 2 ( b ) = t ≥ r + 2 , we have
∑ k = 0 e φ ( p k ) ord p k ( 4 j + 1 ) = 2 + ∑ k = 2 e 2 k − 1 + max { 0 , k − 2 − r } = 2 + ∑ k = 2 r + 2 2 k − 1 + ∑ k = r + 3 e 2 2 k − r − 3 = 2 2 e − r − 1 + 2 r + 2 3 . \begin{aligned}
\sum_{k=0}^{e}\varphi(p^k)\operatorname{ord}_{p^k}(4j+1)=2+\sum_{k=2}^{e}2^{k-1+\max\{0,k-2-r\}} \\
&=2+\sum_{k=2}^{r+2}2^{k-1}+\sum_{k=r+3}^{e}2^{2k-r-3} \\
&=\frac{2^{2e-r-1}+2^{r+2}}{3}.
\end{aligned} k = 0 ∑ e φ ( p k ) ord p k ( 4 j + 1 ) = 2 + k = 2 ∑ e 2 k − 1 + m a x { 0 , k − 2 − r } = 2 + k = 2 ∑ r + 2 2 k − 1 + k = r + 3 ∑ e 2 2 k − r − 3 = 3 2 2 e − r − 1 + 2 r + 2 .
There are 2 e − r − 2 2^{e-r-2} 2 e − r − 2 choices for b b b with v 2 ( b ) ≥ r + 2 v_2(b)\ge r+2 v 2 ( b ) ≥ r + 2 and, for every r ∈ [ 0 , e − 3 ] r\in[0,e-3] r ∈ [ 0 , e − 3 ] , there are 2 e − r − 3 2^{e-r-3} 2 e − r − 3 integers j ∈ [ 0 , 2 e − 2 − 1 ] j\in[0,2^{e-2}-1] j ∈ [ 0 , 2 e − 2 − 1 ] with v 2 ( j ) = r v_2(j)=r v 2 ( j ) = r . Hence, summing over r ∈ [ 0 , e − 3 ] r\in[0,e-3] r ∈ [ 0 , e − 3 ] we have
∑ r = 0 e − 3 2 e − r − 3 2 e − r − 2 ( 2 2 e − r − 1 + 2 r + 2 3 ) = 1 3 ∑ r = 0 e − 3 ( 2 4 e − 3 r − 6 + 2 2 e − r − 3 ) = 1 3 ( 2 4 e − 3 − 2 e + 3 7 + 2 2 e − 2 − 2 e ) = 1 21 ( 2 4 e − 3 + 7 ⋅ 2 2 e − 2 − 15 ⋅ 2 e ) . (10) \begin{aligned}
\sum_{r=0}^{e-3}2^{e-r-3}2^{e-r-2}\left(\frac{2^{2e-r-1}+2^{r+2}}{3}\right)
=\frac{1}{3}\sum_{r=0}^{e-3}\left(2^{4e-3r-6}+2^{2e-r-3}\right) \\
&=\frac{1}{3}\left(\frac{2^{4e-3}-2^{e+3}}{7}+2^{2e-2}-2^e\right) \\
&=\frac{1}{21}\left(2^{4e-3}+7\cdot2^{2e-2}-15\cdot2^e\right). \tag*{(10)}
\end{aligned} r = 0 ∑ e − 3 2 e − r − 3 2 e − r − 2 ( 3 2 2 e − r − 1 + 2 r + 2 ) = 3 1 r = 0 ∑ e − 3 ( 2 4 e − 3 r − 6 + 2 2 e − r − 3 ) = 3 1 ( 7 2 4 e − 3 − 2 e + 3 + 2 2 e − 2 − 2 e ) = 21 1 ( 2 4 e − 3 + 7 ⋅ 2 2 e − 2 − 15 ⋅ 2 e ) . (10)
When a = 1 a=1 a = 1 we have ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 e + s = 2 2 e − v 2 ( b ) \sum_{\ell\in\mathcal L(f,\mathbb Z_{2^e})}\ell^2\mathcal N_\ell(f,\mathbb Z_{2^e})=2^{e+s}=2^{2e-v_2(b)} ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 e + s = 2 2 e − v 2 ( b ) for every b ∈ Z 2 e ∖ { 0 } b\in\mathbb Z_{2^e}\setminus\{0\} b ∈ Z 2 e ∖ { 0 } and ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 e \sum_{\ell\in\mathcal L(f,\mathbb Z_{2^e})}\ell^2\mathcal N_\ell(f,\mathbb Z_{2^e})=2^e ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 e if b = 0 b=0 b = 0 . Thus, we obtain
2 e + ∑ b ∈ Z 2 e ∖ { 0 } 2 2 e − v 2 ( b ) = 2 e + ∑ t = 0 e − 1 2 e − t − 1 2 e − t = 2 e + ∑ t = 0 e − 1 2 3 e − 2 t − 1 = 2 3 e + 1 + 2 e 3 . (11) \begin{aligned}
2^e+\sum_{b\in\mathbb Z_{2^e}\setminus\{0\}}2^{2e-v_2(b)}
=2^e+\sum_{t=0}^{e-1}2^{e-t-1}2^{e-t} \\
&=2^e+\sum_{t=0}^{e-1}2^{3e-2t-1} \\
&=\frac{2^{3e+1}+2^e}{3}. \tag*{(11)}
\end{aligned} 2 e + b ∈ Z 2 e ∖ { 0 } ∑ 2 2 e − v 2 ( b ) = 2 e + t = 0 ∑ e − 1 2 e − t − 1 2 e − t = 2 e + t = 0 ∑ e − 1 2 3 e − 2 t − 1 = 3 2 3 e + 1 + 2 e . (11)
Adding (6.6), (6.7), (6.8), (6.9) and (6.10), we conclude that
∑ f ∈ AP ( Z 2 e ) ∑ ℓ ∈ L ( f , Z 2 e ) ℓ 2 N ℓ ( f , Z 2 e ) = 2 2 e 18 ( 2 2 e + 2 + 6 e + 5 ) . \sum_{f\in\operatorname{AP}(\mathbb Z_{2^e})}\sum_{\ell\in\mathcal L(f,\mathbb Z_{2^e})}\ell^2\mathcal N_\ell(f,\mathbb Z_{2^e})
=\frac{2^{2e}}{18}(2^{2e+2}+6e+5). f ∈ AP ( Z 2 e ) ∑ ℓ ∈ L ( f , Z 2 e ) ∑ ℓ 2 N ℓ ( f , Z 2 e ) = 18 2 2 e ( 2 2 e + 2 + 6 e + 5 ) .
Theorem 6.4. The expectation for the cycle length of an element x ∈ Z 2 e x\in\mathbb{Z}_{2^e} x ∈ Z 2 e over a function f ∈ A P ( Z 2 e ) f\in AP(\mathbb{Z}_{2^e}) f ∈ A P ( Z 2 e ) , both selected uniformly at random, is
E [ ℓ x ( f , Z 2 e ) ] = 2 2 e + 2 + 6 e + 5 9 ⋅ 2 e . \mathbb{E}[\ell_x(f,\mathbb{Z}_{2^e})]=\frac{2^{2e+2}+6e+5}{9\cdot2^e}. E [ ℓ x ( f , Z 2 e )] = 9 ⋅ 2 e 2 2 e + 2 + 6 e + 5 . Proof. The total number of affine permutations in Z 2 e \mathbb{Z}_{2^e} Z 2 e is φ ( 2 e ) ⋅ 2 e = 2 2 e − 1 \varphi(2^e)\cdot2^e=2^{2e-1} φ ( 2 e ) ⋅ 2 e = 2 2 e − 1 and the total number of points is 2 e 2^e 2 e . From the previous theorem we conclude that the expectation is
2 2 e ( 2 2 e + 2 + 6 e + 5 ) 18 ⋅ 2 3 e − 1 = 2 2 e + 2 + 6 e + 5 9 ⋅ 2 e . \frac{2^{2e}(2^{2e+2}+6e+5)}{18\cdot2^{3e-1}}=\frac{2^{2e+2}+6e+5}{9\cdot2^e}. 18 ⋅ 2 3 e − 1 2 2 e ( 2 2 e + 2 + 6 e + 5 ) = 9 ⋅ 2 e 2 2 e + 2 + 6 e + 5 .
Stochastic properties for odd primes
Theorem 6.5. Let p p p be an odd prime and e e e a positive integer. Then
∑ f ∈ A P ( Z p e ) N ( f , Z p e ) = p 2 e − 2 ( p − 1 ) ( p + e + e ( ( p − 1 ) e + p + 1 ) 2 F ) , \sum_{f\in AP(\mathbb{Z}_{p^e})}\mathcal{N}(f,\mathbb{Z}_{p^e})=p^{2e-2}(p-1)\left(p+e+\frac{e((p-1)e+p+1)}{2}F\right), f ∈ A P ( Z p e ) ∑ N ( f , Z p e ) = p 2 e − 2 ( p − 1 ) ( p + e + 2 e (( p − 1 ) e + p + 1 ) F ) , where F = F ( p − 1 ) = ∑ d ∣ p − 1 d ≠ 1 φ ( d ) d F=F(p-1)=\sum_{\substack{d\mid p-1\\d\ne1}}\frac{\varphi(d)}{d} F = F ( p − 1 ) = ∑ d ∣ p − 1 d = 1 d φ ( d ) .
Proof. Let f ∈ A P ( Z p e ) f\in AP(\mathbb{Z}_{p^e}) f ∈ A P ( Z p e ) be given by f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b . From Theorem 5.1 we have
∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = { ∑ k = 0 e φ ( p k ) p k ord p k ( a ) if ν p ( a − 1 ) ≤ ν p ( b ) , p ν p ( b ) otherwise. \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=
\begin{cases}
\sum_{k=0}^{e}\frac{\varphi(p^k)}{p^k\operatorname{ord}_{p^k}(a)} & \text{if }\nu_p(a-1)\leq\nu_p(b),\\
p^{\nu_p(b)} & \text{otherwise.}
\end{cases} ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = { ∑ k = 0 e p k ord p k ( a ) φ ( p k ) p ν p ( b ) if ν p ( a − 1 ) ≤ ν p ( b ) , otherwise. We begin with the case where e = 1 e=1 e = 1 . If a ∈ [ 2 , p − 1 ] a\in[2,p-1] a ∈ [ 2 , p − 1 ] , then ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\leq\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) for every b ∈ Z p b\in\mathbb{Z}_p b ∈ Z p . Thus
∑ b ∈ Z p ∑ i = 2 p − 1 ∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = ∑ b ∈ Z p ∑ i = 2 p − 1 1 + φ ( p ) ord p ( i ) = p ( p − 2 ) + p ( p − 1 ) ∑ i = 2 p − 1 1 ord p ( i ) . (12) \sum_{b\in\mathbb{Z}_p}\sum_{i=2}^{p-1}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})
=\sum_{b\in\mathbb{Z}_p}\sum_{i=2}^{p-1}1+\frac{\varphi(p)}{\operatorname{ord}_p(i)}
=p(p-2)+p(p-1)\sum_{i=2}^{p-1}\frac{1}{\operatorname{ord}_p(i)}. \tag*{(12)} b ∈ Z p ∑ i = 2 ∑ p − 1 ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = b ∈ Z p ∑ i = 2 ∑ p − 1 1 + ord p ( i ) φ ( p ) = p ( p − 2 ) + p ( p − 1 ) i = 2 ∑ p − 1 ord p ( i ) 1 . (12) For each d d d divisor of p − 1 p-1 p − 1 , there are φ ( d ) \varphi(d) φ ( d ) elements with order d d d in U ( Z p ) U(\mathbb{Z}_p) U ( Z p ) . Let
F = ∑ d ∣ p − 1 d ≠ 1 φ ( d ) d . F=\sum_{\substack{d\mid p-1\\d\ne1}}\frac{\varphi(d)}{d}. F = d ∣ p − 1 d = 1 ∑ d φ ( d ) . Thus, (12) is equal to
p ( p − 2 ) + p ( p − 1 ) F (13) p(p-2)+p(p-1)F \tag*{(13)} p ( p − 2 ) + p ( p − 1 ) F (13)
If a = 1 a=1 a = 1 , then ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\leq\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) if and only if b = 0 b=0 b = 0 . Thus
∑ b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = 1 + ( p − 1 ) + ∑ b ∈ Z p ∖ { 0 } p ν p ( b ) = 2 p − 1. (14) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=1+(p-1)+\sum_{b\in\mathbb{Z}_p\setminus\{0\}}p^{\nu_p(b)}=2p-1. \tag*{(14)} b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = 1 + ( p − 1 ) + b ∈ Z p ∖ { 0 } ∑ p ν p ( b ) = 2 p − 1. (14)
Adding (6.12) and (6.13) we get
( p − 1 ) ( p F + p + 1 ) . (p-1)(pF+p+1). ( p − 1 ) ( pF + p + 1 ) .
For e > 1 e>1 e > 1 , we notice that any a ∈ U ( Z p e ) a\in U(\mathbb{Z}_{p^e}) a ∈ U ( Z p e ) can be written as a = j p + i a=jp+i a = j p + i with j ∈ [ 0 , p e − 1 − 1 ] j\in[0,p^{e-1}-1] j ∈ [ 0 , p e − 1 − 1 ] and i ∈ [ 1 , p − 1 ] i\in[1,p-1] i ∈ [ 1 , p − 1 ] . When i ≠ 1 i\neq1 i = 1 , we have that ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\leq\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) for every b ∈ Z p e b\in\mathbb{Z}_{p^e} b ∈ Z p e . Therefore, it follows that
∑ b ∈ Z p e ∑ j = 0 p e − 1 − 1 ∑ i = 2 p − 1 ∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = ∑ b ∈ Z p e ∑ j = 0 p e − 1 − 1 ∑ i = 2 p − 1 ∑ k = 0 e φ ( p k ) ord p k ( j p + i ) . (15) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{j=0}^{p^{e-1}-1}\sum_{i=2}^{p-1}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=\sum_{b\in\mathbb{Z}_{p^e}}\sum_{j=0}^{p^{e-1}-1}\sum_{i=2}^{p-1}\sum_{k=0}^{e}\frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+i)}. \tag*{(15)} b ∈ Z p e ∑ j = 0 ∑ p e − 1 − 1 i = 2 ∑ p − 1 ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = b ∈ Z p e ∑ j = 0 ∑ p e − 1 − 1 i = 2 ∑ p − 1 k = 0 ∑ e ord p k ( j p + i ) φ ( p k ) . (15)
Let d i = ord p ( i ) d_i=\operatorname{ord}_p(i) d i = ord p ( i ) , for i ∈ [ 2 , p − 1 ] i\in[2,p-1] i ∈ [ 2 , p − 1 ] . We observe that ord p ( j p + i ) = ord p ( i ) \operatorname{ord}_p(jp+i)=\operatorname{ord}_p(i) ord p ( j p + i ) = ord p ( i ) . For a fixed i i i , let t j = ν p ( ( j p + i ) d i − 1 ) t_j=\nu_p((jp+i)^{d_i}-1) t j = ν p (( j p + i ) d i − 1 ) . When k = 0 k=0 k = 0 , we have that φ ( p k ) ord p k ( j p + i ) = 1 \frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+i)}=1 ord p k ( j p + i ) φ ( p k ) = 1 and ∑ j = 0 p e − 1 − 1 1 = p e − 1 \sum_{j=0}^{p^{e-1}-1}1=p^{e-1} ∑ j = 0 p e − 1 − 1 1 = p e − 1 . Otherwise, for any k ∈ [ 1 , e ] k\in[1,e] k ∈ [ 1 , e ] , we have that ord p k ( j p + i ) = d i p max { 0 , k − t j } \operatorname{ord}_{p^k}(jp+i)=d_i p^{\max\{0,k-t_j\}} ord p k ( j p + i ) = d i p m a x { 0 , k − t j } and
φ ( p k ) ord p k ( j p + i ) = p k − p k − 1 d i p max { 0 , k − t j } = ( p − 1 ) p min { k − 1 , t j − 1 } d i . \frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+i)}=\frac{p^k-p^{k-1}}{d_i p^{\max\{0,k-t_j\}}}=\frac{(p-1)p^{\min\{k-1,t_j-1\}}}{d_i}. ord p k ( j p + i ) φ ( p k ) = d i p m a x { 0 , k − t j } p k − p k − 1 = d i ( p − 1 ) p m i n { k − 1 , t j − 1 } .
As t j ≥ 1 t_j\geq1 t j ≥ 1 for every j j j and d i < p d_i<p d i < p , Lemma 2.3 implies that, for every r ∈ [ 1 , e ] r\in[1,e] r ∈ [ 1 , e ] , there are p e − r p^{e-r} p e − r choices of j ∈ [ 0 , p e − 1 − 1 ] j\in[0,p^{e-1}-1] j ∈ [ 0 , p e − 1 − 1 ] such that t j ≥ r t_j\geq r t j ≥ r . Thus, there are exactly p e − r − p e − r − 1 p^{e-r}-p^{e-r-1} p e − r − p e − r − 1 choices such that t j = r t_j=r t j = r , for r ∈ [ 1 , e − 1 ] r\in[1,e-1] r ∈ [ 1 , e − 1 ] and 1 1 1 such that t j ≥ e t_j\geq e t j ≥ e . Hence
∑ j = 0 p e − 1 − 1 p min { k − 1 , t j − 1 } = p e − k p k − 1 + ∑ r = 1 k − 1 p r − 1 ( p e − r − p e − r − 1 ) = p e − 1 + ( k − 1 ) ( p e − 1 − p e − 2 ) = k p e − 1 − ( k − 1 ) p e − 2 . \begin{aligned}
\sum_{j=0}^{p^{e-1}-1}p^{\min\{k-1,t_j-1\}}=p^{e-k}p^{k-1}+\sum_{r=1}^{k-1}p^{r-1}\left(p^{e-r}-p^{e-r-1}\right) \\
&=p^{e-1}+(k-1)\left(p^{e-1}-p^{e-2}\right) \\
&=kp^{e-1}-(k-1)p^{e-2}.
\end{aligned} j = 0 ∑ p e − 1 − 1 p m i n { k − 1 , t j − 1 } = p e − k p k − 1 + r = 1 ∑ k − 1 p r − 1 ( p e − r − p e − r − 1 ) = p e − 1 + ( k − 1 ) ( p e − 1 − p e − 2 ) = k p e − 1 − ( k − 1 ) p e − 2 .
Therefore, we have
∑ k = 1 e ( k p e − 1 − ( k − 1 ) p e − 2 ) = e ( e + 1 ) 2 p e − 1 − e ( e − 1 ) 2 p e − 2 . \sum_{k=1}^{e}\left(kp^{e-1}-(k-1)p^{e-2}\right)=\frac{e(e+1)}{2}p^{e-1}-\frac{e(e-1)}{2}p^{e-2}. k = 1 ∑ e ( k p e − 1 − ( k − 1 ) p e − 2 ) = 2 e ( e + 1 ) p e − 1 − 2 e ( e − 1 ) p e − 2 .
and (15) is equal to
∑ b ∈ Z p e ∑ i = 2 p − 1 ( p e − 1 + p − 1 d i ( e ( e + 1 ) 2 p e − 1 − e ( e − 1 ) 2 p e − 2 ) ) . \sum_{b\in\mathbb{Z}_{p^e}}\sum_{i=2}^{p-1}\left(p^{e-1}+\frac{p-1}{d_i}\left(\frac{e(e+1)}{2}p^{e-1}-\frac{e(e-1)}{2}p^{e-2}\right)\right). b ∈ Z p e ∑ i = 2 ∑ p − 1 ( p e − 1 + d i p − 1 ( 2 e ( e + 1 ) p e − 1 − 2 e ( e − 1 ) p e − 2 ) ) .
To sum over i i i , we observe that for every d d d divisor of p − 1 p-1 p − 1 , there are φ ( d ) \varphi(d) φ ( d ) choices of i ∈ [ 1 , p − 1 ] i\in[1,p-1] i ∈ [ 1 , p − 1 ] such that d i = d d_i=d d i = d . Thus,
∑ i = 2 p − 1 1 d i = ∑ d ∣ p − 1 d > 1 φ ( d ) d . \sum_{i=2}^{p-1}\frac{1}{d_i}=\sum_{\substack{d\mid p-1\\d>1}}\frac{\varphi(d)}{d}. i = 2 ∑ p − 1 d i 1 = d ∣ p − 1 d > 1 ∑ d φ ( d ) .
Also summing over b ∈ Z p e b\in\mathbb{Z}_{p^e} b ∈ Z p e , this concludes that (15) is equal to
p 2 e − 1 ( p − 2 ) + p e ( p − 1 ) ( e ( e + 1 ) 2 p e − 1 − e ( e − 1 ) 2 p e − 2 ) ∑ d ∣ p − 1 d > 1 φ ( d ) d . (16) p^{2e-1}(p-2)+p^e(p-1)\left(\frac{e(e+1)}{2}p^{e-1}-\frac{e(e-1)}{2}p^{e-2}\right)\sum_{\substack{d\mid p-1\\d>1}}\frac{\varphi(d)}{d}. \tag*{(16)} p 2 e − 1 ( p − 2 ) + p e ( p − 1 ) ( 2 e ( e + 1 ) p e − 1 − 2 e ( e − 1 ) p e − 2 ) d ∣ p − 1 d > 1 ∑ d φ ( d ) . (16)
Now, we look at the case where i = 1 i=1 i = 1 and j > 0 j>0 j > 0 . We have that ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\leq\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) if and only if ν p ( b ) > ν p ( j ) \nu_p(b)>\nu_p(j) ν p ( b ) > ν p ( j ) . Thus, we have
∑ b ∈ Z p e ∑ j = 1 p e − 1 − 1 ∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = ∑ j = 1 p e − 1 − 1 ∑ b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ k = 0 e φ ( p k ) ord p k ( j p + 1 ) + ∑ j = 1 p e − 1 − 1 ∑ b ∈ Z p e ν p ( b ) ≤ ν p ( j ) p ν p ( b ) . (17) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{j=1}^{p^{e-1}-1}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}N_\ell(f,\mathbb{Z}_{p^e})
=
\sum_{j=1}^{p^{e-1}-1}\sum_{\substack{b\in\mathbb{Z}_{p^e}\\\nu_p(b)>\nu_p(j)}}\sum_{k=0}^{e}\frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+1)}
+
\sum_{j=1}^{p^{e-1}-1}\sum_{\substack{b\in\mathbb{Z}_{p^e}\\\nu_p(b)\leq\nu_p(j)}}p^{\nu_p(b)}. \tag*{(17)} b ∈ Z p e ∑ j = 1 ∑ p e − 1 − 1 ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = j = 1 ∑ p e − 1 − 1 b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ k = 0 ∑ e ord p k ( j p + 1 ) φ ( p k ) + j = 1 ∑ p e − 1 − 1 b ∈ Z p e ν p ( b ) ≤ ν p ( j ) ∑ p ν p ( b ) . (17)
In the first summand, when k = 0 k=0 k = 0 we have φ ( p k ) ord p k ( j p + 1 ) = 1 \frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+1)}=1 ord p k ( j p + 1 ) φ ( p k ) = 1 . Otherwise, we get
φ ( p k ) ord p k ( j p + 1 ) = ( p − 1 ) p min { k − 1 , ν p ( j ) } . \frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+1)}=(p-1)p^{\min\{k-1,\nu_p(j)\}}. ord p k ( j p + 1 ) φ ( p k ) = ( p − 1 ) p m i n { k − 1 , ν p ( j )} .
For each r ∈ [ 0 , e − 2 ] r\in[0,e-2] r ∈ [ 0 , e − 2 ] , there are p e − r − 2 ( p − 1 ) p^{e-r-2}(p-1) p e − r − 2 ( p − 1 ) choices of j ∈ [ 1 , p e − 1 − 1 ] j\in[1,p^{e-1}-1] j ∈ [ 1 , p e − 1 − 1 ] with ν p ( j ) = r \nu_p(j)=r ν p ( j ) = r . Moreover, there are p e − r − 1 p^{e-r-1} p e − r − 1 choices for b ∈ Z p e b \in\mathbb{Z}_{p^e} b ∈ Z p e such that ν p ( b ) > r \nu_p(b)>r ν p ( b ) > r . Therefore, we have that
∑ j = 1 p e − 1 − 1 ∑ b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ k = 0 e φ ( p k ) ord p k ( j p + 1 ) = ∑ r = 0 e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + ∑ k = 1 r + 1 ( p − 1 ) p k − 1 + ∑ k = r + 2 e ( p − 1 ) p r ) = ∑ r = 0 e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + ( p r + 1 − 1 ) + ( e − r − 1 ) ( p − 1 ) p r ) = p e − 2 ∑ r = 0 e − 2 p e − r − 1 ( p − 1 ) ( p + ( e − r − 1 ) ( p − 1 ) ) = p e − 1 ( p − 1 ) ( e p e − 1 − 1 ) . (18) \begin{aligned}
\sum_{j=1}^{p^{e-1}-1}\sum_{\substack{b\in\mathbb{Z}_{p^e}\\ \nu_p(b)>\nu_p(j)}}\sum_{k=0}^{e}\frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(jp+1)}
&=\sum_{r=0}^{e-2}p^{2e-2r-3}(p-1)\left(1+\sum_{k=1}^{r+1}(p-1)p^{k-1}+\sum_{k=r+2}^{e}(p-1)p^r\right)\\
&=\sum_{r=0}^{e-2}p^{2e-2r-3}(p-1)\left(1+(p^{r+1}-1)+(e-r-1)(p-1)p^r\right)\\
&=p^{e-2}\sum_{r=0}^{e-2}p^{e-r-1}(p-1)\left(p+(e-r-1)(p-1)\right)\\
&=p^{e-1}(p-1)(ep^{e-1}-1). \tag*{(18)}
\end{aligned} j = 1 ∑ p e − 1 − 1 b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ k = 0 ∑ e ord p k ( j p + 1 ) φ ( p k ) = r = 0 ∑ e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + k = 1 ∑ r + 1 ( p − 1 ) p k − 1 + k = r + 2 ∑ e ( p − 1 ) p r ) = r = 0 ∑ e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + ( p r + 1 − 1 ) + ( e − r − 1 ) ( p − 1 ) p r ) = p e − 2 r = 0 ∑ e − 2 p e − r − 1 ( p − 1 ) ( p + ( e − r − 1 ) ( p − 1 ) ) = p e − 1 ( p − 1 ) ( e p e − 1 − 1 ) . (18)
In the second summand of (6.16), using Lemma 2.4 we have that
∑ j = 1 p e − 1 − 1 ∑ b ∈ Z p e ν p ( b ) ≤ ν p ( j ) p ν p ( b ) = ∑ j = 1 p e − 1 − 1 ∑ r = 0 p e − 1 − 1 − ν p ( j ) p r ( p e − r − p e − 1 − r ) = ( p e − p e − 1 ) ∑ j = 1 p e − 1 − 1 ν p ( j ) + 1 = ( p e − p e − 1 ) ( p e − 1 − 1 + p e − 1 − 1 p − 1 − ( e − 1 ) ) = p e ( p e − 1 − 1 ) − p e − 1 ( p − 1 ) ( e − 1 ) . (19) \begin{aligned}
\sum_{j=1}^{p^{e-1}-1}\sum_{\substack{b\in\mathbb{Z}_{p^e}\\ \nu_p(b)\leq\nu_p(j)}}p^{\nu_p(b)}
&=\sum_{j=1}^{p^{e-1}-1}\sum_{r=0}^{p^{e-1}-1-\nu_p(j)}p^r\left(p^{e-r}-p^{e-1-r}\right)\\
&=\left(p^e-p^{e-1}\right)\sum_{j=1}^{p^{e-1}-1}\nu_p(j)+1\\
&=\left(p^e-p^{e-1}\right)\left(p^{e-1}-1+\frac{p^{e-1}-1}{p-1}-(e-1)\right)\\
&=p^e(p^{e-1}-1)-p^{e-1}(p-1)(e-1). \tag*{(19)}
\end{aligned} j = 1 ∑ p e − 1 − 1 b ∈ Z p e ν p ( b ) ≤ ν p ( j ) ∑ p ν p ( b ) = j = 1 ∑ p e − 1 − 1 r = 0 ∑ p e − 1 − 1 − ν p ( j ) p r ( p e − r − p e − 1 − r ) = ( p e − p e − 1 ) j = 1 ∑ p e − 1 − 1 ν p ( j ) + 1 = ( p e − p e − 1 ) ( p e − 1 − 1 + p − 1 p e − 1 − 1 − ( e − 1 ) ) = p e ( p e − 1 − 1 ) − p e − 1 ( p − 1 ) ( e − 1 ) . (19)
Now when i = 1 i=1 i = 1 and j = 0 j=0 j = 0 , we have that ν p ( b ) ≥ ν p ( a − 1 ) \nu_p(b)\geq\nu_p(a-1) ν p ( b ) ≥ ν p ( a − 1 ) if and only if b = 0 b=0 b = 0 . Hence, we have
∑ b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) N ℓ ( f , Z p e ) = ∑ k = 0 e φ ( p k ) ord p k ( 1 ) + ∑ b ∈ Z p e ∖ { 0 } p ν p ( b ) = p e + ∑ r = 0 e − 1 p r ( p e − r − p e − r − 1 ) = p e + e ( p e − p e − 1 ) . (20) \begin{aligned}
\sum_{b\in\mathbb{Z}_{p^e}}\sum_{\ell\in L(f,\mathbb{Z}_{p^e})}\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})
&=\sum_{k=0}^{e}\frac{\varphi(p^k)}{\operatorname{ord}_{p^k}(1)}+\sum_{b\in\mathbb{Z}_{p^e}\setminus\{0\}}p^{\nu_p(b)}\\
&=p^e+\sum_{r=0}^{e-1}p^r\left(p^{e-r}-p^{e-r-1}\right)\\
&=p^e+e(p^e-p^{e-1}). \tag*{(20)}
\end{aligned} b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) ∑ N ℓ ( f , Z p e ) = k = 0 ∑ e ord p k ( 1 ) φ ( p k ) + b ∈ Z p e ∖ { 0 } ∑ p ν p ( b ) = p e + r = 0 ∑ e − 1 p r ( p e − r − p e − r − 1 ) = p e + e ( p e − p e − 1 ) . (20)
Adding (6.15), (6.17), (6.18) and (6.19), we obtain
p 2 e − 2 ( p − 1 ) ( p + e ) + p e ( p − 1 ) ( e ( e + 1 ) 2 p e − 1 − e ( e − 1 ) 2 p e − 2 ) ∑ d ∣ p − 1 d > 1 φ ( d ) d = p 2 e − 2 ( p − 1 ) ( p + e + e ( ( p − 1 ) e + p + 1 ) 2 F ) p^{2e-2}(p-1)(p+e)+p^e(p-1)\left(\frac{e(e+1)}{2}p^{e-1}-\frac{e(e-1)}{2}p^{e-2}\right)\sum_{\substack{d\mid p-1\\d>1}}\frac{\varphi(d)}{d}
= p^{2e-2}(p-1)\left(p+e+\frac{e((p-1)e+p+1)}{2}F\right) p 2 e − 2 ( p − 1 ) ( p + e ) + p e ( p − 1 ) ( 2 e ( e + 1 ) p e − 1 − 2 e ( e − 1 ) p e − 2 ) d ∣ p − 1 d > 1 ∑ d φ ( d ) = p 2 e − 2 ( p − 1 ) ( p + e + 2 e (( p − 1 ) e + p + 1 ) F )
Theorem 6.6. Let p p p be an odd prime and e e e a positive integer. The expectation for the number of cycles in the functional graph of a map f ∈ A P ( Z p e ) f\in AP(\mathbb{Z}_{p^e}) f ∈ A P ( Z p e ) selected uniformly at random is
E [ N ( f , Z p e ) ] = 1 + e p + e ( ( p − 1 ) e + p + 1 ) 2 p F . \mathbb{E}[\mathcal{N}(f,\mathbb{Z}_{p^e})]=1+\frac{e}{p}+\frac{e((p-1)e+p+1)}{2p}F. E [ N ( f , Z p e )] = 1 + p e + 2 p e (( p − 1 ) e + p + 1 ) F .
Proof. This result follows by dividing the total number of cycles from Theorem 6.5 by φ ( p e ) ⋅ p e = p 2 e − 1 ( p − 1 ) \varphi(p^e)\cdot p^e=p^{2e-1}(p-1) φ ( p e ) ⋅ p e = p 2 e − 1 ( p − 1 ) , the total number of affine permutations in Z p e \mathbb{Z}_{p^e} Z p e . □
Theorem 6.7. Let p p p be an odd prime and e e e a positive integer. Then
∑ f ∈ A P ( Z p e ) ∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) = p 2 e − 1 ( p + 1 ) 2 ( ( p + 1 ) p 2 e + 1 + p 3 − 2 p − 1 + G ( p 2 e + 1 + e ( p 2 − 1 ) − p ) ) , \sum_{f\in AP(\mathbb{Z}_{p^e})}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})
=\frac{p^{2e-1}}{(p+1)^2}\left((p+1)p^{2e+1}+p^3-2p-1+G(p^{2e+1}+e(p^2-1)-p)\right), f ∈ A P ( Z p e ) ∑ ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) = ( p + 1 ) 2 p 2 e − 1 ( ( p + 1 ) p 2 e + 1 + p 3 − 2 p − 1 + G ( p 2 e + 1 + e ( p 2 − 1 ) − p ) ) , where G = G ( p − 1 ) = ∑ d ∣ p − 1 d ≠ 1 d ⋅ φ ( d ) G=G(p-1)=\sum_{\substack{d\mid p-1\\d\ne1}}d\cdot\varphi(d) G = G ( p − 1 ) = ∑ d ∣ p − 1 d = 1 d ⋅ φ ( d ) .
Proof. For an affine permutation f ( x ) = a x + b f(x)=ax+b f ( x ) = a x + b over Z p e \mathbb{Z}_{p^e} Z p e , we have that
∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) = ∑ k = 0 e φ ( p k ) ord p k ( a ) , \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=\sum_{k=0}^{e}\varphi(p^k)\operatorname{ord}_{p^k}(a), ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) = k = 0 ∑ e φ ( p k ) ord p k ( a ) , if ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) , and
∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) = p 2 e − ν p ( b ) , \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=p^{2e-\nu_p(b)}, ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) = p 2 e − ν p ( b ) , if ν p ( a − 1 ) > ν p ( b ) \nu_p(a-1)>\nu_p(b) ν p ( a − 1 ) > ν p ( b ) .
Suppose e = 1 e=1 e = 1 . If a ∈ [ 2 , p − 1 ] a\in[2,p-1] a ∈ [ 2 , p − 1 ] , then ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) for all b ∈ Z p b\in\mathbb{Z}_p b ∈ Z p and
∑ ℓ ∈ L ( f , Z p ) ℓ 2 N ℓ ( f , Z p ) = 1 + ( p − 1 ) ord p ( a ) . \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_p)} \ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_p)=1+(p-1)\operatorname{ord}_p(a). ℓ ∈ L ( f , Z p ) ∑ ℓ 2 N ℓ ( f , Z p ) = 1 + ( p − 1 ) ord p ( a ) .
Summing over b b b and a a a we have
∑ a ∈ [ 2 , p − 1 ] ∑ b ∈ Z p 1 + ( p − 1 ) ord p ( a ) = p ( p − 2 ) + p ( p − 1 ) ∑ d ∣ p − 1 d ≠ 1 d φ ( d ) . \sum_{a\in[2,p-1]}\sum_{b\in\mathbb{Z}_p}1+(p-1)\operatorname{ord}_p(a)=p(p-2)+p(p-1)\sum_{\substack{d\mid p-1\\d\ne1}}d\varphi(d). a ∈ [ 2 , p − 1 ] ∑ b ∈ Z p ∑ 1 + ( p − 1 ) ord p ( a ) = p ( p − 2 ) + p ( p − 1 ) d ∣ p − 1 d = 1 ∑ d φ ( d ) .
Defining G = ∑ d ∣ p − 1 d ≠ 1 d φ ( d ) G=\sum_{\substack{d\mid p-1\\d\ne1}}d\varphi(d) G = ∑ d ∣ p − 1 d = 1 d φ ( d ) , we have
p ( p − 2 ) + p ( p − 1 ) G . (21) p(p-2)+p(p-1)G. \tag*{(21)} p ( p − 2 ) + p ( p − 1 ) G . (21)
If a = 1 a=1 a = 1 , when b = 0 b=0 b = 0 we have the identity map and ∑ ℓ ∈ L ( f , Z p ) ℓ 2 N ℓ ( f , Z p ) = p \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_p)}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_p)=p ∑ ℓ ∈ L ( f , Z p ) ℓ 2 N ℓ ( f , Z p ) = p . Otherwise, we have ∑ ℓ ∈ L ( f , Z p ) ℓ 2 N ℓ ( f , Z p ) = p 2 \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_p)}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_p)=p^2 ∑ ℓ ∈ L ( f , Z p ) ℓ 2 N ℓ ( f , Z p ) = p 2 for every b ∈ Z p ∖ { 0 } b\in\mathbb{Z}_p\setminus\{0\} b ∈ Z p ∖ { 0 } , thus
∑ b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) = p + ( p − 1 ) p 2 . (22) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=p+(p-1)p^2. \tag*{(22)} b ∈ Z p e ∑ ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) = p + ( p − 1 ) p 2 . (22)
Adding (6.20) and (6.21) we get
p ( p − 1 ) ( G + p + 1 ) . p(p-1)(G+p+1). p ( p − 1 ) ( G + p + 1 ) .
Now, suppose e > 1 e>1 e > 1 . If a = j p + i a=jp+i a = j p + i , where j ∈ [ 0 , p e − 1 − 1 ] j\in[0,p^{e-1}-1] j ∈ [ 0 , p e − 1 − 1 ] and i ∈ [ 2 , p − 1 ] i\in[2,p-1] i ∈ [ 2 , p − 1 ] , then ν p ( a − 1 ) ≤ ν p ( b ) \nu_p(a-1)\le\nu_p(b) ν p ( a − 1 ) ≤ ν p ( b ) for every b ∈ Z p e b\in\mathbb{Z}_{p^e} b ∈ Z p e . Let d i = ord p ( i ) d_i=\operatorname{ord}_p(i) d i = ord p ( i ) and t j = ν p ( ( j p + i ) d i − 1 ) t_j=\nu_p((jp+i)^{d_i}-1) t j = ν p (( j p + i ) d i − 1 ) . When k = 0 k=0 k = 0 , we have
∑ b ∈ Z p e ∑ j = 0 p e − 1 − 1 ∑ i = 2 p − 1 φ ( p k ) ord p k ( j p + i ) = p 2 e − 1 ( p − 2 ) . (23) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{j=0}^{p^{e-1}-1}\sum_{i=2}^{p-1}\varphi(p^k)\operatorname{ord}_{p^k}(jp+i)=p^{2e-1}(p-2). \tag*{(23)} b ∈ Z p e ∑ j = 0 ∑ p e − 1 − 1 i = 2 ∑ p − 1 φ ( p k ) ord p k ( j p + i ) = p 2 e − 1 ( p − 2 ) . (23)
For k = 1 k=1 k = 1 we have
∑ b ∈ Z p e ∑ j = 0 p e − 1 − 1 ∑ i = 2 p − 1 φ ( p k ) ord p k ( j p + i ) = p 2 e − 1 ( p − 1 ) G . (24) \sum_{b\in\mathbb{Z}_{p^e}}\sum_{j=0}^{p^{e-1}-1}\sum_{i=2}^{p-1}\varphi(p^k)\operatorname{ord}_{p^k}(jp+i)=p^{2e-1}(p-1)G. \tag*{(24)} b ∈ Z p e ∑ j = 0 ∑ p e − 1 − 1 i = 2 ∑ p − 1 φ ( p k ) ord p k ( j p + i ) = p 2 e − 1 ( p − 1 ) G . (24)
And, for k ∈ [ 2 , e ] k\in[2,e] k ∈ [ 2 , e ] , we have φ ( p k ) ord p k ( j p + i ) = ( p − 1 ) p max { k − 1 , 2 k − t j − 1 } d i \varphi(p^k)\operatorname{ord}_{p^k}(jp+i)=(p-1)p^{\max\{k-1,2k-t_j-1\}d_i} φ ( p k ) ord p k ( j p + i ) = ( p − 1 ) p m a x { k − 1 , 2 k − t j − 1 } d i . For every r ∈ [ 1 , e − 1 ] r\in[1,e-1] r ∈ [ 1 , e − 1 ] , there are p e − r − p e − r − 1 p^{e-r}-p^{e-r-1} p e − r − p e − r − 1 values for j j j such that t j = r t_j=r t j = r and one value with t j ≥ e t_j \ge e t j ≥ e . For a fixed k k k , we have
∑ j = 0 p e − 1 − 1 d i ( p − 1 ) p max { k − 1 , 2 k − t j − 1 } = d i ( p − 1 ) ( p e − 1 + ∑ r = 1 k − 1 ( p e − r − p e − r − 1 ) p 2 k − r − 1 ) = d i ( p − 1 ) ( p e − 1 + ( p − 1 ) ∑ r = 1 k − 1 p e + 2 k − 2 r − 2 ) = d i ( p − 1 ) ( p e − 1 + p e + 2 k − 2 − p e p + 1 ) = d i ( p − 1 ) p e + 2 k − 2 + p e − 1 p + 1 . \begin{aligned}
\sum_{j=0}^{p^{e-1}-1} d_i(p-1)p^{\max\{k-1,2k-t_j-1\}}=d_i(p-1)\left(p^{e-1}+\sum_{r=1}^{k-1}\left(p^{e-r}-p^{e-r-1}\right)p^{2k-r-1}\right) \\
&=d_i(p-1)\left(p^{e-1}+(p-1)\sum_{r=1}^{k-1}p^{e+2k-2r-2}\right) \\
&=d_i(p-1)\left(p^{e-1}+\frac{p^{e+2k-2}-p^e}{p+1}\right) \\
&=d_i(p-1)\frac{p^{e+2k-2}+p^{e-1}}{p+1}.
\end{aligned} j = 0 ∑ p e − 1 − 1 d i ( p − 1 ) p m a x { k − 1 , 2 k − t j − 1 } = d i ( p − 1 ) ( p e − 1 + r = 1 ∑ k − 1 ( p e − r − p e − r − 1 ) p 2 k − r − 1 ) = d i ( p − 1 ) ( p e − 1 + ( p − 1 ) r = 1 ∑ k − 1 p e + 2 k − 2 r − 2 ) = d i ( p − 1 ) ( p e − 1 + p + 1 p e + 2 k − 2 − p e ) = d i ( p − 1 ) p + 1 p e + 2 k − 2 + p e − 1 .
Summing over k ∈ [ 2 , e ] k\in[2,e] k ∈ [ 2 , e ] , we get
∑ k = 2 e d i ( p − 1 ) p e + 2 k − 2 + p e − 1 p + 1 = d i p e − 1 ( p + 1 ) 2 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) . \sum_{k=2}^{e}d_i(p-1)\frac{p^{e+2k-2}+p^{e-1}}{p+1}
=\frac{d_ip^{e-1}}{(p+1)^2}\left(p^{2e+1}-p^3+(e-1)(p^2-1)\right). k = 2 ∑ e d i ( p − 1 ) p + 1 p e + 2 k − 2 + p e − 1 = ( p + 1 ) 2 d i p e − 1 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) .
And summing over i ∈ [ 2 , p − 1 ] i\in[2,p-1] i ∈ [ 2 , p − 1 ] and b ∈ Z p e b\in\mathbb{Z}_{p^e} b ∈ Z p e , we obtain
∑ b ∈ Z p e ∑ i = 2 p − 1 d i p e − 1 ( p + 1 ) 2 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) = p 2 e − 1 ( p + 1 ) 2 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) G . (25) \begin{aligned}
\sum_{b\in\mathbb{Z}_{p^e}}\sum_{i=2}^{p-1}\frac{d_ip^{e-1}}{(p+1)^2}\left(p^{2e+1}-p^3+(e-1)(p^2-1)\right) \\
&=\frac{p^{2e-1}}{(p+1)^2}\left(p^{2e+1}-p^3+(e-1)(p^2-1)\right)G. \tag*{(25)}
\end{aligned} b ∈ Z p e ∑ i = 2 ∑ p − 1 ( p + 1 ) 2 d i p e − 1 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) = ( p + 1 ) 2 p 2 e − 1 ( p 2 e + 1 − p 3 + ( e − 1 ) ( p 2 − 1 ) ) G . (25)
Adding (6.22), (6.23) and (6.24) we have
p 2 e − 1 ( p − 2 + p 2 e + 1 + e ( p 2 − 1 ) − p ( p + 1 ) 2 G ) . (26) p^{2e-1}\left(p-2+\frac{p^{2e+1}+e(p^2-1)-p}{(p+1)^2}G\right). \tag*{(26)} p 2 e − 1 ( p − 2 + ( p + 1 ) 2 p 2 e + 1 + e ( p 2 − 1 ) − p G ) . (26)
If i = 1 i=1 i = 1 and j > 0 j>0 j > 0 , let r = ν p ( j ) r=\nu_p(j) r = ν p ( j ) . We have that ν p ( a − 1 ) = r + 1 \nu_p(a-1)=r+1 ν p ( a − 1 ) = r + 1 and either r + 1 ≤ ν p ( b ) r+1\le\nu_p(b) r + 1 ≤ ν p ( b ) or r ≥ ν p ( b ) r \geq\nu_p(b) r ≥ ν p ( b ) . In the first case we have
∑ b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ j = 1 p e − 1 − 1 ∑ k = 0 e φ ( p k ) ord p k ( j p + 1 ) = ∑ r = 0 e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + ∑ k = 1 r + 1 ( p − 1 ) p k − 1 + ∑ k = r + 2 e ( p − 1 ) p 2 k − r − 2 ) = ∑ r = 0 e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( p r + 1 + p 2 e − r p + 1 ) = ( p − 1 ) ∑ r = 0 e − 2 ( p 2 e − r − 2 + p 4 e − 3 r − 3 p + 1 ) = 1 p + 1 ( p 2 e − 1 − p e + p 4 e − p e + 3 p 2 + p + 1 ) (27) \begin{aligned}
\sum_{\substack{b\in\mathbb{Z}_{p^e}\\ \nu_p(b)>\nu_p(j)}}\sum_{j=1}^{p^{e-1}-1}\sum_{k=0}^{e}\varphi(p^k)\operatorname{ord}_{p^k}(jp+1) \\
&=\sum_{r=0}^{e-2}p^{2e-2r-3}(p-1)\left(1+\sum_{k=1}^{r+1}(p-1)p^{k-1}+\sum_{k=r+2}^{e}(p-1)p^{2k-r-2}\right) \\
&=\sum_{r=0}^{e-2}p^{2e-2r-3}(p-1)\left(\frac{p^{r+1}+p^{2e-r}}{p+1}\right) \\
&=(p-1)\sum_{r=0}^{e-2}\left(\frac{p^{2e-r-2}+p^{4e-3r-3}}{p+1}\right) \\
&=\frac{1}{p+1}\left(p^{2e-1}-p^e+\frac{p^{4e}-p^{e+3}}{p^2+p+1}\right) \tag*{(27)}
\end{aligned} b ∈ Z p e ν p ( b ) > ν p ( j ) ∑ j = 1 ∑ p e − 1 − 1 k = 0 ∑ e φ ( p k ) ord p k ( j p + 1 ) = r = 0 ∑ e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( 1 + k = 1 ∑ r + 1 ( p − 1 ) p k − 1 + k = r + 2 ∑ e ( p − 1 ) p 2 k − r − 2 ) = r = 0 ∑ e − 2 p 2 e − 2 r − 3 ( p − 1 ) ( p + 1 p r + 1 + p 2 e − r ) = ( p − 1 ) r = 0 ∑ e − 2 ( p + 1 p 2 e − r − 2 + p 4 e − 3 r − 3 ) = p + 1 1 ( p 2 e − 1 − p e + p 2 + p + 1 p 4 e − p e + 3 ) (27)
In the second case, let t = ν p ( b ) t=\nu_p(b) t = ν p ( b ) . We have that
∑ j = 1 p e − 1 − 1 ∑ b ∈ Z p e ν p ( b ) ≤ ν p ( j ) p 2 e − ν p ( b ) = ∑ r = 0 e − 2 ( p − 1 ) p 2 e − r − 2 ∑ t = 0 r ( p − 1 ) p e − t − 1 p 2 e − t = ( p − 1 ) 2 ∑ r = 0 e − 2 ∑ t = 0 r p 4 e − r − 2 t − 3 = p 4 e − p 3 e + 1 p + 1 − p 4 e − p e + 3 ( p + 1 ) ( p 2 + p + 1 ) . (28) \begin{aligned}
\sum_{j=1}^{p^{e-1}-1}\sum_{\substack{b\in\mathbb{Z}_{p^e}\\ \nu_p(b)\leq\nu_p(j)}}p^{2e-\nu_p(b)}
=\sum_{r=0}^{e-2}(p-1)p^{2e-r-2}\sum_{t=0}^{r}(p-1)p^{e-t-1}p^{2e-t} \\
&=(p-1)^2\sum_{r=0}^{e-2}\sum_{t=0}^{r}p^{4e-r-2t-3} \\
&=\frac{p^{4e}-p^{3e+1}}{p+1}-\frac{p^{4e}-p^{e+3}}{(p+1)(p^2+p+1)}. \tag*{(28)}
\end{aligned} j = 1 ∑ p e − 1 − 1 b ∈ Z p e ν p ( b ) ≤ ν p ( j ) ∑ p 2 e − ν p ( b ) = r = 0 ∑ e − 2 ( p − 1 ) p 2 e − r − 2 t = 0 ∑ r ( p − 1 ) p e − t − 1 p 2 e − t = ( p − 1 ) 2 r = 0 ∑ e − 2 t = 0 ∑ r p 4 e − r − 2 t − 3 = p + 1 p 4 e − p 3 e + 1 − ( p + 1 ) ( p 2 + p + 1 ) p 4 e − p e + 3 . (28)
If i = 1 i=1 i = 1 and j = 0 j=0 j = 0 , when b = 0 b=0 b = 0 we have the identity map and
∑ ℓ ∈ L ( f , Z p e ) ℓ 2 N ℓ ( f , Z p e ) = p e . \sum_{\ell\in\mathcal{L}(f,\mathbb{Z}_{p^e})}\ell^2\mathcal{N}_{\ell}(f,\mathbb{Z}_{p^e})=p^e. ℓ ∈ L ( f , Z p e ) ∑ ℓ 2 N ℓ ( f , Z p e ) = p e .
Adding the other values of b ∈ Z p e ∖ { 0 } b\in\mathbb{Z}_{p^e}\setminus\{0\} b ∈ Z p e ∖ { 0 } we have
p e + ∑ b ∈ Z p e ∖ { 0 } p 2 e − ν p ( b ) = p e + ∑ t = 0 e − 1 ( p − 1 ) p e − t − 1 p 2 e − t = p 3 e + 1 + p e p + 1 . (29) p^e+\sum_{b\in\mathbb{Z}_{p^e}\setminus\{0\}}p^{2e-\nu_p(b)}
=p^e+\sum_{t=0}^{e-1}(p-1)p^{e-t-1}p^{2e-t}
=\frac{p^{3e+1}+p^e}{p+1}. \tag*{(29)} p e + b ∈ Z p e ∖ { 0 } ∑ p 2 e − ν p ( b ) = p e + t = 0 ∑ e − 1 ( p − 1 ) p e − t − 1 p 2 e − t = p + 1 p 3 e + 1 + p e . (29)
Adding (6.25), (6.26), (6.27) and (6.28), the result follows.
Theorem 6.8. Let p p p be an odd prime and e e e a positive integer. The expectation for cycle length of an element x ∈ Z p e x \in\mathbb{Z}_{p^e} x ∈ Z p e in the functional graph of a map f ∈ AP ( Z p e ) f \in\operatorname{AP}(\mathbb{Z}_{p^e}) f ∈ AP ( Z p e ) , both selected uniformly at random, is
E [ ℓ x ( f , Z p e ) ] = p ( p + 1 + G ) ( p − 1 ) ( p + 1 ) 2 p e + e G ( p + 1 ) p e + p 3 − 2 p − 1 − p G ( p − 1 ) ( p + 1 ) 2 p e \mathbb{E}[\ell_x(f,\mathbb{Z}_{p^e})] = \frac{p(p+1+G)}{(p-1)(p+1)^2}p^e + \frac{eG}{(p+1)p^e} + \frac{p^3-2p-1-pG}{(p-1)(p+1)^2p^e} E [ ℓ x ( f , Z p e )] = ( p − 1 ) ( p + 1 ) 2 p ( p + 1 + G ) p e + ( p + 1 ) p e e G + ( p − 1 ) ( p + 1 ) 2 p e p 3 − 2 p − 1 − pG Proof. This result follows by dividing the total number of cycles from Theorem 6.7 by p e ⋅ ∣ AP ( Z p e ) ∣ = p 3 e − 1 ( p − 1 ) p^e \cdot|\operatorname{AP}(\mathbb{Z}_{p^e})| = p^{3e-1}(p-1) p e ⋅ ∣ AP ( Z p e ) ∣ = p 3 e − 1 ( p − 1 ) .
Remark 6.1. Lemma 5.2 determines the functional graph of an affine map g g g over Z n \mathbb{Z}_n Z n , for n n n composite, as the product of the functional graph of g g g over Z p i e i \mathbb{Z}_{p_i^{e_i}} Z p i e i , for every p i e i p_i^{e_i} p i e i in the prime decomposition of n n n . However, from Lemma 5.1, we have that the total number of cycles depends on the gcds of each component’s cycle length. Therefore, a closed formula for the total number of cycles generated by all affine maps over Z n \mathbb{Z}_n Z n would rely on the sum of the gcds over all combinations of cycle lengths of each component, making it substantially more complex.
A comparison with random permutations
Let σ \sigma σ be a permutation of the set of n n n integers [ 1 , n ] [1,n] [ 1 , n ] and x ∈ [ 1 , n ] x \in[1,n] x ∈ [ 1 , n ] , both selected uniformly at random. Let N ( σ , n ) \mathcal{N}(\sigma,n) N ( σ , n ) be the number of cycles of σ \sigma σ and ℓ x ( σ , n ) \ell_x(\sigma,n) ℓ x ( σ , n ) be the length of the cycle that contains x x x in σ \sigma σ . A classical result from random permutation theory is the expectation for those values (see [19 Chapter 1.3] ), which is given by
E [ N ( σ , n ) ] = H n = ∑ k = 1 n 1 k and E [ ℓ x ( σ , n ) ] = n + 1 2 . \mathbb{E}[\mathcal{N}(\sigma,n)] = H_n = \sum_{k=1}^{n} \frac{1}{k}
\quad\text{and}\quad
\mathbb{E}[\ell_x(\sigma,n)] = \frac{n+1}{2}. E [ N ( σ , n )] = H n = k = 1 ∑ n k 1 and E [ ℓ x ( σ , n )] = 2 n + 1 .
We first observe the ratio between the expectation for affine permutations over Z p e \mathbb{Z}_{p^e} Z p e and random permutations. Let
R N AP ( p e ) = E [ N ( g , Z p e ) ] E [ N ( σ , p e ) ] and R ℓ AP ( p e ) = E [ ℓ t ( g , Z p e ) ] E [ ℓ x ( σ , p e ) ] . R_{\mathcal{N}}^{\operatorname{AP}}(p^e) = \frac{\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_{p^e})]}{\mathbb{E}[\mathcal{N}(\sigma,p^e)]}
\quad\text{and}\quad
R_{\ell}^{\operatorname{AP}}(p^e) = \frac{\mathbb{E}[\ell_t(g,\mathbb{Z}_{p^e})]}{\mathbb{E}[\ell_x(\sigma,p^e)]}. R N AP ( p e ) = E [ N ( σ , p e )] E [ N ( g , Z p e )] and R ℓ AP ( p e ) = E [ ℓ x ( σ , p e )] E [ ℓ t ( g , Z p e )] .
Using the results of § 6 , we first investigate their asymptotic behavior when e e e increases and p p p is fixed.
Theorem 7.1. Let p p p be a fixed prime. As e e e tends to infinity, the ratios R N AP ( p e ) R_{\mathcal{N}}^{\operatorname{AP}}(p^e) R N AP ( p e ) and R ℓ AP ( p e ) R_{\ell}^{\operatorname{AP}}(p^e) R ℓ AP ( p e ) satisfy
R N AP ( 2 e ) = e 8 log 2 + O ( 1 ) , and R ℓ AP ( 2 e ) = 8 9 + O ( 2 − e ) , R_{\mathcal{N}}^{\operatorname{AP}}(2^e) = \frac{e}{8\log2} + O(1), \quad\text{and}\quad R_{\ell}^{\operatorname{AP}}(2^e) = \frac{8}{9} + O(2^{-e}), R N AP ( 2 e ) = 8 log 2 e + O ( 1 ) , and R ℓ AP ( 2 e ) = 9 8 + O ( 2 − e ) ,
when p = 2 p=2 p = 2 , and
R N A P ( p e ) = ( p − 1 ) F 2 p log p e + O ( 1 ) , and R ℓ A P ( p e ) = 2 p ( p + 1 + G ) ( p − 1 ) ( p + 1 ) 2 + O ( e p − e ) , R_N^{AP}(p^e)=\frac{(p-1)F}{2p\log p}e+O(1),\qquad\text{and}\qquad R_\ell^{AP}(p^e)=\frac{2p(p+1+G)}{(p-1)(p+1)^2}+O(ep^{-e}), R N A P ( p e ) = 2 p log p ( p − 1 ) F e + O ( 1 ) , and R ℓ A P ( p e ) = ( p − 1 ) ( p + 1 ) 2 2 p ( p + 1 + G ) + O ( e p − e ) ,
when p p p is odd, where F = ∑ r ∣ p − 1 r > 1 φ ( r ) r F=\sum_{\substack{r\mid p-1\\r>1}}\frac{\varphi(r)}{r} F = ∑ r ∣ p − 1 r > 1 r φ ( r ) and G = ∑ r ∣ p − 1 r > 1 r φ ( r ) G=\sum_{\substack{r\mid p-1\\r>1}}r\varphi(r) G = ∑ r ∣ p − 1 r > 1 r φ ( r ) and the implied constants depend only on p p p .
Proof. The result follows directly from the asymptotic expansion of the harmonic numbers and Theorems 6.2 , 6.4 , 6.6 and 6.8 .
In particular, the ratio R N A P ( p e ) R_N^{AP}(p^e) R N A P ( p e ) grows linearly with e e e , while R ℓ A P ( p e ) R_\ell^{AP}(p^e) R ℓ A P ( p e ) tends to a constant determined by p p p .
The analysis when p p p grows depends heavily on the prime factorization of p − 1 p-1 p − 1 and cannot be obtained as simply in general. We provide an asymptotic result for safe primes . A prime number p p p is a safe prime if it can be written as p = 2 m + 1 p=2m+1 p = 2 m + 1 , for a prime m m m . Although their infinitude remains an open problem, numerical evidence and the Hardy–Littlewood conjectures point towards the existence of infinitely many safe primes.
Theorem 7.2. Let e e e be a fixed positive integer. For every safe prime p = 2 r + 1 p=2r+1 p = 2 r + 1 , where r r r is an odd prime, we have
R N A P ( p e ) = 1 + e ( e + 1 ) e log p + O ( ( log p ) − 2 ) and R ℓ A P ( p e ) = 3 2 + O ( p − 1 ) , R_N^{AP}(p^e)=\frac{1+e(e+1)}{e\log p}+O\left((\log p)^{-2}\right)\qquad\text{and}\qquad R_\ell^{AP}(p^e)=\frac{3}{2}+O(p^{-1}), R N A P ( p e ) = e log p 1 + e ( e + 1 ) + O ( ( log p ) − 2 ) and R ℓ A P ( p e ) = 2 3 + O ( p − 1 ) , as p p p increases through safe primes, where the implied constants depend on e e e .
Proof. We observe that if p = 2 m + 1 p=2m+1 p = 2 m + 1 , for some odd prime m m m , then
F = ∑ r ∣ p − 1 r ≠ 1 φ ( r ) r = 2 − 3 2 m = 2 − 3 p − 1 . F=\sum_{\substack{r\mid p-1\\r\ne1}}\frac{\varphi(r)}{r}=2-\frac{3}{2m}=2-\frac{3}{p-1}. F = r ∣ p − 1 r = 1 ∑ r φ ( r ) = 2 − 2 m 3 = 2 − p − 1 3 . and
G = ∑ r ∣ p − 1 r ≠ 1 r φ ( r ) = 3 m 2 − 3 m + 2 = 3 p 2 − 12 p + 17 4 . G=\sum_{\substack{r\mid p-1\\r\ne1}}r\varphi(r)=3m^2-3m+2=\frac{3p^2-12p+17}{4}. G = r ∣ p − 1 r = 1 ∑ r φ ( r ) = 3 m 2 − 3 m + 2 = 4 3 p 2 − 12 p + 17 . The result follows from Theorems 6.6 , 6.8 .
Consequently, along any unbounded sequence of safe primes, the ratio between the expected number of cycles of affine permutations and random permutations becomes negligible, while the ratio of the expected length of the cycle containing a random element approaches 3 2 \frac{3}{2} 2 3 .
For generalized cyclotomic permutations, we observe that the coset permutation built in their dynamics contributes exactly with factors equal to the expectations for random permutations in the expected number of cycles and the expected cycle length of a random point. Therefore, the ratio between those two properties for GCPs and random permutations is given by
R N G C P ( d , s ) = H d H d s E [ N ( g , Z s ) ] and R ℓ G C P ( d , s ) = d + 1 d s + 1 E [ ℓ t ( g , Z s ) ] , R_{\mathcal{N}}^{GCP}(d,s)=\frac{H_d}{H_{ds}}\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)] \quad\text{and} \quad R_{\ell}^{GCP}(d,s)=\frac{d+1}{ds+1}\mathbb{E}[\ell_t(g,\mathbb{Z}_s)], R N GC P ( d , s ) = H d s H d E [ N ( g , Z s )] and R ℓ GC P ( d , s ) = d s + 1 d + 1 E [ ℓ t ( g , Z s )] ,
where g g g and t t t are selected uniformly at random from the sets AP ( Z s ) \operatorname{AP}(\mathbb{Z}_s) AP ( Z s ) and Z s \mathbb{Z}_s Z s respectively.
For a fixed s s s , when d d d (and consequently q q q ) tend to infinity, we have that the asymptotic behavior of the ratios is given by the following. We use the classical approximation for the d d d th harmonic number given by H n = log n + γ + O ( n − 1 ) H_n=\log n+\gamma+O(n^{-1}) H n = log n + γ + O ( n − 1 ) , where γ \gamma γ is the Euler-Mascheroni constant.
Theorem 7.3. Let s s s be a fixed positive integer. If d d d tends to infinity through an unbounded sequence for which q = d s + 1 q=ds+1 q = d s + 1 is a prime power, then the asymptotic behavior of R N G C P ( d , s ) R_{\mathcal{N}}^{GCP}(d,s) R N GC P ( d , s ) and R ℓ G C P ( d , s ) R_{\ell}^{GCP}(d,s) R ℓ GC P ( d , s ) are given by
lim d → ∞ R N G C P ( d , s ) = E [ N ( g , Z s ) ] and lim d → ∞ R ℓ G C P ( d , s ) = 1 s E [ ℓ t ( g , Z s ) ] . \lim_{d\to\infty}R_{\mathcal{N}}^{GCP}(d,s)=\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)] \quad\text{and} \quad\lim_{d\to\infty}R_{\ell}^{GCP}(d,s)=\frac{1}{s}\mathbb{E}[\ell_t(g,\mathbb{Z}_s)]. d → ∞ lim R N GC P ( d , s ) = E [ N ( g , Z s )] and d → ∞ lim R ℓ GC P ( d , s ) = s 1 E [ ℓ t ( g , Z s )] .
Proof. From Theorem 4.1 we have that
lim d → ∞ R N G C P ( d , s ) = lim d → ∞ log d + γ + O ( d − 1 ) log d + log s + γ + O ( d − 1 ) E [ N ( g , Z s ) ] = E [ N ( g , Z s ) ] . \lim_{d\to\infty}R_{\mathcal{N}}^{GCP}(d,s)=\lim_{d\to\infty}\frac{\log d+\gamma+O(d^{-1})}{\log d+\log s+\gamma+O(d^{-1})}\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)]=\mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)]. d → ∞ lim R N GC P ( d , s ) = d → ∞ lim log d + log s + γ + O ( d − 1 ) log d + γ + O ( d − 1 ) E [ N ( g , Z s )] = E [ N ( g , Z s )] .
and
lim d → ∞ R ℓ G C P ( d , s ) = lim d → ∞ d + 1 d s + 1 E [ ℓ t ( g , Z s ) ] = 1 s E [ ℓ t ( g , Z s ) ] . \lim_{d\to\infty}R_{\ell}^{GCP}(d,s)=\lim_{d\to\infty}\frac{d+1}{ds+1}\mathbb{E}[\ell_t(g,\mathbb{Z}_s)]=\frac{1}{s}\mathbb{E}[\ell_t(g,\mathbb{Z}_s)]. d → ∞ lim R ℓ GC P ( d , s ) = d → ∞ lim d s + 1 d + 1 E [ ℓ t ( g , Z s )] = s 1 E [ ℓ t ( g , Z s )] .
□ \square □
Since E [ N ( g , Z s ) ] > 1 \mathbb{E}[\mathcal{N}(g,\mathbb{Z}_s)]>1 E [ N ( g , Z s )] > 1 if s > 1 s>1 s > 1 , we have that generalized cyclotomic permutations have asymptotically more cycles, on average, than random permutations. Increasing the index does not eliminate the arithmetic influence when s s s is fixed and even as d d d tends to infinity, the ratios of the expectations do not converge to 1 in general.
We now provide the asymptotic behavior when s = p e s=p^e s = p e using the results from § 6 .
Theorem 7.4. Let d d d be a fixed positive integer and p p p a prime. Along any unbounded sequence of positive integers e e e for which q = d p e + 1 q = dp^{e}+1 q = d p e + 1 is a prime power, the asymptotic behavior of R N G C P ( d , p e ) R^{\mathrm{GCP}}_{N}(d,p^{e}) R N GCP ( d , p e ) and R ℓ G C P ( d , p e ) R^{\mathrm{GCP}}_{\ell}(d,p^{e}) R ℓ GCP ( d , p e ) are given by
R N G C P ( d , 2 e ) ∼ H d 8 log 2 e and R ℓ G C P ( d , 2 e ) ∼ 4 ( d + 1 ) 9 d R^{\mathrm{GCP}}_{N}(d,2^{e}) \sim\frac{H_d}{8\log2}e \quad\text{and} \quad R^{\mathrm{GCP}}_{\ell}(d,2^{e}) \sim\frac{4(d+1)}{9d} R N GCP ( d , 2 e ) ∼ 8 log 2 H d e and R ℓ GCP ( d , 2 e ) ∼ 9 d 4 ( d + 1 ) when p = 2 p=2 p = 2 and
R N G C P ( d , p e ) ∼ H d ( p − 1 ) F 2 p log p e and R ℓ G C P ( d , p e ) ∼ d + 1 d p ( p + 1 + G ) ( p − 1 ) ( p + 1 ) 2 R^{\mathrm{GCP}}_{N}(d,p^{e}) \sim\frac{H_d(p-1)F}{2p\log p}e \quad\text{and} \quad R^{\mathrm{GCP}}_{\ell}(d,p^{e}) \sim\frac{d+1}{d}\frac{p(p+1+G)}{(p-1)(p+1)^2} R N GCP ( d , p e ) ∼ 2 p log p H d ( p − 1 ) F e and R ℓ GCP ( d , p e ) ∼ d d + 1 ( p − 1 ) ( p + 1 ) 2 p ( p + 1 + G ) when p p p is odd, where F = ∑ r ∣ p − 1 r ≠ 1 φ ( r ) r F = \sum_{\substack{r \mid p-1 \\ r \ne1}} \frac{\varphi(r)}{r} F = ∑ r ∣ p − 1 r = 1 r φ ( r ) , G = ∑ r ∣ p − 1 r ≠ 1 r φ ( r ) G = \sum_{\substack{r \mid p-1 \\ r \ne1}} r\varphi(r) G = ∑ r ∣ p − 1 r = 1 r φ ( r ) and H d H_d H d is the d d d th harmonic number.
Proof. We have that E [ N ( σ ) ] = e log p + log d + γ + O ( p − e ) \mathbb{E}[\mathcal{N}(\sigma)] = e\log p+\log d+\gamma+O(p^{-e}) E [ N ( σ )] = e log p + log d + γ + O ( p − e ) . Thus, the case p = 2 p=2 p = 2 follows directly from Theorems 6.2, 6.4 and 4.1. The case p p p odd follows from Theorems 6.6, 6.8 and 4.1.
We observe that the expected number of cycles of GCPs of index q − 1 p e \frac{q-1}{p^{e}} p e q − 1 grows quadratically in e e e whereas in random permutations it only grows linearly. The expected cycle length under a GCP of a random element is asymptotically proportional to a random permutation, with a factor depending on d d d and the divisors of p − 1 p-1 p − 1 .
Conclusion and future research
In this paper, we investigated two statistical properties of the functional graphs of affine permutations over Z p e \mathbb{Z}_{p^{e}} Z p e and generalized cyclotomic permutations over finite fields: the expected number of cycles and the expected length of the cycle containing a randomly selected element. We established exact expressions for these expectations for generalized cyclotomic permutations of index d d d in terms of the expectations for the underlying affine maps. In particular, we showed that the expected number of cycles is the product of the corresponding expectation for affine permutations and the d d d th harmonic number, while the expected length of the cycle containing a random element is multiplied by d + 1 2 \frac{d+1}{2} 2 d + 1 .
We analyzed the ratio between these statistical properties and those of uniformly random permutations on sets of the same cardinality. For affine permutations over Z p e \mathbb{Z}_{p^{e}} Z p e , the asymptotic results showed that the ratio of the expected number of cycles grows linearly with e e e but tends to zero when p p p grows through a sequence of safe primes. On the other hand, the ratio of the expected lengths of the cycles containing uniformly selected elements tends to a constant that depends on p p p , as e e e grows and approaches 3 2 \frac{3}{2} 2 3 when p p p grows through a sequence of safe primes.
In generalized cyclotomic permutations, the asymptotic results show that for s s s fixed, as d d d tends to infinity the ratios of the expectations approach constants determined by the corresponding expectations for affine permutations over Z s \mathbb{Z}_s Z s . On the other hand, when s = p e s=p^e s = p e with p p p and d d d fixed, the expected number of cycles grows quadratically with e e e , whereas the corresponding expectation for uniformly random permutations grows linearly. Their expected cycle lengths for a random element remain asymptotically proportional, with a factor depending on p p p and d d d .
An interesting direction for future research is the extension of the explicit expectation formulas to affine permutations over Z n \mathbb{Z}_n Z n for arbitrary positive integers n n n . Although their functional graphs can be determined from the prime decomposition of n n n , the interaction between cycle lengths from different components makes the calculation of these expectations more involved. Another possible direction is the study of higher moments and the distribution of cycle lengths, which could provide a more detailed understanding of how the functional graphs of these structured permutation families differ from those of uniformly random permutations.
Acknowledgments
The author was funded by the Austrian Science Fund [10.55776/PAT4719224].