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

• Why would you write $f(x)=4-(\frac{3x+v_2(x)}{x})$ when you can write the much simpler $$f(x)=1-\frac{v_2(x)}{x}$$ Also, do you mean $v_2$ from $\mathbb{Q}\to\mathbb{Z}$, the extended 2-adic function? Mar 10, 2017 at 10:21
• The 2-adic order function is (usually) defined differently than you do: read this page on the subject. $v(28)=2$ in the usual sense, since it contains only $2$ factors $2$. How do you define $v_2(x)$ if you allow fractional $x$? Mar 10, 2017 at 10:42
• No, the wikipedia page states (for $n\neq 0$): $$v_2(n)=\max\{v\in\mathbb{N}:2^v\mid n\}$$ Meaning, the largest exponent $v$ such that $2^v$ divides $n$. For $28$, that exponent is $2$ (for $2^2\mid28$ and $2^3\not\mid 28$), thus, $v_2(28)=2$. Mar 10, 2017 at 10:49
• @vrugtehagel I'm happy for $v_2$ to be defined over rational 2-adics but it's important to restrict the starting $x$ to integers otherwise this series doesn't always converge. In fact that fact is almost certainly a crucial part of the answer. Mar 10, 2017 at 10:52
• Um, $1-x|x|_2=1-x/2^{v_2(x)}$ not $1-2^{v_2(x)}/x$. Can you settle once and for all what your function $f$ is? Tell us what the original $f$ is from the original problem.
– anon
Mar 10, 2017 at 13:21

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.

• Regarding "contraction mapping", well, with respect to what order/metric/whatever? In a way, my proof does exactly that, as it shows that suitable iterations of $f$ contract what I call the length (on all of $\Bbb Q$, I don't see what good modding out $\Bbb Z$ would do). By the way, (iterations of $x\mapsto$) $\frac{1}{|x|_2x}$ do generally not converge to $1$, after the first iteration that just gives a sequence alternating between a rational with $2$-adic absolute value 1 and its reciprocal. Jul 18, 2018 at 0:44
• How much work went into this answer? I'm assuming it piqued your interest and you spent an hour or two on it, but I wondered if that assumption is wrong? Jul 20, 2018 at 16:42
• It piqued my interest, I filled a page with examples and tried one or two p-adic approaches (maybe 2-3 hours) which did not work; had it on my mind for a couple of weeks, occasionally thinking about what other approach might work, filled another two or three pages with scribblings; finally sat down again, maybe 2 hours of intense work, also on the analogous problem with "+"; convinced myself that this approach works; then maybe another three hours (spread out over two days) of writing it down, by the way still improving it (e.g. introducing $g$ and $h$). Jul 20, 2018 at 17:11
• I want to say I don't think you're an idiot, but I do find your belief you can prove Collatz, with this as a major step, borders on idiocy. What you need is someone who teaches you, over several months at least, a) basic concepts of math, like all the undergrad courses, and more importantly, b) a different mindset, e.g. recognising one cannot understand a mathematical concept by reading a wikipedia article, and realising that unlike you seem to believe, precision in notation and terminology are not some secondary issue, but the very thing that distinguishes math from babbling. Jul 21, 2018 at 18:32
• I can understand why you'd say that but what I think I need is a proper conversation in more than one comment per day format, about the contraction map on $\omega^{<\omega}$ of which this proof is an example and some help developing some understanding of the bijection between $\Bbb Q\setminus0$ and $\omega^{<\omega}$ which this proof shows exists, and then to discuss the modification of that map, to a map from $\Bbb Z(\frac16)\setminus0$ to $\omega^{<\omega}$, which will prove the Collatz conjecture. With that, I can make rapid progress. Without it this is a long slow, hard slog. Jul 21, 2018 at 18:37