Solving Mathematical Puzzles with Computers
Many mathematical problems arise from a need to describe something in the real world, like a physics problem. Others exist to find new ways to solve existing problem. Others still, however, exist solely for amusement, puzzles to satisfy the mathematician’s curiosity. One puzzle mathematicians like to think about has to do with the discrepancy of a sequence, or list, of numbers. An infinite sequence might look something like , nothing more than an ordered list of numbers. If you start going down the sequence, adding up the numbers as you go, you’ll get something like this:
As you add these numbers, with each subsequent term you get closer to or father away from zero. In this case, by the 5th term the farthest you’ve gone from 0 is 5. However, instead of adding each term in order, you could add together every other term, and see what you get then:
Here the farthest you get is 12. How about every third term?
Here you get to -3, which is 3 away from zero. If you keep following this pattern of adding each dth term and finding the farthest number you get from zero, the absolute farthest number you find is called the discrepancy of the sub-sequence, a number we’ll call . For this particular sequence, and the sub-sequence consisting of the first 8 terms (we’ll use the variable to denote the length of the sub-sequence), the discrepancy is 12, which is reached when d=2. Mathematically speaking, if the sub-sequence is described as , the discrepancy can be found by (note that the subscript i is being multiplied by the coefficient d). Again, though, this can be simply stated as the farthest the sum of every dth term ever gets from zero.
This is all find and dandy to calculate, but it’s not much of a puzzle, just a function to associate a number with a sequence. However, if mathematicians define certain rules and patterns for these sequences, interesting results can appear. One sort of sequence whose discrepancies are often studied are ones where each term is either +1 or -1, such as . With this rule, instead of defining a sequence and finding its discrepancy from there, you can choose a discrepancy that you want a sequence to have, and see how long of a sequence you can make with a discrepancy less than or equal to that chosen C. In 1932, the famed mathematician Paul Erdős conjectured that for some infinite sequence x of ±1 and some desired maximum discrepancy C, there exists a length k and a coefficient d such that the discrepancy of that sub-sequence will always be greater than C. In other words, there’s a finite limit to the length of a ±1 sequence such that the absolute value of the sum of every dth term remains less than or equal to C after each operation. The puzzle? To prove this conjecture, called the Erdős Discrepancy problem, holds for every positive integer value of C.
Solving the Puzzle
It’s pretty easy to show that this problem holds true for C = 1. To do so, let’s assume it’s possible to construct a sequence of length 12 that has a discrepancy of 1 and try to do so (it’s easy to see that it would be impossible to have a discrepancy of ).
Let’s start by making the first number in the sequence a 1, because it doesn’t matter if we start with 1 or -1 (if we started with -1, the end result would just be the opposite of what we’ll get with 1). Because the addition starts at 0, if the first two numbers are 1, we’d have a discrepancy of at least 2! Therefore, the second number has to be -1:
With the second number set to -1, consider if you added up every second number. You’d get -2 if the fourth number were -1, so the fourth number must actually be 1.
Let’s start filling it in a little faster. If you’re counting by fours, the eighth number has to be -1. And because the first two numbers add up to 0, and the fourth number is one, so to stay away from two, the third number has to be -1. Remember that it’s okay to have two +1’s in a row because the numbers that come before them add to -1. Then, if you’re counting by threes, the sixth number has to be 1, and if your counting by sixes, the twelfth number has to be -1:
Now we can see that the fifth number has to be -1, meaning the tenth is 1, and that the seventh number has to be 1.
Again, the numbers before the ninth add up to 0, so it has to be -1, and the same is true of the numbers before the eleventh, so it mst be 1.
And there! We’ve done it! Wasn’t that a fun puzzle? Now we have a sequence where, no matter what you count by, adding up subsequent terms gets you no more than one away from zero!
Or do we? It works if we add every term, or every other term, or every fourth or fifth or sixth term. But if you try added every third term, you end up with -2. How terrible! We must have made a mistake! But remember, we didn’t make any actual decisions in choosing these numbers, other than to start with 1; every decision was forced upon us. Despite this, we’ve been forced into a situation that contradicts our original assumption, that this is a sequence of length twelve with a discrepancy of 1. Therefore, we have to conclude that this assumption was false, and that it’s impossible to have a sequence of length 12 with a discrepancy of 1. However, if you remove the last number:
suddenly it works! Thus, 11 is the biggest length of a sequence of + and -1 with a discrepancy of 1, which means the Erdős discrepancy problem holds for C = 1.
Stepping up the game
While that was pretty easy to show by hand for C=1, a team of computer scientists from the University of Liverpool set out to find if this conjecture, holds for C = 2. To do this, they tackled the problem by converting it from traditional mathematical notation with sigmas and sets to a language more at home on a computer: a Boolean Satisfiability (or SAT) problem.
SAT problems deal with Boolean formulas, the bulding blocks of modern computer science and logic theory. Each element of a Boolean formula is either True or False, and these elements can interact with each other using operators such as AND, NOT and OR. For example:
True AND True = True or, represented mathematically,
True AND NOT False = True or,
True AND NOT True = False or,
Boolean Satisfiability Problems give you a Boolean formula with some of the values replaced with variables, and ask if it’s possible to give the variables values that cause the formula to return True. Many SAT problems are trivial to solve. For instance one such problem is “a AND NOT b” (represented mathematically as ). This formula returns True if a is True and b is False. Since these values of a and b exist, the original formula is classified as satisfiable. However, is unsatisfiable because no value of a would make that formula return True. While these examples are quite simple, Boolean satisfiability is actually considered an NP-complete problem, meaning that no efficient (polynomial time) algorithm is known, or by some, believed) to exist to solve it (however, if you’re given one possible answer, it is very easy from a computer science perspective to see if that answer is correct).
Nevertheless, programs have been developed that are able to solve many SAT problems, and while they are not fast, researchers continue to develop increasingly efficient algorithms. Using a very complicated process, the Liverpool researchers were able to convert the discrepancy problem for C = 2 into a SAT problem, one that ended up being several pages long if it were printed out. With this in hand, they were able to quite simply feed this input file into Plingeling, a publically available SAT solving algorithm running on a standard desktop PC. Then it was just a matter of waiting a little over 6 hours to find that the maximum value of k for this particular problem was 1160. Thus, they concluded, the Erdős discrepancy conjecture holds for C = 2. The team is continuing to evaluate the problem for C = 3, and while they have run the program for close to a month, they have yet to find a maximum k.
The Wikipedia Sized Proof
The controversy in this finding comes from the computer based method the team used to solve this problem. In mathematics, as in all fields of science, work must be peer reviewed to ensure its correctness. This is good, because SAT algorithms, though difficult to compute, are very quick and easy to verify, and the program the researchers used provided a file that could be easily checked to verify their results. Unfortunately, this verification file the SAT algorithm output turned out to be over 13 gigabytes in size, which the researchers proudly note is larger than the whole of Wikipedia. Thus, it is virtually impossible for a mathematician to manually verify these results by hand, and the only way it can be done is by writing yet another computer program. This is quite unexpected for such a simple problem written during a time when using machines to write mathematical proofs was almost unimaginable. Many see this as a paradigm shift in the world of mathematics as computer aided proofs become more and more commonplace, but like all areas where computers slowly replace humans, many are likely to not take this in stride.
Further Reading:
The Original Paper from the University of Liverpool
SAT Problems on Wikipedia
Another explanation of the problem, this time with a more traditional puzzle (YouTube link)
by Jacob Settlemyre