On the distribution of values of recurring sequences and the Bell numbers in finite fields (Q2277018)

Let u(x) \((x=1,2,...)\) be a recurring sequence of order \(n\geq 2\) of elements of the finite field \({\mathbb{F}}_ q\) \((q=p^ r\), p a prime and \(r\geq 1)\), defined by the relation \[ u(x+n)=c_{n-1}u(x+n-1)+...+c_ 0u(x), \] where \(c_ 0,...,c_{n-1}\in {\mathbb{F}}_ q\) with \(c_ 0\neq 0\). It is known that the sequence u(x) is periodic with the period \(\tau \leq q^ n-1.\) We denote by I the smallest (positive) solution x of the equation \(u(x)=0\) if it exists, and let \(I=\infty\) if it does not. A conventional method of exponential sums gives us the estimate \((1)\quad I=O(q^{n/2} \log \tau)\) if \(I<\infty\), whereas the author has proved by a new combinatorial argument that the assumption \(I<\infty\) implies \((2)\quad I\leq \left( \begin{matrix} q+n-1\\ n-1\end{matrix} \right)+1,\) which is stronger than (1) for \(n\geq n_ 0(q)\sim eq^{1/2}\) [Mat. Zametki, 42, 494-507 (1987; Zbl 0635.10006), Engl. translation in Math. Notes 42, 773- 780 (1987)]. Here, using some combinatorial considerations, he improves the bound (2) for \(r>1\); thus, for p fixed it is shown that \(I<\infty\) implies \(I\leq q^{c \log n}\) with \(c=p/\log 2\), a constant depending on p. It is also proved that for the sequence of Bell numbers B(x) the congruence B(x)\(\equiv \lambda (mod p)\), p a prime, has for any integer \(\lambda\) a solution x with \(0\leq x\leq \left( \begin{matrix} 2p-1\\ p-1\end{matrix} \right)\).