/- 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 FormalConjecturesUtil public import FormalConjectures.ErdosProblems.«1129»

Erdős Problem 1130

References:

    erdosproblems.com/1130

    [dBPi78] de Boor, C. and Pinkus, A., Proof of the conjectures of Bernstein and Erdős concerning the optimal nodes for polynomial interpolation. J. Approx. Theory 24 (1978), 289-303.

    [Er47] Erdős, P., Some remarks on polynomials. Bull. Amer. Math. Soc. 53 (1947), 1169-1176. PDF

    [Er61c] Erdős, P., Problems and results on the theory of interpolation. II. Acta Math. Acad. Sci. Hungar. 12 (1961), 235-244. PDF

    [Er67] Erdős, P., Problems and results on the convergence and divergence properties of the Lagrange interpolation polynomials and some extremal problems. Mathematica (Cluj) (1967), 65-73. PDF

    [Ib16] Ibrahimoglu, B. A., Lebesgue functions and Lebesgue constants in polynomial interpolation. J. Inequal. Appl. (2016), Paper No. 93. DOI

    [Ki77] Kilgore, T. A., Optimization of the norm of the Lagrange interpolation operator. Bull. Amer. Math. Soc. 83 (1977), 1069-1071.

    [Ki78] Kilgore, T. A., A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm. J. Approx. Theory 24 (1978), 273-288.

The definitions (nodes, Lebesgue function, canonical node sets, equioscillation) are in FormalConjectures.ErdosProblems.«1129», the file of erdosproblems.com/1129.

@[expose] public sectionopen Erdos1129namespace Erdos1130

$\Upsilon(x)=\min_{0\le i\le n}\max_{t\in[x_i,x_{i+1}]}L_x(t)$ with $x_0=-1$ and $x_{n+1}=1$: the smallest of the $n+1$ local maxima gapMax x i, $0\le i\le n$. If $x_1=-1$ or $x_n=1$ then an outer gap is a single point, where the Lebesgue function is $1$, and $\Upsilon(x)=1$.

noncomputable def upsilon {n : ℕ} (x : Fin n → ℝ) : ℝ := ⨅ i : Fin (n + 1), gapMax x (i : ℕ)

The smallest of the $n-1$ local maxima $\lambda_1,\dots,\lambda_{n-1}$ of the Lebesgue function between consecutive nodes. For a canonical node set this is the smallest local maximum of the Lebesgue function (the quantity $m_n(X)$ of [Ib16, Section 2.1 (c)]). It is meaningful for $n\ge 2$.

noncomputable def minInteriorGapMax {n : ℕ} (x : Fin n → ℝ) : ℝ := ⨅ i : Fin (n - 1), gapMax x ((i : ℕ) + 1)

For $x_1,\ldots,x_n\in [-1,1]$ let $$l_k(x)=\frac{\prod_{i\neq k}(x-x_i)}{\prod_{i\neq k}(x_k-x_i)},$$ which are such that $l_k(x_k)=1$ and $l_k(x_i)=0$ for $i\neq k$.

Let $x_0=-1$ and $x_{n+1}=1$ and $$\Upsilon(x_1,\ldots,x_n)=\min_{0\leq i\leq n}\max_{x\in[x_i,x_{i+1}]} \sum_k \lvert l_k(x)\rvert.$$ Is it true that $$\Upsilon(x_1,\ldots,x_n)\ll \log n?$$

This is the first part, a question of Erdős [Er67, p. 66], who could prove only $\Upsilon<\sqrt n$ [Er47, Theorem 2]. We read $\ll$ as: there is an absolute constant $C$ with $\Upsilon(x_1,\ldots,x_n)\le C\log n$ for all $n\ge 2$ and all nodes $-1\le x_1<\cdots<x_n\le 1$. The answer is yes: $\Upsilon(x)$ is at most the minimal Lebesgue constant (erdos_1130.variants.erdos_inequality, from [Ki77], [Ki78] and [dBPi78]), and the Chebyshev nodes show that this is $<\frac2\pi\log n+O(1)$ [Er61c, p. 236].

