# What is the sequence of accumulation points in the 2-adic space, of the Collatz graph?

In the orbit of the function $$3x+2^{\nu_2(x)}$$ through "accumulation points" of the Collatz graph I have:

$$?\mapsto\dfrac{-\langle2\rangle\cdot\{5,7\}}{9}\mapsto\dfrac{-\langle2\rangle}{3}\mapsto \langle \Bbb 2 \rangle\cdot0$$

What's the full set of predecessors that goes where the question mark is?

$$2^{\nu_2(x)}$$ is the highest power of $$2$$ that divides $$x$$.

The above stands alone as a question asking for the preimage of the given sequence by the given function with no mention of the Collatz graph, but a little background for any who may be interested:

I understand the Collatz function defined by $$f:\Bbb N\to\Bbb N::f(x)=3x+2^{\nu_2(x)}$$ is continuous in $$\Bbb Z_2$$

Note that this function commutes with $$2x$$ so we can ignore multiplication by $$2$$ throughout this question. The set $$\langle2\rangle$$ represents multiplication by any power of $$2$$ of your choosing.

For any odd $$y\in2\Bbb N-1$$, the set of all integers $$x$$ satisfying $$f(x)\in\{2^my:m\in\Bbb Z\}$$ accumulates to $$\dfrac{-\langle2\rangle}{3}$$

And the set of all integers $$x$$ satisfying $$f^2(x)=2^my$$ accumulates under the 2-adic metric to $$\dfrac{-\langle2\rangle\cdot\{5,7\}}{9}$$

We can immediately see that the continuity rule supports this analysis since $$\bar f^{-2}(y)$$ is in the preimage of $$\bar f^{-1}(y)$$

Analysis of the sequences themselves is a little tough going. (More on that here).

But is there some obvious induction over the boundary points alone which indicates the full sequence of predecessors?

Update: we now have the more complete question:

$$?\mapsto\dfrac{-(2^n+3)}{9}\mapsto\dfrac{-1}{3}\mapsto 0$$

