This metaphor will be easier to understand if we draw an analogy with a black hole: we do not know what is under its horizon of events, and to find out we need to come up with a way to get there. Something similar exists in the world of mathematics. This equation is a real "formula" of a prime number, but in order to use it, we need to figure out how to look for suitable {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z} .
The black hole and this equation are the ultimate states of something real and abstract. And, if there are enough guesses and ideas about the first, then about the second, practically nothing is known. But, what if it is truly a “mathematical” black hole? Aren't you curious what can happen if we fall below the horizon?
What does the wall consist of?
Numbers - they are not in the real world. There are seven dice, seven atoms, seven deadly sins, but the seven itself does not exist - it is an abstraction. Yes, we could say that numbers are just a lot of abstract objects, however, this is a whole world. A world in which, as in the real world, there are laws. The very thought of this seems very strange. Nevertheless, the existence of such a branch of mathematics as number theory suggests that this “oddity” is very important for us.
The most exciting thing is that among these imaginary objects there are special ones - prime numbers. They, like deterministic chaos, are predictable and unpredictable at the same time, depending on the scale of their consideration. For example, being next to them, we can notice that their number in front of some arbitrary number n will not exceed:
Changing the scale, we begin to notice a lot of hints of some kind of internal rules of their behavior. Gradually, these hints become too many. More and more often, the questions “Where did they come from?”, “What if there is a certain algorithm for obtaining primes?”, “What if every prime number can be obtained using the same algorithm?”
How the wall appeared
If a certain sequence of numbers is obtained as a result of the operation of a certain algorithm, then the set of numbers of this sequence is considered to be enumerable, even though it can be infinitely large. Enumerated sets have one remarkable property - Diophantine. This means that any such set can be represented by a Diophantine equation - a polynomial with integer positive coefficients and powers.
The following statement may seem completely implausible, but based on this definition, we can argue that all security keys and values ​​of hash functions (even bitcoins) can be expressed through Diophantine equations. those. equations that are solved in integers. And yes, theoretically, someone can learn any secrets, be infinitely rich and influential person. But, in order to become such a person, these equations must first be deduced, and then solved.
The computer can cope with the task of representing the set by the Diophantine equation, partially or completely. But here another problem arises - the Diophantine equations are not solved in a general form, i.e. there is no single algorithm for solving them. This does not seem to be a big problem, because we know that some equations are distinguished into separate forms, for the solution of which effective methods have already been found.
But even despite the presence of these methods, we inevitably encounter computational difficulties that are associated either with the accuracy of calculations or with the speed of iterations.
How did it happen that primes were enumerable? The very process of creating equations representing enumerable sets relies on the foundations of mathematics - arithmetic and logic. And if we have enough knowledge about the properties of objects of a certain set, then, based on this knowledge, we can make assumptions about the algorithm that allows them to be obtained. And, as it turned out, knowledge about the properties of primes was accumulated enough for this purpose. The equation has been obtained, and now all questions related to prime numbers are reduced to it alone.
But we cannot solve it.
Wall thickness and strength
In fact, we are challenged. And we know in advance about the inevitable defeat. Perhaps a retreat would be the most prudent decision. But do not we need these defeats in order to surpass ourselves? Let's try to solve it just a little bit.
Take a look at the equation again:
This is a polynomial whose set of positive values ​​coincides with the set of primes. It consists of two factors: the left factor will be a prime only when the right factor, indicated by curly brackets, is equal to one, and this, in turn, is possible only if each term in the given factor, indicated by square brackets, is equal to zero . It turns out that the question of solving this equation reduces to solving the system of the following equations:
If we solve this system of equations and add 2 to the found value of k , then we get a prime number. But we can go the other way. Take some prime number, subtract 2 from it, thus obtaining the value of k , then substitute this value into the system and try to find the values ​​of the remaining variables relative to it. It is this way that we will go - try to find at least one solution to this polynomial.
All variables are subject to two strict restrictions; they must be integer and cannot be negative. If we take k = 0 , then the first prime number we can get is 2. This will be our starting point. After substituting this value in the system of equations, it will take the following form:
Equations (1) - (5) are linear equations, i.e. the degrees of all variables are 1. Equations (6) - (11) have a very similar structure. And finally, equations (12) - (14) also stand out in a separate group, and equations (13) and (14) are similar to each other, like two drops of water.
We can get rid of variables, or lower the degree, but we have already done this before. A decrease in the number of variables leads to a strong increase in the degrees of other variables, and a decrease in the degrees of variables is possible only through an increase in their number. So let's try to solve this system in this form.
Equations (6) - (11) are modifications of the Pell equation:
In fact, if you rewrite them like this:
then the similarity becomes apparent. This is very encouraging, since we can solve the Pell equations quite well. We can try to solve this system like this: first we solve one equation, substitute its solutions into another, which we also solve, and so on, to the very end. It sounds pretty simple, but it would not hurt to draw something like a permutation graph in order to at least roughly know in which order to solve the equations:
It seems that everything is simple.
Kick on the wall
We start with the Pell equations. To solve them, we will write a small script:
from decimal import * getcontext().prec = 50 def peq_dec(N): n = Decimal(N).sqrt() a = int(n) x = n - a p0, q0 = 1, 0 p1, q1 = int(a), 1 while True: a = int(1/x) x = 1/x - a p_i = a*p1 + p0 q_i = a*q1 + q0 if p_i**2 - N*q_i**2 == 1: return p_i, q_i break p0, q0 = p1, q1 p1, q1 = p_i, q_i
Thanks to him, we can immediately find a solution to equation (10) n = 2 , f = 17 . However, before moving on, we need to know something about the Pell equation.
To begin with, n cannot be a full square. In addition, any Pell equation has an infinite number of solutions, among which there is always a trivial one: x = 1 and y = 0 . Each subsequent decision can be obtained on the basis of the previous ones, according to the following recurrence formula:
It turns out that it’s enough for us to find the minimal non-trivial solution, and we can get all the rest using a simple algorithm. For example, for n = 2, we can easily find such a solution, it is x = 3 and y = 2 , then subsequent solutions will look like this:
17, 12 99, 70 577, 408 3363, 2378 19601, 13860 114243, 80782 665857, 470832 3880899, 2744210 22619537, 15994428 131836323, 93222358 768398401, 543339720 4478554083, 3166815962 26102926097, 18457556052 152139002499, 107578520350 886731088897, 627013566048
Should the further decision be continued? Of course it’s worth it, but ... we can try to predict what lies ahead.
Let's just imagine for now that we are solving a system of equations of three Pell equations of the following form:
The solution to any Pell equation is the hyperbola points with integer coordinates. Then, we can imagine a solution to the first two equations like this:
The solution to the first equation is the integer points of the red hyperbola, but the y coordinate of each such point is present in the second equation and can generate any blue hyperbola, the integer points of which will be the solution to the second equation.
Even this schematic diagram is enough to understand that we are dealing with a very large number of potential candidates for solving the system. Why candidates? Because some integer points of the hyperbola will necessarily be full squares, i.e. inappropriate solutions. And if you imagine that any additional conditions are imposed on each variable in the system, then finding candidates for a solution will become extremely difficult. And so far we are talking only about a system of three equations.
But let's get back to our "formula" of primes. What can be ahead of us?
Sooner or later, we will find that the parameter n in the Pell equation will become catastrophically large. The continued fraction method will simply become useless. We will definitely try something else, for example enumerating values ​​with sifting, somehow generalize the whole process and come to algorithms like a quadratic sieve or a sieve of a number field. In the end, we will focus on the “chakraval" method, although it will also experience some difficulties.
At a certain point, we will feel some confidence in solving each individual equation of the system. But not the whole system. We will try to apply some heuristic optimization methods, for example, an annealing algorithm, or an ant algorithm. But here we will fail. In order to at least somehow understand the reasons for these failures, we will have to dive a little into algebraic geometry and topology. Gradually, we will get some idea of ​​“crystallizable substance”. We can remotely imagine the structure of the hypersurface onto which we release ants.
Based on these ideas, we will try to improve our algorithms. To do this, we will take the best achievements from many branches of mathematics. Gradually, there will be less chance in the algorithms, but you still can’t get rid of it. What will happen next? We suddenly find that many suitable candidates for a true decision in some places are paradoxically dense. Each such density will give hope that somewhere in its center the secret answer is hidden. Such densities will “seem” to ants as something like an inverted hyper-funnel. We will try to “hit” their centers and highs. But then what will happen?
What is behind the wall?
I probably don’t know how, but we will solve this equation. Maybe quantum or (!) Quark computers will help us. But this will not become a hole in the wall. Probably, Gaussian primes and an even more complicated equation, which will represent many of them, will wait for us further. Then, perhaps, among other hypercomplex numbers, we will again come across some sort of “simple” behavior. Maybe this, in the end, will be the limit, a kind of event horizon of a mathematical black hole.
What could be under this horizon? Probably some kind of mathematical singularity. Probably, we will know absolutely everything about all the sets, we will be able to solve any equations and any problems. Or maybe there will be no more new questions and tasks at all?
It is precisely such thoughts that arise. Well, actually, ask any question about primes and thanks to this equation you can get an answer to it. Is the number of twin primes infinite? Solve this equation, make a couple of algebraic calculations and get the answer. What are the prime numbers ending in 1, 3, 7, or 9? The same algorithm: a couple of calculations and substitution of the equation. Do you want to quickly decompose numbers into prime factors? ..
Finally
I first met this equation in 2008, by then I was already crazy about cryptography and number theory, in particular, the RSA scheme and the factorization problem. Of course, the polynomial generating prime numbers seemed to me a very interesting topic, but too complicated. However, all the problems that could or could not be solved were somehow connected with the Diophantine equations. Therefore, already in 2014, I again turned to this polynomial, deciding to simply explore all sections of mathematics in a row and look for something that could be useful in solving it. Of course, there can be no talk of any academic culture of all my works - I never kept systematic records, never aggregated the generated code. This is just my hobby.
The thought of writing this article came up after I saw the movie Interstellar. I could not believe that black holes and gravity could be represented so damn exciting. But, as it turned out, the "non-existent" world of mathematics provided me with the same impressions all the time. This world also has its own inaccessible "deep space" and its own "elementary particles."
With this article I wanted to show that it is possible to approach at least a little bit to any, the most difficult, even impossible task. There are a lot of such tasks, and you can choose one that is to your liking and closest to the area of ​​interest. Of course, excessive complexity and guaranteed defeat will deprive the slightest desire in this undertaking. But the whole paradox is that the most interesting travels and adventures, even in the "non-existent" world of mathematics, most often, begin that way.