1 Introduction

A pseudo-random sequence is a sequence of numbers which is generated by a deterministic algorithm and looks truly random. By truly random we mean that each element of the sequence can not be predicted from others, for instance a sequence generated by samples of atmospheric noise. A pseudo-random sequence in the interval [0, 1) is called a sequence of pseudo-random numbers. Pseudo-random sequences were widely studied in the literature (see [31, 32, 36]). Randomness measures of a sequence depend on its application area, for instance, it has to be unpredictable for cryptographic applications [26], uncorrelated for wireless communication applications [13] and uniformly distributed for quasi-Monte Carlo methods [28, 29]. In this paper we consider the Legendre sequence which is the binary sequence \(E_p(f)=(e_1,\dots ,e_p)\) defined by

$$\begin{aligned} e_j = \left\{ \begin{array}{ll} {\left( \frac{f(j)}{p}\right) } &{} {{\text { for }}}\gcd (f(j),p)=1,\\ 1 &{} {{\text { for }}}p | f(j), \end{array} \right. \end{aligned}$$

where p is a prime number, \(j=1,2,\ldots ,p\) and f is a polynomial over a finite field with p elements.

It is known that the Legendre sequence has several good randomness measures such as high linear complexity [4, 8, 33, 37] and small correlation measure up to rather high orders [23] for cryptography, and a small (aperiodic) auto-correlation [25, 30] for wireless communication, GPS, radar or sonar.

When a family of sequences is considered for an application, e.g. as a key-space of a cryptosystem, then its randomness in terms of many directions is concerned. For instance, a family of sequences must have a large family size, large family complexity, and low cross-correlation. Family complexity (f-complexity) was first introduced as a randomness measure by Ahlswede, Khachatrian, Mauduit and Sárközy [1]. Then they studied families of pseudo-random sequences on k-symbols and their f-complexity [2, 3]. Mauduit and Sárközy [24] studied the f-complexity of sequences of k-symbols and they also gave the connection between f-complexity and VC-dimension. Winterhof and the second author [40] gave a relation between f-complexity and cross-correlation measure. Moreover the complexity measures for different families have been studied in the literature [5, 11, 14, 17,18,19]. Sárközy [34] wrote a survey about definitions of various measures of family of binary sequences (e.g. f-complexity, collision, minimum distance, avalanche effect, and cross-correlation measure).

Gyarmati [16] presented a bound for the f-complexity of Legendre sequences constructed by some polynomials of degree k over a prime finite field \({{\mathbb {F}}}_p\). In this paper, we prove a new bound, which improves the bound given in [16] for any prime p and degree k (see Theorem 1). Moreover, we obtain a simplified lower bound and prove that our bound is better than the bound given in [16] (see Corollary 2). In particular, the new bound surpluses overwhelmingly the bound given in [16] for small k and it gets closer for large k (see Figs. 3, 4 and 5). We also see from these figures that our bound provides a better lower level. We also compare both bounds in terms of time complexity, for which we plot the difference between the elapsed times required to calculate both bounds (see Figs. 7 and 8).

The paper is organized as follows. The new bound we present in this paper depends on the Lambert W function, so we give its definition and some properties in Sect. 2. Then we present some auxiliary lemmas in Sect. 3 and previous results in Sect. 4. Next, we give our main contribution in Sect. 5. Finally we compare the new bound and Gyarmati’s one in Sect. 6.

2 Lambert W function

In this section we introduce the definition of the Lambert W function and present some of its properties.

Definition 1

[7] The Lambert W function, also called the omega function or product logarithm, is defined as the multivalued function W that satisfies

$$\begin{aligned} z=W(z)e^{W(z)} \end{aligned}$$

for any complex number z.

Equivalently, the Lambert W function is known as the inverse function of \(f(z)=ze^{z}\). Note that the multivaluedness of the Lambert W function means that there are multiple solutions for some values since the function f is not injective. The equation \(y=ze^{z}\) is by definition solved by

$$\begin{aligned} z=W(y), \end{aligned}$$

and the equation \(y=z\log z\) is solved by

$$\begin{aligned} z=\frac{y}{W(y)}. \end{aligned}$$
(1)

So, equations containing exponential expressions can be solved by the Lambert W function. For instance, the equation \(xa^{x}=b\) is solved by \(x=\frac{W\left( b\ln {\left( a\right) }\right) }{\ln {\left( a\right) }},\) the equation \(a^{x}=x+b\) is solved by \(x=\frac{-b-W\left( -a^{-b}\ln {\left( a\right) }\right) }{\ln {(a)}},\) and the equation \(x^{x^{a}}=b\) is solved by \(\exp {\left( \frac{W(a\log {(b)})}{a}\right) }\), where “\(\ln\)” stands for the natural logarithm. The Lambert W function stems from the equation proposed by Johann Heinrich Lambert in 1758

$$\begin{aligned} x^{\alpha }-x^{\beta }=(\alpha -\beta )vx^{\alpha +\beta }, \end{aligned}$$

which is known as Lambert’s transcendental equation. Then in 1779 Euler wrote a paper [10] about this equation and introduced a special case which is nearly the definition of the W function. He referenced work by Lambert in his paper, and so this function is called Lambert W function. From now on we will use W as the Lambert W function. The W function, which has applications in many fields from past to present, was applied to problems ranging from quantum physics to population dynamics, to the complexity of algorithms (see [7, 38]). The new bound we obtain for family complexity given in this paper is related to this function. Now we give a simple example in order to show how we use this function.

Example 1

Let us solve \(4^{-t}=3t\) for t. We first multiply both sides by \(\frac{\ln {4}}{3}4^{t}\) to get:

$$\begin{aligned} \frac{\ln {4}}{3} = t \ln 4\, 4^{t} = t\ln 4\, e^{t\ln {4}} \end{aligned}$$

Since the right hand side of the equation is of the form \(ze^{z}\) for \(z = t\ln 4\), we can write the solution using the definition of the W function

$$\begin{aligned} t=\frac{W\left( \frac{\ln {4}}{3}\right) }{\ln {4}}, \end{aligned}$$

which is approximately \(t \approx 0.239243358717019\).

The graph of the W function on the real plane is plotted in Fig. 1.

Fig. 1
figure 1

The graph of the W function obtained in Example 1

Full size image

We note that the W function can be approximately evaluated by using some root-finding methods as given in [7]. Futhermore, in [7] it is shown that

$$\begin{aligned} W(x)=L_1-L_2+\frac{L_2}{L_1}+\frac{L_2\left( -2+L_2\right) }{2L_1^2}+\frac{L_2\left( 6-9L_2+2L_2^2\right) }{6L_1^3}+\cdots \end{aligned}$$
(2)

where \(L_1=\ln x\), \(L_2=\ln \ln x\). Then keeping only the first two terms of the expansion (2) we have

$$\begin{aligned} W(x)=\ln x-\ln \ln x + o(1). \end{aligned}$$
(3)

In the following lemma, the bounds were given with error term \(o\left( \frac{\ln \ln x}{\ln x}\right)\) instead of o(1), with certain coefficients for error terms.

Lemma 1

[21] For every \(x\ge e\) we have

$$\begin{aligned} \ln x-\ln \ln x+\frac{1}{2}\frac{\ln \ln x}{\ln x}\le W(x)\le \ln x-\ln \ln x+\frac{e}{e-1}\frac{\ln \ln x}{\ln x}, \end{aligned}$$
(4)

with equality only when \(x=e\).

3 Preliminaries

In this section we present some definitions and results which we need for the proof of the main results introduced in this paper.

Definition 2

Let q be a prime power and \({{\mathbb {F}}}_{q^n}\) denote the finite field of \(q^n\) elements and define \(G_{q,n}\) as follows.

$$\begin{aligned} G_{q,n}=\{\alpha \in {{\mathbb {F}}}_{q^n} : \exists t, t|n, 0< t < n {{\text { such that }}} \alpha \in {{\mathbb {F}}}_{q^t} \subset {{\mathbb {F}}}_{q^n}\} \end{aligned}$$

In other words, the set \(G_{q,n}\) consists of all elements belonging to the proper subfields of \({{\mathbb {F}}}_{q^n}\).

One can calculate the number of elements in \(G_{q,n}\) for given q and n by counting the elements in the proper subfields of \({{\mathbb {F}}}_{q^n}\). However, this method would be inefficient. Thus, we need a formula for \(|G_{q,n}|\) and, in order to do that, we give some definitions and results below.

Definition 3

[27, Definition 2.1.22] The Möbius \(\mu\) function is defined on the set of positive integers as

$$\begin{aligned} \mu (m)= \left\{ \begin{array}{ll} 1 &{} {{\text {if }}}m=1,\\ (-1)^{k} &{} {{\text {if }}}m=m_1m_2\ldots m_k {{\text { where the }}}m_i {{\text { are distinct primes,}}}\\ 0 &{} {{\text {if }}}p^2 {{\text { divides }}}m {{\text { for some prime }}}p. \end{array}\right. \end{aligned}$$

Let \(I_q(n)\) denote the number of monic irreducible polynomials of degree n over \({{\mathbb {F}}}_q\) for a prime power q.

Gauss discovered the formula presented in the following result and so it was called after him [12].

Proposition 1

For a positive integer n and a prime power q,

$$\begin{aligned} I_{q}(n)=\frac{1}{n}\sum _{d|n}\mu (d)q^{n/d}. \end{aligned}$$

For more details about this formula see [9, Chapter 14.3], [27, Theorem 2.1.24] or [6].

Lemma 2

Let \(n\in {{\mathbb {N}}}\) and q be a prime power. Then

$$\begin{aligned} |G_{q,n} |= q^n-n I_{q}(n). \end{aligned}$$

Proof

It is clear that any root of an irreducible polynomial of degree n over \({{\mathbb {F}}}_q\) can not be an element of a proper subfield of \({{\mathbb {F}}}_{q^n}\). Hence the proof follows. \(\square\)

Example 2

Let q be a prime power. Consider \({{\mathbb {F}}}_{q^n}\) for \(n=105\). Then, the possible divisors of n are \(d=1,3,5,7,15,21,35,105\) and by Lemma 2 we get

$$\begin{aligned} | G_{q,n} | = q^{35}+q^{21}+q^{15}-q^7-q^5-q^3+q. \end{aligned}$$

Now we define the norm and the trace of an element in a finite field. (see [22, Chapter 2] for more details).

Definition 4

For \(\alpha \in {{\mathbb {F}}}_{q^n}\) the norm \(\mathrm{N}_{{\mathbb{F}_{q^n}} / {\mathbb{F}_q}}(\alpha )\) of \(\alpha\) is defined by

$$\begin{aligned} \mathrm{N}_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha ) = \alpha \cdot \alpha ^q\cdot \alpha ^{q^2}\cdots \alpha ^{q^{n-1}}=\alpha ^{(q^n-1)/(q-1)}, \end{aligned}$$

and the trace \(\mathrm{Tr}_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha )\) of \(\alpha\) is defined by

