The Next Great Discovery in Mathematics Could Be Yours: Crowdsourcing a Proof of Goldbach’s Conjecture

Goldbach_partitions_of_the_even_integers_from_4_to_50_rev4b

When we learn about unsolved problems, no matter the discipline, we are generally indoctrinated into the patterns of thought that haven’t been able to bring about a solution. In many cases, these patterns will eventually yield an answer. For instance, the periodic table turned out to be a good guide for thinking nebulium wasn’t a real element. But in other cases, the ideas of our predecessors can actually be a hindrance. To illustrate, if a community of doctors believed that bloodletting were a curative for fevers, the question, “How do we cure scarlet fever?” might be incorrectly narrowed to the question, “How many leeches are necessary for removing scarlet fever from the blood?” Experiments varying the number of leeches used would never produce the cure for scarlet fever, but it isn’t difficult to imagine an empirical experiment showing that 4 leeches are better for the patient’s health than 20. It’s even imaginable that one leech might be  “shown” to be more beneficial to the patient than none—perhaps the presence of one leech leads to patients’ performing better on whatever indicators of health the scientist has chosen for the experiment (e.g. the leech lessens the patient’s flushed appearance).

It isn’t always easy to shake off the old paradigm of thinking—the more we learn on a topic, the deeper we sometimes settle into its ruts. And while much superstition says 30 is over-the-hill for mathematicians (here’s a piece that challenges the stereotype), it’s possible that mathematicians settle into the status quo through exposure more than age. Even if you’ve never thought much about number theory, or especially if you’ve never thought much about number theory, and if you consider yourself to be a puzzle solver or a problem solver in everyday life, now is your chance to dive in and shake things up. So I’m here to give you some tools to do it. Enjoy!

A successful problem solver is someone who figures things out. That person could have a knack for solving problems, or she could have a drive to do it (or both). If solutions don’t come easily to you, don’t let this exclude you from the ranks of problem solvers in the world. Solutions to great problems have been found because their solvers just wouldn’t give up. But this is starting to sound like a motivational speech, so let’s get down to business. I want you to prove Goldbach’s as-yet unproven conjecture about even numbers. I am going to provide you with two examples of mathematical proof that are comprehensible in laymen’s terms, and then I’ll lay out the problem. When you figure it out, contact your nearest mathematician to secure bountiful rewards.

mutilated chessboard problem

Puzzle Walkthrough 1: The Mutilated Chessboard

Begin with an empty chessboard. A chessboard consists of 64 squares that alternate between light and dark, so that no light square is ever adjacent to another light square (and vice versa), arranged in 8 rows of 8 squares to create a large square. Now suppose you remove two diagonal corner squares from the board, leaving the remainder of the board intact. This entails removing either two light squares or two dark squares, and leaving 62 squares as they are. You end up with either 30 light squares and 32 dark squares or 30 dark squares and 32 light squares, depending on which two corners were removed. Suppose you also have 31 dominoes. Each domino is the size and shape of two adjacent squares on your chessboard. It is possible to place a domino on the board so that it completely covers two adjacent squares, and only covers those two adjacent squares. The question is, can you place your 31 dominoes in such a way that they completely cover every square on the board?

And here’s the proof that you can’t: Because no light square can be adjacent to another light square and no dark square can be adjacent to another dark square, we know that one domino cannot cover two light squares or two dark squares: every domino is capable of covering one square and one of its adjacent squares (or one light square and one dark square). 31 dominoes, then, can together cover 31 dark squares and 31 light squares. If our board has 62 squares covered, 31 of them must be light and 31 dark. But wait! We removed two like-colored squares, leaving 32 squares of one color and 30 squares of the other. We can therefore cover 30 pairs of squares with dominoes, but we’ll be left with two remaining non-adjacent squares. To cover these, we would have to mutilate a domino too, which isn’t an option. We therefore know that we cannot cover all the squares of our mutilated chessboard with 31 dominoes.[1]

Puzzle Walkthrough 2: Euclid’s Proof of the Infinitude of Primes

Starting with any prime number, assume we have found all the prime numbers. For our example, we’ll assume that 7 is the highest prime number, and we have found all the prime numbers through 7. We have 2, 3, 5, and 7 (note that 1 is not a prime number). The product of these primes will be divisible by each of them. 2 × 3 × 5 × 7 = 210. Now clearly we can divide 210 by any of these numbers and get an integer, because we multiplied by all of these numbers to begin with (in the same way, when we multiply 2 and 3 to get 6 we can divide 6 by 2 to get 3 or by 3 to get 2). But if we take the product of our primes and add 1 to it (so, [(2 × 3 × 5 × 7) + 1 = 211]), suddenly our number is not divisible by any of the primes we have.

