Citation: Kaimin Cheng. Permutational behavior of reversed Dickson polynomials over finite fields[J]. AIMS Mathematics, 2017, 2(2): 244-259. doi: 10.3934/Math.2017.2.244
[1] | Kaimin Cheng . Permutational behavior of reversed Dickson polynomials over finite fields II. AIMS Mathematics, 2017, 2(4): 586-609. doi: 10.3934/Math.2017.4.586 |
[2] | Xiaoer Qin, Li Yan . Some specific classes of permutation polynomials over Fq3. AIMS Mathematics, 2022, 7(10): 17815-17828. doi: 10.3934/math.2022981 |
[3] | Varsha Jarali, Prasanna Poojary, G. R. Vadiraja Bhatta . A recent survey of permutation trinomials over finite fields. AIMS Mathematics, 2023, 8(12): 29182-29220. doi: 10.3934/math.20231495 |
[4] | Qian Liu, Jianrui Xie, Ximeng Liu, Jian Zou . Further results on permutation polynomials and complete permutation polynomials over finite fields. AIMS Mathematics, 2021, 6(12): 13503-13514. doi: 10.3934/math.2021783 |
[5] | Weihua Li, Chengcheng Fang, Wei Cao . On the number of irreducible polynomials of special kinds in finite fields. AIMS Mathematics, 2020, 5(4): 2877-2887. doi: 10.3934/math.2020185 |
[6] | Sami Alabiad, Yousef Alkhamees . On classification of finite commutative chain rings. AIMS Mathematics, 2022, 7(2): 1742-1757. doi: 10.3934/math.2022100 |
[7] | Xiaofan Xu, Yongchao Xu, Shaofang Hong . Some results on ordinary words of standard Reed-Solomon codes. AIMS Mathematics, 2019, 4(5): 1336-1347. doi: 10.3934/math.2019.5.1336 |
[8] | Turki Alsuraiheed, Elif Segah Oztas, Shakir Ali, Merve Bulut Yilgor . Reversible codes and applications to DNA codes over F42t[u]/(u2−1). AIMS Mathematics, 2023, 8(11): 27762-27774. doi: 10.3934/math.20231421 |
[9] | Guanghui Zhang, Shuhua Liang . On the construction of constacyclically permutable codes from constacyclic codes. AIMS Mathematics, 2024, 9(5): 12852-12869. doi: 10.3934/math.2024628 |
[10] | Zhen Du, Chuanze Niu . Weight distributions of a class of skew cyclic codes over M2(F2). AIMS Mathematics, 2025, 10(5): 11435-11443. doi: 10.3934/math.2025520 |
Permutation polynomials and Dickson polynomials are two of the most important topics in the area of finite fields. Let Fq be the finite field of characteristic p with q elements. Let Fq[x] be the ring of polynomials over Fq in the indeterminate x. If the polynomial f(x)∈Fq[x] induces a bijective map from Fq to itself, then f(x)∈Fq[x] is called a permutation polynomial of Fq. Properties, constructions and applications of permutation polynomials may be found in [4], [5] and [6]. Associated to any integer n≥0 and a parameter a∈Fq, the n-th Dickson polynomials of the first kind and of the second kind, denoted by Dn(x,a) and En(x,a), are defined for n≥1 by
Dn(x,a):=∑[n2]i=0nn−i(n−ii)(−a)ixn−2i |
and
En(x,a):=∑[n2]i=0(n−ii)(−a)ixn−2i, |
respectively, and D0(x,a):=2,E0(x,a):=1. It is well known that Dn(x,0) is a permutation polynomial of Fq if and only if gcd(n,q−1)=1, and if a≠0, then Dn(x,a) induces a permutation of Fq if and only if gcd(n,q2−1)=1. There are lots of published results on permutational properties of Dickson polynomial En(x,a) of the second kind (see, for example, [1]).
The reversed Dickson polynomial of the first kind, denoted by Dn(a,x), was introduced in [3] and defined as follows
Dn(a,x):=∑[n2]i=0nn−i(n−ii)(−x)ian−2i |
if n≥1 and D0(a,x)=2, where [n2] means the largest integer no more than n2. Wang and Yucas [7] extended this concept to that of the n-th reversed Dickson polynomial of (k+1)-th kind Dn,k(a,x)∈Fq[x], which is defined for n≥1 by
Dn,k(a,x):=∑[n2]i=0n−kin−i(n−ii)(−x)ian−2i | (1.1) |
and D0,k(a,x)=2−k. Some families of permutation polynomials from the revered Dickson polynomials of the first kind were obtained in [3]. Hong, Qin and Zhao [2] studied the revered Dickson polynomial En(a,x) of the second kind that is defined for n≥1 by
En(a,x):=∑[n2]i=0(n−ii)(−x)ian−2i |
and E0(a,x)=1. In fact, they gave some necessary conditions for the revered Dickson polynomial En(1,x) of the second kind to be a permutation polynomial of Fq. Regarding the revered Dickson polynomial Dn,2(a,x)∈Fq[x] of the third kind, from its definition one can derive that
Dn,2(a,x)=aEn−1(a,x) | (1.2) |
for each x∈Fq. Using (1.2), one can deduce immediately from [2] the similar results on the permutational behavior of the reversed Dickson polynomial Dn,2(a,x) of the third kind.
In this paper, our main goal is to develop the method presented by Hong, Qin and Zhao in [2] to investigate the reversed Dickson polynomial Dn,k(a,x) of the (k+1)-th kind which is defined by (1.1) if n≥1 and D0,k(a,x):=2−k. For a≠0, we write x=y(a−y) with an indeterminate y≠a2. Then one can rewrite Dn,k(a,x) as
Dn,k(a,x)=((k−1)a−(k−2)y)yn−(a+(k−2)y)(a−y)n2y−a. | (1.3) |
We have
Dn,k(a,a24)=(kn−k+2)an2n. | (1.4) |
In fact, (1.3) and (1.4) follow from Theorem 2.2 (ⅰ) and Theorem 2.4 (ⅰ) below. It is easy to see that if char(Fq)=2, then Dn,k(a,x)=En(a,x) if k is odd and Dn,k(a,x)=Dn(a,x) if k is even. We also find that Dn,k(a,x)=Dn,k+p(a,x), so we can restrict p>k. Thus we always assume p=char(Fq)≥3 in what follows.
The paper is organized as follows. First in section 2, we study the properties of the reversed Dickson polynomial Dn,k(a,x) of the (k+1)-th kind. Subsequently, in Section 3, we prove a necessary condition for the reversed Dickson polynomial Dn,k(1,x) of the (k+1)-th kind to be a permutation polynomial of Fq and then introduce an auxiliary polynomial to present a characterization for Dn,k(1,x) to be a permutation of Fq. From the Hermite criterion [4] one knows that a function f:Fq→Fq is a permutation polynomial of Fq if and only if the i-th moment
∑a∈Fqf(a)i={0,if 0≤i≤q−2,−1,if i=q−1. |
Thus to understand well the permutational behavior of the reversed Dickson polynomial Dn,k(1,x) of the (k+1)-th kind, we would like to know if the i-th moment ∑a∈FqDn,k(1,a)i is computable. We are able to treat with this sum when i=1. The final section is devoted to the computation of the first moment ∑a∈FqDn,k(1,a).
In this section, we study the properties of the reversed Dickson polynomials Dn,k(a,x) of the (k+1)-th kind. Clearly, if a=0, then
Dn,k(0,x)={0,if n is odd,(−1)n2+1(k−2)xn2,if n is even. |
Therefore, Dn,k(0,x) is a PP (permutation polynomial) of Fq if and only if n is an even integer with gcd(n2,q−1)=1. In what follows, we always let a∈F∗q. First, we give a basic fact as follows.
Lemma 2.1. [4] Let f(x)∈Fq[x]. Then f(x) is a PP of Fq if and only if cf(dx) is a PP of Fq for any given c,d∈F∗q.
Then we can deduce the following result.
Theorem 2.2. Let a,b∈F∗q. Then the following are true.
(ⅰ). One has Dn,k(a,x)=anbnDn,k(b,b2a2x).
(ⅱ). We have that Dn,k(a,x) is a PP of Fq if and only if Dn,k(1,x) is a PP of Fq.
Proof. (ⅰ). By the definition of Dn,k(a,x), we have
anbnDn,k(b,b2a2x)=anbn∑[n2]i=0n−kin−i(n−ii)(−1)ibn−2ib2ia2ixi=∑[n2]i=0n−kin−i(n−ii)(−1)ian−2ixi=Dn,k(a,x) |
as required. Part (ⅰ) is proved.
(ⅱ). Taking b=1 in part (ⅰ), we have
Dn,k(a,x)=anDn,k(1,xa2). |
It then follows from Lemma 2.1 that Dn,k(a,x) is a PP of Fq if and only if Dn,k(1,x) is a PP of Fq. This completes the proof of part (ⅱ). So Theorem 2.2 is proved.
Theorem 2.2 tells us that to study the permutational behavior of Dn,k(a,x) over Fq, one only needs to consider that of Dn,k(1,x). In the following, we supply several basic properties on the reversed Dickson polynomial Dn,k(1,x) of the (k+1)-th kind. The following result is given in [2].
Lemma 2.3. [2] Let n≥0 be an integer. Then
Dn(1,x(1−x))=xn+(1−x)n |
and
En(1,x(1−x))=xn+1−(1−x)n+12x−1 |
if x≠12.
Theorem 2.4. Each of the following is true.
(ⅰ). For any integer n≥0, we have
Dn,k(1,14)=kn−k+22n |
and
Dn,k(1,x)=(k−1−(k−2)y)yn−(1+(k−2)y)(1−y)n2y−1 |
if x=y(1−y)≠14.
(ⅱ). If n1 and n2 are positive integers such that n1≡n2(modq2−1), then one has Dn1,k(1,x0)=Dn2,k(1,x0) for any x0∈Fq∖{14}.
Proof. (ⅰ). First of all, it is easy to see that D0,k(1,14)=2−k=k×0−k+220 and D1,k(1,14)=1=k×1−k+221. the first identity is true for the cases that n=0 and 1. Now let n≥2. Then one has
Dn,k(1,14)=∑[n2]i=0n−kin−i(n−ii)(−14)i=∑[n2]i=0n−(k−1)in−i(n−ii)(−14)i+∑[n2]i=0−in−i(n−ii)(−14)i=Dn,k−1(1,14)+14∑[n2]−1i=0(n−2−ii)(−14)i=Dn,k−1(1,14)+14En−2(1,14), |
which follows from Theorem 2.2 (1) in [2] that
Dn,k(1,14)=Dn,1(1,14)+(k−1)14En−2(1,14)=n+12n+(k−1)n−(k−1)2n=kn−k+22n |
as desired. So the first identity is proved.
Now we turn our attention to the second identity. Let x≠14, then there exists y∈Fq2∖{12} such that x=y(1−y). So by the definition of the n-th reversed Dickson polynomial of the (k+1)-th kind, one has
Dn,k(1,y(1−y))=∑[n2]i=0n−kin−i(n−ii)(−y(1−y))i=∑[n2]i=0k(n−i)−knn−i(n−ii)(−y(1−y))i=k∑[n2]i=0(n−ii)(−y(1−y))i−(k−1)∑[n2]i=0nn−i(n−ii)(−y(1−y))i=kEn(1,y(1−y))−(k−1)Dn(1,y(1−y)). | (2.1) |
But Lemma 2.3 gives us that
Dn(1,y(1−y))=yn+(1−y)n | (2.2) |
and
En(1,y(1−y))=∑ni=0yn−i(1−y)i=yn+1−(1−y)n+12y−1. | (2.3) |
Thus it follows from (2.1) to (2.3) that
Dn,k(1,x)=Dn,k(1,y(1−y))=kEn(1,y(1−y))−(k−1)Dn(1,y(1−y))=kyn+1−k(1−y)n+12y−1−(k−1)(yn+(1−y)n)=(k−1−(k−2)y)yn−(1+(k−2)y)(1−y)n2y−1 |
as required. So the second identity holds. Part (ⅰ) is proved.
(ⅱ). For each x0∈Fq∖{14}, one can choose an element y0∈Fq2∖{12} such that x0=y0(1−y0). Since n1≡n2(modq2−1), one has yn10=yn20 and (1−y0)n1=(1−y0)n2. It then follows from part (ⅰ) that
Dn1,k(1,x0)=Dn1,k(1,y0(1−y0))=(k−1−(k−2)y0)yn10−(1+(k−2)y0)(1−y0)n12y0−1=(k−1−(k−2)y0)yn20−(1+(k−2)y0)(1−y0)n22y0−1=Dn2,k(1,x0) |
as desired. This ends the proof of Theorem 2.4.
Evidently, by Theorem 2.2 (ⅰ) and Theorem 2.4 (ⅰ) one can derive that (1.3) and (1.4) are true.
Proposition 2.5. Let n≥2 be an integer. Then the recursion
Dn,k(1,x)=Dn−1,k(1,x)−xDn−2,k(1,x) |
holds for any x∈Fq.
Proof. We consider the following two cases.
CASE 1. x≠14. For this case, one may let x=y(1−y) with y∈Fq2∖{12}. Then by Theorem 2.4 (ⅰ), we have
Dn−1,k(1,x)−xDn−2,k(1,x)=Dn−1,k(1,y(1−y))−y(1−y)Dn−2,k(1,y(1−y))=(k−1−(k−2)y)yn−1−(1+(k−2)y)(1−y)n−12y−1 −y(1−y)(k−1−(k−2)y)yn−2−(1+(k−2)y)(1−y)n−22y−1=(k−1−(k−2)y)yn−(1+(k−2)y)(1−y)n2y−1=Dn,k(1,x) |
as required.
CASE 2. x=14. Then by Theorem 2.4 (ⅰ), we have
Dn−1,k(1,14)−14Dn−2,k(1,14)=k(n−1)−k+22n−1−14k(n−2)−k+22n−2=kn−k+22n=Dn,k(1,14). |
This concludes the proof of Proposition 2.5.
By Proposition 2.5, we can obtain the generating function of the reversed Dickson polynomial Dn,k(1,x) of the (k+1)-th kind as follows.
Proposition 2.6. The generating function of Dn,k(1,x) is given by
∑∞n=0Dn,k(1,x)tn=(k−1)t−k+21−t+xt2. |
Proof. By the recursion presented in Proposition 2.5, we have
(1−t+xt2)∑∞n=0Dn,k(1,x)tn=∑∞n=0Dn,k(1,x)tn−∑∞n=0Dn,k(1,x)tn+1+x∑∞n=0Dn,k(1,x)tn+2=(k−1)t−k+2+∑∞n=0(Dn+2,k(1,x)−Dn+1,k(1,x)+xDn,k(1,x))tn+2=(k−1)t−k+2. |
Thus the desired result follows immediately.
Lemma 2.7. [3] Let x∈Fq2. Then x(1−x)∈Fq if and only if xq=x or xq=1−x.
Let V be defined by
V:={x∈Fq2:xq=1−x}. |
Clearly, Fq∩V={12}. Then we obtain a characterization for Dn,k(1,x) to be a PP of Fq as follows.
Theorem 2.8. Let q=pe with p>3 being a prime and e being a positive integer. Let
f:y↦(k−1−(k−2)y)yn−(1+(k−2)y)(1−y)n2y−1 |
be a mapping on (Fq∪V)∖{12}. Then Dn,k(1,x) is a PP of Fq if and only if f is 2-to-1 and f(y)≠kn−k+22n for any y∈(Fq∪V)∖{12}.
Proof. First, we show the sufficiency part. Let f be 2-to-1 and f(y)≠kn−k+22n for any y∈(Fq∪V)∖{12}. Let Dn,k(1,x1)=Dn,k(1,x2) for x1,x2∈Fq. To show that Dn,k(1,x) is a PP of Fq, it suffices to show that x1=x2, which will be done in what follows.
First of all, one can find y1,y2∈Fq2 satisfying x1=y1(1−y1) and x2=y2(1−y2). By Lemma 2.7, we know that y1,y2∈Fq∪V. We divide the proof into the following two cases.
CASE 1. At least one of x1 and x2 is equal to 14. Without loss of any generality, we may let x1=14. So by Theorem 2.4 (ⅰ), one derives that
Dn,k(1,x2)=Dn,k(1,x1)=Dn,k(1,14)=kn−k+22n. | (2.4) |
We claim that x2=14. Assume that x2≠14. Then y2≠12. Since f(y)≠kn−k+22n for any y∈(Fq∪V)∖{12}, by Theorem 2.4 (ⅰ), we get that
Dn,k(1,x2)=(k−1−(k−2)y2)yn2−(1+(k−2)y2)(1−y2)n2y2−1=f(y2)≠kn−k+22n, |
which contradicts to (2.4}). Hence the claim is true, and so we have x1=x2 as required.
CASE 2. Both of x1 and x2 are not equal to 14. Then y1≠12 and y2≠12. Since Dn,k(1,x1)=Dn,k(1,x2), by Theorem 2.4 (ⅰ), one has
(k−1−(k−2)y1)yn1−(1+(k−2)y1)(1−y1)n2y1−1=(k−1−(k−2)y2)yn2−(1+(k−2)y2)(1−y2)n2y2−1, |
which is equivalent to f(y1)=f(y2). However, f is a 2-to-1 mapping on (Fq∪V)∖{12}, and f(y2)=f(1−y2) by the definition of f. It then follows that y_1=y_2 or y_1=1-y_2. Thus x_1=x_2 as desired. Hence the sufficiency part is proved.
Now we prove the necessity part. Let D_{n, k}(1, x) be a PP of {\mathbb F_{q}}. Choose two elements y_1, y_2\in ({\mathbb F_{q}}\cup V)\setminus \{\frac{1}{2}\} such that f (y_1)=f (y_2), that is,
\frac{(k-1-(k-2)y_1)y_1^n-(1+(k-2)y_1)(1-y_1)^n}{2y_1-1} =\frac{(k-1-(k-2)y_2)y_2^n-(1+(k-2)y_2)(1-y_2)^n}{2y_2-1}. | (2.5) |
Since y_1, y_2\in ({\mathbb F_{q}}\cup V)\setminus \{\frac{1}{2}\}, it follows from Lemma 2.7 that y_1(1-y_1)\in{\mathbb F_{q}} and y_2(1-y_2)\in{\mathbb F_{q}}. So by Theorem 2.4 (ⅰ), (2.5) implies that
D_{n, k}(1, y_1(1-y_1))=D_{n, k}(1, y_2(1-y_2)). |
Thus y_1(1-y_1)=y_2(1-y_2) since D_{n, k}(1, x) is a PP of {\mathbb F_{q}}, which infers that y_1=y_2 or y_1=1-y_2. Since y_2\ne \frac{1}{2}, one has y_2\ne 1-y_2. Therefore f is a 2-to-1 mapping on ({\mathbb F_{q}}\cup V)\setminus \{\frac{1}{2}\}.
Now take y'\in ({\mathbb F_{q}}\cup V)\setminus \{\frac{1}{2}\}. Then from Lemma 2.7 it follows that y'(1-y')\in{\mathbb F_{q}} and
y'(1-y')\ne \frac{1}{2}\Big(1-\frac{1}{2}\Big). |
Notice that D_{n, k}(1, x) is a PP of {\mathbb F_{q}}. Hence one has
D_{n, k}(1, y'(1-y'))\ne D_{n, k}\Big(1, \frac{1}{2}\Big(1-\frac{1}{2}\Big)\Big). |
But Theorem 2.4 (ⅰ) tells us that
D_{n, k}\Big(1, \frac{1}{2}\Big(1-\frac{1}{2}\Big)\Big)=\frac{kn-k-2}{2^n}. |
Then by Theorem 2.4 (ⅰ) and noting that y'\ne \frac{1}{2}, we have
\frac{\big(k-1-(k-2)y'\big)y'^{n}-\big(1+(k-2)y'\big)(1-y')^{n}}{2y'-1}, |
which infers that f (y')\ne \frac{kn-k-2}{2^n} for any y'\in ({\mathbb F_{q}}\cup V)\setminus \{\frac{1}{2}\}. So the necessity part is proved.
The proof of Theorem 2.8 is complete.
Now we can use Theorem 2.4 to present an explicit formula for D_{n, k}(1, x) when n is a power of the characteristic p. Then we derive the detailed characterization for D_{n, k}(1, x) being a PP of {\mathbb F}_q in this case.
Proposition 2.9. Let p={\rm char}({\mathbb F_{q}})\ge 3 and s\ge 0 be an integer. Then
2D_{p^s, k}(1, x)+k-2=k(1-4x)^{\frac{p^s-1}{2}}. |
Proof. We consider the following two cases.
CASE 1. x\ne \frac{1}{4}. For this case, putting x=y (1-y) in Theorem 2.4 (ⅰ) gives us that
D_{p^s, k}(1, x)=D_{p^s, k}(1, y(1-y))\\ =\frac{\big(k-1-(k-2)y\big)y^{p^s}-\big(1+(k-2)y\big)(1-y)^{p^s}}{2y-1}\\ =\frac{\frac{k+(2-k)u}{2}\big(\frac{u+1}{2}\big)^{p^s} -\frac{k+(k-2)u}{2}\big(\frac{1-u}{2}\big)^{p^s}}{u}\\ =\frac{1}{2^{p^s+1}u}\Big((k+(2-k)u)(u+1)^{p^s}-(k+(k-2)u)(1-u)^{p^s}\Big)\\ =\frac{1}{2}(ku^{p^s-1}-k+2), |
where u=2y-1. So we obtain that
2D_{p^s, k}(1, x) =k(u^2)^{\frac{p^s-1}{2}}-k+2 =k\big((2y-1)^2\big)^{\frac{p^s-1}{2}}-k+2, |
which infers that
2D_{p^s, k}(1, x)+k-2=k(1-4x)^{\frac{p^s-1}{2}} |
as desired.
CASE 2. x=\frac{1}{4}. By Theorem 2.4 (ⅰ), one has
2D_{p^s, k}\big(1, \frac{1}{4}\big)+k-2=2\times\frac{kp^s-k+2}{2^{p^s}}+k-2=0 =k(1-4\times\frac{1}{4})^{\frac{p^s-1}{2}} |
as required. So Proposition 2.9 is proved.
It is well known that every linear polynomial over {\mathbb F_{q}} is a PP of {\mathbb F_{q}} and that the monomial x^n is a PP of {\mathbb F_{q}} if and only if \gcd (n, q-1)=1. Then by Proposition 2.9, we have the following result.
Corollary 2.10. Let p\ge 3 be a prime, q=p^e with e\ge 1 and s\ge 0 be an integer. Then D_{p^s, k}(1, x) is a PP of {\mathbb F_{q}} if and only if k\ge 1, p=3, s is odd and \gcd (s, e)=1.
Proof. First assume that D_{p^s, k}(1, x) is a PP of {\mathbb F_{p^e}}. It then follows from Proposition 2.9 that D_{p^s, k}(1, x) is a PP of {\mathbb F_{p^e}} if and only if
k(1-4x)^{\frac{p^s-1}{2}} | (2.6) |
is a PP of {\mathbb F_{p^e}}. Clearly, k\ge 1 and s>0 in this case. Suppose p>3, then (2.6) is a PP of {\mathbb F_{p^e}} if and only if
\gcd\Big(\frac{p^s-1}{2}, p^e-1\Big)=1. |
This is impossible since \frac{p-1}{2}|\gcd\big (\frac{p^s-1}{2}, q-1\big) implies that
\gcd\Big(\frac{p^s-1}{2}, q-1\Big)\ge\frac{p-1}{2}>1. |
So p=3, k\ge 1 and s>0 in what following. Now Suppose s>0 is even, then it is easy to see that 2|\gcd (\frac{3^s-1}{2}, 3^e-1) which is a contradiction. This means that s must be an odd integer and then so is \frac{3^s-1}{2}. Thus we have that (2.6) is a PP of {\mathbb F_{p^e}} if and only if
\gcd\Big(\frac{3^s-1}{2}, 3^e-1\Big)=\frac{1}{2}\gcd\big(3^s-1, 3^e-1\big)=\frac{1}{2}(3^{\gcd(s, e)}-1)=1, |
which is equivalent to that s is odd and \gcd (s, e)=1. So Corollary 2.10 is proved.
In this section, we study a necessary condition on n for D_{n, k}(1, x) to be a PP of {\mathbb F_{q}}. On one hand, it is easy to check that
D_{0, k}(1, 0)=2-k, D_{n, k}(1, 0)=1 |
for any n\ge 1 and D_{0, k}(1, 1)=2-k, D_{1, k}(1, 1)=1. On the other hand, Proposition 2.5 tells us that
D_{n+2, k}(1, 1)=D_{n+1, k}(1, 1)-D_{n, k}(1, 1) |
for n\ge 0. Then one can easily show that the sequence \{D_{n, k}(1, 1)|n\in \mathbb{N}\} is periodic with the smallest positive periods 6. In fact, one has
D_{n, k}(1, 1)={\left\{ \begin{array}{rl} 2-k, & {\rm if} \ n\equiv 0\pmod{6}, \\ 1, & {\rm if} \ n\equiv 1\pmod{6}, \\ k-1, & {\rm if} \ n\equiv 2\pmod{6}, \\ k-2, & {\rm if} \ n\equiv 3\pmod{6}, \\ -1, & {\rm if} \ n\equiv 4\pmod{6}, \\ 1-k, & {\rm if} \ n\equiv 5\pmod{6} \end{array} \right.} |
So we have the following result.
Theorem 3.1. Assume that D_{n, k}(1, x) is a PP of {\mathbb F_{q}} with q=p^e and p>3. Then n\not\equiv 1\pmod{6}.
Proof. Let D_{n, k}(1, x) be a PP of {\mathbb F_{q}}. Then D_{n, k}(1, 0) and D_{n, k}(1, 1) are distinct. Then by the above results, the desired result n\not\equiv 1 \pmod{6} follows immediately.
Let n, k be nonnegative integers. We define the following auxiliary polynomial p_{n, k}(x)\in \mathbb{Z}[x] by
p_{n, k}(x):=k\sum_{j\ge 0}\binom{n}{2j+1}x^j-(k-2)\sum_{j\ge 0}\binom{n}{2j}x^j |
for n\ge 1, and
p_{0, k}(x):=2^n(2-k). |
Then we have the following relation between D_{n, k}(1, x) and p_{n, k}(x).
Theorem 3.2. Let p>3 be a prime and n\ge 0 be an integer. Then each of the following is true.
(ⅰ). One has
D_{n, k}(1, x)=\frac{1}{2^n}p_{n, k}(1-4x). | (3.1) |
(ⅱ). We have that D_{n, k}(1, x) is a PP of {\mathbb F_{q}} if and only if p_{n, k}(x) is a PP of {\mathbb F_{q}}.
Proof. (ⅰ). Clearly, (3.1) follows from the definitions of p_{0, k}(x) and D_{0, k}(1, x) if n=0. Then we assume that n\ge 1 in what follows.
First, let x\in{\mathbb F_{q}}\setminus\{\frac{1}{4}\}. Then there exists y\in{\mathbb F_{q^2}}\setminus\{\frac{1}{2}\} such that x=y (1-y). Let u=2y-1. It then follows from Theorem 2.4 (ⅰ) that
D_{n, k}(1, x)=D_{n, k}(1, y(1-y))\\ =\frac{\big(k-1-(k-2)y\big)y^{n}-\big(1+(k-2)y\big)(1-y)^{n}}{2y-1}\\ =\frac{1}{u}\Big(\frac{-(k-2)u+k}{2}\big(\frac{u+1}{2}\big)^{n}-\frac{(k-2)u+k}{2}\big(\frac{1-u}{2}\big)^{n}\Big)\\ =\frac{1}{2^{n+1}u}\Big(k\big((u+1)^n-(1-u)^n\big)-(k-2)u\big((u+1)^n+(1-u)^n\big)\Big)\\ =\frac{1}{2^{n}}\Bigg ( k\sum_{j\ge 0}\binom{n}{2j+1}x^j-(k-2)\sum_{j\ge 0}\binom{n}{2j}u^{2j}\Bigg)\\ =\frac{1}{2^n}p_{n, k}(u^2)\\ =\frac{1}{2^n}p_{n, k}(1-4y(1-y))\\ =\frac{1}{2^n}p_{n, k}(1-4x) |
as desired. So (3.1) holds in this case.
Consequently, we let x=\frac{1}{4}. Then by Theorem 2.4 (ⅰ), we have
D_{n, k}\Big(1, \frac{1}{4}\Big)=\frac{kn-k+2}{2^n}. |
On the other hand, we can easily check that
p_{n, k}(0)=kn-k+2. |
Therefore
D_{n, k}\Big(1, \frac{1}{4}\Big)=\frac{1}{2^n}p_{n, k}(0) =\frac{1}{2^n}p_{n, k}\Big(1-4\times \frac{1}{4}\Big) |
as one desires. So (3.1) is proved.
(ⅱ). Notice that \frac{1}{2^n}\in{\mathbb F_{q}^*} and 1-4x is linear. So D_{n, k}(1, x) is a PP of {\mathbb F_{q}} if and only if p_{n, k}(x) is a PP of {\mathbb F_{q}}. This ends the proof of Theorem 3.2.
In this section, we compute the first moment \sum_{a\in {\mathbb F_{q}}}D_{n, k}(1, a). By Proposition 2.6, one has
\sum_{n=0}^{\infty}D_{n, k}(1, x)t^n=\frac{(k-1)t-k+2}{1-t+xt^2} =\frac{(k-1)t-k+2}{1-t}\frac{1}{1-\frac{t^2}{t-1}x} \notag\\ =\frac{(k-1)t-k+2}{1-t}\Big(1+\sum_{m=1}^{q-1}\sum_{\ell=0}^{\infty } \bigg(\frac{t^2}{t-1}\bigg)^{m+\ell (q-1)}x^{m+\ell (q-1)}\Big) \notag\\ \equiv\frac{2t-1}{1-t}\Big(1+\sum_{m=1}^{q-1}\sum_{\ell=0}^{\infty } \bigg(\frac{t^2}{t-1}\bigg)^{m+\ell (q-1)}x^{m}\Big)\pmod{x^q-x} \notag\\ =\frac{(k-1)t-k+2}{1-t}\Big(1+\sum_{m=1}^{q-1} \frac{(\frac{t^2}{t-1})^m}{1-(\frac{t^2}{t-1})^{q-1}}x^m\Big) \notag\\ =\frac{(k-1)t-k+2}{1-t}\Big(1+\sum_{m=1}^{q-1} \frac{(t-1)^{q-1-m}t^{2m}}{(t-1)^{q-1}-t^{2(q-1)}}x^m\Big). | (4.1) |
Moreover, by Theorem 2.4 (ⅱ), it follows that for any x\in{\mathbb F_{q}}\setminus\{\frac{1}{4}\}, one has
D_{n_1, k}(1, x)=D_{n_2, k}(1, x) |
when n_1\equiv n_2\pmod{q^2-1}. Thus if x\ne \frac{1}{4}, one has
\sum_{n=0}^\infty D_{n, k}(1, x)t^n=1+\sum_{n=1}^{q^2-1} \sum_{\ell=0}^{\infty }D_{n+\ell(q^2-1), k}(1, x)t^{n+\ell(q^2-1)}\notag\\ =1+\sum_{n=1}^{q^2-1}D_{n, k}(1, x)\sum_{\ell=0}^{\infty }t^{n+\ell(q^2-1)}\notag\\ =1+\frac{1}{1-t^{q^2-1}}\sum_{n=1}^{q^2-1}D_{n, k}(1, x)t^{n}. | (4.2) |
Then (4.1) together with (4.2) gives that for any x\ne \frac{1}{4}, we have
\sum_{n=1}^{q^2-1}D_{n, k}(1, x)t^n= \Big(\sum_{n=0}^{\infty}D_{n, k}(1, x)t^n-1\Big)(1-t^{q^2-1})\notag\\ \equiv \Big(\frac{(k-1)t-k+2}{1-t}-1\Big)(1-t^{q^2-1}) +\frac{(1-t^{q^2-1})((k-1)t-k+2)}{1-t}\sum_{m=1}^{q-1} \frac{(t-1)^{q-1-m}t^{2m}}{(t-1)^{q-1}-t^{2(q-1)}}x^m\pmod{x^q-x}\notag\\ =\frac{(kt+1-k)(1-t^{q^2-1})}{1-t}+h(t)\sum_{m=1}^{q-1} (t-1)^{q-1-m}t^{2m}x^m, | (4.3) |
where
h(t):=\frac{(t^{q^2-1}-1)((k-1)t-k+2)}{(t-1)^q-(t-1)t^{2(q-1)}}. |
Lemma 4.1. [4] Let u_0, u_1, \cdots, u_{q-1} be the list of the all elements of {\mathbb F_{q}}. Then
\sum_{i=0}^{q-1}u_i^k={\left\{ \begin{array}{rl} 0, & {\rm if} \ 0\le k\le q-2, \\ -1, & {\rm if} \ k=q-1. \end{array} \right.} |
Now by Theorem 2.4 (ⅰ), Lemma 4.1 and (4.3), we derive that
\sum_{n=1}^{q^2-1}\sum_{a\in{\mathbb F_{q}}}D_{n, k}(1, a)t^n =\sum_{n=1}^{q^2-1}D_{n, k}\Big(1, \frac{1}{4}\Big)t^n+\sum_{n=1}^{q^2-1} \sum_{a\in{\mathbb F_{q}}\setminus\{\frac{1}{4}\}}D_{n, k}(1, a)t^n\notag\\ =\sum_{n=1}^{q^2-1}\frac{kn-k+2}{2^n}t^n+\sum_{a\in{\mathbb F_{q}} \setminus\{\frac{1}{4}\}}\frac{(kt+1-k)(1-t^{q^2-1})}{1-t}+h(t)\sum_{m=1} ^{q-1}(t-1)^{q-1-m}t^{2m}\sum_{a\in{\mathbb F_{q}}\setminus\{\frac{1}{4}\}}a^m\notag\\ =\sum_{n=1}^{q^2-1}\frac{kn-k+2}{2^n}t^n+(q-1)\frac{(kt+1-k)(1-t^{q^2-1})}{1-t} +h(t)\sum_{m=1}^{q-1}(t-1)^{q-1-m}t^{2m}\sum_{a\in{\mathbb F_{q}}}a^m\notag\\ \ \ \ -h(t)\sum_{m=1}^{q-1}(t-1)^{q-1-m}t^{2m}\Big(\frac{1}{4}\Big)^m\notag\\ =\sum_{n=1}^{q^2-1}\frac{kn-k+2}{2^n}t^n-\frac{(kt+1-k)(1-t^{q^2-1})}{1-t} -h(t)t^{2(q-1)}-h(t)\sum_{m=1}^{q-1}(t-1)^{q-1-m}t^{2m}\Big(\frac{1}{4}\Big)^m. | (4.4) |
Since (t-1)^q=t^q-1 and q is odd, one has
h(t)=\frac{(t^{q^2-1}-1)(2t-1)}{(t-1)^q-(t-1)t^{2(q-1)}}\notag\\ =\frac{(t^{q^2-1}-1)(2t-1)}{(1-t^{q-1})(t^q-t^{q-1}-1)} \notag\\ =\frac{(t^{q^2}-t)(2t-1)}{(t-t^{q})(t^q-t^{q-1}-1)}\notag\\ =\frac{(t^{q}-t)^q+t^q-t}{t-t^{q}}\cdot \frac{2t-1}{t^q-t^{q-1}-1}\notag\\ =\frac{(-1-(t-t^q)^{q-1})(2t-1)}{t^q-t^{q-1}-1}\notag\notag\\ =\frac{(2t-1)\sum_{i=0}^{q^2-q}b_it^i}{t^q-t^{q-1}-1}, | (4.5) |
where
\sum_{i=0}^{q^2-q}b_it^i:=-1-(t-t^q)^{q-1}. |
Then by the binomial theorem applied to (t-t^q)^{q-1}, we can derive the following expression for the coefficient b_i.
Proposition 4.2. For each integer i with 0\le i\le q^2-q, write i=\alpha+\beta q with \alpha and \beta being integers such that 0\le \alpha, \beta \le q-1. Then
b_i={\left\{ \begin{array}{ll} (-1)^{\beta +1}\binom{q-1}{\beta}, & {\it if} \ \alpha +\beta =q-1, \\ -1, & {\it if} \ \alpha =\beta =0, \\ 0, & {\it otherwise}. \end{array} \right.} |
For convenience, let
a_n:=\sum_{a\in{\mathbb F_{q}}}D_{n, k}(1, a). |
Then by (4.4) and (4.5), we arrive at
\sum_{n=1}^{q^2-1}\Big(a_n-\frac{kn-k+2}{2^n}\Big)t^n =-\frac{(kt+1-k)(1-t^{q^2-1})}{1-t}-\frac{(2t-1)\sum_{i=0}^{q^2-q}b_it^i}{t^q-t^{q-1}-1} \Big(t^{2(q-1)}+\sum_{m=1}^{q-1}(t-1)^{q-1-m}t^{2m}\Big(\frac{1}{4}\Big)^m\Big), |
which implies that
(t^q-t^{q-1}-1)\sum_{n=1}^{q^2-1}\Big(a_n-\frac{kn-k+2}{2^n}\Big)t^n\notag\\ =-(t^q-t^{q-1}-1)(kt+1-k)\sum_{i=0}^{q^2-2}t^i-(2t-1)\Big(t^{2(q-1)}+\sum_{k=1}^{q-1} (t-1)^{q-1-k}t^{2k}\Big(\frac{1}{4}\Big)^k\Big)\sum_{i=0}^{q^2-q}b_it^i. | (4.6) |
Let
\sum_{i=1}^{q^2+q-1}c_it^i |
denote the right-hand side of (4.6) and let
d_n:=a_n-\frac{kn-k+2}{2^n} |
for each integer n with 1\le n\le q^2-1. Then (4.6) can be reduced to
(t^q-t^{q-1}-1)\sum_{n=1}^{q^2-1}d_nt^n=\sum_{i=1}^{q^2+q-1}c_it^i. | (4.7) |
Then by comparing the coefficient of t^i with 1\le i\le q^2+q-1 of the both sides in (4.7), we derive the following relations:
{\left\{ \begin{array}{ll} c_j=-d_j, & {\rm if} \ 1\le j\le q-1, \\ c_q=-d_1-d_q, & \\ c_{q+j}=d_j-d_{j+1}-d_{q+j}, & {\rm if} \ 1\le j\le q^2-q-1, \\ c_{q^2+j}=d_{q^2-q+j}-d_{q^2-q+j+1}, & {\rm if} \ 0\le j\le q-2, \\ c_{q^2+q-1}=d_{q^2-1}, & \end{array} \right.} |
from which we can deduce that
{\left\{ \begin{array}{ll} d_j=-c_j, & {\rm if} \ 1\le j\le q-1, \\ d_q=c_1-c_q, & \\ d_{\ell q+j}=d_{(\ell -1)q+j}-d_{(\ell-1)q+j+1}-c_{\ell q+j}, & {\rm if} \ 1\le \ell\le q-2\ \ {\rm and}\ \ 1\le j\le q-1, \\ d_{\ell q}=d_{(\ell -1)q}-d_{(\ell-1)q+1}-c_{\ell q}, & {\rm if} \ 2\le \ell\le q-2, \\ d_{q^2-q+j}=\sum_{i=j}^{q-1}c_{q^2+i}, & {\rm if} \ 0\le j\le q-1. \end{array} \right.} | (4.8) |
Finally, (4.8) together with the following identity
\sum_{a\in {\mathbb F_{q}}}D_{n, k}(1, a)=d_n+\frac{kn-k+2}{2^n} |
shows that the last main result of this paper is true:
Theorem 4.3. Let c_i be the coefficient of t^i in the right-hand side of (4.6) with i being an integer such that 1\le i\le q^2+q-1. Then we have
\sum_{a\in {\mathbb F_{q}}}D_{j, k}(1, a)=-c_j+\frac{kj-k+2}{2^j}\ \ if\ \ 1\le j\le q-1, \\ \sum_{a\in {\mathbb F_{q}}}D_{q, k}(1, a)=c_1-c_q-\frac{k-2}{2}, \\ \sum_{a\in {\mathbb F_{q}}}D_{\ell q+j, k}(1, a)=\sum_{a\in {\mathbb F_{q}}}D_{(\ell-1)q+j, k}(1, a)- \sum_{a\in {\mathbb F_{q}}}D_{(\ell-1)q+j+1, k}(1, a)-c_{\ell q+j}+\frac{k}{2^{\ell +j}}\\ \ \ \ \ if\ \ 1\le \ell\le q-2 \ {\it and} \ 1\le j\le q-1, \\ \sum_{a\in {\mathbb F_{q}}}D_{\ell q, k}(1, a)=\sum_{a\in {\mathbb F_{q}}}D_{(\ell-1)q, k}(1, a)- \sum_{a\in {\mathbb F_{q}}}D_{(\ell-1)q+1, k}(1, a)-c_{\ell q}+\frac{k}{2^{\ell}}\ \ if\ \ 2\le \ell\le q-2 |
and
\sum_{a\in {\mathbb F_{q}}}D_{q^2-q+j, k}(1, a) =\sum_{i=j}^{q-1}c_{q^2+i}+\frac{kj-k+2}{2^j}\ \ if\ \ 0\le j\le q-1. |
Cheng was supported partially by the General Project of Department of Education of Sichuan Province 15ZB0434. [2000] Primary 11T06, 11T55, 11C08.
The author declares no conflicts of interest in this paper.
[1] | S. D. Cohen, Dickson polynomials of the second kind that are permutations, Canad. J. Math., 46 (1994), 225-238. |
[2] | S. Hong, X. Qin andW. Zhao, Necessary conditions for reversed Dickson polynomials of the second kind to be permutational, Finite Fields Appl., 37 (2016), 54-71. |
[3] | X. Hou, G. L. Mullen, J.A. Sellers and J.L. Yucas, Reversed Dickson polynomials over finite fields, Finite Fields Appl., 15 (2009), 748-773. |
[4] | R. Lidl and H. Niederreiter, Finite Fields, second ed. , Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 20 1997. |
[5] | X. Qin and S. Hong, Constructing permutation polynomials over finite fields, Bull. Aust. Math. Soc., 89 (2014), 420-430. |
[6] | X. Qin, G. Qian and S. Hong, New results on permutation polynomials over finite fields, Int. J. Number Theory, 11 (2015), 437-449. |
[7] | Q. Wang and J. L. Yucas, Dickson polynomials over finite fields, Finite Fields Appl., 18 (2012), 814-831. |
1. | Kaimin Cheng, Permutational behavior of reversed Dickson polynomials over finite fields II, 2017, 2, 2473-6988, 586, 10.3934/Math.2017.4.586 | |
2. | Kaimin Cheng, Shaofang Hong, The first and second moments of reversed Dickson polynomials over finite fields, 2018, 187, 0022314X, 166, 10.1016/j.jnt.2017.10.021 |