首页 >
论文范文 >
自然科学论文 >
数学论文 >
数论论文 >
探究有限域子集上的Hermite判别法及推广
0
给我们留言吧!
摘要：利用有限生成代数的语言重述关于置换多项式的经典的Hermite判别法,并将其推广到有限域的子集上,另外也推广了其他一些关于有限域上置换多项式的结果,并给出了一定条件下相关函数的值集大小估计.最后,给出主要结果在有限域上n阶单位根群中的应用实例,并得到了一些有趣的结果.
加入收藏
在数论研究中,关于有限域的研究占据了相当重要的地位.有限域在现代数学及计算机科学的多个领域都有着重要的应用.令Fq为q元有限域,其中q=pr,我们自然对Fq上的函数及其性质感兴趣.特别地,对Fq上的双射函数,自19世纪以来,已有学者进行了大量研究,重要的成果包括Hermite[1],Dickson[2],Cohen[3],Wan[4],Turnwald[5]及Zieve[6,7].
尽管关于有限域Fq上的双射已有不少重要成果,关于有限域Fq上子集的函数却缺少相关研究.本文研究重点将集中于有限域Fq上子集,通过引入有限生成代数的观点,说明对于有限域Fq上子集也有类似有限域上Hermite判别法的结论成立,且可将一些基于有限域Fq上Hermite判别法的研究成果平行地推广到子集上.
1、相关背景回顾
本节主要回顾本文将会用到的已有研究成果与结论.由于任意一个Fq到Fq上的函数,都可唯一表示为Fq上次数小于q的多项式g,对于有限域上的双射函数自然转化为对置换多项式的研究.置换多项式的研究已有相当长的历史.这一方面的早期结果,参见LidlandNiederreiter[8].
称Fq上多项式f满足第k个Hermite条件,若成立等式∑x∈Fqfk(x)=∑x∈Fqxk.关于置换多项式,有下面的重要结果:
定理1.1(Hermite判别法)
f(X)是置换多项式⇔f满足前q-1个Hermite条件
由于对有限域Fq,有正交性:
∑x∈Fqxk={0,−1,0≤k≤q−2k=q−1
因此,对Fq上多项式g(X),∑x∈Fqg(x)由gmodXq-X的q-1次项决定.进而,对k≤q-2,f满足前k个Hermite条件等价于fkmodXq-X的次数小于q-1,即有常见版本的Hermite判别法:
定理1.2(Hermite判别法,经典形式)
f(X)是置换多项式⇔下列两个条件成立:
1)f(X)在Fq中恰有一个零点.
2)fkmodXq-X的次数小于q-1,其中1≤k≤q-2.
置换多项式,虽然定义简单,但却难于研究.为此,人们引入了例外多项式的概念来帮助研究置换多项式.例外多项式(最早由DavenportandLewis[9]提出),基于几何性质定义,更易通过较为深刻的几何工具来帮助研究;基于Lang-Weil估计[10]可知,次数远小于q的置换多项式均为例外多项式.另一方面,由DavenportandLewis[9]猜测,并由S.D.Cohen[3]证明了下列重要定理:
定理1.3(Cohen,1970)Fq上例外多项式都是置换多项式.
进一步的,M.Zieve等人[6,7]于2010年几乎完全刻画了有限域上例外多项式,取得了对有限域上置换多项式的结构刻画的重大进展.
S.D.Cohen[3]给出的证明大量利用了群论工具,这使得证明稍显复杂.其后多人改进/拓展了这个证明,下面列举一些有代表性的相关成果:
K.S.Williams[11,12]利用Newton公式,对大特征情形给出了一个非常简洁的证明.他得到:
定理1.4(Williams,1968).有限域Fq上多项式f(X)是置换多项式,当且仅当存在正整数m<p,使得
1)f满足前m个Hermite条件.
2)|f(Fq)|≥q−m.
推论1.5有限域Fq上多项式f(X)是置换多项式,如果存在正整数m<p,使得
1)deg(f)<q−1m.
2)|f(Fq)|≥q−m.
等价地,有
等价描述若有限域Fq上次数为d的多项式f(x)不是置换多项式,那么对任意满足m<min{p,q−1d}的正整数m,f的值集大小|f(Fq)|≤q−1−m.特别地,f有值集大小上界
|f(Fq)|≤q−1−[q−2d].
这个上界对于q=p的情况相当好,但对于一般情形,Newton公式可能失效,因而不适用于小特征情形.1991年,万大庆[4]注意到推论1.5中条件(1)包含了比定理1.4中更多的信息.充分利用这个条件,万大庆成功将Williams的证明提升到了Newton公式适用的p-adic数域上,从而克服了小特征障碍,给出了Cohen定理的一个新的完整证明.事实上,他得到了以下结论:
定理1.6(Wan)有限域Fq上多项式f(X)是置换多项式,如果存在正整数m,使得
1)deg(f)<q−1m.
2)|f(Fq)|≥q−m.
等价地,我们有
等价描述若有限域Fq上次数为d的多项式f(X)不是置换多项式,那么对任意满足m<q−1d的正整数m,f的值集大小|f(Fq)|≤q−1−m.特别地,f有值集大小上界
|f(Fq)|≤q−1−[q−2d].
最近,张起帆利用线性代数理论推广了Hermite判别法.张起帆注意到,在有限域上Hermite判别法恰好可以看作Newton公式的补充.在Williams的证明中使用Hermite判别法取代Newton公式,就可以规避小特征障碍,从而改进了Williams[12]的结果,并得到了一个完全线性代数化的初等证明.事实上,他得到了
定理1.7(Zhang)有限域Fq上多项式f(X)是置换多项式,当且仅当存在正整数m,使得
1)f满足前2m-1个Hermite条件.
2)|f(Fq)|≥q−m.
定理1.8有限域Fq上多项式f(X)是置换多项式,当且仅当存在正整数m,使得
1)f满足前m-1个Hermite条件.
2)f在Fq中有(q-m)个单簇点.
其中,称a∈Fq为f的一个单簇点,若f(X)=a在Fq中有唯一解.
推论1.9有限域Fq上多项式f(X)是置换多项式,如果存在正整数m,使得
1)degf<q−12m−1.
2)|f(Fq)|≥q−m.
等价地,我们有
等价描述设有限域Fq上次数为d的多项式f(X)不是置换多项式,若存在正整数m,使得f满足前2m-1个Hermite条件,那么f的值集大小|f(Fq)|≤q−1−m.特别地,
|f(Fq)|≤q−1−[uq(f)+12].
其中uq(f)为f满足前k个Hermite条件的最大的k≤q-2,而且万大庆与张起帆的结果均可导出Cohen定理1.3.
2、一些预备工作
首先介绍一下所要用到的有限生成代数相关知识(详细参见文献[13,14]).令K为一个域,称A为域K上(有限生成)n维代数,若A既是域K上n维向量空间,本身又是环,且满足
a(ξη)=(aξ)η=ξ(aη),∀ξ,η∈K,a∈A.
对∀ξ∈A,存在自然的线性变换Tξ:
Tξ:a→ξa,∀a∈K.
自然对线性变换Tξ,可以定义(线性代数的)迹Tr(Tξ),从而也可以定义A中元素ξ对于A/K的迹为Tr(Tξ);进一步地,设线性变换Tξ在取定的某组基(ξ1,…,ξn)下有变换矩阵M(ξ),对应特征值为λ1,…,λn,则ξ对于A/K的迹还可写作:
TrA/K(ξ)=Tr(Tξ)=Tr(A(ξ))=∑i=1nλi.
特别地,令K=Fq,设Fq[x]为Fq上全体函数的集合,则易验证知Fq[x]构成域Fq上的q维代数,且有同构成立:
Fq[x]≅Fq[X]/(Xq-X).
对于Fq[x]中函数f:x|→f(x),直接记为f(x)或f;特别地,Fq上恒等函数IdFq记作x.
由上述知,对∀f∈Fq[x],可以定义f对于Fq[x]/Fq的迹;进一步地,对Fq[x],有一组自然的基δi,i=1,…,q,此处δi(x)为Fq中元素ai的特征函数,而在这组基下,f对应特征值恰为f(ai),从而有:
TrFq[x]/Fq(f)=∑c∈Fqf(c),特别地TrFq[x]/Fq(x)=∑c∈Fqc.
利用上述的结果,我们也可重述Hermite判别法为:
定理2.1(Hermite判别法,迹形式)
f(X)是置换多项式⇔TrFq[x]/Fq(fk)=TrFq[x]/Fq(xk),k=1,2,…,q-1.
同理,令S为有限域Fq上一个给定的n元子集.设AS为S到Fq上的所有函数全体构成的集合,则AS也构成Fq上(有限生成)的n维代数,且有自然的同构:
AS≅Fq[X]/(m(X)).
此处m(X)=∏s∈S(x−s)为集合S的极小多项式,即零化S的次数最小的多项式;进一步地,对AS,依然有一组自然的基δi,i=1,…,n,此处δi(x)仍为S中元素si的特征函数,而f的对应特征值恰为f(si),从而有:
TrAS/Fq(f)=∑s∈Sf(s),特别地TrAS/Fq(x)=∑s∈Ss.
之后讨论中,若无特别注明,均将AS中函数f对于AS/Fq的迹略写为Tr(f).
3、主要定理与推论
定理3.1对S到Fq上函数f(x),有
f(x)为S到S上的双射⇔Tr(fk)=Tr(xk),k=0,1,…,2n-1.
这里右侧等式中x指S上的恒等函数
证明必要性显然,只需证明充分性.事实上,令g∈Fq[X]为满足下列条件的多项式函数:
那么在此定义下,g(x)至少有(q-n)-n=q-2n个单簇点,且有
由定理1.8,g必然是Fq上的置换多项式,从而f必然是S到S上的双射.
如果S=Fq,那么定理3.1自然导出Fq上经典形式的Hermite判别法,因而定理3.1确为Hermite判别法在子集上的推广.
进一步地,利用类似方法,有
定理3.2对S到Fq上函数f(x),f(x)是S上双射当且仅当存在正整数m,使得
1)Tr(fk)=Tr(xk),k=0,1,…,2m-1.
2)|f(S)∩S|≥n−m.
特别地,限制f为S到S上函数,则f(x)是S上双射当且仅当存在正整数m,使得
1)Tr(fk)=Tr(xk),k=0,1,…,2m-1.
2)|f(S)|≥n−m.
证明同定理3.1一样构造多项式函数g(x),迹等式条件自然成立;只需再注意到
|g(Fq)|=|f(S)∩S|+|Fq\S|≥n−m+q−n=q−m(3)
由定理1.7即知g必然是Fq上的置换多项式,从而f必然是S到S上的双射.
现在考虑次数推论的推广;考虑f的Lagrange插值多项式f0(X),我们有
推论3.3对S到Fq上函数f(x),f(x)是S上双射,如果存在正整数m≤[Uf+12]满足
1)degf0<Uf2m−1.
2)|f(S)∩S|≥n−m.
其中Uf是使得Tr(xk)=0,1≤i≤k成立的最大的k≤n-2.
特别地,限制f为S到S上函数,则f(x)是S上双射,如果存在正整数m,使得
1)degf0<Uf2m−1.
2)|f(S)|≥n−m.
其中Uf是使得Tr(xk)=0,1≤i≤k成立的最大的k≤n-2.
证明注意到fk0有自然的多项式表示,从而Tr(fk0)可由x的不超过kdegf0次幂的迹线性表出,而所给条件表明对0≤k≤2m-1,这些迹均为0,从而Tr(fk)和Tr(xk)均为0,满足迹等式条件,从而由定理3.2得证.
最后,同置换多项式的情况类似,如果S到Fq上函数f在S上不满,且f满足前一些迹等式条件,那么f(S)不能包含太多S中的元素(否则依前述,f为双射,矛盾).由此,我们可以将Fq中多项式上界估计推广到子集上.事实上,我们有
推论3.4假设函数f:S→Fq,f(S)≠S.如果存在正整数m使得Tr(fk-xk)=0,k=0,1,…,2m-1,那么f(S)不能包含多于n-1-m个S中的元素.特别地,
|f(S)∩S|≤n−1−[u(f)+12].
若限制f为S到S上函数,则函数f值集大小有上界估计
|f(S)|≤n−1−[u(f)+12].
其中u(f)是使得Tr(fk-xk)=0,1≤i≤k成立的最大的k≤n-2.
4、特殊子集上的讨论
作为应用实例,考虑F*q中n阶子群,即n次单位根群μn<F*q,其中n∣q-1.(关于n次单位根群μn的其他性质,详情参见文献[15])
μn上所有函数的集合Aμn显然构成Fq上有限生成n维代数,进一步有自然的同构:
Aμn≅F[X]/(Xn-1).
对子集μn,有
定理4.1
f(x)是n次单位根群μn上的双射⇔Tr(fk)=0,k=1,2,⋯,n−1⇔fk0(X)modXn−1无常数项,其中k=1,⋯,n−1
证明对S=μn,应用定理3.1,有
f(x)为μn到μn上的双射⇔Tr(fk)=Tr(xk),k=0,1,…,2n-1
注意到n次单位根群μn是循环群,即μn=(ξ0),其中ξ0为n次本原单位根,从而只需验证前n个迹等式条件成立.k≠0时,ξk0≠1,从而
Tr(xk)=∑i=0n−1(ξk0)i=(ξk0)n−1ξk0−1=0.(4)
而k=0时Tr(xk)=Tr(fk)=Tr(1)=n自然成立,从而第一个等价条件成立.又对插值多项式f0(X)=∑n−1i=0biXi,有
Tr(f0)=∑i=0n−1biTr(xi)=b0Tr(1)=nb0.(5)
即知第二个等价条件成立.
特别地,当n=q-1时,μn=F*q,补充定义f(0)=0,则上述定理自然导出Hermite判别法(定理1.2)
进一步地,我们有推论
推论4.2对μn到μn上函数f(x),f(x)是μn上双射当且仅当存在正整数m,使得
1)Tr(fk)=0,k=1,…,2m-1.
2)|f(μn)|≥n−m.
等价地,我们有
等价描述假设函数f:μn→μn不是双射,如果存在正整数m使得Tr(fk)=0,k=1,…,2m-1,那么f(μn)取值个数不能多于n-1-m.特别地,函数f值集大小有上界估计
|f(μn)|≤n−1−[u(f)+12].
其中u(f)是使得Tr(fk)=0,1≤i≤k成立的最大的k≤n-2.
最后,若插值多项式f0无常数项且次数足够小,那么可以导出与万大庆类似的结果:
推论4.3对μn到μn上函数f(x),f(x)是μn上双射,如果存在正整数m,使得
1)f0(0)=0,degf0<n−1m.
2)|f(μn)|≥n−m.
其中f0(X)是f在μn[x]上的Lagrange插值多项式.
等价地,我们有
等价描述假设函数f:μn→μn不是双射,d=deg(f0)为Lagrange插值多项式f0(X)的次数,若f0(0)=0,那么对任意满足m<n−1d的正整数m,f(μn)取值个数不能多于n-1-m.特别地,函数f值集大小有上界估计
|f(μn)|≤n−1−[n−2d].
5、结论
通过导入有限生成代数观点,将有限域上Hermite判别法成功推广到了其子集上,并在子集上推广了有限域上的函数相关的多个重要结果,并给出了计算实例;为有限域相关的理论在一般子集上的推广提供了一个新思路,主要结果对于有限域上特定子集的函数及自同态相关研究也有一定意义.
参考文献：
[14]冯克勤.代数数论[M].北京:科学出版社,2000:57.
郭异,张起帆.有限域子集上的Hermite判别法及推广[J].西南民族大学学报(自然科学版),2019,45(04):415-421.
基金:国防应用项目(0020105501055)
分享：
2008年应用Kuromoto-like模型对电网进行了深入的研究,同时得到了有效的电网动力学模型,并且得出:电网必须保持同步,很小的扰动会引起级联故障,导致大规模停电事故发生,这就表明电网的控制尤为重要.本文中,笔者基于反馈控制的思想,实现了对电网同步能力的改变,分析了反馈增益的取值对同步能力的影响.
2020-09-09
1、数论函数方程φ(φ(n))=S(n15)的可解性2、一个含有伪Smarandache函数的方程3、10的倍数分拆素数和的“1-9猜想”及思考4、有关数论函数φ(m)的一方程整数解的讨论5、纽结理论在数论中的应用6、用易经诠释考拉兹猜想7、数论函数方程φ2(n)=S(SL(nk))的可解性8、大学生就业当中的数学原理及其应用9、含混合型简数根函数的两个数论函数方程的解
2020-08-11
纽结理论看似与数论[1]毫不相干，但已有不少纽结方面的结果是用数论来表达的，例如文献[2]。本文将给出反向的情形，即利用纽结理论证明数论的2个结果： 定理1若m,n是互素的整数，则24整除(m2-1)(n2-1)。 定理2若m,n是互素的整数，则12整除(m-1)(n-1)(2mn-m-n-1)。 容易举例说明，若m,n不是互素，则定理就不成立。
2020-08-10
素数的判定算法是对输入的整数判定是素数还是合数，分为概率算法和确定算法。素数构造算法是输入小素数，经过若干次循环构造出大的素数。对已有的素数构造和判定算法进行梳理，给出算法的描述并编程实现Miller-Rabin素数测试算法、基于莱梅定理的素数构造算法、AKS素数测试算法及变体算法，对上述算法的效率进行比较。
2020-06-28
对于某些特殊的数学问题,即使只是简单地回答“知道”或者“不知道”,也有可能传送出一些有用的信息。考官C从区间[2,99]中选出两个整数n和m,将这两个数的和p=n+m与积q=n×m的数值分别告诉参加测试的智者B与智者A。C要求B与A说出n与m是多少,但不能将自己知道的p与q的值告诉对方。
2020-06-28
哥德巴赫猜想:任何大于4的偶数都可以用2个素数之和表示.本文对根据增殖算法得到的素数分布规律进行了深入的探讨,并在此基础上创建了素数周期循环分布表,计算出两个相邻素数的最大间隙不超过420,找出了105个位缺带对称群,并用位缺带全方位多重对称性证明了哥德巴赫猜想.
2020-06-28
文献[1,2]分别介绍了分解因子法与递归序列法在不定方程中的应用,本文介绍另一种初等方法——幂比较法,在不定方程中的应用.所谓幂比较法,是指在不定方程两边比较某因数的最高方幂,以此来导致矛盾的方法.本文利用幂比较法证明了以下定理1和定理2,并同时得到推论1、推论2和推论3.
2020-06-28
本文将研究包含了伪Smarandache函数Z(n)、简数根函数与p次幂原数函数Sp(n)的复合数论函数方程Z(n)=Sp(sim(n))(其中p=2,3,5)的可解性,并分别给出每个方程的全部解.并推广了一个关于计算p次幂原数函数Sp(n)值在n>p时,更加简易的计算公式以及证明该公式所用的方法.
2020-06-28
初等数论是小学教育专业的一门专业必修课，这门课程与中小学的联系比较紧密，学生开始学习第一章(整数的可除性)时，都觉得简单易懂，但从第二章(不定方程)开始，大部分学生就感觉上课基本能听懂，但一做练习就错，其实出现这种现象的原因就是学生没有真正理解初等数论中的数学思想方法。所以，研究初等数论的教学方法是数论教师必须要研究的一项重要课题。
2020-06-28
整数是数学研究的一个方向。组合数学中就有关于正整数在不同分部量下分拆数的研究。对于一个给定的不定方程(或方程组),它是否有解,如果有解,解是不是唯一的,能不能求出它的所有解,这是数论的一个研究方向。对每一个有基础解的方程,求解得出它的基础解,由这些基础解可以计算得到方程的多个整数解。
2020-06-28
人气：3666
人气：3317
人气：2817
人气：2693
人气：2596
我要评论
期刊名称：数学进展
期刊人气：3382
主管单位：中国科学协术协会
主办单位：中国数学会
出版地方：北京
专业分类：科学
国际刊号：1000-0917
国内刊号：11-2312/O1
邮发代号：2-503
创刊时间：1955年
发行周期：双月刊
期刊开本：16开
见刊时间：一年半以上
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
学术期刊咨询、科普杂志阅读、专利申请方案、课题研究设计、专著挂名咨询、论文下载、文献查询、原创文章检测、SCI实验设计方案等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-06-28
310
上传者：管理员
