Transformations Preserving the Hankel Transform

Christopher French Department of Mathematics and Statistics Grinnell College Grinnell, IA 50112 USA

                   frenchc@math.grinnell.edu

Abstract We classify all polynomial transformations of integer sequences which preserve the Hankel transform, thus generalizing examples due to Layman and Spivey & Steil. We also show that such transformations form a group under composition.

1 Introduction

Given a sequence of integers {a_{i}} = a_{0}, a_{1}, a_{2}, …, the Hankel matrix of A is the infinite matrix whose (i, j) entry is a_{i+j} for i ≥ 0, j ≥ 0. The Hankel matrix of order n of A is the n × n matrix consisting of the first n rows and n columns of the Hankel matrix of A, and the Hankel sequence determined by A is the sequence of determinants of the Hankel matrices of order n. For example, the Hankel matrix of order 3 is given by

(\begin{matrix}a_{0} & a_{1} & a_{2} \\ a_{1} & a_{2} & a_{3} \\ a_{2} & a_{3} & a_{4} \end{matrix}) .

Let R = ℤ[a_{0}, a_{1}, a_{2}, …]. We will say that a sequence {b_{i}} = {b_{0}, b_{1}, b_{2}, …} of elements in R is an HT P sequence (Hankel Transform Preserving) if the Hankel transform of {b_{i}} is formally equal to that of {a_{i}}; that is, if the following identity holds in R for all n:

|\begin{matrix}b_{0} & b_{1} & ⋯ & b_{n} \\ b_{1} & b_{2} & ⋯ & b_{n+1} \\ ⋮ & & ... & ⋮ \\ b_{n} & b_{n+1} & ⋯ & b_{2n} \end{matrix}| = |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

An HT P sequence {b_{i}} determines a ring homomorphism b : R → R by the equation b(a_{i}) = b_{i}. We will sometimes refer to the sequence {b_{i}} as just b. It is easy to see that the composition of two ring homomorphisms associated to HT P sequences is the ring homomorphism associated to an HT P sequence, so that the set of all HT P sequences has a semigroup structure (with b_{i} = a_{i} representing the identity). We will see (Theorem 3.6) that this is actually a group structure.

Example 1.1. Let σ : R → R be given by σ(a_{i}) = (−1)^{i}a_{i}. Then σ determines an HT P sequence. Indeed, the order n Hankel matrix of the sequence {(−1)^{i}a_{i}} is given by conjugating the order n Hankel matrix A_{n} of {a_{i}} by the diagonal matrix D_{n} with (i, i)-entry given by (−1)^{i}. The determinant of D_{n}^{−1}A_{n}D_{n} is the same as that of A_{n}.

Example 1.2. For an integer k, the sequence defined by b_{n} = ∑_{i=0}^{n} \binom{n}{i}k^{n−i}a_{i} is an HT P sequence. (Here, if k = 0, then we interpret 0^{0} to be 1.) Spivey and Steil [5] called this the falling k-binomial transform, and they proved that this preserves the Hankel Transform. When k = 1, this gives the binomial transform, which Layman [3] originally proved preserves the Hankel transform.

Remark 1.3. In fact, Spivey and Steil allow k to be any real number. If k were not an integer, then b_{n} is not in R = ℤ[a_{0}, a_{1}, a_{2}, …], so in our language, {b_{n}} would not be an HTP sequence. Since we are interested in integer sequences, we have restricted to ℤ[a_{0}, a_{1}, a_{2}, …].

Definition 1.4. An HT P sequence b preserves a_{0} through a_{n} if b_{i} = a_{i} for 0 ≤ i ≤ n.

Suppose that b(m) is a sequence of HT P sequences such that for each n, there is a number M(n) such that b(m) preserves a_{0} through a_{n} for all m > M(n). Then the infinite composition

⋯ ∘ b(m) ∘ b(m − 1) ∘ ⋯ ∘ b(0)

is itself a well-defined sequence. Indeed, the nth term in the sequence of this infinite composite is determined by b(M(n)) ∘ b(M(n) − 1) ∘ ⋯ ∘ b(0). It is easy to see that this infinite composition is itself an HT P sequence.

In order to find all HT P sequences, we first describe a special set of sequences, parametrized by R and the positive integers. In fact, for each positive integer n, and each c ∈ R, we will define an HT P sequence b(n, c) which preserves a_{0} through a_{2n}. Example 1.2 above arises when n = 0 and c ∈ ℤ. Our main theorem is

