On three conjectures of binary sequences with low odd-periodic autocorrelation

Abstract

This paper provides a complete answer to three conjectures of Parker about low odd-periodic autocorrelation of sixteen cyclotomic binary sequences in Parker (2001), and also gives new binary sequences with low odd-periodic autocorrelation.

1 Introduction

In applications like continuous-wave radar, digital communications and measurement, the desired information is extracted from the received signal using autocorrelation functions. Hence it is desirable to use sequences with perfect autocorrelation property, namely, the autocorrelation function sidelobes are all zero. Nevertheless, perfect sequences are hardly known (only for a few sequences with certain lengths). Sequences with low correlation are thus of significant importance and have found applications in digital communication systems, particularly in spread-spectrum systems [3, 4]. When applied in direct sequence code division multiple access (DS-CDMA) systems, the sequences’ odd correlation function affects the output of the correlator when the information symbols change over one integration interval, while their even correlation function affects the output of the correlator when the information symbols do not change [9, 12, 13]. For a comprehensive performance analysis of the system, both the even correlation and odd correlation properties should be taken into consideration.

During the last decades, a considerable amount of research has been conducted on the construction and application of sequences with low even-periodic correlation (see for instance [1, 15, 16] and references therein). On the other hand, the odd-periodic correlation property of sequences is less explored and so far only a few constructions have been introduced [6,7,8, 10, 17, 18]. In 1995, Lüke and Schotten [7] proposed a class of odd-periodic almost perfect binary sequences with period q + 1 and one zero element, where q is an odd prime power. By replacing the zero element by ± 1, binary sequences with the odd-periodic autocorrelation magnitude 2 were obtained. Lüke, Sarwate, and Hadinejad-Mahram [8] summarized binary sequences of even period with low odd-periodic autocorrelation, some of which were obtained by applying product method to m-sequences or Legendre sequences. They also showed that odd-periodic perfect binary sequences of period greater than 2 do not exist, which was also derived from a nonexistence result on relative difference sets [11] where the odd-periodic autocorrelation was studied in the name of negaperiodic auto-correlation. Recently some new interleaved binary sequences of even period with optimal odd-periodic autocorrelation were obtained in [17, 18].

By using cyclotomies of order 2 and 4 with respect to an odd prime p, Parker in [10] presented a novel method to construct binary sequences of period 2p with the odd-periodic autocorrelation equal to 0,± 2 and he also gave three conjectures on odd-periodic autocorrelation of sixteen binary sequences of length 4p. In this paper, we will present an interleaving-based construction of sequences that covers the sixteen sequences in [10] and determine the odd-periodic autocorrelation of those sequences by employing some results on cross-correlation of cyclotomic sequences of order 4, which provides a complete answer to Parker’s conjectures. In addition, we further explore the proposed construction and present new binary sequences with low odd-periodic autocorrelation.

The remainder of this paper is organized as follows: Section 2 introduces some preliminaries and recalls the three conjectures by Parker [10]. In Section 3 we propose a construction of sequences based on the interleaving technique, determine the odd-periodic autocorrelation of those conjectured sequences and present new interleaved sequences with low nearly optimal odd-periodic autocorrelation. Section 4 concludes the work of this paper.

2 Preliminaries

2.1 Autocorrelation functions of periodic sequences

Let N be a positive integer. Given two binary sequences $a=(a(i))_{i=0}^{N-1}$ and $b=(b(i))_{i=0}^{N-1}$ of same period N, where a(i),b(i) ∈{0,1}, the (even)-periodic correlation function and the odd-periodic correlation function of a and b at a shift τ are defined as

$$ R_{a,b}(\tau)=\sum\limits_{i=0}^{N-1}(-1)^{a(i)+b(i+\tau)} $$

(1)

and

$$ \hat{R}_{a,b}(\tau)=\sum\limits_{i=0}^{N-1}(-1)^{a(i)+ b(i+\tau)+\lfloor{i+\tau\over N}\rfloor} $$

(2)

respectively, where ⌊x⌋ is the largest integer smaller than or equal to x. When the sequences a and b are identical, R_a,b(τ) and $\hat {R}_{a,b}(\tau )$ are called (even)-periodic autocorrelation function (PACF) and odd-periodic autocorrelation function (OACF), and simply denoted as R_a(τ) and $\hat {R}_{a}(\tau )$, respectively. For a binary sequence a of period N, it is desirable that the out-of-phase PACF (or OACF) magnitude $\max \limits _{\tau \neq 0}|R_{a}(\tau )|$ (or $\max \limits _{\tau \neq 0}|\hat {R}_{a}(\tau )|$) as low as possible. An important correlation metric between periodic sequences is the aperiodic autocorrelation function (AACF), defined as

$$ A_{a}(\tau)=\sum\limits_{i=0}^{N-1-\tau}(-1)^{a(i)+a(i+\tau)}, \quad 0\le \tau < N. $$

(3)

The AACF of a binary sequence can be expressed as the sum and difference of its PACF and OACF depending the sign of the shift in consideration [10]. Sequences used in digital communications systems are usually desired to have the out-of-phase magnitudes of these autocorrelation functions as low as possible [4].

Given a periodic binary sequence a, when the period N is odd, the OACF of the sequence a satisfies $\hat {R}_{a}(\tau ) = (-1)^{\tau }R_{a^{\prime }}(\tau )$, where $a^{\prime }$ is a sequence defined as $a^{\prime }(i) = (a(i)+i) \pmod {2}$. Hence low OACF binary sequences of odd periods can be trivially obtained by transforming low PACF binary sequences, on which there is a large amount of research results [15, 16]. When the period N is even, a relation between the OACF and PACF of binary sequences can be established as follows: one constructs a 2N-period binary sequence u := a||(a ⊕ 1), where a ⊕ 1 is the binary complement sequence of a, and || denotes the concatenation of two sequences a and a ⊕ 1; then

$$ \hat{R}_{a}(\tau) =\frac{1}{2}{R_{u}(\tau)}, \quad 0 \leq \tau < N. $$

(4)

This relation indicates that those 2N-periodic binary sequences having the form of a||(a ⊕ 1) and low PACF would produce N-periodic binary sequences with low OACF. However, known sequences with low PACF usually do not have the form of a||(a ⊕ 1). In general, sequences that have even period and low OACF are not well-explored.

