New York Journal of Mathematics

New York J. Math. 8 (2002) 85–97.

On Finite Sequences Satisfying Linear Recursions

Noam D. Elkies

Abstract. 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} ⊆ W_{n} be the subset of sequences satisfying a degree-m 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, …, n − m. Equivalently, H_{m} is the set of (x_{0}, …, x_{n}) such that the (m + 1) × (n − m + 1) matrix with (i, j) entry x_{i+j} (0 ⩽ i ⩽ m, 0 ⩽ j ⩽ 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 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 ∥μ̂∥_{1} < q^{1/2}. This bound q^{1/2} is best possible if q is a square.

Contents

1. Introduction 85 2. The spaces V_{n}, W_{n} and some linear algebra 87 3. The characteristic function of H_{m} 90 4. Open questions 96 References 97

1. Introduction

Fix a field k. For 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} ⊆ W_{n} be the subset of sequences

Received May 12, 2001, and in revised form in April, 2002. Mathematics Subject Classification. 47B35, 15A57. Key words and phrases. Hankel matrix, linear recursion, finite field, discrete Fourier transform,

random Hankel matrix.

Supported in part by the Packard Foundation.

85^{ISSN 1076-9803/02}

satisfying a degree-m 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 (1)

holds for each j = 0, 1, …, n − m. Equivalently, H_{m} is the set of (x_{0}, …, x_{n}) such that the (m + 1) × (n − m + 1) Hankel matrix^{1}

( \begin{matrix}x_{0} & x_{1} & … & x_{n−m} \\ x_{1} & x_{2} & … & x_{n−m+1} \\ ⋮ & ⋮ & & ⋮ \\ x_{m} & x_{m+1} & … & x_{n} \end{matrix} ) (2)

has rank at most m.^{2} Now linear recursions on infinite sequences {x_{i}}_{i∈Z} are known to correspond to polynomials in the shift operators T^{±1} : {x_{i}} ↦ {x_{i±1}}, modulo multiplication by powers of T. This approach does not work so nicely for finite sequences, because T and T^{−1} push x_{0} and x_{n} off the edge. We propose to remedy this problem at T = 0, ∞ by homogenizing: instead of polynomials in T^{±1}, use homogeneous polynomials in two variables Y and Z that act on W_{n} as the right and left truncation maps to W_{n−1}. We shall see that this approach yields a clean account of linear recursions and the subsets H_{m} in the space W_{n}, which itself will be identified with the dual of the space V_{n} of homogeneous polynomials of degree n in Y and Z.^{3}

In the present paper we develop this account using elementary linear and polynomial algebra. When k is a finite field of q elements, we also 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 we obtain a new proof that #H_{m} = q^{2m}. We further show that if the 2m + 1 entries x_{0}, …, x_{2m} of a square Hankel matrix

( \begin{matrix}x_{0} & x_{1} & … & x_{m} \\ x_{1} & x_{2} & … & x_{m+1} \\ ⋮ & ⋮ & & ⋮ \\ x_{m} & x_{m+1} & … & x_{2m} \end{matrix} ) (3)

of order m + 1 are chosen independently from a fixed but not necessarily uniform distribution μ on k, then as m → ∞ the the matrix is singular with probability approaching 1/q provided the Fourier transform of μ has l_{1} norm less than q^{1/2}. This bound is best possible if q is a square: if μ is the uniform distribution on ck_{0}, where k_{0} is a quadratic subfield of k and c ∈ k^{∗} is arbitrary, then ∥μ̂∥_{1} = q^{1/2} but the probability is q^{−1/2}. It seems reasonable to conjecture that for any μ the matrix (3) is singular with probability → 1/q as long as μ is supported on a set of at least two elements not contained in ck_{0} for any proper subfield k_{0} of k.

1For more background on Hankel matrices (matrices with entries constant on NE-SW diagonals), and the closely related Toeplitz or “persymmetric” matrices (with entries constant on NW-SE diagonals), see for instance [4]. These matrices arise in diverse mathematical contexts; see for instance [1, 3] and the references in [4]. In our setting, Hankel matrices are more natural than Toeplitz ones, but our results on rank distribution, culminating in Theorem 2, apply equally well to matrices of either Hankel or Toeplitz type.

2I thank Joe Harris for the geometric observation that H_{m} consists of the lines through the origin coming from the points (x_{0} : x_{1} : ⋯: x_{n}) lying on the m-th secant variety of the rational normal curve (ξ^{n} : ξ^{n−1}η : ⋯: η^{n}) in n-dimensional projective space over k. We shall not need this formulation here, but it arises naturally in an arithmetic application of H_{m} [3].

3As an added benefit, the whole structure inherits a GL_{2}(k) structure from the action of GL_{2}(k) by linear substitutions on Y, Z. But this, too, is not needed for the present paper.

2. The spaces V_{n}, W_{n} and some linear algebra

Basic notions and lemmas. Fix a field k. For each integer n ≥ −1, let V_{n} be the vector space of dimension n + 1 over k consisting of bivariate homogeneous polynomials

