有限域上n元n次方程只有零解的充要條件

陳璽,屈龍江,李超,2

(1.國防科技大學(xué)理學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)系,湖南長沙410073)

(2.信息保障科學(xué)與技術(shù)實驗室,北京100072)

有限域上n元n次方程只有零解的充要條件

陳璽1,屈龍江1,李超1,2

(1.國防科技大學(xué)理學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)系,湖南長沙410073)

(2.信息保障科學(xué)與技術(shù)實驗室,北京100072)

本文研究了有限域上只有零解的n元n次方程的結(jié)構(gòu)問題.利用對有限域上不可約多元多項式在其擴域中的分解特征的刻畫,結(jié)合Chevalley定理,得到了有限域上n元n次方程只有零解的一個充要條件,并給出這類方程的一些新的具體構(gòu)造.

有限域;方程只有零解;多元多項式分解;不可約多項式

1 引言

有限域上的多項式理論在編碼密碼、有限幾何、組合設(shè)計等領(lǐng)域均有非常重要的應(yīng)用,近年來得到了許多學(xué)者的關(guān)注和研究,詳見文[1,2]及其中的參考文獻.多元多項式方程解數(shù)的計算和估計是有限域上多項式理論的重要內(nèi)容,在工程實際中應(yīng)用廣泛,如應(yīng)用多項式理論構(gòu)造密碼系統(tǒng)、糾錯碼或者組合設(shè)計對象時,構(gòu)造對象的參數(shù)計算問題往往可以轉(zhuǎn)化為有限域上多項式方程解數(shù)的計算問題.然而,有限域上多元多項式方程的解的問題一直是困難的數(shù)學(xué)問題.Chevalley定理是該方面的一個重要結(jié)果:設(shè)f∈Fq[x1,···,xn]且滿足f(0,···,0)=0,deg(f(x1,···,xn))＜n,則方程f(x1,···,xn)=0在Fq上有非平凡解,即存在

使得f(c1,···,cn)=0.但是當n=deg(f(x1,···,xn))時,上述結(jié)論并不成立.Dickson[3,4]給出了如下反例:設(shè)n∈Z+,{α1,···,αn}為Fqn在Fq上的一組基.令

則f(x1,···,xn)為系數(shù)在Fq上的多項式,且方程f(x1,···,xn)=0在Fq上只有零解(0,···,0).該反例中的函數(shù)通常被稱為具有范形式,一個自然的問題是:有限域上只有零解的n元n次方程應(yīng)該具有什么樣的特征呢?能否構(gòu)造出更多這樣的例子呢?Carlitz[5]證明了若q≥13,f∈Fq[x1,x2,x3]為一個齊三次多項式,且滿足f在Fq上僅在(0,0,0)處為零,則f必然具有范形式.Terjanian[6]證明了若n次多項式f∈Fq[x1,···,xn]且在Fq上僅有零解,則對任意次數(shù)小于n的多項式g∈Fq[x1,···,xn],方程f(x1,···,xn)=g(x1,···,xn)在Fq上至少有一解.Carlitz[7],Felszeghy[8],Francis[9]等人先后給出了一些有限域上特殊的多元多項式方程的解的個數(shù)及解法.本文是對該問題的一個一般回答.首先給出了有限域上不可約多元多項式在其擴域中分解特性.在此基礎(chǔ)上,結(jié)合Chevalley定理,得到了有限域上n元n次多項式方程f=0在Fq上只有零解的一個充要條件.該條件在f不是完全不可約的情形下,更為具體的描述了f必須具有范形式.

全文結(jié)構(gòu)如下:第2節(jié)刻畫了有限域上不可約多元多項式在其擴域中分解特征;第3節(jié)給出了有限域上n元n次多項式方程f=0在Fq上只有零解的充要條件,并給出了一些具體的構(gòu)造實例;第4節(jié)總結(jié)并提出有待進一步研究的問題.

2 不可約多元多項式在其擴域中分解特征

為刻畫有限域上不可約多元多項式在其擴域中分解特點,首先引進一些基本概念和相關(guān)性質(zhì).

定義1設(shè)f(x1,···,xn)=為有限域FqN上的n元多項式.令

其中j≥0,即將多項式的每個系數(shù)都做qj次提升,稱f(qj)(x1,···,xn)為f(x1,···,xn)的qj次提升.

由定義直接可得如下結(jié)論.

引理1(f1(x1,···,xn)f2(x1,···,xn))(q)=

引理2f(x1,···,xn)不可約當且僅當f(q)(x1,···,xn)不可約.

引理3設(shè)f(x1,···,xn)∈Fq[x1,···,xn],f1(x1,···,xn)∈FqN[x1,···,xn]且滿足

證設(shè)f(x1,···,xn)=f1(x1,···,xn)H(x1,···,xn),H(x1,···,xn)∈FqN[x1,···,xn].

于是,由引理1有

