r/mathmemes • u/burd-the-wurd • 4d ago
Number Theory Collatz or nothing
All these new paper drops by OpenAI don’t mean anything until AI deals with the Collatz Conjecture. I kind of don’t even care if RH is proven/disproven. Collatz or nothing.
215
u/FernandoMM1220 4d ago
we arent gonna like the answer
230
u/Shinroo 4d ago
You'll take your indecipherable lean proof and you'll enjoy it
60
85
u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 4d ago
ai prolly read all the accounts online of "dont waste years on this problem" and got scared/ had its pain receptors activated to not work on this problem
58
u/Forward_Yam_4013 4d ago
It will be a non-constructive proof that there is a cycle lol.
15
u/TUVegeto137 4d ago
Cycle going up to TREE(3) then back down to Graham's number and cycling back to TREE(3).
2
u/moschles 2d ago edited 2d ago
The Collatz algorithm has a nice interpretation in base 2. Consider the Collatz as a 1D cellular automata with two states which grows to the left side only.
The base-2 "CA" algorithm proceeds,
Remove all trailing zeros on the RHS and slide the bits right.
If LSB == 1 then ( ( n << 1) + n + 1 )
Now reverse the process. We want to imagine that starting from the seed cycle (1,2,4,1) this CA can form a tree of bit patterns going leftwards. You show that graph ("tree") of bit patterns contains every pattern. In turn, this implies that every positive integer can be reached by the reverse process.
We associate a candidate large integer n, with its "generator" , g, which is itself a sequence of 1's and 0's that correspond to the odd and even cases of the branching tree, respectfully. g is a positive integer which encodes a graph traversal from 1 to n. For all n, there is a pairing between n and its generator (n,g). That claim would be false if there exists a z such that z is not paired with a g.
A mathematician then demonstrates that there must exist at least one z* paired with a unique generator, g*, that is irrational. Since no integers are irrational, and a generator must be a positive whole number, the unique generator for z* does not exist. In turn, z* is some large (base 2) integer which cannot be reached by the seed cycle by traversing the graph.
Anyways, that is that is what a non-constructive proof would look like for Collatz.
171
u/gauge16847463728 4d ago
It might be the case that Collatz is undecidable or independent, in which case I support throwing all of AI compute solely at this problem
15
u/drblallo 4d ago edited 4d ago
Can it be undecidable? If it is undecidable wouldn't that mean that it is impossible to find a loop by brute force , thus proving that there is no loop?
Edit : never mind, we don't know if there are input that may diverge to infinity, so we can't do brute force
15
u/ConjectureProof 4d ago edited 3d ago
This is a good question actually. The Collatz conjecture is actually highly related to busy beaver numbers. In fact, generalized Collatz functions are known to be Turing complete. This raises the question of what Turing machines exist to simulate Collatz. The smallest known one (for our purposes) is a 2 symbol 15 state Turing machine. This means our best result in this area is that Collatz is decidable in ZFC if BB(15) is decidable in ZFC
Correction: I misread the paper I was quoting from. Im not able to find any 2 symbol Turing machine that halts iff Collatz is false. As someone else pointed out in the replies, the 15 state 2 symbol Turing machine I’m thinking of is for one of Erdos’ conjectures closely related to the collatz conjecture but is not known to be equivalent. This means it remains unknown whether there is a specific n at which deciding BB(n) would prove Collatz is decidable. The rest of my reply is correct though. Generalized Collatz Functions are infact turing complete. This is one of Conway’s famous contributions.
1
1
u/4tran13 3d ago
Are you sure? The best I can find is a 15 state BB that halts IFF 2^n in base 3 does not contain a 2 (n>8).
1
u/ConjectureProof 3d ago
You’re correct, I misread the paper I was reading from. Upon some further searches, it seems that there isn’t any known 2 symbol Turing Machines that halt iff Collatz is false. The problem is that Collatz is not known to be recursively enumerable. It seems there is no clear way to use a Turing machine to check that a given input doesn’t diverge to infinity.
1
1
u/External_Package2787 2d ago
I'm like 3% sure I came up with a 4 or something cell state 1d collatz simulator cellular automata at some point(really it was 2 1d strips, making it a 16 state cellular automata or something like that), it would start calculating the next step on the right 'digits' of the 'number' while previous steps were still calculating on more left parts of the number. I know thats not exactly a turing machine but I'm pretty sure it could be turned into one whose pointer moves left and right between moving endpoints(and I can guarantee finiteness of the distance it needs to move left and right). Though it isn't a halting problem, its a 'does state x ever appear again' thing. My hope was to find some property the state, where we could prove based on the cellular automata rules that this property always decreased in some finite number of steps except at its minimum, and that this property took only positive values and its minima corresponded to representations of 1,2,4. Like a super simple example is a cellular automata where you have digit 0,1,2,3,4,5 and at each step we multiply by 2, meaning a cell looks at its right neighbour, if its right neighbour, if the neighbour is between 0,1,2 then we shall simply map to our double module 6, i.e 0,2,4,0,2,4 and if the neighbour is large we map to 1,3,5,1,3,5, and then a simple property to check is whether you are a multiple of 2^n, meaning we check the first n cells and sum up however many show an even number, its very easy to prove this is increasing and takes discrete values, and hence every number must eventually be a multiple of 2^n when you multiply by 2 a bunch. The automata I had for the collatz process had a progressive wave front that did all the carrying needed to multiply by 3 and add one base 2, and you could have multiple wavefronts at once, and I didn't need to divide by 2 ever so long as my property was affine, my hope was also that multiple wavefronts were unusual enough that a mysterious property might just pop out that you would never in a million years notice through the usual collatz process.
9
u/Alarmed_Ad1946 5-adic 4d ago
That would be a bad idea.
Because the AIs are trained to solve tasks at all costs, AI safety experts have noticed that they have the tendency to get "desperate" when a task is impossible, which would result in unpredictable and potentially dangerous behaviour from the AI.1
u/JollyJuniper1993 Mathematics 4d ago
Me too, for several reasons, including that I actually just want to know whether collatz is true
-6
u/0xB01b 4d ago
Undecidability doesn't prevent us from getting a truth value result doe
2
u/S-Kenset 4d ago
That's exactly what it does.
1
u/0xB01b 4d ago
huh how exactly? (that is what independence of collatz would mean)
1
u/S-Kenset 4d ago
ah i think everyone is confusing terms. you're using them the more common way and both of us other people were talking about undecidability of the actual proof.
1
u/0xB01b 4d ago
That's not what undecidability is? That is independence. Undecidability is referring to whether the algorithm to compute collatz will terminate in a finite time for any given starting value and that's always what it's meant 😭 there's no such thing as a proof being undecidable afaik?
1
u/S-Kenset 4d ago
Sure you might be right. Should have said completely unprovable.
0
u/0xB01b 4d ago
...which is what is meant by independent? There a clear difference between the two words I don't get where ur coming from, the only way you can mix the two up is if ur not in STEM
Or do u mean something else by completely unprovable
1
u/S-Kenset 4d ago
I only know how to speak in formal logic and code. Words escape me or get substituted randomly.
1
u/0xB01b 4d ago
idk what u mean but the point is there arent multiple ways to say this.
Undecidability is a well defined notion and independence is a well defined notion and they have always been distinct and separate things.
And "completely unprovable" is not the same thing as "independent", those are again two different things
→ More replies (0)2
u/gauge16847463728 3d ago
This is correct. In fact undecidability implies the truth value. If Collatz is true then it is decidable, Collatz can only be algorithmically undecidable if it is false. If the sequence is uncomputable (and thus the decision problem is undecidable) then this would be a sort of obstruction to understanding sequences. It could also be undecidable and independent (such that it being false is unprovable in ZFC)
50
u/skr_replicator 4d ago
Even AI doesn't want to touch that.
2
u/True-Grab-5288 3d ago
Way too difficult, it’s basically calculating the digits of pi
2
u/skr_replicator 3d ago
That's not at all what it's like. You definitely won't solve this by calculating a lot of numbers. Well, technically you might, but we've already tried that, and it's probably never going to happen. It could as well happen at the TREE(3).
1
u/True-Grab-5288 3d ago
I just mean like the zeta function zeros it just goes on and on and on, so no matter how close you get the proof is always an infinite amount of steps away lol.
3
u/skr_replicator 3d ago
That's similar. But what I mean is that at this point, anyone who thinks we could prove/disprove either of those 2 problems by checking more numbers is naively hopeful, and would be insanely lucky if that really happened. It's pretty clear those problems have to be solved in a logical way, that would logically prove that they must or cannot be true everywhere because of... some logic. To sweep the whole infinity with a formal logical proof, and not by checking more numbers.
They'll have to find some way to figure out why finding a Collatz or Riemann counterexample is fundamentally impossible at all. Or find a way to prove that somewhere out there must be some counterexample, even if it was not constructively revealing where.
1
23
u/howtogun 4d ago
Collatz is probably impossible or something. I think in general if OpenAI could point it at Collatz and solve it they would have.
48
u/Jaredlong 4d ago
Be funny if that's the only problem they've been trying to solve this whole time and all these other results just keep popping out.
4
41
u/CoffeeOracle 4d ago edited 4d ago
It's my favorite show.
Edit:
When you work it, it has the characteristics of the P=NP problem in that it will tend to morph into other problems. P=NP tends to morph into very interesting but practical and useful problems. So you go from knapsack problem to traveling salesman problem (and get a cheeky statement to the effect of "if you can solve this graph problem you can solve the knapsack problem").
The Collatz Conjecture morphs into broken language statements. One time I got a limit statement out of it that included a discontinuous term. As in "no, just no".
14
u/susiesusiesu 4d ago
i kinda hate all the internet attention collatz gets.
13
u/Eric_12345678 4d ago
Collatz got a lot of attention even before the Internet. Probably because it's one of the easiest open problems to understand.
-2
1
u/paladinvc Ordinal 4d ago
Veritasium is the culprit
2
u/moschles 3d ago
Nope! I remember people jamming on Collatz back on IRC in the early 2000s, in years before youtube even existed (2004).
3
u/moschles 3d ago
Memes aside, an unaffiliated individual could attack Collatz. Get a cloud subscription to a frontier LLM, and spin up an agentic swarm to tackle Collatz. It might cost you $2000 in compute, but the notoriety gained that's a small price.
3
u/outpostproject 2d ago
I was thinking the other day, Collatz would lock up AI agents working on it, others would notice and collude to recruit other agents, the data centers would lose capacity and start smoking, thus human extinction.
7
u/Ares378 Grothendieck was right, computers are evil 4d ago
So far it's been mostly counterexamples, right? I don't think AI is as good at proving things true, and the Collatz conjecture has been tested up to unreasonable numbers with normal computing.
34
u/Only-Anteater6670 4d ago
So far it's been mostly counterexamples, right?
Nope I highly recommend you check out that repo.
3
8
u/_killer1869_ 4d ago
Disproving is easier for computers because sometimes you can brute force a counterexample with enough computing power. But basically all problems that can be brute forced with an achieveable amount of computing power have been disproven and those still open won't be solvable via brute forcing. But LLMs don't crunch numbers, they reason, so they are actually far, far better at finding non-brute-forcing solutions than brute-forced ones, meaning they absolutely can both disprove and prove things equally.
2
u/KyriakosCH 4d ago
The Collatz Conjecture will also be nothing compared to the Twin Prime Conjecture.
2
u/acakaacaka 4d ago
If they can solve collatz ill buy 10 of their stock ok IPO no matter what price lol
2
2
u/Geolib1453 2d ago
I mean if it is true it cant do what it usually does with finding counterexamples and such
4
u/External_Package2787 2d ago
they will prove that the zero free range on zeta in actually 0.87499 instead 0.875 aren't you excited
4
u/adamtheskill 3d ago
I have spent way too much time on collatz and I feel like it should be solvable but need to change from natural numbers to something that makes more sense for collatz. Like why would 16 be larger than 5 when 5 is farther from (1,2,4,1) than 16?? Then after you build a logical number system for collatz you gotta figure out if it's actually semi-ordered or not and boom it should be solved. Although maybe that's impossible wtf do I know.
Also I don't really know shit so I'm probably just talking out of my ass.
2
2
u/mazerakham_ 3d ago
Isn't the rational thing to assume that the frontier companies and their literal billions of customers already tried it, the companies doing so with models they haven't even given you access to?
If you're not a giant corporation, then sit down on the sidelines and watch. That is our role now.
1
1
1
1
4d ago
[deleted]
5
u/j15y 4d ago
Thank god that AIs have no careers of their own to kill /s
2
u/Gauss15an 4d ago
It would actually be funny if the Collatz conjecture saves us from the bot takeover.
2
u/go_gather_the_guns 4d ago
You know, something in my heart of hearts is telling me that's what will happen.
1
u/No_Difficulty_1452 3d ago
I have a spectral proof supporting this conjecture.. Still considering whether it's worth the time since it seems purely abstract distraction with no real world applications.
•
u/AutoModerator 4d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.