Nonlinear complexity from the Hermitian and the Suzuki function fields (Q6962824)

Let \(s = (s_1, s_2, \ldots, s_n)\) be a sequence of length \(n \ge 1\) over the finite field \(\mathbb{F}_q\), and let \(k \in \mathbb{N}\). If \(s_i = 0\) for all \(1 \le i \le n\), the \(k\)-th order nonlinear complexity \(N^{k}(s)\) is defined to be \(0\). Otherwise, \(N^{k}(s)\) is the smallest integer \(m \in \mathbb{N}\) for which there exists a polynomial \(f \in \mathbb{F}_q[x_1, \ldots, x_m]\) of degree at most \(k\) in each variable such that\N\[\Ns_{m+I} = f(s_I, s_{I+1}, \ldots, s_{m+I-1}), \qquad I = 1, \ldots, n - m.\N\]\NSimilarly, the \(k\)-th order nonlinear complexity of \emph{total degree}, denoted by \(L^{k}(s)\), is defined as follows. If \(s_i = 0\) for all \(1 \le i \le n\), then \(L^{k}(s) = 0\). Otherwise, \(L^{k}(s)\) is the smallest \(m \in \mathbb{N}\) for which there exists a polynomial \(f \in \mathbb{F}_q[x_1, \ldots, x_m]\) of total degree at most \(k\) satisfying\N\[\Ns_{m+I} = f(s_I, s_{I+1}, \ldots, s_{m+I-1}), \qquad I = 1, \ldots, n - m.\N\]\NFor any sequence \(s\) and any \(k \in \mathbb{N}\), it is immediate that \(L^{k}(s) \geq N^{k}(s)\).\N\NThis paper investigates sequences of high nonlinear complexity arising from the Hermitian and Suzuki function fields. Relations among Hermitian triangles determined by three distinct rational points on the Hermitian function field are examined, and lower bounds for the \(k\)-th order nonlinear complexities \(N^{k}(s_n)\) and \(L^{k}(s_n)\) are established. In particular, an existing lower bound for \(L^{k}(s_n)\) is strengthened, and several possible behaviors of the \(k\)-th order nonlinear complexity associated with each type of Hermitian triangle are analyzed.\N\NMoreover, two different families of sequences are constructed using the corresponding Weierstrass semigroup, and the resulting lower bounds on \(N^{k}(s)\) and \(L^{k}(s)\) are compared. Finally, the paper studies lower bounds on \(N^{k}(s)\) and \(L^{k}(s)\) derived from the Weierstrass semigroup of two distinct rational points on a Suzuki function field over \(\mathbb{F}_q\), where \(q = 2 q_0^2\), \(q_0 = 2^t\), and \(t \geq 1\).