Pith. sign in

REVIEW 5 minor 26 references

Every fixed-dimensional subspace of L^p[0,1] linearly embeds into ℓ_p^N with N ≤ C ε^{-2(d-1)/(d+2p)}, and for non-even p this exponent is optimal up to constants.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For fixed d ≥ 2 and every p not an even integer, every d-dimensional subspace of L^p embeds into ℓ_p^N with distortion 1+ε for N ≍_{d,p} ε^{-2(d-1)/(d+2p)}, optimally in ε up to constants.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection This paper settles the epsilon-dependence of constant-dimension L^p subspace embeddings for every p not in 2Z, up to constants, and the proof is worth reading despite one delicate approximation step.

arxiv 2607.11747 v5 pith:BTDMM7VF submitted 2026-07-13 math.FA

Optimal Embeddings of Constant-Dimensional Subspaces of L^p into ell_p^N

Yi Li This is my paper
classification math.FA MSC 46B0741A10
keywords subspace embeddingL^p spacessparsificationequatorial band discrepancypolynomial approximationpartial colouringconstant dimension
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

This paper determines, up to constant factors, the smallest ambient dimension N needed to embed any fixed-dimensional subspace of L^p[0,1] into ℓ_p^N with distortion 1+ε: for every d≥2 and p≥1, N ≤ C_{d,p} ε^{-2(d-1)/(d+2p)}. For p not an even integer this matches a known lower bound, so the ε-dependence of the problem is now fully settled; even integer p already admit isometric embeddings of dimension independent of ε. The proof reduces the problem to a sparsification statement: any finitely supported probability measure on the sphere can be reweighted onto about that many atoms so that the worst-case error in the moment ∫|⟨u,y⟩|^p dμ stays below ε. The mechanism is to split |t|^p into a polynomial part, which cancels exactly after reweighting, and a small-total-variation remainder, controlled by an integrated equatorial-band discrepancy estimate. This removes logarithmic factors for odd integer p and supplies the first upper bound with this exponent for non-integer p.

Core claim

The main theorem states: for fixed d≥2 and p≥1, every d-dimensional subspace of L^p[0,1] admits a linear (1+ε)-embedding into ℓ_p^N with N ≤ C_{d,p} ε^{-2(d-1)/(d+2p)}; for p ∉ 2Z this matches the known lower bound and hence N_p(d,ε) ≍_{d,p} ε^{-2(d-1)/(d+2p)}. It is proved through a sparsification theorem: a finitely supported probability measure on S^{d-1} can be replaced by an atomic probability measure supported on at most C_{d,p} ε^{-2(d-1)/(d+2p)} of the original points such that sup_u |∫|⟨u,y⟩|^p dν − ∫|⟨u,y⟩|^p dμ| ≤ ε. The proof achieves this by making ν exact on spherical polynomials of degree K ≈ ε^{-2/(d+2p)} and controlling the remainder |t|^p − p_K through its total variation a

What carries the argument

The core object is the decomposition |t|^p = p_K(t) + b_K(t), where p_K is an even polynomial of degree ≤K with p_K(0)=0 and b_K is an even function whose total variation on [−1,1] is at most C_p K^{-p}. The sparsification procedure iteratively reduces the number of atoms while preserving exactness on all spherical polynomials of degree K; the polynomial part therefore contributes zero error. The remainder is controlled by writing its integral against the difference of two measures as a Stieltjes integral of equatorial-band discrepancies and bounding that by a chaining-based discrepancy estimate that saturates a constant fraction of atoms per round, with no logarithmic loss. Choosing K propo

Load-bearing premise

The tightness of the whole result rests on one approximation fact: the cusped function sgn(t)|t|^{p−1} can be approximated by odd polynomials in L1 with error exactly O(K^{−p}); if that rate carried any extra logarithmic factor, the matching exponent in Theorem 1.1 would be lost.

What would settle it

