Erdős Problem #1133

Erdős Problem 1133 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1133

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1133.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1133.tex.

FORMAL RESTATEMENT

Fix $C>0$. Question: does there exist $\epsilon>0$ such that for all sufficiently large integers $n$ the following holds? For every choice of nodes $x_1,\dots,x_n\in[-1,1]$, there exist target values $y_1,\dots,y_n\in[-1,1]$ such that: for every real polynomial $P$ of degree \[ \deg P = m < (1+\epsilon)n \] that satisfies \[ \lvert\{1\le i\le n: P(x_i)=y_i\}\rvert\ge (1-\epsilon)n, \] one has \[ \max_{x\in[-1,1]} |P(x)|>C. \]

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states Erdős proved a related result: for any $C>0$ there exists $\epsilon>0$ such that for large $n$ and $m=\lfloor(1+\epsilon)n\rfloor$, for any $x_1,\dots,x_m\in[-1,1]$ there is a polynomial $P$ of degree $n$ with $|P(x_i)|\le 1$ at those $m$ points but $\max_{[-1,1]}|P|>C$. It also states Erdős could not prove the conjectured statement even for $m=n$.

ATTACK PLAN

Proof track ideas.

• Reduce to a statement about interpolation operators and Lebesgue constants: large Lebesgue constants allow choosing $y_i\in\{\pm 1\}$ forcing large sup norm for the interpolant.
• Try to "robustify" the exact interpolation forcing to handle matching only $(1-\epsilon)n$ points: show that any polynomial matching many prescribed signs must have large sup due to oscillation constraints.

Disproof track ideas.

• Attempt to show that for some configurations of points, any assignment $y_i\in[-1,1]$ can be matched on most points by a degree $<(1+\epsilon)n$ polynomial with controlled sup norm.

WORK

Lemma 1133.1 (explicit interpolation formula for degree $\le n-1$). Let $x_1,\dots,x_n$ be distinct points in $\mathbb{R}$ and let $y_1,\dots,y_n\in\mathbb{R}$. Define Lagrange polynomials $l_k$ from these nodes. Then the polynomial \[ P(x):=\sum_{k=1}^n y_k\,l_k(x) \] has degree at most $n-1$ and satisfies $P(x_i)=y_i$ for every $1\le i\le n$. Moreover, it is the unique polynomial of degree at most $n-1$ with these interpolation values.

Proof. Each $l_k$ has degree $n-1$, so $P$ has degree at most $n-1$. At a node $x_i$, we have $l_k(x_i)=\delta_{ki}$, hence \[ P(x_i)=\sum_{k=1}^n y_k\delta_{ki}=y_i. \] For uniqueness, suppose $Q$ is another polynomial of degree at most $n-1$ with $Q(x_i)=y_i$ for all $i$. Then $R:=P-Q$ has degree at most $n-1$ and has $n$ distinct roots $x_1,\dots,x_n$, so $R\equiv 0$. Therefore $P\equiv Q$. $\square$

Lemma 1133.2 (forcing large sup norm via the Lebesgue constant). Let $x_1,\dots,x_n\in[-1,1]$ be distinct nodes and let \[ \Lambda:=\max_{x\in[-1,1]}\sum_{k=1}^n |l_k(x)| \] be the Lebesgue constant associated to these nodes. Choose $x^*\in[-1,1]$ where the maximum is attained and define \[ y_k:=\begin{cases} \phantom{-}1,& l_k(x^*)\ge 0,\\ -1,& l_k(x^*)<0. \end{cases} \] Let $P$ be the degree $\le n-1$ interpolant through $(x_k,y_k)$ given by Lemma 1133.1. Then \[ P(x^*)=\sum_{k=1}^n |l_k(x^*)|=\Lambda, \] and hence $\max_{x\in[-1,1]}|P(x)|\ge \Lambda$.

Proof. By construction, $y_k=\operatorname{sign}(l_k(x^*))$ (with the convention $\operatorname{sign}(0)=1$). Therefore $y_k l_k(x^*)=|l_k(x^*)|$ for every $k$, and Lemma 1133.1 gives \[ P(x^*)=\sum_{k=1}^n y_k l_k(x^*)=\sum_{k=1}^n |l_k(x^*)|=\Lambda. \] Taking absolute values and the maximum over $x$ yields $\max_{[-1,1]}|P|\ge |P(x^*)|=\Lambda$. $\square$

Interpretation. Lemma 1133.2 shows a weaker (but relevant) forcing statement: for exact interpolation by degree $\le n-1$ polynomials (the case $\epsilon=0$ and $m=n-1$), one can always choose $y_k\in\{\pm 1\}$ so that any polynomial matching all $n$ constraints (necessarily the interpolant) must have sup norm at least $\Lambda$. Since the problem file states $\Lambda\gg\log n$ for every node set (Faber), this forcing exceeds any fixed $C$ for sufficiently large $n$. What remains open in the posed problem is robustness: allowing degree up to $(1+\epsilon)n$ and allowing the polynomial to ignore $\epsilon n$ constraints.

