On finite sequences satisfying linear recursions
| dc.creator | Elkies, Noam D. | |
| dc.date | 2001-05-01 | |
| dc.date | 2002-06-12 | |
| dc.date.accessioned | 2026-07-07T04:41:33Z | |
| dc.date.available | 2026-07-07T04:41:33Z | |
| dc.description | 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_0,...,x_n), and let H_m be the subset of W_n consisting of the sequences that satisfy a degree-m linear recursion, that is, for which there exist a_0,...,a_m in k, not all zero, such that sum(a_i x_{i+j}, i=0..m) = 0 holds for each j=0,1,...,n-m. Equivalently, H_m is the set of (x_0,...,x_n) such that the (m+1)-by-(n-m+1) matrix with (i,j) entry x_{i+j} (i=0..m, j=0..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 (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_1 norm less than sqrt(q). This bound sqrt(q) is best possible if q is a square. | |
| dc.description | 13 pages. Revised to include publication data and to correct minor errors (mostly noted by the referee) | |
| dc.identifier | https://arxiv.org/abs/math/0105007 | |
| dc.identifier | http://arxiv.org/abs/math/0105007 | |
| dc.identifier | New York J. Math._8_ (2002) 85-97 = http://nyjm.albany.edu:8000/j/2002/8-5.html | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61404 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Geometry | |
| dc.subject | Rings and Algebras | |
| dc.subject | 47B35; 15A57 | |
| dc.title | On finite sequences satisfying linear recursions | |
| dc.type | text |