on a conjecture on permutation rational functions over finite fields

Daniele Bartoli Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Italy [email protected] and Xiang-dong Hou Department of Mathematics and Statistics, University of South Florida, Tampa, FL 33620, USA [email protected]

Abstract.

Let $p$ be a prime and $n$ be a positive integer, and consider $f_{b}(X)=X+(X^{p}-X+b)^{-1}\in\mathbb{F}_{p}(X)$ , where $b\in\mathbb{F}_{p^{n}}$ is such that $\text{Tr}_{p^{n}/p}(b)\neq 0$ . It is known that (i) $f_{b}$ permutes $\mathbb{F}_{p^{n}}$ for $p=2,3$ and all $n\geq 1$ ; (ii) for $p>3$ and $n=2$ , $f_{b}$ permutes $\mathbb{F}_{p^{2}}$ if and only if $\text{Tr}_{p^{2}/p}(b)=\pm 1$ ; and (iii) for $p>3$ and $n\geq 5$ , $f_{b}$ does not permute $\mathbb{F}_{p^{n}}$ . It has been conjectured that for $p>3$ and $n=3,4$ , $f_{b}$ does not permute $\mathbb{F}_{p^{n}}$ . We prove this conjecture for sufficiently large $p$ .

Key words and phrases:

finite field, Lang-Weil bound, permutation, rational function

2010 Mathematics Subject Classification:

11R58, 11T06, 11T55, 14H05

1. Background

Let $\mathbb{F}_{q}$ denote the finite field with $q$ elements. Polynomials over $\mathbb{F}_{q}$ that permute $\mathbb{F}_{q}$ , called permutation polynomials (PPs) of $\mathbb{F}_{q}$ , have been extensively studied in the theory and applications of finite fields. Recently, permutation rational functions (PRs) of finite fields also attracted considerable attention. There are a number of reasons for studying PRs. Certain types of PPs of high degree can be reduced to PRs of low degree; this approach has allowed people to solve numerous questions about PPs [1, 2, 5, 6, 7, 9, 11, 12, 13, 14, 16]. Oftentimes, PRs reveal phenomena that are not present in PPs; understanding these phenomena requires methods that are different from those in traditional approaches to PPs.

This paper concerns a conjecture on PRs of the type

f_{b}(X)=X+\frac{1}{X^{p}-X+b}\in\mathbb{F}_{p}(X)

of $\mathbb{F}_{p^{n}}$ , where $p$ is a prime, $n$ is a positive integer, and $b\in\mathbb{F}_{p^{n}}$ is such that $\text{Tr}_{p^{n}/p}(b)\neq 0$ . In [15], Yuan et al. proved that for $p=2,3$ and all $n\geq 1$ , $f_{b}$ is a PR of $\mathbb{F}_{p^{n}}$ . Recently, it was shown in [8] that for $p>3$ and $n\geq 5$ , $f_{b}$ is not a PR of $\mathbb{F}_{p^{n}}$ , and for $p>3$ and $n=2$ , $f_{b}$ is a PR of $\mathbb{F}_{p^{2}}$ if and only if $\text{Tr}_{p^{2}/p}(b)=\pm 1$ . Based on computer search, it was conjectured in [8] that for $p>3$ and $n=3,4$ , $f_{b}$ is not a PR of $\mathbb{F}_{p^{n}}$ . We will prove this conjecture for sufficiently large $p$ . Our approach relies on the Lang-Weil bound on the number of zeros of absolutely irreducible polynomials over finite fields. The main technical ingredient of our proof is a claim that that a certain polynomial of degree 18 in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ has a cyclic absolutely irreducible factor in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ and a claim that a certain polynomial of degree 46 in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ has a cyclic absolutely irreducible factor in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

Throughout the paper, $\overline{\mathbb{F}}_{q}$ denotes the algebraic closure of $\mathbb{F}_{q}$ . For $f\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ , define

V_{\mathbb{F}_{q}^{n}}(f)=\{(x_{1},\dots,x_{n})\in\mathbb{F}_{q}^{n}:f(x_{1},\dots,x_{n})=0\}.

$f$ is said to be absolutely irreducible if it is irreducible in $\overline{\mathbb{F}}_{p}[X_{1},\dots,X_{n}]$ . The resultant of two polynomials $f(X)$ and $g(X)$ in $X$ is denoted by $\text{Res}(f,g;X)$ .

2. Cyclic Shift and the Forbenius

For $\sigma\in\text{Aut}(\mathbb{F}_{q})$ and $f\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ , let $\sigma(f)$ denote the resulting polynomial by applying $\sigma$ to the coefficients of $f$ ; this defines an action of $\text{Aut}(\mathbb{F}_{q})$ on $\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ . Let $\rho$ be the cyclic shift on the indeterminates $X_{1},\dots,X_{n}$ : $\rho(X_{1},\dots,X_{n})=(X_{2},,X_{3},\dots,X_{n},X_{1})$ . For $f\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ and $\rho^{i}\in\langle\rho\rangle$ , let $f^{\rho^{i}}=f(\rho^{i}(X_{1},\dots,X_{n}))$ ; this gives an action of $\langle\rho\rangle$ on $\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ . A polynomial $f\in\mathbb{F}_{q}[X_{1},\dot{,}X_{n}]$ is called cyclic if $f^{\rho}=f$ and is called pseudo-cyclic if $f^{\rho}=cf$ for some $n$ th unity in $\mathbb{F}_{q}$ .

For $z\in\mathbb{F}_{q^{n}}$ , $z,z^{q},\dots,z^{q^{n-1}}$ form a normal basis of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_{q}$ if and only if the Moore matrix of $z$ ,

M(z)=\left[\begin{matrix}z&z^{q}&\cdots&z^{q^{n-1}}\cr z^{q}&z^{q^{2}}&\cdots&z\cr\vdots&\vdots&&\vdots\cr z^{q^{n-1}}&z&\cdots&z^{q^{n-2}}\end{matrix}\right],

is invertible. An $n\times n$ matrix $A$ over $\mathbb{F}_{q^{n}}$ is of the form $M(z)$ for some $z\in\mathbb{F}_{q^{n}}$ if and only if $\sigma(A)=CA=AC^{-1}$ , where $\sigma(\ )=(\ )^{q}$ is the Frobenius map of $\mathbb{F}_{q^{n}}/\mathbb{F}_{q}$ , $\sigma(A)$ is the result of entry-wise action of $\sigma$ on $A$ , and

C=\left[\begin{matrix}0&1&0&\cdots&0\cr 0&0&1&\cdots&0\cr\vdots&\vdots&\vdots&\ddots&\vdots\cr 0&0&0&\cdots&1\cr 1&0&0&\cdots&0\end{matrix}\right].

From this, it is easy to see that if $M(z)$ is invertible, then $M(z)^{-1}=M(w)$ for some $w\in\mathbb{F}_{q^{n}}$ .

Lemma 2.1.

Let $z\in\mathbb{F}_{q^{n}}$ be such that $\det M(z)\neq 0$ . Let $f\in\overline{\mathbb{F}}_{q}[X_{1},\dots,X_{n}]$ and $g=f((X_{1},\dots,X_{n})M(z))$ . Then

(i)

$f$ is cyclic if and only if $g$ is cyclic;
(ii)

$f\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ and is cyclic if and only if $g\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$ and is cyclic.

Proof.

Since $f=g((X_{1},\dots,X_{n})M(w))$ , where $M(w)=M(z)^{-1}$ , we only have to prove the “only if” part in both (i) and (ii).

