Abstract:
Let $P$ be the finite field with $q$ elements and let $F_1(x),\ldots,F_k(x)$ be pairwise coprimes polynomials over the field $P$ with the conditions $F_1(0)\ne 0$, $\ldots$, $F_k(0)\ne 0$, $\deg F_1(x)=m_1$, $\ldots$, $\deg F_k(x)=m_k$. For every $j=1,\ldots,k$ we consider resilient system of linear recurrent sequences $u_{j1},u_{j2},\ldots,u_{jt_j}$ over the field $P$ with minimal polynomial $F_j(x)$. We study the sequences $v$ constructed by the rule $v(i)=\varphi(v_1(i),\ldots,v_k(i))$, $i\ge 0$, where $v_j(i)=\varphi_j(u_{j1}(i),\ldots,u_{jt_j}(i))$ and $\varphi:P^k\to P$, $\varphi_j:P^{t_j}\to P$ for all $j=1,2,\ldots,k$. Let $N_l(z,v)$ denote the number of appearances of element $z\in P$ in the sequence $v(0),v(1),\ldots,v(l-1)$. When $\varphi_1,\ldots,\varphi_k$ are balanced functions and the function $\varphi$ is bijective for all of its variables, we prove that $$\left| N_l(z, v) - \frac{l}{q}\right| \le (q-1)\sigma(\varphi) \sigma(\varphi_1)\ldots \sigma(\varphi_k)\left(\frac{4}{\pi^2} \ln T(F) + \frac{9}{5}\right)q^{({m_1+\ldots+m_k})/{2}-1}, $$ where $\sigma(\varphi),\sigma(\varphi_1),\ldots,\sigma(\varphi_k)$ are the curvatures of the functions. We generalize this result to the case of $r$-tuples.
Keywords:finite fields, linear recurrent sequences, linear feedback shift registers, combination generators, filter generators.