\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Transformations Preserving the Hankel \\
\vskip .1in
Transform}

\vskip 1cm
\large
Christopher French\\
Department of Mathematics and Statistics\\
Grinnell College\\
Grinnell, IA 50112\\
USA\\
\href{mailto:frenchc@math.grinnell.edu}{\tt frenchc@math.grinnell.edu}\\
\end{center}

\vskip .2in

\begin{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.
\end{abstract}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\section{Introduction}

Given a sequence of integers $\{a_i\}=a_0, a_1, a_2,\ldots$, the Hankel matrix of $A$
is the infinite matrix whose $(i,j)$ entry is $a_{i+j}$ for $i\geq 0, j\geq 0$.
The Hankel matrix of order $n$ of $A$ is the $n\times 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
\[\left(\begin{matrix} a_0 & a_1 & a_2 \\ a_1 & a_2 & a_3 \\ a_2 & a_3 & a_4\end{matrix}\right).\]

Let $R=\mathbb Z[a_0,a_1,a_2,\ldots]$.  We will say that a sequence 
$\{b_i\}=\{b_0, b_1, b_2,\ldots\}$ of elements in $R$
is an $HTP$ 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$:
\[\left|\begin{matrix} b_0 & b_1 & \cdots & b_n\\
b_1 & b_2 & \cdots & b_{n+1}\\
\vdots && \ddots & \vdots\\
b_n & b_{n+1} & \cdots & b_{2n}\end{matrix}\right|=
\left|\begin{matrix} a_0 & a_1 & \cdots & a_n\\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_n & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]

An $HTP$ sequence $\{b_i\}$
determines a ring homomorphism $b:R\to 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 $HTP$ sequences is the ring homomorphism
associated to an $HTP$ sequence, so that the set of all $HTP$ sequences
has a semigroup structure (with $b_i=a_i$ representing the identity).
We will see (Theorem \ref{thm:group}) that this is actually a group structure.

\begin{example}\label{ex:sigma}
Let $\sigma:R\to R$ be given by $\sigma(a_i)=(-1)^i a_i$.  Then $\sigma$
determines an $HTP$ 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_nD_n$ is the same as that of $A_n$.
\end{example}

\begin{example}\label{ex:k}
For an integer $k$, the sequence defined by
$b_n=\sum_{i=0}^n {n\choose i} k^{n-i}a_i$ is an $HTP$ sequence.
(Here, if $k=0$, then we interpret $0^0$ to be $1$.)
Spivey and Steil \cite{SS} 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 \cite{L} originally proved preserves the Hankel transform.
\end{example}

\begin{remark}
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=\mathbb Z[a_0,a_1,a_2,\ldots]$, so in our
language, $\{b_n\}$ would not be an HTP sequence.  Since we
are interested in integer sequences, we have restricted to $\mathbb Z[a_0,a_1,a_2,\ldots]$.
\end{remark}

\begin{definition} An $HTP$ sequence $b$ {\it preserves $a_0$ through $a_n$} if $b_i=a_i$
for $0\leq i\leq n$.
\end{definition}

Suppose that $b(m)$ is a sequence of $HTP$ 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 {\it infinite composition} \[\cdots \circ b(m)\circ b(m-1)\circ\cdots\circ b(0)\] is itself a well-defined
sequence.  Indeed, the $n$th term in the sequence of this infinite composite
is determined by $b(M(n))\circ b(M(n)-1)\circ\cdots\circ b(0)$.  It is easy to see that this
infinite composition is itself an $HTP$ sequence.

In order to find all $HTP$ 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\in R$, we will define an $HTP$ sequence $b(n,c)$
which preserves $a_0$ through $a_{2n}$.
Example \ref{ex:k} above arises
when $n=0$ and $c\in \mathbb Z$.  Our main theorem is

\begin{theorem}\label{thm:main}
If $b$ is a given $HTP$
sequence, then there is a sequence 
$c_0, c_1, c_2,\ldots$ in $R$ and an $\epsilon\in\{0,1\}$
such that
\[b=\cdots\circ b(n,c_n)\circ\cdots\circ b(1,c_1)\circ b(0,c_0)\circ\sigma^{\epsilon}.\]
\end{theorem}

Our goal in Section \ref{sec:seq} is to define the sequences $b(n,c_n)$, which we do in
Definition \ref{def:seq}.  In Section \ref{sec:classify} we prove that the set of all $HTP$ sequences
forms a group (Theorem \ref{thm:group}), and we prove our classification
Theorem \ref{thm:main}.

\section{A collection of HTP sequences}\label{sec:seq}

\begin{definition}
Let $T:R[x]\to R$ be the $R$-linear homomorphism defined by
$T(x^k)=a_k$.
For integers $i\geq j\geq 0$, define $T_{ij}:R[x]\to R$ to be the $R$-linear homomorphism given by
\[T_{ij}(x^k)=(-1)^{i+j}\left|\begin{matrix} 
a_0 & a_1 & a_2 & \cdots & a_i \\
a_1 & a_2 & a_3 & \cdots & a_{i+1}\\
\vdots &&&\ddots&\vdots \\
a_{j-1} & a_j & a_{j+1} & \cdots & a_{j-1+i}\\
a_{j+1} & a_{j+2} & a_{j+3} & \cdots & a_{j+1+i}\\
\vdots &&&\ddots&\vdots\\
a_i & a_{i+1} & a_{i+2} & \cdots & a_{2i}\\
a_k & a_{k+1} & a_{k+2} & \cdots & a_{k+i}\end{matrix}\right|.\]
\end{definition}

\begin{remark}\label{rem:0}
If $0\leq k\leq i$ and $k\neq 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$.
\end{remark}

\begin{definition}\label{def:recurrence}
For each $c\in R$ and each integer $i\geq 1$, we define a sequence of polynomials
$f_{m,i,c}(x)\in R[x]$ recursively by
\[f_{0,i,c}=1,{\hskip 20pt}
f_{m+1,i,c}=f_{m,i,c}\cdot (x+cT_{i-1,i-1}(x^{i-1}))-
c\left(\sum_{j=0}^{i-1} T_{i-1,j}(f_{m,i,c})\cdot x^j\right).\]
Also, we define $f_{m,0,c}\in R[x]$ by $f_{m,0,c}=(x+c)^m$, or (equivalently)
recursively by
\[f_{0,0,c}=1,{\hskip 20pt}
f_{m+1,0,c}=f_{m,0,c}\cdot (x+c).\]
\end{definition}

We will show in Lemma \ref{lem:leading} that for each $i\geq 0$, $m\geq 0$, and $c\in R$,
$f_{m,i,c}(x)$ is a degree $m$ polynomial in $x$ with leading coefficient $1$.

\begin{definition}\label{def:U}
Fixing a choice of $i$ and $c$, define $U_{k,m}$ for each $k, m$ by
\[f_{m,i,c}(x)=\sum U_{k,m}x^k.\]
Let $U$ be the infinite matrix whose $(k,m)$ entry is given by $U_{k,m}$.
\end{definition}

Thus $U$ is upper triangular, with diagonal entries all $1$.
Let $A$ be the infinite Hankel matrix
\[A=\left(\begin{matrix}
a_0 & a_1 & a_2 & \cdots \\
a_1 & a_2 & a_3 & \cdots \\
a_2 & a_3 & a_4 & \cdots \\
\vdots & \vdots & \vdots & \ddots
\end{matrix}
\right)\]

We will show in Lemma \ref{lem:Hankel} that the product $U^tAU$ is a Hankel matrix.

\begin{definition}\label{def:seq} Let $b(i,c)$ denote the sequence whose
Hankel matrix is the matrix $U^tAU$, where $U$ is defined in terms of $i$ and $c$ as above.
\end{definition}

We show in Corollary \ref{cor:preserve} that $b(i,c)$ is an HTP sequence preserving
$a_0$ through $a_{2i}$.

\begin{example}
If $i=1$ and $c=1$, then the recurrence relation of Definition \ref{def:recurrence} becomes
\[f_{m+1,1,1}=f_{m,1,1}\cdot (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_0x-a_1,\]
\[f_{3,1,1}=(x^2+a_0x-a_1)(x+a_0)-T(x^2+a_0x-a_1)=x^3+2a_0x^2+(a_0^2-a_1)x+-a_0a_1-a_2.\]
Therefore, the upper left $4\times 4$ submatrix of $U$ is
\[\left(\begin{matrix} 1 & 0 & -a_1 & -a_0a_1-a_2\\ 0 & 1 & a_0 & a_0^2-a_1\\ 0 & 0 & 1 & 2a_0\\
0 & 0 & 0 & 1\end{matrix}\right)\]
Using Mathematica, we compute
the upper left $4\times 4$ submatrix of $U^tAU$ to be
\[\left(\begin{matrix} a_0 & a_1 & a_2 & a_3-a_1^2+a_0a_2 \\
a_1 & a_2 & a_3-a_1^2+a_0a_2 & x \\
a_2 & a_3-a_1^2+a_0a_2 & x & y\\
a_3-a_1^2+a_0a_2 & x & y & z
\end{matrix}\right)\]
where
\[x=a_4 - a_0a_1^2+2a_0a_3-2a_1a_2+a_0^2a_2\]
\[y=a_5-4a_0a_1a_2+3a_0a_4-2a_1a_3-a_0^2a_1^2+3a_0a_3-a_2^2+a_0^3a_2+a_1^3\]
\[z=a_6+a_0^4a_2+3a_1^2a_2-a_0^3a_1^2+4a_0^3a_3-2a_2a_3-2a_1a_4-6a_0^2a_1a_2\]
\[+6a_0^2a_4+2a_0a_1^3-3a_0a_2^2-6a_0a_1a_3+4a_0a_5\]

Thus, the first seven terms of $b(1,1)$ are $a_0, a_1, a_2, a_3-a_1^2+a_0a_2, x, y, z$.
\end{example}

\begin{example}
If $i=2$ and $c=1$, then
the recurrence relation of Definition \ref{def:recurrence} becomes
\[f_{m+1,2,1}=f_{m,2,1}\cdot (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_0a_2-a_1^2)-0x-(a_0a_2-a_1^2)=x,\]
\[f_{2,2,1}=x(x+a_0a_2-a_1^2)-(a_0a_2-a_1^2)x+0=x^2,\]
\[f_{3,2,1}=x^2(x+a_0a_2-a_1^2)-(a_0a_3-a_1a_2)x+a_1a_3-a_2^2\]
\[=x^3+(a_0a_2-a_1^2)x^2-(a_0a_3-a_1a_2)x+a_1a_3-a_2^2.\]
Therefore, the upper left $4\times 4$ submatrix of $U$ is
\[\left(\begin{matrix} 1 & 0 & 0 & a_1a_3-a_2^2 \\
0 & 1 & 0 & a_1a_2-a_0a_3\\
0 & 0 & 1 & a_0a_2-a_1^2\\
0 & 0 & 0 & 1\end{matrix}\right)\]
Using Mathematica, we compute
the upper left $4\times 4$ submatrix of $U^tAU$ to be
\[\left(\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}\right)\]
where
\[x=a_5-a_2^3-a_0a_3^2-a_1^2a_4+2a_1a_2a_3+a_0a_2a_4,\]
\[y=a_6-2a_1^3a_2a_3-2a_2^2a_3+a_1^4a_4-a_0^2a_2a_3^2+a_0^2a_2^2a_4+2a_0a_1a_2^2a_3
+2a_1a_3^2+2a_1a_2a_4\]
\[+a_1^2a_2^3+a_0a_1^2a_3^2-2a_0a_1^2a_2a_4-2a_1^2a_5
-a_0a_2^4-2a_0a_3a_4+2a_0a_2a_5.\]
Thus the first seven terms of $b(2,1)$ are $a_0, a_1, a_2, a_3, a_4, x, y$.
\end{example}


\begin{lemma}\label{lem:T00}
Suppose $f$ and $g$ are two polynomials in $R[x]$, and $i\geq 0$ is any integer.
Then \[\sum_{j=0}^{i-1} T(f\cdot x^j)\cdot T_{i-1,j}(g)=\sum_{j=0}^{i-1} T(g\cdot x^j)\cdot T_{i-1,j}(f).\]
\end{lemma}

\begin{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
\[\sum_{j=0}^{i-1} T(x^{m+j})\cdot T_{i-1,j}(x^n)=\sum_{j=0}^{i-1} T(x^{n+j})\cdot T_{i-1,j}(x^m).\]

Consider the matrix below:
\[\left(\begin{matrix}
a_0 & a_1 & a_2 & \cdots & a_{i-1} & a_m \\
a_1 & a_2 & a_3 & \cdots & a_{i} & a_{m+1}\\
a_2 & a_3 & a_4 & \cdots & a_{i+1} & a_{m+2}\\
\vdots &&&\ddots &&\vdots \\
a_{i-1} & a_{i} & a_{i+1} & \cdots & a_{2i-2} & a_{m+i-1}\\
a_n & a_{n+1} & a_{n+2} & \cdots & a_{n+i-1} & 0
\end{matrix}\right)\]
If we compute the determinant by expanding along the rightmost column, we get
\[\sum_{j=0}^{i-1} (-1)^{i+j}a_{m+j} \cdot T_{i-1,j}(x^n)=
-\sum_{j=0}^{i-1} T(x^{m+j}) \cdot T_{i-1,j}(x^n).\]
If we compute the determinant by expanding along the bottom row, we get
\[\sum_{j=0}^{i-1} (-1)^{i+j}a_{n+j} \cdot T_{i-1,j}(x^m)=
-\sum_{j=0}^{i-1} T(x^{n+j}) \cdot T_{i-1,j}(x^m).\]
\end{proof}

\begin{lemma}\label{lem:leading}
For each $i\geq 0$, $m\geq 0$, and $c\in R$, $f_{m,i,c}(x)$ is a degree $m$
polynomial in $x$ with leading coefficient $1$.
\end{lemma}

\begin{proof}
When $i=0$ or $m=0$, the claim is clear.  We assume $i\geq 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 \ref{rem:0}
and the inductive hypothesis.
\end{proof}

\begin{lemma}\label{lem:x} $f_{m,i,c}=x^m$ whenever $m\leq i$.
\end{lemma}

\begin{proof}
Using the recursive definition, we see that it is enough to show that
\[x^mT_{i-1,i-1}(x^{i-1})=\sum_{j=0}^{i-1} T_{i-1,j}(x^m)x^j\]
whenever $m\leq i-1$.  This follows from Remark \ref{rem:0}, 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$.
\end{proof}

\begin{lemma}\label{lem:commute}
For $m,n\geq 0$, \[T(f_{m+1,i,c}\cdot f_{n,i,c})=T(f_{m,i,c}\cdot f_{n+1,i,c}).\]
\end{lemma}

\begin{proof}
First, \[f_{m+1,0,c}\cdot f_{n,0,c}=(x+c)^{m+1}(x+c)^{n}
=(x+c)^{m}(x+c)^{n+1}=f_{m,0,c}\cdot f_{n+1,0,c}.\]
We now assume $i\geq 1$.
We then have
\[f_{m+1,i,c}\cdot f_{n,i,c}-f_{m,i,c}\cdot f_{n+1,i,c}=\]
\[\left(f_{m,i,c}(x+cT_{i-1,i-1}(x^{i-1}))-
c\left(\sum_{j=0}^{i-1} T_{i-1,j}(f_{m,i,c})\cdot x^j\right)\right)\cdot f_{n,i,c}-\]
\[f_{m,i,c}\cdot \left(f_{n,i,c}(x+cT_{i-1,i-1}(x^{i-1}))-
c\left(\sum_{j=0}^{i-1} T_{i-1,j}(f_{n,i,c})\cdot x^j\right)\right)\]
\[=c\left(f_{m,i,c}\left(\sum_{j=0}^{i-1} T_{i-1,j}(f_{n,i,c})\cdot x^j\right)-
\left(\sum_{j=0}^{i-1} T_{i-1,j}(f_{m,i,c})\cdot x^j\right)f_{n,i,c}\right)\]
\[=c\sum_{j=0}^{i-1} \left(f_{m,i,c}\cdot x^j\cdot T_{i-1,j}(f_{n,i,c})-
f_{n,i,c}\cdot x^j\cdot T_{i-1,j}(f_{m,i,c})\right).\]
By Lemma \ref{lem:T00}, this term is in the kernel of $T$.
\end{proof}

\begin{lemma}\label{lem:first} $T(f_{m,i,c}(x))=a_m$ whenever $0\leq m\leq 2i$.
\end{lemma}

\begin{proof}
Suppose $m=2i$.
Since $f_{0,i,c}=1$, and by applying Lemma \ref{lem:commute} $i$ times,
\[T(f_{2i,i,c})=T(f_{2i,i,c}\cdot f_{0,i,c})=T(f_{i,i,c}\cdot f_{i,i,c}).\]
By Lemma \ref{lem:x}, $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.
\end{proof}

\begin{lemma}\label{lem:2i+1} \[T(f_{2i+1,i,c}(x))=
a_{2i+1}+c\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{i}\\
a_1 & a_2 & \cdots & a_{i+1}\\
\vdots & & \ddots &  \vdots\\
a_{i} & a_{i+1} & \cdots & a_{2i}\end{matrix}\right|.\]
\end{lemma}

\begin{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\sum_{j=0}^{i-1} T_{i-1,j}(x^{i})a_{i+j}\]
\[=T\left(x^{2i+1}+cx^{2i}T_{i-1,i-1}(x^{i-1})-c\sum_{j=0}^{i-1} T_{i-1,j}(x^{i})x^{i+j}\right)\]
\[=T\left(x^{i}\left(x^i\left(x+cT_{i-1,i-1}(x^{i-1})\right)
-c\sum_{j=0}^{i-1} T_{i-1,j}(f_{i,i,c})x^j\right)\right)\]
\[=T\left(x^i\left(f_{i,i,c}\cdot \left(x+cT_{i-1,i-1}(x^{i-1})\right)
-c\sum_{j=0}^{i-1}T_{i-1,j}(f_{i,i,c})\cdot x^j\right)\right)\]
\[=T(x^i\cdot f_{i+1,i,c})=T(f_{i,i,c}\cdot f_{i+1,i,c})=T(f_{2i+1,i,c}).\]
Here, we have used Lemma \ref{lem:x} to identify $x^i$ with $f_{i,i,c}$ and
Lemma \ref{lem:commute} for the last equality.
\end{proof}


Now recall that $A$ is the infinite Hankel matrix
\[A=\left(\begin{matrix}
a_0 & a_1 & a_2 & \cdots \\
a_1 & a_2 & a_3 & \cdots \\
a_2 & a_3 & a_4 & \cdots \\
\vdots & \vdots & \vdots & \ddots
\end{matrix}
\right)\]

\begin{lemma}\label{lem:Hankel} The product $U^tAU$ is a Hankel matrix.
\end{lemma}

\begin{proof}
We have $f_{r,i,c}\cdot f_{u,i,c}=\sum_{s,t} U_{s,r}U_{t,u}x^{s+t}$,
so that
\[T(f_{r,i,c}\cdot f_{u,i,c})=\sum_{s,t} U_{s,r} U_{t,u} a_{s+t} =\sum_{s,t} U_{s,r} a_{s+t} U_{t,u}.\]
This is precisely the $(r,u)$ entry of $U^tAU$.  Now the result follows from Lemma \ref{lem:commute}.
\end{proof}

Recall from Definition \ref{def:seq} that $b(i,c)$ denotes the sequence whose
Hankel matrix is $U^tAU$.

\begin{corollary}\label{cor:preserve} We have $b(i,c)_n=T(f_{n,i,c})$,
and $b(i,c)$ is an $HTP$ sequence preserving
$a_0$ through $a_{2i}$.
Moreover \[b(i,c)_{2i+1}=a_{2i+1}+c\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{i}\\
a_1 & a_2 & \cdots & a_{i+1}\\
\vdots & & \ddots & \vdots\\
a_{i} & a_{i+1} & \cdots & a_{2i}\end{matrix}\right|.\]
\end{corollary}

\begin{proof}
Since $U^t$ and $U$ are each triangular with $1$s on the diagonal, it follows that the
Hankel matrices of finite order associated to $U^tAU$ have the same determinants as those of $A$.
Thus the sequence of entries on the top row of $U^tAU$ 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 \ref{lem:first}, while the $2i+1$ term is given by Lemma \ref{lem:2i+1}.
\end{proof}

\section{Classifying all $HTP$ sequences}\label{sec:classify}
 
\begin{lemma}\label{lem:irreducible} For each integer $n\geq 0$, the determinant
\[\left|\begin{matrix} a_0 & a_1 & \cdots & a_n \\
a_1 & a_2 & \cdots & a_{n+1} \\
\vdots && \ddots &\vdots \\
a_n & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|\] is irreducible in $R$.
\end{lemma}

\begin{proof}
The statement is obvious if $n=0$, so suppose $n\geq 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 $\mathbb Z[a_0, a_1, \ldots, a_{2n-1}]$,
the determinant can be written
\[\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} \\
a_1 & a_2 & \cdots & a_{n} \\
\vdots && \ddots & \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2}\end{matrix}\right|\cdot a_{2n}
+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n-1} & a_n \\
a_1 & a_2 & \cdots & a_n & a_{n+1} \\
\vdots && \ddots && \vdots \\
a_{n-1} & a_n & \cdots & a_{2n-2} & a_{2n-1} \\
a_n & a_{n+1} & \cdots & a_{2n-1} & 0\end{matrix}\right|.\]

