5 ms·
Terence Tao makes progress on the Collatz conjecture (2019)
- nielsbot 4y agoRelated: Veritasium did a video about the Collatz (3x+1) conjecture https://www.veritasium.com/videos/2021/7/30/the-simplest-math-problem-no-one-can-solve https://www.veritasium.com/videos/2021/7/30/the-simplest-mat...
- mythamatics 4y agoAny theories about massively large numbers and Collatz conjecture? Would Collatz conjecture reduce Graham's number to 1? Would these proofs get presented before a generic one?
- ballenf 4y agoI never thought one could actually do arithmetic on Graham-size numbers. If you didn't have the branch in Collatz, then it would be algorithmically computable. But then so would Collatz itself.
- pclmulqdq 4y agoI don't think that's the issue. The Collatz conjecture has a non-branching form in binary (using weird operations), but that doesn't really help anything because the operations are hard to analyze as mathematical operators. Here is the non-branching form: 0. Start with an odd number n 1. Apply n = 3n + 1 2. Count trailing zeroes of n 3. Right shift n by the trailing zero count 4. Return to (1), stopping at n = 1
- leereeves 4y agoHow do you "count trailing zeroes of n" without branching?
- pclmulqdq 4y agoI don't know how you formulate it mathematically for unbounded numbers without branching. On a computer, there are a variety of ways (including a single assembly instruction), but pretty much all of them rely on n being bounded. If you're trying to feed a SAT solver, you can bound the size of the numbers at some level, and then pass one of the closed-form formulas into the solver.
- leereeves 4y agoYeah, it seems important that the formula support unbounded numbers, because the numbers can grow inside the sequence. Naively, it seems like any starting value (except those for which you already know the full sequence) might lead to values that exceed any arbitrary bound.
- pclmulqdq 4y agoFrom a theoretical standpoint, I think you could also attempt to approach this by thinking about a field where the "remove trailing zeros" step is built in. It may be a very weird field to do math on, and we may be unprepared for the math that is required, but it's a way to remove branching from the operations required for a proof. There's nothing inherently special about the branchiness of "remove trailing zeros" as an operation if you drill down into it: addition, for example, also needs conditional execution (based on the carry in to each section of a number). Otherwise, if you're searching for a counterexample, bound n by some ridiculous number of bits (whatever your supercomputer supports) and run your solver with a simple closed form.
- eru 4y agoHere's how you can do a 'branchless' one, using Python syntax: f = lambda n: (n & 1) * n + ((n + 1) >> 1) No need to count any trailing zeros. Of course, the multiplication sort-of acts as a branch.
- eru 4y agoI don't think 'non-branching' is something we can rigorously define. I mean, lambda calculus doesn't have any build-in branching, but you can style write arbitrary programs in it. Same for 'post correspondence problem' or SKI calculus.
- pclmulqdq 4y agoI agree with you completely. People get hung up on the fact that the conjecture has a "2-way" decision, but if you redefine the problem, there are a ton of ways to make it have no decision points. The one I posed is a simple mutation, but there are turing machines that compute the Collatz algorithm, you can turn it into a geometry problem, etc. All of these can be defined as "branching" or "non-branching" however you want.
- eru 4y agoYes. 'Branching' and 'non-branching' make sense in the context of specific architectures and/or languages. Just not really in an abstract algorithmic sense.
- dogecoinbase 4y agoIf a computational process could not complete before the heat death of the universe, does it have an output?
- eru 4y agoAre you talking about an abstract mathematical process, or a specific physical embodiment?
- owenpalmer 4y ago> Intuition might suggest that the number you start with affects the number you end up with End up with...? That's a weird way to phrase it. The algorithm can run infinitely. The number you start with does affect the sequence. They should have omitted that paragraph all together.
- turingfeel 4y ago> The algorithm can run infinitely. Really? Isn't the whole point of proving the conjecture attempting to answer that question? If you have an example of a starting integer that causes the algorithm to run infintely I'd be eager to hear it.
- owenpalmer 4y agoEnding up with an infinite repeating sequence and "running infinitely" are not the same thing
- renewiltord 4y agoMan, I think if you think this level of precision is hard to disambiguate I wonder how you handle the notational abuse common in Mathematics. It might not be the field for you.
- eru 4y agoJust use a slightly different rule that stops when it reaches 1.
- hansvm 4y agoHas the acyclic unbounded case been ruled out?
- drexlspivey 4y ago> Tao used this weighting technique to prove that almost all Collatz starting values — 99% or more — eventually reach a value that is quite close to 1. This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. If they reach a value below 200 then they surely will reach 1 (since all sub 200 sequences have been brute forced). What am I missing?
- pclmulqdq 4y agoWhat you're missing is that "99% or more" is not 100%. Tao's technique does not preclude the existence of a small cycle of large numbers that never get below 200 (or rather, below 2^64, since we have tried all of those).
- drexlspivey 4y agoI am commenting on the fact that these two statements are equivalent: * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach a value below 200. * This allowed him to draw conclusions along the lines of 99% of starting values greater than 1 quadrillion eventually reach 1. yet the author used the first which seems weird
- pclmulqdq 4y agoThe paper's "200" comes from plugging "1 quadrillion" into Terence Tao's new theorem directly, and not applying any other results. I think they wanted to communicate only the meaning of the theorem, not the context around it.
- FartyMcFarter 4y agoAt some point I considered doing a computational search for cycles (perhaps using a SAT solver or something similar), but then I found this on Wikipedia: > The length of a non-trivial cycle is known to be at least 186265759595. This probably makes it very hard to find a cycle unless we know of some properties of the numbers involved in the cycle.
- jbandela1 4y agoI hate and fear the Collatz conjecture and Goldbach conjecture. Unlike a lot of other unsolved math problems they are very simple to state and think about but then end up in a quagmire. I have lost many nights of sleep and productive days getting nerd sniped by these problems.
- eru 4y agoThere's lots more of these kinds of problems. Fermat's Last Theorem used to be one of them. Another one (that's actually solvable by mere mortals) is the 'firing squad synchronization problem': > The name of the problem comes from an analogy with real-world firing squads: the goal is to design a system of rules according to which an officer can command an execution detail to fire so that its members fire their rifles simultaneously. > More formally, the problem concerns cellular automata, arrays of finite state machines called "cells" arranged in a line, such that at each time step each machine transitions to a new state as a function of its previous state and the states of its two neighbors in the line. For the firing squad problem, the line consists of a finite number of cells, and the rule according to which each machine transitions to the next state should be the same for all of the cells interior to the line, but the transition functions of the two endpoints of the line are allowed to differ, as these two cells are each missing a neighbor on one of their two sides. > The states of each cell include three distinct states: "active", "quiescent", and "firing", and the transition function must be such that a cell that is quiescent and whose neighbors are quiescent remains quiescent. Initially, at time t = 0, all states are quiescent except for the cell at the far left (the general), which is active. The goal is to design a set of states and a transition function such that, no matter how long the line of cells is, there exists a time t such that every cell transitions to the firing state at time t, and such that no cell belongs to the firing state prior to time t. It's fun to work out.
- dankearney 4y agoI have a proof, would love HN’s perspective. A cycle means the product of all of the increases (each of which is a scaling factor of 3x+1 / x) equal the product of the decreases (a power of 2). 3x+1 / x = 3 + 1/x, so except for trivially small x, each increase is just a bit larger than 3. The product of those increases is a small amount larger than a power of 3, and has to exactly equal a power of 2. Larger cycles allow that little error above a power of 3 to compound, but larger cycles also necessitate larger values of x, which shrink the error.
- eru 4y agoThat sounds like a heuristic, probabilistic argument for why we expect the conjecture to hold, but it doesn't seem like an airtight proof. (Not even a sketch of a proof.)
- dankearney 4y agoIt’s not probabilistic — for any cycle length, you can compute the minimum possible x value that could possibly be the lowest odd number in the cycle. That value trends smaller as the cycle length grows.
- eru 4y agoSorry, I still don't get it. Could you explain it with fewer steps left out? To be honest, I doubt that you will have come up with something that Terrence Tao and other geniuses haven't, but it's interesting to figure out exactly where you went wrong. (Or, on the off chance, seeing how you might be right after all.)
- dankearney 4y agoYes and thanks for giving me the time of day! 1: Derive that, for a cycle with o odds and e evens, that the product of the increases due to odds (3 + 1/x) must exactly equal the product of the decreases by halving, which comes out to 2^e. The trivial cycle meets this, since (3+1/1) = 2^2. As another example, for the alternative rule where odd numbers go up by 3*n + 5, there are some cycles, like 19 => 62 => 31 => 98 => 49 => 152 => 76 => 38 => 19. The increases here come out to approximately 3.26, 3.16, and 3.10, the product of which is exactly 32, or 2^5. 2: Observe that each (3 + 1/x) term (except for trivially small x) is greater than 3, but near it. For x=101, (3+1/x) is about 3.01. As a result, the product of the increases is going to be larger than a product of 3, but somewhat close to one. 3: Observe that we need the little error above the power of 3 to be large enough that the LHS exactly equals a power of 2. This is challenging because as the numbers in the cycle get larger, (3 + 1/x) gets closer to 3.0, which makes it harder for the product to be much larger than a power of 3. And, for large powers of 3, the nearest power of 2 is never particularly close — we actually need this error to compound to a product substantially larger than the power of 3. We can attempt to achieve this with longer cycles for more compounding error, or smaller values of x. 4: Observe that, for a given number of odd numbers in a cycle, we can find an upper bound for the lowest value in the cycle. For example, let’s use o=5. We need (3+1/x1)(3+1/x2)(3+1/x3)(3+1/x4)(3+1/x5) = 2^e. 3^5 is 243, so the easiest e value is 8, making the RHS 256. If we define x1 as the smallest number in the cycle, we can see that x1 can’t be too large. x1=1001 implies that x2, x3 etc are at least 1003 and 1005 etc. Plugging these in, the LHS is 243.4 — not near 256. And making x2, x3 etc larger only makes it worse. Okay, so try a smaller x1 - you can compute that the largest possible x1 that can possibly make the LHS equal 256 is 31. However we know that 31 and every number below it does not have a cycle, so we know there are no cycles of length 5. We can actually define the RHS as the next power of 2 above 3^o, which is floor(log2(3^o))+1. 5: Repeat this process for larger cycle lengths and you see that the largest viable value does not trend larger, it trends smaller.
- tmhn2 4y agoJohn Conway showed a generalization of this problem is undecidable. I can't find a PDF but there's a blurb and citation on wikipedia: https://en.wikipedia.org/wiki/Collatz_conjecture#cite_ref-33 https://en.wikipedia.org/wiki/Collatz_conjecture#cite_ref-33 I don't know enough to say anything more intelligent about it, but I guess if you are reading through comments on this article you might find it interesting!