One of the most notorious open problems in functional analysis is the invariant subspace problem for Hilbert spaces, which I will state here as a conjecture:

Conjecture 1 (Invariant Subspace Problem, ISP0) Let {H} be an infinite dimensional complex Hilbert space, and let {T: H \rightarrow H} be a bounded linear operator. Then {H} contains a proper closed invariant subspace {V} (thus {TV \subset V}).

As stated this conjecture is quite infinitary in nature. Just for fun, I set myself the task of trying to find an equivalent reformulation of this conjecture that only involved finite-dimensional spaces and operators. This turned out to be somewhat difficult, but not entirely impossible, if one adopts a sufficiently generous version of “finitary” (cf. my discussion of how to finitise the infinitary pigeonhole principle). Unfortunately, the finitary formulation that I arrived at ended up being rather complicated (in particular, involving the concept of a “barrier”), and did not obviously suggest a path to resolving the conjecture; but it did at least provide some simpler finitary consequences of the conjecture which might be worth focusing on as subproblems.

I should point out that the arguments here are quite “soft” in nature and are not really addressing the heart of the invariant subspace problem; but I think it is still of interest to observe that this problem is not purely an infinitary problem, and does have some non-trivial finitary consequences.

I am indebted to Henry Towsner for many discussions on this topic.

— 1. Initial reductions —

The first reduction is to get rid of the closed invariant subspace {V}, as this will be the most difficult object to finitise. We rephrase ISP0 as

Conjecture 2 (Invariant Subspace Problem, ISP1) Let {H} be an infinite dimensional complex Hilbert space, and let {T: H \rightarrow H} be a bounded linear operator. Then there exist unit vectors {v, w \in H} such that {\langle T^n v, w \rangle = 0} for all natural numbers {n \in {\bf N}}.

Indeed, to see that ISP1 implies ISP0, we simply take {V} to be the closed invariant subspace generated by the orbit {v, Tv, T^2 v, \ldots}, which is proper since it is orthogonal to {w}. To see that ISP0 implies ISP1, we let {v} be an arbitrary unit vector in the invariant subspace {V}, and {w} be an arbitrary unit vector in the orthogonal complement {V^\perp}.

The claim is obvious if {H} is not separable (just let {v} be arbitrary, and {w} to be a normal vector to the separable space spanned by {v, Tv, T^2 v, \ldots}), so we may normalise {H} to be {\ell^2({\bf N})}. We may also normalise {T} to be a contraction (thus {\|T\|_{op} \leq 1}), and let {(a_{ij})_{i,j \geq 1}} be the coefficients of {T}.

The next step is to restrict {T} to a compact space of operators. Define a growth function to be a monotone increasing function {F: {\bf N} \rightarrow {\bf N}}. Given any growth function {F}, we say that a linear contraction {T: \ell^2({\bf N}) \rightarrow \ell^2({\bf N})} with coefficients {(a_{ij})_{i,j \geq 1}} is {F}-tight if one has the bound

\displaystyle \sup_{1 \leq i \leq N} \sum_{j \geq F(N)} |a_{ij}|^2 \leq \frac{1}{N} \ \ \ \ \ (1)

and

\displaystyle \sup_{1 \leq j \leq N} \sum_{i \geq F(N)} |a_{ij}|^2 \leq \frac{1}{N}. \ \ \ \ \ (2)

For instance, if the matrix {(a_{ij})_{i,j \geq 1}} is band-limited to the region {|j-i| \leq 10}, it is {F}-tight with {F(N) := N+11}. If it is limited to the region {i/2 \leq j \leq 2i}, then it is {F}-tight with {F(N) := 2N+1}. So one can view {F}-tightness as a weak version of the band-limited property.

The significance of this concept lies in the following lemma:

Lemma 3 (Sequential compactness)

  • (i) Every contraction {T: \ell^2({\bf N}) \rightarrow \ell^2({\bf N})} is {F}-tight with respect to at least one growth function {F}.
  • (ii) If {F} is a growth function and {T_1, T_2, \ldots} is a sequence of {F}-tight contractions, then there exists a subsequence {T_{n_k}} which converges in the strong operator topology to an {F}-tight contraction {T}. Furthermore, the adjoints {T_{n_k}^*} converge in the strong operator topology to {T^*}.

Proof: To prove (i), observe that if {T} is a contraction and {N \geq 1}, then