P (Y, Z) = ∑_{i=0}^{n} a_{i}Y^{i}Z^{n−i} (4)

of degree n. Let W_{n} be the dual of V_{n}. We identify W_{n} with the space of sequences (x_{0}, …, x_{n}) by regarding such a sequence as the linear functional

∑_{i=0}^{n} a_{i}Y^{i}Z^{n−i} ↦ ∑_{i=0}^{n} a_{i}x_{i} (5)

on V_{n}. Note that we allow V_{−1} and W_{−1}, each of which is the zero space, but not V_{n}, W_{n} for n < −1.

If m ⩾ 0 and n + 1 ⩾ m, polynomial multiplication V_{m} × V_{n−m} → V_{n} gives for each Q ∈ V_{m} a linear map M_{n}(Q) : V_{n−m} → V_{n} defined by

M_{n}(Q) : P ↦ P Q (P ∈ V_{n−m}). (6)

Our reason for identifying the space W_{n} of sequences (x_{0}, …, x_{n}) with the dual of V_{n} is the following observation:

Lemma 1. Suppose Q ∈ V_{m} is the polynomial ∑_{i=0}^{m} a_{i}Y^{i}Z^{m−i}. Then the adjoint of M_{n}(Q) is the linear map M_{n}^{∗}(Q) : W_{n} → W_{n−m} taking any (x_{0}, …, x_{n}) to the sequence of length n − m + 1 whose j-th term is

∑_{i=0}^{m} a_{i}x_{i+j} (7)

for each j with 0 ⩽ j ⩽ n − m.

Proof. We show the equivalent dual statement: The linear map M_{n}(Q) takes any polynomial

P (Y, Z) = ∑_{j=0}^{n−m} b_{j}Y^{j}Z^{n−m−j}

in V_{n−m} to the polynomial P Q ∈ V_{n} whose Y^{r}Z^{n−r} coefficient is ∑_{i+j=r} a_{i}b_{j} for each r with 0 ⩽ r ⩽ n. But this is immediate from the expansion of P Q. □

Thus H_{m} is the union of ker M_{n}^{∗}(Q) over all nonzero Q ∈ V_{m}.

Of course that union is not disjoint, but as long as 2m ⩽ n + 1 we shall describe the intersection of ker M_{n}^{∗}(Q_{1}) and ker M_{n}^{∗}(Q_{2}) for any Q_{1}, Q_{2} of degree at most m (see Lemma 4 below). We first establish some further basic properties:

Lemma 2. i) For any Q, Q′ ∈ V_{m} and n such that n + 1 ⩾ m ⩾ 0 we have

M_{n}^{∗}(Q + Q′) = M_{n}^{∗}(Q) + M_{n}^{∗}(Q′). (8)

ii) For any Q_{1} ∈ V_{m_{1}}, Q_{2} ∈ V_{m_{2}}, and n such that m_{1}, m_{2} > 0 and n + 1 ⩽ m_{1} + m_{2}, we have

M_{n}^{∗}(Q_{1}Q_{2}) = M_{n−m_{2}}^{∗}(Q_{1}) ∘ M_{n}^{∗}(Q_{2}) = M_{n−m_{1}}^{∗}(Q_{2}) ∘ M_{n}^{∗}(Q_{1}). (9)

iii) For any nonzero Q ∈ V_{m} and any n ≥ m − 1, the map M_{n}^{∗}(Q) is surjective and its kernel has dimension m.

Proof. (i) This is the dual of the identity M_{n}(Q+Q′) = M_{n}(Q)+M_{n}(Q′), which is just the distributive law P (Q + Q′) = P Q + P Q′ for multiplication of homogeneous polynomials. (Alternatively, apply Lemma 1.)

(ii) Likewise this is the dual of the fact that multiplying a polynomial of degree n − m_{1} − m_{2} by Q_{1}Q_{2} is the same as multiplying it first by Q_{2} and then by Q_{1} or vice versa.

(iii) Since k[Y, Z] has no zero divisors, M_{n}(Q) is injective; thus M_{n}^{∗}(Q) is surjective, and its kernel has dimension dim W_{n} − dim W_{n−m} = m. □

The ideal I_{x}. For x = (x_{0}, …, x_{n}) ∈ W_{n}, define I_{x} ⊆ k[Y, Z] as follows: any Q ∈ k[Y, Z] is uniquely ∑_{m=0}^{M} Q_{m} with each Q_{m} ∈ V_{m}; the subset I_{x} consists of those ∑_{m=0}^{M} Q_{m} for which (M_{n}^{∗}(Q_{m}))(x) = 0 for each m ⩽ n + 1.

Lemma 3. I_{x} is a homogeneous ideal in k[Y, Z] for all x ∈ W_{n}.

Proof. By definition ∑_{m=0}^{M} Q_{m} ∈ I_{x} if and only if each Q_{m} ∈ I_{x}. So it is enough to check that I_{x} ∩ V_{m} is closed under addition for each m, and that P Q ∈ I_{x} if Q ∈ I_{x} ∩ V_{m} and P ∈ V_{m′} for some m, m′ ≥ 0. Each of these is vacuously true if m > n + 1 or m + m′ > n + 1 respectively, and follows from part (i) or (ii) of Lemma 2 otherwise. □