$$\begin{aligned} \mathrm{Tr}_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha )=\alpha +\alpha ^{q}+\cdots +\alpha ^{q^{n-1}}. \end{aligned}$$

In particular, \(\mathrm{N}_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha )\) and \(\mathrm{Tr}_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha )\) are elements of \({{\mathbb {F}}}_{q}\).

Definition 5

[22, Chapter 5] Let \(\chi\) be an additive and \(\psi\) be a multiplicative character of \({{\mathbb {F}}}_{q}\). Then \(\chi\) and \(\psi\) can be lifted to \({{\mathbb {F}}}_{q^n}\) by setting \(\chi '(\alpha )=\chi (\text{ Tr }_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha ))\) for \(\alpha \in {{\mathbb {F}}}_{q^n}\) and \(\psi '(\alpha )=\psi (\text{ N }_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(\alpha ))\) for \(\alpha \in {{\mathbb {F}}}_{q^n}^{*}\). Also from the additivity of the trace and multiplicativity of the norm, \(\chi '\) is an additive and \(\psi ^{'}\) is a multiplicative character of \({{\mathbb {F}}}_{q^n}\).

We need the following lemma for the proof of Theorem 1.

Lemma 3

[16, Corollary 2.1.] Let \(p>2\) be a prime number and \(\left( \frac{.}{p}\right)\) be the Legendre symbol. Let \(\gamma\) be the quadratic character of \({{\mathbb {F}}}_{p^n}\). Then for \(\alpha \in {{\mathbb {F}}}^{*}_{p^n}\),

