Erdős Problem #1130

Erdős Problem 1130: the maximin interpolation problem

Statement and normalization.

For distinct ordered nodes $-1\leq x_1<\cdots<x_n\leq1$, let \[ L_{\boldsymbol x}(x)=\sum_{k=1}^n \left|\prod_{j\ne k}\frac{x-x_j}{x_k-x_j}\right|, \qquad \Upsilon(\boldsymbol x)=\min_{0\leq i\leq n} \max_{x\in[x_i,x_{i+1}]}L_{\boldsymbol x}(x), \] where $x_0=-1,x_{n+1}=1$. We prove the logarithmic bound and characterize all maximizers under this literal convention, which includes both exterior intervals. Source: https://www.erdosproblems.com/1130.

The canonical input.

Theorems 1 and 2 of de Boor--Pinkus $1978$, https://doi.org/10.1016/0021-9045(78)90014-X, imply that for $n\geq3$ there is a unique canonical array $-1=t_1^*<\cdots<t_n^*=1$ whose $n-1$ internal interval maxima all have a common value $\Lambda_n^*$. For any other canonical array, the minimum internal maximum is strictly smaller and the maximum internal maximum is strictly larger. We use this theorem as an explicit external input, with its endpoints fixed and its node indexing adjusted. Write $L^*=L_{\boldsymbol t^*}$.

Characterization with exterior intervals included.

The exact maximum of $\Upsilon$ is $\Lambda_n^*$, and all maximizers are \[ \boxed{\quad x_i=c+h t_i^*,\quad h>0,\quad -1\leq c-h<c+h\leq1,\quad L^*((-1-c)/h)\geq\Lambda_n^*,\ L^*((1-c)/h)\geq\Lambda_n^*.\quad} \] Indeed, affine normalization by $c=(x_1+x_n)/2$, $h=(x_n-x_1)/2$ preserves every internal maximum. Thus $\Upsilon(\boldsymbol x)\leq\min_{1\leq i<n}\lambda_i\leq\Lambda_n^*$, with equality only if the normalized array is $\boldsymbol t^*$. For this array each exterior maximum occurs at its outer endpoint: beyond the outermost node each absolute Lagrange product grows as one moves farther away. The two displayed inequalities are therefore exactly the remaining equality conditions.

The canonical array is symmetric by uniqueness. Its exterior function grows strictly from $L^*(1)=1$ to infinity, and $\Lambda_n^*>1$. Let $r_n>1$ satisfy $L^*(r_n)=\Lambda_n^*$. The conditions become \[ |c|<1,\qquad 0<h\leq(1-|c|)/r_n. \] They are nonempty, proving attainment, and also show that maximizers need not be unique or have all $n+1$ maxima equal. For example, with three nodes $-t,0,t$, the internal maxima are $5/4$, the exterior ones are $2/t^2-1$, and every $0<t\leq\sqrt{8/9}$ maximizes $\Upsilon$. For $n=2$, $\Upsilon=1$ for every pair of nodes, because its internal maximum is $1$ and all maxima are at least $1$. For $n=1$, likewise $\Upsilon=1$.

An elementary $O(\log n)$ upper bound.

It remains to bound $\Lambda_n^*$. Use the $n$ Chebyshev zeros $z_k=\cos\theta_k$, $\theta_k=(2k-1)\pi/(2n)$. For $x=\cos\theta$, their Lagrange functions satisfy \[ |l_k(\cos\theta)| =\frac{|\cos n\theta|\sin\theta_k} {n|\cos\theta-\cos\theta_k|} \leq\frac{\pi|\cos n\theta|}{n|\theta-\theta_k|}. \] The inequality follows from $\sin\theta_k\leq2\sin((\theta+\theta_k)/2)$ and $\sin(|\theta-\theta_k|/2)\geq|\theta-\theta_k|/\pi$. Let $k_0$ be a nearest zero angle. Then $|\cos n\theta|\leq n|\theta-\theta_{k_0}|$, so the $k_0$-term is at most $\pi$. For $k\ne k_0$, \[ |\theta-\theta_k|\geq(|k-k_0|-1/2)\pi/n, \qquad |l_k(\cos\theta)|\leq\frac1{|k-k_0|-1/2}. \] Consequently the sum is at most $\pi+2\sum_{j=1}^{n-1}(j-1/2)^{-1}=O(\log n)$, uniformly in $\theta$; values at nodes follow by continuity. Stretching these zeros so that the extreme nodes become $-1,1$ cannot increase the maximum: the affine preimage of the domain is a subinterval of the original domain. Canonical optimality now gives $\Lambda_n^*=O(\log n)$, and hence $\Upsilon\ll\log n$ for $n\geq2$.

Completion estimate.

The logarithmic bound and complete literal maximizer characterization follow, with only the canonical extremal-node theorem imported. COMPLETION: 100%

FORMAL RESTATEMENT

Let $n\ge 1$ and let $x_1<\dots<x_n$ be distinct points in $[-1,1]$. Define the Lagrange polynomials $l_k$ as in Problem 1129. Set $x_0=-1$ and $x_{n+1}=1$ and define \[ \Upsilon(x_1,\dots,x_n):=\min_{0\le i\le n}\ \max_{x\in[x_i,x_{i+1}]}\ \sum_{k=1}^n |l_k(x)|. \] Questions:

