pith. sign in

arxiv: 1906.12209 · v1 · pith:D2RBDMU2new · submitted 2019-06-28 · 🧮 math.LO

On the complexity of classifying Lebesgue spaces

Tyler Brown , Alexander G. Melnikov , Timothy H. McNicholl This is my paper

Pith reviewed 2026-05-25 13:29 UTC · model grok-4.3

classification 🧮 math.LO
keywords Lebesgue spacesisometric isomorphismcomputability theoryclassification complexityeffective descriptive set theoryequivalence relationsBanach spacesfunctional analysis
0
0 comments X

The pith

Computability theory determines the complexity of classifying Lebesgue spaces up to isometric isomorphism.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper applies computability theory to measure how hard it is to decide whether two Lebesgue spaces are isometrically isomorphic. A sympathetic reader cares because Lebesgue spaces are basic objects in analysis and measure theory, so the classification problem directly affects whether effective distinctions are possible. The work treats the isometric isomorphism relation itself as the object of study and places its complexity within known hierarchies from computability. If the evaluation is accurate, certain families of these spaces lack any effective classification procedure.

Core claim

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

What carries the argument

The isometric isomorphism relation on families of Lebesgue spaces, analyzed inside computable structure theory or effective descriptive set theory.

If this is right

  • Isometric isomorphism for some families of Lebesgue spaces is at least as hard as known complete problems in computability.
  • Different kinds of Lebesgue spaces yield equivalence relations of differing computability degrees.
  • No uniform algorithm exists that decides isometric isomorphism across all considered families.
  • Classification reduces to questions about computable presentations of the underlying measure spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same methods could be applied to isometric isomorphism questions for other classes of Banach spaces.
  • Results may limit the feasibility of automated verification tools in functional analysis.
  • Connections to classification problems in ergodic theory or operator algebras become testable once the same formalization is used.

Load-bearing premise

The isometric isomorphism relation on the relevant families of Lebesgue spaces admits a formalization within computable structure theory or effective descriptive set theory that permits complexity analysis.

What would settle it

An explicit effective procedure that classifies the spaces with strictly lower complexity than the bounds obtained, or a reduction showing the relation is simpler than the analysis indicates.

read the original abstract

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that computability theory can be used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

Significance. If substantiated, the work would apply effective descriptive set theory to classification problems for Lebesgue spaces up to isometric isomorphism, contributing to the interface between computability theory and functional analysis by providing precise complexity bounds for these relations.