(i) ( $\Rightarrow$ ) We have

	$\displaystyle g((X_{1},\dots,X_{n})C)\,$	$\displaystyle=f((X_{1},\dots,X_{n})CM(z))$
		$\displaystyle=f((X_{1},\dots,X_{n})M(z)C^{-1})$
		$\displaystyle=f((X_{1},\dots,X_{n})M(z))\kern 50.00008pt\text{(since $f$ is cyclic)}$
		$\displaystyle=g.$

(ii) ( $\Rightarrow$ ) We have

	$\displaystyle\sigma(g)\,$	$\displaystyle=\sigma(f((X_{1},\dots,X_{n})M(z)))$
		$\displaystyle=f((X_{1},\dots,X_{n})\sigma(M(z)))\kern 50.00008pt\text{(since $f\in\mathbb{F}_{q}[X_{1},\dots,X_{n}]$)}$
		$\displaystyle=f((X_{1},\dots,X_{n})M(z)C^{-1})$
		$\displaystyle=g.$

∎

3. The Case $n=3$

For $n=3$ , we have the following theorem.

Theorem 3.1.

Let $p\geq 1734097$ be a prime and $b\in\mathbb{F}_{p^{3}}$ be such that $\text{\rm Tr}_{p^{3}/p}(b)\neq 0$ . Then $f_{b}$ is not a PR of $\mathbb{F}_{p^{3}}$ . (Note: $1734097$ is the $130492$ th prime.)

Proof.

We have

f_{b}(X+Y)-f_{b}(X)=\frac{Y(Z(X)^{2}+(Y^{p}-Y)Z(X)+1-Y^{p-1})}{Z(X)Z(X+Y)},

where

Z(X)=X^{p}-X+b.

Let

F(X,Y)=Z(X)^{2}+(Y^{p}-Y)Z(X)+1-Y^{p-1}\in\mathbb{F}_{p^{3}}[X,Y].

It suffices to show that there exists $(x,y)\in\mathbb{F}_{p^{3}}^{2}$ with $y\neq 0$ such that $F(x,y)=0$ , i.e., such that

(3.1)

z^{2}+(y^{p}-y)z+1-y^{p-1}=0,

where $z=x^{p}-x+b$ . The solution of (3.1) for $z$ is

(3.2)

z=\frac{1}{2}(-(y^{p}-y)+\Delta),

where

(3.3)	$\displaystyle\Delta^{2}\,$	$\displaystyle=(y^{p}-y)^{2}-4(1-y^{p-1})$
(3.4)		$\displaystyle=(y^{p-1}-1)(y^{2}(y^{p-1}-1)+4)$
	$\displaystyle=y^{2p}+y^{2}-2y^{1+p}+4y^{p-1}-4.$

Therefore, it suffices to show that there exist $\Delta,y\in\mathbb{F}_{p^{3}}$ , with $y\neq 0$ and $\text{Tr}_{p^{3}/p}(\Delta)=2\text{Tr}_{p^{3}/p}(b)=:t$ , satisfying

(3.5)

\Delta^{2}=y^{2p}+y^{2}-2y^{1+p}+4y^{p-1}-4.

Assume for the time being that we already have $\Delta,y\in\mathbb{F}_{p^{3}}$ , with $y\neq 0$ and $\text{Tr}_{p^{3}/p}(\Delta)=t$ , that satisfy (3.5). Let $y=y_{1},y_{2}=y^{p},y_{3}=y^{p^{2}}$ and $\Delta_{1}=\Delta,\Delta_{2}=\Delta^{p},\Delta_{3}=\Delta^{p^{2}}$ . Then we have

(3.6)		$\displaystyle\Delta_{1}^{2}=y_{1}^{2}+y_{2}^{2}-2y_{1}y_{2}+4\frac{y_{2}}{y_{1}}-4,$
(3.7)		$\displaystyle\Delta_{2}^{2}=y_{2}^{2}+y_{3}^{2}-2y_{2}y_{3}+4\frac{y_{3}}{y_{2}}-4,$
(3.8)		$\displaystyle\Delta_{3}^{2}=y_{3}^{2}+y_{1}^{2}-2y_{3}y_{1}+4\frac{y_{1}}{y_{3}}-4,$
(3.9)		$\displaystyle\Delta_{1}+\Delta_{2}+\Delta_{3}=t.$

From (3.9) we can express $\Delta_{1}$ in terms of $\Delta_{1}^{2}$ , $\Delta_{2}^{2}$ , $\Delta_{3}^{2}$ and $t$ through the following calculation:

(3.10)		$\displaystyle(t-\Delta_{1})^{2}=(\Delta_{2}+\Delta_{3})^{2},$
(3.11)		$\displaystyle t^{2}+\Delta_{1}^{2}-\Delta_{2}^{2}-\Delta_{3}^{2}-2t\Delta_{1}=2\Delta_{2}\Delta_{3},$
(3.12)		$\displaystyle(t^{2}+\Delta_{1}^{2}-\Delta_{2}^{2}-\Delta_{3}^{2})^{2}+4t^{2}\Delta_{1}^{2}-4t\Delta_{1}(t^{2}+\Delta_{1}^{2}-\Delta_{2}^{2}-\Delta_{3}^{2})=4\Delta_{2}^{2}\Delta_{3}^{2},$
(3.13)		$\displaystyle\Delta_{1}=\frac{(t^{2}+\Delta_{1}^{2}-\Delta_{2}^{2}-\Delta_{3}^{2})^{2}+4t^{2}\Delta_{1}^{2}-4\Delta_{2}^{2}\Delta_{3}^{2}}{4t(t^{2}+\Delta_{1}^{2}-\Delta_{2}^{2}-\Delta_{3}^{2})},$

provided the denominator is nonzero. Using (3.6) – (3.8), we can write (3.13) as

(3.14)

\Delta_{1}=\frac{P(y_{1},y_{2},y_{3})}{4ty_{1}y_{2}y_{3}Q(y_{1},y_{2},y_{3})},

where

(3.15)

P(Y_{1},Y_{2},Y_{3})=16Y_{1}^{4}Y_{2}^{2}+32Y_{1}^{3}Y_{2}^{2}Y_{3}-\cdots-16Y_{1}Y_{2}^{3}Y_{3}^{4},

(3.16)

Q(Y_{1},Y_{2},Y_{3})=-4Y_{1}^{2}Y_{2}+4Y_{1}Y_{2}Y_{3}+\cdots-2Y_{1}Y_{2}Y_{3}^{3}.

It follows that

(3.17)		$\displaystyle\Delta_{2}=\frac{P(y_{2},y_{3},y_{1})}{4ty_{1}y_{2}y_{3}Q(y_{2},y_{3},y_{1})},$
(3.18)		$\displaystyle\Delta_{3}=\frac{P(y_{3},y_{1},y_{2})}{4ty_{1}y_{2}y_{3}Q(y_{3},y_{1},y_{2})}.$

Using (3.14), equation (3.6) becomes

(3.19)

\frac{G(y_{1},y_{2},y_{3})}{16t^{2}y_{1}^{2}y_{2}^{2}y_{3}^{2}Q(y_{1},y_{2},y_{3})^{2}}=0,

and using (3.14), (3.17) and (3.18), equation (3.9) becomes

(3.20)

\frac{G(y_{1},y_{2},y_{3})}{4ty_{1}y_{2}y_{3}Q(y_{1},y_{2},y_{3})Q(y_{2},y_{3},y_{1})Q(y_{3},y_{1},y_{2})}=0,

where $G(Y_{1},Y_{2},Y_{3})\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ is a cyclic polynomial of degree 18. More precisely,

(3.21)

G=g_{18}+g_{16}+g_{14}+g_{12},

where $g_{i}\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ is homogeneous of degree $i$ :

