Relaxed Collatz 3x+1 conjecture

Question

The Collatz $3x+1$ conjecture claims that any positive integer can eventually be reduced to $1$ by iterative application of the maps $x \mapsto 3x+1$ whenever $x$ is odd and $x \mapsto x/2$ whenever $x$ is even.

While the Collatz conjecture is still open, I wonder if the following relaxed version is any simpler. In this relaxed version we are allowed to apply maps in any order keeping the numbers integer. That is, if $x$ is odd, we still have to apply the $x \mapsto 3x+1$ map; but for even $x$, we have the freedom to choose between $x \mapsto 3x+1$ and $x \mapsto x/2$. The conjecture is that for any positive integer, we can reduce it to $1$ with some iterative sequence of maps.

Clearly, the Collatz conjecture would imply the relaxed version. But it may happen that the relaxed version is much simpler. Is it?

The question is inspired by discussion of the sequence http://oeis.org/A109732 which is a permutation of the odd positive integers iff the relaxed version of the $3x-1$ variant of the Collatz conjecture holds.

UPDATE. The minimum number of iterations to reach $1$ in this relaxed version is given by http://oeis.org/A127885 and this number is often smaller than that for the Collatz conjecture given by http://oeis.org/A006577 .

Answer 1

I predict that this weakened conjecture can be proven with some computer assistance. Basically one has to show the following claim:

