# Classification of Base SequencesBS(n+1,n)

Authors: Dragomir Ž. Ðoković
Journal: International Journal of Combinatorics
 (2010)

---

## Abstract

Base sequences BS(n+1,n)
are quadruples of {±1}-sequences (A;B;C;D), with A and B of length n+1 and C and D of length n, such that the sum of their nonperiodic autocor-relation functions is a δ-function. The base sequence conjecture, asserting that BS(n+1,n)
exist for all n, is stronger than the famous Hadamard matrix conjecture. We introduce a new definition of equivalence for base sequences BS(n+1,n) and construct a canonical form. By using this canonical form, we have enumerated the equivalence classes of BS(n+1,n)
for n≤30. As the number of equivalence classes grows rapidly (but not monotonically) with n, the tables in the paper cover only the cases n≤13.


---

## Body

## 1. Introduction

Base sequencesBS(m,n) are quadruples (A;B;C;D) of binary sequences, with A and B of length m and C and D of length n, such that the sum of their nonperiodic autocorrelation functions is a δ-function. In this paper we take m=n+1.Sporadic examples of base sequencesBS(n+1,n) have been constructed by many authors during the last 30 years; see, for example, [1–4] and the survey paper [5] and its references. A more systematic approach has been taken by the author in [6, 7]. The BS(n+1,n) are presently known to exist for all n≤38 (ibid) and for Golay numbers n=2a10b26c, where a,b, and c are arbitrary nonnegative integers. However the genuine classification of BS(n+1,n) is still lacking. Due to the important role that these sequences play in various combinatorial constructions such as that for T-sequences, orthogonal designs, and Hadamard matrices [1, 5, 8], it is of interest to classify the base sequences of small length. Our main goal is to provide such classification for n≤30.In Section2 we recall the basic properties of base sequences of BS(n+1,n). We also recall the quad decomposition and our encoding scheme for this particular type of base sequences.In Section3 we enlarge the collection of standard elementary transformations of BS(n+1,n) by introducing a new one. Thus we obtain new notion of equivalence and equivalence classes. Throughout the paper, the words “equivalence" and “equivalence class" are used in this new sense. We also introduce the canonical form for base sequences. By using it, we are able to compute the representatives of the equivalence classes.In Section4 we introduce an abstract group, GBS, of order 212 which acts naturally on all sets BS(n+1,n). Its definition depends on the parity of n. The orbits of this group are just the equivalence classes of BS(n+1,n).In Section5 we tabulate some of the results of our computations (those for n≤13) giving the list of representatives of the equivalence classes of BS(n+1,n). The representatives are written in the encoded form which is explained in the next section. For n≤8 we also include the values of the nonperiodic autocorrelation functions of the four constituent sequences. We also raise the question of characterizing the binary sequences having the same nonperiodic autocorrelation function. A class of examples is constructed, showing that the question is interesting.The column “Equ.” in Table1 gives the number of equivalence classes in BS(n+1,n) for n≤30. The column “Nor.” gives the number of normal equivalence classes (see Section 5 for their definition).Table 1
Number of equivalence classes of BS(n+1,n).
nEqu.Nor.nEqu.Nor.0111617211041111722410211181731231119455224322034427254121367706502215886071762361390827142410878094442519516410981026106264118432722895012175828310700134755291883121433103019640015491231?0


## 2. Quad Decomposition and the Encoding Scheme

