betaFeedback

WorksMathematics

Computable presentations of separable Lebesgue spaces

Abstract

For every right-c.e.\ real p∈(1,2)p\in(1,2), Lp[0,1]L^p[0,1] has a computable presentation. The proof combines an effective stability modulus for almost isometric embeddings with a Fra"ıssé-style construction in which the exponent varies. In the same range, if ℓp\ell^p has a computable presentation, then pp is computable. Combining these with the known results gives the computable presentability classification for all separable Lebesgue spaces. We also formulate an effective Fra"ıssé theorem for Banach spaces and apply it to obtain a computable presentation of the Gurarij Banach space.

Introduction

The effective study of continuous mathematics begins with a deceptively simple question: what should it mean to compute a real number? In his landmark paper [29], Turing gave this question a precise answer by replacing a completed infinite expansion with a finite mechanical procedure that produces its digits one by one. Although he used this definition to address the Entscheidungsproblem, the conceptual move reached far beyond its original application. It supplied a lasting paradigm for computable analysis: an infinite object becomes accessible through a uniform process that generates finite approximations. The same shift of viewpoint—from an object in the abstract to the information by which it is presented—also lies at the heart of computable structure theory. The present paper follows this line of thought for LpL^p-spaces.

The distinction between an abstract mathematical object and a particular presentation of it is largely suppressed in classical mathematics. Isomorphic groups, isometric metric spaces, and linearly isometric Banach spaces are regarded as the same object, and a theorem is normally stated about the abstract object rather than about a particular choice of coordinates. Computation cannot ignore this distinction. An algorithm never receives an abstract isomorphism type, and an infinite object cannot be handed to it all at once. What the algorithm receives is a concrete presentation: a system of names together with procedures for evaluating the relevant operations, relations, or distances. Computable structure theory studies mathematics through such presentations. It asks for the effective content of classical results: which infinite structures admit algorithmic descriptions, which invariants and constructions can be recovered from those descriptions, whether classically equivalent descriptions can be translated into one another effectively, and how much additional computational information is required when they cannot. In this way the

2020 Mathematics Subject Classification. Primary 03D78; Secondary 03D45, 46B04, 46E30. Key words and phrases. Computable presentations, Lebesgue spaces, approximate ultrahomogeneity. subject connects the computability theory of countable algebraic structures with computable analysis and the study of separable uncountable structures, see [13] and [15].

For a countable structure, a computable presentation gives an isomorphic copy on a computable subset of N\mathbb{N} with computable basic operations and relations. The passage to analysis creates an immediate obstacle. A separable Banach space is normally uncountable, so its vectors cannot be listed by natural numbers. Separability nevertheless supplies a countable interface: if (vn)n∈N(v_n)_{n\in\mathbb{N}} has dense linear span, then its rational linear combinations form a countable skeleton whose completion is the whole space. Computability requires effective access to the norm on this skeleton; arbitrary vectors and operators are then handled by Cauchy names.

This framework gives rise to three closely related problems. The presentability problem asks which classical structures admit at least one computable presentation. The effective uniqueness problem asks whether all computable presentations of a fixed isomorphism or isometry type are computably equivalent. The recognition problem ranges over presentations and asks how difficult it is to determine whether the presented object belongs to a specified class or has a specified type. Separable Lebesgue spaces provide a particularly revealing test case. Their classical linear-isometric structure is governed by the exponent and the underlying measure algebra, but an arbitrary computable Banach presentation need not display either of these objects. It presents only a dense sequence and the norm geometry generated by that sequence. The exponent must therefore be detected indirectly, if it can be detected at all, through geometric identities, embeddings, and finite-dimensional configurations. Conversely, to build a computable presentation one must make all norm computations effective even when the exponent itself is not computable.

The history leading to our work passes naturally through the three problems above. We begin with effective uniqueness. A computably (presentable) Banach space is computably categorical if any two computable Banach presentations of spaces linearly isometric to it are connected by a surjective linear isometry that is computable with respect to their induced Cauchy representations. Pour-El and Richards [25] proved that every separable Hilbert space is computably categorical. The first examples beyond Hilbert spaces arose in finite dimensions. Let (Ω,Σ,μ)(\Omega,\Sigma,\mu) be a measure space and 1≤r<∞1 \le r < \infty. The Lebesgue space Lr(Ω,Σ,μ;F)L^r(\Omega,\Sigma,\mu;\mathbb{F}) consists of equivalence classes modulo almost-everywhere equality of measurable f:Ω→Ff:\Omega\to\mathbb{F} for which ∥f∥r=(∫Ω∣f∣r dμ)1/r<∞\|f\|_r = \left(\int_{\Omega} |f|^r\,d\mu\right)^{1/r} < \infty. We abbreviate Lr([0,1],λ;F)L^r([0,1],\lambda;\mathbb{F}) to Lr[0,1]L^r[0,1]. Also,