$$\begin{aligned} \gamma (\alpha )=\left( \frac{\mathrm{N}_{{{\mathbb {F}}}_{p^n}/{{\mathbb {F}}}_p}(\alpha )}{p}\right) . \end{aligned}$$

Next, we define two new polynomials obtained from a given polynomial over a finite field.

Definition 6

Given \(f(x)=a_kx^k+a_{k-1}x^{k-1}+\cdots +a_0 \in {{\mathbb {F}}}_{q^n}[x]\), we define

$$\begin{aligned} \tau _s(f)(x):=a_k^{q^s}x^k+a_{k-1}^{q^s}x^{k-1}+\cdots +a_0^{q^s} \in {{\mathbb {F}}}_{q^n}[x] \end{aligned}$$

for \(0\le s \le n-1\) and

$$\begin{aligned} N_{{{\mathbb {F}}}_{q^n}/{{\mathbb {F}}}_q}(f):=\tau _0(f)\cdot \tau _1(f)\cdot \tau _2(f)\cdots \tau _{n-1}(f) \in {{\mathbb {F}}}_{q^n}[x]. \end{aligned}$$

Next, we give a result which will be the basis of the proof of our main theorem.

Lemma 4

[22, Exercise 5.64] Let \(i_1,\ldots ,i_j\) be distinct elements of \({{\mathbb {F}}}_{p^k}\), p odd prime, and \(\epsilon _{1},\ldots ,\epsilon _{j} \in \{-1,+1\}\). Let \(N(\epsilon _{1},\ldots ,\epsilon _{j})\) denote the number of \(\alpha \in {{\mathbb {F}}}_{p^k}\) with \(\gamma (\alpha + i_s)=\epsilon _{s} \text{ for } s=1,2,\ldots ,j\) where \(\gamma\) is the quadratic character of \({{\mathbb {F}}}_{p^k}\). Then,

$$\begin{aligned} \left| N(\epsilon _{1},\ldots ,\epsilon _{j})-\frac{p^k}{2^j} \right| \le \left( \frac{j-2}{2}+\frac{1}{2^j}\right) p^{k/2} + \frac{j}{2}. \end{aligned}$$

Proof

By definition we have

