# Frames of iterations and vector-valued model spaces

Carlos Cabrelli, Ursula Molter and Daniel Suárez

> Abstract
> 00footnotetext:  2020 Mathematics Subject Classification: 42C15, 47A56,
> 47B35. Key phrases: frame of orbits, model space, Toeplitz and
> multiplication operators, invariant subspacess.
> Let $T$ be a bounded operator on a Hilbert space $\mathcal{H}$, and
> $\mathcal{F}=\\{f_{j},j\in J\\}$ an at most countable set of vectors in
> $\mathcal{H}$. In this note we characterize the pairs $(T,\mathcal{F})$ such
> that $\\{T^{n}f:f\in\mathcal{F},n\in I\\}$ form a frame of $\mathcal{H}$,
> for the cases of $I=\mathbb{N}\cup\\{0\\}$ and $I=\mathbb{Z}$. The
> characterization for unilateral iterations gives a similarity with the
> compression of the shift acting on model spaces of the Hardy space of
> analytic functions defined on the unit disk with values in $\ell^{2}(J)$.
> This generalizes recent work for iterations of a single function. In the
> case of bilateral iterations the characterization is by the bilateral shift
> acting on doubly invariant subspaces of $L^{2}(T,\ell^{2}(J))$.
>
> Furthermore, we characterize the frames of iterations for vector-valued
> model operators when $J$ is finite in terms of Toeplitz and multiplication
> operators in the unilateral and bilateral case, respectively. Finally we
> study the problem of finding the minimal number of orbits that produce a
> frame in this context.

##  1 Introduction

Let $\mathcal{H}$ be a separable Hilbert space, $T\in\mathcal{L}(\mathcal{H})$
a bounded linear operator on $\mathcal{H}$ and $\\{x_{j}:\,j\in
J\\}\subset\mathcal{H}$ be a subset of $\mathcal{H}$, where the set of indexes
$J$ is countable (finite or countably infinite). A natural problem originated
in dynamical sampling asks for a characterization of the operators and the
vectors such that the orbits

$\mathcal{F}=\\{T^{n}x_{j}:\ n\in\mathbb{N}_{0},\ j\in J\\}$

is a frame, or even a Bessel sequence for $\mathcal{H}$, where
$\mathbb{N}_{0}$ denotes the set of nonnegative integers.

When $T$ is a normal operator and $\sharp J=1$ (the cardinal of $J$) the
problem was solved in two papers [2] and [1], where the authors showed that
$T$ is necessarily diagonalizable, the diagonal is an interpolating sequence
for the Hardy space of the unit disk $H^{2}(\mathbb{D})$ (including finite
interpolation if $\dim\mathcal{H}$ is finite), and the vector $x$ must satisfy
some bound constraints depending on the eigenvalues of $T$.

In [5] the same problem is studied for an arbitrary finite set $J$. In this
case the normal operator $T$ also must be diagonalizable, where the diagonal
is a union of at most $\sharp J$ interpolating sequences. A refinement of this
characterization was obtained in [6], where the authors show that hyperbolic
geometry appears naturally in the interplay between the vectors $x_{j}\ (j\in
J)$ and the sequence of eigenvalues.

In [8] the authors consider the case of an arbitrary bounded operator $T$, not
necessarily normal, and the iterations of a single vector $f\in\mathcal{H}$
i.e. $\\#J=1$. They showed that the orbit $\\{T^{n}f:n\in\mathbb{N}_{0}\\}$ is
a frame of $\mathcal{H}$ if and only if there exist a model space $K_{\theta}$
of $H^{2}(\mathbb{D})$, and a continuous isomorphism $V$ (not necessarily
isometric), from $K_{\theta}$ to $\mathcal{H}$ such that $T$ is similar to
$S_{\theta}$, i.e. $T=VS_{\theta}V^{-1}.$ Here $S_{\theta}$ is the compression
of the unilateral shift acting on $K_{\theta},$ and
$K_{\theta}=H^{2}\ominus\theta H^{2}$ with $\theta$ an inner function.
Furthermore, they show that there exists a function $\varphi\in K_{\theta}$
with $V\varphi=f$ such that $\\{S^{n}_{\theta}\varphi:n\in\mathbb{N}_{0}\\}$
is a frame of $K_{\theta}.$

In other words, that theorem says that the orbit of a bounded operator in a
Hilbert space $\mathcal{H}$ forms a frame if and only if the orbit of the
compression of the shift in some model space isomorphic to $\mathcal{H}$ forms
a frame of the model space. The authors also obtain similar results for the
case of orbits in $\mathbb{Z}$, and the space $L^{2}(\mathbb{T})$ for the
characterization.

In the present paper we show that these results can be extended to the case of
countable orbits. For this we need to use model spaces in Hardy spaces with
multiplicity. We also generalized the case of $\mathbb{Z}-$orbits, with the
bilateral shift and reducing subspaces of $L^{2}(\mathbb{T},\ell^{2}(J)).$

On the other hand, this characterization motivates the study of frames of
model spaces, consisting of orbits of the compression of the shift.
Specifically, we consider the following problems.

For a given model space $\mathcal{N}\subset H^{2}(\mathbb{T},\ell^{2}(J))$,
characterize all the sets $\\{\varphi_{j}:j\in J\\}\subset\mathcal{N}$ such
that $\\{S_{\mathcal{N}}^{n}\varphi_{j}:j\in J,n\in\mathbb{N}_{0}\\}$ is a
frame of $\mathcal{N}.$ Here $S_{\mathcal{N}}$ is the compression of the shift
to $\mathcal{N}.$ We obtain necessary and sufficient conditions in Theorem
2.8.

We also address the same problem for $T$ invertible and $\mathbb{Z}$-orbits,
for which we find the necessary and sufficient conditions in Theorem 3.4, and
determine the minimum number of orbits needed to obtain a frame for
$\mathcal{H}$.

Finally, given a bounded operator $T$ in a separable Hilbert space
$\mathcal{H}$, which is the minimum cardinality of a set of functions
$\mathcal{A}$ in $\mathcal{H}$ such that
$\\{T^{n}f:f\in\mathcal{A},n\in\mathbb{N}_{0}\\}$ is a frame of $\mathcal{H}.$
Using the results mentioned above, this question can be studied in model
spaces of some Hardy space. In this case we provide a conjecture (Conjecture
2.13) together with an example supporting it.

The paper is organized as follows:

After establishing the necessary notation and definitions, in Section 2 we
address the unilateral case. We first establish in Theorem 2.1 a
characterization of when the forward iterations of a bounded operator on a set
$\\{f_{j},j\in J\\}$ in an arbitrary Hilbert space $\mathcal{H}$ are a frame
of $\mathcal{H}$.

This motivates in Subsection 2.1 the study of frames for the the unilateral
shift of multiplicity $\sharp J$ acting on co-invariant subspaces of
$H^{2}(\mathbb{T},\ell^{2}(J))$. In Subsection 2.2 we address the question of
establishing the minimum cardinality of unilateral orbits need to form a
frame.

Finally in Section 3 we look at doubly invariant subspaces, for which in
Theorem 3.5 we establish the minimum number of orbits needed to obtain a frame
for a doubly invariant subspace of of $(L^{2})^{m}$.

##  2 Unilateral orbits

Let $J$ be a countable set of indexes and denote by
$H^{2}(\mathbb{T},\ell^{2}(J))$ the Hardy space of analytic functions from the
torus $\mathbb{T}=\\{z\in\mathbb{C}\\!:|z|=1\\}$ into $\ell^{2}(J)$. That is,
any $g\in H^{2}(\mathbb{T},\ell^{2}(J))$ can be written as

$g(z)=\sum_{n\geq 0}a_{n}z^{n},\mbox{ where $a_{n}\in\ell^{2}(J)$ and
}\|g\|^{2}=\sum_{n\geq 0}\|a_{n}\|_{\ell^{2}(J)}^{2}.$ (2.1)

Via this representation we can think of $\ell^{2}(J)$ as a closed subspace of
$H^{2}(\mathbb{T},\ell^{2}(J))$. Denote by $S$ the operator on
$H^{2}(\mathbb{T},\ell^{2}(J))$ of multiplication by $z$ (the unilateral shift
of multiplicity $\sharp J$). If $E\subset H^{2}(\mathbb{T},\ell^{2}(J))$ is a
closed subspace and $P_{E}$ denotes the orthogonal projection onto $E$, the
operator

$S_{E}:=P_{E}S|_{E}$

is called the compression of $S$ to $E$. We say that $E$ is coinvariant for
$S$ (or a model space) if its orthogonal complement $E^{\bot}$ is
$S$-invariant.

######  Theorem 2.1.

Let $\mathcal{H}$ be a Hilbert space, $T\in\mathcal{L}(\mathcal{H})$ and
$f_{j}\in\mathcal{H}$, where $j\in J$ is countable. Then

$\\{T^{n}f_{j}:n\in\mathbb{N}_{0},\ j\in J\\}$ (2.2)

is a frame for $\mathcal{H}$ if and only if there is an $S$-coinvariant
subspace $K\subset H^{2}(\mathbb{T},\ell^{2}(J))$ and an invertible operator
$V:K\to\mathcal{H}$ such that

$V^{-1}TV=S_{K}\ \mbox{ and }\ V(P_{K}e_{j})=f_{j}\ \mbox{ for all $j\in J$},$

where $e_{j}\in\ell^{2}(J)$ is the standard basis.

###### Proof.

Since $\\{S^{n}e_{j}:\,n\in\mathbb{N}_{0},\,j\in J\\}$ is an ortonormal basis
of $H^{2}(\mathbb{T},\ell^{2}(J))$, we can define a linear transformation
$W:H^{2}(\mathbb{T},\ell^{2}(J))\to\mathcal{H}$ by setting

$W(S^{n}e_{j})=T^{n}f_{j},\ \ \forall n\in\mathbb{N}_{0},\,j\in J.$ (2.3)

The operator $W$ is then bounded because (2.2) is a Bessel sequence and it is
onto because this sequence is a frame. Therefore, letting
$K:=(\mbox{Ker}\,W)^{\bot}$, we have that $W|_{K}:K\to\mathcal{H}$ is
invertible. In addition, it is clear from (2.3) that $TW=WS$, implying that
$\mbox{Ker}\,W$ is $S$-invariant, which means that $K$ is coinvariant.
Consider the compression $S_{K}$ of $S$ to $K$. We claim that the following
diagram commutes

${\mathcal{H}}$${\mathcal{H}}$${K\
}$${K}$$\scriptstyle{T}$$\scriptstyle{W|_{K}^{-1}}$$\scriptstyle{W|_{K}}$$\scriptstyle{S_{K}}$

First notice that $W|_{K}P_{K}(S^{n}e_{j})=W(S^{n}e_{j})=T^{n}f_{j}$. Hence,
applying $T$ we get

$TW|_{K}P_{K}(S^{n}e_{j})=T^{n+1}f_{j}=W|_{K}P_{K}(S^{n+1}e_{j}).$

Consequently,

$\displaystyle W|_{K}^{-1}TW|_{K}P_{K}(S^{n}e_{j})$
$\displaystyle=P_{K}(S^{n+1}e_{j})=(P_{K}S)(S^{n}e_{j})$
$\displaystyle=(P_{K}S)(P_{K}S^{n}e_{j})+(P_{K}S)(P_{K^{\bot}}S^{n}e_{j})$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}(P_{K}S)(P_{K}S^{n}e_{j}),$

where (1) holds because $K^{\bot}$ is $S$-invariant. Since $P_{K}S^{n}e_{j}$
generate $K$, this proves our claim. Thus, the operator $V:=W|_{K}$ satisfies
the theorem. ∎

Now, we have the following proposition whose proof is inmediate.

######  Proposition 2.2.

Let $\mathcal{H}_{0},\,\mathcal{H}$ be two Hilbert spaces,
$T\in\mathcal{L}(\mathcal{H})$ and $f_{j}\in\mathcal{H}$, for $j\in J$
countable. If $V:\mathcal{H}_{0}\to\mathcal{H}$ is an invertible operator,
then

$\\{T^{n}f_{j}:n\in\mathbb{N}_{0},\ j\in J\\}\hskip 5.69054pt\mbox{is a frame
for $\mathcal{H}$}$

if and only if
$\displaystyle\,\\{(V^{-1}TV)^{n}(V^{-1}f_{j}):n\in\mathbb{N}_{0},\ j\in J\\}$
is a frame for $\mathcal{H}_{0}$.

Thus, combining Proposition 2.2 with Theorem 2.1 we have the following
corollary.

######  Corollary 2.3.

Let $\mathcal{H}$ be a Hilbert space, and $\\{f_{j}\\}_{j\in J}$ a set of
vectors in $\mathcal{H}$.The following assertions are equivalent.

  1. 1.

$\\{T^{n}f_{j}:n\in\mathbb{N}_{0},\ j\in J\\}\hskip 5.69054pt\mbox{is a frame
for $\mathcal{H}$}$.

  2. 2.

There exists an $S$-covariant space $K$ in $H^{2}(\mathbb{T},\ell^{2}(J))$, a
collection of functions $\\{\varphi_{j}\\}_{j\in J}\subset K$ and, an
isomorphism $V:K\to\mathcal{H}$ such that

$\\{S_{K}^{n}\varphi_{j}:n\in\mathbb{N}_{0},\ j\in J\\}\hskip
5.69054pt\mbox{is a frame for $K$}$ with $V^{-1}TV=S_{K}\ \mbox{ and }\
V(\varphi_{j})=f_{j}\ \mbox{ for all }j\in J$.

In short, what Corollary 2.3 says, is that every frame of iterations of a set
of functions by a bounded operator in a Hilbert space can be represented as a
frame of iterations of the compression of the shift of a model space of an
appropiate Hardy space.

###  2.1 Toeplitz operators on model spaces

For $m,k\in\mathbb{N}$, $L^{2}=L^{2}(\mathbb{T})$ and a matrix
$G\in(L^{2})^{m\times k}$ let

$D_{G}=\\{\vv{h}\in(H^{2})^{k}:\ G\vv{h}\in(L^{2})^{m}\\},$