The main result of this section is the following partial description of I_{x}, stating in effect that it is approximated by a principal ideal as well as dimension considerations allow:

Proposition 1. Suppose for some x ∈ W_{n} that I_{x} contains a nonzero polynomial of degree at most (n + 1)/2. Let m_{0} be the smallest degree of such a polynomial. Then I_{x} ∩ V_{m_{0}} is 1-dimensional, say

I_{x} ∩ V_{m_{0}} = kQ_{0} (10)

for some nonzero Q_{0} ∈ V_{m_{0}}. For each m ⩽ n + 1 − m_{0},

I_{x} ∩ V_{m} = (M_{n}(Q_{0})) (V_{m−m_{0}}). (11)

Remark 1. In particular, it follows that I_{x} ∩ V_{m} has dimension m − m_{0} + 1 for m_{0} ⩽ m ⩽ n + 1 − m_{0}. This cannot hold once m > n + 1 − m_{0}, except in the trivial case x = 0, when m_{0} = 0 and I_{x} is all of k[Y, Z]. Indeed suppose that m_{0} > 0 and m > n+1−m_{0}. If m > n+1 then I_{x} ∩V_{m} = V_{m} has dimension m+1 > m−m_{0} +1. If m ⩽ n + 1 then I_{x} ∩ V_{m} is the kernel of the linear map

V_{m} → W_{n−m}, Q ↦ (M_{n}^{∗}(Q))(x); (12) thus

(13) dim(I_{x} ∩ V_{m}) ⩾ dim V_{m} − dim W_{n−m} = 2m − n,

which again exceeds m − m_{0} + 1 since m > n + 1 − m_{0}. This is what we mean when we state that I_{x} approximates the principal ideal (Q_{0}) as well as dimension considerations allow.

To prove Proposition 1 we must first make good on our promise to describe intersections of the spaces ker M_{n}^{∗}(Q). We do this in the next lemma, whose statement uses the greatest common divisor Q of two homogeneous polynomials Q_{1}, Q_{2}. This is defined only up to multiplication by k^{∗}, but such scaling does not affect the space ker M_{n}^{∗}(Q), so the choice of g.c.d. will not affect the result.

Lemma 4. Let Q_{1}, Q_{2} be nonzero polynomials in V_{m_{1}}, V_{m_{2}} respectively, with greatest common divisor Q. Then, for each n ⩾ max(m_{1}, m_{2}) − 1,

(14) ker M_{n}^{∗}(Q_{1}) ∩ ker M_{n}^{∗}(Q_{2}) ⊇ ker M_{n}^{∗}(Q),

with equality if and only if

n + 1 ⩾ m_{1} + m_{2} − deg(Q). (15)

Proof. If x ∈ ker M_{n}^{∗}(Q) then x is in the kernel of both M_{n}^{∗}(Q_{1}) and M_{n}^{∗}(Q_{2}), because each of these linear maps factors through M_{n}^{∗}(Q) by part (ii) of Lemma 2. Thus x is in the intersection of the two kernels, whence (14) follows. It remains to establish the condition of equality.

Let m = deg Q, and m′ = m_{1} + m_{2} − m. By Lemma 2(iii), the codimensions in W_{n} of ker M_{n}^{∗}(Q_{1}) and ker M_{n}^{∗}(Q_{2}) are n + 1 − m_{1} and n + 1 − m_{2} respectively. Thus their intersection has codimension at most

(n + 1 − m_{1}) + (n + 1 − m_{2}) = (n + 1 − m) + (n + 1 − m′). (16)

Hence if m′ > n + 1 then this codimension is strictly less than the codimension of ker M_{n}^{∗}(Q). Thus the condition m′ ⩽ n + 1 is necessary for equality in (14).

We conclude the proof by showing that this condition is also sufficient. Let Q′ be the least common multiple

Q′ = Q_{1}Q_{2}/Q (17)

of Q_{1} and Q_{2}; this is a homogeneous polynomial of degree m′. Assuming that m′ ⩽ n + 1, we may then consider M_{n}^{∗}(Q′). We claim that

(18) ker M_{n}^{∗}(Q_{1}) + ker M_{n}^{∗}(Q_{2}) = ker M_{n}^{∗}(Q′).

By duality, this claim is equivalent to

im(M_{n}(Q_{1})) ∩ im(M_{n}(Q_{2})) = im(M_{n}(Q′)). (19)

But this is just the statement that a polynomial in V_{n} is divisible by both Q_{1} and Q_{2} if and only if it is divisible by Q′ — which is true because Q′ is the least common multiple of Q_{1} and Q_{2}. We thus have

(20) dim(ker M_{n}^{∗}(Q_{1}) ∩ ker M_{n}^{∗}(Q_{2}))