$$\begin{aligned} N(\epsilon _{1},\ldots ,\epsilon _{j}) = \frac{1}{2^j}\sum _{\alpha \in {{\mathbb {F}}}_{p^k}}{[1+\epsilon _{1}\gamma (\alpha + i_1)]\cdots [1+\epsilon _{j}\gamma (\alpha + i_j)]} -A, \end{aligned}$$

where \(0 \le A \le j/2\). Note that \(\gamma (\alpha + i_j)\) can be 0 for some \(\alpha \in {{\mathbb {F}}}_{p^k}\) which adds \(2^{j-1}\) to the summation, and this can occur at most j times. So, that is the reason why we have \(0 \le A \le j/2\). By expanding the inner multiplication we get that

$$\begin{aligned} N(\epsilon _{1},\ldots ,\epsilon _{j})= &\, {} \frac{1}{2^j}\sum _{\alpha \in {{\mathbb {F}}}_{p^k}}\bigg [1 +\sum _{s_1}{\epsilon _{s_1}\gamma (\alpha + i_{s_1})} \\&+ \sum _{s_1,s_2}{\epsilon _{s_1}\gamma (\alpha + i_{s_1})\epsilon _{s_2}\gamma (\alpha + i_{s_2})}\\&+ \cdots + [\epsilon _{1}\gamma (\alpha + i_1)\cdots \epsilon _{j}\gamma (\alpha + i_j)]\bigg ] -A. \end{aligned}$$

Then by using the Weil theorem [39] (or [22, Theorem 5.41]),

$$\begin{aligned} \left| N(\epsilon _{1},\ldots ,\epsilon _{j})-\frac{p^k}{2^j} \right|\le & {} \frac{1}{2^j}\sum _{i=1}^j{\left( {\begin{array}{c}j\\ i\end{array}}\right) (i-1)p^{k/2}} + \frac{j}{2} \\= &\, {} \frac{1}{2^j}\left( \sum _{i=1}^j{\left( {\begin{array}{c}j\\ i\end{array}}\right) i} - \sum _{i=1}^j{\left( {\begin{array}{c}j\\ i\end{array}}\right) }\right) p^{k/2} + \frac{j}{2} \\= &\, {} \frac{1}{2^j}( j2^{j-1} - (2^j - 1) ) p^{k/2} + \frac{j}{2}. \end{aligned}$$

Therefore, the result follows. \(\square\)

4 Previous results

In this section we will give a construction method for Legendre sequences, and the definition of family complexity. Then we will recall a result given in [16]. We begin with the definition of Legendre sequence [14, 23].

Definition 7

Let \(K\ge 1\) be an integer and p be a prime number. If \(f \in {{\mathbb {F}}}_p[x]\) is a polynomial with degree \(1\le k\le K\) and no multiple zeros in \({{\mathbb {F}}}_p\), then we define the binary sequence \(E_p(f)=E_p=(e_1,\ldots ,e_p)\) by

$$\begin{aligned} e_j = \left\{ \begin{array}{ll} {\left( \frac{f(j)}{p}\right) } &{} {{\text { for }}}\gcd (f(j),p)=1,\\ 1 &{} {{\text { for }}}p | f(j), \end{array} \right. \end{aligned}$$

for \(j=1,2,\ldots ,p\). Let \({{\mathcal {F}}}(K,p)\) denote the set of all sequences obtained in this way.

Hoffstein and Lieman [20] proposed using the polynomials f to construct the binary sequences given in Definition 7. Goubin, Mauduit and Sárközy [14] proved that the sequences obtained in this way have strong pseudo-random properties.

We now give the definition of f-complexity of a family \({{\mathcal {F}}}\), which was first introduced by Ahlswede et al. [1].

Definition 8

The family complexity (in short f-complexity) 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}$$

The f-complexity of a family \({{\mathcal {F}}}\) is denoted by \(\varGamma ({{\mathcal {F}}})\).

We note that the trivial upper bound on the f-complexity \(\varGamma ({{\mathcal {F}}})\) in terms of the family size \(|{{\mathcal {F}}}|\) is

$$\begin{aligned} 2^{\varGamma ({{\mathcal {F}}})} \le |{{\mathcal {F}}}|. \end{aligned}$$
(5)

Now we give an example for calculating the f-complexity of a family of binary sequences.

Example 3

Consider the family of binary sequences

$$\begin{aligned} {{\mathcal {F}}}=\{(1,1,1,1),(-1,-1,1,-1),(-1,-1,-1,-1),(1,1,-1,-1),(-1,1,1,1)\}. \end{aligned}$$

It is clear that both \(-1\) and 1 occur at the i-th location of the sequences for all \(i=1,2,3,4\). In other words, the set obtained from the first entries of the sequences has both \(-1\) and 1, similarly the other entries have both \(-1\) and 1. Hence, the f-complexity of \({{\mathcal {F}}}\) is at least 1. On the other hand, there is no sequence in \({{\mathcal {F}}}\) consisting of the pair \((1,-1)\) in the first two entries. So we say that the f-complexity of \({{\mathcal {F}}}\) is equal to 1. Similarly, the family of binary sequences