Numerically evaluate, for a non-integer p such as p=3/2, the integral modulus of smoothness ω^r(G_{p−1}; δ)_{L1} of G_α(θ)=sgn(cosθ)|cosθ|^α for small δ (r > α+1). If it behaves like δ^{α+1}·log(1/δ) instead of δ^{α+1}, Lemma A.2 is false and the paper's exponent would carry a hidden log. Equivalently, compute the minimal L1 error of odd degree-K polynomial approximation to sgn(t)|t|^{p−1} on [−1,1]; a decay slower than K^{−p} by a polylog factor would falsify the polynomial-approximation step.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • For every fixed d≥2 and every p≥1 with p∉2Z, the quantity N_p(d,ε) is now known up to constants: it behaves like ε^{-2(d-1)/(d+2p)}.
  • The previously open case of non-integer p is covered, and the logarithmic factors for odd integer p are removed.
  • For even p, the theorem's upper bound is superseded by existing isometric embeddings whose dimension does not depend on ε, completing the dichotomy.
  • When the input measure is given explicitly, the sparsified measure can be computed by a randomized polynomial-time algorithm in M and 1/ε (Remark 1.3 and Section 5).
  • The sparsification theorem applies to arbitrary finitely supported probability measures on the sphere, so it is a standalone dimension-reduction tool for moment problems of the form ∫|⟨u,y⟩|^p dμ.

Where Pith is reading between the lines

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

  • The same polynomial-cancellation plus total-variation strategy could plausibly yield tight ε-dependence for embedding subspaces into ℓ_p^N for other 'cusped' kernels, provided a sharp polynomial approximation with small TV remainder exists.
  • The exponent formula is continuous in p, but the paper treats p as fixed; whether the constants C_{d,p} remain controlled as p approaches an even integer, where b_K vanishes, is not addressed and could be probed numerically.
  • The argument only uses finite-dimensionality and John's theorem, so the same bound likely applies to any d-dimensional subspace of a normed space whose norm is ℓ_p-averaged over an arbitrary measure space, as long as an approximate embedding into ℓ_p^M is available.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper studies the minimal dimension N_p(d,ε) needed to (1+ε)-embed every d-dimensional subspace of L^p[0,1] into ℓ_p^N for fixed d≥2 and p≥1. It proves the upper bound N_p(d,ε) ≤ C_{d,p} ε^{-2(d-1)/(d+2p)} for all p≥1 (Theorem 1.1), via a sparsification theorem (Theorem 1.2) for finitely supported probability measures on S^{d-1}. The proof combines a polynomial approximation of |t|^p with a remainder of small total variation (Lemma 2.2, proved through the Jackson-type Lemma 2.3 and the modulus-of-smoothness estimate Lemma A.2) with an iterative partial-colouring argument controlling integrated equatorial-band discrepancy (Theorem 2.1, Lemmas 4.7 and 4.8). For p∉2Z, the upper bound matches the known lower bounds for ℓ_2^d, giving N_p(d,ε) ≍_{d,p} ε^{-2(d-1)/(d+2p)}; for even p, isometric embeddings of ε-independent dimension are known.

Significance. If correct, the result settles the ε-dependence of the constant-dimensional L^p subspace-embedding problem for every p∉2Z, removing logarithmic factors from earlier integer-p upper bounds and covering non-integral p for the first time. The paper is well structured: the reduction chain Theorem 2.1 → Theorem 1.2 → Theorem 1.1 is clean, and the chaining/partial-colouring iteration in §4.6 is coherent. The polynomial-approximation part is proved in detail, and the stress-test concern about a possible logarithmic loss in the K^{-p} rate does not land: Lemma A.2's two-case estimate gives exactly δ^{α+1}, and the trigonometric-to-algebraic conversion in Lemma 2.3 loses no logarithmic factor. The lower bounds are cited rather than reproved, but that is appropriate. Overall this is a significant advance in a classical problem.