= dim(ker M_{n}^{∗}(Q_{1})) + dim(ker M_{n}^{∗}(Q_{2})) − dim(ker M_{n}^{∗}(Q_{1}) + ker M_{n}^{∗}(Q_{2}))

= dim(ker M_{n}^{∗}(Q_{1})) + dim(ker M_{n}^{∗}(Q_{2})) − dim(ker M_{n}^{∗}(Q′)).

By Lemma 2(iii) again, this dimension equals

m_{1} + m_{2} − m′ = m = dim(ker M_{n}^{∗}(Q)). (21)

Since we already know that ker M_{n}^{∗}(Q_{1}) ∩ ker M_{n}^{∗}(Q_{2}) contains ker M_{n}^{∗}(Q), we conclude that these two spaces are equal. □

Corollary 1. Suppose x ∈ W_{n}. If I_{x} contains homogeneous polynomials Q_{1}, Q_{2} whose least common multiple has degree at most n+1, then I_{x} contains gcd(Q_{1}, Q_{2}). In particular, this conclusion holds if deg Q_{1} + deg Q_{2} ⩽ n + 1.

Proof. Under our hypotheses, x is contained in both ker M_{n}^{∗}(Q_{1}) and ker M_{n}^{∗}(Q_{2}), and the equality condition of Lemma 4 is satisfied. Therefore

(22) x ∈ ker M_{n}^{∗}(Q_{1}) ∩ ker M_{n}^{∗}(Q_{2}) = ker M_{n}^{∗}(gcd(Q_{1}, Q_{2})),

which is to say that I_{x} contains gcd(Q_{1}, Q_{2}) as claimed. □

We can now easily prove Proposition 1:

Proof of Proposition 1. Suppose Q_{1}, Q_{2} are nonzero polynomials in I_{x} ∩ V_{m_{0}}. By the hypothesis of Proposition 1 we know 2m_{0} ⩽ n + 1. Corollary 1 thus applies, and we find that I_{x} contains gcd(Q_{1}, Q_{2}). Unless Q_{1}, Q_{2} are proportional, deg(gcd(Q_{1}, Q_{2})) < m_{0}, which is impossible by the definition of m_{0}. Thus I_{x} ∩ V_{m_{0}} has dimension 1 as claimed. By the same Corollary, if m ⩽ n + 1 − m_{0} and Q ∈ I_{x} ∩ V_{m_{0}} − {0} then I_{x} ∋ gcd(Q_{0}, Q). Since again gcd(Q_{0}, Q) must have degree at least m_{0}, we conclude that Q is a multiple of Q_{0}. Since I_{x} is an ideal (Lemma 3), we already know that I_{x} contains all multiples of Q_{0}; thus I_{x} ∩ V_{m_{0}} consists of all degree-m multiples of Q_{0}, and we are done. □

It is thus natural to call Q_{0} the minimal linear recursion satisfied by x. (Again Q_{0} is defined only up to multiplication by k^{∗}.) From Proposition 1 we deduce the following description of the degree m_{0} of this minimal recursion:

Corollary 2. If x ∈ H_{m} for some m ⩽ (n + 1)/2 then the degree of the minimal linear recursion satisfied by x equals the rank of the Hankel matrix (2) associated to x.

Proof. Let m_{0} be this minimal degree. The rank of (2) is m + 1 − d, where d is the dimension of the kernel of the action of this matrix on row vectors of length m + 1. But Lemma 1 identifies this kernel with the space I_{x} ∩ V_{m} of degree-m recursions satisfied by x. Since m_{0} ⩽ m ⩽ (n + 1)/2, we may apply Proposition 1 to find that d = m − m_{0} + 1. Thus m_{0} is the rank of the Hankel matrix, as claimed. □

3. The characteristic function of H_{m}

