Pith. sign in

REVIEW 2 major objections 4 minor 39 references

Second-Order Parameterizations for the Complexity Theory of Integrable Functions

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Three natural ways to parameterize p-integrable functions are linearly equivalent for 1<p<∞.

desk verdict A new and likely correct equivalence theorem for Lp parameterizations; the proof of part (a) and Example 19 need fixes before publication. read the letter →

arxiv 2506.11210 v1 pith:YV3TZM2N submitted 2025-06-12 cs.CC

Aras Bacho , Martin Ziegler This is my paper · ORCID
classification cs.CC MSC 03D7842A2046E3068Q15
keywords second-orderparameterizedcomplexityLpspacesLp-modulusFourierseriesconvergencestep-functionapproximationcomputableanalysiscompactnessinfunctiontheory
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper aims to give the space $L^p$ of $p$-integrable complex functions on the unit circle a second-order parameterized complexity theory: a way of measuring the cost of computing with a function that can depend not only on the desired precision $n$ but also on a structural 'modulus' of the function itself, just as the modulus of continuity does for continuous functions. It proposes three natural structural measurements for $L^p$: an $L^p$-modulus based on how much a function changes under small shifts, a rate of approximation by step functions, and a rate of convergence of Fourier series. The main result, Theorem 16, proves that for every fixed $1

What carries the argument

The central object is the compact cover of $L^p(T)$ built from the quantitative Fréchet–Kolmogorov theorem: the sets $L^p_\mu(T,R)$ of functions with $p$-norm at most $R$ and $L^p$-modulus at most $\mu$ are compact, and every compact subset of $L^p$ is contained in one such set. The four inequalities are proved by moving between a function and its approximations: part (a) uses Fejér means and the uniform boundedness of Fourier partial sums on $L^p$ for $1<p<\infty$ to control the Dirichlet projection; part (b) bounds the $L^p$-modulus of a finite Fourier series directly and then applies the transfer lemma for $L^p$-close functions; parts (c) and (d) compare against averaged step functions, with the extra $pn$ in part (d) coming from the shift sensitivity of a $K$-step function. The transfer lemma, that functions close in $L^p$ have comparable moduli, is what makes all four directions interchangeable.

What would settle it

Take the lacunary function $f(t)=\sum_{k\ge 0} 2^{-k} e^{2\pi i 2^k t}$ in $L^p(T)$, say $p=3$, and compute or bound its $L^p$-modulus $\mu(n)$, step rate $\sigma(n)$, and Fourier rate $\varphi(n)$ for increasing $n$. The theorem predicts $\varphi(n) \le C\mu(n+C)+n+C$ and $\mu(n) \le C\sigma(n+C)+pn+C$ for constants $C$ depending only on $p$; if a computation ever shows one parameter growing more than linearly faster than another, such as $\varphi(n)$ comparable to $2^{\mu(n)}$, the claimed mutual equivalence is false. The paper's own examples assert exponential growth for all three, so the decisive observation is that no doubly exponential separation appears.

Watch

Extended reading notes

Core claim

On the space $L^p(T,1)$ of $p$-integrable complex functions on the unit circle with $\|f\|_p \le 1$ and fixed $1<p<\infty$, let the $L^p$-modulus $\mu(n)$ be the least shift precision needed to keep the $L^p$ distance between $f$ and its $\delta$-shift below $2^{-n}$; let the step rate $\sigma(n)$ be the least $K$ such that a $K$-level step function approximates $f$ to error $2^{-n}$; and let the Fourier rate $\varphi(n)$ be the least order of a Fourier partial sum achieving the same error. Theorem 16 proves the four inequalities $\varphi(n) \le \mu(n+O(1)) + n + O(1)$, $\mu(n) \le 2\varphi(n+O(1)) + n + O(1)$, $\sigma(n) \le \mu(n+O(1))$, and $\mu(n) \le \sigma(n+O(1)) + pn + O(1)$. Corollary 17 then yields $O(\varphi(n+O(1)) + n) = O(\mu(n+O(1)) + n) = O(\sigma(n+O(1)) + n)$, so the three parameters induce the same second-order linear and polynomial time complexity. This extends the continuous-function parameterization and answers the stated question of how to cover $L^p$ by compact sets parameterized by a modulus.

Load-bearing premise