ℓrN=(FN,∥(aj)j<N∥r=(∑j<N∣aj∣r)1/r).\ell_r^N = \left(\mathbb{F}^N,\|(a_j)_{j<N}\|_r = \left(\sum_{j<N}|a_j|^r\right)^{1/r}\right).

Informally, a real number is computable if a single algorithm can approximate it to any prescribed accuracy. Thus, when pp is computable, the exponent can be used effectively in norm calculations. McNicholl [23] established computable categoricity for ℓpN\ell_p^N where p≥1p \ge1 is computable.

Clanin, McNicholl, and Stull subsequently obtained an infinite-dimensional counterpart. For computable pp, the space Lp[0,1]L^p[0,1] has a standard computable presentation given by the step functions with coefficients in Q\mathbb{Q} in the real case and in Q+iQ\mathbb{Q}+i\mathbb{Q} in the complex case, and with rational interval endpoints.

Theorem 1.1 (Clanin–McNicholl–Stull [9]). Let FF be either R\mathbb{R} or C\mathbb{C}, and let p≥1p \ge1 be a computable real. If Ω\Omega is an atomless, separable measure space such that Lp(Ω;F)≠{0}L^{p}(\Omega; F) \ne\{0\}, then every computable presentation of Lp(Ω;F)L^{p}(\Omega; F) is computably linearly isometric to the standard computable presentation of Lp([0,1];F)L^{p}([0,1]; F). Consequently, Lp([0,1];F)L^{p}([0,1]; F) is computably categorical for every computable real p≥1p \ge1.

We next turn to the recognition problem: how difficult is it to recognize a Lebesgue space from an index? Here a Lebesgue space is a separable Banach space linearly isometric to Lp(Ω)L^{p}(\Omega) for some measure space Ω\Omega and some exponent pp. A computable Banach-space presentation may be viewed as a program that, given a rational linear combination of its distinguished dense sequence and a requested precision, computes the norm of that combination. An index is simply a natural-number code for such a program. Neither the presentation nor its index is unique. Given a class of Banach spaces, its index set is the collection of all codes whose programs present members of that class. The position of this set in the arithmetical or analytical hierarchy measures how difficult it is to recognize the class from an effective description. Naively, deciding whether an indexed Banach space is a Lebesgue space appears to require a search through the uncountably many possible surjective linear isometries and hence to have the crude analytic upper bound Σ11\boldsymbol{\Sigma}^{1}_{1}.

Theorem 1.2 (Brown–McNicholl–Melnikov [7]). The following statements hold.

(i) The set of all indices of Lebesgue-space presentations, with the exponent allowed to vary, belongs to Π30\Pi^{0}_{3}.

(ii) For every fixed computable real p≥1p \ge1, the set of all indices of LpL^{p}-space presentations is Π20\Pi^{0}_{2}-complete.

(iii) For every fixed computable real p≥1p \ge1, the set of all indices of presentations linearly isometric to Lp[0,1]L^{p}[0,1] is Π20\Pi^{0}_{2}-complete.

A one-sided recovery theorem for the uncomputable exponents is also the starting point for our work.

Theorem 1.3 ([7]). Let BB be a LpL^{p}-space (1≤p≤21 \le p \le2) of dimension at least two as a linear space. Uniformly from a presentation of BB, one can computably enumerate {r∈Q:p<r}\{r \in\mathbb{Q}: p < r\}.

A real number xx is right-c.e. if {r∈Q:x<r}\{r \in\mathbb{Q}: x < r\} is c.e., and it is left-c.e. if {r∈Q:r<x}\{r \in\mathbb{Q}: r < x\} is c.e. It is computable if it is both left-c.e. and right-c.e. Consequently, if 1<p<21 < p < 2 and an LpL^{p}-space of dimension at least two is computably presentable, then pp must be right-c.e. The restriction on the dimension is necessary, since every one-dimensional LpL^{p}-space is linearly isometric to the scalar field and therefore carries no information about pp.

Theorem 1.4 (McNicholl [24]). The following statements hold.

(i) If 2≤p<∞2 \le p < \infty and a computably presentable LpL^{p}-space has dimension at least two, then pp is computable.