(3.22)			$\displaystyle g_{18}=-64t^{2}Y_{1}^{4}Y_{2}^{4}Y_{3}^{4}(Y_{1}-Y_{2})^{2}(Y_{2}-Y_{3})^{2}(Y_{3}-Y_{1})^{2},$
(3.23)			$\displaystyle g_{16}=16Y_{1}^{2}Y_{2}^{2}Y_{3}^{2}(16Y_{1}^{6}Y_{2}^{4}-32Y_{1}^{5}Y_{2}^{5}+\cdots+16Y_{2}^{4}Y_{3}^{6}),$
(3.24)			$\displaystyle g_{14}=8Y_{1}Y_{2}Y_{3}(64Y_{1}^{7}Y_{2}^{4}-64Y_{1}^{6}Y_{2}^{5}-\cdots-64Y_{1}^{2}Y_{2}^{2}Y_{3}^{7}),$
(3.25)			$\displaystyle g_{12}=256Y_{1}^{8}Y_{2}^{4}+1024Y_{1}^{7}Y_{2}^{4}Y_{3}-\cdots+256Y_{1}^{4}Y_{3}^{8}.$

We will show that there exists $y\in\mathbb{F}_{p^{3}}$ such that $G(y,y^{p},y^{p^{2}})=0$ but $Q(y,y^{p},y^{p^{2}})\neq 0$ . Once this is done, the proof of the theorem is completed as follows: Clearly, $y\neq 0$ . Let $y_{1}=y,y_{2}=y^{p},y_{3}=y^{p^{2}}$ and let $\Delta_{1},\Delta_{2},\Delta_{3}$ be given by (3.14), (3.17) and (3.18). Then (3.6) and (3.9) hold. Let $\Delta=\Delta_{1}$ . By (3.9), $\text{Tr}_{p^{3}/p}(\Delta)=t$ ; by (3.6), $\Delta$ and $y$ satisfy (3.5).

Choose $z\in\mathbb{F}_{p^{3}}$ such that $M(z)$ is invertible and let

G_{1}=G((Y_{1},Y_{2},Y_{3})M(z)).

By Lemma 3.2 below, $G$ has a cyclic absolutely irreducible factor $d\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ . Let $d_{1}=d((Y_{1},Y_{2},Y_{3})M(z))$ . Then $d\mid G$ implies that $d_{1}\mid G_{1}$ , Lemma 2.1 implies that $d_{1}\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ and is cyclic, and the absolute irreducibility of $d$ implies the absolute irreducibility of $d_{1}$ . The Lang-Weil bound [10] states that

|V_{\mathbb{F}_{p}^{3}}(d_{1})|=p^{2}+O(p^{3/2})\qquad\text{as}\ p\to\infty.

More precisely, by [4, Theorem 5.2],

(3.26)

|V_{\mathbb{F}_{p}^{3}}(d_{1})|\geq p^{2}-(18-1)(18-2)p^{3/2}-5\cdot 18^{13/3}p=p^{2}-272p^{3/2}-5\cdot 18^{13/3}p.

We find that

\text{Res}(G,Q;Y_{3})=2^{16}Y_{1}^{14}Y_{2}^{8}(-256Y_{1}^{4}-\cdots-8t^{2}Y_{1}^{4}Y_{2}^{6})^{2}(256Y_{1}^{3}+\cdots+4t^{2}Y_{1}^{2}Y_{2}^{7})^{2}\neq 0.

Hence $\text{gcd}(G,Q)=1$ . Let $Q_{1}=Q((Y_{1},Y_{2},Y_{3})M(z))$ . It follows that $\text{gcd}(G_{1},Q_{1})=1$ . By [4, Lemma 2.2],

(3.27)

|V_{\mathbb{F}_{p}^{3}}(G_{1})\cap V_{\mathbb{F}_{p}^{3}}(Q_{1})|\leq 18^{2}p.

Therefore,

	$\displaystyle\|V_{\mathbb{F}_{p}^{3}}(G_{1})\setminus V_{\mathbb{F}_{p}^{3}}(Q_{1})\|\,$	$\displaystyle=\|V_{\mathbb{F}_{p}^{3}}(G_{1})\|-\|V_{\mathbb{F}_{p}^{3}}(G_{1})\cap V_{\mathbb{F}_{p}^{3}}(Q_{1})\|$
		$\displaystyle\geq\|V_{\mathbb{F}_{p}^{3}}(d_{1})\|-18^{2}p$
		$\displaystyle\geq p^{2}-272p^{3/2}-(5\cdot 18^{13/3}+18^{2})p$
		$\displaystyle=p(p-272p^{1/2}-(5\cdot 18^{13/3}+18^{2}))$
		$\displaystyle>0$

since

p\geq 1734097>1734081\approx\frac{1}{4}\bigl{[}271+(272^{2}+4(5\cdot 18^{13/3}+18^{2}))^{1/2}\bigr{]}^{2}.

Let $(a_{1},a_{2},a_{3})\in V_{\mathbb{F}_{p}^{3}}(G_{1})\setminus V_{\mathbb{F}_{p}^{3}}(Q_{1})$ and let $y=a_{1}z+a_{2}z^{q}+a_{3}z^{q^{2}}\in\mathbb{F}_{p^{3}}$ . Then $G(y,y^{p},y^{p^{2}})=0$ but $Q(y,y^{p},y^{p^{2}})\neq 0$ . The proof is complete. ∎

Lemma 3.2.

The polynomial $G$ in (3.21) has a cyclic absolutely irreducible factor in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3}]$ .

Proof.

Let $\rho$ denote the cyclic shift $(Y_{1},Y_{2},Y_{3})\mapsto(Y_{2},Y_{3},Y_{1})$ and let $\sigma\in\text{Aut}(\overline{\mathbb{F}}_{p})$ be the Frobenius map $(\ )\mapsto(\ )^{p}$ . Recall that the homogeneous component of the highest degree of $G$ is

g_{18}=-64t^{2}Y_{1}^{4}Y_{2}^{4}Y_{3}^{4}(Y_{1}-Y_{2})^{2}(Y_{2}-Y_{3})^{2}(Y_{3}-Y_{1})^{2}.

All pseudo-cyclic factors of $g_{18}$ in $\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3}]$ are cyclic; therefore, all pseudo-cyclic factors of $G$ in $\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3}]$ are cyclic.

$1^{\circ}$ We have

G=a_{8}(Y_{1},Y_{2})Y_{3}^{8}+a_{7}(Y_{1},Y_{2})Y_{3}^{7}+\cdots,

where

(3.28)

a_{8}(Y_{1},Y_{2})=16Y_{1}^{2}\alpha(Y_{1},Y_{2},t)\alpha(Y_{1},Y_{2},-t)

and

\alpha(Y_{1},Y_{2},T)=4Y_{1}+4TY_{1}Y_{2}+4Y_{1}^{2}Y_{2}+T^{2}Y_{1}Y_{2}^{2}+2TY_{1}^{2}Y_{2}^{2}-4Y_{2}^{3}-2TY_{1}Y_{2}^{3}.

We claim that $\alpha(Y_{1},Y_{2},t)$ and $\alpha(Y_{1},Y_{2},-t)$ are irreducible in $\overline{\mathbb{F}}_{p}[Y_{1},Y_{2}]$ . The discriminant of $\alpha(Y_{1},Y_{2},t)$ , as a polynomial in $Y_{1}$ , is

D=16+32tY_{2}+24t^{2}Y_{2}^{2}-16tY_{2}^{3}+8t^{3}Y_{2}^{3}+64Y_{2}^{4}-16t^{2}Y_{2}^{4}+t^{4}Y_{2}^{4}+32tY_{2}^{5}-4t^{3}Y_{2}^{5}+4t^{2}Y_{2}^{6}.

