關(guān)于Ducci序列的周期性

周方敏

（肇慶學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 肇慶 526061）

1 概論

設(shè) v=(a0,a1,…,an-1)∈Zn,定義 Zn上的Ducci映射為

稱(chēng)序列

為Ducci序列,Ducci序列也叫n-數(shù)游戲.1800年,Ducci E首先研究了此映射.Ducci映射是一種差分方程,它與非線性動(dòng)力系統(tǒng)、混沌理論及數(shù)值分析都有關(guān)系[1-2].文獻(xiàn)[3]研究了Ducci映射與實(shí)數(shù)的連分?jǐn)?shù)的表示之間的關(guān)系.文獻(xiàn)[4]列舉了一些有關(guān)Ducci序列的公開(kāi)問(wèn)題.

Ducci序列Dv中的元素最終會(huì)落到集合{0 ,1}n中去[5-6],因此它本質(zhì)上是F2n中的序列.由于F2n是有限集,因此Dv是周期序列,其周期由初始向量v及其維數(shù)n唯一確定.文獻(xiàn)[7]研究了Ducci序列的最大周期與有限維元胞自動(dòng)機(jī)的最大周期的關(guān)系.由于歷史原因,人們一直在研究如何用維數(shù)n來(lái)刻畫(huà)Dv的周期[4,6,8].

第1個(gè)結(jié)論是:當(dāng)n為2的方冪時(shí),Dv的周期恒為1(即序列中只有有限個(gè)非零向量)[9-10].當(dāng)維數(shù)固定時(shí),對(duì)于不同的初始向量v,Dv的周期也不同.Dv的最大周期和周期分布也是人們熱衷研究的對(duì)象.文獻(xiàn)[11]給出了最大周期的一些整除性質(zhì)及數(shù)值計(jì)算結(jié)果.文獻(xiàn)[12]證明了,當(dāng)整數(shù)k不是2的方冪時(shí),一定存在以k為周期的Ducci序列.文獻(xiàn)[13]指出:研究Dv的周期實(shí)際上是研究F2的某個(gè)擴(kuò)域中的n次單位根在加1之后的乘法階的變化情況.在現(xiàn)有文獻(xiàn)中,研究Dv的周期的工具主要有2種:線性空間F2n上矩陣的最小多項(xiàng)式和定義于F2上的環(huán)中的元素的乘法.這2種工具各有優(yōu)勢(shì),但本質(zhì)上是等價(jià)的.

本文利用環(huán)中元素乘法研究Dv的周期,證明Dv的周期等于環(huán)中某個(gè)元素的乘法階,并指出Dv的周期性質(zhì)類(lèi)似于有理數(shù)的p-adic展開(kāi)式的周期性質(zhì).

設(shè) v=(a0,a1,…,an-1)∈F2n,定義F2n上的Ducci映射

可以看出,以這種方式定義的F2n上的Ducci映射本質(zhì)上與Zn上的Ducci映射等價(jià).稱(chēng)序列

為F2n上的Ducci序列.定義

根據(jù)歸納法,有

根據(jù)映射F和的定義,能夠?qū)ucci映射轉(zhuǎn)化到環(huán)里元素的乘法,因此Ducci映射的周期性就轉(zhuǎn)化到環(huán)里元素的周期性.

2 Ducci序列的周期性

定義1設(shè)v∈F2n,若存在自然數(shù)u和正整數(shù)e,使得Tuv=Tu+ev,則稱(chēng)e為Dv的周期;稱(chēng)滿(mǎn)足Tuv=Tu+ev的最小自然數(shù)u為Dv的不循環(huán)長(zhǎng)度.

下面給出本文的主要結(jié)論及其證明.

定理1設(shè)v∈F2n,且的最簡(jiǎn)分式是,gcd(b(x),1+x)=1,α≥0.則Dv的最小正周期是1+xmodb(x)的乘法階,不循環(huán)長(zhǎng)度為α.

證設(shè)1+xmodb(x)的乘法階為e,則

在式(1)的兩邊同乘以 gcd(F(v),1+xn)(1+x)α,得

設(shè)k是Dv的1個(gè)周期,β是Dv的不循環(huán)長(zhǎng)度,即Tβ+kv=Tβv,則

在上式中消去gcd(F(v),1+xn),可得

因?yàn)?gcd(a(x),(1+x)αb(x))=1,所以

得(1+x)β≡0 mod(1+x)α,這表示β≥α.所以Dv的不循環(huán)長(zhǎng)度為α.

因?yàn)間cd(1+x,b(x))=1,式(2)表明(1+x)k≡1 modb(x).滿(mǎn)足前式的最小正整數(shù)k是1+xmodb(x)的乘法階.

注1 Ducci序列的周期性與有理數(shù)r=a/(pab)(這里gcd(a,pαb)=gcd(p,b)=1)的p進(jìn)制展開(kāi)式的周期性類(lèi)似.r的p進(jìn)制展開(kāi)式的循環(huán)節(jié)長(zhǎng)度是pmodb的乘法階,r的不循環(huán)長(zhǎng)度為α.r的循環(huán)節(jié)長(zhǎng)度只被b確定,而r的循環(huán)節(jié)被a和b確定.

注2 根據(jù)有限域上的多項(xiàng)式理論,1+xmodb(x)的乘法階等于多項(xiàng)式b(x+1)在環(huán)F2[x]/(1+xn)中的階[14].

下面討論最小正周期達(dá)最小值(周期為1)和最大值的Ducci序列.易知,Dv的周期為1當(dāng)且僅當(dāng)Dv中的序列最終都是零向量.

命題1設(shè)n=2km是正整數(shù),m為奇數(shù),且v∈F2n,則Dv的周期為1當(dāng)且僅當(dāng)是F(v)的因子.特別地,若n是2的方冪,則序列Dv的周期為1.

證Dv的周期為1,當(dāng)且僅當(dāng)存在整數(shù)i≥2k,使得Tiv是零向量;當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)因?yàn)?/p>

命題2設(shè)n=2km是正整數(shù),m為奇數(shù),且w=(1,0,…,0)∈F2n,則Dw是集合{Dv|v∈F2n}中具有最大的最小正周期的元素.

證這里所使用的符號(hào)同定理1.任取設(shè)xn+1=(x+1)2kg(x),則b(x)|g(x)且所以,g(x+1)的階大于或者等于b(x+1)的階,因此Dw最小正周期是最大的.

例1設(shè)n=2?32,xn+1=(1+x)2(1+x+x2)2(1+x3+x6)2=(1+x)2p(x)2q(x)2,ordp(1+x)=3,ordq(x+1)=63.

1)取w=(1,0,…,0),F(w)=1,ordp(x+1)2q(x+1)2=126,所以序列Dw的不循環(huán)長(zhǎng)度為2,周期為126.