 

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 


Abstract
For any field k and any integers m,n
with 0 ≦ 2m ≦ n+1, let W_{n} be the kvector space
of sequences (x_{0},...,x_{n}), and let H_{m} ⊂ W_{n} be the
subset of sequences satisfying a degreem linear recursion
 that is, for which there exist a_{0},...,a_{m}∈ k,
not all zero, such that
∑_{i=0}^{m} a_{i} x_{i+j} = 0
holds for each j=0,1,...,nm. Equivalently, H_{m} is the set
of (x_{0},...,x_{n}) such that the (m+1)×(nm+1) matrix
with (i,j) entry x_{i+j} (0≦ i ≦ m, 0≦ j ≦ nm)
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_{1} < q^{1/2}.
This bound q^{1/2} is best possible if q is a square.


Acknowledgements
Supported in part by the Packard Foundation


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