minor comments (5)
  1. [§4.6 (support-reduction step)] The displayed atom-count formula reads 'm−|I*|/2+|I*| = m/2+|I*|/2'; as printed, the left-hand side equals m+|I*|/2. It should be (m−|I*|)/2+|I*| = m/2+|I*|/2. The subsequent bound m/2+N/8 is correct once the parentheses are fixed.
  2. [Appendix A / Lemma 2.3] In the final inequality, the step ∫_{-1}^1 |sgn(t)|t|^α−q_K(t)| dt ≤ 1/2 ∫_0^{2π} |G_α−T'_K| dθ uses sinθ≤1 together with evenness of G_α and T'_K. This is correct, but it should be stated explicitly; otherwise the reader may suspect a missing Jacobian factor.
  3. [Appendix A / Lemma A.2] In Case 2, the estimate ∫_{rδ}^{π/2} x^{α−r} dx ≤ C δ^{α−r+1} is the exact point where the sharp exponent is decided: because r>α+1, the lower limit supplies the negative power, and the later |h|^r factor cancels it to δ^{α+1}. A sentence making this cancellation explicit would reassure the reader that no logarithmic factor enters.
  4. [§1 (Introduction)] The sentence on [18] says Reis–Rothvoss removed the logarithmic factor for p=1, obtaining N_1(d,ε)≲d/ε^2. For fixed d the optimal exponent is ε^{-2(d-1)/(d+2)}, so the cited result is in a different regime; please clarify this to avoid confusion.
  5. [§5 (Algorithmic remarks)] Remark 1.3 promises a poly(M,1/ε) randomized algorithm, but the description of Line 13 is compressed. In particular, the polynomial-time construction of the separation oracle for K and the greedy net-size bound are only sketched. Since this is a side claim, it is not blocking, but a precise statement or lemma would be desirable.

Circularity Check

0 steps flagged

No significant circularity: the upper bound is derived from polynomial approximation plus discrepancy/partial-colouring, with self-citations used only as external lower-bound context.

full rationale

