85

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.

Gil Kalai
  • 24,218
David G. Stork
  • 2,518
  • 1
    While not exactly an answer to your question, the work of Harvey Friedman may be of interest to you. A big part of his results is constituted by statements of arithmetic which are known to not be provable in many strong theories, even stronger than ZFC. – Wojowu Oct 06 '17 at 16:36
  • @Wojowu: Thanks. I'll certainly look at the work of Harvey Friedman. – David G. Stork Oct 06 '17 at 16:37
  • 7
    Is it not the simplicity of the rules which itself endows such endless possibility? Rules are restrictions. – it's a hire car baby Oct 06 '17 at 16:39
  • 28
    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 06 '17 at 16:47
  • 4
    @RobertFrost: Interesting thought. My intuition is that one needs the "right" balance of simplicity (lack of restrictions) and structure (presence of restrictions) in order to generate the broad complexity we find. Perhaps number theory as a discipline has evolved by adding or releasing restrictions so as to keep the field "appropriately" rich and interesting for the current state of mathematicians' cognitive and abilities and computational resources. Perhaps someday, when factoring humongous integers can be done by ubiquitous quantum computers, we'll add restrictions to number theory. – David G. Stork Oct 06 '17 at 16:49
  • One of the striking examples of "complexity behind simple statement" is Goldbach's conjecture, which is understandable to a primary school pupil, and yet resists to any attempt of proof since 1742. – Sylvain JULIEN Oct 06 '17 at 16:52
  • 16
    Then after it is closed, I will vote to reopen. Not only are references requested, there are technical metamathematical issues pertaining. This is not a non-mathematical question. Gerhard "The Extra Not Is Needed" Paseman, 2017.10.06. – Gerhard Paseman Oct 06 '17 at 19:06
  • 8
    Rather than identifying a real feature of number theory, I think this question just reflects an ignorance of the wider world of mathematics. There are deep, difficult, and fundamental questions in all the major branches of the subject. They just require a little more background to appreciate, and thus do not appear in popularizations of the subject. I should also point out that some of the examples the OP gives (e.g. the classification of finite simple groups and the monster group) are not part of number theory at all. – Andy Putman Oct 07 '17 at 00:53
  • 5
    @AndyPutnam: Of course I fully understand that there are "deep, difficult, and fundamental questions in all the major branches" of mathematics. The reason I chose number theory in particular was because the efforts at axiomization are famous (Russell and Whitehead), the axioms spare, and that most mathematicians feel that number theory is the core foundation of the subject. I suppose, though, that we disagree, because I believe that this complexity is "a real feature of number theory." I'm happy to change examples to ones from number theory, if you think that makes a difference. – David G. Stork Oct 07 '17 at 01:12
  • 1
    @LSpice, consider $\exists x,y,z\ x^3 + y^3 = z^3 + 33$, which is an open problem in number theory. What would be the best analog in group theory, of a simple first-order sentence not obviously settled by the axioms? –  Oct 07 '17 at 07:25
  • @LSpice, By "not obviously settled" I mean "not obviously proved, not obviously disproved, and not obviously independent". E.g. $(\forall x,y xyy=yyx) \right arrow (\forall x,y xy=yx)$ is not obviously probable, disprovable, or independent to me -- and if group theory is as enigmatic as number theory we should be able to find similarly simple statements which are actually open problems. –  Oct 07 '17 at 08:01
  • 51
    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 07 '17 at 14:42
  • 4
    @Scott, thank you for your contributions. I am sure more than 20 of us found them useful I too am sorry about the flawed system, and am in hopes of improving it. I will add your blog to my reading list. Gerhard "Has Voted To Reopen This" Paseman, 2017.10.07. – Gerhard Paseman Oct 07 '17 at 17:31
  • 4
    Thanks Gerhard! Always appreciated your contributions here, including the ever-shifting middle names. – Scott Aaronson Oct 07 '17 at 17:59
  • 20
    @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. –  Oct 07 '17 at 18:19
  • Y9u might find the book "Gödel, Escher, Bach: an eternal gold braid" one of the most accessible and enjoyable popular books on this area..... – Stilez Oct 07 '17 at 20:15
  • @Stilez: Please read my comment below about my longtime friends Doug Hofstadter (and Stephen Wolfram) and their books *GEB* and *NKS*.. – David G. Stork Oct 07 '17 at 21:09
  • 21
    @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 08 '17 at 02:22
  • 7
    @ScottAaronson the whole reason questions are closed instead of deleted (across the entire SE network) is so that work that went into answering them is not lost/overridden, even when it is decided the question itself may be off topic (and it seems that decision has now been reversed in this case). – mbrig Oct 08 '17 at 05:31
  • 4
    BTW is the creation of the new tag (philosophy) really needed? There already exists ([tag:math-philosophy]). If you think that a distinct tag is needed, creating some basic tag-info would be a reasonable thing to do. (Single occurrence tags are automatically removed after a certain time unless they have tag-wiki.) Since I do not want to digress from the question too much, tag-related issues can probably be discussed either in chat or on meta. – Martin Sleziak Oct 08 '17 at 05:45
  • 20
    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 08 '17 at 06:04
  • @MarkSapir, that is a nice example. And it is equivalent to "every sufficiently large group has an element x with x^5 != 1", by the compactness theorem for first-order logic. –  Oct 08 '17 at 07:16
  • @MattF. I do not see how this follows from compactness. The fact is true, it is Kostrikin's theorem: https://groupprops.subwiki.org/wiki/Kostrikin%27s_theorem_on_restricted_Burnside_problem. In the case of 33, it follows from Zelmanov's theorem for which he got his Fields medal. But of course you need to bound the number of generators. –  Oct 08 '17 at 11:33
  • 6
    @ScottAaronson Whew! I'm so relieved. Losing you would have been a terrible loss for MO. Your last comment is spot on by the way. – Todd Trimble Oct 08 '17 at 15:56
  • 3
    I re-tagged it math-philosophy. – Gil Kalai Oct 08 '17 at 18:00
  • 12
    I would say that what Cantor, Abel-Ruffini, Turing, Godel, etc. teach us is that it is complexity, rather than simplicity, that should be the default hypothesis for the consequences of any given mathematical theory that is not utterly trivial. The mystery then is not why number theory is complex; it is why there are any non-trivially "easy" theories at all (e.g. linear algebra in fixed dimension, the differential calculus of elementary functions, Euclidean geometry, or more generally algebraic geometry in bounded dimension and degree over an algebraically closed field). – Terry Tao Oct 08 '17 at 19:33
  • 8
    ... this default to complexity, by the way, is something which is perhaps obscured by a rather strong selection bias in mathematical education below the graduate level, in that one is presented almost exclusively with those mathematical theories that do happen to be easy enough that problems in those theories can be assigned as homework to undergraduates. It can be a rude shock for instance as a graduate student to realise that most PDE, or even ODE, cannot be solved by the methods presented in undergraduate classes; but this situation is the rule rather than the exception. – Terry Tao Oct 08 '17 at 19:39
  • 4
    Dear Terry, while solving a question of general nature is often complex and intractable in ways we understand, the fate of famous mathematical problems is not so bad. Maybe we have bias in selecting problems, and in our taste. We prefer problems which interact well with the rest of mathematics and arn't intractable. There might be also some inherent structural reason or some selection bias that makes mathematics suprisingly possible. For some discussion on why math is possible and a link to a paper by Kazhdan, see https://gilkalai.wordpress.com/2013/05/23/why-is-mathematics-possible/ – Gil Kalai Oct 08 '17 at 21:06
  • 3
    @DavidG.Stork Since I see that you mentioned number of views and number of upvotes as a supporting evidence for quality of the question. I'll point out that this question was (in fact, at the moment still is) in the network-wide hot questions list. In such cases, many of views and upvotes come from users outside MO community, so one should be a bit more careful in evaluating such questions or at least take this into consideration. (I am not qualified to judge whether it is a suitable question or not - I am just mentioning this as a factor in voting/view count.) – Martin Sleziak Oct 09 '17 at 03:40
  • 1
    @MartinSleziak: Thanks. I was unaware of that fact. Nevertheless, I made my remark when five contributors voted to close this question and left it [on hold]. The point +29, and just one answer has +57 and getting contributions from elite mathematicians—which certainly counts as some support (though admittedly not the level I had said, due to my ignorance). Thanks again! – David G. Stork Oct 09 '17 at 04:00
  • 3
    @GilKalai : interaction with other fields is certainly a good indicator that a theory may not be as complex as a randomly generated theory, if for no other reason that it increases the probability that the theory may become simpler than it first appears when interpreted using the language and insights of the other field (or, even better, when interpreted using a synthesis of two or more fields). For instance, there are parts of number theory that strongly resemble the comparatively "easier" field of algebraic geometry, and this is indeed a rich and intensively studied part of the subject. – Terry Tao Oct 10 '17 at 16:36

