HIM

Ml!

$

142
717

 

THEfifi'
7.
:02)

This is to certify that the
dissertation entitled

CONSTRUCTION OF EVEN LENGTH BINARY SEQUENCES
WITH ASYMPTOTIC MERIT FACTOR 6.0

presented by

Tingyao Xiong

has been accepted towards fulfillment
of the requirements for the

Ph.D. degree in Mathematics

 

 

Major Professor’s ignature
AMM+ b , 10 I O
0

Date

 

MSU is an Affirmative Action/Equal Opportunity Employer

 

LIBRARY
Michigan State
University

 

 

 

u-I-O-I-O-o_o-u-o-I-I-.-0-0-O-

~o~u-o-.o--

'I¢-D-I-p- o -

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SIOB KProilMPndCIRCIDatoDueJndd

 

 

CONSTRUCTION OF EVEN LENGTH BINARY SEQUENCES WITH
ASYMPTOTIC MERIT FACTOR 6.0

By

Tingyao Xiong

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY

Mathematics

2010

 

ABSTRACT

CONSTRUCTION OF EVEN LENGTH BINARY SEQUENCES WITH
ASYMPTOTIC MERIT FACTOR 6.0

By

Tingyao X iong

The known families of binary sequences having asymptotic merit factor 2 6 are all
modifications to real primitive character sequences. In this thesis, we show a general
technique of constructing an even length binary sequence based on a symmetric or
antisymmetric sequence. With this technique, we will give new modifications to the
character sequences of length N = p, N = pq, and N = p1p2 . . . p7- respectively. This
in turn gives the construction of binary sequences of length 2p, 2pq, and 2p1p2 . . .pr

with asymptotic merit factor 6.0.

 

DEDICATION

This dissertation is dedicated to my dearly beloved husband Xuejian Liu and
dearest son Cephas Liu. I give my deepest expressions of love and appreciation
to them for the encouragement they gave and the sacrifices they made during this
graduate program.

Special gratitude goes to my loving parents Guowei Xiong and Qingfu Wang,
whose words of encouragement and push for tenacity ring in my ears. My sister
Tingqi Xiong has always stood by me and is very special.

I also dedicate this dissertation to my parents—in—law Chengxun Liu and Quanqin

Liu, who have supported me throughout the entire process.

 

ACKNOWLEDGMENT

I would like to express my deepest and sincerest gratitude to my advisor, Dr.
Jonathan I. Hall, for his exceptional support and constant encouragement. Without
his help, this thesis would not have been possible. I am very thankful to him for his
understanding, unconditional trust, and unwavering faith in me, which have helped
me persevere through the most challenging times of my doctoral program. It has
been an enormously enjoyable experience to work under his supervision.

My gratitude goes to my defense committee members, Dr. Meierfrankenfeld Ul-
rich, Dr. Michael Shapiro, Dr. George Pappas and Dr. Rajesh Kulkarni, for their
expertise and precious time. I am thankful to Dr. Meierfrankenfeld Ulrich for his
countless hours of answering my dispersive questions. I would like to thank to Dr.
Michael Shapiro for his generous help, including that of translating 3 Russian pa-
per into English for me. Thank you to Dr. George Pappas for all the enlightening
conversations. Special thanks to Dr. Raj'esh Kulkarni for consenting to serve on my
committee despite the late notification.

I acknowledge and thank Dr. Jonathan J edwab for his generous help, even though
we have never met each other.

Finally I would like to thank Dr. Zhengfang Zhou and Mrs. Barbara Miller. Their

encouragement and support will forever be appreciated.

iv

 

TABLE OF CONTENTS

List of Tables ................................. vi
List of Figures ................................ vii
Introduction ........................... 1
1.1 History of Merit Factor Problem ..................... 2
1.2 Merit Factor and Littlewood’s Conjecture ............... 9
Known Results ......................... 11
2.1 Theoretical Results ............................ 11
2.2 Numerical Approaches .......................... 15

2.2.1 Skew-symmetric Sequences .................... 15

2.2.2 Exhaustive Computation ..................... 16

2.2.3 Periodic Appending ........................ 16
Preliminaries .......................... 20
3.1 Definitions ................................. 20
3.2 Properties ................................. 23
Construction of Even Length Binary Sequences ......... 32
Sequences of Length 2p with Asymptotic Merit Factor 6.0 . . . . 41
5.1 The Asymptotic Merit Factor of Doubled Legendre Sequences . . . . 41
5.2 The Asymptotic Merit Factor of Parker’s Sequences .......... 44
Sequences of Length 2pq with Asymptotic Merit Factor 6.0 . . . . 47
6.1 Theorem 6.1.1 and Proof ......................... 48
6.2 The Doubling of Known Sequences ................... 57
6.3 The Construction of New Sequences and Doubling ........... 61

6.3.1 Conclusion ............................. 79
Sequences of Length 2p1p2 . . . pr with Asymptotic Merit Factor 6.0 80
7.1 Construction ............................... 80
7.2 Periodic Autocorrelations of Sequences z ................ 83
7.3 Proof of Theorem 7.1.3 .......................... 109
Bibliography .......................... 115

 

LIST OF TABLES

2.1 Primitive characters and sequences of Legendre families ........ 13

vi

 

LIST OF FIGURES

1.1 A Simple Model of Communication Channel .............. 4

1.2 Pulse Compression Radar Using Correlation .............. 5

5.1 Merit factor for Parker’s sequences with appending ratio 0.065. . . . . 43
vii

Chapter 1

Introduction

The problem of finding long binary sequences with the best value of the merit factor
has resisted decades of attack by mathematicians and communications engineers.
The best theoretical proven value for the asymptotic merit factor, 6.0, has remained
unchanged since 1988. All the previously known binary sequence families attaining
the highest asymptotic merit factor 6.0 are of odd length. This thesis is mainly focused
on constructing new families of binary sequences of even length with asymptotic merit

factor 6.0.

In Chapter 1, we introduce the historical background of the Merit Factor Problem,
in both theoretical and applicable aspects. We will give a brief review of the known
results about the asymptotic merit factor, both theoretical and numerical, in Chapter
2. In Chapter 3, we will collect the definitions and properties which will be referred to
in the following chapters. In Chapter 4, we show a common technique of constructing
an even length sequence based on a symmetric or antisymmetric sequence. With
the technique introduced in Chapter 4, we will construct binary sequences of length
N = 2p, N = 2pq, and N = 2p1p2 . . .pr with asymptotic merit factor 6.0 in Chapters
5, 6, 7 respectively.

Now we start with the history of Merit Factor Problem (M.F.P.), and the appli-

1

 

 

cation of M.F.P. for both theoretical and practical purposes.

1.1 History of Merit Factor Problem

In this thesis, we transfer the well-known binary digits 0 and 1 into the equivalent
forms: 1 = (—1)0 and —1 = (—1)1. Thus we call sequence a: = (230,2:1, . . . ,xN_1) a
binary sequence of length N if all the :cj’s are +1 or —1, wherej = 0,1,... ,N — 1.
Correlation is a commonly used measure to describe the similarity, or relatedness,
between two phenomena. When properly normalized, the correlation measure is a
real number between +1 and —1. For instance, in statistics, the correlation between
two sets of data is called their covariance. Specifically, let or = ( 010,011, . . . ,an )
and '7 = ( 70, '71, . . . , 7n ) be two n—dimensional vectors of real numbers, which could

represent two sets of experimental data. The magnitudes of these vectors are
n 2 1 n 2 1
la|=(zaz-)?, |7|=(Z7,; )2
i=1 i=1

then the covariance of the two data sets

 

 

C(a, ) = (or-'7) = 2&1 “Hi

1 1
.04 m (3:10;): ( 3:173):

Similarly, supposea: = ($0,271, . . . ,xn ) andy = (310,311, . . . ,yn ) are both binary
vectors. Thus

n 1 n 1
le=<zx3fl=¢a=<§jy3>2=lyl

i=1 i=1

then the binary correlation between a: and y is

n
1
(7013,31) = 52:151.?”
i=1

2

 

 

Note that if a: = y, we call C(x, at) = 1 the autocorrelation of sequence :c.

To conduct research in simpler forms, mathematicians and engineers have studied
the following correlations forms. The application of these definitions will become clear
soon.

Let a: = (x0,x1,...,a:N_1) and y = (y0,y1,...,yN_1) be sequences of length
N (not necessarily binary). The aperiodic crosscorrelation function between a: and y

at shift 2' is defined to be

N—i—l
A$,y(z')= Z xjyj+,-, i=1,...,N—1 (1.1)
.=0

When :1: = y, we call Ax(i) = 143,51; (i) the aperiodic autocorrelation function of a: at
shift 2', where A; (i) is defined as following:

N—i—l
A5,;(z'): Z xjxj+,-, i=1,...,N—1 (1.2)
“:0

Binary sequences with low aperiodic autocorrelations have been widely applied
in communication engineering. To see this statement more clearly, we look at a
simplified communication system with only one signal sender and receiver.

In order to communicate information from a sender to a receiver, the sender needs
to transmit messages through the so called communication channel. It is important
to distinguish here between a signal and a message. In this thesis, 3 signal is a single
digit 1 or —1. While a message means a binary sequence with entries 1 or —1.

As shown in Figure 1.1, in the real world, the sender and receiver have to commu-
nicate over a noisy communication channel. That is, the signals that are received do
not look identical to the signals that are sent. As a result, the receiver must decide
which signal was actually sent, given the actual signal that was received.

The basic problem that serves as a model of detection theory concerns the situation

3

 

 

  
 

 

 

  
 
 

, Noisy ,
Signal _ Co mmunication Slgnal
Sender Channel Receiver

  

 

 

 

 

 

 

Figure 1.1: A Simple Model of Communication Channel

in which there are two possible transmitted signals, represented by 1 and —1, and
these are corrupted by Gaussian noise. For instance, if 1 ( or —1 ) is sent, let 1' be the
corresponding signal received. Then we assume that r has a Gaussian distribution
(normal distribution) with mean value 1 ( or —1 ) and standard deviation 0. The
larger value of o, the noisier the channel and the greater the probability that the

receiver will make an incorrect decision as to what was sent.

If a message a: is represented by a binary sequence x = ($0,121, . . . ,$N_1) of
length N, we use notation mm = (0,...,0,a:0,a:1,...,a:N__1_2-) to represent the
sequence delayed by i time units. Then Ag; (i) represents the correlation between
message a: and the delayed message xii] (not normalized). In 1953, in a foundational
paper [1] of communication engineering, Barker proposed a group synchronization
digital system, based on the use of binary sequences a: with correlations | A1; (i) I’s
collectively small. The purpose of this constraint was to ensure a large difierence
between A$(O), the correlation of message m to itself, and A; (i), the correlation of

message a: to its delay xii].

In 1961, Fano [2] proved a considerably general result: Over a channel corrupted

by Gaussian noise, the optimum decision process is to perform correlation detection,

4

 

that is, to calculate the correlation between the actual received message and ideal
models of each of the possibly transmitted messages. And the message having the
highest value of the correlation with the actual received message is the message that
was actually sent. The optimum detector for a given channel is known as the matched
filter for that channel, and the result we have just mentioned is frequently described
as follows: the matched filter for the Gaussian channel is a correlation detector.
Since 1960’s, binary sequences with low aperiodic autocorrelations have been
widely applied in radar, sonar, and many other communication systems as well as

synchronization.

 

 

    

 

 

I ,
WEIGHTING CORRELATION

 

 

I
I MISMATCHED : MATCHED
I SECTION I FILTER
: : SECTION

Figure 1.2: Pulse Compression Radar Using Correlation

Figure 1.2 is from Radar Handbook ( [3], page 10.2, figure (0)). It gives a concrete
example of the application in a radar system. In Figure 1.2, the detection process is
called pulse compression radar using correlation , which has been widely used in radar

’ is received, the correlation detector

technology. In this system, once a message a:
(“CORRELATOR” in the figure) not only calculates the correlations between 2:, and
all the possibly transmitted messages 2:, but also the correlations between 12’ and
all the delays of xlzl by i time units. The message :1: having the highest correlation

values with 2:, will be detected as the message that was actually sent. Therefore we

5

want the correlations between 2:, and all the delays of xii] (~ Ag;(i)) to be small, for
i > 0, since rlzl is not the correct message. In this model, we can see clearly that
using binary sequences with low aperiodic autocorrelations will increase the accuracy
of correlation detector significantly. More discussion about the application of binary
C sequences for which |A$(i)| is small for each i 75 0, can be found in [4], [5], and [7].

