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:

image
"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

image
(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 image,  image and  image . But do not rush. An experienced researcher in number theory will instantly notice that the equation is a homogeneous </ i>. This means that if image is one of the solutions to the equation, then the solution is image. Do you understand why? Multiplying each variable by some constant (image is just an example), we have nothing we will change, because the constant in each of the parts is reduced.

image
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, image equations with image variables are specified by  image is a dimensional manifold where  image ). 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 image, and those for which image. In the first case, we have only two variables, image and  image , and in the second we can simply divide by  image and get the solution at  image . Therefore, we can simply look for rational solutions in image and image for the case of  image , multiply them by the common divisor and get the integer solution in  image ,  image and image. 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, image will be a monomial of the degree  image .

The behavior of the Diophantine equations strongly depends on their degree. Generally:


With the degree image everything is simple.
The degree image is completely analyzed and can be solved in quite elementary ways.
The degree image is a vast ocean of deep theory and a million unresolved problems.
Degree image and above ... Very, very complex.

We have the degree image. Why? We simply multiply by dividers:

image
Even without opening the brackets, you can see that the degree is image: we never multiply more than three variables at a time. We will have parts like image,  image and  image , but there will never be more than three multipliers. If we carry out the transformations, then the equation will have the form

image
You can argue that multiplication by dividers is impossible if any of them are equal image . 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, image,  image ,  image . 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

image
and sometimes

image
(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

image
image
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

image
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:

image

"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 image of this equation, we can restore the necessary values ​​ image ,  image ,  image with the help of equations

image
image
image
(Remember that the triplet image 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 image,  image ,  image in  image ,  image 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 image,  image or  image are equal to image. 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:

image,  image . 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 image,  image ,  image she gives us. We get image,  image ,  image , and since we can multiply by the common divisor, the results are converted to image, image,  image .

And in fact,

image
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.

image

First, add our point image to it, by finding the tangent to the curve at the point image and specifying where it again meets the curve. The result will be a bit daunting:

image
and again this new point corresponds to the values ​​image,  image , image, which is a solution of the original equation

image
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 image, which can be determined by connecting by a straight line image and  image and finding the third point of intersection with the curve. Again, we calculate image,  image ,  image , and again the result is nonpositive. The same will happen with image, and with  image , and so on ... until we come across  image .

9P=(-66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921,
58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469)

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 image,  image ,  image stunning:

a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,
b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,
c=4373612677928697257861252602371390152816537558161613618621437993378423467772036

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 image, we really get exactly image.

In fact, they are the smallest solutions to the problem. If we continue to add the point image, 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.

image


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  image . 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 image lies on the oval part of the curve, like the points  image for any positive integer  image . 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 image, image,  image : this is the bold part of the chart below, taken from the work of Bremner and MacLeod.

image

Points image,  image , and so on, do not lie on the selected part, but  image - lies, that's how we got our 80-bit positive solutions.

Bremner and MacLeod studied what happens if we replace image 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 image . 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 image, then the solution will contain trillions of digits . Trillions. For this innocent-looking equation:

image

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 image 80-bit numbers,  image numbers from hundreds of millions of digits and  image 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.
xially 20 september 2017, 13:56
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute