Skip to content
DraconiticResearch
Search Sources API
178,033 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

Erdős's Robust Polynomial Interpolation Problem: the Optimal Exponential Scale

  • Jia-Qi Yang
Open at sourcePDFDOICite

Abstract

We determine the optimal exponential scale in Erdős's robust polynomial interpolation problem and identify the leading exponential coefficient for Chebyshev--Lobatto grids. Given C>0 and 0≤ρ<1, put H=C/(1−ρ). We prove that every configuration of n≥ n0 nodes in [−1,1] admits sign data for which every polynomial of degree at most (1+ε)n and uniform norm at most C has error greater than ρ at more than εn nodes. One may choose ε≥ e−A(1+H) and n0≤ eA(1+H), where A is an absolute constant, and a matching upper bound shows that the exponential order is optimal. For the same obstruction restricted to Chebyshev--Lobatto grids, the optimal parameter εCh(C,ρ) satisfies log(1/εCh(C,ρ))=π/2H+O(log(H+1)) as H→∞. The proofs combine finite interpolation estimates in Bernstein spaces with periodic sign constructions and averaging. We also establish obstructions for random signs and stability under angular perturbations of the nodes.

Related

  1. Optimal bound for the polynomial Littlewood-Offord problem
    Alexandr Grebennikov
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  2. Adaptive Adams-Type Methods Based on Algebraic, Trigonometric, and Exponential Interpolation
    Pavlina Atanasova, Valentin Georgiev, Elis Dieva +1
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  3. Besov and Triebel-Lizorkin Spaces on Filtered Lie Groups with Polynomial Growth, II: Interpolation, Localization, Pointwise Multiplication
    Mattia Calzi
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. The double descent and Runge phenomena in overparametrized polynomial interpolation
    Jason Wein, Stephan Wojtowytsch
    arXivPreprintarXiv licenceFull textAnalysis & PDEsNumerical analysis & scientific computingarXiv
  5. On the exponential ergodicity of the McKean-Vlasov SDE depending on a polynomial interaction
    Mohamed, Alfaki Aboubacrine Assadek
    Stochastic Processes and their ApplicationsPeer-reviewedCC BY 4.0Full textAnalysis & PDEsProbabilityHAL

Cite

BibTeXRIS
BibTeX
@misc{yang2026erdőss,
  title = {{Erdős's Robust Polynomial Interpolation Problem: the Optimal Exponential Scale}},
  author = {Jia-Qi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.14769},
  eprint = {2609.14769},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14769},
}
RIS
TY  - UNPB
TI  - Erdős's Robust Polynomial Interpolation Problem: the Optimal Exponential Scale
AU  - Jia-Qi Yang
PY  - 2026
DA  - 2026/09/13
PB  - arXiv
DO  - 10.48550/arxiv.2609.14769
UR  - https://arxiv.org/abs/2609.14769
AB  - We determine the optimal exponential scale in Erdős's robust polynomial interpolation problem and identify the leading exponential coefficient for Chebyshev--Lobatto grids. Given C>0 and 0≤ρ<1, put H=C/(1−ρ). We prove that every configuration of n≥ n_0 nodes in [−1,1] admits sign data for which every polynomial of degree at most (1+ε)n and uniform norm at most C has error greater than ρ at more than εn nodes. One may choose ε≥ e^−A(1+H) and n_0≤ e^A(1+H), where A is an absolute constant, and a matching upper bound shows that the exponential order is optimal. For the same obstruction restricted to Chebyshev--Lobatto grids, the optimal parameter ε_Ch(C,ρ) satisfies log(1/ε_Ch(C,ρ))=π/2H+O(log(H+1)) as H→∞. The proofs combine finite interpolation estimates in Bernstein spaces with periodic sign constructions and averaging. We also establish obstructions for random signs and stability under angular perturbations of the nodes.
ER  -