Computable copies of ℓ p 1

Abstract

Suppose p is a computable real so that $p ⩾ 1$ . It is shown that the halting set can compute a surjective linear isometry between any two computable copies of $ℓ^{p}$ . It is also shown that this result is optimal in that when $p \neq 2$ there are two computable copies of $ℓ^{p}$ with the property that any oracle that computes a linear isometry of one onto the other must also compute the halting set. Thus, $ℓ^{p}$ is $Δ_{2}^{0}$ -categorical and is computably categorical if and only if $p = 2$ . It is also demonstrated that there is a computably categorical Banach space that is not a Hilbert space. These results hold in both the real and complex case.

Keywords

Computable analysis computable model theory

1. Introduction

We start by considering the very general question “Given two computable and linearly isometric Banach spaces, how hard is it to compute a linear isometry from one onto the other?” (Roughly speaking, a Banach space is computable if there are algorithms that compute its scalar multiplication, vector addition, and norm.) We specialize this question to the case of Banach spaces that are linearly isometric to $ℓ^{p}$ where $p ⩾ 1$ is a computable real (i.e. a real whose decimal expansion is computable). Our first result is that this is no harder than computing membership in the halting set. Namely, we show that when p is a computable real so that $p ⩾ 1$ , the halting set is capable of computing a surjective linear isometry between any two computable copies of $ℓ^{p}$ . Our second result is that this problem is not easier than the halting set. Namely, when p is a computable real so that $p ⩾ 1$ and $p \neq 2$ , there are two computable copies of $ℓ^{p}$ so that any oracle that computes a surjective linear isometry from one onto the other must also compute the halting set. It is already known that any two computable copies of $ℓ^{2}$ are computably linearly isometric [11]. This is essentially due to the fact that $ℓ^{2}$ is a Hilbert space and mirrors the classical fact that any two infinite-dimensional separable Hilbert spaces are linearly isometric [6].

The first of our two results is based on a sharpening of an inequality due to J. Lamperti which we prove in Section 4. In the main, our second result was previously shown for $p = 1$ by Pour-El and Richards [11]. Their proof rests on an observation about the extreme points of the closed unit ball of $ℓ^{1}$ that does not generalize to $ℓ^{p}$ when $p > 1$ . The proof presented here uses the characterization of the linear isometries of $L^{p}$ spaces due to S. Banach and J. Lamperti [2,4,7].

Our findings can be recast in the setting of computable categoricity. A mathematical structure is computably categorical if any two of its computable copies are isomorphic via a computable map. A structure is $Δ_{2}^{0}$ -categorical if the halting set can compute an isomorphism between any two of its computable copies [1,5]. Our results can be interpreted in the setting of computable categoricity by replacing ‘isomorphism’ with ‘surjective linear isometry’; i.e. when p is a computable real so that $p ⩾ 1$ , $ℓ^{p}$ is $Δ_{2}^{0}$ -categorical, and $ℓ^{p}$ is computably categorical if and only if $p = 2$ . The latter resolves a question posed by A.G. Melnikov in 2013 [9].

Although our theorems are proven for the complex version of $ℓ^{p}$ , they also hold for the real version of $ℓ^{p}$ .

The paper is organized as follows. Section 2 covers background and preliminaries from functional analysis and computable analysis. Section 3 gives an overview of the proof that $ℓ^{p}$ is $Δ_{2}^{0}$ -categorical. The remainder of the work is then divided into two parts each corresponding to a different mathematical universe: the classical world (Section 4), wherein we have full access to all the concepts, principles, and methods of classical mathematics, and the computable world (Section 5) wherein we can only see approximations of classical objects and can only access computable operations on these approximations. In Section 6, we use the methods developed in the previous sections to provide simple proofs that there is a computably categorical Banach space that is not a Hilbert space. Section 7 presents concluding remarks.

2. Background and preliminaries

2.1. Background and preliminaries from functional analysis

Throughout this paper, it is assumed that all Banach spaces are Banach spaces over the field of complex numbers $C$ .

We begin with some notation and terminology. Let $B = (V, \cdot, +, ‖ ‖)$ be a Banach space. By a subspace of $B$ we will always mean a linear subspace of $B$ that is topologically closed. When $S \subseteq V$ and $F \subseteq C$ , we let $L_{F} (S)$ denote the set of all linear combinations of vectors in S whose coefficients lie in F; i.e. $\begin{matrix} L_{F} (S) = {\sum_{j = 0}^{M} α_{j} v_{j} : M \in N \land α_{0}, \dots, α_{M} \in F \land v_{0}, \dots, v_{M} \in S} . \end{matrix}$ The subspace generated by S is the closure of the linear span of S; we denote this by $⟨ S ⟩$ . We say that $G \subseteq V$ is a generating set for $B$ if it generates all of $B$ ; i.e. $V = ⟨ G ⟩$ . For example, let $e_{n} = χ_{{n}}$ for all $n \in N$ (where $χ_{A}$ denotes the characteristic function of A). Then, $E : = {e_{0}, e_{1}, \dots}$ is a generating set for $ℓ^{p}$ which we refer to as the standard generating set for $ℓ^{p}$ . Also, the set of all $f_{n} (x) = x^{n}$ for $n \in N$ is a generating set for $C [0, 1]$ .

A map between two Banach spaces is linear if it preserves scalar multiplication and vector addition; it is an isometry (or is isometric) if it preserves the metric induced by the norm; i.e. $‖ T (x) - T (y) ‖ = ‖ x - y ‖$ . Thus, every isometry is injective. An endomorphism of a Banach space is a linear (but not necessarily isometric) map of the space into itself.

When p is a positive number, $ℓ^{p}$ denotes the space of all functions $f : N \to C$ so that $\begin{matrix} \sum_{n = 0}^{\infty} {| f (n) |}^{p} < \infty . \end{matrix}$ $ℓ^{p}$ is a vector space over $C$ with the usual scalar multiplication and vector addition. When $p ⩾ 1$ it is a Banach space under the norm defined by $\begin{matrix} ‖ f ‖_{p} = {(\sum_{n = 0}^{\infty} {| f (n) |}^{p})}^{1 / p} . \end{matrix}$ It is often convenient to view $ℓ^{p}$ as $L^{p} (μ)$ where μ is the counting measure on $N$ .

When $f \in ℓ^{p}$ , the support of f is the set of all $t \in N$ so that $f (t) \neq 0$ ; we denote this set by $supp (f)$ . If $f_{0}, f_{1}, \dots$ are vectors in $ℓ^{p}$ so that $supp (f_{m}) \cap supp (f_{n}) = \emptyset$ whenever $m \neq n$ , then we say that $f_{0}, f_{1}, \dots$ are disjointly supported. Note that if $f, g \in ℓ^{p}$ are disjointly supported then $‖ f + g ‖_{p}^{p} = ‖ f ‖_{p}^{p} + ‖ g ‖_{p}^{p}$ .

We now describe a simple numerical test for disjointness of support when $p \neq 2$ . When $z, w \in C$ let: $\begin{matrix} σ_{1} (z, w) = | 2 (| z |^{p} + | w |^{p}) - (| z - w |^{p} + | z + w |^{p}) | . \end{matrix}$ In 1958, J. Lamperti proved that $σ_{1} (z, w) = 0$ iff $z w = 0$ and that the sign of $2 (| z |^{p} + | w |^{p}) - (| z - w |^{p} + | z + w |^{p})$ depends only on p. Define $σ_{1} (f, g)$ to be $\sum_{n} σ_{1} (f (n), g (n))$ . Thus, $σ_{1} (f, g) = | 2 (‖ f ‖^{p} + ‖ g ‖^{p}) - (‖ f - g ‖^{p} + ‖ f + g ‖^{p}) |$ and $σ_{1} (f, g) = 0$ if and only if f, g are disjointly supported. Note also that $σ_{1}$ is invariant under linear isometries. Thus, every isometric endomorphism of $ℓ^{p}$ preserves the ‘disjoint support’ relation. That is, if $T : ℓ^{p} \to ℓ^{p}$ is a linear isometry, then $T (f)$ and $T (g)$ are disjointly supported whenever $f, g \in ℓ^{p}$ are disjointly supported.

When $f, g \in ℓ^{p}$ , write $f ⪯ g$ if $f (n) = 0$ whenever $g (n) \neq f (n)$ . It follows that ⪯ is a partial order of $ℓ^{p}$ . Note that the atoms of this partial order are the nonzero scalar multiples of the $e_{n}$ ’s. Note also that $f ⪯ g$ if and only if $g - f$ and f are disjointly supported. Thus, ⪯ is preserved by isometric endomorphisms of $ℓ^{p}$ .

The proof that $ℓ^{p}$ is not computably categorical when $p \neq 2$ is based on the following.

Theorem 2.1 (Banach–Lamperti).

Suppose $1 ⩽ p < \infty$ and $p \neq 2$ . Suppose T is an endomorphism of $ℓ^{p}$ . Then, T is a surjective isometric endomorphism of $ℓ^{p}$ if and only if there are unimodular constants $λ_{0}, λ_{1}, \dots$ and a permutation of $N$ , ϕ, so that $T (e_{n}) = λ_{n} e_{ϕ (n)}$ for all n.

In his seminal text on linear operators, S. Banach stated Theorem 2.1 for the case of $ℓ^{p}$ spaces over the reals [2]. He also stated a classification of the linear isometries of $L^{p} [0, 1]$ in the real case. Banach’s proofs of these claims were sketchy and did not easily generalize to the complex case. In 1958, J. Lamperti rigorously proved a generalization of Banach’s claims to real and complex $L^{p}$ -spaces of σ-finite measures [7]. Theorem 2.1 follows from J. Lamperti’s work as it appears in Theorem 3.2.5 of [4]. Note that Theorem 2.1 fails when $p = 2$ . For, $ℓ^{2}$ is a Hilbert space. So, if ${f_{0}, f_{1}, \dots}$ is any orthonormal basis for $ℓ^{2}$ , then there is a unique surjective linear isometry T of $ℓ^{2}$ so that $T (e_{n}) = f_{n}$ for all n.

2.2. Background and preliminaries from computable analysis

We assume the reader is familiar with the basic notation and terminology of computability theory as expounded in [3]. We cover here the basic notions from computable analysis necessary to understand the results herein. A more expansive treatment can be found in [11,12].