Theorem 1.5. If b is a given HT P sequence, then there is a sequence c_{0}, c_{1}, c_{2}, … in R and an ϵ ∈ {0, 1} such that

b = ⋯ ∘ b(n, c_{n}) ∘ ⋯ ∘ b(1, c_{1}) ∘ b(0, c_{0}) ∘ σ^{ϵ}.

Our goal in Section 2 is to define the sequences b(n, c_{n}), which we do in Definition 2.5. In Section 3 we prove that the set of all HT P sequences forms a group (Theorem 3.6), and we prove our classification Theorem 1.5.

2 A collection of HTP sequences

Definition 2.1. Let T : R[x] → R be the R-linear homomorphism defined by T (x^{k}) = a_{k}. For integers i ≥ j ≥ 0, define T_{ij} : R[x] → R to be the R-linear homomorphism given by

T_{ij}(x^{k}) = (−1)^{i+j} |\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{i} \\ a_{1} & a_{2} & a_{3} & ⋯ & a_{i+1} \\ ⋮ & & & ... & ⋮ \\ a_{j−1} & a_{j} & a_{j+1} & ⋯ & a_{j−1+i} \\ a_{j+1} & a_{j+2} & a_{j+3} & ⋯ & a_{j+1+i} \\ ⋮ & & & ... & ⋮ \\ a_{i} & a_{i+1} & a_{i+2} & ⋯ & a_{2i} \\ a_{k} & a_{k+1} & a_{k+2} & ⋯ & a_{k+i} \end{matrix}| .

Remark 2.2. If 0 ≤ k ≤ i and k ≠ j, then T_{ij}(x^{k}) = 0, since two rows in the matrix defining T_{ij}(x^{k}) are equal. Also, keeping track of signs, one sees that T_{ij}(x^{j}) = T_{ii}(x^{i}). Finally, we note that T_{00} = T.

Definition 2.3. For each c ∈ R and each integer i ≥ 1, we define a sequence of polynomials f_{m,i,c}(x) ∈ R[x] recursively by

f_{0,i,c} = 1, f_{m+1,i,c} = f_{m,i,c} · (x + cT_{i−1,i−1}(x^{i−1})) − c (∑_{j=0}^{i−1} T_{i−1,j}(f_{m,i,c}) · x^{j}) .

Also, we define f_{m,0,c} ∈ R[x] by f_{m,0,c} = (x + c)^{m}, or (equivalently) recursively by

f_{0,0,c} = 1, f_{m+1,0,c} = f_{m,0,c} · (x + c).

We will show in Lemma 2.9 that for each i ≥ 0, m ≥ 0, and c ∈ R, f_{m,i,c}(x) is a degree m polynomial in x with leading coefficient 1.

Definition 2.4. Fixing a choice of i and c, define U_{k,m} for each k, m by

f_{m,i,c}(x) = ∑ U_{k,m}x^{k}.

Let U be the infinite matrix whose (k, m) entry is given by U_{k,m}.

Thus U is upper triangular, with diagonal entries all 1. Let A be the infinite Hankel matrix

A = (\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ \\ a_{1} & a_{2} & a_{3} & ⋯ \\ a_{2} & a_{3} & a_{4} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix})

We will show in Lemma 2.14 that the product U^{t}AU is a Hankel matrix.

Definition 2.5. Let b(i, c) denote the sequence whose Hankel matrix is the matrix U^{t}AU, where U is defined in terms of i and c as above.

We show in Corollary 2.15 that b(i, c) is an HTP sequence preserving a_{0} through a_{2i}. Example 2.6. If i = 1 and c = 1, then the recurrence relation of Definition 2.3 becomes

f_{m+1,1,1} = f_{m,1,1} · (x + a_{0}) − T (f_{m,1,1}),
f_{0,1,1} = 1.

Thus,

f_{1,1,1} = (x + a_{0}) − T (1) = x + a_{0} − a_{0} = x,
f_{2,1,1} = x(x + a_{0}) − T (x) = x^{2} + a_{0}x − a_{1},

f_{3,1,1} = (x^{2} + a_{0}x − a_{1})(x + a_{0}) − T (x^{2} + a_{0}x − a_{1}) = x^{3} + 2a_{0}x^{2} + (a_{0}^{2} − a_{1})x + −a_{0}a_{1} − a_{2}. Therefore, the upper left 4 × 4 submatrix of U is

