View paper:
pdf dvi ps
View abstract:
pdf gif
links page

Graphical interface
Volume 8
Other volumes
Full text search
of NYJM papers
NYJM home

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

On finite sequences satisfying linear recursions

Noam D. Elkies

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 \leqs 2m \leqs n+1$, let $W_n$ be the \hbox{$k$\/-vector} space of sequences $(x_0,\ldots,x_n)$, and let $H_m \subseteq W_n$ be the subset of sequences satisfying a \hbox{degree-$m$} linear recursion --- that is, for which there exist $a_0,\ldots,a_m\in k$, not all zero, such that $$ \sum_{i=0}^m a_i x_{i+j} = 0 $$ holds for each $j=0,1,\ldots,n-m$. Equivalently, $H_m$ is the set of $(x_0,\ldots,x_n)$ such that the $(m+1) \times (n-m+1)$ matrix with $(i,j)$ entry $x_{i+j}$ ($0\leqs i\leqs m$, $0\leqs j \leqs 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$ \hbox{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~$\mu$ on~$k$, then as $m\ra\infty$ the matrix is singular with probability approaching $1/q$ provided $\|\muhat\|\0_1 < q^{1/2}$. This bound $q^{1/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