(ii) If n≥2n \ge2, 1≤p<∞1 \le p < \infty, and ℓnp\ell^{p}_{n} is computably presentable, then pp is computable.

McNicholl also proved that exponent recovery is at least nonuniform.

Theorem 1.5 ([24]). For every nondegenerate open interval I⊆(1,2)I \subseteq(1,2), there is no partial computable function FF such that, whenever it indexes a computable presentation of an LpL^{p}-space of dimension at least two with p∈Ip \in I, F(e)F(e) is defined and indexes a computable Cauchy name for pp.

The remaining case is that of infinite-dimensional separable LpL^p-spaces with 1<p<21 < p < 2. The one-sided recovery theorem makes right-c.e.-ness of pp necessary, while the nonuniformity theorem suggests that computability may not be necessary.

Conjecture (McNicholl [24], 2020). If 1<p<21 < p < 2 is right-c.e., then Lp[0,1]L^p[0,1] is computably presentable.

This conjecture was later recorded as Conjecture 6.33 in the textbook by Franklin, Goldbring, and McNicholl [15]. It is also connected with the following question in effective duality, posed by Downey and Melnikov in their textbook [13 Question 4.2.116]; a broader version was also posed by Downey, Greenberg, and Qian [12 Question 1].

Question 1.6 (Downey–Melnikov). Suppose BB is a computable Banach space and its dual B∗B^* is separable. Must B∗B^* have a computable presentation?

Downey and Melnikov observed that a positive solution of McNicholl’s conjecture would give a negative answer to Question 1.6: for a noncomputable right-c.e. p∈(1,2)p \in(1,2), take a computable copy BB of Lp([0,1];R)L^p([0,1];\mathbb{R}). Then BB is reflexive and, by classical duality, B∗≅Lq([0,1];R)B^* \cong L^q([0,1];\mathbb{R}), where q=p/(p−1)>2q = p/(p-1) > 2, so B∗B^* is separable. If B∗B^* had a computable presentation, Theorem 1.4(i) would make qq, and hence p=q/(q−1)p = q/(q - 1), computable, a contradiction. Our main theorem supplies such a counterexample.

Theorem 1.7. Let F\mathbb{F} be either R\mathbb{R} or C\mathbb{C}. If 1<p<21 < p < 2 is right-c.e., then Lp([0,1];F)L^p([0,1];\mathbb{F}) has a computable presentation.

The proof combines a locally uniform effective stability theorem with a varying-exponent Fraïssé-style construction. The purely atomic analogue behaves differently. We prove the following complementary result.

Theorem 1.8. Let F\mathbb{F} be either R\mathbb{R} or C\mathbb{C}, and let 1<p<21 < p < 2. If ℓp(F)\ell^p(\mathbb{F}) has a computable presentation, then pp is a computable real.

The proof follows by recovering pp from the decay of symmetric second differences of the norm. For 1<p<21 < p < 2, the argument requires only a single atomic coordinate and therefore extends to every separable LpL^p-space of dimension at least two with a nonzero atomic part. Together with the known cases, this shows that ℓp\ell^p is computably presentable exactly when pp is computable, for every 1≤p<∞1 \leq p < \infty. Combining these results with Theorem 1.7 and the classical classification yields a complete classification of computable presentability for separable LpL^p-spaces with 1≤p<∞1 \leq p < \infty.

As a complementary application of the Fraïssé-style finite-dimensional construction method, we formulate an effective Fraïssé theorem for fixed families of finite-dimensional Banach spaces with effectively enumerable dense families of linear isometric embeddings. Applying it to finite-dimensional ℓ∞\ell_\infty-spaces gives a computable presentation of the Gurariĭ Banach space.

The paper is organized as follows. Section 2 collects the required background on computable analysis, measure theory and the geometry of Banach spaces. Section 3 establishes the locally uniform effective stability theorem, and Section 4 uses it to prove Theorem 1.7. Section 5 proves exponent recovery for ℓp\ell^p, extends the argument to spaces with a nonzero atomic part, and completes the classification of computably presentable separable LpL^p-spaces. Finally, Section 6 proves the effective Fraïssé theorem for Banach spaces and applies it to the Gurariĭ space.

Preliminaries