(\begin{matrix}1 & 0 & −a_{1} & −a_{0}a_{1} − a_{2} \\ 0 & 1 & a_{0} & a_{0}^{2} − a_{1} \\ 0 & 0 & 1 & 2a_{0} \\ 0 & 0 & 0 & 1 \end{matrix})

Using Mathematica, we compute the upper left 4 × 4 submatrix of U^{t}AU to be

(\begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} − a_{1}^{2} + a_{0}a_{2} \\ a_{1} & a_{2} & a_{3} − a_{1}^{2} + a_{0}a_{2} & x \\ a_{2} & a_{3} − a_{1}^{2} + a_{0}a_{2} & x & y \\ a_{3} − a_{1}^{2} + a_{0}a_{2} & x & y & z \end{matrix})

where

x = a_{4} − a_{0}a_{1}^{2} + 2a_{0}a_{3} − 2a_{1}a_{2} + a_{0}^{2}a_{2}
y = a_{5} − 4a_{0}a_{1}a_{2} + 3a_{0}a_{4} − 2a_{1}a_{3} − a_{0}^{2}a_{1}^{2} + 3a_{0}a_{3} − a_{2}^{2} + a_{0}^{3}a_{2} + a_{1}^{3}
z = a_{6} + a_{0}^{4}a_{2} + 3a_{1}^{2}a_{2} − a_{0}^{3}a_{1}^{2} + 4a_{0}^{3}a_{3} − 2a_{2}a_{3} − 2a_{1}a_{4} − 6a_{0}^{2}a_{1}a_{2}
+6a_{0}^{2}a_{4} + 2a_{0}a_{1}^{3} − 3a_{0}a_{2}^{2} − 6a_{0}a_{1}a_{3} + 4a_{0}a_{5}

Thus, the first seven terms of b(1, 1) are a_{0}, a_{1}, a_{2}, a_{3} − a_{1}^{2} + a_{0}a_{2}, x, y, z. Example 2.7. If i = 2 and c = 1, then the recurrence relation of Definition 2.3 becomes

f_{m+1,2,1} = f_{m,2,1} · (x + T_{1,1}(x)) − T_{1,1}(f_{m,2,1})x − T_{1,0}(f_{m,2,1}),
f_{0,1,1} = 1.

Thus,

f_{1,2,1} = (x + a_{0}a_{2} − a_{1}^{2}) − 0x − (a_{0}a_{2} − a_{1}^{2}) = x,
f_{2,2,1} = x(x + a_{0}a_{2} − a_{1}^{2}) − (a_{0}a_{2} − a_{1}^{2})x + 0 = x^{2},

f_{3,2,1} = x^{2}(x + a_{0}a_{2} − a_{1}^{2}) − (a_{0}a_{3} − a_{1}a_{2})x + a_{1}a_{3} − a_{2}^{2}
= x^{3} + (a_{0}a_{2} − a_{1}^{2})x^{2} − (a_{0}a_{3} − a_{1}a_{2})x + a_{1}a_{3} − a_{2}^{2}.

Therefore, the upper left 4 × 4 submatrix of U is

(\begin{matrix}1 & 0 & 0 & a_{1}a_{3} − a_{2}^{2} \\ 0 & 1 & 0 & a_{1}a_{2} − a_{0}a_{3} \\ 0 & 0 & 1 & a_{0}a_{2} − a_{1}^{2} \\ 0 & 0 & 0 & 1 \end{matrix})

Using Mathematica, we compute the upper left 4 × 4 submatrix of U^{t}AU to be

(\begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} \\ a_{1} & a_{2} & a_{3} & a_{4} \\ a_{2} & a_{3} & a_{4} & x \\ a_{3} & a_{4} & x & y \end{matrix})

where

x = a_{5} − a_{2}^{3} − a_{0}a_{3}^{2} − a_{1}^{2}a_{4} + 2a_{1}a_{2}a_{3} + a_{0}a_{2}a_{4},
y = a_{6} − 2a_{1}^{3}a_{2}a_{3} − 2a_{2}^{2}a_{3} + a_{1}^{4}a_{4} − a_{0}^{2}a_{2}a_{3}^{2} + a_{0}^{2}a_{2}^{2}a_{4} + 2a_{0}a_{1}a_{2}^{2}a_{3} + 2a_{1}a_{3}^{2} + 2a_{1}a_{2}a_{4}
+a_{1}^{2}a_{2}^{3} + a_{0}a_{1}^{2}a_{3}^{2} − 2a_{0}a_{1}^{2}a_{2}a_{4} − 2a_{1}^{2}a_{5} − a_{0}a_{2}^{4} − 2a_{0}a_{3}a_{4} + 2a_{0}a_{2}a_{5}.

