A Note on the Computable Categoricity of $\ell ^p$ Spaces

Abstract

Suppose that $p$ is a computable real and that $p \ge 1$. We show that in both the real and complex case, $\ell ^p$ is computably categorical if and only if $p = 2$. The proof uses Lamperti’s characterization of the isometries of Lebesgue spaces of $\sigma$-finite measure spaces.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

When $p$ is a positive real number, let $\ell ^p$ denote the space of all sequences of complex numbers $\{a_n\}_{n = 0}^\infty$ so that

$$ \sum _{n = 0}^\infty |a_n|^p < \infty . $$

$\ell ^p$ is a vector space over $\mathbb {C}$ with the usual scalar multiplication and vector addition. When $p \ge 1$ it is a Banach space under the norm defined by

$$ \left\| \{a_n\}_n \right\| = \left( \sum _{n = 0}^\infty |a_n|^p \right) ^{1/p}. $$

Loosely speaking, a computable structure is computably categorical if all of its computable copies are computably isomorphic. In 1989, Pour-El and Richards showed that $\ell ^1$ is not computably categorical [10]. It follows from a recent result of A.G. Melnikov that $\ell ^2$ is computably categorical [8]. At the 2014 Conference on Computability and Complexity in Analysis, A.G. Melnikov asked “For which computable reals $p \ge 1$ is $\ell ^p$ computably categorical?" The following theorem answers this question.

Theorem 1

Suppose $p$ is a computable real so that $p \ge 1$. Then, $\ell ^p$ is computably categorical if and only if $p = 2$.

We prove Theorem 1 by proving the following stronger result.

Theorem 2

Suppose $p$ is a computable real so that $p \ge 1$ and $p \ne 2$. Suppose $C$ is a c.e. set. Then, there is a computable copy of $\ell ^p$, $\mathcal {B}$, so that $C$ computes a linear isometry of $\ell ^p$ onto $\mathcal {B}$. Furthermore, if an oracle $X$ computes a linear isometry of $\ell ^p$ onto $\mathcal {B}$, then $X$ must also compute $C$.

These results also hold for $\ell ^p$-spaces over the reals. In a forthcoming paper it will be shown that $\ell ^p$ is $\varDelta _2^0$-categorical.

The paper is organized as follows. Section 2 covers background and motivation. Section 3 presents the proof of Theorem 2. Concluding remarks are presented in Sect. 4.

2 Background

2.1 Background from Functional Analysis

Fix $p$ so that $1 \le p < \infty$. A generating set for $\ell ^p$ is a subset of $\ell ^p$ with the property that $\ell ^p$ is the closure of its linear span.

Let $e_n$ be the vector in $\ell ^p$ whose $(n+1)$st component is $1$ and whose other components are $0$. Let $E = \{e_n\ :\ n \in \mathbb {N}\}$. We call $E$ the standard generating set for $\ell ^p$.

Recall that an isometry of $\ell ^p$ is a norm-preserving map of $\ell ^p$ into $\ell ^p$. We will use the following classification of the surjective linear isometries of $\ell ^p$.

Theorem 3

(Banach/Lamperti). Suppose $p$ is a real number so that $p \ge 1$ and $p \ne 2$. Let $T$ be a linear map of $\ell ^p$ into $\ell ^p$. Then, the following are equivalent.

• 1. $T$ is a surjective isometry.

• 2. There is a permutation of $\mathbb {N}$, $\phi$, and a sequence of unimodular points, $\{\lambda _n\}_n$, so that $T(e_n) = \lambda _n e_{\phi (n)}$ for all $n$.

• 3. Each $T(e_n)$ is a unit vector and the supports of $T(e_n)$ and $T(e_m)$ are disjoint whenever $m \ne n$.

