The dynamics of a function family over quadratic extensions of finite fields

This paper provides a complete description of the functional graph of the function $f(X)=(cX^q+aX)(X^{q}-X)^{n-1}$ over the finite field $\mathbb{F}_{q^2}$ by determining its cycle lengths, counting cycles, and classifying the attached tree structures in terms of arithmetic invariants of $\mathbb{F}_q$.

The Gist

Imagine you have a magical machine that takes a number, does some math to it, and spits out a new number. If you feed that new number back into the machine, you get another number, and so on. This is called a dynamical system.

In this paper, the authors (Hugo Teixeira and Fabio Brochero Martínez) are studying a very specific, slightly complicated machine that works inside a special kind of number world called a finite field. Think of a finite field not as an infinite line of numbers, but as a small, closed room with a fixed number of chairs (let's say $q^2$ chairs). Once you sit in a chair, the machine tells you exactly which chair to move to next.

Because there are only a finite number of chairs, if you keep moving, you eventually have to bump into a chair you've already visited. Once you do, you get stuck in a loop.

The Big Picture: The "City" of Numbers

The authors are mapping out the entire "city" of these numbers to see how the machine moves people around. They want to know:

1. The Loops (Cycles): How many people get stuck in a circle? How big are those circles?
2. The Paths (Pre-cycles): How many people are walking toward a circle before they get stuck in it?
3. The Trees: If you look at the map, the loops are the centers of "towns," and the paths leading to them look like trees hanging upside down. They want to know the shape of these trees.

The machine they are studying is defined by a formula that looks scary:
$$f(X) = (cX^q + aX)(X^q - X)^{n-1}$$
But don't panic! The authors realized this machine has a secret superpower: it behaves like a 2D grid.

The Secret Trick: Unfolding the Grid

The authors realized that the numbers in this special room ($F_{q^2}$) can be thought of as points on a 2D grid made of two axes (like an $x$ and $y$ coordinate).

• The "Even" Case ($n$ is even): The machine acts like a blender that mixes the $x$ and $y$ coordinates in a specific way. It turns the problem into a game of "What happens if I multiply these numbers?"
• The "Odd" Case ($n$ is odd): The machine acts a bit differently, almost like a filter that separates the coordinates.

By treating the numbers as coordinates on a grid, the authors could use simple algebra (like solving for $x$ and $y$) to predict exactly where every single number would go, rather than having to test them one by one.

The Three Main Discoveries

Here is what they found, explained with analogies:

1. The "Zero" Neighborhood

There is always one special point, the number 0.

• The Result: The authors figured out exactly how many numbers flow directly into 0 and how many flow into those numbers.
• The Analogy: Imagine 0 is a giant black hole in the center of the city. The authors calculated exactly how many "drain pipes" lead directly into the black hole and how many smaller pipes feed into those drain pipes. They found that the shape of this neighborhood depends on whether certain numbers in the formula are "perfect powers" (like perfect squares or cubes).

2. The Loops (The Dance Circles)

Most numbers eventually get stuck in a loop.

• The Result: They found a precise formula to count how many loops of every size exist.
  • If the parameters $a$ and $c$ are "friendly" (mathematically speaking), you might get loops of odd lengths.
  • If they are "unfriendly," you might only get loops of even lengths.
• The Analogy: Imagine a dance floor. Some people are dancing in a circle of 3, some in a circle of 5, some in a circle of 10. The authors wrote a rulebook that tells you exactly how many circles of each size will form based on the "music" (the numbers $a, c, n$) playing in the room. They even figured out that if the music is a certain way, the dancers can only form circles of even numbers (like 2, 4, 6), never odd ones.

3. The Hanging Trees (The Commuters)

Before people get stuck in a loop, they walk down a path.

• The Result: They described the exact shape of the "trees" that hang off the loops.
• The Analogy: Imagine the loops are the city centers. The trees are the suburbs. The authors found that the suburbs have a very specific, repeating structure.
  • If you are in a suburb, you might have 1 neighbor, or 3 neighbors, or 7 neighbors, depending on the "rules" of the city.
  • They discovered that these trees have a maximum height. You can't have an infinite line of suburbs; eventually, the road ends, and there are no more people to feed into the system. The height of this tree depends on how many "roots" (special numbers) exist in the field.

Why Does This Matter?

You might ask, "Who cares about a machine that moves numbers around in a small room?"

1. Randomness and Security:
These machines are used to generate pseudorandom numbers. If you want to create a code that is hard to crack (like in online banking or secret messages), you need a sequence of numbers that looks random but is actually generated by a rule.

• If the "loops" are too short, the sequence repeats too quickly, and hackers can guess the pattern.
• If the "trees" are too simple, the sequence is predictable.
• By understanding the exact shape of these loops and trees, cryptographers can design better, safer machines that produce longer, more unpredictable sequences.

2. The Beauty of Patterns:
The authors showed that even though the formula looks messy, the underlying structure is incredibly orderly. It's like looking at a complex snowflake; up close, it's a mess of ice crystals, but step back, and you see a perfect, symmetrical pattern. They proved that the "chaos" of these number machines is actually governed by strict, beautiful arithmetic rules involving greatest common divisors and special number properties.

Summary

In short, this paper is a comprehensive map of a specific type of number machine. The authors didn't just guess where the numbers go; they built a mathematical GPS that tells you:

• How many loops exist.
• How long those loops are.
• How many "commuters" are walking toward those loops.
• Exactly what the shape of the "commuter paths" looks like.

They did this by turning a complex 1D problem into a simpler 2D grid problem, revealing that the behavior of these numbers is dictated by the fundamental "DNA" of the number system itself.

Technical Summary

1. Problem Statement

The paper investigates the dynamical behavior of a specific family of functions defined over the quadratic extension of a finite field, $\mathbb{F}_{q^2}$. The function is given by:
$$f(X) = (cX^q + aX)(X^q - X)^{n-1}$$
where $a, c \in \mathbb{F}_q$, $n \ge 1$, and $q = p^s$ (with $p$ an odd prime).

The primary objective is to provide a complete classification of the functional graph $G(f)$ associated with this map. Specifically, the authors aim to determine:

• The number and lengths of all cycles (periodic points).
• The structure of the pre-periodic components (trees attached to cycles).
• The number of fixed points.
• How these structural properties depend on arithmetic invariants of the field (e.g., greatest common divisors, multiplicative characters).

This work generalizes previous studies on quadratic forms ($n=2$) and maps of the form $x \mapsto ax^2$, extending the analysis to arbitrary exponents $n$ and coefficients $a, c$.

2. Methodology

The authors employ a combination of algebraic geometry, number theory, and combinatorial graph theory. The core methodology involves:

• Vector Space Representation: Since $\mathbb{F}_{q^2}$ is a 2-dimensional vector space over $\mathbb{F}_q$, the authors represent elements as $X = x + y\beta$, where $\{1, \beta\}$ is a basis and $\beta^2 \in \mathbb{F}_q$. This transforms the map $f: \mathbb{F}_{q^2} \to \mathbb{F}_{q^2}$ into a map between vector spaces $\mathbb{F}_q \times \mathbb{F}_q \to \mathbb{F}_q \times \mathbb{F}_q$.
• Case Analysis by Parity of $n$: The dynamics are analyzed separately for even $n$ and odd $n$, as the algebraic simplification of the term $(X^q - X)^{n-1}$ differs significantly in these cases.
• Arithmetic Invariants: The analysis relies heavily on:
  • Multiplicative Characters: Specifically the quadratic character $\chi_2$ and generalized characters $\chi_m$ to determine solvability of equations involving powers.
  • GCD Properties: Using $g(k) = \gcd(k, q-1)$ to count roots of unity and solutions to power equations.
  • Lifting The Exponent (LTE) Lemma: Used in the odd $n$ case to analyze the valuation of iterated exponents.
  • Möbius Inversion: Applied to derive exact counts of cycles of specific lengths from the total number of periodic points.
• Tree Structure Analysis: The pre-periodic components are modeled as trees rooted at periodic points. The height and branching factors of these trees are determined by the existence of $n^k$-th roots of unity in $\mathbb{F}_q$.

3. Key Contributions and Results

A. The Case of Even $n$

When $n$ is even, the map simplifies to a form where the coordinates decouple in a specific way, leading to the map:
$$\langle x, y \rangle \mapsto \langle \delta_1 y^n, \delta_2 x y^{n-1} \rangle$$
where $\delta_1, \delta_2$ depend on $a, c, n$.

• Zero Component: The connected component containing the origin $\langle 0,0 \rangle$ is fully characterized. It consists of a fixed point with a specific tree structure depending on whether $\delta_1$ or $\delta_2$ is zero.
• Cycle Classification:
  • Odd Cycles: Exist if and only if $\chi_2(a^2 - c^2) = -1$. The number of odd cycles of length $2j+1$ is given by an explicit formula involving Möbius inversion and $g(n-1)$.
  • Even Cycles: The lengths are determined by the order of $n^2$ modulo divisors of $q-1$. The authors provide exact formulas for the number of cycles of length $2k$.
• Tree Structure: Nonzero periodic points are roots of trees with height $e+1$, where $e$ is the largest integer such that $g(n^e) < s$ (with $q-1=rs$). The shape of these trees is isomorphic to a recursively defined structure $T_n(e+1)$, determined by the distribution of $n^k$-th roots of unity.

B. The Case of Odd $n$

When $n$ is odd, the map takes the form:
$$\langle x, y \rangle \mapsto (4\beta^2)^{\frac{n-1}{2}} y^{n-1} \langle \delta_1 x, \delta_2 y \rangle$$

• Fixed Points: The number of fixed points $N(1)$ is derived based on the solvability of specific power equations involving $\delta_1$ and $\delta_2$. The result depends on whether $\delta_1 = \delta_2$ and the character values of $\delta_2$.
• Cycle Lengths:
  • The cycle lengths are constrained to be multiples of specific integers $\tau_0$ (for elements with $x=0$) and $\tau = \text{lcm}(\text{ord}(\delta_1/\delta_2), \tau_0)$ (for elements with $x \neq 0$).
  • $\tau_0$ is calculated using the Lifting The Exponent Lemma and the prime factorization of $n-1$ and $q-1$.
• Tree Structure:
  • If $g(n) = 1$, there are no trees attached to nonzero periodic points (only the root exists).
  • If $g(n) > 1$, trees of height $e+1$ exist.
  • A distinct feature of the odd case is that if $\delta_1 = 0$, the preimage size of a node is $q \cdot g(n)$ (due to the freedom of the $x$-coordinate), whereas if $\delta_1 \neq 0$, it is $g(n)$. This leads to a different tree isomorphism class $T'_n(e+1)$.

4. Significance

• Complete Characterization: Unlike many previous studies that provide asymptotic results or partial descriptions, this paper offers a complete, explicit algebraic description of the functional graph for the entire family of functions defined.
• Generalization: It unifies and extends known results for quadratic maps ($n=2$) and monomial maps, providing a framework for analyzing higher-degree polynomial dynamics over finite fields.
• Cryptographic Relevance: Functional graphs are fundamental in cryptography (e.g., pseudorandom number generation, hash functions, and signature schemes like the Blum-Blum-Shub generator). Understanding the cycle structure and pre-period lengths is crucial for assessing the security and period quality of such systems. This work provides the theoretical tools to predict these properties for a broad class of maps.
• Arithmetic Insight: The results highlight a deep connection between the dynamical properties of a map and the arithmetic structure of the underlying finite field (specifically the divisibility of $q-1$ and the existence of specific roots of unity).

5. Conclusion

Teixeira and Brochero Martínez successfully map the dynamics of $f(X) = (cX^q + aX)(X^q - X)^{n-1}$ over $\mathbb{F}_{q^2}$. By leveraging the vector space structure of the field extension and number-theoretic tools, they derive exact formulas for cycle counts, lengths, and tree structures. The work demonstrates that the global dynamics are entirely governed by the arithmetic invariants of $\mathbb{F}_q$, providing a definitive classification for both even and odd exponents $n$.