where $\vv{h}$ is taken as a column vector. Then for any linear submanifold
$D\subset D_{G}$ we can define a Toeplitz operator
$T_{G}:D\subset(H^{2})^{k}\to(H^{2})^{m}$ by the rule

$T_{G}\vv{f}=P_{(H^{2})^{m}}(G\vv{h}),$

where $P_{(H^{2})^{m}}$ is the orthogonal projection. Observe that $D_{G}$ is
dense in $(H^{2})^{k}$, since it contains $(H^{\infty})^{k}$. If we write
$G=(g_{ij})$ it follows easily that $T_{G}$ extends boundedly to $(H^{2})^{k}$
if and only if all the scalar operators $T_{g_{ij}}$ extend boundedly to
$H^{2}$, which is equivalent to $g_{ij}\in L^{\infty}$ for all $i,j$ (see [21,
Prop. 10.1]). However, if $T_{G}$ is defined on a linear submanifold $D\subset
D_{G}$, the above condition could be unnecessary for extending $T_{G}$
continuously to the closure of $D$. If $G=(g_{ij})\in(L^{2})^{m\times k}$
write $G^{\ast}:=(\overline{g}_{ji})\in(L^{2})^{k\times m}$ for the conjugate
transpose matrix. A simple calculation shows that

$\langle T_{G}\vv{h},\vv{f}\rangle=\langle\vv{h},T_{G^{\ast}}\vv{f}\rangle\ \
\mbox{ for }\,\vv{h}\in D_{G},\,\vv{f}\in D_{G^{\ast}},$

meaning that $T^{\ast}_{G}=T_{G^{\ast}}$. In particular, given a column matrix
$\vv{g}=(g_{1},\ldots,g_{m})\in(H^{2})^{m\times 1}$, the Toeplitz operator
$T_{\vv{g}^{\ast}}\vv{h}\in H^{2}$ for $\vv{h}\in(H^{\infty})^{m}$ is densely
defined in $(H^{2})^{m}$. The (unilateral) shift $S$ of multiplicity
$m\in\mathbb{N}$ is the Toeplitz operator with symbol $zI_{\mathbb{C}^{m}}$
acting on $(H^{2})^{m}$. That is, $S$ multiplies each coordinate of
$h\in(H^{2})^{m}$ by the variable $z$. It is clear that
$ST_{\Theta}=T_{\Theta}S$ when $\Theta\in(H^{\infty})^{m\times m}$, implying
that the closure of $T_{\Theta}(H^{2})^{m}$ is a closed $S$-invariant
subspace. The Beurling-Lax-Halmos Theorem (for the respective scalar [3],
finite dimensional [16] and infinite dimensional [12] case) says that all the
$S$-invariant subspaces are of this form and they can be written in a more
precise and systematic form.

A matrix $\Theta\in(H^{\infty})^{m\times m}$ is called rigid if the non-
tangential limits $\Theta(e^{it})$ are partial isometries on $\mathbb{C}^{m}$
with the same initial space for almost every point $e^{it}\in\mathbb{T}$. We
include the null matrix as a particular case, and we point out that when the
initial space is all of $\mathbb{C}^{m}$ the matrix is called inner. It
follows that $T_{\Theta}(H^{2})^{m}$ is closed and therefore an $S$-invariant
subspace. The B-L-H Theorem says that these are all. Consequently, all the
$S$-coinvariant subspaces (i.e.: $S^{\ast}$-invariant) are of the form

$K_{\Theta}:=(H^{2})^{m}\ominus T_{\Theta}(H^{2})^{m}$

for a rigid matrix $\Theta\in(H^{\infty})^{m\times m}$. If
$P_{K_{\Theta}}=I-T_{\Theta}T_{\Theta^{\ast}}$ denotes the orthogonal
projection onto $K_{\Theta}$, the operator obtained by compressing $S$ to this
space:

$S_{\Theta}:=P_{K_{\Theta}}S\big{|}_{K_{\Theta}}:K_{\Theta}\to K_{\Theta}$

is called a model operator, while $K_{\Theta}$ is a called a model space.
Since polynomials $\mathcal{P}^{m}$ are dense in $(H^{2})^{m}$, the linear
manifold

$(I-T_{\Theta}T_{\Theta^{\ast}})(\mathcal{P}^{m})\subset(H^{\infty})^{m}\cap
K_{\Theta}\ \mbox{ is dense in $K_{\Theta}$}.$

Therefore, when $\vv{g}\in(H^{2})^{m}$, the restriction of $T_{\vv{g}^{\ast}}$
to $(H^{\infty})^{m}\cap K_{\Theta}$ is also densely defined in $K_{\Theta}$.
The next lemma characterizes the symbols $\vv{g}$ that make it bounded.

######  Lemma 2.4.

$T_{\vv{g}^{\ast}}$ is bounded on $K_{\Theta}$ if and only if

$\vv{g}\in(H^{\infty})^{m}+T_{\Theta}(H^{2})^{m}.$ (2.4)

Moreover, if $\vv{g}\in T_{\Theta}(H^{2})^{m}$ then $T_{\vv{g}^{\ast}}\equiv
0$ on $K_{\Theta}$.

###### Proof.

Let us momentarily denote the backward shift of multiplicity $m$ by
$S^{\ast}_{m}$ . It is easy to deduce the intertwining relation
$T_{\vv{g}^{\ast}}S^{\ast}_{m}=S^{\ast}_{1}T_{\vv{g}^{\ast}}$ on
$(H^{\infty})^{m}\cap K_{\Theta}$, and if $T_{\vv{g}^{\ast}}|_{K_{\Theta}}$ is
bounded, this extends to every $\vv{h}\in K_{\Theta}$. So, assuming
boundedness, the Sz.-Nagy and Foias Commutant Lifting Theorem (see [9, Thm.
5]) tells us that there is a bounded operator $L:(H^{2})^{m}\to H^{2}$ such
that

$L|_{K_{\Theta}}=T_{\vv{g}^{\ast}}|_{K_{\Theta}}\ \mbox{ and }\
LS^{\ast}_{m}=S^{\ast}_{1}L\mbox{ on $(H^{2})^{m}$}.$

Hence, the restriction of $L$ to each coordinate of $(H^{2})^{m}$ is a bounded
operator on $H^{2}$ that commutes with $S^{\ast}_{1}$, meaning that
$L=T_{\vv{f}^{\ast}}$ for some $\vv{f}\in(H^{\infty})^{m\times 1}$. So, if we
write $\vv{\mathsf{g}}=\vv{g}-\vv{f}$ then $T_{\vv{\mathsf{g}}^{\ast}}\equiv
0$ on $K_{\Theta}$, and consequently when $\vv{h}\in K_{\Theta}$:

$0=(T_{\vv{\mathsf{g}}^{\ast}}\vv{h})(0)=P_{H^{2}}\big{(}\overline{\mathsf{g}}_{1}h_{1}+\cdots+\overline{\mathsf{g}}_{m}h_{m}\big{)}(0)=\langle\vv{h},\vv{\mathsf{g}}\rangle_{(H^{2})^{m}}.$

This means that $\vv{\mathsf{g}}\in(K_{\Theta})^{\bot}=T_{\Theta}(H^{2})^{m}$,
from which (2.4) follows immediately.

The reciprocal implication follows from the last assertion of the Lemma.
Therefore it only remains to show that if $\vv{g}=T_{\Theta}\vv{d}$, with
$\vv{d}\in(H^{2})^{m}$, then $T_{\vv{g}^{\ast}}$ vanishes on $K_{\Theta}$. For
$f\in H^{\infty}$ and $\vv{h}\in(H^{\infty})^{m}\cap K_{\Theta}$ we see that

$\displaystyle\langle T_{\vv{g}^{\ast}}\vv{h},f\rangle$
$\displaystyle=\langle\vv{h},\vv{g}f\rangle_{(H^{2})^{m}}=\langle\vv{h},T_{\Theta}(\vv{d}f)\rangle_{(H^{2})^{m}}=\langle
T_{\Theta^{\ast}}\vv{h},\vv{d}f\rangle_{(H^{2})^{m}}=0,$

where the last equality holds because
$K_{\Theta}=\mbox{Ker}\,T_{\Theta^{\ast}}$. ∎

Suppose that $\vv{g}\in K_{\Theta}\subset(H^{2})^{m}$. Then for
$\vv{h}\in(H^{\infty})^{m}\cap K_{\Theta}$:

$\displaystyle\langle\vv{h},S_{\Theta}^{n}\vv{g}\rangle$
$\displaystyle=\sum_{j=1}^{m}\langle
h_{j},z^{n}g_{j}\rangle=\big{\langle}\sum_{j=1}^{m}T_{\overline{g}_{j}}h_{j},z^{n}\big{\rangle}=\langle
T_{\vv{g}^{\ast}}\vv{h},z^{n}\rangle.$

Thus, $\sum_{n\geq
0}|\langle\vv{h},S_{\Theta}^{n}\vv{g}\rangle|^{2}=\|T_{\vv{g}^{\ast}}\vv{h}\|^{2}$.
Furthermore, if $\vv{g}_{1},\ldots,\vv{g}_{k}\in K_{\Theta}$ are column
vectors and we consider the matrices

$G:=\big{[}\vv{g}_{1},\ldots,\vv{g}_{k}\big{]}\in(H^{2})^{m\times k}\ \ \
\mbox{ and }\ \ \
T_{G^{\ast}}\vv{h}=\begin{bmatrix}T_{\vv{g}_{1}^{\ast}}\vv{h}\\\ \vdots\\\
T_{\vv{g}_{k}^{\ast}}\vv{h}\\\ \end{bmatrix}\in(H^{2})^{k\times 1},$

it follows that

$\sum_{j=1}^{k}\sum_{n\geq
0}|\langle\vv{h},S_{\Theta}^{n}\vv{g}_{j}\rangle|^{2}=\sum_{j=1}^{k}\|T_{\vv{g}_{j}^{\ast}}\vv{h}\|^{2}=\|T_{G^{\ast}}\vv{h}\|^{2}.$
(2.5)

Hence, by (2.5) the family $\mathcal{F}:=\\{S_{\Theta}^{n}\vv{g}_{j}:\
n\in\mathbb{N}_{0},\ 1\leq j\leq k\\}$ is a Bessel sequence in $K_{\Theta}$ if
and only if $T_{G^{\ast}}\big{|}_{K_{\Theta}}$ is bounded, and is a frame if
and only if it is bounded above and below.

######  Lemma 2.5.

Let $F\in(H^{\infty})^{m\times k}$ and $\Theta$ be a rigid matrix. Then

$T_{F}T_{F^{\ast}}\geq\delta^{2}I_{(H^{2})^{m}}\mbox{ on }K_{\Theta}\hskip
8.53581pt\mbox{ for some $\delta>0$}$

if and only if $\displaystyle\
\|T_{F^{\ast}}h\|+\|T_{\Theta^{\ast}}h\|\geq\varepsilon\|h\|$ for all
$h\in(H^{2})^{m}$ and some $\varepsilon>0$.

###### Proof.

The implication ($\Leftarrow$) follows by noticing that
$\mbox{Ker}\,T_{\Theta^{\ast}}=K_{\Theta}$. To prove ($\Rightarrow$) we can
assume that $\|T_{F^{\ast}}\|\leq 1$. If $h\in(H^{2})^{m}$ has norm 1,

$\displaystyle\delta\big{[}1-\|T_{\Theta^{\ast}}h\|\big{]}$
$\displaystyle\leq\delta\|(I-T_{\Theta}T_{\Theta^{\ast}})h\|\
\leq\|T_{F^{\ast}}(I-T_{\Theta}T_{\Theta^{\ast}})h\|$ $\displaystyle\leq\
\|T_{F^{\ast}}h\|+\|T_{F^{\ast}}T_{\Theta}T_{\Theta^{\ast}}h\|\
\leq\|T_{F^{\ast}}h\|+\|T_{\Theta^{\ast}}h\|,$

where the first inequality follows from $\|T_{\Theta}\|\leq 1$ and the second
inequality holds by hypothesis. If $\|T_{\Theta^{\ast}}h\|\leq 1/2$ this
proves that $\delta/2\leq\|T_{F^{\ast}}h\|+\|T_{\Theta^{\ast}}h\|$. Otherwise
$\|T_{\Theta^{\ast}}h\|>1/2$ and there is nothing to prove. ∎

The next Proposition requires a version of the Matrix Corona Theorem proved
independently by Fuhrmann [10, Thm. 3.1] and Vasyunin (credited in [20, Thm.
3]).

######  Theorem 2.6.

Let $F_{j}\in(H^{\infty})^{m\times m}$ for $1\leq j\leq q$. Then there are
$B_{j}\in(H^{\infty})^{m\times m}$ such that

$\sum_{j=1}^{q}F_{j}(z)B_{j}(z)=I_{\mathbb{C}^{m}}\ \ \ \forall
z\in\mathbb{D}.$

if and only if there is some $\eta>0$ such that
$\,\sum_{j=1}^{q}F_{j}(z)F^{\ast}_{j}(z)\geq\eta^{2}I_{\mathbb{C}^{m}}$, $\ \
\forall z\in\mathbb{D}$.

######  Proposition 2.7.

Let $\Theta\in(H^{\infty})^{m\times m}$ be a rigid matrix and
$F\in(H^{\infty})^{m\times k}$. The following assertions are equivalent.

  1. (1)

$T_{F}T_{F^{\ast}}\geq\delta^{2}I_{(H^{2})^{m}}$ on $K_{\Theta}$ for some
$\delta>0$.

  2. (2)

$F(z)F^{\ast}(z)+\Theta(z)\Theta^{\ast}(z)\geq\eta^{2}I_{\mathbb{C}^{m}}$ for
some $\eta>0$ and all $z\in\mathbb{D}$.

  3. (3)

There exist $A\in(H^{\infty})^{k\times m}$ and $B\in(H^{\infty})^{m\times m}$
such that

$F(z)A(z)+\Theta(z)B(z)=I_{\mathbb{C}^{m}}\ \ \ \forall z\in\mathbb{D}.$

###### Proof.

By Lemma 2.5, condition (1) says that there is some $\varepsilon>0$ such that

