几类新的有限域上的n-cycle置换.pdf

第 43 卷第 2 期2023 年 6 月数学理论与应用MATHEMATICAL THEORY AND APPLICATIONSVol.43No.2Jun.2023Some New Classes ofncycle Permutations over Finite FieldsZhang ZhilinYuan Pingzhi*(School of Mathematical Science,South China Normal University,Guangzhou 510640,China)AbstractThis paper presents some new classes of ncycle permutations over finite fields.At first,we present aconcise criterion for Dickson polynomials over finite fields being ncycle permutations.Then,we give a necessaryand sufficient condition for linearized polynomials over finite fields being involutions.Finally,some interesting newclasses of ncycle permutations are demonstrated by considering polynomials of different forms.Key wordsncycle permutationPermutation polynomialLinear translatorDickson polynomialLinearizedpolynomialFinite fieldPiecewise function几类新的有限域上的ncycle 置换张志林袁平之*(华南师范大学数学科学学院,广州,510640)摘要本文给出几类新的有限域上的 ncycle 置换.首先,我们给出一个判断 Dickson 多项式是否为ncycle 置换的方法.其次,我们给出一个线性多项式是否为对合的充要条件.最后,我们给出几类新的不同型的 ncycle 置换.关键词ncycle 置换置换多项式线性译码Dickson 多项式线性多项式有限域分段函数doi:10.3969/j.issn.10068074.2023.02.0031IntroductionLet p be a prime number and q be a power of p.Let Fqbe the finite field of order q and let Fqx be theset of polynomials with coefficients in Fq.A polynomial f(x)Fqx is called a permutation polynomialon Fqif it induces a permutation of Fq.The first systematic treatment of permutation polynomials is due to Hermite 11 for a finite primefield and later to Dickson 7 for a general finite field.Permutation polynomials over finite fields havebeen an interesting subject of study for many years,and have applications in coding theory 19,29,cryptography 15,16,20,21,26,28,combinatorial designs 8,and other areas of mathematics andengineering.An important problem of this topic is to find more new classes of permutation polynomials.This work is supported by National Natural Science Foundation of China(Nos.12001204,12171163)Corresponding author:Yuan Pingzhi(1966 ),Associate Professor,PhD Email:收稿日期:2022 年 11 月 2 日几类新的有限域上的 ncycle 置换33In general,it is not easy to do this.Information about permutation polynomials over finite fields can befound in 10,12,13,22,23,24,31,36.In 6,the authors gave the definition of ncycle permutations over finite fields as follows.Definition 1.1Let f f(x)denote the operation of composition f?f(x)?.A permutationpolynomial f(x)Fqx is called an ncycle permutation if it satisfiesfn(x)=f f f|zn times(x)x(mod xq x).When n=2,3 or 4,f(x)is called an involution,a triplecycle permutation or a quadruplecyclepermutation respectively.In the following,we present an interesting example to illustrate the ncycle permutations.Example 1.1Let F24=F2,where is a root of the irreducible polynomial 1+x+x4 F2x.Then the polynomial h(x)=x4+x7+x13is a quadruplecycle permutation on F24.Moreover,the cycledecomposition of h(x)is given by(0)(1)(5)(10)(842)(3141211)(61397).Recently,Chen,Wang and Zhu 6 gave a systematic treatment of ncycle permutations over finitefields and presented some new classes of ncycle permutations with the form xrh(xs).This paper is firstmotivated by the following problem which is proposed in 6,Conclusions.Problem 1.1It is interesting to use the methods in this paper to obtain more ncycle permutationsof other forms in the future.The rest of this paper is organized as follows.In Section 2,we present a concise criterion for Dicksonpolynomials over finite fields being ncycle permutations.In Section 3,we give a necessary and sufficientcondition for linearized polynomials over finite fields being involutions.Finally,some interesting newclasses of ncycle permutations over finite fields are also demonstrated.2nCycle permutations of the Dickson polynomialsThe class of polynomials of the formxk+kk12Xi=1(k i 1)(k 2i+1)i!aixk2iover finite fields,where k is odd,is originated from the work of Dickson when he was studying atthe University of Chicago.As you know,he almost proved that(k,q2 1)=1 is a necessary andsufficientconditionforthesepolynomials beingpermutationpolynomialsoverFq.Sincethen,thisclassofpolynomials and its relevant generalizations caused many scholars attention and the study of it continueduntil this day.34数学理论与应用These polynomials are related to the classical Chebyshev polynomials and they are important inconnection with a Schurs celebrated conjecture 27.Due to the importance of these polynomials,they were named Dickson polynomials by Schur in recognition of Dicksons outstanding contributions.Especially,in recent decades,this class of Dickson polynomials has been extensively investigated underdifferent contexts.A tremendous amount of results of this class of polynomials showed that it forms animportant class of permutation polynomials,which is referred as the Dickson permutational polynomials.For more details,such as the work on the class of Dickson polynomials and its development,see,forinstance,Lidl and Niederreiter 24,Charpter 7 or Lidl,Mullen and Turnwald 25.In terms of ncycle permutations,we deal with Dickson polynomials over finite fields Fqin thissection.Definition 2.1Let k2 denote the largest integer less than or equal tok2.The Dickson polynomialof degree k in indeterminate x and with parameter a Fqis defined byDk(x,a)=k2Xi=0kk i?k ii?(a)ixk2i,where k 2.An easy way of generating Dickson polynomials is via recurrence relations.Lemma 2.1(25)The Dickson polynomials Dk(x,a)satisfy the second order recurrence relationsDk+2(x,a)=xDk+1(x,a)aDk(x,a)for k 0 with initial valuesD0(x,a)=2 and D1(x,a)=x.The following useful results about Dickson polynomials appeared in 25 are wellknown.Lemma 2.2(25)The Dickson polynomials Dk(x,a)satisfy:(i)deg?Dk(x,a)?=k,(ii)Dk(x,a)=Dk?D(x,a),a?,(iii)Dk(x+ax,a)=xk+akxk,for all x,and any integer k,1.Lemma 2.3(25)Let a Fq.Then Dk(x,a)is a permutation polynomial on Fqif and only if(k,q2 1)=1.For a Fq,let P(a)denote the set of all Dickson polynomials Dk(x,a)which are permutationpolynomials of Fqso thatP(a)=?Dk(x,a)|(k,q2 1)=1?.几类新的有限域上的 ncycle 置换35Lemma 2.4(25)P(a)is closed under composition of polynomials if and only if a 1,1.In this section,we always assume that P(a)is closed under composition of polynomials.It shouldbe noted that the proofs of Theorem 2.1 and Corollary 2.1 use some essential ideas of 4,Theorem 2,Corollary 1 and 25,Charpters 2,3.Theorem 2.1Let k be a nonzero integer.ThenDk(x,a)D1(x,a)(mod xq x)if and only if one of the following holds.(i)If a=1,then k 1(mod q+1)or k 1(mod q+1)and k 1(mod q 1)or k 1(mod q 1).(ii)If a=1,then k 1(mod q+1)or k 1(mod 2(q+1)and 2k 2(mod q 1)ork 1(mod q 1).Proof Let x Fq.Then x can be written as x=+awith Fq2,where Fq2is the degree 2extension of Fq.Suppose that Dk(x,a)D1(x,a)(mod xq x).Clearly,by Lemma 2.2(iii),we haveDk(x,a)=k+akk=D1(x,a)=+a.(2.1)Since +a Fq,(+a)q=+ayieldsq+1(q1 1)=a(q1 aq1).(i)If a=1,then q+1=1 or q1=1.(ii)If a=1,then q+1=1 or q1=1.In the following,we present a detailed discussion of these two cases.Let be a primitive element ofFq2.Case(i)Suppose that a=1.Let 0 d such that 0+10 Fqand let 1 Fq2such that01=1,where d=q 1 or q+1.Then 1 d and 0+10=1+11 Fq.Since Fq2=,q+1=1 or q1=1 implies that q1 or q+1 respectively.First,assume that q is even.Now 1+1=0 yields =1.Then,by?+1 Fq|q1?q2,?+1 Fq|q+1?q 22and|Fq|=q 1,we get that there exists Fq2such that =q1or q+1.36数学理论与应用Second,assume that q is odd.First of all,we assert that?q1 q+1?=2.Indeed,let s,t be two integers such that s(q1)=t(q+1),where 0 s q and 0 t q 2.Thens(q1)=t(q+1)yields q(ts)+(t+s)=1.So q(t s)+(t+s)=0.This implies that t=s=0 ors=t+1=q+12.When s=t+1=q+12,the inverse element of s(q1)=t(q+1)=q212is itself.Clearly,+1=2+1=0 if and only if =q214,where Fq2.Since q is an odd primepower,q 1(mod 4)or q 1(mod 4).Without loss of generality,we may assume that q+1=1and q 1(mod 4).Then q214 q1.Thus,by?+1 Fq|q1?q+12and Fq=q 1,there exists Fq2such that q1=1.Similarly,we have?+1 Fq|q+1?q+12.Together with|q+1 q1|=2,we know that there exists Fq2such that =q+1or q1.Assume that q 1(mod 4).Then?+1 Fq|q1?q+32implies that there exists Fq2such that q1=1.Similarly,by q214 q+1,we have?+1 Fq|q+1?q 12.Together with|q+1 q1|=2,we know that there exists Fq2such that =q+1or q1.From(2.1),we conclude that2k+1=k1(2+1),namely,(k+1 1)(k1 1)=0.Thus,k+1=1 or k1=1.Let =q1.Then k 1(mod q+1)or k 1(mod q+1).Let=q+1.Then k 1(mod q 1)or k 1(mod q 1).Case(ii)Suppose that a=1.Let 2 Fq2such that q12=1 and 212 Fq.Let 3 Fq2such that 23=1.Then,by q odd and(23)q1=1,we have q13=1 and313=212.At this point,q+1=1 or q1=1 implies that?q12,3(q1)2,(2q+1)(q1)2?q12or q+1 respectively.Clearly,1=0 if and only if =q212or 1,where Fq2.几类新的有限域上的 ncycle 置换37On the one hand,?1 Fq|=q12,3(q1)2,(2q+1)(q1)2?q+12.On the other hand,?1 Fq|q+1?q 32.Together with?(q1)|=1,3,2q+1?q+1?=0and Fq=q 1,we get that there exists Fq2such that =q12or q+1.Notice that q is odd and,by(k,q2 1)=1,k is also odd.Then(2.1)implies thatk1k=1,which implies that(k+1+1)(k1 1)=0.Thus,k+1=1 or k1=1.Let =q+1.Then 2(k+1)0(mod q1)or k 1(mod q1).Let =q12.Then k 1(mod q+1)or k 1(mod 2(q+1).The proof is complete.Corollary 2.1Define Kaq=nk|1 k q21,Dk(x,a)D1(x,a)(mod xqx)o.Then oneof the following holds.(I)If a=1,thenK1q=n1,q,q2 32,q2+12,q2 2q 12,q2+2q 12,q2 q 1,q2 2o.(II)If a=1,thenK1q=n1,q,q2 2q 12,q2+12,q2+2q 12,q2 33,q2 4q 14,q2 54,3q2 4q 34,3q2 74,q2 2o.Proof Firstassumethata=1.Thenk Kqimpliesthatk mustbeasolutionofoneofthefollowingfour systems of linear congruences:(i)k 1(mod q+1)and k 1(mod q 1)(ii)k 1(mod q+1)and k 1(mod q 1)(iii)k 1(mod q+1)and k 1(mod q 1)(iv)k 1(mod q+1)and k 1(mod q 1).38数学理论与应用Case(i)implies that q+1|k 1 and q 1|k 1.Then there exists an integer such thatk 1=(q+1)=(q 1)+2.So q 1|2.Thus,=0 orq12,which yields k=1 orq2+12.Case(ii)implies that q+1|k 1 and q 1|k+1.Then there exists a positive integer such thatk 1=(q+1)=(q 1)+2 and k+1=(q 1)+2(+1).Thus,=0,q32or q 2 and sok=1,q22q12or q2 q 1.Case(iii)implies that q+1|k+1 and q 1|k 1.Then there exists a positive integer such thatk+1=(q+1)=(q 1)+2 and k 1=(q 1)+2(1).Thus,=1 orq+12and so k=qorq2+2q12,which is a contradiction.Case(iv)implies that q+1|k+1 and q 1|k+1.Then there exists a positive integer such thatk+1=(q+1)=(q 1)+2.Thus,=q12and q 1,so k=q232or q2 2.Now we assume that a=1.Then k Kqimplies that k must be a solution of one of the followingfour systems of linear congruences:(i)k 1(mod q+1)and 2k 2(mod q 1)(ii)k 1(mod q+1)and k 1(mod q 1)(iii)k 1(mod 2(q+1)and 2k 2(mod q 1)(iv)k 1(mod 2(q+1)and k 1(mod q 1).In case(i),there exists an integer such that k+1=(q+1)=(q 1)+2 and 2(k+1)=2(q 1)+4.So =q14,q12,3(q1)4or q 1.Thus,k=q254,q233,3q274or q2 2.In case(ii),there exists an integer such that k+1=(q+1)=(q 1)+2 and k 1=(q 1)+2(1).So =1 orq+12.Thus,k=q orq2+2q12.In case(iii),there exists an integer such that k 1=2(q+1)=2(q 1)+4 and 2(k+1)=4(q 1)+4(2+1).So =0,q58,q34or3q78.Thus,k=1,q24q14,q22q12or3q24q34.In case(iv),there exists an integer such that k 1=2(q+1)=2(q 1)+4.So =0 orq14.Thus,k=1 orq2+12.The proof is complete.In the following,we present the main theorem of this section.Theorem 2.2Let Kaqbe as in Corollary 2.1 and a=1.Let q 4 and 1 k q2 1.ThenDk(x,a)is an ncycle permutation on Fqif and only if(k,q21)=1 and kn (mod q21),where Kaq.Proof Since Dk(x,a)is an ncycle permutation on Fq,by Lemma 2.2,Dnk(x,a)=Dk Dk Dk|zn times(x,a)=Dkn(x,a)D1(x,a)(mod xq x).Thus,kn Kaq,where knis computed modulo q2 1.The proof is complete.几类新的有限域上的 ncycle 置换39Finally,we give some examples of Dickson polynomials which are ncycle permutations to finishthis section.Example 2.1(i)D3(x,1)=x3 3x is a quadruplecycle permutation on F32.(ii)D52(x,1)=12Pi=02525i?25ii?(1)ix252i=x25 25x23+275x21 1750 x19+7125x1719380 x15+35700 x13 44200 x11+35750 x9 17875x7+5005x5 650 x3+25x is a 5cyclepermutation on F55.Example 2.2Let m and d be two positive integers with d|2m and d m.Then Dpd(x,1)is a2mdcycle permutation on Fpm.In fact,let k=pd,then we have(k,p2m 1)=1 and k2md=p2m 1(mod p2m 1).Thus,by1 Kqand Theorem 2.2,we get that Dpd(x,1)is a2mdcycle permutation on Fpm.3nCycle permutations of the linearized polynomialsA linearized polynomial over the finite field Fqtis a polynomial of the formL(x)=t1Xi=0aixqi=a0 x+a1xq+a2xq2+at1xqt1.Linearizedpolynomialsholdaspecialplaceinthestudyofpermutationpolynomialsoverfinitefields.Meanwhile,it is also an important class of polynomials since we can use it to construct many other moreinteresting classes of permutation polynomials,see 1,14,17,34,35,37 for instance.The set of allpermutational linearized polynomials over finite fields Fqtis closed under composition of polynomialsand it forms a subgroup of symmetric group called BettiMathieu group which is isomorphic to the generallinear group GLt(q)of nonsingular matrices over Fq.It is a well known criterion that L(x)is a permutation polynomial over Fqtif and only if det(DL)=0(see 24,Section 3 for more details),whereDL=a0a1at1aqt1aq0aqt2.aqt11aqt12aqt10is called the associate Dickson matrix of L(x).Generally speaking,it is not convenient to use this criteriontofindoutlinearizedpolynomials,asitmaybehardtodetermineifthedeterminantofthismatrixisnonzero9.Theorem 3.1(32)Let L(x)=t1Pi=0ixqi Fqtx be a linear permutation of Fqt.ThenDL1=D1L.40数学理论与应用More precisely,let e aidenote the(i,0)th cofactor of DL,where 0 i t 1.Thendet(L)=t1Xi=0aqitie ai FqandL1(x)=1det(L)t1Xi=0e aixqi.Our important result of this section is the following partial improvement of Charpin,Mesnager andSarkar 5,Proposition 3.8.Corollary 3.1Let L(x)=t1Pi=0ixqi Fqtx be a linear permutation polynomial of Fqt.ThenL(x)is an involution on Fqtif and only ife aidet(L)=aifor each i 0,1,t 1.Proof Assume that L(x)is an involution on Fqt.ThenL2(x)=L L(x)x(mod xqt x)yieldsL1(x)=L(x),by Theorem 3.1,1det(L)t1Xi=0e aixqi=t1Xi=0ixqi.Thus,we havee aidet(L)=aifor each i 0,1,t 1.The proof is complete.Actually,L1 L2(x)is associate with DL1DL2.Thus,we have the following result.Corollary 3.2L(x)is an ncycle permutation if and only if DnL=E,where E is the identitymatrix.4nCycle permutations via linear structure or linear translatorFirst of all,we introduce the concepts of linear structure and linear translator for any mapping.几类新的有限域上的 ncycle 置换41Definition 4.1A nonzero element Fqtis called a blinear structure for the mapping f:FqtFqiff(x+)f(x)=bholds for any x Fqt,Fqand a fixed b Fq.Definition 4.2Let t=rk and let f:Fqt Fqkbe a mapping,where 1 1.Let f:Fpt Fpkand h:Fpk Fpk.DefineF(x)=x+h?f(x)?,where Fptis a 0linear translator of f.Then F(x)is a pcycle permutation on Fpt.Here we give an example to illustrate Theorem 4.4.Example 4.1Let t=rk and let Fqt,where t k 1.If Trt/k()=0 for any Fqk,thenF(x)=x+Trt/k(x)is a pcycle permutation on Fqt.Proof By Trt/k()=0 and Trt/k(x+)=Trt/k(x)+Trt/k(),clearly we haveTrt/k(x+)Trt/k(x)=0,which implies that is a 0linear translator of Trt/k(x).Then,by Theorem 4.4,h(x)=x and f(x)=Trt/k(x),we have that F(x)is a pcycle permutation on Fqt.The proof is complete.At the end of this section,we give an example to show that the existence of the case where b=0.Example 4.2(2)Let t=rk with k 1.Let f:Fpt Fpkand b Fpk.Assume that Fptis a blinear translator of f(x),wh