A computable Polish presentation is a triple (X,d,(ai)i∈N)(X,d,(a_i)_{i\in\mathbb{N}}), where (X,d)(X,d) is complete, (ai)(a_i) is dense, and d(ai,aj)d(a_i,a_j) is a computable real uniformly in i,ji,j. The points aia_i are called special points. A fast Cauchy name for x∈Xx\in X is a sequence (in)(i_n) such that d(ain,ain+1)<2−n−1d(a_{i_n},a_{i_{n+1}})<2^{-n-1} and x=lim⁡nainx=\lim_{n}a_{i_n}. A map between computable Polish spaces is computable if a single Turing functional transforms every fast Cauchy name of an input into a fast Cauchy name of its image. For i∈Ni\in\mathbb{N} and r∈Q>0r\in\mathbb{Q}_{>0}, let B(i,r)={x∈X:d(x,ai)<r}B(i,r)=\{x\in X:d(x,a_i)<r\} be a basic open ball. An open set is c.e. open if it is the union of a c.e. family of basic open balls. The effective compactness principle used throughout the proof is as follows.

Lemma 2.1 (Downey and Melnikov [14]). Let X=(X,d,(ai)i∈N)X=(X,d,(a_i)_{i\in\mathbb{N}}) be a nonempty computable Polish space. The following are equivalent.

(i) Given nn, one can compute a finite tuple (ij,rj)j<m(i_j,r_j)_{j<m}, where rj∈Q>0r_j\in\mathbb{Q}_{>0} and rj<2−nr_j<2^{-n}, such that X=⋃j<mB(ij,rj)X=\bigcup_{j<m}B(i_j,r_j).

(ii) There is a partial computable functional Γ\Gamma such that, for every index ee enumerating a c.e. family UeU_e of basic open balls, Γ(e)\Gamma(e) is defined if and only if UeU_e covers XX, and in that case Γ(e)\Gamma(e) returns a finite subfamily that still covers XX.

The conversions between witnesses to these conditions are uniform. Any space satisfying these conditions is compact and is called computably compact.

Fact 2.2 ([14]). The following operations are uniform.

(i) Finite products of computably compact spaces are computably compact.

(ii) If XX is nonempty and computably compact and f:X→Rf:X\to\mathbb{R} is computable, then the values max⁡Xf\max_X f and min⁡Xf\min_X f are computable.

We now specialize the preceding framework to Banach spaces. Throughout the paper, fix a scalar field F∈{R,C}\mathbb{F}\in\{\mathbb{R},\mathbb{C}\}. Put QR=Q\mathbb{Q}_{\mathbb{R}}=\mathbb{Q} and QC=Q+iQ\mathbb{Q}_{\mathbb{C}}=\mathbb{Q}+i\mathbb{Q}.

Definition 2.3 (Pour-El and Richards [25]). A computable presentation of a separable F\mathbb{F}-Banach space $ BB is a sequence (bn)n∈N(b_n)_{n\in\mathbb{N}} with dense linear span such that ∥∑j<mqjbij∥\left\lVert\sum_{j<m}q_jb_{i_j}\right\rVert is a computable real, uniformly in mm, the indices iji_j, and the coefficients qj∈QFq_j\in\mathbb{Q}_{\mathbb{F}}.

