Last week, I wrote the first part of a series on primes, discussing why mathematicians find them so fascinating and giving you some of the brilliant ideas that the ancient Greeks discovered. This week, we're looking more modern-day. I'm going to give you an idea of what has happened since the ancient Greeks, and then we'll talk about how mathematicians (and you!) can work together to find the biggest prime numbers. I'm giving you a fair warning that this article is a lot more technical than others that I've written, but I did my best to explain it as fully and completely as possible, and it should be meaningful for those that have the courage to tackle it.
We Can't Find Them?
Other than the incredibly exhaustive and time-consuming Sieve of Eratosthenes (see last week), there are not many easy methods to prove that a number is prime or to find the next prime.
The differences between the prime numbers (2,3,5,7,11,13,17,19,23...) are sporadic and random (here: 1,2,2,4,2,4,2,6...) and though they vaguely seem to be getting bigger, there is no way of predicting what the next difference will be.
Centuries of research has led to practically no progress here, leading mathematicians to change course. Instead of finding the next prime, mathematicians zoomed out, beginning to try to find the number of primes under a given number instead.
This would give us an idea not of exactly when the next prime will appear but how dense the sequence is as a whole, and it will still tell us a lot more about the mystery of the primes.
The Prime-Counting Function
Let's look at some examples of this.
From 1 to 100, there's 25 primes. I'll list them here if you're interested: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
From 1 to 1000, there's 168. From 1 to 10,000, there's 1229. From 1 to 100,000, there's 9592.
We're going to define a function here. Call π(x) the prime-counting function. This has absolutely nothing to do with pi and circles. Pi is simply the Greek letter used to represent the function, like the standard f(x) or g(x).
Therefore, π(100) = 25, π(1000) = 168, π(10,000) = 1229, and π(100,000) = 9592.
With that bit of definitions out of the way, let me show you some of the most groundbreaking math of recent years.
The Prime Number Theorem
If we take the percentage of the numbers from 1 to 100 that are primes (or more concretely, π(100)/100), we get 25%. Continuing this on the other intervals, we get 16.8%, 12.29% and 9.592% for 1000, 10,000 and 100,000.
It is clear that the primes seem to get rarer as we move to higher and higher numbers... but how rare are they?
The question now becomes: How can we calculate the number of primes from one to any number x, or at least approximate that number?
In 1793, the then-16-year-old prodigy Carl Friedrich Gauss was able to develop a guess for a function that very closely approximates π(x), giving mathematicians a way to estimate the number of primes within each interval without calculating it exhaustively through computer programs in a sieve-like method.
For those that are interested, the function he chose was x/ln x, which you'll recognize if you know logarithms. He even went beyond that to an even more precise function called the logarithmic integral. If you don't know logarithms or calculus, don't worry! It's not important to the storyline here.
However, Gauss was not able to fully show that his guess was true. It took until the mid-1800s when another brilliant mathematician Bernhard Riemann entered the scene and was able to create a new set of tools to tackle these kinds of problems. He actually only ever wrote one paper on the subject and it was only 10 pages, yet he revolutionized the study of prime numbers more than anyone else up until today.
Using Riemann's tools, two mathematicians, Charles Jean de la Vallee-Poussin (from Belgium) and Jacques Hadamard (from France), were able to prove the Prime Number Theorem independently the same year, making it officially true that the difference between π(x) and Gauss's function gets smaller and smaller as we get to higher and higher values of x. That means that by the time we approximate huge numbers, the actual number of primes will be virtually indistinguishable from the value we can more easily calculate by Gauss's function.
Why Does This Matter?
At this point, you might be thinking that everything I've shown you is quite abstract and irrelevant. After all, who cares about the number of primes in a given interval anyway?
I could sit here and regale you with all sorts of stories about how an important field of math—number theory—depends entirely on prime numbers and any breakthroughs on them are vital to everything we know about math and the universe as the whole, but I don't think those would make quite the impact I'm hoping for.
So let me say this. Our computers today rely on prime numbers. When our messages travel from computer to computer in code, they're often encrypted with absurdly large prime numbers. To simplify it a lot, the computer will encrypt the message by multiplying the large prime numbers together to form an even larger number, and the receiving computer will decrypt it because it knows the key: the two primes that were used to encrypt it. Any computer that might intercept the message can't decode it because since we know so little about primes at this stage, it's practically impossible to factorize a huge number and find the two primes that were used to make it. (If you want to know more, look up the RSA algorithm!)
What the Prime Number Theorem does is take us one step closer to knowing exactly where the primes will land. Knowing more about primes will give us more insight into how our computers work, and lots of other fields too—maybe even biology (think cicadas!)—will be impacted by the new knowledge about primes. We might end up breaking how our current computing system works in the process, but we'll figure out so much that will advance technology and knowledge in general in the long-run. Primes are so fundamental that any advancements affect practically everything in a domino effect.
The Million-Dollar Problem
You've heard me mention a million dollars once or twice, and here's where I finally get to talk about it.
The Prime Number Theorem was a groundbreaking discovery, but it only takes us so far. It shows us that π(x) gets closer and closer to Gauss's function, giving us an approximate value, but it doesn't give us an exact one for the number of primes in a given interval.
Remember Bernhard Riemann? When he developed the tools he created to deal with primes (strangely enough, it involves infinity and fractions!), he also came up with a hypothesis himself. This statement, when interpreted from the proper angle, would actually give us an error term between Gauss's function and π(x), or to put it a lot more simply, it would give us a way to determine by what amount we're off, correct for it, and let us calculate π(x) exactly!
An exact value for π(x) means that we would know exactly how many primes there are from 1 to x, which means that we will know exactly where the primes are! If π(x) = 1000, for example, and π(x+1) = 1001, we know that x+1 is a prime because it's the only number we added and our prime total went up by one! This gives us one of the first innovations on finding primes since two millennia ago, at the Sieve of Eratosthenes.
Proving the Riemann Hypothesis is a million-dollar problem. It's one of the seven Clay Institute Millenium Problems, and whoever solves it gets the prize, as well as recognition for years and years to come. It's a fascinating problem with so many layers (I've actually been looking at it for a research project this year) and I'm hopefully going to write an article explaining as much of it as I possibly can (it's so abstract so it's going to be a challenge) at some point later this semester, so stay tuned for that!
Lots of recent developments in math all throughout the 1900s and up to today have focused on the Riemann Hypothesis and related problems. It's become a cornerstone of its field, so much so that it's often called "the crown jewel of number theory."
To bring this back to cryptography and computers for a second, in 1997, the Princeton mathematician Enrico Bombieri released an April Fool's joke saying that the Riemann Hypothesis had been solved, and the convinced and very worried NSA (the US National Security Agency) sent agents down to Princeton to figure out just what this would do to national security! Primes and code have quite a lot to do with each other.
Some Other Open Problems About Primes
In addition to the Riemann Hypothesis, another open-ended problem in math right now is the Twin Prime Conjecture. Twin primes are any two primes that are two apart like 3 and 5, 5 and 7, and 11 and 13. Mathematicians believe that there is an infinite number of twin primes but nobody can prove it.
There's also the Goldbach Conjecture, which states that any even number can be written as the sum of two primes. Mathematicians have actually shown that the weak Goldbach Conjecture (any odd number can be written as the sum of three primes) follows from the Riemann Hypothesis (meaning it would be automatically proven as soon as the Riemann Hypothesis is), but we've made little direct progress on the original Goldbach Conjecture.
You can find a whole list of more prime-related conjectures (that is, educated guesses that we can't prove) here.
All in all, there's a lot more we don't know about primes than we do!
The Search for Primes
I've taken you down a long and pretty technical route through the more recent discoveries of prime numbers, so let's jump back into something a little easier to grasp.
Do you know how I said mathematicians have mainly been focusing on looking at prime numbers larger-picture? You know, zooming out and looking at the number of primes like we did with π(x)?
Well, there's actually some people that have steered clear of the more abstract route, and they've been looking for specific primes. It's a bit of a competition in the math world right now to find the largest number that we can ever prove to be prime. Right now, the winner is 2^82,589,933 − 1, found in 2018 by Patrick Laroche. It has 24,862,048 digits, and we know for a fact that it's prime.
So how did we do that? First, let me backtrack just a little bit.
The Mersenne Prime
Marin Mersenne was a French mathematician with lots of interests, including music theory, acoustics and philosophy, and his most major contribution to the math world was the type of prime number that bears his name.
The Mersenne prime is a prime number in the form 2^n - 1. Not every value of n gives a prime number, as you can see below, but numbers of this form are more likely to be prime:
In fact, n itself has to be prime. (See if you can explain why! Think about differences of squares, cubes and so on.)
In addition to their role in discovering primes, Mersenne primes also have a very important role in perfect numbers, a property that I'd love to explain in an article one day. For now, I'll send you over to Numberphile.
The Great Internet Mersenne Prime Search
Knowing that Mersenne numbers are more likely to be prime, mathematicians, math amateurs, computer programmers and all sorts of math enthusiasts decided to put all their heads together and begin to search for Mersenne primes.
The end result was The Great Internet Mersenne Prime Search or GIMPS. It's a giant collaborative project that anyone (including you) can download the software for. You keep the program running in the background on available space on your computer, and who knows, your computer might just discover the next big prime number! Patrick Laroche was no more than a member of GIMPS, and he stumbled upon the largest prime number to date.
It uses a couple of algorithms (a little more sophisticated than the Eratosthene's Sieve but still time-consuming) to test the primes, and it's been in existence since 1996 in which time it has found 17 large primes.
If you'd like to download GIMPS or find more about it for a chance at mathematical fame and a cash prize that comes along with it, you can find it here at mersenne.org.
Conclusion
This concludes my two-part series on primes! Today's article was a little more abstract, as I wanted to give you a taste of what more recent research math actually looks like, but I hope you learned a lot about what goes on with prime numbers! If you have any questions, feel free to leave them in the comments below, and stay tuned for a third part if/when my Riemann Hypothesis article comes out!
Update: the Riemann Hypothesis article is out: https://www.gleammath.com/post/the-riemann-hypothesis
Learn More
Here's two videos on GIMPS (back when 2^74,207,281 - 1 was the largest prime number):
And here's two on the Prime Number Theorem:
Here's one on how prime numbers are used in computing/cryptography:
I'll also cite the same article I used last time because it helped me out a lot in this one as well: https://kids.frontiersin.org/article/10.3389/frym.2018.00040
Thanks and have a great week!
Cover Image Courtesy of NPR
Comments