5 oldest unsolved problems in Mathematics about primes.
Mathematics has been a subject which has challenged the greatest minds in human history for ages. Arguably, among the most researched areas in Mathematics is the study of prime numbers.
Our wondering about the prime’s patterns have laid down some of the most difficult problems, unsolved by, even the greatest of the mathematical prodigies ever. Today, we will look at 5 of the oldest problems about primes in Mathematics which are intuitive to understand for a high school student but are still unproven even after a hard and strong pursuit for 500–2000 years.
1. Perfect Numbers:
Does ‘odd’ perfect numbers exist? Are ‘even’ perfect numbers infinite?
Consider the numbers 6, 28, 496, 8128…..
What’s so special about these? If you don’t recognise, I would suggest to pause for a moment and try to look for a beautiful underlying property.
moving on …
If you look at the proper divisors of these numbers, you may notice that “beautiful” property.
6 = 1 + 2 + 3,
28 = 1 + 2 + 4 + 7 + 14,
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
The numbers for which the sum of its proper divisors equals the number itself are called perfect numbers. The earliest known study of perfect numbers is lost to prehistory. However, we know that the Pythagoreans (525 bce) had studied the perfect numbers.
What do we know about such numbers?
- Euclid proved that for a given n, if (2ⁿ−1) is a prime, then
x=2ⁿ⁻ ¹(2ⁿ−1) is a perfect number. Try this as an exercise.
Okay, one quick detour.
Mersenne Primes: Primes of the form x = 2ⁿ -1 for some n. Mersenne conjectured that all numbers of the form 2ⁿ -1 are prime when n is prime.
(We know that’s not true. e.g. 2¹¹ − 1 = 2047 = 23 × 89.)
Open Question: Are there infinitely many Mersenne Primes? We currently know 47 Mersenne primes.
- Euler in the 18th century showed the other way around that any even perfect prime is of the form 2ⁿ⁻ ¹(2ⁿ−1).
In other words, there is a one-to-one correspondence between even perfect numbers and Mersenne primes.
As you can see, we have known about even perfect numbers since Euclid(c. 300 bce) and the ways to produce them.What we don’t know is if there exists any odd perfect numbers!!! (actually, there has been little to no progress to show for this problem)
To summarise, the study of perfect numbers poses 2 long standing open problems namely “the existence of odd perfect numbers” and “the existence of infinitely many Mersenne Primes”.
2. Twin Prim Conjecture: There are infinitely many twin primes
A twin prime is a pair (p, p+2) such that both p and p+2 are primes.
The exact origin of twin primes conjecture is not confirmed and the first statement of the twin prime conjecture was given in 1846 by French mathematician Alphonse de Polignac. However, Greek mathematician Euclid gave the oldest known proof that there exist an infinite number of primes, and he conjectured that there are an infinite number of twin primes”.
Having existed for more than 2000 years, there has been little to no progress in terms of proving this statement.
What we do know!
- There are infinitely many prime-pairs of the form (p, p+k) where k ≤ 246.
- Assuming Elliott-Halberstam conjecture (which we strongly believe to be true), there are infinitely many prime-pairs of the form (p, p+k)
where k ≤ 6.
This means, the set of twin-primes (difference of 2), cousin-primes(difference of 4) and sexy-primes(difference of 6) is infinite.
Arguably, the greatest living mathematician, Terence Tao is actively working on this problem. Do checkout this video to get to know this mathematical prodigy and his work on twin primes.
3. Which all regular n-polygons are constructible?
A constructible polygon is a regular polygon that can be constructed with compass and straightedge. For example, a regular pentagon is constructible with compass and straightedge while a regular heptagon (n=7 sides) is not.
The ancient Greeks knew to construct a regular polygon with sides n = 3,4,5 and they also knew how to construct a regular polygon with double the number of sides of a given regular polygon.
So they could construct for n={6,12,24… 4,8,16... 5,10,20...} and so on.
The natural question to ask was, for what values on n can be construct.
The first real progress on this problem took nearly 2000 years, since the Greeks first studied it when a then 19 year old teenager constructed a regular 17-gon in 1796. That kid was none other than Carl Friedrich Gauss. Few years later, Gauss came up with an answer to the general problem.
What we do know!
Gauss showed that a regular n-gon can be constructed with compass and straightedge if and only if n is the product of a power of 2 and any number of distinct Fermat primes (including none).
A Fermat prime is a prime number of the form.
So, the problem of finding all constructible polygon reduces to finding all Fermat Primes. This is independently an open problem.
The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297……..
As of 2021, the only known Fermat primes are F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65537.
Fermat conjectured that all the Fermat numbers are primes. In 1732, Euler discovered 641 divides F5. Since, then we have proved that for n=5,6…31 Fermat numbers are composite. There is no known Fermat prime after F4.
We would have the answer to the set of all constructible n-gons the day we are able to find out the answers about the existence of Fermat primes.
4. Goldbach Conjecture. (1742)
Goldbach Strong Conjecture:
Every even number can be expressed as sum of 2 primes.
Goldbach Weak Conjecture:
Every odd number greater than 5 can be expressed as the sum of three primes.
This conjecture is called “weak” because if the strong conjecture is proven, then this would also be true. Unfortunately, after considerable efforts of generations of mathematicians since Euler, we have not been able to prove either.
(Note- In 2013, Harald Helfgott published a proof of Goldbach’s weak conjecture. As of 2018, the proof is widely accepted in the mathematics community, but it has not yet been published in a peer-reviewed journal.)
In any case, we are still waiting to resolve the strong version.
What we do know!
- In 1930, it was proved that any natural number greater than 1 can be written as the sum of not more than C prime numbers where C < 800000. [Note- we want C=2]
- In the last decade, it was shown that every even number n ≥ 4 is in fact the sum of at most 4primes (i.e. C ≤ 6). Later, the result was enhanced to C≤ 4.
Fun Fact — Goldbach’s conjecture is part of the plot of the 2007 Spanish film Fermat’s Room.
Disclaimer: The title of the article is misleading. After showing 4 unproven/unsolved results, I wanted to show one long lasting mathematical problem (the 5th problem) which has been recently solved (in 2004).
5. Primes Is In P (2004)
Say you are given a number n = 10089886811898868001.
You are asked, whether this number is prime or not. What you intuitively do is,
Algorithm A — check for every number 1 <k < n if k divides n.
You can optimise on this algorithm by realising that if n is not prime then n will have a factor k such that k≤ √n.
Algorithm B — So you only check for 1 <k ≤ √n.
Okay, wait! first of all, what is ‘P’ ?
A decision problem is said to be in ‘P’, if there exists an “fast” algorithm, which can solve the decision problem (return yes or no).
Here, the decision problem is, given n, is n a prime number ?
Now, what is a fast algorithm?
For any given decision problem, you will have an input size(let us call it x).
For our problem, the input size is the number of digits in the number n.
So, x=20 for the above n.
In general, for a given n, x=log(n)
An algorithm is called fast (a polynomial time algorithm) if it solves the decision problem in f(x) steps where f is a polynomial function.
If we look at our above algorithms to figure out if n is a prime, we get that we take n steps in Algo A and √n steps in Algo B.
Since our input size is log(n).
Let us call no. of steps by an algo for a given input size x as γ(x)
For algo A, γ(x) = n steps= e ˡᵒᵍ⁽ⁿ⁾ = eˣ steps
For algo B, γ(x) = √n steps = √eˣ steps = e^(0.5x) steps
These both are exponential time algorithms in x and for over 400 years mathematicians have tried to figure out if the decision problem of primes can be figured out in polynomial time. It turns out the answer is “Yes” and the news of the result spread like fire in the mathematical community (specially number theorists) in 2004 when it was announced by a professor and 2 of his students studying in IITK.
The algorithm (famously called AKS primality test) was published in the paper called “Primes Is In P” where it showed that this decision problem (whether n is prime or not, could be solved in ~log(n)¹² steps. A lot of improvements have been made not to reduce it to ~log(n)³ steps
(~ is like an approx sign in layman terms; refer to wiki if interested in details)
Fun Fact:
This problem was solved by 2 of my course’s professors from IITK, whose primary interest areas include Computational Number Theory.
The authors received the 2006 Gödel Prize and the 2006 Fulkerson Prize.