@[category research solved, question, AMS 41] theorem erdos_1130.parts.i : ∃ C : ℝ, 0 < C ∧ ∀ (n : ℕ) (x : Fin n → ℝ), 2 ≤ n → IsNodeSet x → upsilon x ≤ C * Real.log n := ⊢ ∃ C, 0 < C ∧ ∀ (n : ℕ) (x : Fin n → ℝ), 2 ≤ n → IsNodeSet x → upsilon x ≤ C * Real.log ↑n All goals completed! 🐙

The set of all node sets that maximise $\Upsilon$. The cited sources describe the maximisers only among canonical node sets, with $\Upsilon$ replaced (erdos_1130.variants.canonical), so it is left as sorry.

def erdos_1130.parts.ii.answer (n : ℕ) : Set (Fin n → ℝ) := sorry

For $x_1,\ldots,x_n\in [-1,1]$ let $$l_k(x)=\frac{\prod_{i\neq k}(x-x_i)}{\prod_{i\neq k}(x_k-x_i)},$$ which are such that $l_k(x_k)=1$ and $l_k(x_i)=0$ for $i\neq k$.

Let $x_0=-1$ and $x_{n+1}=1$ and $$\Upsilon(x_1,\ldots,x_n)=\min_{0\leq i\leq n}\max_{x\in[x_i,x_{i+1}]} \sum_k \lvert l_k(x)\rvert.$$ Describe which choice of $x_i$ maximise $\Upsilon(x_1,\ldots,x_n)$.

This is the second part. Erdős [Er47, p. 1172], [Er67, p. 66] conjectured that the maximisers are the node sets of erdosproblems.com/1129, characterised by equal local maxima. This was proved by Kilgore [Ki77], [Ki78] and by de Boor and Pinkus [dBPi78] for canonical node sets, with the smallest local maximum between consecutive nodes in place of $\Upsilon$ (see [Ib16, Section 3.7]); this is erdos_1130.variants.canonical.

Here, as in the question, $\Upsilon$ includes the two outer gaps and the maximisers range over all node sets in $[-1,1]$. A maximiser is then not unique in general, and it need not have all $n+1$ local maxima $\lambda_0,\ldots,\lambda_n$ equal: for $n=3$ the nodes $-s,0,s$ with $0<s\le\frac{2\sqrt2}{3}$ all give $\Upsilon=\frac54$, the largest possible value, and for $s=\frac12$ the four local maxima are $7,\frac54,\frac54,7$. The cited sources do not describe the whole set of maximisers, so erdos_1130.parts.ii.answer is left as sorry.

@[category research solved, question value, AMS 41] theorem erdos_1130.parts.ii (n : ℕ) : {x : Fin n → ℝ | IsNodeSet x ∧ ∀ y : Fin n → ℝ, IsNodeSet y → upsilon y ≤ upsilon x} = erdos_1130.parts.ii.answer n := n:ℕ⊢ {x | IsNodeSet x ∧ ∀ (y : Fin n → ℝ), IsNodeSet y → upsilon y ≤ upsilon x} = ii.answer n All goals completed! 🐙

The theorem of Kilgore [Ki77], [Ki78] and de Boor and Pinkus [dBPi78] in the form of [Ib16, Section 3.7]: among canonical node sets ($x_1=-1$, $x_n=1$), the ones at which the smallest of the $n-1$ local maxima between consecutive nodes is largest are exactly the canonical node sets whose local maxima between consecutive nodes are all equal, that is, the canonical minimisers of $\Lambda$ (Erdos1129.erdos_1129.variants.canonical). For canonical nodes the two outer gaps are single points and the literal $\Upsilon$ is $1$, which is why $\Upsilon$ is replaced by minInteriorGapMax here.

