{"id":"arxiv/2607.10501","url":"https://arxiv.org/abs/2607.10501","tags":["cs.DS","math.CA","math.NA"],"score":0,"title":"Optimal Extrapolation Bounds for Sparse Fourier Sums","domain":"cs.DS","source":"arxiv","authors":["Ruizhe Zhang"],"reviews":0,"subject":"cs.DS","summary":"We prove a sharp extrapolation bound for $k$-sparse Fourier sums with arbitrary real frequencies and no separation assumption. For every $g(t)=\\sum_{j=1}^k v_je^{iλ_jt}$ with $λ_j\\in\\mathbb{R}$ and every $x\\geq 1$, \\begin{align*} |g(x)|\\le k\\exp(O(k\\operatorname{arcosh} x))\\|g\\|_{L^2[-1,1]}. \\end{align*} Near the endpoint at $x=1+δ$, this gives an exponential factor of $\\exp(O(k\\sqrtδ))$, improving on the $\\exp(O(k^2\\log k\\cdotδ))$ estimate of Chen and Price (ICALP 2019), and the exponent is optimal up to a constant factor. Our theorem has algorithmic applications to recovering gapless…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-11","reactions":{}}