close
AI

Facing the simplest unsolved mystery in the history of mathematics, Tao Zhexuan gave the most important proof in decades

87b0c73a-1e48-11ea-8131-aaaa00151f43.jpg

Editor’s note: This article is from WeChat public account “Xinzhiyuan” (ID: AI_era), source: quantamagazine, editor: Daming, Xiaoqin, 36 氪 Published with permission.Take any positive integer and divide it by 2 if it is even.If it is an odd number, multiply it by 3 and then add 1, then repeat the process, and the result will always be 1.This problem is known as the “Klatz conjecture.”It can almost be said to be the simplest form of expression in the unsolved problems in the history of mathematics, and therefore it has become the most enticing fruit on the towering tree of mathematics.Many senior mathematicians have warned that this problem is simply poisonous, and it is a charming “sea monster song”: you can never go out when you walk in, and you can no longer make any other meaningful results.”This is a dangerous problem,” said Jeffrey Lagarias, a mathematician at the University of Michigan and a Kratz conjecture expert. “Many people are fascinated by it, but it is really impossible to solve at the moment.” But there are always unbelievers.Tao Zhexuan is one of them, and he has achieved the farthest result to date on the Kratz conjecture.On September 8, Tao Zhexuan posted a certificate on his personal blog, showing that at least for most natural numbers, Kratz’s conjecture is correct.Although this certificate is not a complete one, it has already been regarded as a significant progress on this “toxic” issue.”I didn’t expect to solve this problem completely, but the progress made so far has exceeded my expectations.” Tao Zhexuan said.Kratz’s conjecture: The simplest “impossible” problem Kratz’s conjecture is said to have been proposed by the German mathematician Lothar Collatz in the 1930s.However, its specific origin is unknown. It is known that it spread from the University of Syracuse to Bell Labs and then to the University of Chicago.Because there were many disseminators in the early days, during the dissemination process, the Kratz conjecture harvested many names: 3n + 1 conjecture, parity normalization conjecture, Ulam problem, Kakutani conjecture, and so on.The simplicity of its presentation makes it sound like a game at a party.For any positive integer, if it is odd, multiply it by 3 and add 1.If it is even, divide it by two.Keep repeating this process, what will happen in the end?Intuitively, you may think that the difference in the initial numbers will affect the final result.Maybe some numbers start with the end result of 1, and others start with infinity.But Kratz predicts otherwise.He speculated that if the initial number is a positive integer and the process is repeated enough times, the final result will be 1 no matter what the initial number is.After that, 1 becomes the initial number and will fall into a loop: 1, 4, 2, 1, 1, 2, 2, 1 … For many years, many people have expressed the Kratz conjecture simply (this conjecture is also known as the famous”3x +1 problem”) and fascinated by the problem.At present, mathematicians have tested 50 billion numbers, and Kratz’s conjectures are all correct.”This question doesn’t seem to have any barriers to understanding. You only need to know ‘multiply by 3’ and ‘divide by 2’ to understand it completely. The mathematician Marc Chamberland said that the temptation is hereChamberland once made a YouTube popular video about the problem, calling it “the simplest impossible problem.” The following is a Kratz conjecture verification page, you can try it yourself. Https: // www.dcode.fr/collatz-conjecture Although the expression and understanding of the Kratz conjecture are very simple, it is very difficult to prove strictly. In the 1970s, mathematicians proved that almost all Kratz sequences, that is, the calculation process of the repeated Kratz conjectureThe number obtained in the sequence will be smaller than the first number, which is obviously an incomplete proof. But there is also evidence that the final value of almost all Kratz series is approaching 1. Since 1994,Before Tao Zhexuan made new progress this year, Ivan Korec maintained the best record for proving this problem, and the final value of the series is gradually becoming smaller. But the distanceThe core problem is still a great distance.Over time, many mathematicians have come to the conclusion that Kratz’s conjecture proves that the problem is completely beyond the current understanding, so it is best to focus on other problems, because it is futile to continue.Joshua Cooper of the University of South Carolina said in an email: “The Kratz conjecture is a well-known problem that mathematicians tend to put a warning before each discussion so as not to waste time on it.Do research. “Unexpected reminder: Tao Zhexuan was inspired by comments from anonymous netizens. As early as 40 years ago, Lagarias was deeply interested in this conjecture, when he was still a student.For decades, he has been an unofficial collector of Kratz conjecture questions.He organized a collection of papers related to this problem, and published some of them in 2010 under the title “Extreme Challenge: 3x + 1 Problem”.Lagarias said: “Now, after I know more about this problem, I still think it is impossible to solve.” Tao Zhexuan usually does not waste time on “impossible” problems.In 2006, he received the Fields Award, the highest honor in mathematics, and is widely regarded as one of the most outstanding mathematicians of the younger generation.He is used to solving problems, not chasing dreams.Tao Zhexuan once said: “The title of mathematician is actually harmful to your career. It may cause a person to indulge in some heavyweight problems that go beyond anyone’s ability and waste a lot of time.” But Tao Zhexuan is not completelyDon’t touch these issues.Every year, he chooses a well-known problem that has not been solved for a day or two.Over the years, he made several attempts to solve the Kratz conjecture, but all failed.In August of this year, an anonymous reader commented on his personal blog, suggesting that he try to solve the “almost all” numbers of Kratz’s conjecture, rather than try to solve it completely.Tao Zhexuan said, “I didn’t reply, but this message really made me think about this problem again.” He realized that Collatz’s conjecture was somewhat similar to a form of equation, that is, a partial differential equation, and he was exactly thisThe field has achieved some of the most important results of a career.Input and output: Implications from partial differential equations Partial differential equations can be used to simulate many of the most basic physical processes in the universe, such as the evolution of fluids or the fluctuations of gravity in space and time.They occur in the future location of the system (such as the state five seconds after a stone is thrown into a pond), depending on the effects of two or more factors (such as water viscosity and speed).It seems that complex partial differential equations have nothing to do with simple arithmetic problems like Kratz’s conjecture.But Tao Zhexuan realized that there are similarities between the two.Using partial differential equations, you can also insert some values, get other values, and repeat the process.All of this is to understand the future state of the system.For any given partial differential equation, mathematicians want to know whether some initial values ​​will eventually lead to an infinite output value or a finite value, regardless of what value begins with.For Tao Zhexuan, partial differential equations have the same style as Kratz’s conjecture.Therefore, he believes that the idea of ​​studying partial differential equations can also be applied to the proof of Kratz’s conjecture.A particularly useful technique involves a statistical method that can be used to study the long-term behavior of a small number of initial values ​​(for example, a small initial configuration of water in a pond) and use this to infer the long-term behavior at all possible initial settings.If it is extended to the Kratz conjecture, it can be understood as starting from a large number of digital samples, and the goal is to study the behavior of these numbers when applying the Kratz process.If numbers close to 100% in the sample end up exactly equal to 1 or very close to 1, you might conclude that almost all numbers behave the same way.But for conclusions to be correct, the samples must be constructed very carefully.It’s like building a sample of voters in a presidential election.In order to accurately infer the entire population’s willingness to vote from the polls, the Republicans and Democrats need to be weighted in the correct proportions, and the samples must be weighted equally by men and women.Numbers have their own “demographic” characteristics.For example, there is parity, a multiple of 3, or the numbers are different from each other in other subtle ways.When constructing a digital sample, you can weight it to include numbers of some kinds, but not others.The better the quality of the weights chosen, the better able to draw conclusions about the overall number.Looking carefully at digital weighting, Tao Zhexuan gives the Kratz conjecture that the strongest proof of Tao Zhexuan’s challenge is far more difficult than figuring out how to create an initial digital sample with the appropriate weights.At each step of the Collatz process, the numbers processed change.An obvious change is that almost all numbers in the sample have become smaller.Another change that may be less noticeable is that these numbers may start to come together.For example, you can start with a uniform distribution, such as a number from 1 to 1 million.But after five Collatz iterations, these numbers are likely to be concentrated in several small intervals on the number axis.In other words, you may have a good sample in the beginning, but after five steps, it is completely distorted.Tao Zhexuan said in an email: “Usually, people will think that the distribution after iteration is completely different from the original distribution.” Tao Zhexuan’s key insight is to find out how to choose a largely original process throughout the Collatz processWeighted digital samples.For example, Tao Zhexuan’s initial sample does not include multiples of three after weighting because the Collatz process quickly excludes multiples of three.Some other weights proposed by Tao Zhexuan are more complicated.He took the weight of the initial sample as a number with a remainder of 1 after dividing by 3, rather than a number with a remainder of 2 after dividing by 3.As a result, Tao Zhexuan’s initial samples retained their characteristics even as the Collatz process continued.”He found a way to further the process so that after a few steps you still know what is happening,” Soundararajan said.“When I first saw this paper, I was very excited and thought it was very compelling.” Tao Zhexuan used this weighting technique to prove that almost all of the initial values ​​of Collatz (99% or more) eventually reachedA value very close to 1.This enabled him to draw the conclusion that 99% of the Kratz series with an initial value greater than 1 trillion and a final result less than 200.It can be said that this is the strongest proof result in the history of the conjecture.Lagarias said: “This is a big step forward in our understanding of this issue. It must be the best result in a long time.” Tao Zhexuan’s method almost certainly does not fully prove Kratz’s conjecture.The reason is that his initial sample was still slightly skewed after each step of the process.As long as the sample still contains many different values ​​far from 1, the deviation is small.But as the Collatz process continues, the number in the sample approaches 1, and the small deviation effect becomes more and more obvious—by analogy, when the sample size is large in a poll, a slight miscalculation has little effect.; But when the sample size is small, it will have a greater impact.To fully prove this conjecture, another approach is likely to be needed.Therefore, Tao Zhexuan’s work is both a victory and a warning to mathematicians fascinated by Kratz’s conjecture: just when you thought you might have run into a problem, it slipped away.Tao Zhexuan said: “You can get as close as possible to the Kratz conjecture, but to fully prove that it is still out of reach.” Reference link: https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211 / Tao Zhexuan’s blog: https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ dissertation: https://arxiv.org/abs/1909.03562.