Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
×
Math

Mathematician Proves Huge Result on 'Dangerous' Problem (quantamagazine.org) 167

Mathematicians regard the Collatz conjecture as a quagmire and warn each other to stay away. But now Terence Tao has made more progress than anyone in decades. From a report: It's a siren song, they say: Fall under its trance and you may never do meaningful work again. The Collatz conjecture is quite possibly the simplest unsolved problem in mathematics -- which is exactly what makes it so treacherously alluring. "This is a really dangerous problem. People become obsessed with it and it really is impossible," said Jeffrey Lagarias, a mathematician at the University of Michigan and an expert on the Collatz conjecture. Earlier this year one of the top mathematicians in the world dared to confront the problem -- and came away with one of the most significant results on the Collatz conjecture in decades. On September 8, Terence Tao posted a proof showing that -- at the very least -- the Collatz conjecture is "almost" true for "almost" all numbers. While Tao's result is not a full proof of the conjecture, it is a major advance on a problem that doesn't give up its secrets easily. "I wasn't expecting to solve this problem completely," said Tao, a mathematician at the University of California, Los Angeles. "But what I did was more than I expected."

Lothar Collatz likely posed the eponymous conjecture in the 1930s. The problem sounds like a party trick. Pick a number, any number. If it's odd, multiply it by 3 and add 1. If it's even, divide it by 2. Now you have a new number. Apply the same rules to the new number. The conjecture is about what happens as you keep repeating the process. Intuition might suggest that the number you start with affects the number you end up with. Maybe some numbers eventually spiral all the way down to 1. Maybe others go marching off to infinity. But Collatz predicted that's not the case. He conjectured that if you start with a positive whole number and run this process long enough, all starting values will lead to 1. And once you hit 1, the rules of the Collatz conjecture confine you to a loop: 1, 4, 2, 1, 4, 2, 1, on and on forever.

This discussion has been archived. No new comments can be posted.

Mathematician Proves Huge Result on 'Dangerous' Problem

Comments Filter:
  • Interesting (Score:2, Insightful)

    by RobinH ( 124750 )
    I find the interesting thing is that it's so hard (or impossible) to prove. It must be related to the idea of Computability [wikipedia.org], or more specifically the Halting Problem [wikipedia.org]. Let's say you wrote a simple computer program to do this, but made the program stop if it reached 1, then you can't prove that the program won't run forever.
    • Then you can do the same thing, but instead of multiplying it by 3, you CUBE it. Then you can do the same thing, but instead of cubing it, you divide by 6 and subtract 1. Then you can...ad infinium.

    • Re:Interesting (Score:4, Informative)

      by JoshuaZ ( 1134087 ) on Friday December 13, 2019 @12:39PM (#59516418) Homepage
      Yes. It is related to computability and the Halting problem, although in a very general fashion. Suppose one had a different set of rules than Collatz, but each rule was of the same form as with Collatz. Then it turns out that the general problem of whether one will for any input get to 1 is equivalent to the Halting problem. See for example https://link.springer.com/chapter/10.1007/978-3-540-72504-6_49 [springer.com] as well as earlier work by Conway. See in particular, Conway, John H. (1972), "Unpredictable Iterations", Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, pp. 49–52 .
  • by bugs2squash ( 1132591 ) on Friday December 13, 2019 @10:54AM (#59516018)

    Dammit. Now I, one of the worst mathematicians in the country have become obsessed with it.

    Why did you have to go and tell me about it ? Why ?

  • The sequence will slowly "walk forward", halving every time it's even, until it reaches a power of 2 - then it goes down to 1 and stays there.

    Bet the same thing will happen with n*5+1 or n*X+1 with X being any odd number.

    • Re:(n*3+1)/2 (Score:5, Insightful)

      by 110010001000 ( 697113 ) on Friday December 13, 2019 @11:42AM (#59516198) Homepage Journal

      Oh yeah? Prove it.

    • Re:(n*3+1)/2 (Score:4, Informative)

      by JoshuaZ ( 1134087 ) on Friday December 13, 2019 @12:46PM (#59516460) Homepage

      Bet the same thing will happen with n*5+1 or n*X+1 with X being any odd number.

      Actually, the general mathematical consensus is that it is very likely that if one uses an odd number n greater than 3 (such as the 5 in your example) that there will likely be sequences which increase without bound. Here's the basic idea:

      Let's first think about the Collatz example itself. There are two equally likely possibilities given a given x, either we go from x to x/2 (when is even) or we go from x to 3x+1. But in the second case, we immediately will always then divide by 2. So we should think of two cases, where with 50% chance we go to x/2 and with 50% chance we go to (3x+1)/2. Now, this means that given a large x, about half the time it goes to about x/2 and about half the time it goes to about (3/2)x. Now, that means that we should expect on "average" that the growth for a given iteration is about x times the square root of (1/2)(3/2), which is less than x, since 3/4 But what if we replace the 3 with a 5? Well, we can try the same logic, but now we have a growth which looks like the square root of (1/2)(5/2), and that is greater than 1. So we expect that on average to see sequences get very big.

      • by Shotgun ( 30919 )

        You and the other mathematicians that reached the consensus are way over-thinking it.

        The crux of the issue is that the divide by two case is an entrapment case. If repeated infinitely odd_number*n+1 will eventually land on a power of two. Once that occurs, the whole ball of wax unwinds down to one very quickly. The average square root is a non-sequitor. One way to prove the conjecture would be to show that there is no way to get caught in a higher-order loop before the algorithm can hit a power of 2.

        • The difficulty with that line of logic is that powers of 2 get very rare as one gets very big numbers, so the chance that one hits a power of 2 gets very small. But of course, we can't make this notion rigorous enough right now; that 5x+1 has sequences which grow without bound is about as open as proving that 3x+1 doesn't.
      • by psergiu ( 67614 )

        Yes they'll get very big but eventually they'll still hit a power of two. There will just be (way) more iterations.

  • It seems to me the problem comes down to understanding if the results of 3x + 1 and x/2 spend more time as an odd or an even number. If odd, then the number will explode. I'll go one further: the magic number is close to 1.5 (though I'm kind of doing this on a scratchpad, so I could be off). But my thinking is that if I've taken a number and multiplied it by 3, it's going to take me 1.5 times of dividing by 2 to get back to the number I've started with (it's actually slightly greater than that because I'
    • An odd number times an odd number is always odd (by definition, neither odd factor has 2 as a factor itself, the product of them being multiplied will also not have 2 as a factor). Adding one to an odd number is always even. There is a chance that the result is divisible by 2, 4, 8, etc. Therefor there is only opportunity for more time being spent even than odd.

      This is the easy to prove part. Whether the amount of extra time spent even "out-divides the multiplication while odd" is the less easy part.
      • by Shotgun ( 30919 )

        Why is the amount of time spent even or odd make any difference? Once a 2^n number is encountered, its going to all unravel down to one. All that must be shown is that 3n+1 will eventually meet 2^n

    • by Shotgun ( 30919 )

      How much time it spends as odd or even is a non-sequitor. The only thing the algorithm has to do is eventually land on a number equal to 2^n, where n is between 1 and infinity. 2^n will devolve to 1 in this conjecture for all values of n. The question is if repeated an infinite number of times, would 3n+1 eventually encounter a whole power of 2.

      If you can prove that 3n+1 will encounter a power of 2 if repeated less than an infinite number of times, then you have proven the conjecture is true.

  • It seems that this is just a way to start with a prime number and increase its value till you reach a multiple of two. Once you reach a multiple of two, the rules will make it roll down to one, and then the repeating pattern starts. A "proof" for this is to simply show that N*3+1 will produce a number divisible by two?

    • by arcade ( 16638 )

      I think you've misunderstood, unless I've misunderstood you:

      1: 1*3+1 = 4 ... 4/2 = 2 ... 2/2 = 1.
      2: 2/2 = 1
      3: 3*3+1 = 10 .. 10/2 = 5 .. 5*3+1 = 16 .. 16/2 = 8 ... 8/2 = 4 .. leads to 1.
      4: 4/2 = 2 ... 2/2 = 1
      5: 5*3+1 = 16, see 3.
      6: 6/2 = 3, see 3.
      7: 7*3+1 = 22 .. 22/2 = 11 ... 11*3+1 = 34 ... 34/2 = 17 .. 17*3+1 = 52 .. 52/2 = 26 .. 26/2 = 13 .. 13*3+1 = 40 .. 40/2 = 20 .. 20/2 = 10, see 3.

      Number 7 there illustrates it. You get 52, then 26, then 13 .. it's not rolling all the way down to 1 before being mult

    • Look at the powers of 2. The only way you get to 1 is by coming down to 1. Thus, 2, which must be divided by 2 gives you one. The only way to get 2 is from 4 being divided by 2. In fact, once you end up on any power of two, it is just a number of divisions by 2 to get you to 1. If you end up at 1024, then divide by 2 for ten times and you end up at 1.

      So how to you end up on a power of 2? Two possible ways:
      1. Half of the next higher power of two.
      2. 3n + 1

      So what are the powers of two that minus
    • A "proof" for this is to simply show that N*3+1 will produce a number divisible by two?

      Trivial, as long as you remember that you're always doing this to an odd number. Multiplying two odd numbers together will always produce another odd number, and adding one to it will produce an even number, so the step after the multiplication and addition is always division. (If you don't understand why the multiplication always produces an odd number, you're probably not ready to work on the conjecture.)
  • by FeelGood314 ( 2516288 ) on Friday December 13, 2019 @12:09PM (#59516298)
    This proof is a neat way of looking at problems. By looking at this proof you might gain an insight into solving other problems.

    Here is the very simplified version of the argument. Take a large sample of numbers that have a certain random(ish) weighted distribution based on some criteria. This weighting is such that after you apply the Conjecture to each number in the set the weighting of the resultant set stays about the same. One weighting would be no numbers that are multiples of 3, lots that are 3n+1 and a few that are 3n+2. (You can easily see that the conjecture quickly weeds out numbers that are multiples of 3). Now if I can show that 99% of the numbers in these sets get smaller over time then with a lot more work I could generalize this to say 99% of numbers behave this way.
  • by daytonduck ( 1336545 ) on Friday December 13, 2019 @12:36PM (#59516394)
    In thinking about this, I'm looking at odd numbers, specifically, odd numbers that are whole multiples of 3. Those are the numbers that are the result of the first step of the simple arithmetical expression. Every odd number has an odd number as its multiple of three. From there, you must prove that for every prime number greater than two, when multiplied by three and one added to it, is not prime. Since these will be an even integer greater than two, it will not be prime, and therefore, at some point, will reach an integer power of 2, and subsequently the 4,2,1 pattern. Charting it out in excel, you can see some pretty interesting patterns develop quite quickly. The most interesting one is 27. It requires over 100 steps to resolve (25 is the next highest before that, requiring 23 steps to reach 1). Its sequence also contains several two-digit primes and a few three-digit primes. Also, 27 will never be encountered again in a future sequence. Since it is a multiple of three, none of its multiples of powers of 2 can be encountered as the result of adding one to a multiple of three.
  • Why? (Score:5, Insightful)

    by Hartree ( 191324 ) on Friday December 13, 2019 @01:18PM (#59516582)

    It's not the problem itself, it's the tools and knowledge for proving it that's the real prize.

    The Collatz Conjecture is a very famous problem. One of the greats of 20th century mathematics, Paul ErdÅ's, said of it, "Mathematics may not be ready for such problems.".

    What he was meaning is that we just didn't have the tools and the view in order to be able to deal with such a simple but elusive question about something as basic as the integers.

    We're not there yet by any means, but perhaps mathematics is closer to being ready for such a question.

  • Do I feel a Numberphile video coming on? They've talked about Collatz before [youtube.com].

    ...laura

  • by Jerrry ( 43027 )

    I have a complete proof for this conjecture. Unfortunately, it's too large to fit in this post.

C'est magnifique, mais ce n'est pas l'Informatique. -- Bosquet [on seeing the IBM 4341]

Working...