The coefficient of $a_{2n}$ has degree $(n+1)^2-1$, while
the constant coefficient has degree $(n+1)^2$.  But no element
in $\mathbb Z[a_0, a_1, \ldots, 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.
\end{proof}

\begin{lemma}\label{lem:2n} Suppose that $b$ is an HTP sequence which preserves
$a_0$ through $a_{2n-1}$.  Then $b_{2n}=a_{2n}$.
\end{lemma}

\begin{proof}
In order to have
\[\left|\begin{matrix} a_0 & a_1 & \cdots & a_n\\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_n & a_{n+1} & \cdots & b_{2n}\end{matrix}\right|=
\left|\begin{matrix} a_0 & a_1 & \cdots & a_n\\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_n & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|,\]
we must have
\[(b_{2n}-a_{2n})\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} \\
a_1 & a_2 & \cdots & a_{n}\\
\vdots && \ddots & \vdots\\
a_{n-1} & a_n & \cdots & a_{2n-2}\end{matrix}\right|=0.\]
Thus, $b_{2n}-a_{2n}$ must be 0.
\end{proof}

\begin{lemma}\label{lem:n=1} Suppose $b$ is an HTP sequence.
Then either $b_1-a_1$ or $b_1+a_1$ is divisible by $a_0$ in $R$.
\end{lemma}