\displaystyle \sup_{1 \leq i \leq N} \sum_{j=1}^\infty |a_{ij}|^2 \leq 1

and

\displaystyle \sup_{1 \leq j \leq N} \sum_{i=1}^\infty |a_{ij}|^2 \leq 1

and hence by the monotone convergence theorem we can find {F(N)} such that (1), (2). By increasing {F(N)} as necessary one can make {F} monotone.

To prove (ii), we apply the usual Arzelá-Ascoli diagonalisation argument to extract a subsequence {T_{n_k} = (a_{i,j,n_k})_{i,j \geq 1}} that converges componentwise (i.e. in the weak operator topology) to a limit {T = (a_{i,j})_{i,j \geq 1}}. From Fatou’s lemma we see that {T} is an {F}-tight contraction. From the tightness one can upgrade the weak operator topology convergence to strong operator topology convergence (i.e.

\displaystyle \lim_{k \rightarrow \infty} \sum_{j=1}^\infty |a_{i,j,n_k} - a_{i,j}|^2 = 0

for all {i}) by standard arguments, and similarly for the adjoints. \Box

We will similarly need a way to compactify the unit vectors {v, w}. If {F} is a growth function and {0 < N_1 < N_2 < N_3 < \ldots} are natural numbers, we say that a unit vector {v = (v_i)_{i=1}^\infty} is {F,N_1,N_2,\ldots}-tight if one has

\displaystyle \sum_{i \geq N_k} |v_i|^2 \leq \frac{1}{F(N_{k-1})} \ \ \ \ \ (3)

for all {k \geq 1}, with the convention that {N_0=0}. Similarly, we say that {v} is {F,N_1,\ldots,N_K}-tight if one has (3) for all {1 \leq k \leq K}. One has the following variant of Lemma 3:

Lemma 4 (Sequential compactness) Let {F} be a growth function.

  • (i) Every unit vector {v} is {F,N_1,N_2,\ldots}-tight with respect to at least one increasing sequence {0 < N_1 < N_2 < \ldots}. In fact any finite number of unit vectors {v_1,\ldots,v_m} can be made {F,N_1,N_2,\ldots}-tight with the same increasing sequence {0 < N_1 < N_2 < \ldots}.
  • (ii) If {0 < N_1 < N_2 < \ldots}, and for each {k \geq 1}, {v_k} is a {F,N_1,\ldots,N_k}-tight unit vector, then there exists a subsequence {v_{n_l}} of {v_k} that converges strongly to an {F,N_1,N_2,\ldots}-tight unit vector {v}.

The proof of this lemma is routine and is omitted.

In view of these two lemmas, ISP0 or ISP1 is equivalent to

Conjecture 5 (Invariant Subspace Problem, ISP2) Let {F} be a growth function, and let {T = (a_{ij})_{i,j \geq 1}} be an {F}-tight contraction. Then there exist a sequence {0 < N_1 < N_2 < \ldots} and a pair of {F,N_1,N_2,\ldots}-tight unit vectors {v, w \in \ell^2({\bf N})} such that {\langle T^n v, w \rangle = 0} for all natural numbers {n \in {\bf N}}.

The compactness given by the {F}-tightness and {F,N_1,N_2,\ldots} will be useful for finitising later.

— 2. Finitising —

Now we need a more complicated object.