Thus the first seven terms of b(2, 1) are a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, x, y. Lemma 2.8. Suppose f and g are two polynomials in R[x], and i ≥ 0 is any integer. Then

∑_{j=0}^{i−1} T (f · x^{j}) · T_{i−1,j}(g) = ∑_{j=0}^{i−1} T (g · x^{j}) · T_{i−1,j}(f).

Proof. Since both sides of the equation are R-linear in both f and g, it suffices to consider the case when f = x^{m} and g = x^{n}, so we need to show that

∑_{j=0}^{i−1} T (x^{m+j}) · T_{i−1,j}(x^{n}) = ∑_{j=0}^{i−1} T (x^{n+j}) · T_{i−1,j}(x^{m}).

Consider the matrix below:

(\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{i−1} & a_{m} \\ a_{1} & a_{2} & a_{3} & ⋯ & a_{i} & a_{m+1} \\ a_{2} & a_{3} & a_{4} & ⋯ & a_{i+1} & a_{m+2} \\ ⋮ & & & ... & & ⋮ \\ a_{i−1} & a_{i} & a_{i+1} & ⋯ & a_{2i−2} & a_{m+i−1} \\ a_{n} & a_{n+1} & a_{n+2} & ⋯ & a_{n+i−1} & 0 \end{matrix})

If we compute the determinant by expanding along the rightmost column, we get

∑_{j=0}^{i−1}(−1)^{i+j}a_{m+j} · T_{i−1,j}(x^{n}) = − ∑_{j=0}^{i−1} T (x^{m+j}) · T_{i−1,j}(x^{n}).

If we compute the determinant by expanding along the bottom row, we get

∑_{j=0}^{i−1}(−1)^{i+j}a_{n+j} · T_{i−1,j}(x^{m}) = − ∑_{j=0}^{i−1} T (x^{n+j}) · T_{i−1,j}(x^{m}).

Lemma 2.9. For each i ≥ 0, m ≥ 0, and c ∈ R, f_{m,i,c}(x) is a degree m polynomial in x with leading coefficient 1.

Proof. When i = 0 or m = 0, the claim is clear. We assume i ≥ 1. Assume by induction on m that f_{m,i,c}(x) has degree m and leading coefficient 1. It then suffices to show by the recursive definition of f_{m+1,i,c}(x) that T_{i−1,j}(f_{m,i,c}) = 0 whenever i > j > m. This follows at once from Remark 2.2 and the inductive hypothesis.

Lemma 2.10. f_{m,i,c} = x^{m} whenever m ≤ i.

Proof. Using the recursive definition, we see that it is enough to show that

x^{m}T_{i−1,i−1}(x^{i−1}) = ∑_{j=0}^{i−1} T_{i−1,j}(x^{m})x^{j}

whenever m ≤ i − 1. This follows from Remark 2.2, since all terms in the right hand sum are 0, except for the term when j = m, and this is T_{i−1,m}(x^{m})x^{m} = T_{i−1,i−1}(x^{i−1})x^{m}.

Lemma 2.11. For m, n ≥ 0,

T (f_{m+1,i,c} · f_{n,i,c}) = T (f_{m,i,c} · f_{n+1,i,c}).

Proof. First,

f_{m+1,0,c} · f_{n,0,c} = (x + c)^{m+1}(x + c)^{n} = (x + c)^{m}(x + c)^{n+1} = f_{m,0,c} · f_{n+1,0,c}.

We now assume i ≥ 1. We then have

f_{m+1,i,c} · f_{n,i,c} − f_{m,i,c} · f_{n+1,i,c} =

(f_{m,i,c}(x + cT_{i−1,i−1}(x^{i−1})) − c (∑_{j=0}^{i−1} T_{i−1,j}(f_{m,i,c}) · x^{j})) · f_{n,i,c}−

f_{m,i,c} · (f_{n,i,c}(x + cT_{i−1,i−1}(x^{i−1})) − c (∑_{j=0}^{i−1} T_{i−1,j}(f_{n,i,c}) · x^{j}))

