Linearly recurring solution sequences for equations over finite fields

From MaRDI portal





A sequence \(\{a_t\}\) of integers satisfies a linear recurrence if there exist positive integers \(h\) and \(t_0\), and rational numbers \(c_1, \ldots, c_h\) so that for all \(t\ge t_0\), \(a_t=\sum^h_{i=1}c_ia_{t-i}\). The minimal \(h\) is called the order of the sequence. Let \(K= \mathrm{GF}(q)\), \(f(x)\in K[x]\) and let \(N_t\) be the number of \(t\)-tuples \((x_1, \ldots, 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\mid (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)].











This page was built for publication: Linearly recurring solution sequences for equations over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762216)