The enigmatic complexity of number theory

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.)