2.2 Cyclotomy

The word cyclotomy means “circle-division” and refers to the problem of dividing the circumference of the unit circle into a given number of arcs of equal lengths. The rather remarkable fact that the cyclotomic numbers actually represent the two-character distributions and autocorrelation property of some cyclotomic sequences has motivated a lot of research on the design of sequence with low correlation [2]. In this subsection we recall some basic definitions and results.

Let p = df + 1 be an odd prime and α be a primitive element in the multiplicative group of the residue ring $\mathbb {Z}_{p}=\{ a \pmod {p} : a \in \mathbb {Z}\}$. Denote the multiplicative subgroup generated by α^d as D₀, then the coset decomposition of $\mathbb {Z}_{p}^{*}=\mathbb {Z}_{p}\setminus \{0\}$ with respect to the subgroup D₀ is $\mathbb {Z}_{p}^{*}= \bigcup _{i=0}^{d-1}D_{i}$, where

$$ D_{i} = \alpha^{i}D_{0}= \{ \alpha^{i+jd} | 0\leq j <f \}, \quad i=0, 1, \cdots, d-1. $$

The cosets D₀,D₁,⋯ ,D_d− 1 are called the classical cyclotomic classes of orderd with respect to p. For any pair of i,j with 0 ≤ i,j < d, the cyclotomic number of order d is defined as

$$ (i,j) = |(D_{i}+1)\cap D_{j}|. $$

The elementary facts about cyclotomic numbers and the values of cyclotomic numbers for small orders d have been intensively studied in the literature (see, for example, [2]). The known results on cyclotomic numbers significantly facilitate the investigation of correlation properties of cyclotomic sequences. Below we recall the cyclotomic numbers of order 4 that will be used in Section 3.

Lemma 1 (2)

Let p = 4f + 1 = x² + 4y² and (i,j) be cyclotomic numbers of order 4. (i) For odd f, the sixteen cyclotomic numbers are given by Table 1 with

$$ \begin{array}{c} A=\frac{n-7+2x}{16}, B=\frac{n+1+2x-8y}{16}, C=\frac{n+1-6x}{16}, D=\frac{n+1+2x+8y}{16}, E=\frac{n-3-2x}{ 16}. \end{array} $$

(ii) For even f, the sixteen cyclotomic numbers are given by Table 1 with

$$ \begin{array}{c} A=\frac{n-11-6x}{16}, B=\frac{n-3+2x+8y}{16}, C=\frac{n-3+2x}{ 16}, D=\frac{n-3+2x-8y}{16}, E=\frac{n+1-2x}{ 16}. \end{array} $$

Table 1 The cyclotomic numbers of order 4

2.3 Three conjectures of Parker

Parker proposed a novel cyclotomic construction of binary sequences of period 2p with (conjectured) optimal OACF equal to 0,± 2 [10], where he also proposed three conjectures on the OACF of sixteen binary sequences with period 4p. Below we recall conjectured sequences in [10] by describing their characteristic sets, namely, the set $C = \{i\in \mathbb {Z}_{N} | a(i) = 1 \}$ for each periodic binary sequence $(a(i))_{i=0}^{N-1}$.

For an odd prime p = df + 1 and a positive integer r₁ with $\gcd (r_{1}, p)=1$, let r = 2r₁,N = r₁p and let D_i = {α^i+jd|0 ≤ j < f}, i = 0,1,⋯ ,d − 1, be cyclotomic classes of order d with respect to p. By the Chinese Remainder Theorem (CRT), the residue ring $\mathbb {Z}_{rp}$ is isomorphic to $\mathbb {Z}_{r}\times \mathbb {Z}_{p}$. Thus the residue ring

$$ \begin{array}{rcl} \mathbb{Z}_{2N} &=& (\mathbb{Z}_{r}\times \{0\}) \cup (\mathbb{Z}_{r}\times \mathbb{Z}^{*}_{p}) \\&=& (\mathbb{Z}_{r}\times \{0\})\cup (\mathbb{Z}_{r}\times \cup_{i=0}^{d-1}D_{i}) \end{array} $$

The characteristic sets of sequences in [10] were represented in the form as

$$ \begin{array}{rcl} C=(G \times \{0\}) \cup \bigcup\limits_{n=0}^{r-1} (\{n\} \times \bigcup_{i\in T_{n}}D_{i}), \end{array} $$

(5)

where $G\subseteq \mathbb {Z}_{r}$ and $T_{n}\subseteq \mathbb {Z}_{d}$ for 0 ≤ n < r. For a binary sequence u of period 2N with the form u = t||(t ⊕ 1), its characteristic set C satisfies $\mathbb {Z}_{2N} \setminus C= \{x+N \pmod {2N} | x \in C\}$. By this equality, the characteristic set C was compactly denoted in [10] as $(G^{\prime }, T_{0}, \cdots , T_{r_{1}-1}),$ from which one derives

$$ G=G^{\prime} \cup \{r_{1}+g | g\in \mathbb{Z}_{r_{1}}\setminus G^{\prime}\} \text{ and } T_{n+r_{1}}=\mathbb{Z}_{d}\setminus T_{n} \text{ for }0\leq n<r_{1}. $$

(6)

Let p = 4f + 1 be an odd prime, α be a primitive element, and D₀,D₁,D₂,D₃ be the cyclotomic classes of order 4 respective to p. In [10] sixteen sequences were proposed and their OACFs are conjectured as follows.

Conjecture 1

Let p = 4f + 1 be a prime of the form (n² + 1)/2 with f even. Define four binary sequences u₁,u₂,u₃,u₄ of period 8p with characteristic sets given in Table 2, respectively. Then there exist α and α^− 1 such that the sequence v_i derived from u_i = v_i||(v_i ⊕ 1), i = 1,2,3,4, have near-optimal five-valued out-of-phase odd-periodic autocorrelation {0,± 2,± 4} or {0,± 4,± 18}, respectively.

Conjecture 2

