The cyclotomic numbers of order k=2m-1

-, -, -

(School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China)

Abstract： Let n=2m be an even number, for k=2m-1, we provide a method to calculate all the corresponding k-th cyclotomic numbers ai,j over the finite field 2n, and study the value distribution of the k-th cyclotomic matrix. These results can be used to construct a class of de Bruijn sequences by jointing all the cycles of the graph state of the linear shift register with irreducible connective polynomials, and the number of cycles that are joined is as many as possible.

Key words： cyclotomic class; cyclotomic number; finite field; trace; de Bruijn sequence

0 Introduction

The cyclotomic numbers have many applications in coding theory and combinatorial designs. In coding theory, for example, Delsarte et al.[1]used the cyclotomies to construct two-weight irreducible cyclic codes, which was called the “semi-primitive” case, i.e.,k|2s+1 and 2s|n.

Cyclotomies can be used to construct difference sets[2-3], which is an important structure in combinatory designs. There are many results on the cyclotomic numbers for the case of prime finite fields[4-10].

A de Bruijn sequence of stagenis a binary sequence with period 2nwhich contains all binaryn-tuples. De Bruijn sequences can be generated by the cycle join method from a linear feedback shift register(LFSR), especially from irreducible codes[11-18].

In Ref.[19], the authors establish an isomorphism from the finite field2nto stage space2n={(a1,a2, …,an)|ai∈2}, which maps cyclotomic classes to the cycles of the LFSR generated by the irreducible definition polynomialf(x) of the finite field2n, and maps pairs (α,α+1) to conjugate states, and hence the cyclotomic matrix can be used to calculate the number of de Bruijn sequences generated from the LFSR by the cycle join method.

From what we said above, we consider the cyclotomic numbers of the binary finite field2n. From the contribution of Delsarte et al., the semi-primitive case of cyclotomic numbers can be easily derived. In this paper, we consider the casefor even field dimensionn.

1 Preliminaries

We consider the binary finite field2n, letθbe the primitive element of this field. Supposekdivides 2n-1, letl=(2n-1)/k. For everyj=0, 1, 2, …,k-1, we call the subsets of the finite field2n

Tj={θu·k+j|u=0,1,2,…,l-1}

thek-th cyclotomic classes. So there arekcyclotomic classesT0,T1, …,Tk-1. For each pair of cyclotomic classesTiandTj, the cyclotomic number, denoted by (i,j)kis defined to be the number of elements of the set

{(α,α+1)|α∈Ti,α+1∈Tj}

(1)

Firstly, the following lemma and corollary can be easily derived form the basic arithmetics of the finite field2n:

Lemma1Thek-th binary cyclotomic numbersai,jprocesses the following relation:

(1)ai,j=aj,i;

(2)ai,j=a2i,2j;

(3)ai,j=ak-i,j-i=ai-j,k-j;

all the operations on the subscripts are modk.

Corollary1For everyi=1, 2, …,k-1,a0,i=ai,0=a-i,-i.

In Ref.[1], the authors calculate the weight-distributions of binary semi-primitive cyclic codes of even length:nis even and 2n-1=kl, there exists an integerssuch thatk|2s+1 ands|n. For each cyclotomic class

Tj={θuk+j|u=0,1,2,…,l-1},

we define a define corresponding binary vectorS(Tj) of dimensionnas follwing:

S(Tj)={Tr(θj),Tr(θk+j),Tr(θ2k+j), …,

Tr(θ(l-1)k+j)}

(2)

whereTr(x) is the trace function of2n, defined byTr(x)=x+x2+x22+… +x2n-1for allx∈2n.

Theorem1[1]Letsbe any divisor of 2r+1, and letkbe an even multiple ofr, sayk=2mr. Then the irreducible code of lengthn=(2k-1)/sand dimensionkoverGF(2) has only two distinct weightsw0andw1which are the unique solution of the following equations

(3)

