Breaking news: David Harvey and Joris Van Der Hoeven. Integer multiplication in time O(nlogn). 2019. (I heard about it from Yoni Rozenshein on FB (חפירות על מתמטיקה); update GLL post. )
_____
Update: There were many interesting comments here and on FB. Itay Ben-Dan wrote a very interesting : Alternative to Gil Kalai & Nati Linial 10 Milestones in the History of Mathematics.
In 2006, the popular science magazine “Galileo” prepared a special issue devoted to milestones in the History of several areas of science and Nati Linial and me wrote the article about mathematics Ten milestones in the history of mathematics (in Hebrew). Our article had 10 sections highlighting one or two discoveries in each section.
Here are our choices. What would you add? what would you delete?
The list
1) Numbers and Number Systems – The Irrationality of the square root of 2
Discovery No.1: the square root of 2 is not a rational number.
2) Geometry, the Discovery of Non-Euclidean Geometry, and Topology
Discovery no.2(A): Euclidean Geometry
Discovery no.2(B): Non-Euclidean Geometry
3) Algebra, Equations and Mathematical Formulas. Galois Theory.
Discovery no.3: Abel-Galois Theorem: there is no solution with radicals to the general equation of the fifth degree and above.
4) Analysis and the Connection to Physics
Discovery no. 4(A): Differential and integral calculus (Isaac Newton, Gottfried Leibniz, 17th Century).
Discovery no. 4(B): The analysis of complex functions (Augustin-Louis Cauchy, Bernhard Riemann, 19th century).
Nati Linial
5) Proofs and their Limitations: Logic, Set Theory, the Infinity, and Gödel’s Incompleteness Theorem.
Discovery no. 5(A): There are various kinds of infinity. For example, there are more real numbers than natural numbers.
Discovery no. 5(B): Gödel’s Incompleteness theorem: A mathematical theory broad enough includes true statements that cannot be proven.
6) Linear Algebra, Linear Programming and Optimization
Discovery no. 6(A): The Gauss elimination method for solving systems of linear equations.
Discovery no. 6(B): Linear programming and the Simplex algorithm for solving it.
7) Probability Theory and the Bell curve
Discovery no. 7: The Bell Curve and the Central Limit Theorem
8) Prime Numbers and their Density
Discovery no. 8: The Prime Number Theorem.
9) Algorithms, Digital Computers and their Limitations
Discovery no. 9 (a): The theory of computability. Undecidable problems.
Discovery no. 9 (b): Computational Complexity theory. The theory of NP-complete problems.
10) Applied Mathematics
Discovery no. 10: Additional paradigms of mathematical research beyond the paradigm of theorem/proof. Numerical methods, simulations, scientific computation and the development of mathematical models.
Combinatorics and more 
I think that 5B and 9A are almost the same.
Right, we can unify 5 and 9. But then what milestone should we add?
Well, although they might demolish both 5a (indirectly) and 5b (directly), you could consider these relatively recent results from a paper published in the December 2016 issue of ‘Cognitive Systems Research’:
`The truth assignments that differentiate human reasoning from mechanistic reasoning’
https://www.sciencedirect.com/science/article/pii/S1389041716300250?via%3Dihub
(a) The first-order Peano Arithmetic PA has two constructive interpretations (Theorem 5.6, p.40 and Theorem 6.7, p.41—first preference);
(b) PA is consistent (Theorem 6.8, p.41);
(c) A PA formula is provable if, and only if, it interprets as a Turing-computable proposition (Theorem 7.1, p.41—second preference);
(d) Goedel’s `undecidable’ arithmetical formula is decidable in PA (Theorem 8.2, p.42).
Gil and Nati, this is a wonderful list! Supposing that Milestones (5) and (9) are merged, there’s room for “Milestone (10) The Extended Church-Turing Thesis” (ECT) … with “extended” as the crucial milestone-ingredient that is neither present nor implied in Milestones (1-9).
References For students, the ECT figures centrally in Boaz Barak’s textbook-in-progress Introduction to Theoretical Computer Science, see in particular Section 12.6 “Extended Church-Turing Thesis” (in the numbering of 19th March, 2019; most-recent pdf version freely available here, somewhat less-recent html available here).
In the following summary passage, Barak’s textbook makes a strong case for the ECT-as-milestone:
Barak’s thesis — that the ECT is “fundamentally or ‘morally’ correct” — finds consensus support (literally) in the just-released US National Academy of Sciences consensus report Quantum Computing: Progress and Prospects (2019, free pdf here).
It was a personal pleasure to notice that Scott Aaronson is credited as a member of the report’s independent review panel, because on my initial reading of the NAS report, I had thought to detect “the paw of the Shtetl Optimized lion” in the excellence, objectivity, and subtlety of the report’s treatment of the ECT in general, and the feasiblity (or not) of Quantum Supremacy in particular (see pp. xi, S1, S4-5, 1.3, 3.1, 3.18-20, 5.6, 6.7-8, 7.11-13, 7.18, and 7-23).
Needless to say, the broad consensus of today’s scientific community in regard to the “fundamental or even ‘moral’ correctness of the ECT” — to borrow Barak’s phrase — does *not* imply that every researcher should appreciate the ECT in the same way … quite the opposite!
Summary The extraordinary diversity of the cognitive perspectives that the Extended Church-Turing Thesis naturally supports is what composes (to my mind at least) the ECT’s strongest claim to status as a top-ten mathematical milestone … arguably even, up to the present time, humanity’s foremost mathematical milestone.
Hi John, Thanks! ECT is surely very very interesting, I personally work on aspects of it for more than a decade, and incidentally I am looking just now at a very early paper on the (physical) ECT by Itamar Pitowsky.
Yet, while the list and its discussion are perhaps somewhat biased towards Nati’s and my interests, I would feel inconvenience to mention ECT as a separate milestone of mathematics (if not also as a milestone of physics and computer science 🙂 ).
I should say, that ten milestones was an upper bound of the Journal 13 years ago, and today in this post we can certainly accommodate additional milestones (especially referring to modern mathematics) if a reader feels they are in par with existing ones.
John, since 9(a) is closely related to 5(b) we can embed 9(a) into the text and add the extended CTT once its precise scope is determined as 9(b) 🙂
I don’t think 5 and 9 should be completely unified, 5A and 9B are totally different. I don’t see a perfect solution that would keep this structure.
True.
Though there are no formally undecidable PA-propositions, there are `undecidable’ number-theoretic propositions in the sense that the propositions are algorithmically verifiable, but not algorithmically computable (Theorem 2.1, p.37 of the CSR paper cited below).
`The truth assignments that differentiate human reasoning from mechanistic reasoning’
https://www.sciencedirect.com/science/article/pii/S1389041716300250?via%3Dihub
Even keeping essentially the same milestones, one may think of them in a different way,
1 + 2A. “Numbers and figures”. The idea of counting that developed into the arithmetic of rational numbers was married with geometry which deals with geometric shapes. This marriage gave birth to an unplanned child, irrationals.
3. The traditional way of presenting the discovery of Abel and Galois as “solvability” results is misleading. It is rather a theorem of how to choose the “simplest” equations to which all other equations of the same degree can be reduced. Instead I would rather stress this discovery by labeling it “Symmetry, actions, groups”. How to reveal a hidden symmetry of the roots of equations looking at the equations themselves?
4. In my view, two very different milestones are somewhat arbitrarily placed under a common roof. 4A. Both Newton and Leibniz actually realized, that in addition to the “algebraic” equations there is another class of equations, (ordinary) differential equations, that actually rule the world. The “Sturm und Drang” subsequent heroic epoch was exploring this new world, both by discovering new differential equations arising in the calculus of variations and developing means to solve them (expansion in Taylor series e.a.)
4B. Discovery of complex numbers is probably the greatest miracle in mathematics. It combines so many different features (commutative field, algebraically close and topologically complete, topologically 2-dimensional, i.e., rich), and for no apparent reasons for their coexistence! I am not sure whether there is a single person who can be credited for understanding this… Gauss?
I would add a few milestones from the later (19-20 century) mathematics.
A. “Art of infinity”: (Cauchy, Weierstrass, Cantor, Lebesque, …) Understanding of accurate rules to deal with infinity and infinite constructions. Close to your number 5, but with the stress on a slightly different instance.
B. “Art of name calling”. In 20th century we feel absolutely no compunction about calling objects as “points of an appropriate space” (topological space, Banach or Hilbert spaces, non-Archimedian spaces, etc.) or “elements of a certain algebraic structure” (i.e., treating matrices, vectors e.a. as “numbers”, with various rules of operating with them). This led to the category theory, homological algebra e.a. Probably, the most outstanding role here was played by Grothendieck.
C. Singularities. Discovery of the fact that a lot of phenomena can be explained and studied looking only at a tiny part of the objects, starting from the Cauchy residue theorem and ending up with various index theories.
Thanks, Sergei. Very interesting perspective.
Godel’s incompleteness theorem gets all the press, but Godel’s completeness theorem is far more important: by assuring us that true propositions have proofs, it undergirds the entire enterprise of pure mathematics.
Two problems you should mention: 1. The impossibility of squaring the circle. 2. Fermat’s Last Theorem.
They represent the persistence of mathematics: how it is possible to work on a problem for hundreds or thousands of years.
The first should go with the Galois theory as problem 3B. The second should join the PNT as 8B.
As Gauss said, the Fermat’s curve itself is not particularly important, and the proof of the theorem is not about the foundations of nature like the PNT. But the problem drove number theory for about 350 years. It is a milestone.
Lior, we mentioned trisecting an angle in part 3. FLT and the persistence of mathematics are discussed in the introduction.
I saw that you mentioned trisecting the angle (missed the FLT), but the impossibility of squaring the circle is much more difficult, and its proof a more significant milestone. It is one of the greatest achievements of the 19th century.
Why would you mention circling the square near Galois theory?
Is true that the transcendence of
is, in many ways, a result of number theory.
Narratively it would be easier to fit with trisecting angles, though thematically it probably belongs in section 8.
For all items on the list except one my reaction was “Of course!” Somehow the prime number theorem did not seem to me to be on the same level. I would replace that with Approximation.
Kimmo, what do you mean by approximation?
We wanted to have one number theory milestone what would be the best choice for that?
The mathematics has been applied since the times when we first counted apples and add two numbers. Theorems/proofs come much later. So maybe I can propose the algebraic automata theory or category theory instead of #10.
Also, I have an urge to add a conditional to #5A: There are various kinds of infinity —if there exists an actually infinite set in the first place.
Good list!
I like the list. I would add: the discovery of the positional number system, zero (also negative numbers), and the ensuing efficient algorithms for basic arithmetic (addition and multiplication). It’s amazing how long it took humanity to discover and spread these ideas (the Babylonians were already sort of aware of the positional number system idea).
Yuval, yes positional number systems (and zero) are great human discoveries which are largely mathematical. (Can we think about positional number system as a new, for its time, database for numbers?) I would be reluctant to regard it a milestone within mathematics because of its larger scope. (This may also apply to the discovery of natural numbers, the wheel, and digital computers.) And, thanks Scott.
I would say it’s a data structure, not a database. And I think it’s also a milestone within mathematics, because it seems like an essential step towards the diagonalization arguments in set theory, logic, and theory of computation. Can you think of effective numerical analysis (or any form of computation) without a positional number system?
It is interesting to see how many people call a “milestone” a particular result (proof of a long-standing conjecture or a revelation), while others (apparently, a minority) identify a milestone with a paradigm shift.
Sergei, what are the paradigm-shift milestone you would choose?
I will try, but I am not sure these paradigm shifts will be always beneficial in the retroaspect. One simple example is the concept of number. After the real breakthrough that counting and measuring are two sides of the same coin, there was a short outburst of enthusiasm until Pythagoras discovered irrationality of the square root of two. But the beauty of the axiomatic approach (הכל שפיט in today’s parlance) led to a self-imposed restriction that only ruler-and-compass-constructible irrationalities are allowed. This turned the brightest mins of the next millennium to the problems that were well beyond the scope of the mathematics of that time, lacking the adequate language.
Historically very near was Archimedes, who came very close to legalizing infinite constructions and introduce the real numbers as we know them. The Pythagorean rigor pushed Archimedes and his ideas outside of the “Pure” mathematics realm for quite long. You don’t have to stretch your imagination to imagine a world which accepted the Archimedes ideas: the unknown Newton and Leibniz would not take long to appear, and we could have the modern Calculus born a thousand years earlier, with all implications for engineering, physics and of course mathematics.
Another example which I like very much is the Ptolemean/Keplerian collision. The Ptolemean system at the time was more accurate and, what is more important, contained in itself an infinite potential for improvement: no matter what are the laws determining a periodic motion, it can be always expanded in a Fourier series (which is what the Ptolemean system was all about with its complicated system of circles). Newton adopted the Kepler model and derived from it the Laws of Nature in the form of differential equations. One could imagine a genius who would make a step in the different direction and develop the Fourier analysis. This would be a very unusual mathematics, with integrals preceding derivatives, probably variational principles preceding the Euler-Lagrange differential equations etc. Of course, sooner or later the two approaches would converge to the point of mutual understanding, but I am still musing about paradigm shifts 😉
I will return back here with a list of what I think was the sequence of turning events…
Dear Sergei, eagerly waiting…
When Descartes and Fermat developed what today is called analytical geometry it became possible to use algebraic tools to get insights into geometry and ask new geometrical questions based on algebraic considerations. This “wedding” of geometry and algebra has proved very powerful. New coordinate systems were developed, including homogeneous coordinates which results in being able to use algebra to investigate projective geometry which gave new insights into the conic sections and many other parts of geometry. Analytical geometry also spurred interest in the function concept and proved useful in exploiting the evolution of ideas related to Calculus. Very often exciting new developments in mathematics are born in geometric form (e.g. knot theory) and mature and develop when ways to use algebra to study the geometry phenomena (knot polynomials) are found. I think of analytical geometry as an important milestone.
Hi Joe, analytic geometry is described in the text in the geometry section. (But not the connections with calculus.) Alas, not knots.
Gil I would add with PNT the theorem of Dirichlet on prime numbers in arithmetic progressions as a milestone of using analytic methods in number theory.
Hi Yair, We mentioned Dirichlet’s theorem in the discussion and even the (then) very new theorem of Green and Tao.
On second thought… “Milestone” may be not exactly the right word to use. There are alternatives: think about Toynbee-like “challenges and responses” paradigm. The Greeks left a few challenges. Trisection, circle squaring and cube duplication problems was a challenge that was finally responded with creation of the Galois theory (which equations can be solved in quadratic irrationals) and the analytic number theory (transcendence of pi e.a.) The Fifth Postulate challenge was met with development of the concept of Riemann manifold. The Fermat equation challenge was responded by creation of the algebraic number theory and the modern Grothendieck-style algebraic geometry. Very often the formal solution of the problem, albeit duly noticed and celebrated, turns out to be just a step in fast progress driven by the accumulated momentum.
What should count as a milestone in such situations? The formulation of challenges? the key steps which eventually led to finding the proper response? the “formal solutions”? Sometimes challenge and response follow each other relatively fast, within decades (like with most of the Hilbert problems), sometimes it took millennium or longer.
Yes, several people suggested to mention, “homology” “Categories,” algebraic geometry, and also Riemannian geometry.
Hi there! Since You cite Newton in §4—”Analysis and the Connection to Physics”, I would add Joseph-Louis Lagrange for the inception of Symplectic Geometry. Three papers in 1808-1809-1810. (I wrote a paper about : “Les origines de la géométrie symplectique chez Lagrange” l’Enseignement Mathématique, N° 44, 1998, pp. 257—277. There is a pdf on my webpage.) Well I know that Analysis (or Geometry) and the Connection to Physics is a huge domain…
Hi Patrick! long time! Thanks for the comment.
Yes, too long…
Dear Gil, dear Nati,
Discovery number 7 only deals with the laws of classical probability — perhaps it could be expanded to include the discovery of quantum-mechanical laws (and of a way to formally represent them).
Along similar lines, Discovery n. 9 could include the impact of quantum computing on computability/complexity.
I made my first release of the solution of the NP-complete problem BETWEENNES on GitHub Inc. and I uploaded the binary so you could test it without the compilation of the source and report any error or check some examples.
Here is the release:
https://github.com/frankvegadelgado/P-NP/releases/tag/betweenness-1.0
Thanks in advance!!
Pingback: Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.) | Combinatorics and more
Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more