arXiv:1803.08404v1 [cs.IT] 22 Mar 2018

SEQUENCE PAIRS WITH ASYMPTOTICALLY
OPTIMAL APERIODIC CORRELATION
CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT
Abstract. The Pursley-Sarwate criterion of a pair of finite complexvalued sequences measures the collective smallness of the aperiodic autocorrelations and the aperiodic crosscorrelations of the two sequences. It
is known that this quantity is always at least 1 with equality if and only
if the sequence pair is a Golay pair. We exhibit pairs of complex-valued
sequences whose entries have unit magnitude for which the PursleySarwate criterion tends to 1 as the sequence length tends to infinity.
Our constructions use different carefully chosen Chu sequences.

1. Introduction and Results
In this paper, a sequence of length n is a finite sequence of n complex
numbers; such a sequence is called binary if each entry is −1 or 1 and it is
called unimodular if each entry has unit magnitude.
Let A = (a0 , a1 , . . . , an−1 ) and B = (b0 , b1 , . . . , bn−1 ) be two sequences of
length n, where A und B contain at least one nonzero entry. The aperiodic
crosscorrelation of A and B at shift u is defined to be
X
aj bj+u ,
CA,B (u) =
j∈Z

with the convention that aj = bj = 0 if j < 0 or j ≥ n. The aperiodic
autocorrelation of A at shift u is then CA,A (u).
There is sustained interest in sequences with small correlation (see [15] for
a survey of recent developments), mainly because small correlation helps to
separate a useful signal from noise or unwanted signals. In particular, small
crosscorrelation is usually required to ensure that sequences can be distinguished well from each other and small autocorrelation is usually required
to keep the transmitter and the receiver synchronised.
The collective smallness of the aperiodic crosscorrelations of the sequences
A and B is measured by the crosscorrelation demerit factor of A and B,
which is defined to be
P
2
u∈Z |CA,B (u)|
.
CDF(A, B) =
CA,A (0) · CB,B (0)
Date: 22 March 2018.
The authors are supported by German Research Foundation (DFG).

2

CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT

Accordingly, the collective smallness of the aperiodic autocorrelations of A
is measured by the autocorrelation demerit factor of A, which is defined to
be
P
2
u∈Z\{0} |CA,A (u)|
.
ADF(A) =
CA,A (0)2
Notice that CA,A (0) = CB,B (0) = n if A and B are unimodular. The reciprocals of CDF(A, B) and CDF(A) are known as the crosscorrelation merit
factor of A and B and the autocorrelation merit factor of A, respectively.
A fundamental relationship between the three quantities ADF(A), ADF(B),
and CDF(A, B) is given by
p
p
(1)
− ADF(A) ADF(B) ≤ CDF(A, B) − 1 ≤ ADF(A) ADF(B),
as proved by Pursley and Sarwate [13] for binary sequences and generalised by Katz and Moore [8] for general sequences. Following Boothby
and Katz [2], we define the Pursley-Sarwate criterion of A and B to be
p
PSC(A, B) = ADF(A) ADF(B) + CDF(A, B).

From (1) we obtain PSC(A, B) ≥ 1. Hence in order to design pairs of
sequences (A, B) with simultaneously small aperiodic autocorrelations and
crosscorrelations, we would like to have PSC(A, B) close to 1.
Katz [7] and Boothby and Katz [2] studied the Pursley-Sarwate criterion
of sequence pairs derived from m-sequences and Legendre sequences and
generalisations of them. This gives pairs of unimodular and binary sequences
whose Pursley-Sarwate criterion is close to 1, but strictly bounded away
from 1, as the sequence length tends to infinity. (Unlike claimed in [7], the
crosscorrelation demerit factors of pairs obtained from Legendre sequences
and m-sequences have been studied before, namely in [16, Theorem 3] and [6,
Theorem 9].)
In fact, pairs of unimodular sequences (A, B) with PSC(A, B) = 1 were
recently classified by Katz and Moore [8] to be exactly the Golay pairs,
namely pairs of unimodular sequences (A, B) satisfying
CA,A (u) + CB,B (u) = 0 for all u 6= 0.

