# Classification of Normal Sequences

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

---

## Abstract

Base sequencesBS(m,n) are quadruples (A;B;C;D) of {±1}-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. Normal sequences NS(n) are base sequences (A;B;C;D)∈BS(n,n) such that A=B. We introduce a definition of equivalence for normal sequences NS(n) and construct a canonical form. By using this canonical form, we have enumerated the equivalence classes of NS(n) for n≤40.


---

## Body

## 1. Introduction

By abinary respectively ternary sequence we mean a sequence A=a1,a2,…,am whose terms belong to {±1} respectively {0,±1}. To such a sequence, we associate the polynomial A(z)=a1+a2z+⋯+amzm-1. We refer to the Laurent polynomial N(A)=A(z)A(z-1) as the norm of A. Base sequences(A;B;C;D) are quadruples of binary sequences, with A and B of length m and C and D of length n, and such that(1.1)N(A)+N(B)+N(C)+N(D)=2(m+n).
The set of such sequences will be denoted by BS(m,n).In this paper, we consider only the case wherem=n or m=n+1. The base sequences (A;B;C;D)∈BS(n,n) are normal if A=B. We denote by NS(n) the set of normal sequences of length n, that is, those contained in BS(n,n). It is well known [1] that for normal sequences 2n must be a sum of three squares. In particular, NS(14) and NS(30) are empty. Exhaustive computer searches have shown that NS(n) are empty also for n=6,17,21,22,23,24 (see [2]) and n=27,28,31,33,34,…,39 (see [3–6]).The base sequences(A;B;C;D)∈BS(n+1,n) are near-normal if bi=(-1)i-1ai for all i≤n. For near-normal sequences n must be even or 1. We denote by NN(n) the set of near-normal sequences in BS(n+1,n).Normal sequences were introduced by Yang in [1] as a generalization of Golay sequences. Let us recall that Golay sequences(A;B) are pairs of binary sequences of the same length, n, and such that N(A)+N(B)=2n. We denote by GS(n) the set of Golay sequences of length n. It is known that they exist when n=2a10b26c where a,b,c are arbitrary nonnegative integers. There exist two embeddings GS(n)→NS(n): the first defined by (A;B)→(A;A;B;B) and the second by (A;B)→(B;B;A;A). We say that these normal sequences (and those equivalent to them) are of Golay type. For the definition of equivalence of normal sequences see Section 3. However, as observed by Yang, there exist normal sequences which are not of Golay type. We refer to them as sporadic normal sequences. From the computational results reported in this paper (see Table 1) it appears that there may be only finitely many sporadic normal sequences. For example, all 304 equivalence classes in NS(40) are of Golay type. The smallest length for which the existence question of normal sequences is still unresolved is n=41.Table 1
Number of equivalence classes ofNS(n).
nEquGolSponEquGolSpo1112121122311234112451125446262274427876128933292210541301122311244325164803613333314341522351652484361737181138191139203634240304304Base sequences, and their special cases such as normal and near-normal sequences, play an important role in the construction of Hadamard matrices [7, 8]. For instance, the discovery of a Hadamard matrix of order 428 (see [9]) used a BS(71,36), constructed specially for that purpose.Examples of normal sequencesNS(n) have been constructed in [1, 2, 5, 7, 10]. For various applications, it is of interest to classify the normal sequences of small length. Our main goal is to provide such classification for n≤40. The classification of near-normal sequences NN(n) for n≤40 and base sequences BS(n+1,n) for n≤30 has been carried out in our papers [5, 6, 11] and [10, 12], respectively.We give examples of normal sequences of lengthsn=1,…,5:
(1.2)A=+;A=+;C=+;D=+;A=+,+;A=+,+;C=+,-;D=+,-;A=+,+,-;A=+,+,-;C=+,+,+;D=+,-,+;A=+,+,-,+;A=+,+,-,+;C=+,+,+,-;D=+,+,+,-;A=+,+,+,-,+;A=+,+,+,-,+;C=+,+,+,-,-;D=+,-,+,+,-.
When displaying a binary sequence, we often write + for +1 and − for −1. We have written the sequence A twice to make the quads visible (see Section 2).If(A;A;C;D)∈NS(n) then (A,+;A,-;C;D)∈BS(n+1,n). This has been used in our previous papers to view normal sequences NS(n) as a subset of BS(n+1,n). For classification purposes it is more convenient to use the definition of NS(n) as a subset of BS(n,n), which is closer to Yang's original definition [1].In Section2, we recall the basic properties of base sequences BS(m,n). The quad decomposition and our encoding scheme for BS(n+1,n) used in our previous papers also work for NS(n), but not for arbitrary base sequences in BS(n,n). The quad decomposition of normal sequences NS(n) is somewhat simpler than that of base sequences BS(n+1,n). We warn the reader that the encodings for the first two sequences of (A;A;C;D)∈NS(n) and (A,+;A,-;C;D)∈BS(n+1,n) are quite different.In Section3, we introduce the elementary transformations of NS(n). We point out that the elementary transformation (E4) is quite nonintuitive. It originated in our paper [5] where we classified near-normal sequences of small length. Subsequently, it has been extended and used to classify (see [10, 12]) the base sequences BS(n+1,n) for n≤30. We use these elementary transformations to define an equivalence relation and equivalence classes in NS(n). We also introduce the canonical form for normal sequences, and, by using it, we were able to compute the representatives of the equivalence classes for n≤40.In Section4, we introduce an abstract group, GNS, of order 512 which acts naturally on all sets NS(n). Its definition depends on the parity of n. The orbits of this group are just the equivalence classes of NS(n).In Section5, we tabulate the results of our computations giving the list of representatives of the equivalence classes of NS(n) for n≤40. The representatives are written in the encoded form which is explained in the next section.The summary is given in Table1. The column “Equ” gives the number of equivalence classes in NS(n). Note that most of the known normal sequences are of Golay type. The column “Gol” respectively “Spo” gives the number of equivalence classes which are of Golay type respectively sporadic. (Blank entries are zeros.)