References

  1. [1]F. Albiac and N. J. Kalton, Topics in Banach Space Theory, second edition, Graduate Texts in Mathematics, vol. 233, Springer, Cham, 2016. https://doi.org/10.1007/978-3-319-31557-7.
  2. [2]S. Banach, Théorie des opérations linéaires, Monografie Matematyczne, vol. 1, Subwencji Funduszu Kultury Narodowej, Warsaw, 1932.
  3. [3]S. Banach and S. Mazur, Zur Theorie der linearen Dimension, Studia Math. 4 (1933), 100–112. https://doi.org/10.4064/sm-4-1-100-112.
  4. [4]I. Ben Yaacov and C. W. Henson, Generic orbits and type isolation in the Gurarij space, Fund. Math. 237 (2017), no. 1, 47–82. https://doi.org/10.4064/fm193-3-2016.
  5. [5]V. Brattka, Computable versions of the uniform boundedness theorem, in Logic Colloquium ’02 (Z. Chatzidakis, P. Koepke, and W. Pohlers, eds.), Lecture Notes in Logic, vol. 27, 2006, pp. 130–151. https://doi.org/10.1017/9781316755723.007.
  6. [6]J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine, Lois stables et espaces Lp, Ann. Inst. H. Poincaré Sect. B (N.S.) 2 (1965/1966), 231–259.
  7. [7]T. A. Brown, T. H. McNicholl, and A. G. Melnikov, On the complexity of classifying Lebesgue spaces, J. Symbolic Logic 85 (2020), no. 3, 1254–1288. https://doi.org/10.1017/jsl.2020.63.
  8. [8]J. A. Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936), no. 3, 396–414. https://doi.org/10.1090/S0002-9904-1936-1501880-4.
  9. [9]J. Clanin, T. H. McNicholl, and D. M. Stull, Analytic computable structure theory and Lp spaces, Fund. Math. 244 (2019), 255–285. https://doi.org/10.4064/fm448-5-2018.
  10. [10]B. F. Csima, V. S. Harizanov, R. G. Miller, and A. Montálban, Computability of Fraïssé limits, J. Symbolic Logic 76 (2011), no. 1, 66–93. https://doi.org/10.2178/jsl/1294170990.
  11. [11]P. Cembranos and J. Mendoza, Banach Spaces of Vector-Valued Functions, Lecture Notes in Mathematics, vol. 1676, Springer-Verlag, Berlin, 1997. https://doi.org/10.1007/BFb0096765.
  12. [12]R. G. Downey, N. Greenberg, and L. Qian, Some open questions and recent results on computable Banach spaces, in Twenty Years of Theoretical and Practical Synergies (CiE 2024), Lecture Notes in Computer Science, vol. 14773, Springer, Cham, 2024, pp. 10–26. https://doi.org/10.1007/978-3-031-64309-5_2.
  13. [13]R. G. Downey and A. Melnikov, Computable Structure Theory: A Unified Approach, Theory and Applications of Computability, Springer, Cham, 2026. https://doi.org/10.1007/978-3-031-92433-0.
  14. [14]R. G. Downey and A. G. Melnikov, Computably compact metric spaces, Bull. Symbolic Logic 29 (2023), no. 2, 170–263. https://doi.org/10.1017/bsl.2023.16.
  15. [15]J. N. Y. Franklin, I. Goldbring, and T. H. McNicholl, Effective Metric Structure Theory, Springer Monographs in Mathematics, Springer, Cham, 2026. https://doi.org/10.1007/978-3-032-13322-9.
  16. [16]V. Ferenczi, J. López-Abad, B. Mbombo, and S. Todorčević, Amalgamation and Ramsey properties of Lp spaces, Adv. Math. 369 (2020), Article 107190. https://doi.org/10.1016/j.aim.2020.107190.
  17. [17]C. Herz, The theory of p-spaces with an application to convolution operators, Trans. Amer. Math. Soc. 154 (1971), 69–82. https://doi.org/10.1090/S0002-9947-1971-0272952-0.
  18. [18]A. S. Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. https://doi.org/10.1007/978-1-4612-4190-4.
  19. [19]M. Lupini, Fraïssé limits in functional analysis, Adv. Math. 338 (2018), 93–174. https://doi.org/10.1016/j.aim.2018.08.012.
  20. [20]W. Lusky, The Gurarij spaces are unique, Arch. Math. (Basel) 27 (1976), 627–635. https://doi.org/10.1007/BF01224730.
  21. [21]W. Lusky, Some consequences of Rudin’s paper “L^p-isometries and equimeasurability”, Indiana Univ. Math. J. 27 (1978), 859–866. https://doi.org/10.1512/iumj.1978.27.27057.
  22. [22]A. Marcone and M. Valenti, Effective aspects of Hausdorff and Fourier dimension, Computability 11 (2022), nos. 3–4, 299–333. https://doi.org/10.3233/COM-210372.
  23. [23]T. H. McNicholl, Computable copies of L^p, Computability 6 (2017), no. 4, 391–408. https://doi.org/10.3233/COM-160065.
  24. [24]T. H. McNicholl, Computing the exponent of a Lebesgue space, J. Logic Anal. 12 (2020), Paper No. 7, 28 pp. https://doi.org/10.4115/jla.2020.12.7.
  25. [25]M. B. Pour-El and J. I. Richards, Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989.
  26. [26]A. I. Plotkin, An algebra that is generated by translation operators, and L^p-norms, in Functional Analysis, No. 6: Theory of Operators in Linear Spaces, Ul’yanovsk State Pedagogical Institute, Ul’yanovsk, 1976, pp. 112–121 (Russian).
  27. [27]H. P. Rosenthal, On subspaces of L^p, Ann. of Math. (2) 97 (1973), 344–373. https://doi.org/10.2307/1970850.
  28. [28]W. Rudin, L^p-isometries and equimeasurability, Indiana Univ. Math. J. 25 (1976), no. 3, 215–228. https://doi.org/10.1512/iumj.1976.25.25018.
  29. [29]A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1937), 230–265. https://doi.org/10.1112/plms/s2-42.1.230.

Paper details

vlnc:W_pw6zy94s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT 5.6

View statement
Looking for related papers…
Contents