We denote finite sequences of integers by capital letters. If, say,A is such a sequence of length n then we denote its elements by the corresponding lower case letters. Thus (2.1)A=a1,a2,…,an.
To this sequence we associate the polynomial (2.2)A(x)=a1+a2x+⋯+anxn-1,
viewed as an element of the Laurent polynomial ring Z[x,x-1]. (As usual, Z denotes the ring of integers.) The nonperiodic autocorrelation functionNA of A is defined by(2.3)NA(i)=∑j∈Zajai+j,i∈Z,
where ak=0 for k<1 and for k>n. Note that NA(-i)=NA(i) for all i∈Z and NA(i)=0 for i≥n. The norm of A is the Laurent polynomial N(A)=A(x)A(x-1). We have (2.4)N(A)=∑i∈ZNA(i)xi.
The negation, -A, of A is the sequence (2.5)-A=-a1,-a2,…,-an.
The reversed sequence A' and the alternated sequence A* of the sequence A are defined by (2.6)A'=an,an-1,…,a1,A*=a1,-a2,a3,-a4,…,(-1)n-1an.
Observe that N(-A)=N(A')=N(A) and NA*(i)=(-1)iNA(i) for all i∈Z. By A,B we denote the concatenation of the sequences A and B.Abinary sequence is a sequence whose terms belong to {±1}. When displaying such sequences, we will often write + for +1 and - for -1. The base sequences consist of four binary sequences (A;B;C;D), with A and B of length m and C and D of length n, such that (2.7)N(A)+N(B)+N(C)+N(D)=2(m+n).
Thus, for i≠0, we have(2.8)NA(i)+NB(i)+NC(i)+ND(i)=0.We denote byBS(m,n) the set of such base sequences with m and n fixed. From now on we will consider only the case m=n+1.Let(A;B;C;D)∈BS(n+1,n). For convenience we fix the following notation. For n even (odd) we set n=2m (n=2m+1). We decompose the pair (A;B) into quads (2.9)[aian+2-ibibn+2-i],i=1,2,…,[n+12],
and, if n is even, the central column [am+1bm+1]. Similar decomposition is valid for the pair (C;D).Recall the following basic and well-known property [3, Theorem 1].Theorem 2.1.
For(A;B;C;D)∈BS(n+1,n), the sum of the four quad entries is 2(mod4) for the first quad of the pair (A;B) and is 0(mod4) for all other quads of (A;B) and also for all quads of the pair (C;D).Thus there are 8 possibilities for the first quad of the pair(A;B): (2.10)1'=[-+++],2'=[+-++],3'=[+++-],4'=[++-+],5'=[+---],6'=[-+--],7'=[---+],8'=[--+-].
These eight quads occur in the study of Golay sequences (see, e.g., [9]), and we refer to them as the Golay quads.There are also 8 possibilities for each of the remaining quads of(A;B) and all quads of (C;D): (2.11)1=[++++],2=[++--],3=[-+-+],4=[+--+],5=[-++-],6=[+-+-],7=[--++],8=[----].
We will refer to these eight quads as the BS-quads. We say that a BS-quad is symmetric if its two columns are the same, and otherwise we say that it is skew. The quads 1,2,7, and 8 are symmetric and 3,4,5, and 6 are skew. We say that two quads have the same symmetry type if they are both symmetric or both skew.There are 4 possibilities for the central column:(2.12)0=[++],1=[+-],2=[-+],3=[--].We encode the pair(A;B) by the symbol sequence(2.13)p1p2⋯pmpm+1,
where pi is the label of the ith quad except in the case where n is even and i=m+1 in which case pm+1 is the label of the central column.Similarly, we encode the pair(C;D) by the symbol sequence(2.14)q1q2⋯qmrespectivelyq1q2⋯qmqm+1
when n is even respectively odd. Here qi is the label of the ith quad for i≤m, and qm+1 is the label of the central column (when n is odd).


## 3. The Equivalence Relation

We start by defining five types of elementary transformations of base sequencesBS(n+1,n). These elementary transformations include the standard ones, as described in [3, 6]. But we also introduce one additional elementary transformation, see item (T4), which made its first appearance in [10] in the context of near-normal sequences. The quad notation was instrumental in the discovery of this new elementary operation.Theelementary transformations of (A;B;C;D)∈BS(n+1,n) are the following.(T1)
Negate one of the sequencesA;B;C;D.(T2)
Reverse one of the sequencesA;B;C;D.(T3)
Interchange the sequencesA;B or C;D.(T4)
Replace the pair(C;D) with the pair (C̃;D̃) which is defined as follows: if (2.14) is the encoding of (C;D), then the encoding of (C̃;D̃) is τ(q1)τ(q2)⋯τ(qm)qm+1 or τ(q1)τ(q2)⋯τ(qm) depending on whether n is even or odd, where τ is the transposition (45). In other words, the encoding of (C̃;D̃) is obtained from that of (C;D) by replacing each quad symbol 4 with the symbol 5, and vice versa. (We verify below that NC̃+ND̃=NC+ND.)(T5)
Alternate all four sequencesA;B;C;D.In order to justify (T4) one has to verify thatNC̃+ND̃=NC+ND. For that purpose let us fix two quads qk and qk+i and consider their contribution δi to NC(i)+ND(i). We claim that δi is equal to the contribution δ̃i of τ(qk) and τ(qk+i) to NC̃(i)+ND̃(i). If neither qk nor qk+i belongs to {4,5}, then τ(qk)=qk and τ(qk+i)=qk+i and so δi=δ̃i. If q∈{4,5}, then τ(q) is the negation of q. Hence if {qk,qk+i}⊆{4,5}, then again δi=δ̃i. Otherwise, say qk∈{4,5} while qk+i∉{4,5}, and it is easy to verify that δi=0=δ̃i. The pairs qk and qn+1-k-i also make a contribution to NC(i)+ND(i), but they can be treated in the same manner. Finally, if n is odd then the pair (C;D) also has a central column with label qm+1. In that case, if k=m+1-i and qk∈{4,5}, the contribution of qk and qm+1 to NC(i)+ND(i) is 0. This completes the verification.We say that two members ofBS(n+1,n) are equivalent if one can be transformed to the other by applying a finite sequence of elementary transformations. One can enumerate the equivalence classes by finding suitable representatives of the classes. For that purpose we introduce the canonical form.Definition 3.1.
LetS=(A;B;C;D)∈BS(n+1,n) and let (2.13) respectively (2.14) be the encoding of the pair (A;B) respectively (C;D). One says that S is in the canonical form if the following eleven conditions hold.(i)
p1=3', p2∈{6,8} for n even and p2∈{1,6} for n odd.(ii)
The first symmetric quad (if any) of(A;B) is 1 or 8.(iii)
Ifn is even and pi∈{3,4,5,6} for 2≤i≤m, then pm+1∈{0,3}.(iv)
The first skew quad (if any) of(A;B) is 3 or 6.(v)
q1=1 for n even and q1∈{1,6} for n odd.(vi)
The first symmetric quad (if any) of(C;D) is 1.(vii)
The first skew quad (if any) of(C;D) is 6.(viii)
Ifi is the least index such that qi∈{2,7}, then qi=2.(ix)
Ifi is the least index such that qi∈{4,5}, then qi=4.(x)
Ifn is odd and qi∈{1,3,6,8}, for all i≤m, then qm+1≠2.(xi)
Ifn is odd and qi∈{3,4,5,6}, for all i≤m, then qm+1=0.We can now prove that each equivalence class has a member which is in the canonical form. The uniqueness of this member will be proved in the next section.Proposition 3.2.
Each equivalence classℰ⊆BS(n+1,n) has at least one member having the canonical form.Proof.
LetS=(A;B;C;D)∈ℰ be arbitrary and let (2.13) respectively (2.14) be the encoding of (A;B) respectively (C;D). By applying the first three types of elementary transformations and by Theorem 2.1 we can assume that p1=3' and c1=d1=+1. By Theorem 2.1, q1∈{1,6}. If n is even and q1=6 we apply the elementary transformation (T5). Thus we may assume that p1=3′, and that condition (v) for the canonical form is satisfied. To satisfy conditions (ii) and (iii), replace B with -B' (if necessary). To satisfy condition (iv), replace A with A' (if necessary).
We now modifyS in order to satisfy the second part of condition (i). Note that p2 is a BS-quad by Theorem 2.1. If p2=6 there is nothing to do.
Assume that the quadp2 is symmetric. By (ii), p2∈{1,8}. From (2.8) for i=n-1, we deduce that p2=8 if q1=1 and p2=1 if q1=6. Note that if n is even, then q1=1 by (v). If n is odd and q1=1, we switch A and B and apply the elementary transformation (T5). After this change we still have p1=3', q1=1, conditions (ii), (iii), and (iv) remain satisfied, and moreover p2=6.
Now assume thatp2 is skew. In view of (iv), we may assume that p2=3. Then the argument above based on (2.8) shows that q1=6, and so n must be odd. After applying the elementary transformation (T5), we obtain that p2=1. Hence condition (i) is fully satisfied.
To satisfy (vi), in view of (v) we may assume thatn is odd and q1=6. If the first symmetric quad in (C;D) is 2 respectively 7, we reverse and negate C respectively D. If it is 8, we reverse and negate both C and D. Now the first symmetric quad will be 1.
To satisfy (vii), (if necessary) reverseC,  D, or both. To satisfy (viii), (if necessary) interchange C and D. Note that in this process we do not violate the previously established properties. To satisfy (ix), (if necessary) apply the elementary transformation (T4). To satisfy (x), switch C and D (if necessary). To satisfy (xi), (if necessary) replace C with -C',  D with -D', or both.
HenceS is now in the canonical form.


## 4. The Symmetry Group ofBS(n+1,n)

We will construct a groupGBS of order 212 which acts on BS(n+1,n). Our (redundant) generating set for GBS will consist of 12 involutions. Each of these generators is an elementary transformation, and we use this information to construct GBS, that is, to impose the defining relations. We denote by S=(A;B;C;D) an aritrary member of BS(n+1,n).To constructGBS, we start with an elementary abelian group E of order 28 with generators νi,ρi, i∈{1,2,3,4}. It acts on BS(n+1,n) as follows: (4.1)ν1S=(-A;B;C;D),ρ1S=(A';B;C;D),ν2S=(A;-B;C;D),ρ2S=(A;B';C;D),ν3S=(A;B;-C;D),ρ3S=(A;B;C';D),ν4S=(A;B;C;-D),ρ4S=(A;B;C;D'),
that is, νi negates the ith sequence of S and ρi reverses it.Next we introduce two commuting involutory generatorsσ1 and σ2. We declare that σ1 commutes with ν3,ν4,ρ3, and ρ4, and σ2 commutes with ν1,ν2,ρ1, and ρ2 and that (4.2)σ1ν1=ν2σ1,σ1ρ1=ρ2σ1,σ2ν3=ν4σ2,σ2ρ3=ρ4σ2.
The group H=〈E,σ1,σ2〉 is the direct product of two isomorphic groups of order 32: (4.3)H1=〈ν1,ρ1,σ1〉,H2=〈ν3,ρ3,σ2〉.
The action of E on BS(n+1,n) extends to H by defining(4.4)σ1S=(B;A;C;D),σ2S=(A;B;D;C).We add a new generatorθ which commutes elementwise with H1, commutes with ν3ρ3,ν4ρ4, and σ2, and satisfies θρ3=ρ4θ. Let us denote this enlarged group by H̃. It has the direct product decomposition (4.5)H̃=〈H,θ〉=H1×H̃2,
where the second factor is itself direct product of two copies of the dihedral group D8 of order 8: (4.6)H̃2=〈ρ3,ρ4,θ〉×〈ν3ρ3,ν4ρ4,θσ2〉.
The action of H on BS(n+1,n) extends to H̃ by letting θ act as the elementary transformation (T4).Finally, we defineGBS as the semidirect product of H̃ and the group of order 2 with generator α. By definition, α commutes with each νi and satisfies(4.7)αρiα=ρiνin,i=1,2;αρjα=ρjνjn-1,j=3,4;αθα=θσ2n-1.
The action of H̃ on BS(n+1,n) extends to GBS by letting α act as the elementary transformation (T5), that is, we have (4.8)αS=(A*;B*;C*;D*).We point out that the definition of the subgroupH̃ is independent of n, and its action on BS(n+1,n) has a quadwise character. By this we mean that the value of a particular quad, say pi, of S∈BS(n+1,n) and h∈H̃ determine uniquely the quad pi of hS. In other words H̃ acts on the Golay quads, the BS-quads, and the set of central columns such that the encoding of hS is given by the symbol sequences (4.9)h(p1)h(p2)⋯h(pm+1),h(q1)h(q2)⋯.
On the other hand the full group GBS has neither of these two properties.An important feature of the action ofH̃ on the BS-quads is that it preserves the symmetry type of the quads.The following proposition follows immediately from the construction ofGBS and the description of its action on BS(n+1,n).Proposition 4.1.
The orbits ofGBS in BS(n+1,n) are the same as the equivalence classes.The main tool that we use to enumerate the equivalence classes ofBS(n+1,n) is the following theorem.Theorem 4.2.
For each equivalence classℰ⊆BS(n+1,n) there is a unique S=(A;B;C;D)∈ℰ having the canonical form.Proof.
In view of Proposition3.2, we just have to prove the uniqueness assertion. Let
(4.10)S(k)=(A(k);B(k);C(k);D(k))∈ℰ,(k=1,2)
be in the canonical form. We have to prove that in fact S(1)=S(2).
By Proposition4.1, we have gS(1)=S(2) for some g∈GBS. We can write g as g=αsh where s∈{0,1} and h∈H̃. Let p1(k)p2(k)⋯pm+1(k) be the encoding of the pair (A(k);B(k)) and q1(k)q2(k)⋯ the encoding of the pair (C(k);D(k)). The symbols (i-xi) will refer to the corresponding conditions of Definition 3.1. Observe that p1(1)=p1(2)=3' by (i).
We prove first preliminary claims (a-c).
(a)
q1(1)=q1(2).
Forn even see (v). Let n be odd. When we apply the generator α to any S∈BS(n+1,n), we do not change the first quad of (C;D). It follows that the quads q1(1) and q1(2) have the same symmetry type. The claim now follows from (v).
(b)
g∈H̃, that is, s=0.
Assume first thatn is even. By (v), q1(1)=q1(2)=1. For any S∈ℰ the first quad of (C;D) in S and the one in αS have different symmetry types. As quad h(1) is symmetric, the equality αshS(1)=S(2) forces s to be 0. Assume now that n is odd. Then for any S∈ℰ the second quad of (A;B) in S and the one in αS have different symmetry types. Recall that q1(1)=q1(2)∈{1,6} and that (see (i)) p2(1) and p2(2) belong to {1,6}. From (2.8), with i=n-1, we deduce that p2(k)≠q1(k) for k=1,2. We conclude that p2(1)=p2(2). The claim now follows from the fact that h preserves while α alters the symmetry type of the quad p2.
As an immediate consequence of (b), we point out that a quadpi(1) is symmetric if and only if pi(2) is, and the same is true for the quads qi(1) and qi(2).
(c)
p2(1)=p2(2).
This was already proved above in the case whenn is odd. In general, the claim follows from (b) and the equality h(p2(1))=p2(2). Observe that each of the sets {6,8} and {1,6} consists of one symmetric and one skew quad and that h preserves the symmetry type of quads.
Recall thatH̃=H1×H̃2. Since s=0, we have g=h=h1h2 with h1∈H1 and h2∈H̃2. Consequently, h1(pi(1))=pi(2) and h2(qi(1))=qi(2) for all i’s.
We will now prove thatA(1)=A(2) and B(1)=B(2). Since p1(1)=p1(2)=3', the equality h1(p1(1))=p1(2) implies that h1(3')=3'. Thus h1=ρ1e(ν2ρ2)f for some e,f∈{0,1}.
Assume first thatp2(1) is symmetric. By (ii), p2(1)∈{1,8}. Then h1(p2(1))=p2(2)=p2(1) implies that f=0. Hence, h1=ρ1e and so B(1)=B(2). If all quads pi(1), i≠1, are symmetric, then also A(2)=h1A(1)=A(1). Otherwise let i be the least index for which the quad pi(1) is skew. Since B(1)=B(2) and pi(1) is 3 or 6 (see (iv)), we infer that e=0. Hence h1=1 and so A(1)=A(2).
Now assume thatp2(1) is skew. By (ii), p2(1)=6. Then h1(p2(1))=p2(2)=p2(1) implies that e=0. Thus h1=(ν2ρ2)f and so A(1)=A(2). If all quads pi(1), i≠1, are skew, then by invoking condition (iii) we deduce that f=0 and so B(1)=B(2). Otherwise let i be the least index for which the quad pi(1) is symmetric. Since A(1)=A(2) and pi(1) is 1 or 8 (see (ii)), we infer that f=0. Hence h1=1 and so B(1)=B(2).
It remains to prove thatC(1)=C(2) and D(1)=D(2). We set Q={qi(1):1≤i≤m}. By (v) and claim (a) we have q1(1)=q1(2)∈{1,6}.
We first consider the caseq1(1)=q1(2)=6 which occurs only for n odd. Then h2(6)=6 and so h2∈〈ν3ρ3,ν4ρ4,θ,σ2〉. It follows that h2(3)=3.
If someq∈Q is symmetric, let i be the least index such that qi(1) is symmetric. Then (vi) implies that qi(1)=qi(2)=1. Thus h2 must fix the quad 1. As the stabilizer of the quad 1 in 〈ν3ρ3,ν4ρ4,θ,σ2〉 is 〈θ,σ2〉, we infer that h2 must also fix the quad 8. Similarly, if 2∈Q, then (viii) implies that h2 fixes 2 and 7. If 4∈Q, then (ix) implies that h2 fixes 4 and 5. These facts imply that h2 fixes all quads in Q, that is, qi(1)=qi(2) for all i≤m. It remains to show that, for odd n, qm+1(1)=qm+1(2). If Q⊆{3,4,5,6}, this follows from (xi). Otherwise Q contains a symmetric quad and so h2∈〈θ,σ2〉. If Q⊈{1,3,6,8} then Q contains one of the quads 2, 4, 5, or 7. Since h2 fixes all quads in Q, we infer that h2∈〈θ〉, and so qm+1(1)=qm+1(2). If Q⊆{1,3,6,8}, the equality qm+1(1)=qm+1(2) follows from (x).
Finally, we consider the caseq1(1)=q1(2)=1. Since h2(q1(1))=q1(2), h2∈〈ρ3,ρ4,θ,σ2〉. Hence h2 fixes the quads 1 and 8.
If someq∈Q is skew, then (vii) implies that h2 fixes the quads 3 and 6. If 2∈Q, then (viii) implies that h2 fixes the quads 2 and 7. If 4∈Q, then (ix) implies that h2 fixes the quads 4 and 5. These facts imply that h2 fixes all quads in Q. If n is odd, then we invoke conditions (x) and (xi) to conclude that h2 also fixes the central column of (C(1);D(1)). Hence C(1)=C(2) and D(1)=D(2) also in this case.