## 2. Quad Decomposition and the Encoding Scheme

LetA=a1,a2,…,an be an integer sequence of length n. To this sequence, we associate the polynomial (2.1)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.2)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.3)N(A)=∑i∈ZNA(i)xi.
Hence, if (A;B;C;D)∈BS(m,n) then(2.4)NA(i)+NB(i)+NC(i)+ND(i)=0,i≠0.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.Let(A;A;C;D)∈NS(n). For convenience, we set  n=2m(n=2m+1) for n even (odd). We decompose the pair (C;D) into quads (2.7)[cicn+1-ididn+1-i],i=1,2,…,m,
and, if n is odd, the central column [cm+1dm+1]. Similar decomposition is valid for the pair (A;A).The possibilities for the quads of base sequencesBS(n+1,n) are described in detail in [10]. In the case of normal sequences we have 8 possibilities for the quads of (C;D): (2.8)1=[++++],2=[++--],3=[-+-+],4=[+--+],5=[-++-],6=[+-+-],7=[--++],8=[----],
but only 4 possibilities, namely, 1, 3, 6, and 8, for the quads of (A;A). In [10], we referred to these eight quads as BS-quads. The additional eight Golay quads were also needed for the classification of base sequences BS(n+1,n).  Unless stated otherwise, the word “quad” will refer to BS-quads.We say that a quad issymmetric if its two columns are the same, and otherwise we say that it is skew. The quads 1,2,7,8 are symmetric and 3,4,5,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.9)0=[++],1=[+-],2=[-+],3=[--].We encode the pair(A;A) by the symbol sequence(2.10)p1p2⋯pm,respectively,p1p2⋯pmpm+1,
when n is even respectively odd. Here, pi is the label of the ith quad for i≤m and pm+1 is the label of the central column (when n is odd). Similarly, we encode the pair (C;D) by the symbol sequence(2.11)q1q2⋯qm,respectively,q1q2⋯qmqm+1.
For example, the five normal sequences displayed in the introduction are encoded as (0;0), (1;6), (60;11), (16;61), and (160;640), respectively.


## 3. The Equivalence Relation