From this result, and by using the method of exponent sum, we can easily get the following result:

that is, there are only three values in the matrix: ①a0,0denotea; ② excepta0,0, all the other elements of the first row, the first column and the diagram have the same valueb; ③ all the other elements of the matrix have the same valuec. Furthermore, we have that

a=x(x+(-1)m(3-k))-1,
b=x(x+(-1)m),
c=x2

(4)

We consider the quadratic equation over finite field2n. The general quadratic equation over finite field2nhas the following form:

x2+ax+b=0

(5)

witha,b∈2n. Ifa=0, the Eq.(5) has only one root, since the mapxx2is an automorphism of2n. Ifa≠0, by dividinga2on both sides of Eq.(5), we get the following form:

z2+z+c=0

(6)

withc=b/a2∈2n. The following Lemma 2 can be proven easily.

Lemma2Ifcis an element of2n, then the Eq.(6) has 2-2Tsolutions over2n, whereT=Tr(c). Furthermore, ifzis one solution, then the other solution isz+1.

Corollary2Ifa≠0, then the quadratic Eq.(5) has two solutions if and onlyTr(b/a2)=0.

2 The cyclotomic number of order

In number theory, we have the following lemma:

Lemma3Suppose thatGis a finite cyclic group, andHis a subgroup ofGof orderl, then for everya∈G,a∈Hif and only ifal= 1, where 1 denotes the identity element of the groupG.

Sincen=2m, the finite field2nhas a unique finite subfield2m. Letθbe a primitive element of2n. For every nonzero elementα∈2n,α∈2mif and only ifα2m-1=1, that isαk=1. Therefore2m{0}={θjl|j=0, 1, 2, …,k-1}. Thus we have the following lemma:

Lemma4Supposen=2m,k=2m-1, andl=2m+1, then in the finite field2n, all the elementsθjlare distinct for allj=0, 1, 2, …,k-1.

Furthermore, we have the following lemma:

Lemma5Eachk-th cyclotomic classTicontains only one element of the formθjl.

ProofFromk=2m-1 andl=2m+1, we know thatkandlare coprime, so the congruent equationuk+i≡0 (modl) has only one solutionu. That is, thek-th cyclotomic classTicontains only one elementθuk+iwhich has the form ofθjl. Since all thek-th cyclotomic classes are disjoint, each cyclotomic classTicontains only one nonzero element of the subfield2m.

□

In the following, we use the symbolT1(α) to denote the trace function over the subfield2mof2n, that is, for everyα∈2m(i.e., for every elementα∈2nof the formθjl),T1(α)=α+α2+α22+…+α2m-1.

Now, we will prove the following lemma, which gives the bound of all thek-th cyclotomic number:

Lemma6For everyi,j=0, 1, 2, …,k-1, thek-th cyclotomic numberai,j≤2.

ProofLetGbe the multiplicative group of all the nonzero elements of the finite field2n, andθbe the primitive element, thenGis a cyclic group of order 2n-1. The cyclotomic classT0is the unique subgroup of orderlgenerated by the elementθk, in the following, we useHinstead ofT0for simplicity. The other cyclotomic classesTjare just the left cosetsθjHofHinG.

For any giveni,j=0, 1, 2, …,k-1, ifai,j=0, the assertion is true. Now assume thatai,j>0. Then there exist an elementα=θuk+i∈Ti=θiH, such that 1+α∈Tj=θjH. Therefore (1+α)θ-j=(1+θuk+i)θ-j∈H, and by Lemma 3, we have that (1+θuk+i)lθ-lj=1, it is the same thing as

(1+θuk+i)l=θjl

(7)

We calculate the left side of Eq.(7) as following:

(1+θuk+i)l=(1+θuk+i)2m+1=

(1+θuk+i)2m(1+θuk+i)=

(1+θ2m(uk+i))(1+θuk+i)=

1+θ2m(uk+i)+θuk+i+θil

