1 Introduction

For an odd prime number N, the N-periodic Legendre sequence is defined as

$$\begin{aligned} s_u=\left\{ \begin{array}{ll} \frac{1+(\frac{u}{N})}{2}, &{}\quad \mathrm {if}\quad \gcd (u,N)=1,\\ 0, &{} \quad \mathrm {otherwise}, \end{array} \right. \quad u \ge 0, \end{aligned}$$
(1)

where \((\frac{\cdot }{N})\) is the Legendre symbol. Let g be a (fixed) primitive root modulo N, one can define the cyclotomic classes

$$\begin{aligned} D_0=\{g^{2k} \pmod N : 0\le k<(N-1)/2\} \end{aligned}$$

and

$$\begin{aligned} D_1=gD_0=\{g^{2k+1}\pmod N: 0\le k<(N-1)/2\}. \end{aligned}$$

Then we get an equivalent definition of the Legendre sequence

$$\begin{aligned} s_u=\left\{ \begin{array}{ll} 0, &{}\quad \mathrm {if}\ u\bmod N \in D_1\cup \{0\},\\ 1, &{}\quad \mathrm {if}\ u\bmod N \in D_0, \end{array} \right. \quad u \ge 0. \end{aligned}$$
(2)

The Legendre sequences \((s_u)\) have been extensively studied in the literature. They have strong pseudorandomness properties: equidistribution, optimal correlation, high linear complexity, etc., see [3, 4, 6, 9, 10, 14, 18, 23]. Aly, Winterhof [1] studied the k-error linear complexity (over \({\mathbb {F}}_N\)) by viewing the N-periodic \((s_u)\) as a sequence over \({\mathbb {F}}_N\).

In particular, for certain applications to coding theory, some binary sequences are discussed over different finite fields (not in \({\mathbb {F}}_2\)) [7, 8]. Partially motivated by the study, Wang et al considered the N-periodic Legendre sequence \((s_u)\) in \({\mathbb {F}}_p\), where p is an odd prime (or a prime-power) with \(\gcd (p,N)=1\), and investigated the linear complexity and minimal polynomials over \({\mathbb {F}}_p\) in [11, 21, 22]. Certain work had actually been done by He in [13]. In this work, we will continue this project to investigate the trace representation of N-periodic Legendre sequence \((s_u)\) in \({\mathbb {F}}_p\) (not in \({\mathbb {F}}_2\)). We should remark that, the trace representation of \((s_u)\) of Mersenne prime period and of any prime period have been described via trace functions from \({\mathbb {F}}_{2^{n}}\) to \({\mathbb {F}}_2\), where n is the order of 2 modulo N, by No et al in [19] and by Kim et al in [15], sequentially. Some special cases have been studied in [20] recently.

We will compute the Mattson–Solomon polynomial (see definition below) of \((s_u)\) and present the trace representation by using trace functions over \({\mathbb {F}}_p\). For any N-periodic p-ary sequence \((t_u)\), there always exists a polynomial G(X) defined over finite fields of characteristic p such that

$$\begin{aligned} t_u=G(\beta ^u), \quad u\ge 0, \end{aligned}$$

where \(\beta \) is an Nth root of unity in an extension field of \({\mathbb {F}}_p\). G(X) is unique if its degree is smaller than N, see [16]. Such G(X) is called the Mattson–Solomon polynomial of \((t_u)\) in coding theory [17]. Dai et al called G(X) as a defining polynomial and \((G(X),\beta )\) as the defining pair of \((t_u)\) in [5], where they discussed trace representation and linear complexity of certain binary sequences.

Throughout the work, we always let p be an odd prime and co-prime to N, the period of Legendre sequences.

2 Mattson–Solomon polynomials

Define polynomials

$$\begin{aligned} d_l(X)= \sum \limits _{u\in D_l}X^u \in {\mathbb {F}}_p[X], \quad l=0,1. \end{aligned}$$

We need the following technical lemma.

Lemma 1

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\). For any fixed pair of integers i, j with \(0\le i,j<2\), we have

$$\begin{aligned} d_i(\beta )d_j(\beta )+d_{i+1}(\beta )d_{j+1}(\beta ) +\frac{N-1}{2} =\left\{ \begin{array}{ll} N, &{}\quad \mathrm {if}\,\ \frac{N-1}{2}+i-j\equiv 0 \pmod 2, \\ 0, &{}\quad \mathrm {otherwise}. \end{array} \right. \end{aligned}$$

Here and hereafter, the subscript of d is performed modular 2.

Proof

We calculate

$$\begin{aligned} d_i(\beta )d_j(\beta )+d_{i+1}(\beta )d_{j+1}(\beta )= & {} \sum \limits _{k=0}^{1}~\sum \limits _{u\in D_0}\beta ^{ug^{i+k}}~\sum \limits _{v\in D_0}\beta ^{vg^{j+k}}\\= & {} \sum \limits _{k=0}^{1}~\sum \limits _{u\in D_0}\beta ^{ug^{i+k}}~\sum \limits _{w\in D_0}\beta ^{uwg^{j+k}}\\&~~~(\mathrm {we~ use~ } v=uw)\\= & {} \sum \limits _{k=0}^{1}~\sum \limits _{u\in D_0}~\sum \limits _{w\in D_0}\beta ^{ug^{j+k}(g^{i-j}+w)}\\= & {} \sum \limits _{w\in D_0}~\sum \limits _{k=0}^{1}~~\sum \limits _{z\in D_{j+k}}\gamma _w^z\\&\quad \left( \mathrm {we~ use~ } z=ug^{j+k}, \gamma _w=\beta ^{g^{i-j}+w}\right) \\= & {} \sum \limits _{w\in D_0}~\sum \limits _{z=1}^{N-1}\gamma _w^z. \end{aligned}$$

Let \(\mathrm {ord}(\gamma _w)\) denote the order of \(\gamma _w\). We note that \(\mathrm {ord}(\gamma _w)|N\) since \(\beta \) is a primitive Nth root of unity. If \(\mathrm {ord}(\gamma _w)= N\), then we have

$$\begin{aligned} \sum \limits _{z=1}^{N-1}\gamma _w^z=\sum \limits _{z=0}^{N-1}\gamma _w^z-1=\frac{1-\gamma _w^N}{1-\gamma _w}-1=-1\in {\mathbb {F}}_p. \end{aligned}$$

If \(\mathrm {ord}(\gamma _w)= 1\), then we have

$$\begin{aligned} \sum \limits _{z=1}^{N-1}\gamma _w^z=N-1\in {\mathbb {F}}_p. \end{aligned}$$

Now we need to determine the number of \(w\in D_0\) with \(\mathrm {ord}(\gamma _w)=1\) and the number of \(w\in D_0\) with \(\mathrm {ord}(\gamma _w)=N\).

We have \(\mathrm {ord}(\gamma _w)= 1\) if and only if \(g^{i-j}+w \equiv 0 \pmod {N}\), which is equivalent to \(w \equiv g^{(N-1)/2+i-j}\pmod {N}\). This implies that \(2|((N-1)/2+i-j)\) since \(w\in D_0\). That is to say, there exists an \(w\in D_0\) such that \(g^{i-j}+w \equiv 0 \pmod {N}\), which holds if and only if \(2|((N-1)/2+i-j)\). In this case w is unique. We conclude that if \(2|((N-1)/2+i-j)\), then there are \((N-1)/2-1\) elements \(w\in D_0\) such that \(\mathrm {ord}(\gamma _w)= N\) and one \(w\in D_0\) such that \(\mathrm {ord}(\gamma _w)= 1\), while if \(2\not \mid (N-1)/2+i-j)\), all \(w\in D_0\) satisfy \(\mathrm {ord}(\gamma _w)= N\).

Putting everything together, we derive

$$\begin{aligned} d_i(\beta )d_j(\beta )+d_{i+1}(\beta )d_{j+1}(\beta ) =\left\{ \begin{array}{ll} \frac{N+1}{2}, &{}\quad \mathrm {if}\,\ 2|\left( \frac{N-1}{2}+i-j\right) , \\ -\frac{N-1}{2}, &{}\quad \mathrm {otherwise}. \end{array} \right. \end{aligned}$$

This completes the proof. \(\square \)

Theorem 1

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\). Then the Mattson–Solomon polynomial of \((s_u)\) defined in Eq. (1) or Eq. (2) is

$$\begin{aligned} G(X)= N^{-1} \left( d_0(\beta )d_0(X)+d_{1}(\beta )d_{1}(X) +\frac{N-1}{2}\right) \end{aligned}$$

if \(N\equiv 1 \pmod 4\), and otherwise

$$\begin{aligned} G(X)= N^{-1} \left( d_0(\beta )d_1(X)+d_{1}(\beta )d_{0}(X) +\frac{N-1}{2}\right) . \end{aligned}$$

Proof

We get from Lemma 1 that

$$\begin{aligned} (d_0(\beta ))^2+(d_1(\beta ))^2+\frac{N-1}{2} =\left\{ \begin{array}{ll} N, &{}\quad \mathrm {if}\,\ N\equiv 1 \pmod 4, \\ 0, &{}\quad \mathrm {if}\,\ N\equiv -1 \pmod 4, \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} 2d_0(\beta )d_1(\beta )+\frac{N-1}{2} =\left\{ \begin{array}{ll} 0, &{}\quad \mathrm {if}\,\ N\equiv 1 \pmod 4, \\ N, &{}\quad \mathrm {if}\,\ N\equiv -1 \pmod 4. \end{array} \right. \end{aligned}$$

Note that \(d_i(\beta ^u)=d_{i+j}(\beta )\) if \(u\in D_j\), where \(i,j\in \{0,1\}\) and the subscript of d is performed modulo 2. Now, we discuss the Mattson–Solomon polynomial of \((s_u)\).

Case 1 \(N\equiv 1 \pmod 4\).

For \(u\in D_0\), we have

$$\begin{aligned} G(\beta ^u)= & {} N^{-1} \left( d_{0}(\beta )d_{0}(\beta ^u)+d_{1}(\beta )d_{1}(\beta ^u) +\frac{N-1}{2}\right) \\= & {} N^{-1} \left( (d_{0}(\beta ))^2+(d_{1}(\beta ))^2 +\frac{N-1}{2}\right) \\= & {} N^{-1}\cdot N=1=s_u. \end{aligned}$$

For \(u\in D_1\), we have

$$\begin{aligned} G(\beta ^u)= & {} N^{-1} \left( d_{0}(\beta )d_{0}(\beta ^u)+d_{1}(\beta )d_{1}(\beta ^u) +\frac{N-1}{2}\right) \\= & {} N^{-1} \left( d_{0}(\beta )d_{1}(\beta )+d_{1}(\beta )d_{0}(\beta ) +\frac{N-1}{2}\right) \\= & {} N^{-1} \left( 2d_{0}(\beta )d_{1}(\beta ) +\frac{N-1}{2}\right) \\= & {} N^{-1}\cdot 0=0=s_u. \end{aligned}$$

For \(u=0\), we note that

$$\begin{aligned} d_0(1)=d_1(1)=\frac{N-1}{2}, \end{aligned}$$

and

$$\begin{aligned} d_0(\beta )+d_1(\beta )=\sum \limits _{u=1}^{N-1}\beta ^u =\sum \limits _{u=0}^{N-1}\beta ^u-1=\frac{1-\beta ^N}{1-\beta }-1=-1. \end{aligned}$$

Then, we get

$$\begin{aligned} G(\beta ^0)= & {} N^{-1} \left( d_{0}(\beta )d_{0}(1)+d_{1}(\beta )d_{1}(1) +\frac{N-1}{2}\right) \\= & {} N^{-1}\left( -\frac{N-1}{2}+\frac{N-1}{2}\right) =0=s_u. \end{aligned}$$

Putting everything together, we derive that

$$\begin{aligned} G(X)= N^{-1} \left( d_0(\beta )d_0(X)+d_{1}(\beta )d_{1}(X) +\frac{N-1}{2}\right) \end{aligned}$$

is the Mattson–Solomon polynomial of \((s_u)\) when \(N\equiv 1 \pmod 4\).

Case 2 \(N\equiv -1 \pmod 4\).

It can be verified in a similar way. \(\square \)

Now we further consider the values of \(d_0(\beta )\) and \(d_1(\beta )\) in Theorem 1.

Lemma 2

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\) and p a quadratic residue class modulo N (i.e., \(p\in D_0\)). If N satisfies one of the following two conditions

  1. (1)

    \(N\equiv 1 \pmod 4\) and \(N\equiv 1 \pmod {p}\),

  2. (2)

    \(N\equiv -1 \pmod 4\) and \(N\equiv -1 \pmod {p}\),

then we have

$$\begin{aligned} \left\{ \begin{array}{l} d_0(\beta )=0, \\ d_1(\beta )=-1, \end{array} \right. \quad or \quad \left\{ \begin{array}{l} d_0(\beta )=-1, \\ d_1(\beta )=0, \end{array} \right. \end{aligned}$$

and otherwise we have

$$\begin{aligned} d_0(\beta ), d_1(\beta )\in {\mathbb {F}}_p{\setminus }\{0\}, \end{aligned}$$

which means that both \(d_0(\beta )\) and \(d_1(\beta )\) are non-zero.

Proof

Firstly, we have \(d_{0}(\beta )=d_{0}(\beta ^p)=(d_{0}(\beta ))^p\) since \(p \in D_0\). That is to say \(d_{0}(\beta )\in {\mathbb {F}}_p\). Similarly, we have \(d_{1}(\beta )\in {\mathbb {F}}_p\).

For \(N\equiv 1 \pmod 4\), we see that in the proof of Theorem 1

$$\begin{aligned} (d_{0}(\beta ))^2+(d_{1}(\beta ))^2=\frac{N+1}{2}= 1 \end{aligned}$$

if and only if \(N\equiv 1 \pmod p\). So together with \(d_0(\beta )+d_1(\beta )=-1\), we get for \(N\equiv 1 \pmod p\)

$$\begin{aligned} 2d_0(\beta )d_1(\beta )=0, \end{aligned}$$

which derives that either \(d_0(\beta )\) or \(d_1(\beta )\) is zero. Then, it is easy to get that

$$\begin{aligned} \left\{ \begin{array}{l} d_0(\beta )=0, \\ d_1(\beta )=-1, \end{array} \right. \quad \mathrm{or} \quad \left\{ \begin{array}{l} d_0(\beta )=-1, \\ d_1(\beta )=0. \end{array} \right. \end{aligned}$$

For \(N\equiv -1 \pmod 4\), we get similarly \(2d_0(\beta )d_1(\beta )=\frac{N+1}{2}=0\) if and only if \(N\equiv -1 \pmod p\) and then the result is derived.

The proof above also tells us that

$$\begin{aligned} 2d_0(\beta )d_1(\beta )\ne 0 \end{aligned}$$

for other N. \(\square \)

Lemma 3

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\) and p a quadratic non-residue class modulo N (i.e., \(p\in D_1\)). Then both \(d_0(\beta )\) and \(d_1(\beta )\) are non-zero.

Proof

Since \(p \in D_1\), we have for \(i=0,1\)

$$\begin{aligned} (d_{i}(\beta ))^p=d_i(\beta ^p)=d_{i+1}(\beta )=-1-d_i(\beta ), \end{aligned}$$

which indicates both \(d_0(\beta )\) and \(d_1(\beta )\) are non-zero. \(\square \)

From Theorem 1 and Lemmas 2 and 3, we immediately get the following results.

Theorem 2

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\), p a quadratic residue class modulo N (i.e., \(p\in D_0\)) and \((s_u)\) defined in Eq. (1) or Eq. (2).

  1. (1)

    For N satisfying \(N\equiv 1 \pmod 4\) and \(N\equiv 1 \pmod {p}\), if we suppose \(d_0(\beta )=0\) (of course we can also suppose \(d_1(\beta )=0\)), then the Mattson–Solomon polynomial of \((s_u)\) is

    $$\begin{aligned} G(X)= -N^{-1}d_{1}(X). \end{aligned}$$
  2. (2)

    For N satisfying \(N\equiv -1 \pmod 4\) and \(N\equiv -1 \pmod {p}\), if we suppose \(d_0(\beta )=0\) (of course we can also suppose \(d_1(\beta )=0\)), then the Mattson–Solomon polynomial of \((s_u)\) is

    $$\begin{aligned} G(X)= -N^{-1}d_{1}(X)+N^{-1}. \end{aligned}$$
  3. (3)

    For other N, the Mattson–Solomon polynomial of \((s_u)\) is

    $$\begin{aligned} G(X)= N^{-1}\Big ( \rho d_1(X)-(1+\rho )d_{0}(X) +\frac{N-1}{2}\Big ). \end{aligned}$$

    where \(\rho =d_0(\beta )\) and \(\rho (1+\rho )\ne 0\).

Theorem 3

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\) and p a quadratic non-residue class modulo N (i.e., \(p\in D_1\)). Then the Mattson–Solomon polynomial of \((s_u)\) defined in Eq. (1) or Eq. (2) is

$$\begin{aligned} G(X)= N^{-1} \Big (\rho d_1(X)-(1+\rho )d_{0}(X) +\frac{N-1}{2}\Big ), \end{aligned}$$

where \(\rho =d_0(\beta )\) and \(\rho (1+\rho )\ne 0\).

3 Trace representation

In this section, we describe the trace representation of \((s_u)\). For n|m, the trace function from finite field \({\mathbb {F}}_{p^m}\) to \({\mathbb {F}}_{p^n}\) is defined as

$$\begin{aligned} \mathrm {Tr}_{n}^{m}(X)=X+X^{p^n}+X^{p^{2n}}+\cdots +X^{p^{(m/n-1)n}}. \end{aligned}$$

The trace functions play an important role in sequences design [12].

Theorem 4

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\) , p a quadratic residue class modulo N (i.e., \(p\in D_0\)) and \((s_u)\) defined in Eq. (1) or Eq. (2). Let \(\ell \) be the order of p modulo N.

  1. (1)

    For N satisfying \(N\equiv 1 \pmod 4\) and \(N\equiv 1 \pmod {p}\), if we suppose \(d_0(\beta )=0\), then the trace representation of \((s_u)\) is

    $$\begin{aligned} s_u= -N^{-1}\sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_1^{\ell }\left( \beta ^{g^{2j+1}}\right) . \end{aligned}$$
  2. (2)

    For N satisfying \(N\equiv -1 \pmod 4\) and \(N\equiv -1 \pmod {p}\), if we suppose \(d_0(\beta )=0\), then the trace representation of \((s_u)\) is

    $$\begin{aligned} s_u= -N^{-1}\sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_1^{\ell }\left( \beta ^{g^{2j+1}}\right) +N^{-1}. \end{aligned}$$
  3. (3)

    For other N, the trace representation of \((s_u)\) is

    $$\begin{aligned} s_u=N^{-1}\left( \rho \sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_1^{\ell }\left( \beta ^{g^{2j+1}}\right) -(1+\rho )\sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_{1}^{\ell }\left( \beta ^{ug^{2j}}\right) +\frac{N-1}{2}\right) . \end{aligned}$$

    where \(\rho =d_0(\beta )\) and \(\rho (1+\rho )\ne 0\).

Proof

To get the trace presentation of s(u), we only need to describe \(d_0(X)\) and \(d_1(X)\) in Theorem 2 using trace functions.

Let U be set generated by p modulo N, i.e.,

$$\begin{aligned} U=\langle p\rangle =\{p^k\pmod N : 0\le k<\ell \}. \end{aligned}$$

Since \(p\in D_0\), we see that U is a subgroup of \(D_0\) (under the multiplication). Then \(D_0, D_1\) can be written as the union

$$\begin{aligned} D_0=\bigcup \limits _{k=0}^{\frac{N-1}{2\ell }-1}g^{2k}U,\quad D_1=\bigcup \limits _{k=0}^{\frac{N-1}{2\ell }-1}g^{2k+1}U. \end{aligned}$$

Write polynomial

$$\begin{aligned} u(X)=\sum \limits _{u\in U}X^u. \end{aligned}$$

Using the fact that

$$\begin{aligned} \mathrm {Tr}_1^{\ell }(X)&=X+X^p+X^{p^2}+\cdots +X^{p^{\ell -1}}\equiv u(X) \pmod {X^N-1}, \end{aligned}$$

we derive

$$\begin{aligned} d_{0}(X)=\sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}u\left( X^{g^{2j}}\right) \equiv \sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_1^{\ell }\left( X^{g^{2j}}\right) \pmod {X^N-1} \end{aligned}$$

