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

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.

• $f(x)=\dfrac{1}{x}$ is not continuous, so at least the process you described can not be achieved by $3$ continuous functions. Jan 1 at 11:42
• In the case of the USAMO question they are equivalent - is it obvious? Let say I get a large number (e.g. using tan), then apply sin; how do you go back from there? Jan 1 at 11:45
• @Zerox I've just edited the question to include this. Jan 1 at 12:11
• To do it with 2 functions continuous in all $\mathbb{R}$, you can pick $f(x)=x+1$ and, for an enumeration $q_n$ of the rationals, pick $g(x)$ continuous and with $g(n)=q_n$ for natural $n$ Jan 1 at 13:03
• I´m just saying $g(n)=q_n$, nothing about $g(q_n)$. You can define $g$ by linear interpolation for example in the intervals $[n,n+1]$ Jan 1 at 14:55

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.

• Thanks Saúl this is a lovely solution. I noted from the MO answer referenced below that you can generate the dense sequence using a Lipschitz continuous function. I am I right to assume that the homeomorphism you use for the second part of your answer is not Lipschitz? Jan 20 at 9:15
• Thanks! The homeomorphism from the second part of the answer can be Lipschitz, in fact given $A,B$ countable dense subsets of $\mathbb{R}$ and $\varepsilon>0$ there is an homeomorphism $h:\mathbb{R}\to\mathbb{R}$ with $h(A)=B$ and $(1-\varepsilon) d(x,y)<d(h(x),h(y))<(1+\varepsilon)d(x,y)\;\forall x,y$, as shown in theorem 13 of this paper. Jan 20 at 14:38
• That is very cool! So it looks like we can strengthen your result to Lipschitz continuous rather than simply continuous? This means absolutely continuous and therefore a.e. differentiable I believe. Is it correct that your function is not differentiable everywhere on $\mathbb{R}$? Jan 21 at 0:54
• Surprisingly the function can even be taken to be analytic, here is a reference.Sorry for the wait, I thought a bit about the comment, forgot about it and recalled it today. Jan 29 at 8:40
• That is surprising but quite satisfying! Saul thanks again for your efforts on this. Jan 30 at 12:13

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