Nonlinear complexity from the Hermitian and the Suzuki function fields

Official URL: https://dx.doi.org/10.1007/s00200-023-00629-z

The notion of k- th order nonlinear complexity has been studied from various aspects. Geil, Özbudak and Ruano (Semigroup Forum 98:543–555, 2019) gave a construction of a sequence of length (q- 1) (q2- 1) with high nonlinear complexity by using the Weierstrass semigroup of two distinct rational points on a Hermitian function field over Fq2 , and they improved the bounds on the k- th order nonlinear complexity Nk(s) and Lk(s) obtained by Niederreiter and Xing (IEEE Trans Inf Theory 60(10):6696–6701, 2014), where Fq2 is the finite field with q2 elements, and q is a prime power. In this work, we exhibit the lower bounds on Nk(s) and Lk(s) on a Hermitian function field using Hermitian triangles over Fq2. We study the effect of a Hermitian triangle by its type. The possible cases on the k-th order nonlinear complexity are explained, for each type, and we improve the lower bounds obtained by Geil et al. We construct two different sequences with the help of the Weierstrass semigroup of l distinct collinear rational points, and we compare our results of the lower bounds on Nk(s) and Lk(s). Also, we study the lower bounds on Nk(s) and Lk(s) using the Weierstrass semigroup of two distinct rational points on a Suzuki function field over Fq, where q=2q02,q0=2t,t≥1.