# Is $\mathbb{Q}$ the orbit of a rational function under iteration?

In this previous post I asked for the smallest set of continuous real functions that could generate $$\mathbb Q$$ by iteration starting from $$0$$. Surprisingly one continuous function suffices.

In the question I gave the example of three rational functions that generate $$\mathbb{Q}$$, $$f(x)=1/x$$, $$g(x)=x+1$$ and $$h(x)=x-1$$. It would be interesting to know if this is best possible and in particular whether one rational function can generate all of $$\mathbb{Q}$$:

Can $$\mathbb{Q}$$ be generated as the orbit of fewer than 3 rational functions?

The question Orbits of rational functions asks a more general question but I don't think explicitly answers it for $$\mathbb{Q}$$ itself.

• It is possible to generate $\mathbb{Q}$ with the two functions $x \mapsto x+1$ and $x \mapsto -1/x$, as the modular group $PSL(2,\mathbb{Z})$ generated by these two functions acts transitively on $\mathbb{QP}^1$. Jan 4, 2022 at 10:32
• A unique such rational function (if it exists) induces cyclic permutations of all elements of the projective line over $\mathbb F_p$ for all (or perhaps almost all) primes đť‘ť. I think this is quite an extraordinary property. Jan 4, 2022 at 10:56
• $f(x)=(ax+b)/(cx+d)$ does not work, and other functions do not seem to be surjective Jan 4, 2022 at 11:01
• @Algernon By rational function I mean a ratio of polynomials so not necessarily continuous but with at worst finitely many discontinuities. Jan 4, 2022 at 11:25
• @LSpice The $x+1$ map takes $\infty$ to itself, the $-1/x$ map to $0$. Thus, if a path from one rational to another goes through $\infty$, that part of the path must be just $0\mapsto\infty\mapsto0$, and you can eliminate it. Jan 4, 2022 at 21:42

As was mentioned in the comments by pregunton, it is possible to do using two rational functions. I claim it is not possible using just one. As Fedor Petrov suggests in another comment, this is because rational functions of degree higher than $$1$$ are never going to be surjective, which can be shown with help of Hilbert's irreducibility theorem. Indeed, take a rational function $$\frac{f(x)}{g(x)}$$ with coprime polynomials $$f$$, $$g$$ of which at least one has degree greater than $$1$$. The polynomial $$h(x,t)=tf(x)-g(x)\in\mathbb Q[x,t]$$ is irreducible then, so by Hilbert's theorem there are infinitely many values $$q\in\mathbb Q$$ for which $$h(x,q)\in\mathbb Q[x]$$ is irreducible. For all but one of these $$q$$, $$h(x, q)$$ will have degree $$\max(\deg f,\deg g)>1$$, so irreducibility implies it has no rational roots. Hence $$q$$ is not in the image of $$\frac{f(x)}{g(x)}$$.

The only case remaining is that of $$\deg f,\deg g\leq 1$$. In this case either $$\deg g=1$$ and the rational function has a rational pole, so its iteration can't go over all rationals, or else it is affine of the form $$ax+b$$ and it's easy to see explicitly its iterations do not cover all rationals.

• Nice application of Hilbert irreducibility for degree $\ge2$. But as I mentioned in the comments, there's a more elementary proof using growth of height functions that shows that the points in the forward orbit are extremely sparse within the full set of rationals. Indeed, among the $O(B^2)$ rational numbers $p/q$ with $\max\{|p|,|q|\}\le B$, the number of them in a forward orbit is $O(\log\log B)$ as $B\to\infty$. Jan 4, 2022 at 16:51
• I think you are supposing that $f,g$ have rational coefficients. I don´t know if that is what Ivan Meir means with the question but he doesn´t make it explicit Jan 4, 2022 at 19:15
• @SaúlRodríguezMartín I indeed am using the fact that $f,g$ have rational coefficients. This follows from the fact that it takes infinitely many rational values on rational numbers, see e.g. here Jan 4, 2022 at 19:20
• Just like (link after), you don't need Hilbert for nonsurj.! Wlog $f,g\in\mathbb{Z}[x]$ are coprime in $\mathbb{Q}[x]$, let $0\neq R:=\mathrm{Res}_x(f,g)\in\mathbb{Z}$, $k:=\deg{f}-\deg{g}$, which wlog (via $f/g\mapsto g/f$ or $f/g + c$) is $>0$, and let $c_0:=$ leading coeff. of $f$ (it could be made $1$ too). Let $p$ be large. If $f(a/b)/g(a/b)=p$ with $a,b\in\mathbb{Z}$ coprime, then $F(a,b)/(b^k G(a,b)) = p$ with $F,G$ the homogenizations of $f,g$. Hence $b\vert F(a,b)$, so $b\vert c_0$, and also $G(a,b)\vert F(a,b)$ so $G(a,b)\vert R b^{\deg{f}}$ which now bounds $a$ and thus $p$, contra. Jan 5, 2022 at 3:50
• Now time to learn formatting: this is the promised link (if it works)! (Oy, I meant to also say $\deg{g} > 0$ too above but there's no room left to edit it in! Otherwise you should look at $1/p$ instead as in the link.) Jan 5, 2022 at 3:52

A rational function is as a self-map of $$\mathbb P^1$$. With that understanding, as was noted earlier, it is possible to generate all of the points $$\mathbb P^1(\mathbb Q)$$ by starting with the point $$0$$ and applying elements of the semi-group $$\langle f_1,f_2\rangle$$ generated by iteration using the two functions $$f_1=x+1$$ and $$f_2=-1/x$$. In this construction, both $$f_1$$ and $$f_2$$ are rational maps of degree $$1$$.

However, if one instead uses sets of rational maps $$f(z)\in\mathbb Q(z)$$ of degree at least $$2$$, then no finitely generated semi-group of such rational maps has an orbit that contains all of $$\mathbb P^1(\mathbb Q)$$, and indeed, any such orbit will be fairly sparse. Here's a quick proof (shown to be by Wade Hindes). Let $$\mathcal F=\langle f_1,\ldots,f_r\rangle$$, where $$f_i\in\mathbb Q(z)$$ has degree $$d_i\ge2$$. Then we have the height estimate $$h\bigl(f_i(P)\bigr) \ge d_i h(P) - C(f_i).$$ It follows that for each $$i$$, $$f_i\bigl(\mathbb P^1(\mathbb Q)\bigr) := \bigl\{ f_i(Q) : Q \in \mathbb P^1(\mathbb Q) \bigr\}$$ has density $$0$$, where we use the height function to count points. But then for any starting point $$P \in \mathbb P^1(\mathbb Q)$$, the full orbit satisfies $$\mathcal F(P) := \bigl\{ f(P) : f\in\mathcal F\bigr\} \subseteq \bigcup_{1\le i\le r} f_i\bigl(\mathbb P^1(\mathbb Q)\bigr).$$ Thus the orbit $$\mathcal F(P)$$ is the union of finitely many sets of density $$0$$, so the orbit $$\mathcal F(P)$$ has density $$0$$.

• What is $C(f_i)$? Jan 5, 2022 at 15:37
• @user2520938 $C(f_i)$ a constant that depends on $f_i$, but is independent of $P$. For any particular $f_i(z)$, one can write down an explicit value for $C(f_i)$ that depends on the degree of $f_i$ and its coefficients. Jan 5, 2022 at 16:56