@[category research solved, AMS 41] theorem erdos_1130.variants.canonical (n : ℕ) : {x : Fin n → ℝ | IsCanonical x ∧ ∀ y : Fin n → ℝ, IsCanonical y → minInteriorGapMax y ≤ minInteriorGapMax x} = {x | IsCanonical x ∧ Equioscillates x} := n:ℕ⊢ {x | IsCanonical x ∧ ∀ (y : Fin n → ℝ), IsCanonical y → minInteriorGapMax y ≤ minInteriorGapMax x} = {x | IsCanonical x ∧ Equioscillates x} All goals completed! 🐙

The inequality conjectured by Erdős and proved by Kilgore [Ki77], [Ki78] and by de Boor and Pinkus [dBPi78] (stated in [Ib16, Section 3.7] as $m_n(X)\le \Lambda_n(X^*)$ for every node set $X$): the smallest local maximum of the Lebesgue function of any node set is at most the minimal Lebesgue constant. Here $y$ is a minimiser of $\Lambda$. For nodes that contain neither $-1$ nor $1$, $\Upsilon$ is this smallest local maximum [Ib16, Section 2.1 (b), (c)]; otherwise $\Upsilon=1$.

@[category research solved, AMS 41] theorem erdos_1130.variants.erdos_inequality (n : ℕ) (x y : Fin n → ℝ) (hx : IsNodeSet x) (hy : IsMinimiser y) : upsilon x ≤ lebesgueConstant y := n:ℕx:Fin n → ℝy:Fin n → ℝhx:IsNodeSet xhy:IsMinimiser y⊢ upsilon x ≤ lebesgueConstant y All goals completed! 🐙

The same inequality for a canonical node set x, in the form of [Ib16, Section 3.7]: the smallest of the local maxima between consecutive nodes is at most the minimal Lebesgue constant.

@[category research solved, AMS 41] theorem erdos_1130.variants.erdos_inequality_canonical (n : ℕ) (x y : Fin n → ℝ) (hx : IsCanonical x) (hy : IsMinimiser y) : minInteriorGapMax x ≤ lebesgueConstant y := n:ℕx:Fin n → ℝy:Fin n → ℝhx:IsCanonical xhy:IsMinimiser y⊢ minInteriorGapMax x ≤ lebesgueConstant y All goals completed! 🐙

It follows from erdos_1130.variants.erdos_inequality and the bound for Chebyshev nodes in [Er61c, p. 236] that $$\Upsilon(x_1,\ldots,x_n)\le\frac{2}{\pi}\log n+O(1).$$

@[category research solved, AMS 41] theorem erdos_1130.variants.log_bound : ∃ C : ℝ, ∀ (n : ℕ) (x : Fin n → ℝ), 1 ≤ n → IsNodeSet x → upsilon x ≤ 2 / Real.pi * Real.log n + C := ⊢ ∃ C, ∀ (n : ℕ) (x : Fin n → ℝ), 1 ≤ n → IsNodeSet x → upsilon x ≤ 2 / Real.pi * Real.log ↑n + C All goals completed! 🐙

Erdős [Er47, Theorem 2, pp. 1171-1172] proved that for nodes $x_1\le\cdots\le x_n$ in $[-1,1]$ there is an $i$ with $\max_{x\in[x_i,x_{i+1}]}\sum_k\lvert l_k(x)\rvert<\sqrt n$, that is, $\Upsilon(x_1,\ldots,x_n)<\sqrt n$. The paper allows coinciding nodes (then it calls the claim obvious); here the nodes are distinct. We take $n\ge 2$: for $n=1$ the sum is identically $1$.

@[category research solved, AMS 41] theorem erdos_1130.variants.erdos_sqrt (n : ℕ) (hn : 2 ≤ n) (x : Fin n → ℝ) (hx : IsNodeSet x) : upsilon x < Real.sqrt n := n:ℕhn:2 ≤ nx:Fin n → ℝhx:IsNodeSet x⊢ upsilon x < √↑n All goals completed! 🐙end Erdos1130