# Recurrence Ranks and Moment Sequences

Joshua Cooper and Grant Fickes

###### Abstract

We introduce the “moment rank” and “unitary rank” of numerical sequences,
close relatives of linear-recursive order. We show that both parameters can be
characterized by a broad set of criteria involving moments of measures, types
of recurrence relations, Hankel matrix factorizations, Waring rank, analytic
properties of generating functions, and algebraic properties of polynomial
ideals. In the process, we solve the “complex finite-atomic” and “integral
finite-atomic” moment problems: which sequences arise as the moments of a
finite-atomic complex-/integer-valued measures on $\mathbb{C}$?

##  1 Introduction

This work is dedicated to the memory of Ron Graham, a gentle giant of the
highest scholarly caliber, a peerless and playful teacher, and an
extraordinarily generous person. His scientific contributions will live on in
innumerable ways, particularly in his endless demonstrations that theory and
application are not just complementary, but profoundly interwoven. Here we
invoke three persistent themes of his work: recurrence relations, algorithmic
thinking, and expansive TFAE statements.

We begin with a motivating problem, the original impetus for this work:
Suppose that $G$ is a finite, simple graph or hypergraph; then $G$ is
associated with a characteristic polynomial whose roots are its adjacency
eigenvalues. This polynomial, despite substantial attention in the literature
dating back to at least [6] from 1957, still holds many mysteries. One example
is the question of describing the multiplicity of zero as a root. If $f(x)$ is
the polynomial, then this multiplicity is the largest $m$ so that
$g(x)=f(x)/x^{m}$ is also a polynomial; thus, the degree of $g(x)$ (or,
actually, its reciprocal polynomial $\overline{g}(x)=x^{\deg g}g(1/x)$ in this
application) then encodes this quantity as $m=\deg f-\deg g$. Note that

$\log\overline{g}(x)-\log
g(0)=\sum_{i=1}^{r}\log(1-b_{i}x)=\sum_{i=1}^{r}\sum_{j=1}^{\infty}\frac{b_{i}^{j}x^{j}}{j}$

where $\\{b_{i}\\}_{i=1}^{\deg g}$ are the roots of $g$, whereupon the
question becomes of bounding the smallest $r$ so that $c_{j}$ can be written
as a sum of $r$ $j$-th powers, where $jc_{j}$ is the $j$-th coefficient of
$\log\overline{g}$. As will be defined below, this is exactly the “unitary
rank” of the sequence $(jc_{j})_{j\geq 1}$. See condition (6) in Theorem 2 for
this connection with log-polynomial degree.

More generally, one might ask for the simplest recurrence that a combinatorial
sequence $\mathcal{C}$ satisfies, as a kind of measure of complexity. If
$\mathcal{C}$ is “C-finite”, then it satisfies a linear recurrence with
constant coefficients, and the order of that recurrence captures this
complexity. It is natural, then, to ask how to compute this order, or even if
it is finite. Famously, for example, this is an open question for the sequence
$A_{n}$ equal to the number of permutations of $n$ with no $1324$ pattern
(i.e., $\sigma\in S_{n}$ so that there exist no $a<b<c<d$ so that
$\sigma(a)<\sigma(c)<\sigma(b)<\sigma(d)$). The theory of such sequences is
extremely well-trodden territory, and it is simplest in the case that the
characteristic polynomial – the polynomial whose coefficients are the same as
those of the recurrence – has no repeated roots. We focus on this case
presently.

Another way in which the smallest order of a linear recurrence satisfied by a
sequence appears in the literature is in the context of the venerable “moment
problem”. Here, one asks whether a sequence can arise as the sequence of
moments of various kinds of distributions: important instances include
(positive) measures on $\mathbb{R}$, $[0,\infty)$, $[0,1]$, or
$\mathbb{T}=\exp(i\mathbb{R})$ (the “Hamburger”, “Stieltjes”, “Hausdorff”, and
“Toeplitz”/“trigonometric” moment problems, respectively); signed measures on
$\mathbb{R}$ (already considered by Hausdorff [12]); or atomic measures [7,
8]. See [20] for an extensive exploration of this old and very broad topic.
Indeed, the question of when a sequence does not arise as moments of a finite-
atomic measure was recently addressed [3], a topic with a long history
connected with totally positive matrices [10, 17], strong log-
concavity/unimodality [4, 5], continued fractions and Padé approximants [21].
Here, we add to the literature on moment problems by addressing the case of
the underlying space being $\mathbb{C}$ with the two conditions that either
(1) the measures are complex-valued and finite-atomic, or (2) the (positive)
measures are finite-atomic with integer masses.

Yet another large constellation of topics closely connected with recurrence
rank is the theory of Hankel matrices [15, 24], matrices which are constant on
anti-diagonals. These matrices – and, more generally, Hankel operators – play
an important role in combinatorial sequence transforms [11, 15], numerical
methods in signal processing [5], and Riordan arrays [16]. The determinants of
Hankel matrices, known as “catalecticants”, are objects of study going back as
far as Sylvester’s work in the 1850s [23], and lives on in invariant theory
[22], polynomial positivity [1], Waring rank and binary forms [19], and the
theory of orthogonal polynomials [14].

Clearly, the subject matters connected with linear recurrence order are vast,
and there is not space here to discuss them all (and many important references
are therefore omitted, although they can be found by following threads in the
aforementioned references). Indeed, so much work has been done on related
topics over such a long period of time that it is difficult to trace their
history. This work, in addition to presenting several new results, is an
attempt to relate and unify these perspectives into one focused on the matter
of linear recurrence rank, the order of the shortest recurrence a sequence
satisfies, in the particularly interesting cases we term “moment rank” and
“unitary rank.” We attempt to keep the below exposition mostly self-contained,
which entails borrowing a variety of arguments from the literature, indicated
whenever possible.

In the next section, we introduce notation, definitions, and state some basic
results. In Section 3, we present our first main theorem, a wide-ranging TFAE
statement about moment rank, and discuss a few consequences. In Section 4, we
present our second main theorem, another TFAE statement about unitary rank,
and some consequences thereof.

##  2 Preliminaries

Suppose the sequence $\mathcal{C}=(c_{n})_{n=0}^{\infty}$ satisfies an $r$-th
order linear recurrence relation

$\sum_{n=0}^{r}a_{n}c_{n}=0$ (1)

Then, by classical results [9], the elements of $\mathcal{C}$ can be expressed
as

$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{r}$

for some $\\{\alpha_{i}\\}_{i=1}^{r}$, where $\\{\beta_{i}\\}_{i=1}^{r}$ are
the roots of the degree-$r$ polynomial
$p(x)=a_{0}\prod_{i=1}^{r}(x-\beta_{i})=\sum_{i=0}^{r-1}a_{i}x^{r}$, as long
as the $\beta_{i}$ are distinct. The $\\{\alpha_{i}\\}_{i=1}^{r}$ can be
obtained by solving the linear system

$\forall
j\in\\{0,\ldots,r-1\\},\quad\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{j+1}=c_{j}$ (2)

These observations motivate the following definition.

######  Definition 1.

The sequence $\mathcal{C}=(c_{n})_{n=0}^{N}$ (with $N=\infty$ allowed) is said
to have recurrence rank $r$ if $r$ is the smallest positive integer so that
$\mathcal{C}$ satisfies a linear recurrence of order $r$. If $N=\infty$, we
write $\operatorname{rrank}(\mathcal{C})$ for the recurrence rank.

######  Definition 2.

The sequence $\mathcal{C}=(c_{n})_{n=0}^{N}$ (with $N=\infty$ allowed) is said
to have moment rank $r$ if $r$ is the smallest positive integer so that there
exists a set of nonzero complex numbers $\\{\alpha_{i}\\}_{i=1}^{r}$ and
distinct nonzero $\\{\beta_{i}\\}_{i=1}^{r}$ so that
$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for all $0\leq n\leq N$. If
$N=\infty$, we write $\operatorname{mrank}(\mathcal{C})$ for the moment rank.

Use of this definition depends on the uniqueness of the quantity for a given
sequence. This motivates the following lemma.

######  Lemma 1.

$\operatorname{mrank}((c_{n})_{n\geq 0})$ is well-defined.

###### Proof.

Suppose, by way of contradiction, that there are two sets
$\\{\beta_{i}\\}_{i=1}^{r}$ and $\\{\beta^{\prime}_{j}\\}_{j=1}^{s}$ of
nonzero distinct complex numbers along with sets of nonzero complex numbers
$\\{\alpha_{i}\\}_{i=1}^{r}$ and $\\{\alpha^{\prime}_{j}\\}_{j=1}^{s}$ so that

$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}=\sum_{j=1}^{s}\alpha^{\prime}_{j}\beta_{j}^{\prime(n+1)}$

Write $f(z)=\sum_{n=0}^{\infty}c_{n}z^{n}$. Because $\max_{i}|\beta_{i}|$ and
$\max_{j}|\beta^{\prime}_{j}|$ are finite, the following is true around a
sufficiently small ball about $z=0$:

$\displaystyle\sum_{n=0}^{\infty}\sum_{i=1}^{r}z^{n}\alpha_{i}\beta_{i}^{n+1}$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{j=1}^{s}z^{n}\alpha^{\prime}_{j}\beta_{j}^{\prime(n+1)}$
$\displaystyle\sum_{i=1}^{r}\sum_{n=0}^{\infty}z^{n}\alpha_{i}\beta_{i}^{n+1}$
$\displaystyle=\sum_{j=1}^{s}\sum_{n=0}^{\infty}z^{n}\alpha^{\prime}_{j}\beta_{j}^{\prime(n+1)}$
$\displaystyle\sum_{i=1}^{r}\frac{\alpha_{i}\beta_{i}}{1-z\beta_{i}}$
$\displaystyle=\sum_{j=1}^{s}\frac{\alpha^{\prime}_{j}\beta^{\prime}_{j}}{1-z\beta^{\prime}_{j}}$

