Mathematical Detective: Finding Positive Integral Solutions of Equation
"I experimented with the tasks of the cubic representation in the style of the previous work of Andrew and Richard Guy. The numerical results were amazing ... "( comment on MathOverflow)That's how the retired mathematician Allan MacLeod came across this equation several years ago. And it's really very interesting. Honestly, this is one of the best Diophantine equations I've ever seen, but I did not see very many of them.
I found it when it began to spread like a network-nesting picture-pseudomem, invented by someone's ruthless mind ( Sridhar , was it you?). I did not understand right away what it is. The picture looked like this:
"95% of people will not solve this riddle. Can you find positive integer values? "
You probably already saw similar pictures-memes. It's always the cleanest rubbish, clickbites: "95% of MIT graduates will not decide it!". "She" is some stupid or poorly formulated task, or a trivial warm-up for the brain.
But this picture is completely different . This meme is a clever or malicious joke. Approximately 99.999995% of people have not the slightest chance to solve it, including a good part of mathematicians from leading universities that do not deal with the theory of numbers. Yes, it is solvable, but at the same time it is really complicated. (Incidentally, it was not invented by Sridhar, more precisely, not completely.) See the story in this comment ).
You might think that if nothing else helps, then you can just make the computer solve it. It is very simple to write a computer program to find solutions to this seemingly simple equation. Of course, the computer will find them sooner or later, if they exist. Big mistake . Here the method of simple computer enumeration will be useless.
I do not know if it will be possible to fit the full solution into an article if you do not accept that everyone already knows everything about the elliptical curves. I can only give a brief overview here. The main reference source is the wonderful, relatively recent work of Bremner and MacLeod under the name <Anonymous Anonymous cubic representation problem "</a>, published in 2014 in Annales Mathematica et Informaticae .
So, let's get started.
We seek positive integer solutions of equation
(I replaced the notation of variables with those used in the work).
The first thing to do when examining any equation is to try to put it in the right context. We must ask: what is this equation? So, we are asked to find integer solutions, that is, it is the problem of number theory. In the current formulation, rational functions are used in the equation (polynomials that divide into other polynomials), but it is obvious that we can multiply by a common multiple of denominators in order to clean up the equation and get only polynomials, that is, bring it to the form Diophantine equation . The requirement of "positivity" is rather unusual, and, as we will see, complicates everything.
So, how many variables do we have here? The question seems stupid: it is obvious that three, namely , and . But do not rush. An experienced researcher in number theory will instantly notice that the equation is a homogeneous </ i>. This means that if is one of the solutions to the equation, then the solution is . Do you understand why? Multiplying each variable by some constant ( is just an example), we have nothing we will change, because the constant in each of the parts is reduced.
This means that the equation only pretends to be three-dimensional. In fact, it is two-dimensional. In a geometric representation, we have a surface (one equation with three variables in the general case defines a two-dimensional surface. In general, equations with variables are specified by is a dimensional manifold where ). But this surface is actually bounded by a line that oscillates and passes through the origin. The resulting surface can be understood by understanding how it dissects the unit plane. This is a projective curve.
The easiest way to embrace this reduction is as follows: we can divide solutions, whatever they are, into those for which , and those for which . In the first case, we have only two variables, and , and in the second we can simply divide by and get the solution at . Therefore, we can simply look for rational solutions in and for the case of , multiply them by the common divisor and get the integer solution in , and . In essence, the integral solutions of homogeneous equations correspond to rational solutions of the non-homogeneous version, which is one dimension smaller.
We continue: what is the degree of our equation? The degree of the equation is the maximum degree of any one appearing in the monomial equation, where the "monomial" is the product of several variables whose "degree" is the number of monomials that are multiplied. For example, will be a monomial of the degree .
The behavior of the Diophantine equations strongly depends on their degree. Generally:
With the degree everything is simple.
The degree is completely analyzed and can be solved in quite elementary ways.
The degree is a vast ocean of deep theory and a million unresolved problems.
Degree and above ... Very, very complex.
We have the degree . Why? We simply multiply by dividers:
Even without opening the brackets, you can see that the degree is : we never multiply more than three variables at a time. We will have parts like , and , but there will never be more than three multipliers. If we carry out the transformations, then the equation will have the form
You can argue that multiplication by dividers is impossible if any of them are equal . This is true - indeed, our new equation has several solutions that do not correspond to the original equation. But in fact it's good. The version with polynomials adds several "patches" to the original and makes it easier to work with it. We just need to check whether the original divisors disappear at each particular decision.
In fact, an equation with polynomials is easy to solve, for example, , , . This is good: we have a rational solution (rational point). This means that our cubic equation (degree = 3) is in fact an elliptic curve </ i>.
When you find out that the equation is an elliptical curve, then a) you rejoice and b) despair, because there is still much to study. This equation is an excellent example of how a powerful theory of elliptic curves can be applied to finding insanely difficult to determine solutions.
The first thing that is usually done by an elliptic curve is to bring it into a Weierstrass shape. This equation, which looks like
(this is called the expanded Weierstrass shape, which is optional, but sometimes more convenient).
Usually, any elliptical curve can be brought to this kind (unless you are working on fields with small characteristics, but here we do not need to worry about them). It would be too long to explain the way to find the right transformation, so just know that this is an absolutely mechanical process (it is critically important in it that there is at least one rational point that we have). There are different packages of computational algebra that will do everything for you.
But even if you do not know. how to find a transformation, it's very simple to check it, at least it's done purely mechanically. The necessary transformation in our case is given by scary-looking formulas
I know that they are similar to the unknown origin of the magic of voodoo, but believe me, it's not. Having obtained these transformations, using monotonous, but rather simple algebraic calculations, we show that
This equation, although it looks quite different, is in fact a reliable model of the original one. Graphically it looks like this - a typical elliptic curve with two real parts:
"Fish tail" on the right grows "to infinity and beyond". The oval figure on the left is closed and turns out to be quite interesting for us.
Having any solution of this equation, we can restore the necessary values , , with the help of equations
(Remember that the triplet should be perceived projectively - whatever values you get with these equations, they can always be multiplied by any constant).
The two mappings we showed, from , , in , and vice versa, show that these two equations are" the same "from the point of view of number theory: rational solutions alone provide rational solutions to the other. Technically, this is called birational equivalence, and it is a fundamental concept of algebraic geometry. As we have already noted, there may be exception points that do not appear correctly. These are the cases when , or are equal to . This is the usual payoff in the case of birational equivalence, and it should not cause any unrest.
Let's look at an example.
On the elliptic curve (2) there is a good rational point:
, . Perhaps it is not so easy to find, but very simply > check : just insert these values and you will see that the two halves are the same (I did not select this point randomly, but so far it does not matter). You can just check what values are , , she gives us. We get , , , and since we can multiply by the common divisor, the results are converted to , , .
And in fact,
as can be easily verified. This is a simple solution to our original equation in integers, but, alas, not in positive integers. This solution is not easy to get out by hand, but it's easy to get without all this machinima considered here, with a little patience. The most difficult thing is to make positive decisions.
Now, after obtaining a rational point on an elliptic curve, for example, on our curve (2), you can start generating others using the technique of chords and tangents, discussed in the previous article on Quora.
First, add our point to it, by finding the tangent to the curve at the point and specifying where it again meets the curve. The result will be a bit daunting:
and again this new point corresponds to the values , , , which is a solution of the original equation
This solution is definitely not easy to find manually, but it is still possible by the computer. However, it is still nonpositive.
Not frightened of failures, we continue to calculate , which can be determined by connecting by a straight line and and finding the third point of intersection with the curve. Again, we calculate , , , and again the result is nonpositive. The same will happen with , and with , and so on ... until we come across .
It's definitely not easy to find, but with the help of our machine, it's enough to repeat the simple geometric procedure nine times. The corresponding values are , , stunning:
These are 80-bit numbers! You could not find 80-bit numbers on the computer with a simple search. It looks incredible, but by inserting these huge numbers into the simple expression , we really get exactly .
In fact, they are the smallest solutions to the problem. If we continue to add the point , then divisors will simply grow. It is not easy to prove this, because there is always a possibility of contraction, but the theory of heights for an elliptical curve allows us to show that these astronomical numbers are in fact the simplest solution of the equation.
Let's return to the theory. An elliptic curve over rational values has rank , which is the number of points needed to use for the method of chords and tangents and to be sure that sooner or later we will find all the rational points on the curve. Our elliptic curve (2) has rank 1. This means that it has an infinite number of rational points, but all of them are obtained from a single one, which is nothing else than our point . Algorithms for calculating the rank and finding such a generator are far from trivial, but SageMath (now called CoCalc) executes them in less than a second in just a few lines of code. My code can be viewed here . It reproduces the entire solution from scratch, but, of course, uses the built-in Sage methods to work with elliptical curves.
In our case, the point lies on the oval part of the curve, like the points for any positive integer . They "swirl" around the oval and are distributed fairly evenly over it. This is very fortunate, because only a small part of this oval gives positive decisions regarding , , : this is the bold part of the chart below, taken from the work of Bremner and MacLeod.
Points , , and so on, do not lie on the selected part, but - lies, that's how we got our 80-bit positive solutions.
Bremner and MacLeod studied what happens if we replace with something else. If you think that the solutions will be large, then wait until you see what the solutions will be as a result of . Instead of 80 bits, we need 398 605 460 bits. Yes, this is only the number of bits of the solution. If you replace the result with , then the solution will contain trillions of digits . Trillions. For this innocent-looking equation:
A striking example of how Diophantine equations with small coefficients can have huge solutions. This inspires not only awe, but a sense of bottomlessness. A negative solution to the tenth Hilbert problem means that the growth of solutions with increasing coefficients is a non-computable function </ i>, because if it were computable, then we would have a simple algorithm for solving Diophantine equations, but it does not exist (neither simple, or complex). Matching 80-bit numbers, numbers from hundreds of millions of digits and trillions of bits gives us a little idea about the first, small steps of this monstrous non-computable function. Slightly change the numbers in the equation, and the solutions will easily surpass anything that can fit into our wretched, tiny universe.
Here is an amazingly tricky little equation.
|Vote for this post
Bring it to the Main Page