4 Answers4

111

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.

Scott Aaronson
  • 9,743
  • 3
    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 07 '17 at 04: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 07 '17 at 09: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 09 '17 at 14:09
  • 9
    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 09 '17 at 19:01
  • 1
    @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
  • A minor but important correction: It is known that either degree $4$ or $9$ variables is a polynomial is sufficient to have a universal c.e. solution set, but the universal degree $4$ polynomial has $58$ variables and the universal polynomial with $9$ variables has degree $1.6\times 10^{45}$ (or at least these were the known bounds in 1980). – James Hanson Mar 09 '21 at 10:11
41

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.

Timothy Chow
  • 78,129
  • Indeed... very great answer. +1. – David G. Stork Oct 09 '17 at 00:28
  • 3
    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 09 '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 09 '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 03: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 '19 at 07:54
  • @Marty I hope you don't mind if I respond to your comment from a while back - I found it very interesting because I disagree in a pretty fundamental way. I think part of Timothy Chow's answer was to demonstrate the difference between complexity, in the sense of interesting structure, and difficulty. Maybe a good example of a fact in number theory which is difficult to prove but not that interesting without knowing what went into the proof is that there exist three integers whose cubes add up to 33. – Will Sawin Sep 22 '20 at 21:40
  • Maybe a good example of an interesting fact that suggests rich structure but isn't (by modern standards) hard to prove is unique factorization into primes. Anyways the structure in number theory, such as the Langlands program, structure of elliptic curves as demonstrated by BSD, patterns of zeroes of zeta and $L$-functions, is almost perfectly preserved by the removal of carrying. In fact one could argue that the structure is visible more clearly in this setting, and that the conceptual source of some of the complexity is the geometry that we see when we avoid carrying. – Will Sawin Sep 22 '20 at 21:42
  • (Is there a better conceptual understanding of why BSD should be true than the proof over $\mathbb F_q(t)$ assuming finiteness of Sha / the Tate conjecture and then the guess that this phenomenon is probably stable under the addition of carrying?) A perhaps overly cryptic way of describing this is that the complexity in number theory consists of meat and potatoes and carrying is responsible for the potatoes and not the meat. – Will Sawin Sep 22 '20 at 21:44
  • I guess it's subjective which part is the meat and which the potatoes! I agree there are deep geometric reasons for all these things over $\mathbb{F}_q(t)$. And lots of people hope this will help in the number field case. But I think that what makes number theory really number theory (and not "just" geometry") is this excess complexity. And phrasing the excess as "carrying" might be helpful and not just cute. – Marty Sep 24 '20 at 05:46