These two functions are equal, so they have the same set of (simple) poles;
thus, $\\{\beta_{i}\\}_{i}=\\{\beta^{\prime}_{j}\\}_{j}$ and $r=s$.
Furthermore, since the residues of these poles are proportional to the
multiplicity of the $\alpha_{i}\beta_{i}$ and
$\alpha^{\prime}_{j}\beta^{\prime}_{j}$ values, we also have that
$\\{\alpha_{i}\\}_{i=1}^{r}=\\{\alpha^{\prime}_{j}\\}_{j=1}^{s}$. ∎

The beginning of this section motivates the moment rank definition by the
satisfaction of a linear recurrence. The following definition introduces a
specific kind of linear recurrence we consider throughout the work.

######  Definition 3.

An $r$-th order linear recurrence of the form $\sum_{j=0}^{r}a_{j}c_{j+t}=0$
satisfied by the sequence $(c_{j})_{j\geq 0}$ for all $t\geq 0$ is said to be
simple if the characteristic polynomial $\sum_{j=0}^{r}a_{j}x^{j}$ has
distinct roots.

The characteristic polynomial of a recurrence provides a way to translate
between polynomials and recurrences. Given a sequence which satisfies a linear
recurrence, there are methods to define other recurrences of higher orders
which the given sequence satisfies. We consider this idea in the context of
characteristic polynomials, motivating the following definition and the lemma
that follows.

######  Definition 4.

Given a complex sequence $\mathcal{C}=(c_{n})_{n=0}^{\infty}$, let

$R_{\mathcal{C}}=\left\\{\sum_{j=0}^{r}a_{j}x^{j}:a_{j}\in\mathbb{C}\mbox{ and
}\sum_{j=0}^{r}a_{j}c_{j+t}=0\mbox{ for all }t\geq 0\right\\}$

be the set of characteristic polynomials of arbitrary finite order linear
recurrences the sequence $\mathcal{C}$ satisfies for all $t\geq 0$. We note
that the zero polynomial is a trivial element of $R_{\mathcal{C}}$.

The set above is a subset of one variable polynomials with complex
coefficients. We explore useful algebraic properties of this subset of
$\mathbb{C}[x]$.

######  Lemma 2.

Given a complex sequence $\mathcal{C}=(c_{n})_{n=0}^{\infty}$, the set
$R_{\mathcal{C}}$ is an ideal in $\mathbb{C}[x]$.

###### Proof.

We know the zero polynomial is in $R_{\mathcal{C}}$ by definition. Let
$a(x)=\sum_{i=0}^{r}a_{i}x^{i}$ and $b(x)=\sum_{j=0}^{s}b_{j}x^{j}$ be
arbitrary elements of $R_{\mathcal{C}}$. Then $\sum_{i=0}^{r}a_{i}c_{i+t}=0$
and $\sum_{j=0}^{s}b_{j}c_{j+t}=0$, giving that

$\sum_{i=0}^{r}a_{i}c_{i+t}+\sum_{j=0}^{s}b_{j}c_{j+t}=0.$

Thus, $R_{\mathcal{C}}$ is closed under addition.

Now let $\\{d_{k}\\}_{k=0}^{q}$ be complex constants so that $d(x)\in
R_{\mathcal{C}}$ where $d(x)=\sum_{k=0}^{q}d_{k}x^{k}$. Let
$p(x)=\sum_{l=0}^{m}p_{l}x^{l}$ be an arbitrary polynomial with complex
coefficients. If $d(x)$ or $p(x)$ is the zero polynomial, then $p(x)\cdot
d(x)\in R_{\mathcal{C}}$. Suppose now that $d(x)$ and $p(x)$ are not
identically zero. Since the sequence $\mathcal{C}$ satisfies a recurrence with
characteristic polynomial $d(x)$, the generating function $\Phi(x)$ of the
sequence has denominator $d(x)$. Therefore $p(x)\cdot d(x)\cdot\Phi(x)$ is a
polynomial, so $p(x)\cdot d(x)\cdot\Phi(x)$ is the characteristic polynomial
for a recurrence satisfied by $\mathcal{C}$, giving that $R_{\mathcal{C}}$ is
closed under multiplication by elements of $\mathbb{C}[x]$. ∎

Note that since $\mathbb{C}[x]$ is a principal ideal domain, $R_{\mathcal{C}}$
is generated by one complex polynomial. Moreover, we call $R_{\mathcal{C}}$
the recurrence ideal of the sequence $\mathcal{C}$.

######  Corollary 1.

Given a complex sequence $\mathcal{C}=(c_{n})_{n=0}^{\infty}$ let
$R_{\mathcal{C}}$ be generated by $p(x)$. If $p(x)$ has repeated roots, then
$\mathcal{C}$ does not satisfy a simple linear recurrence of any order. Thus,
$\mathcal{C}$ satisfying a simple linear recurrence implies that $p(x)$ has
distinct roots, i.e., if $\operatorname{mrank}(\mathcal{C})<\infty$, then
$\operatorname{rank}(\mathcal{C})=\operatorname{mrank}(\mathcal{C})$.

The algebraic structure of the recurrence ideal gives rise to useful
properties of simple linear recurrences, some of which are investigated by
Lemma 3. The properties addressed in the following two lemmas are useful in
the proof of Theorem 1.

######  Lemma 3.

Let $r$ be the smallest positive integer so that the sequence $(c_{j})_{j\geq
0}$ satisfies the simple $r$-th order linear recurrence
$\sum_{j=0}^{r}a_{j}c_{j+t}=0$. Then the following observations hold.

  1. 1.

$a_{r}\neq 0$.

  2. 2.

The roots of $p(x)=\sum_{j=0}^{r}a_{j}x^{j}$ are non-zero.

  3. 3.

The polynomial $q(x)=\sum_{j=0}^{r}a_{j}x^{r-j}$ (the “reciprocal” of the
characteristic polynomial) has $r$ distinct, nonzero roots.

###### Proof.

(1) - This follows trivially from the minimality of $r$.

(2) - Due to Corollary 1, $p(x)$ is the generator of the recurrence ideal,
$R_{\mathcal{C}}$. If $x$ is a factor of $p(x)$, that corresponds to an index
shift in the corresponding recurrence. Then $a(x)=p(x)/x$ is also the
characteristic polynomial of a linear recurrence satisfied by $\mathcal{C}$,
so $a(x)\in R_{\mathcal{C}}$, contradicting the minimality of $\deg(p)$.

(3) - Since $a_{r}\neq 0$ by (1), $q(x)$ has nonzero constant term so
$q(0)\neq 0$. Therefore, the reciprocal of $q(x)$ is well defined, with $p(x)$
the reciprocal of $q(x)$. The polynomial $p(x)$ has $r$ distinct nonzero roots
by (2) and simplicity, so the same can be said of $q$, whose roots are the
reciprocals of the roots of $p$. ∎

######  Lemma 4.

Let the sequence $\mathcal{C}=(c_{n})_{n\geq 0}$ satisfy two $r$-th order
linear recurrences, namely the minimal order recurrence
$\sum_{n=0}^{r}a_{n}c_{n+t}=0$ and another $r$-th order recurrence
$\sum_{n=0}^{r}b_{n}c_{n+t}=0$, for all $t\geq 0$. Then
$(a_{1},a_{2},\dotsc,a_{r})=\lambda(b_{1},b_{2},\dotsc,b_{r})$, where
$\lambda\neq 0$ is a scalar.

###### Proof.

Let $a(x)$ be the characteristic polynomial of the recurrence
$\sum_{n=0}^{r}a_{n}c_{n+t}=0$. Since $r$ is minimal, we have that $a(x)$
generates $R_{\mathcal{C}}$. If $b(x)$ is the characteristic polynomial of the
recurrence $\sum_{n=0}^{r}b_{n}c_{n+t}=0$, it must be that $a(x)=\lambda b(x)$
for some $\lambda\in\mathbb{C}\setminus\\{0\\}$ since $R_{\mathcal{C}}$ is
principal and $\deg(a)=\deg(b)$, from which the result follows. ∎

We have already seen that the roots of characteristic polynomials associated
with simple linear recurrences are distinct. The discriminant is a polynomial
in the coefficients of univariate complex polynomials, whose kernel is exactly
the set of polynomials with a repeated root. This kernel is the “discriminant
variety”.

######  Definition 5.

Fix the natural number $r\geq 1$. Then the (affine) $r$-discriminant variety,
denoted $\nabla_{r}$, is the closure of

$\left\\{(b_{0},\dotsc,b_{r})\in\mathbb{C}^{r+1}:f(x)=\sum_{i=0}^{r}b_{i}x^{i}\mbox{
has a repeated root}\right\\}$

It is also common to consider a Hankel matrix whose entries are given by the
elements of a sequence. Both finite and infinite dimensional square Hankel
matrices are considered throughout the paper. In [2], the authors show that
all infinite Hankel matrices have generalized Vandermonde decompositions of a
specified form, dependent on the recurrences the original sequence satisfies.
Our investigation into simple linear recurrences invites the question of which
additional matrix properties are satisfied by Hankel matrices generated by
sequences satisfying simple linear recurrences. The following lemma and
subsequent definition provide tools necessary to analyze the structure of
these matrices.

######  Lemma 5.

Let $V$ be an $r\times n$ Vandermonde matrix where the $(i,j)$ entry is
$a_{i}^{j-1}$, and let $D$ be an $r\times r$ diagonal matrix with $(i,i)$
entry $b_{i}$. Take $a_{i}$ and $b_{i}$ for $1\leq i\leq r$ to be complex
scalars. Then the matrix $V^{T}DV$ is a Hankel matrix.

###### Proof.

