Since Gödel, we know that mathematics have limitations: some statements cannot be proved, and cannot be refuted, that is one cannot prove their negation: for both, no demonstration exists. Many works have been made for this problem, and they show that, in some theories, some statements are true, although no proof exists. Some of these proofs are constructive, and they show statements in this category; usually, these statements use reflexivity. We know the Epimenides paradox, who is Cretan and says that all Cretans are liars. I was not embarrassed that so strange statements could not be proved.

However, for a recent post, I have considered a system that created new conjectures. It found several variants of Goldbach conjecture: every even number greater than two may be decomposed as the sum of two prime numbers. It had been a long time since I knew this conjecture, and I was not really annoyed that it had not been proved, although many mathematicians tried to do it since 1742. Indeed, I believed that it was a very difficult problem, that numbers greater than billions of billions had only one, two or three decompositions: it was ever likely that no decomposition existed. If so, it was possible that this conjecture was false; even true, it would be very hard to prove it.

Writing my preceding blog, I read the Wikipedia entry on Goldbach conjecture, and I saw that the number of decompositions is huge; moreover, it is strongly increasing with the value of the numbers. Therefore, with CAIA, I have made some experiments, I had only to write three rules. I was shocked by the results: large numbers really have a lot of decompositions. The greatest number with at most 1 decomposition is 12, with at most 10 is 632, with at most 100 is 11,456, with at most 1000 is 190,562, etc. I have stated a new conjecture:

The number of decompositions of an even number N, greater than 15,788, into the sum of two prime numbers is greater than the square root of N.

As a matter of fact, the greatest number for which this conjecture is false is 15,788: it has 125 decompositions, less than the square root of 15,788: 125.65….

Naturally, I have not proven this conjecture, but I am pretty sure that it is true. When we consider large numbers, they have even much more decompositions than forecast. Moreover, when a number N has small numbers of decompositions, several of its neighbors have similar values: the curve representing the number of decompositions has no pick towards the bottom. CAIA has studied the first hundred even numbers from 100,000,000: the minimal value of the number of decompositions is 218,281 for 100,000,144 (we can notice that it is much larger than the square root of the smaller of these numbers, which is 10,000); among these 100 numbers, 12 have a number of decompositions between 218,281 and 219,000. On the contrary, the abnormally high values are often isolated from their neighbors, there are picks towards the top: in the preceding interval, the largest number of decompositions is 723,776, and the value of its immediate follow-up is only 595,554. It seems very unlikely that there exists a large number N with less decompositions than the square root of N; it is still harder to believe that there is an even number without any decomposition.

Goldbach conjecture has been checked until 4.10^{18 }; then, if my conjecture is true, every even number not yet checked has at least two billions decompositions! And mathematics cannot prove that there is at least one!!!! There would be no proof of a result which is ultra-true.

I do not believe that it is due to an inability of mathematicians; I have a tremendous admiration for the way they succeeded in developing mathematics. They are extremely competent, as long as they do not speak of AI. This is a weakness of mathematics: one cannot find a proof because it does not exist. And this happens for very simple statements, such as the Goldbach conjecture, that anybody can understand easily.

Then, one question arises: are there many conjectures of this kind, simple, true, with no existing proof? Some could say that the decomposition of a number as the sum of two prime numbers is an irrelevant problem. I do not agree: a similar problem is the decomposition of an odd number as the product of two prime numbers, and it is very important, especially for cryptography.

It is possible that the true and provable statements are only a small subset of all the true conjectures. In that situation, along with mathematics, we have to create a new field of research where one would find true (and sometimes ultra-true) conjectures for which no proof exists. Then, with all the power of mathematics, we would use them: the absence of formal proof must not deter us to do that. We know the importance of the Riemann conjecture; there are probably several other conjectures that would also be useful.

AI is ideally suited to this kind of research: a system can create and check a huge number of candidates, much more than any human being can do. It is not enough to build artificial mathematicians, whose performances would significantly exceed those of the best human mathematicians. Improving the investigation mentioned in a preceding blog, a new branch of AI will have to create conjectures very cleverly.

Hello. Ph.D in CS/AI at LIP6 here.

What disappoints you? The amount of unprovable truths? I thought it was a well known result understandable by combinatorial considerations (reminiscient of Cantor diagonal).

From what I understand, your point is that we would benefit from considering empirically explored results as sufficiently convincing to hold them as true without formal proof. This deviates from pure mathematics, and closer to the real world (and that’s fine with me, I’m an engineer.)

I’m trying to get the bottom line … maths can’t prove AI? It might feel disappointing, let’s just move on.

What do you think?

https://www.smbc-comics.com/comic/2011-02-17

We all know that there are unprovable truths, but I believed that it happened only for “near false” truths.

For instance, for Goldbach conjecture, I thought that perhaps 10 to the power 20 had only 2 decompositions, and 10 to the power 30 only 1. Then, it was likely that a very large number had no decomposition at all. It was normal that no proof existed for such a conjecture, which I believed near false, even if it was always true. It would certainly be very hard to prove it.

I was very surprised to see that every odd integer has a huge number of decompositions. Even my conjecture that the number of decompositions of integer N is larger than the square root of N leads in a number much lower than the real one.

For each integer for which the conjecture has not yet been proven, there are billions of decompositions, much more than only 1 as in Goldbach conjecture. This conjecture is not near false: it is “extremely true”! This means that there could be no proof for extremely true sentences. This is why mathematics has disappointed me. Therefore, I think that clever AI systems will have to develop something that is more powerful than mathematics. I have absolutely no idea what sort of thing it could be!