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.
Best Answer
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 geometrizationI'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.