{"id":"1185201c-0725-4f1f-ab58-8234601ab96b","arxiv_id":"1908.05943","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Lipschitz and Sobolev functions on bounded Jordan domains, the asymptotic error constant for optimal approximation and integration depends only on the domain's volume, and explicit uniform bounds nearly match it.","lead":"This paper shows that for smooth-enough functions on oddly shaped domains, the best possible approximation or integration error depends mainly on the domain's volume, not its shape. It also gives explicit error bounds that hold for every number of sample points, useful for deciding how many function evaluations are needed in high-dimensional numerical problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the volume-only asymptotic constant is plausible under Jordan measurability, and the only concrete gap is in a non-central upper-bound proof.","rationale":"The reader identified Jordan measurability as the weakest assumption, and I agree that it is the least secure hypothesis in the paper. I therefore tested whether arbitrary bounded Jordan measurable sets with an interior point could violate the volume-only asymptotic constant. The natural threats are sets with many tiny, well-separated components or with measure-zero fractal boundaries; in both cases, Jordan measurability forces the set to be essentially as large as its closure, so the missing volume of any such pathology has zero measure and its covering contribution is o(ε^{-d}). Consequently, the classical Hlawka/Kolmogorov-Tikhomirov asymptotics, which the paper cites rather than proves, appear to extend to the stated domain class. I also reviewed the new elementary bounds. The lower bound (6) and the sharpness construction are correct. The upper bound (7) has a proof gap because a complete packing of exactly n disjoint balls need not exist for the selected radius on an elongated domain, but the bound is not used in the central asymptotic claim and can be repaired with a standard grid argument; it does not justify changing the verdict. The integration bounds in Theorem 2 are plausible and are explicitly attributed to Chernaya and Gruber; no internal inconsistency emerged. Overall, this is a careful survey with correct elementary additions, and I found no reason to doubt the reader's ACCEPT verdict.","tokens_in":10980,"tokens_out":58833,"duration_ms":647056,"concrete_test":"Check the original hypotheses in Hlawka (1949) and Kolmogorov-Tikhomirov (1959) for the covering-number asymptotics of bounded Jordan measurable sets; as a computational cross-check, compute n-th covering radii for a bounded Jordan measurable domain with a measure-zero fractal boundary (e.g., a Koch-snowflake interior) in d=2 and compare ε_n^d n against λ(D)/(Θ_B λ(B)); if the ratio converges to a different constant, Theorem 1 (5) requires qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing flaw in the central claim. The weakest point is the reliance on classical covering asymptotics (Hlawka 1949; Kolmogorov-Tikhomirov 1959) for arbitrary bounded Jordan measurable sets with interior point; if those sources only cover convex or Lipschitz domains, Theorem 1 (5) would be overbroad. My scrutiny of feasible pathologies (e.g., fat Cantor dusts, separated small components) indicates that Jordan measurability plus the interior-point condition forces the boundary term to be o(ε^{-d}) and the packing-number bound to match the volume asymptotics, so the volume-only constant is credible. A separate, minor gap appears in the proof of the uniform upper bound (7): it invokes a complete packing of n disjoint ε-balls, but for domains such as long thin rectangles the volume-selected radius may not admit n disjoint balls, so that particular packing argument is not valid for every n. This does not affect the central Theorem 1 statement, and the bound itself is likely true by a grid construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies worst-case errors and complexity for approximation and integration of Lipschitz (and more general) functions on bounded subsets D_d of R^d using n function values. Its central claim is that for L-infinity approximation of Lipschitz functions, the optimal error is asymptotically Θ_B^{1/d} (λ_d(D_d)/λ_d(B))^{1/d} n^{-1/d} for every bounded Jordan measurable set with an interior point, so the asymptotic constant depends on the domain only through its volume; Theorem 1 states this and adds an explicit uniform lower bound (6). Theorem 2 states an analogous asymptotic formula for integration with constant ξ_B, together with a uniform lower bound (11) and an upper bound on ξ_B. The paper also surveys higher-smoothness results and Sobolev approximations under general linear information, mainly following Mieth, and lists open problems. The advertised new contributions are the explicit uniform bounds (6), (7), and (11) and the comparison constant for ξ_B; the asymptotic formulas are attributed to Hlawka, Kolmogorov-Tikhomirov, Sukharev, Chernaya, Gruber, and Mieth.","tokens_in":11181,"tokens_out":21741,"duration_ms":219090,"significance":"If the uniform-bound proofs are made fully rigorous, this is a useful contribution: it gives elementary volume-based lower bounds valid for all n and all bounded Jordan measurable domains, records the volume-only dependence of asymptotic constants, and collects recent results in a unified framework. The lower-bound arguments for (6) and the lower half of (11) are clean and correct, and the explicit bounds are relevant for tractability and for practical finite-n error estimates. The main asymptotic theorems are independently established and are not in question. However, two advertised upper-bound claims rest on proofs that are incomplete or incorrect, so the paper needs revision before the new results can be relied upon.","major_comments":[{"comment":"The proof of the uniform upper bound (7) assumes that for arbitrary n one can choose ε and points x_1,...,x_n such that n disjoint balls B_ε(x_i) form a complete packing of D_d and n·λ_d(B_ε) ≤ λ_d(D_d). The volume constraint does not by itself guarantee the existence of such a packing with exactly n balls: for a long thin rectangle, the value ε=(λ_d(D_d)/(nλ_d(B)))^{1/d} can exceed the width of the rectangle, so no n disjoint balls of radius ε exist. A maximal packing may have fewer than n balls, and adding arbitrary points destroys the radius bound. The inequality (7) may well be true by a different grid or volume argument, but the present proof is incomplete and should be repaired.","section":"Remark 1, proof of (7)"},{"comment":"The displayed inequality r(N_n, INT) ≤ (d/(d+1)) r(N_n, APP∞) for a fixed information mapping is false for general bounded Jordan measurable domains. For a counterexample, take B as the ℓ∞-unit ball in R^2, α>1, and D_α={0<x<1, 0<y<x^α}; choose the single sample point x_1=(δ, δ^α/2) with δ>0 small. The function ρ(x)=‖x−x_1‖∞ is admissible for F_B(D_α), vanishes at x_1, and satisfies sup ρ → 1 while (∫_{D_α} ρ dλ)/λ(D_α) → 1 as δ→0 and α→∞. Thus the ratio exceeds d/(d+1)=2/3 for large α, contradicting the claimed inequality. Since the upper bound on ξ_B is advertised as a new contribution and is used in Theorem 2, the proof must be replaced or the claim qualified to a class of domains for which the inequality holds.","section":"Theorem 2, proof of upper bound on xi_B"}],"minor_comments":[{"comment":"The abstract advertises 'bounded Lipschitz domains,' while Theorems 1 and 2 assume bounded Jordan measurable sets with an interior point; the scope of the results should be stated consistently in the introduction and abstract.","section":"Abstract and Theorems 1–2"},{"comment":"The phrase 'Similarly' skips the volume-level-set argument needed to obtain the constant d/(d+1) in the lower bound for arbitrary point sets; spelling out the integration of the distance function over level sets would make the proof self-contained.","section":"Theorem 2, proof of the lower bound (11)"},{"comment":"The displayed formula has mismatched parentheses: it reads 'en(F 2(Dd)), APP∞, Λ std)' and should read e_n(F_2(D_d), APP∞, Λ^std) or similar.","section":"Remark 4"},{"comment":"The paper states that the asymptotic formula (5) follows from Hlawka and Kolmogorov-Tikhomirov; since those classical results are often formulated for convex or more regular sets, a precise statement of the covering-number theorem used, including its validity for arbitrary bounded Jordan measurable sets with interior point, would strengthen the exposition.","section":"Theorem 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The asymptotic portions of the paper rest on established work and are reliable. The two proof gaps concern the new uniform upper bounds and the comparison constant for ξ_B; both are likely repairable with standard volume or grid arguments, so I do not recommend rejection. The author should be asked to provide complete proofs for (7) and for the upper bound on ξ_B, or to state the results under additional hypotheses under which the proofs are valid."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a solid survey of what is known about asymptotic constants and explicit uniform bounds for sampling-based approximation and integration on general domains. The central claim—that for Lipschitz functions and for Hilbert Sobolev embeddings the asymptotic constant depends on the domain only through its volume—is credible and backed by precise citations. The genuinely new items are the explicit uniform lower bounds (6) and (11), the near-optimal uniform upper bound (7), and the bound on ξ_B. They are elementary, short, and essentially correct.\n\nThe paper earns credit for being candid about what is new versus what is collected from Hlawka, Kolmogorov–Tikhomirov, Sukharev, Chernaya, and Mieth. Open problems are labeled as such. That honesty is appreciated.\n\nThe soft spot is the proof of the uniform upper bound (7) in Remark 1. The argument assumes that for a given n you can take ε with n λ(B_ε) = λ(D_d) and then find n disjoint ε-balls inside D_d forming a complete packing. That does not work for every domain and every n: a long thin rectangle with ε larger than its width contains no ball of radius ε at all. So the proof as written is invalid for those cases. The bound itself is likely true—a grid construction gives the same rate with a slightly worse constant—but the proof needs a different argument. This does not affect Theorem 1 or the asymptotic results, which rest on the classical covering asymptotics and are fine.\n\nThe reliance on covering-number asymptotics for bounded Jordan measurable sets is appropriate; the interior-point condition handles the boundary layer. I don't see a hidden assumption there.\n\nWho should read this? People in information-based complexity who want a compact, reliable statement of volume-only constants and the state of the art for explicit bounds. It's not a landmark, but it's useful and checkable.\n\nRecommendation: send it to peer review, and ask the author to fix the packing argument in (7). Everything else is in good shape.","headline":"Solid survey with a few new uniform bounds; central volume-only asymptotics hold, but the proof of (7) has a packing gap that needs fixing.","tokens_in":11694,"tokens_out":8504,"would_cite":true,"duration_ms":82058,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65Y20","41A46","65D30"],"pacs":[],"model":"deepseek-v4-flash","headline":"For Lipschitz approximation, numerical integration, and Sobolev L2-approximation on arbitrary bounded domains, the optimal worst-case error depends on the domain only through its volume, and explicit bounds hold for every n.","keywords":["information-based complexity","optimal recovery","covering numbers","asymptotic constant","Lipschitz functions","Sobolev embeddings","curse of dimensionality","Jordan measurable domains"],"falsifier":"For a fixed volume, compare the optimal $L_\\infty$ error at large $n$ on two bounded Jordan measurable domains of equal volume whose boundaries have very different roughness—for instance, a Euclidean ball and a domain of the same volume with a highly oscillatory boundary of measure zero. If the ratio of their errors does not tend to 1 as $n$ grows, Theorem 1's volume-only constant is false. A sharper numerical check: compute the finite-$n$ error on a domain consisting of $n+1$ equal balls versus a single connected domain of the same total volume; the paper's uniform lower bound is attained by the disjoint balls, so a connected domain with strictly smaller error at the same $n$ would reveal finite-$n$ shape dependence, though not a contradiction of the asymptotic statement.","tokens_in":10773,"feed_emoji":"📐","tokens_out":13356,"duration_ms":113673,"temperature":0.7,"pith_summary":"This paper asks whether the optimal worst-case error for approximating or integrating functions can be understood for arbitrary bounded domains, not just cubes, tori, or spheres. It establishes that for Lipschitz functions in the uniform norm, for numerical integration of the same class, and for $L_2$-approximation of Sobolev functions with arbitrary linear information, the asymptotic constant of the optimal error depends on the domain only through its $d$-dimensional volume—provided the domain is Jordan measurable with an interior point, meaning its boundary carries no volume. Shape and boundary values drop out of the leading term, leaving a constant fixed by the volume and the norm's unit ball. The paper also proves explicit bounds valid for every $n$ and every normalized domain, with uniform lower bounds that are sharp, and shows these finite-$n$ bounds sit close to the asymptotic constants. The upshot is that domain geometry is asymptotically irrelevant for several benchmark problems and that dimension-dependent lower bounds such as the curse of dimensionality can be proven for general domains.","feed_headline":"Domain shape drops out of optimal error asymptotics","feed_subtitle":"For Lipschitz, integration, and Sobolev problems, volume alone sets the leading error constant, even for finite n.","key_machinery":"The carrying object is the covering radius of the domain with respect to the norm's unit ball. Proposition 1 identifies the optimal $L_\\infty$ error with the modulus of continuity of the covering radius, $e_n = \\omega(c_n)$, so covering-number asymptotics translate directly into error asymptotics; classical results on covering $\\mathbb{R}^d$, together with the bound $1 \\leq \\Theta_B \\leq d \\log d + d \\log \\log d + 5d$, supply the volume-normalized constant. For integration, a comparison of the integration radius with the $L_\\infty$ radius of the same $n$-point information mapping contributes the factor $d/(d+1)$. For Sobolev spaces with arbitrary linear information, the machinery switches to eigenvalue asymptotics of the Dirichlet and Neumann Laplacians: the approximation numbers of the Sobolev embedding are governed by the same Weyl term that makes eigenvalue counts depend on volume alone, and eigenvalue bounds make the finite-$n$ estimates explicit. The uniform lower bounds throughout come from a volume estimate: $n$ balls of radius $\\varepsilon$ used to cover a domain have total volume at most $n$ times the volume of one ball, and a domain consisting of $n$ disjoint equal balls attains equality.","core_discovery":"The central discovery is a set of theorems with a common message. Theorem 1 states that for a bounded Jordan measurable set $D_d \\subset \\mathbb{R}^d$ with an interior point, the optimal $L_\\infty$ error for functions with $|f(x)-f(y)| \\leq \\|x-y\\|_B$ satisfies $e_n \\approx \\Theta_B^{1/d} (\\lambda_d(D_d)/\\lambda_d(B))^{1/d} n^{-1/d}$, where $\\Theta_B$ is the covering constant of $\\mathbb{R}^d$ with respect to the unit ball $B$ and $1 \\leq \\Theta_B \\leq d \\log d + d \\log \\log d + 5d$. It also states the uniform lower bound $\\inf_{D_d} e_n \\lambda_d(D_d)^{-1/d} = \\lambda_d(B)^{-1/d} n^{-1/d}$, sharp for a domain made of $n$ equal balls. Theorem 2 gives the integration analogue, with constant $\\xi_B$ between $d/(d+1)$ and $\\frac{d}{d+1} \\Theta_B^{1/d}$ and a sharp uniform lower bound of the same volume-only type. Theorem 4 extends volume-only asymptotics to $L_2$-approximation in Sobolev spaces: the limit of $e_n n^{r/d} \\lambda(D_d)^{-r/d}$ exists, equals $C_{r,d}$, and is the same for $H^r(D_d)$ and the zero-boundary subspace $H^r_0(D_d)$. The paper adds explicit finite-$n$ bounds that are only slightly weaker than the conjectured uniform versions.","pith_inferences":["Editorial: If volume-only asymptotics hold for all Jordan measurable domains, the extremal domain for the lower bounds—a disjoint union of $n$ equal balls—can serve as a worst-case test set: an algorithm that performs well there should perform at least as well on any domain of the same volume, at least in the leading term.","Editorial: The same reasoning suggests a testable extension to domains that are not Jordan measurable: if a boundary has positive $d$-dimensional measure, or its thin-neighborhood volume does not vanish as the neighborhood width shrinks, the inner-strip volume is not negligible and error constants should acquire shape dependence; measuring this would isolate exactly where the Jordan assumption bit","Editorial: Because $\\Theta_B^{1/d}$ tends to 1 as $d$ grows, the volume-only constant is nearly norm-independent in high dimension; one could probe whether the explicit finite-$n$ bounds also converge to a common limit, making the small-$n$ behavior more universal than the asymptotics alone suggest.","Editorial: The open conjecture for $C^2$ classes could be tested numerically on non-cube domains: if a domain with a long thin tentacle admits a fooling function with smaller error than the conjectured $n^{-2/d}$ bound, the volume-only principle would fail for that class; if not, the bound likely holds for all bounded open sets."],"forward_implications":["For Lipschitz and Hölder classes on any bounded Jordan measurable domain of volume $V$, asymptotically optimal sampling points need no detailed knowledge of shape: the leading error is set by $V^{1/d} n^{-1/d}$, and shape or boundary values affect only lower-order terms.","When the volume is normalized to that of the unit ball, optimal sample points beat a regular grid by a factor of about 2 in the leading constant for the Euclidean norm; equivalently, reaching a target error with a grid costs more than $2^d$ times as many function evaluations as optimal points.","The explicit uniform lower bounds imply the curse of dimension on general normalized domains: for Lipschitz classes scaled by $d^{-1/p}$, reaching error $\\varepsilon$ costs at least $(c_p/\\varepsilon)^d$ function evaluations, whether for approximation or integration.","For Sobolev $H^r$ $L_2$-approximation with arbitrary linear information, the asymptotic constant is independent of both domain shape and Dirichlet/Neumann boundary conditions, so spectral asymptotics transfer directly to information-based complexity.","The finite-$n$ bounds, which for the boundary-vanishing $L_\\infty$ case are within a factor 2 of the asymptotic constant, make these estimates usable in the small-$n$ regime where asymptotic formulas alone do not apply."],"supporting_citations":[{"why":"Supplies the classical covering-number asymptotics for Euclidean space used to obtain the asymptotic constant in Theorem 1.","marker":"[19]"},{"why":"Independent classical derivation of the same covering asymptotics, the quantitative backbone of the volume-normalized constant.","marker":"[20]"},{"why":"Gives the explicit upper bound on the covering constant used to sandwich the asymptotic constant.","marker":"[35]"},{"why":"Provides the identity linking covering numbers to optimal worst-case uniform error.","marker":"[38]"},{"why":"Supplies the asymptotic formula for weighted cubature and integration errors used in Theorem 2.","marker":"[6]"},{"why":"Establishes sharp estimates for Sobolev approximation numbers on general domains, the core of Theorem 4.","marker":"[27]"},{"why":"Gives the Neumann eigenvalue upper bound used for explicit finite-n upper estimates in the Sobolev case.","marker":"[23]"},{"why":"Gives the eigenvalue lower bound used for explicit uniform lower estimates in the Sobolev case.","marker":"[26]"},{"why":"Extends Weyl spectral asymptotics to non-smooth elliptic problems, supporting the volume-only asymptotic constant.","marker":"[3]"}],"fun_headline_variants":["Volume alone fixes optimal error constant on any Lipschitz domain","Shape-independent asymptotic error constants for integration and Sobolev","Domain shape never changes the leading order error constant","For Lipschitz domains, volume alone sets leading error constant","Volume-only leading error constants for all bounded Lipschitz domains"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The volume-only constants and the explicit uniform bounds rest on assuming the domain is Jordan measurable with an interior point, so that the volume of the inner strip near the boundary is negligible; on domains with fractal or otherwise badly behaved boundaries, the asymptotic constants may depend on shape and the uniform bounds can fail.","fun_headline_variants_meta":{"raw":{"variants":["Volume alone fixes optimal error constant on any Lipschitz domain","Shape-independent asymptotic error constants for integration and Sobolev","Domain shape never changes the leading order error constant","For Lipschitz domains, volume alone sets leading error constant","Volume-only leading error constants for all bounded Lipschitz domains"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001017,"raw_usage":{"total_tokens":4371,"prompt_tokens":1103,"completion_tokens":3268,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":719,"completion_tokens_details":{"reasoning_tokens":3186}},"tokens_in":719,"tokens_out":3268,"duration_ms":21656,"temperature":1.0,"reasoning_tokens":3186,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:59:10.375929+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed volume, compare the optimal $L_\\infty$ error at large $n$ on two bounded Jordan measurable domains of equal volume whose boundaries have very different roughness—for instance, a Euclidean ball and a domain of the same volume with a highly oscillatory boundary of measure zero. If the ratio of their errors does not tend to 1 as $n$ grows, Theorem 1's volume-only constant is false. A sharper numerical check: compute the finite-$n$ error on a domain consisting of $n+1$ equal balls versus a single connected domain of the same total volume; the paper's uniform lower bound is attained by the disjoint balls, so a connected domain with strictly smaller error at the same $n$ would reveal finite-$n$ shape dependence, though not a contradiction of the asymptotic statement.","supporting_citations":[{"cited_title":"Hlawka, Ausf¨ ullung und ¨Uberdeckung konvexer K¨ orper durch konvexe K¨ orper, Monatsh","cited_arxiv_id":null,"evidence_quote":"Supplies the classical covering-number asymptotics for Euclidean space used to obtain the asymptotic constant in Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Independent classical derivation of the same covering asymptotics, the quantitative backbone of the volume-normalized constant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the explicit upper bound on the covering constant used to sandwich the asymptotic constant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the identity linking covering numbers to optimal worst-case uniform error."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the asymptotic formula for weighted cubature and integration errors used in Theorem 2."},{"cited_title":"Mieth, Sharp estimates for approximation numbers of non-p eriodic Sobolev embeddings, J","cited_arxiv_id":null,"evidence_quote":"Establishes sharp estimates for Sobolev approximation numbers on general domains, the core of Theorem 4."},{"cited_title":"Kr¨ oger, Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space, J","cited_arxiv_id":null,"evidence_quote":"Gives the Neumann eigenvalue upper bound used for explicit finite-n upper estimates in the Sobolev case."},{"cited_title":"Li and S.-T","cited_arxiv_id":null,"evidence_quote":"Gives the eigenvalue lower bound used for explicit uniform lower estimates in the Sobolev case."},{"cited_title":"non-smooth","cited_arxiv_id":null,"evidence_quote":"Extends Weyl spectral asymptotics to non-smooth elliptic problems, supporting the volume-only asymptotic constant."}],"review_version":1}