Mathematics – Combinatorics
Scientific paper
2001-05-01
New York J. Math._8_ (2002) 85-97 = http://nyjm.albany.edu:8000/j/2002/8-5.html
Mathematics
Combinatorics
13 pages. Revised to include publication data and to correct minor errors (mostly noted by the referee)
Scientific paper
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.
No associations
LandOfFree
On finite sequences satisfying linear recursions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On finite sequences satisfying linear recursions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On finite sequences satisfying linear recursions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-5065