Over time I encountered a lot of interesting mathematical open problems that caught my attention. At some level I tried to understand and/or solve (in vain) them, but they remained in my mind and I hope at some point of my life to see their solution.
The first two of these (Riemann Hypothesis and P vs NP problem) are in the Millennium Prize Problems set defined by Clay Mathematics Institute in 2000, and have a one million dollars reward each. The other 5 Millenium Prize problems, although interesting, have never captured my curiosity as they are in a very different field of study respect mine.
All the other problems listed in this post are still challenging and with mathematical implication but don’t have a reward on them (well, “eternal glory” apart).
Riemann Hypothesis
The Riemann Zeta function, denoted as ζ(s), is defined for complex numbers with a real part greater than 1 by the series:
\[ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} \]
The function can also be analytically continued to other parts of the complex plane, except for s=1, where it has a simple pole.
Bernhard Riemann in 1859 stated his homonym Hypothesis:
All non-trivial zeros of the Riemann Zeta function ζ(s) have a real part equal to 1/2.
That is, every non-trivial zero lies on the critical line Re(s)=1/2 in the complex plane.
The significance of the Riemann Hypothesis lies in its deep connections with the distribution of prime numbers. The hypothesis, if proven true, would imply a very precise understanding of how prime numbers are spread among the integers, which is central to many areas of mathematics and its applications, including cryptography and number theory.
The summatory can be rewritten with the Euler product formula:
\[ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \ \text{prime}} \left(1 – \frac{1}{p^s}\right)^{-1} \]
This identity holds for Re(s) >1 and effectively links the Zeta function directly to the primes, showing that ζ(s) can be understood as a reflection of the distribution of prime numbers.
So far billions of non trivial zeroes have been found and all are have real part 1/2.
Restricting to s real there are some interesting results:
- at s=2 the Zeta function evaluates to π2/6, famously solved by Euler and known as the Basel problem (this result was the one that makes me know this hypothesis)
- Other special values at even positive integers involve powers of π and Bernoulli numbers, like ζ(4)=π4/90.
- At negative even integers (-2, -4, -6 …), ζ(s) evaluates to zero, these are known as the trivial zeros of the Zeta function.
P vs NP problem
P (“Polynomial Time”) is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time. There are results showing that RAM model has the same computational power of Turing Machine, so we can consider the definition valid also in this model. We can simply think to P class has “problems solvable in polynomial time in a computer”.
NP (“Nondeterministic Polynomial Time”) is the class of problems that can be verified in polynomial time by a deterministic Turing machine, or solved in polynomial time by a non-deterministic Turing machine. In the relative post we didn’t treat it, but essentially a non-deterministic Turing machine at each state can try more steps.
For example we know that PRIMES is in P, where PRIMES is the problem of determining if a number is prime or composite, while so far we only know that FACTOR (the problem to factorize in prime factors a number) is in NP (given the factors in polynomial time we can check that they are the solution by multiplying them) but we don’t know if it is in P (so far we only know super-polynomial algorithms to factor numbers, like QS or GNFS).
From a practical point of view, P is what we can compute quickly (this is not completely correct, imagine a problem with complexity Ω(x1000)) while NP is what we can verify quickly. We currently don’t know if every problem that can be verified quickly can also be solved quickly, so if P ⊈ NP or P = NP.
NP-completeness
Note that while proving P ⊈ NP requires “just” a super-polynomial lower bound for time complexity of a NP problem, proving P = NP requires to prove for every existing problem in NP that it is solvable in polynomial time. The former is already a very difficult request, the latter even seems unattainable, but here comes in help NP-complete problems.
A NP-complete problem C is a NP problem so that every other problem in NP can be reduced to C in polynomial time, that is every NP problem can be transformed in an instance of C in polynomial time. Clearly if we solve C in polynomial time we also solve any other NP problem in polynomial time (first we convert the NP problem in C in polynomial time and them solve it always in polynomial time).
The first example of NP-complete problem was proposed by Cook, one of the fathers of RAM model, and is the boolean satisfiability problem (SAT). SAT involves determining the truth values for variables that satisfy a given Boolean function. Intuitively a boolean function has the expressiveness of an electric circuit (a computer), this is why it can represent every other NP problem.
If a NP-complete problem can be solved in polynomial time this would imply that also any NP problem has polynomial solution time and P = NP.
Goldbach conjecture
This problem states that:
Every even integer greater than 2 can be expressed as the sum of two prime numbers.
It was proposed to Euler by Christian Goldbach in 1742 in a letter. Euler taught it was true, but couldn’t prove it.
It has been verified up to 4*1018, but also in this case there is no general proof.
Collatz conjecture
Given an integer n, consider the following steps:
\[ f(n) = \begin{cases} \frac{n}{2} & \text{if } n \equiv 0 \pmod{2} \\ 3n + 1 & \text{if } n \equiv 1 \pmod{2} \end{cases} \]
The conjecture states that for every n the sequence reaches 1.
It was first proposed by Lothar Collatz in 1937 and despite it has been check up to 3*1020 it remain unsolved.
I propose you an inductive approach I tried on this conjecture, if you have checked all numbers up to 4n-1, then we can make considerations on the next 4 numbers:
- 4n: is divisible by 2, so the next term is 2n that we already know by hypothesis that it converge to 1.
- 4n+1 => 3(4n+1) +1 = 12n + 4 => 6n + 2 => 3n + 1, that we already know by hypothesis that it converge to 1.
- 4n+2 => 2n+1, that we already know by hypothesis that it converge to 1.
- 4n+3 => 3(4n+3)+1 => 12n+10 => 6n+5 => 3(6n+5)+1 = 18n+16 => 9n+8, since we don’t know is n is even or odd we must stop here and don’t know if it converge.
Similarly you can use 2n to have still finer results, for example using 28 only 19 branches are unknown, while the other 237 converge to 1 since they in the following steps go in a s<256n.
Mersenne Primes
We already talked about Mersenne Primes, let’s just recall the open questions:
- are there infinitely many Mersenne Primes?
- are there a formula to compute the n-th Mersenne Prime?
- now consider:
- s1= 22-1 = 3
- s2 = 2s1-1 = 23-1 = 7
- s3 = 2s2-1 = 27-1 = 127
- s4 = 2s3-1 = 2127-1 about 1.7 * 1038
- Is 2s4 – 1 prime? Is this the start of a sequence of prime numbers?
Odd Perfect Numbers
Jointly to Mersenne Prime we talked also about perfect numbers, numbers equal to the sum of their positive divisors, excluding them-self. We already know that the k-th even perfect number is related to k-th Mersenne Prime: let Mk = 2p-1 than the k-th perfect even number is ek = Mk * 2p-1.
Odd perfect numbers are still an open problem, we know some facts but we don’t yet really know neither if they exist. For example we know:
- N > 101500
- N is not divisible by 105
- N has at least 101 prime factors and at least 10 distinct prime factors
- a series of constraints on factors and exponents of factors, please check Wikipedia for them, they are a lot!
Several researchers think that the existence of a perfect odd number is very unlike, but a rigorous proof is still missing.
Twin Prime Conjecture
Twin primes are pairs of prime numbers that have a difference of two. The conjecture states that:
There are infinitely many twin primes.
The conjecture is still unproven but in 2013 Yitang Zhang made a breakthrough by proving that there are infinitely many pairs of primes that differ by no more than 70 million, then refined to 246.
The conjecture is believed to be true.
NC=P or NC⊈P
This is the little brother of P vs NP problem. The complexity class NC (Nick’s Class) is a subset of P defined as the set of problems that can be solved in poly-logarithmic time (in O(logk n) for some k) on a parallel computer using a polynomial number of processors. So it is the class of problems that can be solved “quickly” in a parallel machine (they have intrinsically a good parallelism level).
An open problem is to determine if NC = P or NC ⊈ P, that is “do all P problems parallelize well or are there problems intrinsically sequential?”. There is a P-completeness theory similar to NP-completeness theory, the solution of the problem would require to find a polynomial lower bound for a problem in P or solve in poly-logarithmic time a NP-complete problem.
Conclusions
These problems are mathematically beautiful and some of them would have a huge practical impact if solved (imagine if a polynomial solution for a NP-complete problem is found, or in parallel computing if a poly-logarithmic solution for a P-complete problem, any problem would be solvable quickly)