This is easy to see with a bit of thought. If some number is divisible by 2 and we add 1 to the number, it will no longer be divisible by 2, because it will give us a remainder of 1. A new number divisible by 2 would be obtained by adding 2 to the original number. Consider 6 again. We know that 6 is the product of 2 and 3, so we know that 6 is divisible by 2. If we add 1 to 6, when we divide 6 by 2, we get a remainder of 1. If we add 2 to 6 to get 8, then we have another number divisible by 2. In the same way, by adding 1 to our product of primes, we create a number that is not divisible by any of them.

Every natural number is either prime or it is not prime: either we can divide it by some integer (other than 1 and itself) to obtain another integer, or we cannot. Likewise, [(2 × 3 × 5 × 7) + 1] is either prime or it is not. If it is prime, we have a new prime number. The number 211 does happen to be prime. But if it were not prime, it would have to be factorable into numbers that are prime. That is, if we divide a divisible number, we’ll reach a stopping place where the integers we end up with are themselves indivisible. For example, if we have the number 16, which is divisible by the prime number 2, and we divide it, we get 8. This is again divisible by 2, leaving us 4. If we divide 4 by 2, we get 2: thus 16 can be expressed in terms of prime constituents 2, 2, 2, and 2. We know that our product 211 isn’t divisible by 2, 3, 5, or 7. But supposing we didn’t know that it is prime, let’s consider what it would mean for it to be divisible. It would mean that dividing it, we would reach a stopping place of constituent primes. Because we know that these constituents can’t be 2, 3, 5, or 7, we also know they would have to be another number that is prime.

Thus the product of these primes + 1 gives us a new prime number either by being itself prime or by entailing a factor that is prime and not one of the primes we already considered. We can easily generalize this proof to all known primes: one plus the product of the set of all known prime numbers will yield a number that is either prime or divisible by some prime number that was not included in the set being multiplied. Euclid was a genius.

Euclid’s proof is a great illustration of how abstract reasoning can trump raw calculation. No matter how many new primes we discover, the fact that we have discovered more does not prove that more are discoverable,[2] just as the fact that the sun has risen perhaps more than a trillion times does not prove that it will rise tomorrow. It makes it very, very statistically likely, but it does not show us a necessary truth. Statistical probability can provide the likelihood that a certain series of numbers will contain a prime number, based on the size of the numbers in the sequence and the observation that the frequency of the appearance of primes tends to decrease as the size of the numbers in the sequence increases (Marcus du Sautoy gives good pop-explanations of this topic). But observing the distribution of primes among the numbers we know does not tell us whether the appearance of primes is always approaching zero without ever reaching it (asymptotically), or whether we can find a number large enough that all numbers larger than it will not be prime (will be divisible by some number other than themselves and 1). Proof tells us, and proof is easier.

The Goldbach Conjecture

Any even number except the number 2 can be expressed as the sum of two primes.[3]

This has been shown empirically for all even numbers from 4 to 4 x 1018, but it’s never been proven. Thus there is a nonzero possibility (no matter how miniscule) that we’ll get to, say, 4 x 1028 and find an even number for which Goldbach’s conjecture doesn’t hold.[4] Although we can say with some practical confidence that the conjecture is likely true for all even numbers, we can’t say it with certainty unless we find a reason that it must be the case. And if it is in fact true for all even numbers, there is certainly a reason.[5] Any of the even numbers in question will be expressible as the sum of a prime number and some other number, because any even number n will contain every prime number less than n. For instance, the number 11 can be expressed as 2 + 9, 3 + 8, 5 + 6, 7 + 4, and even 11 + 0, with the first number in each pair being prime. But why should it be that any even number contains two prime numbers which when added together produce that number? Yet the evidence we have suggests this is the case. 8 = 3 + 5, 10 = 5 + 5 or 7 + 3, and so on.

If it were possible to calculate all possible sums of every even integer greater than 2, then by doing this we could discover that Goldbach’s conjecture is true for all of these numbers (assuming it is true). This method would be sufficient to establish the truth of the conjecture, though it wouldn’t be very efficient. But, again, we can’t possibly take this route, because the numbers are infinite, so whatever we establish about the numbers we crunch cannot predict the behavior of the numbers we haven’t crunched, meaning in order to prove the conjecture we must find a way to demonstrate why it must be the case for any even number greater than 2 that it is the sum of two prime numbers.

