關于Golomb猜想的一般化

祁 蘭，張文鵬

(1.榆林學院 數(shù)學與統(tǒng)計學院, 陜西 榆林 719000；2.西北大學 數(shù)學學院, 陜西 西安 710127)

?

·數(shù)理科學·

關于Golomb猜想的一般化

祁 蘭1，張文鵬2

(1.榆林學院 數(shù)學與統(tǒng)計學院, 陜西 榆林 719000；2.西北大學 數(shù)學學院, 陜西 西安 710127)

設p為奇素數(shù)，c是任意與p互素的整數(shù)。那么Golomb猜想可以簡單描述為對任意素數(shù)p≥3,存在模p的兩個原根α，β，使得α+β≡cmodp。文中的主要目的是推廣這一結果，即利用特征和的估計以及原根的判別性質證明更一般的結論：設p為充分大的素數(shù)，k為給定的正整數(shù)。對于任意給定的兩兩不同余的整數(shù)c1,c2,…,ck且(p,c1c2…ck)=1，一定存在模p的k+1個原根β1，β2，…，βk及α使得βi+α≡cimodp,i=1,2,…,k。顯然當k=1時就是Golomb猜想。所以，該結果是Golomb猜想的進一步推廣和延伸。

Golomb猜想；一般化；特征和的估計；原根的判別方法；漸近公式

設p是一個素數(shù)，r是一個正整數(shù),q=pr,GF(q)表示特征為p的有限域。Golomb在文獻[1]中研究Costas列陣時，提出了如下3個猜想:

(I) 任何有限域GF(q)包含兩個原根α及β使得α+β=1；

(II) 任何有限域GF(q)包含兩個原根α及β使得α+β=-1；

(III) 當q充分大時,對任意非零元素ε∈GF(q),一定存在兩個原根α,β∈GF(q)使得α+β=ε。

這些猜想后來被基本解決,也就是對一些特殊的q或者所有充分大的q,這3個猜測全部成立。有關文章可參閱文獻[2-6]。這里不再一一闡述。本文的主要目的是將這一猜想進行推廣和延伸,即討論下面兩個問題:

(A) 設p為奇素數(shù),k為給定的正整數(shù),c1,c2,…,ck∈GF(p)為k個非零元素。那么GF(p)一定包含k+1個原根α,β1,β2,…,βk，使得

βi+α=ci,i=1,2,…,k。

(B) 設p為奇素數(shù),k為給定的正整數(shù),c1,c2,…,ck∈GF(p)為k個非零元素。那么GF(p)一定包含k+1個原根α,β1,β2,…,βk，使得

βi-α=ci,i=1,2,…,k。

顯然這兩個問題是Golomb猜想當q=p時的一般化,當k=1時即就是Golomb猜想。本文利用特征和的估計以及原根的判別性質證明對任意給定的正整數(shù)k≥1, 當p充分大時上式問題成立。為敘述方便,這里我們僅討論q=p為奇素數(shù)的情況。設p為奇素數(shù),k為給定的正整數(shù)。對任意兩兩模p不同余的整數(shù)c1,c2,…,ck且(c1c2…ck,p)=1，設N(p)表示區(qū)間[1,p-1]中所有正整數(shù)n的個數(shù)使得k+1個整數(shù)n,c1-n,c2-n,…,ck-n均為模p的原根;設M(p)表示區(qū)間[1,p-1]中所有正整數(shù)n的個數(shù)使得k+1個整數(shù)n,c1+n,c2+n,…,ck+n均為模p的原根，則有下面的結論。

定理1 設p為奇素數(shù),k為給定的正整數(shù)。則對于任意給定的兩兩不同余的整數(shù)c1,c2,…,ck且(p,c1c2…ck)=1, 有漸近公式

定理2 設p為奇素數(shù),k為給定的正整數(shù)。則對于任意給定的兩兩不同余的整數(shù)c1,c2,…,ck且(p,c1c2…ck)=1， 有漸近公式

M(p)=

其中φ(n)為Euler函數(shù)，ω(n)表示n的所有不同素因數(shù)的個數(shù)。

推論1 設p為充分大的奇素數(shù),那么一定存在模p的3個原根α,β及γ，使得β+α≡1 modp;γ+α≡-1 modp。

推論2 設p為充分大的奇素數(shù),那么一定存在模p的3個原根α,β及γ，使得β-α≡1 modp;γ-α≡-1 modp。

顯然我們的結論在有限域GF(p)上也成立,其證明方法完全一樣,這里不再重復。

1 幾個引理

引理1[7]設p為奇素數(shù)。那么對任意整數(shù)c且(c,p)=1, 有恒等式

