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₀,...,x_n), and let H_m ⊂ W_n be the subset of sequences satisfying a degree-m linear recursion -- that is, for which there exist a₀,...,a_m∈ k, not all zero, such that ∑_i=0^m a_i x_i+j = 0 holds for each j=0,1,...,n-m. Equivalently, H_m is the set of (x₀,...,x_n) such that the (m+1)×(n-m+1) matrix with (i,j) entry x_i+j (0≦ i ≦ m, 0≦ j ≦ 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 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 μ on k, then as m → ∞ the matrix is singular with probability approaching 1/q provided ||μhat||₁ < q^1/2. This bound q^1/2 is best possible if q is a square.

Supported in part by the Packard Foundation