22
$\begingroup$

Let $C$ : ${\mathbb N}\longrightarrow {\mathbb N}$ be Collatz's map defined by $C(n) = 3n+1$ if $n$ is odd, and $C(n)=n/2$ if $n$ is even. Then according to Collatz's conjecture, we should have $C^k (n)=1$, for all $n>0$ and $k$ large enough. Assume that the conjecture holds and for $n>0$ define the top of the orbit of $n$ by $$ t(n) = \text{max} \{ C^k (n), \ k\geq 0\} $$

Define $$ T(N) = \text{ Card}\{ n\ , \ t(n) \leq N\} /N $$

Had the assymptotic behaviour of T(N) been studied ?

$\endgroup$
6
  • 6
    $\begingroup$ Many elementary things like this have been considered so far, without much success -- do you see a reason to hope that studying this particular function may yield something interesting? $\endgroup$
    – Stefan Kohl
    Feb 19, 2015 at 16:47
  • 7
    $\begingroup$ I did some computations with SAGE which suggest that T(N) could maybe be convergent. $\endgroup$ Feb 19, 2015 at 17:04
  • 2
    $\begingroup$ Could you show us a graph of $T(N)$? $\endgroup$ Feb 19, 2015 at 22:31
  • 4
    $\begingroup$ @JosephO'Rourke: For $k=1 \dots,20$ we get the following values of $T(2^k)$: 1, 0.75, 0.5, 0.625, 0.40625, 0.515625, 0.429688, 0.4375, 0.353516, 0.34375, 0.283203, 0.261719, 0.259644, 0.414551, 0.398773, 0.395294, 0.392509, 0.398922, 0.397013, 0.396653. $\endgroup$
    – Stefan Kohl
    Feb 19, 2015 at 23:47
  • 2
    $\begingroup$ @Stefan I also found T(2^21) =0.39725, T(2^22)=0.39609 and T(2^23)=0.39674. $\endgroup$ Feb 20, 2015 at 11:45

4 Answers 4

13
$\begingroup$

If the sequence $(T(N))_{N \in \mathbb{N}}$ converges and the limit is not equal to $0$, this would imply either positive predecessor density for $1$, cf. e.g.

Günther J. Wirsching, On the problem of positive predecessor density in $3n+1$ dynamics, Discrete and Continuous Dynamical Systems - Series A (DCDS-A), Volume 9, Issue 3, 2003, Pages 771 - 787, doi:10.3934/dcds.2003.9.771,

or the existence of nontrivial cycles.

If the sequence converges, it therefore seems hopeless to prove this with elementary means.

$\endgroup$
1
  • $\begingroup$ Thank you Stefan for your answer and your nice graphics. I indeed found the same values for T(2^n). $\endgroup$ Feb 20, 2015 at 6:59
23
$\begingroup$

As Stefan Kohl has pointed out it is not possible to give good lower bounds for $T(N)$ without making progress on the Collatz problem itself. However it is not difficult to understand what the truth is, and the argument below will yield a rigorous upper bound.

Instead of the map $C(n)$ as defined, it is better to consider $C_0(n) = n/2$ if $n$ is even, and $(3n+1)/2$ if $n$ is odd. For large $n$, this map multiplies by approximately $1/2$ or $3/2$ with probability $1/2$, and the first several iterations of the map behave independently. The crux of the Collatz problem is that this independent behavior roughly persists till the end making the iterates come down to zero -- that of course is hard, but it is easy to see that as many initial iterates as you like will behave independently just by looking at residue classes modulo a large power of $2$.

Now consider the random walk starting with a random real number $\alpha_0=\alpha$ chosen uniformly from $[0,1]$, and setting $\alpha_k = \alpha_{k-1} \times 3/2$ or $\times 1/2$ with equal probability. Then for each such realization take the max of $\alpha_k$ over all $k\ge 1$. In this setting you are asking for the probability that this maximum is at most $1/2$. (The half arises because of the difference between your $C(n)$ and the more natural $C_0(n)$.)

It is easy to upper bound the probability above by running the random walk for some number of steps. After $25$ steps, a computer calculation gave the upper bound $0.40641\ldots$, which agrees with Stefan Kohl's numerics.

$\endgroup$
7
$\begingroup$

(Without any intended answer:) Two further pictures.
First, a bit more detailed curve up to $N=100 000$. I supressed the datapoints $T(N)$ at $N$, where the frequencies are below $6$ here to have the curve a bit more sharpened/showing the peaks in the underlying frequencies-list:

bild1

And it seems to me, that the actual frequency of occurence of N as maximum of a trajectory gives some more intuition what's going on here. While the above cumulative curve tends to "iron out" any variability when going to the right, the systematic spikes of the frequencies-table here indicate, that such spikes do not wear out in the long run but (likely) even get higher counts (again I left out the datapoints of smaller frequencies in the picture):

bild2

$\endgroup$
1
  • $\begingroup$ Very revealing graphs, especially the second one. $\endgroup$ Feb 21, 2015 at 20:42
6
$\begingroup$

Here is a plot of Stefan Kohl's data (now supplemented by Paul Broussous), which they kindly provided in response to my query:


          CollatzPlot
Added as per TMA's suggestion:
          CollatzPlot1


$\endgroup$
3
  • 2
    $\begingroup$ Much as I enjoy your explanatory graphics, I find this one misleading. I recommend either plotting T(N) for all N in the range ( and then using a log scale), or instead relabelling and plot integer k against T(2^k). A comparison of this graph with the first modification (T(N) vs log N for N not powers of 2) might serve as a good topic in data representation. $\endgroup$ Feb 20, 2015 at 1:31
  • 3
    $\begingroup$ Maybe it's just my software, but the numbers labelling the $N$-axis in the second diagram are running into each other. $\endgroup$ Feb 20, 2015 at 2:15
  • $\begingroup$ @GerryMyerson: Yes, sorry, fixed the problem. Also extended with Paul's 3 additional data points. $\endgroup$ Feb 20, 2015 at 13:00

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