The importance of finding binary sequences a: with small [Ax (i)| values led Barker

to seek answers for large N to the following question:
Question 1.1.1. minimise maxO <i < N [Ax (i)| over all length N binary sequences as.

Barker therefore observed that, for this synchronization application, an ideal bi-

nary sequence :r of length N must satisfy
|A3(i)| = O or 1 for all i 75 0. (1.3)

and he proposed the study of such sequences. We call any binary sequence satisfying
condition (1.3) a Barker Sequence.

This motivates the search of binary sequences .7: of large length N, for which the
elements of the set {|A$(1)|, |A$(2)|,..., |A$(s - 1)|} are collectively as small as
possible. Unfortunately, most mathematicians believe that the following conjecture

is true:
Conjecture 1.1.2. There is no Barker sequence of length N > 13.

Another important definition for binary sequences, which is similar to the defi-
nition of aperiodic correlation, is called the periodic correlation. We will use both
aperiodic and periodic correlations heavily in this thesis.

The periodic crosscornelation function between :3 and y at shift i is defined to be

N—l

Ric’s/(2') = 2 xj yj+i, 0 S ’i < N (1.4)
i=0

 

where all the subscripts are taken modulo N. Similarly, when a: = y, put

N — 1
PW) = 2 xj 2,4,, 0 s i < N, (1.5)
i=0
the periodic autocorrelation function of a: at shift i, where all the subscripts are taken
modulo N.

Mn and Storer proved the following theorem [6] in 1961.

Theorem 1.1.3. ( Taryn and Storer) Conjecture 1.1.2 is true for odd N. Further-

more, for a Barker sequence B of even length N > 2, PB (i) equal 0 for all 0 < i < N.

Readers can find more discussion about Barker sequences in many papers, for

instance [8].

In 1972, to describe the “good” binary sequences with aperiodic autocorrelations
collectively small, Golay ([9]) proposed another important measure called Merit Fac-
tor. Given a binary sequence a: of length N, the merit factor of the sequence 2:, is

defined as
N2
2 23,1211 As (2')
Using the concept Merit Factor, given N fixed, finding a binary sequence :1: of length

Fa:

 

(1.6)

N with [Ax (i)|’s collectively small is equivalent to finding a binary sequence a: of
length N with high merit factor value.

Moreover, for the family of sequences
S: {x1,r2,...,zn,...}

where for each i Z 1, xi is a binary sequence of length Ni, if as i approaches infinity,

7

 

N,- also approaches infinity, and the limit of Fri exists, then we call

F 151130 sz- (1.7)
the asymptotic merit factor of the sequence family S.

Golay not only gave a simple measure describing the feature that a binary sequence
has aperiodic autocorrelations collectively small but also revealed the close connection
between the length of the sequence and the aperiodic autocorrelations in an elegant
way. For nearly twenty years, Golay studied the following problem: Let Xn be the

set of all binary sequences of length n,
QUBStiOIl 1.1.4. Fn = maszXn F1; =?

In his series of publications ([9], [10], [11],[12], [13], and [14]), Golay either used
probability theory or computer searching to study Question 1.1.4. Indeed, Question
1.1.4 is still open. That is, at each length N, we do not know the maximum merit
factor value of all the binary sequences with length N except by conducting exhaustive
search for small N. We will discuss these numerical searching results in next chapter.

As discussed before, finding a binary sequence a: with |A$(i)|’s collectively small
can be considered as finding a binary sequence x with high merit factor Fm. In real
communication systems, because of the large amount of information needed to be
transmitted, engineers have more interest in merit factor behavior when the length
of binary sequence is large. Meanwhile, mathematicians have made important break
through in finding the upper bound of the asymptotic merit factor of binary sequences.

To express this question in a mathematical form, we have the following:
Question 1.1.5. lim supn_,oo Fn =?

where Fn is as defined in Question 1.1.4.

 

 

Traditionally, people call Question 1.1.5 the Merit Factor Problem (M.F.P.). Com-
pared to Question 1.1.4, mathematicians have made remarkable progress on the
M.F.P., which will be discussed in more details in next chapter. This thesis is mainly
focused on constructing new families of sequences achieving the known highest value

of asymptotic merit factor.

1.2 Merit Factor and Littlewood’s Conjecture

Mathematicians (for instance, [18],[23], [15]) have tried to approach the merit factor
problem through complex analysis and number theory. An optimal method is to
study polynomials with i1 coefficients on the unit circle of the complex plane, which
have been studied by some famous mathematicians like Littlewood [17]. This section
will give some examples about this connection. Although the topic of this section will
not play a role in the rest of this thesis, here we observe that merit factor is not only
of engineering but also of mathematical interest.

Prior to Golay’s definition of merit factor in 1972, Littlewood [16] and other
number theorists studied questions concerning the norms of polynomials with :I:1
coefficients on the unit circle of the complex plane. Furthermore, some properties
and conjectures from complex analysis can be written in terms of Merit Factors.
Before we see some concrete examples, we need some definitions here.

Let Qa(z) = 25:61 air!i be the complex-valued polynomial whose coefficients
are the elements of the sequence a = (a0, a1, . . . ,aN_1) of length N. The Lg norm

of the polynomial Qa(z) on the unit circle of the complex plane is defined to be

27r . 1/16
[[Qallfi = (i/O [Qa(ez9)[fld0) (1.8)

If the coefficient sequence a = (a0, a1, . . . ,aN_1) is a binary sequence, then we can

9

write the merit factor of a as ([25], Theorem 1.2, page 35)

_ ”Qty”:
“can: — llQall‘21

 

a (1.9)

where Fa is the merit factor of sequence a as defined in (1.6).

The following is one of many Littlewood’s Conjectures ([17], §6, page370):

Conjecture 1.2.1. (Littlewood) Let Q N be the set of all the complex-valued polyno-
miaLs whose coefficients are the elements of some binary sequence of length N. Then
there exists a polynomial fN E QN, so that llfNHfi = N4 + 0(N4).

If we write Conjecture 1.2.1 in terms of merit factor, we will have
Conjecture 1.2.2. (Littlewood) limsupn_,00 Fn = 00.

By studying the L4 norms of polynomials with coefficients :I:1, Newman and
Byrnes [18] obtained an important result on the asymptotic behaviour of the merit

factor in 1990:

Property 1.2.3. The mean value of 1/F, taken over all sequences of length n, is

n-l

n .
[I

We see that the merit factor as defined in (1.6) is of considerable practical and
theoretical interest to both engineers and mathematicians. Starting in the next chap-

ter, we will be mainly focused on the Merit Factor Problem as introduced in Question

1.1.5.

10

Chapter 2

Known Results

In this chapter, we will review all the known research results, both theoretical and
numerical, about the Merit Factor Problems as mentioned in Question 1.1.5. From

now on, we always use (i, N) to represent the greatest common divisor of integers i

and N.

2. 1 Theoretical Results

For p an odd prime, a Legendre Sequence of length p is defined by the Legendre

symbols
aj = (f?) I j=03°")p—13
where
' 1, if ' is a s uare modulo ;
(l) ___ .7 q p (2.1)
p —1, otherwise.

More generally, for N = p1...p7~, where p1 < p2 < < pp and each pj is an odd
prime, a Jacobi Sequence B of length N is defined by

i=(iillé-l-lt)

11

 

Given a sequence a = ((10,011, . . . ,aN_1) of length N. We call

0” = (alfNJ’aLfNJ+1"”’aN—1’ 00’ 01’ "°’alle-1)

a of length N offset by the factor f.
In 1988, tholdt and Jensen [23] made an important breakthrough by proving

the following theorem:

Theorem 2.1.1. The asymptotic merit factor F of Legendre sequences of length p
offset by the factor f is

1/F = 1/6 + 8(f - 1/4)2, Ifl s 1/2, (2.3)

D

By Theorem 2.1.1, offset Legendre sequences have an asymptotic merit factor 6.0
at the fraction If | = i. This Theorem is very important because even today, 6.0 is
still the best theoretically proven value for asymptotic merit factors.

In 1991, J .M. Jensen, and HE. Jensen and Hoholdt [24] defined a new family of
binary sequences called Modified Jaclobi sequences at length N = pq, with p < q odd
primes:

+1, ifj=0,q,2q,...,(p—1)q
mj = —1, ifj=p,2p,...,(q—1)p (2.4)
(%) - ('91) , otherwise .

In the same paper [24], J .M. Jensen, and HE. Jensen and tholdt proved that

the formula (2.3) is also correct for Jacobi Sequences and Modified J aclobi sequences

of length pq provided p and q satisfy

(P + (1)5 10g4 N
N3

 

—>0, forN—ioo. (2.5)

12

 

On the other hand, given an odd prime p, the real primitive character modulo p takes

the form

(2.6)

X190): (13) rif(j,p)=1;

, otherwise

where (11;) is the Legendre symbol as defined in (2.1).
More generally, for an odd number N, where N is a product of distinct odd primes
p1p2 . . . p,- with p1 < p2 < - - - < pr, the real primitive character modulo N takes the

form

XNU) = Xp1(j)Xp2(J') - - - XPTU) (2-7)

The Legendre sequences, Jacobi and Modified Jacobi sequences just redefine the
value at the i—th position where (i, N) > 1. In this sense, all of the Legendre sequences,
Jacobi and Modified Jacobi sequences are modifications of character sequences. Table

2.1 shows the close connection between the two categories.

 

 

 

33k (k, N) = 1 k E 0(mod p) k E 0(mod q)
Legendre sequence x N (k) +1 —
Jacobi sequence x N (k) xq(k / p) xp(k/q)

at length N = pq

 

Modified Jacobi sequence XN(k) +1 —1

 

 

 

 

 

 

Table 2.1: Primitive characters and sequences of Legendre families

We can see clearly all the known families of sequences with high asymptotic merit
factor are highly related to the primitive character sequences as defined in (2.7). By
performing calculations on the character forms ( which are actually triple-valued ),
Borwein and Choi [25] proved that (2.3) is correct for all the sequences defined as in

13

 

 

(2.7) under an improved restriction on p,- ’s

e
11:,— —> 00 for any 6 small enough (23)
1

We can combine all the theoretical results mentioned above into the following

theorem.

Theorem 2.1.2. (Heholdt, Jensens, Borwein and Choi, 1988, 1991, 2001 ) Let aN
be

(I) a Legendre Sequence of length N = pl,
(2) a Jacobi or Modified Jacobi Sequence of length N = plpg,
(3) a real primitive character Sequence of length N = p1p2 . . . pr

with 191 < p2 < < pr and each pj is an odd prime. Now construct any infinite

sequence of such sequences

a = {aN1,aN2,...aNi,...},

Then the asymptotic merit factor F of a ofiset by the factor f is
1/F = 2/3 — 4m + 8f2, lfl s 1/2

provided that

NE/pl —+ 0, for any 6 > 0 small enough as N —> 00.

El

In Chapter 3, we will explore the properties of character sequences more deeply.

14

 

2.2 Numerical Approaches

2.2.1 Skew-symmetric Sequences

A common strategy for extending the reach of merit factor computations is to impose
restrictions on the structure of the sequence. One of the most historically popular
definition is the skew-symmetric binary sequences, defined by Golay [9]:

A binary sequence a = (a0, a1, . . . ,a2m) of odd length 2m + 1 is called a skew-

symmetric binary sequence if
am.” = (_lliam-i for 'i = 1, 2, . . . ,m.

Skew-symmetric binary sequences are good possibilities to have large merit factor

because of the following property [9]:

Property 2.2.1. A skew-symmetric binary sequence .7. of odd length has Az(i) = 0
for all odd i. CI

The computational advantage of only searching skew-symmetric binary sequences
with large merit factor is that it roughly doubles the sequence length that can be
searched with given computational resources. In [11], Golay showed that skew-
symmetric sequences attain the optimal merit factor value Fn (as defined in Question
1.1.1) for the following odd values it < 60: 3, 5, 7, 9, 11, 13, 15, 17, 21, 27, 29, 39, 41,
43, 45, 47, 49, 51, 53, 55, 57, and 59. The optimal merit factor over all skew-symmetric
sequences of odd length n was calculated independently by Golay and Harris [14] for
n _<_ 69 in 1990 and by de Groot, Wiirtz and Hoffmann [26] for n 5 71 in 1992. And
also in 1990, Golay and Harris [14] found good skew-symmetric sequences for odd
length n with 71 _<_ n S 117 by interleaving one symmetric sequences and another

anti-symmetric binary sequence.

15

Based on heuristic searches for long skew-symmetric sequences, Golay proposed

the following conjectures:

Conjecture 2.2.2. (Golay, [11]) The asymptotic optimal merit factor of the set of

skew-symmetric sequences is equal to lim sup.n_,00 Fn.

Conjecture 2.2.3. (Golay, [12]) limsupn_,oo Fn g 12.32.

2.2.2 Exhaustive Computation

The other results of exhaustive searching for Fn values are listed as following:
(i) for ”small n” in 1965 by Lunelli [19]
(ii) for 7 S n g 19 by Swinnerton-Dyer, as presented by Littlewood [16] in 1966
(iii) for n g 32 by Turyn, as presented by Golay [12] in 1982
(iv) for n S 48 by Mertens [20] in 1996

(v) for n S 60 by Mertens and Bauke [21] in 2004

2.2.3 Periodic Appending
From Section 2.1 we know that 6.0 is the best theoretical proven value of the asymp-

totic merit factor. In other words, we can safely claim that

6.0 3 lim sup Fn S 00
n—Ioo

In [23], tholdt and Jensen made the following conjecture:

Conjecture 2.2.4. (tholdt and Jensen) limsupnmoo F", = 6.0

16

 

 

On the other hand, some numerical observation ([27]) strongly suggest that

lim sup Fn > 6.0 .
n—+oo

Before we introduce that result, we need some definitions. Given sequences X =
{$0,x1,...,zN_1} of length N, Y = {y0, . . . in-l} of length M, a real number

0 g r <1, we define
e Rotation Xr = {x0+[TNJ,$1+[TNJI-~I$N_1+[7~NJ},
. rI‘fImcation XT={xO,$la-'°aerNJ—1}’
o Appending X;Y= {x0,...,a:N_1,y0,...,yM_1}.

In 2004, Borwein, Choi, and J edwab [27] used the rotation and appending method

as just defined and obtained the following result:

Observation 2.2.5. (Borwein, Choi, and Jedwab) Suppose X is a Legendre sequence
of length N = p with p prime, then

1 1
o For large N, the merit factor of the appended sequence X1; th‘I is greater than
6.2 when t ~ 0.03.

e For large N, the merit factor of the appended sequence X r; X; is greater than
6.34 for r ~ 0.22 and r N 0.72, when t ~ 0.03.

Furthermore, Borwein, Choi, and Jedwab ([27], Theorem 6.4 and equation (20))

gave an estimate of the asymptotic merit factor of the appended sequence X r; X; :

Theorem 2.2.6. (Borwein, Choi, and Jedwab) Let X be a Legendre sequence of

17

 

 

prime length p and let r, t satisfy 0 S r S 1 and 0 < t S 1. Then for large p

2 ' 2
t 1 l—t 1 .
FXT;X" l—t
t §(F—)1{T+1) ,fort=1.

Now we summarize the known results about the asymptotic merit factor of binary

sequences.
0 6.0 is the highest proven asymptotic merit factor value.

a All the known “good” sequences with high asymptotic merit factor are modi-

fication of the character sequences by putting new values at positions i, with

(i,N) > 1.

o All the known “good” sequences with high asymptotic merit factor are of odd

length: mm . . . pr, and each p, is an odd prime.

0 All the known “good” sequences with high asymptotic merit factor are rotations

of modified character sequences.

0 It may be possible to obtain sequences with asymptotic merit factor > 6.34 by

rotating, truncating, and appending a Legendre sequence.

In the summation above, we have put the key phrases in italic forms. In the
following chapters, we will construct new families of binary sequences. In contrast

with the features listed above, these new families of sequences satisfy the following:
0 Obtain high asymptotic merit factor value 6.0.
0 Give new modification of the character sequences at positions i, with (i, N) > 1.

o Are of even length: 2p1p2 . . . pr, and each p,- is an odd prime.

18

 

 

 

o Are free of rotations of modified character sequences.

We will start with introducing new definitions and properties in next chapter .

19

 

Chapter 3

Preliminaries

This chapter provides the definitions, notation and properties that will be used in later
chapters. Some well-known results are included in order to make the presentation self-

contained.

3.1 Definitions

Given a sequence a: = (r0, :I:1, . . . WEN—1) of length N, we have the Discrete Fourier

’II‘ansform (DFT) of the sequence, that is,

. N—1 .
xléjvl= Z racial“, j=o,1,...,N—1 (3.1)
k=0

where 5%, = egg“.

Definition 3.1.1. Given two sequences a: = (320,31, . . . ,xN_1) and

y = (y0,y1,...,yN_1), we define the product sequence b = x :1: y by b,- = mil/i: for
2': 0,1,...,N— 1.

Definition 3.1.2. A binary sequence a = (00, a1, . . . ,aN_1) of odd length is sym-

metric if az- = O‘N—ir for 1 S i S N — 1, and antisymmetric if a,- = "O‘N—i: for

20

 

1 S i S N — 1.
Lemma 3.1.3. Suppose N is an odd integer. We define a sequence

s=(sO,sl,...,sN_1)

of length N by

—1 W , i ',N =1;
3j = ( ) f0 ) (3.2)
0 , otherwise.

Then the sequence s is antisymmetric.

Proof. For 1 S j S N — 1, via Lemma 3.1.7 and 3.1.3, 3N—j = (—1)N—j =

(—1)N—j = —(—1)j = —s]- since N is odd. Therefore, 3 is antisymmetric. El
Definition 3.1.4. Given a binary sequence a = (010,011, . . .,aN_1), we write —a
for (—a0,—a1,...,—aN_1).

Definition 3.1.5. For 6 = 0,1, let the four sequences :Eflwl be given by

(”2")
5).") = (—1) (3.3)

For instance,
—fl(0) = —1) -1, +1, +1, - - - , —1,—]., +1, +1, . . .
and
15(1) = +1) _1) _1, +1, . . - , +1, -1, _1, +1, . . .

Definition 3.1.6. Suppose r is an integer. For any 1 S i S r, if (i, r) = 1, then
there artists a unique i7, with 1 S 5 S r, such that i '5. E 1 (mod r). Put i;- = E,

where k = min{i, r — i}.

21

 

For instance, when r = 5, i = 3, then 77,: = g = 2, because 3 x 2 E 1 (mod 5).
While {,1 = 33‘5“ = 2—5' = 3, because 2 = min{3,5 — 3}.

As (r — i)(r - E) E 1 (mod) r, we have
Lemma 3.1.7. Suppose r is a positive integer. For any integer i, if (i,r) = 1, then
M: r 42?. D

Forexample, ifr=5,i=3, then (r—i)r=(5—3)5=Z=5—35=3.

Definition 3.1.8. Given two nonnegative numbers A and B, A < B means that

there exist a positive constant C, independent of A and B, so that A < CB.

Definition 3.1.9. For an integer n, the divisor function d(n), is defined to be the

number of positive divisors of n, or

d(n) = Z 1

0<d|n
Definition 3.1.10. For n a positive integer, write n = 5:119:11), where p1; ’s are
distinct primes. We define w(n) = r to be the number of distinct prime divisors of n.
We will end this section with a notation commonly used in number theory.

Definition 3.1.11. Let n be a positive integer, and f (51:) be a function. Define

n n
2 ' f (x) = Z f(=v)
3:]. 3:1
(z,n)=1
For example,
4 N
Z’xz=12+32=10, and Z’l=¢(N).
x=1 . =1

where ¢(N) is the Euler Function of N.

22

 

3.2 Properties
Property 3.2.1. Let x = (x0,x1,...,xN_1) and y = (y0,y1,...,yN_1) be se-
quences of equal length N, and A$,y(i) and Px,y(i) are as defined in expressions
(1.1) and (1.4). Then

Px,y(’t) = Aggy“) + A$,y(N — 7.), fOT' 0 < Z < N.
In particular, if x = y, then

133(2) = A550) + A$(N — 2) for O < 2 < N.

Proof. The proof of Property 3.2.1 could be found in many resources, for instance in

([36], (2), page 137)- '3
Property 3.2.2. For any integer i, (_1)(im) = (—1)-i, for any odd m.

Proof. (_1)i(m+1) = 1 since m + 1 is even. Thus (_1)im = (—1)—i. El
Let the character sequence x N be as defined in expression (2.7). Then we have

the following property

Property 3.2.3. x N is symmetric if N E 1 (mod 4), and antisymmetric if N E 3
N —1

(mod 4). In particular, xN(—1)=(—1) 2 is 1 ifN E 1 (mod 4) and—1 ifN E 3

(mod 4).

Proof. First of all, we assume N = p, so r = 1. But in Z5, —1 is a square if and only

if p :— 1 (mod 4), as desired. Now suppose N = p1p2 . . . pr with r 2 2. Without loss

of generality, suppose pl 5 192 E Epk E 3 (mod 4), and pk+1 E pk+2 .3

23

 

pr E 1 (mod 4). Then by the r = 1 case,

xN(N-i) =Xp1(N-i)----ka(N-i) 'ka+1(N—i)“"Xpr(N-i)
= (—1)’°Xp1 (2') ----- ka(il - ka+1(i) - - - wait)

= (—1)kXN(i) -

Therefore, if k is even, then N E 1 (mod 4), XN(N — i) = XN(i), and XN is
symmetric; while if k is odd, then N .=_ 3 (mod 4), XN(N -i) = —XN(i), and XN is
antisymmetric. El

Property 3.2.4. Suppose N is odd. For the sequence a = (a0,a1,...,aN_1)
of length N, let the sequence 3 = (po,p1,...,pN_1) with s,- = (—1)jaj. Ifa is

symmetric, then fl is antisymmetric, while if a is antisymmetric, then B is symmetric.

Proof. If a is symmetric, then aj = aN_j, for 1 S j S N - 1. Therefore,
5': —1j01'= -1ja _-=——1N_ja _-=—fl _-sinceNisodd.
.7 J N .7 N J N ]

So ,6 is antisymmetric. Interchanging the roles of a and fl gives the other case. [3

Lemma 3.2.5. Suppose Xp is as defined in form (2.6). Then

p-l - .

p - 1 I if plk,
Z Xp(n)Xp(n — k) =
”:0 -1 , otherwise

Proof. Readers can find the proof to Lemma 3.2.5 in many references, for instance,
Lemma 2 in [42]. [I

An immediate application of Lemma 3.2.5 is the following property.

Property 3.2.6. For an odd prime p, suppose a is a Legendre sequence of length p
as defined in expression (2.1).

24

 

(1) Pa(i) = —1,ifp E 3 (mod 4).

(2) Pa(i) = 1 or —3, ifp El (mod 4).

iprl (mod 4);

a _ -,
Proof. For 0 < j < p, from Property 3.2.3, aj = p 3
if p E 3 (mod 4).

—aP—j’
For 0 < i < p

p—l
Pa(i) = Z ajaj+z~
.=0

p—I
= aoat + ap—iao + Z Xp(j)Xp(i + 2')
i=0

= a0(a,- + ap_,-) — 1 by Lemma 3.2.5
When p E 3 (mod 4),
ai=—ap_,- => Pa(i)=1XO—1=—I.

This finishes the proof of part (a). When p E 1 (mod 4),

a7; = ap_,- => Pa(i) = 2010a,; — 1 = 1 or — 3.

Theorem 2.1.1 is based on a famous result for Gauss Sums:

. 27r '.
Theorem 3.2.7. (Gauss Sum) For any j 6 Z, let gfv = e'le. The Gauss sum
is the DFT XNl EN] associated to the primitive character x mod N of (2. 7):

. N-l .
XN Iéjv I = Z XN(m) Ex}

m=0

25

 

Then

[leéjv] [= 2 (J ) (3.4)
0, otherwise

Proof. This is a very well-known result. Readers can find the proof in many resources,

for instance, [38] page233.

Lemma 3.2.8. Let N = p1p2...pr, where p1 < p2 < < pr’ are distinct odd
primes. Then

d(N) < r x E-
p1
where d(N) is the divisor function of N.

Proof.

d(N) < imp,- — 1) < r x 5
i=1 ”1

Cl
Property 3.2.9. Given a sequence x = (x0,x1, . . . ,xN_1) of length N, let x [5%,]
be defined as in expression (3.1) for 0 S j S N — 1. An interpolation formula is

N—l 5k

$I-Efyl=% Z fiaififvl

k=0 N+5N

Proof. This is a well-known result from numerical analysis. Readers can find the
proof in many references, for instance, [23], ((2.5), page162) and [24], (5.6), (page
624). III

For the rest of this section, to simplify the notation, without confusion, we

- it

use {3' instead of 5%,, to represent e .
Given a binary sequence x = (x0, x1, . . . ,xN_1) of length N, the following prop-
erty gives the relation between the merit factor F3; and the DFT of the sequence

x.

26

 

Property 3.2.10. Given a binary sequence x = (x0, x1, . . . ,xN_1) of length N, for

21r ' .
£3: = e—le, let x [63-] be as defined in expressions (3.1), and x [—£j] as defined as
in Property 3.2.9. Then the merit factor F3; satisfies

1 Eli? "leis-1 |4+ IxI—tjl l‘f
F}: _ 2N3 A -1

 

 

 

Proof. Again, the proof of this Property 3.2.10 could be found in many papers, for
instance [23], ((2.2) and (2.3), page 161), and [24], (expression (1.9), page 618). E]

If a sequence u could be written as a sum of two sequences U and v, then following

property shows the difference of l/Fu — l/FU.

Property 3.2.11. Suppose sequences u, U, and v are all of length N. And

3512-
u=U+v,thatisuj=Uj+vj,forj=0,1,...,N—1.Let§j=e , write

Uléjl = Uléjl+vI€jl = Ulijl+au where aj =v[€jl-

til-63°] = U {-6)} + vl-éjl = U {-63-} + b a where bj = vI-éjl-

Let
i_i__G_
Fu FU—ZN3
Then
N—l 4 2 2 2 2
IGIS Z [Iajl +6IUl€jll 1a,) +4(|Ul€jll +laj| )IajIIUIEle
j=0
N_1 4 2 2 2 2
+ Z [ijl +6|Ul-€jl[ ijl +4<|UI-t,-I| +ij| )lbjllUl-éjIH
j=O

27

 

Proof. From Property 3.2.10,

, zf=31(|ult,1|4+|uI—t,~1|4)
E: 2N3 _1

 

iii—01([Uléjl+aj[4+[UI-éjl+bj[4)
= 2N3

 

, 2§V=31(lvlt,-I|4+|UI-tjll4)
E: 2N3 _1

 

Therefore

_ 1
F17

31H

xii—01 (l U [5,] +a, [4 — | U 15,-I [4 + | U {-i)-1+ b,- |4 — | U {—53-} [4)
= 2N3

 

Then

N-l

Z (I U [5,)”,- [4- l U [5,] [4+ | U {—ng +12,- [4— | U {-6)} I4)
,=

N

s:

i=0

G

Ho

[0 U Iéjll + laj |)4 - [ U Iéjl [4 + ([ U I-ifl] + “’3' |)4 - [ U I-Ejl [4]

2

—l

S [lajl4 + 6 [Uléjll2 Iajl2 + 4( [Ulfjll2 + lajl2 )lajl [Ulfjl[[

MEEM

II
o

+ [ ijl4 + 6 lift-61]2 lb,-I2 + 4< |UI-t,-I|2 + ijl2 )ijl [UI-éjll]

.7

28

 

El

Given a family of binary sequences {A(n)}, if at each length n, we only change
positions considerably small in number compared to the n value, the following prop-
erty show that the asymptotic merit factor of the new family of sequences is equal to

the asymptotic merit factor of {A(n)}.

Property 3.2.12. Let {A(n)} and {B(n)} be sets of sequences, where each of A(n)
and B(n) has length n. Suppose that for each n, all elements of A(n) and B(n) are
bounded by a constant independent of n. Suppose further that, as n —+ co, the number
of nonzero elements of B(n) is o(\/;i) and that F A(n) = 0(1) and P A(n) = 0(n).

Then, as n —-> 00, the element-wise sequence sums {A(n) + B (n)} satisfy

1 1
F<A<n> + B(n)) =nF<A< __(11) + 0“”

 

Proof. The reader can find the detailed proof at [36] (Proposition 1., page138). El

For a sequence u (not necessarily binary) is the sum of two sequences U and v
(both U and v are not necessarily binary), the following property gives a concrete
expression of the periodic autocorrelations of a sequence u , in terms of the periodic

autocorrelations of U and v.

Property 3.2.13. For sequences u, U and v, (not necessarily binary) of length N.
Ifuj =Uj +vj ,forOSj <N—1, then we have

N—1N—1
:21 132(2)..— 1—21 PV(i)+ :le P3(t)+2 Z PV(t')Pv(i)
i=1
[v.11
+ Z [2PV(i) (t)PV,,(t)+2PV(t)P ,,V(t)]
N—ll
+ Z [2Pt(t)Pv,.,(t) + 2Pt(t)Pv,v(t) ]
i=1
29

r.

 

N—l

+ Z [2P14e(i)Pv,v(t) +P&,( )+P2V(t‘)]
i=1

where PV, Pu, va and PV,v are as defined in expressions (1.5) and (1.4).

Proof.

N—l 2 N— 1 2
213““): 2 [32:01 “j“ “j+i[

i=1

N—l N—l 2
[Z (V' +2) j)( Vj+i+vj+i)[

2
2

2
(VJ'VJ'H + Vivj+i + ”jVj+t' + ”j”j+i) [
N— 1 N— 1 2
(V'Vj +i+Vjvj+i+vjVj+i+vjv ”j+i)
= [PVUl + Pete) +10 m >+Pv<t>]’
2 N—1 2 N—l
= Z PV(i)+ Z Pv(i)+2 Z PV(2)Pv(il
i=1 i=1

+ Z [+2PV(?1)PV,v(i)+ 2Pv(t)P.,,V<t) ]

i=1

30

 

N—l
+ Z [ 2Pv(2)PV,v(i) + 2Pv(i)Pv,V(i) [

#1

N—l
+ Z [2PV,,( t)P,, (i)+PVv(i)+P 2V(t)]

i=1

=A+B+C+D+E+F

In the proof above, we have separated the summands into six groups. For instance,

in the summation above,

N— 1
F: [2PV,,(t)P W(t)+PVv(t)+P W(t)].

i=1

31

 

Chapter 4

Construction of Even Length

Binary Sequences

In this chapter, we will give a technique of constructing an even length binary sequence
based on a symmetric or an antisymmetric sequence. In the following chapters this
technique will be used heavily.

We will start with a property about the sequences fl as defined in expression (3.3).

Lemma 4.0.14. Let N be an odd number. If the binary sequence )8 of length 2N is

one of the four sequences 1:8(5) of Definition 3.1.5, then for 0 S a, b < 2N we have

 

(6—axb+a+26—1)
Ba. [31, = (*1) 2

Proof. When 0 S a, b < 2N, by definition
( a + 5) ( b + 6)
2 + 2
5a 3b = (*1)

(a+6)(a+6—1)+(b+6)(b+6—1)
=(-1) 2

32

 

 

e2+2es+fl—e—t%t2tzmrwfl—b-5

 

 

=(—1>
a2t2a6—a+b2+2b6—b 2
=(—1) 2 since6 —6=0when6=00r1
a2+2a6—a+b2+2b6—b 2
fi 4 —a +a—2a6
=(_1) 2
since - a2 + a is always even and — 2 a 6 is also an even

b2-a2+a—bi2b6—ga6
= (-1) 2

 

Lb—a)(b+a+26—1)
=(—1) 2 .

El

Suppose the sequence ,8 is one of the four sequences $305) from Definition 3.1.5.
The notations “;” and “*” are as defined in Observation 2.2.5 and 3.1.1. Then we

have the following two lemmas:

Lemma 4.0.15. Let a be an arbitrary binary sequence of length N, and let ,6 of
length 2N be one of the four sequences :Efiwl from Definition 3.1.5. Consider the

new sequence b = {a ; a} * ,8. For even i, we have

(—1)"/ 2 (Ash) + Pea», if 0 < t < N;
A6(1')=
(—1)i/2Aa(t—N), i > N

33

 

Proof. Note that the sequence b is of length 2N. When 0 < i < N,

ZN—i—l
A6“): 2 bjbj+i
i=0
N—i—l N—l 2N—i-1 (4.1)
= Z bjbj+t+ Z bjbj+t+ Z bjbj+t
'=0 j=N—i j=N

Here I I only contains the items from the first half of the sequence, Ir only contains
the items from the second half, and 1m consists of the products of the terms from the

first half and the terms from the second half. As i is even, by Lemma 4.0.14 we have

N—i—I N—i—l

II = Z bjbj+i= Z 5j5j+tajaj+t (4-2)
1:0 i=0

N—t—I i(i+2j+26—1)
___ Z (-1) 2 ajaj+i by Lemma 4.0.14
i=0

 

because i + 23' + 26 - 1 is odd when i is even

N—i—I
(—1)z/2 Z ajaj+i = (—1)z/2Aa(i) by Property 3.2.2
i=0

Similarly, by definition, we have

2N—i—1 2N—i—1
[7. = Z bjbj'i't = Z fijflj+zaj_Naj+z_N (4.3)
j=N j=N

34

N—i—l i(2j+i+26—1)

 

= Z (-1) 2 O‘j—Naj+i—N by Lemma 4.0.14
.20
N—i—I . _
= —1 2/201 -a- - = —1 z/2Aa i by Property 3.2.2
J 3+2
=0
N—l N—1
Im = Z bjbj-I-i = Z: fijflj+iajaj+i—N (4.4)
j=N—i j=N—i
. N—l—(N—i) .
= H)” 2 Z ajaj+N—z' = (-1)’/2Ae(N — 2').
i=0

Combining (4.2), (4.3), and (4.4), by PrOperty 3.2.1, we have
11+ 1m + I,» = (—1)i/2 [ 2Aa(i) + Aa(N — i) ] = (—1)i/2 [ 210(2) + Pap) ].

For even i 2 N, Lemma 4.0.14 gives

2N—i-1 2N—i—1
At(i)= Z: bjbj+t= Z [itinerant—N
j=0 j=0

2N—i—1 Ki+2j+26—1)
= Z (‘1) 2 aj“j+z‘—N
i=0

 

35

This finishes the proof of Lemma 4.0.15. Cl

Lemma 4.0.16. For an odd integer N, let a = (010,041, ""O‘N—ll be a symmetric
or antisymmetric binary sequence of length N as defined in Definition 3.1.2, and let
b = {al a} * B be the corresponding sequence defined in Lemma 4.0.15. For odd i, we

have

(—1)6+Ta0aN_z-, if 0 < i < N;

(—1)6+Taoai_N, if i Z N.

Proof. When 0 < i < N, following (4.1) we write

2N—i—1
Aim = Z bjbj+i
i=0
= Z bjbj+t + Z bjbj+t + Z bjbj+t
j=0 ij—i j=N

First consider any term bjbj+i = Ujfij+iajaj+i in I). By the definition of b and
Lemma 4.0.14

i(2j+2N+i+26— 1)
bj+ij+t+N = 5j+Nfij+t+N2jaj+t = (“1) 2 ajaj+t

 

because Ni is odd. By Property 3.2.2, we have

i(2j+i+26—1)
bj+ij+i+N = -(-1) 2 ajaj+i = -fljflj+tajaj+t = —bjbj+i:

 

36

Thus bjbj+i is canceled by bj+ij+i+N from IT. That is, II + Ir = O. For any

item bjbj+i = fijflj+iajaj+i—N in Im with i+j 74 N, we have 0 <j < N and
i+j > N. From Lemma 4.0.14
b2N—jb2N—j—i = 52N—jB2N—j—iaN—j0‘2N—j—i

i(2j+i—26+1)
= (‘1) 2 aj“j+z‘—N

 

i(2j+i+26—1)
= —(—1) 2 aj%‘+z'—N

 

= ‘fijfij+z‘0j0‘j+z‘—N = —bjbj+z'-

The second equality follows from the property that a is symmetric or antisymmetric.

Therefore when i+ j # N, the item bjbj+i is canceled by b2N—jb2N—j—i' When

i+j = N, b2N—jb2N—j—i 6 Ir, so only bN—ibN remains in Im. Horn Lemma
4.0.14

i(2N—i+26—1)
bN—ibN = fiN—ifiNaN—z‘ao = (-1) 2 O‘N—z'O‘O

 

N+6+i 1 6+i—1
= (-1) $_aoaN—i = (-1) TaoaN—i-

This proves the first part of Lemma 4.0.16. Now we prove the second part.

For i _>_ N, if j > 0 then by Lemma 4.0.14, 0 is symmetric or antisymmetric, and

i being odd,

37

i(2j+i+26—1)
bjbj+i = fijfij+iajaj+i—N = (-1) 2 aN—ja2N—j—z'

 

i(2j+z'—26+Q
= -(-1) 2 aN—ja2N—j—i

 

i(2j+i—26+1-4N)
— -(-1) 2 aN—ja2N—j—z‘

 

= —fl2N—jfi2N—j—z‘aN—j02N—j—i = _bZN—ijN—j—i'

Therefore every term bjbj+i is canceled by b2 N— j b2 N— j—i except for the term

(“5“)
b0 by; = 30 52' a0 ai—N = (-1) “Oat—N

(-1)2 Z Tao ai—N = (-1) TaOQi—N’

where the last equality holds because i is odd. This proves the second part of Lemma

4.0.16. Cl

Lemma 4.0.17. For an odd N, suppose a = (a0,a1,....aN_1) is a symmetric
or antisymmetric binary sequence of length N. Let b = {a ; a} * E be one of the

sequences of Lemma 4.0.16. Then

2N—1 N—l N-l N—l
Z A§(k)=N+ Z Ag(k)+2 Z Pa(k)Aa(k)+ Z Pa(k)2.
evenk even/c

38

Proof. From Lemma 4.0.15 and Lemma 4.0.16, we have

2N—12N—12N—1 2k
2 A,2(k)= k: A,2( (k)+ :1 Ab(
oddk evenlk
2N—1 2N— 1
= 2A 2(k)+ :11 A,2( (k)+ Z A,2(k)
k=1=N+1
odd It even 1k even k
N—l 2N—1
=N+ Z [Pa(k)+Aa(k)l2+ Z A3(k-N)
k=1 k=N+1
evenk evenk
N—l 2N—1 N—l
=N+ Z A2(k )+ Z: A2(k —N)+2 Z Pa(k)Aa(k)
k=1 k=N+1 k=1
even k even k even k
N—l 2
+ Z Pave)
k=1
evenk
N—l N—l N—l
=N+ Z A2,(k)+2 Z Pa(k)Aa(k)+ Z 193(k) El
k=1 19:1 1921
evenk evenk

Remark. From Lemma 4.0.17, we can see that if we have a family of binary sequences

a of length N that at each N, (1 satisfies the following:
o a is symmetric or antisymmetric.

o ZA: 11P2(k) is smaller than than N 2

39

Then for each N, we can construct an even length binary sequence b of length 2N,
so that the asymptotic merit factor of b is four times of the asymptotic merit factor
of family of 0. There is no rotation in the new families of sequences. In the following
chapters, we will construct new families of 0: which satisfy the two features above.
Then we can obtain sequences of even length binary sequences of high asymptotic

merit factor 6.0.

40

Chapter 5

Sequences of Length 2p with

Asymptotic Merit Factor 6.0

5.1 The Asymptotic Merit Factor of Doubled Leg-
endre Sequences

In expression (2.3), it was shown that if F is the asymptotic merit factor of cyclically
shifted Legendre sequences corresponding to the offset fraction f (the number of

positions shifted divided by the length), then
1/F = 2/3 — 4m + 8f2, Ifl s 1/2. (5.1)

In particular for the Legendre sequences a of length p with no shifting (f = 0) we
have

2
Lemma 5.1.1. lim 1) = g.

2"” 2 2i: Age)

 

Now we are ready to prove the main theorem of this chapter.

41

Theorem 5.1.2. For each odd prime number p, let a = up be the Legendre sequence
of length p given in (2.1), and let fl = [31; be one of the binary sequences of length
2p from Definition 3.1.5. For each p, we further let b = bp be the length 2p sequence

{a ; a} * fl. Then the asymptotic merit factor limp—>00 (Fbp) is 6.

Proof. By Proposition 3.1.2, the Legendre sequence a is symmetric for p E 1 (mod 4)

and antisymmetric for p E 3 (mod 4). Therefore by Lemma 4.0.17 we have

2p—1p—1 p—l p—1
Z: A2(k) =p+ZA3(k)+2 Z ckAa(k)+ Z ck2,
evenk evenk

where Ck = Pa(k) = :l:1 or -—3 from Proposition 3.2.6.

AS lckl S 3,

p—l
2 (2,2 = 0(1)).

even k

By Lemma 5.1.1, 21):; A2 O,(k) = 0(p2); so by the Cauchy—Schwarz inequality

 

 

 

 

 

 

P—1 P—1 3
Z ckAao) _<. 2 A30» 0(p>s\/o<p3)=0<p2).
k=1k \ k=1k

We combine these results with Lemma 5.1.1 to find

1 1. 2(221‘1 Age k»

1m
p-—>oo Fbp p—roo (2:02

 

1 -1
_ hm ”+22; A2<k>+zzelt 1._ lakAa<k>+25m=1cfi>
12"“ (2p)2

 

42

even [:21

 

-1 2 p-1 p
P 22:1 A002) _,_ 2 Z CkAa(k) _,_ Zeven kzl ck

 

 

 

 

= +
p—>oo 2P2 2P2 21,2 21,2
-1
__, l 2ZhflAQM ~1x2—3
_ p—>OO 4 p2 — 4 3 -— 6 2
That is, limP—aoo Fbp = 6. D

Here we present some numerical experimentation inspired by similar results in

[27].

 

PT I I T

 

 

 

 

 

 

 

6'2 H I] l V '11,”! '1
6~ l '; Ezl-' “llrll ‘ _
l l ' 2 ’
'5 z 1%
'3 515~ 1‘ .
LL
'5
:2
5» -
115L .
6 7 8 9 1o 11 12 13 14

L092P

Figure 5.1: Merit factor for Parker’s sequences with appending ratio 0.065.

For the sequence b of Theorem 5.1.2, we write (—b)f for the sequence (-b0, —b1, . . . ,

—b[fpj _1) obtained by truncating —b to the fraction f of its length. Computer cal-

43

culation then indicated that

lim supF Z 6.20

pa... {b:(-b)f}
for 0.06 _<_ f S 0.07. Figure 5.1 shows the merit factor asymptote of {b ; (—b)f }
when f = 0.065.

Jedwab [22] reports that Parker has done similar calculations.

5.2 The Asymptotic Merit Factor of Parker’s Se-
quences

In [28] Parker gave a construction for sequences of length N = 2p, with p prime,
which motivated the present investigations. We restate his results here. Let Do be
the set of squares in GF(p)\0, and let D1 be the set of nonsquares. First, Parker
constructed a sequence of length 4p by specifying a subset C of ZZN’ then defined

the characteristic sequence s’(i) of C:

1, ifiEC
0, 111910

s'(i) =

LetC’:{{n}xcn|cng2;,ogn<r},F={Gxo|G_c_Zr},andC=C’UF.

Then Parker gave the concrete description of C as follows:
If prime p = 4f +1,

then let CO = D0, C1: D0, C2 = D1, C3 2 D1, G = {1,2}.
If primep = 4f + 3,

then let CO = D0, CI = D0, C2 = D1, C3 2 D1, G = {0,1}.

44

Under this construction, the characteristic sequence 3’ (i) of C = C" U F is of the
form s’(i) = s(i), for 0 _<_ i < N, and s’(i) = s(i -- N) + 1, for N S i < 2N, where
s(i) is a {0, 1}-sequence of length N. We convert s(i) into :tl binary form by putting
bi=(—1)S(2), 0 g i g N — 1. (5.2)

Parker did computer calculations indicating that the aymptotic merit factor of
the sequences b given by (5.2) is 6.0. We will show that Parker’s sequence (5.2) is
almost identical to the length 2p sequence b of Theorem 5.1.2 coming from the choice

3 = _g(0).

By the Chinese Remainder Theorem there exist n and m so that
n E 1 (mod 4), n _=_ 0 (mod p); m E 0 (mod 4), and m E 1 (mod p)

Specifically, whenp= 4f+1, n =p, m: 3p+1; whenp= 4f+3, n = 3p, m =p+1.

Thus the construction of C = C, U F as above becomes

(0,C0) = {mDO} _=_ 0 (mod 4

7

(1,01) = {n+mD0} 51 (mod 4

).
l,
(2,02) = {2n+mD1} E 2 (mod 4);
(3,03) = {3n+mD1} E 3 (mod 4).

Now let j E (0, 2p) with j 72 p:

1. Suppose j E 0 (mod 4). Ifj = mfi for some 5 6 D0, thenj 6 (0,00) and
bj = (—1)5(j) = —-1. At the same time, B 6 D0 implies that afl = 1. Therefore
bj = (—1)5(j) = —a3 sincej E fl (mod p). Ifj ¢ mfi for any fl 6 D0, then

s(j) = 0 and so bj = (—1)S(j) = 1 = —a- That is, ifj E 0 (mod 4) then

J.
j=—%-
Similarly, ifj E 1 (mod 4) then bj = —aj .

45

2. Supposej E 2 (mod 4). Ifj = 2n + ml? for some fl 6 DI, thenj E (2,02)
and bj = (—1)S(-l) = -1. At the same time, 3 ¢ DO implies that 05 = —1.
Therefore bj = afl since j E H (mod p). If j 75 2n + mfi for any fl E D1,
then s(j) = O and so bi = (—1)3(j) = 1 = aj. That is, ifj E 2 (mod 4) then
bj = aj.

Similarly, if j E 3 (mod 4) then bj = ozj .

Finally, when p = 4f + 1, we have F = {p, 2p} under Parker’s construction, so
3(0) = 0 and b0 = (—1)3(0) = 1. Then s(p) = 1 gives bp = (-1)S(P) = —1. When
p = 4f + 3, we have F = {0, 3p} under Parker’s construction, so s(O) = 1 and
b0 = (——1)3(0) = —1. Now s(p) = 0 gives bp = (_1)s(p) = 1. Therefore under
Parker’s construction the sequence b has the following form:

—a,-, ifiEOOrl (mod4),i7$0;

-1
be = (4)2210, 1,: (5.3)
01,-, ifi‘2-20’r3 (mod4).

Comparing (5.3) with the —[3(0) form of b in Theorem 5.1.2, we realize that the
two sequences are exactly the same when p = 4f + 3. When p = 4f + 1 they are
identical in every position except the first; Parker’s sequence begins with 010, while
—fi(0) sequence from Theorem 5.1.2 starts with —a0. From Property 3.2.12, we know
that a change in one position of each sequence will not influence the aymptotic merit

factor of a family (for instance. Therefore Parker’s sequences have asymptotic merit

factor 6 by Theorem 5.1.2.

46

Chapter 6

Sequences of Length 2pq with

Asymptotic Merit Factor 6.0

This chapter is divided into three sections. In the first section, we will prove that for
a character sequence X N with N 2 pg, we have freedom to put any new values at
those position i’s with (i, N) > 1 while the asymptotic merit factor of the new family
of sequences still has the same form as in Theorem 2.3. In the second section, we
will apply the doubling technique introduced in chapter 4 to the Jacobi and Modified
Jacobi Sequences of length N = pq. In the third section, we will apply the doubling
technique introduced in chapter 4 on some newly constructed sequences of length
N = pq, so that we will obtain several families of binary sequences of length N = 2pq
with high asymptotic merit factor 6.0. In both sections 6.2 and 6.3, the new families

of sequences are free of cyclic shifting.

Throughout this chapter, we simplify {if as

. 27r'.
€j=€§v=€7vzz

47

6.1 Theorem 6.1.1 and Proof

From the discussion in section 2.1 , we have seen that Legendre sequences, Jacobi or
modified Jacobi sequences are modifications of character sequences by putting new
values at positions 2', with (i, N) > 1. When N = pq, the number of those positions
is greater than \/N. In view of Property 3.2.12, people have been hesitant to change
the values at those positions. However, we show in the following theorem that we are

free to put any new values at those position i’s with (i, N) > 1.

Theorem 6.1.1. Let N = pq, where p < q are distinct odd primes. Then for each

N, let the binary sequences uN = (u0,u1, . . . , uN_1) satisfy

1' , i i,N = 1 ;
:l:1, otherwise .

where the sequence x N is as defined in expression ( 2. 7) Now construct any infinite

sequence of such sequences
11 = {uN1,uN2,...,uNi,...},

where Ni = pig,- for p,- < q, distinct odd primes. Then 21 has the same asymptotic

merit factor value F form as the character sequence x, given by

1 2 2
_ E _ — 4 < 2
F 3 |f|+8f, 111-1/ .
whenever
N6
T?"— —> 0 when N,- —-> 00, (6.2)
i

where f is the fraction of shifting and e is any positive number satisfying 0 < e < 13'-

Given a sequence a: = ($0,271,...,113N_1) of length N, we have the Discrete

48

Fourier Transform (DFT) of the sequence, that is,

N—l
x[gj] = Z xkék, j = 0,1,...,N— 1, (6.3)
k=0

s1
where {j = e .

Furthermore, for 0 _<_ t < N, let :ct = (xt,a:t+1,...,:1:N_1,:1:0,:131,...,a:t_1)be
the offset :1: sequence arising from t cyclic left shifts of sequence 1:. The Discrete

Fourier Transform (DFT) of set is then
N—l k
ast[£j]= 2.1-Hts, j=0,1,...,N—1, (6.4)
k=0

where all the subscripts are taken modulo N.

Property 6.1.2. Let :1: = (x0, :I:1, . . . ,xN_1) be a real-valued sequence of length N,

se-
5,- = e . For :c[§j] the DFT ofx as defined above,

N—l
Z 1211,12 = Nllzvll2,
1:0

where ”:13”2 = git—612%.

Proof. There is a well-known trigonometric identity

N-‘1 2 k'. - -.
Z ell-N12: N) lle]: (65)

k=0 0, otherwise

Then

49

 

 

 

j: —0 m=0
N— 1N—1 N—l ”(k—m)“.
=2 Zxkmee

k: 0m=0

N—l
= Z xk2-N=N 1x112
k=0

m=k

Property 6.1.3. Suppose we have sequences a = (a0,a1,.. .,,am_1) and b =

(b0,b1,..bn__1) with (m, n)— — 1. Let N: mn and consider 21:10 aJ-bj, where

the subscripts are taken modulo m and n respectively. Then

N—l m—1 n—1
Z “ij =(Z ”all: 58),

Proof.

N —1 m— 1n—1 m—l n—l

Z ajbj: Z Z ak‘n-l-Sbs = 2:125 Z: akn+s= (Z ak) ' (2 b8)
where the last equality follows from the fact that (m, n) = 1. C]

Proof of Theorem 6.1.1

50

N N

For each N, write 11 , where the sequence X N is the character sequence

= X N + v
of (2.7) and uN is as defined in (6.1). In the following proof, in order to simplify

N

the notation, we write u, x and v instead of u , x N and vN. Then for each N,

0 S t < N, put ut = xt +vt, where ut = ( ut,ut+1,...,uN__1,u0,u1,...,ut_1)
and similarly for xt and vt.
a:
For 53' = e , where 0 S j g N — 1, for a fixed t, from the Discrete Fourier

Transform as shown in (6.4),
#11,] = 211,-} + #11,} = 211,-] + a, . (6.6)

utl-fijl = th_€jl + Utl—Ejl = th‘Ejl + b' 1 (5-7)
where aj = vt[€j] and bj = vt[—§j].

Let FtN be the merit factor of Xt- Then by Theorem 1.2 of [25] (page 35), when

condition (6.2) is satisfied,

N—
1 1 t 4 t 4 2 2
Nil-POO— FN ”Al-131002 N3 §1(IX [5]“ +lX l 6]“ ) 3 lfl+8f ,
where f = [72'] is the offset fraction.

Let FtN be the merit factor of ut. Then from ([24], (5.4) page 624),

N—
1 _ 1 t , 4 t . 4
ENE—‘3 3:010” [€le +|u [‘5le )—1
Put l/FtN — l/FtN = G/2N3. Our goal is to prove that the limit of FtN takes

exactly the same form as FtN . In other words,

1 2
=§-4lfl+8f2,

lim
N——+OO FtN

51

provided condition (6.2) is satisfied, where f = [7%] is the offset fraction. So it
suffices to prove that

G/2N3—>O asN-eoo.

Again, using the form ([24], (5.10), page 624),

N—l
IGIS Z [laj|4+6lxt[€jl|2-laj|2+4(Ixtléjl|2+|aj|2)-laj|-|Xt[€jl|] (6.8)
j=0
N-l
+ Z [ijl4 + 6|xtl-éjllz - :bjlz + 4< Meg-1|? + 1b,? ) - ijl - Ixtl-éjll] .
j=O

Now we look at the values of aj and bj, where 0 S j S N — 1.

P—1 27rmz' . (1‘1 27rk2' .
_ z z
aj = vt[§j] = g]. t E vmqe p + E vkpe q ,
m=0 k=1

P—l 27rm2'. 9—1 27rkz'z.

_ z
bj = vt[—§j] = {j t Z v§nqe p + I; vzpe q , (6.9)

where vqukpa’Ufnqa'ULp 6 {+1, —1}, for 1 S m < q, 1 S k < p. Denote

) . .
' P—l 27rm2. .. (1‘1 27rk2. .
_ z _ z
gjt Z vmqe P = Ivél, g]. t Sigma 0 = lvél;
m=0 k=1
tip-1 I 7rm z tq-l I 27mg, .
6] Z '0qu p = 1339': Ej Z vkpe q — IWII
m=0 k=1
For any j,
27rm(j+p )2. 27rm 2'2. 2771904412 z' 27Tk.2 z
e P = e P and 6 q = 6 q ,

so we have for any j,

. .+ N. .;+
IU£|=IU£ pl, Ivfil=lvz72 pl; (610)

lug: = Iv5+qL 15%,): W91.

From Property 6.1.2, we have

p-l . p-l .
Zia/1%? = Z 16;)? =p2, (6.11)
9': j:
and
q-1 . q-l .
2 122512 = 2 Ivan? = q(q— 1). (6.12)
j=0 j=0

Now we estimate the sum within the first bracket in expression (7.41). Note that

Iajl _<_ |u{,| + lvgl, lbj| g (27%| + r173]. Then for 1 g s g 4,

N41 .N—l . . s.N—1 s\ . .

Z lajlss Z (Iv{;|+|v?;|)3= 2: ~ Iviglm-lvéls‘m,
j=o j=0 7n=0j=0 1%)

N—1 N—l _ , s N—l s , ,

Z ij|8 S 2 (l5{9|+|55|)3= Z |'gg,|m.|5{1|S-m,
i=0 j=0 m=0 j=0 m

The following calculations are the upper estimates to the values of
s N —1 , .
2: : lam-1W
m=0 j=0

for 1 S s S 4. Suppose r is either p or q. Applying the result from (6.10), (6.11) and

53

(6.12), we have

 

N—l ,2 N r—1 [:2

Iv¥~l =7-Zlvrl gm; (6.13)
j=0 k=0
N—l

' N

Iv¥~I4=7£Ivrl4 s-r-w (:2:le _<..Nr3
i=0
N—l r—l r—l

' N N

Iv¥~I=-;- was? ZIvW-rswi.

Note that (r, N / r) = 1. By Property 6.1.3 we have

 

 

IV—l , , ,r—l AUr—l
EE:h#l'Wfivrt= [§E:h¢l]- §::IvE@A (6L0
3:0 1:20 m=0
r—l N/"‘ 1 3
s ZIvW-rx Z lvN/TIZ 50/2.
— m=0

Furthermore, since (r,N/r) = 1, from (6.10), Property 6.1.3 and the estimate

shown in (6.13) and (6.14), we obtain

N— 1

3 N r—l k3 N r—l k2 'r—l k\ 5
Iviél =7 lvrl 37- Zlvrl - ZIvTIJSNfl; (6.15)

54

N/r—l

Zlilev¥|21M/l=(2|vfl2)- Z lugs/TI srvm.
k=0

Combine all the results above, noting that we assume p < q. Then when p and q

are large enough, we have

N— . . . . . . . .
= Z (|v§l4+lv§|4+4lv%|3-Iv§|+4lv£|-lv5|3+6lv%I2-lvél2)
j=0

3
g Np3 + Nq3 + 4N2(1o2 + q2) + 6N2 < 10Nq3. (6.16)

Similarly, under the same conditions for p and q, we get

. . 5

Z IajI3 s (Ivfil + Ivgl )3 < 3ng ; (6.17)
i=0 i=0
N—1 2 N—l , , 2

IajI s (Iv;I+Iv;I> <4Nq;
3:0 i=0
N-l N—l

laJ|< ZIIv£I+Iva><2NqE
J=0 i=0

In the calculation above, if we replace 11'}, with i713), and 215 with '63, then for
0 S m S s S 4, the upper bounds for Zj'i—ol |v139|m- Inglis-m as in (6.13) and (6.15)
are also the upper bounds for EN -1 [film - l'z‘z'jIS—m. As a result, the upper bounds
for ZN; Olal jls are also upper bounds for 2N: Ollbj -,|3 for each 1 < s < 4. By
Theorem 03.2.7,

Ixtléjll = IgthIngI = lxwléjll s «N. (6.18)

55

Using the interpolation formula ([23], (2.5), page 162)

xtl— «31:1,, 2153—— +€jx xtlékl,

and the inequality (for instance, [24], page 625),

N—l
5k

€k+€j

 

SNlogN,

 

 

k=0

combined with the result in (6.18), we have

lth‘Ejll S 2\/—N-logN, for 0 S j g N — 1. (6.19)

Combining the results from (6.18) and (6.19), we can write
IxtHzfj“ s 2\/Nlog N, for 0 g j g N — 1. (6.20)
Now we give an upper bound to the two brackets of form (7.41) simultaneously.

We use symbol cj to represent either aj or bj. Using (6.16), (6.17) and (6.20), we

have that there exists a positive constant C independent of N, such that

N—l

Z chI4 < CNq3;

J=0

N—l N—1

Z 6|xt( igj)|2 - ch|2 S 24Nlog2N- Z ICjI2 < CN2qlog2N;
J'= —0 J'=0

N— 1 3 N—l 5 1

Z 4|Xt( (151-) )13 ch |<32N210g3 N Z chl <CN2q21og3N;
J=0 J=0

56

N—l
Z 4|Xt(i§j)| - Icy-I3 g 8x/NlogN. (:1 |c J13) < CNEqZIOgN.
.=0

Thus the sum in the two brackets of form (7.41)
2 I I I4 +6|x (iaJ>I2 Ic JI-2 +4< IX (isJI2 +IcJ I2 > lc J--I Ix (igJ-M I ~ o<N2)

provided the condition (6.2) is satisfied. This finishes the proof of Theorem 6.1.1. [:1

6.2 The Doubling of Known Sequences

Suppose the binary sequence 2 of length N = pq is a Jacobi sequence as defined in
expression (2.2). The correponding modified Jacobi sequence of length N = pq is
given by
+1, j=0,q,2q,...,(p—1)q;
mj == —-—1, j: p, 2;), 3p, . . . , (q —1)p; (6.21)
[It] , gcd(J.N)=1.
As defined in Section 2.1, the asymptotic merit factor F of Jacobi or modified

Jacobi sequences of length N = pq offset by the factor f is
1/F= 2/3—4|f| +8f2, |f| :1/2, (6.22)

provided p and q satisfy

(19 + (1)510g4 N

N3 —+ 0, for N —> oo. (6.23)

 

Particularly, for the sequence a (equal to the Jacobi sequence 2 or a modified

Jacobi sequence m) with no shifting (f = 0):

57

 

Lemma 6.2.1. Under condition (6.23), we have Nlim

It is important to realize that under (6.23) both p and q go to infinity as N goes

to infinity.

Theorem 6.2.2. For each pair p and q of distinct primes with p E q E 1 (mod 4),
let a = a N be a Jacobi sequence or a modified Jacobi sequence of length N = pq; and
let ,8 = ,8 N be one of the binary sequences of length 2N from Definition 3.1.5. For
each such N, we further let b = b N be the length 2N sequence {a ; a} * fl. Then the

asymptotic merit factor lim F is 6 for N = pq subject to 6. 23 .
N —>OO b N

Proof. It was shown in [24] that a Jacobi or modified Jacobi sequence of length

N = pq is symmetric when p E q E 1 (mod 4). By Lemma 4.0.17 we thus have

2N—1 N—l N—1 N-l
Z A§(k)=N+ Z A2,(k)+2 Z Pa(k)Aa(k)+ Z Pa(k)2.
evenk evenk

We may assume throughout that q > p.

For oz a Jacobi sequence, the periodic correlation function Pa(k) has the following

distribution [24, Theorem 4.2]:

Pa (k) 2p occurs (q — 1) / 2 times;
— 3p occurs (q — 1) / 2 times;
q occurs (p — 1)/2 times;
-— 3q occurs (p — 1)/2 times;
1 occurs (p — 1)(q — 1)/4 times;

58

170(k): — 3 occurs (p —1)(q —1)/2 times;

9 occurs (p -1)(q — 1)/4 times.

Therefore
N — 1
Z H.002 =0(pq2>.
k=1
even/c
By Lemma 6.2.1, when p and q satisfy (6.23) we have 25:31 213(k) = 0(N2).

Therefore by the Cauchy-Schwarz inequality

 

 

 

 

 

 

N—l N-l

Z Pa(k)Aa(k) S Z 43.09) 0 ( pq2 ) S 1(0 (p3q4 ) = 0 (19qu)
k=1 k=1
evenk \ _evenk _

Combining these results with Lemma 6.2.1, we calculate (as in Theorem 5.1.2)

that, for p and q subject to (6.23), the asymptotic merit factor is

 

 

2
lim (Fb)= lim ”(351) 2
N...» Newman:1 Awe»
— lim 4N2
N ~00 2 25: A2100
3
=4 -2
x2 6

Similarly for 0: a modified Jacobi sequence, the periodic correlation function 190(k)

has the following distribution [31, p. 246]:

Pa(k) =q — p — 3 occurs (q — 1) times;
p-q+1 occurs (p—l) times;
1 occurs (p — 1)(q — 1)/2 times;

59

Pa(k) = — 3 occurs (p —1)(q — 1)/2 times.

Therefore 2:1\/:1PP()J(kk)2 = 0(pq) = 0(N) .

evenlk
By Lemma 6. 2. 1 when p and q satisfy (6. 23) we have Ell—:1 1 A2 a(k)= 0(N2).

Hence by the Cauchy-Schwarz inequality

 

N—l N—l 3
Z Pa(k)Aa(k) 3 Z A2,(k) O(N)S 0(N3)=0(N2).
k 1

ev; k \ [eve—h k -

 

 

 

 

 

We again combine all the results above with Lemma 6.2.1 and find that, when p

and q satisfy (6.23), the asymptotic merit factor is

2
lim F = lim 2182A?
N——>oo N—+002(Zk=1A2b(k))

 

 

= lim 4N2
N2<><>2(2*"’__:1 12(1))

60

6.3 The Construction of New Sequences and Dou-
bling

Throughout this section, we define the triple-valued sequence V of length N to be

(6.24)

From Property 3.2.3, the sequence V is symmetric when N E 1 (mod 4) and
antisymmetric when N E 3 (mod 4). Our goal is to construct specific families of
binary sequences based on the triple-valued sequence V. These new sequences have
the same symmetric type as the sequence V, depending upon the values of N modulo

4.

Definition 6.3.1. Suppose N = pq, where p and q are distinct odd primes. Let the
sequence V of length N be as defined in (6.24). Then we define the binary sequences
2:, y and z of length N with

$j=yj=Zj= j, f0Tj=0 and (j,N)=l.

Otherwise, for {r, d} = {p, q} and 1 S k S r — 1, put

(—1)kr ,z‘st 3 (mod 4);

27kd= j; J
(—1)7‘ ,ZfNE 1 (mod4).

ykd =
xd(-1) -x.~<k> , if k > 23—1.

2M = (Xd(—1))k ~xT(k)-

61

To better understand the definitions of sequences at, y, and 2, we will study a

concrete example.

Example 1. Suppose N = 3 x 5 = 15, the sequence V of length 15 is as defined
in expression (6.24), and the Jacobi sequence J of length 15 is as shown in Table 1.

Then we have

position j 0 1 2 3 4 5 6 7

V]- +1 +1 +1 0 +1 0 0 —1
Jj +1 +1 +1 +1 +1 +1 —1 —1
T
X5(1) X5(2)

position j 8 9 10 11 12 13 14

V,- +1 0 0 —1 0 —1 —1
Jj +1 —1 —1 —1 +1 —1 —1
T T
X5(3) X5(4)

Here V is antisymmetric because 15 E 3 (mod 4). But the Jacobi sequence J is
neither symmetric nor antisymmetric; indeed, the positions 0, 3, 6, 9, and 12 give a
subsequence (1, x5(1), x5(2), x5(3), x5(4)) which is symmetric since 5 E 1 (mod 4).

Definition 6.3.1 gives new values on positions j, with (j, 15) > 1:

J 3 5 6

J3 X5(1) =1 X3(1) =1 X59) = -1
x,- (4)13 = —1 (—1)E = _1 (—1)—5 = —1
yj X5(1) = 1 X3(1) = x5(2) = —1

Note that in Example 1, 11:, y and 2 only differ at positions j, where (j, N) > 1,
and all are antisymmetric, as is V. This is a concrete example of the following general

result.

62

j 9 10 12

Jj X5(3) = -1 X3(2) = -1 X5(4) = 1
x,- (-1)§§=1 (_1)E=1 (4)35: 1
yj -X5(3) = 1 X3(2) = -1 -X5(4) = —1

z, (—1)3X5(3)=1 X3(2)=—1 (—1)4X5(4)=1

Lemma 6.3.2. Suppose N = pq, where p and q are distinct odd primes. Let the three
binary sequences 1:, y and z of length N be as defined in Definition 6.3.1. Then as, y

and z are symmetric if N E 1( mod 4), and antisymmetric if N E 3( mod 4).

Proof. To shorten the proof, we use the notation uj to represent one of xj, yj, or zj.

If (j, N) = 1, uj = Vj, thus by Lemma 3.2.3, we have

uj =“N—j’ ifN E 1 (mod 4) ;

uj = _“N—j’ ifN E 3 (mod 4) .

We wish to prove this for all j ’s with 1 S j S N -— 1.

m—l
By Lemma 3.2.3, for m E {p, q, N}, we have Xm(—1) = (—1) 2 . In particular,

the two equalities above are equivalent to the single equality
uj 'uN—j = XN(—1).

Let {r, d} = {p, q}, so that N = rd and N — kd = (r—k) -d. Therefore to complete

the proof of the lemma, it is enough to verify

de ' u(r—k)d = XN(_1)'

for all 1 S k S T—E—l We do this in cases.

63

First,

ykd ' y(r—k)d = Xr(k)'Xd(—1)'Xr(7‘ “- k)
= Xd(—1)-Xr(k)-Xr(-k)

= xd(-1)-><r(—1)-(><r(k))2 = xN<—1>.

Next,

zkd . 20.4,” = (xd(—-1))’° Mk) - (>cd(—--1))"—’c - w — k)
= (xd(—1))" was) -Xr(-k)

= Xd(—1)'Xr(—1)'(Xr(k))2 = xN(—1),

since when r is odd, (Xd(—1))T = Xd(—1).

Finally, if N E 1 (mod 4),

N

~

In - Stu—km = H)“ - cut—k)?

while if N E 3 (mod 4), then by Lemma 3.1.7

 

zkd - mm). = H)” - (AW-’9)?"

— (-1)E-(—1)T"E

= (*1)? = --1 = XN(-1)-

Combing all the results above, we have that x, y and z are symmetric when

N E 1( mod 4), and antisymmetric when N E 3( mod 4). In other words, 2:, y and

2 have the same symmetric type as the sequence V. E]

64

Recall that the product of sequences ”*” and sequence 5(6) are as defined in
Definition 3.1.1 and Definition 3.1.5. In [39], certain sequences b = (u,u) =1: (:tfi(6))
give rise to sequences with asymptotic merit factor 4 x F once the following are

demonstrated:
(a) u is symmetric or antisymmetric ;
(b) the sequences u have asymptotic merit factor F ;
(c) the periodic autocorrelations have 2:21:11 P3 (2') ~ 0(N2) .

Here Lemma 6.3.2 provides (a), and Theorem 6.1.1 gives (b) with F = 1.5. There
fore we will be able to prove the following theorem, once we have studied autocorrela-
tions in the next section. Based on the new constructions, we will prove the following

Theorem.

Theorem 6.3.3. For each N = quN, where pN < qN are distinct odd primes,
let uN be any one of the binary sequences 2:, y and 2 as in Definition 6.3.1. Let the
sequence fiN of length 2N be one of the four sequences $805) from the Definition
3.1.5. Let b N = {uN, uN} * 6N, be a sequence of length 2N . Then the sequence of
sequences {b N} has asymptotic merit factor 6.0 provided

N6

— —> 0 when N ——> oo , (6.25)
10N

where 6 satisfies 0 < e < 13'.

We will prove Theorem 6.3.3 in steps.

From Lemma 3.2.5 and Property 6.1.3, the periodic autocorrelations of X N are

1-p .ifplj;
PXN(j)=PXP(j)XPXq(j)= 1-q.ifq|j;

+1 , otherwise.

65

Therefore, the periodic autocorrelations of the sequence V of (6.24) satisfy

1+1? ,ifplj;
IPv(J°)|S 1+q ,ifQIJ'; (6-26)

+ 3 , otherwise .

where V is as defined in (6.24).

Property 6.3.4. For p an odd primes, let Xp be the primitive character mod p as
defined in ( 2. 6 ) Then for any 1:, we have

1
36p 210gp+1 ,ifp’fk
I Z (71)Xp(n+k)l<
0 ,ifplk

Proof. The result is obviously correct when plk. Now suppose p f It. From Lemma

3.2.5,

p—l
I Z (-1)nxp(n)Xp(n + 1€)|
n=0
131 1+1
:IZXp(2j)(Xp2j+k)- 21X p(2j—1)(Xp2j—1+k)|
i=1j1=

251 1,1

g I Z Xp(2j)Xp(2j + in +1 :3 Xp(2j‘1)Xp(2j—1+k)l
3231—1 3:1

s 2| Z Xp(2j)><p(2j + k)l +1

= 2|];1 meow—1k»! +1.

66

Weil [34] proved that the Riemann Hypothesis is true for the zeta-function of an

algebraic function field over a finite field. A specifically useful consequence is that,
for any integers u and v with u > 0,

1
| Z Xp(f(i))|39mp?10gp, (627)

u<j<u+v

where f (3:) E Fp[:z:] is a polynomial of degree m not of the form b(g(:r))2 with b E Fp,
g(:r) E Fp[a:]. (The readers can find a detailed proof for equation (6.27) in [37]

Corollary 1.) When p f k, the polynomial x(:r + 2—1k) is not the square of any

polynomial over Fp[:r], so

——1
22— 1
I Z we +2—1km 3 up? Iogp,
i=1

hence

P-1 1
n

I Z (_1) XP(n)Xp(n + kll S 36p210gp +1 ,

n=0

For the triple-valued sequence V defined in (6.24), write uj = V]- + 123*, where u

could be any one of the binary sequences 3:, y or z of length N as defined in Definition

6.3.1. For instance, for {r,d} = {p, q} and 1 S k S r - 1, when u = 11:,

(n); ,iszkd, and NE 3 (mod 4);
u}: : (_1)kr , ifj = kd, and N E 1 (mod 4);

O , otherwise;

and ifu= z,

67

k . .
—1 - k , z = kd ;
”i: (xd( )) Xr( ) fi (628)
O , otherwise.

In all three cases, we have
ZIvylSpq—(p-1)(q—1)=p+q-l<2q. (629)

as p < q. As remarked 1n the previous section, we wish to prove that 2N1 1 P2(Z )~

0(N2). The most important part of that IS the following technical lemma.

Lemma 6.3.5. Suppose N = pq, where p, q are distinct odd primes with p < q. Let

the sequence V be as defined inform (6.24), and write uj = Vj +1139, where u could be

any one of the binary sequences :5, y or z of length N as defined in Definition 6.3.1.
Then when p and q are large enough, for {r, d} = {p, q}, (we have

2, if(i.N)=1,

IPUU(i)| S

1
4r? log3(r), if(vl.N) = d.
Proof. For any 1 S i S N _ 11 Pv’u( 2'=) 2?]6110313‘44, while from the definition
vj uvj+i¢0¢>(jaN)=m1 >1, and (j+z,N):m2>1

We break the proof into cases:

Case 1 m1 75 m2, and (i, N) = 1.

Case 2 m1: m2 = (i,N) = d, with {r, d} = {p, q}.

We first note that this handles all situations in which nonzero coefficients occur.

68

Clearly if m1 = mg, then (i, N) = m1 = m2. If m1 75 m2, there must be 0 < k < r
and0<s<dwith

kdii=jiiEsr (modN),

As (1 f s we have d ’f i, and similarly r f i as d f k. Therefore m1 51$ m2 implies
(i,N) = 1.

Case 1 m1 75 m2, and (i,N) = 1.

First suppose d = m1, r = mg. Then as above there exist 0 < k < r and
O < s < d, such that

kd+i=j+iEsr (modN), (6.30)

Such a pair k and s is unique. Indeed if there exists another pair 0 < k, < r and
0 < s’ < d, such that

k’d+ 2' s s’r (mod N),

then (k —- k’)d a (s — s’)r (mod N). As le and d|(k — k’)d, we find d|(s — s’) with
O < s, s’ < d. Therefore, 3 = s’, and similarly, k = k’.

In addition, if expression (6.30) is satisfied, then kd +i E sr (mod N) implies
(d — s)r + i E (r — k)d (mod N), and this must give the unique solution pair when

r = 777.1 and d 2 m2. Therefore, when (i, N) = 1,
IP30“ S lvic‘dvé‘r + vgkdvgsrl S 2'

Case 2 m1: m2 = (i,N) = d, with {r, d} = {p, q}.

There is an s with O < s < r, and

r—l
i=1

Case 2.1(i,N)= d and u = x.

69

In 1998, W. Zhang [32] proved that for any integer t,
r—1 _ _—
Z (_1)717‘+(n+t)7" 3 fl log2r. (6.32)
n=1

r[n+t

where ii? is as in Definition 3.1.6.

More generally, for any integers t, t1 and t2 with t > 0, H. Liu proved [33]

 

| Z (—1)n_r+("+t)r|g,/Fiog3r. (6.33)

t1<n<t2
r]n,n+t

In the following proof, to simplify the notations, we use notation 3 instead of 3;.

When N E 3 (mod 4), from (6.32),

T—1 r—1 _. _
va(i) = Z vfdvfs+j)d = Z (‘1)]+S+J S W logzr,
J=1 j=1
r+j+s

When N E 1 (mod 4), suppose s S (r — 1)/2. Then from Lemma 3.1.7 and

expression (6.33),

r—1
_ a:
[PUCL' (2)] Z vjdv(8+])d

J=1

r—1_ r—1

T s _2— r—l—s r—l

= ( Z + Z + + Z )vjdv(s+])d
J=1 j=£§l—s+1 Jar—51.11 i=r-s

 

 

r-1_s r—1
2 —. —T 2 _. —'—.
=| Z (_1)]+8+J__ Z: (_1)]+s+J
j=1 j=£§l—s+l
r—l—s 7 ——+ r—1 f __7
+ Z (_1)J+S+J _ Z (_1)]+S+] l
j:T—1+1 jo—S
r—1_S r—1
3 Z (4)759 + Z (4)3617
j=1 j=£§l—s+1
r—-—1—-s -+ ——. r—l __ __
+ Z (_1)]+8+] + Z (_1)]+S+]
3.1.1.—1+1 jzr—S
34¢? log3r.

Case 2.2 (i,N) = d and u = y.

If d E 1 (mod 4), then from Lemma 3.2.5, expression (6.31) is

r—l r—l
Bur/(Z) - j_1”jd”(s+j)d — J; Xr(J)Xr(J + S) — -1-

If d E 3 (mod 4), then expression (6.31) becomes

 

 

r-l

- _ y y
[va(z)] — ; vjdv(s+])d

r—1_s r—1

2 2 r—l—s r—I
__ y y
— ( Z + Z + + )vjdv(s+j)d

3:1 y=%—s+1 j=1§l+1 FT—S

 

 

 

r—1_S r—l
T _2—
S 2 Xr(j)Xr(3+J) + Z Xr(j)Xr(3+j)
3:1 J=r—§—1-—s+1
r—1—s r—l
+ Z Xr(j)Xr(8+j) + Z Xr(i)Xr(8+J')
Fig—1+1 FT—S
3 72¢; logr,

The last inequality follows from equation (6.27) by taking the degree m = 2.
Case 2.3 (i,N) = d and u = 2:.

Equation (6.31) becomes

r—l . .
l— IZvj'TdvszJ-MI = I Ear—1))?«1(1)-(xd(—1>)(S+J>r-x.~(s+j)I,
j=1

whereOS (s+j)7~ g r— 1, and (s+j)r E s+j (mod r).
Now we study the values of (j: (Xd(—1))j+(3+3)7' From Definition 6. 3. 1, we

have
1. Cj=1,ide1 (mod 4).
2. g, = (—1)J'+(8+J')r, ifd a 3 (mod 4).

Ide1(mod4),
[ZXMD )Xr(8+j)l= 1, sincedfs.

If d E 3 (mod 4), let 31 be the number such that s +j1 < r, but 5 +j1 +1 2 r.

72

Then

r— 1
IP02 W|=l§XrU )(xrs+j)- Z Xr(J J')Xr(s+J')l
j: —1 j=j1+1
.71 r—l
:Ith(j)xh(s+J)l+I Z xt~(J)xt~(s+J)I
i=1 J=i1+1

S 36%? logr.

Again, the last inequality comes from equation (6.27) by putting the degree m =
2. [:1
Now we are ready to prove that 2N1 1 133(2 ) ~ o(N2):

Lemma 6.3.6. Suppose N = pq, where p < q are distinct odd primes. Then when

2

q S p , and both p and q are large enough, we have

N—

21193 i)<ch

where u may be any one of binary sequences x, y and z of length N as defined in

Definition 6.3.1 and c is a constant independent of N.

Proof. Again, using the notation of Lemma 6.3.5, we write u = V + v, where u may

be any one of sequences um, vy, or '02. Then by Property 3.2.13, we have

ZP3(2')=A+B+C+D+E+F (6.34)

In expression (6. 34), we have separated the summands into six groups. For instance

A=£(:—11Pv(i), and F: zfi— 11[2Pv,v(i)P,,,V(i) + P,2,U(t) + P3 Va) ]. In the
following, each of the sums X E {A, B, C, D, E, F} will be bounded above by c X -N q

for appropriate constants CX' To simplify the notation, it should be understood that

73

all of the following statements are valid when p and q are large enough.

For group A, from equation (6.26),

N—l N—1 N—l N—l
2 133(2): 2 P,2/(2)+ Z P3(t)+ 2: Pas) (6.35)
i=1 (i,N)=1 (i,N)=p (i,N)=q

39¢(N)+qx(1+p)2+px(1+q)2<3Nq.

For group B, using Lemma 6.3.5, we have

N—1
2103(2): Z P3<2>+ Z P3<2>+ 2: 133(2)
i=1 (i,N)=1 (i,N)=p (i,N)=q

g 4¢(N) + 16q210g6 q + 16p210g6p < Nq .

Also from Lemma 6.3.5,

N—l N—1
lCl = 2I Z: Pv(i)Pv(i)l s 2 Z IPV(2)P6(2)I
i=1 i=1
:2 Z [PV(i)Pv(i)l+2 Z IPV(2')Pe(2')I+2 Z IPv(z‘)P22(z')l
(i,N)=1 (i,N)=p (i,N)=q

1 1
g 12¢(N) + 9Np? log3p + 9Nq7 log3 q
1 3
< 19Nq2 log q < Nq.

74

For group D, by equations (6.26) and (6.29), the absolute value of the first item is

N—1 N—l N—l
| Z Pv(i)Pv,v(i)| = Z Pv(i) ( Z vme_z-)
i=1 i=1 m=0

N —1 N —1 N —1
s :3 IPV(2)I Z Iva <2qx Z IPv(z')|;
Similarly, we can show that any other item in group D is bounded above by
N —1
2a X Z IPv(i)|-
i=1

Again from (6.26), we have

N—l N—l N—1
IDIS8q>< 2 WW) =8q><l Z IPv(z')|+ Z IPV(2')| ]
i=1 7;: 2':

(i,N)1=1 (i,N)1>1

S 8q x [3¢(N) + 3N] < 48Nq.

Now for group E. Again, consider the absolute value of item

N—l N—l N—l
I Z P..,V(2)Pe(2>I =I Z Pe(2)( Z ”jVj+i)l

N —1 N —1 N —1
S 2 IPv(i)| Z lvjl <2q Z IPv(i)|-
Similarly any other item in group E has absolute value bounded above by

N—l
29 Z [1321(1)]
i=1

75

Thus using Lemma 6.3.5 and expression (6.29),

N—l
IEIsquIPe(2>I=8qxI Z IP66 )l+ Z IP66 )|+ Z IP66)
i=1 (i,N)=1 (72 ,N)=P (i,N)=q

3 3 3 3
3 8g x [2¢(N) + 4p? log 12 + 421? 10s q]

S 17Nq.

where the last inequality follows from the assumption that q 3 p2.

Finally, consider the first item in group F.

2
2

—1N—1 —1

I :1 PV,v (1)106 =1 Vjvj+ivme+t|
i 1 j=0m 0

—1N—1

:2

—1
vjvmVj—t'Vm+2|
0

F112;

1 j=0m

S.
ll

1N— 1 N—1

Z vjum( Z V_ij+z-)|
m=0 i= 1

N—
=(|XN 1) Z
i=0

N— 1N— 1
=|XN( -1) Z vjvav( (m+J')|
j=0 m=0

II

N— 1N—
[2: 2:11; jv—s jPV(5 5)] wheres=m+j

N—l

=| Z Pv(5)PV(5)|~
=0

CI:

Similarly, we can prove that any other item in group F has the same absolute value

76

[29:01 Pv(S)PV(8)|- SO

N——1 N—l
IFI S4| Z Pv(8)Pv(8)| S 4 X (IPv(O)PV(0)l+l Z Pv(3)Pv(S)|) -

3:0 3:1

From equation (6.29),
Pv(0)PV(O) < 2Nq ; (6.36)

From the estimate for group C, we know that

N-l 1 3
| Z Pv(s)PV(s)| < 19N6216g q < Nq; (6.37)
s=1

Now (7.27) and (7.28) imply that

IF] <12Nq.

Combining all of the inequalities above, we obtain the desired result. El

. . . . N—1 .

Lemma 7.2.7 shows that when condition (6.25) IS satisfied, 22-:1 P230) ~ 0(N2),
where u may be any one of the binary sequences :6, y and 2 as defined in Definition
6.3.1. Therefore, as remarked at the end of the previous section, we are now ready to

prove Theorem 6.3.3.
Proof of Theorem 6.3.3.

For each odd N = p Nq N with p N < q N2 Lemma 6.3.2 shows that each of the

three sequences 11:, y and z is symmetric or antisymmetric. Let

bN={uN;uN}*fi

N

where u = :c, y or 2 as defined in definition 6.3.1. In the following, without confu-

77

N

sion, we use b and u instead of b N and u . Then lemma 4.0.17 gives

2N—1 N—l N—l N-l
Z A§(k)=N+ Z A,2,(k)+2 Z Pu(k)Au(k)+ Z Pu(k)2.
evenk evenk

When condition (6.2) holds, Theorem 6.1.1 shows that

2 Z 213(k) ~ §N2. (6.38)

N—l N—1
2 223(2) 3 P302) = 0(Nq)
evenk

Then given condition (6.2), by the Cauchy-Schwarz inequality

 

N—l
z Pu(k)Au(k)
k=1

 

N-1 3 1
S [2: 142226)] 0(N9) ~ 1172612 = 0W2)-
k=1

Therefore, for p and q subject to (6.2), the asymptotic merit factor of b is

 

 

. . (2N)2
11m (Fb ) = 11m
N—>oo N N—>oo 2 2N—1A2 k
(2k:1 bN( ))
— lim 4N2
New 2 Eli-,1 246(2)
3
= 4 _ =
X 2
This finishes the proof of Theorem 6.3.3. D

78

6.3.1 Conclusion

For a character sequence of length N = pq, the number of positions j with ( j, N) > 1
is larger than x/N, so those “modified” positions are large enough to make a difference
in the merit factor. However, Theorem 6.1.1 shows that subject to condition (6.2),
any modification on these positions will give the same asymptotic merit factor values
as the character sequences. The authors were informed recently that Jedwab and
Schmidt have obtained the same result independently under an improved condition
([40]). In [39], the doubling technique shown in Lemma 4.0.17 was only applied
to some of the Jacobi or modified Jacobi sequences with additional restriction to the
values of p, q (mod 4). Here we have constructed new sequences considerably different
from the canonical Jacobi or modified Jacobi sequences and with no restrictions on
the values of p, q (mod 4), yet achieving the same asymptotic merit factor, as seen in

Theorem 6.3.3.

79

Chapter 7

Sequences of Length 2p1p2 . . . p).

with Asymptotic Merit Factor 6.0

In this chapter, we will give a new modification to the character sequences X N) where
N = p1p2 . . . pr, for pi’s distinct odd primes and r 2 2. In Section 7.1, we will give
the definition of the new families of binary sequences 2. In Section 7 .2, we will give
an estimate to the periodic autocorrelations of 2. And in Section 7.3, we will prove
the asymptotic merit factor of 2 satisfies formula (5.1), and we will construct a family

of binary sequences of length 2p1p2 . . .pr with asymptotic merit factor 6.0.

7 .1 Construction

Definition 7.1.1. Let N = p1p2 . . . pr, where p,- ’s are distinct odd primes and r 2 2,
forlngN—I, define

(xd(-1))k°xN/d(k) . if (2.N)=2>1 2222:1222;

O , otherwise.

’Uj = (7.1)

80

and
1 .2”fJ'=0;
22= 22,- .if (.23N)>1; (7-2)

V7 , otherwise

where V is character sequences defined in expression (6.24).

To see the definition of sequence z more clearly, let’s consider a concrete example.
Suppose N = 3 x 5 = 15, so p = 3 E 3( mod 4), q = 5 E 1( mod 4). Let V denote

the character sequence as in (6.24), then

V={0,+1,+1, 0,+1,0,0,—1,+1,0,0,—1,0,—1,—1}

z = {+1, +1, +1, -1,+1, +1,-1,—1,+1,+1,-1,—1, +1,—1,—1}

Note that in the above example, we put in italic type those entries at j-th positions
where (j, N) > 1.

It is obvious that when r = 2, the sequence defined in Definition 7.1.1 is exactly the
same sequence 2 as in Definition 6.3.1. Therefore Definition 7.1.1 is a generalization
of Definition 6.3.1 for length N = pq. Then similar to Lemma 6.3.2, we will prove that
the sequence 2 defined in Definition 7.1.1, is symmetric or antisymmetric depending

on N.

Lemma 7.1.2. Suppose N = p1p2 . . . pr, where p,- ’s are distinct odd primes, and the
binary sequence 2 of length N is as defined in Definition 7.1.1. Then 2 is symmetric

if N E 1 (mod 4), and z is antisymmetric if N E 3 (mod 4).

Proof. If (j, N) = 1, zj = uj, thus from Property 3.2.3,

zj = ZN—jr if N E 1 (mod 4) and 23- = "ZN—j) if N E 3 (mod 4)

Now suppose (j, N) = d > 1, and j = kd with 1 S k < N/d. For the similar reason

81

stated in the proof of Lemma 6.3.2, it is enough to prove that

zkd ' zN—kd = XN(—1)-

th - 26-2).) = (Xd(—1))k - 222(k) - (xd(—1))’"—k - m — t)
= (Xd(-1))r - Xr(k) -Xr(-k)

= xd(-1) -xt~(—-1)o(xt~(k))2 = xN(—1),

since when r is odd, (xd(—1))7' = xd(—1). El

The main theorem of this chapter is as follows:

Theorem 7.1.3. For any positive integer r 2 2, suppose N = p1p2...p1-, where
p1 < p2 < ...p2r are distinct odd primes. Then for each N, let zN be the binary
sequence defined in Definition 7.1.1. Now construct any infinite sequence of such

sequences

,0 I .

z={zN1,zN2,...,zNi },

with increasing lengths N1 < N2 < < Ni <

(1) Let F be the asymptotic merit factor of 2, f be the ofiset fraction. Then we have

1/F = 2/3 — 4m + 822, |f| 31/2. 222222

N6
— -—> 00 for any 6 small enough as N —2 00. (7.3)
pl

{2) Let the sequence 6 of length 2N be one of the four sequences ifiwl from the
Definition 3.1.5. The new sequence b = {z ; z} * 6 of length 2N has asymptotic merit
factor 6.0 given {7.3) is satisfied.

We will prove Theorem 7.1.3 in steps. First of all, we will estimate the periodic

82

autocorrelations of sequence 2 in the following section.

7 .2 Periodic Autocorrelations of Sequences z

First, we review some simple properties from number theory.

Lemma 7.2.1. Let y1 = ( yé ,... ,y11V1_1 ), y2 =(yg,...,y12V2_1),..., yr 2
( y6 , . .. ’ylVr—l ) be r sequences (not necessarily binary) of length N1,N2, . . . Nr

respectively, such that (NiaNj) = 1for any 1 S i < j S r. LetN = N1 XN2 - - -er,

define a new sequence u = y1 <8) 312 (8) . . . yr of length N via

j 371712 j N—1 '16
Furthermore, let EN = e , let u[€N] = 2,620 uk({‘17v) be the DFT ofu as defined

in {3.1). Then there exist integers 31,32, . . . ,sr with (32-, Ni) = 1 for 1 S i S r, and

, r .
22 I21.) = H 2h 45;)
i=1
Proof. We will prove the two results simultaneously by the induction on r. When
r = 1, the result is trivial. Now suppose Lemma 7.2.1 holds for r = k — 1, where
k 2 2. Then for r = k, suppose y1,y2, . . . yk_1,yk is a series of sequences, where
for each i, sequence yi has length Ni) and (Ni) Nj) = 1 for any 1 S i < j S It. Now
denote N’ = N1 x N2~~ x Nk_1,u1= y1 @312 ®...yk'—1, then u = 111 @311“. By

83

induction,

21.6) = along/2(2)
. . I '8
2216(2) =21I2§§A 2323;)

where (s', N’) = 1 and (sk, Nk) = 1. Then by induction

76
1311(7): Pul(.7) Pyk(.7) =P1—Iy

i=1
On the other hand, by induction,

I .

.[ k—l . jss
U1l€£21= H y’léN. 3]
2:1 1

where(s Nj=) 1), forj=l,2,...k—1. Since (s',N')=1, wehave (s',Nj)=1,

Sj)
forj = 1,2,. ..k—l. Thus (s'sj, Nj) = 1, which finishes the proof of the Lemma. C]

We consider a simple example of Lemma 7.2.1. Let sequence V be as defined in
. form (6.24), for r = 2, so N = pq, where p and q are different odd primes. Then from
Lemma 7.2.1

I’ . .
']1—p rzfpl]
PV(j)= 1_q ”'qu ,lSjSN—l. (7.4)

+1 , otherwise

Expression (7.4) is exactly the same as the form (6.26).

Generally, for r 2 2, N = p1p2 . . . pr, where pi’s are distinct odd primes, we have

the following upper estimate for the periodic autocorrelation for V.

Lemma 7.2.2. Let N = plpg...p7~, where p1 < p2 < < pr are distinct odd

84

primes, r is finite. Let the sequence V of entries {0, :tl} be as defined in form ( 6. 24 ),

then we have

1-Ipv( z')| <(i N);
2
2. 2:21:11 P12/(i) S C - a]? , where C is a constant only depending on r.

Proof. For part 1, if (i,N) = 1, then (i,pj) = 1 forj = 1,2,...,r. From Lemma
3.2.5 and 7.2.1,

2) = H Pxpj (i) = :tl

Now if (i, N) = N1 > 1, then (i, N/Nl) = 1. Use the above result and Lemma 7.2.1,

IPv(i)| = IPXN1(0) >< PX N (2'): _<_ IPXN1(0)I s (i,N).
Ni
So part 1 is true.

For part 2, by Lemma 7.2.1,

N—l
232/“) 2: PV(Z)+ 2 PW)

i=1 _(i, N)=1 (i, N)>1
N
2(
( 1%“; 13111132 ”’9' ”+323; [PM ”WW/W")

< Z 1+Zal2 -Z—=¢(N)+ZN-d

(i,N)=1 le d|N

N_2
< (11—
P1

where d(N) is the Euler function of N, and C1 is a constant only depending on r. E]

85

Before we can give an upper bound of the periodic autocorrelations of sequence

'0, we still need one more property.

27ri
Lemma 7.2.3. Let {N = e—N, suppose N = N1 x N2 - - - x NT, where (Ni, Nj) = 1,

for any 1 S i < j S r, then for any integer k, there exist integers k1, k2, . . . , kr, such

that (ki’Nz) = 1, and
7.
Mc-
57v = H 5N;
i=1

Proof. We will prove the lemma by the induction on r. When r = 1, the result is
obviously true if we choose k1 = 1. Suppose the result is correct for r = s — 1, where
s 2 2. Then for r = s, so N = N1 x N2~~ x NS__1 x N3, where (NiaNj) = 1, for
any 1 S i < j S s. Denote N’ = N1 x N2 x Ns_1, so (N’,Ns) = 1. Then there

exist integers k, and 193, such that

ksN' + k’NS = 1 => k a kksN’ + kk’Ns (mod N)

’ kk
=>€jkif =43? 'ENSS

by induction
s— 1

kk' _ kk’s-
EN, — HIEN. .
Z:

where (si,Nz-) = 1, for 1 S i S s— 1. Now
ksN’+k'Ns=1=> (k’,N’) = 1 => (k’,N,-) = 1 for 1 SiSs—l

Let k,- = #3,, for 1 _<_ i g s — 1. Similarly, kSN’ + k’Ns = 1 => (k3,Ns) = 1, then

we have the desired result. [:1

Lemma 7.2.4. Suppose N = 191172 . . . pr, where pi ’s are distinct odd primes fori =
1, 2,. . . ,r. Let X N be the primitive character mod N, f (as) be a polynomial of degree

It. Iffor each pa, 1 S a S r, there is afactorization f(:c) = b(:c—$1)d1 (x-$3)d3

86

in 719a: where :13,- ¢ xj, fori 793' with

(pa—1,d1,...,ds)=1,

then

1
I Z mom» I < 2:.er log (N)
u<nSu+t

where u and t are integers and t > 0.

Proof. From Lemma 3 in [37] (Page 374), we know that for each pj, 1 S j S r,

2 ij(f(rr))e 1’] s lop} (7.5)

for any b E Z. At the same time, one form of the Erdos-Turén inequality ([37] Lemma
4, Page 375) is presented as following
If m E N, the function g(x): Z —><C is periodic with period m, and u and t are real

numbers with 0 S t < m, then

m m
t+1 _ hn27r-
I 2 g(n)Is—m—|Zg(n>u+ 2: VII 112902»: m ‘I (7.6)
u<nSu+t n=1 1g|h|gm/2 n=1

Now apply equation (7.6) with N and x N( f (n)) in place of m and g(n) respectively,

87

and use Lemma 7.2.3 and equation (7.5):

 

 

 

 

 

 

 

Z XN(f(n))
u<nSu+t
t+ 1 N _1 N hn27rz-
S T Z XN(f(n)) + 2 lhl 2 X1v(f(n))e W (7-7)
n=1 lsIhISN/2 "=1
t+ 1 7' pj T pj M,-
= —N— H mum» + Z W4 H 2 moans 1”]
j=1 n=1 1S|h|SN/2 j=1 n=1
r Pj r 1 1
and LEFT/1H ZijUUll) SQXtEIHpES2xN2
3:1 n=1 j=1 .

 

The last inequality follows from equation (7.5).

The calculations above follow from the fact that kj’s are integers such that

(kj.pj)=1

For the second item in (7.7), from equation (7.5), we have

hk-n27r
1 n))_l—p' 2' 1 1
Z W” H 2:1ij )6 J 32x 2 |h|‘ N2
1311431102 1': —1 n=11_<_|h|sN/2

88

Again the last inequality follows from equation (7.5). Therefore we obtain

| Z XN(f(n))l
u<nSu+t
t+ 1 r Pj 1 r pj hkpZ-n27ri
s—N— H 2mm» + Z Ihl" H prjvmne J
i=1 n=1 lglhlgN/Q j=1 n=1
1 1 1 1
g kTN? + kTNQ Z |h|_ < 219W? log (N)
lslhISN/2
which is the desired result. El

Remark 1. In the hypothesis of Lemma 7.2.4, for each pj, 1 S j S r, f (:5) can’t be
a perfect square over ij. As an application of Lemma 7.2.4, the following property

gives a general estimate for all f (SE) of degree 2.
Property 7.2.5. Suppose N = p1p2 . . . pr, where p,- ’s are distinct odd primes and r

is finite. Let x be the primitive character mod N. Let u and t be integers such that

OSt<N,thenforanylSklaékZSN—l,wehave

1- l2u<ngu+t XN(n + k1)XN(n + k2)| S 2 - maxfligl, 2T vN/d 10% (N/d)}
2- IZu<ngu+t(-1)"XN(n+k1)XN(n+k2)| S 4'ma${l§(71112r x/N/Ul 10g(N/d)}
where d = (k2 — k1,N).

Proof. We will prove part 1 first. For d 2 (k2 — k1, N), write N = ds, thus (k2 —

89

191,3): 1. Then

| Z XN(n+ l91) 'XN(n + k2)|
u<nSu+t

=| Z XN(n)'XN(n+k2—k1)|
u+k1<n_<_u+t+k1

=1 2 x302) - x302) «so: + k2 — km.
u’<nSu’+t

whereu’ =u+k1. Letm=|_% j=LN (1.] ThenfromLemma7..,24 wehave

I Z xN(n)-XN(n+k2-k1)l
u’<nSu’+t

m
<21|sz(k2-k1)|+l Z xS(n) -Xs(n+k2—k1)l
J=1u’+ms<nSu’+t

<m+2r ./§- log(s)<2 max{|_-t—-13,-j2r \/N d-log ()N/d},

where the second inequality follows from the fact that (k2 — k1, s) = 1, thus PXs (k2 —
k1) = —1, and Lemma 7.2.4.

For part 2,

Zu<nSu+t(_1)nXN(n + kllXN(n + ’92)

90

s | Z (-1)2"XN(2n + k1)XN(2n + kg) (7.8)
L%J<nstl§dJ
+ z (—1)2n—1XN(2n—1+k1)xN(2n—1+k2) |+2
1%] (723(231)
S I Z XN(2n + k1)XN(2" + k2) l
Lamas-{$1

+| Z XN(2n—1+k1)XN(2n—1+k2)I+2
L%J<nsll§tl

For the first item in expression (7.8),

| Z XN(2n+ k1)XN(2n+k2)| (7.9)
1&1 <ns1%t1
=| Z XN(n+2_1k1)XN(n+2_1k2)|
L%J<nsL%tJ

S 2 - max {LEgLyVN/d log (N/d)}

from part 1. Similarly, from part 1, the second item in expression (7.8),

| Z XN(2n—1+k1)XN(2n—1+k2)| (7.10)
Lg1<nsLU=F1
=1 2 xN<n+ 2‘1<k1—1>>xN<n+ 240:2 — 1)»
L%J<nstl§§1

S 2 - max {L%j,2r\/N/d log (N/d)}

91

Plug the result from expressions (7.9) and (7.10) into (7.8). Then we get the result

we want to prove. C]

Based on Property 7.2.5, we will give an estimate of the upper bound of the Pv(i),

where the sequence v is as defined in Definition 7.1.1.

Lemma 7.2.6. Suppose N = p1p2...pr, where p1 < p2 < < pr are distinct
odd primes and r 2 2 is finite. Let w be the function as defined in Definition 3.1.10.
Then for the sequence v as defined in Definition 7.1.1, for each 1 S i S N — 1, given

condition ( 7. 3) holds, we have

_ FNMA—222") log 9%) , if d = 1;
IP'UCEZH S d/Pl , if w(d) = 7‘ _ 1; (7.11)
mar (d, (/N/d log (%)} , otherwise;

 

where d = (i, N), and C is a constant only depending on r.

Proof. For any 1 S i S N — 1, Pv(i) 2: 2?:01 ”jvj+i1 while from the definition
”jvj+i # 04:) (j,N) =m1 > 1, and (j+i,N) = m2 >1.

Suppose ”jvj+i 71$ 0, and put (m1,m2) = d1. Then m1 = d1d2, m2 = d1d3,
and d1d2d3IN. In the following proof, we put D = d1d2d3. Write j = kd1d2,
j+i = Sd1d3. Then

N N

[$61le + Z = 8611613, and (’6, mg) = (15,-d3;

)= 1. (7.12)

92

Actually, starting with equality (7.12), we can obtain a series of equalities as following

(k + d3)d1d2 + 2' = (s + d2)d1d3 (mod N),
(k + 2d3)d1d2 + i = (S + 2d2)d1d3 (mod N),
(7.13)

(k + Md3)d1d2 + i = (s + Md2)d1d3 (mod N).

where M = 9/7 — 1. Note that all the values in (7.13) are taken modulo N.

Denote (k + nd3,N/d1d2) = g1, and (s + nd2,N/d1d3) = g2. Then all of the

equalities above give us the following partial sum in PU.

M
2 v[ (k + nd3)al10l2 l 'v[ (8 + nal2)0l1d3l
n=0
M
= E: v[ (k + nd3>d1d2 l -v[ (8 + nd2)d1d3l
n=0
91-92>1
M
+ E v[ (k + nd3)d1d2 ] -v[ (s + nd2)d1d3]
n=0
91=92=1
M
= E 'U[ (k + ”d3)d1d2 l -’U[ (S + “d2)d1d3l
n=0
91-92>1
M
+ Z Cn-X N (k+nd3)°x N (3+nd2) (7-14)
n=0 31—35 3133
g1=92=1

where Cn = (Xd1d2(_1))(k+nd3) - (Xd1d3(_1))(s+nd2) from Definition 7.1.1.

93

Therefore,

M
Z Cn'X N (k+nd3)-X N (s+nd2) (7-15)
n=0 211712 3113-
M
= Z gn.XN/D(k+nd3)-xd3(k+nd3)-xN/D(s+nd2)'Xd2(8+nd2)
n=0
M
= Z Cn . XN/D(k +nd3) - XN/D(s +nd2) ' X61309) 'Xd2(5)
n=0

= X61309) ' Xd2 (3) 'XN/D(d3) ' XN/D(d2)'

M

n=0

where d2d2_1 E d3d§1 E 1 (mod N/D). So we have

 

 

M
Z ("'X N (k+nd3)'x N (8+nd2) (7.16)
"=0 21132 3133

91=92=1

M

n=0

Now we take a closer look at the Cn values. From the Definition 7.1.1,
1- (n = 1, if Xd1d2(—1) = Xd1d3("1) = 1;

_ k - _ _ .
2. a — (—1)< ”+870, 11 xd1d2(-1) — xd1d3(-1) — —1,

3- Cn = (4)16”, ifxd1d2(-1) = —1, Xd1d3(-1) =1;

94

where k E k + nd mod N , E s + nd mod N .
n 3( 71715) ., 2‘ Eras)
Now we study each case separately. In the following cases, we let n1 be the first

number that k + n1d3 2 ail—35, and n2 be the first number that s + n2d2 Z 31%;.

For case 1,

M

IX Cn-xN/D(n+kd3—1)-XN/D(n+sd2_1)| (7.17)
n=0

M

= |Z XN/D(n+ kdgl) -XN/D(n+ sd2_1)|
n=0

—1 —1

For case 2, if n1 = n2, then we still have

M
I: a - xN/D(n+ keg-1) - XN/D(n+ .d;1))=|pXN/D(.d;1_ kdgln

n=0

So suppose n1 aé n2. Without loss, suppose n1 < n2, noting that all of d2, d3, 31%
N

and H— are odd. Then we have
1 3

M
| Z(n-XN/D(n+kd3—1)-xN/D(n+sd2—1)| (7.18)
n=0

3 2 I Z XN/D(n+kd3:1)'XN/D(n+3d2_1)I

n1—1<nSn2—1

—1 —1
+|13X,\,/D(sd2 —kd3 )|

95

Since cases 3 are 4 are similar, we consider case 3. Then Cn = (—1)k’n, we have

M
I: cn-xN/D<n+kdg11 -xN/D<n+sd;1>1

n=0

2 | Z (—1)n-XN/D(n+kd§1)~XN/D(n+sd§1)
O<nSn1—1

- Z <-1>”-xN/D<n+kd§1)-xN/D(n+sd;1)1
n1—1<nSM

:1 Z (—1)"-xN/D(n+kd§1)-xN/D(n+sd;1)1
O<nSn1—1

+1 2 (—1)".XN/D(n+kdg1).XN/D(n+sd2-1)| (7.19)
n1—1<TLSM

If N/D = 1, then all of the expressions (7.17), (7.18) and (7.19) are 0(1). S0
suppose N/D > 1.

Put (i,N/D) = 2'1, and (3712-1 — kd§1,N/o) = i2. Then we will prove that
2'1 = 2'2.

Suppose d2d2_1 = k1 - g— + 1, and d3d3_1 = k2 - 2A),- + 1 for some integers k1 and
k2. Then from (7.12), we have

_ _ N N
(3012 1— kd3 1)1) = sd1d3(k1-E +1) — kd1d2(k2 - 5 +1)

- (sk1d1d3 — kk2d1d2) + (sd1d3 — kd1d2)

- (Sk1d1d3 — kk2d1d2) +7:

DIZDIZ

96

 

. N . N .
(z, 5) = (1 => 21 I [ .13 - (8k1d1d3 — kk2d1d2) + z]

:>i1|(sd2_1— ledglw => i1 1 (edgl — kdgl) since (i1, D) :1

N
:>i|—=>i|i.
11) 1 2

On the other hand,

. _ _ . N .
22 | (3712 1— kd31) => 22 | [B(sk1d1d3 — kk2d1d2) + z]
. N . .
1.2 I .13 => 22 I 7.1.
So we have (i, N/D) = (sd2—1 — kd§1,N/D).
Put (i, N/D) = i0, so (3712—1 — kd§1,N/D) = iD.

By lemma 3.2.5 and 7.2.1, expressions (7.17) satisfies

_1 _1 .
IPXN/D(Sd2 — kd3 )l S 2D (7.20)

From Property 7.2.5, equations (7.18) and (7.19) satisfy
M

n=0
N N
S4-max{iD,2r . log< . )}
D-iD D-iD

If (i, N) = d = 1, then ip = 1. We want to show that w(D) 2 2. If w(D) = 1,

(7.21)

 

 

 

 

then d1 = pj for some 1 S j S r, d2 = d3 = 1. Then expression (7.12) becomes

kpj+i=spj => pj|i=> dej

97

which contradicts to the hypothesis that d = 1.

If d = iD :2 1, and w(D) Z 2, then expression (7.21) satisfies

M

—1 —1 r—2 N N
Cn'X (n+kd )-x (n+sd ) S2 —-log(—)
E0 N/D 3 N/D 2 pm pm

And d = 1 implies expression (7.20)
P d—1 — led—1) —— 1
XN/D(3 2 3 - '

So we have proved that when d = 1,

M l N N
Z Cn'X N (k+nd3)‘X N (s+nd2) <1+27~71 ———10g(__)
n=0 22132 El d P1192 P1192

1 3

 

 

Next we want to show that w(iD) S r — 2. If w(iD) = r - 1, then iD = N/pj,

for some 1 S j S r, d1 = pj and d2 2 d3 = 1. Then equation (7.12) becomes
kpj+i=spj => pj|i=> Nli.

This contradicts to the hypothesis that i < N. Thus w(iD) S r — 2.

For d = (i, N), suppose w(d) = r — 1. Then from the above statement we have

just proved,
(i, N) d
S — .

P1 P1

 

i —(i-1Y-)<
D— 11)—

Thus

IPXN/D(8d2_1_ kd§1)l= (sdgl — kd§1,N/D) = 2D 3 d/p1 .

98

When w(d) = r — 1,

 

 

 

N N N
'N =' > > .
(2’ /D) zD—D-z'D- D-iD log(D-iD)

when N is large. So expression (7.21) satisfies

n=0

S 4.ma:l: {iD’ 2T D1~ViD log (DjiD)}

d
S4-iDS4-F.
1

 

M l

 

 

Finally, for 1 S w(d) S r — 2, because 0,11%) = iD S d = (i,N), so equation
(7.21) satisfies

M

n=0

 

 

 

 

S 4 - mam {iD,2T log ( N )} by Property 7.2.5

S 4 . max {d,2r(/ g—log (%)}

Now for the first term of expression (7.14).

M
2 vl (’6 + "d3ld1d2 l 'v[ (8 + nd2)d1d3 l 79 0
n=0
glg2>1

99

 

It means that there exist another set of factors (1’ , (1’2 and d, , with d’ld’2dé | N
such that
I I I - I I I
k d1d2 +2 = s d1d3
where (k’, —,N—,-) = (s’, 7117—) = 1. Then we can set up another series of equalities
d1d2 d1d3
similar to (7.13) and obtain the same upper bound as before. Repeating the previous

steps, we could come up with the following

M
IPv(i)|S Z IZCn'XN(n+kd)'XN(n+3dll
1<d|N n=0 7 7

where (ii = {+1, —1} depending on n values, kd and sd are some integers depending
on the values of d with (sdkd, 1%) = 1 and (sd — kd, g) = (i, g)

Noting that

lair)==j[:1

le
is a finite number only depending on r value, by the discussion above, we have proved

the lemma. [:1

Now we are ready to prove the following lemma:

Lemma 7.2.7. Suppose N = p1p2...pr, where p1 < p2 < < pr’s are distinct
odd primes and r is finite. Let 2 be the binary sequences of length N as defined in

expression (7.2). Then
N —1

2 133(7) 3 C x NQ/pl .

i=1

where C is a constant only depending on r.

Proof. Let the binary sequence V be as defined in form (6.24). Then zj = Vj + v -,

where sequence v is as defined in definition 7.1.1. So from Property 3.2.13, we know

100

that
N—
2111932 =A+B+C+D+E+F (7.22)

In expression (7.22), we have separated the summands into six groups. In the follow-
ing, we will show that the absolute value of every sum from the same group has the
same upper bound. To simplify the notation, it should be understood that all of the
following statements are valid when p1 and p2’s are large enough. For group A,

from Lemma 7.2.2

where Cl is a constant only depending on r.

For group B, we denote i N = (i, N). From Lemma 7.2.6, we have
N_ 2 2 2
21110,? :2 PU (i) + Z PU (2') + Z PU (i).
i1: iN=1 w(iN)=r—1 1Sw(iN)Sr—2
From Lemma 7.2.6,

2
0g2 (_)_ < 021 x —N—, (7.23)
121292 121192121

 

2 133(2) 3 C21x N x
iN=1

where C21 is a constant only depending on r.

Note that

N/d
)3 103(2) = Z Z ’P3<md)
w(iN)<r—2 le m=1
w(d)Sr—2
2
g 2: g x d2 + 5:112— x log2 (N/d)
w(d)Sr—2 w(d)Sr—2
d>(/N/d log (N/d) d<(/N/d log (N/d)
2
£022 X :I—l- , (7.25)

where C22 is a constant only depending on r.

Combine the results from equations (7.23), (7.24) and (7.25), we have

N—1 2

N
i=1 p1

where C2 = mar{C21, C22,r}.

For groups C and D, every term in this group could be written as

N—l N—l
Z PVU) Z: ’Umém, where {m 6 {+1, -1}.
i=1 m=0

Lemma 3.2.5, 3.2.8, 7.2.1 and Lemma 7.2.2 give

N—l N—l N-l
| Z Pv(z') 2 vaml .<_ rN/pi x Z IPv(i)|

102

N—l N-
mWflZWWH23WWl
i-l i 1

(M7)»
N/d

< rN/pl x [N + Z Z ’IPv(kd)ll
le k=1

ng/p1 x [N+ ZN/dxd]
le

SC3XN/p1XN

= C3 X N2/p1,

where C3 is a constant only depending on r. Again, the inequality second to the last

follows from the fact that d(N) is a finite number.

Now we consider the terms in group F.

N—l 2 N—lN—lN—l

Z P V41“) 2 Vjvj+ivam+i

i=1 i=1 j=0 m=0
— 1N- N— 1
:NZ:1 Zlvj VN—mvN—m— —i (7°26)
i=1 j=0 m: 0

N— l-N 1N—
: :1 2:01 ZOVjvj+ivme+i=1:—:11PV,21() V()
1:1 jO: m:0

N—l N—l
Zfim=2wmmm
i=1 i=1

Therefore for every term in group F, it is enough to estimate the upper bound of

2,"; 1Py.,( 1 Pun/(2').

N—l —1N-1N—1
PV,v(z)Pv,V(z) = VjvJ-l-vaVm-I-Z
i=1 i=1 j=0 m=0
N—1N—1N—1
= vgvmVj—iVm-l—i
i=1 3:0 m=0
N— 1N—1—1
1); 2 ”WM 2V2 V—m— 2')
j: —0 m=0
N—1N—1
(—1) vjvaV(m +j)
j=0 m=0
Also
N—lN—l
I Z: Z vjvaV(m+])I
3:0 m=0
N—lN—I
=| vjvs—jPV(S)|
s=0 j=0
N—1 2 N—l N
SI ’UJPv(0)|+| Z Pv(8)Pv(8)|+ I Z Pv(8)(-1)T|
J20 3:1 3:
3:0 (s,N)>1

From Lemma 3.2.8,

104

N—l N—l
| Z vgpvmn = M 2 12%| 3 TN x N/pl g r x N2/p1 (7.27)
i=0 i=0

In the proof of Lemma 7.2.6, we know that when (5, N) = 1,

N
Nlo(

g .
191372 P1102

 

 

IPv(S)| S 2r

Then when 'r 2 2,

N
N N
I I r 7‘ 2
2 P3 <2 Ps <N><2 log — 2 xN p 7.28
I v( )I I v( )I 191192 g_(p1p2) / 1 ( )

3:1 3:1

 

We will have to be more careful in estimating | 2%: 7V1)>1 PU (s)PV (s)|. We write

N—l

Z Pv(8)Pv(8)|S| Z Pv(S)Pv(8)| (729)
3:1 w((s,N))=r—l

(s,N)>1

+ I Z Pv(S)Pv(S) |
w((s,N))§r——2

For the first item of equation (7.29),

 

r Pk—l
| Z Pv(8)Pv(8) |= | Z Z Pv(mN/pk)Pv(mN/Pk)| (7-30)
w((s,N))=r—1 k=1 m=1
7' IP‘k 7" Pic—1 N
(m P mN —
$221111) N/pk|X|v( /pk|<gn§1plpkxpk

k:1m=1

T
<21 N2/ /(P1Pk) < N2/P1

105

Now for the second item of equation (7.29),

I Z Pv(3)Pv(5)| (7.31)
w((s,N))_<_r—2
N/d
= I Z Z ’Pv(md)PV(md)|
d|N m=1
w(d)Sr—2
N/d
3 Z Z 'va(md)I|Pv(md)l
w(d)_<_r—2
N 2 N3 N N2
g 2 Exd+ 2: dx d—3xlog(g)3031xfi,
d|N le
dZN/N/d log (LXI) d<‘/N/d log (Lg/r)
here C31 is a constant only depending on r .
= Z1 is finite
le
Now equations (7.27) and (7.28),(7.30) and (7.31) give us
—lN— 1 N— IN— 1 N2
I}: :0 :0 Vyvj+ivme+i| =| Z Z 7’ j<vaV (m+j)l <03 X H
i=1 j0= =0 j=0 m=0

where C3 is a constant only depending on 7' .

Finally, for the items in group B, we first consider

N—l N— 1
:W, =23Pv<n 2:12).
i=1

We will use a similar method to the proof for Lemma 7.2.6 to give an upper estimate

106

Oijr- —10 ”3 V744

From Lemma 3.2.8 and 7.2.6, we have
vjVj-l'i 750% (j,N) =d>1 and (j+i,N) =1

Writej = kd, j+i= 3. So , (k,N/d) = (s,N) = 1.

Again, we can set up the following series of equalities, noting that all the values

are taken modulo N.

kd+i=s
(k+1)d+i=s+d
(7.32)

(k+(M—1))d+i=s+(M—1)d

_ N
where M — 7'

The equation series in (7. 32) give the following partial sum of Z]_01v ”jvj+z'

Cm' (m) (md+z')
Z: XLXT XN
M—l
=Xd(i)-XN(d)- ( Z Cm'XN(m)'XN(m+id_l)) ,
'J mzo 'J U

I
where (m = +1, or (—1)m with m’ s m (mod N/d), dd‘1 2 1 (mod N/d). Note
that (d, N/d) = 1, so that (id—1,12%) = (2315-). Then from Lemma 7.2.6, if (m = 1,

107

 

forallOSmSM—l,then

IZJCmXNUn 720%de )|= IPxN(id_1)l=(i,g)SiN (7.33)

I
If Cm = (—1)m , where m’: — m (mod N /d), then just repeating the process in

expression (7.19) and using Lemma 7.2.5, we can obtain

—1
Z (—1)m' - XN (m) “if (m + id—l) (7.34)

m=0 H-

N 10 N }
d-t'D g d-iD

 

 

 

 

S maa:{z'D, 27'

where iD = (i, N/d).

1

For the remaining items in 29;?) vjVj+iv we use a similar argument to before.

Since d(z'N) is a finite number, we have
N —1
. /_ N N
I Z ”J'Vj+z' | S max{zD, 2' log (2,— )} (7.35)
j=0 D D

By Lemma 7.2.6 and expression (7.35), we have

N- N—l
[:IPMZX 1:3:1’J'VJHH SZIIP (JIXIZUJ'VJI'I’Z'I

N/d
=(§=<I1IPI )IXIZIUJ newcgjjvzl’vaHsdlxIZ jj+sd|
z, s:

108

Z IP71“) IXIZIUJ' Vj+iI

(i,N)=1

N/d

+( Z + Z ZIP’USdIXIZJJ-l-Sdl

le le

dzt/N/d log(N/d) d<‘/N/d log (N/d

( )
3 C41 x I: Z Nd+ 2 $103 (g)

 

 

 

k 1 am le
( d2,/N/d log (N/d) d<,/N/d log (N/d) }
x N o 2 Ni
+ 041 “NEH __plp21gm) <C4xp1;

where C4 is a constant only depending on 7‘.

Using the similar method to expression (7.26), it can be shown that Pv(i)P.U,V(i) =
Pv(z')Pv,v(i), for any 2' = 1,. . . , N — 1. Then all of the inequalities above will give us

the desired result. C]

Now we are ready to prove Theorem 7.1.3.

7 .3 Proof of Theorem 7 .1.3

Proof. ( Theorem 6. 3. 3 part (1) )
We denote g N — -e7vli. For any sequence a: of length N, let x[ 6N] be the Discrete

Fourier Transform of x as defined in Definition 3.1. Recall the interpolation formula

109

as in Property 3.2.9,

N—l 5k

' 2
$1 —€fvl :N Z (I:

Then for the sequence 2 as defined in Definition 7.1.1, we have
zI {iv} = VI {1,} + vI 6%,]
Note that from Gauss sum,

x/N, 2f (j,N)=1;

0, otherwise

IVI ti,“ =

Therefore, using the interpolation formula (7.36), we have

 

 

 

 

I 2 E1 6h I.
|V[—€N1|= — —-—V[€N]
Nk=0%+%
5k
_ <\/NlogN
<7? 2 065% +€NI
Now consider v[ 6V ]. By definition
vItN ]= Z det§I+ Z XIII—5(3)]
le le
dEN( mod 4) d$N( mod 4)

Using the Gauss sum ([38], page 233),

I Z XdlégllIS Z IXdiéfillsg

dIN dIN
dEN( mod 4) dEN( mod 4)

110

 

(7.36)

(7.37)

(7.38)

As in (7.38), we have

. . N
| Z XdI if)“ S 2 leI 456])“ S C X (Elf-103 (if) I
le d|N 1 1
d¢N( mod 4) d¢N( mod 4)

where C is a constant only depending on r.

Then we have obtained

N N
v[ 6N ] < C x filog (1)—1) (7.39)

Note that

III 4%,] = Z de 43)] + Z de 63)]
d|N le
dEN( mod 4) daéN( mod 4)

Then using exactly the same method, we have

vl 453V] 3 C x \Elog (1%) (7.40)

Let F be the merit factor of sequence as, F the merit factor of V. From Property
3.2.10,

1 _ . .
1/P= ——§ :3 [IzItvaI4+IzI—t}VII4] -1
J20
1 N ' 4 ' 4
1/P=——3 :30 [IV[€}VJI +|V[—€}V]l ]—1
Let 1/F —1/F = G/2N3, want to show that

G/2N3—+0 asN—+oo.

111

Put aj = v[ {k} and bj = v[ —§:,7V]. Then from Property 3.2.11,

N—l
IGI s 2 I IajI4 + 6|V[ e,-II2Ia,-I2 + 4< M 4,12 + IajI2 )laJIIVI 5,1 I (7.41)
j=0

N—l
+ Z I IbJ-I4 + filVl-éjllzlbjlz + 4< IVI—thI2 + lbjlg )lijVI—éjll I
j=0

If we apply the results from (7.37), (7.38), (7.39), and (7.40) to (7.41), then we obtain

N3
|G| << 7171-1051 (N) (7.42)

Thus provided (7.3) is satisfied, we have

which finishes the proof for part (1) of Theorem 6.3.3. 1:]

Now we are ready to prove part (2) of Theorem 7.1.3.
Proof. ( Theorem 7.1.3 part (2) )
For N = plpg . . .pr odd, Lemma 6.3.2 shows that sequence z is symmetric or

antisymmetric depending the value of N (mod 4). Let the sequence 6 of length 2N
be as defined in (3.1.5). Then for

b = {2; 2} *fl
2N—1 N—l N—l N—l
Z A§(II)=N+ Z A§(k)+2 Z Pz(k)Az(k)+ Z 102(k)?
evenk even]:

112

By Lemma 4.0.17.

The proof for part (1) of Theorem 7.1.3 shows that
2 :11 A2(k) ~-N2 (7.43)

if the condition (7.3) holds. Lemma 7.2.7 shows that

— N—l N2
Z P2002: 2: PM)2 <C<<;—
1

even I:

Then given condition (7.3), by the Cauchy-Schwarz inequality

 

N—l N—l N—l
23PMM&WHS IEZPQMIIZZPQM

It even It even It even

 

S [ Az(k)l-[ 102(k)] <<—-
k=1 k=1 m

Therefore, provided condition (7.3) holds, the asymptotic merit factor of b is

 

 

2
lim (Fb) = lim 21(31N1) 2
New Newmzk .44»
4N2
2 11m N—1 2 =4xg=6
NTOO 22k 1 140(k)
This finishes the proof of part (2) of Theorem 7.1.3. [:1

Conclusion. For a long time, being afraid of losing ideal properties of the real prim-

113

itive character sequences, people have been passive in changing the values of those
j—th positions with gcd( j, N ) > 1. This thesis has provided new modifications to char-
acter sequences on those j-th positions with gcd(j, N) > 1. Particularly, at length
N = 121102, the author has shown that we could have more freedom in changing
the values on those positions. The author was informed recently that J edwab and
Schmidt have obtained the same result independently under an improved condition
([40])-

All the known binary sequences obtaining high asymptotic merit factor 6.0 prior
to this thesis are of odd length. This thesis also provides a general technique to
construct binary sequences of even length, from which the high asymptotic merit

factor 6.0 can be achieved as well.

114

BIBLIOGRAPHY

[1] RH. Barker, “Group Synchronizing of Binary Digital Systems”, Commu-
nication Theory (W. Jackson, ed. ), Academic Press, New York, 1953, Page
273-287.

[2] R. Fano, Transz'mz'ssz'on of Information, Cambridge, MIT Press, 1961.
[3] EC Parnett, GH Stevens, Radar handbook, 1990 - helitavia.com.

[4] GR. Welti, “Quaternary Codes for Pulsed Radar”, IRE Trans. Inform.
Theory Vol. IT—6, 1960, Page 400-408.

[5] A.M. Boehmer, “Binary Pulse Compression Codes”, IEEE Trans. Inform.
Theory Vol.1T-13, 1967, Page 156-167.

[6] R.J. 'I‘uryn and J. Storer, “On Binary Sequences”, Proc. Amer. Math. Soc.,
Vol. 12, 1961, Page 394-399.

[7] R.J. Turyn, “Sequences with Small Correlation”, Error Correcting Codes
(H.B. Mann, ed. ), Wiley, New York, 1968, Page 195-228.

[8] J. Jedwab, “What Can Be Used lnstead of a Barker Sequence?”, Contem-
porary Math., Vol 461, 2008, Page 153-178.

[9] M.J.E. Golay, “A Class of Finite Binary Sequences with Alternate Autocor-
relation Values Equal to Zero”, IEEE Trans. Inform. Theory, Vol. IT-18,
1972, Page 449—450.

[10] M.J.E. Golay, “Hybrid Low Autocorrelation Sequences”, IEEE Trans. In-
form. Theory, Vol. IT—21, 1975, Page 460—462.

[11] M.J.E. Golay, “Sieves for Low autocorrelation Binary Sequences”, IEEE
Trans. Inform. Theory, Vol. IT-23, 1977, Page 43—51. .

[12] M.J.E. Golay, “The Merit Factor of Long Low Autocorrelation Binary Se-
quences”, IEEE Trans. Inform. Theory, Vol. IT-28, 1982, Page 543-549.

115

[13] M.J.E. Golay. “The merit Factor of Legendre Sequences”, IEEE Trans.
Inform. Theory, Vol. IT—29, 1983, Page 934-936.

[14] M.J.E. Golay and DB. Harris. “A New Search for Skewsymmetric Binary
Sequences with Optimal Merit Factors”, IEEE Trans. Inform. Theory, Vol.
36, 1990, Page 1163-1166.

[15] P. Borwein, R. Ferguson, and J. Knauer, “The Merit Factor Problem”, 2000
Mathematics Subject Classification, Vol. 11B83, 11Y55, Page 52-70.

[16] J .E. Littlewood, “Some Problems in Real and Complex Analysis”, Heath
Mathematical Monographs, D.C. Heath and Company, Massachusetts, 1968.

[17] J.E. Littlewood, “On Polynomials Zn 212’", Z” eamizm, z = e62”, J.
London Math. Soc., Vol. 41, 1966, Page 367-376.

[18] D.J.Newman and J .S.Byrnes, “The L4 Norm of a Polynomial with Coeffi-
cients 21:1”, Amer. Math. Monthly, , Vol. 97, 1990, Page 42-45.

[19] L. Lunelli, “Tabelli di Sequenze (+1, —1) con Autocorrelazione Tioncata
non Maggiore di 2”, Politecnico di Milano, 1965.

[20] S. Mertens, “Exhaustive Search for Low-Autocorrelation Binary Se-
quences”, J. Phys. A: Math. Gen, Vol. 29, 1996, Page L473—L481.

[21] S. Mertens and H. Bauke, “Ground Statas of the Bernasconi Model with
Open Boundary Conditions”, Online available: <http://odysseus.nat. uni-
magdeburg. de/ mertens/bernasconi/open.dat>, November 2004.

[22] J. Jedwab, “A Survey of the Merit Factor Problem for Binary Sequences,”
in: T. Helleseth et al, eds., Lecture Notes in Computer Science, Vol. 3486,
Sequences and Their Applications—Proceedings of SETA 2004, Springer-
Verlag, 2005, Page 30-55.

[23] T. Hoholdt, H.E. Jensen, “Determination of the Merit Factor of Legendre
Sequences,” IEEE Transactions on Inform. Theory, Vol. 34 No. 1, Jan.
1988, Page 161-164.

[24] J .M. Jensen, H.E. Jensen, T. Hoholdt, “The Merit Factor of Binary Se-
quences Related to Difference Sets,” IEEE Transactions on Inform. Theory,
Vol. 37 No. 3, May 1991, Page 617—625.

[25] P. Borwein,K-K. S. Choi, “Merit Factors of Polynomials Formed by Jacobi
Symbols”, canad. J. Math. Vol. 53 (1), 2001, Page 33-50.

[26] C. de Groot, D. Wiirtz, and K.H. Hoffmann, “Low Autocorrelation Binary
Sequences: Exact Enumeration and Optimization by Evolutionary Strate—
gies”, Optimization, Vol. 23, 1992, Page 369-384.

116

[27] P. Borwein, K—K. S. Choi, and J. Jedwab, “Binary Sequences with Merit
Factor Greater Than 6.34”, IEEE Transactions on Inform. Theory, Vol. 50,
No. 12, Dec. 2004, Page 3234-3249.

[28] MG. Parker, “Even Length Binary Sequence Families with Low Negape-
riodic Autocorrelation”, Applied Algebra, Algebraic Algorithms and Error-
Correctin Codes, AAECC-14 Proceedings, Springer- Verlag, 2001, Page 200-
210.

[29] N .Y. Yu and G. Gong, “The Perfect Binary Sequence of Period 4 for Low
Periodic and Aperiodic Autocorrelations”, Sequences, Subsequences, and
Consequences, Springer— Verlag, Berlin, 2007, Page 37-49.

[30] K.U. Schmidt, J. Jedwab, and MG. Parker, “Two Binary Sequence Families
with Large Merit Factor ”, Advances in Mathematics of Communications,
Vol. 3, No.2, 2009, Page 135-156.

[31] DH. Green and RR. Green, “Modified Jacobi Sequences”, IEE Proc.-
Comput. Digit. Tech., Vol. 147 No. 4, July 2000, Page 241-251.

[32] W. Zhang, “ On a Problem of P. Gallagher ”, Acta math. Hangar. Vol. 78,
1998, Page 345-357.

[33] H. N. Liu, “ New Pseudorandom Sequences Constructed Using Multiplica-
tive Inverses ”, Acta Arith. Vol. 125, 2006, Page 11-19.

[34] A. Weil, “Sur les courbes algebriques et les varietes qui s’en deduisent”,
Actualites math. sci. No.1041, Paris, 1945, Deuxieme Partie, §IV.

[35] A. A. Karatsuba, “Sums of Characters With Prime Numbers and Their Ap-
plications”, Tatra Mt. Math. Publ. Vol. 20, 2000, Page 155-162.

[36] W. M. Schmidt,“Equations over Finite Fields: an Elementary Approach”,
Springer, 1976

[37] C. Mauduit and A. Sérkozy, “On Finite Psudorandom Binary Sequences
1: Measure of Pseudorandomnass, the Legendre Symbol, Acta Arithmetica,
LXXXIIA, 1997.

[38] G. Everest, T. Ward, “An Introduction to Number Theory”, Springer, 2005.

[39] T. Xiong and J .I.Ha11, “Construction of Even Length Binary Sequences
With Asymptotic Merit Factor 6,” IEEE Transactions on Information The-
ory Vol. 54(2), 2008, Page 931-935.

[40] J. Jedwab, K. Schmidt, “The Merit Factor of Binary Sequences Derived
from the Jacobi Symbol”, Preprint, 2010.

117

 

[41] T. Xiong and J .I.Ha11, “Modifications of Modified Jacobi Sequences,” sub-
mitted.

[42] B. Conrey, A. Granville, B. Poonen, K. Soundararajan, “Zeros Of Fekete
Polynomials ”, Annales de l’institut Fourier, Vol. 50, No. 3, 2000, Page
865-889.

118