Why do polynomials $x^n + 1 \bmod N$ close a shorter cycle when $n$ is even than when $n$ is odd?

Question

Polynomials $f(x) \bmod N$, where $f(x)$ is of integer coefficients and $N$ is a composite of two distinct primes $p, q$, form a cycle --- usually leaving a tail because the cycle tends to close not on the first element of the sequence. The cycle size is called the period of the polynomial.

Definition (cycle). A sequence generated by a polynomial $f(x) \bmod N$ has a cycle if there are indices $i, j$ with $i \neq j$ satisfying $$f(x_i) \bmod N = f(x_j) \bmod N.$$ Its cycle length is $j - i$. End of definition.

Trying out a few different polynomials in the form $x^n + 1 \bmod N$, I noticed even $n$ yields cycles with a smaller period than with odd $n$. I computed the average cycle length from the sample of all $C(50,2)$ composites $N$ formed by taking combinations of the smallest $50$ primes.

In the table below, the second column shows the cycle length and the third column shows the tail length of the polynomial --- that is, tail length is defined as the number of elements before the cycle begins.

polynomial                   cycle length          tail length
x^[2] + 1 mod N                     33.31                 7.38
x^[3] + 1 mod N                    380.07                 3.40
x^[4] + 1 mod N                     13.43                 6.57
x^[5] + 1 mod N                   1242.46                 1.53
x^[6] + 1 mod N                     16.39                 5.85
x^[7] + 1 mod N                   1971.81                 1.07
x^[8] + 1 mod N                     11.47                 7.65
x^[9] + 1 mod N                    580.61                 2.58
x^[10] + 1 mod N                    11.13                 6.45
x^[11] + 1 mod N                  1593.10                 0.30
x^[12] + 1 mod N                    13.75                 4.32
x^[13] + 1 mod N                  1620.03                 0.19
x^[14] + 1 mod N                    26.46                 6.29
x^[15] + 1 mod N                   298.20                 2.68
x^[16] + 1 mod N                     9.67                 8.50
x^[17] + 1 mod N                  2643.80                 0.24
x^[18] + 1 mod N                    11.89                 6.03
x^[19] + 1 mod N                  1331.40                 0.06
x^[20] + 1 mod N                     9.25                 5.90
x^[21] + 1 mod N                   525.22                 2.65
x^[22] + 1 mod N                    12.49                 8.18
x^[23] + 1 mod N                  2005.32                 0.08
x^[24] + 1 mod N                    12.28                 4.77
x^[25] + 1 mod N                   913.86                 0.88
x^[26] + 1 mod N                    16.60                 7.54
x^[27] + 1 mod N                   488.15                 3.35
x^[28] + 1 mod N                    13.78                 7.16
x^[29] + 1 mod N                  2557.41                 0.01
x^[30] + 1 mod N                    11.59                 4.73
x^[31] + 1 mod N                  2919.89                 0.00
x^[32] + 1 mod N                    12.13                 7.20
x^[33] + 1 mod N                   660.20                 2.73
x^[34] + 1 mod N                    21.58                 8.06
x^[35] + 1 mod N                   981.59                 1.82
x^[36] + 1 mod N                     9.63                 6.00
x^[37] + 1 mod N                  1438.84                 0.05
x^[38] + 1 mod N                    12.43                 7.80
x^[39] + 1 mod N                   547.79                 2.70

We can also see in this table that if the power is prime, the cycle length is even larger than when it's merely an odd power.

To see this hierarchy of periods --- even powers smallest, odd powers, prime powers greatest ---, I computed the following three experiments. In all there experiments, the composite $N$ is all combinations of two primes in the set of all 50 smallest primes.

The first experiment computes the average period of polynomials $x^n + 1 \bmod N$ where $n$ is even in $\{2, ..., 12\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [2, 4, 6, 8, 10, 12])
{'poly': 'x^[2, 4, 6, 8, 10, 12] + 1 mod N',
 'avg_tail': 6.369387755102041,
 'avg_cycle': 16.580884353741496}

In the second experiment, $n$ is a non-prime odd power in $\{9,15,21,25,27,33\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [9,15,21,25,27,33])
{'poly': 'x^[9, 15, 21, 25, 27, 33] + 1 mod N',
 'avg_tail': 2.4783333333333335,
 'avg_cycle': 577.7066326530612}

In the third experiment, $n$ is a prime power in $\{3, 5, 7, 11, 13, 17\}$.

>>> average_poly_class(primes()[0:50], [0,1,2,3], [3, 5, 7, 11, 13, 17])
{'poly': 'x^[3, 5, 7, 11, 13, 17] + 1 mod N',
 'avg_tail': 1.1217006802721088,
 'avg_cycle': 1575.211768707483}

Can you explain this difference between even, odd, prime powers? Thank you.

Answer 1

If $gcd(e,\lambda(N))=1,$ the sequence is purely periodic. Otherwise it may have an initial segment followed by a cycle, as you observe. Its maximal period divides the Carmichael function $\lambda(N)$ which is $\textrm{lcm}(p-1,q-1)$ when $N=pq,$ with $p,q$ prime.

Note that $2$ divides $\lambda(N)$ in this case, and explains the tendency in the period which you noticed. The paper Period of the power generator and small values of the Carmichael function by Friedlander, Pomerance and Shparlinski available here has a detailed discussion.