New York Journal of Mathematics
Volume 8 (2002) 85-97


Noam D. Elkies

On Finite Sequences Satisfying Linear Recursions

Published: May 1, 2002
Keywords: Hankel matrix, linear recursion, finite field, discrete Fourier transform, random Hankel matrix
Subject: 47B35, 15A57

For any field k and any integers m,n with 0 ≦ 2m ≦ n+1, let Wn be the k-vector space of sequences (x0,...,xn), and let Hm ⊂ Wn be the subset of sequences satisfying a degree-m linear recursion -- that is, for which there exist a0,...,am∈ k, not all zero, such that
i=0m ai xi+j = 0
holds for each j=0,1,...,n-m. Equivalently, Hm is the set of (x0,...,xn) such that the (m+1)×(n-m+1) matrix with (i,j) entry xi+j (0≦ i ≦ m, 0≦ j ≦ n-m) has rank at most m. We use elementary linear and polynomial algebra to study these sets Hm. In particular, when k is a finite field of q elements, we write the characteristic function of Hm as a linear combination of characteristic functions of linear subspaces of dimensions m and m+1 in Wn. 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||1 < q1/2. This bound q1/2 is best possible if q is a square.


Supported in part by the Packard Foundation

Author information

Department of Mathematics, Harvard University, Cambridge, MA 02138