🔢 mathematics

Periodicity and Dynamical Systems of Dickson Polynomials in Finite Fields

This paper investigates the periodicity and dynamical systems of Dickson polynomials over finite fields by relating their iteration to power maps on $\mathbb{F}_{q^2}^\times$ , thereby determining exact periods, characterizing their composition groups in permutation and non-permutation cases, and establishing new identities and symmetry properties.

Original authors: Wayne Peng, Yen-Ju Chen

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wayne Peng, Yen-Ju Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a giant, magical factory where you have a special machine that takes a number, does a specific math trick to it, and spits out a new number. In the world of this paper, the "factory" is a finite field (think of it as a clock with a limited number of hours, say 7 hours or 13 hours, where after you hit the max, you wrap back to zero).

The "machines" in this factory are called Dickson Polynomials. They are like complex recipes for transforming numbers. The authors of this paper, Yen-Ju Chen and Wayne Peng, decided to ask a very specific question: What happens if we keep running the same recipe over and over again, but we change the "recipe number" (the index $n$ ) each time?

Here is a breakdown of their findings using simple analogies:

1. The Great Loop (Periodicity)

Imagine you have a set of keys (the numbers in the field) and a set of locks (the polynomial functions). You start turning the keys with Recipe #1, then Recipe #2, then Recipe #3, and so on.

The authors discovered that these recipes don't just keep changing forever. Eventually, the pattern of results starts to repeat itself, like a song on a loop.

The Discovery: They calculated the exact length of this loop.
The Analogy: Think of a clock. If you have a 12-hour clock, the hands repeat every 12 hours. The authors found that for their specific "Dickson machines," the loop length is usually related to the square of the number of hours on the clock (specifically $q^2 - 1$ ).
The Twist: Sometimes, if the "recipe ingredient" ( $\alpha$ ) is a special kind of number (a "square"), the loop is exactly half as long. It's like a clock that only ticks every other hour.

2. The Secret Decoder Ring (The Connection to Power Maps)

The paper reveals a secret link between these complex Dickson recipes and a much simpler machine: the Power Map.

The Analogy: Imagine the Power Map is a simple machine that just raises a number to a power (like squaring it or cubing it). The Dickson Polynomial is a fancy, decorated version of this simple machine.
The Connection: The authors show that if you look at the Dickson machine through a special "decoder ring" (a mathematical transformation called $\phi_\alpha$ ), it behaves exactly like the simple Power Map.
Why it matters: This means that even though Dickson polynomials look complicated, their behavior is actually just the behavior of simple powers, just viewed through a funhouse mirror. This allows the authors to predict exactly how these machines will behave when you combine them (compose them).

3. The Group of Friends (Algebraic Structure)

When the recipes are "permutations" (meaning every input gives a unique output, like a perfect shuffle of a deck of cards), the authors found that these Dickson machines form a Group.

The Analogy: Think of a group of friends who can swap seats in a circle. If you swap two people, then swap two others, it's the same as doing one big swap. The authors mapped out exactly how these "swaps" (the Dickson polynomials) relate to each other. They proved that the "friends" (the polynomials) follow strict rules of friendship (algebraic structure) that can be described using simple number theory.

4. The Magic Mirror (Symmetry)

One of the most beautiful parts of the paper is the discovery of a Symmetry Property.

The Analogy: Imagine you write a long poem on a piece of paper. If you rotate the paper 180 degrees (upside down), the poem looks different, but the authors found a specific mathematical "mirror" where the poem written upside down is actually the same as a different poem written right-side up, just with the letters slightly rearranged.
The Finding: They proved that if you take a Dickson polynomial, flip it inside out (replace $x$ with $1/x$ ), and rotate it, it looks exactly like another Dickson polynomial with a different ingredient. This is like finding that two different recipes actually produce the exact same flavor profile when you swap the main ingredients in a specific way.

5. The Detective Work (Algorithms)

Finally, the authors wrote a set of instructions (an algorithm) for a detective.

The Scenario: Imagine someone hands you a finished cake (a polynomial) and asks, "Did you bake this using our special Dickson recipe? If so, what was the secret ingredient ( $\alpha$ )?"
The Solution: Instead of tasting every possible ingredient (which would take forever), the detective looks at the frosting pattern (the coefficients). Because of the symmetry and structure the authors discovered, the detective can mathematically deduce the secret ingredient just by looking at a few specific spots on the cake. This makes identifying these polynomials much faster and smarter.

Summary

In short, Chen and Peng took a complex mathematical object (Dickson polynomials) and showed that:

They repeat in predictable loops.
They are secretly just simple power functions in disguise.
They follow strict group rules when they are "perfect shuffles."
They have a hidden mirror symmetry that links different versions of themselves.
We can use these patterns to quickly identify them in the wild.

They didn't invent a new drug or a new engine; they simply mapped out the hidden rules of a mathematical game, showing us that even in a finite, limited world, there is a beautiful, repeating order.

Technical Summary: Periodicity and Dynamical Systems of Dickson Polynomials in Finite Fields

Problem Statement
This paper investigates the dynamical properties of Dickson polynomials of the first kind, denoted $D_n(x, \alpha)$ , over finite fields $\mathbb{F}_q$ . While the functional graphs of fixed polynomial maps (such as $x \mapsto x^n$ or Chebyshev polynomials) have been extensively studied, this work shifts focus to the sequential behavior of the Dickson polynomial family as the index $n$ varies. Specifically, the authors analyze the sequence of polynomial functions $[D_n(x, \alpha) \pmod{x^q - x}]_{n \ge 1}$ within the ring $\mathbb{F}_q[x]/(x^q - x)$ . The primary objectives are to determine the exact period of this sequence, describe the algebraic structure of the group generated by these polynomials under composition (particularly in the permutation case), and derive new structural identities and symmetries.