Claim There exists a natural number $k$ such that, for every residue class $n \hbox{ mod } 2^k$, there exists $1 \leq j \leq k$ and a sequence of Collatz moves that can be applied to an input in this residue class that involves $j$ divisions by two and at most $j \frac{\log 2}{\log 3}$ applications of $x \mapsto 3x+1$. (Note that as long as one doesn't divide by $2$ more than $k$ times, one only needs to know the residue class of the input mod $2^k$ to be able to describe the tree of available Collatz moves.)

Indeed, if this claim were true, then any sufficiently large $n$ would be able to be iterated to a number smaller than $n$ regardless of which residue class mod $2^k$ one started with. This would reduce the problem to a finite number of inputs which can then be treated by computer.

In principle, the above claim can be tested numerically for any given $k$. I expect the proportion of residue classes that violate the claim to drop super-exponentially in $k$, so for $k$ large enough there should be no counterexamples at all among the $2^k$ residue classes, so for $k$ large enough the claim should be true. The only issue is whether verifying it is within current computational capability.

[To justify why I think the proportion of violators is super-exponential: even if one just does the ordinary Collatz iteration, the Chernoff inequality will give an exponential upper bound $O(e^{-cn})$ on the proportion of violators, basically because one is running a gambler's ruin (random walk with negative drift). If one has the option of applying up to $a$ applications of $x \mapsto 3x+1$ first, then one has $a$ different options that each have $O_a(e^{-cn})$ chance of failure, and which are only weakly correlated, so I would expect the chance that they all fail to drop to $O_a(e^{-acn})$. Letting $a$ grow slowly to infinity gives the superexponetial decay prediction.]

Just to illustrate the claim, here is how it plays out for small $k$:

• $k=1$: If $n=0 \hbox{ mod } 2$ the claim is true (divide by 2 immediately), otherwise it is false.
• $k=2$: If $n=0,2 \hbox{ mod } 4$ the claim is true as before; if $n=1 \hbox{ mod } 4$ the claim is also true (apply $3x+1$ and then divide by 2 twice); but $n=3 \hbox{ mod } 4$ survives as a counterexample.
• $k=3$: from the preceding discussion the only potential counterexamples are $n=3,7 \hbox{ mod } 8$. Unfortunately, there are no further eliminations at this stage.
• $k=4$: from the preceding, the surviving candidates are $n=3,7,11,15 \hbox{ mod } 16$. One can eliminate $n=3 \hbox{ mod } 16$ here (apply $3x+1$, then divide by two, then apply $3x+1$, then divide by two three more times), but there are unfortunately no further eliminations at this stage, leaving $7,11,15 \hbox{ mod } 16$ as the surviving residue classes.

The number of survivors is slowly growing in $k$ here because the superexponential decay has not yet kicked in, but I believe it will do so eventually, and hopefully while still within range of computer verification.

Answer 2

I'll write $\longrightarrow$ for some standard iterations and $\implies$ for some possibly non-standard iterations. The relaxed Collatz conjecture is that for all $x$, $x \implies 1$. I'll call counterexamples to the conjecture escapees.

First of all, since it's a good example of the notation, a lemma: for all $a$, $4 a \implies 9 a + 1$.

Proof: $4a \implies 12 a + 1 \longrightarrow 36a + 4 \longrightarrow 18a + 2 \longrightarrow 9 a + 1$.

$\square$

Now here is what I will try to show:

Theorem: If $x$ is the smallest escapee, then $4x \implies 1$.

Proof: By elementary considerations, $x \equiv 3 \pmod{4}$. If $x \equiv 2 \pmod{3}$, then $\frac{2 x - 1}{3} \longrightarrow 2 x \longrightarrow x$. So in this case, $2 x$ can't be an escapee, and neither can $4 x$.

The next case is $x \equiv 0 \pmod{3}$. Write $x = 12k+3$. Using the lemma, $4x \implies 27k+7$. Observe that $x > 9k+2 \rightarrow 27k+7$ if $k$ is odd. Now if $x \equiv 15 \pmod{24}$, we also have that $4x \implies 1$.

It's also possible that $x \equiv 3 \pmod{24}$. In that case, we have $x = 24 j + 3$ and $x \longrightarrow 27j+4$. This means $j$ cannot be even. So we drill down again, with $x = 48i + 27 \longrightarrow 81i+49$. This means $i$ cannot be odd. But also, $4x = 4(48i+27) \implies 81i + 92$, so if $i$ is even, the next step brings us under $x$. This covers all the $x \equiv 0 \pmod{3}$ cases.

So far, our result is that if $x \implies 4x$, then $x \equiv 7 \pmod{12}$. Now I'll handle that case. Suppose $x \implies 4x$ and $x = 24k + 7$. Then we have:

$4x = 4(24k+7) \implies 9(24k+7)+1 = 216k+64 \longrightarrow 108k+32 \longrightarrow 54k+16$.

But also, $18k+5 \longrightarrow 54k+16$. This means $18k+5$ is an escapee too, but it can't be, since it's less than $x$. So the hypothesis is false and we have $x = 24k + 19$ instead.

Now, consider:

$4x = 4(24k+19) \implies 216k + 172 \longrightarrow 108k + 86 \longrightarrow 54k + 43 \longrightarrow 162k + 130 \longrightarrow 81k+65$.

By similar reasoning, $k \neq 3 \pmod{4}$, or else we can continue the chain two more steps to get an escapee less than $x$. Finally,

$x = 24k+19 \longrightarrow 72k+58 \longrightarrow 36k + 29 \longrightarrow 108k + 88 \longrightarrow 54k + 44 \longrightarrow 27k + 22$.

shows that $k$ can't be even, and substituting $k = 4 j + 1$:

$27k + 22 = 108j + 49 \longrightarrow 324j + 148 \longrightarrow 162j + 74 \longrightarrow 81j + 37 < x$

completes the proof, since that's all the cases.

$\square$

Corollary: if the Collatz conjecture is false and the smallest counterexample leads back to itself then that number is not a counterexample to the relaxed Collatz conjecture. In other words, if $y$ is the smallest number satisfying $\neg(y \longrightarrow 1)$, then $y \longrightarrow y$ implies $y \implies 1$. This is a weaker version of what I originally thought I had proved.

Corollary: If $4x$ is an escapee, then there is an escapee smaller than $x$. This suggests to me a recursive descent strategy where we attempt to show $z \implies 4k < 4x$. But it's not clear if number-crunching will get us anywhere further.

Answer 3

Update: See end of post.

Having abandoned my previous approach, I have found another computer-assisted approach to the problem that should heuristically work and which is not subject to the obstructions of my previous approach.

Define a legal move to be an affine function $x \mapsto ax+b$ that is the composition of a finite number of the maps $x \mapsto \frac{x}{2}$ and $x \mapsto 3x+1$ (allowing repetitions). For instance, $x \mapsto \frac{9x+a}{4}$ will be a legal move for $a = 4, 5, 7, 8, 10, 15, 16$, and more generally legal moves take the form $x \mapsto \frac{3^n x + a}{2^m}$ for some natural numbers $n,m,a$ with $a$ not divisible by $3$ (except when $n=0$). Note that while the generating moves $x \mapsto \frac{x}{2}$ and $x \mapsto 3x+1$ can map integers to half-integers, which can in turn be mapped to other dyadic rationals (rationals whose denominator is a power of 2), they cannot turn half-integers (or other non-integer dyadic rationals) back into integers. Hence if a legal move takes an natural number $x$ to a natural number $y$, all intermediate steps in that move must also be natural numbers, and so $y$ can be reached from $x$ by a relaxed Collatz iteration. Since one can of course get from any power of $2$ to $1$ by a legal move, and one can use $x \mapsto 3x+1$ to get from a multiple of $3$ to a non-multiple of $3$, the relaxed Collatz conjecture now follows from

Conjecture Given any natural number $x_0$ that is not a multiple of $3$, there exists a power of $2$ that is reachable from $x_0$ by a legal move.

In the previous approach the strategy was to iterate $x_0$ to something smaller. Here we will take the opposite approach of instead making $x_0$ larger in search of a power of two, but taking advantage of the flexibility available in the relaxed setting to "aim" where the iterates go to a certain extent.

More specfically, I claim that the above conjecture follows from the following (in principle numerically verifiable) claim.

Claim There exists $n,m$ with $3^n > 2^m$ and an interval $[a_-,a_+]$ of length at least $4 \times 3^n$ such that $x \mapsto \frac{3^n x + a}{2^m}$ is a legal move for every natural number $a \in [a_-,a_+]$ that is not a multiple of $3$.

Indeed, suppose that we have verified this claim for some $n,m$. Then we have

Interval expansion lemma If $[x_-, x_+]$ is an interval with $x_-, x_+$ natural numbers (excluding the degenerate case when $x_-=x_+$ is a multiple of $3$), then every natural number $y$ in the interval $[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ that is not a multiple of $3$, can be reached by a legal move from some natural number in $[x_-,x_+]$ that is not a multiple of $3$.

Proof It suffices to show that $y$ is reachable by legal moves from two consecutive elements of $[x_-, x_+]$ (or just one, if $x_-=x_+$). From the claim, $y$ is reachable from any $x$ with $$ \frac{3^n x + a_-}{2^m} \leq y \leq \frac{3^n x + a_+}{2^m}$$ (the fact that those $\frac{3^n x + a}{2^m}$ with $a$ divisible by $3$ are omitted from the claim is not an issue here since these only generate multiples of $3$, and $y$ is assumed not to be a multiple of $3$). This constraint restricts $x$ to an interval. By the hypothesis on $y$, the right endpoint of this interval is at least $x_-+1$ and the left endpoint is at most $x_+-1$, so the intersection of this interval contains two consecutive elements of $[x_-,x_+]$ (or just one, if $x_-=x_+$), giving the lemma. $\Box$

Note that if $[x_-,x_+]$ has length $h$, then the new interval $[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ has length greater than $\frac{3^n}{2^m} h$, since $a_+ - a_- \geq 4 \cdot 3^n$. If one iterates the interval expansion lemma from an arbitrary starting point $x_0$ that is not a multiple of $3$, one creates a sequence of intervals $[x_{-,k},x_{+,k}]$ of length $\gg (3^n/2^m)^k$ with and midpoint $\alpha_k (3^n/2^m)^k$ for some real numbers $\alpha_k$ that form a Cauchy sequence and thus converge to some limit $\alpha$ as $\alpha \to \infty$, such that every natural number in this interval that is not a multiple of $3$ can be reached by a legal move from $x_0$. Because $\log (3^n/2^m) / \log 2$ is irrational, we see from the equidistribution theorem that $\log ( \alpha (3^n/2^m)^k ) / \log 2$ can be arbitrarily close to an integer, so in particular the interval $[x_{-,k},x_{+,k}]$ will contain a power of two for infinitely many $k$, giving the conjecture (of course, powers of two are not multiples of 3).

The following heuristic argument suggests that the claim should be true for sufficiently large $n,m$ with $3^n/2^m$ close to $1$. In this regime we have $n \approx r \log 2$ and $m \approx r \log 3$ for some large $r$. A legal move of the form $x \mapsto \frac{3^n+a}{2^m}$ can be generated by $n$ applications of $x \mapsto 3x+1$ and $m$ applications of $x \mapsto x/2$, in any order; so there are $\binom{n+m}{m}$ ways to generate a legal move, which by Stirling's formula is $$ \approx \exp( r (\log 6 \log\log 6 - \log 2 \log\log 2 - \log 3 \log\log 3) ) \approx \exp(1.196 r)$$ up to lower order terms. On the other hand, a calculation using the law of large numbers suggests that the typical size of the offset $a$ is $$\approx 3^n \approx 2^m \approx \exp( r \log 2 \log 3 ) \approx \exp(0.762 r),$$ again ignoring lower order terms (indeed, I would expect $a$ to have a roughly log-normal distribution around a quantity of this magnitude, and obey a Benford law, in the spirit of this paper of Lagarias and Soundararajan.). Thus for $r$ large there are significantly more legal moves than likely offsets $a$, and the only obvious restriction on the offset $a$ is that they are not multiples of three. Standard heuristics (based on the coupon collector problem) then suggest that the claim should hold for $r$ large enough.

I ran some numerics but the intervals I found fell a bit short of the claim. For instance, when $n=7$ and $m=9$ (so one considers legal moves of the form $x \mapsto \frac{2187x+a}{512}$) I could find an interval of length 134, but no longer, in which every shift $a$ in this interval that was not a multiple of 3 gave a legal move. There are several lower order terms in the analysis (including a log factor arising from coupon collector problem) that may require one to take $r$ to be relatively large in order to create the intervals of the length required in the claim, given that the difference between the two rates of exponential growth in the heuristc analysis is somewhat slight.

p.s. One consequence of either the original or relaxed Collatz conjecture is that one can reach $1$ from any starting natural number $x_0$ by multiplying by ratios of natural numbers and their Collatz iterates. This weaker claim is in fact a theorem, due to Applegate and Lagarias.

UPDATE: Unfortunately the same counterexample of $-1$ that blocked the previous approach, blocks this approach also. A variant of the expansion lemma analysis reveals that after applying $n$ copies of $x \mapsto 3x+1$ and $m$ copies of $x \mapsto x/2$ starting from $-1$, one should be able to reach $\lfloor \frac{-3^n+a_+}{2^m} \rfloor$ (if it isn't a multiple of 3) or $\lfloor \frac{-3^n+a_+}{2^m} \rfloor - 1$ (otherwise); but $-1$ can only iterate to negative numbers, hence $a_+ < 3^n + 2^m \leq 2 \cdot 3^n$. Since $a_-$ is positive, this prevents the interval $[a_-,a_+]$ being of length $4 \cdot 3^n$ as desired. So that was somewhat disappointing; still, I'll leave my two answers up on this question in case it is helpful for some future attempt at this problem. It is interesting that while the problem is posed for positive numbers, the negative counterexample -1 to the conjecture (and its relatives) are somehow lurking behind the scenes to sabotage a number of otherwise viable attacks.