The load-bearing premise is a deep analytic fact the paper cites without proof: for each exponent $p$ strictly between 1 and infinity, taking the $K$-th partial sum of a Fourier series is a bounded operation on $p$-integrable functions, uniformly in $K$; if that uniformity fails, the claimed equivalence of Fourier rate with the other two parameters breaks.

Editorial extensions

If this is right

  • Any second-order runtime bound for an algorithm on $L^p(T)$ stated with one of these parameters translates to the same linear or polynomial bound stated with either of the other two.
  • The compact cover $L^p(T)=\bigcup_{r,\mu} L^p_\mu(T,2^r)$ gives each integrable function a finite structural parameter, opening the way to bit-complexity statements for operators on $L^p$ data, such as solution operators of PDEs.
  • Step-function approximation, which is computationally the simplest of the three encodings, can be used as a canonical parameter without losing information about smoothness measured by the $L^p$-modulus or by Fourier convergence.
  • Because the equivalence is uniform over the unit ball with constants depending only on $p$, complexity classifications based on these parameters do not depend on the particular integrable function being studied.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the equivalence is adopted as a definition, functions with $\mu(n)=O(n)$ form an $L^p$ analogue of Lipschitz functions, and one could compare that class with Sobolev or Besov smoothness; the paper's Sobolev generalization suggests this comparison is within reach.
  • The Fourier leg of the theorem is the only place where the restriction $1<p<\infty$ is truly load-bearing; a natural test is whether the step-rate and $L^p$-modulus equivalence survives at $p=1$, where Fourier partial sums no longer converge.
  • The higher-dimensional extension works only for max-norm partial Fourier sums, since Euclidean-ball sums fail to converge in $L^p$ for $p\neq 2$ in dimension two or more; this suggests the parameterization is sensitive to the geometry of the summation rule, and other summation geometries could define inequivalent rates.
  • The paper's basis-change example shows the Fourier rate is not invariant under a change of orthonormal basis, so a useful follow-up would be to characterize which Schauder bases of $L^p$ yield rates linearly equivalent to the $L^p$-modulus.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a second-order parameterized complexity theory for the Banach space Lp(T), 1<p<∞. Three parameterizations are considered: the Lp-modulus of translation continuity (from Steinberg), the rate of approximation by step functions, and the rate of convergence of Fourier series. Theorem 16 claims that these three parameters are mutually bounded up to constant factors in both argument and value, and Corollary 17 concludes that they induce the same notion of second-order linear (or polynomial) time complexity. The proofs use the Fréchet–Kolmogorov theorem, Fejér summation, M. Riesz boundedness of the Dirichlet projection, and elementary norm inequalities. The paper also sketches examples of functions with large moduli, generalizations to Sobolev spaces and higher-dimensional tori, and a unifying definition of Schauder-system rates.

Significance. If the proof gaps identified below are repaired, this is a useful and credible contribution. It gives the first unified quantitative treatment of natural encodings of Lp(T), generalizing the well-understood continuous-function case, and it provides a principled answer to the parameterization question for integrable functions. The central derivation is grounded in standard external theorems (Fréchet–Kolmogorov, M. Riesz, Fejér), and the paper does not assume the equivalence it proves. The authors are also explicit about limitations, such as the failure of ball-multiplier Fourier convergence in higher dimensions. These are genuine strengths: the claimed equivalence is plausible and the overall architecture is sound, even though the written proofs need local repairs.

major comments (2)
  1. [§2.5, proof of Theorem 16(a)] The displayed chain concludes ∥F_Kf−f∥_p ≤ (C_p+1)2^{−n}, not ≤2^{−n}. For p≠2, the Lp norm of the Dirichlet projection is strictly larger than 1, so the bound at precision n does not satisfy the requirement of Definition 15. The theorem's O(1) argument shift can absorb C_p, but the proof must say so explicitly: start from the Fejér approximation with error 2^{−(n+N)} for N≈log_2(C_p+1) and then set K accordingly. As written, the proof is incomplete at exactly the point where the Riesz bound is used.
  2. [§2.5, proofs of Theorem 16(b) and (d); Fact 11e] Fact 11e is stated without proof and is applied in parts (b) and (d) with the wrong index. As stated, Fact 11e bounds μ_f(n) using an approximant with error 2^{−(n+2)}. The displayed proofs invoke it with K=2^{φ(n)} and K=2^{σ(n)}, which only guarantee error 2^{−n}, so the estimates do not close as written. The fix is to take K=2^{φ(n+2)} and K=2^{σ(n+2)} respectively (or to prove a variant of Fact 11e with the weaker closeness assumption), and to include the short triangle-inequality proof of Fact 11e.
