Shulou(Shulou.com)11/24 Report--

Original title: "Why is it so difficult to calculate the volume of high-dimensional convex bodies?" What is the pure proof of existence of mathematics? "

Start with a simple equation.

Obviously, this equation has (at least) a solution. Because, let f (x) = x ^ 5-x mae 13, there is f (1) =-13m f (2) = 17. Therefore, there must be an x between 1 and 2 so that f (x) = 0.

This is an example of a pure existential argument that tells you what exists (in this case, a solution to an equation), but does not say how to find it. If the equation is x ^ 2-x mi 1350 0, it can be demonstrated in a completely different way. The formula for finding the root of the quadratic equation tells us that there happen to be two solutions, and it even tells us what the solution is.

But there is no similar formula for the quintic equation.

These two arguments represent the basic dichotomy of mathematics. If you want to prove the existence of a mathematical object, you can sometimes explicitly prove that it actually describes the object, or indirectly, that it will cause contradictions if it does not exist.

In the meantime, there are all kinds of possibilities to form a spectrum. As explained, the previous argument only states that between 1 and 2, the equation x ^ 5-x color 130has a solution, but it also suggests a way to calculate the solution, accurate as you need it. For example, if you need to be accurate to two decimal places, you can take a string of numbers ∶ 1, 1.01, 1.02,. , 1.99992, and then estimate the value of f at each point. It is found that f (1.71) is approximately-0.0889 and f (1.72) is approximately 0.3337, so there must be a solution (the calculation shows that the solution is closer to 1.71). In fact, there are better ways, such as Newton's method, to approach a solution. For many purposes, the formula of a beautiful solution is not as important as the method of calculating or approaching the solution. If there is a method, whether it is useful or not depends on whether it runs fast.

In this way, there is a simple formula for defining a familiar object at one end of the spectrum, which can also be easily used to find the object, while at the other end of the spectrum, there is a proof that can establish the existence of the object without giving further information. in between, there are algorithms that can be used to find the object, and the faster these algorithms are executed, the more useful they will be.

As with the question of rigor, if all other conditions are the same, a strict argument is better than a less strict argument. Now, even if indirect proofs are known, it is still worthwhile to find an explicit algorithmic argument, on the grounds that similar ∶ 's efforts to seek explicit arguments often lead to new mathematical insights (less obvious is ∶ 's efforts to find indirect arguments, sometimes new insights).

One of the most famous examples of proof of pure existence is about transcendental numbers. Transcendental numbers are the real numbers of the roots of polynomial equations that cannot be arbitrary integer coefficients. The first proof of the existence of such numbers was given by Liouville in 1844. He proved that there is a condition sufficient to guarantee that a number is transcendental, and that it is easy to construct a number that satisfies this condition. Later, all kinds of important numbers such as e and π have been proved to be transcendental numbers, but these proofs are very difficult. Even now, there are still many numbers that are almost certainly transcendental numbers, but they just can't be proved.

The proofs mentioned above are all direct and explicit. Then, in 1873, Cantor used his countability theory to give a completely different proof of the existence of transcendental numbers. He proved that algebraic numbers form a countable set, while real numbers form an uncountable set. Because countable sets are much smaller than uncountable sets, this means that almost every real number (though not necessarily almost every real number you really see) is transcendental.

In this case, each of the two arguments tells us what the other argument does not tell us. Cantor's proof tells us that there are transcendental numbers, but not a single example is given to us.

Strictly speaking, this is not true that ∶ can specify a way to arrange algebraic numbers into a list, and then apply Cantor's famous diagonal argument to this list to find a transcendental number, but the transcendental number found in this way basically has no meaning.

Liouville's proof is much better in one respect because it gives us a way to construct several transcendental numbers with a straightforward definition. However, if we only know Liouville's direct argument and the proof that e, π is a transcendental number, we may get the impression that the transcendental number is a very special number. There is an insight that is not seen at all in these arguments, but in Cantor's proof that a typical real number is a transcendental number.

For most of the 20th century, highly abstract indirect proof prevailed, but in recent years, especially because of the invention of computers, attitudes have changed. Recently, more attention has been paid to whether a proof of ∶ is explicit, and if so, whether an efficient algorithm can be derived.

Needless to say, the algorithms themselves are interesting, not just because they give a perspective of mathematical proof. We briefly describe a particularly interesting algorithm that gives a method for calculating the volume of a high-dimensional convex body.

A figure

It is called convex body, which means that if you take any two points z and y in K, the straight line segments connecting x and g are all in K. For example, squares and triangles are convex, while pentagram is not. This concept can be directly extended to the n-dimensional case, where n is any positive integer. The concepts of area and volume can also be extended in this way.

Now we specify an n-dimensional convex body K in the following sense, that is, there is a fast computer program that can tell us every point. , xroomn) whether it belongs to K. How to estimate the volume of K? For a problem like this, one of the most powerful methods is the statistical method ∶ to randomly take a point to see if it belongs to K, and to estimate the volume of K based on the frequency at which the point falls into K. For example, if you want to estimate π, take a circle with a radius of 1, put it in a square with a side length of 2, and then randomly take many points from the square. The probability that each point belongs to this circle is π / 4, so the estimate of π is obtained by multiplying the ratio of the total number of points that fall into the circle by 4.

This approach is easy to work for very low dimensions, but when the dimension is very high, it will encounter great difficulties. For example, let's say we want to use this method to estimate the volume of an n-dimensional sphere. Put the ball in an n-dimensional cube and see how often this point falls into the ball. However, the ratio of the volume of the n-dimensional sphere to the volume of the n-dimensional cube is exponentially small, that is to say, the number of points to be cast is exponentially large before finding a point in the sphere. So this method becomes impractical.

However, because there is another strategy that can get around this difficulty. A sequence of convex bodies can be defined. Each convex body is contained in the next convex body, and starts with the convex body whose volume you want to calculate (that is, you want to calculate the volume of the Ko), and ends with a cube (that is, a cube) such that the volume of Kampi is at least half the volume of Krab1. So for each I, it is necessary to estimate the ratio of the volume of KiMui 1 to that of Khami. The product of these ratios is the volume ratio of Kendo to Kramm. But the volume of Kcubic (cube) is known, so you get the volume of Kcubic 0.

How to estimate the volume ratio of KiMui 1 to Khami? You just need to simply randomly take the points of Khami and see how many of them fall into KImuri. It is here, however, that the subtlety of the problem arises how does ∶ randomly pick points from a convex body that is little known? It is easy to take random points in an n-dimensional cube. It is only necessary to select n random numbers independently. , xroomn, and each xroomi is between-1 and + 1. But it's not easy for a convex body.

There is a wonderful and clever way to avoid this problem. This is to carefully design a random walk, starting from a point in the convex body, and at each step, the point to which you move can be randomly selected from a few possibilities. The more random steps you take, the less you know about where this point goes. If the walk is properly defined, it can be proved that after a few more steps, the position of the point is purely random. However, it is very difficult to prove.

This article comes from the official account of Wechat: Lao Hu Shuo Science (ID:LaohuSci). Author: I am Lao Hu.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.