9

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 Paseman
  • 12,968
  • 4
    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 06 '17 at 18:39
  • My training (and practice) in metamathematics is more solid than my training in number theory, and I have neither as a profession. I can give you more of what I think a foundational basis for the complexity would be, but I do not know how to cast it in terms that are purely within number theory. The closest I can offer for the professional number theorists is above: study arithmetical dynamical systems and their complexity, especially around cellular automata. Gerhard "Likes Having His Amateur Status" Paseman, 2017.10.06. – Gerhard Paseman Oct 06 '17 at 18:53
  • 10
    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 06 '17 at 19:51
  • @nfdc23 : It is tempting to start a flame war here. Instead, I invite you to vote to close as you deem appropriate/are able. I stand by my responses. Gerhard "And Also By My Mistakes" Paseman, 2017.10.06. – Gerhard Paseman Oct 06 '17 at 19:58
  • 1
    No need for flames. This is (to me at least) a serious and important question. I actually expected an answer of the form that referred to Chaitin or Kolmogorov or a philosopher of mathematics (possibly Gödel, as appears in a related question, or Turing), and was pleased to learn of the relevant work of Harvey Friedman which indeed seems relevant. I wish there were a book (beyond *GEB* and *NKS*) where I could turn. – David G. Stork Oct 06 '17 at 20:54
  • Correction: The set of provable sentences in TNT (or any formal system of arithmetic to which Gödel's theorem applies) is recursively enumerable but not recursive. The set of true sentences in the standard model is not recursively enumerable (not $\Sigma_1$), in fact not even arithmetic (not $\Sigma_n$ for any $n$). – Alex Kruckman Oct 07 '17 at 03:40
  • Thank you Alex. I will update later. Gerhard "Have To Go To Bed" Paseman, 2017.10.06. – Gerhard Paseman Oct 07 '17 at 04:33
  • 4
    @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 07 '17 at 05:13
  • 2
    @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 07 '17 at 07:12
  • 5
    @nfdc23, KConrad: Now I've seen everything! – Lucia Oct 08 '17 at 01:07
5

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

Gil Kalai
  • 24,218
  • 1
    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 08 '17 at 18:58
  • 3
    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 08 '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 08 '17 at 23:09
  • @GilKalai what is the 'very very very very stronger form' of the NP\neq P$ conjecture? – Turbo Oct 09 '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 04:51
  • @ttw: Well, I work in probability, statistics (admittedly, more as a user than as a theorist), but I don't see complexity in probability at nearly the level one finds in number theory. Bayes theorem, convergence theorems, and such don't lead to anything like the astounding complexity of the Collatz Conjecture or distribution of twin primes, or ... True, there can be complex, subtle actual practical problems addressed in probability, but those generally arise from complex data, which came from some complex system outside math... not because of it. – David G. Stork Feb 27 '21 at 05:26