The derivation chain is self-contained. Theorem 1.1 is reduced to the sparsification statement Theorem 1.2 by a standard averaging/John-theorem argument, and Theorem 1.2 is proved from Theorem 2.1, Lemma 2.2, and the integrated-band-discrepancy estimate. The polynomial part p_K(⟨u,y⟩) cancels exactly because it lies in P_K(S^n), while the remainder b_K is controlled through Stieltjes integration by parts and the band-discrepancy bound; this is a genuine cancellation, not a renaming of the target error. The sharp K^{-p} total-variation rate is derived in Lemma 2.2 from Lemma 2.3, whose proof rests on the modulus-of-smoothness estimate Lemma A.2 and Jackson's theorem, not on the paper's main theorem. The chaining/partial-colouring argument (Lemmas 4.5, 4.7, 4.8 and Rothvoss's theorem) delivers the band-discrepancy bounds from covering-number estimates and does not presuppose the sparsification error. The self-citations [13] and [14] are used for the known lower bound N_p(ℓ_2^d, ε) and for prior upper bounds; they are external, parameter-free results and are not inputs to the upper-bound derivation. Thus no step reduces by construction to its own inputs or to a fitted parameter, and no load-bearing self-citation chain forces the conclusion.

Axiom & Free-Parameter Ledger

5 free parameters · 9 axioms · 0 invented entities

None of the axioms are invented for this paper: they are classical theorems (John, Jackson, Šidák) or published deep results (low-crossing matchings [16], Rothvoss partial colouring [19], polynomial sign patterns [17]). The two domain_assumption items are standard reductions used by the whole subfield. The load-bearing novelty — the K^{-p} total-variation polynomial approximation (Lemma 2.2) — is proved in the paper (Lemma 2.3 + Appendix A), not assumed; its delicacy is captured under weakest_assumption. Free parameters are existential proof constants (thresholds γ_n, A_q, c_n, c̄_n, and the implicit constant in N ≍ ⋯), none fitted to data and none encoding the target result. No invented entities: P_K(S^n), q_K, b_K, β_K are constructions, and the integrated-discrepancy vectors A_u are linear functionals, not new objects.

free parameters (5)
  • γ_n (K = ⌊γ_n N^{1/n}⌋)
    Hand-chosen small threshold in §3 so that dim P_K(S^n) ≤ c_n N, making Theorem 2.1 applicable. Existence constant, not data-fitted.
  • A_q (chaining slab width, Lemma 4.5)
    Chosen large so that c_q := 2^{q/2} e^{-A_q²/2} ≤ 1/5, guaranteeing γ_F(K_s) ≥ e^{-s}. Part of the Gaussian-measure lower bound feeding Rothvoss partial colouring.
  • c_n (Theorem 2.1 / iteration dimension threshold)
    Chosen with c_n ≤ min(c̄_n/4, 1/(4r_n)) so the support-reduction loop in §4.6 can run to completion.
  • c̄_n (Lemma 4.8 codimension constant)
    Chosen small so that codim(F) ≤ c_0 k, the hypothesis of Rothvoss's theorem, holds with k = ⌊r/2⌋.
  • Implicit constant in N ≍_{d,p} ε^{-2(d-1)/(d+2p)} (§3)
    Chosen 'sufficiently large' to absorb C_{d,p} in the final error bound of Theorem 1.2. Existence constant.
axioms (9)
  • standard math John's ellipsoid theorem
    Used in proof of Theorem 1.1 to reparametrize the subspace so that 1 ≤ ||Au||_p^p ≤ d^{p/2} on S^{d-1}.
  • domain assumption Every d-dimensional subspace of L^p[0,1] is arbitrarily close to a subspace of some ℓ_p^M
    Standard density/step-function reduction at the start of the proof of Theorem 1.1; the sparsification then operates on the finite coordinate representation.
  • standard math dim P_K(S^n) = O(K^n) (spherical polynomial dimension formula)
    Cited [4, Cor. 1.1.5]; used in §3 to calibrate K ≍ N^{1/n}.
  • standard math Dual shatter bound for equatorial bands: π*_{B_n}(m) ≤ C_n m^n
    Polynomial sign-pattern count ([17, §6.2]); used in Lemma 4.2 to feed the low-crossing matching theorem.
  • domain assumption Low-crossing matching theorem (Matoušek [16, Thm 5.17])
    Provides a matching whose edges are crossed by every equatorial band at most O(r^{1−1/n}) times; used as a black box in Lemma 4.8.
  • domain assumption Rothvoss's subspace partial-colouring theorem ([19, Lemma 9])
    The engine producing saturation of κ_0 k coordinates under exactness constraints and a Gaussian-measure hypothesis; used in Lemma 4.8 and Section 5.
  • standard math Šidák's lemma for Gaussian rectangles
    Lower bound for the Gaussian measure of the slab intersection in Lemma 4.5.
  • standard math Jackson-type L1 approximation and L∞–L1 inequality for trigonometric polynomials
    Appendix A (Lemma A.1, [24, p. 325]) and §5 ([24, p. 229]); bases of the polynomial-approximation lemma and the algorithmic derivative bound (17).
  • domain assumption Existence of equal-area partitions of S^n into N cells of diameter O(N^{-1/n})
    Used in the secondary results of Appendices C and D (sphere-partitioning bounds).

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$." pith.science (2026). https://pith.science/paper/BTDMM7VF

@misc{pith2026260711747,
  author       = {Pith},
  title        = {Pith review of: Optimal Embeddings of Constant-Dimensional Subspaces of $L^p$ into $\ell_p^N$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BTDMM7VF}},
  note         = {Machine review of arXiv:2607.11747}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

For $d \geq 2$, $p \geq 1$ and $\epsilon > 0$, let $N_p(d,\epsilon)$ be the smallest integer $N$ such that every $d$-dimensional subspace of $L^p[0,1]$ admits a linear embedding into $\ell_p^N$ with distortion at most $1 + \epsilon$. For fixed $d\geq 2$ and $p\geq 1$, the bound \[ N_p(d,\epsilon) \lesssim_{d,p} \epsilon^{-2(d-1)/(d+2p)} \] is established. For $p \notin 2\mathbb{Z}$, this matches the known lower bound up to constant factors. For odd integers $p$, previous upper bounds with this exponent incurred additional logarithmic factors, except in the logarithm-free case $p = 1$; for non-integral $p$, no upper bound with this exponent was previously known. For even integers $p$, isometric embeddings of dimension independent of $\epsilon$ are known. For $p \notin 2\mathbb{Z}$, the proof approximates $|t|^p$ by a polynomial with a remainder of small total variation. The polynomial part contributes no error, while the error from the remainder is controlled by an integrated equatorial-band discrepancy estimate.

Review history (4 revisions) →

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

26 extracted references · 1 linked inside Pith

  1. [1]

    Bourgain and J

    J. Bourgain and J. Lindenstrauss. Distribution of points on spheres and approximation by zonotopes.Israel Journal of Mathematics, 64(1):25–31, Feb 1988

    1988

  2. [2]

    Bourgain, J

    J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by zonotopes.Acta Mathematica, 162:73–141, 1989

    1989

  3. [3]

    Cohen and Richard Peng.L p row sampling by Lewis weights

    Michael B. Cohen and Richard Peng.L p row sampling by Lewis weights. InProceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 183–192, New York, NY, USA, 2015. ACM

    2015

  4. [4]

    Springer Monogr

    Feng Dai and Yuan Xu.Approximation theory and harmonic analysis on spheres and balls. Springer Monogr. Math. New York, NY: Springer, 2013

    2013

  5. [5]

    Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15(2):341–363, 1986

    Herbert Edelsbrunner, Joseph O’Rourke, and Raimund Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15(2):341–363, 1986

    1986

  6. [6]

    Computing Lewis weights to high precision

    Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing Lewis weights to high precision. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022, pages 2723–2742. SIAM, 2022

    2022

  7. [7]

    Foucart, Y

    S. Foucart, Y. Kryakin, and A. Shadrin. On the exact constant in the Jackson-Stechkin inequality for the uniform metric.Constructive Approximation, 29:157–179, 2009

    2009

  8. [8]

    One-shot active learning based on Lewis weight sampling for multiple deep models

    Sheng-Jun Huang, Yi Li, Yiming Sun, and Ying-Peng Tang. One-shot active learning based on Lewis weight sampling for multiple deep models. InProceedings of the International Conference on Learning Representations, 2024

    2024

  9. [9]

    Johnson and Gideon Schechtman

    William B. Johnson and Gideon Schechtman. Chapter 19 – Finite dimensional subspaces of Lp. In W. B. Johnson and J. Lindenstrauss, editors,Handbook of the Geometry of Banach Spaces, volume 1 ofHandbook of the Geometry of Banach Spaces, pages 837–870. Elsevier Science B.V., 2001

    2001

  10. [10]

    Chapter 21 – Aspects of the isometric theory of Banach spaces

    Alexander Koldobsky and Hermann K¨ onig. Chapter 21 – Aspects of the isometric theory of Banach spaces. In W. B. Johnson and J. Lindenstrauss, editors,Handbook of the Geometry of Banach Spaces, volume 1 ofHandbook of the Geometry of Banach Spaces, pages 899–939. Elsevier Science B.V., 2001

    2001

  11. [11]

    Springer, 1991

    Michel Ledoux and Michel Talagrand.Probability in Banach Spaces: Isoperimetry and Pro- cesses. Springer, 1991

    1991

  12. [12]

    D. R. Lewis. Ellipsoids defined by Banach ideal norms.Mathematika, 26(1):18–29, 1979

    1979

  13. [13]

    Woodruff

    Yi Li, Honghao Lin, and David P. Woodruff. Theℓ p-subspace sketch problem in small di- mensions with applications to support vector machines. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 850–877. SIAM, 2023

    2023

  14. [14]

    Woodruff

    Yi Li, Ruosong Wang, and David P. Woodruff. Tight bounds for the subspace sketch problem with applications.SIAM J. Comput., 50(4):1287–1335, 2021. 23

    2021

  15. [15]

    Improved upper bounds for approximation by zonotopes.Acta Mathematica, 177(1):55–73, 1996

    Jiˇ r ´ ı Matouˇ sek. Improved upper bounds for approximation by zonotopes.Acta Mathematica, 177(1):55–73, 1996

    1996

  16. [16]

    Springer-Verlag, 1999

    Jiˇ r ´ ı Matouˇ sek.Geometric Discrepancy: An Illustrated Guide, volume 18 ofAlgorithms and Combinatorics. Springer-Verlag, 1999

    1999

  17. [17]

    Springer-Verlag, 2002

    Jiˇ r ´ ı Matouˇ sek.Lectures on Discrete Geometry, volume 212 ofGraduate Text in Mathematics. Springer-Verlag, 2002

    2002

  18. [18]

    Linear-sizeℓ 1 sparsifiers, 2026

    Victor Reis and Thomas Rothvoss. Linear-sizeℓ 1 sparsifiers, 2026. arXiv:2606.28147 [math.MG]

    Pith/arXiv arXiv 2026

  19. [19]

    Constructive discrepancy minimization for convex sets.SIAM J

    Thomas Rothvoss. Constructive discrepancy minimization for convex sets.SIAM J. Comput., 46(1):224–234, 2017

    2017

  20. [20]

    Tight embedding of subspaces ofL p inℓ n p for evenp.Proceedings of the American Mathematical Society, 139(12):4419–4421, December 2011

    Gideon Schechtman. Tight embedding of subspaces ofL p inℓ n p for evenp.Proceedings of the American Mathematical Society, 139(12):4419–4421, December 2011

    2011

  21. [21]

    Rectangular confidence regions for the means of multivariate normal distribu- tions.Journal of the American Statistical Association, 62(318):626–633, 1967

    Zbynˇ ekˇSid´ ak. Rectangular confidence regions for the means of multivariate normal distribu- tions.Journal of the American Statistical Association, 62(318):626–633, 1967

    1967

  22. [22]

    Jonathan W. Siegel. Optimal approximation of zonoids and uniform approximation by shallow neural networks.Constructive Approximation, 62:441–469, 2025

    2025

  23. [23]

    PhD thesis, Nanyang Technological University, 2024

    Yiming Sun.Algorithms for Large-Scale Numerical Linear Algebra. PhD thesis, Nanyang Technological University, 2024

    2024

  24. [24]

    A. F. Timan.Theory of Approximation of Functions of a Real Variable. Pergamon Press, 1963

    1963

  25. [25]

    PhD thesis, Carnegie Mellon University, 2024

    Taisuke Yasuda.Algorithms for Matrix Approximation: Sketching, Sampling, and Sparse Optimization. PhD thesis, Carnegie Mellon University, 2024. A Polynomial Approximation inL 1-Norm The goal of this section is to prove Lemma 2.3. We first recall some basic definitions from approx- imation theory. For a 2π-periodic functionfthat is integrable on [0,2π], de...

    2024

  26. [26]

    Otherwise, under a linear transformation, the problem reduces to approximatings7→s p on the fixed interval [1,1 +Cn]

    IfI j is a singleton, takep j to be the constant value of| · |p onI j. Otherwise, under a linear transformation, the problem reduces to approximatings7→s p on the fixed interval [1,1 +Cn]. This function has an analytic extension to the ellipseE ρn(1,1 +C n) for someρ n > Cn/2 depending only onn. Lemma C.3, followed by the inverse transformation, gives a p...

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.