On the regularity of certain continuous algebraic functions

Question

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.

Answer 1

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$.

Answer 2

If I understand correctly the question, both statements hold indeed thanks to existence of Puiseaux series for algebraic curves: https://en.wikipedia.org/wiki/Puiseux_series

Namely, for a generic point $(x, f(x))$ the curve $P=0$ passing through the point is smooth and has tangent line that his not vertical, so $f(x)$ is smooth at $x$. Otherwise you have a finite number of $x_i\in [0,1]$ such that $(x_i,f(x_i))$ is a singular point of the curve $P=0$ or it is a point where $P=0$ is tangent to a vertical line. At each such point $x_i$ you have Puiseaux series for $f(x)$ converging in some neighbourhood of $x_i$. This shows that the function is Holder continuous with a rational exponent in a neighbourhood of the point. Since we the number of such points $x_i$ is finite, we just take the minimum of these exponents. This proves the first claim, the second claim holds for the same reason.