Dense samples on a cube norm and reproduce polynomials with exponential coefficient bounds

We first prove that for every real univariate polynomial $r$ of degree at most $N\ge 1$, $\mathrm{\mid }{r}^{\mathrm{\prime }}(u)\mathrm{\mid }\le \frac{100N}{\sqrt{1-u^2}}{\sup }_{-1\le v\le 1}\mathrm{\mid }r(v)\mathrm{\mid }(-1<u<1)\mathrm{.}$ For $m\ge 1$ define the finite trigonometric polynomial $F_m(t)={\sum }_{\mathrm{\mid }k\mathrm{\mid }<m}(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}m)e^{ikt}=\frac{1}{m}{\mid {\sum }_{j=0}^{m-1}{e}^{ijt}\mid }^2=\frac{{\sin }^2(mt\mathrm{/}2)}{m{\sin }^2(t\mathrm{/}2)}\mathrm{.}$ Here $i^2=-1$; the square identity follows by expanding the finite sum and counting pairs of indices with a prescribed difference, and the last identity follows from the finite geometric series, with continuous values at multiples of $2\pi$. For $\mathrm{\mid }t\mathrm{\mid }\le 1\mathrm{/}m$, differentiate the finite Fourier sum to obtain $\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }\le {\sum }_{\mathrm{\mid }k\mathrm{\mid }<m}\mathrm{\mid }k\mathrm{\mid }(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}m)\le m^2$. For $1\mathrm{/}m\le \mathrm{\mid }t\mathrm{\mid }\le \pi$, differentiating the sine quotient gives $\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }\le \frac{{\pi }^2}{t^2}+\frac{{\pi }^3}{m\mathrm{\mid }t{\mathrm{\mid }}^3},$ because $\mathrm{\mid }\sin (t\mathrm{/}2)\mathrm{\mid }\ge \mathrm{\mid }t\mathrm{\mid }\mathrm{/}\pi$. This sine bound follows on $[0,\pi \mathrm{/}2]$ by concavity of sine, whose second derivative is $-\sin \le 0$, applied to the chord joining $(0,0)$ and $(\pi \mathrm{/}2,1)$; symmetry gives the negative arguments.

Put $Q=[-1,1{]}^d$ and $Q_c=[-1\mathrm{/}2,1\mathrm{/}2{]}^d$. For a univariate polynomial of degree at most $n$, interpolate at $t_j=-1\mathrm{/}2+j\mathrm{/}n$ for $0\le j\le n$. The interpolation identity holds because its difference from the polynomial has degree at most $n$ and $n+1$ distinct roots; the root bound follows by successively factoring each distinct root. For $\mathrm{\mid }t\mathrm{\mid }\le 1$ the absolute value of the $j$th Lagrange polynomial is at most $(3\mathrm{/}2{)}^n{n}^n\mathrm{/}(j!(n-j)!)$: numerator factors are at most $3\mathrm{/}2$ and its denominator has absolute value $n^{-n}j!(n-j)!$. Summing these bounds gives $(3n{)}^n\mathrm{/}n!\le (3e{)}^n$, where $\log (n!)={\sum }_{j=1}^n\log j\ge {\int }_1^n\log tdt=n\log n-n+1$ proves $n!\ge (n\mathrm{/}e{)}^n$. Applying this univariate estimate in each coordinate in turn, and taking suprema after each application, shows for every polynomial $p$ of total degree at most $n$ that $\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le R^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c},R=(3e{)}^d,$ since its degree in each separate coordinate is at most $n$. Here and below $\mathrm{\parallel }p{\mathrm{\parallel }}_E={\sup }_{z\in E}\mathrm{\mid }p(z)\mathrm{\mid }$.

Integrating the bounds of step 1.1 over $[-\pi ,\pi ]$, with the near-zero interval contributing at most $2m$ and the other terms bounded by extending their elementary integrals to infinity, gives $\frac{1}{2\pi }{\int }_{-\pi }^{\pi }\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }dt\le \frac{2+2{\pi }^2+{\pi }^3}{2\pi }m\le 20m\mathrm{.}$ For $m=1$ this also holds because $F_1=1$. Define $V_N=2F_{2N}-F_N$. Its Fourier coefficients for every $\mathrm{\mid }k\mathrm{\mid }\le N$ equal $1$: for $\mathrm{\mid }k\mathrm{\mid }<N$ they are $2(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}(2N))-(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}N)$, and for $\mathrm{\mid }k\mathrm{\mid }=N$ they are $2(1\mathrm{/}2)$. For any trigonometric polynomial $T$ of degree at most $N$, integration of finite sums, using ${\int }_{-\pi }^{\pi }{e}^{ikt}dt=0$ for nonzero integer $k$ and $2\pi$ for $k=0$, therefore gives $T(t)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }T(s)V_N(t-s)ds\mathrm{.}$ Differentiating this finite-sum identity and using periodicity and the integral bound yields $\mathrm{\parallel }{T}^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}\le 100N\mathrm{\parallel }T{\mathrm{\parallel }}_{\mathrm{\infty }}$. Taking $T(t)=r(\cos t)$, a trigonometric polynomial of degree at most $N$ by expansion of powers of cosine, and using $T^{\mathrm{\prime }}(t)=-\sin (t)r^{\mathrm{\prime }}(\cos t)$ proves the inequality announced in step 1.1. All integrals here integrate continuous finite trigonometric sums or the displayed elementary bounds.

Define constants depending only on $d$ by $a=(3\mathrm{/}4{)}^d,\delta =\min \{1\mathrm{/}4,a\mathrm{/}(8R)\},G=600\sqrt{d}\mathrm{/}\sqrt{\delta },\kappa =\min \{\delta \mathrm{/}2,1\mathrm{/}(2G)\},A=2R\mathrm{/}a\mathrm{.}$ Let $Y\subset Q$ be finite and nonempty with Euclidean fill distance $\eta$ and $n\eta \le \kappa$. The zero polynomial satisfies the desired inequality, so fix nonzero $p$ of degree at most $n$ and set $q(u)=p(u){\prod }_{i=1}^d(1-u_i^2{)}^n,S=\mathrm{\parallel }q{\mathrm{\parallel }}_Q,M={\max }_{y\in Y}\mathrm{\mid }p(y)\mathrm{\mid }\mathrm{.}$ The coordinate degrees of $q$ are at most $3n$. On $Q_c$ its product weight is at least $a^n$, so $S\ge a^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}>0$. The last inequality holds because a polynomial vanishing on a box with nonempty interior vanishes identically: fix all but one coordinate in the interior and apply the univariate root bound, then repeat in each coordinate. If some $\mathrm{\mid }{u}_i\mathrm{\mid }\ge 1-\delta$, then $1-u_i^2\le 2\delta$ while all other weight factors are at most $1$, and step 1.2 implies $\mathrm{\mid }q(u)\mathrm{\mid }\le (2\delta {)}^n\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le (2\delta R{)}^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}\le (1\mathrm{/}4{)}^{n}S<S\mathrm{.}$ The maximum of $\mathrm{\mid }q\mathrm{\mid }$ is attained on $Q$ by compactness and the extreme value theorem, so a maximizer $u_{\ast }$ lies in $[-1+\delta ,1-\delta {]}^d$.

Take $y\in Y$ with $\mathrm{\parallel }y-u_{\ast }{\mathrm{\parallel }}_2\le \eta$; such a point exists because the minimum over the finite set is attained and is at most its supremum $\eta$. Since $\eta \le \kappa \le \delta \mathrm{/}2$, the segment from $u_{\ast }$ to $y$ lies where every coordinate has absolute value at most $1-\delta \mathrm{/}2$. Apply step 2.1 to each univariate coordinate slice of $q$, of degree at most $3n$ and norm at most $S$ on $[-1,1]$. At each point of this segment it gives $\mathrm{\mid }{\mathrm{\partial }}_{i}q\mathrm{\mid }\le \frac{300nS}{\sqrt{\delta -{\delta }^2\mathrm{/}4}}\le \frac{600nS}{\sqrt{\delta }},\mathrm{\parallel }\mathrm{\nabla }q{\mathrm{\parallel }}_2\le GnS\mathrm{.}$ Apply the fundamental theorem of calculus to the univariate polynomial $t\mapsto q(u_{\ast }+t(y-u_{\ast }))$: it follows directly here by integrating each power in this finite polynomial. With the Euclidean Cauchy–Schwarz inequality, obtained by expanding ${\sum }_i(v_i-s{w}_i{)}^2\ge 0$ and minimizing the quadratic in $s$, this gives $S\le \mathrm{\mid }q(y)\mathrm{\mid }+Gn\eta S\le M+S\mathrm{/}2.$ Thus $S\le 2M$, and steps 1.2 and 2.2 yield $\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le R^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}\le (R\mathrm{/}a{)}^{n}S\le 2(R\mathrm{/}a{)}^{n}M\le A^{n}M\mathrm{.}$ This also includes the zero polynomial.

Fix $x\in Q$, enumerate $Y=\{y_1,\dots ,y_m\}$, and let $v(u)\in {\mathbb{R}}^D$ be the vector of all monomials in $u$ of total degree at most $n$, in any fixed order, where $D$ is their finite number. Let $K$ be the convex hull of $\{v(y_j),-v(y_j):1\le j\le m\}$. More explicitly it is the image of the closed bounded simplex of $2m$ nonnegative real coordinates summing to $1$, under the continuous map taking these coordinates to the corresponding weighted sum of these $2m$ vectors. Thus $K$ is nonempty and compact, and is convex because convex combinations of two sets of simplex weights remain simplex weights. Suppose $v(x)\mathrm{\notin }{A}^{n}K$. The continuous squared distance from $v(x)$ attains a minimum at some $z\in A^{n}K$; put $b=v(x)-z\mathrm{\ne }0$. For each $w\in A^{n}K$ the segment $z+t(w-z)$, $0\le t\le 1$, lies in $A^{n}K$. Its squared distance to $v(x)$ equals $\mathrm{\parallel }b{\mathrm{\parallel }}_2^2-2tb\cdot (w-z)+t^2\mathrm{\parallel }w-z{\mathrm{\parallel }}_2^2\mathrm{.}$ Minimality at $t=0$ forces $b\cdot (w-z)\le 0$, since a strictly positive value would make this displayed expression smaller for sufficiently small positive $t$.

Therefore $b\cdot z$ is the maximum of the linear functional $b\cdot w$ on $A^{n}K$. A linear functional on this convex hull has maximum equal to the largest of its values on its finite generators: every convex weighted average is at most that largest value and that value is attained at a generator. Consequently $b\cdot v(x)=b\cdot z+\mathrm{\parallel }b{\mathrm{\parallel }}_2^2>A^n{\max }_{1\le j\le m}\mathrm{\mid }b\cdot v(y_j)\mathrm{\mid }\mathrm{.}$ This contradicts step 3.1 applied to the polynomial $u\mapsto b\cdot v(u)$, because $x\in Q$. Thus $v(x)\in A^{n}K$. Write it as $A^n$ times a convex combination of the vectors $\pm v(y_j)$, with nonnegative weights $t_j^{+},t_j^{-}$ summing to $1$. For ${\lambda }_j=A^n(t_j^{+}-t_j^{-})$ one has $v(x)={\sum }_j{\lambda }_{j}v(y_j),{\sum }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid }\le A^n{\sum }_j(t_j^{+}+t_j^{-})=A^n\mathrm{.}$ Taking the scalar product with the coefficient vector of any polynomial of degree at most $n$ proves simultaneous reproduction. This argument uses finite-dimensional compactness and a single minimum, without an infinite choice principle.

Finally choose orthonormal coordinates along the edges of $\mathrm{\Omega }$, with its center as origin, and multiply these coordinates by $2\mathrm{/}L$. This affine map carries $\mathrm{\Omega }$ to $Q$ and scales Euclidean distances by $2\mathrm{/}L$, so it carries $X$ to a set $Y$ of fill distance $\eta =2h_X\mathrm{/}L$. Composition in either direction preserves total polynomial degree because each coordinate is affine linear. The condition in the Statement is exactly $n\eta \le \kappa$. Transporting the norming inequality from step 3.1 and the coefficients from step 5.1 proves both assertions on $\mathrm{\Omega }$, including rotated cubes. All selections made in the proof are finite or individual existential choices, so no choice axiom is used.