In his seminal text on linear operators, S. Banach stated Theorem 3 for the case of $\ell ^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 results 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 $\sigma$-finite measure spaces [7]. Theorem 3 follows from J. Lamperti’s work as it appears in Theorem 3.2.5 of [4]. Note that Theorem 3 fails when $p = 2$. For, $\ell ^2$ is a Hilbert space. So, if $\{f_0, f_1, \ldots \}$ is any orthonormal basis for $\ell ^2$, then there is a unique surjective linear isometry of $\ell ^2$, $T$, so that $T(e_n) = f_n$ for all $n$.

2.2 Background from Computable Analysis

We assume the reader is familiar with the fundamental notions of computability theory as covered in [3].

Suppose $z_0 \in \mathbb {C}$. We say that $z_0$ is computable if there is an algorithm that given any $k \in \mathbb {N}$ as input computes a rational point $q$ so that $|q - z_0| < 2^{-k}$. This is equivalent to saying that the real and imaginary parts of $z_0$ have computable decimal expansions.

Our approach to computability on $\ell ^p$ is equivalent to the format in [10] wherein a more expansive treatment may be found.

Fix a computable real $p$ so that $1 \le p < \infty$. Let $F = \{f_0, f_1, \ldots \}$ be a generating set for $\ell ^p$. We say that $F$ is an effective generating set if there is an algorithm that given any rational points $\alpha _0, \ldots , \alpha _M$ and a nonnegative integer $k$ as input computes a rational number $q$ so that

$$ q - 2^{-k} < \left\| \sum _{j = 0}^M \alpha _j f_j \right\| < q + 2^{-k}. $$

That is, the map

$$ \alpha _0, \ldots , \alpha _M \mapsto \left\| \sum _{j = 0}^M \alpha _j f_j \right\| $$

is computable. Clearly the standard generating set is an effective generating set.

Suppose $F = \{f_0, f_1, \ldots \}$ is an effective generating set for $\ell ^p$. We say that a vector $g \in \ell ^p$ is computable with respect to $F$ if there is an algorithm that given any nonnegative integer $k$ as input computes rational points $\alpha _0, \ldots , \alpha _M$ so that

$$ \left\| g - \sum _{j = 0}^M \alpha _j f_j \right\| < 2^{-k}. $$

Suppose $g_n \in \ell ^p$ for all $n$. We say that $\{g_n\}_n$, is computable with respect to $F$ if there is an algorithm that given any $k,n \in \mathbb {N}$ as input computes rational points $\alpha _0, \ldots , \alpha _M$ so that

$$ \left\| g_n - \sum _{j = 0}^M \alpha _j f_j \right\| < 2^{-k}. $$

When $f \in \ell ^p$ and $r > 0$, let $B(f ; r)$ denote the open ball with center $f$ and radius $r$. When $\alpha _0, \ldots , \alpha _M$ are rational points and $r$ is a positive rational number, we call $B\left( \sum _{j = 0}^M \alpha _j f_j; r \right)$ a rational ball.

Suppose $F = \{f_0, f_1, \ldots \}$ and $G = \{g_0, g_1, \ldots \}$ are effective generating sets for $\ell ^p$. We say that a map $T: \ell ^p \rightarrow \ell ^p$ is computable with respect to $(F,G)$ if there is an algorithm $P$ that meets the following three criteria.

• Approximation: Given a rational ball $B(\sum _{j = 0}^M \alpha _j f_j ; r)$ as input, $P$ either does not halt or produces a rational ball $B(\sum _{j = 0}^N \beta _j g_j; r')$.

• Correctness: If $B(\sum _{j = 0}^N \beta _j g_j ; r')$ is the output of $P$ on input $B(\sum _{j = 0}^M \alpha _j f_j; r)$, then $T(f) \in B(\sum _{j = 0}^N \beta _j g_j; r')$ whenever $f \in B(\sum _{j = 0}^M \alpha _j f_j; r)$.

• Convergence: If $U$ is a neighborhood of $T(f)$, then $f$ belongs to a rational ball $B_1 = B(\sum _{j = 0}^M \alpha _j f_j; r)$ so 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 \alpha _j f_j; r)$ as input, we of course mean that it accepts some representation of the ball such as a code of the sequence $(r, M, \alpha _0, \ldots , \alpha _M)$.