Assume to the contrary that $D$ is a square in $\overline{\mathbb{F}}_{p}[Y_{2}]$ . Then

D-(2tY_{2}^{3}+aY_{2}^{2}+bY_{2}+c)^{2}=0,

where $a,b\in\overline{\mathbb{F}}_{p}$ and $c=\pm 4$ .

When $c=4$ ,

D-(2tY_{2}^{3}+aY_{2}^{2}+bY_{2}+4)^{2}\equiv-8(b-4t)Y_{2}\pmod{Y_{2}^{2}}.

Then $b=4t$ , and it follows that

	$\displaystyle D-(2tY_{2}^{3}+aY_{2}^{2}+bY_{2}+4)^{2}$
	$\displaystyle=-8(a-t^{2})Y_{2}^{2}+8t(-4-a+t^{2})Y_{2}^{3}+(64-a^{2}-32t^{2}+t^{4})Y_{2}^{4}-4t(-8+a+t^{2})Y_{2}^{5}$
	$\displaystyle\neq 0,$

which is a contradiction.

When $c=-4$ ,

D-(2tY_{2}^{3}+aY_{2}^{2}+bY_{2}-4)^{2}\equiv 8(b+4t)Y_{2}\pmod{Y_{2}^{2}}.

Then $b=-4t$ , and it follows that

	$\displaystyle D-(2tY_{2}^{3}+aY_{2}^{2}+bY_{2}-4)^{2}$
	$\displaystyle=8(a+t^{2})Y_{2}^{2}+8t(a+t^{2})Y_{2}^{3}+(64-a^{2}+t^{4})Y_{2}^{4}-4t(-8+a+t^{2})Y_{2}^{5}$
	$\displaystyle\neq 0,$

which is a contradiction.

$2^{\circ}$ Write $\alpha_{1}=\alpha(Y_{1},Y_{2},t)$ and $\alpha_{2}=\alpha(Y_{1},Y_{2},-t)$ . Let $f,h\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3}]$ be irreducible factors of $G$ of the form

	$\displaystyle f\,$	$\displaystyle=\alpha_{1}\beta_{1}Y_{3}^{i}+\text{lower terms in}\ Y_{3},$
	$\displaystyle h\,$	$\displaystyle=\alpha_{2}\beta_{2}Y_{3}^{j}+\text{lower terms in}\ Y_{3},$

where $\beta_{1},\beta_{2}\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2}]$ . We first claim that $\sigma(f)=f$ . Otherwise, $f\sigma(f)\mid G$ . Since $\sigma(\alpha_{1})=\alpha_{1}$ , it follows that $\alpha_{1}^{2}\mid a_{8}$ , which is a contradiction. In the same way $\sigma(h)=h$ .

Next, we claim that either $f$ or $h$ is cyclic. Otherwise, $ff^{\rho}f^{\rho^{2}}\mid G$ and $hh^{\rho}h^{\rho^{2}}\mid G$ . Then $\deg f\leq 18/3=6$ and $\deg h\leq 6$ . We must have $h\in\{f,f^{\rho},f^{\rho^{2}}\}$ . (Otherwise, $ff^{\rho}f^{\rho^{2}}hh^{\rho}h^{\rho^{2}}\mid G$ , whence $\deg G\geq 6\cdot 4>18$ , which is a contradiction.) If $h=f$ , then $\alpha_{2}\mid\beta_{1}$ . Hence $\deg f\geq\deg(\alpha_{1}\alpha_{2})=8$ , which is a contradiction. If $h=f^{\rho}$ , then $\deg h\geq 4+\deg_{Y_{3}}h=4+\deg_{Y_{2}}f\geq 7$ , which is a contradiction. If $h=f^{\rho^{2}}$ , i.e., $f=h^{\rho}$ , we have $\deg f\geq 7$ , which is also a contradiction. ∎

4. The Case $n=4$

The proof for the case $n=4$ is more complicated but is based on the same approach for the case $n=3$ .

Theorem 4.1.

Let $p\geq 100,018,663$ be a prime and $b\in\mathbb{F}_{p^{4}}$ be such that $\text{\rm Tr}_{p^{4}/p}(b)\neq 0$ . Then $f_{b}$ is not a PR of $\mathbb{F}_{p^{4}}$ . (Note: $100,018,663$ is the $5,762,458$ th prime.)

Proof.

First, by [8, Conjecture 4.1^′], it suffices to show that $f_{1/2}$ is not a PR of $\mathbb{F}_{p^{4}}$ . We have

f_{1/2}(X+Y)-f_{1/2}(X)=\frac{YF(X,Y)}{Z(X)Z(X+Y)},

where

Z(X)=X^{p}-X+\frac{1}{2}

and

(4.1)

F(X,Y)=Z(X)^{2}+(Y^{p}-Y)Z(X)+1-Y^{p-1}\in\mathbb{F}_{p}[X,Y].

It suffices to show that there exists $(x,y)\in\mathbb{F}_{p^{4}}^{2}$ with $y\neq 0$ such that $F(x,y)=0$ . To this end, it suffices show that there exist $\Delta,y\in\mathbb{F}_{p^{4}}$ , with $y\neq 0$ and $\text{Tr}_{p^{4}/p}(\Delta)=2\text{Tr}_{p^{4}/p}(1/2)=4$ , satisfying

(4.2)

\Delta^{2}=y^{2p}+y^{2}-2y^{1+p}+4y^{p-1}-4;

see (3.1) – (3.5).

Assume that such $\Delta$ and $y$ exist, and let $y_{i}=y^{p^{i-1}}$ and $\Delta_{i}=\Delta^{p^{i-1}}$ , $1\leq i\leq 4$ . Then

(4.3)

\Delta_{i}^{2}=y_{i}^{2}+y_{i+1}^{2}-2y_{i}y_{i+1}+4\frac{y_{i+1}}{y_{i}}-4,\quad 1\leq i\leq 4,

where the subscript is taken modulo 4, and

(4.4)

\Delta_{1}+\Delta_{2}+\Delta_{3}+\Delta_{4}=4.

Under the condition (4.4), one can express $\Delta_{1}$ in terms of $\Delta_{1}^{2},\dots,\Delta_{4}^{2}$ as follows:

	$\displaystyle(4-\Delta_{1}-\Delta_{2})^{2}=(\Delta_{3}+\Delta_{4})^{2},$
	$\displaystyle(4-\Delta_{1})^{2}+\Delta_{2}^{2}-2(4-\Delta_{1})\Delta_{2}=\Delta_{3}^{2}+\Delta_{4}^{2}+2\Delta_{3}\Delta_{4},$
	$\displaystyle(16+\Delta_{1}^{2}-8\Delta_{1}+\Delta_{2}^{2}-\Delta_{3}^{2}-\Delta_{4}^{2})^{2}=\bigl{[}2(4-\Delta_{1})\Delta_{2}+2\Delta_{3}\Delta_{4}\bigr{]}^{2},$
	$\displaystyle(16+\Delta_{1}^{2}+\Delta_{2}^{2}-\Delta_{3}^{2}-\Delta_{4}^{2})^{2}+64\Delta_{1}^{2}-16\Delta_{1}(16+\Delta_{1}^{2}+\Delta_{2}^{2}-\Delta_{3}^{2}-\Delta_{4}^{2})$
	$\displaystyle=4\bigl{[}(4-\Delta_{1})^{2}\Delta_{2}^{2}+\Delta_{3}^{2}\Delta_{4}^{2}+2(4-\Delta_{1})\Delta_{2}\Delta_{3}\Delta_{4}\bigr{]},$
	$\displaystyle(16+\Delta_{1}^{2}+\Delta_{2}^{2}-\Delta_{3}^{2}-\Delta_{4}^{2})^{2}+64\Delta_{1}^{2}-16\Delta_{1}(16+\Delta_{1}^{2}+\Delta_{2}^{2}-\Delta_{3}^{2}-\Delta_{4}^{2})$
	$\displaystyle-4(4-\Delta_{1})^{2}\Delta_{2}^{2}-4\Delta_{3}^{2}\Delta_{4}^{2}=8(4-\Delta_{1})\Delta_{2}\Delta_{3}\Delta_{4}.$

