Archives For June 2013

Would you accept US$1,000,000 to solve a maths problem? Apparently, not everyone would say yes. A new prize of this amount was recently announced, in an attempt to prove Beal’s Conjecture. Originally offered with a prize of US$5,000 in 1997, Beal’s conjecture remains unsolved. Today, the Beal Prize has been increased to one million dollars, according to an announcement from the American Mathematical Society.

But what is Beal’s Conjecture? Let’s instead start with something more well known, Fermat’s Last Theorem. Pythagoras originally proposed a formula for the right-angle triangle, where a^2 + b^2 = c^2. This equation has an infinite number of natural number, or positive integer, solutions. However, Fermat claimed that any system with integer exponents greater than 2 (as in Pythagoras’ Theorem) has no integer solutions in a, b, and c. Fermat was kind enough to solve his conjecture for an integer exponent of 4, but he left the rest unsolved. In 1995, Sir Andrew Wiles released a (then-flawed) solution to Fermat’s Conjecture, which included over 100 pages of work over the course of seven years. His story, and the story of the theorem, is a fantastic one, and I recommend reading more on it.

In 1993, two years prior to the solution of Fermat’s Conjecture and five years into Wiles’ quarantine, Andrew Beal proposed another conjecture. It is an extension of the aforementioned theorem. He claimed that the system a^x + b^y = c^z with a, b, c, x, y, and z being positive integers may only have an integer solution for x, y, z > 2 if a, b, and c have a common factor. As mentioned above, he promised US$5,000 to one who could provide a proof or counterexample of his conjecture. Put less abstractly, if we say that a=7, b=7, x=6, and y=7, then we have 7^6 + 7^7 = 941,192. Solving this, we have 7^6 + 7^7 = 98^3 = 941,192. Note that x, y, and z are all integers greater than 2. Thus, Beal would claim that a, b, and c must have a common factor. In this case they do, considering that 98 is divisible by 7 (or 98/7 = 14). There are many (possibly infinite) examples like this, but we still need a proof or counterexample of the conjecture. To date, it remains unsolved, and a solution will be reward with one million dollars.

In addition to the Beal Prize, the Clay Mathematics Institute offers US$1,000,000 for a solution to any of seven listed problems. As of this post, only one has been solved, and no money has yet been accepted. These Millennium Prize Problems continue to baffle mathematicians. It is fascinating to consider that there are so many open problems in mathematics, including those integral to number theory, such as Hilbert’s eighth problem.

Not everyone reading this post is a mathematician. Many of us, including myself, think visually. We like pictures, and we like problems we can solve, or at least ones that currently have solutions. So I’ll introduce one! I’m going to turn this post now to a classic problem that began to lay the foundations for graph theory and topologyFor a related post in topology, I recommend my post, Diving through Dimensions. Some of you may be aware of this problem, and I hope I do it justice. Let us begin by traveling to the capital of Prussia, Königsberg. The city (now Kaliningrad) was set on opposite sides of the Pregel River. On this river sat two islands. Thus, we have four land masses. Connecting these regions were seven bridges, as laid out below in red:


The people of Königsberg posed a question: Is it possible to traverse the city, crossing all bridges once and only once? Let us assume that one cannot dig under the ground, fly through the sky, cross the water by river, or use teleportation technology. One may only access each land mass by crossing bridges. Additionally, one may begin and end at any point. The only requirement is that each bridge must be crossed and that it cannot be crossed more than once.

Leonhard Euler proposed a solution to this problem in 1735. He began by first reducing each land mass to a point. The only relevant information is found in the bridges and where they connect, with the areas of land masses being irrelevant. This combination of nodes (points) and edges (lines) is commonly used in graph theory. Euler noticed that when when reaches a node by one bridge, one must leave that node by another bridge, resulting in an even number of bridges during a full pass-through over a node. Thus, all nodes that are passed over (that is, they are not the beginning nor the end) must have an even number of edges. There may be at most two nodes with an odd number of edges, and these nodes must serve as the beginning and/or the end of our journey.

Now, take a look at our bridges as Euler may have drawn them:


In this case, we see that the top and bottom nodes on the left each have three bridges, the rightmost node has three bridges, and the middle node on the left has five bridges. In other words, all four nodes have an odd number of edges. This violates our requirement that no more than two nodes may have an odd number of edges. As a result, Euler demonstrated that there is no way to traverse each of the Prussian bridges once and only once. This requirement can be applied to any drawing similar to the one above. I recommend trying it out and testing Euler’s proposal. It is quite rewarding.

If you are really interested, take a gander at the current layout on Google Maps:

Screen Shot 2013-06-04 at 3.53.02 PM

It seems that the people of Kaliningrad demolished two of our bridges! The Königsberg bridge problem now has a solution. A part of me likes to think that the bridges were demolished for no other reason than to provide a solution!

As mentioned above, Euler’s solution laid the framework for what we call graph theory. Graph theory, or the study of graphs like the one shown above, has myriad applications. It is used in computer science to model networking. Linguists take advantage of graphs to examine semantic structure. Chemists represent atoms and bonds using graphs. Social network analysis is described in the same terminology, using the same theory, where each person or group may be a node. In biology, we use it to model migration or the spread of disease. More relevant to my work, weighted graphs are used in network analysis, and computational neuroscientists may recognize graphs like the one above when modeling neural networks.

What we thus see is something fantastic. Abstract open problems like the one Euler solved and those proposed by Beal and the Clay Mathematics Institute provide foundational tools that can (and often do) advance our knowledge in numerous fields. Euler’s work propelled us into graph theory. A solution to the Navier-Stokes open problem will advance our understanding of fluid flow. Even if the abstract does not become practical, the journey is delightful.