1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Torsten Schoeneberg May 9 at 20:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Torsten Schoeneberg May 9 at 22:18
  • $\begingroup$ @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. $\endgroup$ – user334732 May 10 at 3:07
  • $\begingroup$ @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$? $\endgroup$ – user334732 May 10 at 7:44
  • $\begingroup$ @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. $\endgroup$ – user334732 May 10 at 10:42
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – user334732 May 21 at 19:26
  • $\begingroup$ 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. $\endgroup$ – user334732 May 21 at 19:31
  • $\begingroup$ 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$... $\endgroup$ – user334732 May 21 at 19:56
  • $\begingroup$ 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. $\endgroup$ – user334732 May 21 at 19:58
  • $\begingroup$ ...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. $\endgroup$ – user334732 May 21 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.