$T_{F}T_{F^{\ast}}+T_{\Theta}T_{\Theta^{\ast}}\geq\varepsilon^{2}I_{(H^{2})^{m}}.$
(2.6)

For $\vv{c}\in\mathbb{C}^{m}$ consider
$\vv{c}_{\\!z}:=\vv{c}k_{z}\in(H^{2})^{m}$, where $k_{z}\in H^{2}$ is the
normalized reproducing kernel of $z\in\mathbb{D}$. Then
$T_{F^{\ast}}\vv{c}_{\\!z}=F^{\ast}(z)\vv{c}k_{z}$, from which

$\|T_{F^{\ast}}\vv{c}_{\\!z}\|_{(H^{2})^{k}}=\|F^{\ast}(z)\vv{c}\|_{\mathbb{C}^{k}}\
\mbox{ and }\
\|T_{\Theta^{\ast}}\vv{c}_{\\!z}\|_{(H^{2})^{m}}=\|\Theta^{\ast}(z)\vv{c}\|_{\mathbb{C}^{m}}.$

These equalities with (2.6) give
$\displaystyle\|F^{\ast}(z)\vv{c}\|^{2}_{\mathbb{C}^{k}}+\|\Theta^{\ast}(z)\vv{c}\|^{2}_{\mathbb{C}^{m}}\geq\varepsilon^{2}\|\vv{c}\|^{2}_{\mathbb{C}^{m}}$,
for all $\vv{c}\in\mathbb{C}^{m}$ and $z\in\mathbb{D}$, which is (2) with
$\eta=\varepsilon$.

Now suppose that (2) holds. If $k=m$ then (3) follows immediately from Theorem
2.6. Otherwise the idea is to use a very simple trick of linear algebra to
reduce our problem to that theorem. Write $k=mp+r$, where
$p\in\mathbb{N}_{0}$, $\,0\leq r<m$, and decompose the matrix $F(z)$ into $p$
square matrices $F_{j}(z)\in(H^{\infty})^{m\times m}$ formed by each of the
columns of $F(z)$, and if $r>0$ include another matrix $F_{p+1}(z)$ formed by
the last $r$ columns of $F(z)$ plus columns of zeros until completing a
$(m\times m)$-matrix. Assume this case to avoid changing indexes. Then
condition (2) translates into

$\sum_{j=1}^{p+1}F_{j}(z)F^{\ast}_{j}(z)+\Theta(z)\Theta^{\ast}(z)\geq\eta^{2}I_{\mathbb{C}^{m}},\
\ \forall z\in\mathbb{D}.$

Thus, Theorem 2.6 says that there are matrices
$A_{j},B\in(H^{\infty})^{m\times m}$ such that

$\sum_{j=1}^{p+1}F_{j}(z)A_{j}(z)+\Theta(z)B(z)=I_{\mathbb{C}^{m}},\ \ \
\forall z\in\mathbb{D}.$

It is clear then that if $A\in(H^{\infty})^{k\times m}$ is formed by all the
files of $A_{1}$ followed by the files of $A_{2}$ and so on until the first
$r$ files of $A_{p+1}$, then $A$ and $B$ satisfy (3).

Finally, if (3) holds, passing to Toeplitz operators we get

$I_{(H^{2})^{m}}=T_{FA+\Theta
B}^{\ast}=(T_{F}T_{A}+T_{\Theta}T_{B})^{\ast}=T_{A^{\ast}}T_{F^{\ast}}+T_{B^{\ast}}T_{\Theta^{\ast}},$

which implies that $T_{F^{\ast}}|_{K_{\Theta}}$ has a left inverse, and this
is equivalent to (1).
∎

######  Theorem 2.8.

Let $\Theta\in(H^{\infty})^{m\times m}$ be a rigid matrix and $\vv{g}_{j}\in
K_{\Theta}$ for $j=1,\ldots,k$. Then the family

$\mathcal{F}=\\{S_{\Theta}^{n}\vv{g}_{j}:\,n\in\mathbb{N}_{0},\,1\leq j\leq
k\\}$

is a Bessel sequence in $K_{\Theta}$ if and only if
$\vv{g}_{j}=P_{K_{\Theta}}(\vv{f}_{j})$, with $\vv{f}_{j}\in(H^{\infty})^{m}$
for all $1\leq j\leq k$, and a frame for $K_{\Theta}$ if and only if, in
addition,
$F:=\big{[}\vv{f}_{1},\ldots,\vv{f}_{k}\big{]}\in(H^{\infty})^{m\times k}$
satisfies any of the conditions of Proposition 2.7.

###### Proof.

Consider the matrix $\displaystyle
G:=\big{[}\vv{g}_{1},\ldots,\vv{g}_{k}\big{]}\in(H^{2})^{m\times k}$, where
each $\vv{g}_{j}$ is a column vector. By the comment that follows (2.5),
$\mathcal{F}$ is a Bessel sequence (or a frame) for $K_{\Theta}$ if and only
if $T_{G^{\ast}}\big{|}_{K_{\Theta}}$ is bounded above (respectively above and
below). Since $\vv{g}_{j}\in K_{\Theta}$, Lemma 2.4 says that upper
boundedness is equivalent to the existence of $\vv{f}_{j}\in(H^{\infty})^{m}$
such that $\vv{g}_{j}=P_{K_{\Theta}}\vv{f}_{j}$ for $1\leq j\leq k$. So,
writing $F=\big{[}\vv{f}_{1},\ldots,\vv{f}_{k}\big{]}\in(H^{\infty})^{m\times
k}$, a new use of Lemma 2.4 gives

$T_{G^{\ast}}\big{|}_{K_{\Theta}}=T_{F^{\ast}}\big{|}_{K_{\Theta}}.$

Thus, $T_{G^{\ast}}\big{|}_{K_{\Theta}}$ is bounded below if and only if
$T_{F^{\ast}}\big{|}_{K_{\Theta}}$ satisfies (1) of Propos. 2.7. ∎

Among the conditions of Proposition 2.7 it is apparent that (2) is the easiest
to check. This fact will be reflected in the next two examples, where it is
used to characterize frames of orbits in accordance with Theorem 2.8.

######  Example 2.9.

Suppose that $u\in H^{2}$ is inner or the null function and let $f_{j}\in
H^{\infty}$ for $j=1,\ldots,k$, be such that

$|f_{1}(z)|^{2}+\cdots+|f_{k}(z)|^{2}+|u(z)|^{2}\geq\eta^{2}$

for some $\eta>0$ and all $z\in\mathbb{D}$, which is (2) of Proposition 2.7.
Then the $S_{u}$ orbits of

$g_{j}:=(I-T_{u}T_{\overline{u}})f_{j}\in K_{u}\ \mbox{ for }\ j=1,\ldots k$

form a frame for $K_{u}$. By the last theorem any frame of at most $k$ orbits
(because of possible repetitions) has this form. Repetitions of the
$g_{j}^{\prime}s$ can be avoided by setting the additional condition
$f_{i}-f_{j}\not\in uH^{\infty}$ for $1\leq i<j\leq m$. Furthermore, if the
set of functions $\\{f_{j}\\!:1\leq j\leq k\\}$ that satisfies the above
inequality is minimal then so is $\\{g_{j}\\!:1\leq j\leq k\\}$, in the sense
that if we extract any of the respective orbits, the remaining orbits no
longer form a frame.

When $u\equiv 0$ the corresponding operator is the simple shift $S$ and a
single orbit is a frame if and only if it is generated by an invertible
function $f\in\mbox{$H^{\infty}$}$. Observe the contrast with the
characterization of cyclic vectors for $S$ given by Beurling’s theorem, where
the orbit is generated by an outer function $g\in H^{2}$ (see [11, Cor. 7.3]).

######  Example 2.10.

For $b_{1},b_{2}\in H^{\infty}$ inner functions such that
$\inf_{\mathbb{D}}|b_{1}|^{2}+|b_{2}|^{2}\geq\delta^{2}$ consider the inner
matrix

$\Theta=\begin{bmatrix}b_{1}&0\\\ 0&b_{2}\\\
\end{bmatrix}\in(H^{\infty})^{2\times 2}$

and the model operator $S_{\Theta}:K_{\Theta}\subset(H^{2})^{2}\to
K_{\Theta}$. If $F={1\choose 1}\in(H^{\infty})^{2\times 1}$ then

$\displaystyle\left\|F^{\ast}(z){c_{1}\choose
c_{2}}\right\|^{2}+\left\|\Theta^{\ast}(z){c_{1}\choose c_{2}}\right\|^{2}$
$\displaystyle=|c_{1}+c_{2}|^{2}+|b_{1}(z)c_{1}|^{2}+|b_{2}(z)c_{2}|^{2}$
$\displaystyle\geq(|c_{1}|-|c_{2}|)^{2}+\delta^{2}\min\\{|c_{1}|^{2},|c_{2}|^{2}\\}$
$\displaystyle\geq\frac{\delta^{2}}{16}\,(|c_{1}|^{2}+|c_{2}|^{2})$

for all $(c_{1},c_{2})\in\mathbb{C}^{2}$ and $z\in\mathbb{D}$, where the last
inequality follows easily by considering the two cases $2|c_{2}|\leq|c_{1}|$
and $2|c_{2}|\geq|c_{1}|\geq|c_{2}|$. Since the above inequality is (2) of
Proposition 2.7, then Theorem 2.8 says that the $S_{\Theta}$-orbit generated
by

$\vv{g}:=(I-T_{\Theta}T_{\Theta^{\ast}}){1\choose
1}={1-b_{1}\overline{b_{1}(0)}\choose 1-b_{2}\overline{b_{2}(0)}}\in
K_{\Theta}$

is a frame for $K_{\Theta}$. Therefore $K_{\Theta}$ admits a frame of a single
$S_{\Theta}$-orbit, which according to Theorem 2.1 means that $S_{\Theta}$ is
similar to a scalar model operator. We can imitate the proof of that theorem
to find the model space and the similarity. Indeed, let $W:H^{2}\to
K_{\Theta}$ be the linear operator defined by

$W(z^{n})=S^{n}_{\Theta}\vv{g}=P_{K_{\Theta}}S^{n}{1\choose 1}.$

Hence, $\displaystyle W(h)=P_{K_{\Theta}}{h\choose h}$ for every $h\in H^{2}$,
and consequently

$\text{Ker}\,W=\Big{\\{}h\in H^{2}:\,{h\choose h}\in
T_{\Theta}H^{2}\Big{\\}}=\\{h\in H^{2}:\,h\in b_{1}H^{2}\cap
b_{2}H^{2}\\}=b_{1}b_{2}H^{2}.$

So, $(\text{Ker}\,W)^{\bot}=K_{b_{1}b_{2}}$, the operator
$V:=W|_{K_{b_{1}b_{2}}}:K_{b_{1}b_{2}}\to K_{\Theta}$ is invertible,

$V^{-1}S_{\Theta}V=S_{b_{1}b_{2}}\ \ \mbox{ and }\ \
VP_{K_{b_{1}b_{2}}}1=\vv{g}.$

###  2.2 Minimum cardinality of unilateral orbits

Definition. Let $T:\mathcal{H}\to\mathcal{H}$ be a bounded operator on a
separable Hilbert space $\mathcal{H}$. We define the (unilateral) frame number
$\vartheta_{+}(T)$ of $T$ as the minimum $m\in\mathbb{N}\cup\\{\infty\\}$ such
that there exists a frame formed by the union of $m$ orbits. If there is no
$m$ with this property we say that $T$ has no unilateral frame number. If $T$
is invertible, its (bilateral) frame number $\vartheta_{-}(T)$ is defined
analogously with the bilateral orbits $\\{T^{n}g:\,n\in\mathbb{Z}\\}$, for
$g\in\mathcal{H}$.

Observe that Theorem 2.1 implies that $T$ has frame number $m$ if and only if
it is similar to a model operator $S_{\Theta}$ acting on $K_{\Theta}\subset
H^{2}(\mathbb{T},\ell^{2}(J))$, where $m=\sharp J$ is the minimum with this
property. Examples 2.9 and 2.10 show two operators of frame number 1. A simple
example will show that a rank 1 operator could have infinite frame number or
no number at all.

######  Example 2.11.

Every rank 1 operator on the separable Hilbert space $\mathcal{H}$ has the
form $Tx=\langle x,g\rangle f$ for all $x\in\mathcal{H}$, where
$f,g\in\mathcal{H}\setminus\\{0\\}$. Thus,

$T^{0}x=x\ \mbox{ and }\ T^{n}x=\langle x,g\rangle\,\langle
f,g\rangle^{n-1}f,\/\ \mbox{ for $n\in\mathbb{N}$. }$

Therefore

$\sum_{n\geq 0}|\langle h,T^{n}x\rangle|^{2}=|\langle h,x\rangle|^{2}+|\langle
x,g\rangle|^{2}\,|\langle h,f\rangle|^{2}\,\sum_{n\geq 1}|\langle
f,g\rangle|^{2(n-1)}.$

If $|\langle f,g\rangle|=0$ then $\\{T^{n}x_{j}:n\in\mathbb{N}_{0},\,j\in
J\\}$ is a frame if and only if $\\{x_{j}:j\in J\\}$ is a frame. So, in this
case $\vartheta_{+}(T)=\sharp J$. If $|\langle f,g\rangle|\geq 1$, the series
diverges, so when $x\not\perp g$ the orbit of $x$ is not even a Bessel
sequence (take $h=f$). When $x\bot g$, taking $h=g$ we see that $\langle
g,T^{n}x\rangle=0$ for all $n$ and there is no frame formed by orbits.
Finally, if $0<|\langle f,g\rangle|<1$ and $\\{x_{j}:j\in J\\}$ is a frame,
then so is $\\{T^{n}x_{j}:n\in\mathbb{N}_{0},\,j\in J\\}$. That is,
$\vartheta_{+}(T)\leq\sharp J$ again.

######  Remark 2.12.

