In mathematics, there are many times where you explore an apparently simple idea, and you find unexpected beauty.
Numberphile has recently been posting about tests for prime numbers, also referred to as primality tests, and their latest one fascinated me because of the amazing patterns involved.
Their first video on this topic was about Fermat's primality test, and the fascinating concept of liar numbers. However, I'm going to discuss their more recent video on the AKS primality test, named for the last initials of the authors, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena:
Let's examine this formula a bit closer, with the help of Wolfram|Alpha. The command used to find the expanded form of an equation is simply the command Expand[]. So, if we wanted to find out the expanded form of (x-1)3, we simply enter it as Expand[(x-1)3], and just like in the video, we get the result x3 - 3x2 + 3x - 1.
As in the video, if we subtract x3 - 1, we're left with - 3x2 + 3x, and both coefficients are divisible by the original power, 3, so we know we've got a prime.
Let's try that with the power 4, resulting - 4x3 + 6x2 - 4x + 2. While 4 is obviously evenly divisible by 4, the numbers 6 and 2 are quite obviously not, so 4 isn't prime.
Note that the powers of x don't really matter much, so perhaps it would be nicer to just look at this problem without all the variables and powers getting in the way. Since the AKS test starts with the simple form of (x - 1)p, all the resulting coefficients (the numbers multiplied by the variables and their powers) are simply what are known as binomial coefficients.
Don't worry, binomials are easy to understand when taught properly. They're basically the number of ways k things can be combined of n possibilities without regard to the exact order. BetterExplained.com's post on permutations and combinations makes this clear. What you really want to focus on in that post in the part about combinations, as they are also known as binomials.
Wolfram|Alpha uses the command Binomial[n, k] to work out these combinations, also read as n choose k. For example, entering Binomial[8, 3] gives us 56, telling us that there are 56 ways 3 items can be combined from among 8 possibilities. The Mind Your Decisions blog's fresh fruit puzzle explains how binomials are used in probability.
Now, if we want to see just the coefficients of the cube of (x - 1), we can combine the Binomial[] command with the Table[] command in Wolfram|Alpha to read Table[Binomial[3, k], {k, 0, 3}]. This command is telling Wolfram|Alpha to work out the possible combinations of 0 objects from among 3, then the combinations of 1 object from among 3, then the combinations of 2 objects from among 3, and finally the combinations of 3 objects from among 3, and to put all that information in 1 horizontal table. The result is {1, 3, 3, 1}, which are the same numbers from the calculation above, but without all those messy variables and powers to spoil the view!
Just for fun, let's throw in the Column[] command, and go through the same process for all the numbers from 0 to 10, by entering the command Column[Table[Binomial[n, k], {n, 0, 10}, {k, 0, n}]]. Does that pattern of binomials look familiar?
. {1}
{1, 1}
{1, 2, 1}
{1, 3, 3, 1}
{1, 4, 6, 4, 1}
{1, 5, 10, 10, 5, 1}
{1, 6, 15, 20, 15, 6, 1}
{1, 7, 21, 35, 35, 21, 7, 1}
{1, 8, 28, 56, 70, 56, 28, 8, 1}
{1, 9, 36, 84, 126, 126, 84, 36, 9, 1}
{1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1}If it looks familiar, it's because you probably know it as Pascal's Triangle! I've talked about it before, most often in my annual 12 Days of Christmas post, but also in my Happy 10/11/12! post. I think it's interesting that a test for primes has lead us to Pascal's Triangle!You might note that all the binomials in Pascal's Triangle are positive, while the multiplication of (x - 1) to various powers gives us alternating positive and negative signs. This is easily remedied, by multiplying every other number in the command above by -1. However, the signs really don't matter in the AKS test, as -35 is just as evenly divisible by 7 as +35, so I'm going to ignore the signs from here on out.
Another thing to notice about the binomials in Pascal's Triangle is that the entire pattern has left/right symmetry. For example, the binomials in the 8th row, representing the coefficients for (x - 1)8, are {1, 8, 28, 56, 70, 56, 28, 8, 1}. The first 5 a different, {1, 8, 28, 56, 70}, but then they start going back down from 70 in the same way they built up. By taking advantage of Wolfram|Alpha's Floor[] command, and only going halfway across each table, we can shorten the list of coefficients we need to examine by half!
Also, remember in the text that for any power p, xp is subtracted, which effectively removes the first coefficient from the list. So, by starting at the 1st coefficient instead of the 0th, we can trim the list even more. Not surprisingly, this eliminates the tables for the power of 0 and 1, so we'll just start the list with coefficients of the power of 2.
At this point, we can look at just the coefficients for any power, without getting the numerous variables and powers in the way, and we've minimized the numbers we need to examine at each step. It's time to run through the AKS primality test again. For each of the numbers 1 through 10, it's not hard to see whether the coefficients are divisible by those numbers, because we're so familiar with them. What about numbers on a larger scale?
Let's turn our Pascal's Triangle generator into a generator for a single power, so we can run tests on individual numbers. We remove the Column[] command, and set n to an individual number. I'm going to use 71 for the first test, since James Grime uses that example at about the 2:20 mark in the video above. The result is this horrendous-looking set: {71, 2485, 57155, 971635, 13019909, 143218999, 1329890705, 10639125640, 74473879480, 461738052776, 2560547383576, 12802736917880, 58104729088840, 240719591939480, 914734449370024, 3201570572795084, 10358022441395860, 31074067324187580, 86680293062207460, 225368761961739396, 547324136192795676, 1243918491347262900, 2650087220696342700, 5300174441392685400, 9964327949818248552, 17629195603524593592, 29381992672540989320, 46171702771135840360, 68461490315822108120, 95846086442150951368, 126764178842844806648, 158455223553556008310, 187265264199657100730, 209296471752557936110, 221256270138418389602} *PHEW!*
Since few of us are familiar with our multiples of 71, you can't easily tell whether all these numbers are evenly divisible by 71. If you could verify that, then this test and our refinements via Pascal's Triangle will verify that 71 is a prime number. If all these numbers were evenly divisible by 71, then there would be no remainder. We can take advantage of this by using modular arithmetic!
If we simply take each of the above numbers, and apply mod 71 to them, we get a far simpler result: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} Every number is clearly divisible by 71, so 71 is prime!
Using the AKS primality test this way, you can set n to any number, and instantly tell whether than number is prime. Do you see any numbers other than 0? Then it's not a prime number. Is the number 391 prime? If you set n to 391 in this test, you'll see plenty of numbers that aren't 0, so you know 391 isn't prime.
If nothing else, I hope you get an idea of where exploring one idea in math can lead you to some surprising places. Sometimes, it's just fun to explore!
Posts
1 Response to AKS Meets Pascal
Unfortunately, the test they describe isn't AKS, and it most certainly isn't fast. It's a well known theorem that the AKS authors start with to derive the actual AKS algorithm. Worse, even when you use the actual AKS algorithm (with Lenstra and Bernstein improvements) it is still very, very slow.
I wish I knew why they did the video the way they did, as it is quite misleading.
Post a Comment