Definition 6 A barrier is a family {{\mathcal T}} of finite tuples {(N_1, \ldots, N_m)} of increasing natural numbers {0 < N_1 < \ldots < N_m}, such that

  • (i) Every infinite sequence {N_1 < N_2 < \ldots} of natural numbers has at least one initial segment {(N_1,\ldots,N_m)} in {{\mathcal T}}; and
  • (ii) If {(N_1,\ldots,N_m)} is a sequence in {{\mathcal T}}, then no initial segment {(N_1,\ldots,N_{m'})} with {m' < m} lies in {{\mathcal T}}.

I learned the terminology “barrier” after asking this question on MathOverflow. Examples of barriers include

  • The family of all tuples {(N_1,\ldots,N_m)} of increasing natural numbers with {m=10};
  • The family of all tuples {(N_1,\ldots,N_m)} of increasing natural numbers with {m=N_1+1};
  • The family of all tuples {(N_1,\ldots,N_m)} of increasing natural numbers with {m=N_{N_1+1}+1}.

We now claim that ISP2 is equivalent to the following finitary statement. Let {\ell^2(N) \equiv {\bf C}^N} denote the {\ell^2} space on {\{1,\ldots,N\}}.

Conjecture 7 (Finitary invariant subspace problem, FISP0) Let {F} be a growth function, and let {{\mathcal T}} be a barrier. Then there exists a natural number {N_*} such that for every {F}-tight contraction {T: \ell^2(F(N_*)) \rightarrow \ell^2(F(N_*))}, there exists a tuple {(N_1,\ldots,N_m)} in {{\mathcal T}} with {0 < N_1 < \ldots < N_m < N_*}, and {F,N_1,\ldots,N_m}-tight unit vectors {v, w \in \ell^2(F(N_*))}, such that {|\langle T^n v, w \rangle| \leq \frac{1}{F(N_m)}} for all {0 \leq n \leq F(N_m)}.

We now show that ISP2 and FISP0 are equivalent.

Proof of ISP2 assuming FISP0. Let {F} be a growth function, and let {T} be an {F}-tight contraction. Let {{\mathcal T}'} denote the set of all tuples {0 < N_1 < \ldots < N_m} with {m > 1} such that there does not exist {F,N_1,\ldots,N_m}-tight unit vectors {v, w \in \ell^2({\bf N})} such that {|\langle T^n v, w \rangle| \leq \frac{2}{m}} holds for all {0 \leq n \leq m}. Let {{\mathcal T}} be those elements of {{\mathcal T}'} that contain no proper initial segment in {{\mathcal T}'}.

Suppose first that {{\mathcal T}} is not a barrier. Then there exists an infinite sequence {0 < N_1 < N_2 < \ldots} such that {(N_1,\ldots,N_m) \not \in {\mathcal T}} for all {m}, and thus {(N_1,\ldots,N_m) \not \in {\mathcal T}'} for all {m}. In other words, for each {m} there exists {F,N_1,\ldots,N_m}-tight unit vectors {v_m,w_m \in \ell^2({\bf N})} such that {|\langle T^n v_m, w_m \rangle| \leq \frac{2}{m}} for all {0 \leq n \leq m}. By Lemma 4, we can find a subsequence {v_{m_j}, w_{m_j}} that converge strongly to {F,N_1,N_2,\ldots}-tight unit vectors {v, w}. We conclude that {\langle T^n v, w \rangle=0} for all {n \geq 0}, and ISP2 follows.

Now suppose instead that {{\mathcal T}} is a barrier. Let {F'} be a growth function larger than {F} to be chosen later. Then the {F}-tight contraction {T} is also {F'}-tight, as is the restriction {T|_N: \ell^2(N) \rightarrow \ell^2(N)} of {T} to any finite subspace. Using FISP0, we can thus find {0 < N_1 < \ldots < N_m < N_*} with {(N_1,\ldots,N_m) \in {\mathcal T}} and {F',N_1,\ldots,N_m}-tight unit vectors {v, w \in \ell^2(F'(N_*))} such that

\displaystyle |\langle (T|_{F'(N_m)})^n v, w \rangle| \leq \frac{1}{F'(N_m)}

for all {0 \leq n \leq F'(N_m)}, and in particular for all {0 \leq n \leq m}. Note that {v, w} are almost in {\ell^2(N_m)}, up to an error of {1/F'(N_{m-1})}. From this and the {F}-tightness of the contraction {T}, we see (if {F'} is sufficiently rapid) that {(T|_{F'(N_m)})^n v} and {T^n v} differ by at most {1/m} for {0 \leq n \leq m}. We conclude that

\displaystyle |\langle T^n v, w \rangle| \leq \frac{2}{m},

and so {(N_1,\ldots,N_m) \not \in {\mathcal T}}, a contradiction. This yields the proof of ISP2 assuming FISP0.

Proof of FISP0 assuming ISP2. Suppose that FISP0 fails. Then there exists a growth function {F} and a barrier {{\mathcal T}} such that, for every {N_*}, there exists an {F}-tight contraction {T_{N_*}: \ell^2(F(N_*)) \rightarrow \ell^2(F(N_*))} such that there does not exist any tuples {(N_1,\ldots,N_m)} in {{\mathcal T}} with {0 < N_1 < \ldots < N_m < N_*}, and {F,N_1,\ldots,N_m}-tight unit vectors {v, w \in \ell^2(F(N_*))}, such that {|\langle T^n v, w \rangle| \leq \frac{1}{F(N_m)}} for all {0 \leq n \leq F(N_m)}.

We extend each {T_{N_*}} by zero to an operator on {\ell^2({\bf N})}, which is still a {F}-tight contraction. Using Lemma 3, one can find a sequence {N_{*,k}} going to infinity such that {T_{N_{*,k}}} converges in the strong (and dual strong) operator topologies to an {F}-tight contraction {T}. Let {F'} be a growth function larger than {F} to be chosen later. Applying ISP2, there exists an infinite sequence {0 < N_1 < N_2 < \ldots} and {F',N_1,N_2,\ldots}-tight unit vectors {v, w \in \ell^2({\bf N})} such that {\langle T^n v, w \rangle = 0} for all {n \geq 0}.

As {{\mathcal T}} is a barrier, there exists a finite initial segment {(N_1,\ldots,N_m)} of the above sequence that lies in {{\mathcal T}}. For {k} sufficiently large, we have {N_{*,k} \geq N_m}, and also we see from the strong operator norm convergence of {T_{N_{*,k}}} to {T} (and thus {T^n_{N_{*,k}}} to {T^n} for any {n}, as all operators are uniformly bounded) that

\displaystyle |\langle T^n_{N_{*,k}} v, w \rangle| \leq \frac{1}{F'(N_m)}

for all {0 \leq n \leq F(N_m)}.

Now we restrict {v, w} to {\ell^2(F(N_{*,k}))}, and then renormalise to create unit vectors {v', w' \in \ell^2(F(N_{*,k}))}. For {k} large enough, we have

\displaystyle \|v-v'\|, \|w-w'\| \leq 1 / F'(N_m)

and we deduce (for {F'} large enough) that {v', w'} are {F,N_1,N_2,\ldots,N_m}-tight and {|\langle T^n v, w \rangle| \leq \frac{1}{F(N_m)}} for all {0 \leq n \leq F(N_m)}. But this contradicts the construction of the {T_{N_{*}}}, and the claim follows.

— 3. A special case —

The simplest example of a barrier is the family of {1}-tuples {(N)}, and one of the simplest examples of an {F}-tight contraction is a contraction that is {1}-band-limited, i.e. the coefficients {a_{ij}} vanish unless {|i-j| \leq 1}. We thus obtain

Conjecture 8 (Finitary invariant subspace problem, special case, FISP1) Let {F} be a growth function and {\epsilon > 0}. Then there exists a natural number {N_*} such that for every {1}-band-limited contraction {T: \ell^2(F(N_*)) \rightarrow \ell^2(F(N_*))}, there exists {0 < N < N_*} and unit vectors {v, w \in \ell^2(F(N_*))} with

\displaystyle \sum_{j \geq N} |v_j|^2, \sum_{j \geq N} |w_j|^2 \leq \epsilon^2

(i.e. {v, w} are {\epsilon}-close to {\ell^2(N)}) such that {|\langle T^n v, w \rangle| \leq \frac{1}{F(N)}} for all {0 \leq n \leq F(N)}.

This is perhaps the simplest case of ISP that I do not see how to resolve. (Note that the finite-dimensional operator {T: \ell^2(F(N_*)) \rightarrow \ell^2(F(N_*))} will have plenty of (generalised) eigenvectors, but there is no particular reason why any of them are “tight” in the sense that they are {\epsilon}-close to {\ell^2(N)}.) Here is a slightly weaker version that I still cannot resolve:

Conjecture 9 (Finitary invariant subspace problem, special case, FISP2) Let {F} be a growth function, let {\epsilon > 0}, and let {T: \ell^2({\bf N}) \rightarrow \ell^2({\bf N})} be a {1}-band-limited contraction. Then there exists {N > 0} and unit vectors {v, w \in \ell^2({\bf N})} such that

\displaystyle \sum_{j \geq N} |v_j|^2, \sum_{j \geq N} |w_j|^2 \leq \epsilon^2

(i.e. {v, w} are {\epsilon}-close to {\ell^2(N)}) such that {|\langle T^n v, w \rangle| \leq \frac{1}{F(N)}} for all {0 \leq n \leq F(N)}.

This claim is implied by ISP but is significantly weaker than it. Informally, it is saying that one can find two reasonably localised vectors {v, w}, such that the orbit of {v} is highly orthogonal to {w} for a very long period of time, much longer than the degree to which {v, w} are localised.