“The source of the difficulty [in proving Goldbach’s conjecture] is that primes are defined in terms of multiplication, while the problem involves addition. Generally speaking, it is difficult to establish connections between the multiplicative and the additive properties of integers.”[6] This is not for lack of trying. The history of progress on the problem is not really our concern here (but here’s a link), because I want to focus on the unsullied perspective non-mathematicians might have to offer. Complex mathematics aside, if even numbers all share some property that allows them to be expressed as two primes—or perhaps if prime numbers are distributed such that if every prime number is added to every other prime number in pairs (excluding 2 from the group, as 2 + an odd prime would create an odd number) (e.g., 3 + 5, 3 + 7 … 3 +n, 5 + 5, 5 + 7 … 5 + n, and so on), the sums will include every even number—then looking at the numbers in just the right way could conceivably give any one of us non-mathematicians the key to unlocking Goldbach’s conjecture. While it seems natural for mathematicians to continue whittling away at the work that’s already done, the beauty of approaching the problem from the outside is that we have the potential to cut new paths in our initial approach to the problem (though obviously we could still end up retracing the old ones!).

Proving Goldbach’s conjecture could lead to useful knowledge about the distribution of primes. And knowledge about the distribution of primes has real-world applications. This might[7] be a very basic example: If an even number n can be expressed as the sum of two primes, either the primes are identical (e.g., the prime 5 doubled equals the even number 10) or one of the primes must be greater than half of n. If this is true for any even number, then no even number can exist inside a prime gap that extends beyond half of that number (e.g. the even number 30 must contain a prime that is greater than or equal to 15 and less than 30), meaning a prime gap immediately preceding any arbitrarily chosen even number could not be more than half that number. But even supposing proving the conjecture had no useful application at all, imagine how satisfying it would be to make waves in the mathematical world as an outsider.

We manipulate numbers every day just by negotiating reality, whether we put our pants on one leg at a time or two (or go naked). The ubiquity of numbers alone means none of us approaches number theory entirely without experience, and our lack of experience could be just the source of brilliance necessary to solve the problem. Why not try? After you prove the Goldbach conjecture, you can make some fast cash by solving the millennium problems, or solve the problems on this list (to achieve what I can only assume would be some sort of nirvana). Happy proving.


[1] I found this puzzle in Fermat’s Enigma (1997) by Simon Singh, but it originally appeared in Max Black’s Critical Thinking (1946).

[2] On a side note, “discoverability” of numbers is a fascinating topic in itself. It’s the source, I think, of gross misconception about the existence of numbers in nature. While, for example, three things would exist in the world prior to our conceptualization of them as the decimal number 3, and while they would share certain properties with 3, such as the inability to be evenly apportioned between 2 people while remaining whole, it would be a mistake to assume that any number in nature shares every property with its corresponding number in our base-ten axiomatic system of numbers. E.g., the easily observed resemblance between 3, 13, and 23 is a product of our choice to reset the ticker after 9. In a truly separate base system that didn’t borrow its symbols from the decimal system, it would become clear that entirely different patterns would emerge. Here’s an illustration of a base-6 system (with a zero equivalent) with symbols we don’t already associate with decimal: !, @, #, $, %, ^, @!, @@, @#, @$, @%, @^, #!, #@ (or, using decimal symbols, 0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 20, 21, where 10 represents what we call 7 objects in decimal, etc.). In the example system, we would see a resemblance between the units digits in @, @@, and #@, but these numbers, translated into decimal, would be 1, 7, and 13, which don’t share units digits.  Discovering new objects within an axiomatic system is distinguishable from discovering a tangible object that was “there” before we found it. The possibility of the axiomatic discovery was generated by the creation of the system. On the other hand, we could argue that discovering, for example, America, relied on axiomatic distinctions between things like land and water, and even that all discovery is premised on non-evident rational distinctions. It’s mind-bending.

[3] There are also weaker forms of Goldbach’s conjecture. See the Wikipedia page for details.

[4] As an aside, because the series of numbers is infinite, then the series of known numbers constitutes an infinitely small portion of all numbers, and I would imagine that this diminishes the statistical significance of the behavior of our limited set (when viewed through the lens of infinity). It could very well be that Goldbach’s conjecture only applies to this limited set of known numbers.

