/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 1152
References:
[EKS89] Erdős, P., Kroó, A. and Szabados, J., On convergent interpolatory polynomials. J. Approx. Theory 58 (1989), 232-241. PDF
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).
@[expose] public sectionopen Filter MeasureTheoryopen scoped Topology Polynomialnamespace Erdos1152For $n\geq 1$ fix some sequence of $n$ distinct numbers $x_{1n},\ldots,x_{nn}\in [-1,1]$. Let $\epsilon=\epsilon(n)\to 0$.
Does there always exist a continuous function $f:[-1,1]\to \mathbb{R}$ such that if $p_n$ is a sequence of polynomials, with degrees $\deg p_n<(1+\epsilon(n))n$, such that $p_n(x_{kn})=f(x_{kn})$ for all $1\leq k\leq n$, then $p_n(x)\not\to f(x)$ for almost all $x\in [-1,1]$?
This is Problem 2.42 in [Va99]. The $n$ nodes of the $n$-th row form the finite set nodes n.
We take $\epsilon(n)>0$. A smaller $\epsilon$ only shrinks the class of $p_n$, so this is
equivalent to allowing any real $\epsilon(n)\to 0$. We impose the degree bound only for
$n\geq 1$, since for $n=0$ the bound natDegree < 0 can never hold. We read
"$p_n(x)\not\to f(x)$ for almost all $x$" as: for almost every $x$, the sequence $p_n(x)$ does
not converge to $f(x)$.
For $\deg p_n<n$ the interpolating polynomial is unique (the Lagrange polynomial). Erdős, Kroó and Szabados [EKS89, pp. 232-233] give necessary and sufficient conditions on the nodes under which, for every continuous $f$ and every fixed $\epsilon>0$, there are interpolating polynomials of degree at most $\lfloor n(1+\epsilon)\rfloor$ approximating $f$ at the rate of the best uniform approximation (in particular converging uniformly to $f$).
@[category research open, question, AMS 41]
theorem erdos_1152 :
∀ nodes : ℕ → Finset ℝ, (∀ n, (nodes n).card = n) →
(∀ n, ∀ x ∈ nodes n, x ∈ Set.Icc (-1 : ℝ) 1) →
∀ ε : ℕ → ℝ, (∀ n, 0 < ε n) → Tendsto ε atTop (𝓝 0) →
∃ f : ℝ → ℝ, ContinuousOn f (Set.Icc (-1 : ℝ) 1) ∧
∀ p : ℕ → ℝ[X],
(∀ n : ℕ, 1 ≤ n → ((p n).natDegree : ℝ) < (1 + ε n) * n) →
(∀ n, ∀ x ∈ nodes n, (p n).eval x = f x) →
∀ᵐ t ∂(volume.restrict (Set.Icc (-1 : ℝ) 1)),
¬ Tendsto (fun n => (p n).eval t) atTop (𝓝 (f t)) := ⊢ ∀ (nodes : ℕ → Finset ℝ),
(∀ (n : ℕ), (nodes n).card = n) →
(∀ (n : ℕ), ∀ x ∈ nodes n, x ∈ Set.Icc (-1) 1) →
∀ (ε : ℕ → ℝ),
(∀ (n : ℕ), 0 < ε n) →
Tendsto ε atTop (𝓝 0) →
∃ f,
ContinuousOn f (Set.Icc (-1) 1) ∧
∀ (p : ℕ → ℝ[X]),
(∀ (n : ℕ), 1 ≤ n → ↑(p n).natDegree < (1 + ε n) * ↑n) →
(∀ (n : ℕ), ∀ x ∈ nodes n, Polynomial.eval x (p n) = f x) →
∀ᵐ (t : ℝ) ∂volume.restrict (Set.Icc (-1) 1),
¬Tendsto (fun n ↦ Polynomial.eval t (p n)) atTop (𝓝 (f t))
All goals completed! 🐙end Erdos1152