56
$\begingroup$

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 .

$\endgroup$
11
  • 4
    $\begingroup$ It can certainly reduce the time for reducing it to zero by a good amount. For example 27 takes at most 48 steps (out of possibilities considered) instead of 112. $\endgroup$
    – wythagoras
    Sep 3, 2015 at 18:24
  • $\begingroup$ If instead of 3x+1 you had ceil(\alpha x + 1) with \alpha smaller than 2, you could show convergence pretty easily. My feeling is that there is a threshold between 2 and 3 where for \alpha below the threshold, it will be easy to prove convergence, and for \alpha above it, it will be hard. Gerhard "The Threshold Might Be Two" Paseman, 2015.09.03 $\endgroup$ Sep 3, 2015 at 18:47
  • 9
    $\begingroup$ @GerhardPaseman: the idea fails for $\alpha=\frac{\sqrt(5)+1}{2}$ (and 7 as starting point) and more generally for salem numbers. See item 29 in the Lagarias's survey on the $3x+1$ problem: arxiv.org/pdf/math/0309224.pdf; for more detail: math.grinnell.edu/~chamberl/papers/3x_survey_eng.pdf $\endgroup$ Sep 3, 2015 at 22:17
  • 4
    $\begingroup$ @wythagoras: In fact, 27 can take just 23 steps (and that's the minimum): 27 -> 82 -> 41 -> 124 -> 373 -> 1120 -> 560 -> 280 -> 140 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. $\endgroup$ Sep 3, 2015 at 23:48
  • 1
    $\begingroup$ @YaakovBaruch, I am surprised. I must have been thinking about something different from what I said. Thank you for the links. Gerhard "And It Wasn't Floor Either" Paseman, 2015.09.03 $\endgroup$ Sep 4, 2015 at 0:19

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
15
  • 3
    $\begingroup$ At $k = 32$ I have $r = 2394$ residue classes left. After $(k, r) = (24, 1724)$ it started going down and dipped at $(28, 510)$, but now it seems to be growing again. $\endgroup$
    – Ville Salo
    Sep 22 at 9:35
  • 6
    $\begingroup$ I think the residue $(-1) \bmod 2^k$ will never be eliminated. You can see a problem already if you try applying the $3x+1$ rule followed by the $x/2$ rule in that you end up at $(-1)\bmod 2^{k-1}$, sort of no better than you had started. In general, the issue is that after applying the $3x+1$ rule $a$ times and the $x/2$ rule $b$ times, in some order, you will necessarily be between $(-1)\bmod 2^{k-b}$ inclusive and $(-3^a/2^b)\bmod 2^{k-b}$ exclusive. In particular, you will never be able to divide by $2$ more times than you multiply by $3$ because this bound implies $3^a/2^b > 1$. $\endgroup$
    – aorq
    Sep 22 at 17:46
  • 2
    $\begingroup$ Despite @aorq's disappointing comment (that I didn't think about), here are my numbers: 1: 2, 2: 2, 3: 2, 4: 4, 5: 6, 6: 8, 7: 16, 8: 22, 9: 22, 10: 44, 11: 62, 12: 124, 13: 176, 14: 162, 15: 324, 16: 402, 17: 248, 18: 496, 19: 548, 20: 1096, 21: 1328, 22: 782, 23: 1564, 24: 1724, 25: 738, 26: 1476, 27: 1554, 28: 510, 29: 1020, 30: 1052, 31: 2104, 32: 2394, 33: 1122, 34: 2244, 35: 2390. I did not spend many minutes on this, just checked that the first few cases were deduced correctly and let it run, so take with a grain of salt. $\endgroup$
    – Ville Salo
    Sep 22 at 18:48
  • 3
    $\begingroup$ @aorq Great observation! This shows that the claim as stated will not be true for any $k$. However, it may still be the case that $(-1) \hbox{ mod } 2^k$ is the only exception for all sufficiently large $k$, which could still suffice to settle this problem since no natural number can equal $(-1) \hbox{ mod } 2^k$ for every $k$. It's potentially possible that this could still be verified by computer for some $k=k_0$ and then one just has to treat the residue classes $2^{k-1}-1 \hbox{ mod } 2^{k}$ for $k > k_0$ by a separate argument. $\endgroup$
    – Terry Tao
    Sep 22 at 18:49
  • 2
    $\begingroup$ Am I the only one here trying to prove this thing rather than find new problems with this approach?? (NB. is joke) Here's the code pastebin.com/LME3Tm2u in case it inspires someone to verify / go further. $\endgroup$
    – Ville Salo
    Sep 23 at 3:53
8
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Erm... "It ends in a finite cycle" is not the same as "it returns to the original number" Am I missing something? $\endgroup$
    – fedja
    Dec 15, 2017 at 16:15
4
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ I found "since one can get from any power of two to one" a bit jarring at first, and edited it to "since one can get from any power of $2$ to $1$" (to emphasise that the ‘one’s are different, and that the second ‘one’ means the number $1$, not one other power of two). I figured it was not too objectionable, since you likewise used numerals in place of words in the following Claim. I hope this was all right. $\endgroup$
    – LSpice
    Sep 25 at 16:08
  • 4
    $\begingroup$ After reading this, I realized that "relaxation" is not a reliable method to simplify Collatz-like problems. For example, if Collatz is restated using $x \mapsto (3x + 1)/2$ and $x \mapsto x/2$ then the "relaxed" version is exactly the same as the original. This is because neither map can send a non-integer dyadic rational to an integer. Using $x \mapsto 3x + 1$ and $x \mapsto x/2$ gives some more wiggle room so "relaxation" might actually help but there can't be a general reason why "relaxation" would help, it has to be specific to this combination of affine maps. $\endgroup$ Sep 25 at 23:59

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.