6
$\begingroup$

Let $C$ be the Collatz map on the natural numbers, defined by: $$C(n) := \begin{cases} n/2 & \text{if} \;n \;\text{even} \\ (3n+1)/2 & \text{if} \;n \;\text{odd} \end{cases}$$ enter image description here
The inverse of $C$ is: $$C^{-1}(\{n\}) = \begin{cases} \{2n\} & \text{if} \;n \not \equiv 2 \pmod 3 \\ \{2n, (2n-1)/3\} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$ Let $n$ be a natural number with $n \equiv 2 \pmod 3$. Let $C^{-k}$ be $C^{-1} \circ \cdots \circ C^{-1}$ ($k$ times).
Consider the cardinals $c_1(n,k):= \vert C^{-k}(\{2n\}) \vert $ and $c_2(n,k):= \vert C^{-k}(\{(2n-1)/3\}) \vert$.

Question: Is it true that $\forall n \equiv 2 \pmod 3$, $\exists k>0$ such that $c_1(n,k) \neq c_2(n,k)$?
Remark: It is checked for $n \le 10^8$.

Assuming the answer is no, let $n$ be a counter-example.
Motivation-Question: Is $n$ also a counter-example of the Collatz conjecture?

Assuming the answer is yes, let $\alpha$ be the map defined by:
$$\alpha (n) := \begin{cases} 1 & \text{if} \;n \not \equiv 2 \pmod 3 \\ 1+\min\{k>0 \ \vert \ c_1(n,k) \neq c_2(n,k) \} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$

By looking to the graph below, we get for example that $\alpha(8)=2$ and $\alpha(20)>3$.

A natural number $N$ is called a champion if $\forall n<N$ we have $\alpha(n)<\alpha(N)$.
Below is the list of the first champions (read as $[N,\alpha(N)]$):

[2, 4]
[20, 6]
[182, 8]
[1640, 10]
[14762, 12]
[132860, 14]
[1195742, 16]
[10761680, 18]
[96855122, 20]

Observation: Two consecutive champions $N$ and $N'$ in the finite list above satisfy the relations: $N'=9N+2$ and $\alpha(N')=\alpha(N)+2$.

Bonus question: Is the list of champions exactly $(N_r)_{r \ge 1}$ with $N_r = \frac{9^r-1}{4}$ and $\alpha(N_r) = 2r+2$?

Remark: I don't know whether $N_r = \frac{9^r-1}{4}$ is champion $ \forall r \ge 10$; but I have checked that $\alpha(N_r) = 2r+2$, $\forall r \le 26$, and we can confidently conjecture that it is true in general (the proof should be workable using the fact that the base-$9$ representation of $N_r$ is $222 \cdots 2$).

$\endgroup$
  • 1
    $\begingroup$ Sequence appears here: oeis.org/A125857 $\endgroup$ – Fred Kline Dec 19 '17 at 11:05
  • 1
    $\begingroup$ Yes, it is the sequence of numbers whose base-$9$ representation is $22222222.......2$. It is nice to see that they appear in several other mathematical subjects. $\endgroup$ – Sebastien Palcoux Dec 19 '17 at 13:46
  • $\begingroup$ It would be great if you could establish a link with prime gaps, which on average also grow logarithmatically. $\endgroup$ – Sylvain JULIEN Dec 19 '17 at 19:45
3
$\begingroup$

What is $k_n$ (the ones you checked for $n \le 10^8$)?

Some thought on the champions, but I didn't dig much yet:

I think the tree must be symmetric up to $[k-1]$ (I'll come to symmetry later), you could still have $c1=c2$ without symetry, but it would probably not hold with the other rules (e.g. alternance). I have to check.

For visual purpose, I put the "$\{2n\}$" leafs on the left in the left part of the tree, and on the right in the right part of the tree. I put multiple of $3$ in red, and circled the "$n \equiv 2 \pmod 3$".

I call "symmetric counterparts" elements which map to each other in the symmetry (e.g. $69$ and $213$ are symmetric counterparts. $80$ and $26$ are symmetric counterparts). For the symmetry to be kept, every counterparts must be of the same value modulo $3$ ($0$, $1$ or $2$).

enter image description here

From the example above, you can see that the symmetry is lost on the $2^{k-2}-1=7$ element, which is not $\equiv 2 \pmod 3$ like its counterpart $23$, so it has one child less.

It is well known that in a Collatz sub-sequence starting with $2^a-1$, you will always climb up to $3^a-1$ in $a$ steps, which is the largest "forward sub-sequence" up to this $n=2^a-1$, so my guess is that having a champion has something to do with that (especially knowing that the forward sub-sequence must have a symmetric counterpart of the same kind, which is the case as shown bellow).

So for the example above, on the left of the tree we have a forward sub-sequence starting with $2^{k-1}-1=15$: $\{15,23,35,53,80\}$, ending with $3^{k-1}-1=80$, and on the right, the (almost) symmetric counterpart sub-sequence starting with $2^{k-2}-1=7$: $\{7,11,17,26\}$, ending with $3^{k-2}-1=26$.

Note that $[k-1]$ is even since $[k+1]=\alpha (n)$ is even, so $3^{k-1}-1$ can be rewritten $9^{\frac{k-1}{2}}-1$, and from there you divide by $4$ to reach $n=20$ which leads to your formula $n=\frac{9^{\frac{k-1}{2}}-1}{4}$. The $\{(2n-1)/3\}$ element ($13$ in the example) is therefore $\frac{(2\cdot\frac{9^{\frac{k-1}{2}}-1}{4})-1}{3}=\frac{(\frac{3^{k-1}-1}{2})-1}{3}=\frac{3^{k-2}-1}{2}$ and the parent ($26$) is therefore $3^{k-2}-1$ which we know leads up to $2^{k-2}-1=7$ but in 1 step less than its counterpart, which gives a symmetry break ($2^a-1$ is not $\equiv 2 \pmod 3$ like its successors).

For the symmetry part, I still have to look, but perhaps this kind of thing might do the trick:mod 18 (probably depends on $k$)

I also have to look at other possible "symmetry breaks", and probably draw some other cases to find some rules as soon as I have more time.

$\endgroup$
  • $\begingroup$ Welcome to mathoverflow! Thanks for your investigation! $k_n$ is just a positive integer depending on $n$. The formulation of the question was probably confusing, I have clarified it. $\endgroup$ – Sebastien Palcoux Dec 23 '17 at 23:18

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.