We simply perform the matrix multiplication, showing the form of each product
along the way. Let the matrices $D_{r\times r}$ and $V_{n\times r}$ be defined
as follows, where $\\{a_{i}\\}_{i=1}^{r}$ and $\\{b_{i}\\}_{i=1}^{r}$ are
complex scalars. Let $D_{r\times r}=\operatorname{diag}(b_{i})$ and

$V=\begin{pmatrix}1&a_{1}&a_{1}^{2}&\cdots&a_{1}^{n-1}\\\
1&a_{2}&a_{2}^{2}&\cdots&a_{2}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&a_{r}&a_{r}^{2}&\cdots&a_{r}^{n-1}\end{pmatrix}_{.}$

We see that

$V^{T}D=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\cdots&b_{r}\\\
b_{1}a_{1}&b_{2}a_{2}&b_{3}a_{3}&\cdots&b_{r}a_{r}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
b_{1}a_{1}^{n-1}&b_{2}a_{2}^{n-1}&b_{3}a_{3}^{n-1}&\cdots&b_{r}a_{r}^{n-1}\end{pmatrix}_{,}$

and furthermore that

$V^{T}DV=\begin{pmatrix}\sum_{i=1}^{r}b_{i}&\sum_{i=1}^{r}b_{i}a_{i}&\sum_{i=1}^{r}b_{i}a_{i}^{2}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{n-1}\\\
\sum_{i=1}^{r}b_{i}a_{i}&\sum_{i=1}^{r}b_{i}a_{i}^{2}&\sum_{i=1}^{r}b_{i}a_{i}^{3}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
\sum_{i=1}^{r}b_{i}a_{i}^{n-1}&\sum_{i=1}^{r}b_{i}a_{i}^{n}&\sum_{i=1}^{r}b_{i}a_{i}^{n+1}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{2n-2}\\\
\end{pmatrix}_{.}$

Then $c_{j}=\sum_{i=1}^{r}b_{i}a_{i}^{j}$ for $0\leq j\leq 2n-2$ is the
sequence which populates the Hankel matrix $V^{T}DV$. ∎

We are specifically interested in Vandermonde matrices with no zero entries,
motivating the following definition.

######  Definition 6.

Let $H_{n\times n}$, where $n$ is allowed to be $\infty$, be a complex matrix.
We say $H$ has a non-degenerate Vandermonde decomposition if there exists a
Vandermonde matrix $V_{r\times n}$ with all entries nonzero and a diagonal
matrix $D_{r\times r}$ so that $H_{\infty}=V^{T}DV$.

##  3 Moment Rank

Finally, before presenting the main theorem of this section, we describe an
algorithm which returns the moment rank of a sequence and the coefficients of
a linear combination of powers witnessing to this rank. Denote the $r\times r$
(modified) Vandermonde matrix with $(i,j)$ entry $\beta_{i}^{j}$ for
$\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{r})$ by
$\operatorname{VDM}^{\prime}(\boldsymbol{\beta})$, and the $r\times r$
(ordinary) Vandermonde matrix with $(i,j)$ entry $\beta_{i}^{j-1}$ by
$\operatorname{VDM}(\boldsymbol{\beta})$.

Algorithm $\textsc{mrank}(\mathcal{C})$: Given the sequence
$\mathcal{C}=(c_{n})_{n\geq 0}$, set $r=0$. Then

  1. 1.

$r\leftarrow r+1$

  2. 2.

Let $\mathbf{c}_{t}=(c_{t},\ldots,c_{t+r-1})$, and
$\mathbf{C}=(\mathbf{c}_{0}^{T},\ldots,\mathbf{c}_{r-1}^{T})$.

  3. 3.

If $\det(\mathbf{C})=0$, goto step 1. Else continue.

  4. 4.

Let $(a_{0},\ldots,a_{r-1})^{T}=-\mathbf{C}^{-1}\mathbf{c}_{r}^{T}$, and
define $p(x)=\sum_{n=0}^{r}a_{n}x^{n}$, where $a_{r}=1$.

  5. 5.

If $(c_{n})_{n\geq 0}$ does not satisfy the recurrence
$\sum_{i=0}^{r}a_{i}c_{i+t}=0$ for all $t\geq 0$, goto step 1. Else continue.

  6. 6.

If $p$ has repeated roots, throw ErrorNotSimple and terminate. Else continue.

  7. 7.

return $r$ and
$\boldsymbol{\alpha}=(\mathbf{c}_{0}\operatorname{VDM}^{\prime}(\boldsymbol{\beta})^{-1})^{T}$,
where $\boldsymbol{\beta}$ is the vector of roots of $p(x)$.

Note that the above is in truth only a template for an actual executable
algorithm, since some steps involve unspecified subroutines, such as
computation of the determinant in Step 3, or checking for repeated roots in
Step 6. Indeed, Step 5 involves checking whether a sequence is satisfied by a
given recurrence, a task which could range from very straightforward (e.g., if
the sequence was given as the solution to a linear recurrence) to undecidable
(e.g., if the sequence is not a computable function of its index). We
therefore make no attempt to analyze the complexity of $\textsc{mrank}(\cdot)$
and instead treat constitutive subproblems as black boxes. However, we do
assume that each step is indeed computable in the sense that there exists an
algorithm which will, in finite time, return True or False correctly.

The following is our main theorem concerning sequences of finite moment rank.
We show that all of the above contexts provide interpretations of the moment
rank. Recall that an $S$-measure on a space $(\mathcal{X},\Sigma)$, where
$\Sigma$ is a $\sigma$-algebra on $\mathcal{X}$, is a countably additive
function from $\Sigma$ to $S$, where $S$ is an additive monoid with limits
such as $[0,\infty)$ (positive measure), $\mathbb{R}$ (signed measure), or
$\mathbb{C}$ (complex measure). The $t$-th moment $m_{t}$ of an $S$-measure
$d\mu$ on $\mathcal{X}$ is the quantity $\int_{\mathcal{X}}x^{t}\,d\mu$, and
the sequence $\\{m_{t}\\}_{t=0}^{\infty}$ is its “moment sequence”. We call a
measure “$r$-atomic” if there exists an $A\subset\mathcal{X}$ with $|A|=r$ so
that $\mu(x)\neq 0$ for $x\in A$, and $\mu(B)=0$ for any
$B\subset\mathcal{X}\setminus A$ in $\Sigma$.

######  Theorem 1.

Suppose $\mathcal{C}=(c_{n})_{n=0}^{\infty}$ is a sequence in $\mathbb{C}$,
and $r\in\mathbb{N}$. Let $H_{m,t}$ denote the $(m+1)\times(m+1)$ Hankel
matrix whose entries come from the sequence $(c_{n})_{n=t}^{2m+t}$, and let
$f=\sum_{n\geq 0}c_{n}z^{n}$ denote the ordinary generating function of
$\mathcal{C}$. Then the following are equivalent.

  1. 1.

The sequence $\mathcal{C}$ has moment rank $r$.

  2. 2.

$\mathcal{C}$ satisfies a simple $r$-th order linear recurrence, and $r$ is
the smallest positive integer so that $\mathcal{C}$ has this property.

  3. 3.

The matrices $H_{m,t}$ satisfy $\det(H_{r-1,t})\neq 0$,
$\operatorname{null}(H_{r,0})=1$, $\ker(H_{r,t})=\ker(H_{r,0})$ for every
$t\geq 0$, and $\ker(H_{r,0})\not\subseteq\nabla_{r}$.

  4. 4.

There exist
$\\{\alpha_{1},\ldots,\alpha_{r}\\},\\{\beta_{1},\ldots,\beta_{r}\\},\\{\lambda_{1},\ldots,\lambda_{r}\\}\subset\mathbb{C}\setminus\\{0\\}$
so that, for each $t\geq 0$, the polynomial
$\sum_{j=0}^{2r}\binom{2r}{j}c_{j+t}x^{2r-j}y^{j}=\sum_{j=1}^{r}\lambda_{j}(\beta_{j}/\alpha_{j})^{t}(\alpha_{j}x+\beta_{j}y)^{2r}$
and $\\{\alpha_{j}/\beta_{j}\\}_{j=1}^{r}$ is a set of $r$ distinct values.

  5. 5.

The ordinary generating function $\Phi(z)=\sum_{n\geq 0}c_{n}z^{n}$ of
$\mathcal{C}$ is a rational function with exactly $r$ simple poles.

  6. 6.

The infinite Hankel matrix $H_{\infty}$ has rank $r$ and admits a non-
degenerate Vandermonde decomposition.

  7. 7.

The ideal $R_{\mathcal{C}}$ is radical, and the least degree of any nonzero
element is $r$.

  8. 8.

The sequence $\mathcal{C}$ is the moment sequence for a complex $r$-atomic
measure on $\mathbb{C}$.

  9. 9.

The algorithm $\textsc{mrank}(\mathcal{C})$ returns the parameter $r$.

###### Proof.

$2\Leftrightarrow 7$:

Suppose $7$. Let $p(x)$ be a monic generator of $R_{\mathcal{C}}$, which
exists because $\mathbb{C}[x]$ is a PID. We know that $p$ is the
characteristic polynomial for a linear recurrence of minimal order satisfied
by $\mathcal{C}$. Note that $\deg(p)=r$. Let $\\{\beta_{i}\\}_{i=1}^{s}$ be
the distinct roots of $p$, and let $m$ be the maximum multiplicity of a root
of $p$. Consider the polynomial $q(x)=\prod_{i=1}^{s}(x-\beta_{i})^{m}$.
Clearly $p$ divides $q$, giving that $q(x)\in R_{\mathcal{C}}$. Since the
ideal is radical, we have that $\sqrt[m]{q(x)}=\prod_{i=1}^{s}(x-\beta_{i})$
is an element of $R_{\mathcal{C}}$. Thus,
$\deg(\sqrt[m]{q(x)})\leq\deg(p(x))$, and $p(x)$ generating the recurrence
ideal implies $\deg(\sqrt[m]{q(x)})=\deg(p(x))$, so $p(x)$ has distinct roots.