and

$$\begin{aligned} d_{1}(X)=\sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}u\left( X^{g^{2j+1}}\right) \equiv \sum \limits _{j=0}^{\frac{N-1}{2\ell }-1}\mathrm {Tr}_1^{\ell }\left( X^{g^{2j+1}}\right) \pmod {X^N-1}. \end{aligned}$$

Then, replacing \(d_{0}(X)\) and \(d_{1}(X)\) in Theorem 2 and noting that \(s_u=G(\beta ^u)\), we finish the proof. \(\square \)

Theorem 5

Let \(\beta \) be a primitive Nth root of unity in an extension field of \({\mathbb {F}}_p\) and p a quadratic non-residue class modulo N (i.e., \(p\in D_1\)). Let \(\ell \) be the order of p modulo N. Then, the trace representation of \((s_u)\) defined in Eq. (1) or Eq. (2) is

$$\begin{aligned} s_u=N^{-1}\left( \rho \sum \limits _{j=0}^{\frac{N-1}{\ell }-1}\mathrm {Tr}_2^{\ell }\left( \beta ^{ug^{2j+1}}\right) -(1+\rho )\sum \limits _{j=0}^{\frac{N-1}{\ell }-1}\mathrm {Tr}_{2}^{\ell }\left( \beta ^{ug^{2j}}\right) +\frac{N-1}{2}\right) . \end{aligned}$$

