Formal power series is Taylor expansion of rational function iff Hankel determinants vanish?

Question

Let $$ u(T)=\sum_{n = 0}^\infty a_nT^n$$ be a formal power series over a field $K$. Then why does $u(T)$ lie in $K(T)$ (i.e. is the Taylor expansion of a rational function) if and only if there is an $N > 0$ such that the Hankel determinants $$\det(a_{i + j + M}){_{0 \le i, j \le N}} = \det \begin{pmatrix} a_M & a_{M + 1} & \ldots a_{M + N} \\ a_{M + 1} & a_{M + 2} & & \\ \vdots & & & \\ a_{M + N} & \ldots & & a_{M + 2N} \end{pmatrix}$$vanish for all $M\gg0$?

Answer 1

Call your displayed matrix $H_{M,N}$.

Theorem The following are equivalent:

1. $u$ is the Taylor series of a rational function.

2. There is a finite sequence $q_0,\ldots, q_N$, not all zero, such that for all $m\gg0$, $a_mq_N+a_{m+1}q_{N-1}+\cdots+a_{m+N}q_0=0$.

3. There exists $N$ and $M$ such that $|H_{m,N}|=0$ for all $m>M$.

4. There exists $M$ and $N$ such that $|H_{m,n}|=0$ for all $m>M$ and $n>N$.

Proof that 1) is equivalent to 2):

$u$ is rational iff there is a polynomial $q$ with $qu$ a polynomial. Taking the $q_i$ to be the coefficients of $q$, we are done.

Proof that 2) implies 3): Suppose $a_mq_N+\cdots+a_{m+N}q_0=0$ for all $ m>M$. Then for all $m>M$, $H_{m,N}$ kills the column vector $\pmatrix{q_0&q_1&\ldots&q_N}^T$, so $|H_{m,N}|=0$.

Proof that 2) implies 4): Exactly as above, noting that $$H_{m,N+p}\cdot\pmatrix{q_0\cr\vdots\cr q_N\cr 0\cr \vdots\cr 0}=0$$

Proof that 4) implies 3): Trivial.

Proof that 3) implies 2):

Let $N$ be the smallest number with the property that there exists $M$ with $|H_{m,N}|=0$ for all $m>M$. If $M=1$, then $u$ is a polynomial and we are done. Otherwise there are arbitrarily large values of $m$ with $|H_{m,N-1}|\neq 0$.

Claim: $|H_{m,N-1}|\neq 0$ for any $m>M$. Proof of claim: Let $m>M$. It is pretty easy to check that $$|H_{m,N-1}||H_{m+2,N-1}|=|H_{m+1,N-1}|^2+|H_{m,N}||H_{m+2,N-2}|$$ (I'll come back and insert a proof of this displayed equation when I have a little more time.) By assumption, $|H_{m,N}|=0$, so $|H_{m,N-1}|=0$ would imply $|H_{m+1,N-1}|=0$, whence by induction $|H_{m+p,N-1}|>0$ for all $p>0$, contradicting the last line of the preceding paragraph. This proves the claim.

Continue to assume $m>M$.

Note that $H_{m,N}$ is an $(N+1)\times (N+1)$ matrix of determinant zero that contains a nonsingular $N\times N$ submatrix (namely $H_{m,N-1}$) and hence has rank precisely $N$. Thus there is a unique (up to linear multiples) column vector $\overline{q}$ such that $$H_{m,N}\overline{q}=0$$

Then $\overline{q}$ is the unique (again up to scalar multiples) column vector killed by the top $n$ rows of $H_{m,N}$ and also the unique column vector killed by the bottom $n$ rows. Now since $H_{m+1,N}$ is also rank 1, and because its kernel must be killed by the bottom $n$ rows of $H_{m,N}$,it follows that the kernel is again generated by the same vector $\overline{q}$, and by induction $\overline{q}$ is killed by $H_{m+p,N}$ for all $p\ge 0$, so that in particular $a_{m+p}b_0+\cdots+a_{m+p+N}b_N=0$ for all $p>0$, which, modulo a change of notation, is 2).

Edited to add:

The displayed equation above is a special case of the following:

Theorem: Let $a,b,c,d$ be scalars. Let $\alpha,\beta$ be row vectors of length $n$. Let $\phi,\psi$ be columns of length $n$. Let $B$ be an $n\times n$ matrix. Let $A$ be the following $(n+2)\times(n+2)$ matrix: $$A=\pmatrix{a&\alpha&b\cr\phi&B&\psi\cr c&\beta&d\cr}$$ Then $$\det\pmatrix{a&\alpha\cr\phi& B\cr}\cdot \det\pmatrix{B&\psi\cr \beta &d\cr} =\det\pmatrix{\alpha&b\cr B&\psi\cr} \det\pmatrix{\phi&B\cr c&\beta\cr}+\det(A)\cdot\det(B).$$

Proof: We can assume $B$ is invertible and then premultiply $A$ by $$\pmatrix{1&0&0\cr 0&B^{-1}&0\cr 0&0&1\cr}$$ where the zeroes represent scalars, rows or columns as appropriate. This does not affect the truth of the theorem and allows us to assume $B$ is the identity, after which row and column operations render the desired equality trivial.

Answer 2

I assume this question is motivated by your earlier query on Dwork's Theorem since this is the "rational function criterion" wielded towards the end of the proof of the rationality of the zeta function. In the answer I posted there, see Chapter 5 in my linked undergrad thesis for an explanation of this proof (pdf pp. 48-50) that follows Koblitz's presentation.

Or, to avoid link-chasing, here is the relevant excerpt:

Answer 3

This is Lemma III, attributed to Kronecker, on page 5 of Salem, Algebraic Numbers and Fourier Analysis. The book has been posted to the web by Plouffe, at http://plouffe.fr/simon/math/Algebraic%20Numbers%20and%20Fourier%20Analysis.pdf

Answer 4

I am not going to add anything new, just what is my take on it. The proof consists of four really simple steps.

Step I. Determinant is zero iff there exist numbers $b_0,\dots,b_N$, not all of them zero, such that $$\sum_{i=0}^N a_{M+i+j}b_i=0$$ for all $0\le j\le N$. (Proof: Basically, the definition of determinant.)

Step II. Determinant is zero iff there exists a nonzero polynomial $B(T)=b_0T^N+\dots+b_N$ such that in the series $$B(T)u(T)=\sum_{n=0}^\infty c_n T^n$$ we have $$c_{M+N}=c_{M+N+1}=\dots=c_{M+2N}=0.$$ (Proof: Multiplication of series.)

Step III. The series $u(T)$ is rational iff there exists $N>0$ and a nonzero polynomial $B(T)=b_0T^N+\dots+b_N$ such that in the series $$B(T)u(T)=\sum_{n=0}^\infty c_n T^n$$ we have $$c_{M+N}=c_{M+N+1}=\dots=c_{M+2N}=0$$ for $M\gg 0$. (Proof: just the definitions!)

Step IV. The series $u(T)$ is rational iff there exists $N>0$ such that the determinant is zero for $M\gg 0$.

Now, I cheated in the step IV: even if the determinant is zero, the polynomial $B(T)$ may actually depend on $M$, which is wrong! Actually, this is the hard part. The standard way to fix this is to chose the smallest possible $N$, as it is done in Koblitz.