Squaring both sides leads to

(4.5)

\Delta_{1}=\frac{A(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})}{32B(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})},

provided $B(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})\neq 0$ , where

	$\displaystyle A(X_{1},X_{2},X_{3},X_{4})$	$\displaystyle=65536+114688X_{1}+\cdots+X_{4}^{4},$
	$\displaystyle B(X_{1},X_{2},X_{3},X_{4})$	$\displaystyle=4096+1792X_{1}+\cdots-X_{4}^{3}.$

In the same way,

(4.6)

\Delta_{i}=\frac{A(\Delta_{i}^{2},\Delta_{i+1}^{2},\Delta_{i+2}^{2},\Delta_{i+3}^{2})}{32B(\Delta_{i}^{2},\Delta_{i+1}^{2},\Delta_{i+2}^{2},\Delta_{i+3}^{2})},\quad 1\leq i\leq 4.

The equation

(4.7)

\Bigl{[}\frac{A(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})}{32B(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})}\Bigr{]}^{2}=\Delta_{1}^{2}

can be written as

(4.8)

\frac{P(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})}{1024B(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})^{2}}=0,

where

P(X_{1},X_{2},X_{3},X_{4})=4294967296-2147483648X_{1}+\cdots+X_{4}^{8}.

Using (4.6), equation (4.4) becomes

(4.9)

\frac{P(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})Q(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})}{16\prod_{i=1}^{4}B(\Delta_{i}^{2},\Delta_{i+1}^{2},\Delta_{i+2}^{2},\Delta_{i+3}^{2})^{2}}=0,

where

Q(X_{1},X_{2},X_{3},X_{4})=-209715-196608\Delta_{1}^{2}+\cdots+\Delta_{4}^{5}.

Using (4.3), we can write

	$\displaystyle P(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})=\,$	$\displaystyle-\frac{2^{16}}{(y_{1}y_{2}y_{3}y_{4})^{8}}G(y_{1},y_{2},y_{3},y_{4}),$
	$\displaystyle B(\Delta_{1}^{2},\Delta_{2}^{2},\Delta_{3}^{2},\Delta_{4}^{2})=\,$	$\displaystyle-\frac{2^{4}}{(y_{1}y_{2}y_{3}y_{4})^{3}}L(y_{1},y_{2},y_{3},y_{4}),$

where

G(Y_{1},Y_{2},Y_{3},Y_{4})=-Y_{1}^{16}Y_{2}^{8}Y_{3}^{8}+16Y_{1}^{15}Y_{2}^{8}Y_{3}^{8}Y_{4}+\cdots+4Y_{1}^{8}Y_{2}^{10}Y_{3}^{12}Y_{4}^{16}

and

L(Y_{1},Y_{2},Y_{3},Y_{4})=4Y_{1}^{6}Y_{2}^{3}Y_{3}^{3}-10Y_{1}^{4}Y_{2}^{3}Y_{3}^{3}Y_{4}-\cdots+Y_{1}^{3}Y_{2}^{3}Y_{3}^{5}Y_{4}^{7}

are cyclic polynomials over $\mathbb{F}_{p}$ of degree 46 and 18, respectively, and $\deg_{Y_{i}}G=16$ , $1\leq i\leq 4$ . More precisely,

(4.10)

G=g_{46}+g_{44}+g_{42}+g_{40}+g_{38}+g_{36}+g_{34}+g_{32},

where $g_{i}\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ is homogeneous of degree $i$ :

(4.11)	$\displaystyle g_{46}=\,$	$\displaystyle-4(Y_{1}Y_{2}Y_{3}Y_{4})^{8}\bigl{[}(Y_{1}-Y_{2})(Y_{2}-Y_{3})(Y_{3}-Y_{4})(Y_{4}-Y_{1})\bigr{]}^{2}$
(4.12)		$\displaystyle\cdot\bigl{[}(Y_{1}-Y_{3})(Y_{2}-Y_{4})\bigr{]}^{2}(Y_{1}-Y_{2}+Y_{3}-Y_{4})^{2},$
(4.13)	$\displaystyle g_{44}=\,$	$\displaystyle(Y_{1}Y_{2}Y_{3}Y_{4})^{6}(Y_{1}^{10}Y_{2}^{6}Y_{3}^{4}-4Y_{1}^{9}Y_{2}^{7}Y_{3}^{4}+\cdots+Y_{2}^{4}Y_{3}^{6}Y_{4}^{10}),$
(4.14)	$\displaystyle g_{42}=\,$	$\displaystyle 2(Y_{1}Y_{2}Y_{3}Y_{4})^{5}(Y_{1}^{11}Y_{2}^{7}Y_{3}^{4}-4Y_{1}^{10}Y_{2}^{8}Y_{3}^{4}+\cdots-Y_{1}^{2}Y_{2}^{2}Y_{3}^{7}Y_{4}^{11}),$
(4.15)	$\displaystyle g_{40}=\,$	$\displaystyle(Y_{1}Y_{2}Y_{3}Y_{4})^{4}(Y_{1}^{12}Y_{2}^{8}Y_{3}^{4}-4Y_{1}^{11}Y_{2}^{9}Y_{3}^{4}+\cdots+Y_{1}^{4}Y_{3}^{8}Y_{4}^{12}),$
(4.16)	$\displaystyle g_{38}=\,$	$\displaystyle 2(Y_{1}Y_{2}Y_{3}Y_{4})^{3}(2Y_{1}^{13}Y_{2}^{8}Y_{3}^{5}-6Y_{1}^{12}Y_{2}^{9}Y_{3}^{5}+\cdots-2Y_{1}^{5}Y_{2}^{2}Y_{3}^{6}Y_{4}^{13}),$
(4.17)	$\displaystyle g_{36}=\,$	$\displaystyle 2(Y_{1}Y_{2}Y_{3}Y_{4})^{2}(3Y_{1}^{14}Y_{2}^{8}Y_{3}^{6}-6Y_{1}^{13}Y_{2}^{9}Y_{3}^{6}+\cdots+3Y_{1}^{6}Y_{2}^{4}Y_{3}^{4}Y_{4}^{14}),$
(4.18)	$\displaystyle g_{34}=\,$	$\displaystyle 4Y_{1}Y_{2}Y_{3}Y_{4}(Y_{1}^{15}Y_{2}^{8}Y_{3}^{7}-Y_{1}^{14}Y_{2}^{9}Y_{3}^{7}+\cdots-Y_{1}^{7}Y_{2}^{6}Y_{3}^{2}Y_{4}^{15}),$
(4.19)	$\displaystyle g_{32}=\,$	$\displaystyle Y_{1}^{16}Y_{2}^{8}Y_{3}^{8}-16Y_{1}^{15}Y_{2}^{8}Y_{3}^{8}Y_{4}-\cdots+Y_{1}^{8}Y_{2}^{8}Y_{4}^{16}.$

Later, we will use the fact that

(4.20)

\text{gcd}(G,L)=1.