Golay pairs of unimodular sequences are known to exist for infinitely many,
though not for all, lengths (see [4] for the existence for small lengths). The
classification in [8] does however not say anything about the individual quantities ADF(A), ADF(B), and CDF(A, B) for a Golay pair (A, B). These values are known for the Rudin-Shapiro pairs, which are Golay pairs (Am , Bm )
of binary sequences of length 2m and satisfy
ADF(Am ) = ADF(Bm ) = 13 (1 − (−1/2)m )

(see [15], for example). Since PSC(Am , Bm ) = 1, we have
CDF(Am , Bm ) = 13 (2 + (−1/2)m ).

Therefore, as m → ∞, we have ADF(Am ) → 1/3 and ADF(Bm ) → 1/3 and
CDF(Am , Bm ) → 2/3.

APERIODIC CORRELATION OF SEQUENCE PAIRS

3

In this paper we exhibit unimodular sequences whose Pursley-Sarwate
criterion is asymptotically 1 and for which we can control the autocorrelation
and crosscorrelation demerit factors. Our results involve Chu sequences [3],
which are unimodular sequences of length n of the form
Zn(a) = (z0 , z1 , . . . , zn−1 ),

zj = eπiaj

2 /n

,

where a is an integer (Chu [3] used a slightly different definition when n is
odd).
(1)
Several authors
[11], [17], [10] have shown independently that 1/ ADF(Zn )
√
grows like n and the exact constant has been determined by the second
author [14] by showing that
√
2
(2)
lim n ADF(Zn(1) ) = ,
n→∞
π
which confirms previous numerical evidence obtained by Littlewood [9] and
(1)
Bömer and Antweiler [1]. In fact, since ADF(Zn ) tends to zero, this immediately implies that
lim PSC(Zn(1) , Zn(1) ) = 1.

n→∞
(1)

(1)

However, the pair (Zn , Zn ) would be a bad choice when good crosscorrelation is required since the crosscorrelation at the zero shift equals the
(1)
(−1)
sequence length n. This problem is avoided by taking the pair (Zn , Zn ).
Indeed it can be shown using Lemma
6 that in this case the crosscorrelation
√
at the zero shift is of the order n. Our first result is the following theorem.
(1)

Theorem 1. For each n, let Xn = Zn
of length n. Then, as n → ∞,
(i) ADF(Xn ) → 0, ADF(Yn ) → 0,
(ii) CDF(Xn , Yn ) → 1,
(iii) PSC(Xn , Yn ) → 1.

(−1)

and Yn = Zn

be Chu sequences

In our second result we construct a pair of unimodular sequences from
two Chu sequences of even length such that the Pursley-Sarwate criterion
is asymptotically 1 and the autocorrelation and crosscorrelation demerit
factors are asymptotically balanced, which means that they all tend to the
same constant 1/2.
(n+1)

(n−1)

Theorem 2. For each n, let Xn = Z2n
and Yn = Z2n
of length 2n. Then, as n → ∞,
(i) ADF(Xn ) → 1/2, ADF(Yn ) → 1/2,
(ii) CDF(Xn , Yn ) → 1/2,
(iii) PSC(Xn , Yn ) → 1.

be Chu sequences

We shall prove the first parts of Theorems 1 and 2 in Section 2 and the
second parts in Section 3. Of course the third parts are trivial consequences
of the first two parts.

4

CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT

2. Autocorrelation of Chu sequences
In this section we prove our results on the autocorrelations of the Chu
sequences in question. We begin with a lemma, which gives an expression
for the autocorrelation demerit factor of Chu sequences.
Lemma 3. Let a and n ≥ 1 be integers and write d = gcd(a, n). Then


X
sin(πau2 /n) 2 (d − 1)(2d − 1) 2dǫn/d
4d
(a)
+
−
,
ADF(Zn ) = 2
n
sin(πau/n)
3d
n2
1≤u≤n/(2d)

where ǫn/d = 1 if n/d ≡ 2 (mod 4) and ǫn/d = 0 otherwise.
(a)

Proof. Write Z = Zn , a = db, and n = dm. Straightforward manipulations
give
n−u−1
X
e2πibuj/m .
|CZ,Z (u)| = |CZ,Z (−u)| =
j=0

for 0 ≤ u < n. Hence, if u is not a multiple of m, then
|CZ,Z (u)| =

sin(πbu2 /m)
.
sin(πbu/m)

Therefore
ADF(Zn(a) )

n−1
2 X
|CZ,Z (u)|2
= 2
n u=1

=

m−1
d−1
2d X
2 X
2
|C
(u)|
+
|CZ,Z (km)|2
Z,Z
n2
n2
u=1

=

4d
n2

X

1≤u≤m/2

k=1

|CZ,Z (u)|2 +

d−1
2dǫm
2 X
|CZ,Z (km)|2 −
2
n
n2
k=1

since |CZ,Z (u)| = |CZ,Z (m − u)| for 1 ≤ u < m and |CZ,Z (m/2)| = ǫm for
even m. Finally, note that
d−1
d−1
X
X
2
(n − km)2
|CZ,Z (km)| =
k=1

k=1

= m2

d−1
X

k2

k=1

n2
(d − 1)(2d − 1),
=
6d
which completes the proof.



The second author obtained (2) from Lemma 3 with a = 1 and the first
identity in the following lemma.

APERIODIC CORRELATION OF SEQUENCE PAIRS

5

Lemma 4 ([14]). We have
lim

n→∞

lim

1
n3/2



sin(πu2 /n)
sin(πu/n)

2

=

1
,
2π

X



sin(πu2 /n)
πu/n

2

=

1
.
2π

1≤u≤n/2

1

n→∞ n3/2

X

1≤u≤n/2

From Lemmas 3 and 4 we also obtain
2
,
n→∞
π
which implies Theorem 1 (i). We now use Lemmas 3 and 4 to prove Theorem 2 (i).
lim n1/2 ADF(Zn(−1) ) =

Proof of Theorem 2 (i). We distinguish the cases that n runs through the
set of even and odd positive integers. First we show that
(3)

lim ADF(X2m ) = lim ADF(Y2m ) = 1/2.

m→∞

m→∞

It is readily verified that the aperiodic autocorrelations of X2m and Y2m
have equal magnitudes at all shifts, so that it is sufficient to establish that
ADF(X2m ) → 2. Noting that 2m + 1 is coprime to 4m and using trigonometric addition formulas, Lemma 3 with n = 4m and a = 2m + 1 shows
that 4m2 ADF(X2m ) equals


2m 
2m 
X
X
cos(πu2 /(4m)) 2
sin(πu2 /(4m)) 2
+
.
sin(πu/(4m))
cos(πu/(4m))
u=1
u=1
u odd

u even

O(m3/2 ),

By Lemma 4, the first sum is
so that it is sufficient to show that