minor comments (4)
  1. [§2.5(a)] The symbol F_K is used both for the Fejér kernel and for the Dirichlet projection operator; please use distinct notations (for example V_K for the kernel and S_K for the projection) to avoid confusion.
  2. [§3.1, Example 19] The claimed asymptotic rates in Example 19 appear incorrect as stated: for f(t)=Σ 2^{−k}e^{2πi2^k t}, the L2 tail after truncating at k=m has norm Θ(2^{−m}), so Definition 15 gives φ(n)=Θ(n), not exponential growth. The double-exponential example is similar; please correct the statements or clarify that the exponential growth refers to the degree 2^{φ(n)} rather than to φ(n) itself.
  3. [§1.2.1] The sentence 'Proceeding from a multitape to a one-tape Turing machine is known to incur an increase in running time increase most polynomial' contains a duplicated and ungrammatical phrase; it should say 'at most polynomial'.
  4. [§3.3] The asserted generalization of Corollary 17 to T^d with maximum-norm summation is stated without a proof sketch; given the known dependence on the summation convention (see [Fef71]), please add at least an outline of why the one-dimensional proof adapts.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main equivalence is proved from independent definitions and external analytic theorems, not from its own conclusion.

full rationale

The paper's central claim, Theorem 16, is an equivalence among three separately defined parameters: the Lp-modulus (Definition 10), the step rate (Definition 14), and the Fourier rate (Definition 15). Each parameter is defined minimally in terms of its own approximation or translation error, and none is defined in terms of another. The proof of part (a) uses Fejér kernels, a quantitative translation estimate, and the M. Riesz boundedness of the Dirichlet projection cited to Duoandikoetxea; parts (b) and (d) construct approximants and transfer a modulus bound via Fact 11e, a standard modulus-transfer lemma; part (c) is a direct averaging construction on subintervals. None of these steps assumes the inequality being proved, and no fitted parameter is later reported as a prediction. The Lp-modulus itself is imported from Steinberg [Ste17], an external source not authored by the present authors, so the load-bearing input is not a self-citation. There is a non-circular proof gap in the displayed chain for Theorem 16(a): the estimate gives ||F_K f - f||_p <= (C_p + 1)2^{-n}, not the claimed 2^{-n}, unless the constant C_p is absorbed into the O(1) argument shift; this is a correctness and repair issue, not a circularity. The paper is self-contained against external classical theorems, and the equivalence is not forced by definition.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard theorems of functional analysis and Fourier analysis: Frechet-Kolmogorov compactness provides the Lp-modulus; M. Riesz boundedness of the Dirichlet projection supplies the Fourier side; Fejer kernel estimates and Holder/Minkowski inequalities carry the quantitative estimates. No free parameters are fitted to data; no new physical or mathematical entities are postulated. The only potentially ad hoc element is the choice of binary moduli, which is a modeling convention justified in Remark 9.

assumptions (6)
  • standard math Dirichlet projection F_K is uniformly bounded on Lp(T) for 1 < p < infinity
    Used in proof of Theorem 16(a) to bound ||F_K(f-g_K)||_p <= C_p ||f-g_K||_p; cited to Duoandikoetxea Section 3.5.
  • standard math Frechet-Kolmogorov compactness: Lp_mu(T,R) is compact and every f in Lp(T) has an Lp-modulus (Fact 11)
    Basis for Definition 10 and for the modulus-transfer Fact 11e used in parts (b) and (d).
  • standard math Fejer kernel properties: F_K(t) >= 0, integral 1, and tail integral O(1/delta)/(K+1)
    Used in proof of Theorem 16(a) to control the tail of the Fejer mean.
  • standard math Holder and Minkowski integral inequalities (Equations 9-13)
    Used throughout the proof of Theorem 16.
  • standard math Step functions are dense in Lp(T)
    Underlies Definition 14 and the approximation property used in proof (c).
  • standard math Translations are continuous in Lp for p < infinity, so the pointwise minimal Lp-modulus exists
    Definition 10 requires existence of a minimal mu.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Second-Order Parameterizations for the Complexity Theory of Integrable Functions." pith.science (2026). https://pith.science/paper/YV3TZM2N