FAST REALITY CHECK (numerical illustration). For $n=5$ equally spaced nodes $[-1,-0.5,0,0.5,1]$, the above construction gives:

nodes [-1.  -0.5  0.   0.5  1. ]
Lambda approx 2.20782438320626 at x* -0.7919
y_k [ 1.  1. -1.  1. -1.]
P sup approx 2.20782438320626 attained near -0.7919
P(x*) 2.20782438320626

This empirically confirms Lemma 1133.2 in a concrete case.

VERIFICATION

• Lemma 1133.1 is standard and gap-free: interpolation property and uniqueness via $n$ roots.
• Lemma 1133.2 depends on existence of a maximizer $x^*$, which holds because $x\mapsto \sum_k|l_k(x)|$ is continuous on compact $[-1,1]$.
• The leap from Lemma 1133.2 to the conjectured statement is nontrivial because the conjecture permits dropping $\epsilon n$ constraints and increasing degree to $(1+\epsilon)n$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For any node set $x_1,\dots,x_n$, one can choose $y_k\in\{\pm 1\}$ so that the unique interpolant of degree $\le n-1$ has $\max_{[-1,1]}|P|\ge \Lambda(x_1,\dots,x_n)$ (Lemma 1133.2).

(ii) First gap (crisp). Upgrade the exact-interpolation forcing (degree $n-1$ and matching all $n$ points) to the robust regime of the problem: degree $<(1+\epsilon)n$ and matching at least $(1-\epsilon)n$ points.

(iii) Top 3 next moves.

• Prove a robustness lemma: if a degree $m$ polynomial matches a sign pattern on many nodes, then its sup norm is bounded below in terms of a "restricted" Lebesgue constant for those nodes.
• Use quantitative bounds on how many alternations/oscillations a degree $m$ polynomial with bounded sup norm can have on $[-1,1]$, and choose $y_i$ to force more oscillation than allowed.
• Try probabilistic constructions for $y_i\in\{\pm 1\}$ and prove that with positive probability any degree-$m$ polynomial matching $>(1-\epsilon)n$ points must have large sup norm.

(iv) Minimal counterexample structure. A counterexample for a given $C$ would be a sequence of node sets $x^{(n)}_1,\dots,x^{(n)}_n$ such that for every assignment $y_i\in[-1,1]$ there exists a polynomial of degree $<(1+\epsilon)n$ matching $>(1-\epsilon)n$ constraints while keeping $\max_{[-1,1]}|P|\le C$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT

Fix $C>0$. Question: does there exist $\epsilon>0$ such that for all sufficiently large integers $n$ the following holds? For every choice of nodes $x_1,\dots,x_n\in[-1,1]$, there exist target values $y_1,\dots,y_n\in[-1,1]$ such that: for every real polynomial $P$ of degree \[ \deg P = m < (1+\epsilon)n \] that satisfies \[ \lvert\{1\le i\le n: P(x_i)=y_i\}\rvert\ge (1-\epsilon)n, \] one has \[ \max_{x\in[-1,1]} |P(x)|>C. \]

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states Erdős proved a related result: for any $C>0$ there exists $\epsilon>0$ such that for large $n$ and $m=\lfloor(1+\epsilon)n\rfloor$, for any $x_1,\dots,x_m\in[-1,1]$ there is a polynomial $P$ of degree $n$ with $|P(x_i)|\le 1$ at those $m$ points but $\max_{[-1,1]}|P|>C$. It also states Erdős could not prove the conjectured statement even for $m=n$.

ATTACK PLAN

Proof track ideas.

• Reduce to a statement about interpolation operators and Lebesgue constants: large Lebesgue constants allow choosing $y_i\in\{\pm 1\}$ forcing large sup norm for the interpolant.
• Try to "robustify" the exact interpolation forcing to handle matching only $(1-\epsilon)n$ points: show that any polynomial matching many prescribed signs must have large sup due to oscillation constraints.

Disproof track ideas.

• Attempt to show that for some configurations of points, any assignment $y_i\in[-1,1]$ can be matched on most points by a degree $<(1+\epsilon)n$ polynomial with controlled sup norm.

WORK

Lemma 1133.1 (explicit interpolation formula for degree $\le n-1$). Let $x_1,\dots,x_n$ be distinct points in $\mathbb{R}$ and let $y_1,\dots,y_n\in\mathbb{R}$. Define Lagrange polynomials $l_k$ from these nodes. Then the polynomial \[ P(x):=\sum_{k=1}^n y_k\,l_k(x) \] has degree at most $n-1$ and satisfies $P(x_i)=y_i$ for every $1\le i\le n$. Moreover, it is the unique polynomial of degree at most $n-1$ with these interpolation values.

