What is the smallest set of real continuous functions generating all rational numbers by iteration?

Question

I recently came across this problem from USAMO 2005:

"A calculator is broken so that the only keys that still work are the $\sin$, $\cos$, $\tan$, $\arcsin$, $\arccos$ and $\arctan$ buttons. The display initially shows $0$. Given any positive rational number $q$, show that pressing some finite sequence of buttons will yield $q$. Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians."

A surprising question whose ingenious solution actually shows how to generate the square root of any rational number.

I'd like to pose the following questions related to this problem:

What is the smallest set of real functions, continuous at all points of $\mathbb{R}$, which can be applied to $0$ to yield a sequence containing all the rational numbers?

It's also interesting perhaps weaken this to allowing finite numbers of discontinuities so you can use the rational functions for example:

What is the smallest set of real functions, continuous except at a finite set of points, which can be applied to $0$ to yield a sequence containing all the rational numbers?

Note that these are slightly different questions to the one above in that we are asking not only to be able to produce any rational from $0$ but to produce all of them at some point after starting at $0$. In the case of the USAMO question you can generate a complete sequence of rationals as well as any given rational but this may not always be true. (See solution for details)

For the second question note that from the theory of continued fractions of rational numbers the functions $f(x)=1/x$, $g(x)=x+1$ will generate any given rational starting from $0$. For example since

$$\frac{355}{113} = 3+\cfrac{1}{7+\cfrac{1}{16}}$$

we have $\frac{355}{113}=g^{[3]}(f(g^{[7]}(f(g^{[16]}(0)))))$.

If we also throw in $h(x)=x-1$ we again have every inverse included hence this set of three functions will generate all rationals.

So we know that the smallest set must contain either $1$, $2$ or $3$ functions.

In fact as pregunton noted in this related question the functions $f(x)=x+1$ and $g(x)= -1/x$ generate the modular group which acts transitively on $\mathbb{Q}$ and this gives an elegant example with only two functions.

Answer 1

It is enough with one continuous function. First, I'll give a simple example with one function which is discontinuous at one point. To do it, consider the function $$f:(0,\pi+1)\to(0,\pi+1)$$ with $$ f(x) = \begin{cases} x+1 &\text{if $x<\pi$,} \\ x-\pi &\text{if $x>\pi$,} \\ 1 &\text{if $x=\pi$.}\\ \end{cases} $$ Claim: The sequence $$1,f(1),f^2(1),\dots \tag{$*$}$$ is dense in $(0,\pi+1)$.

To verify the claim, it is enough to see that the image is dense in the interval $(0,1)$, and that is true because for every $n$, the number $\lceil n\pi\rceil-n\pi$ is in the image, and the sequence of multiples of $\pi$ modulo 1 is dense in $(0,1)$ due to $\pi$ being irrational.

Let $A$ denote the image of the sequence $(*)$. Since $A$ is dense in $(0,\pi+1)$, we can find an homeomorphism $h:(0,\pi+1)\to\mathbb{R}$ with $h(A)=\mathbb{Q}$ (using that $\mathbb{R}$ is countable dense homogeneous, see for example this reference). We can also suppose $h(1)=0$ changing $h$ by $h-h(1)$ if necessary.

Then the function $F=hfh^{-1}$ does the trick, because $$F^n(0)=hf^nh^{-1}(0)=h(f^n(1)),$$ so $h(A)$, which is $\mathbb{Q}$, is the image of the sequence $0,F(0),F^2(0),\dots$

To prove that the problem can be solved with one continuous function, we can apply the same argument but taking instead of $f$ a continuous function $g:\mathbb{R}\to\mathbb{R}$ such that $0,g(0),g^2(0),\dots$ is dense in $\mathbb{R}$. As Martin M. W. noticed in his answer, those functions are known to exist (they are called transitive maps), this paper gives examples of them.

Answer 2

You only need one continuous function.

There exists a continuous function $f: \mathbb{R} \to \mathbb{R}$ with a dense orbit, according to this MathOverflow answer. As in Saúl's construction, you can conjugate $f$ with a homeomorphism to get a map where the forward iterates of $0$ are $\mathbb{Q}$.