# recent ideas/leads & the collatz random walk

hi all. found some very neat new papers on the collatz conjecture. would like to go into much more detail about them, but if a blog writer writes and nobody comments, does it make any noise? in short michel finds some collatz-like problems at the heart of some low-complexity TMs. laarhoven ties the iteration dynamics into de bruijn graphs. cool! both refs show that this problem is increasingly being taken seriously. couldnt have imagined it would generate so much more research in the 2 decades since Ive been looking at it. 2 of my favorite quotes, both coming close to some of my original motivations for studying it…

laarhoven:

“Because of its simple formulation, researchers from many different branches of mathematics have at one time or another encountered this problem and have become fascinated by it. This has lead to hundreds of papers in the last few decades, with each researcher using his own area of expertise to shed a new light on this problem.”

michel:

Actually, the halting problem for Turing machines launched on a blank tape is m-complete, and this implies that this problem is as hard as the problem of the provability of a mathematical statement in a logical theory such as ZFC (Zermelo Fraenkel set theory with axiom of choice). So, when Turing machines with more and more states and symbols are studied, potentially all theorems of mathematics will be met. When more and more non-halting Turing machines are studied to be proved non-halting, one has to expect to face hard open problems in mathematics, that is problems that current mathematical knowledge can’t settle.

Many universal models of computation are known: Turing machines, tag-systems, cellular automata, Diophantine equations, etc. (see [35]). Of course, any universal model can simulate and be simulated by any other universal model. But it is Collatz-like functions, and not another model, that appear naturally in this study. Their unexpectedly pervasive presence leads to wonder about the signiﬁcance of their status among mathematical beings.

have been thinking about random-walk type angles on this question lately that give me a few new ideas. these two following graphs show the random walk in forward or reverse order. the collatz path isnt really much of a random walk, it tends to be biased toward increasing early on, and then decreasing later. could that insight help toward finding patterns?

def walk(n)

n1 = n0 = n
x = 0
l = []
while (n != 1)
l << n0
if (n.even?) then
n >>= 1
n0 -= 1
else
n = ((n * 3) + 1) >> 1
n0 += 1
end
x += 1
end

(1..l.size).each \
{
|i|
puts([i, l[i - 1], -i, n1 + l[-i] - l[-1]].join("\t"))
}
puts
end

n = 3
100.times \
{
walk(n)

n += 4
}


* * *

heres another short snippet related to an idea mentioned in [8]. it involves finding impossible vs possible iterates mod $2^n$, here $n=8$. it is possible to compute this more efficiently recursively for the set associated with $2^n$ in terms of the set for $2^{n-1}$ but thats not implemented here (exercise for reader). here stopping distance is the time for an iterate to go less than the initial seed. this replicates an exercise from a book by Klee and Wagon. it outputs the values in triples, the forbidden value mod $2^n$, and the final coefficients $a, b$ on the iterated eqn $a \cdot 2^n + b$ (notice $a$ is in the form $3^m$)
 [[27, 2187, 242], [31, 2187, 274], [47, 2187, 412], [63, 729, 182], [71, 729, 206], [91, 2187, 790], [103, 2187, 890], [111, 2187, 958], [127, 6561, 3280], [155, 2187, 1336], [159, 6561, 4102], [167, 2187, 1438], [191, 2187, 1640], [207, 2187, 1780], [223, 729, 638], [231, 2187, 1984], [239, 6561, 6154], [251, 2187, 2158], [255, 6561, 6560]] 

def scan(n)

l = []

(1...n).each \
{
|i|
a = n
b = i

p([a, b])
loop \
{
if (b.odd?) then
a *= 3
b = b * 3 + 1
print("x")
end
if (b.even?) then
if (!a.even?) then
l << [i, a, b]
break
end
a /= 2
b /= 2
print("/")
end
puts("\t" + [a, b].inspect)
break if (a < n && b <= i)
}
puts
}
p(l)
end

scan(2 ** 8)


* * *

another wildcard. a proof was recently claimed by Zheng on arxiv [9][12]. did skim this halfway-decent paper a bit. posted it as a reply on tcs.se question asking about grammar-based approaches [13] (highly relevant to tcs.se, and an attack style I highly favor & personally conjecture to be ultimately viable, and am not alone in that regard). what followed was a case study in the group psychology (literally, groupthink) of a scientific community. quickly got -8 votes, 1 upvote! some ensuing comments.

SN wrote in a comment “to me it does not look credible. they claim to solve a problem widely considered out of reach by little more than symbol manipulation. the only idea seems to be to add edges to the collatz graph, and then they claim that the new edges actually don’t matter. i think an answer that calls undue attention to a preprint by virtually unknown authors claiming a result on a crank-friendly topic should be discouraged, -1”. partly on this cue I replied in a comment. “some further look at the paper, am tending to agree with SNs comment. there is a crucial step on p15, lemma 6.1 which attempts to relate model M0 to MS but it seems to be missing details, have some gap, and/or incorrect.”

then it got deleted by typically heavy-handed policeman k., ouch! ironically, wondering if I had not mentioned that the authors claimed a proof, the audience/mod might not have reacted in such a negative fashion. have a few issues with this; think tcs.se can be useful in alerting people to flawed proofs or areas where they are questioned, and even the lead moderator Eppstein with his tens of thousands of se rep points has expressed this pov in meta.[10]

my own feeling is that it’s useful to have a place to publicly discuss whether it’s worthwhile to pay any serious attention to certain controversial preprints. I guess my question for here is, should this exchange be that place?

but he apparently has no cajones or “dog in that fight” to push for it (as the vernacular goes)….

so the community works in something like an extreme-thinking, “all or nothing” fashion and his idea on meta got mass-armtwisted into exactly the opposite outcome. even if there is a lot of decent math/analysis in the zheng paper, quite a bit of it valid, the whole thing is trashed and vaporized from mere mention because of the invalid claim. whitewashed out of existence like graffiti on the wall! is this any way to do science/research? apparently so! at least I got my @#\$& 6 pts back after the whole futile runaround!

oh yeah, which reminds me, am still attempting to find a single paper published by k., even as a preprint… now that seems to be the quixotic quest…. he listed a paper on his home page once awhile back, but seems to have disappeared without a trace…. :shock:… oh wait correction! I guess its back on his pg or maybe I was mistaken about it being taken off![11] my mistake! oh hell he has new a paper coauthored with Cook, so clearly Im out of line here!

so, what you call a learning experience! a teachable moment!

a. 3n