= c (f_{m,i,c} (∑_{j=0}^{i−1} T_{i−1,j}(f_{n,i,c}) · x^{j}) − (∑_{j=0}^{i−1} T_{i−1,j}(f_{m,i,c}) · x^{j}) f_{n,i,c})

= c ∑_{j=0}^{i−1} (f_{m,i,c} · x^{j} · T_{i−1,j}(f_{n,i,c}) − f_{n,i,c} · x^{j} · T_{i−1,j}(f_{m,i,c})) .

By Lemma 2.8, this term is in the kernel of T.

Lemma 2.12. T (f_{m,i,c}(x)) = a_{m} whenever 0 ≤ m ≤ 2i. Proof. Suppose m = 2i. Since f_{0,i,c} = 1, and by applying Lemma 2.11 i times,

T (f_{2i,i,c}) = T (f_{2i,i,c} · f_{0,i,c}) = T (f_{i,i,c} · f_{i,i,c}).

By Lemma 2.10, f_{i,i,c} = x^{i}, so (f_{i,i,c})^{2} = x^{2i}, and T (x^{2i}) = a_{2i}. The other cases follow similarly. Lemma 2.13.

T (f_{2i+1,i,c}(x)) = a_{2i+1} + c |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{i} \\ a_{1} & a_{2} & ⋯ & a_{i+1} \\ ⋮ & & ... & ⋮ \\ a_{i} & a_{i+1} & ⋯ & a_{2i} \end{matrix}| .

Proof. If we expand the determinant on the right hand side of the equation along the last column, we get

a_{2i+1} + ca_{2i}T_{i−1,i−1}(x^{i−1}) − c ∑_{j=0}^{i−1} T_{i−1,j}(x^{i})a_{i+j}

= T (x^{2i+1} + cx^{2i}T_{i−1,i−1}(x^{i−1}) − c ∑_{j=0}^{i−1} T_{i−1,j}(x^{i})x^{i+j})

= T (x^{i} (x^{i} (x + cT_{i−1,i−1}(x^{i−1})) − c ∑_{j=0}^{i−1} T_{i−1,j}(f_{i,i,c})x^{j}))

= T (x^{i} (f_{i,i,c} · (x + cT_{i−1,i−1}(x^{i−1})) − c ∑_{j=0}^{i−1} T_{i−1,j}(f_{i,i,c}) · x^{j}))

= T (x^{i} · f_{i+1,i,c}) = T (f_{i,i,c} · f_{i+1,i,c}) = T (f_{2i+1,i,c}).

Here, we have used Lemma 2.10 to identify x^{i} with f_{i,i,c} and Lemma 2.11 for the last equality.

Now recall that A is the infinite Hankel matrix

A = (\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ \\ a_{1} & a_{2} & a_{3} & ⋯ \\ a_{2} & a_{3} & a_{4} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix})

Lemma 2.14. The product U^{t}AU is a Hankel matrix. Proof. We have f_{r,i,c} · f_{u,i,c} = ∑_{s,t} U_{s,r}U_{t,u}x^{s+t}, so that

T (f_{r,i,c} · f_{u,i,c}) = ∑_{s,t} U_{s,r}U_{t,u}a_{s+t} = ∑_{s,t} U_{s,r}a_{s+t}U_{t,u}.

This is precisely the (r, u) entry of U^{t}AU. Now the result follows from Lemma 2.11.

Recall from Definition 2.5 that b(i, c) denotes the sequence whose Hankel matrix is U^{t}AU.

Corollary 2.15. We have b(i, c)_{n} = T (f_{n,i,c}), and b(i, c) is an HT P sequence preserving a_{0} through a_{2i}. Moreover

b(i, c)_{2i+1} = a_{2i+1} + c |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{i} \\ a_{1} & a_{2} & ⋯ & a_{i+1} \\ ⋮ & & ... & ⋮ \\ a_{i} & a_{i+1} & ⋯ & a_{2i} \end{matrix}| .

Proof. Since U^{t} and U are each triangular with 1s on the diagonal, it follows that the Hankel matrices of finite order associated to U^{t}AU have the same determinants as those of A. Thus the sequence of entries on the top row of U^{t}AU represents a transformation of A which preserves the Hankel transform. This is the same as the sequence of entries in the top row of AU since U^{t} preserves the top row. But it is easy to see that this sequence is given by T (f_{n,i,c}). The first 2i terms of the sequence are given by Lemma 2.12, while the 2i + 1 term is given by Lemma 2.13.