We prove the reverse direction by contraposition. Let $p(x)$ be the generator
of $R_{\mathcal{C}}$ and suppose $R_{\mathcal{C}}=\langle p(x)\rangle$ is not
radical. Let $f(x)\in R_{\mathcal{C}}$ and $m\geq 2$ be an integer so that
$\sqrt[m]{f(x)}$ is an element of $\mathbb{C}[x]\setminus R_{\mathcal{C}}$.
Since $R_{\mathcal{C}}$ is principal, we have that $p$ divides $f$, but $p$
does not divide $\sqrt[m]{f}$. Since the distinct roots of $f$ and
$\sqrt[m]{f}$ are the same, we have that $p$ does not have distinct roots.
Since $p$ does not have distinct roots, the same can be said of every
polynomial in $R_{\mathcal{C}}$ and so $\mathcal{C}$ does not satisfy a simple
linear recurrence.

$2\Rightarrow 5\Rightarrow 4$:

We adapt an argument from [19], ultimately drawing upon Sylvester’s legendary
manuscript [23]. Suppose $(2)$, giving that for $\mathcal{C}$ we have
$\sum_{n=0}^{r}a_{n}c_{n+t}=0$ for $t\geq 0$, where $r$ is the smallest order
simple recurrence the sequence satisfies. By Lemma (3), the polynomial
$g(x)=\sum_{n=0}^{r}a_{n}x^{r-n}$ has no repeated roots, and $a_{r}\neq 0$.
Define $h(x,y)=\sum_{n=0}^{r}a_{n}x^{r-n}y^{n}$. Without loss of generality
let $a_{r}=1$. Let $\alpha_{n}$ and $\beta_{n}$ be complex numbers for $1\leq
n\leq r$ so that $h(x,y)=\prod_{n=1}^{r}(-\beta_{n}x+\alpha_{n}y)$. Note that
the $\frac{\alpha_{n}}{\beta_{n}}$ are distinct since $h(x,1)=g(x)$ has
distinct roots.

Let $\Phi(T)=\sum_{m=0}^{\infty}c_{m}T^{m}$. Then we have the following, which
converges within a positive-radius disk about zero:

$\left(\sum_{n=0}^{r}a_{r-n}T^{n}\right)\Phi(T)=\sum_{j=0}^{r-1}\sum_{k=0}^{j}a_{r-(j-k)}c_{k}T^{j}+\sum_{j=r}^{\infty}\sum_{k=0}^{r}a_{r-k}c_{j-k}T^{j}$

In the second term above, we have $j-r\geq 0$. Therefore,
$\sum_{k=0}^{r}a_{r-k}c_{j-k}=\sum_{n=0}^{r}a_{n}c_{n+(j-r)}$ and the second
term vanishes, leaving

$\left(\sum_{n=0}^{r}a_{r-n}T^{n}\right)\Phi(T)=\sum_{j=0}^{r-1}\sum_{k=0}^{j}a_{r-(j-k)}c_{k}T^{j}$

Thus, $\Phi(T)$ is a rational function with denominator
$\sum_{n=0}^{r}a_{r-n}T^{n}=\sum_{n=0}^{r}a_{n}T^{r-n}=h(T,1)=\prod_{n=1}^{r}(\alpha_{n}-\beta_{n}T)$.
Since the $\frac{\alpha_{n}}{\beta_{n}}$ are distinct, this completes the
proof of $(5)$.

Continuing from here, by partial fractions, since the
$\frac{\alpha_{n}}{\beta_{n}}$ are distinct there exist $\lambda_{n}$ for
$1\leq n\leq r$ so that (choosing numerators with foresight)

$\Phi(T)=\sum_{n=1}^{r}\frac{\lambda_{n}\alpha_{n}^{2r+1}}{\alpha_{n}-\beta_{n}T}\Rightarrow
c_{m}=\sum_{n=1}^{r}\lambda_{n}\alpha_{n}^{2r}\left(\frac{\beta_{n}}{\alpha_{n}}\right)^{m}.$

The following computation completes the proof of (4), noting that the
minimality of $r$ in this setting is due to the construction in $4\Rightarrow
2$ (see below).

$\displaystyle\sum_{j=0}^{2r}\binom{2r}{j}c_{j+t}x^{2r-j}y^{j}$
$\displaystyle=\sum_{n=1}^{r}\lambda_{n}\alpha_{n}^{2r}\left(\frac{\beta_{n}}{\alpha_{n}}\right)^{t}\sum_{j=0}^{2r}\binom{2r}{j}\left(\frac{\beta_{n}}{\alpha_{n}}\right)^{j}x^{2r-j}y^{j}$
$\displaystyle=\sum_{n=1}^{r}\lambda_{n}(\beta_{n}/\alpha_{n})^{t}(\alpha_{n}x+\beta_{n}y)^{2r}$

$4\Rightarrow 2$:

Suppose $(4)$, giving that there exist nonzero
$\\{\alpha_{1},\ldots,\alpha_{r}\\}$, $\\{\beta_{1},\ldots,\beta_{r}\\}$, and
$\\{\lambda_{1},\ldots,\lambda_{r}\\}$ so that, for each $t\geq 0$, the
polynomial
$\sum_{j=0}^{2r}\binom{2r}{j}c_{j+t}x^{2r-j}y^{j}=\sum_{j=1}^{r}\lambda_{j}(\beta_{j}/\alpha_{j})^{t}(\alpha_{j}x+\beta_{j}y)^{2r}$,
the set $\\{\alpha_{j}/\beta_{j}\\}_{j=1}^{r}$ consists of $r$ distinct
values, and $r$ is the smallest positive integer for which this property
holds. Then for $0\leq j\leq 2r$ we have

$c_{j+t}=\sum_{j=1}^{r}\lambda_{j}(\beta_{j}/\alpha_{j})^{t}(\alpha_{j}^{2r-j}\beta_{j}^{j})=\sum_{j=1}^{r}\lambda_{j}\alpha_{j}^{2r-j-t}\beta_{j}^{j+t}.$

Let $h(x,y)=\prod_{n=1}^{r}(-\beta_{n}x+\alpha_{n}y)$. Moreover, let $a_{n}$
for $0\leq n\leq r$ so that $h(x,y)=\sum_{n=0}^{r}a_{n}x^{r-n}y^{n}$. Note
that $a_{r}=\prod_{n=1}^{r}\alpha_{n}$. Since $\alpha_{n}\neq 0$ for all
$1\leq n\leq r$, we have that $a_{r}\neq 0$. Continuing, we have

$\displaystyle\sum_{n=0}^{r}a_{n}c_{n+t}$
$\displaystyle=\sum_{j=1}^{r}\sum_{n=0}^{r}a_{n}\lambda_{j}\alpha_{j}^{2r-n-t}\beta_{j}^{n+t}$
$\displaystyle=\sum_{j=1}^{r}\lambda_{j}\alpha_{j}^{r-t}\beta_{j}^{t}\sum_{n=0}^{r}a_{n}\alpha_{j}^{r-n}\beta_{j}^{n}$
$\displaystyle=\sum_{j=1}^{r}\lambda_{j}\alpha_{j}^{r-t}\beta_{j}^{t}h(\alpha_{j},\beta_{j})=0.$

Therefore, the sequence satisfies an $r$-th order linear recurrence. Notice
that the recurrence is simple since
$h(x,1)=\prod_{n=1}^{r}(-\beta_{n}x+\alpha_{n})$ has distinct, nonzero roots.
Moreover, the minimality of $r$ in this setting is due to the construction in
the preceding argument.

$5\Rightarrow 7$:

Suppose $(5)$. Let $\Phi(z)=\sum_{n=0}^{\infty}c_{n}z^{n}$. Let the $r$ simple
poles of $\Phi(z)$ be $\gamma_{n}$ for $1\leq n\leq r$ so that
$g(z)=\prod_{n=1}^{r}(z-\gamma_{n})$ is the denominator of $\Phi(z)$. It is a
well-known result [9] that the polynomial $f(z)=\sum_{i=0}^{m}a_{i}z^{i}$ is
the characteristic polynomial of a recurrence satisfied by $\mathcal{C}$ if
and only if $f(z)\Phi(z)$ is a polynomial. Thus $f(z)\in R_{\mathcal{C}}$ if
and only if $g(z)$ divides $f(z)$, giving that $g(z)$ (a polynomial of degree
$r$) is a generator for $R_{\mathcal{C}}$. The distinctness of the roots of
$g(z)$ implies $R_{\mathcal{C}}$ is radical.

$1\Leftrightarrow 2$:

Suppose (1), meaning there exists a set of nonzero complex numbers
$\\{\alpha_{i}\\}_{i=1}^{r}$ and distinct nonzero $\\{\beta_{i}\\}_{i=1}^{r}$
so that $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for all $n\geq 0$. We
multiply both sides of the equation by $z^{n}$ and take the sum over $n$ to
examine the ordinary generating functions of both sides. We have the
following.

$\Phi(z)=\sum_{n=0}^{\infty}\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}z^{n}=\sum_{i=1}^{r}\sum_{n=0}^{\infty}\alpha_{i}\beta_{i}^{n+1}z^{n}=\sum_{i=1}^{r}\frac{\alpha_{i}\beta_{i}}{1-\beta_{i}z}$

Thus, if we let $g(z)=\prod_{i=1}^{r}(1-\beta_{i}z)=\sum_{i=0}^{r}a_{i}z^{i}$
for some coefficients $a_{i}$, then
$\Phi(z)g(z)=\sum_{i=0}^{r-1}\lambda_{i}z^{i}$ is a polynomial of degree $r-1$
where $\lambda_{r-1}\neq 0$, i.e.,