\begin{proof}
Clearly, $b_0=a_0$, since the $0$th terms in the Hankel transforms must coincide.
Now, in order to have
\[\left|\begin{matrix} a_0 & b_1 \\ b_1 & b_2\end{matrix}\right|=
\left|\begin{matrix} a_0 & a_1 \\ a_1 & a_2\end{matrix}\right|\]
we must have $b_2a_0-b_1^2=a_2a_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$.
\end{proof}

\begin{lemma}\label{lem:divisible} Fix an integer $n\geq 1$.
Suppose $b$ is an $HTP$ sequence preserving $a_0$ through $a_{2n}$.
Then $b_{2n+1}-a_{2n+1}$ is divisible by
\[\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1} \\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]
\end{lemma}

\begin{proof}
We have
\[\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
a_1 & a_2 & \cdots & a_{n+1} & a_{n+2}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & b_{2n+1} \\
a_{n+1} & a_{n+2} & \cdots & b_{2n+1} & b_{2n+2}\end{matrix}\right|\]
\[=b_{2n+2}\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n-1} & a_{n}\\
a_1 & a_2 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2} & a_{2n-1} \\
a_{n} & a_{n+1} & \cdots & a_{2n-1} & a_{2n}\end{matrix}\right|
+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
a_1 & a_2 & \cdots & a_{n+1} & a_{n+2}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & b_{2n+1} \\
a_{n+1} & a_{n+2} & \cdots & b_{2n+1} & 0\end{matrix}\right|\]

