Complexity of oscillatory integrals on the real line (Q2363514)

The authors study optimal algorithms for oscillatory integrals of the form \[ I_k^{\rho}(f)=\int_{\mathbb{R}}f(x)e^{-ikx}\rho(x)\,dx, \quad f\in H^s({\mathbb{R}}), \] with smooth density functions \(\rho\) such as the norm one. The main result is that for the real line and the Sobolev space \(H^s({\mathbb{R}})\), sharp error bounds for algorithms that use \(n\) function values are roughly the same as for the interval \([0,1]\) and the periodic space \(H^s{[0,1]}\). More precisely, they are of order \(n + \max(1, |k|)^{-s}\).