# The enigmatic complexity of number theory

One of the most salient aspects of the discipline of number theory is that from a very small number of definitions, entities and axioms one is led to an extraordinary wealth and diversity of theorems, relations and problems--some of which can be easily stated yet are so complex that they take centuries of concerted efforts by the best mathematicians to find a proof (Fermat's Last Theorem, ...), or have resisted such efforts (Goldbach's Conjecture, distribution of primes, ...), or lead to mathematical entities of astounding complexity, or required extraordinary collective effort, or have been characterized by Paul Erdös as "Mathematics is not ready for such problems" (Collatz Conjecture).

(Of course all branches of mathematics have this property to some extent, but number theory seems the prototypical case because it has attracted some of the most thorough efforts at axiomization (Russell and Whitehead), that Gödel's work is most relevant to the foundations of number theory (more than, say, topology), and that there has been a great deal of work on quantifying complexity for number theory--more so than differential equations, say.)

Related questions, such as one exploring the relation between Gödel's Theorem and the complexity of mathematics, have been highly reviewed and somehow avoided any efforts to close. This current problem seems even more focused on specific references, theorems, and such.

How do professional mathematicians best understand the foundational source of the complexity in number theory? I don't think answers such as "once relations are non-linear things get complicated" or its ilk are intellectually satisfying. One can refer to Gödel's Theorem to "explain" that number theory is so complicated that no finite axiomitization will capture all its theorems, but should we consider this theorem as in some sense the source of such complexity?

This is not an "opinion-based" question (though admittedly it may be more appropriate for metamathematics or philosophy of mathematics): I'm seeking theorems and concepts that professional mathematicians (particularly number theorists) recognize as being central to our understanding the source of the breadth and complexity of number theory. Why isn't number theory trivial?

What references, especially books, have been devoted to specifically addressing the source of the deep roots of the diversity and complexity of number theory?

By contrast, I think physicists can point to a number of sources of the extraordinary wealth and variety of physical phenomena: It is because certain forces (somehow) act on fundamentally different length and time scales. The rules of quantum mechanics govern the interaction of a small number of subatomic particles. At sufficiently larger scales, though, quantum mechanics effective "shuts off" and classical mechanics dominates, including in most statistical mechanics, where it is the large number of particles is relevant. At yet larger scales (e.g., celestial dynamics), we ignore quantum effects. Yes, physicists are trying to unify the laws so that even the quantum mechanics that describes the interactions of quarks is somehow unified with gravitation, which governs at the largest scales... but the fact that these forces have different natural scales leads to qualitatively different classes of phenomena at the different scales, and hence the complexity and variety of physical phenomena.

• Is there some reason to think that number theory is an unusual example of this phenomenon? It seems to me that this is just a description of the general post-Euclid approach to mathematics, and that one could say much the same ("from a very small number of definitions, entities and axioms one is led to an extraordinary wealth and diversity of theorems, relations and problems") of, for the first example that comes to mind, group theory. – LSpice Oct 6 '17 at 16:47
• I regret to say I'm ending my participation in MathOverflow, for the same reason I decided a decade ago never again to edit Wikipedia. It's hard to express how disheartening it is to spend hours of volunteer labor explaining stuff---in this case, in a way that at least 19 MO users apparently found useful---only to have your work overridden by a smaller set of users, for being (part of something larger that's) "off-topic" or whatever it is. Who the hell has time for that? From now on, if I have math questions, I'll post them on my own blog. Was nice being here for 6 years; thanks everyone. – Scott Aaronson Oct 7 '17 at 14:42
• @MattF. if a finitely generated group $G$ satisfies $\forall x, x^5=1,$ then $G$ is finite. It is an unsolved problem in group theory. If you like number 33 more than 5, you can replace 5 by 33 and get another unsolved problem. – Mark Sapir Oct 7 '17 at 18:19
• @ScottAaronson I hope you reconsider. Your work here was by no means overridden -- it's there to stay. (And I cannot imagine that any question you ask here would ever be closed.) – Todd Trimble Oct 8 '17 at 2:22
• Ah, maybe I just didn't understand how MO worked. I thought my work was, not deleted (nothing ever is on the Internet :-) ), but permanently deprecated---similar to what happened when my students and I wrote Wikipedia pages about some CS theory topics, which were then promptly deprecated for being "not notable." In this case, though, it seems to have taken less than a day for the "off-topic" verdict to be reversed---I'd say clearly the right decision, since while the question wasn't perfect, it's not hard to error-correct it to something of real research-level mathematical interest. Thanks MO! – Scott Aaronson Oct 8 '17 at 6:04

I'm not a number theorist, but FWIW: I would talk, not so much about Gödel's Theorem itself, but about the wider phenomenon that Gödel's Theorem was pointing to, although the terminology didn't yet exist when the theorem was published in 1931. Namely, number theory is already a universal computer. Or more precisely: when we ask whether a given equation has an integer solution, that's already equivalent to asking whether an arbitrary computer program halts. (A strong form of that statement, where the equations need to be polynomial Diophantine equations, was Hilbert's Tenth Problem, and was only proven by the famous MRDP Theorem in 1970. But a weaker form of the statement is contained in Gödel's Theorem itself.)

Once you understand that, and you also understand what arbitrary computer programs can do, I think it's no surprise that number theory would seem to contain unlimited amounts of complexity. The real surprise, of course, is that "simple" number theory questions, like Fermat's Last Theorem or the Goldbach Conjecture, can already show so much of the complexity, that one already sees it with questions that I intend to explain to my daughter before she's nine. This is the number-theoretic counterpart of the well-known phenomenon that short computer programs already give rise to absurdly complicated behavior.

(As an example, there are 5-state Turing machines, with a single tape and a binary alphabet, for which no one has yet proved whether they halt or not, when run on a tape that's initially all zeroes. This is equivalent to saying that we don't yet know the value of the fifth Busy Beaver number.)

Here, I think a crucial role is played by a selection effect. Above, I didn't talk about the overwhelming majority of 5-state Turing machines for which we do know whether they halt, nor did I talk about 10,000-state TMs---because those wouldn't have made my point. Likewise, the number-theory questions that become famous, are overwhelmingly skewed toward those that are easiest to state yet hardest to solve. So it's enough for some such questions to exist---or more precisely, for some to exist that are discoverable by humans---to give rise to what you're asking about.

Another way to look at it is that number theorists, in the course of their work, are naturally going to be pushed toward the "complexity frontier"---as one example, to the most complicated types of Diophantine equations about which they can still make deep and nontrivial statements, and aren't completely in Gödel/Turing swampland. E.g., my layperson's caricature is that linear and then quadratic Diophantine equations were understood quite some time ago, so then next up are the cubic ones, which are the kind that give rise to elliptic curves, which are of course where number theory still expends much of its effort today. Meanwhile, we know that if you go up to sufficiently higher complexity---apparently, a degree-4 equation in 9 unknowns suffices; it's not known whether that's optimal---then you've already entered the terrain of the MRDP Theorem and hence Gödel-undecidability (at least for arbitrary equations of that type).

In summary, if there is a borderland between triviality and undecidability, where questions can still be resolved but only by spending centuries to develop profound theoretical machinery, then number theory seems to have a pretty natural mechanism that would cause it to end up there!

(One sees something similar in low-dimensional topology: classification of 2-manifolds is classical; 4-manifold homeomorphism is known to be at least as hard as the halting problem; so then that leaves classification of 3-manifolds, which was achieved by Perelman's proof of geometrization I've since learned this is still open, although geometrization does lead to a decision procedure for 3-manifold homeomorphism.)

In some sense I agree with Gerhard Paseman's answer, except that I think that Wolfram came several generations too late to be credited for the basic insight, and that there's too much wrong with A New Kind of Science for it to be recommended without strong warnings. The pictures of cellular automata are fun, though, and do help to make the point about just how few steps you need to take through the space of rule-systems before you're already at the edge of the abyss.

• Hmm although I like this answer, I believe it also shows that the question is not too interesting the way it is posed. It is like if you are fascinated by very short verses that are able to convey big wealth of perceptions, associations, emotions, inexplicable thoughts, etc., but ask instead about nonformalizability aspects of the natural language. The two are closely related, but still are very different things. – მამუკა ჯიბლაძე Oct 7 '17 at 4:51
• Your comment below the post that contrasts decidability of the theory of the field R with undecidability of the theory of the ring N also seems very relevant to the OP's question. – Todd Trimble Oct 7 '17 at 9:39
• Re: "if there is a borderland between triviality and undecidability, where questions can still be resolved but only by spending centuries to develop profound theoretical machinery, then number theory seems to have a pretty natural mechanism that would cause it to end up there!", one could replace "number theory" with "program analysis", or by virtue of MRDP, "pull back" this observation about number theory to one about program analysis. Despite Rice's theorem, this arena is a large and fruitful area of research and practical applications--and it could be forever. – Steve Huntsman Oct 9 '17 at 14:09
• This is a good partial answer but I don't think it addresses the core of the question, which is why number theory has so much amazingly beautiful structure near the border between triviality and undecidability. The border between P and NP is populated by some cool stuff (linear programming, blossoms, PCP) but things like reciprocity theorems or the connection with complex analysis defy ordinary expectations; you can't predict them just by pretending that the primes are random or something like that. There's a certain amount of 'unreasonable effectiveness' that seems unique to number theory. – Timothy Chow Oct 9 '17 at 19:01
• @Stella: When I said "equivalent," I just meant that knowing either one reduces the other to a "mere" finite computation -- not that we can place any effective bound whatsoever on the length of the computation! – Scott Aaronson Oct 20 '17 at 10:36

What references, especially books, have been devoted to specifically addressing the source of the deep roots of the diversity and complexity of number theory?

To a first approximation, I would say that the answer to this question is, there are none.

You have emphasized that you are interested in the point of view of professional number theorists. I would say that for most number theorists, a term such as the "diversity and complexity of number theory" brings to mind central problems in modern number theory, such as the generalized Riemann hypothesis, the parity problem in sieve theory, the Langlands conjectures, the structure of Gal(${\overline{\mathbb{Q}}}/\mathbb{Q})$, etc. These are the sorts of things that professional number theorists might cite as the "source" of the diversity and complexity of number theory. Note in particular that things such as Hilbert's Tenth Problem are interesting to relatively few professional number theorists. The kind of "complexity" that logicians and theoretical computer scientists are interested in is not what interests most number theorists. Roughly speaking, it is because undecidability questions are regarded as signs of chaos whereas number theorists are interested in finding structure.

If we want an explanation of why there is so much diversity and complexity in number theory even when we focus on the structures that occupy the attention of number theorists, then I do not think that looking towards undecidability will give us the answer. Generalized chess, for example, exhibits that kind of "complexity" but the deeper one studies chess, the more it seems to exhibit seemingly "random" behavior that defies elegant description (just take a look at the record-holders in the endgame tablebases for example). In generalized chess we find no sign of anything with the beautiful and deep structure of, say, class field theory.

Seeking an explanation of what number theorists regard as the diversity and complexity of their subject is instead likely to elicit essays with "unreasonable effectiveness" or some such in the title, and the discussion will likely follow the same path that the discussion of Wigner's article has taken. For example it can be pointed out that there is a natural selection process taking place, with number theorists deliberately gravitating towards the areas of diversity and complexity and abandoning areas that are sterile.

• Indeed... very great answer. +1. – David G. Stork Oct 9 '17 at 0:28
• In this spirit, I'd say that carrying carries a fair amount of the complexity. For if we represent numbers in binary, and add/multiply with school algorithms, but forget about carrying, we're left in the ring ${\mathbb F}_2[X]$. And then the Riemann hypothesis and BSD (accepting finiteness of Sha) are in the bag. But sadly $1000000 +$1000000 = $0. – Marty Oct 9 '17 at 21:38 • @Marty : Carrying makes it harder to prove things, for sure. But it doesn't explain the source of the subtle patterns that make number theory so rich. Whatever that source is, somehow it makes its presence felt even when carrying tries to get in the way. – Timothy Chow Oct 9 '17 at 23:57 • I just saw the Star Wars trailer, so now I might be inclined to look for "the source" which "makes its presence felt". My previous comment was meant to give at least one source... one which I think is not considered sufficiently. – Marty Oct 10 '17 at 3:20 • I was going to write (under the oririgal post): "the source is that integers allow both addition and multiplication, but @Marty's post here makes it clear that at least something else is needed as well. I wonder if there is a way to describe the extra complexity coming from carrying in a more notation independent way? – Vincent Apr 16 at 7:54 You might enjoy A New Kind Of Science. It is a lavishly illustrated book with copious (Edit: endnotes, not references; thanks to Scott Aaronson's review for helping me see the distinction) centered around the theme of computation and complexity in the behaviour of cellular automata. Although you might listen to the book's critics before diving into it, I spent a few hours skimming its thousand plus pages and did not regret the time spent. One can take an automatic (or syntactic) view of your question, as has been done in another worthy read (Goedel, Escher, Bach: An Eternal Golden Braid), where typographical number theory is considered. An upshot of this is that the provable sentences of such a theory are recursive (a recursive set), while true sentences (those holding in a standard model of the theory) are not recursive (they are recursively enumerable, if I recall correctly). Edit 2017.10.07 In fact I recalled incorrectly. Thanks to Alex Kruckman who commented that the set of provable sentences is recursively enumerable (not recursive) and the set of true sentences is not arithmetically definable (really different from recursively enumerable). Looks like I need some retraining. End Edit 2017.10.07. In order to relate this view to the philosophical aspect of your question, I would want to understand more about how you perceive complexity, but I am confident in suggesting that your perception relates to how simply you can describe a collection of things, and that the technical results say there will be no simple description any time soon. Apart from the metamathematics involved in recursion theory and studying concepts of descriptive and definable complexities, I would say that studying behaviour of automata (and more so, engaging in a psychological study of such studies!) is as quick a path to answering your question as any. An example of this is How do these primes jump? , where I take a simple variant of a prime sieve algorithm and ask some number-theoretic questions. I have not formalized the questions and the study, but I would be surprised if I needed much more than PRA (primitive recursive arithmetic) to carry out such a study. I think there are even simpler systems whose metamathematics are easily formalized and will yield complexity similar to what you see in number theory. (Edit: Eternal, not Enigmatic) Gerhard "Who Will Study The Studier?" Paseman, 2017.10.06. • Gerhard: I consider both Stephen Wolfram and Doug Hofstadter as personal friends; both have dined at one of my homes and I spent the day with Stephen yet again last month. I have read my signed copies of both NKS and GEB several times. Doug would focus on recursion and Stephen on "algorithmic irreducibility" but is this how most professional number theorists conceive of the source? I grant that our notions of what is difficult or complex or central in a discipline will change, but now what do we believe is the source? Casting the problem in the realm of automata may indeed help. – David G. Stork Oct 6 '17 at 18:39 • In GEB it is claimed that filling the hole in the middle of Escher's Print Gallery is impossible: "...Escher could not have completed that portion of the picture without being inconsistent with the rules by which he was drawing the picture. That center of the whorl is -- and must be -- incomplete", so "Escher has thus given a pictorial parable for Goedel's Incompleteness Theorem". But this is completely wrong: Lenstra later used Tate's uniformization of elliptic curves (which was developed for applications in number theory) to precisely fill the hole. Andy Putman's comment is apt. – nfdc23 Oct 6 '17 at 19:51 • @nfdc23 perhaps you are not reading the claim in GEB properly. If you take the "center of the whorl" to be either the exact center point or a neighborhood of the center it really can't be completely filled in: you can't continuously extend the Escher work to include the center point any more than the group$\mathbf C^\times/q^{\mathbf Z}$can be made to include 0 while still being a group. – KConrad Oct 7 '17 at 5:13 • @KConrad: Given what is written in that book about that Escher print, the proposed interpretation focusing on the origin point is not what is meant. – nfdc23 Oct 7 '17 at 7:12 • @nfdc23, KConrad: Now I've seen everything! – Lucia Oct 8 '17 at 1:07 It is an interesting question if there is some complexity-like hierarchy for (ordinary) conjectures in number theory, and we can limit our interest even to conjectures claiming a certain randomness of the prime numbers. (For such statements I am not aware of universality results, but this by itself is interesting.) Something of this kind was manifested in polymath4 - the task of finding efficiently a prime number with$n$digits. This can be done if you take for granted Cramer's conjecture regarding gaps between primes, and it can also be achieved if you take for granted very strong derandomization conjectures (which in turn follow (or some weakening follows) from very very very very stronger form of the$NP \ne P$conjecture.) Another manifestation of the speculation regarding complexity-type hierarchy for (standard) number-theoretic conjectures is in this MO question Infinitely many primes, and Mobius randomness in sparse sets which proposes that Mobius randomness for sparse sets might be intractable. (Yet another related, but of less speculative nature, aspect of the complexity of number theory can be found in this question Walsh Fourier Transform of the Möbius function and the post about AC0-prime number theorem. referring to various problem that were raised from a lecture by Sarnak at HUJI.) • May I ask: What form might a universality result concerning the randomness of primes take? I am unclear on what you mean here by "universality." – Joseph O'Rourke Oct 8 '17 at 18:58 • Joe, a universality result would say that for a certain class of problems which describe a certain fragment of number theory, this fragment already represents a universal computer. I am not aware of results in this direction for statements regarding randomness properties of primes (but I did not carefully think if this is at all possible). – Gil Kalai Oct 8 '17 at 20:39 • Thanks, Gil! That clarifies. Such a result does not seem so far beyond "current technology," to use that useful popular phrase. – Joseph O'Rourke Oct 8 '17 at 23:09 • @GilKalai what is the 'very very very very stronger form' of the NP\neq P$ conjecture? – Brout Oct 9 '17 at 23:09
• Other mathematical fields generate lots of results from a few axioms. Probability theory comes to mind. – ttw Oct 12 '17 at 4:51