where \(\rho =d_0(\beta )\) and \(\rho (1+\rho )\ne 0\).

Proof

The proof is similar to that of Theorem 4. From the condition \(p\in D_{1}\), we see that \(p^2\in D_{0}\) and the order of \(p^2\) modulo N is \(\frac{\ell }{2}\). We remark here that \(\ell \) is even. Indeed, if \(p\equiv g^{2k+1} \pmod {N}\) for some k, we get \(p^\ell \equiv g^{(2k+1)\ell }\equiv 1 \pmod {N}\), which indicates that \((N-1)|\ell (2k+1)\). Then \(\ell \) is even since \(N-1\) is even.

Now write

$$\begin{aligned} V=\langle p^2\rangle =\left\{ p^{2k} \pmod N : 0\le k<\frac{\ell }{2}\right\} . \end{aligned}$$

Then V is a subgroup of \(D_0\) and \(D_0, D_1\) can be represented as

$$\begin{aligned} D_0=\bigcup \limits _{k=0}^{\frac{N-1}{\ell }-1}g^{2k}V, \quad D_1=\bigcup \limits _{k=0}^{\frac{N-1}{\ell }-1}g^{2k+1}V. \end{aligned}$$

Similar to the proof of Theorem 4, we have

$$\begin{aligned} \mathrm {Tr}_{2}^{\ell }(X)=X+X^{p^2}+X^{p^{2\times 2}}+\cdots +X^{p^{2\times (\frac{\ell }{2}-1)}}\equiv v(X) \pmod {X^N-1}, \end{aligned}$$