1. Is it true that for all node sets, $\Upsilon(x_1,\dots,x_n)\ll \log n$?
2. Describe node sets $x_1,\dots,x_n$ that maximize $\Upsilon(x_1,\dots,x_n)$.

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states that Erdős proved $\Upsilon(x_1,\dots,x_n)<\sqrt{n}$, and suggests a conjectured characterization of maximizers via equalizing certain interval maxima.

ATTACK PLAN

Proof track ideas.

• Relate $\Upsilon$ to the Lebesgue constant $\Lambda$ from Problem 1129 via simple inequalities (Lemma 1130.1).
• Investigate configurations where all interval-wise maxima are large; maximizing $\Upsilon$ means even the smallest interval maximum is large.

Disproof track ideas.

• Try to construct node sets with $\Upsilon$ growing faster than $\log n$ (e.g. by clustering points so that $\sum |l_k(x)|$ is large on every subinterval).

WORK

Lemma 1130.1 (comparison with Lebesgue constant). Let \[ \Lambda(x_1,\dots,x_n):=\max_{x\in[-1,1]}\sum_{k=1}^n|l_k(x)| \] be the Lebesgue constant from Problem 1129. Then \[ 1\le \Upsilon(x_1,\dots,x_n)\le \Lambda(x_1,\dots,x_n). \]

Proof. For the lower bound, Lemma 1129.1 gives $\sum_k l_k(x)=1$ for all $x$, hence by the triangle inequality $\sum_k|l_k(x)|\ge 1$ for all $x\in[-1,1]$. Therefore each interval maximum $\max_{x\in[x_i,x_{i+1}]}\sum_k|l_k(x)|$ is at least $1$, so the minimum over $i$ is at least $1$.

For the upper bound, for each fixed $i$ we have \[ \max_{x\in[x_i,x_{i+1}]}\sum_k|l_k(x)|\le \max_{x\in[-1,1]}\sum_k|l_k(x)|=\Lambda. \] Taking the minimum over $i$ preserves the inequality, giving $\Upsilon\le\Lambda$. $\square$

Lemma 1130.2 (endpoint inclusion forces $\Upsilon=1$). If $x_1=-1$ and $x_n=1$, then $\Upsilon(x_1,\dots,x_n)=1$.

Proof. If $x_1=-1$, then the interval $[x_0,x_1]=[-1,-1]$ is a single point. At $x=-1$ we have $l_1(-1)=1$ and $l_k(-1)=0$ for $k\ne 1$, hence $\sum_k|l_k(-1)|=1$. Thus \[ \max_{x\in[x_0,x_1]}\sum_k|l_k(x)| = 1. \] Similarly, if $x_n=1$, then on the degenerate interval $[x_n,x_{n+1}]=[1,1]$ we have $\sum_k|l_k(1)|=1$. Therefore the minimum over $i$ of these interval maxima is at most $1$. Combined with the universal lower bound $\Upsilon\ge 1$ from Lemma 1130.1, we get $\Upsilon=1$. $\square$

FAST REALITY CHECK (numerics for small examples). The value of $\Upsilon$ depends strongly on whether endpoints are included as nodes.

Nodes [-1,0,1] (n=3): interval maxima [1.0, 1.25, 1.25, 1.0]
  => Upsilon = min(...) = 1.0

Nodes [-0.5,0,0.5] (n=3): interval maxima [7.0, 1.25, 1.25, 7.0]
  => Upsilon = 1.25

Nodes [-0.9,-0.3,0.2] (n=3): interval maxima [1.8, 1.327273, 1.189394, 11.133333]
  => Upsilon ≈ 1.189394

VERIFICATION

• Lemma 1130.1 uses only Lemma 1129.1 and monotonicity of max/min with respect to domain inclusion.
• Lemma 1130.2 carefully checks the degenerate intervals when endpoints are among the nodes.
• Numerical interval maxima are grid-based and should be read as approximations.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Always $1\le \Upsilon\le\Lambda$ (Lemma 1130.1), and if the node set includes both endpoints $\{-1,1\}$ then $\Upsilon=1$ exactly (Lemma 1130.2).

(ii) First gap (crisp). Prove or disprove the conjectured upper bound $\Upsilon(x_1,\dots,x_n)\ll \log n$ uniformly over all node sets.

(iii) Top 3 next moves.

• Search for constructions where every interval $[x_i,x_{i+1}]$ contains points where $\sum_k|l_k(x)|$ is large, so that the minimum of the interval maxima grows.
• Attempt to relate $\Upsilon$ to more tractable functionals (e.g. $L^2$ norms) using inequalities like Cauchy--Schwarz on each subinterval.
• For candidate maximizers, attempt to prove a necessary equalization condition: at optimality, all interval maxima should coincide.

(iv) Minimal counterexample structure. A counterexample to $\Upsilon\ll\log n$ would be a family of node sets $x^{(n)}_1<\dots<x^{(n)}_n$ such that on every subinterval $[x^{(n)}_i,x^{(n)}_{i+1}]$ the quantity $\sum_k|l_k(x)|$ attains values much larger than $\log n$, forcing their minimum to grow faster than $\log n$.