On finite sequences satisfying linear recursions

Original · EN

For any field k and any integers m,n with 0 <= 2m <= n+1, let Wₙ be the k-vector space of sequences (x₀,...,xₙ), and let Hₘ be the subset of Wₙ consisting of the sequences that satisfy a degree-m linear recursion, that is, for which there exist a₀,...,aₘ in k, not all zero, such that sum(aᵢ xᵢ₊ⱼ, i=0..m) = 0 holds for each j=0,1,...,n-m. Equivalently, Hₘ is the set of (x₀,...,xₙ) such that the (m+1)-by-(n-m+1) matrix with (i,j) entry xᵢ₊ⱼ (i=0..m, j=0..n-m) has rank at most m. We use elementary linear and polynomial algebra to study these sets Hₘ. In particular, when k is a finite field of q elements, we write the characteristic function of Hₘ as a linear combination of characteristic functions of linear subspaces of dimensions m and m+1 in Wₙ. 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₁ norm less than sqrt(q). This bound sqrt(q) is best possible if q is a square.