All of these definitions have natural relativizations. For example, if $F = \{f_0, f_1, \ldots \}$ is an effective generating set, then we say that $X$ computes a vector $g \in \ell ^p$ with respect to $F$ if there is a Turing reduction that given the oracle $X$ and an input $k$ computes rational points $\alpha _0, \ldots , \alpha _M$ so that $\left\| g - \sum _{j = 0}^M \alpha _j f_j \right\| < 2^{-k}$.

2.3 Background from Computable Categoricity

For the sake of motivation, we begin by considering the following simple example. Let $\zeta$ be an incomputable unimodular point in the plane. For each $n$, let $f_n = \zeta e_n$. Let $F = \{f_0, f_1, \ldots \}$. Thus, $F$ is an effective generating set. However, the vector $\zeta e_0$ is computable with respect to $F$ even though it is not computable with respect to the standard generating set $E$. In fact, the only vector that is computable with respect to $E$ and $F$ is the zero vector. The moral of the story is that different effective generating sets may yield very different classes of computable vectors and sequences. However, there is a surjective linear isometry of $\ell ^p$ that is computable with respect to $(E,F)$; namely multiplication by $\zeta$. Thus, $E$ and $F$ give the same computability theory on $\ell ^p$ even though they yield very different classes of computable vectors. This leads to the following definition.

Definition 4

Suppose $p$ is a computable real so that $p \ge 1$. We say that $\ell ^p$ is computably categorical if for every effective generating set $F$ there is a surjective linear isometry of $\ell ^p$ that is computable with respect to $(E,F)$.

The definitions just given for $\ell ^p$ can easily be adapted to any separable Banach space. Suppose $G = \{g_0, g_1\ldots , \}$ is an effective generating set for a Banach space $\mathcal {B}$. The pair $(\mathcal {B}, G)$ is called a computable Banach space. Suppose that $\mathcal {B}$ is linearly isometric to $\ell ^p$, and let $T$ denote a linear isometric mapping of $\mathcal {B}$ onto $\ell ^p$. Let $f_n = T(g_n)$, and let $F = \{f_0, f_1, \ldots \}$. Then, $F$ is an effective generating set for $\ell ^p$, and $T$ is computable with respect to $(G, F)$. Thus, Theorem 2 can be rephrased as follows.

Theorem 5

Suppose $p$ is a computable real so that $p \ge 1$ and $p \ne 2$. Suppose $C$ is a c.e. set. Then, there is an effective generating set for $\ell ^p$, $F$, so that with respect to $(E,F)$, $C$ computes a surjective linear isometry of $\ell ^p$. Furthermore, any oracle that computes a surjective linear isometry of $\ell ^p$ with respect to $(E,F)$ must also compute $C$.

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 [8, 9]. The study of computable categoricity for countable structures goes back at least as far as the work of Goncharov [5]. The text of Ash and Knight has a thorough discussion of the main results of this line of inquiry [1]. The survey by Harizanov covers other directions in the countable computable structures program [6].

3 Proof of Theorems 1 and 2

We begin by noting the following easy consequence of the definitions and Theorem 3.

Proposition 6

Suppose $p$ is a computable real so that $p \ge 1$ and so that $p \ne 2$. Let $F$ be an effective generating set for $\ell ^p$. Then, the following are equivalent.

• 1. There is a surjective linear isometry of $\ell ^p$ that is computable with respect to $(E,F)$.

• 2. There is a permutation of $\mathbb {N}$, $\phi$, and a sequence of unimodular points $\{\lambda _n\}_n$, so that $\{\lambda _n e_{\phi (n)}\}_n$ is computable with respect to $F$.

• 3. There is a sequence of unit vectors $\{g_n\}_n$ so that $\{g_n\}_n$ is computable with respect to $F$, $G = \{g_0, g_1, \ldots \}$ is a generating set for $\ell ^p$, and so that the supports of $g_n$ and $g_m$ are disjoint whenever $n \ne m$.

Proof

Parts (2) and (3) just restate each other. It follows from Theorem 3 that (1) implies (2).

Suppose (3) holds. Let $T$ be the unique linear map of the span of $E$ onto the span of $G$ so that $T(e_n) = g_n$ for all $n$. Since the supports of $g_0, g_1, \ldots$ are pairwise disjoint, and since each $g_n$ is a unit vector, $T$ is isometric. It follows that there is a unique extension of $T$ to a unique linear isometry of $\ell ^p$; denote this extension by $T$ as well. We claim that $T$ is computable with respect to $(E,F)$. For, suppose a rational ball $B(\sum _{j=0}^M \alpha _j e_j; r)$ is given as input. Since $\{g_n\}_n$ is computable with respect to $F$, it follows that we can compute a non-negative integer $N$ and rational points $\beta _0, \ldots , \beta _N$ so that $\left\| \sum _{j = 0}^M \alpha _j g_j - \sum _{j = 0}^N \beta _j f_j \right\| < r$. We then output $B(\sum _{j = 0}^N \beta _j g_j; 2r)$. It follows that the Approximation, Correctness, and Convergence criteria are satisfied and so $T$ is computable with respect to $(E, F)$.   $\square$

We now turn to the proof of Theorem 5 which, as we have noted, implies Theorem 2. Our construction of $F$ is a modification of the construction used by Pour-El and Richards to show that $\ell ^1$ is not computably categorical [10]. Let $C$ be an incomputable c.e. set. Without loss of generality, we assume $0 \not \in C$. Let $\{c_n\}_{n \in \mathbb {N}}$ be an effective one-to-one enumeration of $C$. Set

$$ \gamma = \sum _{k \in C} 2^{-k}. $$

Thus, $0 < \gamma < 1$, and $\gamma$ is an incomputable real. Set:

$$\begin{aligned} f_0= & {} (1 - \gamma )^{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, \ldots \} \end{aligned}$$

Since $1 - \gamma > 0$, we can use the standard branch of $\root p \of {\ }$.

We divide the rest of the proof into the following lemmas.

Lemma 7

$F$ is an effective generating set.

Proof

Since

$$ (1 - \gamma )^{1/p} e_0 = f_0 - \sum _{n =1}^\infty 2^{-c_{n-1} / p} f_n $$

the closed linear span of $F$ includes $E$. Thus, $F$ is a generating set for $\ell ^p$. Note that $\left\| f_0 \right\| = 1$.

Suppose $\alpha _0, \ldots , \alpha _M$ are rational points. When $1 \le j \le M$, set

$$ \mathcal {E}_j = |\alpha _0 2^{-c_{j-1} / p} + \alpha _j |^p - |\alpha _0|^p 2^{-c_{j-1}}. $$

It follows that

$$\begin{aligned} \left\| \alpha _0 f_0 + \ldots +\alpha _M f_M \right\| ^p= & {} |\alpha _0|^p \left\| f_0 \right\| ^p + \mathcal {E}_1 + \ldots + \mathcal {E}_M\\= & {} |\alpha _0|^p + \mathcal {E}_1 + \ldots + \mathcal {E}_M. \end{aligned}$$

Since $\mathcal {E}_1$, $\ldots$, $\mathcal {E}_M$ can be computed from $\alpha _0, \ldots , \alpha _M$, $\left\| \alpha _0 f_0 + \ldots + \alpha _M f_M \right\|$ can be computed from $\alpha _0, \ldots , \alpha _M$. Thus, $F$ is an effective generating set.   $\square$

Lemma 8

Every oracle that with respect to $F$ computes a scalar multiple of $e_0$ whose norm is $1$ must also compute $C$.

Proof

Suppose that with respect to $F$, $X$ computes a vector of the form $\lambda e_0$ where $|\lambda | = 1$. It suffices to show that $X$ computes $(1 - \gamma )^{-1/p}$.