另一方面,由f(x1,···,xn)∈Fq[x1,···,xn]知f(x1,···,xn)=f(q)(x1,···,xn).結(jié)合兩式,得進而對任意非負整數(shù)j(0≤j≤N-1),均有

定理1設(shè)f(x1,···,xn)為Fq上n元M次不可約多項式,f1(x1,···,xn)為FqN上n元l次首一不可約多項式,且滿足f1(x1,···,xn)|f(x1,···,xn).則有l(wèi)|M,FqM/l為包含f1(x1,···,xn)系數(shù)的最小域,且

對某個c∈Fq成立.

證設(shè)t為使得=bf1(x1,···,xn)對某個b∈FqN成立的最小正整數(shù).由f1(x1,···,xn)=知這樣的t一定存在.又因為f1(x1,···,xn)是首一的,故b=1,即=f1(x1,···,xn).進一步,Fqt為包含f1(x1,···,xn)所有系數(shù)的最小域.

由引理2和f1(x1,···,xn)為FqN[x1,···,xn]中首一不可約多項式知,j=0,···,t-1均為FqN[x1,···,xn]中的首一不可約多項式,因此多項式

因此

于是l|M,且t=M/l.由t的定義知,顯然FqM/l為包含f1(x1,···,xn)系數(shù)的最小域.

3 主要結(jié)果

3.1 n元n次方程只有零解時的充要條件

引理4(見文[1,推論6.9])設(shè)f1(x1,···,xn),···,fm(x1,···,xn)∈Fq[x1,···,xn],對i=1,···,m,滿足fi(0,···,0),且

則存在(c1,···,cn)(0,···,0),ck∈Fq,k=1,···,n使得fi(c1,···,cn)=0對i= 1,···,m成立.

定理2設(shè)f(x1,···,xn)為Fq上n元n次多項式,則f(x1,···,xn)=0在Fq上只有零解當且僅當對n的某個正因子l,f可以表示為如下形式

證(充分性)設(shè)f如(3.1)式表示.容易驗證f(x1,···,xn)確為Fq上n元n次多項式.下面只需證f(x1,···,xn)=0在Fq上只有零解.設(shè)存在(c1,···,cn),其中ck∈Fq,k=1···n,使得f(c1,···,cn)=0.則由(3.1)式知,存在0≤r≤n/l-1,使得

(必要性)設(shè)f(x1,···,xn)=0在Fq上只有零解,則由Chevalley定理知f(x1,···,xn)必在Fq上不可約.假若不然,設(shè)

為f(x1,···,xn)在Fq上的一個非平凡分解,則有f1(0,···,0)=0或者f2(0,···,0)= 0.不妨設(shè)f1(0,···,0)=0.但由1≤degf1(x1,···,xn)≤n-1和Chevalley定理知f1(x1,···,xn)=0在Fq上必有非零解,從而f(x1,···,xn)=0在Fq上也有非零解,矛盾！從而f(x1,···,xn)必在Fq上不可約.

若f(x1,···,xn)完全不可約,即其在Fq的任何擴域上均不可約,則有l(wèi)=n,令c=r1=1,g1=f.于是結(jié)論成立.

若f(x1,···,xn)不是完全不可約的,則存在Fq的某個擴域FqN上的l(1≤l＜n)次不可約多項式f1(x1,···,xn)滿足f1(x1,···,xn)|f(x1,···,xn).由定理1得l|n,Fqn/l為包含f1(x1,···,xn)系數(shù)的最小域,且

因為f1(x1,···,xn)是FqN上的l次多項式,所以存在r1,···,rm為Fqn/l中一組在Fq上線性無關(guān)的元素,g1(x1,···,xn),···,gm(x1,···,xn)為Fq上一組次數(shù)均不超過l的多項式,使

于是

由f(x1,···,xn)=0在Fq上只有零解知f1(x1,···,xn)=0在Fq上只有零解,又因為r1,···,rm∈FqN在Fq上線性無關(guān),所以方程組gi(x1,···,xn)=0,i=1,···,m在Fq上只有零解.

因為deg(gi(x1,···,xn))≤l,所以

若d＜n,由引理4,方程組gi(x1,···,xn)=0,i=1,···,m在Fq上有非零解,矛盾！所以n≥d≥ml.

另一方面,由r1,···,rm∈Fqn/l在Fq上線性無關(guān)知n/l≥m.于是m=n/l,且等號當且僅當deg(g1(x1,···,xn))=···=deg(gm(x1,···,xn))=l時成立.

綜上所述,此時

3.2 應(yīng)用及舉例

例1 F3上的4元4次多項式

在F3上只有零解,其中α∈F32F3.

證顯然f(x1,x2,x3,x4)是F3上的4元4次多項式.由于F32是F3的二次擴張, α∈F32F3,故1,α為F32在F3上的一組基.由定理2可得,f(x1,x2,x3,x4)=0在F3上只有零解當且僅當方程組

在F3上只有零解.注意到1是F3上的非平方元,g1=0當且僅當x1=-x2且x3=-x4,代入g2=0得-=0,從而x1=x3=0.進一步,x2=x4=0,即f(x1,x2,x3,x4)=0在F3上只有零解.

推論1設(shè)n為正整數(shù),l為n的某個正因子,x1,···,xn為n個不同的變元,xi1,···,xil, 0≤i≤n/l-1為變元x1,···,xn的一個分劃.設(shè)

證因為每個方程gi(xi1,···,xil)=0,i=1···n/l限制在自身l個變元上時,在Fq上只有零解,所以方程組gi(x1,···,xn)=0,i=1···n/l在Fq上只有零解.由定理2,命題成立.

在上述推論中,令l=1;對i=1,···,n/l=n令gi(xi)=xi,則得到前文Dickson的實例.

在推論1中,每個方程gi(xi1,···,xil)=0,i=1···n/l限制在自身l個變元上時,可以看做l元l次多項式

在Fq上只有零解.這表明可以用任意m個在Fq上只有零解的l元l次多項式,構(gòu)造出在Fq上只有零解的ml元ml次多項式.下面是一個具體的例子.

則n元n次方程f=0在Fq上只有零解.

注意到例2中的f沒有交叉項,利用反證法容易證明f不含一次因式,因此是與Dickson實例不同構(gòu)的只有零解的n元n次方程.例2利用n/2個限制在自身兩個變元上在Fq上只有零解的2次方程,構(gòu)造出了高次的只有零解的方程.

從定理2的證明可以看出,若f(x1,···,xn)完全不可約,則得到對應(yīng)定理2的l=n的平凡情形.但對于給定的有限域Fq和正整數(shù)n,這種平凡情形可能發(fā)生,也可能不能發(fā)生.如文[5]中表明對于給定有限域Fq,q≥13和正整數(shù)n=3,l=3時,定理2中的平凡情形是不存在的.

例3設(shè)F3上的4元4次多項式

容易驗證f(x1,x2,x3,x4)在F3上只有零解,且其在F3的任何擴域上均不可約.此時對應(yīng)定理2中l(wèi)=n的平凡情形.

4 總結(jié)與展望

本文首先刻畫了有限域上不可約多元多項式在其擴域中分解特征,然后結(jié)合Chevalley定理,得到了有限域上n元n次多項式方程f=0在Fq上只有零解的充要條件,并進一步構(gòu)造了一些具體實例.該條件在f不是完全不可約的情形下,更為具體的描述了f必須具有范形式.進一步也可以考慮給出更多具體的例子.例3表明了當f完全不可約時,定理2是平凡的,因此如何刻畫有限域上完全不可約的n元n次方程只有零解的條件依舊是一個值得研究的方向.

[1]Lidl R,Niederreiter H.Finite fields[M].Cambridge:Cambridge University Press,1997.

[2]Gary L Mullen,Daniel Panario.Handbook of finite fields[M].Boca Raton:CRC Press,2013.

[3]Dickson L E.On triple algebras and ternary cubic forms[J].Bulletin of the American Math.Soc., 1908,14(4):160–169.

[4]Dickson L E.On the representation of numbers by modular forms[J].Bulletin of the American Math. Soc.,1909,15(7):338–347.

[5]Carlitz L.A theorem of Dickson on nonvanishing cubic forms in a finite field[J].Proc.American Math.Soc.,1957,8(5):975–977.

[6]Terjanian,Guy.Sur les corps finis[J].C.R.Acad.Sci.Paris Sr.,1966,262:A167–A169.

[7]Carlitz L.Solvability of certain equations in a finite field[J].Acta Arith.,1961,7:389–397.

[9]Francis N Castro.On systems of linear and diagonal equation of degree pi+1 over finite fields of characteristic p[J].Finite Fields Appl.,2008,14(3):648–657.

THE STRUCTURE OF THE EQUATION OVER FINITE FIELDS WITH n UNKNOWNS AND WITH DEGREE n WHICH VANISH ONLY AT ZERO

CHEN Xi1,QU Long-jiang1,LI Chao1,2
(1.Departement of Mathematics and System Science,National University of Defense Technology, Changsha 410073,China)
(2.Information Assurance Science and Technology Laboratory,Beijing 100072,China)

In this paper,we investigate the structure of the equation over finite fields with n unknowns and with degree n which vanish only at zero.By using the factorization of the irreducible multivariable polynomial in some extension field and with the Chevalley Theorem, a sufficient and necessary condition of the equation with n unknowns and with degree n which vanish only at zero is obtained.Furthermore,we construct some explicit equations of this class.

finite field;equation which vanish only at zero;multivariate polynomial factorization;irreducible polynomial

tion:12E12;12E20

O153.4

A

0255-7797(2017)01-0138-07

2014-03-25接收日期:2014-09-09

國家自然科學(xué)基金資助(61272484);信息保障科學(xué)技術(shù)實驗室開放基金資助(KJ-12-02).

陳璽(1990–),男,遼寧大連,碩士,主要研究方向:編碼密碼理論及其應(yīng)用.