@misc{pith2026250611210,
  author       = {Pith},
  title        = {Pith review of: Second-Order Parameterizations for the Complexity Theory of Integrable Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YV3TZM2N}},
  note         = {Machine review of arXiv:2506.11210}
}
abstract

We develop a unified second-order parameterized complexity theory for spaces of integrable functions. This generalizes the well-established case of second-order parameterized complexity theory for spaces of continuous functions. Specifically we prove the mutual linear equivalence of three natural parameterizations of the space $\Lrm{p}$ of $p$-integrable complex functions on the real unit interval: (binary) $\Lrm{p}$-modulus, rate of convergence of Fourier series, and rate of approximation by step functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    R. L. Acosta Babb . The Lp convergence of fourier series on triangular domains. Proceedings of the Edinburgh Mathematical Society , 66(2), 453–474, 2023

    work page 2023

  2. [2]

    Complexity Blowup for Solutions of the Laplace and the Diffusion Equation

    A. Bacho, H. Boche, and G. Kutyniok . Complexity blowup for solutions of the laplace and the diffusion equation. CoRR , abs/2212.00693, 2022

    work page Pith review arXiv 2022

  3. [3]

    Braverman and S

    M. Braverman and S. A. Cook . Computing over the reals: Foundations for scientific computing. Notices of the AMS , 53(3), 318--329, 2006

    work page 2006

  4. [4]

    Brattka and R

    V. Brattka and R. Dillhage . Computability of compact operators on computable banach spaces with bases. Math. Log. Q. , 53(4-5), 345--364, 2007

    work page 2007

  5. [5]

    Br \'e zis

    H. Br \'e zis . Functional Analysis, S obolev Spaces and Partial Differential Equations . Springer-Verlag, New York, 2011

    work page 2011

  6. [6]

    E. W. Cheney . Introduction to Approximation Theory . AMS Chelsea Publishing. AMS Chelsea Pub., New York, NY, second edition, 2000

    work page 2000

  7. [7]

    Duoandikoetxea

    J. Duoandikoetxea . Fourier Analysis , volume 29 of GSM . AMS, 2001

    work page 2001

  8. [8]

    Fefferman

    C. Fefferman . The multiplier problem for the ball. Annals of Mathematics , 94(2), 330--336, 1971

    work page 1971

