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.

  • 28
    $\begingroup$ 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. $\endgroup$
    – LSpice
    Oct 6, 2017 at 16:47
  • 51
    $\begingroup$ 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. $\endgroup$ Oct 7, 2017 at 14:42
  • 20
    $\begingroup$ @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. $\endgroup$
    – user6976
    Oct 7, 2017 at 18:19
  • 21
    $\begingroup$ @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.) $\endgroup$
    – Todd Trimble
    Oct 8, 2017 at 2:22
  • 20
    $\begingroup$ 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! $\endgroup$ Oct 8, 2017 at 6:04

4 Answers 4


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.

  • 3
    $\begingroup$ 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. $\endgroup$ Oct 7, 2017 at 4:51
  • $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Oct 7, 2017 at 9:39
  • $\begingroup$ 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. $\endgroup$ Oct 9, 2017 at 14:09
  • 9
    $\begingroup$ 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. $\endgroup$ Oct 9, 2017 at 19:01
  • 1
    $\begingroup$ @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! $\endgroup$ Oct 20, 2017 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.

  • $\begingroup$ Indeed... very great answer. +1. $\endgroup$ Oct 9, 2017 at 0:28
  • 3
    $\begingroup$ 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. $\endgroup$
    – Marty
    Oct 9, 2017 at 21:38
  • $\begingroup$ @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. $\endgroup$ Oct 9, 2017 at 23:57
  • $\begingroup$ 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. $\endgroup$
    – Marty
    Oct 10, 2017 at 3:20
  • $\begingroup$ 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? $\endgroup$
    – Vincent
    Apr 16, 2019 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.

  • 4
    $\begingroup$ 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. $\endgroup$ Oct 6, 2017 at 18:39
  • 10
    $\begingroup$ 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. $\endgroup$
    – nfdc23
    Oct 6, 2017 at 19:51
  • 4
    $\begingroup$ @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. $\endgroup$
    – KConrad
    Oct 7, 2017 at 5:13
  • 2
    $\begingroup$ @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. $\endgroup$
    – nfdc23
    Oct 7, 2017 at 7:12
  • 5
    $\begingroup$ @nfdc23, KConrad: Now I've seen everything! $\endgroup$
    – Lucia
    Oct 8, 2017 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.)

  • 1
    $\begingroup$ 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." $\endgroup$ Oct 8, 2017 at 18:58
  • 3
    $\begingroup$ 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). $\endgroup$
    – Gil Kalai
    Oct 8, 2017 at 20:39
  • $\begingroup$ Thanks, Gil! That clarifies. Such a result does not seem so far beyond "current technology," to use that useful popular phrase. $\endgroup$ Oct 8, 2017 at 23:09
  • $\begingroup$ @GilKalai what is the 'very very very very stronger form' of the NP\neq P$ conjecture? $\endgroup$
    – Turbo
    Oct 9, 2017 at 23:09
  • $\begingroup$ Other mathematical fields generate lots of results from a few axioms. Probability theory comes to mind. $\endgroup$
    – ttw
    Oct 12, 2017 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.