minor comments (1)
  1. [Abstract] The abstract provides no details on the specific families of Lebesgue spaces considered, the coding of the isometric isomorphism relation, the complexity notions employed (e.g., Borel, computable, etc.), or any theorems or reductions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript. The report provides a summary of the work but lists no specific major comments or points of criticism. The recommendation is listed as uncertain without elaboration. We therefore have no individual comments to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The abstract and context describe an application of computability theory to assess classification complexity for Lebesgue spaces and isometric isomorphism relations, with no equations, reductions, self-definitions, or load-bearing self-citations visible. The approach relies on standard frameworks from effective descriptive set theory and computable structure theory applied to the isomorphism problems, without any step that reduces by construction to its own inputs or prior author results. This constitutes a self-contained analysis using external mathematical tools.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.0 · 5526 in / 939 out tokens · 20215 ms · 2026-05-25T13:29:54.444086+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Ash and J

    C. Ash and J. Knight, Computable structures and the hyperarithmetical hierarch y, Stud- ies in Logic and the Foundations of Mathematics, vol. 144, No rth-Holland Publishing Co., Amsterdam, 2000

    work page 2000

  2. [2]

    Brattka, P

    V. Brattka, P. Hertling, and K. W eihrauch, A tutorial on computable analysis , New compu- tational paradigms, Springer, New York, 2008, pp. 425–491

    work page 2008

  3. [3]

    Brown and T

    T. Brown and T. H. McNicholl, Analytic computable structure theory and lp-spaces part 2 , Submitted. Preprint available at http://arxiv.org/abs/1 801.00355, 2018

    work page 2018

  4. [4]

    Calvert, V

    W. Calvert, V. Harizanov, J. Knight, and S. Miller, Index sets of computable models , Algebra Logika 45 (2006), no. 5, 538–574, 631–632. MR 2307694

    work page 2006

  5. [5]

    Carson, V

    J. Carson, V. Harizanov, J. Knight, K. Lange, C. McCoy, A. Morozov, S. Quinn, C. Safranski, and J. W allbaum, Describing free groups, Trans. Amer. Math. Soc. 364 (2012), no. 11, 5715–

    work page 2012

  6. [6]

    1676, Springer-Verlag, Berlin, 1997

    Pilar Cembranos and Jos´ e Mendoza, Banach spaces of vector-valued functions , Lecture Notes in Mathematics, vol. 1676, Springer-Verlag, Berlin, 1997. MR 1489231

    work page 1997

  7. [7]

    Remmel, Index sets in computable analysis , Theoret

    Douglas Cenzer and Jeffrey B. Remmel, Index sets in computable analysis , Theoret. Comput. Sci. 219 (1999), no. 1-2, 111–150, Computability and complexity in a nalysis (Castle Dagstuhl, 1997)

    work page 1999

  8. [8]

    McNicholl, and Don M

    Joe Clanin, Timothy H. McNicholl, and Don M. Stull, Analytic computable structure theory and Lp spaces, Fund. Math. 244 (2019), no. 3, 255–285

    work page 2019

  9. [9]

    Downey and A

    R. Downey and A. Melnikov, Effectively categorical abelian groups , J. Algebra 373 (2013), 223–248. 30 TYLER A. BROWN, TIMOTHY H. MCNICHOLL, AND ALEXANDER G. MEL NIKOV

    work page 2013

  10. [10]

    Downey and A

    R. Downey and A. Montalb´ an, The isomorphism problem for torsion-free abelian groups is analytic complete , J. Algebra 320 (2008), no. 6, 2291–2300. MR 2437501 (2009e:20122)

    work page 2008

  11. [11]

    Melnikov, Computable completely decomposable groups , Trans

    Rodney Downey and Alexander G. Melnikov, Computable completely decomposable groups , Trans. Amer. Math. Soc. 366 (2014), no. 8, 4243–4266

    work page 2014

  12. [12]

    Downey, Alexander G

    Rodney G. Downey, Alexander G. Melnikov, and Keng Meng N g, A Friedberg enumeration of equivalence structures , J. Math. Log. 17 (2017), no. 2, 1750008, 28

    work page 2017

  13. [13]

    Ershov and S

    Y. Ershov and S. Goncharov, Constructive models , Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000

    work page 2000

  14. [14]

    Fuchs, Infinite abelian groups

    L. Fuchs, Infinite abelian groups. Vol. I , Pure and Applied Mathematics, Vol. 36, Academic Press, New York, 1970

    work page 1970

  15. [15]

    , Infinite abelian groups. Vol. II , Academic Press, New York, 1973, Pure and Applied Mathematics. Vol. 36-II

    work page 1973

  16. [16]

    Goncharov, Countable Boolean algebras and decidability , Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997

    S. Goncharov, Countable Boolean algebras and decidability , Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997

    work page 1997

  17. [17]

    Goncharov and J

    S. Goncharov and J. Knight, Computable structure and antistructure theorems , Algebra Logika 41 (2002), no. 6, 639–681, 757

    work page 2002

  18. [18]

    Noam Greenberg, Dan Turetsky, and Linda Brown W estrick , Finding bases of uncountable free abelian groups is usually difficult , Trans. Amer. Math. Soc. 370 (2018), no. 6, 4483–4508. MR 3811535

    work page 2018

  19. [19]

    Halmos, Measure Theory, D

    Paul R. Halmos, Measure Theory, D. Van Nostrand Company, Inc., New York, N. Y., 1950

    work page 1950

  20. [20]

    Olof Hanner, On the uniform convexity of Lp and lp, Ark. Mat. 3 (1956), 239–244

    work page 1956

  21. [21]

    Shizuo Kakutani, Concrete representation of abstract (L)-spaces and the mean ergodic the- orem, Ann. of Math. (2) 42 (1941), 523–537

    work page 1941

  22. [22]

    Mal ′cev, Constructive algebras

    A. Mal ′cev, Constructive algebras. I , Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60. MR 0151377 (27 #1362)

    work page 1961

  23. [23]

    Charles McCoy and John W allbaum, Describing free groups, Part II: Π0 4 hardness and no Σ0 2 basis, Trans. Amer. Math. Soc. 364 (2012), no. 11, 5729–5734

    work page 2012

  24. [24]

    McNicholl and D

    T.H. McNicholl and D. M. Stull, The isometry degree of a com- putable copy of ℓp, To appear in Computability. Available online at https://content.iospress.com/articles/computability/com180214., 2019

    work page 2019

  25. [25]

    McNicholl, Computable copies of ℓp, Computability 6 (2017), no

    Timothy H. McNicholl, Computable copies of ℓp, Computability 6 (2017), no. 4, 391–408

    work page 2017

  26. [26]

    Alexander Melnikov, Computable topological groups and Pontryagin duality , Trans. Amer. Math. Soc. 370 (2018), no. 12, 8709–8737

    work page 2018

  27. [27]

    Alexander Melnikov and Antonio Montalb´ an, Computable Polish group actions , J. Symb. Log. 83 (2018), no. 2, 443–460

    work page 2018

  28. [28]

    Melnikov, Computably isometric spaces , J

    Alexander G. Melnikov, Computably isometric spaces , J. Symbolic Logic 78 (2013), no. 4, 1055–1085

    work page 2013

  29. [29]

    Melnikov and Keng Meng Ng, Computable structures and operations on the space of continuous functions , Fund

    Alexander G. Melnikov and Keng Meng Ng, Computable structures and operations on the space of continuous functions , Fund. Math. 233 (2016), no. 2, 101–141

    work page 2016

  30. [30]

    Melnikov and Andr´ e Nies, The classification problem for compact computable metric spaces, The nature of computation, Lecture Notes in Comput

    Alexander G. Melnikov and Andr´ e Nies, The classification problem for compact computable metric spaces, The nature of computation, Lecture Notes in Comput. Sci., v ol. 7921, Springer, Heidelberg, 2013, pp. 320–328

    work page 2013

  31. [31]

    Proceeding s, 2015, pp

    Andr´ e Nies and Slawomir Solecki, Local compactness for computable polish metric spaces is Π1 1 -complete, Evolving Computability - 11th Conference on Computabilit y in Europe, CiE 2015, Bucharest, Romania, June 29 - July 3, 2015. Proceeding s, 2015, pp. 286–290

    work page 2015

  32. [32]

    Pour-El and J

    Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989

    work page 1989

  33. [33]

    Rabin, Computable algebra, general theory and theory of computabl e fields

    M. Rabin, Computable algebra, general theory and theory of computabl e fields. , Trans. Amer. Math. Soc. 95 (1960), 341–360

    work page 1960

  34. [34]

    Kyle Riggs, The decomposability problem for torsion-free abelian grou ps is analytic-complete , Proc. Amer. Math. Soc. 143 (2015), no. 8, 3631–3640

    work page 2015

  35. [35]

    Rogers, Theory of recursive functions and effective computability , second ed., MIT Press, Cambridge, MA, 1987

    H. Rogers, Theory of recursive functions and effective computability , second ed., MIT Press, Cambridge, MA, 1987

    work page 1987

  36. [36]

    Rogers, Ulm’s theorem for partially ordered structures related to s imply presented abelian p-groups, Trans

    L. Rogers, Ulm’s theorem for partially ordered structures related to s imply presented abelian p-groups, Trans. Amer. Math. Soc. 227 (1977), 333–343

    work page 1977

  37. [37]

    Soare, Recursively enumerable sets and degrees , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, A study of computable funct ions and computably generated sets

    R. Soare, Recursively enumerable sets and degrees , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, A study of computable funct ions and computably generated sets. ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES 31

    work page 1987

  38. [38]

    Turing, On computable numbers, with an application to the entscheid ungsproblem, Proceedings of the London Mathematical Society 42 (1936), 230–265

    Alan M. Turing, On computable numbers, with an application to the entscheid ungsproblem, Proceedings of the London Mathematical Society 42 (1936), 230–265

    work page 1936

  39. [39]

    A Cor- rection, Proceedings of the London Mathematical Society 43 (1937), 544–546

    , On Computable Numbers, with an Application to the Entscheid ungsproblem. A Cor- rection, Proceedings of the London Mathematical Society 43 (1937), 544–546

    work page 1937

  40. [40]

    An EATCS Series, Springer-Verlag, Berlin, 2000, An introduction

    Klaus W eihrauch, Computable analysis , Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000, An introduction. Department of Mathematics, Iow a State University, Ames, Iow a 50011 USA E-mail address : tab5357@iastate.edu Department of Mathematics, Iow a State University, Ames, Iow a 50011 USA E-mail address : mcnichol@iast...

    work page 2000