9
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 12
    $\begingroup$ 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$. $\endgroup$
    – pregunton
    Jan 4, 2022 at 10:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    Jan 4, 2022 at 10:56
  • 2
    $\begingroup$ $f(x)=(ax+b)/(cx+d)$ does not work, and other functions do not seem to be surjective $\endgroup$
    – Fedor Petrov
    Jan 4, 2022 at 11:01
  • 2
    $\begingroup$ @Algernon By rational function I mean a ratio of polynomials so not necessarily continuous but with at worst finitely many discontinuities. $\endgroup$
    – Ivan Meir
    Jan 4, 2022 at 11:25
  • 2
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Jan 4, 2022 at 21:42

2 Answers 2

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 5
    $\begingroup$ 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$. $\endgroup$
    – Joe Silverman
    Jan 4, 2022 at 16:51
  • $\begingroup$ 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 $\endgroup$
    – Saúl RM
    Jan 4, 2022 at 19:15
  • 2
    $\begingroup$ @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 $\endgroup$
    – Wojowu
    Jan 4, 2022 at 19:20
  • $\begingroup$ 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. $\endgroup$
    – alpoge
    Jan 5, 2022 at 3:50
  • $\begingroup$ 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.) $\endgroup$
    – alpoge
    Jan 5, 2022 at 3:52
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ What is $C(f_i)$? $\endgroup$
    – user2520938
    Jan 5, 2022 at 15:37
  • $\begingroup$ @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. $\endgroup$
    – Joe Silverman
    Jan 5, 2022 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.