# Computational number theory

I am interested in learning computational number theory and doing some computer experiments.

Which sort of number theory problems can be solved by using computers? For example, is it possible to determine the ring of integers in number field extensions or find the discriminant of the extensions?

To what extent one can use computers to solve number theory problems?

What is the best software for this purpose? Maple, Matlab, Pari/gp or Mathematica?

First, this question is extremely broad and thus I hesitate to start answering it, but anyway some remarks.

Number therory is a broad field and there are many different types of problems to which "computers" can contribute in one form or another.

Since you ask about rings of integers let me focus on this.

Regarding literature: One book I can recommend is Henri Cohen "A Course in Computational Algebraic Number Theory" and there is also a follow-up "Advanced Topics in Computational Number Theory".

In this book the author explains, among others, how to solve the basic tasks of Comptuational Algebraic Number Theory. So how to calculate with algebraic numbers, calculating rings of integers, discriminant, Galois group and so on. Also, certain methods of factorisation are discussed as well as question on arithemtic of polynomials.

The author is/was a main contributor to the development of Pari.
Pari is specialized for number theory; opposed to the other programms you mention.

Roughly, the functionality of Matlab is not geared towards number theory. Mathematica and Maple offer more here, certainly useful for some things and for some even very good as far as I know, but not specialized for number theory. An important (non-free) other program is Magma, which is I think considered as leading for certain number theory (related) tasks.

And, last but certainly not least, there is a large free open-source project Sage http://www.sagemath.org that has a certain focus on number theory (the founder William Stein is a number theorist). It inculdes (more or less) Pari and much other free open-source math software; some directly or indirectly relevant for number theory.

If you search for a possibility to do computational number theory and to potentially do something of lasting value, I would recommend that you look into Sage. Its web page offers a lot of documentation but also (number theory) papers written with the help of Sage. Yet also (number theory) lecture notes and text books with a computational slant. The developpment process seems very open and there are plenty of tasks to be done (from small to large, from beginner friendly to research level). [Note: I did not contribute anything to Sage, I only followed its developpment from a distance but somewhat in detail.]

You might be interested in Project Euler (http://projecteuler.net/), which guides you through solving progressively more difficult math problems using computer programming. This is not exactly what you asked about, but is rather a complement to quid's excellent answer.

There's a different sort of number theory, combinatorial, that benefits tremendously from computation and experimentation. An excellent website to get you started is http://www.experimentalmath.info/. Borwein and Bailey (responsible for that website) are two of the champions of using computers to find new results, and Zeilberger is the godfather of using computers to prove combinatorial results.

Surprisingly, of the various branches of number theory (analytic, algebraic, combinatorial, additive), it seems to me that analytic number theory has benefited the least from experimentation.

• To me it is indeed surprising that you hold the believe in the last line ;D What about the Prime Number Theorem? It was conjectured based on data/experiment. Or, for some though likely not all people believe in the Riemann Hypothesis is mainly due to experimental data. The Mertens conjecture was disproved using computation. – user9072 Jun 29 '12 at 17:18
• The PNT was conjectured based on data from 200+ years ago, the RH on data from 150+ years ago. I think you have the situation with Mertens Conjecture backwards: it was supported by data but is now known to be false. – Kevin O'Bryant Jun 29 '12 at 18:11
• Well, even if old, to me PNT and RH seem like a lot of benefit. Regarding Mertens: the disproof involves computation, see in particular section 4 of the orig. paper dtc.umn.edu/~odlyzko/doc/arch/mertens.disproof.pdf – user9072 Jun 29 '12 at 19:08
• Certainly. I did only write "the least", after all. What I had in mind when I wrote that was that of my friends (not a random sample) in the various areas, the analytic number theorists are the least likely to use experiment to figure out what is true, or to decide how to steer a proof. – Kevin O'Bryant Jun 30 '12 at 4:37
• Interesting. I agree ones view on this could/should well depend one various (subjective) factors. Likely also on where one draws the line between the different subfields. – user9072 Jun 30 '12 at 12:23

You might look at Bach and de Shallit's book, for one.

In general, I'd recommend Python (a real computer language, with built-in long ints) for numerical experimentation.

Sage is an extension of Python, with many built-in number-theoretic bits of data and also algorithms.

It is true that Mathematica and other commercial/proprietary mathematics packages have widespread commercial use, but the non-public-ness of their actual algorithms, etc., is rather disappointing if one cares about what is actually happening. Bad enough that we are not able to personally witness the correctness of a large-integer computation, but even worse if we cannot even view the algorithms involved. Also, as computer languages, they have considerable failings, I think.

My favorite book on computational number theory is A Course in Computational Number Theory by David Bressoud and Stan Wagon, which is based on Mathematica. It contains lots of Mathematica code, printed right in the body of the text, and you can easily implement this code to both duplicate the results in the text and explore with your own problems. Several of the homework problems are of the form "Modify the code of Algorithm 1 so that it performs...," thereby saving you lots of programming time. It comes with an Appendix on basic Mathematica coding, and although I'm an expert Mathematica programmer and do not need that background, I have the sense that anyone computer-literate can implement the code in the text and understand the language. You also get to exploit numerous number-theoretic functions built into the language, on prime factorization, totients, and so on.

I would say my favorite book on number theory is An Illustrated Theory of Numbers by Martin H. Weissman, whose graphical presentations really make the discipline memorable and help develop intuition and insight. This book does not treat the computational aspects of number theory, however, and hence is not quite right for the question as asked.

• Thanks! I'm happy that you're enjoying the book. I created some tutorials for novice programmers to learn Python for number theory at illustratedtheoryofnumbers.com/prog.html. I hope this complements the book well and introduces basic computational number theory. – Marty Oct 7 '17 at 15:12