Newman's theorem

Newman's theorem is a result in approximation theory describing the optimal rate at which the absolute-value function can be uniformly approximated by rational functions. It establishes that rational approximation of (x\mapsto |x|) on ([-1,1]) has root-exponential convergence, in contrast with the algebraic convergence obtained from polynomial approximation.

For each nonnegative integer (n), let (\mathcal R_{n,n}) denote the set of real rational functions

[ r(x)=\frac{p(x)}{q(x)}, ]

where (p) and (q) are polynomials of degree at most (n), and (q) has no zeros on ([-1,1]). Define the minimax error

[ E_n(|x|)

\inf_{r\in\mathcal R_{n,n}} \max_{-1\le x\le 1}\bigl||x|-r(x)\bigr|. ]

The theorem states that there are positive absolute constants (c_1,c_2,C_1,C_2) such that

[ C_1 e^{-c_1\sqrt n} \le E_n(|x|) \le C_2 e^{-c_2\sqrt n}. ]

Thus,

[ E_n(|x|)=e^{-\Theta(\sqrt n)}. ]

A standard normalization of the original estimates gives, above a fixed absolute degree threshold,

[ \frac12 e^{-9\sqrt n} \le E_n(|x|) \le 3e^{-\sqrt n}. ]

The constants in these inequalities are not asymptotically optimal. Their significance lies in the matching dependence on (\sqrt n), which identifies the convergence rate independently of constant factors.

Historical formulation

Donald J. Newman established the theorem in his 1964 paper “Rational approximation to (|x|).” The published argument combined Newman's explicit rational construction with an interval-product estimate derived by You Watanabe. Watanabe's estimate controlled the behavior of the construction between geometrically spaced nodes near the origin, where the nonanalyticity of (|x|) determines the approximation rate.

The theorem resolved a qualitative distinction between polynomial and rational approximation. The best uniform polynomial approximation to (|x|) has error of order (n^{-1}), a consequence of the corner at (x=0). Rational functions can place poles outside the approximation interval, allowing their behavior to reflect the nearby complex-analytic obstruction more efficiently. The resulting convergence is faster than every inverse power of (n), but slower than geometric convergence of the form (e^{-cn}).

The later development of the subject refined the constants without changing this root-exponential classification. Andrei Gonchar connected the problem with logarithmic potential theory and the distribution of poles in extremal rational approximation. Herbert Stahl subsequently determined the sharp asymptotic behavior,

[ E_n(|x|)\sim 8e^{-\pi\sqrt n} \qquad (n\to\infty). ]

This formula identifies both the exponential constant (\pi) and the leading multiplicative factor (8).

Upper-bound construction

The constructive part of the theorem uses zeros placed on a geometric scale approaching the singular point. With

[ \alpha=e^{-1/\sqrt n}, ]

consider the polynomial

[ p_n(x)=\prod_{k=1}^{n-1}(x+\alpha^k). ]

A corresponding rational function is

[ r_n(x)

x, \frac{p_n(x)-p_n(-x)} {p_n(x)+p_n(-x)}. ]

The numerator and denominator have the parity required to make (r_n) an even function, consistent with the symmetry of (|x|). On the nonnegative half-interval, comparison with the target reduces to an estimate involving the ratio (p_n(-x)/p_n(x)). Symmetry then extends the same estimate to the negative half-interval.

The factors in (p_n) generate transition scales near

[ \alpha,\alpha^2,\ldots,\alpha^{n-1}. ]

Their logarithms are approximately equally spaced, so the construction allocates an increasing concentration of resolution near (x=0). The product estimate bounds the approximation error separately between consecutive scales and yields

[ |,|x|-r_n(x),|_{\infty,[-1,1]} \le 3e^{-\sqrt n} ]

under the original normalization. The same construction illustrates why geometric pole or zero clustering arises in rational approximation of functions with branch-point or corner singularities.

Lower bound

The lower bound excludes any convergence rate of the form (e^{-cn}) for fixed-degree numerator and denominator constraints. Its proof translates a hypothetical approximation of (|x|) into a rational approximation of the sign function away from a small neighborhood of the origin.

Since

[ |x|=x,\operatorname{sgn}(x) ]

for (x\ne 0), an approximation with uniform error (\varepsilon) produces tight control of the associated sign approximation whenever (|x|) is appreciably larger than (\varepsilon). Complex-analytic estimates then relate the attainable error to the degree and to the logarithmic separation between the two real subintervals. Optimizing the size of the excluded neighborhood gives a bound proportional to

[ e^{-c\sqrt n}. ]

The square-root exponent results from balancing two quantities. A smaller omitted neighborhood improves the reconstruction of (|x|), while increasing the analytic difficulty of separating the positive and negative portions of the interval. The optimal balance occurs when the logarithmic scale of the neighborhood is proportional to (\sqrt n).

Analytic interpretation

The function (|x|) is continuous on ([-1,1]), but it is not differentiable at the origin and has no single-valued holomorphic continuation through that point. Polynomial approximants cannot reproduce this local singularity through adjustable finite poles, and their minimax error therefore decreases only algebraically.

Rational approximants introduce poles whose locations depend on (n). For near-optimal approximants, these poles accumulate outside the interval and toward the singularity in a structured pattern. Their collective effect represents the branch behavior associated with

[ |x|=\sqrt{x^2}. ]

Only (O(\sqrt n)) effective logarithmic scales contribute independently near the origin. This scale count accounts for the exponent (\sqrt n), while the equilibrium distribution governing asymptotically optimal poles produces the sharp constant (\pi).

Newman's theorem is therefore a model result for rational approximation near isolated singularities. It separates the influence of smooth behavior on most of the interval from the local complex geometry around the singular point.