## Main Question

This question is about finding *explicit*, *calculable*, and *fast* error bounds when approximating continuous functions with polynomials to a user-specified error tolerance.

In this question:

- A polynomial $P(x)$ is written in
*Bernstein form of degree $n$*if it is written as $P(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},$ where $a_0, ..., a_n$ are the polynomial's*Bernstein coefficients*. - For the
*Bernstein polynomial*of $f(x)$ of degree $n$, $a_k = f(k/n)$.

Let $f:[0,1]\to [0,1]$ be continuous and polynomially bounded (both $f$ and $1-f$ are bounded below by min($x^n$, $n(1-x)^n$) for some integer $n$), let $r\ge 3$, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$.

Given that $f$ has a continuous $r$-th derivative (or has a Lipschitz continuous $(r-1)$-th derivative), are there results that give a sequence of polynomials $P_n$ with the following error bound?

$$| f(x) - P_n(f)(x) | \le \epsilon(f, n, x) = O(1/n^{r/2}),$$ where:

- $\epsilon(f, n, x)$ is a fully determined function, with all constants in the expression having a
**known exact value or upper bound**. - $P_n(f)(x)$ is an approximating polynomial of degree $n$ that can be readily rewritten to a polynomial in Bernstein form with coefficients in $[0, 1]$. Preferably, $P_n(f)$ has the form $B_n(W_n(f))$ where $W_n(f)$ is easily computable from $f$ using rational arithmetic only (see "Remarks", later).

One way to answer this (see this question) is to find a sequence $W_n(f)$ and an explicit and tight upper bound on $C_1>0$ such that, for each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n}\left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}},$$ where $M$ is the maximum absolute value of $f$ and its derivatives up to the $r$-th derivative (or, respectively, the maximum of $|f|$ and the Lipschitz constants of $f$ and its derivatives up to the $(r-1)$-th derivative).

Then $| f(x) - B_n(W_n(f))(x) | \le \frac{C_1}{1-\sqrt{2/2^{r+1}}}\frac{M}{n^{r/2}}=O(1/n^{r/2})$ (see Lemma 3 in "Proofs for Polynomial-Building Schemes), although this is only guaranteed to work for power-of-2 values of $n$. For example, $W_n$ can be $2f-B_n(f)$ and $r$ can be 3 or 4, or $W_n$ can be $B_n(B_n(f))+3(f-B_n(f))$ and $r$ can be 5 or 6.

### Motivation

My motivation for this question is to implement "*approximate Bernoulli factories*", or algorithms that toss heads with a probability equal to a polynomial in Bernstein form that comes within $\epsilon$ of a continuous function $f(x)$. This involves finding a reasonably small degree $n$ of that polynomial, then the algorithm works as follows:

- Flip the coin $n$ times, count the number of heads as $h$.
- With probability equal to the $h$-th Bernstein coefficient, return heads; otherwise tails.

Note that the algorithm requires finding only one Bernstein coefficient per run. And for ordinary Bernstein polynomials, finding it is trivial — $f(h/n)$ — but the degree $n$ can be inordinate due to Bernstein polynomials' slow convergence; for example, if $\epsilon=0.01$ and $f$ is Lipschitz with constant 1, the required polynomial degree is 11879.

- Approximating $f$ with a rational function is also interesting, but is outside the scope of this question.
*Exact*Bernoulli factories require a slightly different approach to finding the polynomials; see another question of mine.

### Polynomials with faster convergence than Bernstein polynomials

As is known since Voronovskaya (1932), the Bernstein polynomials converge uniformly to $f$, in general, at a rate no faster than $O(1/n)$, regardless of $f$'s smoothness, which means that it won't converge in a finite expected running time. (See also a related question by Luis Mendo on ordinary Bernstein polynomials.)

But Lorentz (1966, "The degree of approximation by polynomials with positive coefficients") has shown that if $f(x)$ is positive (the case that interests me) and has $k$ continuous derivatives, there are polynomials with non-negative Bernstein coefficients that converge to $f$ at the rate $O(1/n^{k/2})$ (and thus can be faster than the $O(1/n^{2+\epsilon})$ needed for a finite expected running time, depending on $f$).*

Thus, people have developed alternatives, including *iterated Bernstein polynomials*, to improve the convergence rate. These include:

- Micchelli, C. (1973). The saturation class and iterates of the Bernstein polynomials. Journal of Approximation Theory, 8(1), 1-18.
- Guan, Zhong. "Iterated Bernstein polynomial approximations." arXiv preprint arXiv:0909.0684 (2009).
- Güntürk, C. Sinan, and Weilin Li. "Approximation with one-bit polynomials in Bernstein form" arXiv preprint arXiv:2112.09183 (2021).
- The "Lorentz operator": Holtz, Olga, Fedor Nazarov, and Yuval Peres. "New coins from old, smoothly" Constructive Approximation 33, no. 3 (2011): 331-363.
- Draganov, Borislav R. "On simultaneous approximation by iterated Boolean sums of Bernstein operators." Results in Mathematics 66, no. 1 (2014): 21-41.

Usually, papers like those express a bound on the error when approximating a function with polynomials as follows: $$| f(x) - P_n(f)(x) | \le c_n \epsilon(f, n, x),$$ where $\epsilon(f, n, x)$ is a fully determined function, $c_n>0$ is a constant that may depend on $n$, and $P_n(f)(x)$ is an approximating polynomial of degree $n$.

There are results where the error bound $\epsilon(.)$ is in $O(1/n^{k/2})$, but in all those results I've seen so far (e.g., Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li), $c_n$ is unknown, and no upper bound for $c_n$ is given by the results in the papers above, so that the error bound is unimplementable and there is no way of knowing beforehand whether $P_n$ will come close to $f$ within a user-specified error tolerance. (There is also a separate matter of rewriting the polynomial to its Bernstein form, but this is much more manageable, especially with the Lorentz operator.)

### Remarks

I prefer approaches that involve only rational arithmetic and don't require transcendental or trigonometric functions to build the Bernstein-form polynomials.

- Unlike with rational arithmetic (where arbitrary precision is trivial thanks to Python's
`fractions`

module), transcendental and trig. functions require special measures to support arbitrary accuracy, such as constructive/recursive reals — floating point won't do for my purposes. - In general, "rounding" a polynomial's coefficients or "nodes" to rational numbers will add a non-trivial error that, for my purposes, has to be accounted for in any error bound.

- Unlike with rational arithmetic (where arbitrary precision is trivial thanks to Python's

* If the polynomials are not restricted in their coefficients, then the rate $O(1/n^k)$ is possible (e.g., DeVore and Lorentz 1993). But this result is not useful to me since my use case (approximate Bernoulli factories) requires the polynomials to have Bernstein coefficients in $[0, 1]$.