Erdős Problem #1129

Erdős Problem 1129: optimal nodes and the endpoint convention

Statement.

For distinct ordered nodes $-1\leq x_1<\cdots<x_n\leq1$, let \[ l_k(x)=\prod_{j\ne k}\frac{x-x_j}{x_k-x_j}, \qquad L_{\boldsymbol x}(x)=\sum_k|l_k(x)|, \qquad\Lambda(\boldsymbol x)=\max_{[-1,1]}L_{\boldsymbol x}. \] We describe all minimizers, relative to the established de Boor--Pinkus theorem for fixed endpoints. The distinction between fixed and movable endpoints matters: the literal formulation at https://www.erdosproblems.com/1129 does not have a unique minimizer when $n\geq3$.

Explicit external theorem.

For $n\geq3$, among canonical arrays $-1=t_1<\cdots<t_n=1$, there is a unique array $\boldsymbol t^*$ whose $n-1$ internal interval maxima of $L_{\boldsymbol t^*}$ all equal a constant $\Lambda_n^*$. For every other canonical array, the least internal maximum is strictly below $\Lambda_n^*$ and the greatest is strictly above it. This is the consequence of Theorems 1 and 2 of C. de Boor and A. Pinkus, Proof of the conjectures of Bernstein and Erdős concerning the optimal nodes for polynomial interpolation, J. Approximation Theory 24 $1978$, 289--303, https://doi.org/10.1016/0021-9045(78)90014-X. Their paper fixes both endpoints; its indexing uses $n+1$ nodes. This deep theorem is imported, not reproved here. Reflection and uniqueness show that $\boldsymbol t^*$ is symmetric.

All minimizers with movable endpoints.

Write $L^*=L_{\boldsymbol t^*}$. Then the answer to the literal problem is precisely \[ \boxed{\quad x_i=c+h t_i^*,\quad h>0,\quad -1\leq c-h<c+h\leq1,\quad L^*((-1-c)/h)\leq\Lambda_n^*,\ L^*((1-c)/h)\leq\Lambda_n^*.\quad} \] To prove necessity, normalize an arbitrary array by \[ c=(x_1+x_n)/2,\qquad h=(x_n-x_1)/2,\qquad t_i=(x_i-c)/h. \] The Lagrange product formula gives $L_{\boldsymbol x}(c+hu)=L_{\boldsymbol t}(u)$. The global maximum is at least the largest internal interval maximum, hence at least $\Lambda_n^*$. The canonical optimal array attains that lower bound. If any other array attains it, the strict part of the external theorem forces $\boldsymbol t=\boldsymbol t^*$, and the two displayed endpoint inequalities are necessary.

They are also sufficient. For $u>1$, each $|l_k^*(u)|$ is a product of positive increasing factors divided by a positive constant, so $L^*(u)$ is increasing. For $u<-1$ it increases as $u$ moves left. Thus the exterior interval maxima occur at the domain endpoints $-1,1$, while every internal maximum equals $\Lambda_n^*$.

Equivalently, let $r_n>1$ be the unique solution $L^*(r_n)=\Lambda_n^*$. It exists since $L^*(1)=1<\Lambda_n^*$, exterior growth is strict, and $L^*(u)\to\infty$. Symmetry gives the alternative constraints \[ (1+|c|)/r_n\leq h\leq1-|c|. \] This makes the nonuniqueness explicit.

A fully calculated example.

For three canonical nodes $-1,u,1$, the two internal maxima are \[ 1+\frac{(1+u)^2}{4(1-u)},\qquad 1+\frac{(1-u)^2}{4(1+u)}. \] If $u\geq0$, the first is at least $5/4$; if $u\leq0$, the second is at least $5/4$. Equality of their maximum to $5/4$ forces $u=0$. For nodes $-t,0,t$, direct evaluation outside their span gives \[ \Lambda(-t,0,t)=\max\{5/4,\ 2/t^2-1\}. \] Thus every $\sqrt{8/9}\leq t\leq1$ is a minimizer. Only the first of these has both exterior maxima equal to the internal ones. Unqualified uniqueness or equality of all $n+1$ interval maxima therefore cannot characterize the literal problem.

For $n=2$, the minimum $1$ is attained only at $-1,1$, since the Lebesgue function is $1$ between the two nodes and strictly larger outside. For $n=1$, it is identically $1$, so every node is optimal.

Completion estimate.

All literal minimizers are characterized, using the stated canonical de Boor--Pinkus theorem as the external input; the three-node case and the endpoint correction are proved directly. COMPLETION: 100%

FORMAL RESTATEMENT

Let $n\ge 2$ and let $x_1,\dots,x_n\in[-1,1]$ be pairwise distinct. For $1\le k\le n$ define the $k$th Lagrange fundamental polynomial \[ l_k(x):=\frac{\prod_{i\ne k}(x-x_i)}{\prod_{i\ne k}(x_k-x_i)}. \] Define the Lebesgue function and Lebesgue constant \[ L(x):=\sum_{k=1}^n |l_k(x)|,\qquad \Lambda(x_1,\dots,x_n):=\max_{x\in[-1,1]} L(x). \] Problem: characterize the choice(s) of nodes $x_1,\dots,x_n$ that minimize $\Lambda(x_1,\dots,x_n)$.

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states lower bounds $\Lambda\gg\log n$ (Faber) and $\Lambda>\tfrac{2}{\pi}\log n-O(1)$ (Erdős), and that choosing $x_i$ as roots of the $n$th Chebyshev polynomial gives $\Lambda<\tfrac{2}{\pi}\log n+O(1)$. It also states the minimising canonical choice is known only for $n\le 4$.