whereθ2m(uk+i)θuk+i=θ(2m+1)(uk+i)=θl(uk+i)=θil. Sincek=2m-1, then 2m(uk+i)=2muk+(2m-1)i+i=(2mu+i)k+i. Letu1be the remainder oflthat divides 2mu+i, that is, there exist 5 an integerqsuch that 2mu+i=ql+u1, with 0≤u1

θ2m(uk+i)=θ(2mu+i)k+i=θqlk+u1k+i=θu1k+i∈Ti.

Now, the Eq.(7) becomes

θuk+i+θu1k+i=1+θil+θjl

(8)

Setξ=1+θil+θjl, then bothα=θuk+iandα1=θu1k+iinTiare the roots of the following equation in the finite field2n:

x2+ξx+θil=0

(9)

Leti,jbe given as above, we define the setΓi,j={γ∈Ti|1+γ∈Tj}. Notice that the Eq.(9) is only related toiandj, all the element ofΓi,jare the solutions of the Eq.(9). Since the quadratic equation over any field has at most two roots, we have thatai,j=|Γi,j|≤2 for thisiandj. Therefore, the assertion of Lemma 6 is true.

□

Now, we can prove the following result:

Theorem3Suppose thatn=2m, andk=2m-1,l=2m+1. Letθbe a primitive element of the finite field2n, then we have that

(1)ai,j=1 if and only if 1+θil+θjl=0.

(2) For all thei,j=0, 1, 2, …,k-1, such thatξ=1+θil+θjl≠0, then

ProofNotice that the coefficientsξ=1+θil+θilandθjlof the Eq.(9) belong to the subfield2m. We will consider the general quadratic Eq.(9) of alli,j=0, 1, 2, …,k-1.

Ifξ=1+θil+θjl=0, then the quadratic Eq.(9) becomes

x2=θil

which has only one solution. Therefore,ai,j=1. In this case, the corresponding elementα∈Tibelongs to the subfield2m. On the other hand, ifai,j=1, then there exists only one elementa∈Tisuch that 1+α∈Tj, sinceαis the solution of the Eq.(9), thenξmust be zero, otherwise, this quadratic equation would have two solutions inTi, contrary to the condition thatai,j=1.

Ifξ= 1+θil+θjl≠0, setη=θil/ξ2. By dividing both sides of Eq.(9), we get the following quadratic equation

z2+z+η=0

(10)

If the trace functionT1(η) of the subfield2mis zero, then the quadratic Eq.(10) has two solutions in2m, in this case, the correspondingk-th cyclotomic numberai,jmust be zero. Otherwise, thek-th cyclotomic classTiwould contain two solutions of the quadratic Eq.(9), which belong to the subfield2m, contrary to the Lemma 5.

If the trace functionT1(η) of the subfield2mis one, we will prove that the correspondingk-th cyclotomic numberai,j=2. In this case, the quadratic equation of the form Eq.(9) has no solution in the subfield2m, i.e., it is irreducible over2m, and it has two solutions in the large field2n. Letαbe one of its solution, then,αmust belong to one of thek-th cyclotomic class, sayTr. By the process of the proof of Lemma 6,αis a solution of the following quadratic equation:

x2+(1+θrl+θjl)x+θrl=0.

We know that, any two different irreducible polynomial over any field can not contain a common solution, thereforeθrl=θil, andr=i, that is, the quadratic Eq.(9) has two solutions in thek-th cyclotomic classTi. Hence the correspondingk-th cyclotomic numberai,j=2, which completes the proof.

□

The following example illustrates the idea in the proof of Theorem 3:

Example1It is easy to verify thatf(x)=x6+x+1 is a primitive polynomial of degreen=6 over the finite field2. Letθbe a root off(x), then each element of the finite field26has a unique formc5θ5+c4θ4+c3θ3+c2θ2+c1θ+c0with eachci∈2={0,1}, the binary 0-1 stringc5c4c3c2c1c0of length 6 can be used to represent the field element of26, yet we would like to use the corresponding hexadecimal form for short. For example, the binary form of the field elementθ5+θ3+θ2+1 is 101101, and the corresponding hexadecimal form is 2d.

Letk=7,l=9, then the 7-th cyclotommic classes are listed as follows:

T0={1,θ7,θ14,θ21,θ28,θ35,θ42,θ49,θ56}={01, 06, 14, 3b, 1c, 0b, 3a, 1a, 1f},

T1={θ,θ8,θ15,θ22,θ29,θ36,θ43,θ50,θ57}={02, 0c, 28, 35, 38, 16, 37, 34, 3e},

T2={θ2,θ9,θ16,θ23,θ30,θ37,θ44,θ51,θ58}={04, 18, 13, 29, 33, 2c, 2d, 2b, 3f},

T3={θ3,θ10,θ17,θ24,θ31,θ38,θ45,θ52,θ59}={08, 30, 26, 11, 25, 1b, 19, 15, 3d},

T4={θ4,θ11,θ18,θ25,θ32,θ39,θ46,θ53,θ60}={10, 23, 0f, 22, 09, 36, 32, 2a, 39},

T5={θ5,θ12,θ19,θ26,θ33,θ40,θ47,θ54,θ61}={20, 05, 1e, 07, 12, 2f, 27, 17, 31},

T6={θ6,θ13,θ20,θ27,θ34,θ41,θ48,θ55,θ62}={03, 0a, 3c, 0e, 24, 1d, 0d, 2e, 21}.

From this, we can calculate easily the 7-th cyclotomic matrix of26as follows:

We calculate the trace functionT1(x) of the subfield23for allx∈23as following:

T1(0)=0,

T1(1)=1+1+1=1,

T1(θ9)=θ9+θ18+θ36=18+0f+16=1=

T1(θ18)=T1(θ36),

T1(α27)=θ27+θ54+θ45=0e+17+19=0=

T1(θ54)=T1(θ45).

It is easy to check that 1+θ2l+θ3l=1+0f+0e=1, so the cyclotomic numbera2,3=1.

To compute the cyclotomic numbera3,6, letξ=1+θ3l+θ6l=1+θ27+θ54=01+0e+17=18=θ9, thenθil/ξ2=θ3l/θ2l=θ9, sinceT1(θil/ξ2)=T1(θ9)=1, we havea3,6=2 by Theorem 3.

To compute the cyclotomic numbera4,5, letξ= 1+θ4l+θ5l=1+θ36+θ45=01+16+19=0e=θ27=θ3l, thenθil/ξ2=θ4l/θ6l=θ5l, sinceT1(θil/ξ2)=T1(θ5l)=0, we havea4,5=0 by Theorem 3.

In fact, the proof of Lemma 6 provides another method to calculate the cyclotomic numberai,jas following:

Now, we can show that the cyclotomic classTican be partitioned into subsets of the form {θuk+i,θu1k+i}, whereu1is the remainder ofldivides 2mu+ias above. Since 2mu1+i≡22mu+2mi+i=(2n-1)u+(2m+1)i+u=lku+li+u≡u(modl),uis the remainder ofldivides 2mu1+i. Furthermore, if 0≤v

For each subset {θuk+i,θu1k+i}, from the relation (8), we can obtain a uniquej, and then the corresponding cyclotomic numberai,jequals the cardinal number of the subset {θuk+i,θu1k+i}.

Example2Letn=6,k=7,l=9, we consider the finite field26as in Example 1. We takei=3 as an example to illustrate the idea used in the above statement:

Letu=0, thenu1≡2mu+i=23·0+3≡3 (mod 9), we have the subset {θ3,θ3k+3=θ24}. By Eq.(8), we shall compute the unique valuejwith 0≤j

