We determine the optimal exponential scale in Erd\H{o}s's robust polynomial interpolation problem and identify the leading exponential coefficient for Chebyshev--Lobatto grids. Given $C>0$ and $0\le\rho<1$, put $H=C/(1-\rho)$. We prove that every configuration of $n\ge n_0$ nodes in $[-1,1]$ admits sign data for which every polynomial of degree at most $(1+\epsilon)n$ and uniform norm at most $C$ has error greater than $\rho$ at more than $\epsilon n$ nodes. One may choose $\epsilon\ge e^{-A(1+H)}$ and $n_0\le e^{A(1+H)}$, where $A$ is an absolute constant, and a matching upper bound shows that the exponential order is optimal. For the same obstruction restricted to Chebyshev--Lobatto grids, the optimal parameter $\epsilon_{\mathrm{Ch}}(C,\rho)$ satisfies $\log(1/\epsilon_{\mathrm{Ch}}(C,\rho))=\frac{\pi}{2}H+O(\log(H+1))$ as $H\to\infty$. The proofs combine finite interpolation estimates in Bernstein spaces with periodic sign constructions and averaging. We also establish obstructions for random signs and stability under angular perturbations of the nodes.
We prove that, for every real Lipschitz function $A$ and every integer $n\ge1$, $\|T_{A,n}\|_{L^2(\mathbb{R})\to L^2(\mathbb{R})}\le C\,\|A'\|_\infty^n$, where $T_{A,n}$ is the $n$-th Calder\'on commutator and $C$ is an absolute constant. The essential tool is the Coifman--McIntosh--Meyer theorem, applied to a holomorp...
Joan Hernández, Joan Mateu, Laura Prat· 0 citations
The Brown--Erd\H{o}s--S\'os problem is a fundamental problem in sparse hypergraph Tur\'an theory. For integers $r,k\ge 2$ and $s\ge r$, the problem asks for the maximum number $f^{(r)}(n;s,k)$ of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ distinct edges spanning at most $s$ vertices. In 1971, Brown...
For a compact set $K\subset\mathbb{C}$, let $\vartheta(K)$ be the infimum of the planar areas of the unit lemniscates of all monic polynomials with zeros in $K$, allowing arbitrary degree and repeated zeros. We prove that $\vartheta(K)=0$ whenever $\operatorname{cap}(K)=1$, with no regularity assumption on $K$. The pro...
We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $\kappa$, to any relative residual tolerance $0<\epsilon\le1/2$ using $\widetilde{O(}mn\log(\kappa/\epsilon))$ bit operations for inputs with logarithmically...
For $1\le p<\infty$, $\varphi_p$ is the function of minimal $L^p$ norm among all functions $f$ of exponential type at most $\pi$ for which $f(0)=1$. We start from the ansatz that the positive zeros $\tau_n$ of $\varphi_p$ are close to \(n+1/p-1/2\) and use a weighted convex correction to first place them in an \(\ell^2...
A. Bondarenko, Joaquim Ortega-Cerdà, Kristian Seip· 0 citations
We resolve the Rademacher singularity conjecture: an $n\times n$ matrix with independent uniform $\{-1,1\}$ entries is singular with probability $(2+o(1))n^22^{-n}$. More generally, for an $n\times n$ matrix $M_n$ with independent entries uniform on a fixed set $S\subset\mathbb{R}$ of cardinality $q\ge2$, we prove $\ma...