Fix a rational number $q_0$ so that $(1 - \gamma )^{-1/p} \le q_0$. Let $k \in \mathbb {N}$ be given as input. Compute $k'$ so that $2^{-k'} \le q_0 2^{-k}$. Since $X$ computes $\lambda e_0$ with respect to $F$, we can use oracle $X$ to compute rational points $\alpha _0, \ldots , \alpha _M$ so that

$$\begin{aligned} \left\| \lambda e_0 - \sum _{j = 0}^M \alpha _j f_j \right\| < 2^{-k'}. \end{aligned}$$

(1)

We claim that $|(1 - \gamma )^{-1/p} - |\alpha _0| | < 2^{-k}$. For, it follows from (1) that $|\lambda - \alpha _0 (1 - \gamma )^{1/p}| < 2^{-k'}$. Thus, $|1 - |\alpha _0| (1 - \gamma )^{1/p}| < 2^{-k'}$. Hence,

$$ |(1 - \gamma )^{-1/p} - |\alpha _0|| < 2^{-k'}(1 - \gamma )^{-1/p} \le 2^{-k'}q_0 \le 2^{-k}. $$

Since $X$ computes $\alpha _0$ from $k$, $X$ computes $(1 - \gamma )^{-1/p}$.   $\square$

Lemma 9

If $X$ computes a surjective linear isometry of $\ell ^p$ with respect to $(E,F)$, then $X$ must also compute $C$.

Proof

By Lemma 8 and the relativization of Proposition 6.   $\square$

Lemma 10

With respect to $F$, $C$ computes $e_0$.

Proof

Fix an integer $M$ so that $(1 - \gamma )^{-1/p} < M$.

Let $k \in \mathbb {N}$. Using oracle $C$, we can compute an integer $N_1$ so that $N_1 \ge 3$ and

$$ \left\| \sum _{n = N_1}^\infty 2^{-c_{n - 1}/p} e_n \right\| \le \frac{2^{-(kp + 1)/p}}{2^{-(kp + 1)/p} + M}. $$

We can use oracle $C$ to compute a rational number $q_1$ so that $|q_1 - (1 - \gamma )^{-1/p}| \le 2^{-(kp + 1)/p}$. Set

$$ g = q_1 \left[ f_0 - \sum _{n = 1}^{N_1 - 1} 2^{-c_{n-1}/p} f_n \right] \!\!. $$

It suffices to show that $\left\| e_0 - g \right\| < 2^{-k}$. Note that since $1 - \gamma < 1$, $|q_1(1 - \gamma )^{1/p} - 1| \le 2^{-(kp + 1)/p}$. Note also that $|q_1| < M + 2^{-(kp +1)/p}$. Thus,

$$\begin{aligned} \left\| e_0 - g \right\| ^p= & {} \left\| e_0 - q_1(1 - \gamma )^{1/p} e_0 - q_1 \sum _{n = N_1}^\infty 2^{-c_{n - 1/p}}e_n \right\| ^p\\\le & {} |q_1 (1 - \gamma )^{1/p} - 1|^p + |q_1|^p \left\| \sum _{n = N_1}^\infty 2^{-c_{n-1}/p} e_n \right\| ^p\\< & {} 2^{-(kp + 1)} + 2^{-(kp + 1)} = 2^{-kp} \end{aligned}$$

Thus, $\left\| e_0 - g \right\| < 2^{-k}$. This completes the proof of the lemma.   $\square$

Lemma 11

With respect to $(E,F)$, $C$ computes a surjective linear isometry of $\ell ^p$.

Proof

By Lemma 10 and the relativization of Proposition 6.   $\square$

4 Concluding Remarks

We note that all of the steps in the above proofs work just as well over the real field.

Lamperti’s result on the isometries of $L^p$ spaces hold when $0 < p < 1$. For these values of $p$, $\ell ^p$ is a metric space under the metric

$$ d(\{a_n\}_n, \{b_n\}_n) = \sum _{n = 0}^\infty |a_n - b_n|^p. $$

The steps in the above proofs can be adapted to these values of $p$ as well.

In a forthcoming paper it will be shown that $\ell ^p$ is $\varDelta _2^0$-categorical.