3 Classifying all HT P sequences

Lemma 3.1. For each integer n ≥ 0, the determinant

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}|

is irreducible in R.

Proof. The statement is obvious if n = 0, so suppose n ≥ 1. We make R into a graded ring by assigning deg(a_{i}) = 2n+1−i. Then the determinant is a homogeneous polynomial of degree (n + 1)^{2}. As a polynomial in a_{2n} with coefficients in ℤ[a_{0}, a_{1}, …, a_{2n−1}], the determinant can be written

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} \\ a_{1} & a_{2} & ⋯ & a_{n} \\ ⋮ & & ... & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} \end{matrix}| · a_{2n} + |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n} & a_{n+1} & ⋯ & a_{2n−1} & 0 \end{matrix}| .

The coefficient of a_{2n} has degree (n + 1)^{2} − 1, while the constant coefficient has degree (n + 1)^{2}. But no element in ℤ[a_{0}, a_{1}, …, a_{2n−1}] has degree 1. Therefore, the coefficient of a_{2n} does not divide the constant coefficient. By induction, the coefficient of a_{2n} is irreducible. The result follows from this.

Lemma 3.2. Suppose that b is an HTP sequence which preserves a_{0} through a_{2n−1}. Then b_{2n} = a_{2n}.

Proof. In order to have

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & b_{2n} \end{matrix}| = |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| ,

we must have

(b_{2n} − a_{2n}) |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} \\ a_{1} & a_{2} & ⋯ & a_{n} \\ ⋮ & & ... & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} \end{matrix}| = 0.

Thus, b_{2n} − a_{2n} must be 0.

Lemma 3.3. Suppose b is an HTP sequence. Then either b_{1} − a_{1} or b_{1} + a_{1} is divisible by a_{0} in R.

Proof. Clearly, b_{0} = a_{0}, since the 0th terms in the Hankel transforms must coincide. Now, in order to have

|\begin{matrix}a_{0} & b_{1} \\ b_{1} & b_{2} \end{matrix}| = |\begin{matrix}a_{0} & a_{1} \\ a_{1} & a_{2} \end{matrix}|

we must have b_{2}a_{0} − b_{1}^{2} = a_{2}a_{0} − a_{1}^{2}, so a_{0}(b_{2} − a_{2}) = b_{1}^{2} − a_{1}^{2} = (b_{1} − a_{1})(b_{1} + a_{1}). Therefore, a_{0} divides either b_{1} − a_{1} or b_{1} + a_{1}.

Lemma 3.4. Fix an integer n ≥ 1. Suppose b is an HT P sequence preserving a_{0} through a_{2n}. Then b_{2n+1} − a_{2n+1} is divisible by

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

Proof. We have

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ a_{1} & a_{2} & ⋯ & a_{n+1} & a_{n+2} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & b_{2n+1} \\ a_{n+1} & a_{n+2} & ⋯ & b_{2n+1} & b_{2n+2} \end{matrix}|

= b_{2n+2} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n} & a_{n+1} & ⋯ & a_{2n−1} & a_{2n} \end{matrix}| + |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ a_{1} & a_{2} & ⋯ & a_{n+1} & a_{n+2} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & b_{2n+1} \\ a_{n+1} & a_{n+2} & ⋯ & b_{2n+1} & 0 \end{matrix}|

The determinant on the right above can be written

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ 0 & 0 & ⋯ & 0 & b_{2n+1} \\ 0 & 0 & ⋯ & b_{2n+1} & 0 \end{matrix}| + |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & 0 \\ 0 & 0 & ⋯ & b_{2n+1} & 0 \end{matrix}|

+ |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ 0 & 0 & ⋯ & 0 & b_{2n+1} \\ a_{n+1} & a_{n+2} & ⋯ & 0 & 0 \end{matrix}| + |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & 0 \\ a_{n+1} & a_{n+2} & ⋯ & 0 & 0 \end{matrix}| .

(In each of the four above matrices, all rows except the last two are the same.) Now, we can write this as

= −b_{2n+1}^{2} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} \\ ⋮ & & ... & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} \end{matrix}| − b_{2n+1} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n−1} & 0 \end{matrix}|

−b_{2n+1} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n} & 0 \end{matrix}| + |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & 0 \\ a_{n+1} & a_{n+2} & ⋯ & 0 & 0 \end{matrix}| .

The second and third terms in the above sum are equal, since the determinant of a matrix is equal to the determinant of its transpose.