$\sum_{i=0}^{r-1}\lambda_{i}z^{i}=\sum_{n=0}^{\infty}c_{n}z^{n}g(z)=\sum_{n=0}^{\infty}c_{n}z^{n}\sum_{i=0}^{r}a_{i}z^{i}=\sum_{n=r}^{\infty}z^{n}\sum_{i=0}^{r}a_{i}c_{n-i}+\sum_{n=0}^{r-1}z^{n}\sum_{i=0}^{n}a_{i}c_{n-i}.$

By matching coefficients of $z^{n}$ on each side, we see, for $n\geq r$,

$0=\sum_{i=0}^{r}a_{i}c_{n-i}.$

But, $a_{0}=1$, so

$c_{n}=-\sum_{i=1}^{r}a_{i}c_{n-i},$ (3)

i.e., if $\boldsymbol{\alpha}=(a_{r},a_{r-1},\ldots,a_{1})$, we have
$\mathbf{C}\boldsymbol{\alpha}^{T}=-\mathbf{c}_{r}^{T}$, where
$\mathbf{c}_{t}:=(c_{t},\cdots,c_{t+r-1})$ and
$\mathbf{C}=(\mathbf{c}_{0},\cdots,\mathbf{c}_{r-1})^{T}$. So
$\boldsymbol{\alpha}^{T}=-\mathbf{C}^{-1}\mathbf{c}_{r}^{T}$, and

$q(x)=\sum_{i=0}^{r}a_{i}x^{r-i}$ is the characteristic polynomial of the
recurrence (3). Since the recurrence is solved by
$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$, the roots of $p(x)$ are the
distinct nonzero values $\\{\beta_{i}\\}_{i=1}^{r}$. Moreover, since each
$\beta_{i}\neq 0$, we have that $a_{r}\neq 0$. Thus, $\mathcal{C}$ satisfies a
simple $r$-th order linear recurrence, and the minimality of $r$ in this
setting is given by the construction in the other direction of the proof
(below) together with Lemma 1.

Suppose $(2)$, giving that $\sum_{n=0}^{r}a_{n}c_{n+t}=0$ for all $t\geq 0$,
and $r$ is the smallest order recurrence the sequence satisfies. By Lemma 3,
let $\\{\beta_{i}\\}_{i=1}^{r}$ be the distinct nonzero roots of $p(x)$, the
characteristic polynomial of the recurrence. It follows from standard facts
about rational functions that $p(x)$ having distinct roots implies
$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for all $n\geq 0$ where each
$\alpha_{i}\in\mathbb{C}$. If any of the $\alpha_{i}$ are zero, the
construction in the other direction of the proof would contradict the
minimality of $r$ in this direction. Therefore all $\alpha_{i}$ are nonzero
and $\mathcal{C}$ has moment rank $r$.

$3\Leftrightarrow 2$:

Suppose $(2)$, giving that $\sum_{n=0}^{r}a_{n}c_{n+t}=0$ for all $t\geq 0$
with $a_{r}=1$, and $r$ is the smallest order recurrence the sequence
satisfies. The $r$-th order linear recurrence implies $H_{r,t}A=0$, where
$A=[a_{0},a_{1},\dotsc,a_{r}]^{T}$. Let $M$ be the $(r+1)\times(r+1)$ matrix
given by $M_{i,j}=1$ if $j=i+1$, $M_{r+1,j}=-a_{j-2}-a_{j-1}$ for $1\leq j\leq
r+1$ where we define $a_{-1}=0$, and $M_{i,j}=0$ otherwise. Then $M$ is
invertible, because $M_{r+1,1}\neq 0$, the $(r+1,1)$-minor of $M$ is $1$, and
$M(c_{t},\ldots,c_{r+t})^{T}=(c_{t+1},\ldots,c_{r+t+1})^{T}$ because $M$ acts
as a left-shift on the first $r$ coordinates, and the $r+1$-st coordinate is
given by

$\displaystyle\sum_{j=1}^{r+1}-(a_{j-1}+a_{j-2})c_{j+t-1}$
$\displaystyle=\sum_{j=1}^{r+1}-a_{j-2}c_{j+t-1}-\sum_{j=1}^{r+1}a_{j-1}c_{j+t-1}$
$\displaystyle=a_{r}c_{r+t+1}-\sum_{n=0}^{r}a_{n}c_{n+t+1}-\sum_{n=0}^{r}a_{n}c_{n+t}$
$\displaystyle=c_{r+t+1}.$

Therefore, $H_{r,t}=M^{k}H_{r,t-k}$ for any integers $t\geq\max\\{0,k\\}$, so
$\ker(H_{r,t})=\ker(H_{r,t^{\prime}})$ for every $t,t^{\prime}\geq 0$. Suppose
that there exists a non-trivial vector $B=[b_{0},b_{1},\dotsc,b_{r}]^{T}$
contained within $\ker(H_{r,t})$. Then $\sum_{n=0}^{r}b_{n}c_{n+t}=0$ for all
$t\geq 0$, and Lemma 4, gives that $B$ is a scalar multiple of $A$. Thus,
$\operatorname{null}(H_{r,t})=1$. The polynomial
$p(x)=\sum_{i=0}^{r}a_{i}x^{r}$ has no repeated roots, implying that
$\ker(H_{r,t})\not\subseteq\nabla_{r}$.

Finally, the minimality of $r$ gives that $\operatorname{null}(H_{m,t})=0$ for
all $1\leq m\leq r-1$, implying that $\det(H_{r-1,t})\neq 0$ for all $t\geq
0$.

Suppose $(3)$. There exists $A=[a_{0},a_{1},\dotsc,a_{r}]^{T}$ so that
$A\in\ker(H_{r,t})$ for all $t\geq 0$. Moreover,
$(a_{0},\dotsc,a_{r})\notin\nabla_{r}$, so the polynomial
$a(x)=\sum_{i=0}^{r}a_{i}x^{i}$ has distinct complex roots. Let the first row
of $H_{r,t}=\textbf{c}_{t}=[c_{t},\dotsc,c_{t+r}]$. Then $\textbf{c}_{t}\cdot
A=0$, giving that $0=\sum_{i=0}^{r}a_{i}c_{i+t}$ for all $t\geq 0$, and the
original sequence satisfies an $r$th order linear recurrence. The minimality
of $r$ is given by $\det(H_{r-1,t})\neq 0$ for all $t\geq 0$, completing the
proof.

$1\Leftrightarrow 6:$

Suppose (6). Let $H_{\infty}$ (with entries from the sequence $\mathcal{C}$)
have rank $r$ and admit a non-degenerate Vandermonde decomposition. Let
$\\{a_{i}\\}_{i=1}^{r}$ and $\\{b_{i}\\}_{i=1}^{r}$ be sets of complex scalars
so that $D_{r\times r}=\operatorname{diag}(b_{i})$,

$V_{r\times\infty}=\begin{pmatrix}1&a_{1}&a_{1}^{2}&\cdots&a_{1}^{n-1}&\cdots\\\
1&a_{2}&a_{2}^{2}&\cdots&a_{2}^{n-1}&\cdots\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\cdots\\\
1&a_{r}&a_{r}^{2}&\cdots&a_{r}^{n-1}&\cdots\end{pmatrix}_{,}$

and $H_{\infty}=V^{T}DV$. Since $\operatorname{rank}(H_{\infty})=r$,
$\operatorname{rank}(V)\leq r$, and $\operatorname{rank}(D)\leq r$, we have
that $\operatorname{rank}(V)=\operatorname{rank}(D)=r$ and furthermore that
$b_{i}\neq 0$ for $1\leq i\leq r$. By the computation given in Lemma 5, we see
that

$\displaystyle\begin{pmatrix}c_{0}&c_{1}&\cdots&c_{n-1}&\cdots\\\
c_{1}&c_{2}&\cdots&c_{n}&\cdots\\\ \vdots&\vdots&\ddots&\vdots&\cdots\\\
c_{n-1}&c_{n+1}&\cdots&c_{2n-2}&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots\end{pmatrix}$
$\displaystyle=H_{\infty}=V^{T}DV$
$\displaystyle=\begin{pmatrix}\sum_{i=1}^{r}b_{i}&\sum_{i=1}^{r}b_{i}a_{i}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{n-1}&\cdots\\\
\sum_{i=1}^{r}b_{i}a_{i}&\sum_{i=1}^{r}b_{i}a_{i}^{2}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{n}&\cdots\\\
\vdots&\vdots&\ddots&\vdots&\cdots\\\
\sum_{i=1}^{r}b_{i}a_{i}^{n-1}&\sum_{i=1}^{r}b_{i}a_{i}^{n}&\cdots&\sum_{i=1}^{r}b_{i}a_{i}^{2n-2}&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\ddots\end{pmatrix}_{.}$

Thus, equating the entries of the two representations of $H_{\infty}$ yields
$c_{n}=\sum_{i=1}^{r}b_{i}a_{i}^{n}$ for all $n\geq 0$. Using the
transformation $\beta_{i}=a_{i}$ and $\frac{b_{i}}{\beta_{i}}=\alpha_{i}$ for
$1\leq i\leq r$, we obtain the desired form. Note that this transformation is
well-defined since $a_{i}\neq 0$ is a consequence of the definition of a non-
degenerate Vandermonde decomposition. Moreover, all $a_{i}=\beta_{i}$ are
distinct, since $a_{i}=a_{j}$ for $i\neq j$ implies the $i$th and $j$th rows
of $V$ are equal, contradicting $\operatorname{rank}(V)=r$.