m
1 X cos((π(2v − 1)2 /(4m)) 2
(4)
lim
= 2.
m→∞ m2
cos(π(2v − 1)/(4m))
v=1

Let x be a real number satisfying 0 < x < π/2. From the Taylor series of
cos x at π/2 we find that
−(x − π/2) + 16 (x − π/2)3 < cos x < −(x − π/2),

from which it follows that
0<

1
1
−
< 1.
2
(cos x)
(x − π/2)2

Therefore,

m 
X
cos(π(2v − 1)2 /(4m)) 2
v=1

cos(π(2v − 1)/(4m))

−

Put v = m + 1 − w to obtain

m 
X
cos(π(2v − 1)2 /(4m)) 2
v=1

π(2v − 1)/(4m) − π/2


m 
X
cos(π(2v − 1)2 /(4m)) 2
v=1

=

π(2v − 1)/(4m) − π/2

< m.


m 
X
cos(π(2w − 1)2 /(4m)) 2

w=1

π(2w − 1)/(4m)

.

6

CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT

Apply (cos x)2 = 1 − (sin x)2 to the right hand side and use Lemma 4 to
obtain
!2
m 
∞
16 X
1
1 X cos(π(2w − 1)2 /(4m))
= 2
lim
m→∞ m2
π(2w
−
1)/(4m)
π
(2w
− 1)2
w=1
w=1
!
∞
∞
X
16 X 1
1
= 2
−
π
w2
(2w)2
w=1

w=1

∞
12 X 1
= 2
= 2,
π
w2
w=1

using Euler’s evaluation
pletes the proof of (3).
Next we prove that
(5)

P∞

w=1 1/w

2

= π 2 /6. This gives (4), and so com-

lim ADF(X2m+1 ) = lim ADF(Y2m+1 ) = 1/2.

m→∞

m→∞

Note that gcd(2m + 2, 4m + 2) = 2, so that Lemma 3 with n = 4m + 2 and
a = 2m + 2 gives

m
X
sin(π(m + 1)u2 /(2m + 1)) 2 1
8
+ .
ADF(X2m+1 ) =
(4m + 2)2
sin(π(m + 1)u/(2m + 1))
2
u=1

On the other hand, gcd(2m, 4m + 2) = 2, so that Lemma 3 with n = 4m + 2
and a = 2m gives

m 
X
8
sin(πmu2 /(2m + 1)) 2 1
ADF(Y2m+1 ) =
+ .
(4m + 2)2
sin(πmu/(2m + 1))
2
u=1

Comparing the two preceding equations and using






π(m + 1)k
πmk
πmk
− πk = sin
= sin
,
sin
2m + 1
2m + 1
2m + 1

we conclude that ADF(X2m+1 ) = ADF(Y2m+1 ). To complete the proof, we
show that

m 
1 X sin(πmu2 /(2m + 1)) 2
(6)
lim
= 0.
m→∞ m2
sin(πmu/(2m + 1))
u=1

For even k, we have






πk
πmk
π
πmk
− k = sin
sin
= sin
,
2m + 1
2m + 1 2
4m + 2
so that


m 
X
sin(πmu2 /(2m + 1)) 2
= O(m3/2 )
sin(πmu/(2m
+
1))
u=1

u even

APERIODIC CORRELATION OF SEQUENCE PAIRS

7

by Lemma 4. For odd k, we have






πk
π
πmk
πmk
− k = cos
= cos
,
sin
2m + 1
2m + 1 2
4m + 2
so that


m 
m 
X
X
sin(πmu2 /(2m + 1)) 2
cos(πu2 /(4m + 2)) 2
=
.
sin(πmu/(2m + 1))
cos(πu/(4m + 2))
u=1
u=1
u odd

u odd

The summands on the right hand side are at most 2, so that the entire sum
is at most m + 1. This proves (6), and so completes the proof of (5).

3. Crosscorrelation of Chu sequences
In this section we prove our results on the crosscorrelations of the Chu
sequences in question. A straightforward computation shows that the modulus of the aperiodic crosscorrelations between two Chu sequences of equal
length are given by generalised Gauss sums, which are for real x and θ and
integral N defined to be
SN (x, θ) =

N
X

eπixj

2 +2πiθj

.

j=1

An asymptotic expansion of these sums was obtained by Paris [12] using
an asymptotic expansion of the error function. We deduce an estimate for
generalised Gauss sums from this expansion. To state the result, define for
real x 6= 0 and θ,
p

2
E(x, θ) = e−πiθ /x erfc eπi/4 θ π/x ,

where, for complex z,

Z z
2
2
erfc(z) = 1 − √
e−t dt
π 0
is the complementary error function and the integral is over any path from 0
to z.
Proposition 5 ([12, Theorem 1]). Let N be a positive integer, let x ∈ (0, 1),
and let θ ∈ (−1/2, 1/2]. Write N x + θ = M + ǫ, where M is integral and
ǫ ∈ (−1/2, 1/2]. Then
2

e−πiθ /x+πi/4
µ−1
√
SM (−1/x, θ/x) +
2
x
πi/4

 i
e
+ √ E(x, θ) − µE(x, ǫ) + g(θ) − µg(ǫ) + R,
2
2 x

SN (x, θ) =

2

where |R| < x and µ = eπixN +2πiθN and g : [−1/2, 1/2] → R is given by
(
0
for t = 0
g(t) =
−1
cot(πt) − (πt)
otherwise.

8

CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT

Fiedler, Jurkat, and Körner [5] obtained the following estimate from a
slightly weaker version of Proposition 5.
Lemma 6 ([5, Lemma 4]). Let N , k, and m be integers such that 2m ∤ k
and 1 ≤ N ≤ 2m and let θ be real. Then
√
|SN (k/m, θ)| = O( m),
where the implicit constant is absolute.

From Proposition 5 we can also deduce the following result, which will be
the key ingredient to our proofs of Theorem 1 and 2.
Lemma 7. Let m be a positive integer and let u be an integer such that
either u or m − u is in the set
(7)

Then
(8)

{w ∈ Z : m2/3 ≤ w ≤ m/2 − m2/3 }.

Sm−u (2/m, u/m) =

where the implicit constant is absolute.

r

m
+ O(m1/3 ),
2

Proof. Throughout the proof, all implicit constants are absolute. We first
prove the desired bound when u is in the set (7). This is an application of
Proposition 5 with N = m − u, x = 2/m, θ = u/m, so that M = 2 and
ǫ = −u/m and µ = 1. We have
1
2m
1
+
= 2 cot(πu/m) −
cot(πθ) − cot(πǫ) −
πθ πǫ
πu
= O(m1/3 ),
using that cot(πt) is nonnegative on (0, 1/2] and, for m ≥ 8,

cot(πu/m) ≤ cot πm−1/3
1

≤
sin πm−1/3
1
≤ m1/3 .
2
Now use the identity
erfc(−z) = 2 − erfc(z),
to obtain
2
E(x, θ) − E(x, −θ) = 2E(x, θ) − 2e−πiθ /x .
Since
S2 (−1/x, θ/x) = (−i)m (−1)u + 1,
we then find from Proposition 5 that
r
m
|SN (x, θ)| =
(−i)m (−1)u + E(x, θ) + O(m1/3 ).
2

APERIODIC CORRELATION OF SEQUENCE PAIRS

9

From the asymptotic expansion [12, (1.3) and (1.4)] of E(x, θ) we find that
√
2
x3/2
e−2πiθ /x−πi/4 x
≤ 2 3,
E(x, θ) −
πθ
2π θ
so that |E(x, θ)| is O(m−1/6 ) and (8) follows, as required.
Now assume that m − u is in the set (7). Put v = m − u and apply
Proposition 5 with N = v, x = 2/m, and θ = −v/m, so that M = 0 and
ǫ = v/m and µ = 1. Proceeding similarly as in the first case, we obtain
r
m −πiθ2 /x
e
− E(x, θ) + O(m1/3 ),
|SN (x, θ)| =
2
which again implies (8).



We conclude by proving the second parts of Theorems 1 and 2.
Proof of Theorem 1 (ii). For each u ∈ {0, 1, . . . , n − 1}, we have
|CXn ,Yn (u)| = |CXn ,Yn (−u)| =

n−u−1
X

e2πi(j

2 +ju)/n

.

j=0

Since the first and the last term in the sum are both equal to 1, we find that
n2 CDF(Xn , Yn ) = |Sn (2/n, 0)|2 + 2

n−1
X
u=1

|Sn−u (2/n, u/n)|2 .

Now use Lemma 7 to find that |Sn−u (2/n, u/n)|2 = n/2 + O(n5/6 ) when u
or n − u is in the set
{w ∈ Z : n2/3 ≤ w ≤ n/2 − n2/3 }

and use Lemma 6 to bound the remaining O(n2/3 ) values of |Sn−u (2/n, u/n)|2
by O(n). This gives
CDF(Xn , Yn ) = 1 + O(n−1/6 ),
as required.



Proof of Theorem 2 (ii). For each u ∈ {0, 1, . . . , 2n − 1}, we have
|CXn ,Yn (u)| = |CXn ,Yn (−u)| =

2n−u−1
X

(−1)ju eπi(j

2 +ju)/n

.

j=0

If u is odd, then the summands corresponding to j and 2n−u−j add to zero,
leaving the summand corresponding to j = 0. Therefore |CXn ,Yn (u)| = 1 for
each odd u satisfying |u| ≤ 2n − 1. Hence
(2n)2 CDF(Xn , Yn ) = |S2n (1/n, 0)|2 + 2

n−1
X
v=1

|S2n−2v (1/n, v/n)|2 + O(n).

10

CHRISTIAN GÜNTHER AND KAI-UWE SCHMIDT

Now use Lemma 7 to find that |S2n−2v (1/n, v/n)|2 = n + O(n5/6 ) when 2v
or 2n − 2v is in the set
{w ∈ Z : (2n)2/3 ≤ w ≤ n − (2n)2/3 }

and use Lemma 6 to bound the remaining O(n2/3 ) values of |S2n−2v (1/n, v/n)|2
by O(n). This gives
1
CDF(Xn , Yn ) = + O(n−1/6 ),
2
as required.

References
[1] M. Antweiler and L. Bömer, Merit factor of Chu and Frank sequences, IEE Electron.
Lett. 46 (1990), no. 25, 2068–2070.
[2] K. T. R. Boothby and D. J. Katz, Low correlation sequences from linear combinations
of characters, IEEE Trans. Inform. Theory 63 (2017), no. 10, 6158–6178.
[3] D. Chu, Polyphase codes with good periodic correlation properties, IEEE Trans. Inform. Theory IT-18 (1972), no. 4, 531–532.
[4] F. Fiedler, Small Golay sequences, Adv. Math. Commun. 7 (2013), no. 4, 379–407.
[5] H. Fiedler, W. Jurkat, and O. Körner, Asymptotic expansions of finite theta series,
Acta Arith. 32 (1977), no. 2, 129–146.
[6] J. Jedwab and K.-U. Schmidt, The merit factor of binary sequence families constructed from m-sequences, Finite fields: theory and applications, Contemp. Math.,
vol. 518, Amer. Math. Soc., Providence, RI, 2010, pp. 265–278.
[7] D. J. Katz, Aperiodic crosscorrelation of sequences derived from characters, IEEE
Trans. Inform. Theory 62 (2016), no. 9, 5237–5259.
[8] D. J. Katz. and E. Moore, Sequence pairs with lowest combined autocorrelation and
crosscorrelation, 2017, arXiv:1711.02229 [cs.IT].
P
Pn αm i m
[9] J. E. Littlewood, On polynomials n ±z m ,
e
z , z = eθi , J. London Math.
Soc. 41 (1966), 367–376.
[10] I. Mercer, Merit factor of Chu sequences and best merit factor of polyphase sequences,
IEEE Trans. Inform. Theory 59 (2013), no. 9, 6083–6086.
[11] D. J. Newman, An L1 extremal problem for polynomials, Proc. Amer. Math. Soc. 16
(1965), 1287–1290.
[12] R. B. Paris, An asymptotic expansion for the generalised quadratic Gauss sum revisited, J. Class. Anal. 5 (2014), no. 1, 15–24.
[13] M. P. Pursley and D. V. Sarwate, Bounds on aperiodic cross-correlation for binary
sequences, IEE Electron. Lett. 12 (1976), no. 12, 304–305.
[14] K.-U. Schmidt, On a problem due to Littlewood concerning polynomials with unimodular coefficients, J. Fourier Anal. Appl. 19 (2013), no. 3, 457–466.
[15]
, Sequences with small correlation, Des. Codes Cryptogr. 78 (2016), no. 1,
237–267.
[16] K.-U. Schmidt, J. Jedwab, and M. G. Parker, Two binary sequence families with large
merit factor, Adv. Math. Commun. 3 (2009), no. 2, 135–156.
[17] S. Stańczak and H. Boche, Aperiodic properties of generalized binary Rudin-Shapiro
sequences and some recent results on sequences with a quadratic phase function, Proc.
of Int. Zurich Seminar on Broadband Communications, IEEE, 2000, pp. 279–286.
Department of Mathematics, Paderborn University, Warburger Str. 100,
33098 Paderborn, Germany.
E-mail address: chriguen@math.upb.de, kus@math.upb.de