Now suppose

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ a_{1} & a_{2} & ⋯ & a_{n+1} & a_{n+2} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & b_{2n+1} \\ a_{n+1} & a_{n+2} & ⋯ & b_{2n+1} & b_{2n+2} \end{matrix}| = |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} & a_{n+1} \\ a_{1} & a_{2} & ⋯ & a_{n+1} & a_{n+2} \\ ⋮ & & ... & & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} & a_{2n+1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n+1} & a_{2n+2} \end{matrix}| .

Expanding these determinants as above and setting them equal, we get

b_{2n+2} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}|−b_{2n+1}^{2} |\begin{matrix}a_{0} & ⋯ & a_{n−1} \\ a_{1} & ⋯ & a_{n} \\ ⋮ & ... & ⋮ \\ a_{n−1} & ⋯ & a_{2n−2} \end{matrix}|−2b_{2n+1} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n−1} & 0 \end{matrix}| =

a_{2n+2} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}|−a_{2n+1}^{2} |\begin{matrix}a_{0} & ⋯ & a_{n−1} \\ a_{1} & ⋯ & a_{n} \\ ⋮ & ... & ⋮ \\ a_{n−1} & ⋯ & a_{2n−2} \end{matrix}|−2a_{2n+1} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n−1} & 0 \end{matrix}| .

Thus, we must have

(b_{2n+2} − a_{2n+2}) |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}|

= (b_{2n+1}^{2} − a_{2n+1}^{2}) |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} \\ a_{1} & a_{2} & ⋯ & a_{n} \\ ⋮ & & ... & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} \end{matrix}| + 2(b_{2n+1} − a_{2n+1}) |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n−1} & 0 \end{matrix}| .

By Lemma 3.1, either the claim is true or

|\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}|

must divide

(b_{2n+1} + a_{2n+1}) |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} \\ a_{1} & a_{2} & ⋯ & a_{n} \\ ⋮ & & ... & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} \end{matrix}| + 2 |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n−1} & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ ⋮ & & ... & & ⋮ \\ a_{n−1} & a_{n} & ⋯ & a_{2n−2} & a_{2n−1} \\ a_{n+1} & a_{n+2} & ⋯ & a_{2n−1} & 0 \end{matrix}| .

But in the quotient by the ideal I generated by a_{0}, a_{1}, …, a_{n−1}, a_{n+2}, a_{n+3}, …, a_{2n+1}, the first determinant becomes a_{n}^{n+1} (up to a sign), while the sum above becomes 2a_{n}^{n} ∗ a_{n+1} (again up to a sign). Since a_{n} does not divide a_{n+1} in R/I, the claim must be true.

We now turn to showing that the set of HT P sequences forms a group under composition. For this, we first need the following Lemma.

Lemma 3.5. Suppose that b and b′ are two HT P sequences which each preserve a_{0} through a_{2n}, n ≥ 1. Also, suppose that b_{2n+1} +b′_{2n+1} = 2a_{2n+1}. Then b∘b′ preserves a_{0} through a_{2n+2}.

Proof. Let d = b ∘ b′. Clearly d preserves a_{0} through a_{2n}. By Lemma 3.4, there is a c such that

b_{2n+1} = a_{2n+1} + c |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

Since b_{2n+1} + b′_{2n+1} = 2a_{2n+1}, we must have

b′_{2n+1} = a_{2n+1} − c |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

Since both b and b′ preserve a_{0} through a_{2n}, it follows that d_{2n+1} = a_{2n+1}. Now d_{2n+2} = a_{2n+2} by Lemma 3.2.

Theorem 3.6. The set of HT P sequences forms a group under composition.

Proof. It suffices to show that any HT P sequence b has a left inverse. By Lemma 3.3, either b_{1} − a_{1} is divisible by a_{0} or b_{1} + a_{1} is divisible by a_{0}. We will assume first that b_{1} − a_{1} is divisible by a_{0}. Now let n be the smallest number such that b_{2n+1} ≠ a_{2n+1} (so n ≥ 0, since b_{0} = a_{0}.) By Lemma 3.2, we know that b_{2n} = a_{2n}. Choose c_{n} as in Lemma 3.4 (or 3.3) so that

b_{2n+1} = a_{2n+1} − c_{n} |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

Then by Lemma 3.5 and Corollary 2.15, the composition b(n, c_{n}) ∘ b preserves a_{0} through a_{2n+2}.