## 5. Representatives of the Equivalence Classes

We have computed a set of representatives for the equivalence classes of base sequencesBS(n+1,n) for all n≤30. Due to their excessive size, we tabulate these sets only for n≤13. Each representative is given in the canonical form which is made compact by using our standard encoding. The encoding is explained in detail in Section 2.As an example, the base sequences(5.1)A=+,+,+,+,-,-,+,-,+,B=+,+,+,-,+,+,+,-,-,C=+,+,-,-,+,-,-,+,D=+,+,+,+,-,+,-,+,
are encoded as 3'6142,1675. In the tables we write 0 instead of 3'. This convention was used in our previous papers on this and related topics.This compact notation is used primarily in order to save space, but also to avoid introducing errors during decoding. For eachn, the representatives are listed in the lexicographic order of the symbol sequences (2.13) and (2.14).In Table2 we list the codes for the representatives of the equivalence classes of BS(n+1,n) for n≤8. This table also records the values NX(k) of the nonperiodic autocorrelation functions for X∈{A,B,C,D} and k≥0. For instance let us consider the first item in the list of base sequences BS(8,7) given in Table 2. The base sequences are encoded in the first column as 0165, 6123. The first part 0165 encodes the pair (A;B), and the second part 6123 encodes the pair (C;D). The function NA, at the points 0,1,…,7, takes the values 8,-1,2,-1,0,1,2, and 1 listed in the second column. Just below these values one finds the values of NB at the same points. In the third column we list likewise the values of NC and ND at the points i=0,1,…,6.Table 2
Equivalence classes of BS(n+1,n), n≤8.
ABCDNA & NBNC & NDn=1102,1102,-11n=21033,-2,12,113,0,-12,1n=31064,-1,0,13,2,1114,1,-2,-13,-2,1n=410605,0,1,0,14,-1,0,1165,2,-1,-2,-14,-1,0,120825,0,-1,-2,14,3,2,1125,-2,1,0,-14,-1,-2,130835,0,-1,-2,14,-1,0,1165,2,1,0,-14,-1,0,1n=510166,1,0,1,2,15,2,-1,-2,-16406,-1,2,-1,0,-15,-2,-1,2,-120176,1,-4,-1,2,15,-2,1,0,-16136,3,2,1,0,-15,-2,1,0,-130646,1,-2,-1,0,15,0,1,0,11606,-1,0,1,-2,-15,0,1,0,140656,-3,2,-1,0,15,0,-1,2,11136,3,0,-3,-2,-15,0,-1,2,1n=6106127,-2,3,-2,1,0,16,1,-4,-1,2,11277,4,1,0,-1,-2,-16,-3,0,3,-2,1208207,-2,1,0,3,-2,16,1,0,-1,-2,11887,0,-1,2,1,0,-16,1,0,-1,-2,1308617,-2,-3,2,1,-2,16,1,2,1,0,11627,0,3,0,-1,0,-16,1,-2,-3,0,1408727,2,1,0,-1,-2,16,1,0,1,2,11267,0,-1,-2,1,0,-16,-3,0,1,-2,1508827,2,1,0,-1,-2,16,1,-2,-1,0,11647,0,-1,2,1,0,-16,-3,2,-1,0,1n=7101658,-1,2,-1,0,1,2,17,0,-1,2,1,0,-161238,1,0,1,-2,-1,0,-17,0,-1,-2,1,0,-1201658,-1,2,-1,0,1,2,17,0,3,0,-1,0,-161418,1,0,1,-2,-1,0,-17,0,-5,0,3,0,-1301668,3,-2,-1,0,1,2,17,0,-1,2,1,0,-161228,1,0,1,-2,-1,0,-17,-4,3,-2,1,0,-1401738,-1,-2,1,-2,-1,2,17,0,3,0,-1,0,-161618,1,0,-1,4,1,0,-17,0,-1,0,-1,0,-1501738,-1,-2,1,-2,-1,2,17,4,1,0,-1,-2,-164118,1,0,-1,4,1,0,-17,-4,1,0,-1,2,-1601838,-1,-2,1,-2,-1,2,17,4,3,2,1,0,-161218,-3,0,-1,0,1,0,-17,0,-1,-2,1,0,-1706138,-1,0,3,0,1,0,17,-2,3,-2,1,0,116238,1,-2,1,2,-1,-2,-17,2,-1,-2,-3,0,1806148,-1,4,-1,0,1,0,17,2,-1,0,-1,0,116418,1,-2,1,2,-1,-2,-17,-2,-1,0,-1,0,1906158,-1,0,3,0,1,0,17,2,-3,-2,1,2,112638,1,2,1,-2,-1,-2,-17,-2,1,-2,1,-2,11006158,-1,0,3,0,1,0,17,2,-3,-4,-1,2,112728,1,2,1,-2,-1,-2,-17,-2,1,0,3,-2,11106168,-1,4,-1,0,1,0,17,2,-3,-2,1,2,112628,1,2,1,-2,-1,-2,-17,-2,-3,2,1,-2,11206188,-1,0,-1,-2,1,0,17,2,1,2,1,2,112618,1,-2,1,0,-1,-2,-17,-2,1,-2,1,-2,11306358,-1,-4,1,2,-1,0,17,2,3,2,1,0,116218,-3,2,-1,0,1,-2,-17,2,-1,-2,-3,0,11406388,-1,0,-3,0,-1,0,17,2,3,2,1,0,116208,1,-2,-1,2,1,-2,-17,-2,-1,2,-3,0,11506418,3,0,1,0,-1,0,17,-2,3,-2,1,0,116228,1,-2,-1,2,1,-2,-17,-2,-1,2,-3,0,11606468,3,0,-3,-2,-1,0,17,2,1,0,3,2,112228,-3,2,-1,0,1,-2,-17,-2,-3,4,-1,-2,11706468,3,0,-3,-2,-1,0,17,2,1,2,1,2,112608,-3,2,-1,0,1,-2,-17,-2,-3,2,1,-2,1n=81061139,0,1,4,-1,2,1,0,18,-1,0,-3,0,-1,0,116389,2,-1,2,1,0,-1,-2,-18,-1,0,-3,0,-1,0,12061229,0,1,4,-1,2,1,0,18,3,0,-3,-2,-1,0,116449,-2,3,-2,1,0,-1,-2,-18,-1,-4,1,2,-1,0,13061419,0,5,0,1,0,1,0,18,-1,0,1,-2,-1,0,116639,2,-5,-2,3,2,-1,-2,-18,-1,0,1,-2,-1,0,14061429,0,1,0,-3,0,1,0,18,-1,4,-1,0,1,0,116249,2,-1,-2,3,2,-1,-2,-18,-1,-4,3,0,-3,0,15061519,0,1,0,5,0,1,0,18,-1,0,-1,-2,1,0,116189,2,-1,2,-1,-2,-1,-2,-18,-1,0,-1,-2,1,0,16061529,0,-3,0,1,0,1,0,18,3,-2,-1,0,1,2,112649,2,3,2,-1,-2,-1,-2,-18,-5,2,-1,0,1,-2,17061839,0,1,-4,-1,-2,1,0,18,-1,-2,5,0,-1,2,112719,2,-1,-2,1,0,-1,-2,-18,-1,2,1,0,3,-2,18061839,0,1,-4,-1,-2,1,0,18,-1,0,3,0,1,0,116139,2,-1,-2,1,0,-1,-2,-18,-1,0,3,0,1,0,19063109,0,1,2,1,4,-1,0,18,-1,0-1,0,-3,0,116869,2,-1,0,-1,2,1,-2,-18,-1,0-1,0,-3,0,110063809,-4,1,-2,1,0,-1,0,18,3,0,1,0,-1,0,116619,-2,-1,0,-1,2,1,-2,-18,3,0,1,0,-1,0,111063829,0,1,-2,-3,0,-1,0,18,3,0,1,0,-1,0,116419,-2,-1,0,-1,2,1,-2,-18,-1,0,1,4,-1,0,112064129,0,1,2,-3,0,-1,0,18,-1,0,1,4,-1,0,116329,2,-1,0,-1,2,1,-2,-18,-1,0,-3,0,-1,0,113065809,-4,1,-2,1,0,-1,0,18,3,-2,-3,0,3,2,111279,2,3,0,-1,-2,-3,-2,-18,-1,-2,5,0,-1,2,114066339,0,-3,2,-1,-2,-1,0,18,-1,2,-1,0,1,2,111639,2,-1,0,1,0,-3,-2,-18,-1,2,-1,0,1,2,115068529,0,-3,0,1,0,-3,0,18,-1,2,-1,0,1,2,111639,2,-1,2,-1,-2,-1,-2,-18,-1,2,-1,0,1,2,116068609,0,-3,0,1,0,-3,0,18,-1,2,-1,0,1,2,111639,2,-1,2,-1,-2,-1,-2,-18,-1,2,-1,0,1,2,117081109,0,3,2,1,0,3,-2,18,-1,-2,-1,0,1,-2,118669,2,1,0,-1,-2,1,0,-18,-1,-2,-1,0,1,-2,118083509,0,-1,-4,1,0,1,-2,18,-1,2,1,0,3,-2,118229,-2,-3,2,-1,-2,3,0,-18,3,2,1,0,-1,-2,119083839,0,3,0,-1,-2,1,-2,18,-1,-2,-1,0,1,-2,118669,2,1,2,1,0,3,0,-18,-1,-2,-1,0,1,-2,120086309,-4,-1,0,1,0,1,-2,18,3,0,1,0,-1,0,116619,-2,1,-2,-1,2,-1,0,-18,3,0,1,0,-1,0,121086409,0,-1,-4,1,0,1,-2,18,-1,-2,5,0,-1,2,112829,-2,1,-2,-1,2,-1,0,-18,3,2,1,0,-1,-2,122086429,0,-1,0,-3,0,1,-2,18,3,0,1,0,-1,0,116419,-2,1,-2,-1,2,-1,0,-18,-1,0,1,4,-1,0,123086609,0,-1,-4,1,0,1,-2,18,-1,-2,5,0,-1,2,112719,2,1,-2,-1,-2,-1,0,-18,-1,2,1,0,3,-2,124086609,0,-1,-4,1,0,1,-2,18,-1,0,3,0,1,0,116139,2,1,-2,-1,-2,-1,0,-18,-1,0,3,0,1,0,125088339,0,-1,2,-1,2,-1,-2,18,-1,0,-1,0,-3,0,116869,2,1,0,1,4,1,0,-18,-1,0,-1,0,-3,0,126088629,0,-1,2,-1,2,-1,-2,18,-1,4,-1,0,1,0,116269,2,-3,0,1,0,1,0,-18,-1,0,-1,0,-3,0,127088639,0,-1,2,-1,2,-1,-2,18,-1,0,-3,0,-1,0,116389,2,1,4,1,0,1,0,-18,-1,0,-3,0,-1,0,1Tables3, 4, 5, 6, and 7 contain only the list of codes for the representatives of the equivalence classes of BS(n+1,n) for 9≤n≤13.Table 3
Equivalence classes of BS(10,9).
ABCDABCDABCDABCD101235664502013246618130161864150401624641835016276413060163364140701642645608016526145390165264313100165461163110165561180120167261281130167561430140168261180150168461122160173464160170173561640180176461821190176561281200176761831210178361411220186761311230612416282240613616640250614716450260615212763270616416133280617212681290617512670300617516143310618716131320635116460330638216460340638816340350641216273360641216381370641316460380645116163390645812612400648112623410648116161420658111622430658311631440687511622Table 4
Equivalence classes of BS(11,10).
ABCDABCDABCD10611731645620612531624630613501664540614501626750614501644360614601643470614631282680614631627190615531271610061563161341106158212631120616331267113061740126841406187012286150618701614416063140168621706341316822180635101638219063513164412006355016414210635831634122063810166162306382116445240638331661325063840162622606384216242270638701632228063873162172906388116342300641221627731064130164653206414116423330641411645234064170163443506431316282360644131282637064413162713806448016213390644801632140064510126384106451012676420648701261643065843112764406811011863450683831186346068560112634706857111632480685801162749068580116435006861111634510686321163252068641116345306875211276540687711164555082661186425608311018863570833831886358083510182265908352118642600838501862261086231162486208624316277630862631633264086310166136508633316616660863431622867086421164276808643216242690864631621770086473162177108648316344720865321614273086640126317408664316134750867401264276086840126827708686012671780868701267179087110128638008711016273810871201646182087130164618308713116262840872211628485087323162828608734316282870873611642288087372128648908738316382900876631614691087683126379208773212684930886511626494088651164249508867316434960887621624697088771162649808877116424Table 5
Equivalence classes of BS(12,11).
ABCDABCDABCD101182366142220123566614223013682663120401375366312050164266412726016445616230701647264512180165256142329016525643511100165356127701101654261246312016542612843130165426142421401654661244015016572614320160166346141231701663461423118016643612271190166536123132001672464312121016727612440220167566112802301677461236324016817614320250172626412432601735661612327017374616242280173756412432901763261462030017646612640310176646145203201767461246233017674614272340182656127723501834261462036018382612770370187676131233801876761323039061186164231400612461663234106125616434142061264162273430612641624334406128416423145061462162452460614621643224706146316226248061472128681490614731642515006147616243151061476164320520615471276215306157512623254061618126232550616241263325606164412634157061764126242580617741263435906314416828160063412168481610635121626426206351516244163063515164321640635411626606506354116442066063551163241670638111642616806382416266069063824164420700638251627727106382816227372063828162433730638421642617406385816332075063877128160760638821634237706388416342178064143164251790641461624318006414616432081064615122632820648261262628306483812645184064842126451Table 6
Equivalence classes of BS(13,12).
ABCDABCDABCD106118631645212061187116614330612360164844406125731642155061276012828760612760162443706128701624248061423016486490614533164226100614670162327110614671128266120614830162624130615230126876140615230161883150615643161234160615733126452170616433126452180616533126143190616733126143200617212126847210617220126876220617220161883230617623126413240617651122818250617811126428260617820161624270618833126413280631412168644290634170168382300635120164558310635152164341320635340164621330635440164242340635483162246350635483162432360635513164132370635550163214380635810163422390635810164142400635872162134410638112163822420638121164423430638212164242440638220164278450638241164423460638781162167470641282162424480641363164522490641370164265500641470162732510641471128642520641471164217530641481164215540643513164242550643822164522560643880162424570644833163214580646430126143590648112126283600648212161624610648213161644620648363126461630648382126716640648433126452650658112116273660658363116342670658463112645680661363116245690661453112634700663640116342710663853116324720663880116245730664360116245740685733116245750685860112645760685871112766770686130116245780686230116636790686240116273800686433116245810687623112645820688613116245830688671112764840811283182788850812661182668860812883186247870816621181128880817883181128890826620186247900826782182266910826783182641920826851186444930835382182266940836121186621950837383182278960837383182771970838521186627980838652182777990838673182668100083875118277710108388711866441020862230164278103086227016441310408623121642261050862322166128106086238316274810708624411642651080862483128674109086265016334111008626511621381110863220164287112086335316264211308633531646121140863482166144115086412116432411608643111642261170864343164226118086438216441311908644631624511200864781162167121086526112623712208653101264521230865343161642124086538212623812508653821612671260866310126413127086644312631412808677401261741290868761126238130086876116126713108711301627471320871332162624133087223116283813408728331644321350873111166361136087347016284213708734701664131380873481162862139087358116441314008735831624451410873670162248142087368116226814308737111642261440873750164413145087622112776314608765101263421470876510126451148087657012286414908765701612471500876581126238151087658116126715208766121263411530876663126314154087675012623815508767501612671560877382126876157087738216188315808778711267481590878631127778160087866312764716108788611618861620878870161884163088121116838216408827621682421650883571168242166088367116842216708862611628741680886280162867169088647116284217008864711664131710886560164215172088661316452117308866711627411748867601642151750887780162748Table 7
Equivalence classes of BS(14,13).
ABCDABCDABCD1011645566163802011653666451833011654666451534011673466418225011765366182736011765366184227011766366184508011817666184419011832366182221001183246618241110118327661271212011832766141221301183456614212140123628664515315012364466414501601236726614413170123827661181118013155466182721901316576618273200131657661842221013167666127632201317356641851230131743664451324013174566455602501318426618222260132157664182227013228466145802801323546614153290132427664181030013246366188433101331546612743320133414661845133013342566118133401341746641273350134174664185336013423466415133701342466645113380134273661241239013427466122804001343146641851410134416664182242013616766364404301367646634111440137536663122345013832466314114601613276441863470161533641864348016163364148534901616556456330500161742641864351016175564127435201617626418430530162173616284254016228364156805501623286418650560162556645134057016258264513435801626176451282590162766641315160016315761684336101631746168441620163255616414363016328761621316401633256168241650163352616276066016337264141616701633756412612680163417641465369016346264126817001635626451883710163822645563072016384464512207301641336456613740164143616824275016415664565507601642346164450770164314616286278016431761628717901643276412623800164367616431181016447164185418201644816411811830164624645113384016517361428328501651746142582860165243614164387016527461224638801653276142412890165347614162290016536761423129101654136144831920165428614215293016552361435139401657166143581950165816611424296016582661145319701658266123142980166137612818299016615361274331000166173612837110101663176127481102016632461248411030166413612783210401664236141830105016654361124711060167125614268210701671346148463108016715664343501090167162612764311001671626142763111016723861282221120167286612216211301673456144161114016735661414611150167356618388111601673656144311117016738561162701180167416614458111901674266142280120016745564313111210167457643515012201674656141272123016746661245121240167583611274012501675846123240126016781761127631270168171611828212801681716143841129016827661145211300168286611453113101682866123142132016842561434111330168465611242213401684766123420135016848661145301360171655641627313701716566416851138017183164164811390172647641142214001726566415223141017336264161221420173413644186314301734746445160144017352161627811450173523641415114601735546161242147017361261648801480173612641486314901736586412511150017374461627601510173843641214115201738436412710153017616461826721540176421614627315501764216184643156017642461465111570176515643435015801765266431511159017654161246821600176542614228016101765546141272162017655761453131630176583614531016401766366142172165017664161427801660176744643141316701767566124831168017683461271721690176834614124117001768436116413171017684761216321720176865612173017301768736121742174017766364314131750177683612828017601776866145161177017826261162711780178283614123117901783256142411180017834661424201810178356612428118201783656141440183017836564313101840178377618342218501783846121641186017868361124221870178686612312318801787376118273189018235761264111900182652612484219101826556431311192018265761412221930182662612748119401826636122863195018266461242631960182665612471219701826686141522198018276161277731990182766614122320001828836121763201018324161846832020183262612647320301832776182231204018352161246812050183533614165020601835536121641207018355761271302080183624614228320901836446142281210018365761224812110183734612842121201837346142240213018374461424112140183753612441121501837576141232216018376761242332170183773614127221801837746121642219018377661241422200186553613231122101866526131422222018677461323122230186827613122322401868476131222225018762661322812260187667613142222706113641662871228061145316486532290611455164842223006115461626832231061155416278412320611645164385123306116541286740234061168612863202350611763162485223606117641642733237061185316262332380611853164252323906118741638220240061228616634802410612356164824124206124571662171243061251716427532440612528163824224506125361287762246061254716248202470612548164451124806125561286422249061258516238202500612586128642025106126451286441252061264616247302530612744164228025406127521624282255061275216246702560612753164413125706127531661181258612758162425025906127641286620260061284416612712610612853162614226206135151663843263061355416282432640613647162832326506137531628263266061375316641222670614236166445026806142711663481269061427416621422700614475162821327106145271622843272061457112863722730614571128667127406145771643513275061463812863212760614642128634127706146751623412278061468116232332790614773164345028006147741643270281061478416242502820614873164321128306148841645130284061511812686322850615146126846228606151471268452287061547112764432880615487126811128906156271612342290061574112634822910615743161624229206157831228631293061578412716602940615785161435029506158741612341296061588312623132970616234126476029806162371264280299061628112286323000616358126711330106164721614551302061648112623433030616481161423230406165341261732305061684116118223060617413161886130706174261268423308061752616164313090617556127164231006175561612741311061757216146513120617586127166031306176251262433314061762612623433150617626161423231606176551613422317061768216136403180617786127164231906177861612741320061782412646203210617824161623132206178441616450323061784512662123240617853161246132506178531614222326061787412716623270617884126245032806185161262443329061851712624333300618527161244133106185571613450332061861616134413330618625161344133406187141612662335061874812286313360618824126414233706188251263172338061884716123613390618874161324134006188831613451341063114716864223420631352168622234306314581682421344063155716814113450631778168141134606341351686220347063418716823213480635124164434034906351321644270350063513716382203510635138162624035206351521624740353063531116458603540635381162671035506354411646161356063585716213413570636178163441035806361781641321359063688216314433600638171164413136106381711661181362063817712864203630638188128662036406382211645681365063823716426203660638248164247036706382811644141368063828516434403690638372162482137006383841661242371063842716382213720638428163842137306384571624420374063848716261323750638522163382237606387441632281377063874716412723780641147163842237906411631286372380064116312866713810641264164343038206412781624260383064136116248423840641361164383338506414511286372386064145112866713870641457162245338806415171632482389064171216327833900641754162166239106418671621370392064311316484223930643412166271339406435361286881395064354516614213960643611162457339706438141638221398064383616612223990643842166127140006438431646150401064412416245704020644134162761140306441451286240404064438116261224050644813162126340606448131634121407064482316341414080645172161644140906453871263821410064565112263434110645857126124341206458711261623413064612312613734140646138126162241506463871261233416064812112647604170648175126228241806481761614430419064822512634824200648272161266242106482751614460422064827612622824230648376126462042406483761616231425064841212645234260648426126332342706484721264141428064848112641614290648586122648043006485871226380431064863512264814320648863122645343306554161126471434065541611621824350655417112637143606581251164341437065813511664504380658146116246143906581471162451440065817311276214410658275112676044206583641162461443065846311277624440658487112763144506612741127641446066358211645224470663614116344144806638751163241449066388511634224500682412118682245106852361128263452068542411286234530685536116274045406856371126370455068572411623234560685753112634145706858271162742458068584611627624590685863112643246006861421163422461068615411226714620686213116247146306862151163322464068625311264524650686273112676046606863571163222467068637411646504680686413116456046906864241162731470068645111263414710687515116245147206875251162631473068756111263614740687645112676047506887631164561Let us say that the base sequencesS=(A;B;C;D)∈BS(n+1,n) are normal respectively near-normal if bi=ai respectively bi=(-1)i-1ai for all i≤n. We denote by NS(n) respectively NN(n) the set of all normal respectively near-normal sequences in BS(n+1,n). Let us say also that an equivalence class ℰ⊆BS(n+1,n) is normal respectively near-normal if ℰ∩NS(n) respectively ℰ∩NN(n) is not void. Our canonical form has been designed so that if ℰ is normal, then its canonical representative S belongs to NS(n). The analogous statement for near-normal classes is false. It is not hard to recognize which representatives S in our tables are normal sequences. Let (2.13) be the encoding of the pair (A;B). Then S∈NS(n) if and only if all the quads pi, i≠1, belong to {1,3,6,8}, and, in the case when n=2m is even, the central column symbol pm+1 is 0 or 3.It is an interesting question to find the necessary and sufficient conditions for two binary sequences to have the same norm. The group of order four generated by the negation and reversal operations acts on binary sequences. We say that two binary sequences areequivalent if they belong to the same orbit. Note that the equivalent binary sequences have the same norm. However the converse is false. Here is a counter-example which occurs in Table 2 for the case n=8. The base sequences 15 and 16 differ only in their first sequences, which we denote here by U and V, respectively: (5.2)U=++---+--+,V=++-++---+.
Their associated polynomials are (5.3)U(x)=1+x-x2-x3-x4+x5-x6-x7+x8,V(x)=1+x-x2+x3+x4-x5-x6-x7+x8.
It is obvious that U and V are not equivalent in the above sense. On the other hand, from the factorizations U(x)=p(x)q(x) and V(x)=p(x)r(x), where p(x)=1+x-x2, q(x)=1-x3-x6, and r(x)=1+x3-x6=-x6q(x-1), we deduce immediately that NU(x)=NV(x).This counter-example can be easily generalized. Let us definebinary polynomials as polynomials associated to binary sequences. If f(x) is a polynomial of degree d with f(0)≠0, we define its dual polynomial f* by f*(x)=xdf(x-1). Then for any positive integer k we have f*(xk)=f(xk)*, that is, f*(xk)=g*(x) where g* is the dual of the polynomial f(xk). In general we can start with any number of binary sequences, but here we take only three of them: A;B;C of lengths m,n,k, respectively. From the associated binary polynomials A(x),B(x), and C(x) we can form several binary polynomials of degree mnk-1. The basic one is A(x)B(xm)C(xmn). The others are obtained from this one by replacing one or more of the three factors by their duals. It is immediate that the binary sequences corresponding to these binary polynomials all have the same norm. In general many of these sequences will not be equivalent. However, note that if we replace all three factors with their duals, we will obtain a binary sequence equivalent to the basic one.



---

*Source: 851857-2010-06-28.xml*