We start by defining five types ofelementary transformations of normal sequences (A;A;C;D)∈NS(n)(E1)
Negate both sequencesA;A or one of C;D.(E2)
Reverse both sequencesA;A or one of C;D.(E3)
Interchange the sequencesC;D.(E4)
Replace the pair(C;D) with the pair (C̃;D̃) which is defined as follows: if (2.11) is the encoding of (C;D), then the encoding of (C̃;D̃) is τ(q1)τ(q2)⋯τ(qm) or τ(q1)τ(q2)⋯τ(qm)qm+1 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 simultaneously each quad symbol 4 with the symbol 5, and vice versa. For the proof of the equality NC̃+ND̃=NC+ND see [10].(E5)
Alternate all four sequencesA;A;C;D.We say that two members ofNS(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;A;C;D)∈NS(n) and let (2.10) respectively (2.11) be the encoding of the pair (A;A) respectively (C;D). We say that S is in the canonical form if the following twelve conditions hold.(i)
Forn even p1=1, and for n>1 odd p1∈{1,6}.(ii)
The first symmetric quad (if any) of(A;A) is 1.(iii)
The first skew quad (if any) of(A;A) is 6.(iv)
Ifn is odd and all quads of (A;A) are skew, then pm+1=0.(v)
Ifn is odd and i<m is the smallest index such that the consecutive quads pi and pi+1 have the same symmetry type, then pi+1∈{1,6}. If there is no such index and pm is symmetric, then pm+1=0.(vi)
q1∈{1,6} if n>1.(vii)
The first symmetric quad (if any) of(C;D) is 1.(viii)
The first skew quad (if any) of(C;D) is 6.(ix)
Ifi is the least index such that qi∈{2,7} then qi=2.(x)
Ifi is the least index such that qi∈{4,5} then qi=4.(xi)
Ifn is odd and qi≠2, for all i≤m, then qm+1≠2.(xii)
Ifn is odd and qi≠1, 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ℰ⊆NS(n) has at least one member having the canonical form.Proof.
LetS=(A;A;C;D)∈ℰ be arbitrary and let (2.10) respectively (2.11) be the encoding of (A;A) respectively (C;D). By applying the elementary transformations (E1), we can assume that a1=c1=d1=+1. If n=1, S is in the canonical form. So, let n>1 from now on. Note that now the first quads, p1 and q1, necessarily belong to {1,6} and that p1≠q1 by (2.4). In the case when n is even and p1=6 we apply the elementary transformation (E5). Note that (E5) preserves the quads p1 and q1. Thus the conditions (i) and (vi) for the canonical form are satisfied.
The conditions (ii), (iii), and (iv) are pairwise disjoint, so at most one of them may be violated. To satisfy (ii), it suffices (if necessary) to apply to the pair(A;A) the transformation (E2). To satisfy (iii) or (iv), it suffices (if necessary) to apply to the pair (A;A) the transformations (E1) and (E2).
For (v), assume thatpi and pi+1 have the same symmetry type and that i is the smallest such index. Also assume that pi+1∉{1,6}, that is, pi+1∈{3,8}.
We first consider the case wherep1=1 and pi and pi+1 are symmetric. By our assumption, we have pi+1=8, and, by the minimality of i, i must be odd. We first apply (E2) to the pair (A;A) and then apply (E5). The quads pj for j≤i remain unchanged. On the other hand, (E2) fixes pi+1 because it is symmetric, while, (E5) replaces pi+1=8 with 1 because i+1 is even. We have to make sure that previously established conditions are not spoiled. Only condition (iii) may be affected. If so, we must have i=1 and we simply apply (E2) again.
Next, we consider the case where againp1=1 while pi and pi+1 are now skew. Thus pi+1=3 and i is even. We again apply (E2) to the pair (A;A) and then apply (E5). The quads pj for j≤i again remain unchanged. On the other hand (E2) replaces pi+1=3 with 6 while (E5) fixes it because i+1 is odd. Note that in this case none of the conditions (i–iv) and (vi) will be spoiled.
The remaining two cases (wherep1=6) can be treated in a similar fashion. Now assume that any two consecutive quads pi, pi+1 have different symmetry types and that the last quad, pm, is symmetric. Assume also that pm+1≠0, that is, pm+1=3. If p1=1 then m is odd and we just apply (E5). Otherwise p1=6 and m is even and we apply the elementary transformations (E1) and (E2) to the pair (A;A) and then apply (E5). After this change, the conditions (i–vi) will be satisfied.
To satisfy (vii), in view of (vi) we may assume thatq1=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 (viii), (if necessary) reverseC or D, or both. To satisfy (ix), (if necessary) interchange C and D. To satisfy (x), (if necessary) apply the elementary transformation (E4). Note that in this process we do not violate the previously established properties.
To satisfy (xi), (if necessary) switchC and D and apply (E4) to preserve (x). To satisfy (xii), (if necessary) replace C with –C′ or D with –D′, or both.
Hence,S is now in the canonical form.We end this section by a remark on Golay-type normal sequences. Let(A;B)∈GS(n), with n=2m>2. While the Golay sequences (A;B) and (B;A) are always considered as equivalent (see [13]) the normal sequences (A;A;B;B) and (B;B;A;A) may be nonequivalent. It is easy to show that, in fact, these two normal sequences are equivalent if and only if the binary sequences A and B* are equivalent, that is, if and only if B*∈{A;-A;A′;-A′}.The equivalence classes of Golay sequences of length ≤40 have been enumerated in [13]. This was accomplished by defining the canonical form and listing the canonical representatives of the equivalence classes. These representatives are written there in encoded form as δ1δ2⋯δm obtained by decomposing (A;B) into m quads. These are Golay quads and should not be confused with the BS-quads defined in Section 2. If (A;B)∈GS(n) is one of the representatives, it is obvious that B*≠-A and B*≠-A′, and it is easy to see that also B*≠A. Thus. if B* is equivalent to A we must have B*=A′. Finally, one can show that the equality B*=A′ holds if and only if δi≡i(mod2) for each index i. For another meaning of the latter condition see [13, Proposition 5.1]. Thus an equivalence class of Golay sequences GS(n) with canonical representative (A;B) provides either one or two equivalence classes of NS(n). The former case occurs if and only if δi≡i(mod2) for each index i.By using this criterion, it is straightforward to list the equivalence classes ofNS(n) of Golay type for n≤40. For instance, if n=8 there are five equivalence classes of Golay sequences. Their representatives are (see [13]) 3218, 3236, 3254, 3272, and 3315. Only the last representative violates the above condition. Hence, we have exactly 4+2=6 equivalence classes of Golay type in NS(8).