Letu=1, thenu1≡2mu+i=23·1+3≡2 (mod 9), we get the subset {θ10,θ17}. By the similarly calculation, we have thatj=5, and thusa3,5=2.

Letu=4, thenu1≡2mu+i=23·4+3≡8 (mod 9), we get the subset {θ31,θ59}. By the similarly calculation, we have thatj=6, and thusa3,6=2.

Letu=5, thenu1≡2mu+i=23·5+3≡7 (mod 9), we get the subset {θ38,θ52}. By the similarly calculation, we have thatj=0, and thusa3,0=2.

Letu=6, thenu1≡2mu+i=23·6+3≡6 (mod 9), we get the subset {θ45}, which contains only one element. Sinceθjl=1+θil=1+θ27=0f=θ18, we have thatj=2, and thusa3,2=1.

3 The value distribution of the (2m-1)-th cyclotomic matrix

The result of Theorem 3 just provides a method to compute eachai,j, and can not give any global information of the wholek-th cyclotomic matrixA=(ai,j)k×k. In this section, we study the value distribution of this cyclotomic matrix. Let2mbe any finite field, for eachα∈2mwithα≠0, we define a mapψα(x) parameterized byα:

(11)

The following Lemma 7 shows that the mapψα(x) is a one-to-one map from the finite field2minto itself for every nonzero elementα∈2m:

Lemma7For every nonzeroα∈2m, the mapψα(x) defined by Map (11) is a one-to-one map.

ProofIt is necessary to show that this map is onto, since the set2mis finite. For everyy∈2m, ify=0, thenψα(1+α)=yby definition of the Map (11). Ify≠0, we can solvexform

□

Lemma8For every nonzeroα∈2m, we have thatwhereTr(x) is the trace function of the finite field2m.

ProofFor every nonzero elementα∈2m, we consider the following quadratic equation over the finite field2m:

x2+(1+α)x+α=0.

□

Theorem4Supposen=2mis an even integer, letk=2m-1, andl=2m+1, then thek-th cyclotomic matrixA=(ai,j)k×kof finite field2nprocesses the following properties:

(1)a0,0=0, ifmis even, anda0,0=2, ifmis odd.

(2) In the first row, there are 2m-1elements taking value 2, and the other 2m-1-1 elements taking value 0.

(3) In each of the other rows, there are 2m-1elements taking value 2, only one element taking value 1, and all the other 2m-1-2 elements taking value 0.

Proof(1) Ifi=0,j=0, then the correspondingξ= 1+θil+θjl=1, andθil/ξ2=1, and henceT1(θil/ξ2)=T1(1) =m(mod 2). By the (2) of Theorem 11, we have thata0,0=2 if and only ifmis odd.

For eachi=0, 1, 2, …,k-1, letα=θil. By Lemma 7, the mapψα(x) is one-to-one over the subfield2m. For the special valuex0=θjlsuch that 1+θil+θjl=0, the corresponding valueψα(x0)=0. Let ∑i=2m{0=ψα(x0),ψα(0)}.By the part (2) of Theorem 3, the whole elements of thei-th row of the matrixAthat taking values 0 or 2 are exactly the {T1(x)|x∈∑i}.Since the trace functionT1(x) of the subfield2mtaking value 0 for half elements of2mand value 1 for the other half elements of2m, andT1(0)=0,T1(ψα(0))=0 by Lemma 8, there are 2m-1elements of ∑ithat taking 1 as the trace function value of2m, thus there are 2m-1elements of thei-th row of the matrixAthat taking value 2.

Ifi=0, then the element 1 belongs to the cyclotomic classT0, and 1+1=0 does not appear in any cyclotomic classes, therefore in the first row of the matrixA, no element can take value 1, therefore the part (2) of this theorem is held.

Ifi≠0, then there exists only valuejsuch that 1+θil+θjl=0, and by part (1) of Theorem 3, the correspondingai,j=1, and part (3) of this theorem is held.

□

4 Application

