A conjecture on consistent monotone sequences of polynomials in Bernstein form

Question

A Conjecture

In the following, 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. The degree-$n$ Bernstein polynomial of an arbitrary function $f(\lambda)$ has Bernstein coefficients $f(k/n)$. In general, this Bernstein polynomial differs from $f$ even if $f$ is a polynomial.

Let $f(\lambda):[0,1]\to(0,1)$ have $r\ge 1$ continuous derivatives, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$. Let $W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ be a sequence of functions on [0, 1] that converge uniformly to $f$.

For each integer $n\ge 1$ that's a power of 2, suppose that there is $D>0$ such that— $$|f(\lambda)-B_n(W_n(\lambda))| \le DM/n^{r/2},$$ whenever $0\le \lambda\le 1$ and $M$ is the maximum absolute value of $f$ and its derivatives up to the $r$-th derivative.

Then, a conjecture is that there is $C_0\ge D$ such that for every $C\ge C_0$, there are polynomials $g_n$ and $h_n$ (for each $n\ge 1$) as follows:

1. $g_n$ and $h_n$ have Bernstein coefficients $W_n(k/n) - CM/n^{r/2}$ and $W_n(k/n) + CM/n^{r/2}$, respectively ($0\le k\le n$), if $n$ is a power of 2, and $g_n=g_{n-1}$ and $h_n=h_{n-1}$ otherwise;
2. $\lim_n g_n =\lim_n h_n=f$;
3. $(g_{n+1}-g_{n})$ and $(h_{n}-h_{n+1})$ are polynomials with non-negative Bernstein coefficients once they are rewritten to polynomials in Bernstein form of degree exactly $n+1$.

(2 and 3 correspond to the formal statement above.)

Equivalently (see also Nacu and Peres 2005), there is $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}}.$$

It is also conjectured that the same value of $C_0$ (or $C_1$) suffices when $f$ has a Lipschitz continuous $(r-1)$-th derivative and $M$ is the maximum absolute value of $f$ and the Lipschitz constants of $f$ and its derivatives up to the $(r-1)$-th derivative.

Without loss of generality: For what value of $C_0$ is the conjecture true when $W_n = 2 f - B_n(f)$ and $r$ is 3 or 4? When $W_n$ is arbitrary?

Background

I asked this question in order to solve the so-called Bernoulli factory problem, described next. We're given a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads with a probability that depends on $\lambda$, call it $f(\lambda)$. This is the Bernoulli factory problem, and it can be solved only if $f$ is continuous (Keane and O'Brien 1994).

However, since I asked this question I have found a Bernoulli factory algorithm that I believe is general enough to cover all the cases that this conjecture would help solve.

Since this conjecture may be of broader interest, though, I leave this question open. See also my other open questions about the Bernoulli factory problem.

Results

Here are results that correspond to the conjecture.

• If $r=1$ and $W_n=f$, then $C_0 = (1+\sqrt{2})$ (Nacu and Peres 2005), even in the Lipschitz case.
• If $r=2$ and $W_n=f$, then $C_0 = 1/2$ (Nacu and Peres 2005).
• If $r=2$ and $W_n=f$, then $C_0 = 1/7$ for every $n\ge 4$ (see "Proofs for Polynomial Building Schemes").

Here are some conjectured results (for others see "A Conjecture on Polynomial Approximation"). They relate to polynomials that achieve a better convergence rate than Bernstein polynomials (namely $O(1/n^{r/2})$ rather than $O(1/n)$), such as linear combinations (Butzer 1953) and iterated Boolean sums (Micchelli 1973) of Bernstein polynomials.

• If $r=3$ and $W_n=2 f - B_n(f)$*, then $C_0 = \frac{3}{16-4 \sqrt{2}}.$
• If $r=5$ and $W_n = B_n(B_n(f))+3(f-B_n(f))$**, then $C_0 = 0.27.$

References

• Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
• Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.
• Micchelli, C. (1973). The saturation class and iterates of the Bernstein polynomials. Journal of Approximation Theory, 8(1), 1-18.
• Butzer, P.L., "Linear combinations of Bernstein polynomials", Canadian Journal of Mathematics 15 (1953).

---

* Corresponds to the iterated Boolean sum of order 2 (Güntürk and Li 2021).

*** Corresponds to the iterated Boolean sum of order 3 (Güntürk and Li 2021).