From now on we write
$\mathfrak{S}:=\\{\vv{c}\in\mathbb{C}^{m}:\|\vv{c}\|=1\\}$ for the unit sphere
in $\mathbb{C}^{m}$. For $m\in\mathbb{N}$ let $\Theta\in(H^{\infty})^{m\times
m}$ be a rigid matrix and consider the model operator
$S_{\Theta}:K_{\Theta}\to K_{\Theta}$. It is clear that if $\Theta\equiv 0$
then $S_{\Theta}$ actually is the shift of multiplicity $m$ and
$\vartheta_{+}(S_{\Theta})=m$. This immediate observation has an interesting
generalization: if there is a sequence $z_{n}\in\mathbb{D}$ such that
$\Theta(z_{n})\to 0$ then $\vartheta_{+}(S_{\Theta})=m$. Indeed, if
$F\in(H^{\infty})^{m\times k}$ satisfies (2) of Propos. 2.7 then

$\inf_{\vv{c}\in\mathfrak{S}}\|F^{\ast}(z_{n})\vv{c}\|^{2}_{\mathbb{C}^{m}}\geq(\eta/2)^{2}\
\mbox{ for $n$ large enough.}$

This is not possible if $k<m$. This shows that in Example 2.10 the hypothesis
$\inf_{\mathbb{D}}|b_{1}|^{2}+|b_{2}|^{2}\geq\delta^{2}$ is necessary for the
frame number to be 1. This remark leads directly to Conjecture 2.13 below.

If $T\in\mathcal{L}(\mathcal{H})$ admits a frame formed by finitely many
orbits, there is some $m\in\mathbb{N}$ such that $T$ is similar to a model
operator $S_{\Theta}$ acting on $K_{\Theta}\subset(H^{2})^{m}$ for some rigid
matrix $\Theta\in(H^{\infty})^{m\times m}$. In this case, Theorem 2.8 tells us
that $\vartheta_{+}(T)=\vartheta_{+}(S_{\Theta})=k$ is the minimum number of
vectors $\vv{f}_{j}\in(H^{\infty})^{m}$, with $1\leq j\leq k$, such that if
$F=[\vv{f}_{1}\ldots\vv{f}_{k}]\in(H^{\infty})^{m\times k}$, there exists some
$\eta>0$ satisfying (2) of Propos. 2.7. If $\Theta\equiv 0$ (i.e.:
$S_{\Theta}$ is the shift of multiplicity $m$) then $F\in(H^{\infty})^{m\times
m}$ must be invertible. For instance, $F$ is the identity in the proof of
Theorem 2.1.

The maximal ideal space of $H^{\infty}$ is

$\mathcal{M}(H^{\infty})=\\{\varphi:\mbox{$H^{\infty}$}\to\mathbb{C}\,\text{
linear, continuous, multiplicative and $\neq 0$}\\}$

with the weak $\ast$ topology, that makes it a compact Hausdorff space. Via
evaluations the disk can be viewed as an open subset of
$\mathcal{M}(H^{\infty})$ and thanks to the corona theorem of Carleson [7] we
know that it is dense. Therefore $\mathcal{M}(H^{\infty})$ is a
compactification of $\mathbb{D}$. The Gelfand transform of
$f\in\mbox{$H^{\infty}$}$ consists of looking at $f$ in the bidual space of
$H^{\infty}$ and then restricting its domain to $\mathcal{M}(H^{\infty})$.
Thus, the Gelfand transform provides a continuous extension of $f$ to the
whole $\mathcal{M}(H^{\infty})$. In particular, the Gelfand transform induces
a continuous extension of any $\Theta\in(H^{\infty})^{m\times m}$ as a map
from $\mathcal{M}(H^{\infty})$ into $\mathbb{C}^{m\times m}$, that we also
denote by $\Theta$.

Below we conjecture a formula for the unilateral frame number and subsequently
we show that one inequality holds and the other can be reduced to a particular
case. Finally, we give an example that supports the conjecture.

######  Conjecture 2.13 (The unilateral frame number).

Let $0\neq K_{\Theta}\subset(H^{2})^{m}$ be the $S$-coinvariant subspace
associated to the rigid matrix $\Theta\in(H^{\infty})^{m\times m}$. Then

$\vartheta_{+}(S_{\Theta})=\sup_{x\in\mathcal{M}(H^{\infty})}\big{(}\\!\dim\mbox{Ker}\,\Theta(x)\big{)}.$
(2.1)

###### Proof of ($\geq$) in (2.1):.

We are looking for the minimum integer $k\in\mathbb{N}$ such that there are
$F\in(H^{\infty})^{m\times k}$ and $\delta>0$ satisfying

$\|F^{\ast}(z)\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|\Theta^{\ast}(z)\vv{c}\|_{\mathbb{C}^{m}}^{2}\geq\delta$

for all $z\in\mathbb{D}$ and $\vv{c}\in\mathfrak{S}$, where
$F^{\ast}(z):\mathbb{C}^{m}\to\mathbb{C}^{k}$. By the density of $\mathbb{D}$
in $\mathcal{M}(H^{\infty})$ and the compactness of the latter, this is
equivalent to

$\|F^{\ast}(x)\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|\Theta^{\ast}(x)\vv{c}\|_{\mathbb{C}^{m}}^{2}>0,\
\ \forall x\in\mathcal{M}(H^{\infty}),\ \forall\vv{c}\in\mathfrak{S}.$ (2.2)

By the dimension theorem, the kernels of $\Theta(x)$ and $\Theta^{\ast}(x)$
have the same dimension. Let $p$ be the right number in (2.1) and
$x\in\mathcal{M}(H^{\infty})$ be such that
$\dim\mbox{Ker}\,\Theta^{\ast}(x)=p$. If $k$ and $F$ are such that (2.2) holds
and we restrict

$F^{\ast}(x)|_{\text{Ker}\,\Theta^{\ast}(x)}:\mbox{Ker}\,\Theta^{\ast}(x)\approx\mathbb{C}^{p}\to\mathbb{C}^{k},$

the dimension theorem tells us that

$p=\dim\big{(}\mbox{Ker}\,F^{\ast}(x)|_{\text{Ker}\,\Theta^{\ast}(x)}\big{)}+\dim\big{(}\mbox{Ran}\,F^{\ast}(x)|_{\text{Ker}\,\Theta^{\ast}(x)}\big{)},$

where the last summand is $\leq k$. If $k<p$ the first summand must be
nonzero, which implies that
$\mbox{Ker}\,F^{\ast}(x)\cap\mbox{Ker}\,\Theta^{\ast}(x)\neq 0$. Since this
contradicts (2.2), we get $k\geq p$.

Proof that it is enough to assume that $\Theta$ is inner: Denote by
$E\subset\mathbb{C}^{m}$ the common initial space of the partial isometries
$\Theta(e^{it})$ for almost every $e^{it}\in\partial\mathbb{D}$. If $\Theta$
is not an inner matrix, $m_{1}:=\dim E<m$. Then there is an unitary matrix
$V\in\mathbb{C}^{m\times m}$ mapping
$\mathbb{C}^{m_{1}}\times\\{0\\}^{m-m_{1}}$ onto $E$ and
$\\{0\\}^{m_{1}}\times\mathbb{C}^{m-m_{1}}$ onto $E^{\bot}$. Consequently,

$\Theta V=\begin{bmatrix}\Theta_{1}&0\\\ \\!\\!0&0\\\
\end{bmatrix}\in(\mbox{$H^{\infty}$})^{m\times m},\text{ where
}\Theta_{1}\in(\mbox{$H^{\infty}$})^{m_{1}\times m_{1}}\text{ is inner.}$

Therefore, if there is $F_{1}\in(\mbox{$H^{\infty}$})^{m_{1}\times k_{1}}$
(with $k_{1}\leq m_{1}$) such that $F_{1},\,\Theta_{1}$ satisfy (2.2) with
$k_{1}$ and $m_{1}$ instead of $k$ and $m$, the pair

$F=\begin{bmatrix}F_{1}&0\\\ \\!\\!0&I_{m-m_{1}}\\\
\end{bmatrix}\in(\mbox{$H^{\infty}$})^{m\times(k_{1}+m-m_{1})}\,\mbox{ and
$\Theta V$ satisfy \eqref{maxcoro},}$

and the same holds for the pair $F$ and $\Theta$. ∎

By the above reduction, to prove the conjecture we can assume that $\Theta$ is
an inner matrix, and consequently its determinant is an inner function.

######  Example 2.14.

If $\Theta\in(H^{\infty})^{m\times m}$ is such that $u:=\det\Theta$ is an
interpolating Blaschke product, the conjecture holds.

###### Proof.

Consider $Z_{u}:=\\{x\in\mathcal{M}(H^{\infty})\\!:\,u(x)=0\\}$. If $p$ is the
right number in (2.1), for each $x\in Z_{u}$ there is a constant matrix
$F_{x}\in\mathbb{C}^{m\times p}$ such that
$\|F_{x}^{\ast}\vv{c}\|_{\mathbb{C}^{p}}\geq 1$ when
$\vv{c}\in\mbox{Ker}\,\Theta^{\ast}(x)\cap\mathfrak{S}$. Thus, by the
compactness of $\mathfrak{S}$, for each fixed $x\in Z_{u}$ we have

$\beta_{x}:=\inf_{\vv{c}\in\mathfrak{S}}\big{(}\|F_{x}^{\ast}\vv{c}\|_{\mathbb{C}^{p}}^{2}+\|\Theta^{\ast}(x)\vv{c}\|^{2}_{\mathbb{C}^{m}}\big{)}>0,$

from which the following set is an open neighborhood of $x$ in
$\mathcal{M}(H^{\infty})$:

$V_{x}=\\{y\in\mathcal{M}(H^{\infty})\\!:\,\inf_{\vv{c}\in\mathfrak{S}}\big{(}\|F_{x}^{\ast}\vv{c}\|_{\mathbb{C}^{p}}^{2}+\|\Theta^{\ast}(y)\vv{c}\|^{2}_{\mathbb{C}^{m}}\big{)}>\beta_{x}/2\\}$

Since $Z_{u}$ is compact, there is a finite covering by these sets
$V_{1},\ldots,V_{N}$, and the associated matrices $F_{j}\in\mathbb{C}^{m\times
p}$, with $1\leq j\leq N$, such that for some $\alpha>0$,

$\inf_{\vv{c}\in\mathfrak{S}}\big{(}\|F_{j}^{\ast}\vv{c}\|_{\mathbb{C}^{p}}^{2}+\|\Theta^{\ast}(y)\vv{c}\|^{2}_{\mathbb{C}^{m}}\big{)}\geq\alpha\
\mbox{ when $y\in V_{j}$.}$ (2.3)

Furthermore, since $Z_{u}$ is totally disconnected (see [11, p. 395]), by a
well-known result of dimension theory (see [17, p. 87]) we can assume that the
$V_{j}^{\prime}s$ satisfy the extra condition

$(V_{j}\cap Z_{u})\cap(V_{k}\cap Z_{u})=\emptyset\ \mbox{ if }j\neq k.$

This means that every $y\in Z_{u}$ belongs to only one of the
$V_{j}^{\prime}s$. In particular, when $z_{n}\in Z_{u}\cap\mathbb{D}$ let
$V_{j}$ be the corresponding set such that $z_{n}\in V_{j}$. Since the
sequence $\\{z_{n}\\}$ is interpolating, there is
$F\in(\mbox{$H^{\infty}$})^{m\times p}$ such that $F(z_{n})=F_{j}$. By the
density of $Z_{u}\cap\mathbb{D}$ in $Z_{u}$ (see [11, p. 395]), for every
$x\in Z_{u}$:

$F(x)=F_{j},\mbox{ where $V_{j}$ is the unique set that contains $x$.}$

Consequently, (2.3) says that

$\displaystyle\inf_{\vv{c}\in\mathfrak{S}}\big{(}\|F(y)^{\ast}\vv{c}\|_{\mathbb{C}^{p}}^{2}+\|\Theta^{\ast}(y)\vv{c}\|^{2}_{\mathbb{C}^{m}}\big{)}$
$\displaystyle\geq\alpha\ \mbox{ when $y\in\bigcup_{j=1}^{N}V_{j}$,}$

and since this is an open neighborhood of $Z_{u}$, we also have
$\inf_{\vv{c}\in\mathfrak{S}}\|\Theta^{\ast}(x)\vv{c}\|^{2}_{\mathbb{C}^{m}}>0$
when $x\not\in\bigcup_{j=1}^{N}V_{j}$. That is, (2.2) holds for
$F\in(\mbox{$H^{\infty}$})^{m\times p}$, giving the inequality that is missing
in the conjecture. ∎

In the above example, $u$ could be a finite Blaschke product that satisfies
finite interpolation (i.e.: with single zeros). Moreover, it is clear that the
proof of the Example can be easily adapted to a finite Blaschke product times
an interpolating Blaschke product.

##  3 Bilateral orbits

Let $J$ be a countable set of indexes and let $\mathbb{Z}$ be the set of
integers. Denote by $L^{2}(\mathbb{T},\ell^{2}(J))$ the space of $L^{2}$
functions from $\mathbb{T}$ into $\ell^{2}(J)$. That is, any $g\in
L^{2}(\mathbb{T},\ell^{2}(J))$ writes as (2.1), where the sum runs over
$\mathbb{Z}$ and $z\in\mathbb{T}$. The bilateral shift $U$ of multiplicity
$\sharp J$ is the operator of multiplication by the variable $z$ on
$L^{2}(\mathbb{T},\ell^{2}(J))$. It is clear that $U^{\ast}$ consists of
multiplication by $z^{-1}=\overline{z}$, so $U$ is unitary. A subspace
$E\subset L^{2}(\mathbb{T},\ell^{2}(J))$ is doubly invariant if $E$ and
$E^{\bot}$ are $U$-invariant, or equivalently, $E$ is both $U$ and $U^{\ast}$
invariant. A proof analogous to that of Theorem 2.1 gives

######  Theorem 3.1.

Let $\mathcal{H}$ be a Hilbert space, $T\in\mathcal{L}(\mathcal{H})$ be an
invertible operator and $f_{j}\in\mathcal{H}$, where $j\in J$ is countable.
Then $\\{T^{n}f_{j}:n\in\mathbb{Z},\ j\in J\\}$ is a frame for $\mathcal{H}$
if and only if there is a doubly invariant subspace $K\subset
L^{2}(\mathbb{T},\ell^{2}(J))$ and an invertible operator $V:K\to\mathcal{H}$
such that

$V^{-1}TV=U|_{K}\ \mbox{ and }\ V(P_{K}e_{j})=f_{j}\ \mbox{ for all $j\in
J$},$

where $e_{j}\in\ell^{2}(J)$ is the standard basis.

The theorem relates general frames of bilateral orbits to doubly invariant
subspaces of $L^{2}(\mathbb{T},\ell^{2}(J))$. The characterization of these
spaces were obtained by Helson and Lowdenslager [13] and Srinivasan [18]. We
follow the treatment of Lecture VI in Helson’s book [14].

Definition. A range function is a map defined almost everywhere

$\mathcal{J}:\mathbb{T}\to\\{\mbox{closed subspaces of $\mathcal{H}$}\\}$

that is (weakly) measurable in the sense that if $P_{\mathcal{J}(z)}$ is the
orthogonal projection on $\mathcal{J}(z)$, then $z\mapsto\langle
P_{\mathcal{J}(z)}a,b\rangle$ is measurable for all $a,b\in\mathcal{H}$.

In [14, Thm. 8] it is showed that a closed subspace $\mathfrak{M}\subset
L^{2}(\mathbb{T},\mathcal{H})$ is doubly invariant if and only if there is a
(unique) measurable range function $\mathcal{J}$ such that

$\mathfrak{M}=\mathfrak{M}_{\mathcal{J}}:=\\{f\in
L^{2}(\mathbb{T},\mathcal{H}):\ f(z)\in\mathcal{J}(z),\mbox{ a.e.}\
z\in\mathbb{T}\\}.$

So, the orthogonal projection
$P_{\mathfrak{M}}:L^{2}(\mathbb{T},\mathcal{H})\to\mathfrak{M}$ is given by

$(P_{\mathfrak{M}}\vv{f})(z)=P_{\mathcal{J}(z)}\vv{f}(z)\ \mbox{ for
a.e.$\,z\in\mathbb{T}$}.$

When $\mathcal{H}=\ell^{2}(J)$, where $\sharp J=m\in\mathbb{N}$, we identify
$L^{2}(\mathbb{T},\mathcal{H})=L^{2}(\mathbb{T},\mathbb{C}^{m})=L^{2}(\mathbb{T},\mathbb{C})^{m}=(L^{2})^{m}$,
where the last equality is just notation. Therefore for
$\mbox{a.e.}\,z\in\mathbb{T}$, the orthogonal projection
$P_{\mathcal{J}(z)}:\mathbb{C}^{m}\to\mathcal{J}(z)$ is represented by a
multiplication operator $M_{\sigma(z)}$ whose symbol is pointwise the matrix
of a projection in $\mathbb{C}^{m}$. That is, there is a unique matrix
$\sigma\in(L^{\infty})^{m\times m}$ such that
$M_{\sigma}=P_{\mathfrak{M}}:(L^{2})^{m}\to\mathfrak{M}$. So,
$P_{\mathcal{J}(z)}=M_{\sigma(z)}$ for a.e.$\,z\in\mathbb{T}$. Conversely, if
$\sigma\in(L^{\infty})^{m\times m}$ is any self-adjoint and idempotent matrix
then $\mathfrak{M}:=M_{\sigma}(L^{2})^{m}$ is a doubly invariant subspace. It
follows immediately that
$M_{\sigma}(L^{\infty})^{m}=(L^{\infty})^{m}\cap\mathfrak{M}$ is dense in
$\mathfrak{M}$.

###  3.1 Multiplication operators on doubly invariant subspaces

Most of the results in this subsection are completely analogous to those for
Toeplitz operators on model subspaces, except that the multiplication operator
is not followed by the analytic projection. This greatly simplifies many
arguments.

For $m,k\in\mathbb{N}$, $L^{2}=L^{2}(\mathbb{T})$ and $G\in(L^{2})^{m\times
k}$ define the multiplication operator

$M_{G}:(L^{\infty})^{k}\subset(L^{2})^{k}\to(L^{2})^{m}\ \mbox{ as }\
M_{G}\vv{f}=G\vv{h}.$

It is densely defined on $(L^{2})^{k}$ and if we write $G=(g_{ij})$, it is
immediate that $M_{G}$ is bounded on $(L^{2})^{k}$ if and only if the scalar
operators $M_{g_{ij}}$ are bounded on $L^{2}$, which is equivalent to
$g_{ij}\in L^{\infty}$ for all $i,j$. Also, $M^{\ast}_{G}=M_{G^{\ast}}$.

Let $\mathfrak{M}\subset(L^{2})^{m}$ be a doubly invariant subspace and
$\vv{g}\in(L^{2})^{m}$. Then $M_{\vv{g}^{\ast}}$ is densely defined on
$\mathfrak{M}$, and for $\vv{h}\in(L^{\infty})^{m}\cap\mathfrak{M}$:

$\langle\vv{h},U^{n}\vv{g}\rangle=\sum_{i=1}^{m}\langle
h_{i},z^{n}g_{i}\rangle=\big{\langle}\sum_{i=1}^{m}M_{\overline{g}_{i}}h_{i},z^{n}\big{\rangle}=\langle
M_{\vv{g}^{\ast}}\vv{h},z^{n}\rangle.$ (3.1)

Thus, if $\vv{g}_{1},\ldots,\vv{g}_{k}\in(L^{2})^{m}$ are the column vectors
of $G\in(L^{2})^{m\times k}$,

$\sum_{j=1}^{k}\sum_{n\in\mathbb{Z}}|\langle\vv{h},U^{n}\vv{g}_{j}\rangle|^{2}=\sum_{j=1}^{k}\|M_{\vv{g}_{j}^{\ast}}\vv{h}\|^{2}=\|M_{G^{\ast}}\vv{h}\|^{2}.$
(3.2)

######  Lemma 3.2.

If $\vv{g}\in(L^{2})^{m}$ then $M_{\vv{g}^{\ast}}$ is bounded on
$\mathfrak{M}$ if and only if

$\vv{g}\in(L^{\infty})^{m}+\mathfrak{M}^{\bot}.$ (3.3)

Moreover, if $\vv{g}\in\mathfrak{M}^{\bot}$ then $M_{\vv{g}^{\ast}}\equiv 0$
on $\mathfrak{M}$.

###### Proof.

Let $\sigma\in(L^{\infty})^{m\times m}$ be the matrix that satisfies
$M_{\sigma}=P_{\mathfrak{M}}$, the orthogonal projection. If
$\vv{g}\in(L^{2})^{m}$ is such that $M_{\vv{g}^{\ast}}$ is bounded on
$\mathfrak{M}$ then
$M_{\vv{g}^{\ast}}P_{\mathfrak{M}}=M_{\vv{g}^{\ast}\,\sigma}$ is bounded on
$(L^{2})^{m}$, which yields $\vv{g}^{\ast}\,\sigma\in(L^{\infty})^{1\times
m}$. If $\sigma^{\bot}\in(L^{\infty})^{m\times m}$ is such that
$M_{\sigma^{\bot}}=P_{\mathfrak{M}^{\bot}}$ then

$\vv{g}=\sigma\vv{g}+\sigma^{\bot}\vv{g}=(\vv{g}^{\ast}\sigma)^{\ast}+\sigma^{\bot}\vv{g}\in(L^{\infty})^{m\times
1}+\mathfrak{M}^{\bot},$

as claimed. The other assertions follow from (3.1). ∎

Suppose that $\mathfrak{M}\subset(L^{2})^{m}$ is doubly invariant and
$G\in(L^{2})^{m\times k}$ is a matrix with columns
$\vv{g}_{j}\in\mathfrak{M}$, for $1\leq j\leq k$. By (3.2) the family

$\mathcal{F}:=\\{U^{n}\vv{g}_{j}:\ n\in\mathbb{Z},\ 1\leq j\leq k\\}$ (3.4)

is a Bessel sequence for $\mathfrak{M}$ if and only if
$M_{G^{\ast}}\big{|}_{\mathfrak{M}}$ is bounded, and a frame if and only if it
is bounded above and below.

In Theorem 2.3 of [4] Bownik characterized the families $\mathcal{F}$ that
form a Bessel sequence, or a frame for its closed span in terms of the fibers

$\Phi(z)=\\{\vv{g}_{j}(z):\ 1\leq j\leq k,\
z\in\mathbb{T}\\}\subset\mathbb{C}^{m}.$

Namely, $\mathcal{F}$ is a Bessel sequence with constant $B$ or a frame with
constants $A,\ B$ if and only if the same holds for $\Phi(z)$ uniformly for
a.e $z\in\mathbb{T}$. Given a doubly invariant subspace
$\mathfrak{M}\subset(L^{2})^{m}$, Theorem 3.4 below gives a characterization
of the Bessel sequences and the frames in $\mathfrak{M}$ in terms of the
multiplication operator that projects on $\mathfrak{M}$.

######  Proposition 3.3.

Let $\mathfrak{M}\subset(L^{2})^{m}$ be a doubly invariant subspace and
$\beta\in(L^{\infty})^{m\times m}$ such that
$M_{\beta}=P_{\mathfrak{M}^{\bot}}$. If $F\in(L^{\infty})^{m\times k}$, the
following assertions are equivalent:

  1. (1)

$M_{FF^{\ast}}\geq\delta^{2}I_{(L^{2})^{m}}$ on $\mathfrak{M}$ for some
$\delta>0$.

  2. (2)

$F(z)F^{\ast}(z)+\beta(z)\geq\eta^{2}I_{\mathbb{C}^{m}}$ for some $\eta>0$ and
a.e.$\,z\in\mathbb{T}$.

###### Proof.

Since $\mathfrak{M}=\mbox{Ker}\,M_{\beta}$, it is clear that (1) is equivalent
to $M_{FF^{\ast}}+M_{\beta}\geq\varepsilon^{2}I_{(L^{2})^{m}}$ for some
$\varepsilon>0$. Also, this is an immediate consequence of (2). Finally, if
this inequality holds, consider a function $\chi_{E}(z)\vv{c}\in(L^{2})^{m}$,
where $\vv{c}\in\mathbb{C}^{m}$ and $E\subset\mathbb{T}$ is a set of measure
$|E|>0$. Then the above inequality says that

$\|\chi_{E}F^{\ast}\vv{c}\|^{2}_{(L^{2})^{k}}+\|\chi_{E}\beta\vv{c}\|^{2}_{(L^{2})^{m}}\geq\varepsilon^{2}\|\chi_{E}\vv{c}\|^{2}_{(L^{2})^{m}}=\varepsilon^{2}\|\vv{c}\|^{2}_{\mathbb{C}^{m}}\,|E|,$

which can be rewritten as

$\int_{E}\big{(}\|F^{\ast}(z)\vv{c}\|^{2}_{\mathbb{C}^{k}}+\|\beta(z)\vv{c}\|^{2}_{\mathbb{C}^{m}}\big{)}\,dz\geq\int_{E}\varepsilon^{2}\|\vv{c}\|^{2}_{\mathbb{C}^{m}}\,dz,$

where $dz$ denotes the Lebesgue measure on $\mathbb{T}$. Since $E$ is
arbitrary, we conclude that (2) holds with $\eta=\varepsilon$. ∎

######  Theorem 3.4.

Let $\mathfrak{M}\subset(L^{2})^{m}$ be a doubly invariant subspace,
$M_{\sigma}=P_{\mathfrak{M}}$ (with $\sigma\in(L^{\infty})^{m\times m}$), and
$g_{j}\in\mathfrak{M}$, where $j=1,\ldots,k$. The family $\mathcal{F}$ in
(3.4) is a Bessel sequence if and only if $\vv{g}_{j}=M_{\sigma}\vv{f}_{j}$,
with $\vv{f}_{j}\in(L^{\infty})^{m}$ for $1\leq j\leq k$, and a frame for
$\mathfrak{M}$ if and only if
$F:=\big{[}\vv{f}_{1},\ldots,\vv{f}_{k}\big{]}\in(L^{\infty})^{m\times k}$
satisfies Proposition 3.3 with $\beta=I_{(L^{2})^{m}}-\sigma$.

###### Proof.

The assertion on Bessel sequences follows immediately from (3.2) and (3.3).
For the other assertion write $G:=\big{[}\vv{g}_{1},\ldots,\vv{g}_{k}\big{]}$
and notice that Lemma 3.2 implies that
$M_{G^{\ast}}\big{|}_{\mathfrak{M}}=M_{F^{\ast}}\big{|}_{\mathfrak{M}}$. Thus,
the comments following (3.4) say that $\mathcal{F}$ is a frame for
$\mathfrak{M}$ if and only if we have (1) of Proposition 3.3. ∎

In particular, $\\{U^{n}f,\ n\in\mathbb{Z}\\}$, with $f\in(L^{2})^{m}$, is a
Bessel sequence if and only if $f\in(L^{\infty})^{m}$. The bilateral frame
number of a model operator on $\mathfrak{M}\subset(L^{2})^{m}$ can be obtained
from [4, Thm. 3.3] (see also the subsequent Remark (i) in[4]). We give below a
very simple proof that exploits a classical diagonalization result.

######  Theorem 3.5 (The bilateral frame number).

Let $0\neq\mathfrak{M}\subset(L^{2})^{m}$ be a doubly invariant subspace and
$\Theta\in(L^{\infty})^{m\times m}$ be the matrix that satisfies
$M_{\Theta}=P_{\mathfrak{M}^{\bot}}$. Then

$\vartheta_{-}(U|_{\mathfrak{M}})=\sup_{z\in\mathbb{T}}\big{(}\\!\dim\mbox{Ker}\,\Theta(z)\big{)},\vspace{-2mm}$

where $\sup$ is the essential supremum and $\Theta(z)$ acts on
$\mathbb{C}^{m}$ for a.e.$\,z\in\mathbb{T}$.

###### Proof.

