Show $f(x)=1-\frac{1}{x\left(\lvert x\rvert_2\right)}$ converges on $0$ in finite steps

Let

$$ f(x)=1-\frac{1}{x\lvert x\rvert_2}. $$

Show that $f^m(x)$ converges to $0$ for all $x\in\mathbb{N_{>0}}$, for sufficiently high $m\in\mathbb{N}$.

In a nutshell, $x\lvert x\rvert_2$ boils down to the odd factors of $x$. $\lvert x\rvert_2$ is the $2$-adic metric of $x$, defined by $\lvert x\rvert_2=\frac{1}{2^p}$, where $x=2^p\cdot\frac{r}{q}$ and $r,q$ are odd numbers. Note that the question is, whether for an initial integer input $x$, $f^m(x)$ converges, however $f(x)$ must be defined over rationals so we have

$$f(x)=1-\frac{1}{x\lvert x\rvert_2}\quad \mathbb{Q}\mapsto\mathbb{Q}.$$

Let $x_{m+1}=f(x_m)$. Show that $\forall x_0\in\mathbb{N_{>0}}\exists > n\mid (f^m(x)=0\forall m\geq n)$

UPDATE

I'm currently investigating whether Mahler's theorem and Newton's forward difference formula have something to say. Forward difference formula looks promising on the face of it but I haven't studied that in depth.

Solution 1:

The formula $$f(x) = 1-\frac{1}{x |x|_2}$$ does not define a function on $\Bbb R$ because most real numbers do not have a well-defined $2$-adic value $|\cdot|_2$. However, it is clear that you are basically interested in rational inputs anyways. Now, the above formula does describe a well-defined function $f: K\setminus\{0\} \rightarrow K$ for any algebraic extension $K$ of the $2$-adic numbers $\Bbb Q_2$, and for $0\neq x \in K$ we indeed have:

There exists $k\in \Bbb N$ such that $f^k(x) = 0 \qquad$ if and only if $\qquad x \in \Bbb Q$.

"Only if" is clear since for irrational $x$, the number $f(x)$ is also irrational. So let us prove the interesting "if" direction.

Prerequisite 1: For a rational number $q$ call $$l(q) := \min\{ |m|+|n| : q =\frac{m}{n} \text{ with }m, n \in \Bbb Z \}$$ (where $|\cdot|$ denotes the usual absolute value) the length of $q$. So e.g. $l(-4) = 5, l(\frac{3}{4})=7, l(\frac{-18}{15})=11$. Note that instead of taking the minimum, we could have demanded $\gcd(m,n)=1$ in the definition. We have $l(q) = 1 \Leftrightarrow q=0$ as well as $l(q)=2 \Leftrightarrow q=\pm1$ (and in general for each $N\in \Bbb N$ there are only finitely many $q$ with $l(q)=N$, although we will not need that). Crucially, this length will allow us to use induction.

Prerequisite 2: It helps to take $f$ apart as follows: We have $f = g \circ h$ with $h(x) = x \cdot |x|_2$ and $g(x) = 1-\frac{1}{x} = \frac{x-1}{x}$. So $$f^2(x) = g(h(g(h(x))))$$ etc. Note that $h$ is idempotent i.e. $h^2 = h$. (All exponents here are w.r.t. composition of functions.) Note also that $l(h(q)) \le l(q)$ for all $q\in \Bbb Q\setminus\{0\}$.

Now after noting $f(1) = 0, f(-1) = 1$, the claim follows by induction (on the length $l(q)$) from

Lemma: For $q\in \Bbb Q\setminus \{0\}$, we have $l(h(f(q))) < l(q)$ or $l(f^2(q)) < l(q)$.

Proof: Let $0\neq q\in \Bbb Q$, $q=\frac{m}{n}$ with $\gcd(m,n)=1$. W.l.o.g. (by applying $h$) assume that both $m,n$ are odd, and also that $n$ is positive (only needed in case 2). Then $$f(q) = g(q) = \frac{m-n}{m} $$

and since $m$ is odd, $$h(f(q)) = h\left(\frac{m-n}{m}\right) = \frac{|m-n|_2 \cdot (m-n)}{m}.$$

Case 1: $|m| < |n|$. Then $|m-n| < |m|+|n| < 2|n|$ and hence $$l(h(f(q))) \le \frac{1}{2}|m-n| + |m| < |m|+|n| = l(q).$$

Case 2: $|m| > |n|$. Note that we have $$f^2(q) = \frac{2^{-r}(m-n) -m}{2^{-r}(m-n)}$$ where $r = v_2(m-n) \ge 1$.

Case 2a: $m$ is positive, i.e. $m > n \ge 1$. Then $$|2^{-r}(m-n) -m| = 2^{-r}\cdot |-n-(2^r-1)m| = 2^{-r}((2^r-1)m+n)$$ and $$|2^{-r}(m-n)| = 2^{-r}(m-n)$$ hence $$l(f^2(q)) = 2^{-r}((2^r-1)m+n) + 2^{-r}(m-n) = m < m+n =l(q).$$

Case 2b: $m$ is negative, i.e. $m < -n \le -1$. We just have to switch some signs and now have $|2^{-r}(m-n) -m| = 2^{-r}\cdot |-n-(2^r-1)m| = 2^{-r}(-(2^r-1)m-n)$ and $|2^{-r}(m-n)| = 2^{-r}(-m+n)$, hence $$l(f^2(q)) = 2^{-r}(-(2^r-1)m-n) + 2^{-r}(-m+n) = -m =|m| < |m|+|n| =l(q).$$ $$QED.$$

NB 1: The proof actually gives a -- very crude -- upper bound for the number of necessary iterations $k$, namely $f^{2l(q)+2}(q)=0$. (Specifically, as you asked for integers, $f^{2|m|+3}(m)=0$ for $m\in \Bbb Z$.) The longest I found playing around with small $m,n$ was $q=\frac{17}{5}$, where $$f(q)=\frac{12}{17}, f^2(q) = \frac{-14}{3}, f^3(q) = \frac{10}{7}, f^4(q) = \frac{-2}{5}, f^5(q) = 6, f^6(q) =\frac{2}{3}, f^7(q) = -2, f^8(q) = 2, f^9(q) = 0.$$ Remark that $l(f^2(q)) = 17$, the numerator of $q$, as predicted by case 2 of the proof. Another relatively long chain is given by $q=\frac{-5}{9}$, the iterated values are $$\frac{14}{5}, \frac{2}{7}, -6, \frac{4}{3}, -2, 2, 0 = f^7(q)$$

NB 2: I think a similar approach works e.g. for the function $$x\mapsto 1+\frac{1}{x|x|_2}$$ and possibly other similar ones, although with more subtle considerations and more case distinctions. Still, I feel that there should be a more conceptual proof. I basically made up what I call the "length" as an ad hoc method because after looking at enough examples, it seemed to work. Probably this "length" has been used somewhere else under a possibly different name; I would be glad to be informed about other (names and) uses of it.

NB 3: What this shows resp. is equivalent to is that it is exactly the elements $q\in \Bbb Q^*$ which can be written as a finite continued fraction of the form

$$ \dfrac{2^{a_0}}{1- \dfrac{2^{a_1}}{1 - \dfrac{2^{a_2}}{1- 2^{a_3} ...}}}$$

with $a_i \in \Bbb N$. For example:

$$\frac{9}{5} = \dfrac1{1- \dfrac4{1 - \dfrac8{1- 2}}} $$

I know next to nothing about continued fractions, so maybe somebody from that camp can see something there. I have asked about this and possible generalisations as a follow-up question here.