Linearly recurring solution sequences for equations over finite fields (Q762216)

A sequence \(\{a_ t\}\) of integers satisfies a linear recurrence if there exist positive integers h and \(t_ 0\), and rational numbers \(c_ 1,...,c_ h\) so that for all \(t\geq t_ 0\), \(a_ t=\sum^{h}_{i=1}\) \(c_ ia_{t-i}\). The minimal h is called the order of the sequence. Let \(K=GF(q)\), f(x)\(\in K[x]\) and let \(N_ t\) be the number of t-tuples \((x_ 1,...,x_ t)\in K^ t\) which satisfy \(\sum^{t}_{i=1}\) \(f(x_ i)=0\). In this paper the author studies conditions under which \(\{N_ t\}\) satisfies a linear recurrence. For example if K has characteristic p, it is shown that if \(f(x)=x^ d\) \((d>1)\) with \(d| (q-1)\) and \((d,(q-1)/(p-1))=1\), then \(\{N_ t\}\) satisfies a linear recurrence of order \(d+1\). Extensions are also given to systems of equations which generalize a result of \textit{S. Chowla}, \textit{J. Cowles} and \textit{M. Cowles} [J. Number Theory 9, 502-506 (1977; Zbl 0363.10013)].