Skip to content

Erdős problem 1133

Must every sufficiently large node set admit bounded labels that force any polynomial fitting almost all labels at degree below (1+ε)n(1+\varepsilon)n to have arbitrarily large uniform norm? Claimed via Beurling density for Bernstein spaces.

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1133.lean

Retained formal statement2 of 2

Erdős proved that, for any C>0C>0, there exists ϵ>0\epsilon>0 such that if nn is sufficiently large and m=⌊(1+ϵ)n⌋m=\lfloor (1+\epsilon)n\rfloor then for any x1,…,xm∈[−1,1]x_1,\ldots,x_m\in [-1,1] there is a polynomial PP of degree nn such that ∣P(xi)∣≤1\lvert P(x_i)\rvert\leq 1 for 1≤i≤m1\leq i\leq m and max⁡x∈[−1,1]∣P(x)∣>C\max_{x\in [-1,1]}\lvert P(x)\rvert>C. The conjectured statement would also imply this, but Erdős in [Er67] says he could not even prove it for m=nm=n.

FormalConjectures/ErdosProblems/1133.leanErdos1133.erdos_1133.variants.weaker8 linesExact file
∀ C > 0,  ∃ ε > 0,    ∀ᶠ (n : ℕ) in Filter.atTop,      have m := ⌊(1 + ε) * ↑n⌋₊;      ∀ (x : Fin m → ↑(Set.Icc (-1) 1)),        ∃ P,          P.natDegree = n ∧            (∀ (i : Fin m), |Polynomial.eval (↑(x i)) P| ≤ 1) ∧ ∃ z ∈ Set.Icc (-1) 1, |Polynomial.eval z P| > C
SolvedStatement only, no proof