The determinant on the right above can be written
\[\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
0 & 0 & \cdots & 0 & b_{2n+1} \\
0 & 0 & \cdots & b_{2n+1} & 0\end{matrix}\right|
+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & 0 \\
0 & 0 & \cdots & b_{2n+1} & 0\end{matrix}\right|\]

\[+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
0 & 0 & \cdots & 0 & b_{2n+1} \\
a_{n+1} & a_{n+2} & \cdots & 0 & 0\end{matrix}\right|
+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & 0 \\
a_{n+1} & a_{n+2} & \cdots & 0 & 0\end{matrix}\right|.\]

(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\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n-1}\\
\vdots && \ddots & \vdots\\
a_{n-1} & a_n & \cdots & a_{2n-2}\end{matrix}\right|
-b_{2n+1}\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n-1} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_n & a_{n+1} & \cdots & a_{2n-1} & 0\end{matrix}\right|\]

\[-b_{2n+1}\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n-1} & a_n\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_n & \cdots & a_{2n-2} & a_{2n-1}\\
a_{n+1} & a_{n+2} & \cdots & a_{2n} & 0
\end{matrix}\right|
+\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & 0 \\
a_{n+1} & a_{n+2} & \cdots & 0 & 0\end{matrix}\right|.\]
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
\[\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
a_1 & a_2 & \cdots & a_{n+1} & a_{n+2}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & b_{2n+1} \\
a_{n+1} & a_{n+2} & \cdots & b_{2n+1} & b_{2n+2}\end{matrix}\right|=
\left|\begin{matrix} a_0 & a_1 & \cdots & a_{n} & a_{n+1}\\
a_1 & a_2 & \cdots & a_{n+1} & a_{n+2}\\
\vdots && \ddots && \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n} & a_{2n+1} \\
a_{n+1} & a_{n+2} & \cdots & a_{2n+1} & a_{2n+2}\end{matrix}\right|.\]
Expanding these determinants as above and setting them equal, we get
\small{\[b_{2n+2}\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|
-b_{2n+1}^2\left|\begin{matrix}
a_0 & \cdots & a_{n-1} \\
a_1 & \cdots & a_{n}\\
\vdots & \ddots & \vdots\\
a_{n-1} & \cdots & a_{2n-2}\end{matrix}\right|-
2b_{2n+1}\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} & a_{n} \\
a_1 & a_2 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2} &  a_{2n-1} \\ 
a_{n+1} & a_{n+2} & \cdots & a_{2n-1} & 0\end{matrix}\right|=\]
\[a_{2n+2}\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|
-a_{2n+1}^2\left|\begin{matrix}
a_0 & \cdots & a_{n-1} \\
a_1 & \cdots & a_{n}\\
\vdots & \ddots & \vdots\\
a_{n-1} & \cdots & a_{2n-2}\end{matrix}\right|-
2a_{2n+1}\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} & a_{n} \\
a_1 & a_2 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2} &  a_{2n-1} \\ 
a_{n+1} & a_{n+2} & \cdots & a_{2n-1} & 0\end{matrix}\right|.\]}