Since $\Theta$ is self-adjoint, a result of Kadison [15, Thm. 3.19] asserts
that there is a unitary matrix $V\in(L^{\infty})^{m\times m}$ such that
$V^{\ast}\Theta V=D\in(L^{\infty})^{m\times m}$ is the diagonal matrix of a
projection for a.e.$\,z\in\mathbb{T}$. Therefore, when
$G\in(L^{\infty})^{m\times k}$, we have

$\displaystyle\inf_{\vv{c}\in\mathfrak{S}}\|G^{\ast}(z)\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|D(z)\vv{c}\|_{\mathbb{C}^{m}}^{2}$
$\displaystyle=\inf_{\vv{c}\in\mathfrak{S}}\|G^{\ast}(z)V^{\ast}(z)\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|D(z)V^{\ast}(z)\vv{c}\|_{\mathbb{C}^{m}}^{2}$
$\displaystyle=\inf_{\vv{c}\in\mathfrak{S}}\|\underbrace{G^{\ast}(z)V^{\ast}(z)}_{F^{\ast}(z)}\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|\underbrace{V(z)D(z)V^{\ast}(z)}_{\Theta(z)}\vv{c}\|_{\mathbb{C}^{m}}^{2},$

where $F\in(L^{\infty})^{m\times k}$. Hence, if
$\mathfrak{D}\subset(L^{2})^{m}$ is the doubly invariant subspace that
satisfies $M_{D}=P_{\mathfrak{D}^{\bot}}$, we get
$\vartheta_{-}(U|_{\mathfrak{M}})=\vartheta_{-}(U|_{\mathfrak{D}})$. The
diagonal of $D$ is formed by the characteristic functions of measurable sets
$E_{1},\ldots,E_{m}\subset\mathbb{T}$. Since $G^{\ast}$ must satisfy

$\inf_{\vv{c}\in\mathfrak{S}}\|G^{\ast}(z)\vv{c}\|_{\mathbb{C}^{k}}^{2}+\|D(z)\vv{c}\|_{\mathbb{C}^{m}}^{2}\geq\eta\
\mbox{ for a.e.$\,z\in\mathbb{T}$ and some $\eta>0$},$ (3.5)

the rank of $G^{\ast}(z)$ must be at least the cardinal of $\\{1\leq j\leq m:\
\chi_{E_{j}}(z)=0\\}$. Thus,

$\vartheta_{-}(U|_{\mathfrak{D}})\geq\sup_{z\in\mathbb{T}}\big{(}\\!\dim\mbox{Ker}\,D(z)\big{)}.\vspace{-1mm}$

For the other inequality let $p$ be the above supremum and let $1\leq
j_{1}<\ldots<j_{t}\leq m$ (with $t\leq p$), be such that
$\chi_{E_{j_{i}}}(z)=0$. Then the matrix $G^{\ast}\in(L^{\infty})^{p\times m}$
whose rows are $\vv{e}_{j_{1}},\ldots,\vv{e}_{j_{t}},0\ldots 0$, where
$\vv{e}_{j}\in\mathbb{C}^{m}$ is the standard basis, satisfies (3.5). Hence,

$\vartheta_{-}(U|_{\mathfrak{M}})=\vartheta_{-}(U|_{\mathfrak{D}})=\sup_{z\in\mathbb{T}}\big{(}\\!\dim\mbox{Ker}\,D(z)\big{)}=\sup_{z\in\mathbb{T}}\big{(}\\!\dim\mbox{Ker}\,\Theta(z)\big{)}.\vspace{-7mm}$

∎

Acknowledgement. We are grateful to E. Andruchow for bringing Kadison’s paper
[15],to our attention.

## References

  * [1] Aldroubi A., Cabrelli C. Çakmak A.F., Molter U. and Petrosyan A. Iterative actions of normal operators, J. Funct. Anal. 272 (2017), 1121-1146.
  * [2] Aldroubi A., Cabrelli C., Molter U., and Tang S., Dynamical Sampling, Appl. Comput. Harmon. Anal. 42 (2017), 378-401.
  * [3] Beurling A., On two problems concerning linear transformations in Hilbert space, Acta Math., 81 (1949), 239-255.
  * [4] Bownik M., The structure of shift-invariant subspaces of $L^{2}(\mathbb{R})^{n}$ , J. Funct. Anal. 177 (2) (2000) 282-309.
  * [5] Cabrelli C., Molter U., Paternostro V. and Philipp F. Dynamical sampling on finite index sets, Journal d’Analyse Mathématique, 140 (2019), 637-667.
  * [6] Cabrelli C., Molter U. and Suárez D. Multi-orbital frames through model spaces, Complex Analysis and Operator Theory 15, 16 (2021), 1-22.
  * [7] Carleson L. Interpolation by bounded analytic functions and the corona problem. Ann. of Math., 76 (1962), 547-559.
  * [8] Christensen O., Hasannasab M., and Philipp F., Frame properties of operator orbits, Math. Nachr. 293 (2020), 52-66.
  * [9] Douglas R. G., Muhly P. S. and Pearcy C. Lifting commuting operators. Michigan Math. J. I5 (1968), 385-395.
  * [10] Fuhrmann P. A. On the Corona Theorem and its Applications to Spectral Problems in Hilbert Space. T.A.M.S. Vol. 132, No. 1. (1968), 55-66.
  * [11] Garnett J. B. Bounded Analytic Functions, Graduate Texts in Mathematics, 236, Revised edition, Springer, (2006).
  * [12] Halmos P. R. Shifts on Hilbert spaces. J. Reine Angew. Math. 208 (1961), 102-112.
  * [13] H. Helson, and D. Lowdenslager, Invariant subspaces, Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), (1961), 251–262.
  * [14] Helson H. Lectures on Invariant subspaces. Academic Press, New York, (1964).
  * [15] Kadison R. V. Diagonalizing matrices. American J. of Math. Vol. 106, No. 6 (1984), 1451-1468
  * [16] Lax P. D. Translation invariant spaces. Acta Math., 101 (1959), 163-178.
  * [17] Nagata J. Modern Dimension Theory. Heldermann Verlag, Berlin, (1964).
  * [18] Srinivasan T.P., Double invariant subspaces, Pacific J. Math., 14, 2, (1964), 701–707.
  * [19] Sz.-Nagy B. and Foias C. Harmonic Analysis of Operators on Hilbert Space, North-Holland, Amsterdam, (1970).
  * [20] Tolokonnikov V. A. Estimates in the Carleson corona theorem, ideals of the algebra $H^{\infty}$, a problem of Sz.-Nagy, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 113 (1981), 178-198, 267, Investigations on linear operators and the theory of functions, XI.
  * [21] Zhu K. Operator Theory in Function spaces. Mathematical Surveys and Monographs Vol 138 2nd Edition, AMS (2007).


