REVIEW 1 major objections 3 minor 10 references
Kolmogorov widths of the class $W_1^1$
T0 review · 1 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read This paper proves sharp two-sided estimates for the Kolmogorov n-width of the Sobolev class W_1^1[0,1] in L_q[0,1] for 2<q<∞, establishing that d_n(W_1^1,L_q) ≍ n^{-1/2} log n and completing the classical table of width orders for…
desk verdict Resolves the last open case in the classical Sobolev-width table with a clean, checkable proof; worth refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key object is the family of step functions χ_t and their Fourier–Haar coefficients X_{k,j}(t), together with an auxiliary family Z_{k,j}(t) of functions of t that are mutually orthogonal and satisfy ∫ Z_{k,j}(t)^2 dt = 2^k. These Z functions serve as a dual test family: the weighted inner product of X(t) with Z(t), averaged over t, equals (k1-k0+1)/a, a quantity of order log n. The Marcinkiewicz–Paley inequality transfers L_q norms of functions to weighted ℓ_q norms of Haar coefficients, and the isotropy identity ∫⟨v,Z(t)⟩^2 dt = ‖v‖^2 makes the projection of Z onto an n-dimensional subspace have integrated squared norm exactly n, bounding the cross term I2 by about δ log n. The dichotomy in the lemma follows by comparing these estimates.
What would settle it
Fix q=3 and compute or bound from below the quantity d_n($W_1^{1}$[0,1], L_3[0,1]) for increasing n using a discretized linear programming formulation; if $n^{{1/2}}$ d_n / log n tends to 0, the theorem's lower bound fails. Alternatively, for infinitely many n exhibit an n-dimensional subspace whose elements approximate every step function χ_t within o($n^{{-1/2}}$ log n) in L_q norm, which would directly contradict the lemma.
Extended reading notes
Core claim
The central claim is the two-sided estimate c1(q) $n^{{-1/2}}$ log n ≤ d_n($W_1^{1}$[0,1], L_q[0,1]) ≤ c2(q) $n^{{-1/2}}$ log n for all q>2 and n≥2. The paper contributes the missing lower bound, obtained by showing that any n-dimensional subspace that approximates every step function χ_t (the sign-changing function at t) to within less than δ $n^{{-1/2}}$ log n in L_q must fail to control the Haar coefficients of these functions in a weighted ℓ_q sense. A specially designed family Z_{k,j}(t) of functions of t provides a duality test: its inner product with the Haar coefficient vectors of χ_t is large, of order log n, while the error's L_q norm and the finite-dimensionality of the subspace impose upper bounds of order $n^{{-1/2}}$ and $n^{{γ}}$. The combination forces the lower bound and completes the parameter range r=p=1, 2<q<∞.
Load-bearing premise
The proof assumes that, given an approximation of each step function χ_t by some n-dimensional subspace, the approximating functions η_t can be chosen so that they depend measurably on t, because the central estimate averages over all t in [0,1].
Editorial extensions
If this is right
- The sharp order for r=p=1, 2<q<∞ now matches the pattern expected from the classical table, with exactly a logarithmic factor multiplying n^{-1/2}.
- Kulanin's lower bound with log^{1/2-ε} n is improved to a full log n, closing the logarithmic gap that remained after earlier work.
- Belinsky's result for subspaces generated by n harmonics has the same order as the unrestricted n-width, so allowing arbitrary approximating subspaces does not improve the rate.
- The lemma establishes a quantitative dichotomy: any n-dimensional family approximating the step functions either has L_2-average error at least δ n^{-1/2} log n or L_q error at least n^{-γ} for γ>1/q.
Reading between the lines
- Beyond the paper's claims, the simultaneous dyadic-control mechanism may extend to lower bounds for average Kolmogorov widths or for related Besov classes, whose Haar-coefficient structure is similar.
- The argument suggests a general principle: when a one-parameter family of targets must be approximated by a finite-dimensional subspace, a logarithmic factor arises precisely because no single frequency band can absorb all the error.
- A routine but necessary addition to the written proof is a measurable selection argument ensuring that the approximating functions η_t can be chosen to depend measurably on t; without it, the averaging over t in the lemma is not fully justified.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that for every q in (2,∞) the Kolmogorov n-width of the univariate Sobolev class W_1^1 in L_q satisfies d_n(W_1^1,L_q) ≍ n^{-1/2} log n. The upper bound is cited from Kulanin, and the main contribution is a matching lower bound. The lower bound is obtained through a lemma: for any family {η_t} lying in an n-dimensional subspace, either the average squared L2 distance to the step functions χ_t is at least δ^2 n^{-1} log^2 n, or the average Lq distance is at least n^{-γ}. The lemma is proved via weighted Haar coefficients, a duality/Hölder step, and isotropy of specially constructed functions Z_{k,j}. The proof tracks all constants, with the levels k0 and k1 chosen as floor functions of logarithmic scales.
Significance. If correct, this result completes the study of orders of decay of Kolmogorov widths for classical univariate Sobolev classes of integer smoothness, closing the last open parameter case r=p=1, 2<q<∞. The proof is transparent and largely self-contained, using standard tools (Marcinkiewicz–Paley, Hölder duality, metric projection) and tracking constants explicitly. The lower-bound method, which combines dyadic decomposition with simultaneous control of all levels via duality and averaging, is elegant and likely to be influential. The manuscript also gives credit to prior work and clearly identifies the open gap it closes.
major comments (1)
- [Proof of Theorem (paragraph following the Lemma)] The passage asserting the existence of a family {η_t} with sup_t ‖χ_t−η_t‖_{L_q} < δ n^{-1/2} log n is not justified by the definition of the n-width alone: the width gives for each t a near-optimal approximation, but the Lemma requires a single measurable family in t, and without measurability the integrals in (2) and (3) are undefined. This gap is load-bearing for the lower-bound proof. It is fixable: since the map t↦χ_t is continuous into L_q and L_q is uniformly convex for q∈(2,∞), the metric projection P_{Q_n}χ_t onto the fixed finite-dimensional subspace Q_n is single-valued and continuous; taking η_t=P_{Q_n}χ_t yields the required measurable family. Please add this argument or an appropriate measurable-selection reference.
minor comments (3)
- [Introduction] The definition of A≍B contains a corrupted symbol: 'A /greaterorsimilarB' should read 'A ≳ B' (or 'A ≥ cB').
- [Proof of Lemma (definition of Z_{k,j})] In the definition of Z_{k,j}(t), the variable in the first line is written as 'x' but should be 't'; the support condition should be t ∈ [(j−1)2^{−k}, j2^{−k}].
- [Proof of Lemma (final paragraph)] The final paragraph contains typos: 'is δ is small enough' should be 'if δ is small enough', and 'Denonimator' should be 'denominator'.
Circularity Check
No circularity: the lower bound is derived from explicit dual-function estimates; self-citations are contextual only.
full rationale
The derivation is self-contained. The central lower bound is obtained from the Lemma, whose proof starts from the negation of inequality (2) and derives inequality (3) through explicit estimates of I1, I2, and I3 using the Haar expansion, duality, orthogonality of the constructed functions Z_{k,j}, and the bound I3^{1/q'} ≲ 2^{k1/q} ≤ n^γ. None of these steps assumes the target width bound or fits constants to the desired answer; the constants c1(q), c2(q), and δ are existential and depend only on q and the auxiliary parameters. The upper bound is attributed to Kulanin as an external result, and the author's own papers [Mal21, Mal24, MR25] appear only as context in the introduction, not as load-bearing ingredients in the proof. The only gap noted by a careful reader, the unstated measurable selection of the family η_t, is a standard fillable technicality rather than a definitional equivalence, and it does not make any claim reduce to its own input. No self-citation chain, renamed known result, or fitted-input-as-prediction pattern is present.
Assumptions & free parameters
assumptions (4)
- standard math Marcinkiewicz-Paley theorem: for 1<q<∞, the L_q norm of f is equivalent to the L_q norm of the dyadic square function, and in particular ||f||_q is at least a constant times the weighted ell_q norm of its Haar coefficients.
- domain assumption Kulanin's upper bound: d_n(W_1^1, L_q) is O(n^{-1/2} log n).
- domain assumption Existence of a measurable family eta_t in Q_n with sup_t ||chi_t - eta_t||_{L_q} below the claimed threshold, given that the width is below that threshold.
- standard math The Haar system {h_{k,j}} is an orthonormal basis of L_2 with the stated dyadic properties.
Cite this review
Pith. "Pith review of Kolmogorov widths of the class $W_1^1$." pith.science (2026). https://pith.science/paper/IKQG2SUH
@misc{pith2026250206716,
author = {Pith},
title = {Pith review of: Kolmogorov widths of the class $W_1^1$},
year = {2026},
howpublished = {\url{https://pith.science/paper/IKQG2SUH}},
note = {Machine review of arXiv:2502.06716}
}
abstract
We prove that $d_n(W^1_1,L_q)\asymp n^{-1/2}\log n$, $2<q<\infty$. This completes the study of orders of decay of Kolmogorov widths for the classical case of the univariate Sobolev classes of integer smoothness.
Reference graph
Works this paper leans on
-
[1]
E.S. Belinskii, ``Approximation of periodic functions by a ‘floating’ system of exponentials, and trigonometric widths'' (in Russian), Studies on the Theory of Functions of Many Real Variables, (1984), 10--24
work page 1984
-
[2]
Gluskin, ``On some finite-dimensional problems of the theory of widths'' (in Russian), Vestn
E.D. Gluskin, ``On some finite-dimensional problems of the theory of widths'' (in Russian), Vestn. Leningrad. Univ., 13 (1981), 5--10
work page 1981
-
[3]
Kashin, ``Diameters of some finite-dimensional sets and classes of smooth functions'', Math
B.S. Kashin, ``Diameters of some finite-dimensional sets and classes of smooth functions'', Math. USSR-Izv., 11:2 (1977), 317--333
work page 1977
-
[4]
B.S. Kashin, Yu.V. Malykhin, K.S. Ryutin, ``Kolmogorov Width and Approximate Rank'', Proc. Steklov Inst. Math., 303 (2018), 140--153
work page 2018
-
[5]
Kolmogorov, ``On the best approximation of functions of a given class'', Selected Works of A.N
A.N. Kolmogorov, ``On the best approximation of functions of a given class'', Selected Works of A.N. Kolmogorov. Volume 1. Mathematics and Mechanics. Translated from: Ueber die beste Ann\"aherung von Funktionen einer gegebenen Funktionen-klasse. --- Ann.Math., 1936, vol.37, p.107--110
work page 1936
-
[6]
E.D. Kulanin, ``On the diameters of a class of functions of bounded variation in the space L_q(0,1) , 2<q< '', Russian Mathematical Surveys, 38:5 (1983), 146--147
work page 1983
-
[7]
G.G. Lorentz, M. Golitschek, Y. Makovoz, Constructive approximation: Advanced problems. Berlin: Springer, 1996
work page 1996
-
[8]
Malykhin, ``Kolmogorov Widths of the Besov Classes B^1_ 1, and Products of Octahedra'', Proc
Yu.V. Malykhin, ``Kolmogorov Widths of the Besov Classes B^1_ 1, and Products of Octahedra'', Proc. Steklov Inst. Math., 312 (2021), 215--225
work page 2021
Show all 10 references
-
[9]
Malykhin, ``Widths and rigidity'', Sb
Yu.V. Malykhin, ``Widths and rigidity'', Sb. Math., 215:4 (2024), 543--571
2024
-
[10]
Malykhin, K.S
Yu.V. Malykhin, K.S. Ryutin, ``Widths and rigidity of unconditional sets and random vectors'', Izv.RAN, in press
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.