Thus, we must have
\[(b_{2n+2}-a_{2n+2})\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|\]
\[=(b_{2n+1}^2-a_{2n+1}^2)\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} \\
a_1 & a_2 & \cdots & a_{n}\\
\vdots && \ddots & \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2}\end{matrix}\right|+
2(b_{2n+1}-a_{2n+1})\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} & a_{n} \\
a_1 & a_2 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2} &  a_{2n-1} \\ 
a_{n+1} & a_{n+2} & \cdots & a_{2n-1} & 0\end{matrix}\right|.\]

By Lemma \ref{lem:irreducible}, either the claim is true or
\[\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|\]
must divide
\[(b_{2n+1}+a_{2n+1})\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} \\
a_1 & a_2 & \cdots & a_{n}\\
\vdots && \ddots & \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2}\end{matrix}\right|+
2\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n-1} & a_{n} \\
a_1 & a_2 & \cdots & a_{n} & a_{n+1}\\
\vdots && \ddots && \vdots\\
a_{n-1} & a_{n} & \cdots & a_{2n-2} &  a_{2n-1} \\ 
a_{n+1} & a_{n+2} & \cdots & a_{2n-1} & 0\end{matrix}\right|.\]
But in the quotient by the ideal $I$ generated by $a_0, a_1, \ldots, a_{n-1}, a_{n+2}, a_{n+3},
\ldots, 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.