In this section, we will use our results to construct a class of de Bruijn sequences of stagen. Letp(x) be a primitive polynomial of degreen=2mover2, withθbeing one of its primitive roots. Letk=2m-1 andl=2m+1 as above. Now, we takeα=θk, andf1(x) be the minimal polynomial ofαover the finite field2. Consider the set {α,α2,α22, …,α2d-1}, withα2d=α. Then, we have that

f1(x)=(x-α)(x-α2)(x-α22)…(x-α2d-1),

andf1(x) is an irreducible polynomial of degreedover2. The following Lemma 9 shows that the degreedoff1(x) isn:

Lemma9Letn=2m,k=2m-1,l=2m+1, anddbe as above, thend=n.

ProofWe know thatdis the minimal integer such thatα2d=α, i.e.,θ2dk=θk. Since the multiplicative order ofθin the finite field2nis 2n-1=kl, we have that 2dk≡k(modkl), that is, 2d≡1 (modl). Thusdis the multiplicative order of 2 modl. By 2n≡1 (modl), we have thatd|n.

On the contrary, if we suppose thatd1. By 2d≡1 (modl), we can say that 2d-1=ls, withs≥1. Then

kl=2n-1=2n1d-1=

(2d-1)(1+2d+22d+… +2(n1-1)d)=

ls(1+2d+22d+…+2(n1-1)d).

Thus, we have that 2m-1=k=s(1+2d+22d+…+2(n1-1)d)≥1+2d>2d-1>l=2m+1, a contradiction.

□

Letf(x)=xnf1(1/x) be the reciprocal polynomial off1(x), thenf(x) is the minimal polynomial ofα-1. Since both the multiplicative order ofα-1andαare equal, the period off(x), i.e., the smallest integerlsuch thatf(x)l≡1 (modf(x)), isl=(2n-1)/k=2m+1.

If we takef(x) as the feedback polynomial of a linear feedback shift register (LFSR), then stage graphG(f) of the resulting LFSR consists ofk+1 cycles, one of which is the 1-cycle generated by the zero state (called zero cycle), and the otherkcycles have the same lengthl.

Iff(x)=1+c1x+c2x2+…+cn-1xn-1+xnis an irreducible polynomial of degreenin2[x] with periodl=2m+1, then the matrix

Z=s={s,sT,sT2, …,sTl-1}.

The characteristic polynomial ofTis

det(xI-T)=xnf(1/x)=f*(x)=f1(x),

which is the reciprocal polynomial off(x). By Cayley-Hamilton Theorem, we have thatf1(T)=0.

Then there is an field isomorphismψform the finite field2n=2[α] to the set2[T]={a0In+a1T+a2T2+…+an-1Tn-1|ai∈2}, by sendingαtoT. All nonzero matrices of2[T] form a multiplicative cyclic group of order 2n-1, and the subgroupH0={I,T,T2, …,Tl-1} is of orderl. There existk-1 matricesgi(T)∈2[T] (i=1, 2, …,k-1) such that all the other left cosets ofH0are of the following form:

Hi=gi(T)H0={gi(T),gi(T)T,

gi(T)T2, …,gi(T)Tl-1}.

Lets0=(1, 0, …, 0) be a fixed vector. Then the mapφfrom2[T] to the vector spaceby sendingg(T) of2[T] tos0g(T), is a one-to-one map. This map also sends each cosetHiinto the corresponding state cycleZi=s0gi(T). If two state vectorsx=s0g(T) andy=s0h(T) are conjugate, then, byx+y=s0, we have thatg(T)+h(T)=In. Through the isomorphismψ, we can get a one-to-one mapψfrom the finite field2n=2[α] to the vector spaceby sendingg(α) tos0g(T). In the multiplicative cyclic group2[α]{0}, there is a unique cyclic subgroupW0={1,α,α2, …,αl-1} of orderl. There existk-1 elementgi(α)∈2[α]{0} (i=1, 2, …,k-1) such that all the other left cosets ofW0are of the following form

