Periodicity and Dynamical Systems of Dickson Polynomials in Finite Fields
Wayne Peng
Academia Sinica
### Set-up <ul> <li>$q$: a power of prime $p$.</li> <li class="fragment">$\mathbb{F}_q$: a finite field of order $q$.</li> <li class="fragment">$\mathbb{F}_q^\times=\mathbb{F}_q\setminus\{0\}$</li> </ul> <p class="fragment">A polynomial $f\in \mathbb{F}_q[x]$ is called a <em>permutation polynomial</em> if the map $f$ permutes the elements of $\mathbb{F}_q$.</p>
<p> What problems about permutation polynomials are studied? </p> <ul> <li class="fragment"> Existence and classification (when is a polynomial a permutation?) </li> <li class="fragment"> Structure and cycle type (how does it act as a permutation?). </li> <li class="fragment"> Exceptional families (which permute infinitely many fields?). </li> <li class="fragment"> Applications and explicit constructions (geometry, cryptography, dynamics). </li> </ul>
<div class="definition"> <p> For positive integers $n$ and $\alpha \in \mathbb{F}_q$, the Dickson polynomials (of the first kind) over $\mathbb{F}_q$ are given by $$ D_{n}(x,\alpha)=\sum_{i=0}^{\lfloor {\frac{n}{2}}\rfloor}\frac{n}{n-i}\binom{n-i}{i}(-\alpha)^i x^{n-2i}. $$ </p> </div> <p class="fragment"> Dickson polynomials can be generated by the following recursive relation for $n\geq 3$: $$ D_n(x,\alpha) = x D_{n-1}(x,\alpha) - \alpha D_{n-2}(x,\alpha), $$ with initial conditions $D_1(x,\alpha) = x$ and $D_2(x,\alpha) = x^2 - 2\alpha$. The definition can be extended for $n=0$ as $D_{0}(x,\alpha) = 2$. </p>
<p> The $D_n$ are also the unique monic polynomials satisfying the functional equation $$D_n(u+\frac{\alpha}{u},\alpha)=u^n+\left(\frac{\alpha}{u}\right)^n$$ where $\alpha\in \mathbb{F}_q$ and $u\in\mathbb{F}_{q^2}^\times$. In particular, with $\phi_{\alpha}=u+\frac{\alpha}{u}$, we have </p> <!-- https://q.uiver.app/#q=WzAsNCxbMCwwLCJcXG1hdGhjYWx7VH1fe1xcYWxwaGF9Il0sWzEsMCwiXFxtYXRoY2Fse1R9X3tcXGFscGhhXm59Il0sWzAsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzEsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzAsMSwieF5uIl0sWzAsMiwiXFxwaGlfXFxhbHBoYSIsMl0sWzIsMywiRF9uKHgsXFxhbHBoYSkiLDJdLFsxLDMsIlxccGhpX3tcXGFscGhhXm59Il1d --> <iframe class="quiver-embed" src="https://q.uiver.app/#q=WzAsNCxbMCwwLCJcXG1hdGhjYWx7VH1fe1xcYWxwaGF9Il0sWzEsMCwiXFxtYXRoY2Fse1R9X3tcXGFscGhhXm59Il0sWzAsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzEsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzAsMSwieF5uIl0sWzAsMiwiXFxwaGlfXFxhbHBoYSIsMl0sWzIsMywiRF9uKHgsXFxhbHBoYSkiLDJdLFsxLDMsIlxccGhpX3tcXGFscGhhXm59Il1d&embed" width="304" height="304" style="border-radius: 8px; border: none;"></iframe> <p>where $\mathcal{T}_\alpha=\phi^{-1}_\alpha(\mathbb{F}_q^\times)$.</p>
<p class="fragment"> For $\alpha\in \mathbb{F}_q$ and $\alpha=1$, there exists $u_{\alpha}$ with $$ \alpha = u_\alpha + \frac{1}{u_\alpha}. $$ </p> <p> <span class="fragment">We use the notation $(n)_r$ to denote $n\mod r$, the smallest postive integer congruent to $n$ modulo $r$. </span><span class="fragment">Let us also define $$ S_{q-1}=\{\alpha\in\mathbb{F}_q:u_\alpha^{q-1}=1\},\qquad S_{q+1}=\{\alpha\in\mathbb{F}_q:u_{\alpha}^{q+1}=1\},\qquad S_p=\{\pm 2\}. $$ Then,</span> </p>
<div class="theorem"> <div class="theorem-header"> <span class="theorem-authors">(Q. Wang, J.L. Yucas)</span> </div> <p> As functions on $\mathbb{F}_q$, we have $$ D_{n,k}(a,\alpha)=\begin{cases} D_{(n)_{2p},k}(a,\alpha) &\text{if }a\in S_p,\\ D_{(n)_{q-1},k}(a,\alpha) &\text{if }a\in S_{q-1},\\ D_{(n)_{q+1},k}(a,\alpha) &\text{if }a\in S_{q+1}. \end{cases} $$ </p> </div> <p class="fragment"> Use this functional equation, we can conclude that the (k+1)-th Dickson polynomial modulo $x^q-x$ at $\alpha$ has period $\frac{p(q^2-1)}{2}$. </p> <p class="fragment"><strong>Question:</strong> What is the exact peirod for general $\alpha$?</p>
### The first main theorem <div class="theorem"> <div class="theorem-header"> <span class="theorem-authors">(Y.-J. Chen, P.)</span> </div> <p> Let $q$ be a prime power and $\alpha\in \mathbb{F}_{q}^\times$. The period of the sequence $[D_n(x,\alpha)\ \mathrm{mod} (x^q-x)]_{n}$ is $\frac{q^2-1}{2}$ if $2\nmid q$ and $\alpha$ is a square in $\mathbb{F}_q$, and is $q^2-1$ otherwise. </p> </div> <div class="corollary fragment"> <p> Let $q$ be a prime power and $\alpha\in \mathbb{F}_q^\times$. Then for $0\leq i \leq q^2-1$ we have $$ D_{q^2-1-i}(x,\alpha) \equiv \alpha^{-i}D_{i}(x,\alpha)\ \mathrm{mod}(x^q-x). $$ Moreover, if $2\nmid q$ and $\alpha\in \mathbb{F}_q^\times$ is a square in $\mathbb{F}_q$, then for $0\leq i \leq \frac{q^2-1}{2}$ we have $$ D_{\frac{q^2-1}{2}-i}(x,\alpha) \equiv \alpha^{-i}D_{i}(x,\alpha)\ \mathrm{mod}(x^q-x). $$ </p> </div>
<div class="proof"> <p><span>Induction + recurssive relation.</span></p> <p><span class="fragment"> For $1< i\leq q^2-1$, we suppose $$ D_{q^2-1-i}(x-\alpha)\equiv \alpha^{-i}D_i(x,\alpha)\mod (x^q-x) $$ and $$ D_{q^2-1-(i+1)}(x,\alpha)\equiv\alpha^{-(i+1)}D_i(x,\alpha)\mod(x^q-x). $$ </span><span class="fragment"> Then, we have $$ \begin{align*} D_{q^2-1-(i+2)}(x,\alpha)&=\dfrac{x}{\alpha} D_{q^2-1-(i+1)}(x,\alpha)-\dfrac{1}{\alpha}D_{q^2-1-i}(x,\alpha)\\ &\equiv \alpha^{-(i+2)}(xD_{i+1}(x,\alpha)-\alpha D_{i}(x,\alpha))\\ &\equiv\alpha^{-(i+2)}D_{i+2}(x,\alpha)\mod(x^q-x). \end{align*} $$ </span> </p> </div>
### Proof of the first main theorem <div class="proposition"> <p> We have $$ D_{q^2-1}(x,\alpha) \equiv 2 \ \mathrm{mod}(x^q-x) \quad \textrm{and}\quad D_{q^2}(x,\alpha) \equiv x \ \mathrm{mod}(x^q-x). $$ If $\alpha\in\mathbb{F}_q^\times$ is a square. Then, we have $$ D_{\frac{q^2-1}{2}}(x,\alpha) \equiv 2 \ \mathrm{mod}(x^q-x) \quad \textrm{and}\quad D_{\frac{q^2+1}{2}}(x,\alpha) \equiv x \ \mathrm{mod}(x^q-x). $$ </p> </div> <div class="lemma fragment"> <p> Let $n$ be a positive integer such that $D_{n}(x, \alpha) \equiv 2\ \mathrm{mod}(x^q-x)$. If $2\mid q$, then $(q^2-1)\mid n$. If $2 \nmid q$, then $\frac{q^2-1}{2} \mid n$; especially, if $\alpha$ is nonsquare in $\mathbb{F}_q$, then $q^2-1\mid n$. </p> </div>
<div class="proof no-auto-qed" style="--proof-label:'Proof of the lemma.'"> <p> Recall the commutattive diagram: </p> <!-- https://q.uiver.app/#q=WzAsNCxbMCwwLCJcXG1hdGhjYWx7VH1fe1xcYWxwaGF9Il0sWzEsMCwiXFxtYXRoY2Fse1R9X3tcXGFscGhhXm59Il0sWzAsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzEsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzAsMSwieF5uIl0sWzAsMiwiXFxwaGlfXFxhbHBoYSIsMl0sWzIsMywiRF9uKHgsXFxhbHBoYSkiLDJdLFsxLDMsIlxccGhpX3tcXGFscGhhXm59Il1d --> <iframe class="quiver-embed" src="https://q.uiver.app/#q=WzAsNCxbMCwwLCJcXG1hdGhjYWx7VH1fe1xcYWxwaGF9Il0sWzEsMCwiXFxtYXRoY2Fse1R9X3tcXGFscGhhXm59Il0sWzAsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzEsMSwiXFxtYXRoYmJ7Rn1fcV5cXHRpbWVzIl0sWzAsMSwieF5uIl0sWzAsMiwiXFxwaGlfXFxhbHBoYSIsMl0sWzIsMywiRF9uKHgsXFxhbHBoYSkiLDJdLFsxLDMsIlxccGhpX3tcXGFscGhhXm59Il1d&embed" width="304" height="304" style="border-radius: 8px; border: none;"></iframe> <p> Let's assume $D_n(x,\alpha)\equiv 2\mod(x^q-x)$. We note that </p> <ul> <li>$\mathbb{F}_q^\times\subseteq \mathcal{T}_\alpha$;</li> <li>$|\phi^{-1}_{\alpha^n}(\{2\})|=1$ or $2$.</li> </ul> <P class="fragment"> If $q$ is even, then we immediately have $q-1|n$. If $q$ is odd, we need to eliminate the possibility that $|\phi^{-1}_{\alpha^n}(\{2\})|=2$. </p>
<div class="proof no-auto-qed unlabelled"> <p> If $n=t(q-1)/2$ for some odd integer $t$, then $$ \phi_{\alpha^n}^{-1}(\{2\})=(\mathcal{T}_\alpha)^n=\{1,-1\}, $$ that is, both $1$ and $-1$ are roots of $x^2-2x+\alpha^n$ in $\mathbb{F}_{q^2}$, therefore $2=1+(-1)=0$, a contradiction. </p> <p class="fragment" data-fragment-index="1"> For $q+1|n$, we note that there must be some element in $\mathcal{T}_\alpha$ with order divisble by $q+1$. </p> <p class="fragment" data-fragment-index="2"> If $q$ is odd and $\alpha$ is nonsquare, then we must find some element $u$ in $\mathcal{T}_\alpha$ with $$ u^{\frac{q^2-1}{2}}=-1\neq 1. $$ </p> <p class="fragment" data-fragment-index="3"> Such an element exists because we can write $\mathcal{T}_\alpha$ as union $$ \mathcal{T}_\alpha=\mathbb{F}_q^\times\cup \{u\in\mathbb{F}_{q^2}|u^{q+1}=\alpha\}. $$ </p> <span class="qed fragment" data-fragment-index="3"></span> </div>
### A Detour <div id="tables-two" style="margin:1rem auto;"> <div style="display:flex;gap:2%;align-items:flex-start;flex-wrap:wrap;"> <figure class="subtable shrink-70" id="tab-tableA" style="flex:1 1 0;min-width:260px;margin:0;"> <figcaption style="font-weight:600;margin:0 0 .4rem 0;">$D_{120}(x, −1)$</figcaption> <table class="grid-table" border="1" cellpadding="4" cellspacing="0" style="width:100%;border-collapse:collapse;font-size:.9em;"> <tbody> <tr><td>1</td><td>10</td><td>2</td><td>6</td><td>3</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>10</td><td>9</td><td>2</td><td>7</td><td>10</td><td>5</td><td>7</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>3</td><td>6</td><td>5</td><td>1</td><td>3</td><td>7</td><td>1</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>0</td><td>1</td><td>2</td><td>9</td><td>4</td><td>1</td><td>6</td><td>4</td><td>0</td></tr> <tr><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td><td>7</td><td>8</td><td>2</td><td>1</td><td>8</td></tr> <tr><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>1</td><td>10</td><td>2</td><td>6</td><td>3</td></tr> </tbody> </table> </figure> <figure class="subtable shrink-70" id="tab-tableB" style="flex:1 1 0;min-width:260px;margin:0;"> <figcaption style="font-weight:600;margin:0 0 .4rem 0;">$3D_{120}(x,2)$</figcaption> <table class="grid-table" border="1" cellpadding="4" cellspacing="0" style="width:100%;border-collapse:collapse;font-size:.9em;"> <tbody> <tr><td>3</td><td>6</td><td>2</td><td>10</td><td>1</td><td>6</td><td>0</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>8</td><td>1</td><td>2</td><td>8</td><td>7</td><td>4</td><td>2</td><td>0</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>4</td><td>6</td><td>1</td><td>4</td><td>9</td><td>2</td><td>1</td><td>0</td><td>0</td></tr> <tr><td>0</td><td>0</td><td>1</td><td>7</td><td>3</td><td>1</td><td>5</td><td>6</td><td>3</td><td>0</td></tr> <tr><td>0</td><td>0</td><td>0</td><td>7</td><td>5</td><td>10</td><td>7</td><td>2</td><td>9</td><td>10</td></tr> <tr><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>3</td><td>6</td><td>2</td><td>10</td><td>1</td></tr> </tbody> </table> </figure> </div> <div style="text-align:center;margin-top:.6rem;font-style:italic;">Rotate by 180°</div> </div>
<div class="theorem"> <div class="theorem-header"> <span class="theorem-authors">(Y.-J. Chen, P.)</span> </div> <p> Let $q$ be a power of an odd prime and $\alpha \in \mathbb{F}_q^\times$, $$ x^{q^2+1}\left(D_{q^2-1}\left(x^{-1},\alpha\right) - 2\right)=(-4\alpha)^{-1} \left(D_{q^2-1}\left(x,(16\alpha)^{-1} \right)-2\right). $$ Furthermore, if $\alpha \in\mathbb{F}_q^\times$ is square in $\mathbb{F}_q$, then $$ x^{\frac{q^2+1}{2}}D_{\frac{q^2-1}{2}}(x^{-1},\alpha)=2D_{\frac{q^2+1}{2}}\left(x, (16\alpha)^{-1}\right). $$ </p> </div>
<div class="corollary"> <p style="font-size: 20px;"> Let $q$ be a power of an odd prime $p$. Let $$ a_{j, k} = \dfrac{q^2-1}{q^2-1-(j(q-1)+k)}\binom{q^2-1-(j(q-1)+k)}{j(q-1)+k} $$ for $0\leq j\leq \frac{q-1}{2}$ and $0\leq k\leq q-2$. Then, we have $$ \sum_{j=0}^{\frac{q-1}{2}}a_{j,k}\equiv 0 \mod p. $$ Similarly, let $$ b_{j,k}=\dfrac{\frac{q^2-1}{2}}{\frac{q^2-1}{2}-(j\frac{q-1}{2}+k)}\binom{\frac{q^2-1}{2}-(j\frac{q-1}{2}+k)}{j\frac{q-1}{2}+k} $$ for $0\leq j\leq\frac{q-1}{2}$ and $0\leq k \leq \frac{q-3}{2}$. Then, we have $$ \sum_{j=0}^{\frac{q-1}{2}}b_{j,k}\equiv 0\mod p. $$ </p> </div>
<p class="proof"> We can write the dickson polynomial of degree $q^2-1$ as the following double sum $$ \pm 1+\sum_{j=0}^{\frac{q-1}{2}}\sum_{k=0}^{q-2}\dfrac{q^2-1}{q^2-1-(j(q-1)+k)}\binom{q^2-1-(j(q-1)+k)}{j(q-1)+k}(-\alpha)^{(j(q-1)-k)}x^{q^2-1-2(j(q-1)+k))}. $$ <span class="fragment"> Note that $x^{q-1}\not\equiv 1\mod x^q-x$ because $0^{q-1}\not\equiv 1\mod x^q-x$. Therefore, the only term of a polynomial modulo $x^q-x$ that becomes a constant term is the polynomial's own constant term. </span> <span class="fragment"> The constant term is $j=\frac{q+1}{2}$ and $k=0$. Observing the expoenent and by the main theorem, we may conclude that $\sum_{j}a_{j,k}=0$. </span> </p>
### Dynamics of Dickson polynomials <p> When we choose $\alpha\in \mathbb{F}_q^\times$ with $\alpha^n=\alpha$, we have $\phi_{\alpha^n}=\phi_{\alpha}$. This allows us to study the dynamics of $D_n(x,\alpha)$. </p> <p class="fragment"> Let $D_{n,\alpha}(x)=D_n(x,\alpha)$. We then have $$ D_{n,\alpha}^m(x)=D_{n^m,\alpha}(x). $$ </p> <p class="fragment"> Note that, for $n$ coprime to $q^2-1$, we have the following homomorphism $$ \langle n|\alpha^n=\alpha\rangle(\mathbb{Z}/(q^2-1)\mathbb{Z})^\times\to \mathcal{D}_\alpha=\{D_{n,\alpha}(x)|\alpha^n=\alpha\} $$ by the first main theorem. </p> <p class="fragment"><strong>Question:</strong> What is the kernel? Is there any $n\neq 1$ such that $D_{n,\alpha}(x)=x$?</p>
<div class="example"> <p> Conisdering $q=5^2$, we have $$ D_{5}(x,1) \equiv x \equiv D_{7}(x,1)\ \mathrm{mod}(x^5-x) $$ despite both $5$ and $7$ are not congruent to $1$ modulo $24$ or $12$. </p> </div> <div class="theorem"> <div class="theorem-header"> <span class="theorem-authors">(Y.-J. Chen, P.)</span> </div> <p> Let $\alpha\in\mathbb{F}_q^\times$. Then, $\mathcal{D}_{\alpha} = \{D_{n,\alpha}(x)\mod x^q-x|\alpha^n=\alpha\}$ is a group, whose operation is composition. Furthermore, $\mathcal{D}_n$ is isomorphic to a subgroup of $$ \begin{cases} (\mathbb{Z}/(q^2-1)\mathbb{Z})^{\times}/H_1, &\text{if }\alpha\text{ is not a square;}\\ (\mathbb{Z}/(\frac{q^2-1}{2})\mathbb{Z})^{\times}/H_1, &\text{if }\alpha\neq 1\text{ is a square;}\\ (\mathbb{Z}/(q^2-1)\mathbb{Z})^{\times}/H_2, &\text{if }\alpha=1. \end{cases} $$ where $H_1\cong\mathbb{Z}/2\mathbb{Z}$ and $H_2\cong\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/2\mathbb{Z}$. </p> </div>
<div class="corollary"> <p> <ol> <li style="font-size: 18px;"> Let $\alpha\in\mathbb{F}_q^\times$ satisfy $\alpha^n=\alpha$. The period of $D_{n,\alpha}(x)\mod (x^q-x)$ is $\delta_{n,\alpha}k$, where $k$ is the multiplicative order of $n$ modulo $\pi(\alpha)$ with $$ \delta_{n,\alpha}= \begin{cases} \frac{1}{2}, &\text{ if } n \text{ and } \alpha \text{ satisfy the conditions we describe below,}\\ 1, &\text{ otherwise. } \end{cases} $$ The condition is that when $\alpha = 1$, $-1,\pm q \not \in \{n^i \mod q^2-1| i=1,2,3\dots\}$, and that when $\alpha \neq 1$, $q \not \in \{n^i \mod \pi(\alpha) | i=1,2,3\dots\}$. </li> <li class="fragment" style="font-size: 18px;"> For $\alpha\in(\mathbb{F}_q)^\times$ with the multiplicative order $m$, let $m=2^{k'}p_{1}^{e'_{1}}\cdots p_{l}^{e'_{l}}$. Let $\pi(\alpha)=2^kp_1^{e_1}\cdots p_r^{e_r}q_1^{f_1}\cdots q_s^{f_s}$ where $p_i$ and $q_i$ are odd primes that divide $q-1$ and $q+1$ respectively. Then there exists $n$ with $\alpha^n=\alpha$ such that $D_{n,\alpha}(x)$ has period $$\operatorname{lcm}:= \begin{cases} \operatorname{lcm}(\{2^{k-k'},p_1^{e_1-e'_1},\ldots,p_l^{e_l-e'_l},\phi(p_{l+1}^{e_{l+1}}),\ldots \phi(p_n^{e_n}),\phi(q_1^{f_1}),\ldots \phi(q_s^{f_s})\}) & \text{if }k' > 1\\ \operatorname{lcm}(\{2^{k-2},p_1^{e_1-e'_1},\ldots,p_l^{e_l-e'_l},\phi(p_{l+1}^{e_{l+1}}),\ldots \phi(p_n^{e_n}),\phi(q_1^{f_1}),\ldots \phi(q_s^{f_s})\}) & \text{if }k'=1\\ \operatorname{lcm}(\{p_1^{e_1-e'_1},\ldots,p_l^{e_l-e'_l},\phi(p_{l+1}^{e_{l+1}}),\ldots \phi(p_n^{e_n}),\phi(q_1^{f_1}),\ldots \phi(q_s^{f_s})\}) & \text{if }k'=0 \end{cases} $$ where $\phi$ is the Euler's totient function. <li class="fragment" style="font-size: 18px;"> Following the above notations, we have $\alpha$ such that the period of $D_{n,\alpha}(x)\mod x^q-x$ equals the maximum of the multiplicative order of $n$ in $\mathbb{Z}/(q^2-1)\mathbb{Z}$ if some $\phi(p_i^{e_i})$ or $\phi(q_i^{f_i})$ is divisible by $2^k$. </li> </ol> </p> </div>
<div class="lemma"> <p> Let $n$ be a positive integer such that $D_{n,\alpha}(x)=x \mod(x^q-x)$. Then, for even $q$, we have: </p> <ol> <li>$n^2\equiv 1\mod(q^2-1)$.</li> <li>When $\alpha=1$, $n\equiv \pm 1,\ \pm q\mod q^2-1$</li> <li>When $\alpha\neq 1$, $n \equiv 1,q \mod q^2-1$</li> </ol> <p>For odd $q$,</p> <ol> <li>$n^2\equiv 1\mod\dfrac{q^2-1}{2}$. In particular, if $\alpha$ is nonsquare, we have $n^2\equiv 1\mod q^2-1$.</li> <li>When $\alpha=1$, $n\equiv \pm 1,\ \pm q\mod \frac{q^2-1}{2}$.</li> <li>When $\alpha\neq 1$, $n\equiv 1\ \textrm{or}\ q\mod\pi(\alpha)$.</li> <li>We have $$ \{n|\alpha^n=\alpha\text{ and }D_{n,\alpha}(x)=x\mod x^q-x\}\cong\begin{cases} \mathbb{Z}/2\mathbb{Z}, &\text{ if }\alpha\neq 1\\ \mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/2\mathbb{Z}, &\text{ if }\alpha=1. \end{cases} $$ </li> </ol>
<div class="proof no-auto-qed" style="--proof-label:'Proof of 2.'"> <p> <span>Assuming $\alpha=1$ and letting $\zeta$ be a generator of $\mathbb{F}_q^\times$, we have $\zeta^n=\zeta$ or $\zeta^n=\zeta^{-1}$.</span><span class="fragment"> This implies $n\equiv \pm 1\mod q-1$.</span><span class="fragment"> There exists an element $u\mathcal{T}_\alpha$ of order $q+1$.</span><span class="fragment"> Since $u^n$ is either $u$ or $u^{-1}$, $u^{n-1}=1$ or $u^{n+1}=1$. Thus, $n-1$ or $n+1$ have to congruence to zero mod $q+1$.</span> </p> </div>
<div class="proof no-auto-qed unlabelled"> <p> It follows that we have the following four possible systems of congruence equations $$\begin{align*} & \begin{cases} n\equiv 1 & \mod q-1\\ n\equiv 1 & \mod q+1 \end{cases} & \begin{cases} n\equiv -1 & \mod q-1\\ n\equiv 1 & \mod q+1 \end{cases}\\ & \begin{cases} n\equiv 1 & \mod q-1\\ n\equiv -1 & \mod q+1 \end{cases} & \begin{cases} n\equiv -1 & \mod q-1\\ n\equiv -1 & \mod q+1 \end{cases} \end{align*} $$ </p> <p class="fragment"> By the Chinese remainder theorem, we can conclude the following: <ul> <li class="fragment">if $q$ is even, $n\equiv \pm 1,\ \pm q\mod q^2-1$.</li> <li class="fragment">if $q$ is odd, then $n\equiv \pm 1,\pm q\mod \frac{q^2-1}{2}$</li> </ul> </p> <span class="qed fragment" data-fragment-index="3"></span> </div>
### When $n$ is not coprime to $q^2-1$ <p> we denote the dynamic structure of $[n^k\mod\pi(\alpha)]_k$ by $(l,k)$, so we have $$ D^{l+1}_n(x)=D_{n^{l+1}}(x)=D_{n^{l+1+k}}(x)=D_n^{l+1+k}(x). $$ This equation implies $\mathscr{l}=l-\mathscr{m_l}\mathscr{k}$ and $k=\mathscr{m_k}\mathscr{k}$ for some integers $\mathscr{m_l}$ and $\mathscr{m_k}$. The integer $\mathscr{k}$ is the smallest positive integer such that $D_n^\mathscr{k}(x)$ is an identity map on the periodic points of $D_n(x)$ in $\mathbb{F}_q$. </p>
<div class="lemma"> <p>Using the notation defined above, we have $l=\mathscr{l}$.</p> </div> <div class="proof fragment"> <p> Let $\gamma\in \mathbb{F}_q^\times$, and suppose $\gamma$ is not a periodic point under $x^n$, but $\phi_\alpha(\gamma)$ is a periodic point under $D_n$. Let $\mathscr{k}$ be the period of $[D_{n^m}(x,\alpha)\mod x^q-x]_{m}$. Then, both $\gamma$ and $\gamma^{n^\mathscr{k}}$ map to the same point under $\phi_\alpha$. That is $\phi_{\alpha}^{-1}(\gamma+\frac{\alpha}{\gamma})=\{\gamma,\gamma^{n^\mathrm{k}}\}$. Moreover, we know that $\phi_\alpha^{-1}(\gamma+\frac{\alpha}{\gamma})=\{\gamma, \frac{\alpha}{\gamma}\}$, so we have $\gamma^{n^\mathscr{k}}=\frac{\alpha}{\gamma}$. It implies $(\gamma^{n^\mathscr{k}})^{n^\mathscr{k}}=(\frac{\alpha}{\gamma})^{n^\mathscr{k}}=\frac{\alpha^{n^\mathscr{k}}}{\gamma^{n^{\mathscr{k}}}}=\frac{\alpha}{\alpha/\gamma}=\gamma$. This shows that $\gamma$ is a periodic point under $x^n$, contradicts with the assumption. </p> <div class="proposition fragment"> <p>If $k$ is odd, then $(\mathscr{l},\mathscr{k})=(l,k)$.</p> </div> </div>
### Discussion 1. How to deal with $n$ not coprime to $q^2-1$ 2. New special polynomials for dynamical system? 3. Quadratic recurrence relations can also be viewed from the perspective of orthogonal polynomials. How can we give a combinatorical viewpoint about this problem?