The nonlinear complexity of level sequences over Z/(4)

For any sequence $\underline{a}$ over $\mathrm{Z}/(2^2)$, there is an unique 2-adic expansion $\underline{a}={\underline{a}}_0+{\underline{a}}_1·2$, where ${\underline{a}}_0$ and ${\underline{a}}_1$ are sequences over $\{0,1\}$ and can be regarded as sequences over the binary field $\mathit{GF}(2)$ naturally. We call ${\underline{a}}_0$ and ${\underline{a}}_1$ the level sequences of $\underline{a}$. Let $f(x)$ be a primitive polynomial of degree $n$ over $\mathrm{Z}/(2^2)$, and $\underline{a}$ be a primitive sequence generated by $f(x)$. In this paper, we discuss how many bits of ${\underline{a}}_1$ can determine uniquely the original primitive sequence $\underline{a}$. This issue is equivalent with one to estimate the whole nonlinear complexity, $\mathit{NL}(f(x),2^2)$, of all level sequences of $f(x)$. We prove that $4n$ is a tight upper bound of $\mathit{NL}(f(x),2^2)$ if $f(x)(\mathrm{mod}2)$ is a primitive trinomial over $\mathit{GF}(2)$. Moreover, the experimental result shows that $\mathit{NL}(f(x),2^2)$ varies around $4n$ if $f(x)(\mathrm{mod}2)$ is a primitive polynomial over $\mathit{GF}(2)$. From this result, we can deduce that $\mathit{NL}(f(x),2^2)$ is much smaller than $L(f(x),2^2)$, where $L(f(x),2^2)$ is the linear complexity of level sequences of $f(x)$.