What loops are possible when doing this function to the rationals?

Here is a modification of @Steven Stadnicki's proof. The novel contribution of this answer is justifying the reduction step in Steven's solution through the use of a suitable partial order on the set of lattice points.

Step 1. Settings and Useful Observations

Let $mathbb{N}_1 = {1, 2, 3, dots}$ denote the set of positive integers and define $mathsf{Red} : mathbb{N}_1^2 to mathbb{N}_1^2$ by

$$ mathsf{Red}(a, b) = frac{(a,b)}{gcd(a,b)}. $$

Also, we equip $mathbb{N}_1^2$ with the partial order $leq$ such that¹⁾

$$ (a, b) leq (c, d) quad Leftrightarrow quad [b < d]text{ or }[b = d text{ and } a leq c]. $$

The following observations are easy to prove but will be useful throughout.

• $text{(P1)} $ $a leq c$ and $b leq d$ implies $(a, b) leq (c, d)$.

• $text{(P2)} $ $mathsf{Red}(mathrm{p}) leq mathrm{p}$ for any $mathrm{p} in mathbb{N}_1^2$.

Step 2. Key Observation

We will identify each pair $(a,b) in mathbb{N}_1^2$ satisfying $gcd(a, b) = 1$ with the simplified fraction $a/b$. Under this identification, we have

$$f(a/b) = mathsf{Red}(a+b,b+1). $$

Now we will investigate the effect of a suitable number of iterations of $f$. By noting that either $a$ or $b$ must be odd, the following three cases exhaust all the possibilities:

• Case 1. Suppose that both $a$ and $b$ are odd. Then both $a+b$ and $b+1$ are even, and so,

  begin{align*} f(a,b) = mathsf{Red}(a+b, b+1) = mathsf{Red}(tfrac{a+b}{2}, tfrac{b+1}{2}) stackrel{text{(P2)}}leq (tfrac{a+b}{2}, tfrac{b+1}{2}). tag{1} end{align*}

• Case 2. Suppose that $a$ is odd and $b$ is even. Then by writing $d=gcd(a+b,b+1)$,

  begin{align*} f^{circ 2}(a,b) = f(tfrac{a+b}{d},tfrac{b+1}{d}) = mathsf{Red}(tfrac{a+2b+1}{d},tfrac{b+d+1}{d}). end{align*}

  Since $d$ is odd, both $a+2b+1$ and $b+d+1$ are even. This means that both are divisible by $2d$, and so,

  begin{align*} f^{circ 2}(a,b) = mathsf{Red}(tfrac{a+2b+1}{2d},tfrac{b+d+1}{2d}) stackrel{text{(P2)}}leq (tfrac{a+2b+1}{2d},tfrac{b+d+1}{2d}) stackrel{text{(P1)}}leq (tfrac{a+2b+1}{2},tfrac{b+2}{2}). tag{2} end{align*}

  Here, the last inequality follows from the general fact that $frac{A+Bd}{d}leq A+B$ for all $A, B geq 0$ and $d geq 1$.

• Case 3. Suppose that $a$ is even and $b$ is odd. Since $d = gcd(a+b, b+1)$ is odd, we find that $frac{a+b}{d}$ is odd and $frac{b+1}{d}$ is even. So by applying $text{(2)}$ and using the inequality in the previous step,

  begin{align*} f^{circ 3}(a,b) = f^{circ 2}(tfrac{a+b}{d},tfrac{b+1}{d}) stackrel{text{(2)}}leq (tfrac{a+3b+d+2}{2d},tfrac{b+2d+1}{2d}) stackrel{text{(P1)}}leq (tfrac{a+3b+3}{2},tfrac{b+3}{2}). tag{3} end{align*}

Step 3. Proof

Let $(a, b) in mathbb{N}_1$ satisfy $gcd(a, b) = 1$. Then by $text{(1)}$–$text{(3)}$, we observe the following:

1. If $b > 3$, then $frac{b+3}{2} < b$, and so, a suitable number of iterations by $f$ reduces the second coordinate. This can be repeated finitely many times until the second coordinate becomes $leq 3$.

2. If $b leq 3$ and $a > 12$, then $frac{a+3b+3}{2} < a$, and so, a suitable number of iterations by $f$ reduces the first coordinate. Similarly as before, this can be repeated finitely many times until the first coordinate becomes $leq 12$.

