We study integration on a 3d-dimensional trigonometric space whose unit ball has all coordinate mixed partial derivatives bounded by one. With evaluations anywhere in Rd, we determine the exact minimal worst-case error among all deterministic algorithms using at most n function values. An optimal quadrature formula is obtained by truncating an exact product quadrature formula on {1/2,1/2+π}d. All weights are positive. For each error tolerance 0<ε<1, the information complexity grows exponentially in d with the common base Λ≈1.10546546. The correction of order d to the logarithm of the information complexity and the corresponding error limit are determined by the standard normal distribution function. For b≥1 and n=⌈bd⌉, the error tends to one, one half, or zero according as b<Λ, b=Λ, or b>Λ.
Introduction and Main Results
We study worst-case integration on a finite-dimensional trigonometric class. The integral is taken over the unit cube, while function values may be taken either in the cube or anywhere in Rd.
For d∈N, define
Fd∞={f∈C∞([0,1]d;R):∥Dαf∥∞≤1 for every α∈N0d}.
The supremum norm on [0,1]d is denoted by ∥⋅∥∞, and D0f=f. The sets of positive and nonnegative integers are N={1,2,…} and N0={0,1,2,…}. All logarithms are natural, empty sums equal zero, and empty products equal one.
Woźniakowski [20] posed the tractability question for Fd∞. Wojtaszczyk [19] proved that the problem is not strongly polynomially tractable. Sengelen Sevim [14] proved the curse of dimensionality, with asymptotic exponential base approximately 1.10546546 in the lower bound for the information complexity. Matrix methods for quadrature in Hilbert spaces were developed in [2].
Here we show that the spectral lower bound from [14] is attained on the Veronese class when exterior nodes are allowed. We determine optimal quadrature formulas for every n and derive Gaussian asymptotics for their error and information complexity.
For σ∈{ext,□} and n∈N0, eVσ(n,d) denotes the minimal deterministic worst-case error among all algorithms based on at most n function values in Ddσ. Adaptive nodes, input-dependent stopping, and nonlinear return maps are included. Thus
eVσ(n,d)=Ainff∈BV,dsup∣Sd(f)−A(f)∣.
By Proposition 2.2, the initial errors satisfy
eVext(0,d)=eV□(0,d)=1.
For 0<ε<1, define
nVσ(ε,d)=min{n∈N0:eVσ(n,d)≤ε}.
The absolute and normalized error criteria coincide. Exponential growth of nVσ(ε,d) in d for a fixed ε∈(0,1) is called the curse of dimensionality.
Let Φ be the standard normal distribution function, and let Φ−1 denote the inverse function. For d∈N, arrange the numbers qd−kpk, with multiplicity (kd) for k=0,…,d, in decreasing order as
λ1(d)≥⋯≥λ2d(d)>0.
For n∈N0, define
τn,d={∑j=n+12dλj(d),0,0≤n<2d,n≥2d.
Theorem 1.1. Let d∈N and n∈N0. Then
eV(n,d)≥eVext(n,d)=τn,d.
For n≤2d, eVext(n,d) is attained by a nonadaptive quadrature formula with n nodes from {1/2,1/2+π}d. The weights are positive and equal to the n largest eigenvalues. For n≥2d, the complete grid attains zero error with 2d evaluations.
Theorem 1.2. Let s∈R, and let (nd)d≥1⊂N satisfy
dlognd−dH(p)⟶s.
Then
d→∞limeVext(nd,d)=1−Φ(Vs).(1)
For every fixed 0<ε<1,
d→∞limdlognVext(ε,d)−dH(p)=VΦ−1(1−ε).(2)
Consequently,
d→∞limnVext(ε,d)1/d=Λ.(3)
Remark 1.3 (Monte Carlo). For n∈N and independent uniform points Ξ1,…,Ξn in [0,1]d, put Qn,dMC(f)=n−1∑i=1nf(Ξi). Independence and ∣f∣≤1 give E∣Sd(f)−Qn,dMC(f)∣2=Var(f(Ξ1))/n≤1/n for f∈Fd∞. Thus
f∈Fd∞sup(E∣Sd(f)−Qn,dMC(f)∣2)1/2≤n−1/2.(4)
The same bound applies to BV,d.
Remark 1.4 (Optimal Quadrature Formulas by Deletion). The optimal exterior formulas are obtained from one exact product formula by retaining its largest weights. A related deletion property holds for the periodic trigonometric problem [8, 18]; see § 4.4.
Remark 1.5 (Approximation, Integration, and Widths). For Fd∞, let eapp(n,d) denote the minimal deterministic worst-case error for uniform approximation by algorithms based on at most n continuous linear functionals, selected adaptively, and an arbitrary return map. Novak and Woźniakowski [11], Theorem 1 proved
eapp(n,d)=1(0≤n<2⌊d/2⌋).
The corresponding integration question is resolved for Fd∞ by the exponential lower bound in [14].
For widths of smooth function classes and related numbers, see Kashin [5] and Pietsch [13]; for multivariate approximation and optimal sampling, see Temlyakov [17] and the survey of Krieg and Ullrich [6].
Novak [7 Proposition 3(c)] constructed an infinite-dimensional linear subspace E⊂C([0,1]) such that, for every continuous linear functional μ on C([0,1]), there are xμ∈[0,1] and aμ∈R with
μ(f)=aμf(xμ)(f∈E).
Thus every such functional can be computed exactly on E from one function value. On the whole space E, the Kolmogorov and Gelfand widths in the uniform norm are infinite for every finite index, and uniform approximation from finitely many function values has infinite worst-case error. Hence integration and uniform approximation can have a very different information complexity; see [12].
For an orthonormal eigenbasis v1,…,vN of B, we obtain tr(MB)=∑j=1NμjvjTMvj and ∣vjTMvj∣≤∥M∥op. Equality in (6) follows for the symmetric matrix determined by Mvj=vj when μj≥0 and Mvj=−vj when μj<0.
For N1,N2∈N, A∈SymN1, and B∈SymN2, every eigenvalue of A⊗B is a product of an eigenvalue of A and an eigenvalue of B. Consequently,
Since ∥z(x)∥=1, the matrix K(x) is a rank-one orthogonal projection. The entries span T1. For f(x)=c0+c1cos(x−21)+c2sin(x−21), the identity f(x)=tr(AfK(x)) determines a unique matrix
Af=(c0+c1c2c2c0−c1).(9)
The eigenvalues of Af are c0±c12+c22. Hence
∥f∥V,1=∥Af∥op=∣c0∣+c12+c22.(10)
The name Veronese refers to the quadratic map (u,v)↦(X,Y,Z)=(u2,uv,v2). For the entries u,v of z(x), the image coordinates satisfy X+Z=1 and Y2=XZ. Thus the quadratic image of z lies on a conic in the plane X+Z=1. The matrix estimates depend on the rank-one property of K(x).
The tensor definition gives
Kd(x)=j=1⨂dK(xj).
Thus Kd(x) is a rank-one orthogonal projection on R2d. Every entry of Kd is in Td. Conversely, tensor products of the matrices in (9) yield every basis tensor of Td, so Td(Sym2d)=Td. The functions 1,cos(x−21),sin(x−21) are linearly independent on [0,1]: the value and the derivatives of orders one and two at 1/2 determine all three coefficients. Tensor products therefore yield 3d linearly independent functions on [0,1]d.
The minimum in (5) is attained: a bounded minimizing sequence in the closed affine space {M∈Sym2d:TdM=f} has a convergent subsequence. Thus BVd={f∈Td:∥f∥V,d≤1}. For d≥2, the representing matrix is not unique. Indeed, dimSym4=10>9=dimT2, and tensoring a nonzero element of kerT2 with I2d−2 gives a nonzero element of kerTd. This explains the minimum in (5).
Linear independence of the tensor basis on the cube implies that its coefficients, and hence its extension to Rd, are uniquely determined. Thus exterior evaluation is well defined on the quotient space.
The univariate trace-norm identity on [0,1], the cube-node spectral lower bound, and the finite expression for τn,d are obtained in [14]. Lemma 2.1 yields the equality on R and the tensor identity.
Lemma 2.1. Let ℓ∈N0 and d∈N. For every x∈R,
K(ℓ)(x)∗=1.
Consequently, for every α∈N0d and x∈Rd,
∥DαKd(x)∥∗=1.(11)
Proof. For ℓ=0, the rank-one projection K(x) has eigenvalues one and zero. For ℓ≥1, differentiation of (8) yields
The supremum over x and α, followed by the infimum over M, yields (12). Since the derivative identity holds for every x∈Rd, we also obtain
x∈Rdsup∣Dαf(x)∣≤∥f∥V,d(α∈N0d).(13)
The identity matrix I2d satisfies TdI2d=1, since trKd(x)=1. Thus ±1∈BV,d, and ∣Sd(f)∣≤1 for every f∈BV,d. An algorithm with zero evaluations returns a constant a∈R, and max{∣1−a∣,∣−1−a∣}≥1. The constant approximation zero attains error one.
Spectral Lower Bound
The integration matrix and the spectrum are given in [14]. Integration of (8) yields
G=∫01K(x)dx=(q00p).
Coordinatewise integration yields
Gd=∫[0,1]dKd(x)dx=G⊗d,Sd(TdM)=tr(MGd).
The eigenvalues of Gd are λj(d), 1≤j≤2d, and tr(Gd)=(p+q)d=1. For a deterministic algorithm A and a class B, define
e(A,B)=f∈Bsup∣Sd(f)−A(f)∣.
Proposition 2.3. Let d∈N and n∈N0. Then
eVcube(n,d)≥eVext(n,d)≥τn,d.
Proof. Every cube-node algorithm is also an exterior-node algorithm, so the first inequality is immediate. For n≥2d, the second follows from τn,d=0. Let n<2d. Run an arbitrary deterministic algorithm A on the zero function. Let x1,…,xm, with m≤n, be the nodes it uses, and put a=A(0). Let Π be the orthogonal projection onto
W=span{zd(x1),…,zd(xm)},r=dimW≤n,
and set P=I2d−Π. Since ∥P∥op≤1, the functions ±fP belong to BVd, where
fP(x)=zd(x)TPzd(x)=∥Pzd(x)∥22.
They vanish at every xi. By induction over the evaluations, the inputs 0, fP, −fP produce the same observations, the same stopping decision and the same output a. Therefore
Let v1,…,v2d be an orthonormal eigenbasis of Gd, ordered by decreasing eigenvalues, and define bj=∥Πvj∥22. Then 0≤bj≤1 and ∑jbj=trΠ=r. For r≥1, we obtain
Taking the infimum over A proves the exterior lower bound.
Optimal Exterior Quadrature
For u=(u1,…,ud)∈{0,1}d, define
∣u∣=j=1∑duj,
xu=(1/2+πu1,…,1/2+πud),
λ(u)=qd−∣u∣p∣u∣.(14)
Let e1=(1,0)T and e2=(0,1)T. For the nodes in (14), the identities z(1/2)=e1 and z(1/2+π)=e2 imply zd(xu)=⨂j=1de1+uj. Hence the vectors zd(xu) are the standard orthonormal eigenbasis of Gd. With Pu=Kd(xu), the spectral decomposition becomes
Gd=u∈{0,1}d∑λ(u)Pu.
The trace pairing with a matrix satisfying TdM=f then yields a positive quadrature formula on Td.
Sd(f)=u∈{0,1}d∑λ(u)f(xu),f∈Td.(15)
For d∈N and 0≤n≤2d, let En,d⊆{0,1}d contain n elements satisfying
λ(u)≥λ(v)(u∈En,d,v∈{0,1}d∖En,d).
Define the quadrature formula
Qn,dext(f)=u∈En,d∑λ(u)f(xu),f∈Td.(16)
Proof of Theorem 1.1. Proposition 2.3 provides eV□(n,d)≥eVext(n,d)≥τn,d. For f∈BVd, choose M∈Sym2d with TdM=f and ∥M∥op≤1. Then, for x∈Rd,
∣f(x)∣≤∥M∥op∥zd(x)∥22≤1.
For 0≤n≤2d, equations (15) and (16) therefore yield
∣Sd(f)−Qn,dext(f)∣≤u∈/En,d∑λ(u)=τn,d.
The function f≡1∈BVd attains equality, so
e(Qn,dext,BVd)=eVext(n,d)=τn,d.
The nodes are nonadaptive and the weights are positive. For n=0, (16) equals zero. For n≥2d, the full quadrature formula in (15) has zero error and uses at most n evaluations.
Define the cumulative multiplicities and masses by
for r=0,…,d. For n∈{0,…,2d−1}, let r∈{0,…,d} satisfy Lr−1(d)≤n<Lr(d). Since q>p, the eigenvalue levels decrease strictly with k. We obtain
τn,d=(Lr(d)−n)qd−rpr+k=r+1∑d(kd)qd−kpk.
Corollary 2.4. Let d∈N, 0<ε<1, and r=min{j∈{0,…,d}:Bj(d)≥1−ε}. Then
nVext(ε,d)=Lr−1(d)+⌈qd−rpr1−ε−Br−1(d)⌉.(17)
Proof. By Theorem 1.1, retain all levels below r, giving Lr−1(d) nodes and total weight Br−1(d), and then retain the least integer number of weights qd−rpr needed to reach total weight 1−ε. This gives (17). Since Br−1(d)<1−ε≤Br(d), the ceiling lies between 1 and (rd).
Since q>p, optimal node selection follows increasing ∣u∣, with arbitrary selection among equal weights. The sum of the weights is 1−τn,d, and
Qn,dext(1)=1−τn,d<1(0≤n<2d).
Remark 2.5 (Trace-Norm Characterization). For Qn(f)=∑i=1naif(xi) with xi∈Rd and ai∈R, the definition of BVd and trace-norm duality give
e(Qn,BVd)=Gd−i=1∑naiKd(xi)∗.(18)
Indeed, the error is the maximum of tr(M[Gd−∑iaiKd(xi)]) over ∥M∥op≤1. This argument also covers noninjective Td.
Since BVd is convex and symmetric and Sd is a linear functional, it suffices to consider nonadaptive linear quadrature [1, 10]. Consequently,
The same identity holds for eVext(n,d) with nodes in Rd. For n=0, the empty sum gives ∥Gd∥∗=1. Formula (16) attains the exterior infimum for n≤2d; zero coefficients cover larger n.
so its omitted probability is at least P(Yd≥logn+a)−e−a.
Since Xd=∣U∣ is binomial with parameters d and p,
Yd=dH(p)+log(q/p)(Xd−dp).
The binomial central limit theorem gives
dVYd−dH(p)=dpqXd−dp⇒N(0,1).
Suppose that (lognd−dH(p))/d→s. Taking a=d1/4 in (19), both standardized thresholds converge to s/V, and e−a→0. Continuity of Φ yields (1).
Fix 0<ε<1 and δ>0. Define
sε=VΦ−1(1−ε),md±=⌈exp(dH(p)+(sε±δ)d)⌉.
Since H(p)>0, integer rounding changes the logarithms by o(1). Equation (1) gives
ed(md−)>ε>ed(md+)
for all sufficiently large d. Monotonicity yields md−<nVext(ε,d)≤md+. Taking logarithms, subtracting dH(p), dividing by d, and then letting δ↓0 gives (2). It follows that lognVext(ε,d)/d→H(p); exponentiation gives (3).
Corollary 3.1. Let c>0 and b≥1 be independent of d. Then
Proof. For s∈R, put νd(s)=⌈exp(dH(p)+sd)⌉. Since H(p)>0, rounding changes the logarithm by o(1), so Theorem 1.2 gives
d→∞limeVext(νd(s),d)=1−Φ(s/V).(20)
At b=Λ, Theorem 1.2 applies with s=0, because log⌈cΛd⌉=dH(p)+O(1). For 1≤b<Λ, the relation log⌈cbd⌉=dlogb+O(1) implies ⌈cbd⌉≤νd(s) eventually, for every fixed s. Monotonicity and (20) give a lower limit at least 1−Φ(s/V); letting s→−∞ gives one. For b>Λ, the comparison is reversed, so the upper limit is at most 1−Φ(s/V); letting s→+∞ gives zero. Here we use 0≤eVext(n,d)≤1.
Cube Evaluations and Further Comparisons
Cube Evaluations
Let eF∞□(n,d) and nF∞□(ε,d) be defined in the same way, with F∞ in place of BV,d and nodes in [0,1]d. The embedding in Proposition 2.2 and Dd□⊂Ddext give
Each basis tensor has V-norm one. The coefficient cν is obtained at (1/2,…,1/2) by applying in coordinate j the operator Id+∂j2, −∂j2, or ∂j according as νj=0,1,2. Hence
The values of f′ and f′′ at 1/2 give a,b≤1. Put c=cos(1/2) and t=sin(1/2). The endpoint values give
∣c0+cc1∣+tb=max{∣f(0)∣,∣f(1)∣}≤1.
Equation (10) therefore yields
∥f∥V,1≤1+ca−tb+a2+b2.
The function on the right, without the initial one, is convex on [0,1]2, so the maximum is attained at a vertex. The four values are 0, c+1, 1−t, and c−t+2. Since t≥21−6(1/2)3=4823>2−1, the maximum is c+1. Thus ∥f∥V,1≤2+c. The function f∗ gives equality in (22).
We know only a few cases where optimal quadrature formulas are known, in particular in the multivariate case, d>1.
Let Bdper be the unit ball of the d-fold Hilbert tensor product of the three-dimensional space in which 1,cos(2πx),sin(2πx) are declared orthonormal. Its minimal linear error satisfies
en(Bdper)2=max{1−n2−d,0}.
Novak [8] proved the lower bound for positive weights; Vybíral [18 Section 5] extended it to arbitrary real weights. For n≤2d, equality is attained by retaining any n nodes of {0,1/2}d, each with weight 2−d.
Thus both this periodic problem and the exterior Veronese problem admit an exact 2d-point product formula whose summands can be deleted without changing the remaining nodes or weights. In the periodic case any n summands may be retained; in the Veronese case the n largest weights must be retained, with arbitrary choices among ties. This deletion property does not hold if we only allow nodes inside the cube.
The Korobov-type class in [15] is defined by a weighted supremum bound on Fourier coefficients and has a different norm. The Veronese ball is instead the image of an operator-norm matrix ball; these norms define distinct integration problems.
For the Hölder class
Lα,d={f:[0,1]d→R:∣f(x)−f(y)∣≤∥x−y∥∞α for all x,y∈[0,1]d},
where 0<α≤1, the quantization identity [16] gives, for n≥1,
If n=md with m∈N, the centers of the md congruent subcubes and equal weights m−d are optimal, and
emd(Lα,d)=d+αd(2m)−α.
Optimal univariate quadrature on Sobolev classes with derivative bounds in Lρ can be characterized by minimal-norm monosplines. This was a very active research direction, see the excellent survey [21].
References
[1]N. S. Bakhvalov. On the optimality of linear methods for operator approximation in convex classes of functions. U.S.S.R. Comput. Math. Math. Phys. 11(4) (1971), 244–249. doi:10.1016/0041-5553(71)90017-6.DOI
[2]A. Hinrichs, D. Krieg, E. Novak and J. Vybíral. Lower bounds for the error of quadrature formulas for Hilbert spaces. J. Complexity 65 (2021), 101544. doi:10.1016/j.jco.2020.101544.DOI
[3]A. Hinrichs, E. Novak and M. Ullrich. On weak tractability of the Clenshaw–Curtis Smolyak algorithm. J. Approx. Theory 183 (2014), 31–44. doi:10.1016/j.jat.2014.03.012.DOI
[4]A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski. The curse of dimensionality for numerical integration of smooth functions II. J. Complexity 30 (2014), 117–143. doi:10.1016/j.jco.2013.10.007.DOI
[5]B. S. Kashin. Diameters of some finite-dimensional sets and classes of smooth functions. Math. USSR-Izv. 11(2) (1977), 317–333. doi:10.1070/IM1977v011n02ABEH001719.
[6]D. Krieg and M. Ullrich. Approximation of functions: Optimal sampling and complexity. Acta Numerica 35 (2026), 273–457. doi:10.1017/S0962492925100287.DOI
[7]E. Novak. Quadrature and widths. J. Approx. Theory 47(3) (1986), 195–202. doi:10.1016/0021-9045(86)90027-4.DOI
[8]E. Novak. Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials. J. Complexity 15 (1999), 299–316. doi:10.1006/jcom.1999.0507.DOI
[9]E. Novak and F. Pillichshammer. Intractability results for integration in tensor product spaces. J. Complexity 86 (2025), 101901. doi:10.1016/j.jco.2024.101901.DOI
[10]E. Novak and H. Woźniakowski. Tractability of Multivariate Problems. Volume I. Linear Information. EMS Tracts in Mathematics 6, European Mathematical Society, Zürich, 2008. doi:10.4171/026.
[11]E. Novak and H. Woźniakowski. Approximation of infinitely differentiable multivariate functions is intractable. J. Complexity 25 (2009), 398–404. doi:10.1016/j.jco.2008.11.002.DOI
[12]E. Novak and H. Woźniakowski. Tractability of Multivariate Problems. Volume II. Standard Information for Functionals. EMS Tracts in Mathematics 12, European Mathematical Society, Zürich, 2010. doi:10.4171/084.
[13]A. Pietsch. Eigenvalues and s-numbers. Cambridge Studies in Advanced Mathematics 13, Cambridge University Press, Cambridge, 1987.
[14]E. Sengelen Sevim. The curse of dimensionality for integration of infinitely differentiable functions. J. Complexity 97 (2026), 102074. doi:10.1016/j.jco.2026.102074.
[15]I. H. Sloan and H. Woźniakowski. An intractability result for multiple integration. Math. Comp. 66 (1997), 1119–1124. doi:10.1090/S0025-5718-97-00834-X.DOI
[16]A. G. Sukharev. Optimal numerical integration formulas for some classes of functions of several variables. Dokl. Akad. Nauk SSSR 246(2) (1979), 282–285. English transl.: Soviet Math. Dokl. 20 (1979), 472–475. https://www.mathnet.ru/eng/dan42697.
[17]V. Temlyakov. Multivariate Approximation. Cambridge Monographs on Applied and Computational Mathematics 32, Cambridge University Press, Cambridge, 2018. doi:10.1017/9781108689687.DOI
[18]J. Vybiral. A variant of Schur’s product theorem and its applications. Adv. Math. 368 (2020), 107140. doi:10.1016/j.aim.2020.107140.DOI
[19]J. O. Woitaszczyk. Multivariate integration in C∞([0,1]^d) is not strongly tractable. J. Complexity 19 (2003), 638–643. doi:10.1016/S0885-064X(03)00069-4.
[20]H. Woźniakowski. Open problems for tractability of multivariate integration. J. Complexity 19 (2003), 434–444. doi:10.1016/S0885-064X(03)00016-5.DOI
[21]A. A. Zhensykbaev. Monosplines of minimal norm and the best quadrature formulae. Russian Math. Surveys 36(4) (1981), 121–180. doi:10.1070/RM1981v036n04ABEH003024.DOI