Numb3rs 106: Prime Suspect

Riemann Hypothesis and Millenium Problems

As was made obvious in the episode, the Riemann Hypothesis is one of the most famous conjectures in mathematics. It was originally stated in an 1859 paper written by Bernhard Riemann, and it involves the Riemann zeta-function defined as the infinite series:

It can be shown that this series converges if the real part of s (which is a complex number in general) is greater than 1. Then it is possible to analytically continue the zeta function so that it is defined for all s with real part not equal to 1. This definition of the zeta function is analytic on its domain of definition, which is the complex analysis version of being differentiable. This basically means that with this formula we can define the function for part of the complex plane, and then we can show that there is a way of extending this to almost all of the complex plane that agrees nicely with the original definition. The Riemann Hyopthesis is that all the zeros of the continued zeta function occur either when s is a negative even integer or when the real part of s is 1/2. It is important in mathematics because it has many deep connections to prime numbers and especially to the distribution of the prime numbers (how often they occur), and there are many interesting results which have been proved to be true assuming that the Riemann hypothesis is true. For more information about various connections between other parts of math, look up the Wikipedia page about it.

As was also mentioned in the episode, the Riemann hypothesis is one of the Millennium Prize Problems. These are 7 (actually, the number recently became 6) famous mathematical problems which come with a prize of one million dollars offered by the [[http://www.claymath.org/][ Clay Mathematics Institute]] for anyone who solves them. This institute was established by Landon T. Clay and is "dedicated to increasing and disseminating mathematical knowledge." Here is a list of the problems with short descriptions:

• P versus NP: This problem deals with how hard different problems are to solve on a computer based on the length of the input for the problem. (Here the particular problem is fixed and the length of its input is allowed to vary.) A problem S is in the set P if there is a polynomial p(x) and a computer algorithm which given an input for S of length n can solve the problem in time p(n). An example is the problem of sorting a list of n numbers, which can be done in polynomial time. A problem is an NP problem if given an input and a possible solution, the solution can be checked to see if is an actual solution in polynomial time (again the polynomial is a function of the length of the input). An example of this kind of problem is the zero sum subset problem - given a set of integers is there a subset of them that sum to zero. Clearly if a problem is in P it is also in NP. The major question is whether there is a problem that is in NP but is not in P.
• The Hodge Conjecture: This conjecture is even difficult to state since it involves some very technical definitions. A (very) vague statement is that certain algebraic invariants of algebraic/geometric objects called varieties come from geometric invarients.
• The Riemann Hypothesis: This was discussed above.
• Yang-Mills existence: This is discussed in Episode 103.
• Navier-Stokes existence and smoothness: The Navier-Stokes equations describe in full detail the motion of liquids. Even though they have been known for over a century, it is still not known whether there are smooth (i.e. differentiable infinitely many times) solutions to these equations.
• The Birch and Swinnerton-Dyer conjecture: This conjecture is similar to the Hodge conjecture in that it is difficult to state, but it roughly states that there is a relationship between the number of solutions to a particular type of equation and the order of the zero of the L-function at a particular point (L-functions are related to Riemann's zeta function.)
• The Poincare conjecture: This conjecture has actually been solved in 2006 and recieved fairly wide media coverage. The two-dimensional version of the the conjecture says that if you have a surface that is simply connected (that means that if you draw a loop on the surface, you can shrink it to a point by sliding the loop continuously along the surface) and closed (it doesn't go off to infinity, and can't be stretched so that it does), then it can be deformed into a sphere. The three dimensional version of this took many years to prove.

Encryption

One of the main plot points of the episode is that the bad guys wanted the math professor to give them his solution to the Riemann hypothesis so that they could crack the encryption on major financial data. As was mentioned in the episode, many encryption algorithms depend on the fact (or apparent fact) that it is very hard to factor large numbers. One of the main encryption algorithms used today is called the RSA algorithm (the name comes from the initials of its inventors. This algorithm is also described Episode 205. As mentioned there, the main difficulty in trying to break the RSA code is that factoring numbers into prime factors can be very difficult. In particular, there is no known algorithm that factors a number n into its prime factors that is in P, i.e. runs in polynomial time as a function of log(n) (here log is used because the number of bits it takes to store a number n is log base 2 of n). It is believed that no such algorithm exists. Interestingly, there is another kind of cryptosystem that is provably difficult in the sense that if an algorithm is devised to decrypt messages in polynomial time, then this algorithm can be adapted to factor integers in polynomial time.