where \(v(X)=\sum \limits _{u\in V}X^u\). Then we describe \(d_0(X)\) and \(d_1(X)\) as follows

$$\begin{aligned} d_{0}(X)=\sum \limits _{j=0}^{\frac{N-1}{\ell }-1}v\left( X^{g^{2j}}\right) \equiv \sum \limits _{j=0}^{\frac{N-1}{\ell }-1}\mathrm {Tr}_{2}^{\ell }\left( X^{g^{2j}}\right) \pmod {X^N-1} \end{aligned}$$

and

$$\begin{aligned} d_{1}(X)=\sum \limits _{j=0}^{\frac{N-1}{\ell }-1}v\left( X^{g^{2j+1}}\right) \equiv \sum \limits _{j=0}^{\frac{N-1}{\ell }-1}\mathrm {Tr}_{2}^{\ell }\left( X^{g^{2j+1}}\right) \pmod {X^N-1}. \end{aligned}$$

Then, replacing \(d_{0}(X)\) and \(d_{1}(X)\) in Theorem 3 and noting that \(s_u=G(\beta ^u)\), we finish the proof. \(\square \)

4 Remarks and conclusions

In this work, we view N-periodic Legendre sequences in \({\mathbb {F}}_2\) as in \({\mathbb {F}}_p\) and considered their trace representation by calculating Mattson–Solomon polynomials. The results extended the early work of No et al and Kim et al on trace representation over \({\mathbb {F}}_2\).

The way in this work also can be used to consider the trace representation if we put N-periodic Legendre sequences in rings, for example in \({\mathbb {Z}}_4\), the residue class ring modulo 4.

We finally remark that, there is a relationship between Mattson–Solomon polynomials of prime periodic sequences and their linear complexity[12, Theorem 6.3]. The linear complexity\(LC(t_u)\) of an N-period sequence \((t_u)\) over \({\mathbb {F}}_p\) is the least order L of a linear recurrence relation over \({\mathbb {F}}_p\)

$$\begin{aligned} t_{u+L} + c_{1}t_{u+L-1} +\cdots +c_{L-1}t_{u+1}+ c_Lt_u=0\quad \mathrm {for}\quad u \ge 0, \end{aligned}$$

where \(c_1, c_2, \ldots , c_{L}\in {\mathbb {F}}_p\). By [2], \(LC(t_u)\) equals the number of nonzero coefficients of the Mattson–Solomon polynomial G(x) of degree \(<N\). So from Theorems 2 and 3, we immediately derive the linear complexity of N-periodic Legendre sequences studied in [13, 22].