Suppose (1) by letting $\mathcal{C}$ have moment $r$. Then there exists a set
of nonzero complex numbers $\\{\alpha_{i}\\}_{i=1}^{r}$ and distinct nonzero
$\\{\beta_{i}\\}_{i=1}^{r}$ so that
$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for all $n$. We see from the
computation in Lemma 5 that $D=\operatorname{diag}(\alpha_{i}\beta_{i})$ and
the $(i,j)$ entry of $V_{r\times\infty}$ given by $\beta_{i}^{j-1}$ is a non-
degenerate Vandermonde decomposition of $H_{\infty}$.

It only remains to show that $H_{\infty}$ has rank $r$. It is immediately
clear that $\operatorname{rank}(H_{\infty})\leq r$. Moreover, Frobenius’s
inequality [13, 0.4.5(e)] implies that for the product $V^{T}DV$,

$\operatorname{rank}(V^{T}D)+\operatorname{rank}(DV)\leq\operatorname{rank}(D)+\operatorname{rank}(V^{T}DV).$

We show now that $\operatorname{rank}(V^{T}D)=r$. Suppose that
$\operatorname{rank}(V^{T}D)<r$. Then, not all columns of $V^{T}D$ are
linearly independent, and there exists
$\\{\gamma_{i}\\}_{i=1}^{r-1}\subset\mathbb{C}$ so that
$\sum_{i=1}^{r-1}\gamma_{i}C_{i}=C_{r}$, where $C_{i}$ denotes the $i$th
column of $V^{T}D$. By examining the entries within the columns of $V^{T}D$,
we see that $\sum_{i=1}^{r-1}\gamma_{i}C_{i}=C_{r}$ implies
$\sum_{i=1}^{r-1}\gamma_{i}\alpha_{i}\beta_{i}^{n+1}=\alpha_{r}\beta_{r}^{n+1}$
for all $n\geq 0$, leading to the following representation of $c_{n}$.

$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}=\sum_{i=1}^{r-1}(1+\gamma_{i})\alpha_{i}\beta_{i}^{n+1}$

This implies $\mathcal{C}$ has description complexity at most $r-1$,
contradicting Lemma 1. Therefore
$\operatorname{rank}(V^{T}D)=r=\operatorname{rank}(DV)$, and Frobenius’s
inequality produces the desired result. (It is also possible to argue this via
Sylvester’s Law of Inertia applied to the leading principal $r\times r$
submatrices of $H_{\infty}$, $V$, and $D$.)

$1\Leftrightarrow 8$:

It is clear that $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ is the
$(n+1)$-st moment of the $r$-atomic complex measure
$\mu=\sum_{i=1}^{r}\alpha_{i}\delta_{\beta_{i}}$, where $\delta_{\beta_{i}}$
denotes the standard Dirac delta function.

$1\Leftrightarrow 9$:

We argue that the algorithm returns the parameter $r$ if and only if $r$ is
the smallest positive integer so that every term of the sequence $(c_{n})$ can
be expressed as $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for a set of
nonzero complex $\alpha_{i}$ and distinct $\beta_{i}$ (since $\alpha_{i}=0$ or
$\beta_{i}=\beta_{j}$ for $i\neq j$ contradict the minimality of $r$).

Suppose the algorithm succeeds. Then $(c_{n})_{n\geq 0}$ satisfies the
recurrence $\sum_{n=0}^{r}a_{n}c_{n+t}=0$, where the $\\{a_{n}\\}$ are defined
by step 4; this is well-defined because step 3 says that $\det(\mathbf{C})\neq
0$. The characteristic polynomial of the recurrence $p(x)$ is well-defined and
factors into $r$ distinct linear factors $x-\beta_{i}$ by step 6. Thus, by
standard results in the theory of linear recurrence relations,

$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$

for some $\\{\alpha_{i}\\}_{i=1}^{r}\subset\mathbb{C}$, which are nonzero by
the minimality of $r$ (since $\textsc{mrank}(\mathcal{C})$ did not terminate
on any $r^{\prime}<r$). So, $\operatorname{mrank}(\mathcal{C})=r$.

Now, suppose that $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ with all
distinct nonzero $\beta_{i}$ and nonzero values $\alpha_{i}$. By $1\Rightarrow
3$ above, the matrix $\mathbf{C}=H_{r-1,0}$ introduced in step 2 is
invertible, so we pass step 3. Write $\Phi(z)=\sum_{n=0}^{\infty}c_{n}z^{n}$.
Because $\max_{i}|\beta_{i}|<\infty$, the following is true in a sufficiently
small ball about $z=0$:

$\displaystyle\Phi(z)$
$\displaystyle=\sum_{n=0}^{\infty}\sum_{i=1}^{r}z^{n}\alpha_{i}\beta_{i}^{n+1}$
$\displaystyle=\sum_{i=1}^{r}\frac{\alpha_{i}\beta_{i}}{1-\beta_{i}z}.$

Thus, if we let
$g(z)=\prod_{i=1}^{r}(1-\beta_{i}z)=:\sum_{i=0}^{r}a_{r-i}z^{i}$, then
$\Phi(z)g(z)$ is a polynomial of degree $r-1$, i.e.,

$\displaystyle\Phi(z)g(z)$
$\displaystyle=\sum_{n=0}^{\infty}c_{n}z^{n}g(z)=\sum_{n=0}^{\infty}c_{n}z^{n}\sum_{i=0}^{r}a_{r-i}z^{i}$
$\displaystyle=\sum_{n=r}^{\infty}z^{n}\sum_{i=0}^{r}a_{r-i}c_{n-i}+\sum_{n=0}^{r-1}z^{n}\sum_{i=0}^{n}a_{r-i}c_{n-i}$
$\displaystyle=\sum_{n=r}^{\infty}z^{n}\sum_{i=0}^{r}a_{i}c_{i+n-r}+\sum_{n=0}^{r-1}z^{n}\sum_{i=0}^{n}a_{i+r-n}c_{i}.$

By matching coefficients of $z^{n}$ on each side, we see, for $n\geq r$,
$0=\sum_{i=0}^{r}a_{i}c_{i+n-r}$, so we pass step 5. But, $a_{r}=1$, so
setting $n=r$,

$c_{r}=-\sum_{i=0}^{r-1}a_{i}c_{i},$ (4)

i.e.,

$\mathbf{C}\left[\begin{array}[]{c}a_{0}\\\ \vdots\\\ a_{r-1}\\\
\end{array}\right]=-\mathbf{c}_{r}^{T}$

so

$\left[\begin{array}[]{c}a_{0}\\\ \vdots\\\ a_{r-1}\\\
\end{array}\right]=-\mathbf{C}^{-1}\mathbf{c}_{r}^{T}$

Thus, $p(x)=\sum_{i=0}^{r}a_{i}x^{i}$ is the characteristic polynomial of the
recurrence (4). Since the recurrence is solved by
$c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$, the roots of $p(x)$ are the
distinct values $\\{\beta_{i}\\}_{i=1}^{r}$, and we pass step 6. Since Lemma 1
implies that the algorithm does not succeed for any $r^{\prime}<r$, the result
follows.

∎

In condition (4), the quantity $r$ is known as the “Waring rank” of this
polynomial. Pratt [18] presents a history and many interesting results about
this classical invariant.

Note that, when $\operatorname{mrank}{C}$ is finite,
$\textsc{mrank}(\mathcal{C})$ returns $r$ (the order of the recurrence
satisfied by $\mathcal{C}$) and a vector
$\boldsymbol{\alpha}=(\mathbf{c}_{0}\operatorname{VDM}(\boldsymbol{\beta})^{-1})^{T}$.
Since $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for some nonzero values
$\\{\alpha_{i}\\}_{i=1}^{r}$, we may write

$\operatorname{VDM}(\boldsymbol{\beta})^{T}\left[\begin{array}[]{c}\alpha_{1}\\\
\alpha_{2}\\\ \vdots\\\ \alpha_{r}\\\
\end{array}\right]=\left[\begin{array}[]{cccc}\beta_{1}&\beta_{2}&\cdots&\beta_{r}\\\
\beta_{1}^{2}&\beta_{2}^{2}&\cdots&\beta_{r}^{2}\\\
\vdots&\vdots&\ddots&\vdots\\\
\beta_{1}^{r}&\beta_{2}^{r}&\cdots&\beta_{r}^{r}\\\
\end{array}\right]\left[\begin{array}[]{c}\alpha_{1}\\\ \alpha_{2}\\\
\vdots\\\ \alpha_{r}\\\ \end{array}\right]=\left[\begin{array}[]{c}c_{0}\\\
c_{1}\\\ \vdots\\\ c_{r-1}\\\ \end{array}\right]=\mathbf{c}_{0}^{T}.$

Since the $\\{\beta_{i}\\}$ are distinct when $r$ is minimal,
$\operatorname{VDM}(\boldsymbol{\beta})$ is invertible, so the vector of
$\alpha_{i}$ values equals
$(\operatorname{VDM}(\boldsymbol{\beta})^{-1})^{T}\mathbf{c_{0}}$, i.e.,
$\boldsymbol{\alpha}=(\alpha_{1},\ldots,\alpha_{r})$.

######  Corollary 2.

For a sequence $\mathcal{C}=(c_{n})_{n=0}^{\infty}$ satisfying a simple $r$-th
order linear recurrence for $r$ minimal,

$\operatorname{null}H_{m,t}=\max\\{0,m-r+1\\}$

###### Proof.

The rank of $H_{m,t}$ is equal to the order $r$ of the smallest linear
recurrence satisfied by $\mathcal{C}$ for $m\geq r$ and is $m+1$ for $m<r$,
since $H_{r,t}$ is invertible. Therefore,
$\operatorname{null}(H_{m,t})=\max\\{0,m-r+1\\}$ ∎

##  4 Unitary Rank

