  For any field k and any integers m,n with 0 <= 2m <= n+1, let W_n be the
k-vector space of sequences (x_0,...,x_n), and let H_m be the subset of W_n
consisting of the sequences that satisfy a degree-m linear recursion, that is,
for which there exist a_0,...,a_m in k, not all zero, such that sum(a_i
x_{i+j}, i=0..m) = 0 holds for each j=0,1,...,n-m. Equivalently, H_m is the set
of (x_0,...,x_n) such that the (m+1)-by-(n-m+1) matrix with (i,j) entry x_{i+j}
(i=0..m, j=0..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 and m+1 in W_n.
We deduce a formula for the discrete Fourier transform (DFT) 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->infty
the matrix is singular with probability approaching 1/q provided the DFT of mu
has l_1 norm less than sqrt(q). This bound sqrt(q) is best possible if q is a
square.
