1 Introduction

Pseudorandom binary sequences are used in many areas such as telecommunication, cryptography, simulation, spectroscopy, see for example [2, 7, 11]. The quality of a pseudorandom sequence has to be screened by statistical test packages (for example, L’Ecuyer’s TESTU01, Marsaglia’s Diehard or the NIST battery) as well as by proving theoretical results on certain measures of pseudorandomness such as the correlation measure of order \(\ell \) introduced by Mauduit and Sárközy [9]. Here we focus on theoretical results.

In many applications such as cryptography, one needs a large family of good pseudorandom sequences and has to prove bounds on several figures of merit [4, 7]. In this paper we study the relationship of two such quality measures, the family complexity (abbreviated \(f\)-complexity) and the cross-correlation measure of order \(\ell \) of families of binary sequences.

Ahlswede et al. [1] introduced the \(f\)-complexity as follows.

Definition 1.1

The \(f\)-complexity \(C({\mathcal F})\) of a family \({\mathcal F}\) of binary sequences \(E_N \in \{-1,+1\}^N\) of length \(N\) is the greatest integer \(j \ge 0\) such that for any \(1 \le i_1 < i_2< \cdots < i_j \le N\) and any \(\epsilon _1,\epsilon _2, \ldots , \epsilon _j \in \{-1,+1\}\) there is a sequence \(E_N = \{e_1,e_2,\ldots , e_N\}\in {\mathcal F}\) with

$$\begin{aligned}e_{i_1}=\epsilon _1,e_{i_2}=\epsilon _2, \ldots ,e_{i_j}=\epsilon _j.\end{aligned}$$

We have the trivial upper bound

$$\begin{aligned} 2^{C({\mathcal F})} \le |{\mathcal F}|, \end{aligned}$$
(1)

where \(|{\mathcal F}|\) denotes the size of the family \({\mathcal F}\).

Gyarmati et al. [4] introduced the cross-correlation measure of order \(\ell \).

Definition 1.2

The cross-correlation measure of order \(\ell \) of a family \({\mathcal F}\) of binary sequences \(E_{i,N} = (e_{i,1},e_{i,2},\ldots , e_{i,N}) \in \{-1+1\}^N\), \(i=1,2, \ldots , F\), is defined as

$$\begin{aligned} \varPhi _\ell ({\mathcal F}) = \max _{M,D,I}\left| \sum _{n=1}^{M}{e_{i_1,n+d_1} \ldots e_{i_\ell ,n+d_\ell }}\right| , \end{aligned}$$

where \(D\) denotes an \(\ell \) tuple \((d_1,d_2,\ldots , d_\ell )\) of integers such that \(0 \le d_1 \le d_2 \le \cdots \le d_\ell < M+d_\ell \le N\) and \(d_h \ne d_j\) if \(E_{h,N} = E_{j,N}\) for \(h \ne j\), and \(I\) denotes an \(\ell \) tuple \((i_1,i_2, \ldots , i_\ell )\in \{1,2,\ldots ,F\}^\ell \).

In Sect. 2 we estimate the \(f\)-complexity of a family of binary sequences

$$\begin{aligned} E_{i,N} = (e_{i,1},e_{i,2},\ldots , e_{i,N}) \in \{-1+1\}^N, \quad i=1,\ldots ,F, \end{aligned}$$

in terms of the cross-correlation measure of the dual family \(\overline{{\mathcal F}}\) of binary sequences

$$\begin{aligned} E_{i,F} = (e_{1,i},e_{2,i},\ldots , e_{F,i}) \in \{-1+1\}^{F}, \quad i=1,\ldots ,N. \end{aligned}$$

In Sect. 3 we apply this result to prove a bound on the \(f\)-complexity of the family of sequences of Legendre-symbols of monic quadratic irreducible polynomials with vanishing middle coefficient

$$\begin{aligned} {\mathcal F}=\left\{ \left( \frac{n^2-bi^2}{p}\right) _{n=1}^{(p-1)/2} : i=1,\ldots ,(p-1)/2\right\} , \end{aligned}$$

where \(b\) is a quadratic non-residue modulo \(p\), showing that this family as well as its dual family has both a large family complexity and a small cross-correlation measure up to a rather large order.

