On certain algebraic functions on the interval $[0, 1]$

Let $\mathcal{C}$ be the class of continuous and polynomially bounded functions that map the interval [0, 1] to [0, 1].

A function $f(x)$ is polynomially bounded 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). This implies that $f$ admits no roots on (0, 1) and can't take on the value 0 or 1 except possibly at 0 and/or 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 real analytic on the interval $(0, 1)$?
2. 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$? (See note 2 below.)
3. Are there functions in class $\mathcal{C}$ that—
   • are algebraic over the rational numbers, but
   • are not algebraic over the non-negative rational numbers?

Motivation:

According to Mossel and Peres (2005), a function in the class $\mathcal{C}$ can be simulated by a pushdown automaton only if the function is algebraic over the rational numbers, but the converse is not known to be true. Banderier and Drmota (2015) proved certain things involving algebraic functions over the non-negative real numbers, including their so-called "critical exponents" and the fact that these exponents impose a kind of lower bound on the complexity of any context-free grammar generating those functions. My question 3 may help answer whether those results apply more generally to algebraic functions over the rational numbers (not just over non-negative ones) in class $\mathcal{C}$. Just like question 3, the other two questions may help answer whether certain things can be concluded about all algebraic functions in class $\mathcal{C}$ over rational numbers.

Notes:

1. A Google Scholar search didn't help me much in answering the first two questions. For example, Flajolet (1987) discussed how to determine if a power series is algebraic over rationals, but gave no example of a function that is algebraic over rationals but not analytic. Moreover, apparently not all algebraic functions over rationals might be expressible as power series, as Richman's results suggest.
2. It is relatively easy to show that constants, the identity $x$, 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, 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.
• Banderier, C. And Drmota, M., 2015. Formulae and Asymptotics for Coefficients of Algebraic Functions. Comb. Probab. Comput., 24(1), pp.1-53.
• Richman, Fred. "Algebraic functions, calculus style." Communications in Algebra 40, no. 7 (2012): 2671-2683.
• Flajolet, P., 1987. Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49(2-3), pp.283-309.

Answering question 1:

The answer is no. There are non-analytic functions in $\mathcal{C}$ that are algebraic over the rational numbers.

One example is $f(x) = |x-1/2|+1/2$, which is differentiable everywhere except at $1/2$ (and thus not real analytic on $(0, 1)$). By translating this equation to $f(x) = \sqrt{(x-1/2)^2} + 1/2$ and bringing the right-hand side to 0, we get $f(x)^2 - f(x) - x^2 + x = 0$, which is a polynomial in $x$ and $f(x)$ whose coefficients are rational numbers (in fact, integers). Thus, $f(x)$ is algebraic over the rationals.

Answering question 2:

The answer is yes. A proof by Reid Barton involves the theory of semialgebraic functions and the Łojasiewicz inequality.

Answering question 3:

Yes, there are functions in $\mathcal{C}$ that are algebraic over rationals but not over non-negative rationals.

One example is $f(x)=\sqrt{1-x}$, whose series expansion's coefficients are all negative except the first, which is 1. Moreover, $f$ satisfies the polynomial equation $x+(f(x))^2-1=0$. This equation's coefficients are all rational numbers, one of which is negative, showing that this function is algebraic over rationals but not over non-negative rationals.