Suppose $B$ is a Banach space and $F = {f_{0}, f_{1}, \dots} \subseteq B$ is a generating set for $B$ . We say that F is an effective generating set for $B$ if there is an algorithm that, given any $f \in L_{Q (i)} (F)$ and a nonnegative integer k as input computes a rational number q so that $| ‖ f ‖ - q | < 2^{- k}$ ; less formally, the map $f \in L_{Q (i)} (F) \mapsto ‖ f ‖$ is computable. For example, ${1, i}$ is an effective generating set for $C$ , and the standard generating set of $ℓ^{p}$ is an effective generating set for $ℓ^{p}$ . On the other hand, if $| ζ | = 1$ , then $ζ E : = {ζ e_{0}, ζ e_{1}, \dots}$ is also an effective generating set for $ℓ^{p}$ , even if ζ is incomputable. We designate ${1, i}$ and E as the default effective generating sets for $C$ and $ℓ^{p}$ respectively; i.e. when discussing computability on these spaces without mention of an effective generating set it is implicit that we are using the default generating set.

Suppose F is an effective generating set for a Banach space $B$ . We say that a vector $g \in B$ is computable with respect to F if there is an algorithm that given any nonnegative integer k as input computes a vector $f \in L_{Q (i)} (F)$ so that $‖ g - f ‖ < 2^{- k}$ . Thus a point $z \in C$ is computable (with respect to the default generating set) if there is an algorithm that given any $k \in N$ as input, produces a rational point q so that $| q - z | < 2^{- k}$ . A vector $f \in ℓ^{p}$ is computable (with respect to the default generating set E) if there is an algorithm that given any $n, k \in N$ as input computes a rational point q so that $| q - f (n) | < 2^{- k}$ . On the other hand, if ζ is an incomputable unimodular point, then only the zero vector is computable with respect to both E and $ζ E$ .

Suppose $B$ is a Banach space. When $f \in B$ , and $r > 0$ , let $B (f; r)$ denote the open ball with center f and radius r. Suppose F is an effective generating set for $B$ . When $f \in L_{Q (i)} (F)$ and r is a positive rational number, we call $B (f; r)$ a rational ball (with respect to F).

Suppose that for each $j \in {1, 2}$ , $F_{j}$ is an effective generating set for $B_{j}$ . We say that a map $T : B_{1} \to B_{2}$ is computable with respect to $(F_{1}, F_{2})$ if there is an algorithm P that meets the following three criteria.

Approximation: Given as input a rational ball with respect to $F_{1}$ , P either does not halt or produces a rational ball with respect to $F_{2}$ .

Correctness: If $B_{2}$ is the output of P on input $B_{1}$ , then $T (f) \in B_{2}$ whenever $f \in B_{1}$ .

Convergence: If V is a neighborhood of $T (f)$ , and if U is a neighborhood of f, then f belongs to a rational ball $B_{1} \subseteq U$ with the property that P halts on $B_{1}$ and produces a rational ball that is included in U.

When we speak of an algorithm accepting a rational ball $B (\sum_{j = 0}^{M} α_{j} f_{j}; r)$ as input, we mean that it accepts some representation of the ball such as a code of the sequence $(r, M, α_{0}, \dots, α_{M})$ and similarly when we say it produces a rational ball as output we mean that it produces codes of the center and radius.

It is well-known that many familiar functions of a complex variable (such as sin, exp) are computable (with respect to the generating set ${1, i}$ used in the domain and range). Note also that when $| ζ | = 1$ the ‘multiplication by ζ’ operator on $ℓ^{p}$ is computable with respect to E and $ζ E$ .

A computable Banach space consists of a pair $(B, F)$ where $B$ is a Banach space and F is an effective generating set for $B$ . Unless the effective generating set truly requires explicit mention, for the sake of economy of expression we will just refer to ‘the computable Banach space $B$ ’.

If $(B_{1}, F_{1})$ and $(B_{2}, F_{2})$ are computable Banach spaces, then we say a map $T : B_{1} \to B_{2}$ is computable if it is computable with respect to $(F_{1}, F_{2})$ . It easily follows that if $T : B_{1} \to B_{2}$ is a computable surjective linear isometry, then $T^{- 1}$ is also computable.

If $(B_{1}, F_{1})$ and $(B_{2}, F_{2})$ are computable Banach spaces, then $(B_{1} \times B_{2}, F_{1} \times F_{2})$ is a computable Banach space. Thus, if $B$ is a computable Banach space, then vector addition is a computable map from $B \times B$ onto $B$ and scalar multiplication is a computable map from $C \times B$ onto $B$ . In addition the norm of $B$ is a computable map from $B$ into $[0, \infty)$ .