11institutetext:  University of Edinburgh, Edinburgh, UK
11email: {Weizhi.Tang<EMAIL_ADDRESS>
# LTLBench: Towards Benchmarks for Evaluating Temporal Logic Reasoning in
Large Language Models

Weizhi Tang  0009-0006-7444-292X Vaishak Belle  0000-0001-5573-8465

###### Abstract

Temporal reasoning (TR) is a critical component of artificial intelligence,
encompassing understanding and processing temporal information and
relationships between events. To discover and study the TR ability in Large
Language Models (LLMs), various datasets have been constructed in different
ways for evaluating various aspects of TR ability. Our work proposes a novel
approach to design and develop a pipeline for constructing datasets to
evaluate the TR ability of LLMs by leveraging random directed graph
generation, LTL formula, and the NuSMV model checker. Based on the pipeline,
we have also constructed a dataset as a benchmark, namely LTLBench, consisting
of 2,000 TR challenges and evaluated six LLMs with it. Furthermore, we have
conducted additional experiments to discover the impact of increasing the
number of events and formula operators on the complexity of TR problems and
the performance of LLMs. We have demonstrated that although LLMs exhibit some
promise in handling TR challenges, they still struggle with complex TR. We
expect this work can offer insights into TR ability in LLMs while also
providing a valuable tool for future TR evaluations.111The source code of the
study is open source and available at
https://github.com/RutaTang/LTLBench.222LTLBench is available at
https://huggingface.co/datasets/RutaTang/LTLBench.

###### Keywords:

Large Language Models Temporal Logic Reasoning Benchmark Dataset

##  1 Introduction

Temporal reasoning (TR) is a fundamental and critical aspect of artificial
intelligence, that encompasses understanding, processing, and reasoning about
the temporal information and relationships between events, which is essential
for handling and solving problems in various scenarios [20, 4, 27]. Recently,
Large Language Models (LLMs) have demonstrated and shown promise and emergence
of various reasoning abilities, including but not limited to mathematical
reasoning [9, 31, 12], commonsense reasoning [3, 31], and theory of mind
reasoning [21, 14, 23, 24]. Nevertheless, there still remains a lack of
definitive consensus regarding the emergence, performance, and robustness of
their ability to tackle TR challenges. Several studies have demonstrated that
although LLMs have shown some promise with TR ability, they still struggle
with TR and there is a substantial gap on the performance of handling and
solving TR challenges between the state-of-the-art LLMs and humans [5, 30, 2].
Furthermore, since TR ability is crucial for handling and processing temporal
information and relationships between temporal events and TR problems are
ubiquitous among many activities [27], for LLMs, in their frequently mentioned
and utilized scenario, question and answering, correctly comprehending
temporal information and handling temporal tasks is necessary and warranted to
provide efficient and helpful responses. In addition, LLMs are also discussed
and used in various ways such as embodied agent [18, 29, 17] for which
planning and decision making unavoidably intertwine with TR. Therefore, it is
necessary and important to study and discover the TR ability of LLMs.

In order to discover and evaluate the TR ability of LLMs, various benchmarks
have been developed in previous studies using various dataset construction
approaches, aiming at evaluating the TR ability of LLMs from different
perspectives and at different levels of complexity. For example, in [32], they
utilize GPT-3.5 to generate graph-based TR problems based on the temporal
knowledge graph YAGO11k [7]. Additionally, in [8], they employ random graph
generation as a foundation and preparation to form rule-based and different
types of temporal facts and questions. In order to further discover the TR
ability of LLMs and push the boundaries of evaluation of TR ability, we
proposed and designed a novel pipeline for TR dataset construction which
allows for the controllable and scalable generation of TR problems at any
level of complexity and size. Based on it, we have also generated and
constructed a dataset consisting of 2,000 TR problems as a benchmark, namely
LTLBench.

Inspired by [8], although our approach also involves random graph generation
as the prerequisite and preparation for subsequent problem generations, the
methodology differs a lot from it in terms of the usage of generated graphs
and subsequent problem generations. In our approach, a generated TR problem
mainly consists of a context that depicts the situation of a TR problem and a
hypothesis requiring LLMs to judge its validity against the given context of
the problem. In addition, the core components in the process of dataset
generation involve a randomly generated directed graph which forms the
preparation for subsequent problem generations, a random linear temporal logic
(LTL) formula that serves as the hypothesis regarding a given problem context,
and the NuSMV model checker [6] which allows for running the code which
represents the events, the transitions between events, and also the LTL
formula to provide the ground truth label for the TR problem.

It is worth noting that although complex LTL is always discussed and used in
the context of formal and program verification, basic and reasonably complex
LTL tasks are ubiquitous in many daily tasks. For example, if people are out
of milk, they will eventually buy it, which can be formalized in an LTL
formula as $G(\text{OutOfMilk}\rightarrow F(\text{BuyMilk}))$, and also if the
traffic light is green, it will then turn to yellow, which can be formalized
as $G(\text{Green}\rightarrow X(\text{Yellow})$.333Refer to [15] and [10] for
more details on LTL syntax and semantics. Therefore, LLMs are supposed to
handle reasonably complex LTL problems in order to provide efficient and
accurate responses. Therefore, we propose to use LTL, a subset of temporal
logic, to form reasonably complex hypotheses of TR problems.

In addition, as shown in Figure 1, during the generation process for a TR
problem, we first generate a random directed graph. Then, we adopted and
slightly modified the LTL formulas generation algorithm designed by [33] to
generate an LTL formula based on the events given in the graph. Subsequently,
we convert the information of events given in the graph and the LTL formula
into NuSMV [6] code and execute the code to obtain the ground truth label of
the TR problem. Finally, the information of events and the LTL formula are
converted into the TR problem in the form of natural language.

Figure 1: The overview of the TR problem generation pipeline

Furthermore, in order to intensively and comprehensively evaluate LLMs, we
selected six models of which three are the models with large parameter sizes
and three are the models with small parameter sizes, and evaluated them on
LTLBench consisting of 2,000 generated TR challenges. We demonstrated that
although LLMs have shown promise in handling TR challenges, they still
struggle with complex TR. In addition, we have also taken additional
experiments to discover how the number of events and operators may affect the
complexity of TR problems and the performance of LLMs. The key contributions
of our study are outlined as follows:

  1. 1.

We have designed and developed a novel pipeline based on the random directed
graph generation, LTL formula, and the NuSMV model checker for TR problem
generation and dataset construction. Based on it, we have also generated and
constructed a dataset, LTLBench, as a benchmark for evaluating the TR ability
of LLMs. The data generation process in the pipeline is controllable and
scalable, meaning it enables and allows for generating TR problems at any
level of complexity and size.

  2. 2.

We have also taken intensive and comprehensive experiments on six selected
models for which three are models with large parameter sizes and three are in
small parameter sizes and demonstrated that they still face significant
challenges when tackling complex TR problems.

##  2 Related Work

###  2.1 TR in LLMs

Temporal reasoning has recently obtained substantial attention and study [32,
8, 2, 5, 11, 16, 26]. In the work [2], they point out the deficiencies of LLMs
in terms of their ability to understand and handle temporal information and
reasoning. Additionally, in [32], they introduce and propose a framework, TG-
LLM, to improve the performance of LLMs in tackling TR tasks. Nevertheless,
the evaluation and enhancement of TR ability in LLMs are still in progress and
need more effort and study.

###  2.2 TR Benchmarks

To evaluate TR ability of LLMs, various TR datasets and benchmarks have been
developed and constructed in different approaches for evaluating different
aspects of TR ability of LLMs at varying levels of complexity [8, 30, 32, 2,
19, 22, 28]. For instance, in [32], a TR dataset is constructed by leveraging
a large temporal knowledge graph, YAGO11k [7], and utilizing GPT-3.5 and rule-
based Python script to generate TR challenges. However, in the work [8], they
leverage graph generation and use rule-based methods without introducing LLMs
to generate TR tasks, highlighting and focusing on temporal semantics and
arithmetic reasoning. Additionally, in [30], they introduce a TR dataset
consisting of various temporal aspects such as order, arithmetic, frequency,
and duration. Our work introduces a novel pipeline for generating TR problems
based on graph generation, LTL formula, and the NuSMV model checker, allowing
for the control of the complexity and size of problems.

##  3 TR Problem Generation Pipeline

The pipeline to generate a single TR problem consists of four stages: (1)
Random Directed Graph Generation, (2) LTL Formula Generation, (3) NuSMV Code
Generation, and (4) Natural Language Generation. Figure 1 demonstrates the
overview of the process for a TR problem generation.

###  3.1 Random Directed Graph Generation

During this stage, a directed graph is randomly generated with a given number
of events $n$ where $n>1$ to ensure the formation of transitions between
events.

In this graph, each $node_{i}$ represents an individual $event_{i}$, and each
$edge^{i}_{j}$ is a directed edge pointing from $node_{i}$ to another
$node_{j}$, which forms the relationships and transitions between events,
indicating that $event_{j}$ represented by $node_{j}$ can occur after the
$event_{i}$ represented by $node_{i}$. It is important to note that each
$node_{i}$ within the graph can have multiple outgoing edges, signifying that
several subsequent events can follow $event_{i}$, as well as multiple incoming
edges, indicating that $event_{i}$ can be preceded by several other events.

As an example illustrated in Figure 2, given $n=3$, three events are
generated: $event_{1}$, $event_{2}$, and $event_{3}$. The case that
$event_{1}$ points to $event_{2}$ indicates that $event_{2}$ can happen after
$event_{1}$. The case that $event_{1}$ points to $event_{3}$ and $event_{3}$
also points to $event_{1}$ means that $event_{1}$ can happen after $event_{3}$
and $event_{3}$ can happen after $event_{1}$. In addition, $event_{1}$ not
only points to $event_{2}$ but also $event_{3}$, indicating that both
$event_{2}$ and $event_{3}$ can happen after $event_{1}$.

The generation of the random directed graph during this stage serves as the
foundation and preparation for generating the LTL formula, NuSMV code, and TR
problem represented in natural language by providing the information of events
and also the transitions between events.

Figure 2: An example of a generated random directed graph

###  3.2 LTL Formula Generation

Based on the events generated in the graph, we employed and slightly modified
the algorithm designed by [33] to generate an LTL formula444Note: only one LTL
formula is generated for each given graph from the previous stage, meaning the
formulaCount parameter in Algorithm 1 is always 1. with a given number of
operators $m$ where $m>0$. The LTL operators include unary and binary
operators. Unary operators, for example, include but are not limited to $X$
which indicates that for a given event $\phi$, $X\phi$ denotes that the event
$\phi$ will occur at the next moment, and $F$ for which $F\phi$ means that
event $\phi$ will eventually occur at some point in the future. Binary
operators include but are not limited to $\&$ representing logical AND and $|$
representing logical OR. The given number of operators refers to the number of
unary and binary LTL operators contained in an LTL formula. The algorithm for
generating LTL formulas is detailed in Algorithm 1.

Algorithm 1 Generate LTL Formulas

1:procedure GenerateLTLFormulas($states,formulaLength,formulaCount$)

2:Input: $states$ \- an array of atomic states representing events

3:Input: $formulaLength$ \- the number of operators

4:Input: $formulaCount$ \- the number of formulas to generate

5:Output: an array of LTL formulas

6: $\textit{unaryOperators}\leftarrow[X,G,F,!]$

7: $\textit{binaryOperators}\leftarrow[\&,|,\rightarrow]$

8:
$\textit{operators}\leftarrow\textit{unaryOperators}+\textit{binaryOperators}$

9: $\textit{B}\leftarrow[[\;]\text{ of size }formulaLength+1$ ]

10: $\textit{B}[0]\leftarrow states$

11: $\textit{formulas}\leftarrow[\;]$

12: for $i\leftarrow 1$ to $formulaCount$ do

13: for $j\leftarrow 1$ to $formulaLength$ do

14: $x\leftarrow\text{randomly choose an operator from }\textit{operators}$

15: if $x\in\textit{unaryOperators}$ then

16: $y\leftarrow\text{ randomly sample a formula from }\textit{B}[j-1]$

17: $\textit{newFormula}\leftarrow[x,y]$

18: else

19: $s\leftarrow\text{randomly sample a integer from }[0,j)$

20: $y1\leftarrow\text{randomly sample a formula from }\textit{B}[s]$

21: $y2\leftarrow\text{randomly sample a formula from }\textit{B}[j-1-s]$

22: $\textit{newFormula}\leftarrow[y1,x,y2]$

23: end if

24: $\text{append }\textit{newFormula}\text{ to }\textit{B}[j]$

25: end for

26: $\textit{formula}\leftarrow\textit{B}[formulaLength][-1]$

27: append formula to formulas

28: end for

29: return formulas

30:end procedure

An example of a generated LTL formula is also provided and shown in Listing 1.
The formula means that if $event_{1}$ happens, it will be globally true that,
at some point in the future, $event_{2}$ will eventually happen.

⬇

1(event1 -> (G (F event2)))

Listing 1: An example of a generated LTL formula

The generation of the LTL formula aims to be the preparation for generating
the LTLSPEC part of the NuSMV code and also to generate the hypothesis part of
the TR problem represented in natural language.

###  3.3 NuSMV Code Generation

Given the information of events from the graph and the LTL formula, this stage
aims at converting and representing them in NuSMV code. The generation of the
NuSMV code is divided into two parts: (1) context generation and (2) LTLSPEC
generation. The context describes the situation of the TR problem while
LTLSPEC represents a hypothesis regarding the context.

For the context generation, it includes event definitions, initial event
setup, and event transitions setup. Based on the generated graph, the events
and their transitions are converted into the context part of the NuSMV code
while an initial event is set up randomly and also converted into the NuSMV
code. As shown in Listing 2, Lines 2-3 define the three events, Line 5 sets up
the initial event which is $event_{3}$, and Lines 6-12 construct the
transitions of events in which, for instance, Line 7 shows that $event_{2}$
can follow $event_{1}$. In addition, Line 11 indicates that $event_{2}$
remains to itself and after $event_{2}$, no other events can happen, if there
is no other transition specified from $event_{2}$ to $event_{i}$ where $i\neq
2$.

For LTLSPEC generation, we convert the generated LTL formula into code that
complies with NuSMV, as illustrated at Line 13 in Listing 2 which represents
the LTL formula shown in Listing 1.

The generation of the NuSMV code aims at providing the ground truth label for
the TR problem. The generated code will be executed by the NuSMV model checker
to give the ground truth label during the generation process.

⬇

1MODULE main

2VAR

3 state : {event1, event2, event3};

4ASSIGN

5 init(state) := event3;

6 next(state) := case

7 state = event1 : event2;

8 state = event1 : event3;

9 state = event3 : event1;

10 state = event3 : event2;

11 state = event2 : event2;

12 esac;

13LTLSPEC ((state=event1) -> (G (F (state=event2))))

Listing 2: An example of NuSMV code

###  3.4 Natural Language Generation

During this stage, the events information in the graph and the LTL formula
will be converted and represented in natural language. Similar to the NuSMV
code generation, this stage can also be divided into two parts: (1) context
generation and (2) hypothesis generation. The context describes the situation
of the problem while the hypothesis is what the LLMs need to judge for
validity against the given situation.

For context generation, based on the generated graph and the initial event, we
convert the information of events and their transitions into natural language.
As shown at Lines 1-4 in Listing 3, the initial event and events transitions
are converted and described in natural language.

For hypothesis generation, we transform the generated LTL formula into natural
language as shown at Lines 5-10 in Listing 3. Additionally, Line 11 is used to
prompt LLMs to judge the validity of the hypothesis, requiring an answer in
"True" or "False" format.

The TR problem represented in natural language generated in this stage is the
core and final product of the generation process, which will be used to
evaluate the TR ability of LLMs.

⬇

1=== Context ===

2

3Initially, event3 happened. After event1, event2 can happen. After event1,
event3 can happen. After event2, no other events can happen. After event3,
event1 can happen. After event3, event2 can happen.

4

5=== Hypothesis ===

6

7C1: Event2 will happen eventually.

8C2: C1 will always be true at any future time.

9C3: That event1 happens implies that C2 holds.

10

11C3 is True or False? Answer with "True" or "False" directly:

Listing 3: An example of TR problem in the form of natural language

##  4 Experiment Settings

To evaluate the TR ability of LLMs, based on the pipeline, we generated and
constructed a dataset, LTLBench, consisting of 2,000 problems. Each problem
features the number of events $n=3$ and the number of formula operators $m=3$.
Additionally, to explore the impact of changes in the number of formula
operators, we conducted evaluations on newly generated problems with the fixed
number of events $n=2$ while varying the number of formula operators for which
$m\in\\{1,2,3,4,5,7,9\\}$. For each $(n,m_{i})$, such as $(2,1)$ indicating
that the number of events is 2 and the number of operators is 1, there are 300
problems generated as a dataset for evaluation. Similarly, we fixed the number
of formula operators $m=2$ and varied the number of events for which
$n\in\\{2,3,4,5,7,9\\}$ to examine the effects of changing the number of
events while keeping the number of operators constant. In addition, for all
generated datasets, their distributions of ground truth labels are
meticulously balanced, meaning half of the problems are labeled as True while
half of the problems are labeled as False.

Furthermore, for comprehensive evaluations, we selected six models. Three of
them are in larger parameter sizes including GPT-3.5 Turbo noted as
gpt-3.5-turbo, Llama 3 for which we choose its instruct model with 70 billion
parameters noted as llama3:70b-instruct, and Qwen [1] for which we utilize its
chat model with 72 billion parameters noted as qwen:72b-chat. In addition, we
also choose three models in smaller parameter sizes comprising Gemma [25] for
which we use its instruct model with 7 billion parameters noted as
gemma:7b-instruct, Mistral [13] for which we choose its instruct model with 7
billion parameters noted as mistral:7b-instruct, and Qwen [1] for which we use
its chat model with 7 billion parameters noted as qwen:7b-chat. This selection
is intended for assessing the performance variability of handling TR
challenges across models with different parameter sizes. In addition, the
temperature hyperparameter for all selected models is set to 0 to keep the
responses deterministic and also to ensure that the models consistently select
the optimal next token.

##  5 Results and Analyses

###  5.1 Evaluation with LTLBench

We have evaluated the selected models on LTLBench which consists of 2,000
generated TR problems with the number of events $n=3$ and the number of
formula operators $m=3$. The metrics consisting of Accuracy, F1, and AUC are
shown in Table 1.

From the metrics, all Accuracy and AUC of LLMs are above 0.5. In addition, the
model, qwen:72b-chat, demonstrates the highest Accuracy at 0.60, F1 at 0.59,
and AUC at 0.60 while the llama3:70b-instruct also shows a similar
performance. It may indicate that they show promise and ability to handle TR
challenges. Nevertheless, the modest metrics signify that they still struggle
with complex TR problems.

In addition, the averages of Accuracy, F1, and AUC for the models with large
parameter sizes are 0.58, 0.58, and 0.58 respectively, while for the models
with small parameter sizes, they are 0.54, 0.52, and 0.54 respectively. It
unsurprisingly indicates that models with large parameter sizes may surpass
the models with small parameter sizes when handling these complex TR
challenges, although the difference between the performance is modest.

Table 1: The metrics of LLMs on LTLBench Models |  Accuracy |  F1 |  AUC
---|---|---|---
gpt-3.5-turbo |  0.56 |  0.55 |  0.56
llama3:70b-instruct |  0.59 |  0.59 |  0.59
qwen:72b-chat |  0.60 |  0.59 |  0.60
gemma:7b-instruct |  0.55 |  0.53 |  0.55
qwen:7b-chat |  0.54 |  0.54 |  0.54
mistral:7b-instruct |  0.54 |  0.50 |  0.54

###  5.2 Impact of increasing $m$

The selected models are also evaluated on the additional constructed datasets,
where the number of events is fixed to $n=2$ while the number of formula
operator $m$ increases from 1 to 9, specifically $m\in\\{1,2,3,4,5,7,9\\}$.
The performance in terms of Accuracy and AUC of the evaluated models is shown
in Figure 3.

(a) Accuracy

(b) AUC

Figure 3: Accuracy and AUC when increasing the number of operators

As shown in Figure 3, the accuracy of models significantly drops from $m=1$ to
$m=2$ regardless of the models with large parameter sizes or models with small
parameter sizes. It is also the same case for AUC as shown in Figure 3.
Although several models can have a good performance when $m=1$ such as
gpt-3.5-turbo and qwen:72b-chat, they suffer from TR tasks when $m$ increases.
It indicates that increasing the number of formula operators may significantly
introduce more complexity of TR and the TR ability of LLMs is currently still
lacking consistency and robustness when TR tasks become more complex.

Furthermore, it is obvious to note that models with large parameter sizes
outperform all other models with small parameter sizes when $m=1$. However,
they show indifferent performance when $m$ increases while the AUC decreases
and approaches to 0.5, signifying that all models start random guessing.

###  5.3 Impact of increasing $n$

In addition, the selected models are also evaluated with the number of formula
operators fixed to $m=2$ while the number of events $n$ where $n>1$ increases
from 2 to 9, specifically $n\in\\{2,3,4,5,7,9\\}$. The performance in terms of
Accuracy and AUC of the evaluated models is shown in Figure 4.

(a) Accuracy

(b) AUC

Figure 4: Accuracy and AUC when increasing the number of events

As shown in Figure 4 and Figure 4, the Accuracy and AUC of models show a trend
to decrease while the number of events increases. Although it is not as
obvious and significant as the case when $n$ is fixed and $m$ increases, it
still indicates that increasing the number of events will also introduce a
certain level of complexity. In addition, as the same case discussed in
Section 5.2, as the number of events increases, models with large parameter
sizes show indifferent performance to the models with small parameter sizes
since their AUC approaches 0.5, indicating random guessing.

##  6 Implications

We designed a pipeline for constructing TR datasets to evaluate the TR ability
of LLMs. The pipeline is controllable and scalable to be able to introduce any
level of complexity of TR by modifying the number of events and the number of
formula operators. Future work can leverage this pipeline to generate TR
problems at a certain level of complexity depending on specific needs.

In addition, since TR is crucial in many scenarios, we hope this work can not
only offer insights into the TR ability of LLMs but also provide a valuable
tool to further evaluate the TR ability of future LLMs or other AI systems
that are required to equip with a certain level of TR ability, thus, to enable
confident deployment and application.

##  7 Limitations and Future Work

Considering the difficulty of generated TR problems, we only included a subset
of LTL operators in the TR problem generation pipeline but excluded several
LTL operators such as $U$ (Until) and $R$ (Release). However, adding and
incorporating more LTL operators should be easy and straightforward to enable
future work to evaluate the more complex TR ability of LLMs.

In addition, although we have intensively and comprehensively evaluated six
models, due to the unavoidable heavy computation costs, we did not run the
evaluation on GPT-4 and other LLMs exhaustively. Nevertheless, future work can
easily leverage the pipeline and the constructed dateset, LTLBench, in this
work to evaluate GPT-4 and other LLMs.

##  8 Conclusion

In this study, we designed a pipeline for generating and constructing the TR
datasets based on the random graph generation, LTL formula, and the NuSMV
model checker. Based on the pipeline, we have generated a dataset, LTLBench,
consisting of 2,000 TR challenges and taken intensive and comprehensive
evaluations on it with the six selected models in which three are the models
with large parameter sizes while the other three models are in small parameter
sizes. We have demonstrated that although LLMs show promise and emergence in
handling the TR problem, they still struggle with it. We expect our work to
offer insights into the TR ability of LLMs and to provide a valuable tool for
TR evaluation while hoping it can pave the way for future more intelligent
LLMs or AI systems requiring handling complex TR tasks.

## References

  * [1] Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang, F., Hui, B., Ji, L., Li, M., Lin, J., Lin, R., Liu, D., Liu, G., Lu, C., Lu, K., Ma, J., Men, R., Ren, X., Ren, X., Tan, C., Tan, S., Tu, J., Wang, P., Wang, S., Wang, W., Wu, S., Xu, B., Xu, J., Yang, A., Yang, H., Yang, J., Yang, S., Yao, Y., Yu, B., Yuan, H., Yuan, Z., Zhang, J., Zhang, X., Zhang, Y., Zhang, Z., Zhou, C., Zhou, J., Zhou, X., Zhu, T.: Qwen technical report (arXiv:2309.16609) (Sep 2023), http://arxiv.org/abs/2309.16609, arXiv:2309.16609 [cs]
  * [2] Beniwal, H.: Remember this event that year? assessing temporal information and reasoning in large language models
  * [3] Bian, N., Han, X., Sun, L., Lin, H., Lu, Y., He, B., Jiang, S., Dong, B.: ChatGPT is a knowledgeable but inexperienced solver: An investigation of commonsense problem in large language models. In: Calzolari, N., Kan, M.Y., Hoste, V., Lenci, A., Sakti, S., Xue, N. (eds.) Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024). pp. 3098–3110. ELRA and ICCL, Torino, Italia (May 2024), https://aclanthology.org/2024.lrec-main.276
  * [4] Chittaro, L., Montanari, A.: Temporal representation and reasoning in artificial intelligence: Issues and approaches. Annals of Mathematics and Artificial Intelligence 28(1), 47–106 (2000)
  * [5] Chu, Z., Chen, J., Chen, Q., Yu, W., Wang, H., Liu, M., Qin, B.: Timebench: A comprehensive evaluation of temporal reasoning abilities in large language models (arXiv:2311.17667) (Nov 2023), http://arxiv.org/abs/2311.17667, arXiv:2311.17667 [cs]
  * [6] Cimatti, A., Clarke, E., Giunchiglia, E., Giunchiglia, F., Pistore, M., Roveri, M., Sebastiani, R., Tacchella, A.: NuSMV Version 2: An OpenSource Tool for Symbolic Model Checking. In: Proc. International Conference on Computer-Aided Verification (CAV 2002). LNCS, vol. 2404. Springer, Copenhagen, Denmark (July 2002)
  * [7] Dasgupta, S.S., Ray, S.N., Talukdar, P.: HyTE: Hyperplane-based temporally aware knowledge graph embedding. In: Riloff, E., Chiang, D., Hockenmaier, J., Tsujii, J. (eds.) Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. pp. 2001–2011. Association for Computational Linguistics, Brussels, Belgium (Oct-Nov 2018). https://doi.org/10.18653/v1/D18-1225, https://aclanthology.org/D18-1225
  * [8] Fatemi, B., Kazemi, M., Tsitsulin, A., Malkan, K., Yim, J., Palowitch, J., Seo, S., Halcrow, J., Perozzi, B.: Test of time: A benchmark for evaluating llms on temporal reasoning
  * [9] Gaur, V., Saunshi, N.: Reasoning in large language models through symbolic math word problems. In: Rogers, A., Boyd-Graber, J., Okazaki, N. (eds.) Findings of the Association for Computational Linguistics: ACL 2023. pp. 5889–5903. Association for Computational Linguistics, Toronto, Canada (Jul 2023). https://doi.org/10.18653/v1/2023.findings-acl.364, https://aclanthology.org/2023.findings-acl.364
  * [10] Goranko, V., Rumberg, A.: Temporal Logic. In: Zalta, E.N., Nodelman, U. (eds.) The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2024 edn. (2024)
  * [11] Hu, X., Chen, J., Li, X., Guo, Y., Wen, L., Yu, P.S., Guo, Z.: Do large language models know about facts?
  * [12] Imani, S., Du, L., Shrivastava, H.: MathPrompter: Mathematical reasoning using large language models. In: Sitaram, S., Beigman Klebanov, B., Williams, J.D. (eds.) Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track). pp. 37–42. Association for Computational Linguistics, Toronto, Canada (Jul 2023). https://doi.org/10.18653/v1/2023.acl-industry.4, https://aclanthology.org/2023.acl-industry.4
  * [13] Jiang, A.Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D.S., Casas, D.d.l., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., Lavaud, L.R., Lachaux, M.A., Stock, P., Scao, T.L., Lavril, T., Wang, T., Lacroix, T., Sayed, W.E.: Mistral 7b (arXiv:2310.06825) (Oct 2023), http://arxiv.org/abs/2310.06825, arXiv:2310.06825 [cs]
  * [14] Kosinski, M.: Evaluating large language models in theory of mind tasks (2023). https://doi.org/10.48550/ARXIV.2302.02083, https://arxiv.org/abs/2302.02083
  * [15] Kröger, F., Merz, S.: Temporal logic and state systems. Texts in theoretical computer science: An EATCS series, Springer, Berlin (2008)
  * [16] Liu, J.X., Yang, Z., Idrees, I., Liang, S., Schornstein, B., Tellex, S., Shah, A.: Grounding complex natural language commands for temporal tasks in unseen environments
  * [17] Liu, J.X., Yang, Z., Idrees, I., Liang, S., Schornstein, B., Tellex, S., Shah, A.: Grounding complex natural language commands for temporal tasks in unseen environments (arXiv:2302.11649) (Oct 2023), http://arxiv.org/abs/2302.11649, arXiv:2302.11649 [cs]
  * [18] Liu, X., Yu, H., Zhang, H., Xu, Y., Lei, X., Lai, H., Gu, Y., Ding, H., Men, K., Yang, K., Zhang, S., Deng, X., Zeng, A., Du, Z., Zhang, C., Shen, S., Zhang, T., Su, Y., Sun, H., Huang, M., Dong, Y., Tang, J.: Agentbench: Evaluating llms as agents (arXiv:2308.03688) (Oct 2023), http://arxiv.org/abs/2308.03688, arXiv:2308.03688 [cs]
  * [19] Qin, L., Gupta, A., Upadhyay, S., He, L., Choi, Y., Faruqui, M.: Timedial: Temporal commonsense reasoning in dialog. In: Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). p. 7066–7076. Association for Computational Linguistics, Online (2021). https://doi.org/10.18653/v1/2021.acl-long.549, https://aclanthology.org/2021.acl-long.549
  * [20] Shoham, Y., Goyal, N.: Chapter 11 - temporal reasoning in artificial intelligence. In: Shrobe, H.E., the American Association for Artificial Intelligence (eds.) Exploring Artificial Intelligence, pp. 419–438. Morgan Kaufmann (1988). https://doi.org/https://doi.org/10.1016/B978-0-934613-67-5.50015-0, https://www.sciencedirect.com/science/article/pii/B9780934613675500150
  * [21] Strachan, J.W.A., Albergo, D., Borghini, G., Pansardi, O., Scaliti, E., Gupta, S., Saxena, K., Rufo, A., Panzeri, S., Manzi, G., Graziano, M.S.A., Becchio, C.: Testing theory of mind in large language models and humans. Nature Human Behaviour (May 2024). https://doi.org/10.1038/s41562-024-01882-z, https://www.nature.com/articles/s41562-024-01882-z
  * [22] Tan, Q., Ng, H.T., Bing, L.: Towards benchmarking and improving the temporal reasoning capability of large language models. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). p. 14820–14835. Association for Computational Linguistics, Toronto, Canada (2023). https://doi.org/10.18653/v1/2023.acl-long.828, https://aclanthology.org/2023.acl-long.828
  * [23] Tang, W., Belle, V.: Tom-lm: Delegating theory of mind reasoning to external symbolic executors in large language models. arXiv preprint arXiv:2404.15515 (2024)
  * [24] Tang, W., Belle, V.: Zero, finite, and infinite belief history of theory of mind reasoning in large language models. arXiv preprint arXiv:2406.04800 (2024)
  * [25] Team, G., Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre, L., Rivière, M., Kale, M.S., Love, J., Tafti, P., Hussenot, L., Sessa, P.G., Chowdhery, A., Roberts, A., Barua, A., Botev, A., Castro-Ros, A., Slone, A., Héliou, A., Tacchetti, A., Bulanova, A., Paterson, A., Tsai, B., Shahriari, B., Lan, C.L., Choquette-Choo, C.A., Crepy, C., Cer, D., Ippolito, D., Reid, D., Buchatskaya, E., Ni, E., Noland, E., Yan, G., Tucker, G., Muraru, G.C., Rozhdestvenskiy, G., Michalewski, H., Tenney, I., Grishchenko, I., Austin, J., Keeling, J., Labanowski, J., Lespiau, J.B., Stanway, J., Brennan, J., Chen, J., Ferret, J., Chiu, J., Mao-Jones, J., Lee, K., Yu, K., Millican, K., Sjoesund, L.L., Lee, L., Dixon, L., Reid, M., Mikuła, M., Wirth, M., Sharman, M., Chinaev, N., Thain, N., Bachem, O., Chang, O., Wahltinez, O., Bailey, P., Michel, P., Yotov, P., Chaabouni, R., Comanescu, R., Jana, R., Anil, R., McIlroy, R., Liu, R., Mullins, R., Smith, S.L., Borgeaud, S., Girgin, S., Douglas, S., Pandya, S., Shakeri, S., De, S., Klimenko, T., Hennigan, T., Feinberg, V., Stokowiec, W., Chen, Y.h., Ahmed, Z., Gong, Z., Warkentin, T., Peran, L., Giang, M., Farabet, C., Vinyals, O., Dean, J., Kavukcuoglu, K., Hassabis, D., Ghahramani, Z., Eck, D., Barral, J., Pereira, F., Collins, E., Joulin, A., Fiedel, N., Senter, E., Andreev, A., Kenealy, K.: Gemma: Open models based on gemini research and technology (arXiv:2403.08295) (Apr 2024), http://arxiv.org/abs/2403.08295, arXiv:2403.08295 [cs]
  * [26] Vashishtha, S., Poliak, A., Lal, Y.K., Van Durme, B., White, A.S.: Temporal reasoning in natural language inference. In: Findings of the Association for Computational Linguistics: EMNLP 2020. p. 4070–4078. Association for Computational Linguistics, Online (2020). https://doi.org/10.18653/v1/2020.findings-emnlp.363, https://www.aclweb.org/anthology/2020.findings-emnlp.363
  * [27] Vila, L.: A survey on temporal reasoning in artificial intelligence. Ai Communications 7(1), 4–28 (1994)
  * [28] Virgo, F., Cheng, F., Kurohashi, S.: Improving event duration question answering by leveraging existing temporal information extraction data
  * [29] Wang, G., Xie, Y., Jiang, Y., Mandlekar, A., Xiao, C., Zhu, Y., Fan, L., Anandkumar, A.: Voyager: An open-ended embodied agent with large language models (arXiv:2305.16291) (Oct 2023), http://arxiv.org/abs/2305.16291, arXiv:2305.16291 [cs]
  * [30] Wang, Y., Zhao, Y.: Tram: Benchmarking temporal reasoning for large language models (arXiv:2310.00835) (May 2024), http://arxiv.org/abs/2310.00835, arXiv:2310.00835 [cs]
  * [31] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., Zhou, D.: Chain-of-thought prompting elicits reasoning in large language models (2022). https://doi.org/10.48550/ARXIV.2201.11903, https://arxiv.org/abs/2201.11903
  * [32] Xiong, S., Payani, A., Kompella, R., Fekri, F.: Large language models can learn temporal reasoning (arXiv:2401.06853) (Jun 2024), http://arxiv.org/abs/2401.06853, arXiv:2401.06853 [cs]
  * [33] Zhu, W.: Big data on linear temporal logic formulas. In: 2021 IEEE 4th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC). p. 544–547. IEEE, Chongqing, China (Jun 2021). https://doi.org/10.1109/IMCEC51613.2021.9482368, https://ieeexplore.ieee.org/document/9482368/