Methodology
The authors employ a combination of algebraic number theory, finite field theory, and combinatorial analysis. The core methodology relies on the classical functional equation characterizing Dickson polynomials:
$D_n(\phi_\alpha(u), \alpha) = \phi_\alpha(u^n)$
where $\phi_\alpha(u) = u + \alpha u^{-1}$ . This equation establishes a commutative diagram linking the dynamics of $D_n(x, \alpha)$ on $\mathbb{F}_q$ to the power map $u \mapsto u^n$ on a specific subset $\mathcal{T}_\alpha \subset \mathbb{F}_{q^2}^\times$ (defined as $\{u \in \mathbb{F}_{q^2} \mid u^{q+1} = \alpha \text{ or } u \in \mathbb{F}_q^\times\}$ ).

Key methodological steps include:

Periodicity Analysis: Using the recurrence relation $D_n = x D_{n-1} - \alpha D_{n-2}$ and the functional equation, the authors determine the smallest $n$ such that $D_n(x, \alpha) \equiv x \pmod{x^q - x}$ and $D_{n+1}(x, \alpha) \equiv 2 \pmod{x^q - x}$ .
Group Theoretic Mapping: In the permutation case (where $\gcd(n, q^2-1)=1$ ), the authors construct a group homomorphism from a subgroup of $(\mathbb{Z}/\pi_q(\alpha)\mathbb{Z})^\times$ to the group of Dickson polynomial functions under composition, explicitly characterizing the kernel.
Coefficient Symmetry: The authors utilize generalized versions of Lucas' Theorem and combinatorial identities involving binomial coefficients to prove non-trivial symmetries in the coefficients of $D_n(x, \alpha)$ .
Algorithmic Extraction: An algorithm is proposed to extract the parameter $\alpha$ from a given polynomial by analyzing the ratios of its coefficients, leveraging the derived symmetry properties.

Key Contributions and Results

Exact Periodicity (Theorem 1.1): The paper establishes the exact period of the sequence $[D_n(x, \alpha) \pmod{x^q - x}]_{n \ge 1}$ .
- If $q$ is odd and $\alpha$ is a square in $\mathbb{F}_q$ , the period is $\frac{q^2-1}{2}$ .
- Otherwise, the period is $q^2 - 1$ .
  This result is derived by analyzing the order of elements in $\mathcal{T}_\alpha$ and proving that $D_n(x, \alpha) \equiv 2$ implies specific divisibility conditions on $n$ relative to $q-1$ and $q+1$ .
Group Structure of Permutation Dickson Polynomials (Theorem 1.2): For $\alpha \in \mathbb{F}_q^\times$ , the set $\mathcal{D}_\alpha = \{D_{n, \alpha}(x) \pmod{x^q-x} \mid \alpha^n = \alpha, \gcd(n, q^2-1)=1\}$ forms a group under composition. The authors prove that this group is isomorphic to a quotient of a subgroup of $(\mathbb{Z}/\pi_q(\alpha)\mathbb{Z})^\times$ . Specifically:
- If $\alpha = 1$ , the group is isomorphic to $(\mathbb{Z}/\pi_q(1)\mathbb{Z})^\times / H_1$ , where $H_1 \cong \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z}$ .
- If $\alpha \neq 1$ , the group is isomorphic to $U_\alpha / H_2$ , where $H_2 \cong \mathbb{Z}/2\mathbb{Z}$ .
  This provides an explicit description of the composition dynamics when the index $n$ is coprime to $q^2-1$ .
Coefficient Symmetry Identities (Theorem 1.3): The authors derive new identities reflecting a "rotation" symmetry in the coefficients of Dickson polynomials.
- For odd $q$ : $x^{q^2+1}(D_{q^2-1}(x^{-1}, \alpha) - 2) = (-4\alpha)^{-1}(D_{q^2-1}(x, (16\alpha)^{-1}) - 2)$ .
- If $\alpha$ is a square: $x^{\frac{q^2+1}{2}} D_{\frac{q^2-1}{2}}(x^{-1}, \alpha) = 2 D_{\frac{q^2+1}{2}}(x, (16\alpha)^{-1})$ .
  These identities are proven using combinatorial manipulations of the explicit coefficient formulas and generalized Lucas' Theorem.
Dynamical Structure and Partial Results: The paper defines the dynamical structure $(\ell, k)$ (tail length and period) for the sequence. While the tail length is fully determined, the exact period for the case where $\gcd(n, q^2-1) \neq 1$ is only partially characterized. The authors note that when the period $k$ of the underlying power map is even, the period of the Dickson sequence may be either $k$ or $k/2$ , leaving the precise criterion for this distinction as an open question.
Algorithmic Application: An algorithm is presented to identify if a given polynomial $f(x)$ is a Dickson polynomial $D_n(x, \alpha)$ and to recover $\alpha$ . This method avoids brute-force search by using the greatest common divisor of the indices of non-zero coefficients to determine $\alpha$ directly, reducing the complexity of the search space.

Significance
The paper claims significance in providing a unified algebraic framework for understanding the iteration of Dickson polynomials, extending the known group-theoretic mechanisms of Chebyshev polynomials and power maps to the broader Dickson family. By determining the exact periodicity and the group structure of the composition of these polynomials, the work offers a deeper theoretical understanding of their functional graphs. The derived symmetry identities and the coefficient-extraction algorithm provide new tools for analyzing these polynomials, potentially aiding in the study of their applications in cryptography and pseudorandom number generation, though the paper focuses primarily on the theoretical algebraic structure rather than specific applied implementations. The results bridge the gap between the dynamics of fixed maps and the sequential behavior of polynomial families.