Suppose $B$ is a computable Banach space. A closed set $C \subseteq B$ is c.e. closed if the set of all rational balls that contain a point of C is c.e. An open set $U \subseteq B$ is c.e. open if the set of all rational balls included in U is c.e. Suppose $B^{'}$ is a computable Banach space and $f : B \to B^{'}$ is computable. It is well-known that if $U \subseteq B^{'}$ is c.e. open, then $f^{- 1} [U]$ is c.e. open.

The following is ‘folklore’.

Proposition 2.2.
Suppose $B$ is a computable Banach space and $f : B \to R$ is a computable function with the property that $f (v) ⩾ d (v, f^{- 1} [{0}])$ for all $v \in B$ . Then, $f^{- 1} [{0}]$ is c.e. closed.

The computability notions we have covered are all relativized in the usual way. We now formally state our two main theorems.
Theorem 2.3.
Suppose p is a computable real so that $p ⩾ 1$ . Then, whenever $B_{0}$ and $B_{1}$ are computable Banach spaces that are linearly isometric to $ℓ^{p}$ , the halting set computes a surjective linear isometry of $B_{0}$ onto $B_{1}$ .
Theorem 2.4.
Suppose p is a computable real so that $p ⩾ 1$ and $p \neq 2$ . Suppose C is a c.e. set. Then, there is a computable Banach space $B$ so that C computes a surjective linear isometry of $ℓ^{p}$ onto $B$ and so that any oracle that computes a surjective linear isometry of $ℓ^{p}$ onto $B$ also computes C.

So if we take C to be the halting set in Theorem 2.4, then it follows that the problem of computing a linear isometric map of one computable copy of $ℓ^{p}$ onto another is at least as hard as computing membership in the halting set.

We close this section by mentioning some related work. A.G. Melnikov and K.M. Ng have investigated computable categoricity questions with regards to the space $C [0, 1]$ of continuous functions on the unit interval with the supremum norm. In particular, they have shown that $C [0, 1]$ is not computably categorical as a metric space nor as a Banach space [9,10]. The study of computable categoricity for countable structures goes back at least as far as the 1961 work of A.I. Malcev. The text of Ash and Knight has a thorough discussion of the main early results of this line of inquiry [1]. The survey by Fokina, Harizanov, and Melnikov contains a wealth of recent results on computable categoricity and other directions in the countable computable structures program [5].
3. Overview

The proof of Theorem 2.4 is fairly straightforward. Here, we set forth the key concepts and supporting intermediate results for the proof of Theorem 2.3.

We first reduce the problem to the computation of surjective isometric endomorphisms. Fix a computable real so that $p ⩾ 1$ . Suppose $(B, G)$ is a computable Banach space, and suppose T is a linear isometric mapping of $B$ onto $ℓ^{p}$ . Then, $T [G]$ is an effective generating set for $ℓ^{p}$ , and T is computable with respect to $(G, T [G])$ . Thus, since inverses of computable surjective linear isometries are computable, the study of computable Banach spaces that are linearly isometric to $ℓ^{p}$ can be reduced to the study of computability notions on $ℓ^{p}$ with respect to different generating sets. In particular, to prove Theorem 2.3, it suffices to show that whenever F is an effective generating set for $ℓ^{p}$ , the halting set computes a surjective isometric endomorphism of $ℓ^{p}$ with respect to $(E, F)$ .

Now, suppose $g_{0}, g_{1}, \dots$ , are disjointly supported unit vectors in $ℓ^{p}$ . Then, there is a unique linear isometric map $T : ℓ^{p} \to ℓ^{p}$ so that $T (e_{n}) = g_{n}$ for all n; if the $g_{n}$ ’s generate $ℓ^{p}$ , then T is also surjective. Furthermore, if an oracle X computes ${g_{n}}_{n = 0}^{\infty}$ with respect to an effective generating set F, then X also computes T with respect to $(E, F)$ . So, to prove Theorem 2.3, it suffices to prove the following.

Theorem 3.1.
If p is a computable real so that $p ⩾ 1$ and $p \neq 2$ , and if F is an effective generating set for $ℓ^{p}$ , then with respect to F the halting problem computes a sequence of disjointly supported unit vectors that generate $ℓ^{p}$ .

Our main tool for producing such a sequence of unit vectors is the concept of a disintegration which we define now. To begin, fix a real $p ⩾ 1$ . Suppose $S \subseteq ω^{< ω}$ and $ϕ : S \to ℓ^{p}$ . We say that ϕ is a reverse-order homomorphism if $ϕ (τ) ⪯ ϕ (ρ)$ whenever $τ, ρ \in S$ are such that $τ \supset ρ$ . (Recall from Section 2.1 that $f ⪯ g$ if and only if $f (n) = 0$ whenever $f (n) \neq g (n)$ .) We say that ϕ is a strong reverse-order homomorphism if it is a reverse-order homomorphism with the additional feature that it maps incomparable nodes to disjointly supported vectors. Accordingly, an injective (strong) reverse-order homomorphism will be called a (strong) reverse-order monomorphism.

Suppose S is a subtree of $ω^{< ω}$ . When ν is a nonterminal node of S, let $ν_{S}^{+}$ denote the set of all children of ν in S. Call a map $ϕ : S \to ℓ^{p}$ summative if $ϕ (ν) = \sum_{ν^{'} \in ν_{S}^{+}} ϕ (ν^{'})$ whenever ν is a nonterminal node of S. A disintegration is a summative strong reverse-order monomorphism whose range generates $ℓ^{p}$ .

That disintegrations exist is easy to see; e.g. set $ϕ (\emptyset) = \sum_{n} 2^{- n} e_{n}$ and set $ϕ ((n)) = 2^{- n} e_{n}$ . The challenge is to produce a disintegration that is computable with respect to an effective generating set F (in the sense that there is an algorithm that given a $ν \in S$ and a $k \in N$ computes an $f \in L_{Q (i)} (F)$ so that $‖ ϕ (ν) - f ‖_{p} < 2^{- k}$ ). Accordingly, in Section 5, we prove the following.
Theorem 3.2.
If $p ⩾ 1$ is a computable real besides 2, and if F is an effective generating set for $ℓ^{p}$ , then there is a disintegration of $ℓ^{p}$ that is computable with respect to F.

How does possession of a disintegration $ϕ : S \to ℓ^{p}$ that is computable with respect to an effective generating set F help us to prove Theorem 3.1? Intuitively, to define $g_{n}$ we want to use the halting set to compute the limit of $ϕ (ν)$ as ν descends some carefully chosen branch of S. To see how we choose these branches, we now define the concept of an almost norm-maximizing chain. When ν is a non-root node of $ω^{< ω}$ , let $ν^{-}$ denote its parent.
Definition 3.3.
Suppose $ϕ : S \to ℓ^{p}$ is a disintegration.
If ν is a non-root node of S, then we say ν is an almost norm-maximizing child of $ν^{-}$ if $‖ ϕ (μ) ‖_{p}^{p} ⩽ ‖ ϕ (ν) ‖_{p}^{p} + 2^{- (| ν | + 1)}$ whenever μ is a child of $ν^{-}$ in S.

A chain $C \subseteq S$ is almost norm-maximizing if every nonterminal node in $C$ has an almost norm-maximizing child in $C$ .

In Section 4 we prove the following.
Theorem 3.4.
Suppose $ϕ : S \to ℓ^{p}$ is a disintegration.
If $C \subseteq S$ is an almost norm-maximizing chain, then the ⪯-infimum of $ϕ [C]$ exists and is either $0$ or an atom of ⪯. Furthermore, $inf ϕ [C]$ is the limit in the $ℓ^{p}$ norm of $ϕ (ν)$ as ν traverses the nodes in $C$ in increasing order.

If ${C_{n}}_{n = 0}^{\infty}$ is a partition of S into almost norm-maximizing chains, then $inf ϕ [C_{0}], inf ϕ [C_{1}], \dots$ are disjointly supported vectors that generate $ℓ^{p}$ .

And, in Section 5, we prove:
Theorem 3.5.
Suppose $ϕ : S \to ℓ^{p}$ is a disintegration that is computable with respect to an effective generating set F. Then, there is a computable partition of S into c.e. almost norm-maximizing chains.

So, to prove Theorem 3.1 we first compute with respect to F a disintegration $ϕ : S \to ℓ^{p}$ , and then compute a partition of S into c.e. almost norm-maximizing chains $C_{0}, C_{1}, \dots$ . Set $g_{n} = inf ϕ [C_{n}]$ . Note that $‖ g_{n} ‖_{p}$ is a right-c.e. real. Thus, the halting set computes $‖ g_{n} ‖_{p}$ from n. Since $g_{n} ⪯ ϕ (ν)$ for all $ν \in C_{n}$ , it follows that the halting set computes $g_{n}$ with respect to F (since $‖ ϕ (ν) - g_{n} ‖_{p}^{p} = ‖ ϕ (ν) ‖_{p}^{p} - ‖ g_{n} ‖_{p}^{p}$ for all $ν \in C_{n}$ ). We can also use the halting set to enumerate all values of n for which $g_{n} \neq 0$ ; denote these $n_{0} < n_{1} < \dots$ . Then, ${‖ g_{n_{j}} ‖^{- 1} g_{n_{j}}}_{j = 0}^{\infty}$ is a disjointly supported sequence of unit vectors that generates $ℓ^{p}$ , and the halting set computes ${g_{n_{j}}}_{j = 0}^{\infty}$ with respect to F.

Let us now return to the proof of Theorem 3.2. The idea is to construct a disintegration ϕ via an ascending sequence of partial disintegrations that are computable uniformly with respect to F. Specifically, we define a partial disintegration to be a strong order monomorphism $ψ : S - {\emptyset} \to ℓ^{p}$ where S is a finite nonempty subtree of $ω^{< ω}$ . We say a partial disintegration $ψ_{2}$ extends a partial disintegration $ψ_{1}$ if $dom (ψ_{1}) \subseteq dom (ψ_{2})$ and if $ψ_{2} (ν) = ψ_{1} (ν)$ for all $ν \in dom (ψ_{1})$ .

Let $F = {f_{0}, f_{1}, \dots}$ be a generating set for $ℓ^{p}$ . If F is an effective generating set, then it is quite easy to produce a partial disintegration that is computable with respect to F. Namely, set $S = {\emptyset}$ and $ψ = \emptyset$ . Of course, this partial disintegration does not do much for us and is quite far from being a disintegration. Accordingly, when $ψ : S - {\emptyset} \to ℓ^{p}$ is a partial disintegration, we define the success index of ψ (with respect to F) to be the largest integer N so that $d (f_{j}, ⟨ ran (ψ) ⟩) < 2^{- N}$ whenever $0 ⩽ j < N$ and $\begin{matrix} {‖ ψ (ν) - \sum_{ν^{'} \in ν_{S}^{+}} ψ (ν^{'}) ‖}_{p} < 2^{- N} \end{matrix}$ whenever ν is a non-root nonterminal node of S.

Here is how we can glue an ascending sequence of partial disintegrations into a disintegration. Suppose $ψ_{0}, ψ_{1}, \dots$ is an ascending sequence of partial disintegrations (in the sense that $ψ_{n + 1}$ extends $ψ_{n}$ ) so that the success index of $ψ_{n + 1}$ is larger than n for all n. Set $S = {\emptyset} \cup ⋃_{n} dom (ψ_{n})$ , and set $\begin{matrix} ψ (ν) = 2^{- ν (0)} lim_{n} {({‖ ψ_{n} (ν (0)) ‖}_{p} + 1)}^{- 1} ψ_{n} (ν) \end{matrix}$ for all $ν \in S - {\emptyset}$ . Set $ψ (\emptyset) = \sum_{(a) \in S} ψ ((a))$ . Then, ψ is a disintegration. Such a chain of partial disintegrations can be obtained by a fairly straightforward application of the following which is proven in Section 5. Theorem 3.6.
Suppose F is an effective generating set for $ℓ^{p}$ where $p ⩾ 1$ is a computable real besides 2. If $N, k \in N$ , and if $ϕ : S - {\emptyset} \to ℓ^{p}$ is a partial disintegration that is computable with respect to F, then there exists a map $ϕ^{'} : S - {\emptyset} \to ℓ^{p}$ so that $\begin{matrix} max {{‖ ϕ (ν) - ϕ^{'} (ν) ‖}_{p} : ν \in S - {\emptyset}} < 2^{- k} \end{matrix}$ and so that $ϕ^{'}$ extends to a partial disintegration ψ that is computable with respect to F and whose success index with respect to F is larger than N. Furthermore, an index of ψ can be computed from N, k and an index of ϕ.

4. Classical world

4.1. Results on disintegrations and partial disintegrations

The following is a preliminary step to proving Theorem 3.4.

Proposition 4.1.
If $g_{0} ≻ g_{1} ≻ \dots$ are vectors in $ℓ^{p}$ , then ${lim}_{n} g_{n}$ exists pointwise and in the $ℓ^{p}$ -norm and is the ⪯-infimum of ${g_{0}, g_{1}, \dots}$ .
Proof.
Let $\begin{matrix} S = ⋂_{n} supp (g_{n}) . \end{matrix}$ Set $g = g_{0} \cdot χ_{S}$ . Since $g_{n + 1} ⪯ g_{n}$ , it follows that g is the pointwise limit of ${g_{n}}_{n}$ .

We claim that $| g_{n} (t) - g (t) | ⩽ | g_{0} (t) |$ for all t. For, either $g_{n} (t) = g (t)$ , or $g (t) = 0$ and $g_{n} (t) = g_{0} (t)$ . By regarding summation as integration with respect to the counting measure, it now follows from the Dominated Convergence Theorem that ${lim}_{n \to \infty} ‖ g_{n} - g ‖_{p} = 0$ .

Suppose $h ⪯ g_{n}$ for all n. Thus, as discussed in Section 2.1, $σ_{1} (g_{n} - h, h) = 0$ for all n. Since ${g_{n}}_{n = 0}^{\infty}$ converges to g in the $ℓ^{p}$ -norm, $σ_{1} (g - h, h) = 0$ ; that is $h ⪯ g$ . Thus, $g = inf {g_{0}, g_{1}, \dots}$ . □
Proof of Theorem 3.4.
(1): Suppose $C \subseteq S$ is an almost norm-maximizing chain. It follows from Proposition 4.1 that the ⪯-infimum of $ϕ [C]$ exists; let g denote this infimum. By way of contradiction, suppose $j_{0}, j_{1} \in supp (g)$ and $j_{0} \neq j_{1}$ . Since ϕ maps incomparable nodes to disjointly supported vectors, whenever $ν \in S$ , the support of $ϕ (ν)$ contains both $j_{0}$ and $j_{1}$ if it contains either one of them. Since ϕ is reverse-order preserving, if $j_{0}$ and $j_{1}$ belong to the support of $ϕ (ν)$ , then $ϕ (ν) (j_{0}) = g (j_{0})$ and $ϕ (ν) (j_{1}) = g (j_{1})$ . But, since ϕ is a disintegration, the range of ϕ generates $ℓ^{p}$ – a contradiction. Thus, g is either $0$ or an atom.

(2): Suppose $C_{0}, C_{1}, \dots$ is a partition of S into almost norm-maximizing chains. By part (1), $inf ϕ [C_{n}]$ exists for each n; let $h_{n} = inf ϕ [C_{n}]$ .

We first claim that for every j, there is a k so that j belongs to the support of $h_{k}$ . If there is an atom in $ran (ϕ)$ whose support contains j, then there is nothing to prove. So, suppose j does not belong to the support of any atom in $ran (ϕ)$ .

We claim that there is a $ν \in S$ so that $j \in supp (ϕ (ν))$ and $| ν | = 1$ . For otherwise, $j \notin supp (g)$ for all $g \in ran (ϕ)$ . But, since ϕ is a disintegration, $ran (ϕ)$ generates $ℓ^{p}$ – a contradiction.

Since ϕ is a disintegration, if ν is a nonterminal node of S, then $ϕ (ν) = \sum_{ν^{'} \in ν_{S}^{+}} ϕ (ν^{'})$ . It thus follows by induction that for each s, j belongs to the support of a $ϕ (ν)$ so that $| ν | = s$ ; since ϕ maps incomparable nodes to disjointly supported vectors, ν is unique and accordingly we denote it by $ν_{s}$ . Let $g_{s} = ϕ (ν_{s})$ . Again, since ϕ maps incomparable nodes to disjointly supported vectors, $ν_{s + 1} \supset ν_{s}$ for all s. Since ϕ is a reverse-order monomorphism, $g_{s + 1} ≺ g_{s}$ for all s. Thus, $g_{s} (j) = g_{0} (j) \neq 0$ for all s.

Now, for each s, let $k_{s}$ denote the k so that $g_{s} \in ϕ [C_{k}]$ . We claim that ${lim}_{s} k_{s}$ exists. By way of contradiction suppose otherwise. Let $s_{0} < s_{1} < \dots$ be the increasing enumeration of all values of s for which $k_{s} \neq k_{s + 1}$ . Since $ν_{s_{m} + 1} \supset ν_{s_{m}}$ , $ν_{s_{m}}$ is a nonterminal node of S. Therefore, since $C_{k_{s_{m}}}$ is almost norm-maximizing, it must contain a child of $ν_{s_{m}}$ in S; let $μ_{m}$ denote this child and let $λ_{m} = ϕ (μ_{m})$ . Thus, $λ_{m} ≺ g_{s_{m}}$ and the supports of $λ_{m}$ and $g_{s_{m} + 1}$ are disjoint (since $μ_{m}$ and $ν_{s_{m} + 1}$ are distinct nodes at the same level of S). In addition, since $μ_{m}$ is an almost norm-maximizing child of $ν_{s_{m}}$ , $| g_{0} (j) |^{p} = | g_{s_{m} + 1} (j) |^{p} ⩽ ‖ λ_{m} ‖_{p}^{p} + 2^{- s_{m}}$ . Since $λ_{m + r} ⪯ g_{s_{m + r}} ⪯ g_{s_{m} + 1}$ , the supports of $λ_{m}$ and $λ_{m + r}$ are disjoint if $r > 0$ . That is to say, $supp (λ_{m}) \cap supp (λ_{m^{'}}) = \emptyset$ whenever $m \neq m^{'}$ . Thus, $\infty = \sum_{m} ‖ λ_{m} ‖_{p}^{p} ⩽ ‖ g_{0} ‖_{p}^{p}$ – a contradiction. Thus, $k : = {lim}_{s} k_{s}$ exists, and so j belongs to the support of $h_{k}$ . Moreover, it follows from part (1) that $h_{k}$ is a nonzero scalar multiple of $e_{j}$ . It then follows that $h_{0}, h_{1}, \dots$ generate $ℓ^{p}$ .

Finally, we claim that $h_{0}, h_{1}, \dots$ are disjointly supported. For, suppose $k \neq k^{'}$ . It suffices to show that there are incomparable nodes ν, $ν^{'}$ so that $ν \in C_{k}$ and $ν^{'} \in C_{k^{'}}$ . If there is an integer s so that $C_{k}$ and $C_{k^{'}}$ both contain a node of length s, then we may choose ν and $ν^{'}$ to be these nodes (since $C_{k} \cap C_{k^{'}} = \emptyset$ ). So, suppose there is no s so that $C_{k}$ and $C_{k^{'}}$ both contain a node of length s. Let μ be the ⊆-minimal node in $C_{k}$ and let $μ^{'}$ be the ⊆-minimal node in $C_{k^{'}}$ . Let $s = | μ |$ , and let $s^{'} = | μ^{'} |$ . Thus, $s \neq s^{'}$ . Without loss of generality, assume $s < s^{'}$ . This entails that $C_{k}$ contains a terminal node of S; let τ denote this node and let $t = | τ |$ . Thus, $h_{k} = ϕ (τ)$ . Furthermore, $t < s^{'}$ . Let $μ^{″}$ denote the length t ancestor of $μ^{'}$ . Since τ is a terminal node of S, τ and $μ^{″}$ are incomparable. Thus, τ and $μ^{'}$ are incomparable. □

For the sake of proving Theorem 3.5, we prove the following existence result.
Proposition 4.2.
If $ϕ : S \to ℓ^{p}$ is a disintegration, and if ν is a nonterminal node of S, then $\begin{matrix} max {{‖ ϕ (ν^{'}) ‖}_{p}^{p} : ν^{'} \in ν_{S}^{+}} \end{matrix}$ exists.
Proof.
Since ϕ is a disintegration, $ϕ (ν) = \sum_{ν^{'} \in ν_{S}^{+}} ϕ (ν^{'})$ . Since ϕ maps incomparable nodes to disjointly supported vectors it follows that $\begin{matrix} \sum_{ν^{'} \in ν_{S}^{+}} {‖ ϕ (ν^{'}) ‖}_{p}^{p} = {‖ ϕ (ν) ‖}_{p}^{p} < \infty . \end{matrix}$ Therefore, there is a finite set ${ν_{0}^{'}, \dots, ν_{t}^{'}} \subseteq ν_{S}^{+}$ so that $\begin{matrix} {‖ ϕ (ν^{'}) ‖}_{p}^{p} ⩽ max {{‖ ϕ (ν_{0}^{'}) ‖}_{p}^{p}, \dots, {‖ ϕ (ν_{t}^{'}) ‖}_{p}^{p}} \end{matrix}$ whenever $ν^{'} \in ν_{S}^{+} - {ν_{0}^{'}, \dots, ν_{t}^{'}}$ . Thus, $\begin{matrix} sup {{‖ ϕ (ν^{'}) ‖}_{p}^{p} : ν^{'} \in ν_{S}^{+}} = max {{‖ ν_{0}^{'} ‖}_{p}^{p}, \dots, {‖ ν_{t}^{'} ‖}_{p}^{p}} . \end{matrix}$ □

For the sake of proving Theorem 3.6, we prove the following existence theorem; Theorem 3.6 will then be demonstrated by a search procedure. Recall that the success index of a partial disintegration, which was defined in Section 3, measures how close a partial disintegration is to being a disintegration. Theorem 4.3.
Suppose $F = {f_{0}, f_{1}, \dots}$ is a generating set for $ℓ^{p}$ . If $ϕ : S - {\emptyset} \to ℓ^{p}$ is a partial disintegration, and if $N_{0} \in N$ , then ϕ extends to a partial disintegration ψ whose success index (with respect to F) is larger than $N_{0}$ .
Proof.
There is a nonnegative integer $N_{1}$ so that $d (f_{j}, ⟨ e_{0}, \dots, e_{N_{1}} ⟩) < 2^{- N_{0}}$ whenever $0 ⩽ j < N_{0}$ and so that $d (ϕ (ν), ⟨ e_{0}, \dots, e_{N_{1}} ⟩) < 2^{- N_{0}}$ whenever $ν \in S - {\emptyset}$ .

When $0 ⩽ k ⩽ N_{1}$ , let $ν_{k} = \emptyset$ if $k \notin ⋃_{ν \in S} supp (ϕ (ν))$ ; otherwise let $ν_{k}$ denote the ⊆-maximal node in S so that $k \in supp (ϕ (ν))$ .

Intuitively, we define ψ so that its range includes nonzero scalar multiples of each of $e_{0}, \dots, e_{N_{1}}$ . We first define the domain of ψ. Let $\begin{matrix} S^{'} = S \cup {ν_{k}^{⌢} (k + # S) : 0 ⩽ k ⩽ N_{1} \land (ν_{k} = \emptyset \lor # supp (ϕ (ν_{k})) ⩾ 2)} . \end{matrix}$ (Here, $# A$ denotes the cardinality of A, and $^{⌢}$ denotes concatenation.) Let $ψ (ν) = ϕ (ν)$ if $ν \in S - {\emptyset}$ . Suppose $ν_{k}^{⌢} (k + # S) \in S^{'}$ . Let $\begin{matrix} ψ (ν^{⌢} (k + # S)) = \{\begin{matrix} ϕ (ν_{k}) \cdot e_{k} & if ν_{k} \neq \emptyset, \\ e_{k} & otherwise . \end{matrix} \end{matrix}$ Thus, by construction, ψ is a partial disintegration, and ψ extends ϕ.

We claim that the success index of ψ is at least as large as $N_{0}$ . For, by construction, $e_{0}, \dots, e_{N_{1}} \in ⟨ ran (ψ) ⟩$ . Thus, by choice of $N_{1}$ , $d (f_{j}, ⟨ ran (ψ) ⟩) < 2^{- N_{0}}$ whenever $0 ⩽ j < N_{0}$ . Suppose ν is a nonterminal node of $S^{'}$ . Thus, by definition of $S^{'}$ , $ν \in S$ . We show that $\begin{matrix} (1) & {‖ ψ (ν) - \sum_{ν^{'} \in ν_{S^{'}}^{+}} ψ (ν^{'}) ‖}_{p} < 2^{- N_{0}} . \end{matrix}$ Since $ν \in S$ , $ψ (ν) = ϕ (ν)$ . By choice of $N_{1}$ , $‖ ϕ (ν) - ϕ (ν) \cdot χ_{{0, \dots, N_{1}}} ‖_{p} < 2^{- N_{0}}$ . By definition of $S^{'}$ , whenever $0 ⩽ k < N_{1}$ and $k \in supp (ϕ (ν))$ , k belongs to the support of $ϕ (ν^{'})$ for some child $ν^{'}$ of ν in $S^{'}$ ; furthermore $ϕ (ν) \cdot e_{k} ⪯ ψ (ν^{'})$ . The inequality (1) follows. □

4.2. On the distance to the nearest strong reverse-order homomorphism

Let S be a finite nonempty subset of $ω^{< ω}$ . Define $ℓ_{S}^{p}$ to be the space of all functions that map S into $ℓ^{p}$ . When $ϕ \in ℓ_{S}^{p}$ , define $‖ ϕ ‖_{S}$ to be $max {‖ ϕ (ν) ‖_{p} : ν \in S}$ . Thus, $‖ ‖_{S}$ is a norm on $ℓ_{S}^{p}$ under which $ℓ_{S}^{p}$ is a Banach space.

Suppose $ϕ \in ℓ_{S - {\emptyset}}^{p}$ is a partial disintegration, and let $S^{'} \supseteq S$ be a finite subtree of $ω^{< ω}$ . Define $H_{ϕ, S^{'}}$ to be the set of all strong reverse-order homomorphisms $ψ \in ℓ_{S^{'} - {\emptyset}}^{p}$ so that $ψ (ν) = ϕ (ν)$ whenever ν is a non-root node of S. Thus, $H_{ϕ, S^{'}}$ is a closed subset of $ℓ_{S^{'} - {\emptyset}}^{p}$ . For the sake of a search procedure we will employ in the proof of Theorem 3.6, we wish to find a reasonable upper bound on $d (ψ, H_{ϕ, S^{'}})$ in terms of ϕ, ψ.

When $p \neq 2$ , set $c_{p} = | 4 - 2 {\sqrt{2}}^{p} |^{- 1}$ . When $z, w \in C$ set $σ (z, w) = c_{p} σ_{1} (z, w)$ . As a first step toward bounding $d (ψ, H_{ϕ, S^{'}})$ above, we prove the following sharpening of an inequality due to J. Lamperti [7].

Theorem 4.4.
Suppose $p ⩾ 1$ and $p \neq 2$ . Then, $\begin{matrix} (2) & min {| z |^{p}, | w |^{p}} ⩽ σ (z, w) \end{matrix}$ for all $z, w \in C$ . Furthermore, if $1 ⩽ p < 2$ , then $\begin{matrix} 2 | z |^{p} + 2 | w |^{p} - | z + w |^{p} - | z - w |^{p} ⩾ 0 \end{matrix}$ and if $2 < p$ then $\begin{matrix} 2 | z |^{p} + 2 | w |^{p} - | z + w |^{p} - | z - w |^{p} ⩽ 0 . \end{matrix}$
Proof.
Without loss of generality, assume $0 < | z | ⩽ | w |$ . Set $w / z = t e^{i θ}$ where $t ⩾ 1$ . Then, (2) reduces to $\begin{matrix} 1 ⩽ \frac{| 2 + 2 t^{p} - | 1 + t e^{i θ} |^{p} - | 1 - t e^{i θ} |^{p} |}{| 4 - 2 {\sqrt{2}}^{p} |} . \end{matrix}$ This leads to consideration of the function $\begin{matrix} f_{p} (θ, t) : = \{\begin{matrix} 2 + 2 t^{p} - | 1 + t e^{i θ} |^{p} - | 1 - t e^{i θ} |^{p}, & 1 ⩽ p < 2, \\ | 1 + t e^{i θ} |^{p} + | 1 - t e^{i θ} |^{p} - 2 t^{p} - 2, & p > 2 . \end{matrix} \end{matrix}$ We show that $\begin{matrix} min_{t ⩾ 1} f_{p} (θ, t) = | 4 - 2 {\sqrt{2}}^{p} | . \end{matrix}$ We note that $f_{p} (θ + π, t) = f_{p} (θ, t)$ . So, we restrict attention to values of θ between 0 and π. We use basic multivariable calculus to minimize $f_{p} (θ, t)$ in the region $[0, π] \times [1, \infty)$ . To this end, we first note that $\begin{matrix} \frac{\partial}{\partial t} | 1 \pm t e^{i θ} | = \frac{t \pm cos (θ)}{| 1 \pm t e^{i θ} |} \end{matrix}$ and that $\begin{matrix} \frac{\partial}{\partial θ} | 1 \pm t e^{i θ} | = \frac{\mp t sin (θ)}{| 1 \pm t e^{i θ} |} . \end{matrix}$ It follows that when $1 ⩽ p < 2$ : $\begin{array}{l} \frac{\partial f_{p}}{\partial t} (θ, t) = 2 p t^{p - 1} - p [(t - cos (θ)) {| 1 - t e^{i θ} |}^{p - 2} + (t + cos (θ)) {| 1 + t e^{i θ} |}^{p - 2}], \\ \frac{\partial f_{p}}{\partial θ} (θ, t) = p t sin (θ) [{| 1 + t e^{i θ} |}^{p - 2} - {| 1 - t e^{i θ} |}^{p - 2}] . \end{array}$ The signs are reversed when $p > 2$ .

So, when $0 < θ_{0} < π$ and $t_{0} ⩾ 1$ , $\begin{array}{rcl} \frac{\partial f_{p}}{\partial θ} (θ_{0}, t_{0}) = 0 & \Leftrightarrow & | 1 + t_{0} e^{i θ_{0}} | = | 1 - t e^{i θ_{0}} | \\ \Leftrightarrow & θ_{0} = π / 2 . \end{array}$ We now claim that $\frac{\partial f_{p}}{\partial t} (π / 2, t_{0}) > 0$ when $t_{0} ⩾ 1$ . We first consider the case $1 ⩽ p < 2$ . We have $\begin{matrix} \frac{\partial f_{p}}{\partial t} (π / 2, t) = 2 p t^{p - 1} - 2 p t | 1 + t i |^{p - 2} . \end{matrix}$ Since $t < | 1 + t i |$ and $p - 2 < 0$ , $t^{p - 2} > | 1 + t i |^{p - 2}$ . Thus, $\frac{\partial f_{p}}{\partial t} (π / 2, t_{0}) > 0$ . The case $2 < p$ is symmetric; the signs are merely reversed and $p - 2 > 0$ .

We next claim that $\frac{\partial f_{p}}{\partial t} (0, t) ⩾ 0$ if $t ⩾ 1$ . We first consider the case $1 ⩽ p < 2$ . In this case the claim reduces to $\begin{matrix} 2 ⩾ {(\frac{t - 1}{t})}^{p - 1} + {(\frac{t + 1}{t})}^{p - 1} . \end{matrix}$ Since $0 ⩽ p - 1 < 1$ , $x \mapsto x^{p - 1}$ is concave. Thus, $\begin{matrix} 1 = {(\frac{\frac{t - 1}{t} + \frac{t + 1}{t}}{2})}^{p - 1} ⩾ \frac{1}{2} [{(\frac{t - 1}{t})}^{p - 1} + {(\frac{t + 1}{t})}^{p - 1}] . \end{matrix}$ This verifies the claim when $1 ⩽ p < 2$ . The case $2 < p$ is symmetric: signs are reversed and the function $x \mapsto x^{p - 1}$ is convex.

Thus, $\frac{\partial f_{p}}{\partial t} (π, t) ⩾ 0$ if $1 ⩽ t$ .

So, let $t_{0} > 1$ , and let R denote the rectangle $[0, π] \times [1, t_{0}]$ . It follows from what has just been shown that the minimum of $f_{p}$ on R is achieved on the lower line segment $[0, π] \times {1}$ . Moreover, it is achieved at one of the points $(0, 1)$ , $(π / 2, 1)$ , $(π, 1)$ . $f_{p} (0, 1) = f_{p} (0, π) = | 2 - 2^{p} |$ and $f_{p} (0, π / 2) = | 4 - 2 {\sqrt{2}}^{p} |$ . Since $p \neq 2$ , it follows that $| 4 - 2^{p} | > | 4 - 2 {\sqrt{2}}^{p} |$ . Thus, the minimum of $f_{p}$ on R is $| 4 - 2 {\sqrt{2}}^{p} |$ . Since $t_{0}$ can be any number larger than 1, the minimum of $f_{p}$ on $[0, π] \times [1, \infty)$ is $| 4 - 2 {\sqrt{2}}^{p} |$ .

The theorem now follows. □

When $ψ \in ℓ_{S}^{p}$ , set $\begin{matrix} σ (ψ) = \sum_{ν | ν^{'}} σ (ψ (ν), ψ (ν^{'})) + \sum_{ν^{'} \supset ν} σ (ψ (ν^{'}) - ψ (ν), ψ (ν^{'})) \end{matrix}$ where ν, $ν^{'}$ range over all nodes of S and $ν | ν^{'}$ denotes that ν and $ν^{'}$ are incomparable. Note that $σ : ℓ_{S}^{p} \to [0, \infty)$ is continuous and $σ (ψ) = 0$ if and only if ψ is a strong order homomorphism. The following is the main result of this subsection.
Theorem 4.5.
Suppose $ϕ \in ℓ_{S - {\emptyset}}^{p}$ is a partial disintegration. Suppose $ψ \in ℓ_{S^{'} - {\emptyset}}^{p}$ where $S^{'} \supseteq S$ is a finite subtree of $ω^{< ω}$ so that each node in $S^{'}$ extends a node in S. Then, $\begin{matrix} d {(ψ, H_{ϕ, S^{'}})}^{p} ⩽ ‖ ϕ |_{S - {\emptyset}} - ψ |_{S - {\emptyset}} ‖_{S - {\emptyset}}^{p} + 2^{p} σ (ϕ \cup ψ |_{S^{'} - S}) . \end{matrix}$
Proof.
Let $ψ_{0} = ϕ \cup ψ |_{S^{'} - S}$ . Set $\begin{array}{rcl} \hat{σ} (ψ_{0}) (n) & = & \sum_{ν | ν^{'}} min {{| ψ_{0} (ν) (n) |}^{p}, {| ψ_{0} (ν^{'}) (n) |}^{p}} \\ + \sum_{ν^{'} \supset ν} min {{| ψ_{0} (ν^{'}) (n) - ψ_{0} (ν) (n) |}^{p}, {| ψ_{0} (ν^{'}) (n) |}^{p}} \end{array}$ where ν, $ν^{'}$ range over the nodes of $S^{'} - {\emptyset}$ . Thus, by Theorem 4.4, $\sum_{n} \hat{σ} (ψ_{0}) (n) ⩽ σ (ψ_{0})$ .

We now construct $ψ_{1}$ . If $ν \in S - {\emptyset}$ , set $ψ_{1} (ν) = ϕ (ν)$ . If $ν \in S^{'} - S$ , and if $n \in N$ , set $\begin{matrix} ψ_{1} (ν) (n) = \{\begin{matrix} ψ_{1} (ν^{-}) (n) & if | ψ_{0} (ν) (n) |^{p} > \hat{σ} (ψ_{0}) (n) a n d ν^{-} \neq \emptyset, \\ ψ (ν) (n) & if | ψ_{0} (ν) (n) |^{p} > \hat{σ} (ψ_{0}) (n) a n d ν^{-} = \emptyset, \\ 0 & otherwise . \end{matrix} \end{matrix}$

By construction $ψ_{1}$ is a reverse-order homomorphism. We show it is a strong reverse-order homomorphism. Suppose $ν, ν^{'} \in S^{'}$ are incomparable. Since $ψ_{1}$ is a reverse-order homomorphism, it suffices to consider the case where $ν, ν^{'} \notin S$ . Suppose $ψ_{1} (ν) (n) \neq 0$ . Then, $| ψ_{0} (ν) (n) |^{p} > \hat{σ} (ψ_{0}) (n)$ . So, $| ψ_{0} (ν) (n) |^{p} > | ψ_{0} (ν^{'}) (n) |^{p}$ . Thus, $\hat{σ} (ψ_{0}) (n) ⩾ | ψ_{0} (ν^{'}) (n) |^{p}$ . Hence, $ψ_{1} (ν^{'}) (n) = 0$ . Thus, $ψ_{1} (ν)$ and $ψ_{1} (ν^{'})$ are disjointly supported.

If $ν \in S - {\emptyset}$ , then $‖ ψ (ν) - ψ_{1} (ν) ‖_{p} = ‖ ψ (ν) - ϕ (ν) ‖_{p}$ . Suppose $ν \in S^{'} - S$ . Let $n \in N$ . It suffices to show that $| ψ (ν) (n) - ψ_{1} (ν) (n) |^{p} ⩽ 2^{p} \hat{σ} (ψ_{0}) (n)$ . We first consider the case $ψ_{1} (ν) (n) = 0$ . We can assume $| ψ (ν) (n) |^{p} > \hat{σ} (ψ_{0}) (n)$ . Thus, there exists $μ \subset ν$ so that $ψ_{1} (μ) (n) = 0$ ; take the least such μ. Therefore $| ψ_{0} (μ) (n) |^{p} ⩽ \hat{σ} (ψ_{0}) (n)$ . On the other hand, $| ψ_{0} (μ) (n) - ψ_{0} (ν) (n) |^{p} ⩽ \hat{σ} (ψ_{0}) (n)$ . Therefore, $| ψ (ν) (n) |^{p} ⩽ 2^{p} \hat{σ} (ψ_{0}) (n)$ . Now, suppose $ψ_{1} (ν) (n) \neq 0$ . Then, $| ψ (ν) (n) |^{p} > \hat{σ} (ψ_{0}) (n)$ . Let $ν_{0}$ denote the maximum prefix of ν that belongs to S or has length 1. Then, $ψ_{1} (ν) (n) = ψ_{0} (ν_{0}) (n)$ . However, $| ψ (ν) (n) - ψ (ν_{0}) (n) |^{p} ⩽ \hat{σ} (ψ_{0}) (n)$ . □

We note that the hypothesis that each node of $S^{'}$ extends a node in S is not superfluous. For, let $p = 1$ . Choose $x > 0$ so that $2 σ (x, 1) < 1$ . Let $S = {(0)}$ , and let $ϕ = {((0), x e_{0})}$ . Let $S^{'} = {(0), (1)}$ , and let $ψ = ϕ \cup {((1), e_{0})}$ . If $ψ^{'} : S^{'} \to ℓ^{1}$ is a strong reverse-order homomorphism that extends ϕ, then $‖ ψ^{'} - ψ ‖_{S^{'}} ⩾ 1 > 2 σ (ψ)$ .
5. Computable world

5.1. Proof of Theorem 3.5

Suppose $ϕ : S \to ℓ^{p}$ is a disintegration that is computable with respect to F. Since ϕ is computable, S is c.e.; fix a computable enumeration of S, ${S_{t}}_{t \in N}$ . We can choose this enumeration so that each $S_{t}$ is a finite subtree of $ω^{< ω}$ .

It suffices to show that from a nonterminal node $μ \in S$ we can compute an almost-norm maximizing child of μ in S. We base the proof of this claim on a sequence of lemmas as follows. When $ν \in S_{t}$ , let $ν_{t}^{+}$ abbreviate $ν_{S_{t}}^{+}$ .

Lemma 5.1.
If ν is a non-root and nonterminal node of S, then there are infinitely many numbers t so that $\begin{matrix} (3) & {‖ ϕ (ν) ‖}_{p}^{p} - \sum_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} < max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{t}^{+}} . \end{matrix}$ When t is such a number, $\begin{matrix} max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{t}^{+}} = max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{S}^{+}} . \end{matrix}$
Proof.
By Proposition 4.2, there is a $μ_{0} \in ν_{S}^{+}$ so that $\begin{matrix} {‖ ϕ (μ_{0}) ‖}_{p}^{p} = max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{S}^{+}} . \end{matrix}$ Since ϕ is a disintegration, $‖ ϕ (μ_{0}) ‖_{p}^{p} \neq 0$ and $\begin{matrix} lim_{t \to \infty} {‖ ϕ (ν) ‖}_{p}^{p} - \sum_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} = 0 . \end{matrix}$ Thus, there are infinitely many numbers t so that (3) holds.

Now, suppose t is a number so that (3) holds. By way of contradiction, suppose $‖ ϕ (μ_{0}) ‖_{p}^{p} > max {μ \in ν_{t}^{+} : ‖ ϕ (μ) ‖_{p}^{p}}$ . Therefore, $\begin{matrix} {‖ ϕ (ν) ‖}_{p}^{p} < \sum_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} + {‖ ϕ (μ_{0}) ‖}_{p}^{p} . \end{matrix}$ Since $μ_{0} \in ν_{S}^{+}$ but $μ_{0} \notin ν_{t}^{+}$ , it follows that $μ_{0}$ is incomparable with every node in $ν_{t}^{+}$ . So, since ϕ maps incomparable nodes to disjointly supported vectors, $\begin{matrix} \sum_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} + {‖ ϕ (μ_{0}) ‖}_{p}^{p} ⩽ \sum_{μ \in ν_{S}^{+}} {‖ ϕ (ν) ‖}_{p}^{p} = {‖ ϕ (ν) ‖}_{p}^{p} . \end{matrix}$ This is a contradiction. Therefore, $‖ ϕ (μ_{0}) ‖_{p}^{p} = max {‖ ϕ (μ) ‖_{p}^{p} : μ \in ν_{S}^{+}}$ . □

Since ϕ is computable with respect to F, $ν \mapsto ‖ ϕ (ν) ‖_{p}$ is computable. So, there is a computable function $q : S \times N \to Q$ so that $| q (ν, t) - ‖ ϕ (ν) ‖_{p}^{p} | < 2^{- (t + 1)}$ . Set: $\begin{array}{l} m (ν, t) = min {q (ν, t) - 2^{- (t + 1)}, 0}, \\ M (ν, t) = q (ν, t) + 2^{- (t + 1)}, \\ Σ^{-} (X, t) = \sum_{ν \in X} m (ν, t), \\ \overline{m} (X, t) = max {m (μ, t) : μ \in X} . \end{array}$ Thus, $m (ν, t)$ is a lower bound on $‖ ϕ (ν) ‖_{p}^{p}$ , and $M (ν, t)$ is an upper bound on $‖ ϕ (ν) ‖_{p}^{p}$ . $Σ^{-} (ν_{t}^{+}, t)$ is a lower bound on $\sum_{μ \in ν_{S}^{+}} ‖ ϕ (μ) ‖_{p}^{p}$ , and $\overline{m} (ν_{t}^{+}, t)$ is a lower bound on $max {‖ ϕ (μ) ‖_{p}^{p} : μ \in ν_{S}^{+}}$ . Also $\overline{m} (ν_{t}^{+}, t) + 2^{- t}$ is an upper bound on $max {‖ ϕ (μ) ‖_{p}^{p} : μ \in ν_{S}^{+}}$ .
Lemma 5.2.
Suppose ν is a non-root and nonterminal node of S. Then, there are infinitely many stages t so that $M (ν, t) - Σ^{-} (ν_{t}^{+}, t) < \overline{m} (ν_{t}^{+}, t)$ . At such a stage t, $\begin{matrix} 0 ⩽ max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{S}^{+}} - \overline{m} (ν_{t}^{+}, t) < 2^{- t} . \end{matrix}$
Proof.
Let $N \in N$ . By Lemma 5.1, there is a stage $t_{0} > N$ so that $\begin{matrix} {‖ ϕ (ν) ‖}_{p}^{p} - \sum_{μ \in ν_{t_{0}}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} < max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{t_{0}}^{+}} . \end{matrix}$ Set $U = ν_{t_{0}}^{+}$ . Then, $\begin{matrix} lim_{t \to \infty} M (ν, t) - Σ^{-} (U, t) = {‖ ϕ (μ) ‖}_{p}^{p} - \sum_{μ \in U} {‖ ϕ (μ) ‖}_{p}^{p} \end{matrix}$ and, $\begin{matrix} lim_{t \to \infty} \overline{m} (ν_{t}^{+}, t) = max {μ \in ν_{S}^{+} : {‖ ϕ (μ) ‖}_{p}^{p}} . \end{matrix}$ So, there is a number $t_{1} > t_{0}$ so that $\begin{matrix} M (ν, t_{1}) - Σ^{-} (U, t_{1}) < \overline{m} (ν_{t_{1}}^{+}, t_{1}) . \end{matrix}$ By definition, $m (ν, t) ⩾ 0$ . Since $t_{1} > t_{0}$ , $U \subseteq ν_{t_{1}}^{+}$ . Thus, $M (ν, t_{1}) - Σ^{-} (ν_{t_{1}}^{+}, t_{1}) < \overline{m} (ν_{t_{1}}^{+}, t_{1})$ .

Now, suppose $M (ν, t) - Σ^{-} (ν_{t}^{+}, t) < \overline{m} (ν_{t}^{+}, t)$ . By definition of M, $Σ^{-}$ , m, $\begin{matrix} {‖ ϕ (ν) ‖}_{p}^{p} - \sum_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} ⩽ M (ν, t) - Σ^{-} (ν_{t}^{+}, t), \end{matrix}$ and $\begin{matrix} \overline{m} (ν_{t}^{+}, t) ⩽ max_{μ \in ν_{t}^{+}} {‖ ϕ (μ) ‖}_{p}^{p} . \end{matrix}$ So, by Lemma 5.1, $\begin{matrix} max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{S}^{+}} = max {{‖ ϕ (μ) ‖}_{p}^{p} : μ \in ν_{t}^{+}} . \end{matrix}$ Furthermore, $\begin{matrix} max {{‖ ϕ (ν) ‖}_{p}^{p} : μ \in ν_{t}^{+}} < \overline{m} (ν, t) + 2^{- t} . \end{matrix}$ This proves the lemma. □

Now, suppose μ is a nonterminal node of S. Search for $t > | μ |$ so that $\begin{matrix} M (μ, t) - Σ^{-} (μ_{t}^{+}, t) < \overline{m} (μ_{t}^{+}, t) . \end{matrix}$ Then, find $τ \in μ_{t}^{+}$ so that $m (τ, t) = \overline{m} (μ_{t}^{+}, t)$ . Therefore, $\begin{array}{rcl} max {{‖ ϕ (μ^{'}) ‖}_{p}^{p} : μ^{'} \in μ^{+}} & = & max {{‖ ϕ (μ^{'}) ‖}_{p}^{p} : μ^{'} \in μ_{t}^{+}} \\ < & m (τ, t) + 2^{- t} \\ < & m (τ, t) + 2^{- | μ |} \\ ⩽ & {‖ ϕ (τ) ‖}_{p}^{p} + 2^{- | μ |} . \end{array}$ Thus, τ is an almost norm-maximizing child of μ in S.
5.2. Proof of Theorem 3.6

Suppose $F = {f_{0}, f_{1}, \dots}$ is an effective generating set for $ℓ^{p}$ . Let $F^{S}$ denote the set of all maps from S into F. It follows that $F^{S}$ is an effective generating set for $ℓ_{S}^{p}$ ; i.e. $(ℓ_{S}^{p}, F^{S})$ is a computable Banach space. Furthermore, $L_{Q (i)} (F^{S})$ coincides with the set of all maps from S into $L_{Q (i)} (F)$ .

We now introduce some notation. Suppose $S^{'}$ is a finite subtree of $ω^{< ω}$ that includes S. Let: $\begin{array}{l} M_{S^{'}} = {ψ \in ℓ_{S^{'} - {\emptyset}}^{p} : ψ is injective}, \\ Δ_{S^{'}, N} = {ψ \in ℓ_{S^{'} - {\emptyset}}^{p} : \forall 0 ⩽ j < N d (f_{j}, ⟨ ran (ψ) ⟩) < 2^{- N}} . \end{array}$ Let $S_{S^{'}, N}$ denote the set of all $ψ \in ℓ_{S^{'} - {\emptyset}}^{p}$ so that $\begin{matrix} {‖ ψ (ν) - \sum_{ν^{'} \in ν_{S^{'}}^{+}} ψ (ν^{'}) ‖}_{p} < 2^{- N} \end{matrix}$ whenever ν is a non-root and nonterminal node of $S^{'}$ .

Lemma 5.3.

If each node of $S^{'}$ extends a node of S, then $H_{ϕ, S^{'}}$ is c.e. closed uniformly in ϕ, $S^{'}$ .

The sets $M_{S}$ , $Δ_{S^{'}, N}$ , $S_{S^{'}, N}$ are c.e. open uniformly in S, $S^{'}$ , N.

Proof.
(1): When $ψ \in ℓ_{S^{'} - {\emptyset}}^{p}$ , set $\begin{matrix} E (ψ) = {‖ ψ^{'} |_{S - {\emptyset}} - ϕ |_{S - {\emptyset}} ‖}_{p}^{p} + 2^{p} σ (ϕ \cup ψ^{'} |_{S^{'} - S}) . \end{matrix}$ Therefore, $ψ \in H_{ϕ, S^{'}}$ if and only if $E (ψ) = 0$ . By Theorem 4.5, $d (ψ, H_{ϕ, S^{'}}) ⩽ E {(ψ)}^{1 / p}$ . Since $ϕ, p$ are computable, $E$ is computable. Thus, by Proposition 2.2, $H_{ϕ, S^{'}}$ is c.e. closed.

(2): When $ψ \in ℓ_{S}^{p}$ , let $\begin{matrix} G_{1} (ψ) = min {{‖ ψ (ν) - ψ (ν^{'}) ‖}_{p} : ν, ν^{'} \in S \land ν \neq ν^{'}} . \end{matrix}$ Therefore, $G_{1}$ is computable with respect to $F^{S^{'}}$ . Since, $M_{S^{'}} = G_{1}^{- 1} [(0, \infty)]$ , $M_{S^{'}}$ is c.e. open.

When $ψ \in ℓ_{S^{'}}^{p}$ , let $G_{2} (ψ)$ denote the minimum of $\begin{matrix} {‖ ψ (ν) - \sum_{ν^{'} \in ν_{S^{'}}^{+}} ψ (ν^{'}) ‖}_{p} \end{matrix}$ as ν ranges over the nonterminal non-root nodes of $S^{'}$ . It follows that $G_{2}$ is computable with respect to $F^{S^{'}}$ and so $S_{S^{'}, N} = G_{2}^{- 1} [(- \infty, 2^{- N})]$ is c.e. open.

Note that $ψ \in Δ_{S^{'}, N}$ if and only if there exists $β : {0, \dots, N - 1} \times S^{'} - {\emptyset} \to Q (i)$ so that $\begin{matrix} {‖ f_{j} - \sum_{ν \in S^{'} - {\emptyset}} β (j, ν) ψ (ν) ‖}_{p} < 2^{- N} \end{matrix}$ whenever $0 ⩽ j < N$ . When $β : {0, \dots, N - 1} \times S^{'} - {\emptyset} \to Q (i)$ , set $\begin{matrix} Δ_{S^{'}, N, β} = {ψ \in ℓ_{S^{'} - {\emptyset}}^{p} : \forall 0 ⩽ j < N {‖ f_{j} - \sum_{ν \in S^{'} - {\emptyset}} β (j, ν) ψ (ν) ‖}_{p} < 2^{- N}} . \end{matrix}$ Thus, $Δ_{S^{'}, N} = ⋃_{β} Δ_{S^{'}, N, β}$ . Set $\begin{matrix} G_{3, β} (ψ) = max {{‖ f_{j} - \sum_{ν \in S^{'} - {\emptyset}} β (j, ν) ψ (ν) ‖}_{p} : 0 ⩽ j < N} . \end{matrix}$ Therefore, $Δ_{S^{'}, N, β} = G_{3, β}^{- 1} [(- \infty, 2^{- N})]$ . Hence, $Δ_{S^{'}, N, β}$ is c.e. open uniformly in $S^{'}$ , N, β. Thus, $Δ_{S^{'}, N}$ is c.e. open uniformly in $S^{'}$ , N. □

We can now prove Theorems 3.6 and 3.2. Proof of Theorem 3.6.
For the moment, fix a finite tree $S^{'} \supseteq S$ . When $S^{'} \supseteq S$ , let $π_{S^{'}}$ denote the canonical projection of $ℓ_{S^{'} - {\emptyset}}^{p}$ onto $ℓ_{S - {\emptyset}}^{p}$ , and let $\begin{matrix} C_{S^{'}} = H_{\emptyset, S^{'}} \cap M_{S^{'}} \cap Δ_{S, N} \cap S_{S^{'}, N} \cap π_{S^{'}}^{- 1} [B (ϕ; 2^{- k})] . \end{matrix}$ By Theorem 4.3, there is an $S^{'}$ so that $C_{S^{'}} \neq \emptyset$ . Such an $S^{'}$ can be found by an effective search procedure. Since $H_{\emptyset, S^{'}}$ is c.e. closed, it follows that $C_{S^{'}}$ contains a vector ψ that is computable with respect to $F^{S^{'} - {\emptyset}}$ and an index of ψ can be computed from k, N, and an index of ϕ. □
Proof of Theorem 3.2.
Let $F = {f_{0}, f_{1}, \dots}$ .

Set $S_{0} = {(0)}$ . Compute $j_{0}$ so that $f_{j_{0}} \neq 0$ . Set ${\hat{ϕ}}_{0} ((0)) = f_{j_{0}}$ . By Lemma 5.3, we can compute a $k_{0} \in N$ so that each map in $B ({\hat{ϕ}}_{0}; 2^{- k_{0}})$ is injective and never zero.

It now follows from Theorem 3.6 and Lemma 5.3 that there is a sequence ${{\hat{ϕ}}_{n}}_{n}$ of computable partial disintegrations of $ℓ^{p}$ and a sequence ${k_{n}}_{n}$ of nonnegative integers that have the following properties.
An index of ${\hat{ϕ}}_{n}$ and a canonical index of $dom ({\hat{ϕ}}_{n})$ can be computed from n.

If $S_{n} = dom (ϕ_{n})$ , then $S_{n + 1} \supset S_{n}$ and $‖ {\hat{ϕ}}_{n + 1} |_{S_{n}} - {\hat{ϕ}}_{n} ‖_{S_{n}} < 2^{- (k_{n} + 1)}$ .

Each map in $\overline{B ({\hat{ϕ}}_{n}; 2^{- k_{n}})}$ is injective, never zero, and has a success index that is at least n.

Let $ϕ_{n, t} = {\hat{ϕ}}_{t + n} |_{S_{n}}$ for all $n, t$ . It follows that ${ϕ_{n, t}}_{t}$ is computable with respect to $F^{S_{n} - {\emptyset}}$ ; furthermore, an index of this sequence can be computed from n. It also follows that $‖ ϕ_{n, t + 1} - ϕ_{n, t} ‖_{S_{n}} < 2^{- (k_{n + t} + 1)}$ . Thus, $ϕ_{n} : = {lim}_{t} ϕ_{n, t}$ is computable with respect to $F^{S_{n} - {\emptyset}}$ ; furthermore, an index of $ϕ_{n}$ can be computed from n. Also, $‖ {\hat{ϕ}}_{n} - ϕ_{n} ‖_{S_{n}} ⩽ 2^{- k_{n}}$ . Thus, $ϕ_{n}$ is a partial disintegration whose success index is at least n. By definition, $ϕ_{n, t + 1} \subseteq ϕ_{n + 1, t}$ . Thus, $ϕ_{n} \subseteq ϕ_{n + 1}$ . Let $ϕ = ⋃_{n} ϕ_{n}$ .

Let $S = dom (ϕ)$ . For each $ν \in S$ , let $\begin{matrix} ψ (ν) = 2^{- ν (0)} {‖ ϕ ((ν (0))) ‖}_{p}^{- 1} ϕ (ν) . \end{matrix}$ Then, let $\begin{matrix} ψ (\emptyset) = \sum_{ν \in N^{1} \cap S} ψ (ν) . \end{matrix}$ Since S is computable, it follows that $ψ (\emptyset)$ is a computable with respect to F. It then follows that ψ is a disintegration and is computable with respect to F. □

5.3. Proof of Theorem 2.4

Suppose p is a computable real so that $p ⩾ 1$ and $p \neq 2$ , and assume C is a c.e. set. Again, we can reduce to the consideration of surjective linear endomorphisms of $ℓ^{p}$ . Specifically, it suffices to show there is an effective generating set F for $ℓ^{p}$ so that, with respect to $(E, F)$ , C computes a surjective linear endomorphism of $ℓ^{p}$ and so that any oracle that with respect to $(E, F)$ computes a surjective linear endomorphism of $ℓ^{p}$ also computes C. We demonstrate this as follows.

We can assume C is incomputable. Without loss of generality, we also assume $0 \notin C$ . Let ${c_{n}}_{n \in N}$ be a one-to-one effective enumeration of C. Set $\begin{matrix} γ = \sum_{k \in C} 2^{- k} . \end{matrix}$ Thus, $0 < γ < 1$ , and γ is an incomputable real. Set: $\begin{array}{l} f_{0} = {(1 - γ)}^{1 / p} e_{0} + \sum_{n = 0}^{\infty} 2^{- c_{n} / p} e_{n + 1}, \\ f_{n + 1} = e_{n + 1}, \\ F = {f_{0}, f_{1}, f_{2}, \dots} . \end{array}$ Since $1 - γ > 0$ , we can use the standard branch of $\sqrt[p]{}$ . We divide the rest of the proof into a sequence of lemmas.

Lemma 5.4.
F is an effective generating set.
Proof.
Since $\begin{matrix} {(1 - γ)}^{1 / p} e_{0} = f_{0} - \sum_{n = 1}^{\infty} 2^{- c_{n - 1} / p} f_{n} \end{matrix}$ the closed linear span of F includes E. Thus, F is a generating set for $ℓ^{p}$ . Note that $‖ f_{0} ‖ = 1$ .

Suppose $α_{0}, \dots, α_{M}$ are rational points. When $1 ⩽ j ⩽ M$ , set $\begin{matrix} E_{j} = {| α_{0} 2^{- c_{j - 1} / p} + α_{j} |}^{p} - | α_{0} |^{p} 2^{- c_{j - 1}} . \end{matrix}$ It follows that $\begin{array}{rcl} ‖ α_{0} f_{0} + \dots + α_{M} f_{m} ‖^{p} & = & | α_{0} |^{p} ‖ f_{0} ‖^{p} + E_{1} + \dots + E_{M} \\ = & | α_{0} |^{p} + E_{1} + \dots + E_{m} . \end{array}$ Since $E_{1}, \dots, E_{M}$ can be computed from $α_{0}, \dots, α_{M}$ , $‖ α_{0} f_{0} + \dots + α_{M} f_{M} ‖$ can be computed from $α_{0}, \dots, α_{M}$ . Thus, F is an effective generating set. □
Lemma 5.5.
Every oracle that with respect to F computes a unimodular scalar multiple of $e_{0}$ must also compute C.
Proof.
Suppose that with respect to F, X computes a vector of the form $λ e_{0}$ where $| λ | = 1$ . It suffices to show that X computes ${(1 - γ)}^{- 1 / p}$ .

Fix a rational number $q_{0}$ so that ${(1 - γ)}^{- 1 / p} ⩽ q_{0}$ . Let $k \in N$ be given as input. Compute $k^{'}$ so that $2^{- k^{'}} ⩽ q_{0} 2^{- k}$ . Since X computes $λ e_{0}$ with respect to F, we can use oracle X to compute rational points $α_{0}, \dots, α_{M}$ so that $\begin{matrix} (4) & ‖ λ e_{0} - \sum_{j = 0}^{M} α_{j} f_{j} ‖ < 2^{- k^{'}} . \end{matrix}$ We claim that $| {(1 - γ)}^{- 1 / p} - | α_{0} | | < 2^{- k}$ . For, it follows from (4) that $| λ - α_{0} {(1 - γ)}^{1 / p} | < 2^{- k^{'}}$ . Thus, $| 1 - | α_{0} | {(1 - γ)}^{1 / p} | < 2^{- k^{'}}$ . Hence, $\begin{matrix} | {(1 - γ)}^{- 1 / p} - | α_{0} | | < 2^{- k^{'}} {(1 - γ)}^{- 1 / p} ⩽ 2^{- k^{'}} q_{0} ⩽ 2^{- k} . \end{matrix}$ Since X computes $α_{0}$ from k, X computes ${(1 - γ)}^{- 1 / p}$ . □
Lemma 5.6.
If X computes a surjective isometric endomorphism of $ℓ^{p}$ with respect to $(E, F)$ , then X must also compute C.
Proof.
Let T be a surjective endomorphism of $ℓ^{p}$ , and suppose X computes T with respect to $(E, F)$ . By Theorem 2.1, there exists $j_{0}$ , λ so that $T (e_{j_{0}}) = λ e_{0}$ and $| λ | = 1$ . So, by Lemma 5.5, X computes C. □
Lemma 5.7.
With respect to F, C computes $e_{0}$ .
Proof.
Fix an integer M so that ${(1 - γ)}^{- 1 / p} < M$ .

Let $k \in N$ . Using oracle C, we can compute an integer $N_{1}$ so that $N_{1} ⩾ 3$ and $\begin{matrix} ‖ \sum_{n = N_{1}}^{\infty} 2^{- c_{n - 1} / p} e_{n} ‖ ⩽ \frac{2^{- (k p + 1) / p}}{2^{- (k p + 1) / p} + M} . \end{matrix}$ We can use oracle C to compute a rational number $q_{1}$ so that $| q_{1} - {(1 - γ)}^{- 1 / p} | ⩽ 2^{- (k p + 1) / p}$ . Set $\begin{matrix} g = q_{1} [f_{0} - \sum_{n = 1}^{N_{1} - 1} 2^{- c_{n - 1} / p} f_{n}] . \end{matrix}$ It suffices to show that $‖ e_{0} - g ‖ < 2^{- k}$ . Note that since $1 - γ < 1$ , $| q_{1} {(1 - γ)}^{1 / p} - 1 | ⩽ 2^{- (k p + 1) / p}$ . Note also that $| q_{1} | < M + 2^{- (k p + 1) / p}$ . Thus, $\begin{array}{rcl} ‖ e_{0} - g ‖^{p} & = & {‖ e_{0} - q_{1} {(1 - γ)}^{1 / p} e_{0} - q_{1} \sum_{n = N_{1}}^{\infty} 2^{- c_{n - 1 / p}} e_{n} ‖}^{p} \\ ⩽ & {| q_{1} {(1 - γ)}^{1 / p} - 1 |}^{p} + | q_{1} |^{p} {‖ \sum_{n = N_{1}}^{\infty} 2^{- c_{n - 1} / p} e_{n} ‖}^{p} \\ < & 2^{- (k p + 1)} + 2^{- (k p + 1)} = 2^{- k p} . \end{array}$ Thus, $‖ e_{0} - g ‖ < 2^{- k}$ . This completes the proof of the lemma. □
Lemma 5.8.
With respect to $(E, F)$ , C computes a surjective linear isometry of $ℓ^{p}$ .
Proof.
By Lemma 5.7, C computes $e_{0}$ with respect to F. Thus, C computes ${e_{n}}_{n = 0}^{\infty}$ with respect to F, and it follows that C computes the identity map with respect to $(E, F)$ . □

6. Additional results

Suppose n is a positive integer and $1 ⩽ p < \infty$ . Define $ℓ_{n}^{p}$ to be the set of all $f \in ℓ_{n}^{p}$ so that $f (j) = 0$ whenever $j ⩾ n$ ; i.e. $supp (f) \subseteq {0, \dots, n - 1}$ . Thus, $ℓ_{n}^{p}$ is a subspace of $ℓ^{p}$ , and ${e_{0}, \dots, e_{n - 1}}$ is an effective generating set for $ℓ_{n}^{p}$ . Now, suppose p is computable and $p \neq 2$ . Let F be an effective generating set for $ℓ_{n}^{p}$ . Via the methods of the previous section, we can show that there are disjointly supported unit vectors $f_{1}, \dots, f_{n} \in ℓ_{n}^{p}$ so that each $f_{j}$ is computable with respect to F. Thus, $f_{1}, \dots, f_{n}$ generate $ℓ_{n}^{p}$ . It then follows that $ℓ_{n}^{p}$ is computably categorical. However, since $p \neq 2$ , $ℓ_{n}^{p}$ is not a Hilbert space. Thus, there is a computably categorical Banach space that is not a Hilbert space.

7. Conclusion

To summarize, we have investigated the complexity of isometries between computable copies of $ℓ^{p}$ . We have shown that the halting set bounds the complexity of computing these isometries and that this bound is optimal. Along the way we have strengthened an important inequality due to J. Lamperti. These results stand as a contribution to the emergent program of grafting computable structure theory onto computable analysis. It is anticipated that there will be many other interesting discoveries in this area and that the proofs will present opportunities to blend methods from classical analysis and computability theory.

Footnotes

Acknowledgements

I thank Joe Cima, Johanna Franklin, Xiang Huang, and Don Stull for helpful and inspiring conversation. I also thank the anonymous referees for frankly sharing many helpful suggestions for improving the style of the paper. This work was supported by a Simons Foundation Collaboration Grant for Mathematicians.

References

C.J.

Ash and

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000.

Banach, Theory of Linear Operations, North-Holland Mathematical Library, Vol. 38, North-Holland Publishing Co., Amsterdam, 1987, Translated from the French by F. Jellett, With comments by A. Pełczyński and Cz. Bessaga.

S.B.

Cooper, Computability Theory, Chapman & Hall/CRC, Boca Raton, FL, 2004.

R.J.

Fleming and

J.E.

Jamison, Isometries on Banach Spaces: Function Spaces, Chapman & Hall/CRC Monographs and Surveys in Pure and Applied Mathematics, Vol. 129, Chapman & Hall/CRC, Boca Raton, FL, 2003.

E.B.

Fokina,

Harizanov and

A.G.

Melnikov, Computable model theory, in: Turing’s Legacy: Developments from Turing’s Ideas in Logic,

Downey, ed., Cambridge University Press, Cambridge, 2014.

P.R.

Halmos, Introduction to Hilbert Space and the Theory of Spectral Multiplicity, AMS Chelsea Publishing, Providence, RI, 1998, Reprint of the second (1957) edition.

Lamperti, On the isometries of certain function-spaces, Pacific J. Math. 8 (1958), 459–466. doi:10.2140/pjm.1958.8.459.

T.H.

McNicholl, A note on the computable categoricity of ℓ^p spaces, in: Evolving Computability, Lecture Notes in Comput. Sci., Vol. 9136, Springer, Cham, 2015, pp. 268–275.

A.G.

Melnikov, Computably isometric spaces, J. Symbolic Logic 78(4) (2013), 1055–1085. doi:10.2178/jsl.7804030.

10.

A.G.

Melnikov and

K.M.

Ng, Computable structures and operations on the space of continuous functions, Fundamenta Mathematicae 233(2) (2014), 1–41.

11.

M.B.

Pour-El and

J.I.

Richards, Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989.

12.

Weihrauch, Computable Analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.