Show all 39 references
  1. [9]

    Flum and M

    J. Flum and M. Grohe . Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006

    2006

  2. [10]

    Friedman

    H. Friedman . The computational complexity of maximization and integration. Advances in Mathematics , 53, 80--98, 1984

    1984

  3. [11]

    B. M. Kapron and S. A. Cook . A new characterization of type-2 feasibility. SIAM Journal on Computing , 25(1), 117--132, 1996

    1996

  4. [12]

    Kawamura and S

    A. Kawamura and S. A. Cook . Complexity theory for operators in analysis. ACM Transactions on Computation Theory , 4(2), 5:1--5:24, 2012

    2012

  5. [13]

    Y. Kanada . -0.5ex [height=2.5ex] computingpi . Journal of Mathematical Culture , 1(1), 72--83, 2003

    2003

  6. [14]

    Kawamura

    A. Kawamura . L ipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity , 19(2), 305--332, 2010

    2010

  7. [15]

    K.-I. Ko . Complexity Theory of Real Functions . Progress in Theoretical Computer Science. Birkh\"auser, Boston, 1991

    1991

  8. [16]

    Kohlenbach

    U. Kohlenbach . Applied Proof Theory: Proof Interpretations and Their Use in Mathematics . Springer, Berlin, 2008

    2008

  9. [17]

    Kolmogorov and V

    A. Kolmogorov and V. Tikhomirov . E -entropy and E -capacity of sets in functional spaces. Uspekhi Mat. Nauk , 14(2), 3--86, 1959

    1959

  10. [18]

    Koswara, G

    I. Koswara, G. Pogudin, S. Selivanova, and M. Ziegler . Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations. Journal of Complexity , page 101727, 2023

    2023

  11. [19]

    Kreitz and K

    C. Kreitz and K. Weihrauch . Theory of representations. Theoretical Computer Science , 38, 35--53, 1985

    1985

  12. [20]

    Kawamura, F

    A. Kawamura, F. Steinberg, and M. Ziegler . Complexity theory of (functions on) compact metric spaces. In Proceedings of the 31st A nnual ACM - IEEE S ymposium on L ogic in C omputer S cience ( LICS 2016) , page 10, New York, 2016. ACM

    2016

  13. [21]

    Kawamura, F

    A. Kawamura, F. Steinberg, and M. Ziegler . On the computational complexity of the D irichlet problem for P oisson's equation. Mathematical Structures in Computer Science , 27(8), 1437--1465, 2017

    2017

  14. [22]

    D. Kunkle . Type-2 computability on spaces of integrable functions. Mathematical Logic Quarterly , 50(4,5), 417--430, 2004

    2004

  15. [23]

    Lim and M

    D. Lim and M. Ziegler . Quantitative coding and complexity theory of compact metric spaces. In M. Anselmo, G. Della Vedova, F. Manea, and A. Pauly, editors, Beyond the Horizon of Computability , pages 205--214, Cham, 2020. Springer International Publishing

    2020

  16. [24]

    Lim and M

    D. Lim and M. Ziegler . Degrees of second and higher-order polynomials. arXiv, 2023. 2305.03439

    2023 arXiv

  17. [25]

    Lim and M

    D. Lim and M. Ziegler . Quantitative coding and complexity theory of continuous data: Part i: Motivation, definition, consequences. J.ACM , 72(1), January 2025

    2025

  18. [26]

    D. Lim, S. Selivanova, and M. Ziegler . What is a polynomial-time computable L 2 function? In G. G. et al., editor, Proc. 17th International Conference on Computability and Complexity in Analysis , volume 17th of Computability and Complexity in Analysis , pages 41--42, Bologna...

    2020

  19. [27]

    S. Park, F. Brau e, P. Collins, S. Kim, M. Kone c n \' y , G. Lee, N. M \"u ller, E. Neumann, N. Preining, and M. Ziegler . Semantics, specification logic, and H oare logic of exact real computation. Logical Methods in Computer Science , 20(2), June 2024

    2024

  20. [28]

    M. B. Pour-El and J. I. Richards . A computable ordinary differential equation which possesses no computable solution. Annals Math.\ Logic , 17, 61--90, 1979

    1979

  21. [29]

    M. B. Pour-El and J. I. Richards . The wave equation with computable initial data such that its unique solution is not computable. Advances in Math. , 39, 215--239, 1981

    1981

  22. [30]

    M. B. Pour-El and J. I. Richards . Computability in Analysis and Physics . Perspectives in Mathematical Logic. Springer, Berlin, 1989

    1989

  23. [31]

    oder . Admissible representations in computable analysis. In A. Beckmann, U. Berger, B. L \

    M. Schr\"oder . Admissible representations in computable analysis. In A. Beckmann, U. Berger, B. L \"o we, and J. Tucker, editors, Logical Approaches to Computational Barriers , volume 3988 of Lecture Notes in Computer Science , pages 471--480, Berlin, 2006. Springer. Second C...

    2006

  24. [32]

    E. Specker . Der S atz vom M aximum in der rekursiven A nalysis. In A. Heyting, editor, Constructivity in Mathematics , Studies in Logic and the Foundations of Mathematics, pages 254--265, Amsterdam, 1959. North-Holland. Proc. Colloq., Amsterdam, Aug. 26--31, 1957

    1959

  25. [33]

    Steinberg

    F. Steinberg . Complexity theory for spaces of integrable functions. Logical Methods in Computer Science , 13(3), Paper No. 21, 39, 2017

    2017

  26. [34]

    S. Sun, N. Zhong, and M. Ziegler . Computability of the solutions to navier-stokes equations via effective approximation. In D. Du and J. Wang, editors, Complexity and Approximation - In Memory of Ker-I Ko , volume 12000 of Lecture Notes in Computer Science , pages 80--112. Sp...

    2020

  27. [35]

    Townsend

    M. Townsend . Complexity for type-2 relations. Notre Dame J. Formal Log. , 31(2), 241--262, 1990

    1990

  28. [36]

    Weihrauch

    K. Weihrauch . Computable Analysis . Springer, Berlin, 2000

    2000

  29. [37]

    Weihrauch

    K. Weihrauch . Computational complexity on computable metric spaces. Mathematical Logic Quarterly , 49(1), 3--21, 2003

    2003

  30. [38]

    Weihrauch and N

    K. Weihrauch and N. Zhong . Is wave propagation computable or can wave computers beat the T uring machine? Proceedings of the London Mathematical Society , 85(2), 312--332, 2002

    2002

  31. [39]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence '...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.