$$\begin{aligned} {{\mathcal {G}}}=\{(1,1,1,1),(-1,1,1,-1),(-1,1,-1,-1),(1,1,-1,-1),(-1,1,1,1)\}. \end{aligned}$$

has f-complexity 0 since \(-1\) does not appear in the second entry of any sequences in \({{\mathcal {G}}}\).

Let \({{\mathcal {F}}}_{\mathrm{irred}}(k,p)\) denote the family of Legendre sequences generated by irreducible polynomials of degree k over a prime field \({{\mathbb {F}}}_p\),

$$\begin{aligned} {{\mathcal {F}}}_{\mathrm{irred}}(k,p):=\{E_p(f) : f \in {{\mathbb {F}}}_p[x] \text{ monic } \text{ irreducible } \text{ polynomial } \text{ with } \text{ degree } k\}. \end{aligned}$$

Different properties of this family have been studied in the literature [14, 15, 18]. A lower bound on the f-complexity of the family \({{\mathcal {F}}}_{\mathrm{irred}}(k,p)\) was proved in [16], which we present in the following theorem.

Theorem A

[16] Let p be an odd prime and k be a positive integer. Define

$$\begin{aligned} c = {\left\{ \begin{array}{ll}\frac{1}{2} \text{ if } k\le \frac{p^{1/4}}{10\ln p}, \\ \frac{5}{2} \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Then

$$\begin{aligned} \varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(k,p))\ge \min \left\{ p, \frac{k-c}{2\ln 2}\ln p\right\} . \end{aligned}$$

Theorem A says that the f-complexity is at least of order \(\frac{p^{1/4}}{20\ln {2}}\). In the next section, for the same family of sequences as in Theorem A, we give a new bound by using the formula \(|G_{p,k} |\) given in Lemma 2 and the W function given in Definition 1.

5 Main method

The main contribution of this paper is given in this section, which is a new bound on the f-complexity of Legendre sequences generated by irreducible polynomials. This new bound improves the bound given in [16]. The comparison of both bounds is given in the next section.

Theorem 1

Let p be an odd prime and k be a positive integer. Let A and B be defined as

$$\begin{aligned} A=\frac{2p^{k/2}-2}{1+p^{-k/2}} \text{ and } B=\frac{2 | G_{p,k}| p^{-k/2}-2}{1+p^{-k/2}}. \end{aligned}$$

Then

$$\begin{aligned} \varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(k,p)) \ge \min \left\{ p,\log _{2}\left( \frac{A}{W(2^BA)}\right) \right\} . \end{aligned}$$

We first give an example for calculating the f-complexity of Legendre sequences.

Example 4

Let \(p=3\) and \(k=2\). Then by the definition of Legendre sequences, we get the following family of sequences.

$$\begin{aligned} {{\mathcal {F}}}_{\mathrm{irred}}(2,3)=\{(1,-1,-1),(-1,1,-1),(-1,-1,1)\}. \end{aligned}$$

As \(|{{\mathcal {F}}}_{\mathrm{irred}}(2,3)|=3\), by using (5) we have \(2^{\varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(2,3))}\le 3\). And by Theorem 1, we obtain

$$\begin{aligned} \varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(2,3))\ge \log _2\left( \frac{3}{W(3)}\right) >0.58167368954. \end{aligned}$$

Therefore, we get \(\varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(2,3))=1.\)

Before proving the Theorem 1, we will give two auxiliary lemmas. In the first lemma, the solution of a logarithmic equation is obtained by the W function. In the second lemma, we give an upper bound on j such that \(| G_{p,k}| < N(\epsilon _1,\ldots ,\epsilon _j)\).

Lemma 5

Let \(A,B \in {{\mathbb {R}}}\). If \(Bx+ x\log _{2}x - A = 0\), then \(x = \frac{A}{W(2^BA)}.\)

Proof

We have

$$\begin{aligned} x(B+ \log _{2}x) = A \end{aligned}$$

or equivalently,

$$\begin{aligned} 2^Bx(B+ \log _{2}x) = 2^BA. \end{aligned}$$

Then we get

$$\begin{aligned} 2^Bx(\log _{2}2^B + \log _{2}x) = 2^BA\implies 2^Bx(\log _2(2^Bx)) = 2^BA. \end{aligned}$$

Thus by (1) we have

$$\begin{aligned} 2^Bx = \frac{2^BA}{W(2^BA)}, \end{aligned}$$

that is

$$\begin{aligned} x = \frac{A}{W(2^BA)}. \end{aligned}$$

\(\square\)

Lemma 6

Let p be an odd prime and k be a positive integer. Let \(|G_{p,k}|\) be defined as in Lemma 2. Let A and B be defined as

$$\begin{aligned} A=\frac{2p^{k/2}-2}{1+p^{-k/2}} \text{ and } B=\frac{2 | G_{p,k}| p^{-k/2}-2}{1+p^{-k/2}}. \end{aligned}$$