## 4. The Symmetry Group ofNS(n)

We will construct a groupGNS of order 512 which acts on NS(n). Our (redundant) generating set for GNS will consist of 9 involutions. Each of these generators is an elementary transformation, and we use this information to construct GNS, that is, to impose the defining relations. We denote by S=(A;A;C;D) an arbitrary member of NS(n).To constructGNS, we start with an elementary abelian group E of order 64 with generators ν, ρ, and νi, ρi, i∈{3,4}. It acts on NS(n) as follows: (4.1)νS=(-A;-A;C;D),ρS=(A′;A′;C;D),ν3S=(A;A;-C;D),ρ3S=(A;A;C′;D),ν4S=(A;A;C;-D),ρ4S=(A;A;C;D′).Next, we introduce the involutory generatorσ. We declare that σ commutes with ν and ρ, and that σν3=ν4σ and σρ3=ρ4σ. The group H=〈E,σ〉 is the direct product of two groups: H1=〈ν,ρ〉 of order 4 and H2=〈ν3,ρ3,σ〉 of order 32. The action of E on NS(n) extends to H by defining σS=(A;A;D;C).We add a new generatorθ which commutes elementwise with H1, commutes with ν3ρ3, ν4ρ4, and σ, and satisfies θρ3=ρ4θ. Let us denote this enlarged group by H̃. It has the direct product decomposition (4.2)H̃=〈H,θ〉=H1×H̃2,
where the second factor is itself a direct product of two copies of the dihedral group D8 of order 8: (4.3)H̃2=〈ρ3,ρ4,θ〉×〈ν3ρ3,ν4ρ4,θσ〉.
The action of H on NS(n) extends to H̃ by letting θ act as the elementary transformation (E5).Finally, we defineGNS as the semidirect product of H̃ and the group of order 2 with generator α. By definition, α commutes with ν, ν3, ν4 and satisfies (4.4)αρα=ρνn-1,αρjα=ρjνjn-1,j=3,4;αθα=θσn-1.
The action of H̃ on NS(n) extends to GNS by letting α act as the elementary transformation (E5), that is, we have αS=(A*;B*;C*;D*).We point out that the definition of the subgroupH̃ is independent of n and its action on NS(n) has a quadwise character. By this we mean that the value of a particular quad, say pi, of S∈NS(n) and h∈H̃ determine uniquely the quad pi of hS. In other words, H̃ acts on the quads and the set of central columns such that the encoding of hS is given by the symbol sequences (4.5)h(p1)h(p2)⋯,h(q1)h(q2)⋯.
On the other hand, the definition of the full group GNS depends on the parity of n, and only for n odd it has the quad-wise character.An important feature of the quad-action ofH̃ is that it preserves the symmetry type of the quads. If n is odd, this is also true for GNS.The following proposition follows immediately from the construction ofGNS and the description of its action on NS(n).Proposition 4.1.
The orbits ofGNS in NS(n) are the same as the equivalence classes.The main tool that one uses to enumerate the equivalence classes ofNS(n) is the following theorem.Theorem 4.2.
For each equivalence classℰ⊆NS(n) there is a unique S=(A;A;C;D)∈ℰ having the canonical form.Proof.
In view of Proposition3.2, we just have to prove the uniqueness assertion. Let
(4.6)S(k)=(A(k);A(k);C(k);D(k))∈E,(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∈GNS. We can write g as g=αsh where s∈{0,1} and h=h1h2 with h1∈H1 and h2∈H̃2. Let p1(k)p2(k)⋯ be the encoding of the pair (A(k);A(k)) and q1(k)q2(k)⋯ the encoding of the pair (C(k);D(k)). The symbols (i–xii) will refer to the corresponding conditions of Definition 3.1.
We prove first preliminary claims (a–c).
(a)p1(1)=p1(2) and, consequently, q1(1)=q1(2).
Forn even this follows from (i). Let n be odd. When we apply the generator α to any S∈NS(n), we do not change the first quad of (A;A). It follows that the quads p1(1) and p1(2)=g(p1(1))=h1(p1(1)) have the same symmetry type. The claim now follows from (i).
Clearly, we are done with the casen=2.
Ifn=3 it is easy to see that we must have p1(1)=p1(2)=6 and q1(1)=q1(2)=1. By (iv), for the central column symbols, we have p2(1)=p2(2)=0. Then (2.4) for i=1 implies that q2(k)∈{1,2} for k=1,2. By (xi) we must have q2(1)=q2(2)=1. Hence S(1)=S(2) in that case.
Thus from now on we may assume thatn>3.
(b) Ifn is even then, s=0.
By (i),p1(1)=p1(2)=1. Note that the first quads of (A;A) in S and in αS have different symmetry types for any S∈ℰ. As the quad h(1) is symmetric, the equality αshS(1)=S(2) forces s to be 0.
As an immediate consequence of (b), we point out that, ifn is even, a quad pi(1) is symmetric iff pi(2) is, and the same is true for the quads qi(1) and qi(2).
(c)p2(1)=p2(2).
We first observe thatp2(1) and p2(2) have the same symmetry type. If n is even this follows from (b) since then g=h. If n is odd then under the quad action on p2, each of α, ν, ρ preserves the symmetry type of p2. Now the assertion (c) follows from (ii) and (iii) if p1(1) and p2(1) have different symmetry types, and from (v) otherwise.
We will now prove thatA(1)=A(2).
Assume first thatn is even. Then p1(1)=p1(2)=1 by (i), s=0 by (b), and the equality h1(p1(1))=p1(2) implies that h1(1)=1. Thus h1∈{1,ρ}. Let i be the smallest index (if any) such that the quad pi(1) is skew. Then pi(1)=pi(2)=6 by (iii). Hence h1(6)=6 and so h1=1 and A(1)=A(2) follows. On the other hand, if all quads pi(1) are symmetric, then all these quads are fixed by h1 and so A(1)=A(2).
Next assume thatn is odd. Then p1(1)=p2(1)∈{1,6} by (i). Let i<m be the smallest index (if any) such that the quads pi(1) and pi+1(1) have the same symmetry type.
We first consider the casep1(1)=1. Since n is odd, α fixes the quad p1, and so h1 must fix the quad 1. Thus we again have h1∈{1,ρ}.
Ifi is even then, by minimality of i, both pi(1) and pi+1(1) are skew. By (v), we have pi+1(1)=pi+1(2)=6. Since i is even, α fixes pi+1 and so we must have h1(6)=6. It follows that h1=1. As i>1, the quad p2(1) is skew and by (iii) we have p2(1)=p2(2)=6. Since α maps p2 to its negative, we must have s=0. Consequently, A(1)=A(2).
Ifi is odd then both pi(1) and pi+1(1) are symmetric. By (v) we have pi+1(1)=pi+1(2)=1. Since i is odd, α maps pi+1 to its negative. Since ρ fixes the symmetric quads, we conclude that 1=g(1)=αsh1(1)=αs(1) and so s=0. If all quads pi(1) are symmetric, then they are all fixed by g and so A(1)=A(2). Otherwise, let j be the smallest index such that pj(1) is skew. By (iii) we have pj(1)=pj(2)=6, and 6=pj(2)=g(pj(1))=g(6)=h1(6) implies that h1=1. Thus A(1)=A(2).
We now consider the casep1(1)=6. Since n is odd, α fixes the quad p1, and so h1 must fix the quad 6. Thus we have h1∈{1,νρ}.
Ifi is even then, by minimality of i, both pi(1) and pi+1(1) are symmetric. By (v) we have pi+1(1)=pi+1(2)=1. Since i is even, α fixes pi+1 and so we must have h1(1)=1. It follows that h1=1. As i>1, the quad p2(1) is symmetric and by (ii) we have p2(1)=p2(2)=1. Since α maps p2 to its negative, we must have s=0. Consequently, A(1)=A(2).
Ifi is odd then both pi(1) and pi+1(1) are skew. By (v) we have pi+1(1)=pi+1(2)=6. Since i is odd, α maps pi+1 to its negative. Since νρ fixes the skew quads, we conclude that 6=g(6)=αsh1(6)=αs(6) and so s=0. If all quads pi(1), i≤m, are skew, then they are all fixed by g and pm+1(1)=pm+1(2)=0 by (iv). Now 0=pm+1(2)=h1(pm+1(1))=h1(0) entails that h1=1 and so A(1)=A(2). Otherwise let j be the smallest index such that pj(1) is symmetric. By (ii) we have pj(1)=pj(2)=1, and 1=pj(2)=g(pj(1))=h1(1) implies that h1=1. Thus A(1)=A(2).
It remains to consider the case where any two consecutive quadspi(1) and pi+1(1), i<m, have different symmetry types. Say, the quads pi(1), i≤m, are skew for even i and symmetric for odd i. By (i) and (iii) we have p1(1)=p1(2)=1 and p2(1)=p2(2)=6. Then h1 must fix the quad 1, and so h1∈{1,ρ}. Since 6=p2(2)=g(p1(2))=g(6)=αsh1(6), we must have s=0 and h1=1 or s=1 and h1=ρ. In the former case, we obviously have A(1)=A(2). In the latter case, all quads pi(1), i≤m, are fixed by g. Moreover, if m is even also the central column pm+1 is fixed by g and so A(1)=A(2). On the other hand, if m is odd, then the quad pm(1) is symmetric and the second part of the condition (v) implies that pm+1(1)=pm+1(2)=0. Hence again A(1)=A(2).
Similar proof can be used if the quadspi(1), i≤m, are symmetric for even i and skew for odd i. This completes the proof of the equality A(1)=A(2). The proof of the equality (C(1);D(1))=(C(2);D(2)) is the same as in [5].


## 5. Representatives of the Equivalence Classes

We have, computed a set of representatives for the equivalence classes of normal sequencesNS(n) for all n≤40. 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. This compact notation is used primarily in order to save space, but also to avoid introducing errors during decoding. For each n, the representatives are listed in the lexicographic order of the symbol sequences (2.10) and (2.11).In Tables2 and 3, we list the codes for the representatives of the equivalence classes of NS(n) for n≤15 and 16≤n≤29, respectively. As there are 516 and 304 equivalence classes in NS(32) and NS(40), respectively, we list in Table 4 only the 36 representatives of the sporadic classes of NS(32). The cases (5.1)n=6,14,17,21,…,24,27,28,30,31,33,34,…,39
are omitted since then NS(n)=∅. We also omit n=40 because in that case there are no sporadic classes. The Golay-type equivalence classes of normal sequences can be easily enumerated (as explained in Section 3) by using the tables of representatives of the equivalence classes of Golay sequences [13].Table 2
Class representatives forn≤15.
n=110  0n=216  1n=3160  11n=4116  61n=51160  640n=711660  612226113  162336160  126246163  1261n=811163  661821613  616831613  644341638  611651661  618361686  613171866  6311n=9116133  64140216163  64150361180  16640n=10111863  66311216166  64156316613  61838416616  61831518863  63311n=111611680  1642312616163  126232n=121161383  6412612163868  6122433186338  6314224186631  631422n=1311616133  641485326116680  128632036168160  1613441n=15161613163  12676761261683860  12626262Table 3
Class representatives for16≤n≤29.
n=16111186366  66631811211186636  66631181311631866  66186311411633381  66181163511636618  66188836611638133  66183688711661836  66116381811663681  66111863911666318  661181361011668163  661136181111816333  663618881211816663  663611181316131686  616861311416133831  616816131516136168  616883861616138313  616838681716161386  616168311816163861  616116831916163861  641243282016166138  616183162116166138  641271562216168613  616131682316381331  611668132416381661  611661832516388338  611638162616388668  611631862716611368  618368862816611638  618361162916618361  618338833016618631  618331133116831313  613868683216833838  613816163316836161  613842423416836161  613883833516838686  613831313616838863  613443133716861613  613161683816863868  613116863916866131  613183134016868386  613138314118116333  636618884218116663  636611184318631133  631866884418633388  631811664518636611  631888334618638866  631833114718661163  631166184818663688  631118664918666311  631181335018668836  631133815118886366  633318115218886636  63331181n=181161633881  641242146n=1911168186360  6643551210n=2011166131836  661168638121166861836  661131638131181616633  663616118841186161633  663161618851186868366  663131381161188686366  663313181171611663138  644182761481613383113  616816136891613383186  6168161331101616138631  6164224786111616311386  6161866831121616681386  6161136831131616831361  6161386883141616833886  6161381631151616836113  6161388368161616838638  6161383116171638133138  6116681316181638133161  6116681383191638883818 6183331633201661813881 6116361666211661863138 6183311316221661863161 6183311383231683381313 6138836868241683611313 6138166868251683831361 6138386883261683833886 6138381631271683836113 6138388368281683838638 6138383116291686613113 6131831368301686613186 6131831331311863161133 6318616688321863831133 6318386688331881616663 6336161118341886161663 6331616118351886868336 6331313881361888686336 6333131881n=25116161383131636414148485143216161613831636414148584143316161613861636414148585143416161686131636414158585143n=2911613831313168306414148415158432161686161313860641515851514853Table 4
Sporadic classes forn=32.
11111636366331881  666618184554227721111663318816363  666645541188272731166186333886318  664123181472117641166186366113681  664123185863556751166813633883681  661432814127116761166813666116318  661432818536557671613161361683831  616861684252574781616168313861313  641265176582648791616168338613838  6412623728284126101616168361386161  6412623756567358111616383883163861  6412214634822843121616386113133168  6412434384672376131616386186866831  6412282832157623141616613813136831  6412565684677623151616613886863168  6412717132152376161616616116833861  6412785365172843171616831613868686  6412348265823512181616831638616161  6412376243437358191616831661383838  6412376271714126201638163886681331  6142241631477413211638163886681331  6241142632488423221661166113688631  6142758368527413231661166113688631  6241857367518423241683161638383861  6138642142161717251683161661616138  6138642183575656261683383813863131  6138421671711253271683383886136868  6138164234348746281683616113866868  6138428321218256291683616186133131  6138834235351743301683838338386138  6138342816574646311683838361613861  6138342842831212321686168638686131  6131613142475752331818633611886666  6363445518812222341818666636638811  6363111144552772351863116636816611  6341268841334537361863116663183388  6341268814221826Note that in the casen=1, there are no quads and both zeros in Table 2 represent central columns.



---

*Source: 937941-2011-03-09.xml*