/-
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.
-/modulepublicimportFormalConjecturesUtil
[Be31] Bernstein, S., Sur la limitation des valeurs d'un polynome $P_n(x)$ de degré $n$ sur
tout un segment par ses valeurs en $(n+1)$ points du segment. Izv. Akad. Nauk SSSR (1931),
1025-1050.
[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) 10 (1968),
65-73. PDF
[Ta26b] Tao, T., Local Bernstein theory, and lower bounds for Lebesgue constants.
arXiv:2603.21453 (2026).
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference
"Paul Erdős and his mathematics", Budapest, July 1999 (1999).
The fundamental Lagrange function $l_k$ of the nodes x 0, …, x (n - 1), evaluated at t:
$$l_k(t)=\frac{\prod_{i\neq k}(t-x_i)}{\prod_{i\neq k}(x_k-x_i)},$$
where $i$ and $k$ range over Finset.range n. If two nodes coincide, a denominator vanishes and
the value is the junk value 0, so the statements below assume that the nodes are distinct.
The Lebesgue function $L_n(t)=\sum_{k<n}\lvert l_k(t)\rvert$ of the first n nodes
x 0, …, x (n - 1). The nodes x 0, x 1, … play the role of $x_1, x_2, \ldots$.
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_1,x_2,\ldots\in [-1,1]$ be an infinite sequence, and let
$$L_n(x) = \sum_{1\leq k\leq n}\lvert l_k(x)\rvert,$$
where each $l_k(x)$ is defined above with respect to $x_1,\ldots,x_n$.
Must there exist $x\in (-1,1)$ such that
$$L_n(x) >\frac{2}{\pi}\log n-O(1)$$
for infinitely many $n$?
This is the first part, asked in [Er67, p. 68] (see also [Va99, 2.43]); [Er61c, (4)] states it as
"quite possibly true". Both papers consider an arbitrary triangular array of nodes; as on the
problem page, we take the first $n$ terms of one sequence, a special case. The nodes are required
to be distinct, so that $l_k$ is defined. We let the constant $C$ in $O(1)$ depend on the sequence
and on $x$, the weakest reading. In [Er61c, (4)] it is an absolute constant.
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_1,x_2,\ldots\in [-1,1]$ be an infinite sequence, and let
$$L_n(x) = \sum_{1\leq k\leq n}\lvert l_k(x)\rvert,$$
where each $l_k(x)$ is defined above with respect to $x_1,\ldots,x_n$.
Is it true that
$$\limsup_{n\to \infty}\frac{L_n(x)}{\log n}\geq \frac{2}{\pi}$$
for almost all $x\in (-1,1)$?
This is the second part, asked in [Er67, p. 68] ("Perhaps (7) holds for almost all $x_0$"), again
for triangular arrays. The nodes are required to be distinct. We write the $\limsup$ condition as:
for every $\varepsilon>0$, there are infinitely many $n$ with
$$L_n(x)\geq\left(\frac{2}{\pi}-\varepsilon\right)\log n.$$
This is equivalent, and avoids the junk value of a real limsup of an unbounded sequence.
The problem page says that a result of Bernstein [Be31] implies that the set of such $x$ is
everywhere dense. In [Er67, p. 68] Erdős derives this from his own unpublished bound (6), which
sharpens a result of Bernstein. It also follows from erdos_1132.variants.tao with
$\omega(n)=\log\log n$.
Erdős [Er61c, Theorem 1] proved that, for any fixed $x_1,\ldots,x_n\in [-1,1]$,
$$\max_{x\in [-1,1]}\sum_{1\leq k\leq n}\lvert l_k(x)\rvert>\frac{2}{\pi}\log n-O(1).$$
Here $O(1)$ is an absolute constant $C$, and the maximum exceeds a bound if and only if some point
does, so we write the statement with ∃ t. The nodes are required to be distinct.
Tao [Ta26b, Corollary 1.11] has proved that for any function $\omega(n)$ which tends to infinity
with $n$ there exists a dense set of $x\in (-1,1)$ such that
$$L_n(x)\geq \frac{2}{\pi}\log n-\omega(n)$$
for infinitely many $n$.
Tao proves this for an arbitrary triangular array of distinct nodes in $[-1,1]$, so in particular
for the first $n$ terms of a sequence. We state the array version: x n k is the $k$-th node
(counted from $0$) of the $n$-th row, and the set is dense in $(-1,1)$ if every point of
$(-1,1)$ is in its closure.