Let j be an integer such that \(j < \log _2\left( \frac{A}{W(2^BA)}\right)\). Let \(\epsilon _1,\ldots ,\epsilon _j \in \{-1,+1\}\) and \(N(\epsilon _1,\ldots ,\epsilon _j)\) be defined as in Lemma 4. Then

$$\begin{aligned} | G_{p,k}| < N(\epsilon _1,\ldots ,\epsilon _j). \end{aligned}$$

Proof

Assume that \(|G_{p,k}| \ge N(\epsilon _1,\ldots ,\epsilon _j).\) Then by Lemma 4

$$\begin{aligned} |G_{p,k}| \ge \frac{p^k}{2^j}-p^{k/2}\left( \frac{1}{2^j}+\frac{(j-2)}{2}\right) -\frac{j}{2}. \end{aligned}$$

Divide both sides by \(p^{k/2}\)

$$\begin{aligned} |G_{p,k}| p^{-k/2}\ge \frac{p^{k/2}}{2^j}-\left( \frac{1}{2^j}+\frac{(j-2)}{2}\right) -\frac{jp^{-k/2}}{2}. \end{aligned}$$

Multiply both sides by \(2(2^j)\), and so get the following inequality:

$$\begin{aligned}&2(2^j)|G_{p,k}| p^{-k/2}\ge 2p^{k/2}-2-2^j(j-2)-2^j jp^{-k/2}, \\&2(2^j) |G_{p,k}| p^{-k/2}-2(2^j)+2^jj+2^jjp^{-k/2}\ge (2p^{k/2}-2), \\&{(2|G_{p,k}| p^{-k/2}-2)}2^j+2^jj(1+p^{-k/2})\ge (2p^{k/2}-2). \end{aligned}$$

Divide both sides by \((1+p^{-k/2})\),

$$\begin{aligned} \frac{(2 |G_{p,k}| p^{-k/2}-2)}{(1+p^{-k/2})}2^j +2^j j \ge \frac{(2p^{k/2}-2)}{(1+p^{-k/2})}. \end{aligned}$$

According to the definition of A and B, we have,

$$\begin{aligned} B2^j +2^j j \ge A. \end{aligned}$$

Hence, by Lemma 5 and the fact that \(B2^j +2^j j\) increases with respect to j, we obtain that

$$\begin{aligned} 2^j \ge \frac{A}{W(2^BA)} \text{ or } \text{ equivalently } j\ge \log _2\left( \frac{A}{W(2^BA)}\right) , \end{aligned}$$

which is a contradiction. \(\square\)

Proof of Thoerem 1

For all integers \(j < \log _2\left( \frac{A}{W(2^BA)}\right)\) and for all tuples \((\epsilon _1,\epsilon _2,\ldots ,\epsilon _j)\in \{-1,+1\}^j\), we need to show the existence of an irreducible polynomial \(g \in {{\mathbb {F}}}_p[x]\) of degree k such that

$$\begin{aligned} \left( \frac{g(i_s)}{p}\right) =\epsilon _s \text{ for } s=1,2,\ldots ,j \end{aligned}$$
(6)

for some \(1 \le i_1< i_2< \cdots < i_j \le p\). Then the definition of f-complexity gives that \(\varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(k,p)) \ge \log _{2}\left( \frac{A}{W(2^BA)}\right)\). By Lemma 6 we know that

$$\begin{aligned} | G_{p,k}| < N(\epsilon _1,\ldots ,\epsilon _j). \end{aligned}$$

By the definition of \(N(\epsilon _1,\ldots ,\epsilon _j)\) we get that there exists \(\alpha \in {{\mathbb {F}}}_{p^k} \backslash G_{p,k}\) such that

$$\begin{aligned} \gamma (\alpha +i_s)=\epsilon _s \text{ for } s= 1,2,\ldots ,j. \end{aligned}$$
(7)