• The set of $x$ with $f(f(x)) \in \langle 2\rangle$ has many more accumulation points, even if (what I assume you want) you only allow odd natural numbers $x$. E.g. all $\dfrac{2^{6m+1} -11}{9}$ are in there, and they have accumulation point $-11/9$. (You are looking at $\lbrace \dfrac{2^{m+n} -2^n -3}{9}:m,n \in \Bbb Z\rbrace$ and maybe want to restrict to those $n$ for which this is an odd integer for an unbounded set of $m$'s; for those you get $(-2^n-3)/9$ as accumulation point.) – Torsten Schoeneberg May 9 at 20:42
• Actually, all $n \in \Bbb N$ work: $\dfrac{2^{6m+5} -5}{9}$ (accumulates at $-5/9$), $\dfrac{2^{6m+4} -7}{9}$ (accumulates at $-7/9$), $\dfrac{2^{6m+1} -11}{9}$ (accumulates at $-11/9$), $\dfrac{2^{6m} -19}{9}$ (accumulates at $-19/9$), $\dfrac{2^{6m+3} -35}{9}$ (accumulates at $-35/9$), $\dfrac{2^{6m+2} -67}{9}$ (accumulates at $-67/9$), $\dfrac{2^{6m+5} -131}{9}$ (accumulates at $-131/9$), $\dfrac{2^{6m+4} -259}{9}$ (accumulates at $-259/9$), $\dfrac{2^{6m+1} -515}{9}$ (accumulates at $-515/9$), and the pattern in the exponents repeats. – Torsten Schoeneberg May 9 at 22:18
• @TorstenSchoeneberg thank-you I'll try to understand those. My first thought is surprise to see any integers not $\equiv 1\pmod4$ as these sequences contain only those as all but their first element but I immediately see my mistake there. – user334732 May 10 at 3:07
• @TorstenSchoeneberg if all $\Bbb N$ work, and the function is continuous, then does this not mean the graph of the function connects all $\Bbb N$? – user334732 May 10 at 7:44
• @TorstenSchoeneberg (p.s. you were right to interpret that what I'm really talking about here is $\Bbb N/\langle2\rangle$) where the quotient's taken multiplicatively. – user334732 May 10 at 10:42

As alluded to in the comments, and not hard to see, the sequence of predecessor sets of $$\langle 2 \rangle = \lbrace 2^n: n \in \Bbb Z\rbrace$$ for $$f$$ is

$$\dots \mapsto\dfrac{2^{l+m+n}-2^{l+m}- 2^l \cdot 3-9}{27}\cdot\langle 2 \rangle\mapsto \dfrac{2^{m+n}-2^m-3}{9}\cdot\langle 2 \rangle\mapsto \dfrac{2^n-1}{3}\cdot\langle 2 \rangle \mapsto \langle 2 \rangle$$

so the set of $$k$$-th predecessors is

$$\lbrace\dfrac{2^{n_1+...+n_k} -2^{n_2+...+n_k} \cdot 3 - \dots -2^{n_{k-1}+n_k}\cdot 3^{k-3}-2^{n_k}\cdot3^{k-2}-3^{k-1}}{3^k} : n_1, ..., n_k \in \Bbb Z\rbrace,$$

let's call this $$X_k$$. (I.e. we have $$X_0 = \langle 2 \rangle, X_{k+1}:= f^{-1}(X_k)$$.) The Collatz conjecture is equivalent to: every natural number can be written this way for some $$k$$ with all $$n_i \ge 0$$.

What you seem to be asking for are the sets of $$2$$-adic accumulation points of each $$X_k$$ or, more interestingly, $$X_k \cap \Bbb N$$. For $$k=2$$ I pointed out some elements of $$cl(X_2 \cap \Bbb N)$$ in the comments, and I am relatively sure (although I have not proven) those are all elements of $$cl (X_2 \cap \Bbb N) \setminus cl(X_1 \cap \Bbb N)$$ ($$cl$$ meaning $$2$$-adic closure in $$\Bbb Z_2$$).

Obviously, $$cl(X_3)$$ contains all $$\lbrace \dfrac{-2^{l+m}-2^l\cdot 3-9}{27}:l,m \in \Bbb Z\rbrace$$, and a first guess would be that $$cl(X_3 \cap \Bbb N) \setminus cl(X_2 \cap \Bbb N)$$ is that set restricted to $$l,m \ge 1$$ (for such $$(l,m)$$, the set of $$r$$ with $$2^r \equiv 2^{l+m}+2^l\cdot 3+9$$ mod $$27$$ is unbounded, so these are all contained in $$cl(X_3 \cap \Bbb N)$$; the other inclusion looks likely, but I have no rigorous proof for it.) For higher $$k$$, the expressions get more complicated as one deals with more variables, but it's quite possible there is a general argument that

$$cl(X_k \cap \Bbb N) \setminus cl(X_k \cap \Bbb N) \\ \\ \stackrel{?!}= \lbrace\dfrac{-2^{n_2+...+n_k} \cdot 3 - \dots -2^{n_{k-1}+n_k}\cdot 3^{k-3}-2^{n_k}\cdot3^{k-2}-3^{k-1}}{3^k} : n_2, ..., n_k \ge 1\rbrace.$$

I want to emphasize that, even if we have this or something similar which describes all $$cl(X_k\cap \Bbb N)$$, I see no reason why the knowledge of those would immediately bring us closer to a knowledge of the $$X_k$$ or the Collatz conjecture. For example it is quite possible there is some easy argument that $$\bigcup_{k \ge 1} cl(X_k \cap \Bbb N)$$ contains $$\Bbb N$$, but as far as I see, that tells us next to nothing about whether $$\bigcup_{k\ge 1} (X_k \cap \Bbb N) \stackrel{?}= \Bbb N$$.

• Thanks. I have three comments. The original question asks which Collatz sequences, seen as equivalence classes of 5-rough natural numbers the same number of steps from $0$, converge to $0$ (rather than converge to $1$ as the conjecture asks). The point of this is that the points converging to $0$ appear to be the limit points of the conventional graph so sequential continuity should mean if we have all limit points connected by the graph, we have all 5-rough naturals covered (a sufficient set to prove the conjecture). – user334732 May 21 at 19:26
• Next, on the question of $\cap \Bbb N$. The given function $3x+2^{\nu_2(x)}$ can wlog be assumed to commute with $3x$ in the sense $f(3x)=3f(x)$ simply by considering only $\Bbb N\setminus3\Bbb N$, because $3\Bbb N$ are the leaves of the graph, and it is not necessary to prove for the leaves, provided all non-leaves are proven. So the problem of $\cap \Bbb N$ can essentially be ignored, provided we remain within $\Bbb Z[\frac16]\geq0$, because every element is simply a representative for its 5-rough positive integer. – user334732 May 21 at 19:31
• Thirdly, at the bottom I acknowledge $\dfrac{-(2^n+3)}{9}\mapsto\dfrac{-1}{3}\mapsto 0$ is the full set of limit points "of order 2" and this is not too tricky to prove. The points of order $3$ are not that hard. (But harder). Just take $-\frac59$, find the lowest power of $2$ such $f(y)=-\frac{2^m5}9$ has a solution, then by induction find the rest for $m+1\ldots$. In this case we get $-\frac{19}{27},-\frac{29}{27},-\frac{49}{27},\ldots$, then it is necessary to repeat the induction for all of the (infinitely many) predecessors of order $2$... – user334732 May 21 at 19:56
• But I don't see this as the challenge. The challenge is either to find the rule that chooses the "lowest" power of $2$ for each sequence (and show the rule gives a dense or complete set), or (and I see this as more likely) to characterise the induction in such a way that one can step back and have a look at what we've got, in order for the contraction mapping to become apparent. – user334732 May 21 at 19:58
• ...for example, I could quickly throw a hypothesis out there already for what it's worth... the limit points (in the 2-adic metric) of the graph of the orbit of $f(x)=3x+2^{\nu_2(x)}$ through the $5$-rough numbers, contract under the 3-adic metric. Once we have this, we can check it for arbitrary values of the conjecture rather than ones known to converge to $1$, and see if it holds universally. – user334732 May 21 at 20:03