Let p = 4f + 1 be a prime of the form (n² + 1)/2 with f odd. Define four binary sequences u₅,u₆,u₇,u₈ of period 8p with characteristic sets given in Table 2, respectively. Then there exist α and α^− 1 such that the sequence v_i derived from u_i = v_i||(v_i ⊕ 1), i = 5,6,7,8, have near-optimal five-valued out-of-phase odd-periodic autocorrelation {0,± 2,± 4} or {0,± 2,± 4,± 22}, respectively.

Conjecture 3

Let p = 4f + 1 be a prime of the form n² + 4. Define four binary sequences u₉,⋯ ,u₁₆ of period 8p with characteristic sets given in Table 3, respectively. Then there exist α and α^− 1 such that the sequence v_i derived from u_i = v_i||(v_i ⊕ 1), i = 9,⋯ ,16, have near-optimal five and seven-valued out-of-phase odd-periodic autocorrelation {0,± 2,± 4} or {0,± 2,± 4,± 12}, respectively.

At the end of this subsection, we give an example to demonstrate how the characteristic set of a sequence u is derived from its compact form in Tables 2 and 3.

Example 1

We choose a representative sequence u₁₃ from Table 3. From the notation we have $(G^{\prime }, T_{0}, T_{1}, T_{2}, T_{3}) = (\{0,3\}, \{0, 1\}, \{0,2\},\{0,2\},\{0, 1\})$. It follows from (6) that $G = G^{\prime } \cup \{4+g | g\in \mathbb {Z}_{4} \setminus G^{\prime }\} = \{0, 3\} \cup \{5, 6\} = \{0, 3, 5, 6\}$ and (T₄,T₅,T₆,T₇) = ({2,3},{1,3},{1,3},{2,3}). According to (5), the characteristic set

$$ \begin{array}{@{}rcl@{}} C_{13}&= & \{ (0, 0), (3,0), (5, 0), (6,0)\} \\& &\cup (0, D_{0}\cup D_{1})\cup (1, D_{0}\cup D_{2}) \cup (2, D_{0}\cup D_{2})\cup (3, D_{0}\cup D_{1}) \\& &\cup (4, D_{2}\cup D_{3})\cup (5, D_{1}\cup D_{3}) \cup (6, D_{1}\cup D_{3})\cup (7, D_{2}\cup D_{3}), \end{array} $$

where for each $(k_{1},k_{2})\in \mathbb {Z}_{8}\times \mathbb {Z}_{p}$, a unique element $z\in \mathbb {Z}_{8p}$ is derived from the equations