3. If $a leq 12$ and $b leq 3$, then a suitable number of iterations by $f$ will map $(a, b)$ into another point $(a', b')$ with $a' leq 12$ and $b' leq 3$. So by the pigeonhole principle, iteration by $f$ will eventually fall into a cycle.

4. By checking all the possible $12+6+8=26$ cases manually, we find that there are only three types of cycles: $$ (1, 1) qquad (5, 2), (7, 4) qquad (2, 1), (3, 2), (5, 3) $$

This completes the proof.

---

^{1) Note that this is exactly the colexicographical order induced by the usual order on $mathbb{N}_1$.}

The key here is that for parity reasons, we'll always get to a 'smaller' fraction in a short, finite number of stages. Rather than fractions, I'll refer to an iteration on a pair of numbers $f:langle a,brangle mapsto mathop{Red}(langle a+b,b+1rangle)$ where $mathop{Red}()$ denotes reduction $mathop{Red}(langle a,brangle) = langlefrac{a}{gcd(a,b)},frac{b}{gcd(a,b)}rangle $. We'll start by inducting on the value of $b$, to show that we need to only consider a small number of values of $b$ when looking for cycles. Note that $a$ and $b$ can't both be even, so there are three cases: $a=2m+1, b=2n$, $a=2m, b=2n+1$, and $a=2m+1, b=2n+1$. The third case immediately goes to $langle a',b'rangle$ $=mathop{Red}(langle 2m+2n+2,2n+2rangle)$ $=mathop{Red}(langle m+n+1,n+1rangle)$; this might reduce even further, but this is good enough for our purposes. note that $b'=n+1lt b=2n+1$, so the value of $b$ always reduces in this case unless $b=1$.

In the case $a=2m+1, b=2n$, the map goes $langle 2m+1, 2nrangle$ $mapsto mathop{Red}(langle 2m+2n+1, 2n+1rangle)$ $mapstomathop{Red}(langle 2m+4n+2, 2n+2rangle)$ $=mathop{Red}(langle m+2n+1, n+1rangle)$. Here we have $b'=n+1lt b=2n$ as long as $bgt 2$.

Finally, in the case $a=2m, b=2n+1$, the map goes $langle 2m, 2n+1rangle mapstomathop{Red}(langle 2m+2n+1, 2n+2rangle)$ $mapstomathop{Red}(langle 2m+4n+3, 2n+3rangle)$ $mapstomathop{Red}(langle 2m+6n+6, 2n+4rangle) = mathop{Red}(langle m+3n+3, n+2rangle)$. Here, $b'=n+2lt b=2n+1$ as long as $bgt 3$.

Together, these mean that we can study the effects of the iteration specifically on the cases $langle a,brangle: bin {1,2,3}$; any larger $b$ will eventually reduce to a $b$ in this range. More specifically, we have the cases $langle a, 1rangle$, $langle 2m+1, 2rangle$, and $langle 2m, 3rangle$ to study. I'm going to use a different form of induction on these cases, based on the value of $a+b$.

Let's start with the case $langle a,1rangle$. If $a$ is odd, then we have $langle 2m+1, 1rangle mapsto langle m+1, 1rangle$; here $a'+b'=m+2$ will always be less than $a+b=2m+2$. If $a$ is even, then we have the case $langle 2m, 1rangle$; by the logic above, this maps to $mathop{Red}(langle m+3, 3rangle)$. We get a smaller value for the sum as long as $a+b=2m+1gt a'+b'=m+6$, or in other words as long as $mgt 5$ (i.e., $agt 10$).

Next up, we have the case $langle 2m+1, 2rangle$; by the logic above, this maps to $mathop{Red}(langle m+3, 2rangle)$. Since $a'+b'=m+5lt a+b=2m+3$ as long as $mgt 2$, we can see that any pair $langle a,2rangle$ with $a$ an odd number greater than $5$ will yield new pair with a smaller sum.

Finally, we have the case $langle 2m, 3rangle$; once again, using the logic above we see that this will map to $mathop{Red}(langle m+6, 3rangle)$. Here we have $a+b=2m+3gt a'+b'=m+9$ as long as $mgt 6$, or in other words $agt 12$.

Putting this all together, we can see that cases of the form $langle a,brangle$ with $bleq 3$ always yield another case of similar form with smaller $a$ as long as $agt 12$; this leaves only a finite number of values to check, which yields the loops that have already been found.