This fact follows from the computation that

	$\displaystyle\text{Res}(G(1,1,Y_{3},Y_{4}),L(1,1,Y_{3},Y_{4});Y_{4})$
	$\displaystyle=2^{112}(-1+Y_{3})^{8}Y_{3}^{56}(3+Y_{3})^{8}(-19+2Y_{3}+Y_{3}^{2})^{8}(-1+8Y_{3}-26Y_{3}^{2}+3Y_{3}^{4})^{4}$
	$\displaystyle\kern 10.00002pt\cdot(-16+11Y_{3}+88Y_{3}^{2}-16Y_{3}^{3}-98Y_{3}^{4}+5Y_{3}^{5}+10Y_{3}^{6})^{4}$
	$\displaystyle\kern 10.00002pt\cdot(16+8Y_{3}-204Y_{3}^{2}+369Y_{3}^{3}+30Y_{3}^{4}-76Y_{3}^{5}-2Y_{3}^{6}+3Y_{3}^{7})^{4}$
	$\displaystyle\kern 10.00002pt\cdot(256+672Y_{3}+505Y_{3}^{2}-4456Y_{3}^{3}+5718Y_{3}^{4}-364Y_{3}^{5}-1139Y_{3}^{6}$
	$\displaystyle\kern 16.99998pt+52Y_{3}^{7}+52Y_{3}^{8})^{2}(-256-256Y_{3}+832Y_{3}^{2}+672Y_{3}^{3}-1056Y_{3}^{4}$
	$\displaystyle\kern 16.99998pt-392Y_{3}^{5}+431Y_{3}^{6}+76Y_{3}^{7}-66Y_{3}^{8}-4Y_{3}^{9}+3Y_{3}^{10})^{2}$
	$\displaystyle\neq 0.$

To prove the theorem, it suffice to show that there exists $y\in\mathbb{F}_{p^{4}}$ such that $G(y,y^{p},y^{p^{2}},y^{p^{3}})=0$ but $L(y,y^{p},y^{p^{2}},y^{p^{3}})\neq 0$ . Once this is done, the proof of the theorem is completed as follows: Clearly, $y\neq 0$ . Let $y_{i}=y^{p^{i-1}}$ , $1\leq i\leq 4$ . Let $\Delta_{i}$ ( $1\leq i\leq 4$ ) be given by (4.6) and in (4.6) let $\Delta_{i}^{2}$ be given by (4.3), whence $\Delta_{i}$ is defined in terms of $y_{1},\dots,y_{4}$ . For $\Delta_{i}$ so defined, (4.8) and (4.9) are satisfied. Let $\Delta=\Delta_{1}$ . From (4.8) we have (4.7) and hence (4.2); from (4.9) we have (4.4), i.e., $\text{Tr}_{p^{4}/p}(\Delta)=4$ .

Choose $z\in\mathbb{F}_{p^{4}}$ such that $M(z)$ is invertible and let

G_{1}=G((Y_{1},Y_{2},Y_{3},Y_{4})M(z)).

By Lemma 4.2 below, $G$ has a cyclic absolutely irreducible factor $d\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ . Then $d_{1}=d((Y_{1},Y_{2},Y_{3},Y_{4})M(z))\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ is a cyclic absolutely irreducible factor of $G_{1}$ . By [4, Theorem 5.2],

	$\displaystyle\|V_{\mathbb{F}_{p}^{4}}(d_{1})\|\,$	$\displaystyle\geq p^{2}-(46-1)(46-2)p^{3/2}-5\cdot 46^{13/3}p$
		$\displaystyle=p^{2}-1980p^{3/2}-5\cdot 46^{13/3}p.$

Let $L_{1}=L((Y_{1},Y_{2},Y_{3},Y_{4})M(z))$ . By (4.20), $\text{gcd}(G_{1},L_{1})=1$ . Then by [4, Lemma 2.2],

|V_{\mathbb{F}_{p}^{4}}(G_{1})\cap V_{\mathbb{F}_{p}^{4}}(L_{1})|\leq 46^{2}p.

Hence

	$\displaystyle\|V_{\mathbb{F}_{p}^{4}}(G_{1})\setminus V_{\mathbb{F}_{p}^{4}}(L_{1})\|\,$	$\displaystyle\geq\|V_{\mathbb{F}_{p}^{4}}(d_{1})\|-\|V_{\mathbb{F}_{p}^{4}}(G_{1})\cap V_{\mathbb{F}_{p}^{4}}(L_{1})\|$
		$\displaystyle\geq p^{2}-1980p^{3/2}-(5\cdot 46^{13/3}+46^{2})p$
		$\displaystyle=p(p-1980p^{1/2}-(5\cdot 46^{13/3}+46^{2}))$
		$\displaystyle>0$

since

p\geq 100,018,663>100,018,659\approx\frac{1}{4}\bigl{[}1980+(1980^{2}+4(5\cdot 46^{13/3}+46^{2}))^{1/2}\bigr{]}^{2}.

Let $(a_{1},a_{2},a_{3},a_{4})\in V_{\mathbb{F}_{p}^{4}}(G_{1})\setminus V_{\mathbb{F}_{p}^{4}}(L_{1})$ and let $y=a_{1}z+a_{2}z^{p}+a_{3}z^{p^{2}}+a_{4}z^{p^{3}}\in\mathbb{F}_{p^{4}}$ . Then $G(y,y^{p},y^{p^{2}},y^{p^{3}})=0$ but $L(y,y^{p},y^{p^{2}},y^{p^{3}})\neq 0$ . ∎

Lemma 4.2.

The polynomial $G$ in (4.10) has a cyclic absolutely irreducible factor in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

Proof.

Throughout this proof, $\rho$ denotes the cyclic shift $(Y_{1},Y_{2},Y_{3},Y_{4})\mapsto(Y_{2},Y_{3},Y_{4},Y_{1})$ and $\sigma\in\text{Aut}(\overline{\mathbb{F}}_{p})$ is the Frobenius map $(\ )\mapsto(\ )^{p}$ . For any $f\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ , $f_{i}$ denotes the homogenous component of degree $i$ in $f$ . For $f=f_{i}+f_{i-1}+\cdots$ with $f_{i}\neq 0$ , let $\bar{f}=f_{i}+f_{i-1}X+\cdots\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4},X]$ be the homogenization of $f$ and let $\tilde{f}=\bar{f}(Y_{1},Y_{2},Y_{3},Y_{4},-1)=f_{i}-f_{i-1}+f_{i-2}-\cdots$ . Since $\overline{G}=g_{46}+g_{44}X^{2}+\cdots+g_{32}X^{14}$ , we have $\widetilde{G}=G$ . Therefore, if $f\mid G$ , then $\bar{f}\mid\overline{G}$ , whence $\tilde{f}\mid\widetilde{G}$ , i.e., $\tilde{f}\mid G$ .

$1^{\circ}$ Let $y_{1},y_{2},y_{3}$ be independent indeterminates and let $y_{4}$ be a root of $G(y_{1},y_{2},y_{3},Y_{4})$ . We claim that $4\mid[\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3},y_{4}):\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3})]$ . Let $\Delta_{i}$ , in terms of $y_{1},\dots,y_{4}$ , be given by (4.6) and (4.3). Then (4.3) is satisfied. By (4.3), $\Delta_{1}^{2},\Delta_{2}^{2}\in\mathbb{F}_{p}(y_{1},y_{2},y_{3})$ and it is easy to see that $\Delta_{1}^{2}$ , $\Delta_{2}^{2}$ and $\Delta_{1}^{2}\Delta_{2}^{2}$ are all nonsquares in $\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3})$ . It follows that

[\overline{\mathbb{F}}_{p}(y_{1},y_{2},\Delta_{1},\Delta_{2}):\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3})]=4.

Hence the claim. (A more general fact which is easily proved by induction: If $F$ is a field with $\text{char}\,F\neq 2$ and $u_{1},\dots,u_{n}\in F$ are such that for every $\emptyset\neq I\subset\{1,\dots,n\}$ , $\prod_{i\in I}u_{i}$ is a nonsquare in $F$ , then $[F(\sqrt{u_{1}},\dots,\sqrt{u_{n}}):F]=2^{n}$ and $\text{Aut}(F(\sqrt{u_{1}},\dots,\sqrt{u_{n}})/F)\cong(\mathbb{Z}/2\mathbb{Z})^{n}$ .)

..................................................................................................................

\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3})

\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3},\Delta_{1},\Delta_{2})

\overline{\mathbb{F}}_{p}(y_{1},y_{2},y_{3},y_{4})

\scriptstyle 4

$2^{\circ}$ We claim that $g_{32}$ has no factors with multiplicity $>1$ . This claim follows from the following computation:

	$\displaystyle\text{Res}\Bigl{(}g_{32}(1,-1,Y_{3},Y_{4}),\,\frac{\partial}{\partial Y_{4}}g_{32}(1,-1,Y_{3},Y_{4});\,Y_{4}\Bigr{)}$
	$\displaystyle=2^{256}\cdot 3^{8}\,Y_{3}^{148}(1-Y_{3})^{8}(1+Y_{3})^{8}\cdots(65536+245760Y_{3}-\cdots+Y_{3}^{12})$
	$\displaystyle\neq 0.$

$3^{\circ}$ We claim that if $f\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ is an irreducible factor of $G$ , then $\tilde{f}=f$ . Assume the contrary. Then $f\tilde{f}\mid G$ . Write $f=f_{i}+f_{i-1}+\cdots+f_{i-s}$ , where $f_{i}f_{i-s}\neq 0$ . By $1^{\circ}$ , $i\geq 4$ . Note that $\tilde{f}=f_{i}-f_{i-1}+\cdots+(-1)^{s}f_{i-s}$ . It follows that $f_{i-s}^{2}\mid g_{32}$ . By $2^{\circ}$ , we have $i-s=0$ , that is, $f=1+f_{1}+\cdots+f_{i}$ . We have

G(Y_{1},Y_{2},Y_{1},Y_{2})=-2^{8}(Y_{1}Y_{2})^{12}\alpha(Y_{1},Y_{2})\alpha(Y_{2},Y_{1})\beta(Y_{1},Y_{2})^{2}\beta(Y_{2},Y_{1})^{2},

where

	$\displaystyle\alpha(Y_{1},Y_{2})\,$	$\displaystyle=Y_{1}^{2}-Y_{1}Y_{2}+Y_{1}^{2}Y_{2}+Y_{2}^{2}-Y_{1}Y_{2}^{2},$
	$\displaystyle\beta(Y_{1},Y_{2})\,$	$\displaystyle=4Y_{1}-8Y_{2}+Y_{1}^{2}Y_{2}-2Y_{1}Y_{2}^{2}+Y_{2}^{3}.$

It is easy to see see that $\alpha$ and $\beta$ are irreducible in $\overline{\mathbb{F}}_{p}[Y_{1},Y_{2}]$ . (The discriminants of $\alpha$ and $\beta$ , as polynomials in $Y_{1}$ , are $Y_{2}^{2}(-3+Y_{2})(1+Y_{2})$ and $16(1+Y_{2}^{2})$ , respectively. These are nonsquares in $\overline{\mathbb{F}}_{p}(Y_{2})$ .) Therefore $G(Y_{1},Y_{2},Y_{1},Y_{2})$ does not have any nonconstant factor with nonzero constant term. It follows that $f(Y_{1},Y_{2},Y_{1},Y_{2})=1$ . Then

42=\deg G(Y_{1},Y_{2},Y_{1},Y_{2})\leq\deg(G/f\tilde{f})\leq 46-2i\leq 46-8=38,

which is a contradiction.

$4^{\circ}$ We claim that if $f$ is a pseudo-cyclic absolutely irreducible factor of $G$ , then $f$ is cyclic. We have $f^{\rho}=cf$ , where $c\in\overline{\mathbb{F}}_{p}^{*}$ . Let $h=G/f$ . By $3^{\circ}$ , $f=f_{i}+f_{i-2}+\cdots$ ( $f_{i}\neq 0$ ) and hence $h=h_{j}+h_{j-2}+\cdots$ ( $h_{j}\neq 0$ ). Then $f_{i}h_{j}=g_{46}$ . Since $f_{i}\mid g_{46}$ and $f_{i}^{\rho}=cf_{i}$ , it follows from (4.11) that

	$\displaystyle f_{i}=\,$	$\displaystyle d(Y_{1}Y_{2}Y_{3}Y_{4})^{i_{1}}\bigl{[}(Y_{1}-Y_{2})(Y_{2}-Y_{3})(Y_{3}-Y_{4})(Y_{4}-Y_{1})\bigr{]}^{i_{2}}$
		$\displaystyle\cdot\bigl{[}(Y_{1}-Y_{3})(Y_{2}-Y_{4})\bigr{]}^{i_{3}}(Y_{1}-Y_{2}+Y_{3}-Y_{4})^{i_{4}},$

where $d\in\overline{\mathbb{F}}_{p}^{*}$ , $0\leq i_{1}\leq 8$ , $0\leq i_{2},i_{3},i_{4}\leq 2$ . Thus $f_{i}^{\rho}=\pm f_{i}$ . If $f_{i}^{\rho}=-f_{i}$ , it follows from $f_{i}h_{j}=g_{46}$ that either $(Y_{1}-Y_{3})(Y_{2}-Y_{4})$ or $Y_{1}-Y_{2}+Y_{3}-Y_{4}$ divides both $f_{i}$ and $h_{j}$ . Then $g_{44}=f_{i}h_{j-2}+f_{i-2}h_{j}$ is divisible by $(Y_{1}-Y_{3})(Y_{2}-Y_{4})$ or $Y_{1}-Y_{2}+Y_{3}-Y_{4}$ , which is a contradiction.

$5^{\circ}$ We claim that $G$ cannot be written as $G=cff^{\prime}hh^{\prime}$ , where $c\in\overline{\mathbb{F}}_{p}^{*}$ , $f,g\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ are irreducible or equal to $1$ . $f^{\prime}=f^{\rho}$ or $\sigma(f)$ , and $h^{\prime}=h^{\rho}$ or $\sigma(h)$ . Otherwise, by $3^{\circ}$ , $f=f_{i}+f_{i-2}+\cdots+f_{i-2s}$ and $h=h_{j}+h_{j-2}+\cdots+h_{j-2t}$ , where $f_{i}f_{i-2s}h_{j}h_{j-2t}\neq 0$ . Since $G=g_{46}+\cdots+g_{32}$ , we have $2(i+j)=46$ and $2(i-2s+j-2t)=32$ , which is impossible.

$6^{\circ}$ Let

k=\min\bigl{\{}\deg_{Y_{i}}f:f\in\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]\ \text{is irreducible},\ f\mid G,\ 1\leq i\leq 4\Bigr{\}}.

We may assume that $k=\deg_{Y_{4}}f$ for some irreducible factor $f$ of $G$ in $\overline{\mathbb{F}}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ . Clearly, $G$ does not have any nontrivial factor in $\overline{\mathbb{F}}_{p}^{[}Y_{1},Y_{2},Y_{3}]$ , so $k>0$ . By $1^{\circ}$ , we have $k\in\{4,8,16\}$ . Let $l$ be the smallest integer such that $f\in\mathbb{F}_{p^{l}}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

Case 1. Assume that $k=16$ . Then $G=f$ and we are done.