Now, we inductively define a sequence c_{0}, c_{1}, c_{2}, … so that the composition

b(n, c_{n}) ∘ b(n − 1, c_{n−1}) ∘ ⋯ ∘ b(0, c_{0}) ∘ b

preserves a_{0} through a_{2n+2}. Thus

(⋯ ∘ b(n, c_{n}) ∘ b(n − 1, c_{n−1}) ∘ ⋯ ∘ b(0, c_{0})) ∘ b = id.

We assumed above that b_{1} − a_{1} is divisible by a_{0}. If b_{1} + a_{1} is divisible by a_{0}, then we can reduce to the former case by replacing b by b ∘ σ (see Example 1.1). Then, as above, we can find a sequence c_{0}, c_{1}, c_{2}, … so that

⋯ ∘ b(n, c_{n}) ∘ b(n − 1, c_{n−1}) ∘ ⋯ ∘ b(0, c_{0}) ∘ b ∘ σ = id.

Composing and precomposing both sides with σ (which satisfies σ^{2} = id), we get

σ ∘ (⋯ ∘ b(n, c_{n}) ∘ b(n − 1, c_{n−1}) ∘ ⋯ ∘ b(0, c_{0})) ∘ b = id.

Lemma 3.7. The inverse b(n, c)^{−1} of b(n, c) preserves a_{0} through a_{2n} and satisfies

b(n, c)_{2n+1}^{−1} = a_{2n+1} − c |\begin{matrix}a_{0} & a_{1} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & a_{n+1} \\ ⋮ & & ... & ⋮ \\ a_{n} & a_{n+1} & ⋯ & a_{2n} \end{matrix}| .

Proof. Since b(n, c) preserves a_{0} through a_{2n} by Corollary 2.15, it is clear that b(n, c)^{−1} also preserves a_{0} through a_{2n}. For the second part, b(n, −c) = b(n, −c) ∘ b(n, c) ∘ b(n, c)^{−1}. Since b(n, −c)∘b(n, c) preserves a_{0} through a_{2n+2} by Lemma 3.5 and Corollary 2.15, it follows that b(n, c)^{−1} must have the same 2n + 1 term as b(n, −c).

Remark 3.8. We do not know whether or not b(n, c)^{−1} = b(n, −c) in general.

We now prove our main theorem.

Proof. As in Theorem 3.6, we can inductively define c_{0}, c_{1}, … such that either

b′ := b ∘ b(0, c_{0})^{−1} ∘ b(1, c_{1})^{−1} ∘ ⋯ ∘ b(n, c_{n})^{−1}

or

b′ := b ∘ σ ∘ b(0, c_{0})^{−1} ∘ b(1, c_{1})^{−1} ∘ ⋯ ∘ b(n, c_{n})^{−1}

preserves a_{0} through a_{2n+2}. Here, we use Lemma 3.7 together with Lemma 3.5 to complete the inductive step. Now either b or b ∘ σ can be written as

b′ ∘ b(n, c_{n}) ∘ ⋯ ∘ b(1, c_{1}) ∘ b(0, c_{0}).

It follows that

⋯ ∘ b(n, c_{n}) ∘ ⋯ ∘ b(1, c_{1}) ∘ b(0, c_{0})

agrees on all terms with b or b ∘ σ. In the latter case, we multiply both sides by σ.

References

[1] M. Chamberland and C. French, Generalized Catalan numbers and generalized Hankel transformations, J. Integer Seq. 10 (2007), Article 07.1.1.

[2] R. Ehrenborg, The Hankel determinant of exponential polynomials, Amer. Math. Monthly, 107 (2000), 557–560.

[3] J. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5.

[4] C. Radoux, Déterminant de Hankel construit sur des polynômes liés aux nombres de dérangements. European J. Combin. 12 (1991), 327–329.

[5] M. Spivey and L. Steil, The k-binomial transforms and the Hankel transform, J. Integer Seq. 9 (2006), Article 06.1.1.

[6] E. Weisstein, Binomial transform, from MathWorld – A Wolfram Web Resource,

   http://mathworld.wolfram.com/BinomialTransform.html.

2000 Mathematics Subject Classification: Primary 11B75; Secondary 15A36, 11C20. Keywords: Hankel transform, binomial transform.

Received April 20 2007; revised version received June 20 2007. Published in Journal of Integer Sequences, July 4 2007.

Return to Journal of Integer Sequences home page.