# On the regularity of certain continuous algebraic functions

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.

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

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.

• I don't see how the two claims follow from the convergence of Puiseux series, especially when the polynomial's coefficients must be rational numbers (and not, say, numbers in an algebraically closed field such as the complex numbers). You should edit your answer to give more detail on your proof. Jun 9, 2021 at 7:49
• Peter, it might be that I don't understand your question. I consider the case of real numbers, i.e. when $P(x,y)$ is a polynomial on $\mathbb R^2$ with real (or if you want rational) coefficients. The only thing that I say is that a converging power series $\sum_{i=1}^\infty a_i x^{i/k}$ is Holder (here $k>0$ is integer). Do you agree with this? Jun 9, 2021 at 8:28
• I believe I understand: any algebraic function over rationals can be rewritten as a convergent Puiseux series, and is thus Hölder continuous since the series has only additions, multiplications, and radicals; and polynomially bounded by choosing $n$ large enough. Jun 9, 2021 at 9:19