\end{proof}

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

\begin{lemma}\label{lem:advance} Suppose that $b$ and $b'$ are two $HTP$ sequences which
each preserve $a_0$ through $a_{2n}$, $n\geq 1$.  Also, suppose that
$b_{2n+1}+b'_{2n+1}=2a_{2n+1}$.
Then $b\circ b'$ preserves $a_0$ through $a_{2n+2}$.
\end{lemma}

\begin{proof}
Let $d=b\circ b'$.  Clearly $d$ preserves $a_0$ through $a_{2n}$.  
By Lemma \ref{lem:divisible}, there is a $c$ such that
\[b_{2n+1}=a_{2n+1}+c\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n}\\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots & & \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]
Since $b_{2n+1}+b'_{2n+1}=2a_{2n+1}$, we must have
\[b'_{2n+1}=a_{2n+1}-c\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n}\\
a_1 & a_2 & \cdots & a_{n+1}\\
\vdots & & \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]
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 \ref{lem:2n}.
\end{proof}

\begin{theorem}\label{thm:group} The set of $HTP$ sequences forms a group under composition.
\end{theorem}

\begin{proof}
It suffices to show that any $HTP$ sequence $b$ has a left inverse.
By Lemma \ref{lem:n=1}, 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}\neq a_{2n+1}$ (so $n\geq 0$, since $b_0=a_0$.)  By Lemma \ref{lem:2n},
we know that $b_{2n}=a_{2n}$.
Choose $c_n$ as in Lemma \ref{lem:divisible} (or \ref{lem:n=1}) so that
\[b_{2n+1}=a_{2n+1}-c_n
\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1} \\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]
Then by Lemma \ref{lem:advance} and Corollary \ref{cor:preserve}, the composition
$b(n,c_n)\circ b$ preserves $a_0$ through $a_{2n+2}$.