Given a sequence $\mathcal{C}=(c_{n})_{n\geq 0}$ with moment rank $r$, we know
that $c_{n}=\sum_{i=1}^{r}\alpha_{i}\beta_{i}^{n+1}$ for nonzero
$\\{\alpha_{i}\\}$ and nonzero, distinct $\\{\beta_{i}\\}$. It will be useful
for some applications to isolate and consider the case when $\alpha_{i}=1$ for
all $i$, meaning $c_{n}=\sum_{i=1}^{r}\beta_{i}^{n+1}$ for $n\geq 0$. We
proceed with the following definition (changing the sequence index for ease of
use later).

######  Definition 7.

The sequence $\mathcal{C}=(c_{n})_{n=1}^{N}$ (with $N=\infty$ allowed) is said
to have unitary rank $r$ if $r$ is the smallest positive integer so that there
exists a multiset of nonzero complex values $\\{\beta_{i}\\}_{i=1}^{r}$ so
that $c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}$ for all $1\leq n\leq N$. If
$N=\infty$, we write $\operatorname{urank}((c_{n})_{n\geq 1})$ for the unitary
rank.

######  Lemma 6.

$\operatorname{urank}((c_{n})_{n\geq 1})$ is well-defined.

###### Proof.

Suppose, by way of contradiction, that there are two distinct multi-sets
$\\{\beta_{i}\\}_{i=1}^{r}$ and $\\{\gamma_{j}\\}_{j=1}^{s}$ of nonzero
complex numbers so that

$c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}=\sum_{j=1}^{s}\gamma_{j}^{n}$

Write $f(z)=\sum_{n=1}^{\infty}c_{n}z^{n}$. Because $\max_{i}|\beta_{i}|$ and
$\max_{j}|\gamma_{j}|$ are finite, the following is true around a sufficiently
small ball about $z=0$:

$\displaystyle\sum_{n=1}^{\infty}\sum_{i=1}^{r}z^{n}\beta_{i}^{n}$
$\displaystyle=\sum_{n=1}^{\infty}\sum_{j=1}^{s}z^{n}\gamma_{j}^{n}$
$\displaystyle\sum_{i=1}^{r}\frac{z\beta_{i}}{1-z\beta_{i}}$
$\displaystyle=\sum_{j=1}^{s}\frac{z\gamma_{j}}{1-z\gamma_{j}}$

These two functions are equal, so they have the same set of poles; thus, as
sets, $\\{\gamma_{i}\\}_{i}=\\{\beta_{i}\\}_{i}$. Furthermore, since the
residues of these poles are proportional to the multiplicity of the
$\gamma_{i}$ and $\beta_{i}$ values, they also occur the same number of times.
Thus, as multisets as well, $\\{\gamma_{i}\\}_{i}=\\{\beta_{i}\\}_{i}$.

∎

######  Theorem 2.

Let $\mathcal{C}=(c_{n})_{n=1}^{\infty}$ be a sequence and $r$ a positive
integer. Let $H_{r-1,t}$ denote the $r\times r$ Hankel matrix whose entries
come from the sequence $(c_{n})_{n=t}^{2r-2+t}$. Lastly, let
$\Phi(z)=\sum_{n\geq 1}c_{n}z^{n}$ denote the ordinary generating function of
the sequence $\mathcal{C}$. Then the following are equivalent.

  1. 1.

The sequence $\mathcal{C}$ has unitary rank $r$.

  2. 2.

The algorithm $\textsc{mrank}(T[\mathcal{C}])$ succeeds on the sequence
$T[\mathcal{C}]=(c_{n+1})_{n\geq 0}$ and returns $r^{\prime}$ and
$\boldsymbol{\alpha}\in\mathbb{N}^{r^{\prime}}$ so that
$\boldsymbol{\alpha}\cdot\mathbf{1}=r$, where $\mathbf{1}$ is the all-ones
vector of dimension $r^{\prime}$.

  3. 3.

$\mathcal{C}$ satisfies an $r^{\prime}$-th order simple linear recurrence for
some $r^{\prime}\leq r$ with coefficients
$\\{\alpha_{i}\\}_{i=1}^{r^{\prime}}$, $\alpha_{i}\in\mathbb{N}$ for all
$1\leq i\leq r^{\prime}$, and $\sum_{i=1}^{r^{\prime}}\alpha_{i}=r$.

  4. 4.

Let $\mathcal{C}^{\prime}=(c^{\prime}_{n})_{n\geq 0}$ be a sequence so that
$c^{\prime}_{0}=r$ and $c^{\prime}_{n}=c_{n}$ for $n\geq 1$. If
$H^{\prime}_{r-1,t}$ is the $r\times r$ Hankel matrix whose first row consists
of $c^{\prime}_{t},\ldots,c^{\prime}_{t+r-1}$, then there exists an $r\times
r$ Vandermonde matrix $V=\operatorname{VDM}(\boldsymbol{\beta})$ so that
$H^{\prime}_{r-1,t}=V^{T}D^{t}V$ where
$D=\operatorname{diag}(\boldsymbol{\beta})$, for each $t\geq 0$.

  5. 5.

Let $\mathcal{C}^{\prime}=(c^{\prime}_{n})_{n\geq 0}$ be a sequence so that
$c^{\prime}_{0}=r$ and $c^{\prime}_{n}=c_{n}$ for $n\geq 1$. If
$H_{\infty}^{\prime}$ is the infinite Hankel matrix with entries from
$\mathcal{C}^{\prime}$, then there exists a Vandermonde matrix
$V_{r,\infty}^{\prime}$ so that
$H_{\infty}^{\prime}=(V^{\prime})^{T}V^{\prime}$.

  6. 6.

$\exp(\int-x^{-1}\Phi(x)\,dx)$ is a polynomial of degree $r$ with nonzero
roots.

  7. 7.

There exist nonzero $r^{\prime}\in\mathbb{N}$ and
$\\{\alpha_{1},\ldots,\alpha_{r^{\prime}}\\}$,
$\\{\beta_{1},\ldots,\beta_{r^{\prime}}\\}$, and
$\\{\lambda_{1},\ldots,\lambda_{r^{\prime}}\\}$ so that, for each $t\geq 0$,
the polynomial
$\sum_{j=0}^{2r^{\prime}}\binom{2r^{\prime}}{j}c_{j+t}x^{2r^{\prime}-j}y^{j}=\sum_{j=1}^{r^{\prime}}\lambda_{j}(\beta_{j}/\alpha_{j})^{t}(\alpha_{j}x+\beta_{j}y)^{2r^{\prime}}$,
and the $\\{\alpha_{j}\\}_{j=1}^{r^{\prime}}$ are positive naturals that sum
to $r$.

  8. 8.

The sequence $\mathcal{C}$ is the moment sequence for a complex finite-atomic
measure on $\mathbb{C}$ where the masses of the atoms are positive naturals
with sum $r$.

###### Proof.

$1\Leftrightarrow 3$:

This is clear from the definitions of $\operatorname{urank}$ and
$\operatorname{mrank}$, taking into account the shift in index.

$1\Leftrightarrow 2$:

The sequence $\mathcal{C}$ having unitary rank $r$ implies there exists
$r^{\prime}\leq r$ so that $\operatorname{mrank}(T[\mathcal{C}])=r^{\prime}$,
since we may take the same $\beta_{i}$ with $\alpha_{i}$ equal to the
multiplicity of $\beta_{i}$ in the representation
$c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}$. Thus, the algorithm applied to
$T[\mathcal{C}]$ with Hankel matrix of size $r^{\prime}$ succeeds and returns
$r^{\prime}$ and
$\boldsymbol{\alpha}=(\mathbf{c}_{0}\operatorname{VDM}(\boldsymbol{\beta})^{-1})^{T}$,
which, by the note following the proof of Theorem 1, is the vector of
coefficients $\alpha_{i}$ in the representation
$c_{n}=\sum_{i=1}^{r^{\prime}}\alpha_{i}\beta_{i}^{n}$. (Note that the
exponent of $\beta_{i}$ is $n$ instead of $n+1$ because $T[\mathcal{C}]$ is
the input to mrank here.) But then, the sum
$\sum_{i=1}^{r^{\prime}}\alpha_{i}$ over the values generated by the algorithm
is $r$, since this is the number of terms in the representation
$c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}$.

To establish the converse direction, suppose the algorithm returns
$r^{\prime}$ and $\boldsymbol{\alpha}\in\mathbb{N}^{r^{\prime}}$ with
$\boldsymbol{\alpha}\cdot\mathbf{1}=r$. Note that none of the $\alpha_{i}$ are
zero, since then mrank would have terminated on a smaller value of
$r^{\prime}$. Thus, the $\alpha_{i}$ are positive integers summing to $r$, so
we may write

$c_{n+1}=\sum_{j=1}^{r^{\prime}}\sum_{i=1}^{\alpha_{i}}\beta_{j}^{n+1},$

i.e., $c_{n}=\sum_{j=1}^{r}{\beta^{\prime}_{j}}^{n}$ if
$\\{\beta_{j}\\}_{j=1}^{r^{\prime}}=\\{\beta^{\prime}_{j}\\}_{j=1}^{r}$ with
$\beta_{j}$ appearing with multiplicity $\alpha_{j}$ on the right-hand side.

$3\Leftrightarrow 8$:

This is a direct consequence of Theorem 1.

$1\Leftrightarrow 5$:

Suppose condition $(1)$ holds and let $\\{\beta_{i}\\}_{i=1}^{r}$ be given to
satisfy the definition of unitary rank for the sequence $\mathcal{C}$. To
adopt the notation of Lemma 5, letting $b_{i}=1$ and $a_{i}=\beta_{i}$ for
$1\leq i\leq r$ proves $(5)$.