We note that there are several related constructions of families of binary sequences defined with the Legendre symbol and polynomials, see [4, 6] and references therein. For instance, the family given in [6] has a large family complexity but a large cross-correlation measure of order 2. Moreover, the families given in [4] have a small cross-correlation measure, but it is not easy to measure their family complexity; for further details, see the remarks in Sect. 3. One of the aims of this study is to construct a family of binary sequences having both a large family complexity and a small cross-correlation measure.

Throughout the paper, the notation \(U \ll V\) is equivalent to the statement that \(\vert U \vert \le cV\) holds with some positive constant \(c\). Moreover, the notation \(f(n) = o(1)\) is equivalent to

$$\begin{aligned} \lim _{n \rightarrow \infty }{f(n)} = 0. \end{aligned}$$

2 A relation between family complexity and cross-correlation measure

In this section we prove the following relationship between the \(f\)-complexity of a family of binary sequences and the cross-correlation measure of its dual family.

Theorem 2.1

Let \({\mathcal F}\) be a family of binary sequences \((e_{k,1},\ldots ,e_{k,N}) \in \{-1,+1\}^N\) for \(k=1,2,\ldots ,F\) and \(\overline{{\mathcal F}}\) its dual family of binary sequences \((e_{1,n},e_{2,n},\ldots ,e_{F,n}) \in \{-1,+1\}^{F}\) for \(n=1,2,\ldots ,N\). Then we have

$$\begin{aligned} C({\mathcal F}) \ge \left\lceil \log _2{F} - \log _2{\max _{1 \le i \le \log _2{F}}{\varPhi _{i}(\overline{{\mathcal F}})}} \right\rceil -1, \end{aligned}$$

where \(\log _2\) denotes the binary logarithm.

Proof

We are looking for the largest \(j\) such that any specification

$$\begin{aligned} e_{k,n_1}=\epsilon _1,e_{k,n_2}=\epsilon _2,\ldots ,e_{k,n_j}=\epsilon _j \end{aligned}$$
(2)

occurs in the family \({\mathcal F}\) for some \(k \in \{1,2,\ldots ,F\}\). We will prove a sufficient condition for the existence of a sequence in \({\mathcal F}\) satisfying (2) by a counting argument. We know that

$$\begin{aligned} \frac{1}{2}(1+\epsilon _ie_{k,n_i}) = \left\{ \begin{array}{ll}1 &{} \quad \mathrm{if \ }e_{k,n_i}=\epsilon _i,\\ 0 &{} \quad \mathrm{if \ }e_{k,n_i}=-\epsilon _i. \end{array} \right. \end{aligned}$$

Then the number \(A\) of sequences in \({\mathcal F}\) satisfying (2) equals

$$\begin{aligned} A = \sum _{k=1}^{F}{\frac{1}{2^j} \prod _{i=1}^{j}{(1+\epsilon _ie_{k,n_i})}}. \end{aligned}$$

Extending the product and after easy calculations we have

$$\begin{aligned} \begin{array}{lll} A &{}=&{}\displaystyle \frac{1}{2^j}\sum _{k=1}^{F}{\left[ 1+ \sum _{{\ell }=1}^{j}{\sum _{1 \le i_1 < \cdots < i_{\ell } \le j}{\epsilon _{i_1}\ldots \epsilon _{i_{\ell }}e_{k,n_{i_1}} \ldots e_{k,n_{i_{\ell }}}}}\right] }\\ &{}=&{}\displaystyle \frac{1}{2^j}\left[ F+ \sum _{{\ell }=1}^{j}{\sum _{1 \le i_1 < \cdots < i_{\ell } \le j}{\epsilon _{i_1}\ldots \epsilon _{i_{\ell }} \sum _{k=1}^{F}{e_{k,n_{i_1}} \ldots e_{k,n_{i_{\ell }}}}}} \right] \\ &{}\ge &{}\displaystyle \frac{1}{2^j}\left[ F- \sum _{{\ell }=1}^{j}{\sum _{1 \le i_1 < \cdots < i_{\ell } \le j}{\left| \sum _{k=1}^{F}{e_{k,n_{i_1}} \ldots e_{k,n_{i_{\ell }}}}\right| }} \right] \\ &{}\ge &{} \displaystyle \frac{1}{2^j}\left[ F- \sum _{{\ell }=1}^{j}{\left( \begin{array}{c}j\\ {\ell }\end{array}\right) {\varPhi _{\ell }(\overline{{\mathcal F}})}} \right] . \end{array} \end{aligned}$$

Thus if

$$\begin{aligned} \displaystyle F > \sum _{{\ell }=1}^{j}{\left( \begin{array}{c}j\\ {\ell }\end{array}\right) {\varPhi _{\ell }(\overline{{\mathcal F}})}}, \end{aligned}$$
(3)

then there exists at least one sequence in \({\mathcal F}\) satisfying (2).

By (1) we may assume \(j \le \log _2F\), and so we get

$$\begin{aligned} \begin{array}{lll} \displaystyle \sum \limits _{\ell =1}^{j}{\left( \begin{array}{c}j\\ {\ell }\end{array}\right) {\varPhi _{\ell }(\overline{{\mathcal F}})}}&< 2^j \max \limits _{1 \le i \le \log _2 F}\varPhi _{i}(\overline{{\mathcal F}}). \end{array} \end{aligned}$$

Therefore for all integers \(j \ge 0\) satisfying

$$\begin{aligned} j < \log _2{F} - \log _2{\max _{1 \le \ell \le \log _2{F}}{\varPhi _{\ell }(\overline{{\mathcal F}})}}\end{aligned}$$

(3) is satisfied and we have \(A > 0\) which completes the proof. \(\square \)

3 A family with low cross-correlation measure and high family complexity

In this section we demonstrate how to apply Theorem 2.1 and prove that the following family of sequences and its dual family have both high family complexity and small cross-correlation measure of order \(\ell \) up to a large order \(\ell \).

Let \(p>2\) be a prime and \(b\) a quadratic nonresidue modulo \(p\). The family \({\mathcal F}\) and its dual family \(\overline{{\mathcal F}}\) are defined as follows:

$$\begin{aligned} {{\mathcal F}}=\left\{ \left( \frac{n^2-bi^2}{p}\right) _{i=1}^{(p-1)/2} : n=1,\ldots ,(p-1)/2\right\} ,\\ \overline{{\mathcal F}}=\left\{ \left( \frac{n^2-bi^2}{p}\right) _{n=1}^{(p-1)/2} : i=1,\ldots ,(p-1)/2\right\} . \end{aligned}$$

Since

$$\begin{aligned} \left( \frac{n^2-bi^2}{p}\right) =\left( \frac{-b}{p}\right) \left( \frac{i^2-bn^2}{p}\right) =(-1)^{(p+1)/2}\left( \frac{i^2-bn^2}{p}\right) \end{aligned}$$

both families have the same family complexity and cross-correlation measure of order \(\ell \). We will show

$$\begin{aligned} \varPhi _\ell ({{\mathcal F}})\ll \ell p^{1/2}\log p\quad \text{ and } \quad \varPhi _\ell (\overline{{\mathcal F}})\ll \ell p^{1/2}\log p \end{aligned}$$
(4)

for each integer \(\ell =1,2,\ldots \) Then Theorem 2.1 immediately implies

$$\begin{aligned} C({{\mathcal F}})\ge \left( \frac{1}{2}-o(1)\right) \frac{\log p}{\log 2} \quad \hbox {and}\quad C(\overline{{\mathcal F}})\ge \left( \frac{1}{2}-o(1)\right) \frac{\log p}{\log 2}. \end{aligned}$$

Here we used

$$\begin{aligned} |{\mathcal F}|=|\overline{{\mathcal F}}|=(p-1)/2,\quad p\ge 11, \end{aligned}$$

which can be verified in the following way. For some \(1\le n_1<n_2\le (p-1)/2\) assume that \(\big (\frac{n_1^2-bi^2}{p}\big )=\big (\frac{n_2^2-bi^2}{p}\big )\) for \(i=1,\ldots ,(p-1)/2\). Since \(i^2\equiv (p-i)^2 \hbox {mod}\, p\) and \(\big (\frac{n_1^2}{p}\big )=\big (\frac{n_2^2}{p}\big )=1\), these Legendre symbols are the same for all \(i=0,\ldots ,p-1\) and thus

$$\begin{aligned} p=\sum _{i=0}^{p-1} \left( \frac{n_1^2-bi^2}{p}\right) \left( \frac{n_2^2-bi^2}{p}\right) \le 3p^{1/2} \end{aligned}$$

by Weil’s bound and we get a contradiction to \(p\ge 11\).

Now we prove (4). According to Definition 1.2 and since the Legendre symbol is multiplicative, we need to estimate sums of the form

$$\begin{aligned} \displaystyle \left|\sum _{n=1}^M\left( \frac{h(n)}{p} \right) \right|, \end{aligned}$$

where

$$\begin{aligned} h(X)=((X+d_1)^2-bi_1^2)((X+d_2)^2-bi_2^2)\ldots ((X+d_\ell )^2-bi_\ell ^2). \end{aligned}$$

The result follows from the Weil bound after reducing these incomplete character sums to complete ones using the standard method provided that \(h(X)\) is not a square, see [8, 10, 12]. Since each factor of \(h(X)\) of the form \((X+d)^2-bi^2\) is irreducible over \({\mathbb {F}}_p\), it is enough to show that one factor is distinct from all the others. We may assume that the first factor is of the form \(X^2-bi^2\). Comparing coefficients we see that

$$\begin{aligned} X^2-bi^2=(X+d)^2-bj^2 \end{aligned}$$

is only possible if \(d=0\) and \(i\equiv \pm j \hbox {mod}\, p\). Since \(1\le i,j\le (p-1)/2\) we get \(i=j\) and \(h(X)\) is not a square since either \(d_j\ne d_k\) for \(i\ne k\) or \(d_j=d_k\) and \(i_j\ne i_k\) with \(1\le i_j,i_k\le (p-1)/2\).

Remarks

  1. 1.

    Gyarmati [6] studied the family \({\mathcal F}\) of binary sequences \(E_f = (e_{f,1}, \ldots , e_{f,p}) \in \{-1, +1\}^p\) defined by

    $$\begin{aligned} e_{f,n} = \left\{ \begin{array}{ll}\left( \frac{f(n)}{p} \right) &{} \quad \mathrm{if \ }\gcd (f(n),p) =1,\\ \quad 1 &{} \quad \mathrm{if \ }p \mid f(n), \end{array}\right. \end{aligned}$$
    (5)

    where \(f\) runs through all non-constant square-free polynomials over \({\mathbb {F}}_p\) of degree at most \(k\). She proved

    $$\begin{aligned} C(F) \ge \frac{k}{2\log {2}}\log {p} - O(k \log {(k \log {p})}). \end{aligned}$$

    However, this family has obviously a very large cross-correlation measure of order 2. (Compare \(E_f\) and \(E_g\) with \(g(X) = f(X+d)\) for some \(d \in {\mathbb {F}}_p^*\).)

  2. 2.

    Gyarmati et al. [3] studied the family \({\mathcal F}\) of sequences \(E_f = (e_{f,1}, \ldots , e_{f,p}) \in \{-1, +1\}^p\) defined by (5) where \(f\) runs through all monic irreducible polynomials of degree d with second leading coefficient 0 and showed in Theorem 8.14 that

    $$\begin{aligned} \varPhi _l({\mathcal F}) \ll \ell d p^{1/2}\log {p}. \end{aligned}$$

    We note that for \(d=2\) the polynomials \(f\) are of the form \(X^2 - a\) where \(a\) is a quadratic non-residue modulo \(p\) and we have \(e_{f,1} = e_{f,p-1}\) and thus \(C({\mathcal F}) \le 1\). For \(d \ge 3\) it seems to be a challenging problem to estimate the family complexity of this family.

  3. 3.

    Very recently, Gyarmati [5] proved also a lower bound on the family complexity of the family of sequences \(E_f\) defined by (5) where \(f\) runs through all monic irreducible polynomials of degree \(d\) (with arbitrary second leading coefficient). However, since \(f(X)\) is irreducible whenever \(f(X+c)\) for all \(c \in {\mathbb {F}}_p\), the cross-correlation measure of order 2 of this family is again very large.