Note

Arb was merged into FLINT in 2023.

The documentation on arblib.org will no longer be updated.

See the FLINT documentation instead.

General formulas and bounds

This section collects some results from real and complex analysis that are useful when deriving error bounds. Beware of typos.

Error propagation

We want to bound the error when \(f(x+a)\) is approximated by \(f(x)\). Specifically, the goal is to bound \(f(x + a) - f(x)\) in terms of \(r\) for the set of values \(a\) with \(|a| \le r\). Most bounds will be monotone increasing with \(|a|\) (assuming that \(x\) is fixed), so for brevity we simply express the bounds in terms of \(|a|\).

Theorem (generic first-order bound):

\[|f(x+a) - f(x)| \le \min(2 C_0, C_1 |a|)\]

where

\[C_0 = \sup_{|t| \le |a|} |f(x+t)|, \quad C_1 = \sup_{|t| \le |a|} |f'(x+t)|.\]

The statement is valid with either \(a, t \in \mathbb{R}\) or \(a, t \in \mathbb{C}\).

Theorem (product): For \(x, y \in \mathbb{C}\) and \(a, b \in \mathbb{C}\),

\[\left| (x+a)(y+b) - x y \right| \le |xb| + |ya| + |ab|.\]

Theorem (quotient): For \(x, y \in \mathbb{C}\) and \(a, b \in \mathbb{C}\) with \(|b| < |y|\),

\[\left| \frac{x}{y} - \frac{x+a}{y+b} \right| \le \frac{|xb|+|ya|}{|y| (|y|-|b|)}.\]

Theorem (square root): For \(x, a \in \mathbb{R}\) with \(0 \le |a| \le x\),

\[\left| \sqrt{x+a} - \sqrt{x} \right| \le \sqrt{x} \left(1 - \sqrt{1-\frac{|a|}{x}}\right) \le \frac{\sqrt{x}}{2} \left(\frac{|a|}{x} + \frac{|a|^2}{x^2}\right)\]

where the first inequality is an equality if \(a \le 0\). (When \(x = a = 0\), the limiting value is 0.)

Theorem (reciprocal square root): For \(x, a \in \mathbb{R}\) with \(0 \le |a| < x\),

\[\left| \frac{1}{\sqrt{x+a}} - \frac{1}{\sqrt{x}} \right| \le \frac{|a|}{2 (x-|a|)^{3/2}}.\]

Theorem (k-th root): For \(k > 1\) and \(x, a \in \mathbb{R}\) with \(0 \le |a| \le x\),

\[\left| (x+a)^{1/k} - x^{1/k} \right| \le x^{1/k} \min\left(1, \frac{1}{k} \, \log\left(1+\frac{|a|}{x-|a|}\right)\right).\]

Proof: The error is largest when \(a = -r\) is negative, and

\[ \begin{align}\begin{aligned}x^{1/k} - (x-r)^{1/k} &= x^{1/k} [1 - (1-r/x)^{1/k}]\\&= x^{1/k} [1 - \exp(\log(1-r/x)/k)] \le x^{1/k} \min(1, -\log(1-r/x)/k)\\&= x^{1/k} \min(1, \log(1+r/(x-r))/k).\end{aligned}\end{align} \]

Theorem (sine, cosine): For \(x, a \in \mathbb{R}\), \(|\sin(x+a) - \sin(x)| \le \min(2, |a|)\).

Theorem (logarithm): For \(x, a \in \mathbb{R}\) with \(0 \le |a| < x\),

\[|\log(x+a) - \log(x)| \le \log\left(1 + \frac{|a|}{x-|a|}\right),\]

with equality if \(a \le 0\).

Theorem (exponential): For \(x, a \in \mathbb{R}\), \(|e^{x+a} - e^x| = e^x (e^a-1) \le e^x (e^{|a|}-1)\), with equality if \(a \ge 0\).

Theorem (inverse tangent): For \(x, a \in \mathbb{R}\),

\[|\operatorname{atan}(x+a) - \operatorname{atan}(x)| \le \min(\pi, C_1 |a|).\]

where

\[C_1 = \sup_{|t| \le |a|} \frac{1}{1 + (x+t)^2}.\]

If \(|a| < |x|\), then \(C_1 = (1 + (|x| - |a|)^2)^{-1}\) gives a monotone bound.

An exact bound: if \(|a| < |x|\) or \(|x(x+a)| < 1\), then

\[|\operatorname{atan}(x+a) - \operatorname{atan}(x)| = \operatorname{atan}\left(\frac{|a|}{1 + x(x+a)}\right).\]

In the last formula, a case distinction has to be made depending on the signs of x and a.

Sums and series

Theorem (geometric bound): If \(|c_k| \le C\) and \(|z| \le D < 1\), then

\[\left| \sum_{k=N}^{\infty} c_k z^k \right| \le \frac{C D^N}{1 - D}.\]

Theorem (integral bound): If \(f(x)\) is nonnegative and monotone decreasing, then

\[\int_N^{\infty} f(x) \le \sum_{k=N}^{\infty} f(k) \le f(N) + \int_N^{\infty} f(x) dx.\]

Complex analytic functions

Theorem (Cauchy’s integral formula): If \(f(z) = \sum_{k=0}^{\infty} c_k z^k\) is analytic (on an open subset of \(\mathbb{C}\) containing the disk \(D = \{ z : |z| \le R \}\) in its interior, where \(R > 0\)), then

\[c_k = \frac{1}{2\pi i} \int_{|z|=R} \frac{f(z)}{z^{k+1}}\, dz.\]

Corollary (derivative bound):

\[|c_k| \le \frac{C}{R^k}, \quad C = \max_{|z|=R} |f(z)|.\]

Corollary (Taylor series tail): If \(0 \le r < R\) and \(|z| \le r\), then

\[\left|\sum_{k=N}^{\infty} c_k z^k\right| \le \frac{C D^N}{1-D}, \quad D = \left|\frac{r}{R}\right|.\]

Euler-Maclaurin formula

Theorem (Euler-Maclaurin): If \(f(t)\) is \(2M\)-times differentiable, then

\[\sum_{k=L}^U f(k) = S + I + T + R\]

\[S = \sum_{k=L}^{N-1} f(k), \quad I = \int_N^U f(t) dt,\]

\[T = \frac{1}{2} \left( f(N) + f(U) \right) + \sum_{k=1}^M \frac{B_{2k}}{(2k)!} \left(f^{(2k-1)}(U) - f^{(2k-1)}(N)\right),\]

\[R = -\int_N^U \frac{B_{2M}(t - \lfloor t \rfloor)}{(2M)!} f^{(2M)}(t) dt.\]

Lemma (Bernoulli polynomials): \(|B_n(t - \lfloor t \rfloor)| \le 4 n! / (2 \pi)^n\).

Theorem (remainder bound):

\[|R| \le \frac{4}{(2\pi)^{2M}} \int_N^U \left| f^{(2M)}(t) \right| dt.\]

Theorem (parameter derivatives): If \(f(t) = f(t,x) = \sum_{k=0}^{\infty} a_k(t) x^k\) and \(R = R(x) = \sum_{k=0}^{\infty} c_k x^k\) are analytic functions of \(x\), then

\[|c_k| \le \frac{4}{(2\pi)^{2M}} \int_N^U |a_k^{(2M)}(t)| dt.\]