Case 2. Assume that $k=8$ . We claim that $f$ cyclic. Otherwise, by $4^{\circ}$ , $f$ is not pseudo-cyclic. Then $ff^{\rho}\mid G$ . Since $\deg_{Y_{4}}(ff^{\rho})\geq 8+8=16$ , we have $G=cff^{\rho}$ for some $c\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ . Hence the claim is proved.

If $l>1$ , then $G=d\,f\sigma(f)$ for some $d\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ . Hence $l=1$ , i.e., $f\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

Case 3. Assume that $k=4$ . We first claim that $f^{\rho^{2}}=cf$ for some $c\in\overline{\mathbb{F}}_{p}^{*}$ . Otherwise, $ff^{\rho}f^{\rho^{2}}f^{\rho^{3}}\mid G$ . Since $\deg_{Y_{4}}(ff^{\rho}f^{\rho^{2}}f^{\rho^{3}})\geq 4\cdot 4=\deg_{Y_{4}}G$ , we have $G=d\,ff^{\rho}f^{\rho^{2}}f^{\rho^{3}}$ for some $d\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ . So the claim is proved. Write $f=f_{i}+f_{i-2}+\cdots$ , where $f_{i}\neq 0$ . Since $f_{i}\mid g_{46}$ and $f_{i}^{\rho^{2}}=cf_{i}$ , we have $c=1$ , so $f^{\rho^{2}}=f$ .

Case 3.1. Assume that $f$ is cyclic. Since $f\sigma(f)\cdots\sigma^{l-1}(f)\mid G$ , we have $4l\leq\deg_{Y_{4}}G=16$ , i.e., $l\leq 4$ .

If $l=1$ , then $f$ is a cyclic absolutely irreducible factor of $G$ in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ , and we are done.

If $l=4$ , then $G=ef\sigma(f)\sigma^{2}(f)\sigma^{3}(f)$ for some $e\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ .

If $l=3$ , $G/f\sigma(f)\sigma^{2}(f)$ is a cyclic absolutely irreducible factor of $G$ in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ , and we are done.

If $l=2$ , then $H:=G/f\sigma(f)$ is cyclic and belongs to $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ . If $H$ is absolutely irreducible, we are done. So assume that $H$ has a proper absolutely irreducible factor $h$ . By the minimality of $k$ , we have $\deg_{Y_{4}}h=4$ . If $h$ is not pseudo-cyclic, then $hh^{\rho}\mid H$ , whence $G=\epsilon f\sigma(f)hh^{\rho}$ for some $\epsilon\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ . Therefore $h$ is pseudo-cyclic and hence cyclic (by $4^{\circ}$ ). If $\sigma(h)/h$ is not a constant, we have $h\sigma(h)\mid H$ , which leads to the same contradiction. Thus $\sigma(h)/h$ is a constant. We may assume that $\sigma(h)=h$ . Now $h$ is a cyclic absolutely irreducible factor of $G$ in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

Case 3.2. Assume that $f$ is not cyclic. By $4^{\circ}$ , $f$ is not pseudo-cyclic. Then $ff^{\rho}$ is a cyclic factor of $G$ . We claim that $\sigma(ff^{\rho})/ff^{\rho}$ is a constant. (Otherwise, $f$ , $f^{\rho}$ , $\sigma(f)$ and $\sigma(f^{\rho})$ are different factors of $G$ . Then $G=eff^{\rho}\sigma(f)\sigma(f^{\rho})$ for some $e\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ .) We may assume that $ff^{\rho}\in\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ . Let $H=G/ff^{\rho}$ , which is cyclic and belongs to $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ . By $5^{\circ}$ , $H$ is not a constant. Let $h$ be an absolutely irreducible factor of $H$ . By the minimality of $k$ , $\deg_{Y_{4}}h\geq 4$ . If $h$ is not cyclic, then $hh^{\rho}\mid H$ . Thus $G=\epsilon ff^{\rho}hh^{\rho}$ for some $\epsilon\in\overline{\mathbb{F}}_{p}^{*}$ , which is impossible by $5^{\circ}$ . So $h$ is cyclic. If $\sigma(h)/h$ is not a constant, then $h\sigma(h)\mid H$ , which leads to the same contradiction. So $\sigma(h)/h$ is a constant, and we may assume that $\sigma(h)=h$ . Now $h$ is a cyclic absolutely irreducible factor of $G$ in $\mathbb{F}_{p}[Y_{1},Y_{2},Y_{3},Y_{4}]$ .

The proof of the lemma is now complete. ∎

Acknowledgment

The research of D. Bartoli was supported by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INdAM).

References

[1] D. Bartoli, On a conjecture about a class of permutation trinomials, Finite Fields Appl. 52 (2018), 30 – 50.
[2] D. Bartoli, Permutation trinomials over $\mathbb{F}_{q^{3}}$ , Finite Fields Appl. 61 (2020), Article 101597.
[3] D. Bartoli and M. Giulietti, Permutation polynomials, fractional polynomials, and algebraic curves, Finite Fields Appl. 51 (2018), 1 – 16.
[4] A. Cafure and G. Matera, Improved explicit estimates on the number of solutions of equations over a finite field, Finite Fields Appl. 12 (2006), 155 – 185.
[5] X. Cao, X. Hou, J. Mi, S. Xu, More permutation polynomials with Niho exponents which permute $\mathbb{F}_{p^{2}}$ , Finite Fields Appl. 62 (2020), Article 101626.
[6] X. Hou, On a class of permutation trinomials in characteristic 2, Cryptography and Communications, 11 (2019), 1199 – 1210.
[7] X. Hou, On the Tu-Zeng Permutation Trinomial of Type $(1/4,3/4)$ , arXiv:1906.07240.
[8] X. Hou and Sze, On a type of permutation rational functions over finite fields, arXiv:1910.11989.
[9] X. Hou, Z. Tu, X. Zeng, Determination of a class of permutation trinomials in characteristic three, Finite Fields Appl. 61 (2020), Article 101596.
[10] S. Lang and A. Weil, Number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819 – 827.
[11] K. Li, L. Qu, C. Li, S. Fu, New permutation trinomials constructed from fractional polynomials, Acta Arith. 183 (2018), 101 – 116.
[12] Z. Tu and X. Zeng, Two classes of permutation trinomials with Niho exponents, Finite Fields Appl. 53 (2018), 99 – 112.
[13] Z. Tu, X. Zeng, C. Li, T. Helleseth, A class of new permutation trinomials, Finite Fields Appl. 50 (2018), 178 – 195.
[14] Q. Wang, Polynomials over finite fields: an index approach, In: Combinatorics and Finite Fields, Editors: K-U. Schmidt and A. Winterhof, De Gruyter, 2019, pp. 319 – 348.
[15] J. Yuan, C. Ding, H. Wang, J. Pieprzyk, Permutation polynomials of the form $(x^{p}-x+\delta)^{s}+L(x)$ , Finite Fields Appl. 14 (2008), 482 – 493.
[16] M. E. Zieve, On some permutation polynomials over $\mathbb{F}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$ , Proc. Amer. Math. Soc. 137 (2009), 2209 – 2216.

on a conjecture on permutation rational functions over finite fields

Abstract.

Key words and phrases:

2010 Mathematics Subject Classification:

1. Background

2. Cyclic Shift and the Forbenius

Lemma 2.1.

Proof.

3. The Case n=3n=3

Theorem 3.1.

Proof.

Lemma 3.2.

Proof.

4. The Case n=4n=4

Theorem 4.1.

Proof.

Lemma 4.2.

Proof.

Acknowledgment

References

3. The Case $n=3$

4. The Case $n=4$