We have captured the story of Kolmogorov N^2 Conjecture and how it was considered one of the most difficult problems yet was disproved in 4 years after its formulation with a week's work.

This interesting story involve three personalities:

• Kolmogorov
• Karatsuba
• Ofman

Who is Kolmogorov?

The story starts with Andrey Nikolaevich Kolmogorov.

Kolmogorov was a Soviet mathematician and was the first to introduce the idea of Time Complexity. He defined the idea of Time Complexity, captured previous results by all researchers and defined his own results and conjectures.

Of the many conjectures by Kolmogorov, the famous is Kolmogorov's N^2 conjecture.

The conjecture was proved wrong in just 4 years which was an embarassement for Kolmogorov. This lead to several unexpected events which we have captured in this article.

Some regard Kolmogorov to be an arrogant or unethical mathematician but this was not this case. In fact, it was opposite. The misinterpretation came for the translation of the original story.

Kolmogorov's N^2 conjecture

In 1956, Kolmogorov formulated a conjecture that the lower estimate for the number of operations for Multiplication of N bit numbers is of the order of N^2.

In modern terms, the theoretical limit of Time Complexity of Multiplication is O(N^2).

This was discussed in a meeting at Moscow Mathematical Society in 1956. Kolmogorov explained the Czech method of representing numbers in a system of residue classes and the time complexity in this context. The Czech method was suggested by Svoboda and Valach. The calculations noted the multiplication in Czech notation is O(N logN).

Vitushkin mentioned that N^2 conjecture is wrong in Czech notation but in Number System is may hold true as the conversion from Number System to Czech system is a costly operation and no benefit will be observed overall.

In Czech notation, there is no provision for comparison and hence, Number system is still the only way of utilizing numbers. Moreover, it was believed that if a better algorithm for Multiplication would exist, it should have been developed till now. Therefore, it was believed that Kolmogorov N^2 conjecture must be true.

Proved wrong by Karatsuba

In 1960, a seminar was held in Faculty of Mechanics and Mathematics at Moscow Univesity under the guidance of Kolmogorov. Kolmogorov N^2 conjecture along with complexity of linear systems were presented.

Karatsuba was one of the attendees.

Just in 1 week, Karatsuba developed an algorithm for Multiplication with a Time Complexity of less than O(N^2). More specifically, the Time Complexity of Karatsuba Algorithm is O(N^log3) = O(N^1.5849...).

In the next seminar, Karatsuba informed Kolmogorov of his new algorithm and how his N^2 conjecture is wrong. Kolmogorov was disturbed by this.

How Kolmogorov reacted?

Kolmogorov was disappointed as his conjecture "Kolmogorov N^2 conjecture" was the main focus of his seminars and was an active area of research in Time Complexity.

Multiplication was considered to be a difficult problem and his conjecture was assumed to be very difficult to prove or disprove if not considered to be true.

This was a setback for Kolmogorov as he was a leading figure in this field.

In the next seminar following the seminar where Karatsuba and Kolmogorov discussed, Kolmogorov talked about Karatsuba's discovery. This was the last interaction between Kolmogorov and Karatsuba.

Kolmogorov abruptly ended the seminar and never talked about his conjecture and Karatsuba's algorithm ever.

Suddenly 2 years later in 1960, Kolmogorov submitted a short article in the name of Karatsuba and Ofman. Ofman was a student of Kolmogorov.

This raised a controversy that Kolmogorov published Karatsuba's work in name of other researchers. This was an toxic practice in the research community. This was not the case as it was clearly mentioned in the article that it was Karatsuba's work solely.

Karatsuba was unaware of the publication of this short article and got to know about it later.

This is how Kolmogorov reacted on the events:

• In 1956, Kolmogorov formed Kolmogorov N^2 conjecture which was a major point in his seminars and in the field of Time Complexity.
• In 1960, Kolmogorov planned to conduct seminars in Moscow University.
• In his first seminar, he explained his conjecture along with other problems.
• In the second seminar, Karatsuba informed Kolmogorov that his conjecture was wrong.
• In third seminar, Kolmogorov talked about Karatsuba's findings.
• Kolmogorov ended the seminar without any notice and never contacted Karatsuba ever after this day.
• In 1962 (after 2 years), Kolmogorov published Karatsuba's work in name of Karatsuba and Ofman (his student) without informing Karatsuba. The credit was clearly given to Karatsuba.

With this article at OpenGenus, you must have a good idea of how the problem of Multiplication was tackled in the intial days and the progress of Time Complexity study.

To get more knowledge in this field and the problem of Multiplication, go through these articles:

• Karatsuba Algorithm (for fast integer multiplication)
• Toom Cook method for multiplication
• Evolution of Integer Multiplication Algorithms (from 1960 to 2019)
• Research papers on Integer Multiplication (1960 to 2019)