其中e(y)=e2πiy,indc表示c對于模p某一原根的指標，μ(n)是M?bius函數(shù)。

引理2[11]設p為奇素數(shù),k為正整數(shù),χ1,χ2,…,χk是模p的k個Dirichlet特征且至少有模p的一個非主特征。設f(x)是有限域GF(p)上的任一d次多項式。那么對GF(p)中任意兩兩不同的α1,α2,…,αk有估計式

2 定理的證明

本節(jié)給出定理的簡單證明。在證明過程中我們需要用到一些初等數(shù)論知識,其內容和結論都可以在初等數(shù)論教材中找到[8-10]。

首先證明定理1。 設N(p)表示區(qū)間[1,p-1]中所有滿足條件n,c1-n,c2-n,…,ck-n均為模p原根的正整數(shù)n的個數(shù)，則由引理1，有

(1)

p+O(k)。

(2)

另一方面，當hi(i=0,1,2,…,k)中至少有一個比如hs不為1時，此時χ(rs,hs;n)至少為模p的一個非主特征，于是注意到(c1c2…ck,p)=1，由引理2有估計式

χ(rk,hk;ck-n)=χ(r1,h1;-1)…

注意到恒等式

其中ω(n)表示n的所有不同素因子的個數(shù)。

注意到μ(1)=φ(1)=1，應用(1)，(2)及式(3)可得漸近公式

N(p)=

于是證明了定理1。

同理應用估計式

以及

并注意定理1的證明方法，不難推出漸近公式

M(p)=

于是完成了定理2的證明。

[1]GOLOMBS.OnthealgebraicconstructionforConstasarrays[J].JournalofCombinatoialTheory(Ser.A.), 1984，37：13-21.

[2]WANGJ.OnGolomb′sconjecture[J].ScienceinChina(Ser.A.), 1987,9:927-935.

[3]ZHANGWen-peng.OnaproblemrelatedtoGolomb′sconjectures[J].JournalofSystemsScienceandComplexity,2003,16:13-18.

[4]COHENSD,ZHANGWen-peng.SumsofTwoExactPowers[J].Finitefieldsandtheirapplications, 2002,8:471-477.

[5]WANGP,CAOX，F(xiàn)ENGR.Ontheexistenceofsomespecificelementsinfinitefieldsofcharacteristic2 [J].Finitefieldsandtheirapplications, 2012,18:800-813.

[6]TIANT，QIW.Primitivenormalelementanditsinverseinfinitefields[J].ActaMathematicaSinica, 2006,49:657-668.

[7] NARKIEWICZ W. Classical Problems in Number Theory [M].Warszawa:PWN-Polish Scientific Publishers, 1987:79-80.

[8] APOSTOL M.Introduction to Analytic Number Theory[M].New York:Springer-Verlag, 1976.

[9] 華羅庚.數(shù)論導引[M].北京:科學出版社, 1980.

[10] 張文鵬,李海龍.初等數(shù)論[M].西安:陜西師范大學出版社, 2012.

[11] BOURGAIN J, GARAEV M Z, KONYAGIN S V, et al. Shparlinski, on the hidden shifted power problem [J].SIAM Journal on Scientific Computing, 2012,41:1524-1557.

(編 輯亢小玉)

On the generalization of Golomb′s conjecture

QI Lan1， ZHANG Wen-peng2

(1.College of Mathematics and Statistics, Yulin University, Yulin, 719000, China; 2.School of Mathematics, Northwest University, Xi′an 710127， China)

Letpbe an odd prime,cbe any integer with (p,c)=1. The Golomb′s conjecture can be simply described as there exist two primitive rootsαandβmodpsuch thatα+β≡cmodp. In this paper, we give a generalized result. That is, we will use the estimate for character sums modpand the discriminant method of primitive roots modpto prove the following general conclusion: Letpbe an odd prime large enough,kbe any fixed positive integer. Then for any integersc1,c2,…,ckwith (c1c2…ck,p)=1, there existk+1 primitive rootsβ1,β2,…,βkandαmodpso thatβi+α≡cimodp,i=1,2,…,k. It is clear that this result in fact is Golomb′s conjecture, ifk=1.So the result is a generalization of Golomb′s conjecture.

Golomb′s conjecture; generalization; the estimate for character sums; the discriminant method of primitive roots modp; asymptotic formula

2014-04-11

國家自然科學基金資助項目(11371291)；陜西省教育廳科研專項基金資助項目(2013JK0889)

祁蘭，女，陜西榆林人，從事初等數(shù)論研究。

O156.7

：ADOI：10.16152/j.cnki.xdxbzr.2015-02-005