No Arabic abstract
Given a nondecreasing function $f$ on $[-1,1]$, we investigate how well it can be approximated by nondecreasing algebraic polynomials that interpolate it at $pm 1$. We establish pointwise estimates of the approximation error by such polynomials that yield interpolation at the endpoints (i.e., the estimates become zero at $pm 1$). We call such estimates interpolatory estimates. In 1985, DeVore and Yu were the first to obtain this kind of results for monotone polynomial approximation. Their estimates involved the second modulus of smoothness $omega_2(f,cdot)$ of $f$ evaluated at $sqrt{1-x^2}/n$ and were valid for all $nge1$. The current paper is devoted to proving that if $fin C^r[-1,1]$, $rge1$, then the interpolatory estimates are valid for the second modulus of smoothness of $f^{(r)}$, however, only for $nge N$ with $N= N(f,r)$, since it is known that such estimates are in general invalid with $N$ independent of $f$. Given a number $alpha>0$, we write $alpha=r+beta$ where $r$ is a nonnegative integer and $0<betale1$, and denote by $Lip^*alpha$ the class of all functions $f$ on $[-1,1]$ such that $omega_2(f^{(r)}, t) = O(t^beta)$. Then, one important corollary of the main theorem in this paper is the following result that has been an open problem for $alphageq 2$ since 1985: If $alpha>0$, then a function $f$ is nondecreasing and in $Lip^*alpha$, if and only if, there exists a constant $C$ such that, for all sufficiently large $n$, there are nondecreasing polynomials $P_n$, of degree $n$, such that [ |f(x)-P_n(x)| leq C left(frac{sqrt{1-x^2}}{n}right)^alpha, quad xin [-1,1]. ]
This paper deals with approximation of smooth convex functions $f$ on an interval by convex algebraic polynomials which interpolate $f$ at the endpoints of this interval. We call such estimates interpolatory. One important corollary of our main theorem is the following result on approximation of $fin Delta^{(2)}$, the set of convex functions, from $W^r$, the space of functions on $[-1,1]$ for which $f^{(r-1)}$ is absolutely continuous and $|f^{(r)}|_{infty} := ess,sup_{xin[-1,1]} |f^{(r)}(x)| < infty$: For any $fin W^r capDelta^{(2)}$, $rin {mathbb N}$, there exists a number ${mathcal N}={mathcal N}(f,r)$, such that for every $nge {mathcal N}$, there is an algebraic polynomial of degree $le n$ which is in $Delta^{(2)}$ and such that [ left| frac{f-P_n}{varphi^r} right|_{infty} leq frac{c(r)}{n^r} left| f^{(r)}right|_{infty} , ] where $varphi(x):= sqrt{1-x^2}$. For $r=1$ and $r=2$, the above result holds with ${mathcal N}=1$ and is well known. For $rge 3$, it is not true, in general, with ${mathcal N}$ independent of $f$.
For a polynomial $P$ mapping the integers into the integers, define an averaging operator $A_{N} f(x):=frac{1}{N}sum_{k=1}^N f(x+P(k))$ acting on functions on the integers. We prove sufficient conditions for the $ell^{p}$-improving inequality begin{equation*} |A_N f|_{ell^q(mathbb{Z})} lesssim_{P,p,q} N^{-d(frac{1}{p}-frac{1}{q})} |f|_{ell^p(mathbb{Z})}, qquad N inmathbb{N}, end{equation*} where $1leq p leq q leq infty$. For a range of quadratic polynomials, the inequalities established are sharp, up to the boundary of the allowed pairs of $(p,q)$. For degree three and higher, the inequalities are close to being sharp. In the quadratic case, we appeal to discrete fractional integrals as studied by Stein and Wainger. In the higher degree case, we appeal to the Vinogradov Mean Value Theorem, recently established by Bourgain, Demeter, and Guth.
Given a function $uin L^2=L^2(D,mu)$, where $Dsubset mathbb R^d$ and $mu$ is a measure on $D$, and a linear subspace $V_nsubset L^2$ of dimension $n$, we show that near-best approximation of $u$ in $V_n$ can be computed from a near-optimal budget of $Cn$ pointwise evaluations of $u$, with $C>1$ a universal constant. The sampling points are drawn according to some random distribution, the approximation is computed by a weighted least-squares method, and the error is assessed in expected $L^2$ norm. This result improves on the results in [6,8] which require a sampling budget that is sub-optimal by a logarithmic factor, thanks to a sparsification strategy introduced in [17,18]. As a consequence, we obtain for any compact class $mathcal Ksubset L^2$ that the sampling number $rho_{Cn}^{rm rand}(mathcal K)_{L^2}$ in the randomized setting is dominated by the Kolmogorov $n$-width $d_n(mathcal K)_{L^2}$. While our result shows the existence of a randomized sampling with such near-optimal properties, we discuss remaining issues concerning its generation by a computationally efficient algorithm.
Limits on the number of satisfying assignments for CNS instances with n variables and m clauses are derived from various inequalities. Some bounds can be calculated in polynomial time, sharper bounds demand information about the distribution of the number of unsatisfied clauses. Quite generally, the number of satisfying assignments involve variance and mean of this distribution. For large formulae, m>>1, bounds vary with 2**n/n, so they may be of use only for instances with a large number of satisfying assignments.
We investigate the dispersive properties of solutions to the Schrodinger equation with a weakly decaying radial potential on cones. If the potential has sufficient polynomial decay at infinity, then we show that the Schrodinger flow on each eigenspace of the link manifold satisfies a weighted $L^1to L^infty$ dispersive estimate. In odd dimensions, the decay rate we compute is consistent with that of the Schrodinger equation in a Euclidean space of the same dimension, but the spatial weights reflect the more complicated regularity issues in frequency that we face in the form of the spectral measure. In even dimensions, we prove a similar estimate, but with a loss of $t^{1/2}$ compared to the sharp Euclidean estimate.