Let \(f(x)=x+\alpha \in {{\mathbb {F}}}_{p^k}[x]\) and we define \(g(x):=N_{{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(f(x)) \in {{\mathbb {F}}}_p[x]\). We note that g is an irreducible polynomial by using [16, Lemma 2.4]. We know that if p is a prime number, \(\left( \frac{.}{p}\right)\) is the Legendre symbol and \(\gamma\) is the quadratic character of \({{\mathbb {F}}}_{p^k}\) then for \(\alpha \in {{\mathbb {F}}}^{*}_{p^k}\) we have

$$\begin{aligned} \gamma (\alpha ) = \left( \frac{N_{{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(\alpha )}{p}\right) . \end{aligned}$$

By [16, Lemma 2.3], we know that if \(f\in {{\mathbb {F}}}_{p^k}[x]\) then for \(\alpha \in {{\mathbb {F}}}_p\) we have

$$\begin{aligned} N_{{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(f(\alpha ))=N_{{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(f)(\alpha ). \end{aligned}$$

Finally, using (7) we get

$$\begin{aligned} \epsilon _s= &\, {} \gamma (\alpha +i_s)=\gamma (f(i_s))=\left( \frac{N_ {{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(f(i_s))}{p}\right) =\left( \frac{N_{{{\mathbb {F}}}_{p^k}/{{\mathbb {F}}}_p}(f)(i_s))}{p}\right) \\= &\, {} \left( \frac{g(i_s)}{p}\right) \text{ for } s=1,2,\ldots ,j, \end{aligned}$$

as desired. \(\square\)

Corollary 1

Let p be an odd prime and K be a positive integer. Let A and B be defined as in Theorem 1. Then

$$\begin{aligned} \varGamma ({{\mathcal {F}}}(K,p)) \ge \min \left\{ p, \log _{2}\left( \frac{A}{W(2^BA)}\right) \right\} . \end{aligned}$$

Proof

We know that \({{\mathcal {F}}}_{\mathrm{irred}}(K,p)\subset {{\mathcal {F}}}(K,p)\) and \(\varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(k,p)) \ge \log _{2}\frac{A}{W(2^BA)}\) by Theorem 1. Thus we get the result. \(\square\)

Now, we consider the upper bound for the W function given in Lemma 1 and we get an approximation for the bound given in Theorem 1. Before that, we give a lemma which we use in Corollary 2 for proving that Theorem 1 provides a better bound than Theorem A.

Lemma 7

Let p be an odd prime, k be a positive integer and c be defined as in Theorem A. Then,

$$\begin{aligned} \min \left\{ p, \log _{2}\frac{p^{k/2}}{\ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) } \right\} \ge \min \left\{ p,\frac{k-c}{2\ln 2}\ln p\right\} . \end{aligned}$$

Proof

For \(k\le \frac{p^{1/4}}{10\ln p}\), we have \(c=1/2\) and so

$$\begin{aligned} \frac{k-1/2}{2\ln 2}\ln p = \log _2 p^{k/2} - \log _2 p^{1/4}. \end{aligned}$$

Hence, we need to show that

$$\begin{aligned} \ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) < p^{1/4}. \end{aligned}$$

We have the following upper bound for the left hand side

$$\begin{aligned} \ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) = \ln \left( \frac{8}{\ln 8p^{k/2}}\right) + \ln p^{k/2}\le & {} \ln \left( \frac{8}{\ln 8p^{k/2}}\right) + \ln p^{\frac{p^{1/4}}{20\ln {p}}} \\= &\, {} \ln \left( \frac{8}{\ln 8p^{k/2}}\right) + \frac{p^{1/4}}{20} \end{aligned}$$

which is obviously less than \(p^{1/4}\) for all primes p and positive integers k.

For \(k > \frac{p^{1/4}}{10\ln p}\), the proof follows by using the fact that the f-complexity can not exceed p, that is

$$\begin{aligned} p\ge \log _{2}\frac{p^{k/2}}{\ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) }. \end{aligned}$$

\(\square\)

Corollary 2

Let \(p>41\) be a prime and k be a positive integer. Then,

$$\begin{aligned} \varGamma ({{\mathcal {F}}}_{\mathrm{irred}}(k,p)) \ge \min \left\{ p, \log _{2}\frac{p^{k/2}}{\ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) }\right\} . \end{aligned}$$

Moreover, this lower bound is greater than the lower bound given in Theorem A.

Proof

We know that \(|G_{p,k}|\le 2p^{k/2}\) by [16, Lemma 2.5]. Hence, \(B < 2\) and \(A=\frac{2p^{k/2}(1-p^{-k/2})}{1+p^{-k/2}} < 2p^{(k/2)}\) where A and B are defined as in Theorem 1. By these inequalities and Lemma 1, we get

$$\begin{aligned} \log _{2}\left( \frac{A}{W(2^BA)}\right)\ge & {} \log _2\left( \frac{A}{\ln (4A)-\ln \ln (4A)+\frac{e}{e-1}\frac{\ln \ln (4A)}{\ln (4A)}}\right) \\= &\, {} \log _2A-\log _2\left( \ln \left( \frac{4A}{\ln (4A)}\right) +\frac{e}{e-1}\frac{\ln \ln (4A)}{\ln (4A)}\right) \\\ge & {} \log _2A-\log _2\left( \ln \left( \frac{8p^{k/2}}{\ln (8p^{k/2})}\right) +\frac{e}{e-1}\frac{\ln \ln (8p^{k/2})}{\ln (8p^{k/2})}\right) \\\ge & {} \log _{2}p^{k/2}-\log _{2}\left( \ln \left( \frac{8p^{k/2}}{\ln 8p^{k/2}}\right) \right) \\&\qquad +\log _2\left( \frac{1-p^{-k/2}}{1+p^{-k/2}}\right) -\frac{e}{e-1}\frac{\ln \ln 8p^{k/2}}{\ln 8p^{k/2}}+1. \end{aligned}$$
(8)

where the last inequality follows from the definition of A and the properties of natural logarithm. Finally, let the error part E(p, k) be defined as

$$\begin{aligned} E(p,k) := \log _2\left( \frac{1-p^{-k/2}}{1+p^{-k/2}}\right) -\frac{e}{e-1}\frac{\ln \ln 8p^{k/2}}{\ln 8p^{k/2}}+1. \end{aligned}$$

E(p, k) increases when k increases and \(E(p,1) > 0\) for \(p>41\). Therefore, the first part of the corollary follows from Theorem 1. The second part is a direct consequence of Lemma 7. \(\square\)

Remark 1

We compare the ceiling values of the bounds given in Theorem 1, Corollary 2 and Eq. (8) for \(k=10\) and \(p<8000\) in Fig. 2, where we just plot the gap between the bounds. We see that the bound given in Theorem 1 differs from the bound (8) in at most 1, and at most 2 from the bound given in Corollary 2.

Fig. 2
figure 2

Gap between the bounds given in Theorem 1 and Eq. (8), Corollary 2 and Eq. (8), respectively

Full size image

6 Comparison

In this section, we compare the lower bounds given in Theorem 1 and Theorem A.

Firstly in Figs. 3, 4 and 5 we show that the bound given in Theorem 1 is better than the bound given in Theorem A. The red line shows the bound given in Theorem A and the blue line the bound given in Theorem 1. Both bounds are plotted with respect to primes \(p<8000\) for \(k=1,2,\ldots ,10\), respectively. For \(k=1\) and \(k=2\), the bound given in [16] is negative for the primes in the range, on the other hand, the bound given in Theorem 1 is always positive. We note that the bound given in [16] turns into positive for \(p \ge 2128240847\) and \(k=1\). For \(3\le k\le 10\), we see that both bounds are positive and the bound given in Theorem 1 is better than the bound given in Theorem A for all \(p<8000\). We conclude that our bound is better than the bound given in Theorem A for small values of k, but they are close to each other for large values of k. In Fig. 6, the lower bound on the f-complexity of the sequences given in Definition 7 is plotted in the range \(k \in [1,50]\) for \(p=10000019\) and \(p=2128240847\), respectively. Here, \(p=10000019\) is the first prime greater than \(10^7\) and \(p=2128240847\) is the first prime for which the bound given in Theorem A turns into positive for \(k=1\). In both cases, both lower bounds are close, but the one in Theorem 1 is better.

Fig. 3
figure 3

Lower bound on the f-complexity of Legendre sequence with respect to p for \(k=1,2,3,4\), respectively

Full size image
Fig. 4
figure 4

Lower bound on the f-complexity of Legendre sequence with respect to p for \(k=5,6,7,8\), respectively

Full size image
Fig. 5
figure 5

Lower bound on the f-complexity of Legendre sequence with respect to p for \(k=9,10\), respectively

Full size image
Fig. 6
figure 6

Lower bound on the f-complexity of Legendre sequence with respect to k for \(p=10000019\) and \(p=2128240847\), respectively

Full size image

Secondly, we compare the two bounds in terms of time complexity. The bound given in Theorem 1 is based on the W function, so it can be argued that it would take more time. However, calculating the W function is not slow. In particular, Figs. 7 and 8 show the time difference between the bounds given in Theorem A and Theorem 1. We first measure the time (in seconds) it takes for calculating both bounds for all values of p and k that we have already examined in Figs. 3, 4 and 5. Then we plot the difference in seconds between both bounds in Figs. 7 and 8, which show that both bounds take time quite close to each other for all p and k. For instance, in Fig. 7 for \(k=1\), the bound given in Theorem 1 takes more time, the difference is at most 0.005 seconds. On the other hand, for \(k=10\) the bound given in Theorem A takes more time and the difference is at most 0.01 s. Similarly, Fig. 8 shows that the time difference between both bounds is at most 0.06 s for primes \(p=10000019\), \(p=2128240847\) and \(k \in \{1,2,\ldots ,2000\}\). We conclude that the bound given in Theorem 1 can be calculated very fast for arbitrarily large prime powers and it only differs in a few milliseconds from calculation time of the bound depending only on p and k. We note that all figures in this paper were plotted using SageMath [35], and SageMath uses Eq. (2) for a numerical approximation on the W function.

Fig. 7
figure 7

Time difference between the bounds given in Theorem A and Theorem 1 with respect to p for \(k=1\) and \(k=10\), respectively

Full size image
Fig. 8
figure 8

Time difference between the bounds given in Theorem A and Theorem 1 with respect to k for \(p=10000019\) and \(p=2128240847\), respectively

Full size image

7 Conclusion

In this paper we study the family of Legendre sequences generated by irreducible polynomials over a prime finite field and its f-complexity. The main aim of this work is to give a better bound on the f-complexity of this family. We present a new lower bound on the f-complexity depending on the Lambert W function. Then we approximate the W function so that we get another bound depending only on logarithmic functions. Also we prove that this bound strictly improves the previously known bounds. It would be a good future work to construct Legendre sequences by using the irreducibles of degree \(k>k_0\) for some positive integer \(k_0\) for getting a better family complexity bound, and to apply the bounds obtained in this paper to improve the bounds for other randomness measures.