Now, suppose $(5)$ holds. Letting $b_{i}=1$ for each $1\leq i\leq r$ in the
form of $V^{T}DV$ given in Lemma 5, we have that the $(i,j)$ entry of
$H_{\infty}^{\prime}$ is $\sum_{i=1}^{r}a_{i}^{i+j-2}$. Clearly then, we have
that $c_{n}^{\prime}=\sum_{i=1}^{r}a_{i}^{n}$, further implying that
$c_{n}=\sum_{i=1}^{r}a_{i}^{n+1}$. The uniqueness of unitary rank given by
Lemma 6 completes the proof.

$1\Leftrightarrow 6$:

Suppose $(1)$ holds. Let $c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}$. Since
$f(x)=\sum_{n\geq 1}c_{n}x^{n}$, we have that
$\int-x^{-1}f(x)\,dx=-\sum_{n\geq 1}\frac{c_{n}x^{n}}{n}+C$. We have the
following computation.

$\displaystyle\exp\left(-\sum_{n\geq 1}\frac{c_{n}x^{n}}{n}\right)$
$\displaystyle=\exp\left(-\sum_{n\geq
1}\sum_{i=1}^{r}\frac{\beta_{i}^{n}x^{n}}{n}\right)$
$\displaystyle=\exp\left(-\sum_{i=1}^{r}\sum_{n\geq
1}\frac{(\beta_{i}x)^{n}}{n}\right)$
$\displaystyle=\prod_{i=1}^{r}\exp\left(-\sum_{n\geq
1}\frac{(\beta_{i}x)^{n}}{n}\right)$
$\displaystyle=\prod_{i=1}^{r}\exp\left(\log[1-\beta_{i}x]\right)$
$\displaystyle=\prod_{i=1}^{r}(1-\beta_{i}x)$

Therefore, we see that $\int-x^{-1}f(x)\,dx$ is the log of a polynomial of
degree $r$, as desired.

Suppose $(6)$ holds. Since it is only possible to take the log of a polynomial
if the polynomial has nonzero constant term, we have that there exists nonzero
$\\{\beta_{i}\\}_{i=1}^{r}$ so that $\exp(-\int
x^{-1}f(x)\,dx)=\prod_{i=1}^{r}(1-\beta_{i}x)$. By letting
$c_{n}=\sum_{i=1}^{r}\beta_{i}$ and working backwards through the computation
given in the first direction of the proof shows

$\exp\left(-\int x^{-1}f(x)\,dx\right)=e^{C}\exp\left(-\sum_{n\geq
1}\frac{c_{n}x^{n}}{n}\right)$

Taking log of both sides and differentiating gives that $f(x)=\sum_{n\geq
1}c_{n}x^{n}$, showing that $f(x)$ is the generating function for a sequence
with unitary rank $r$, completing the proof.

$1\Leftrightarrow 7$:

Suppose $(1)$ holds. Having already proved $1\Leftrightarrow 3$, we appeal to
$(3)$ and Theorem 1, to give that (despite the shift in index, which is taken
care of by the variable $t$) there exist nonzero
$\\{\alpha_{1},\ldots,\alpha_{r^{\prime}}\\}$,
$\\{\beta_{1},\ldots,\beta_{r^{\prime}}\\}$, and
$\\{\lambda_{1},\ldots,\lambda_{r^{\prime}}\\}$ so that, for each $t\geq 0$,
the polynomial
$\sum_{j=0}^{2r^{\prime}}\binom{2r^{\prime}}{j}c_{j+t}x^{2r^{\prime}-j}y^{j}=\sum_{j=1}^{r^{\prime}}\lambda_{j}(\beta_{j}/\alpha_{j})^{t}(\alpha_{j}x+\beta_{j}y)^{2r^{\prime}}$.
The fact that $\sum_{i=1}^{r^{\prime}}\alpha_{i}=r$ is given by the assumption
of condition $(1)$.

Now suppose $(7)$ is true. By Theorem 1, we have that
$\operatorname{mrank}(\mathcal{C})=r^{\prime}$. The assumption in $(7)$ that
$\\{\alpha_{i}\\}_{i=1}^{r^{\prime}}$ is a set of positive naturals summing to
$r$ gives that $\operatorname{urank}(\mathcal{C})=r$.

$1\Leftrightarrow 4$:

Suppose $(4)$. By the computation given in Lemma 5, it is clear that the
$(i,j)$ entry of $V^{T}D^{t}V$ is given by
$\sum_{i=1}^{r}\beta_{i}^{t+i+j-2}$. By letting
$c_{n}=\sum_{i=1}^{r}\beta_{i}^{n}$, we have that
$\mathcal{C}=(c_{n})_{n=1}^{\infty}$ has unitary rank at most $r$. We note
that Lemma 6 completes the proof that $\operatorname{urank}(\mathcal{C})=r$.

Now, suppose $(1)$. By the computation given in Lemma 5, we see that letting
the $i$th row of $V$ be generated by $\beta_{i}$ and defining
$D=\operatorname{diag}(\beta_{i})$, the result follows immediately.

∎

Suppose $A$ is an infinite positive-semidefinite matrix (aka positive-type
kernel for $\ell^{2}$); then $A$ can be written as $A=M^{\ast}M$, which we
will refer to as a “Gramian representation” (since $M^{\ast}M$ is a Gramian
matrix in the finite-dimensional case). In general, this representation is
unique up to unitary conjugation.

######  Corollary 3.

The property that a real sequence $\mathcal{C}$ is the moment sequence of a
finite-atomic measure on $\mathbb{C}$ with integer masses is equivalent to
$H^{\prime}_{\infty}$ being positive semi-definite of finite rank with a
Vandermonde Gramian representation.

###### Proof.

By Theorem 3, $H^{\prime}_{\infty}$ has a factorization as $V^{T}V$ for some
Vandermonde kernel $V$. Note that, if $H^{\prime}_{\infty}=M^{\ast}M$ for some
$M$, then $H^{\prime}_{\infty}$ is Hermitian and symmetric, which implies that
$\mathcal{C}$ is real. Thus, $V^{T}=V^{\ast}$. ∎

## References

  * [1] Grigoriy Blekherman.  Nonnegative polynomials and sums of squares.  In Semidefinite optimization and convex algebraic geometry, volume 13 of MOS-SIAM Ser. Optim., pages 159–202. SIAM, Philadelphia, PA, 2013.
  * [2] Daniel L. Boley, Franklin T. Luk, and David Vandevoorde.  Vandermonde factorization of a Hankel matrix.  In Scientific computing (Hong Kong, 1997), pages 27–39. Springer, Singapore, 1997.
  * [3] Alin Bostan, Andrew Elvey-Price, Anthony Guttmann, and Jean-Marie Maillard.  Stieltjes moment sequences for pattern-avoiding permutations.  The Electronic Journal of Combinatorics, to appear.
  * [4] Francesco Brenti.  Unimodal, log-concave and Pólya frequency sequences in combinatorics.  Mem. Amer. Math. Soc., 81(413):viii+106, 1989.
  * [5] Moody T. Chu and Matthew M. Lin.  On the finite rank and finite-dimensional representation of bounded semi-infinite Hankel operators.  IMA J. Numer. Anal., 35(3):1256–1276, 2015.
  * [6] Lothar Collatz and Ulrich Sinogowitz.  Spektren endlicher Grafen.  Abh. Math. Sem. Univ. Hamburg, 21:63–77, 1957.
  * [7] Raúl E. Curto, Lawrence A. Fialkow, and H. Michael Möller.  The extremal truncated moment problem.  Integral Equations and Operator Theory, 60:177–200, 2 2008.
  * [8] Philipp J. di Dio and Konrad Schmüdgen.  The multidimensional truncated moment problem: atoms, determinacy, and core variety.  J. Funct. Anal., 274(11):3124–3148, 2018.
  * [9] Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward.  Recurrence sequences, volume 104 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2003.
  * [10] Sergey Fomin and Andrei Zelevinsky.  Total positivity: Tests and parametrizations.  The Mathematical Intelligencer, 22:23–33, 2000.
  * [11] Christopher French.  Transformations preserving the Hankel transform.  J. Integer Seq., 10(7):Article 07.7.3, 14, 2007.
  * [12] Felix Hausdorff.  Momentprobleme für ein endliches Intervall.  Math. Z., 16(1):220–248, 1923.
  * [13] Roger A. Horn and Charles R. Johnson.  Matrix analysis.  Cambridge University Press, Cambridge, second edition, 2013.
  * [14] Alexandre Junod.  Hankel determinants and orthogonal polynomials.  Expo. Math., 21(1):63–74, 2003.
  * [15] John W. Layman.  The Hankel transform and some of its properties.  J. Integer Seq., 4(1):Article 01.1.5, 11, 2001.
  * [16] Paul Peart and Wen-Jin Woan.  Generating functions via Hankel and Stieltjes matrices.  J. Integer Seq., 3(2):Article 00.2.1, 1 HTML document, 2000.
  * [17] Allan Pinkus.  Totally Positive Matrices.  Cambridge University Press, 2010.
  * [18] Kevin Pratt.  Waring rank, parameterized and exact algorithms.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 806–823, Los Alamitos, CA, USA, nov 2019. IEEE Computer Society.
  * [19] Bruce Reznick.  On the length of binary forms.  In Quadratic and higher degree forms, volume 31 of Dev. Math., pages 207–232. Springer, New York, 2013.
  * [20] Konrad Schmüdgen.  The Moment Problem.  Springer, 2017.
  * [21] J. Shohat and J. Tamarkin.  The Problem of Moments, volume 1.  American Mathematical Society, 12 1943.
  * [22] Bernd Sturmfels.  Algorithms in invariant theory.  Texts and Monographs in Symbolic Computation. Springer, second edition, 2008.
  * [23] J.J. Sylvester.  LX. On a remarkable discovery in the theory of canonical forms and of hyperdeterminants.  The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(12):391–410, 1851.
  * [24] Harold Widom.  Hankel matrices.  Transactions of the American Mathematical Society, 121:1–35, 1 1966\.