On finite sequences satisfying linear recursions

Abstract:

For any field $k$\/ and any integers $m,n$ with $0 \leqs 2m \leqs n+1$, let $W_n$ be the \hbox{$k$\/-vector} space of sequences $(x_0,\ldots,x_n)$, and let $H_m \subseteq W_n$ be the subset of sequences satisfying a \hbox{degree-$m$} linear recursion --- that is, for which there exist $a_0,\ldots,a_m\in k$, not all zero, such that $$ \sum_{i=0}^m a_i x_{i+j} = 0 $$ holds for each $j=0,1,\ldots,n-m$. Equivalently, $H_m$ is the set of $(x_0,\ldots,x_n)$ such that the $(m+1) \times (n-m+1)$ matrix with $(i,j)$ entry $x_{i+j}$ ($0\leqs i\leqs m$, $0\leqs j \leqs n-m$) has rank at most~$m$. We use elementary linear and polynomial algebra to study these sets $H_m$. In particular, when $k$\/ is a finite field of~$q$ elements, we write the characteristic function of~$H_m$ as a linear combination of characteristic functions of linear subspaces of dimensions~$m$ \hbox{and $m+1$} in~$W_n$. We deduce a formula for the discrete Fourier transform of this characteristic function, and obtain some consequences. For instance, if the $2m+1$ entries of a square Hankel matrix of order $m+1$ are chosen independently from a fixed but not necessarily uniform distribution~$\mu$ on~$k$, then as $m\ra\infty$ the matrix is singular with probability approaching $1/q$ provided $\|\muhat\|\0_1 < q^{1/2}$. This bound $q^{1/2}$ is best possible if $q$ is a square.

Supported in part by the Packard Foundation

Department of Mathematics, Harvard University, Cambridge, MA 02138
elkies@math.harvard.edu
http://www.math.harvard.edu/~elkies/