Thread by @AlexKontorovich

Unpopular opinion: The 3x+1 Conjecture might be False!

Here's why I think this may be the case. (thread)

My first paper, with Y. Sinai in 2002, arxiv.org/abs/math/06016… proves that 3x+1 paths are a geometric Brownian motion (in a precise asymptotic sense), with drift log 3/4 < 0

2/ This suggests typical trajectories decay, and can be used to recover the fact (proved before us) that almost every seed eventually reaches a value below itself (but this cannot be iterated, since the paths could fall into a very sparse divergent trajectory). For a long time,

3/ like everyone else, I thought 3x+1 should be true for all kinds of reasons (heuristic/probabilistic, numerically checked up to 2^60). Then a few years ago, I happened to be visiting UCLA, and chatted with Igor Pak, around the time he wrote this: igorpak.wordpress.com/2015/05/26/the…

4/The point was that everyone thought a conjecture was right, so nobody was really working hard to disprove it; could this be the case with 3x+1?

In 1972, Conway showed that some generalizations of 3x+1 were undecidable, by representing in them the halting problem. This is

5/ probably also where Conway got the idea for his FRACTRAN universal Turing machine en.wikipedia.org/wiki/FRACTRAN

So here's the idea: the 3x+1 map is HARDWARE that runs programs, and each initial seed is SOFTWARE, that is, a program that produces some behavior when run on hardware.

6/ This hardware is almost certainly (provably?) not a universal Turing machine, but what does it really do? Every program ever put into it eventually halts at 1, but who's to say there isn't some extremely long program, thousands of bits long, that has some other behavior?

7/ From this point of view, you should not at all be impressed with 3x+1 being verified up to 2^60 -- ok, all programs of length 60 characters halt. That says nothing.

The heuristic/probabilistic arguments point to average behavior, and are probably right - it's entirely

8/ possible that almost all initial seeds decay to 1, while some extremely special ones don't. Makes the problem really hard, since you don't know what you should be trying to prove!

Another close (I think) analogy is to Conway's Game of Life;

9/ it's also a universal Turing machine, because one can find gliders, etc, see en.wikipedia.org/wiki/Conway%27…

Those gliders were not easy to discover, but they were the key to unlocking the universality of the Game of Life.

What if there actually is some 3x+1 software (that is,

10/ some initial seed) that makes something like a "glider" (some kind of understandable repeating but growing pattern) when "run" on the 3x+1 hardware?

Let's try to elaborate a bit more. As in [K-Sinai, op cit], it's enough to look at numbers coprime to 6, and divide out

11/ all powers of 2. So the map is x->(3x+1)/2^k, with k>=1 as large as possible, keeping the result integral (notice the images are always coprime to 3). These k's are the key here. The Structure Thm in [K-Sinai] says that, no matter what "k-Path", that is, sequence of these k's

12/ you want to occur in order, say, (k_1,..,k_N), there's an arithmetic progression of x's which are exactly the seeds having the prescribed first N steps. For example, for the k-Path (1,1,2,2), the initial seed =1(mod 6) is 199, which one can check has this sequence. What's the

13/ point? Here's a pic of a 3x+1 path. Each row is a number in binary; the black dots are 1's and white are 0's. The solid line on the right is that every number is odd. This is the seed 887570260646934643447331259693373543698140232874500619768489156911. You wouldn't know it at

14/ first, but in a few steps, the seed turns into just a few isolated bits (2^220 + 2^151 + 1). What's happening at each bit? The right most (ones-place) is fixed by 3x+1 and doesn't change (until something coming from the left starts to interact with it). The other two bits

15/ start to grow. That's because the map on them is just 3x, not 3x+1! Fun observation: the period of 3 mod 2^m is 2^(m-2). So the multiplicative group generated by 3 in (Z/2^m)* has index 2. That means you can cook up almost any behavior you want on the left, separated by

16/ enough 0's, and have it come in to the right, and interact at *just* the right time with some right-most sequence (which can be controlled by the Structure Thm). Maybe, just maybe, it's possible to create in this way some kind of "glider" that keeps sending information out to

17/17 the left. I've obviously tried off and on for a few years to find such a thing, to no avail. Perhaps it's time to turn these ideas loose (a Polymath?), especially since the prevailing wisdom almost everywhere else is still that 3x+1 is true...