[5] I believe it is safe to say “certainly” here. If a set number of objects in a finite system behaved according to a pattern, it’s possible that their conformity to the pattern not be explained by a shared property of the objects. For example, if we observe that all the slides in a playground are red and only the slides are red, there need be no explanatory connection between being a slide and being red: perhaps in the case of one slide, red was the cheapest, and perhaps a second slide was added to attract hummingbirds. But if we can say truthfully that all slides in all possible playgrounds (i.e. an infinite system of slides) will be red (such that it is not possible to introduce a slide to a playground without the slide being red), yet not all slides outside of playgrounds are red (so that red is not an essential property of being a slide) then there must be something about being a slide in a playground that entails being red. There must be an answer to the question “Why is it not possible for a slide in a playground not to be red?” I am grateful to Peter Klein for helping me with some terminology issues in this section and note—where error remains, it is likely that I should have more strictly heeded his advice.

[6] Courant, Richard, Herbert Robbins, and revised by Ian Stewart. What is Mathematics? An Elementary Approach to Ideas and Methods,. Second ed. London: Oxford University Press, 1996.

[7] I say “might” because this is my own idea, and another way to prove this may already have been discovered.

Comments

  1. Your reasoning in [5] is flawed. In fact, Goedel proved that some true statements have “no reason” in the sense that they have no proof, so there’s no rigorous explanation to why they hold.

    • Cherie Braden says:

      While it is certainly possible that Goldbach’s conjecture will turn out to be a Gödel sentence, I would argue that there would still exist the sort of connection that I’m calling a reason. You are very right, though, that such a reason might not be demonstrable without additional axioms (and thus not demonstrable in the sense the article discusses). Though I never suggested that the theorem must be provable if it is true, perhaps I should have been more explicit. But the word is still out on Goldbach, and I doubt that it’s time to throw this problem into the Gödel waste bin yet. Interested readers can have a look here for more info on the incompleteness theorems.

      • Thank you for your answer, Cherie. Here’s a heuristic argument for why Goldbach’s conjecture might not have a proof. Consider instead of the primes another set of odd numbers S, chosen at random, but having the same density as the primes. Then it is easy to show that with fairly good probability every even number is a sum of two numbers in S. The idea is that perhaps the conjecture is true, but that it is “just a coincidence”. Of course, this argument should not deter anyone from trying to find a proof or a counterexample.

    • Cherie Braden says:

      After taking a peek at your CV, I am honored that you read and commented. The heuristic argument is an important point that I had not considered. Taking the random test set {9, 11, 13, 17, 19, 23, 25, 29, 35}, which mirrors the density of primes (beginning at 3), this does in fact generate similar results (limited by the limited scope of the particular set; obviously your S would be infinite). But doesn’t this also suggest the possibility that there’s something significant about the distribution of primes which leads to what Goldbach observed? Granted, this makes the task of determining that significance complex, but it does seem as if your heuristic argument narrows our concern to the distribution of primes rather than definitively reducing the conjecture to coincidence. Especially when we begin considering very large even numbers, the fact that the density of primes in the greater half of a number is significantly thinner than the density in the lesser half seems like it would decrease the statistical likelihood that two prime numbers from each half would coincidentally sum to the even number. But if this is an error in thinking, I’d appreciate a correction.

      • Thanks again, Cherie – I appreciate your response. I have two comments:
        – The heuristic argument says that there’s a good chance that _all_ even numbers will be sums of elements of S; all infinity of them! It is true that as we go to higher numbers the primes get thinner, but that is offset by the fact that we have more combinations of them to play with. The number of pairs of primes under n is much much larger than n, and indeed grows fast enough for the calculation to work.
        – You are right to say that my argument only applies if we think of the primes as just a random set with a given density. And in fact we know that they have many properties that are very different than what would be expected of a random set – for example, the recent result of Zhang that got a lot of attention. I don’t think that this argument says anything about the “chance” that there is a proof for the conjecture. The point is to give a feeling for how it may come about that something is true without having a proof.

        As a side note, it would be interesting to find a formal way of assigning a probability to the event that there is a proof for the Goldbach conjecture.

    • Cherie Braden says:

      Maybe the ratio of top-half to bottom-half density always stays the same, so the likelihood of finding the two primes that sum always stays the same?

  2. Sylvain JULIEN says:

    Maybe you could get interested in this: http://mathoverflow.net/questions/61842/about-goldbachs-conjecture. It’s not a proof of Goldbach’s conjecture, but it might lead to one some day.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: