Let $\mathcal{C}$ be the class of continuous functions that—


* map $[0, 1]$ to $[0, 1]$, and
* equal neither 0 nor 1 on the open interval $(0, 1)$.


A function $f(x)$ is *algebraic over the rational numbers* if—


* It can be a solution of a system of polynomial equations whose coefficients are rational numbers, or equivalently,
* there is a nonzero polynomial $P(x, y)$ in two variables and whose coefficients are rational numbers, such that $P(x, f(x)) = 0$ for every $x$ in the domain of $f$.


Then:


1. Is a function in the class $\mathcal{C}$ algebraic over the rational numbers only if it's $\alpha$-Hölder continuous for some $\alpha > 0$?
2. Is a function in the class $\mathcal{C}$ algebraic over the rational numbers only if it's *polynomially bounded*, that is, only if both $f$ and $1-f$ are bounded below by min($x^n$, $(1-x)^n$) for some integer $n$ (Keane and O'Brien 1994)?


**Notes:**


1. According to Mossel and Peres (2005), a function in the class $\mathcal{C}$ can be simulated via a pushdown automaton only if the function is algebraic over the rational numbers, but the converse is not known to be true. The questions here may help answer whether certain things can be concluded about functions in the class $\mathcal{C}$ that are algebraic over rational numbers.
2. It is relatively easy to show that constants, the identity function, and arbitrary additions and multiplications of these functions are Lipschitz continuous (1-Hölder continuous), and that those functions together with radicals are $\alpha$-Hölder continuous. However, it's not so easy to show whether those functions together with their reciprocals are $\alpha$-Hölder continuous (while remaining in class $\mathcal{C}$), or whether that remains true with arbitrary algebraic functions in the class $\mathcal{C}$, including those that can't be expressed in terms of radicals. Also, I believe that a function that maps (0, 1) to (0, 1) is algebraic over the rationals only if it's polynomially bounded.


REFERENCES:


* Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
* Mossel, Elchanan, and Yuval Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6), pp.707-724.



On the regularity of certain continuous algebraic functions
A continuous function $f : [0, 1] \to [0, 1]$ which is algebraic over the rational numbers in your sense is a semialgebraic function: its graph can be defined by a first-order formula in the language of an ordered field. Indeed, suppose $P(x, f(x)) = 0$ for a nonzero polynomial $P$. The zero locus $Z = \{\,(x,y) \in [0, 1]^2 \mid P(x,y) = 0\,\}$ is one-dimensional and the projection from $Z$ to the $x$-axis is a local homeomorphism for all but finitely many exceptional values of $x$. Then on each of the open intervals determined by these exceptional values, since the graph of $f$ is contained in $Z$, we can describe $f(x)$ as the "$i$th root of $P(x, -)$" for some $i$; and at the exceptional values of $x$, $f(x)$ must also be algebraic by continuity.


Now, the Łojasiewicz inequality says that if $g$ and $h$ are semialgebraic functions on $A$ such that $h$ vanishes wherever $g$ does, then there exists $c > 0$ and $N > 0$ such that $|h|^N \le c|g|$ on $A$. In particular,


* taking $g(x,y) = |x-y|$ and $h(x,y) = |f(x)-f(y)|$, we deduce that a semialgebraic function is Hölder.
* taking $g(x) = f(x)$ and $h(x) = \min(x, 1-x)$, we deduce that $f(x) \ge \min(x^N, (1-x)^N)/c$ on $[0, 1]$. By adjusting $N$ we can remove the constant $c$.


