# Is the Invariant Subspace Problem arithmetic?

Invariant Subspace Conjecture: A bounded operator on a separable Hilbert space has a non-trivial closed invariant subspace.

Can this conjecture be reformulated as an arithmetic statement, that is, $\Pi^0_n$ statement for some n? (I tried to figure it out, but failed.)

EDIT: For what I understand from answers, it appears to be an open problem. As Emil Jerabek and others mentioned, the intrinsic complexity of the conjecture (considered as a statement in second-order arithmetic) is $\Pi^1_2$. Apparently, no reduction to lesser complexity is known. One may speculate about how much of a solution would be a reduction to $\Pi^1_1$ or $\Pi^0_n$, but I would rather not.

Carl Mummert pointed out an interesting possibility: whether the conjecture itself is true or not, its interpretation in computable analysis may be false. In this case, if I got it right, the only way to reduce its complexity is to disprove it. However, this obstacle would disappear if we are allowed to use set theory to prove equivalence, because computable analysis doesn't work there.

Thanks to everyone.

-
It’s $\Pi^1_2$, and I am quite skeptical you can reduce this complexity without essentially solving the problem. –  Emil Jeřábek Jun 4 at 17:08
Is there any weak axiom system over which ISC is known to be undecidable - say, $RCA_0$? (I believe, although I haven't really put much thought into it, that ISC can be reasonably stated in the language of second-order arithmetic.) –  Noah S Jun 4 at 18:22
@EmilJeřábek Why not post an answer explaining it? This is a great opportunity to explain how these complexity calculations go in applications of descriptive set theory to other parts of mathematics. Those calculations are often confounding for non-set-theorists, and this kind of interdisciplinary question is a great fit for MO. –  Joel David Hamkins Jun 4 at 18:28
@Joel: Feel free to take the opportunity. There’s only so much procrastination time on MO I can handle. –  Emil Jeřábek Jun 4 at 19:02
I think you misinterpret Carl's comment. Even if the conjecture failed in computable analysis, it would still be perfectly possible to prove the conjecture or to reduce its complexity in another way. It's just that such a reduction would need something stronger to prove than RCA_0 (which is a fairly weak theory with respect to problems of this complexity). –  Emil Jeřábek Jun 7 at 10:43

I played with this a few years ago at http://terrytao.wordpress.com/2010/06/29/finitary-consequences-of-the-invariant-subspace-problem/ ; in the language of the analytical hierarchy, I was trying to lower the complexity of the invariant subspace problem from $\Pi^1_2$ to $\Pi^1_1$. I didn't quite succeed, because I couldn't quantify universally over all second-order objects, but one can instead reformulate the problem as a universal quantification of an arithmetic sentence over all "barriers" (a class of finite sets of natural numbers that "block" all infinite sequences, see Is there a name for a family of finite sequences that block all infinite sequences? ). Unfortunately, barriers (or more precisely, the property of not being a barrier, which is the relevant predicate when reducing to prenex normal form) are defined by a $\Sigma^1_1$ sentence, so this does not reduce the analytic complexity of the invariant subspace problem; but one can at least express this problem as an infinite conjunction of arithmetic sentences, one for each barrier. (One has of course has to add the predicate of membership in the given barrier to the arithmetic language.)

(There is also a universal quantification over growth functions in my formulation, which is another second order object, but this does not significantly increase the complexity, being a simpler object than the barrier.)

Henry Towsner (private communication) has achieved similar such "finitisations" for any $\Pi^1_2$ sentence.

-
Thank you, this is interesting. Asking about "arithmetization", I too had in mind some kind of reduction to finite dimensions. Now it seems to me even more hopeless then I expected. –  Alex Gavrilov Jun 6 at 10:12

It seems to me also that the assertion is naturally expressed by a $\Pi^1_2$ assertion in second-order number theory, as Emil had indicated. Let me explain how one can see this.

The basic issue here is that the natural expression of the statement in the language of set theory makes direct reference to uncountable objects, such as the space and the operator and the closed subspace, and therefore cannot be said to be purely arithmetic nor even projective.

But the point is that, nevertheless, one can use the separability hypothesis to find a natural translation of the statement that brings it into the realm of second-order number theory, the context of much of reverse mathematics, and in this way reduce the complexity to $\Pi^1_2$.

In order to do this, one must translate the basic concepts of separable Hilbert space theory to second-order number theory and develop a bit of analysis in that context. In particular, the only objects available in this context are countable, and so one must represent the space, the operator and the subspaces ultimately as countable objects. For example, one can represent the space by providing detailed information about the countable dense set, such as the metric distances on that set and the linear operations; and one represents operators by how they act on that dense subset, and closed subspaces by their projections of that set, and so on. Everything is ultimately represented by a countable amount of information in this context.

Avigad and Simic have written a beautiful account precisely undertaking this project:

If you look there (chapter 9), you will find how they represent the whole space, and they develop the basic theory of real analysis in second-order number theory. Since they are interested in the reverse mathematical aspect of the situation, you will see that they pay attention to precisely which axioms of second-order number theory one needs to develop the basic facts one wants when working with separable Hilbert spaces. Closed subspaces are treated in chapter 11.

Now, putting all this together, one looks at your statement, which asserts:

• For every separable Hilbert space and every bounded linear operator on it, there is a nontrivial closed invariant subspace.

So we have universal quantifiers, followed by an existential quantifier, and each of these quantifiers is quantifying over the space of countable objects available in second-order number theory. The properties of being (the code of) a separable Hilbert space or an unbounded operator on such a space are themselves arithmetic, and the encoding of these concepts into second-order number theory is arranged with that in mind. Thus, altogether the complexity is $\forall\exists$ in second-order number theory, or in other words, $\Pi^1_2$ in the projective hierarchy, which is of course a few steps beyond arithmetic.

This is of course, an upper bound, since it is conceivable that one could find a clever equivalent formulation with reduced complexity.

And while this doesn't make the assertion arithmetic, nevertheless the $\Pi^1_2$ level of complexity means that the assertion will be invariant by forcing, on account of the Shoenfield absoluteness theorem.

-
Very nice explanation, JD! –  Bill Johnson Jun 4 at 23:51
A slight simplification of the formulation of the problem, but unfortunately not a reduction in the $\Pi^1_2$ complexity, would be to omit the quantifier "for every separable Hilbert space", since you can always take the space to be $\ell_2$. (This doesn't help the projective complexity because you still have the quantifier "for every bounded linear operator".) –  Andreas Blass Jun 5 at 0:35
That is an important issue, but it seems to be arithmetic, since you just have to say that the operator applied to any of the points generating the subspace is in the subspace (that is, in the closure of the points representing it). But this all involves only arithmetic quantifiers, since you're just asserting that all the approximations to the stuff you have is is arbitrarily close to the stuff you have. That is, quantifying over the subspace is not a second-order quantifier, since you're representing it with a countable dense subset, so you've only got to quantify over those points. –  Joel David Hamkins Jun 5 at 1:18
Nice :) One more thing may be worth pointing out. One may try to get rid of the existential quantifier by noting that the invariant subspace is almost definable: if $T$ is the operator and $u$ any nonzero vector in a nontrivial invariant subspace, then the closure of the span of $u,Tu,T^2u,\dots$ is also a nontrivial invariant subspace. However, this does not really help, as one still needs a second-order existential quantifier for $u$. –  Emil Jeřábek Jun 5 at 10:17
As a comment on my own comment (and somewhat related to Emil's): we can also formulate the ISP as $\forall T \exists x,y\not=0 (\sum_{n\ge 0} |\langle x, T^n y \rangle |=0)$. (Of course, I'm only considering $\|T\|<1$ now.) –  Christian Remling Jun 5 at 14:44