Decomposition into signed linear subspaces. We assume henceforth that k is a finite field of q elements. For integers m, n satisfying our customary condition 2m ⩽ n + 1, let P_{m} be the set of all subspaces of W_{n} of the form ker M_{n}^{∗}(Q) for some nonzero Q ∈ V_{m}. (By Lemma 4 and part (iii) of Lemma 2, ker M_{n}^{∗}(Q_{1}) = ker M_{n}^{∗}(Q_{2}) if and only if Q_{1}, Q_{2} are proportional; thus P_{m} consists of

\frac{#(V_{m} − \{0\})}{#(k^{∗})} = \frac{q^{m+1} − 1}{q − 1} (23)

subspaces. We note for later use that this formula remains valid if we allow m = −1, when P_{m} is empty.) Recall that we defined H_{m} as the set of x ∈ W_{n} satisfying a recursion of degree m, and noted that H_{m} is thus the union of all the subspaces in P_{m}. We further noted that this union is not disjoint, and thus that χ_{H_{m}}, the characteristic function of H_{m}, is not simply the sum of the characteristic functions of the subspaces in P_{m}. However, by Lemma 4, the intersection of any two subspaces in P_{m} is again the kernel of M_{n}^{∗}(Q) for some nonzero homogeneous Q of degree ⩽ m, and more generally if m_{1}, m_{2} ⩽ m then the intersection of any subspace in P_{m_{1}} with any subspace in P_{m_{2}} is itself in P_{m′} for some m′ ⩽ m. Thus we can use inclusion-exclusion identities to write χ_{H_{m}} as a linear combination of the characteristic functions of subspaces in P_{m′} for m′ ⩽ m. Fortunately the resulting formula is quite simple:

Proposition 2. The characteristic function of H_{m} equals

∑_{K∈P_{m}} χ_{K} − q ∑_{K∈P_{m−1}} χ_{K}, (24)

in which χ_{K} is the characteristic function of the set K, and the second sum is interpreted as zero when m = 0.

Proof. Clearly (24) is an integer-valued function on W_{n} supported on H_{m}. Thus we need only show that its value at x equals 1 for all x ∈ H_{m}. But this value is

(25)  \frac{#(I_{x} ∩ V_{m}) − 1}{q − 1} − q \frac{#(I_{x} ∩ V_{m−1}) − 1}{q − 1}

= 1 + \frac{#(I_{x} ∩ V_{m}) − q #(I_{x} ∩ V_{m−1})}{q − 1}.

Let m_{0} be the degree of the minimal linear recursion satisfied by x. By Proposition 1, I_{x}∩V_{m} and I_{x}∩V_{m−1} are vector spaces of dimensions m−m_{0}+1 and m−m_{0} respectively over k. (Note that this remains true if m_{0} = m, when I_{x} ∩ V_{m−1} is the zero space.) Thus #(I_{x} ∩ V_{m}) = q #(I_{x} ∩ V_{m−1}), and (25) simplifies to 1 as claimed. □

We easily deduce the formula [2, Thm. 1] for the size of H_{m}:

Corollary 3. For all nonnegative m ⩽ (n + 1)/2 we have

#(H_{m}) = q^{2m}. (26)

Proof. The size of H_{m} is the sum of χ_{H_{m}}(x) over x ∈ W_{n}. By (24), this sum is

∑_{K∈P_{m}}#(K) − q ∑_{K∈P_{m−1}}#(K). (27)

But by Lemma 2(iii), each K ∈ P_{m} has size q^{m}, and each K ∈ P_{m−1} has size q^{m−1}. Using (23) — and this is where we use the validity of (23) also for m = −1 — we thus simplify (27) to

\frac{q^{m+1} − 1}{q − 1} q^{m} − q \frac{q^{m} − 1}{q − 1} q^{m−1} = q^{2m}, (28)

as claimed. □

In particular, if n = 2m − 1 then #H_{m} = #W_{n}, whence H_{m} = W_{n} — which is clear because in this case the Hankel matrix (2) has only m rows, so must have rank at most m. (This is essentially the special case n = 2m − 1 of the dimension count we used earlier to deduce (13); in this case we find that I_{x} ∩ V_{m} has rank at least 2m − n = 1, so must contain a nonzero vector.) Starting from this, one may establish without too much difficulty a bijection from W_{2m−1} to the subset H_{m} of W_{n} for any n ⩾ 2m − 1, even without our k[Y, Z] framework. (This is in effect how (26) is proved in [2].) But our approach also yields a formula for the Fourier transform χ̂_{H_{m}}(P) for all P ∈ V_{n}, whereas (26) only gives χ̂_{H_{m}}(0). We turn to χ̂_{H_{m}} next.

Discrete Fourier transform. To define the Fourier transform on W_{n}, we first define it on k. Fix a nontrivial character ψ_{0} of k, that is, a nontrivial homomorphism from the additive group of k to the unit circle in C. [If k = Z/pZ for some prime p, we may take ψ_{0}(x) = exp(2πix/p); in general k contains Z/pZ where p is the characteristic of k, and we may take ψ_{0}(x) = exp(2πit(x)/p) where t : k → Z/pZ is any nontrivial homomorphism of additive groups. One common choice for t is the trace from k to Z/pZ. At any rate none of our results will depend on the choice of ψ_{0}.] For any function f : k → C, we define the (discrete) Fourier transform f̂ of f to be the following function from k to C:

f̂(a) := ∑_{x∈k} f(x)ψ_{0}(ax). (29)

It is known that f ↦ f̂ is a linear bijection on the space C^{q} of complex-valued functions on k, and that the inverse bijection is given by the Fourier inversion formula:

f(x) = \frac{1}{q} ∑_{a∈k} f̂(a)ψ_{0}(−ax). (30)

The Fourier transform is defined more generally for finite-dimensional vector spaces over k. Let V, W be a dual pair of such spaces, of dimension d. (We shall use V = V_{n}, W = W_{n}, d = n + 1.) To each function F : W → C we associate its discrete Fourier transform

F̂(a) := ∑_{x∈W} F (x)ψ_{0}(⟨a, x⟩). (31)

Again F ↦ F̂ is a linear bijection, and in this context the inversion formula reads

F (x) = \frac{1}{q^{d}} ∑_{a∈V} F̂(a)ψ_{0}(−⟨a, x⟩). (32)

To recover χ̂_{H_{m}} from Proposition 2, we shall need one more fact about the discrete Fourier transform:

Lemma 5. For any linear subspace K ⊆ W, the Fourier transform of its characteristic function χ_{K} is (#K) · χ_{K^{⊥}}, where K^{⊥} is the annihilator of K in V.

Proof. By definition, χ̂_{K}(a) is the sum over K of the character x ↦ ψ_{0}(⟨a, x⟩); thus χ̂_{K}(y) = #K or 0 according as this character is trivial or nontrivial on K, that is, according as a ∈ K^{⊥} or a ∉ K^{⊥}. □

We can now give our formula for χ̂_{H_{m}}. It will be convenient to introduce the following notation: for P ∈ V_{n} and any integer d, define ω_{d}(P) to be 1/(q − 1) times the number of nonzero Q ∈ V_{d} such that P is a multiple of Q. Equivalently, ω_{d}(P) is the number of degree-d factors of P up to k^{∗} scaling, and the number of homogeneous principal ideals in k[Y, Z] that contain P and have a generator of degree d. For instance, ω_{0}(P) = 1, and for all d ≥ −1,

ω_{d}(0) = \frac{q^{d+1} − 1}{q − 1} [= #(P_{d}) if 2d ⩽ n + 1]. (33)

Moreover, for nonzero P we have the identity

ω_{d}(P) = ω_{n−d}(P), (34)

due to the bijection Q ↔ P/Q between factors of P of degree d and n − d. (The notation ω_{d} is suggested by the omega function in elementary number theory, which counts the positive divisors of a given positive integer.)

Theorem 1. For every m ⩽ (n + 1)/2 and P ∈ V_{n} we have

χ̂_{H_{m}}(P) = q^{m} (ω_{m}(P) − ω_{m−1}(P)) . (35)

Proof. By Proposition 2 and Lemma 5, this follows from the following observation: for any homogeneous polynomial Q of degree at most n, the annihilator in V_{n} of ker M_{n}^{∗}(Q) is the image of M_{n}(Q), which is the space of degree-n multiples of Q. Thus when we use (24) to expand χ̂_{H_{m}} as a linear combination of characteristic functions of annihilators, the number of subspaces in P_{m} or P_{m−1} that contribute a term to χ̂_{H_{m}}(P) is the number of divisors of P of degree m or m − 1 up to k^{∗} scaling. Each of these terms is q^{m} or −q · q^{m−1} = −q^{m} respectively, whence the formula (35). □

As promised, Proposition 2 is the special case P = 0 of this formula (cf. (33)). Also, if n = 2m − 1, the identity (34) yields χ̂_{H_{m}}(P) = 0 for all P ≠ 0, consistent with H_{m} = W_{n} in that case.

Hankel matrices with independently biased entries. The formula (26) can be interpreted thus: if x_{0}, …, x_{n} are chosen independently at random from the uniform distribution on k, then the resulting vector (x_{0}, …, x_{n}) is in H_{m} with probability q^{2m−(n+1)}. Using Theorem 1 we can also get at the probability that (x_{0}, …, x_{n}) ∈ H_{m} if the x_{i} are still chosen independently at random but from distributions μ_{i} on k that are not necessarily uniform.

We regard the μ_{i} as functions from k to R satisfying the conditions: μ_{i}(x) ⩾ 0 for all x ∈ k, and

[μ̂_{i}(0) =] ∑_{x∈k} μ_{i}(x) = 1. (36)

Then the probability that x⃗ := (x_{0}, …, x_{n}) is in H_{m} is

Π_{m}(μ_{0}, …, μ_{n}) = ∑_{x⃗∈W_{n}} χ_{H_{m}}(x⃗) ∏_{i=0}^{n} μ_{i}(x_{i}). (37)

By applying Fourier inversion to χ_{H_{m}} we can express this as a linear combination of the values of χ̂_{H_{m}}(P). The resulting formula is:

Lemma 6. We have

Π_{m}(μ_{0}, …, μ_{n}) = q^{−(n+1)} ∑_{P ∈V_{n}} χ̂_{H_{m}}(P) ∏_{i=0}^{n} μ̂_{i}(−a_{i}), (38)

where a_{i} is the Y^{i}Z^{n−i} coefficient of P as in (4).

Proof. By Fourier inversion (32),

Π_{m}(μ_{0}, …, μ_{n}) = q^{−(n+1)} ∑_{P ∈V_{n}} χ̂_{H_{m}}(P) ( ∑_{x⃗∈W_{n}} ψ_{0}(−⟨P, x⟩) ∏_{i=0}^{n} μ_{i}(x_{i})) . (39)

Now ⟨P, x⟩ = ∑_{i=0}^{n} a_{i}x_{i}, so

ψ_{0}(−⟨P, x⟩) ∏_{i=0}^{n} μ_{i}(x_{i}) = ∏_{i=0}^{n} ψ_{0}(−a_{i}x_{i})μ_{i}(x_{i}). (40)

Thus the inner sum in (39) factors into

∏_{i=0}^{n} ( ∑_{x_{i}∈k} ψ_{0}(−a_{i}x_{i})μ_{i}(x_{i})) = ∏_{i=0}^{n} μ̂_{i}(−a_{i}). (41)

Entering this into (39) yields the claimed formula (38). □

The term P = 0 in (39) contributes

q^{−(n+1)}χ̂_{H_{m}}(0) ∏_{i=0}^{n} μ̂_{i}(0) = q^{2m−(n+1)}, (42)

because χ̂_{H_{m}}(0) = q^{2m} and each μ̂_{i}(0) = 1. The absolute value of the sum of the remaining terms is at most

(43)  q^{−n+1} sup_{P ∈V_{n}−{0}} |χ̂_{H_{m}}(P)| · ∑_{P ∈V_{n}−{0}} ∏_{i=0}^{n} |μ̂_{i}(−a_{i})|

= q^{−n+1} sup_{P ∈V_{n}−{0}} |χ̂_{H_{m}}(P)| [(∏_{i=0}^{n} ∥μ̂_{i}∥_{1}) − 1] ,

where ∥μ̂_{i}∥_{1} is the l_{1} norm

∥μ̂_{i}∥_{1} := ∑_{a∈k} |μ̂_{i}(a)|. (44)

Since μ̂_{i}(0) = 1, we have ∥μ̂_{i}∥_{1} ⩾ 1, with equality if and only if μ̂_{i}(a) = 0 for all a ≠ 0. By Fourier inversion (30), this condition is equivalent to μ_{i}(x) = 1/q for all x. Hence ∥μ̂_{i}∥_{1} = 1 if and ony if μ_{i} is the uniform distribution on k. We may thus regard (∏_{i=0}^{n} ∥μ̂_{i}∥_{1}) − 1 as a measure of how far the product distribution μ_{0} … μ_{n} departs from uniform distribution on W_{n}.

What of the other factor sup_{P ≠0} |χ̂_{H_{m}}(P)| in the error estimate (43)? By Theorem 1, each χ̂_{H_{m}}(P) is a multiple of q^{m}. Once n ⩾ 2m, we cannot expect χ̂_{H_{m}}(P) to vanish for all P ≠ 0, so sup_{P ≠0} |χ̂_{H_{m}}(P)| must be at least q^{m}. We next show that it |χ̂_{H_{m}}(P)| is never much larger than q^{m} for P ≠ 0:

Lemma 7. For every q and ϵ > 0, there exists an effective constant C such that

ω_{d}(P) < C(1 + ϵ)^{n} (45)

for every nonzero P ∈ V_{n} and every integer d.

(This is analogous to the standard fact that the number of factors of an n-digit integer is subexponential in n, and will be proved in the same way.)

Proof. Define

ω(P) := ∑_{d=0}^{n} ω_{d}(P), (46)

the total number of divisors of P up to k^{∗} scaling. Factor P into irreducibles over k:

P = ∏_{s=1}^{r} P_{s}^{e_{s}}, (47)

with P_{s} distinct irreducibles of degree f_{s}. Comparing degrees in (47) we find

n = ∑_{s=1}^{r} e_{s}f_{s}. (48)

Now

ω(P) = ∏_{s=1}^{r}(e_{s} + 1), (49)

because the general divisor of P is ∏_{s=1}^{r} P_{s}^{e′_{s}} with each e′_{s} chosen from among the e_{s} + 1 possibilities 0, 1, …, e_{s}. Fix m_{0} large enough that 2^{1/m_{0}} < 1 + ϵ, and factor (49) as

ω(P) = ∏_{f_{s}<m_{0}}(e_{s} + 1) ∏_{f_{s}⩾m_{0}}(e_{s} + 1). (50)

The second product is at most

∏_{f_{s}⩾m_{0}} 2^{e_{s}} = 2^{∑_{fs⩾m_{0}} e_{s}} ⩽ 2^{n/m_{0}}, (51)

since m_{0} ∑_{f_{s}⩾m_{0}} e_{s} ⩽ ∑_{s=1}^{r} e_{s}f_{s} = n by (48). The first product in (50) has at most B factors, where B is the number of irreducible bivariate homogeneous polynomials of degree < m_{0} up to k^{∗} scaling. Each factor is at most n + 1, so the product is at most (n + 1)^{B}. Since log(n + 1)^{B} = o(n) as n → ∞, and 2^{1/m_{0}} < 1 + ϵ, we conclude that

ω(P) ⩽ 2^{n/m_{0}}(n + 1)^{B} ≪ (1 + ϵ)^{n}. (52)

Since ω_{d}(P) ⩽ ω(P), we deduce ω_{d}(P) ≪ (1 + ϵ)^{n}. □

Combining this estimate with Theorem 1 and Lemma 6, we obtain:

Theorem 2. For every q and ϵ > 0, there exists an effective constant C such that

|Π_{m}(μ_{0}, …, μ_{n}) − q^{2m−(n+1)}| < C(1 + ϵ)^{n}q^{m−n} ∏_{i=0}^{n} ∥μ̂_{i}∥_{1} . (53)

for any n and any distributions μ_{i} on k.

In particular, suppose that n = 2m+α for some fixed nonnegative integer α, and that all the μ_{i} are the same, so that each x_{i} is chosen from the same distribution μ. Then, as long as ∥μ̂∥_{1} < q^{1/2}, the error term in (53) approaches 0 as m → ∞, and we conclude that if each of x_{0}, …, x_{2m+α} is chosen independently from the distribution μ then x ∈ H_{m} with probability approaching q^{−(α+1)}, same as for the uniform distribution. As noted in the Introduction, the bound on ∥μ̂∥_{1} is best possible, at least if q is a square: in that case k has a quadratic subfield k_{0}, and if each x_{i} is chosen uniformly from k_{0} (or from ck_{0} for some c ∈ k^{∗}) then x ∈ H_{m} with probability q^{−(α+1)/2}, not q^{−(α+1)}; but for this distribution, ∥μ̂∥_{1} = q^{1/2} by Lemma 5.

4. Open questions

Better bounds on Π_{m}(μ_{0}, …, μ_{n}) − q^{2m−(n+1)}? We showed (Theorem 2) that Π_{m}(μ_{0}, …, μ_{n}) is well approximated by q^{2m−(n+1)} under certain hypotheses on the μ_{i}. Can these hypotheses by weakened by lowering the error bound in (53)? Of course we must exclude some choices of μ_{i}. For instance we certainly cannot have every μ_{i} supported on only one point; and we already gave the counterexample of uniform distribution on a proper subfield of k. But it seems plausible that, except for such pathological cases, (x_{0}, …, x_{n}) should be about as likely to be in H_{m} with x_{i} chosen from μ_{i} as it is with x⃗ chosen uniformly from W_{n} — whether or not the ∥μ_{i}∥_{1} are small enough to deduce Π_{m}(μ_{0}, …, μ_{n}) ∼ q^{2m−(n+1)} from Theorem 2. For instance we may surmise the following

Conjecture. Fix k and a closed set K of distributions μ : k → R. Assume that no μ ∈ K is supported on a single point, nor on ck_{0} for any c ∈ k^{∗} and any proper subfield k_{0} of k. Then, for every real R ⩾ 2, we have

Π_{m}(μ_{0}, …, μ_{n}) = (1 + o(1))q^{2m−(n+1)} (54)

for any sequence of (n, m, μ_{0}, …, μ_{n}) for which m → ∞, 2m ⩽ n ⩽ Rm, and μ_{i} ∈ K for each i.

In particular, suppose q = R = 2. A distribution on k is then a pair (μ(0), μ(1)) of nonnegative numbers with μ(0) + μ(1) = 1. The conjecture then asserts that, for each p > 0, if each entry x_{i} of a square Hankel matrix of order m + 1 over Z/2Z is chosen independently at random with probabilities μ_{i}(0), μ_{i}(1) both ⩾ p, then the matrix is singular with probability approaching 1/2 as m → ∞. Theorem 2 shows this only for p > 1 − 2^{−1/2} ≈ 29.3%.

Higher dimensions. What happens to our theory in the context of arrays of dimension 2 or greater, rather than finite sequences? One could start the analysis in the same way, using for instance homogeneous polynomials in three variables to treat triangular arrays, or bihomogeneous polynomials in two pairs of variables for rectangular arrays. The resulting structures will surely be more complicated in higher dimensions, but it may still be possible to find tractable descriptions.

Determinants of nonsingular Hankel matrices. In another direction, we return to the case n = 2m of square Hankel matrices (3) of order m + 1, for which H_{m} consists in effect of such matrices whose determinant vanishes. We then ask: Is there a formula analogous to (35), or even an estimate analogous to Lemma 7, for

On Finite Sequences Satisfying Linear Recursions 97

the discrete Fourier transform of the set of square Hankel matrices of order m + 1 with determinant c, for any given nonzero c ∈ k? This is easy when q = 2, in which case that set is just the complement of H_{m}. But the problem seems to require new techniques once q ⩾ 3.

References

[1] D. G. Cantor, On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. (Crelle’s J.), 447 (1994), 91–145, MR 94m:11071, Zbl 0788.14026.

[2] D. Daykin, Distribution of bordered persymmetric matrices in a finite field, J. Reine Angew. Math. (Crelle’s J.), 203 (1960), 47–54, MR 22 #3734, Zbl 0104.01304.

[3] A. Dress, N. D. Elkies and F. Luca, A characterization of Mahler’s generalized Liouville numbers by simultaneous rational approximation, preprint, 2001.

[4] I. S. Iohvidov, Hankel and Toeplitz Matrices and Forms: Algebraic Theory (trans. G.P.A. Thijsse), Boston: Birkhäuser 1982, MR 83k:15021, Zbl 0493.15018.

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

This paper is available via http://nyjm.albany.edu:8000/j/2002/8-5.html.