Proof. Each $l_k$ has degree $n-1$, so $P$ has degree at most $n-1$. At a node $x_i$, we have $l_k(x_i)=\delta_{ki}$, hence \[ P(x_i)=\sum_{k=1}^n y_k\delta_{ki}=y_i. \] For uniqueness, suppose $Q$ is another polynomial of degree at most $n-1$ with $Q(x_i)=y_i$ for all $i$. Then $R:=P-Q$ has degree at most $n-1$ and has $n$ distinct roots $x_1,\dots,x_n$, so $R\equiv 0$. Therefore $P\equiv Q$. $\square$

Lemma 1133.2 (forcing large sup norm via the Lebesgue constant). Let $x_1,\dots,x_n\in[-1,1]$ be distinct nodes and let \[ \Lambda:=\max_{x\in[-1,1]}\sum_{k=1}^n |l_k(x)| \] be the Lebesgue constant associated to these nodes. Choose $x^*\in[-1,1]$ where the maximum is attained and define \[ y_k:=\begin{cases} \phantom{-}1,& l_k(x^*)\ge 0,\\ -1,& l_k(x^*)<0. \end{cases} \] Let $P$ be the degree $\le n-1$ interpolant through $(x_k,y_k)$ given by Lemma 1133.1. Then \[ P(x^*)=\sum_{k=1}^n |l_k(x^*)|=\Lambda, \] and hence $\max_{x\in[-1,1]}|P(x)|\ge \Lambda$.

Proof. By construction, $y_k=\operatorname{sign}(l_k(x^*))$ (with the convention $\operatorname{sign}(0)=1$). Therefore $y_k l_k(x^*)=|l_k(x^*)|$ for every $k$, and Lemma 1133.1 gives \[ P(x^*)=\sum_{k=1}^n y_k l_k(x^*)=\sum_{k=1}^n |l_k(x^*)|=\Lambda. \] Taking absolute values and the maximum over $x$ yields $\max_{[-1,1]}|P|\ge |P(x^*)|=\Lambda$. $\square$

Interpretation. Lemma 1133.2 shows a weaker (but relevant) forcing statement: for exact interpolation by degree $\le n-1$ polynomials (the case $\epsilon=0$ and $m=n-1$), one can always choose $y_k\in\{\pm 1\}$ so that any polynomial matching all $n$ constraints (necessarily the interpolant) must have sup norm at least $\Lambda$. Since the problem file states $\Lambda\gg\log n$ for every node set (Faber), this forcing exceeds any fixed $C$ for sufficiently large $n$. What remains open in the posed problem is robustness: allowing degree up to $(1+\epsilon)n$ and allowing the polynomial to ignore $\epsilon n$ constraints.

FAST REALITY CHECK (numerical illustration). For $n=5$ equally spaced nodes $[-1,-0.5,0,0.5,1]$, the above construction gives:

nodes [-1.  -0.5  0.   0.5  1. ]
Lambda approx 2.20782438320626 at x* -0.7919
y_k [ 1.  1. -1.  1. -1.]
P sup approx 2.20782438320626 attained near -0.7919
P(x*) 2.20782438320626

This empirically confirms Lemma 1133.2 in a concrete case.

VERIFICATION

• Lemma 1133.1 is standard and gap-free: interpolation property and uniqueness via $n$ roots.
• Lemma 1133.2 depends on existence of a maximizer $x^*$, which holds because $x\mapsto \sum_k|l_k(x)|$ is continuous on compact $[-1,1]$.
• The leap from Lemma 1133.2 to the conjectured statement is nontrivial because the conjecture permits dropping $\epsilon n$ constraints and increasing degree to $(1+\epsilon)n$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For any node set $x_1,\dots,x_n$, one can choose $y_k\in\{\pm 1\}$ so that the unique interpolant of degree $\le n-1$ has $\max_{[-1,1]}|P|\ge \Lambda(x_1,\dots,x_n)$ (Lemma 1133.2).

(ii) First gap (crisp). Upgrade the exact-interpolation forcing (degree $n-1$ and matching all $n$ points) to the robust regime of the problem: degree $<(1+\epsilon)n$ and matching at least $(1-\epsilon)n$ points.

(iii) Top 3 next moves.

• Prove a robustness lemma: if a degree $m$ polynomial matches a sign pattern on many nodes, then its sup norm is bounded below in terms of a "restricted" Lebesgue constant for those nodes.
• Use quantitative bounds on how many alternations/oscillations a degree $m$ polynomial with bounded sup norm can have on $[-1,1]$, and choose $y_i$ to force more oscillation than allowed.
• Try probabilistic constructions for $y_i\in\{\pm 1\}$ and prove that with positive probability any degree-$m$ polynomial matching $>(1-\epsilon)n$ points must have large sup norm.

(iv) Minimal counterexample structure. A counterexample for a given $C$ would be a sequence of node sets $x^{(n)}_1,\dots,x^{(n)}_n$ such that for every assignment $y_i\in[-1,1]$ there exists a polynomial of degree $<(1+\epsilon)n$ matching $>(1-\epsilon)n$ constraints while keeping $\max_{[-1,1]}|P|\le C$.