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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jan 5, 2022 at 16:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .