Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam The Collatz Conjecture is one of maths' most notorious problems. Its statement is deceptively simple: take any positive integer, n. If it is odd, multiply it by 3 and add 1 (giving 3n+1). If it is even, divide it by 2 (giving n/2). Then repeat these steps with the result, forming a sequence of numbers. If we start with, say, 5, this sequence would be 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1.... - as you can see, it gets to 1 and then repeats the 4-2-1 sequence ad infinitum. The Collatz Conjecture states that regardless of which positive integer you start with, the sequence will end in the 1-4-2-1 loop. Posited in 1937, the Collatz Conjecture remains one of math's most well-known unsolved problems. However, new computational methods may shed light on the problem.
The biggest recent breakthrough using traditional mathematical methods was in 2019, when mathematical supercelebrity Terence Tao of UCLA released a proof implying that about 99% of numbers greater than a quadrillion eventually reduce to values less than 200, which means 99% of numbers satisfy the Collatz Conjecture since all numbers less than 200 have manually been shown to end in the 1-4-2-1 loop. Tao's method was analogous to how you sample a population for an election: you have to pick a sample that is representative of the full population. Similarly, Tao tried using a sample of positive integers to see whether the conjecture would hold. The problem with such a method is that each number in the sample changes its character with each iteration - numbers change from even to odd and become multiples of different numbers. The sample must therefore be constructed keeping this in mind. Tao managed to create a method to select samples that would maintain their original character through each iteration, making it easier to keep track of how the sample would behave. This method resulted in what was at the time "arguably the strongest result in the long history of the Conjecture." More recently, Marijn Heule, a computer scientist at Carnegie Mellon University, has tried applying computational methods that provided successful proofs of the Pythagorean triple problem and Schur number 5 to the Collatz Conjecture. Heule and his team created a rewriting system that simulates the Collatz sequence on mixed binary–ternary representations of positive integers. They also proved that similar rewriting systems using unary representations of positive integers do not allow the sequence to terminate, as required by the conjecture. Although their paper doesn't prove the Collatz Conjecture, it presents novel approaches that may yet prove useful in solving this problem. More broadly, this paper demonstrates the significant influence that computational methods hold in mathematics today. We discussed the Ramanujan machine in a previous article - this is yet another example of modern computing proving to be extremely useful in pure maths.
1 Comment
Aleh Kavalenka
16/3/2024 09:01:59 pm
Hallo ,
Reply
Leave a Reply. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|