Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve (Q2416387)

Let $\mathbf{s}=(s_1,s_2,\dots,s_n)\in F_q^n$ and $k$ be an integer $\geq 0$. If $\mathbf{s} \neq 0$, then we denote by $N_k(\mathbf{s})$ (respectively $L_k(\mathbf{s})$) the smallest integer $m \geq 0$ for which there exists a polynomial $f \in F_q[x_1, \dots , x_m]$ with $\deg_{x_i} f \leq k$ (respectively $\deg f \leq k$) such that $s_{i+m} = f (s_i, s_{i+1}, \dots, s_{i+m-1})$ for $1 \leq i \leq n - m$. If $\mathbf{s} = 0$, then we set $N_k(\mathbf{s}) = L_k(\mathbf{s}) =0$. The quantities $N_k(\mathbf{s})$ and $L_k(\mathbf{s})$ are referred as $k$-th order nonlinear complexity of $\mathbf{s}$. Furthermore, the Hermitian function field is the field $H = F_{q^2}(x, y)$ with $y^q + y = x^{q+1}$. In this paper, using the Weierstrass semigroup of a pair of distinct points of a Hermitian curve over a finite field, lower bounds for the quantities $N_k(\mathbf{s})$ and $L_k(\mathbf{s})$ are computed. These results improve bounds obtained by \textit{H. Niederreiter} and \textit{C. Xing} [IEEE Trans. Inf. Theory 60, No. 10, 6696--6701 (2014; Zbl 1360.94284)].