Now, we inductively define a sequence
$c_0, c_1, c_2, \ldots$ so that the composition
\[b(n,c_n)\circ b(n-1,c_{n-1})\circ \cdots\circ b(0,c_0)\circ b\]
preserves $a_0$ through $a_{2n+2}$.
Thus \[( \cdots \circ b(n,c_n)\circ b(n-1,c_{n-1})\circ \cdots\circ b(0,c_0))\circ b=\text{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\circ\sigma$ (see Example \ref{ex:sigma}).  Then, as
above, we can find a sequence $c_0, c_1, c_2, \ldots$ so that
\[ \cdots \circ b(n,c_n)\circ b(n-1,c_{n-1})\circ \cdots\circ b(0,c_0)\circ b\circ\sigma=\text{id}.\]
Composing and precomposing both sides with $\sigma$ (which satisfies $\sigma^2=\text{id}$),
we get
\[\sigma\circ( \cdots \circ b(n,c_n)\circ b(n-1,c_{n-1})\circ \cdots\circ b(0,c_0))\circ b=\text{id}.\]
\end{proof}

\begin{lemma}\label{lem:inverse}
The inverse $b(n,c)^{-1}$ of $b(n,c)$ preserves $a_0$ through $a_{2n}$ and satisfies
\[b(n,c)^{-1}_{2n+1}=a_{2n+1}-c\left|\begin{matrix}
a_0 & a_1 & \cdots & a_{n} \\
a_1 & a_2 & \cdots & a_{n+1} \\
\vdots && \ddots & \vdots\\
a_{n} & a_{n+1} & \cdots & a_{2n}\end{matrix}\right|.\]
\end{lemma}

\begin{proof}
Since $b(n,c)$ preserves $a_0$ through $a_{2n}$ by Corollary \ref{cor:preserve},
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)\circ b(n,c)\circ b(n,c)^{-1}$.  Since $b(n,-c)\circ b(n,c)$ preserves
$a_0$ through $a_{2n+2}$ by Lemma \ref{lem:advance} and Corollary \ref{cor:preserve},
it follows that $b(n,c)^{-1}$ must
have the same $2n+1$ term as $b(n,-c)$.
\end{proof}

\begin{remark}
We do not know whether or not $b(n,c)^{-1}=b(n,-c)$ in general.
\end{remark}
We now prove our main theorem.

\begin{proof}
As in Theorem \ref{thm:group}, we can inductively define $c_0, c_1, \ldots$
such that either
\[b':=b\circ b(0,c_0)^{-1}\circ b(1,c_1)^{-1}\circ\cdots\circ b(n,c_n)^{-1}\]
or
\[b':=b\circ\sigma \circ b(0,c_0)^{-1}\circ b(1,c_1)^{-1}\circ\cdots\circ b(n,c_n)^{-1}\]
preserves $a_0$ through $a_{2n+2}$.  Here, we use Lemma \ref{lem:inverse}
together with Lemma \ref{lem:advance} to complete the inductive step.
Now either $b$ or $b\circ\sigma$ can be written as
\[b'\circ b(n,c_n)\circ \cdots\circ b(1,c_1)\circ b(0,c_0).\]
It follows that
\[\cdots\circ b(n,c_n)\circ \cdots\circ b(1,c_1)\circ b(0,c_0)\]
agrees on all terms with $b$ or $b\circ\sigma$.  In the latter case, we multiply both
sides by $\sigma$.
\end{proof}


\begin{thebibliography}{4}

\bibitem{CF} M.~Chamberland and C.~French,\\
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Chamberland/chamberland12.html}{Generalized Catalan
numbers and generalized Hankel transformations}, {\it
J. Integer Seq.} {\bf 10} (2007), Article 07.1.1.

\bibitem{E} R.~Ehrenborg, The Hankel determinant of exponential
polynomials, {\it Amer. Math. Monthly,} {\bf 107} (2000), 557--560.

\bibitem{L} J.~Layman, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html}{The Hankel transform and some of its properties},
{\it J. Integer Seq.} {\bf 4} (2001), Article 01.1.5.

\bibitem{R} C.~Radoux, D\'eterminant de Hankel construit sur des polyn\^omes li\'es aux
nombres de d\'erangements.  {\it European J. Combin.} {\bf 12} (1991), 327--329.

\bibitem{SS} M.~Spivey and L.~Steil, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html}{The $k$-binomial transforms and the Hankel
transform},
{\it J. Integer Seq.} {\bf 9} (2006), Article 06.1.1.

\bibitem{W} E.~Weisstein, Binomial transform, from MathWorld -- A Wolfram Web Resource,
\href{http://mathworld.wolfram.com/BinomialTransform.html}{\tt http://mathworld.wolfram.com/BinomialTransform.html}.

\end{thebibliography}

\bigskip
\hrule
\bigskip


\noindent 2000 {\it Mathematics Subject Classification}: Primary 11B75;
Secondary 15A36, 11C20.

\noindent {\it Keywords}: Hankel transform, binomial transform.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 20 2007;
revised version received  June 20 2007.
Published in {\it Journal of Integer Sequences}, July 4 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}