## Main Question

This question is about finding *explicit*, *calculable*, and *fast* error bounds (no hidden constants) when approximating continuous functions with polynomials or simpler functions 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)$.

Suppose $f:[0,1]\to [0,1]$ is continuous and belongs to a large class of functions (for example, the $k$-th derivative, $k\ge 0$, is continuous, Lipschitz continuous, concave, strictly increasing, bounded variation, and/or in the Zygmund class, or $f$ is real analytic).

*Given $\epsilon > 0$, compute the Bernstein coefficients of a polynomial or rational function (of some degree $n$) that is within $\epsilon$ of $f$.* (*6)

The convergence rate must be $O(1/n^{r/2})$ if the class has only functions with Lipschitz-continuous $(r-1)$-th derivative. The method may not introduce transcendental or trigonometric functions (as with Chebyshev interpolants).

Without loss of generality, here are some ways to tackle this question:

- For iterated Boolean sums (linear combinations of iterates) of Bernstein polynomials ($U_{n,k}$ in
**Micchelli 1973**; see also**Güntürk and Li**), find an explicit bound, with no hidden constants, on the approximation error for functions with continuous $r$-th derivative, or verify my**proofs of these bounds in Propositions B10C and B10D**. - For linear combinations of Bernstein polynomials (Butzer 1953,
**Tachev 2022**), verify my proof of those error bounds in**my Proposition B10**. - For the "
**Lorentz operator**", find an explicit bound, with no hidden constants, on the approximation error for the operator $Q_{n,r}$ and for the polynomials $(f_n)$ and $(g_n)$ formed with it, and find the hidden constants $\theta_\alpha$, $s$, and $D$ as well as those in Lemmas 15, 17 to 22, 24, and 25 in the paper. Or verify my proof of the order-2 operator's error bounds in**my Proposition B10A**. - Let $f:[-1,1]\to [0,1]$ be continuous. Find explicit bounds, with no hidden constants, on the error in approximating $f$ with the following polynomials: The polynomials are similar to Chebyshev interpolants, but evaluate $f$ at
*rational*values of $\lambda$ that converge to Chebyshev points (that is, converging to $\cos(j\pi/n)$ with increasing $n$). The error bounds must be close to those of Chebyshev interpolants (see, e.g., chapters 7, 8, and 12 of Trefethen,, 2013).*Approximation Theory and Approximation Practice* - Find other polynomial operators meeting the requirements of the main question (see "Main Question", above) and having explicit error bounds, with no hidden constants, especially operators that preserve polynomials of a higher degree than linear functions.

### Motivation

My motivation for this question is to implement "*approximate Bernoulli factories*", or ways to toss heads with probability equal to a function that approximates another function. This question is broader in scope than my previous question.(^)

Please see my section on approximate Bernoulli factories for details on my progress in this problem. For example, the section shows how to build polynomials that answer the question if $f(\lambda)$ is Lipschitz or Hölder or has a Lipschitz-continuous derivative, but in general the polynomials have inordinate degree, for which improvements may be possible if $f(\lambda)$ is smoother or if the approximating function is other than a polynomial.

#### Approximate Bernoulli factories and polynomials with fast convergence

Approximate Bernoulli factories are 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 ($\Theta(1/n)$ unless $f$ is linear [Voronovskaya 1932]); for example, if $\epsilon=0.01$ and $f$ is Lipschitz with constant 1, the required polynomial degree is 11879. (See also a related question by Luis Mendo on ordinary Bernstein polynomials.)

Although ordinary Bernstein polynomials have slow convergence, 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 linear combinations and iterated Boolean sums of Bernstein polynomials, to improve the convergence rate. These include Micchelli (1973), Guan (2009), Güntürk and Li (2021a, 2021b), the "Lorentz operator" in Holtz et al. (2011) (see also "**New coins from old, smoothly**"), Draganov (2014), and Tachev (2022).

These alternative polynomials usually include results where the error bound is the desired $O(1/n^{k/2})$, but most of those results (e.g., Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li) have hidden constants with no upper bounds given, making them unimplementable (that is, it can't be known beforehand whether a given polynomial will come close to the target function within a user-specified error tolerance).

### Related Question

The following is related to the main question, but is also one way to answer the main question. Nice to have would be a sequence of polynomials $(g_n)$, based on linear combinations or iterated Boolean sums of Bernstein polynomials, that: (A) converge to $f(\lambda)$ from below; (B) have the rate $O(1/n^{r/2})$ if the class has only functions with a continuous $r$-th derivative; and (C) satisfy: $(g_{2n}−g_n)$ is a polynomial with non-negative Bernstein coefficients, once it's rewritten to a polynomial in Bernstein form of degree exactly $2n$.

### Notes

(^) *Exact* Bernoulli factories require a slightly different approach to finding the polynomials; see another question of mine.

(****) If the polynomials are not restricted in their coefficients, then the rate $O(1/n^k)$ is possible (e.g., DeVore and Lorentz 1993). However, my use case (approximate Bernoulli factories) requires the polynomials to have Bernstein coefficients in the closed unit interval.

(*6) More generally, the approximating function $g(\lambda)$ can have a simple algorithm that tosses heads with probability exactly equal to $g$, given a coin that shows heads with probability $\lambda$.

## References

- 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).
- 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.
- Güntürk, C. Sinan, and Weilin Li. "
**Approximation with one-bit polynomials in Bernstein form**", arXiv:2112.09183 (2021); Constructive Approximation, pp.1-30 (2022). - Güntürk, C. Sinan, and Weilin Li. "
**Approximation of functions with one-bit neural networks**", arXiv:2112.09181 (2021). - Tachev, Gancho. "
**Linear combinations of two Bernstein polynomials**",*Mathematical Foundations of Computing*, 2022. - E. Voronovskaya, "Détermination de la forme asymptotique d'approximation des fonctions par les polynômes de M. Bernstein", 1932.
- Butzer, P.L., "Linear combinations of Bernstein polynomials", Canadian Journal of Mathematics 15 (1953).