ATTACK PLAN

Proof track ideas.

• Use structural identities of the Lagrange basis (partition of unity) and variational conditions for optimality.
• Explore symmetry reductions for canonical node sets with $x_1=-1$, $x_n=1$.

Disproof track ideas.

• For proposed characterizations (e.g. equal interval maxima), attempt to find a node set violating the characterization yet having comparable $\Lambda$.

WORK

Lemma 1129.1 (partition of unity). For any distinct nodes $x_1,\dots,x_n$ and the associated Lagrange polynomials $l_k$, one has \[ \sum_{k=1}^n l_k(x)=1\qquad\text{for all }x\in\mathbb{R}. \]

Proof. Define $p(x):=\sum_{k=1}^n l_k(x)-1$. Each $l_k$ is a polynomial of degree at most $n-1$, hence so is $p$. For each node $x_i$ we have $l_k(x_i)=\delta_{ki}$ by construction, so \[ \sum_{k=1}^n l_k(x_i)=1\quad\Rightarrow\quad p(x_i)=0. \] Thus $p$ has at least $n$ distinct roots $x_1,\dots,x_n$. But a nonzero polynomial of degree at most $n-1$ can have at most $n-1$ roots. Therefore $p$ must be the zero polynomial, i.e. $\sum_k l_k(x)=1$ for all $x$. $\square$

Lemma 1129.2 (universal lower bound $\Lambda\ge 1$). For every choice of distinct nodes $x_1,\dots,x_n$, \[ \forall x\in[-1,1],\quad \sum_{k=1}^n |l_k(x)|\ge 1, \] and hence $\Lambda(x_1,\dots,x_n)\ge 1$.

Proof. By Lemma 1129.1, $\sum_k l_k(x)=1$ for all $x$. By the triangle inequality, \[ 1=\left|\sum_{k=1}^n l_k(x)\right|\le \sum_{k=1}^n |l_k(x)|. \] Taking the maximum over $x\in[-1,1]$ yields $\Lambda\ge 1$. $\square$

Lemma 1129.3 (exact computation for $n=2$ and endpoints). If $n=2$ and $(x_1,x_2)=(-1,1)$, then $\Lambda(x_1,x_2)=1$.

Proof. For $x_1=-1,x_2=1$ we have \[ l_1(x)=\frac{x-1}{-2}=\frac{1-x}{2},\qquad l_2(x)=\frac{x+1}{2}. \] On $[-1,1]$ both are nonnegative and satisfy $l_1(x)+l_2(x)=1$. Therefore $|l_1(x)|+|l_2(x)|=1$ for all $x\in[-1,1]$, so the maximum is $1$. $\square$

FAST REALITY CHECK (numerics for small $n$). Using barycentric evaluation on a fine grid, I computed approximate Lebesgue constants for some named node choices.

n=2 endpoints
  Lambda approx 1.0000000000000002 at x≈ -0.9998

n=3 -1,0,1
  Lambda approx 1.25 at x≈ -0.5

n=4 t=0.4177 (nodes -1,-t,t,1)
  Lambda approx 1.4230953773112645 at x≈ -0.7331

Chebyshev roots n=5:  Lambda≈1.988854 ; (2/pi)log n≈1.024600
Chebyshev roots n=10: Lambda≈2.428829 ; (2/pi)log n≈1.465871
Chebyshev roots n=20: Lambda≈2.869774 ; (2/pi)log n≈1.907142

These numbers are consistent with the statements in the problem file (logarithmic growth and the $2/\pi$ coefficient).

VERIFICATION

• Lemma 1129.1 is the standard "degree vs number of roots" argument and uses only that nodes are distinct.
• Lemma 1129.2 uses only triangle inequality and Lemma 1129.1.
• Lemma 1129.3 is an exact computation.
• The numerical maxima were computed over a dense grid; they certify lower bounds on $\Lambda$ and are close to known exact values for $n=2,3$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. The Lagrange basis satisfies $\sum_k l_k(x)=1$ for all $x$ (Lemma 1129.1), hence $\Lambda\ge 1$ for all node sets (Lemma 1129.2), with equality achieved for $n=2$ at $\{-1,1\}$ (Lemma 1129.3).

(ii) First gap (crisp). Determine, for general $n$, the node configurations $x_1,\dots,x_n\in[-1,1]$ minimizing $\Lambda(x_1,\dots,x_n)$ (beyond the known small-$n$ cases).

(iii) Top 3 next moves.

• Derive first-order optimality conditions for minimizers of $\Lambda$ (subgradient/alternation type conditions) and test whether they force the "equal interval maxima" property mentioned in the problem file.
• For canonical configurations with $x_1=-1,x_n=1$, reduce the minimization to a finite-dimensional constrained optimization and attempt to prove uniqueness and symmetry for all $n$.
• Perform rigorous computer-assisted optimization for $n=5,6$ to guess patterns and candidate algebraic constants (as done for $n=4$ in the file).

(iv) Minimal counterexample structure. A counterexample to a proposed characterization would be a node set with strictly smaller $\Lambda$ than the characterized family, likely breaking symmetry or the equal-maxima condition while still matching the $\tfrac{2}{\pi}\log n+O(1)$ asymptotic scale.