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

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,b\rangle \mapsto \mathop{Red}(\langle a+b,b+1\rangle)$ where $\mathop{Red}()$ denotes reduction $\mathop{Red}(\langle a,b\rangle) = \langle\frac{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+2\rangle)$ $=\mathop{Red}(\langle m+n+1,n+1\rangle)$; this might reduce even further, but this is good enough for our purposes. note that $b'=n+1\lt 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, 2n\rangle$ $\mapsto \mathop{Red}(\langle 2m+2n+1, 2n+1\rangle)$ $\mapsto\mathop{Red}(\langle 2m+4n+2, 2n+2\rangle)$ $=\mathop{Red}(\langle m+2n+1, n+1\rangle)$. Here we have $b'=n+1\lt b=2n$ as long as $b\gt 2$.

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

Together, these mean that we can study the effects of the iteration specifically on the cases $\langle a,b\rangle: b\in \{1,2,3\}$; any larger $b$ will eventually reduce to a $b$ in this range. More specifically, we have the cases $\langle a, 1\rangle$, $\langle 2m+1, 2\rangle$, and $\langle 2m, 3\rangle$ 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,1\rangle$. If $a$ is odd, then we have $\langle 2m+1, 1\rangle \mapsto \langle m+1, 1\rangle$; 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, 1\rangle$; by the logic above, this maps to $\mathop{Red}(\langle m+3, 3\rangle)$. We get a smaller value for the sum as long as $a+b=2m+1\gt a'+b'=m+6$, or in other words as long as $m\gt 5$ (i.e., $a\gt 10$).

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

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

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


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 that1)

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

Tags:

Number Theory

Sequences And Series

Related

Do functions with the same gradient differ by a constant? Is there a story proof behind the combinatorial identity $(n-2k)\binom{n}{k} = n\left[ \binom{n-1}{k} - \binom{n-1}{k-1} \right]$? Finding the Center of Mass of a disk when a part of it is cut out. How to prove divisibility by $7$? If $A^m = 0$, then $\mbox{rank}(A) \leq \frac{m-1}{m}{n}$ For a complex number $\alpha $ which is algebraic over $\Bbb Q$, determining whether $\bar{\alpha}\in \Bbb Q(\alpha)$ or not How many elements of order $2$ does Sym $6$ have? Purely geometric proof of inverse trigonometric functions derivatives Let $b \in [0,1)$. Prove that $\frac{b}{1-b} \in [0,\infty)$ Find $\sum_{n=1}^{\infty} \frac{1}{\prod_{i=0}^{k} \left(n+i\right)}$ Solving $\int_0^{\infty} {1 \over x^4-81}\ dx$? Let $G$ be a group with a free subgroup of rank $2$. Let $H\leq G$ be such that $[G:H]<\infty$. Then $H$ also contains a free subgroup of rank $2$.

Recent Posts