Wi=gi(α)W0={gi(α),gi(α)α,

gi(α)α2, …,gi(α)αl-1}.

The mapψsends each cosetWiinto the corresponding state cycleZi=s0gi(T). Two state vectorsx=s0g(T) andy=s0h(T) are conjugate if and only ifg(α)+h(α)=1.

The adjacent matrixB=(bi,j)k×kof the LFSR generated byf(x) is defined as following:

bi,j=the pairs of conjugate states that lie inZiandZjrespectively.

The adjacent matrix can be used to calculate the number of de Bruijn sequences that the cycle-join method can generate. Next, we will show that by suitable chosengi(α), the cosetsWiof2[α] equals the cyclotomicTirespectively.

W0={1,α,α2,…,αl-1}={1,θk,θ2k, …,θ(l-1)k}=T0

for eachi=1, 2, …,k-1, setgi(α)=θi, then, we have that

Wi={θi,θiα,θiα2, …,θiαl-1={θuk+i|u=0,1,2,…,l-1}=Ti.

Thus, by suitable labeling the state cycles, the adjacent matrix is exactly thek-th cyclotomic matrix. From the adjacent matrixAk=(ai,j)k×k, we letM=(mi,j)k×kas following:

(12)

The BEST theorem shows that the number of de Bruijn sequences generated by cycle-join method is equal to the minor of any element ofM. The following theorem shows that the cycle-join method does work for our case, that is, forn=2m,k=2m-1.

Theorem5Suppose thatn,k,l, andf(x) as above, then we can find enough pairs of conjugate states that can join all the cycles of theG(f) into a full cycle.

ProofSince the zero cycle (0) can be joined withZ0=s0as above. We just consider how to join all thekcyclesZ0,Z1, …,Zk-1.

Firstly, consider the cycleZ0. Let ∑1={Zi|a0,i=2, 0

For eachZj∈∑2, that is,Zjcan not be joined withZ0directly. We shall show that there exists at least oneZi∈∑1such thatai,j=2. For otherwise, there are at least 2m-1cycles suchai,j=0 in thej-th row of thek-th cycotomic matrix. However, there are exactly 2m-1-2 cycles such thataj,i=0 by (3) of Theorem 4, a contridication. That is, the cycleZjcan be joined with the cycleZi, andZican be joined with the cycleZ0, thus all the cycles can be joined with the cycleZ0.

□

Example3Letn=6,k=7,l=9 as before. It is easy to check that the polynomialf(x)=x6+x3+1 is irreducible with periodl=9. By suitable labeling, the adjacent matrix of the state graph is equal the 7-th cyclotomic matrixA=(ai,j)7×7as in Example 1.

In this case, ∑1={Z3,Z5,Z6}, that is, the cyclesZ3,Z5andZ6can be joined withZ0, and ∑2={Z1,Z2,Z4}, none of which can not be joined withZ0.

For the state cycleZ1, consider the 1-th column of the matrixA, since there are only two elementsaj,1taking value 0, i.e.,a0,1=0 anda3,1=0. Thus there must exist state cycleZjsuch thataj,i=2, in facta5,1=2, andZ1can be joined withT5.

For the state cycleZ2, we can find thata3,2=1 anda5,2=2, then the cycleZ2can be joined withZ3orZ5of the set ∑1.

For the state cycleZ4, we can find thata3,4=2 anda6,4=1, then the cycleZ4can be joined withZ3orZ6of the set ∑1.

All the cycles ofG(f) are joined into a full cycle.

It seems difficult to calculate any one minor of the matrix defined by Eq.(12) to get the number of de Bruijn sequences generated by the cycle-join method. In the following, we list, in the following Table 1, some experimental data of the number of de Bruijn sequences for small dimensionn:

Table 1 The number of de Bruijn sequences that can be generated