$$ \left\{\begin{array}{ll} z\equiv k_{1} \pmod{8} \\ z\equiv k_{2} \pmod{p} \end{array}\right. $$

by the Chinese Remainder Theorem [10].

2.4 Interleaved sequences

Gong in [5] introduced the concept of interleaved sequences, which are associated with a polynomial f over finite fields and a positive integer m. Some basic properties of interleaved sequences over finite fields and their applications were intensively studied there.

Definition 1

[5] Let f(z) be a polynomial over the finite field GF(q) of degree n with f(0)≠ 0 and m be a positive integer. A sequence $u=(u(i))_{i=0}^{\infty }$ is called an (f(z),m)-interleaved sequence if f(x) is a common characteristic polynomial of its m-decimated sequences:

$$ u_{j}^{(m)} = (u(im+j))_{i=0}^{\infty}, \quad 0\leq j <m, $$

(7)

where $u_{j}^{(m)}$ are called component sequences of u.

Denote by per(f) the period of the polynomial f(z), i.e., the least integer e such that f(z) divides (z^e − 1). By the definition, it is easily verified that the period of an (f(z),m)-interleaved sequence u divides m ⋅ per(f). When f(z) is an irreducible polynomial, the elements of an (f(z),m)-interleaved sequence u can represented as $u(im+j) ={\operatorname {Tr}^{n}_{1}}(\gamma _{j}\alpha ^{i}),$ where $0\leq j< m, i=0, 1, \dots$, γ_j ∈ GF(qⁿ), and α is a root of f(x) in the extension field GF(qⁿ) and ${\operatorname {Tr}^{n}_{1}}(z)=z+z^{q}+\cdots +z^{q^{n-1}}$. In particular, if f(z) is a primitive polynomial, the sequence u is called a primitive interleaved sequence. As a matter of fact, the element of a primitive interleaved sequence u can be rewritten as

$$ u(im+j) ={\operatorname{Tr}^{n}_{1}}(\alpha^{i+e_{j}}), \quad 0\leq i < q^{n}-1, 0\leq j< m, $$

(8)

where e_j is defined as the exponent of γ_j with the base α, namely, e_j = k if γ_j = α^k and $e_{j}=\infty$ if γ_j = 0. It was shown that primitive interleaved sequences include a large number of well-known good sequences, such as multiplexed sequences, clock-controlled sequences, GMW-sequences, and cascaded GMW-sequences [5].

Denote N = qⁿ − 1 and express a primitive interleaved sequence u in a matrix A with $A[i, j] = u(im+j) = {\operatorname {Tr}^{n}_{1}}(\alpha ^{i+e_{j}})$, where A[i,j] is the entry in the i-th row and j-column in A. It is easily verified that each column vector of the matrix A is either a phase shift of the sequence $a = ({\operatorname {Tr}^{n}_{1}}(\alpha ^{i}))_{i=0}^{q^{n}-2}$ or a zero sequence. The column vectors $A_{j} = L^{e_{j}}(a), j=0,1,\cdots , m-1$, correspond to the component sequences u_j of u and A is called the matrix form of u. The matrix form of an interleaved sequence appears to nicely capture the structure of the sequence and turns out to be a powerful tool in investigating the autocorrelation property of the sequence.

The matrix form of interleaving sequences was later extended to more general cases. For a family $\mathcal {A}=\{ (a_{j}(i))_{i=0}^{N-1} | j= 0, 1, \cdots , m-1 \}$ of N-periodic sequences, the interleaved sequence u of $\mathcal {A}$, denoted by u = I(a₀,a₁,⋯ ,a_m− 1), is given by

$$ u(im+j) = a_{j}(i), \quad 0\leq i < N-1,0\leq j < m. $$

The periodic autocorrelation of an interleaved sequence u = I(a₀,a₁,⋯ ,a_m− 1) can be expressed in terms of its building sequences as in the following lemma.

Lemma 2

Let u = I(a₀,a₁,⋯ ,a_m− 1) be the interleaved sequence from a family $\mathcal {A}=\{ (a_{j}(i))_{i=0}^{N-1} | j= 0, 1, \cdots , m-1 \}$ of N-periodic sequences. Then its periodic autocorrelation function is given by

$$ R_{u}(\tau_{1}m+\tau_{2})=\sum\limits_{j=0}^{m-\tau_{2}-1}R_{a_{j},a_{j+\tau_{2}}}(\tau_{1})+\sum\limits_{j=m-\tau_{2}}^{m-1}R_{a_{j},a_{j+\tau_{2}-m}}(\tau_{1}+1), $$

(9)

where 0 ≤ τ₁ < N and 0 ≤ τ₂ < m.

3 Interleaved sequences with low OACF

In this section, we will propose a generic construction of binary sequences by means of the interleaving technique, which covers all the sequences given in Conjectures 1 - 3. The interleaving representation helps us better understand the structure of the sequences and investigate their autocorrelation property in a more lucid manner, which leads to comprehensive answers to Conjectures 1 -3. In addition, based on the generic construction, we will present more binary sequences with low odd-periodic autocorrelation.

3.1 Main construction

This subsection presents a generic construction of interleaved binary sequences u of the form u = v||(v ⊕ 1) with period 2N = 2r₁p, where r₁ is a positive integer co-prime to p.

Construction 1

Let p = 4f + 1 = x² + 4y². Let $\mathcal {A}$ be a family of r = 2r₁ sequences $a_{0}, a_{1}, \cdots , a_{2r_{1}-1}$ of period p such that $a_{j+r_{1}} = a_{j}$ for 0 ≤ j < r₁. Let b be a binary sequence of length 2r₁ satisfying b(j + r₁) = b_j ⊕ 1 and e = (e₀,⋯ ,e_r− 1) be a sequence defined by e_j = j/r (mod p), where 0 ≤ j < r. An interleaved binary sequence u of period 2N = rp is defined by

$$ u = I (\bar{a}_{0}, \bar{a}_{1}, \cdots, \bar{a}_{r-1}) \text{ with } \bar{a}_{j}= L^{e_{j}}(a_{j}) \oplus b(j) , $$

where $L^{e_{j}}(a_{j})$ denotes the left circular shift of a_j by e_j position(s) for 0 ≤ j < r.

Before discussing properties of the interleaved sequences in Construction 1, we first give a simple example to demonstrate how an interleaved sequence in Construction 1 is derived.

Example 2

Let p = 5 and r = 2r₁ = 4. Let $\mathcal {A}$ be a family of sequences

$$a_{0}= (01101), a_{1}=(10101), a_{2}= (01101), a_{3}=(10101)$$

and b = (0110). Since r^− 1 (mod p) = 4, the sequence e is given by e = (0432). It follows that

$$ (\bar{a}_{0},\bar{a}_{1}, \bar{a}_{2}, \bar{a}_{3}) = \left( \begin{array}{lllll} 0011\\ 1000\\ 1111\\ 0001\\ 1100 \end{array}\right). $$

Hence the binary sequence u in Construction 1 is given by

$$ u = (00111000111100011100). $$

Below we discuss some properties of the sequences u defined in Construction 1.

Lemma 3

Let u be a sequence of period 2N = 2r₁p defined as in Construction 1. Then u(k + N) = u(k) ⊕ 1 for any integer k with 0 ≤ k < N.

Proof

By the definition of u, we have

$$ u(k) = u(ir+j) = \bar{a}_{j}(i) = (L^{e_{j}}(a_{j}) \oplus b(j))(i) = a_{j}(i+e_{j}(\text{mod} p)) + b(j) $$

for any k = ir + j with 0 ≤ i < p and 0 ≤ j < r. Then for any k = ir + j with j < r₁,

$$ \begin{array}{rcl} &&u(k+N)\\ &=& u\left( \left( i+\frac{p-1}{2}\right)r + j + r_{1}\right) = a_{j+r_{1}}(i+\frac{p-1}{2}+e_{j+r_{1}}(\text{mod} p)) + b(j+r_{1}) \\&=& a_{j}(i+e_{j}(\text{mod} p)) + b(j) \oplus 1 \\&=& u(k) \oplus 1, \end{array} $$

and for any k = ir + j with r₁ ≤ j < p, we get

$$ \begin{array}{rcl} &&u(k+N)\\ &=& u\left( \left( i+\frac{p+1}{2}\right)r + j - r_{1}\right) = a_{j-r_{1}}\left( i+\frac{p+1}{2}+e_{j-r_{1}}(\text{mod} p)\right) + b(j-r_{1}) \\&=& a_{j}(i+e_{j}(\text{mod} p)) + b(j) \oplus 1 \\&=& u(k) \oplus 1. \end{array} $$

□

Lemma 4

Let u be a sequence of period 2N = 2r₁p defined in Construction 1. Then the periodic autocorrelation function

$$ R_{u}(\tau_{1}r + \tau_{2} ) = 2\sum\limits_{j=0}^{r_{1}-1}(-1)^{b(j)+b(j+\tau_{2})}R_{a_{j}, a_{j+\tau_{2}}}(\tau_{1}+e_{\tau_{2}}), $$

where 0 ≤ τ₁ < p, 0 ≤ τ₂ < r, and the index j + τ₂ is taken modulo r.

Proof

For a shift τ = τ₁r + τ₂ with 0 ≤ τ₁ < p and 0 ≤ τ₂ < r, By the definition of u and (9) we have the periodic autocorrelation function

$$ \begin{array}{@{}rcl@{}} &&R_{u}(\tau_{1}r + \tau_{2})\\ & = & \sum\limits_{j=0}^{r-1-\tau_{2}}R_{\bar{a}_{j},\bar{a}_{j+\tau_{2}}}(\tau_{1})+\sum\limits_{j=r-\tau_{2}}^{r-1}R_{\bar{a}_{j},\bar{a}_{j+\tau_{2}-r}}(\tau_{1}+1) \\&=&\sum\limits_{j=0}^{r-1-\tau_{2}}(-1)^{b(j)+b(j+\tau_{2})}\sum\limits_{i=0}^{p-1}(-1)^{a_{j}(i+e_{j})+a_{j+\tau_{2}}(i+e_{j}+e_{\tau_{2}}+\tau_{1})} \\ && + \sum\limits_{j=r-\tau_{2}}^{r-1}(-1)^{b(j)+b(j+\tau_{2}-r)}\sum\limits_{i=0}^{p-1}(-1)^{a_{j}(i+e_{j})+a_{j+\tau_{2}-r}(i+e_{j}+e_{\tau_{2}}-1+\tau_{1}+1)} \\&=&\sum\limits_{j=0}^{r-1-\tau_{2}}(-1)^{b(j)+b(j+\tau_{2})}\sum\limits_{i=0}^{p-1}(-1)^{a_{j}(i)+a_{j+\tau_{2}}(i+e_{\tau_{2}}+\tau_{1})} \\ && + \sum\limits_{j=r-\tau_{2}}^{r-1}(-1)^{b(j)+b(j+\tau_{2}-r)}\sum\limits_{i=0}^{p-1}(-1)^{a_{j}(i)+a_{j+\tau_{2}-r}(i+e_{\tau_{2}}+\tau_{1})} \\& =& 2\sum\limits_{j=0}^{r_{1}-1}(-1)^{b(j)+b(j+\tau_{2})}R_{a_{j}, a_{j+\tau_{2}}}(\tau_{1}+e_{\tau_{2}}), \end{array} $$

(10)

where the last equality sign holds due to the fact that $a_{r_{1}+j}=a_{j}$ and b(j + r₁) = b(j) ⊕ 1 for 0 ≤ j < r₁. □

3.2 Answers to conjectures 1 - 3

Let s_i, 1 ≤ i ≤ 6, denote the sequences that admit

$$ \begin{array}{@{}rcl@{}} &&C_{1}=D_{0}\cup D_{1}, C_{2}=D_{0}\cup D_{2}, C_{3}=D_{0}\cup D_{3},\\ &&C_{4}=D_{1}\cup D_{2}, C_{5}=D_{1}\cup D_{3}, C_{6}=D_{2}\cup D_{3} \end{array} $$

(11)

as their characteristic set, respectively. We observe that the 16 conjectured sequences can be expressed in the form of interleaved sequences as in Construction 1, where the column sequences are cyclic shifts of a_j ⊕ b(j) for a_j taken from {s₁,s₂,⋯ ,s₆} and certain binary sequence b. This enables us to investigate the OACF of the sequences in Conjectures 1 - 3 in terms of even-periodic cross-correlations between s_i and s_j for 1 ≤ i,j ≤ 6.

In the following we shall deal with the sequence u₁ in Conjecture 1 in detail. The other 15 sequences can be handled in an exactly same manner, so we will present the result of them without proof.

3.2.1 Interleaved representation of u₁ = v₁||(v₁ ⊕ 1)

We take the sequence u₁ as an representative. By Table 2 and (6), we obtain

$$ \begin{array}{lll} C_{u_{1}} =& \{(2, 0), (4, 0), (5, 0), (7, 0)\} \\ & \cup (0, C_{3}) \cup (1, C_{4}) \cup (2, C_{1})\cup (3, C_{1}) \\ & \cup (4, C_{4}) \cup (5, C_{3}) \cup (6, C_{6})\cup (7, C_{6}). \end{array} $$

For the interleaved representation for the sequence u₁, it suffices to discuss the position in a p × 8 matrix A with A(i,j) = i8 + j that corresponds to each element in $C_{u_{1}}$. By the Chinese Remainder Theorem, we have the following 1-to-1 correspondence between $\mathbb {Z}_{8}\times \mathbb {Z}_{p}$ and $\mathbb {Z}_{8p}$:

$$ (k_{1}, k_{2}) \longleftrightarrow k_{1} + 8((k_{2}-k_{1})\text{Inv}_{p}(8)\pmod{p}), $$

(12)

where Inv_p(8) is the inverse of 8 modulo p.

Table 2 The characteristic sets in Conjectures 1 and 2

Table 3 The characteristic sets in Conjecture 3

From (12) we can see that if we arrange elements of $C_{u_{1}}$ in an p × 8 matrix $\mathcal {A}$, then an element (k₁,k₂) naturally corresponds to the entry ((k₂ − k₁)Inv_p(8) (mod p),k₁) in $\mathcal {A}$. Moreover, the sequence can be expressed as

$$ u_{1} = I(\bar{a}_{0}, \bar{a}_{1}, \bar{a}_{2}, \bar{a}_{3}, \bar{a}_{4}, \bar{a}_{5}, \bar{a}_{6}, \bar{a}_{7})$$

with $\bar {a}_{j} = L^{e_{j}}(a_{j}) \oplus b(j)$ for j = 0,1,⋯ ,7 as in Construction 1, where the characteristic set of a_j is derived from the subset of $C_{u_{1}}$ in the corresponding column. For instance, the subset (0,C₃) of $C_{u_{1}}$ yields a sequence a₀ with characteristic set $\left \{k_{2}\text {Inv}_{p}(8) : k_{2} \in C_{3}\right \}$; and the subset {(2,0)}∪ (2,C₁) yields a sequence a₂ with characteristic set $\{0\}\cup \left \{k_{2}\text {Inv}_{p}(8) : k_{2} \in C_{1} \right \}$, whose complementary sequence a₂ ⊕ 1 has characteristic set $\left \{k_{2}\text {Inv}_{p}(8) : k_{2} \in C_{6} \right \}$; Assume Inv_p(8) belongs to D_κ, which depends on the explicit primitive element α, then Inv_p(8) ⋅ D_i = D_i+κ and

Table 4

Therefore, u₁ can be expressed as $u_{1} = I(\bar {a}_{0}, \bar {a}_{1}, \bar {a}_{2}, \bar {a}_{3}, \bar {a}_{4}, \bar {a}_{5}, \bar {a}_{6}, \bar {a}_{7}),$ where the sequences $\bar {a}_{j} = L^{e_{j}}(a_{j}) \oplus b(j)$ for 0 ≤ j < 8 with $e_{j}=\frac {j}{8} \pmod {p}$, b = (0,0,1,0,1,1,0,1) and a_j’s given by the following table

Table 5

It appears that value of κ, which depends on explicit primitive element α, affects the resulting sequence u₁ generated from given sequences a₁,⋯ ,a₈ and $b=(b(j))_{i=0}^{7}$. In next subsection, we will show that the PACFs of the sequences u₁ deduced from different values of κ are indeed identical.

3.2.2 Odd-periodic autocorrelation of v₁

As in Lemma 4, the autocorrelation of u₁ at a shift τ = 8τ₁ + τ₂ is given by

$$ R_{u_{1}}(\tau ) = 2\sum\limits_{j=0}^{3}(-1)^{b(j)+b(j+\tau_{2})}R_{a_{j}, a_{j+\tau_{2}}}(\tau_{1}+e_{\tau_{2}}), $$

where 0 ≤ τ₁ < p and 0 ≤ τ₂ < 8. According to b = (0,0,1,0,1,1,0,1), we define four functions:

$$ \begin{array}{lllllllllllllllll} g_{0}(\tau_{1})&\triangleq& &R_{a_{0}}(\tau_{1})&+&R_{a_{1}}(\tau_{1})&+&R_{a_{2}}(\tau_{1})&+&R_{a_{3}}(\tau_{1}),\\ g_{1}(\tau_{1})&\triangleq& &R_{a_{0},a_{1}}(\tau_{1})&-&R_{a_{1},a_{2}}(\tau_{1})&-&R_{a_{2},a_{3}}(\tau_{1})&-&R_{a_{3},a_{0}}(\tau_{1}),\\ g_{2}(\tau_{1})&\triangleq& -& R_{a_{0},a_{2}}(\tau_{1})&+&R_{a_{1},a_{3}}(\tau_{1})&+&R_{a_{2},a_{0}}(\tau_{1})& - &R_{a_{3},a_{1}}(\tau_{1}),\\ g_{3}(\tau_{1})&\triangleq& &R_{a_{0},a_{3}}(\tau_{1})&- &R_{a_{1},a_{0}}(\tau_{1})&+&R_{a_{2},a_{1}}(\tau_{1})&+&R_{a_{3},a_{2}}(\tau_{1}). \end{array} $$

Since a_j = a_j+ 4 for 0 ≤ j < 4, it follows that

$$ R_{u_{1}}(8\tau_{1}+\tau_{2}) = \left\{\begin{array}{ll} 2g_{\tau_{2}}(\tau_{1} + \tau_{2}/8), & \text{ if } 0\leq \tau_{2} <4,\\ -2g_{\tau_{2}-4}(\tau_{1} + \tau_{2}/8), & \text{ if } 4\leq \tau_{2} <8. \end{array}\right. $$

The above discussion indicates that each sequence a_j, 1 ≤ j ≤ 8, belongs to {s₁,s₃,s₄,s₆}. For an odd prime p = 4f + 1 = x² + 4y², the known results on periodic auto- and cross-correlation of the sequences s₁,s₃,s₄ and s₆ can be used to examine the autocorrelation of u₁. Indeed, the correlation of these sequences are given in terms of the cyclotomic number of order 4 as follows.

Lemma 5 ([14])

Let p = 4f + 1 = x² + 4y² and D₀,⋯ ,D₃ be the cyclotomic cosets of order 4. Let s_i and s_j be two sequences defined by character sets $C_{i} = D_{i_{1}}\cup D_{i_{2}}$ and $C_{j} = D_{j_{1}}\cup D_{j_{2}}$ respectively, where (i₀,i₁,i₂,i₃) and (j₀,j₁,j₂,j₃) are two permutations of {0,1,2,3}. Then the (even-) periodic cross-correlation between s_i and s_j at a shift τ ∈ D_k is given by

$$ \begin{array}{@{}rcl@{}} R_{s_{i},s_{j}}(\tau)&=&(-1)^{s_{i}(0)+s_{j}(\tau)}+(-1)^{s_{i}(p-\tau)+s_{j}(0)}+{\varDelta}_{s_{i},s_{j}}(\tau)\\ &=&(-1)^{s_{j}(\tau)}+(-1)^{s_{i}(p-\tau)}+{\varDelta}_{s_{i},s_{j}}(\tau) \end{array} $$

(13)

where

$$ \begin{array}{@{}rcl@{}} {\varDelta}_{s_{i},s_{j}}(\tau) &=& ~~(j_{0}-k,i_{0}-k)+(j_{1}-k,i_{0}-k)\\ &&-(j_{2}-k,i_{0}-k)-(j_{3}-k,i_{0}-k)\\ &&+(j_{0}-k,i_{1}-k)+(j_{1}-k,i_{1}-k)\\ &&-(j_{2}-k,i_{1}-k)-(j_{3}-k,i_{1}-k)\\ &&-(j_{0}-k,i_{2}-k)-(j_{1}-k,i_{2}-k)\\ &&+(j_{2}-k,i_{2}-k)+(j_{3}-k,i_{2}-k)\\ &&-(j_{0}-k,i_{3}-k)-(j_{1}-k,i_{3}-k)\\ &&+(j_{2}-k,i_{3}-k)+(j_{3}-k,i_{3}-k). \end{array} $$

(14)

By the above lemma, the auto- and cross-correlation of the sequences s_i, 1 ≤ i ≤ 6, is comprehensively investigated and listed in [14, Tables A3 and A4].

Assume (s_i,s_j) and $(s_{i^{\prime }}, s_{j^{\prime }})$ are two pairs of sequences defined as in Lemma 5 with

$$ (D_{i^{\prime}_{0}}, D_{i^{\prime}_{1}}, D_{i^{\prime}_{2}}, D_{i^{\prime}_{3}} ) = (D_{i_{0}+\kappa}, D_{i_{1}+\kappa }, D_{i_{2}+\kappa}, D_{i_{3}+\kappa}) $$

and

$$ (D_{j^{\prime}_{0}}, D_{j^{\prime}_{1}}, D_{j^{\prime}_{2}}, D_{j^{\prime}_{3}} ) = (D_{j_{0}+\kappa}, D_{j_{1}+\kappa }, D_{j_{2}+\kappa}, D_{j_{3}+\kappa}). $$

By (13) and (14), we have

$$ \begin{array}{@{}rcl@{}} R_{s_{i^{\prime}},s_{j^{\prime}}}(\tau) &=&(-1)^{s_{j^{\prime}}(\tau)}+(-1)^{s_{i^{\prime}}(p-\tau)}+{\varDelta}_{s_{i^{\prime}},s_{j^{\prime}}}(\tau) \\&=& (-1)^{s_{j}(8\tau)}+(-1)^{s_{i}(p-8\tau)}+{\varDelta}_{s_{i},s_{j}}(8\tau) \\&=& R_{s_{i},s_{j}}(8\tau). \end{array} $$

(15)

This indicates that the correlation distribution of the sequence pair $(s_{i^{\prime }}, s_{j^{\prime }})$ is exactly the same as that of the sequence pair (s_i,s_j). Therefore, in the investigation of $R_{u_{1}}(\tau )$, it is sufficient to consider the case κ = 0 since other cases κ = 1,2,3 will result in the same distribution.

In the case κ = 0, we have (a₀,a₁,a₂,a₃) = (s₃,s₄,s₆,s₁). From Table A4 in [14] it follows that

Table 6

Hence the out-of-phase OACF of the sequence v₁ derived from u₁ = v₁||(v₁ ⊕ 1) satisfies $\hat {R}_{v_{1}}(\tau )\in \{0,\pm 2, \pm 4, \pm (2x+4y)\}$.

3.2.3 Odd-periodic autocorrelation of v_i’s

By using the same method, the interleaved representation of the sequences t_i’s in Conjectures 1 - 3 can be determined. The sequences (a₀,a₁,a₂,a₃) and b for them is given in the following table.

Table 7

Based on the above table, the odd-periodic autocorrelation for all the sequences v_i’s can be calculated similarly to that of v₁. We have the following answer to Parker’s conjectures:

Theorem 1

Let p = 4f + 1 = x² + 4y². Let u_i = v_i||(v_i ⊕ 1), i = 1,2,⋯ ,16, be the sequences defined in Conjectures 1 - 3. Then the odd-periodic autocorrelation of v_i’s, which depends on the values of x and y, is given as in Table 4. In particular, when the pair (x,y) satisfies the condition listed in Table 4, we have $\hat {R}_{v_{i}} \in \{0, \pm 2, \pm 4\}$.

Table 4 Odd-Periodic Autocorrelation of sequences v_i, 1 ≤ i ≤ 16, for κ = 0,1,2,3

3.3 New low-correlation binary sequences from cyclotomic sequences

From the investigation of conjectured sequences v_i’s in the previous section, it is natural to raise a question: can we obtain more binary sequences with OACF in {0,± 2,± 4} from cyclotomic sequences s₁,⋯ ,s₆? In this subsection, we will study this question in a comprehensive manner and present more low-correlation binary sequences from cyclotomic sequences.

Given an odd prime p = 4f + 1 and r₁ = 4, it is easy to see that an interleaved sequence $u=v||(v\oplus 1)=I(\bar {a}_{0}, \bar {a}_{1}, \bar {a}_{2},\bar {a}_{3},\bar {a}_{4},\bar {a}_{5},\bar {a}_{6},\bar {a}_{7})$ from Construction 1 is uniquely determined by the sequences a₁,a₂,a₃,a₄ and $(b(j))_{j=0}^{3}$ since a_4+j = a_j and b(j + 4) = b(j) ⊕ 1 for j = 0,1,2,3.

From Lemma 4, the PACF of u at a shift τ = 8τ₁ + τ₂ is given by

$$ R_{u}(\tau ) = 2\sum\limits_{j=0}^{3}(-1)^{b(j)+b(j+\tau_{2})}R_{a_{j}, a_{j+\tau_{2}}}(\tau_{1}+e_{\tau_{2}}), $$

where 0 ≤ τ₁ < p and 0 ≤ τ₂ < 8. Denote

$$g(\tau_{1}, \tau_{2})=\sum\limits_{j=0}^{3}(-1)^{b(j)+b(j+\tau_{2})}R_{a_{j}, a_{j+\tau_{2}}}(\tau_{1}+e_{\tau_{2}}).$$

Then we have

$$ g(\tau_{1}, \tau_{2}) = - g(\tau_{1}, \tau_{2}-4),\quad \text{ for } 4\leq \tau_{2} <8, $$

which indicates that it suffices to focus on the cases where 0 ≤ τ₂ < 4.

For the cyclotomic sequences s_i’s with respect to p = 4f + 1, the correlation between any two cyclotomic sequences $s_{i_{1}},s_{i_{2}}$ was completely determined in [14]. Therefore, in the investigation of the PACF of an interleaved sequence u with the sequences a₀,a₁,a₂,a₃ taken from {s₁,s₂,s₃,s₄,s₅,s₆}, one can apply the result of [14] in the calculation.

Note that there are 16 possible binary sequences b and 6⁴ possible choices of sequences a₀,a₁,a₂,a₃, which produce 12⁴ different interleaved sequences u in aggregate. Although the correlation between any two cyclotomic sequences is available from [14], calculating the PACF for each generated interleaved sequence u manually is simply infeasible. By a Mathematica program, we exhaustively check the PACF for all the 12⁴ interleaved sequences.

Theorem 2

Let p = 4f + 1 = x² + 4y² with an even f. Then the sequence v derived from sequences a₀,⋯ ,a₃ and b in the following table has out-of-phase $\hat {R}_{v}({\tau }) \in \{0, \pm 2, \pm 4\}$ if the corresponding condition on x,y is satisfied:

Table 9

Theorem 3

Let p = 4f + 1 = x² + 4y² with an odd f. Then the sequence v derived from sequences a₀,⋯ ,a₃ and b in the following table has out-of-phase $\hat {R}_{v}({\tau }) \in \{0, \pm 2, \pm 4\}$ if the corresponding condition on y is satisfied.

Table 10

Theorem 4

Let p = 4f + 1 = x² + 4y² with an odd f. Then the sequence v derived from sequences a₀,⋯ ,a₃ and b in the following table has out-of-phase $\hat {R}_{v}({\tau }) \in \{0, \pm 2, \pm 4\}$ if the corresponding condition on y is satisfied.

Table 11

Remark 1

Theorems 2-4 provide a complete result on low-OACF interleaved sequences from cyclotomic sequences {s₁,⋯ ,s₆}. Due to the fact that different κ leads to identical OACF, it’s easy to verify that the sequences v₁,⋯ ,v₄ are covered in Theorem 2, v₅,⋯ ,v₈ are covered in Theorem 3, and v₉,⋯ ,v₁₆ are covered in Theorem 4.

Remark 2

Theorems 2-4 indicate that the possible values of $\hat {R}_{v}$ are completely determined by the value of x,y. Below we provide two counter-examples to Conjectures 1 and 2 in [10].

• (1) Let p = 113. Then p = (15² + 1)/2 and 8|(p − 1). For a primitive element α in {5,10,19,20,27,33,37,38,39,43,47,54,59,66,70,74,75,76,80,86,93,94,103,108} of $\mathbb {Z}_p$, define a binary sequence u given by Conjecture 1 with support defined by $G^{\prime }=\{2\}$, C₀ = D₀ ∪ D₃, C₁ = D₁ ∪ D₂, C₂ = D₀ ∪ D₁, C₃ = D₀ ∪ D₁. Then u can be written as u = v||(v + 1), where v = (u(0),⋯ ,u(4p − 1)). In this case, the sequence t of length 4p has out-of-phase odd periodic autocorrelation {± 30,± 4,± 2,0} respectively. This is not consistent with Conjecture 1.

• (2) Let p = 61. Then p = (11² + 1)/2 and $8\nmid (p-1)$. For a primitive element α ∈{21,24,41,57,63,66,85,91,97,98,103,104,105,112,123,127,128,131,134,153, 158,163,171,179} of $\mathbb {Z}_p$, define a binary sequence u given by Conjecture 2 with support defined by $G^{\prime }=\{0\}$, C₀ = D₀ ∪ D₃, C₁ = D₁ ∪ D₂, C₂ = D₀ ∪ D₁, C₃ = D₀ ∪ D₁. Then u can be written as u = v||(v + 1), where v = (u(0),⋯ ,u(4p − 1)). In this case, the sequence t of length 4p has out-of-phase odd periodic autocorrelation {± 38,± 4,± 2,0} respectively. This is not consistent with Conjecture 2.

In closing this section, we provide two explicit examples of interleaved sequences derived from cyclotomic sequences.

Example 3

Let p = 29, and α = 2 be a primitive element of the residue ring $\mathbb {Z}_{p}$. Then

$$ \begin{array}{ll} D_{0} = \{ 1, 7, 16, 20, 23, 24, 25 \}, & D_{1} = \{ 2, 3, 11, 14, 17, 19, 21 \},\\ D_{2}=\{ 4, 5, 6, 9, 13, 22, 28 \},& D_{3}= \{ 8, 10, 12, 15, 18, 26, 27 \} \end{array} $$

are four cyclotomic classes of order 4 with respect to p and Inv_p(8) = 11 ∈ D₁. In this case, x = 5 and y = − 1. Generate binary sequences s₁ and s₂ with supports D₀ ∪ D₁ and D₀ ∪ D₂ respectively

$$ \begin{array}{@{}rcl@{}} s_{1}&=&(01110001000100101101110111000),\\ s_{2}&=&(01001111010001001000101111001). \end{array} $$

Let b = (1,0,0,0). By Construction 1, we have the interleaved sequence u₉

$$ \begin{array}{rcl} u_{9} = && (1111101011010001000111100100110011001111100100011110100111 \\ && 0101110100011110110100011101110010100100101110101100000000 \\ && 0000010100101110111000011011001100110000011011100001011000 \\ && 1010001011100001001011100010001101011011010001010011111111 ). \end{array} $$

Then we have u₉ = v₉||(v₉ ⊕ 1). By computer experiment, we have the odd auto-correlation $\hat {R}_t(\tau )\in \{0,\pm 2, \pm 4\}$ for all 1 ≤ τ < 116.

Example 4

Let p = 29, and α = 8 be a primitive element of the residue ring $\mathbb {Z}_{p}$. Then

$$ \begin{array}{ll} D_{0}=\{ 1, 7, 16, 20, 23, 24, 25 \}, & D_{1}=\{ 8, 10, 12, 15, 18, 26, 27 \},\\ D_{2}=\{ 4, 5, 6, 9, 13, 22, 28 \},& D_{3}=\{ 2, 3, 11, 14, 17, 19, 21 \} \end{array} $$

are four cyclotomic classes of order 4 with respect to $\mathbb {Z}_p$ and and Inv_p(8) = 11 ∈ D₃. In this case, x = 5 and y = 1. Generate binary sequences s₁ and s₂ with supports D₀ ∪ D₃ and D₁ ∪ D₂ respectively

$$ \begin{array}{@{}rcl@{}} s_{2}&=&(01001111010001001000101111001),\\ s_{4}&=&(00001110111011010010001000111). \end{array} $$

Let b = (1,0,0,0). By Construction 1, we have the interleaved sequence u₁₁

$$ \begin{array}{@{}rcl@{}} u_{11}&=&(1100100111100010001011010111111111111100101000101101101011 \\&& 0001000111010010000111010001010001101000011101100000110011 \\ && 0011011000011101110100101000000000000011010111010010010100 \\ && 1110111000101101111000101110101110010111100010011111001100 ). \end{array} $$

Then we have u₁₁ = v₁₁||(v₁₁ ⊕ 1). By computer experiment, we have the odd auto-correlation $\hat {R}_{t_{11}}(\tau )\in \{0,\pm 2, \pm 4\}$ for all 1 ≤ τ < 116.

4 Conclusion

In this paper, we employ the interleaving technique to interpret sixteen binary sequences of length 4p proposed in [10] and provide a complete answer to Parker’s conjectures on the near-optimal out-of-phase five-valued or seven-valued odd-periodic autocorrelation of the sixteen sequences. The technique also enables us to exhaustively investigate the interleaved sequences from cyclotomic sequences and to present many new near-optimal binary sequences in terms of odd-periodic autocorrelation.