Computational Number Theory in the Modern World

Hello and welcome to our talk, computational number theory in the modern world. My name is Luciana Tukasyan and I work here at Wolfram Research in the Discrete Computation group. So let's begin. First of all, what is number theory? Number theory is one of the oldest and most intuitive fields of mathematics. It studies integers and their properties. And here is a very famous quote by very famous mathematician Carl Friedrich Gauss, who said that mathematics is the queen of sciences and arithmetic is the queen of mathematics. Today we're going to talk about about number theory, number theoretic functions in the Wolfram language. And we group them into the following factoring in primes, divisibility and divisors, congruences and modular arithmetic, number representations DIOF19 and other equations, analytic number theory and algebraic number theory. The first group is factoring in primes. So the primes have been a focal point for investigations of numbers for more than two millennia. Is, I'm sure, the first thing that pops into your mind when you hear the word number theory or prime number. And here we grouped the functions into the categories generating primes, sequence of primes, and primality testing. So let's start with functions that generate primes. And here we have the function prime which gives the nth prime number. And we can use it to quickly find, for example, the millionth prime. Next prime gives the smallest prime above x. And we can use it to find the next prime after 1000 by simply doing this. Or we can visualize the gaps between primes below 1000 by running this simple line of code and you see the histogram of it. And by the way, next prime gives the smallest prime above x and next prime 1000 minus 1, because of this minus 1. This will give us the largest prime above x. So in this case we will get 997. The function Mersenne prime exponent gives the nth Mersenne prime exponent. So what is it? A Mersenne prime exponent is a prime number P for which the Mersenne prime the Mersenne number two to the power of p minus one is prime. And here are the first ten Mersenne prime exponents. Another function in this category is random prime. Now let's talk about the functions, about the sequence of primes. Here of course, the most important function is prime PI. And it the function prime PI gives us the number of primes PI x less than or equal to x. And by the way, this has nothing to do the mathematical constant PI. This is just how we denote it. This is a Very important function has very interesting qualities. But let's just now compute the number of primes up to 10 to the power of 10, which will give us this number. Now let's talk about the function zeta. The function zeta gives the Riemann zeta function, which is defined as this that you see on your screen. This is a complex valued function. It's a very important and interesting functions function. And we can of course, if we have a function, we want to plot it. So first let's plot it over a subset of the reals. We'll get this. And now let's plot it over a subset of the complexes and we get this very beautiful complex plot. The other functions here are z0 log integral and some other functions. Now, primality testing. So the first function here is the function prime Q, which is used to test whether an integer is prime or not. So for example, we can test whether 119 is prime or not by by just doing this and it says false, it is not prime. Similarly, composite Q is used to test whether an integer is a composite number. So for example, we can test whether 149 is composite or not by just doing this. And false, it is not a composite number. Now, Mersenne prime exponent Q Mersenne prime exponent Q is used to test whether an integer is a Mersenne prime exponent. For example, we can test whether five is a Mersenne prime exponent by doing this. And we can also check by this. So 2 to the power of 5 minus 1 is 31. And since theta 1 is a prime number, that makes 5amersenne prime exponent. Or we can highlight Mersenne prime exponents in this table. And Mersenne prime exponents here are highlighted in red for numbers up to 100. The next function is the function prime power Q, which is used to test whether a number is a power of a prime number. For example, we can use it to test whether 9 is a power of a prime number, which is of course true, because 9 is 3 squared. Or we can write this very simple function to recognize Mersenne numbers. Since Mersenne numbers have the form 2 to the power of P minus 1, that if we add 1, that would make them an even number and that would also. That should also be prime power. That should, because that is the power of the number two. And since now we have this function, we can, when we can easily see that this number is the Mersenne number, while this number is not. So another function in this category is the function co Prime Q. Okay, so we talked about the functions about primes, now let's talk about functions about factoring. And prime factorization is one of the most one of the key notions in number theory. It says that every natural number can be written uniquely as a product of primes. And here again we have two groups, factoring and factoring related functions. So let's start about the functions about factoring. And here, of course, the most important function is factor integer, which gives a list of the prime factors of an integer together with their exponents. For example, we can find the prime factors of 120 and their exponents by doing this. And we can check that indeed 2 to the power of 3 times 3 times 5 is 120. And this is the unique representation, or we can compute it for very large integers and see that indeed it is very quick and see that the factors are really, really large. So why are prime numbers called the building blocks of integers? Because every integer is a prime or a product of primes. And here in this interactive example, we see that the system randomly picks a number and gives us the numbers prime factorization. Now, let's talk about a function into integer exponent which gives the highest power of p that divides n. We can use it, for example, to find the number of trailing zeros by doing this. And we'll get four, of course. Or we can find the powers two in successive integers by running this line of code. And this is you can see the plot. Actually, another function in this category is the function squared for Q. Okay, now let's talk about functions that are related to factoring. For example, the prime omega functions prime U and prime omega are one of these functions. The prime omega functions count the number of prime factors of a natural number n. Prime U counts the number of distinct primes of n. So if N has the following prime factorization, that prime U would be equal to m. We can use it to compute prime u for 24 to get 2. And prime omega counts the total number of prime factors of N, taking into account now their multiplicity. So if N has the following prime number representation prime factorization, then the prime omega would be equal to k1 plus km, and the problem go for 24 would then be equal to to 24. As I said, these are connected to prime factor to prime factorization. And if we compute the factor integer for 24, we indeed we can check that, yes, prime omega would be 3 plus 14 and prime U would be 2, because it has two distinct prime factors. Now let's talk about the function W lambda, which gives us the new function lambda n, which is defined as this. If n has the following prime factorization, then lambda n is equal minus 1 to the power of k1 plus k m. So it only takes two values, minus 1 and 1. And here we can actually see the table for luvial lambda, and you can see that, yes, it has two values, minus one and one. For example, we can use it to compute the luvial function at 8 and we'll get minus 1. Or we can plot the luvial lambda sequence for the first 50 numbers and you just get values minus 1 and 1. So other functions here are Mobius Mu and Mango lambda. Okay, so we talked about factorization, we talked about prime numbers. Now let's talk about divisibility and divisors, which is again, divisibility is one of the key notions in number theory. Let's just quickly remind you what it is. So the number D divides the number N. If there exists an integer K such that n equals d times K, we call N a divisor of D and D is a multiple of N. So what are functions that we use here? Of course, divisible, which yields true if n is divisible by m and it yields false if it is not. So, for example, we can test to see whether the number 437 is divisible by 19 and it is. Indeed it is. We can check by doing this. And yes, we get 23. Or we can compute more. We can compute a more symbolic stuff and see that this expression is divisible by 15, where n is an odd integer. The number GCD gives the greatest common divisor of numbers, and the LCM gives the least common multiple of numbers. For example, we can find the GCD and LCM of 4 and 18 by doing this. So the GCD would be 2 and the LCM would be 36. Euler Phi. So Euler phi gives the Euler Todian function, which gives the number of positive integers up to some integer N that are relatively prime to N. For example, we can compute the Euler torture function of 10 by doing this. And we can see. We can. There's a very interesting result that says that for any prime number P and natural number R, this is what you get. And we can. In the Wolfram language, we can see that, yes, it is indeed true. And Wolfram language has some great capabilities in symbolic computation. Other functions include co prime Q, extended gcd, model inverse, and these functions that you see on your screen. Okay, now let's talk about. We talked about divisibility. Now let's talk about divisors. As I said, B is a divisor of A if there exists an integer case that A equals k times B. So what are functions here? Of course, the function divisors, which gives a list of the integers that divide n. For example, to find the divisors of 1729, we simply do this. And yes, we can check that indeed 1729 is divisible by all of them, because these are the divisors of a number or divisor sigma, which gives the divisor function sigma kn, which is the sum of the kth powers of the integer n. For example, the sum of divisors of 20 is just divisor sigma 120, I.e. 42, or the sum of squares of divisors of 20 is divisor sigma 220. We can compare the following plots. We can compare the number of divisors, the sum of divisors and the sum of square of divisors. Now I want to talk about the function divisor sum, which represents the sum of form E for all E for all I that divide N. For example, we can, and you see that yes, indeed, it is a summation of a function F for all the divisors of N. We can use it to find the sum of squares of divisors of 20 by simply doing this. Other functions in this category are dedekind theta, elliptic theta. Okay, now let's talk about congruences and modular arithmetics. So congruences are of great practical importance in both numpy and everyday life. And in fact you here see the clock, because modular arithmetic is also called a clock arithmetic. I mean, clock arithmetic is the modular is the arithmetic module at 12. And so this notion has been introduced by Gauss. What are the functions that are related to congruences and modular arithmetic? Of course, it's mod, which gives the remainder of division m by n. For example, we can compute 5 mod 3 by doing this and we get 2. Or we can plot the sequence with fixed modulus by simply doing this. Power mode is another function and it is known as modular exponentiation. And power mode gives A to the power of B mod M. For example, we can just compute 2 to the power of 10 mod 3 and we'll get 1. Modular Inverse gives the modular inverse of K modulo n. And we can compute the inverse of 3 modulo 5 by doing this and we'll get 2. Other functions are multiplicative order, primitive root, Chinese remainder, and the rest of the functions that you see on your screen. Okay, Tiofontin and other equations. A diofantine equation is a polynomial equation, usually two in two or more unknowns, such that only the integer solutions are sought or studied. It's very difficult to solve a tear of antenna equations. In fact, we can't solve a given geofunctine equations and so the functions here would be a bit different. First of all, as I said, we seek only integer solutions. So integers represents the domain of integers. We can check, for example, if the number 7 is an integer or not by doing this. Or we can use the function reduce to reduce expressions. Here we have these equations, these are the equations and we want to find the solutions in integers. And we just use the function reduce and say that x and Y should be integers. And yes, we get three and four. And by the way, as you already know, X squared plus Y squared is phi squared. The solutions here are called Pythagorean triples. And 3, 4, 5 is a Pythagorean triple, is a very famous, well known Pythagorean triple. Or we can use the function findinstance to find solutions of Geoff and equations. And here we have two different equations and we want to find the solutions X, Y and Z should be integers. And so for then is an instance of a solution is 0, 2213. So as I said, it's very difficult to solve the front end equations and we need to, if we want to study them, we need to narrow down the subject. The simplest geofentine equation are linear geofunctine equations. So a linear geofunctine equation in two variables is an equation of the form A times x plus B times Y equals C for apcr integers. And we want to find integer solutions X and Y. So what is it? A linear fountain equation is a line and the solutions are the integer points that are on the line. And here you can see on your screen that you can see here we have, this is our geofentine equation and we can just change A, B and C. And also we can zoom in and zoom out and you see that these red points, red dots here are in fact the integer or in fact the solutions of here, of this, of this T of 19 equation. So other functions that we use here that are useful are element rationals, reals, algebraic and primes. Okay, number representations. So so far we talked about natural numbers, but of course there are so many other kinds of numbers. And let's see how numbers are natural numbers and other numbers, how they are represented in how we can represent them. So digit representations. Okay, Integer digits gives a list of the decimal digits in the integer n. And integer digits NP gives a list of the base pay digits in the integer n. For example, we can find digits in base 10 and 2. We can find digits of this number and we can find the digits of this number in base 2 from digits constructs an integer from a list of decimal digits. For example, we can construct a number from its base 10 digits like like here, 5128. That gives us 5128. We can also use symbolic digits in base. This is the base and these are the digits. Base form prints with a number and expression given in base n. So a binary integer, what is the binary for 33. Here you go. And here is an interesting example. And you can actually see that expansions in different bases can be terminating or non terminating for the same number. Other functions here are number decomposed real digits, integer reverse integer part, integer name. Now let's talk about the functions in the group continued fractions and rational approximations. So a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on. The function continued fraction generates a list of the first n terms in the continued function representation of X. And from continued fraction reconstructs a number from a list of continued fraction terms. So in this case we can find the 20 terms in the continued fraction from PI by doing this. Or we can find, we can use it for a rational number. We can actually then use these to construct the number from by using the function from continued fraction convergence. That's a function which gives a list of convergence corresponding to the continued fraction terms. List. For example, here are the convergence for a rational number and you can actually see that the convergence tend to the number. So here the line is our number and here are the convergence and they tend to the number as you can see in this plot. Now let's talk about Newton's constant. So far we only talked about functions. This is the first constant that we're going to talk about today. Hinschin's constant is a mathematical constant which is approximately 2.68545 what it is. So for almost all real numbers, X terms AI of the continued fraction expansion of X have a finite geometric mean that is independent of the value of X known as Hinton's constant. And mathematically speaking this is what it says. And in this plot you can see that Hinsch's constant is the red line, right? And you can see that this value indeed almost for all numbers tends to the red line. And basically, actually almost all is a very is a mathematical term, but let's just not go there. So for example, PI to the power of PI that works for it. PI to the power of E again works for square root of two. Well, this is not correct for the square root of two. And that's why I would say for almost all numbers, other functions are rationalized. So quadratic irrational Q continued fraction K. Okay, number representations. So representations is a sum of powers. Here the functions are squares R, which gives the number of ways to represent the integer N as the sum of d squares. For example, number of ways to represent 45 the sum of 2 squares, I.e. 8 powers. Representations NKP gives the distinct representations of the integer N as the sum of k non negative pth power in pth integer powers. So we can find representations of 1729 as a sum of two cubes by doing this. Indeed we can check that, yes, these are. This is correct. That's how we can check it. Another function here is elliptic theta. Or we can find partitions of a number. So integer partitions gives a list of all possible ways to partition the integer N into smaller integers. For example, we can find all the partitions of 5. Here you go. Partitions P gives the number Pn of unrestricted partitions of the integer N, while partitions Q gives the number qn of partitions of the integer N into distinct parts. So partitions P for 20 is this one and partitions Q for 20 is 64. Okay, so analytic number theory, what it is Analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. And analytic number theory has two categories, has two subgroups, multiplicative number theory and additive number theory. So multiplicative number theory is a subfield of analytic number theory that deals with prime numbers and with factorization and divisors. The focus is usually on developing approximate formulas for counting these objects in various contexts. So zeta functions, you know, has a great number of functions, a great number of zeta functions implemented. So for example, Zeta 0 represents the case 0 of the Riemann zeta function on the critical line. And we can visualize, we can use that function and Visualize the first 10 zeros of the Riemann zeta function or dirty class series. So one of the functions here is diraclet transform, which gives the Diraclet transform of expression with respect to N. The diraclet transform for discrete function is given by this formula formula. And for example you can use. Here we get the ZAs and here we get the polylog. Another function is theoretically L. So arithmetic function. Let's talk about a bit about arithmetic functions. What is it? Number theory. An arithmetic function is any function whose domain is the positive integers and whose range is a subset of the complex numbers. One of the cases here, one of the functions here is Mobius mu, which gives the Mobius function mu N, which is defined as this. So if n is greater than 1, then and n has the following prime factorization, then the Mobius mu function equals this. So now it takes three values minus 1, 0 and 1. Here's the table of values for the numbers up to 10. Other arithmetic functions are divisors, divisor sigma, Euler phi. Let's go back to prime numbers again and let's talk about prime PI function again, because this is a very important function. As I said, this is very important mostly because mathematicians for centuries tried to find its estimates. And that is one of the reasons how that prompted development of analytic number theory. And you see that actually it has very interesting estimates. The log in the x over log x and the log interval are great estimates for this function. Other arithmetic functions are prime, U prime, omega, prime angle, Samda, no perfect numbers. Perfect what is it? Very, you know, peculiar group of numbers. Perfect number N gives the nth perfect number. And perfect number Q tests whether a number is perfect. So what? A perfect number is a positive integer that is equal to the sum of its positive divisors excluding the number itself. So 28 is a perfect number because it's the sum of its divisors minus that number itself is 28. Here are the first 10 perfect numbers and we can use the perfect number Q to check that yes, they are indeed perfect numbers. And here is actually the plot of the length of the first 47 even perfect numbers with log scaled values. And they see that. So they grow very rapidly and they are very rare. Other functions are prime or some exponent prime or sine exponent Q. So additive number theory. Additive number theory is the substitute of number theory concerning the study of subset of integers and their behavior under addition. So here the groups are integer partitions, B slab representations, representation in terms of powers, summation, related operations, arithmetic functions. Let's now go and talk about algebraic number theory, which is a branch of number theory that uses the techniques of abstract algebra to study the integers rational numbers and their generalizations. Now, the first group here is algebraic numbers and representation. So what is the algebraic number Is an algebraic number represented in a particular field. So, for example, we can represent an algebraic number and we can even do arithmetic to it. We can get a numerical approximation for it. Algebraic number fields. For example, one of the functions here is two number field which finds a common field or expresses numbers in a given field. Like this, we can express square root of 2 in the number field generating by this, by using function to number field. Let's go back to factorization. So Gaussian integers allows factorization over Gaussian integers. So we can factor 36 over Gaussian integers. And this is the factorization we can, if we skip this, if we just say factor integer 36, you know, we are in the field of natural numbers. We just get the prime factorization of 36. But if we add this, then we get it over Gaussian integers and some other functions. Here are the function extension, which is a field extension for number theoretic and polynomial operations. For example, we can factor a polynomial over this N. Or another function is root reduced which reduces an algebraic number to minimal root form like this. Another function is two radicals. Okay, so here are the. We very briefly talked about the functions and the Wolfram language, the capabilities in number theory. So what's next in our plans for number theory? Of course, it's functionality, adding new functions, improve what we have. We're now working on a course and a book about number theory that that's coming shortly. And of course the documentation. We always improve and improve our documentation. If you have any questions, you can write them down. We will gladly answer them. And yeah, thanks for listening.