The abc Conjecture: Applications and Significance

This is the third part of a three-part post concerning the abc conjecture. For the first, see here.

The first post in this series presented some explanation as to why the abc conjecture seems like a reasonable attempt to mathematically codify a big idea. This idea is that the prime factorization of a sum of two numbers should not really relate to those of the individual numbers. Equivalently, it says that if we see an equation like 3 + 5³ = 2⁷, we should think of it as a "rare event" or "coincidence" that big powers of small primes are related in this way. The second post provided some examples and numerical evidence rigorous version of the conjecture. To review, this states that

The abc Conjecture: For any ε > 0, no matter how small, for all but finitely many equations of the form a + b = c where a and b are relatively prime, rad(abc)^{1 + ε} > c.

Again, the radical rad(n) of an integer n is the product of its distinct prime factors. However, none of what has been discussed so far constitutes a mathematical proof that the abc conjecture is true or false.

In 2012, the Japanese mathematician Shinichi Mochizuki shocked the mathematical community by publishing, out of the blue, what he claimed was a proof of the abc conjecture. However, the initial excitement at this announcement was quickly replaced by confusion; almost no one was able to decipher the tools used in the proof, which totaled over 500 pages in length! Mochizuki, working in isolation for years, had built up a brand new mathematical formalism which he called "Inter-Universal Teichmüller Theory" that was bizarre and unfamiliar to other researchers. The language and notation (an sample of which is provided in the screenshot below) seemed alien, even to mathematicians!

Moreover, he refused to publicly lecture on the new material, instead only working with a few close colleagues. The combination of the length and inscrutability of the proof with his unwillingness to elucidate it discouraged people from attempting to understand it. In the years since the proof was published, skepticism has mounted concerning the proof's validity. While a small group of mathematicians defend it, a majority of the mathematical community thinks it is unlikely that the proof is valid. For now, the abc conjecture remains effectively open.

Nevertheless, it is certain that attempts to prove the conjecture will continue. It has a number of useful applications that would solve a myriad of other mathematical problems, should it be true. To illustrate the power of the abc conjecture, we give one famous example of an application: Fermat's Last Theorem.

One of the first equations we considered in this series was x² + y² = z², which relates the side lengths of right triangles. This equation has infinitely many solutions, namely 3² + 4² = 5², 5² + 12² = 13², etc. Fermat's Last Theorem states that if we raise the exponents from 2 to any higher power, there are no solutions in the positive integers. That is, x³ + y³ = z³, x⁴ + y⁴ = z⁴, and so on are not satisfied by any x, y, and z > 0. Famously claimed by Pierre de Fermat in the 17th century, this problem remained unsolved for centuries. In 1985, when the abc conjecture was first stated, it remained open.

So let us assume that we have (somehow) proven the abc conjecture, and were interested in Fermat's Last Theorem. The first thing to note about the equation xⁿ + yⁿ = zⁿ is that if we had a solution for this equation, we could always find one for which xⁿ and yⁿ were relatively prime. This is because if they have a common prime factor, so must zⁿ, and we can cancel this factor (raised to the nth power) from both sides. Therefore, we have arrived at a situation in which we can apply the abc conjecture. The radical of xⁿ, for any n, is at most x since multiplying x by itself does not introduce any more prime factors that were not already there. Hence rad(xⁿyⁿzⁿ) = rad(xⁿ)rad(yⁿ)rad(zⁿ) ≤ xyz < z³. Therefore, for ε > 0, we have that

rad(xⁿyⁿzⁿ)^{1 + ε} < (z³)^{1 + ε} = z^{3 + 3ε}.

On the other hand, applying the conjecture to this triple, we have that for ε > 0,

rad(xⁿyⁿzⁿ)^{1 + ε} > zⁿ

in all but finitely many cases. Since we can choose ε to be any positive number, we can make it small enough so that 3 + 3ε < 4 (e.g. if ε = 0.1). Then if n ≥ 4, the two inequalities above directly contradict each other. Since the top one always holds and the bottom holds in all but finitely many cases, we conclude that there can be at most finitely many exceptions to Fermat's Last Theorem when n ≥ 4.

So the abc conjecture does not quite imply Fermat's Last Theorem, but it comes very close. If, in addition, we knew just a bit more about how the exceptional abc triples behaved, we could manually verify that there are no counterexamples to Fermat's Last Theorem for n ≥ 4. Interestingly, this argument does not say anything about the n = 3 case, that is, about the non-existence of solutions to x³ + y³ = z³. This special case, however, had already been proven by Euler in the mid-1700s.

Of course, the abc conjecture remains unproven, while Fermat's Last Theorem was finally proven by Andrew Wiles in 1995. This was done by entirely different means. Nevertheless, this serves as a relatively simple example of how the conjecture can prove results about Diophantine equations without invoking very difficult mathematics. Another example of a consequence is the following statement, sometimes called Pillai's conjecture:

Conjecture: Every natural number k occurs only finitely many times as the difference of two perfect powers.

For example, the special case k = 1 is the subject of Catalan's conjecture, and states that x^p - y^q = 1 has only one solution: 3² - 2³ = 1. This was proven by Preda Mihăilescu in 2002 (again by very different means from those above and from Wiles' methods), but the general case remains unsolved. If we knew for a fact that the abc conjecture were true, we would be able to prove this result by a very similar argument to the one given above for Fermat's Last Theorem (the reader is encouraged to try this!). Note that Pillai's conjecture also implies that the original equation that motivated the abc conjecture, namely y² = x³ + k, also has only finitely many solutions (for fixed k). This is the result David Masser and Joseph Oesterlé sought on their way to first formulating the statement.

These examples start to indicate how important the abc conjecture is to the study of Diophantine equations; if it were proven, it would resolve many different problems that are currently treated separately in a single stroke. Even reproving known results in a new and simple way would be greatly beneficial to the theory, since a set of tools that could prove abc would help to unify disparate parts of number theory. As a result, mathematicians will doubtlessly continue work toward solving the conjecture and probing the most fundamental structure of numbers.

Sources: http://projectwordsworth.com/the-paradox-of-the-proof/, Shinichi Mochizuki: Inter-Universal Teichmüller Theory I: Construction of Hodge Theaters, http://mathworld.wolfram.com/PillaisConjecture.html, https://rlbenedetto.people.amherst.edu/talks/abc\_intro14.pdf, Brian Conrad: The abc Conjecture, 12 sep 2013.

The abc Conjecture: abc Triples

This is the second post in a series about the abc conjecture. For the first post, see here.

In the last post, we defined the radical of an integer n, namely the product of distinct prime factors of n. We suspected in the last post that for most equations a + b = c where a and b are relatively prime, rad(abc) > c. This is because this inequality expresses our hypothesis that there should not be too many high powers of primes in the factorizations of a, b, and c. As a result, we made the following conjecture:

Conjecture 1: For all but finitely many equations of the form a + b = c where a and b are relatively prime, rad(abc) > c.

However, as mentioned at the end of the previous post, this is in fact false. To prove this, we have to exhibit an infinite family of equations a + b = c with rad(abc) ≤ c. Any triple (a,b,c) of numbers satisfying this property is called an abc triple. The only example we've seen so far is (1,8,9), or in equation form, 1 + 8 = 9. In terms of this new definition, we are trying to show that there are infinitely many abc triples. The following claim gives the desired result.

Claim: For any prime number p grater than 2, the triple (a,b,c) = (1,2^p(p-1) - 1,2^p(p-1)) is an abc triple.

Proof: This family is infinite because there are infinitely many prime numbers p. The proof depends on a fact in elementary number theory known as the Euler-Fermat Theorem. This theorem may be used to show that b = 2^p(p-1) - 1 is divisible by p². This is significant because we now know that the radical of b cannot be greater than b divided by p; this is because taking the radical of b "forgets" about at least one of the factors of p. Of course, rad(1) = 1 and rad(2^p(p-1)) = 2 so

Since p > 2, this last value is less than c, so that we do in fact have an infinite family of abc triples.

In fact the situation is even worse than this. Since the radical is less than 2c/p (as shown in the proof), it is not enough to replace the hypothesis rad(abc) > c with 2rad(abc) > c, or any higher multiple. We can make 2/p arbitrarily small by increasing p so that the radical is smaller than c by an arbitrarily large factor. For example, taking p = 5 gives the abc triple (1,1048575,1048576). Note that 5² = 25 divides b = 1048575, as claimed. Our proof guarantees that rad(abc) ≤ 2c/5. In fact the radical of this product is 419430. This is indeed less than 2/5 of c.

All of this shows that we cannot correct our conjecture 1 by adding a multiplicative factor to our inequality. The next reasonable thing one might try is a power law. Perhaps rad(abc)² > c for all but finitely many equations, or something similar. This, in fact, is the correct idea. However, the choice of 2 as the exponent again seems arbitrary. We know already that the statement is false when the power is 1, so let's try increasing it just a little. This leads us to the actual abc conjecture.

The abc Conjecture: For any ε > 0, no matter how small, for all but finitely many equations of the form a + b = c where a and b are relatively prime, rad(abc)^{1 + ε} > c.

The variable ε could for example be 1, and then we recover the rad(abc)² > c inequality. However, ε could also be very close to 0, giving an exponent of 1 + ε very close to 1. Crucially, any function x^{1 + ε} with ε > 0 eventually increases faster than any constant multiple of x, for example x^1.1, x^1.00001, etc. Therefore, this conjecture gets around the counterexample to conjecture 1. Nevertheless, the abc conjecture in some sense says that conjecture 1 is really close to being true. All we needed to do was increase the exponent by any positive amount. These concepts may become a little clearer with a new concept, called the quality of a triple (a,b,c). The formula for the quality, denoted q(a,b,c) is

This is another measure of how large c is compared to rad(a,b,c). In fact, rad(a,b,c)^q(a,b,c) = c. For example, q(13,22,35) is about 0.386, and q(1,8,9) is close to 1.226. This allows a more succinct description of the conjecture: for most triples, q ≤ 1. It follows from our definition that abc triples are those for which q > 1. Finally, the abc conjecture is equivalent to the following.

The abc Conjecture (Second Formulation): For any ε > 0, no matter how small, for all but finitely many equations of the form a + b = c where a and b are relatively prime, q(a,b,c) < 1 + ε.

Let's see if our conjecture seems plausible from the numerical data. One possible way to do this is to come up with many triples and see how large the quality q is for each.

In the above diagram (click to enlarge), the x-axis is our variable c. For each c between 2 and 2000, the plot goes through all possible relatively prime values a and b adding to c, finds the triple among these with the highest quality, and plots a corresponding point there. Therefore, all points are already among the highest quality triples. Even among these, abc triples (those that lie above the horizontal q = 1 line) are rare. Furthermore, they seem to get even more rare as c increases. In terms of diagrams of this sort, the conjecture states that only finitely many dots lie above a given horizontal line q = 1 + ε for any ε > 0. The highest quality abc triple that appears on the plot is (3,125,128) = (3,5³,2⁷), with a quality of 1.426. Are there any higher quality triples out there?

In fact, there are well over a hundred known with higher quality, a list of which may be found here. Currently, the highest known quality belongs to the triple (2,6436341,6436343) = (2,3¹⁰109,23⁵), with q = 1.6299. Even assuming the abc conjecture does not answer the question of whether this triple is really the highest quality there is. All it says is that examples of this sort must eventually die out as we approach infinity. For instance, there may very well be no triples at all with q ≥ 2, meaning that c ≤ rad(abc)² may hold in all cases with no exceptions.

Of course, no matter how many examples we check, we are no closer to proving that the abc conjecture holds. In the last post, we will discuss attempts to prove it, as well as the applications of the statement, should it be true.

Sources: http://www.math.leidenuniv.nl/~desmit/abc/, Greg Martin and Winnie Miao: abc Triples; Arxiv:1409.2974v1 [math.NT] 10 sep 2014, Brian Conrad: The abc Conjecture, 12 sep 2013.

The abc Conjecture: Motivation

Some of the earliest problems in mathematics asked about the integer solutions to simple polynomial equations. For instance, what are the possible right triangles with whole number side lengths? The solution dates at least back to the Ancient Greeks; the side lengths are related by Pythagoras' famous formula x² + y² = z². The 7th century Indian mathematician Brahmagupta studied integer solutions to the equation x² - 2y² = 1 as well as the same formula with 2 replaced by a general integer n (called Pell's equation). Many other similar equations have been studied for centuries or millennia.

In general, a Diophantine equation is a polynomial equation for which we are interested in integer solutions. Counterintuitively, some questions about solving these in the integers may be more difficult than considering all types of solutions. For example, the fundamental theorem of algebra states that any polynomial in a single variable has a root over the complex numbers (e.g. x³ - 4x² + 17x + 20 = 0 is true for some complex number). However, there is often no integer solution to such equations.

Historically, different types of Diophantine Equations were typically solved by ad hoc methods, as they come in many different varieties. However, one general observation that connects many of these equations is that they state something about the factorization of a sum of two numbers. Pythagoras' equation says something special about the sum of two squares, namely that it is another square! Similarly, Pell's equation says that one plus some number multiplied by a square has the property that it too is square. Our motivating question may then be taken to be:

How does the factorization of a sum of two numbers relate to the factorizations of the individual numbers?

The abc Conjecture provides a partial answer to this question. Its name comes from the fact that we are considering equations of the form a + b = c and asking how the factorizations of the three numbers relate. Mathematicians David Masser and Joseph Oesterlé first made the conjecture in 1985 while studying integer points on what are called elliptic curves, in this case given by the equation y² = x³ + k (where k is a fixed integer). This is yet another example of a sum having special factorization properties. Throughout the rest of this post, we will see how thinking about the motivating question might lead you to formulating the abc conjecture.

Simply put, we want the answer to our motivating question to be "it doesn't." Somehow, the additive and multiplicative structures of the integers should be independent of one another. This is in some ways a deep statement, and not at all intuitively clear, but we'll begin with this assumption. In other words, for an equation a + b = c, if all three numbers satisfy some special factorization properties (e.g. being cubes, etc.) it should in some sense be a coincidence. Our next task is to make this progressively less vague. First, we need a definition.

Definition: Two numbers are relatively prime if they share no common prime divisors.

For example, 34 and 45 are relatively prime, but 24 and 63 are not, because they are both divisible by 3. Here is how we will express our independence hypothesis: for any equation of the form a + b = c, where a and b are relatively prime, if a and b are divisible by high powers of primes, c almost always is not. This is in keeping with our theme because "divisible by high powers of primes" is special factorization property. That is, most prime factorizations should look more like 705 = 3*5*47 and not 768 = 2⁸*3. The assumption that a and b are relatively prime exists to rule out silly equations like

2ⁿ + 2ⁿ = 2^{n + 1},

in which all three numbers are divisible by arbitrarily high powers of 2. This doesn't represent some special connection between addition and multiplication - all we've done is multiplied the equation 1 + 1 = 2 by 2ⁿ. If we assert that a and b are relatively prime, then the prime factors of each of the three numbers are distinct, and we eliminate the uninteresting examples. Next, we require a mathematical notion that measures "divisibility by high prime powers".

Definition: The radical of a number n, denoted rad(n), is the product of the distinct prime powers of n. Also define rad(1) = 1.

For example, rad(705) = 3*5*47 = 705 (since the factors 3, 5, and 47 are distinct) but rad(768) = 2*3 = 6. The radical function forgets about any powers in the prime factorization, keeping only the primes themselves. Notice that the radical of a number can be as large as the number itself, but it can also be much smaller. The amount by which rad(n) is smaller than n can be taken as a measure of to what extent n is divisible by large prime powers.

Now we return to our equation a + b = c (where we will now consistently assume the relatively prime hypothesis). A reasonable way to test for high prime power divisibility for all three of these numbers is to calculate rad(abc) = rad(a)rad(b)rad(c) (the reader may wish to prove this last equation). Since rad(abc) could be as large as abc itself, it seems likely that rad(abc) would usually be much larger any of the individual numbers, the largest of which is c. For example, consider 13 + 22 = 35. In this case, rad(abc) = rad(13*22*35) = 13*2*11*7*5 = 10010, which is much larger than c = 35. However, this property does not always hold true. Consider another example, 1 + 8 = 9. Now we have rad(abc) = rad(1*8*9) = 2*3 = 6, and 6 < 9 = c. Notice that this anomaly reflects something weird going on; the equation can also be written 1 + 2³ = 3², so one plus a cube is a square. Testing different values of a, b, and c gives the impression that equations of the second sort are rare. Therefore, we make an almost mathematical conjecture:

"Almost" Conjecture: For equations of the form a + b = c where a and b are relatively prime, rad(abc) is almost always greater than c.

We're close! The equation rad(abc) > c is a bona fide mathematical condition that we can check. However, we have yet to render "almost always" into mathematical language. Clearly there are infinitely many a + b = c equations to look at. What does it mean to say that "most of them" behave in some way? We know from our 1 + 8 = 9 example that there are at least some exceptions. Maybe we could assert that there are less than 10 total exceptions, or less than 100. However, these numbers seem arbitrary, so we'll just guess that there are only finitely many exceptions. That is, all but at most N of these equations, for some fixed finite number N, satisfy our hypothesis. In conclusion, we conjecture that:

Conjecture 1: For all but finitely many equations of the form a + b = c where a and b are relatively prime, rad(abc) > c.

Finally, a real conjecture! Unfortunately, it's false. In other words, there are infinitely many such equations for which rad(abc) ≤ c. Don't worry! It's rare in mathematics to come up with the correct statement on the first try! In the next post, we'll prove our conjecture 1 false and see how to correct it.

Sources: https://rlbenedetto.people.amherst.edu/talks/abc\_intro14.pdf, Brian Conrad: The abc Conjecture, 12 sep 2013.

Goodstein's Theorem and Non-Standard Models of Arithmetic

This is the final post in a four-part series on logic and arithmetic, with a focus on Goodstein's Theorem. For the first post, see here.

In the previous post, Goodstein's Theorem, a statement about the properties of certain sequences of natural numbers, was proven using infinite ordinals. The use of a method "outside" arithmetic makes it reasonable that this proof cannot be encoded in the language of Peano Arithmetic (PA), the formal logical system for discussing the natural numbers. A stronger statement is also true: there is no proof of Goodstein's Theorem in PA because it cannot be deduced from the axioms of PA.

But how does one go about proving something unprovable? Certainly it is intractable to check every possible method, as the diversity of such attempts could be infinite. Mathematicians take a different approach, using tools from what is called model theory. In mathematical logic, a model of a collection of axioms is a specific structure within which the axioms (and all theorems derived from them) are interpreted to be true. Recall that the axioms of PA mentioned five specific objects, that were assumed to be given from the start: a set N, a specific member, 0, a function S from N to itself, and two binary operations on N, + and *. Of course, to actually do arithmetic we interpret N as the set of natural numbers, 0 as the number 0, S as the "successor" function taking in a number n and returning n+1, and + and * as the usual addition and multiplication. Until we provide an interpretation of to what these objects refer, namely a model, they are just symbols! We may prove statements about them, such as the fact that S(0) and S(S(0)) are distinct members of N, but this is just a mathematical sentence resulting as the end product of a series of formal deductive rules.

Any collection A = (N_A,0_A,S_A,+_A,*_A) of a set N_A, a member 0_A of the set, a function S_A:N_A→N_A, and two binary operations +_A and *_A that satisfies the axioms is a model of PA. Of course, we know fairly well what we mean by "natural numbers", namely {0,1,2,...} with 0 the first element, S sending 0 to 1, 1 to 2, etc, and the usual addition and multiplication. The entire point of selecting axioms for PA is to study ℕ = (N,0,S,+,*), the standard natural numbers. A natural question (called the question of categoricity) arises: is the standard model the only type of model for PA, or are there others? The answer is no; there are other, non-standard models A that still satisfy every axiom of PA. These were first discovered by Norwegian mathematician Thoralf Skolem in 1934. To be clear, they are not the natural numbers, at least, not as we intend them to be. Their existence exemplifies another limitation of first-order logic: axiom systems often fail to specify structures uniquely and hence fail to capture some features of the field to be studied.

Non-standard models often serve as an essential tool in independence proofs. First, we know from the previous post that the standard model ℕ of PA does satisfy Goodstein's Theorem (the standard model has the properties the natural numbers possess within the larger field of set theory, the methods of which were used in the proof). This means that the negation of Goodstein's Theorem cannot be a theorem of PA, since there is a model satisfying both the axioms and the theorem. If one could find a model of PA in which the negation of Goodstein's Theorem were true, then this would prove independence, because there would be models in which it is true and others in which it is false! Kirby and Paris used precisely this method in their 1982 proof of the result.

But what do non-standard models of natural numbers actually look like? First, we may infer what they have in common. PA axiom 1 guarantees the existence of a number 0. Axiom 2 gives it successors S(0), S(S(0)), etc. Axiom 3 says that S(n) = S(m) implies m = n. Therefore, all the successors generated from 0 are distinct from one another. This means that any model A has a set of natural numbers N_A containing the analogues of 0, 1, 2, and so on. The set of standard natural numbers N is thus contained in N_A for every A. The difference is that non-standard models have extra numbers!

At first brush, having additional "non-standard" numbers seems to contradict the Peano axioms, specifically the fifth, the axiom schema of induction. It states that if 0 has some property and that any n having the property implies that n + 1 does as well, then all natural numbers have the property. The spirit of this axiom schema, if not the letter, is that beginning at 0 and knocking down the inductive dominoes will eventually reach every natural number. If we could choose the property to be "is in the set {0,1,2,...} (the standard natural numbers N)" then this would immediately rule out nonstandard models: 0 is this set, and for any n in the set, its successor is also standard, so all of N_A is contained in {0,1,2,...} and hence we would have N_A = {0,1,2,...}. Unfortunately, it is impossible to define the set {0,1,2,...} inside of the first-order logic formulation. It is also impossible to simply add an axiom "there are no other numbers besides 0, 1, 2, etc." for the same reason. Both approaches require infinitely long logical sentences to formulate, which are forbidden in the finitary system of first-order logic.

Though the axioms of PA cannot rule out non-standard natural numbers, they are forced by the axioms to satisfy some strange conditions. Any nonstandard number c must be greater than all standard numbers. Further, PA can prove that 0 is the only number without a successor, so a "predecessor" to c, which we may call c - 1, must exist. Similarly, c - 2, c - 3, etc. must exist, as must, of course, c + 1, c + 2, etc. These must all be new non-standard numbers. Therefore, the existence of one non-standard number guarantees the existence of a whole non-standard "copy" of the integers: {...,c - 2,c - 1,c,c + 1,c + 2,...}. However, it gets much, much worse. The operation of addition is part of Peano Arithmetic, so there must be a number c + c, that may be proven to be greater than all numbers c + 1, c + 2, and so on. From here, we get another new infinite collection of non-standards {...,c + c - 2,c + c - 1,c + c,c + c + 1,c + c + 2,...}. A similar story occurs for c + c + c = c*3 and larger numbers as well, but we can also go in reverse. One can prove in PA that every number is either even or odd; that is, for any n, there is an m satisfying either m + m = n (if n is even), or m + m + 1 = n (if n is odd). This theorem means that c is even or odd, so there must be a smaller non-standard d with d + d = c or d + d + 1 = c. This d has its own infinite set of non-standard neighbors. The reader may continue this type of exercise and eventually derive the type of picture illustrated above: any non-standard model of natural numbers must contain the standard numbers plus (at least) an infinite number of copies of the integers, ℤ, one for each member of the set of rational numbers, ℚ.

As strange as these models are, they cannot be ruled out in PA, nor is there a natural addition to the axioms that may do so. Rather than being just a defect of first-order logic however, non-standard models are a useful tool for examining the structure of different theories. Now that we have a non-standard model at our disposal, it seems reasonable that Goodstein's Theorem should fail for some non-standard models: "Goodstein sequences" beginning at non-standard natural numbers do not seem likely to terminate at zero. After all, they have infinitely many copies of the integers to move around in! These sequences often cannot be computed explicitly, but using other logical machinery, one can prove the fact that they do not necessarily terminate. This establishes the independence of the theorem from PA.

Goodstein sequences, interesting in their own right for their rapid growth, allow an interesting perspective on Peano Arithmetic and its limitations. The questions of independence and non-standard models arise frequently in the foundations of mathematics, as we seek to define precisely the scope of our mathematical theories.

Sources: http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf, http://blog.kleinproject.org/?p=674, http://www.ams.org/journals/proc/1983-087-04/S0002-9939-1983-0687646-0/S0002-9939-1983-0687646-0.pdf, http://settheory.net/model-theory/non-standard-arithmetic, http://www.columbia.edu/~hg17/nonstandard-02-16-04-cls.pdf, http://boolesrings.org/victoriagitman/files/2015/04/introToPAModels.pdf, http://lesswrong.com/lw/g0i/standard_and_nonstandard_numbers/

Proving Goodstein's Theorem and Transfinite Methods

This is the third part of a post series on Goodstein's theorem. For the first part, see here.

The previous post introduced the reader to Peano arithmetic (PA), the archetypical example of an axiomatic system introduced to standardize the foundations of mathematics. Despite having tremendous expressive power in formulating and proving theorems about natural numbers, the system is not without limitations. Gödel's Incompleteness Theorem guarantees the existence of statements out of the reach of formal proofs in PA. Goodstein's Theorem, which states that every Goodstein sequence terminates at 0, is an example. Further, it is a "natural" example in the sense that it was not contrived to demonstrate incompleteness. In fact, Goodstein proved the theorem in 1944, decades before Laurence Kirby and Jeff Paris discovered that it is independent of the axioms of PA in 1982.

To see why this independence holds, we consider the proof of Goodstein's Theorem. As mentioned, it is not provable in PA, so the proof makes use of tools outside of arithmetic: in particular, infinite ordinal numbers. A more thorough discussion of ordinal numbers may be found elsewhere on this blog. For our purposes, the key property of ordinal numbers is that they represent order types of well-ordered sets.

A well-ordered set is simply a set of elements and an ordering relation (often called "less than" and denoted by "<") such that any two elements are comparable (each is less than, equal to, or greater than) the others, and every subset has a minimal element. The set may be finite or infinite. Here are some examples:

• The set of natural numbers itself, {0,1,2,3,...}, with the relation "less than" is well-ordered because every two elements are comparable and every subset has a smallest number
• The set of natural numbers with the "greater than" relation is not well-ordered: with this relation, "minimal" elements are really largest elements, and the subset {3,4,5,...}, for example, has no greatest element
• The set {A,H,M,R,Z} with the relation "comes before in the alphabet" is well-ordered because we can compare any two letters to see which comes first in the alphabet, and any subset has a first letter
• The set of all integers {...-2,-1,0,1,2,...} is not well-ordered by either less than or greater than relations

The gist of the definition is that all set elements are listed in a particular order so that we can always tell which of a pair comes first, and that infinite ascending sequences are acceptable while decreasing ones are not. To understand order type, we need a notion of when two well-ordered sets are "the same". For example, the set {1,2,3,4,5} with the less than relation and {A,H,M,R,Z} with the alphabet relation are quite similar. Using the one-to-one relabeling 1 → A, 2 → H, 3 → M, 4 → R, 5 → Z, we can move from one set to the another and preserve the ordering relation. That is, 1 < 2 in the first set and their images satisfy A < H in the second set, and so on. If there is a relabeling like the one above between two sets, they are said to be of the same order type.

The purpose of ordinal numbers is to enumerate all possible order types for well-ordered sets; there is one ordinal for each order type. To make thinking about ordinals simpler, we often say that an ordinal is a specific set of the given order type, a particularly nice set. Specifically, we choose the set of all smaller ordinals. Since the sets in the example of the previous paragraph have five elements, their order type is the ordinal 5 = {0,1,2,3,4} (the reader may wish to show that any well-ordered five element set in fact has this order type). In fact, for finite sets, there is simply one ordinal for each size set. For infinite sets, matters become more interesting.

The ordinal corresponding to the order type of the natural numbers is called ω. Using the canonical choice of representative set, ω = {0,1,2,3,...} (where we now view the elements as ordinals). The next ordinal is ω + 1, the order type of {0,1,2,3,...,ω} or in general the order type of a well-ordered set with an infinite ascending collection plus one element defined to be greater than all others. One can go on to define ω + n for any finite n and ω*2, the order type of {0,1,2,3,...,ω,ω + 1,ω + 2,...} (two infinite ascending chains stuck together). The precise details do not concern us here, but ω², ω^ω, ω^ωω, and so on may be defined as well. What matters is that these ordinals exist and that the set of all ordinals expressible with ordinary operations on ω (for example, (ω^ω)*4 + (ω³)*2 + ω*5 + 7) is a well-ordered set. In fact, the set of such ordinals is itself a larger ordinal called ε₀.

Once these preliminaries are established, the proof of Goodstein's Theorem is rather simple, and even clearer when considered intuitively. For any Goodstein sequence, the members are represented in hereditary base-n notation at every step: the first member is put into base 2, the next base 3, and so on. The idea is to take each member of the sequence and replace the base with ω to obtain a sequence of ordinals. For example, the sequence G₄ generates a sequence of ordinals H₄ in the following way:

G₄(1) = 4 = 1*2^1*21 → H₄(1) = ω^ω (the 2's are replaced with ω's),
G₄(2) = 26 = 2*3² + 2*3¹ + 2 → H₄(2) = (ω²)*2 + ω*2 + 2 (3's are replaced with ω's),
G₄(3) = 41 = 2*4² = 2*4¹ + 1 → H₄(3) = (ω²)*2 + ω*2 + 1 (4's are replaced by ω's),
and so on.

Note that the multiplication by coefficients has been moved to the other side of the ω's for technical reasons and that some of the 1's have been removed for clarity. One may precede in this matter to get a sequence of ordinals, the key property of which is that the sequence is strictly decreasing. In the above example, ω^ω > (ω²)*2 + ω*2 + 2 > (ω²)*2 + ω*2 + 1 and this downward trend would continue if we were to list more terms. This is because the H sequences "forget" about the base: it is always replaced by ω. The only change is caused by the subtraction of 1 at each step, which slowly reduces the coefficients. Intuitively, this is the point of the proof: by forgetting about the base, we replace the extreme growth of Goodstein sequences with a gradual decline. The units digit of the H sequence decreases by 1 every step. When it reaches 0, on the next step the ω coefficient is reduced by 1 and the units digit is replaced by the current base minus 1 (the highest allowed coefficient). These may become quite large, but they always reach zero eventually. Reasoning this way, it is clear that Goodstein's Theorem should be true.

In formal terms, the set of ordinals is well-ordered, so the set consisting of all members of an H sequence must have a minimal element, i.e., it cannot decrease forever. The only way that it can stop decreasing is if the G sequence stops, and Goodstein sequences only terminate at 0. Therefore, every Goodstein sequence terminates at 0 after a finite number of steps. We've proved Goodstein's Theorem!

Bringing in infinite ordinals to prove a statement about natural numbers is strange. So strange in fact that the argument is not formalizable in PA; there is simply no way to even define infinite ordinals in this language! This indicates why the given proof does not go through in PA, but does not settle the matter as to whether there is no possible proof of Goodstein's Theorem within PA. It leaves the possibility that there is a different clever approach that can succeed without infinite ordinals. A discussion of why this in fact does not occur may be found in the final post of this series.

Sources: http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf, http://blog.kleinproject.org/?p=674, http://www.ams.org/journals/proc/1983-087-04/S0002-9939-1983-0687646-0/S0002-9939-1983-0687646-0.pdf

Goodstein's Theorem and Peano Arithmetic

This is the second part of a post series on Goodstein's theorem. For the first part, see here.

We saw last post that Goodstein sequences are certain sequences of positive integers defined using base representations. Despite their simple definition, they grow extraordinarily large. However, Goodstein's Theorem states that no matter how large the starting value is, the sequence will eventually terminate at 0 after some finite number of steps. Before discussing the proof to this remarkable theorem, we move in a completely different direction and define the axioms of Peano arithmetic.

Increasing standards of rigor were a hallmark of late 19th and early 20th century mathematics. With this movement came a need to precisely define the basic building blocks with which a given branch of mathematics worked. This was even true for simple arithmetic! By 1890, the mathematician Giuseppe Peano had published a formulation of the axioms (fundamental assumptions) of arithmetic, which are used nearly unchanged to this day. Written in simple english, the axioms state the following about the collection N of natural numbers (nonnegative integers), a function S known as the successor function, a function + known as addition, and a function * known as multiplication:

1) There exists a natural number called 0 in N
2) For every natural number n in N there is a successor S(n) in N (commonly written
n + 1)
3) There is no natural number whose successor is 0
4) For any two natural numbers m and n in N, if S(m) = S(n), then m = n
5) For any natural number n, n + 0 = n
6) For any natural numbers n and m, n + S(m) = S(m + n)
7) For any natural number n, n*0 = 0
8) For any natural numbers n and m, n*S(m) = n*m + n
9) For any "well-behaved" property P, if P(0) holds and for each n in N, P(n) implies
P(n + 1), then P is true for every natural number in N

The first two axioms simply say that you can start from 0 and count upwards forever through the natural numbers. The third says that there is no natural number below 0 (this is of course false for larger sets of numbers such as integers, but Peano's axioms are only for properties of the natural numbers). The fourth shows that the successor of a natural number is unique. The fifth through eighth axioms state the common properties of addition and multiplication. The ninth axiom is actually a large collection of axioms (an axiom schema) in disguise, called the "axiom schema of induction."

The idea of induction may be familiar to readers who recall their high school mathematics: one often wishes to prove that a given property holds for every natural number. To do so, it is sufficient to show that it is true in the "base case," that is, true for 0, and that the statement being true for a number means that it is also true for the next. Then since the property is true for 0, it is true for 1. Since it is true for 1, it is true for 2, and so on. The figure above illustrates the idea of induction, where each "statement" is that the given property is true for some number. The final axiom simply codifies the fact this type of reasoning works; we get that the property is true for all natural numbers. In this context, a "well-behaved" property is one expressible in the semantics of the variety of logic being used (first-order logic in this case).

Remarkably, the above assumptions are all that is needed to perform arithmetic. In principle, though formalizing complicated proofs would be quite lengthy, true statements such as "17 is prime" and "every number is the sum of four squares" become theorems in Peano arithmetic. All of these proofs would take the form of a chain of statements beginning from axioms and concluding with the desired result, such as "17 is prime," rendered appropriately in the formal mathematical language. The progression from each statement to the next would also follow a collection of well-defined deductive rules. In principle, almost all theorems concerning natural numbers could be proven this way, beginning from just a small collection of axioms! However, Peano arithmetic still runs afoul of a result that vexes many axiom systems of first-order logic: Gödel's Incompleteness Theorem.

Gödel's (First) Incompleteness Theorem, originally proven by the mathematician Kurt Gödel in 1931, dashed the hopes of those who imagined that formal logical systems would provide a complete description of mathematics. It states, informally, that for any first-order logical system powerful enough to encode arithmetic (Peano arithmetic is of course such a system), there exist statements in the language of the system that are neither provable nor refutable from the axioms. Further, there are explicit sentences in the logical system that are true (under the intended interpretation of the theory, more on this later) but unprovable. The above diagram illustrates the situation: there will always be things we know to be true or false that are beyond the reach of the axioms to formally prove or refute.

Some questions may spring to mind at this unintuitive result. What is the distinction between "true" and "provable"? How do we define "true" in mathematics if not as the end result of a proof? What do these unprovable statements look like, and what do they say?

The answer to the first of these depends on there being something "we mean by" the term "natural numbers". In other words, there is an intended interpretation of what natural numbers should be that the logical system fails to completely capture. Consequently, there are statements that we know to be true using methods outside the formal system but are unprovable within it. Bringing in additional assumptions does not simply resolve the incompleteness theorem, however. For each outside axiom added, the theorem guarantees the existence of a new unprovable statement. And if the system ever does become complete by the addition of more axioms, it also becomes inconsistent, that is, able to prove a contradiction (and loses all validity as a mathematical system).

As for the final question, the first known unprovable statements were those constructed in the proof of Gödel's theorem; these are known as Gödel sentences. They are highly contrived for the proof, however, and do not have any intuitive meaning. In the years following the original proof, the concern remained whether, for example, any statement that "naturally" arises in the study of natural numbers would be unprovable and unrefutable from the axioms of Peano arithmetic. Amazingly, such statements exist! In fact, a great example is Goodstein's Theorem. No proof exists, beginning from the Peano axioms, that has it as a conclusion. To read more about how it can be proven and why it is not a theorem of Peano arithmetic, see the next post.

Sources: https://www.cs.toronto.edu/~sacook/csc438h/notes/page96.pdf, https://plato.stanford.edu/entries/goedel-incompleteness/

Goodstein Sequences and Hereditary Base Notation

In mathematics, Goodstein sequences are certain sequences of natural numbers. Though they are fairly easy to define, their properties have important consequences in logic. Before investigating these, however, we give the definition. It depends on the concept of expressing numbers in different bases (well-known examples in addition to normal base-10 representations include binary, base 2, and hexadecimal, base 16). Recall that when writing a number, such as 4291, what we mean is 4 thousands plus 2 hundreds plus 9 tens, plus 1 one, alternatively expressed as

4291 = 4*10³ + 2*10² + 9*10¹ + 1.

This decomposition uses 10 as a base. Note that the numbers multiplying the powers of 10 always vary between 0 and 9. Base 2, for example, could be used just as easily, with only digits 0 and 1 as coefficients. Expressing 4291 as powers of 2 yields

4291 = 1*4096 + 0*2048 + 0*1024 + 0*512 + 0*256 + 1*128 + 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 1*2 + 1*1
= 1*2¹² + 0*2¹¹ + 0*2¹⁰ + 0*2⁹ + 0*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1.

Therefore, 4291 is typically expressed in binary as the sequence of coefficients 1000011000011. However, for our purposes, it is more convenient to explicitly express the powers of the base involved, although it will simplify matters to drop those terms with coefficient 0 since they have no contribution to the sum. The equation above then becomes

4291 = 1*2¹² + 1*2⁷ + 1*2⁶ + 1*2¹ + 1.

The system described above is known as ordinary base notation, but the definition of Goodstein sequences requires a slightly modified version, hereditary base notation. This involves taking the exponents themselves and subjecting them to the same base decomposition as the original number. Since 12 = 1*2³ + 1*2², 7 = 1*2² + 1*2¹ + 1, and 6 = 1*2² + 1*2¹, the integer 4291 now becomes

4291 = 1*2^{1*23 + 1*22} + 1*2^{1*22 + 1*21 + 1} + 1*2^{1*22 + 1*21} + 1*2¹ + 1.

This expression is quite complicated, but the process is not quite finished yet! The exponents 2 and 3 within the exponents are not yet in base-2: 3 = 1*2¹ + 1 and 2 = 1*2¹. Making the necessary replacements finally gives 4291 in hereditary base-2 notation:

4291 = 1*2^{1*21*21 + 1 + 1*21*21} + 1*2^{1*21*21 + 1*21 + 1} + 1*2^{1*21*21 + 1*21} + 1*2¹ + 1.

In the general case, there may be many iterations of this process, which motivates the name "hereditary"; a base-2 decomposition is applied to the original integer and then the exponents that result, and then their exponents, and so on. The end result has only 2's as bases of exponents and only 1's as coefficients. The interested reader can verify that this type of process may be repeated for any positive integer in any base (using as coefficients positive integers less than the base), and that for a fixed number and base, the representation thus obtained is unique. The stage is now set for the definition of Goodstein sequence.

A Goodstein sequence is simply a sequence of nonnegative numbers. We may choose any number 1, 2, 3,... to begin the sequence. Next, whatever this number is, we express it in hereditary base-2 notation, just as we did with the example 4291 above. To generate the next member of the sequence, simply change every 2 in the hereditary base-2 representation to a 3, and then subtract 1 from the resulting number. This is the second member of the sequence. After that, express this second number in hereditary base-3 notation, change the 3's to 4's, and subtract one to get the third, and so on. We denote the nth member of the Goldstein sequence beginning with m by G_m(n). The first few sequences G_m die out quickly: if the seed is 1 (whose hereditary base-2 representation is just 1), there are no 2's to change to 3's so we simply subtract 1 to find G₁(2) = 0. If a sequence reaches 0, we end it there, so that the sequence

G₁ = {1,0}.

G₂ is scarcely more interesting: G₂(1) = 2 = 1*2¹ so changing the single 2 to a 3 and subtracting 1 yields G₂(2) = 1*3¹ - 1 = 2. Recall that coefficients 0-2 are allowed in hereditary base-3 notation so 2 in this notation is simply 2. There are no 3's to change to 4's, so we subtract 1 to get G₂(3) = 1. There are no 4's to change to 5's, so G₂(4) = 0 and the sequence is finished:

G₂ = {2,2,1,0}.

Beginning with 3 leads to a sequence nearly identical: the reader may try calculating the sequence. The end result is G₃ = {3,3,3,2,1,0}. However, at m = 4, new behavior emerges. 4 = 1*2^1*21, so both 2's must be replaced by 3's to get: G₄(2) = 1*3^1*31 - 1 = 27-1 = 26. In hereditary base-3, 26 = 2*3² + 2*3¹ + 2 so G₄(3) = 2*4² + 2*4¹ + 2 - 1 = 41. For the next step, we get G₄(4) = 2*5² + 2*5¹ + 1 - 1 = 60. Note that the units digit is reduced by one in each step even as the sequence increases. When it hits zero, as in this step, the coefficient of the penultimate coefficient is decreased by one: G₄(5) = 2*6² + 2*6¹ - 1 = 83 = 2*6² + 1*6¹ + 5. However, the new units digit becomes one less than the base, namely 5, so it takes more steps for this to reach zero than previously. After another five steps, we arrive at G₄(10) = 2*11² + 1*11 = 253. When changing to base 12 at the next step, we obtain G₄(11) = 2*12² + 11 = 299. The units digit again decreases for the next 11 steps, until G₄(22) = 2*23² = 1058.

The next step starts to indicate why Goodstein sequences can increase for so long: G₄(23) = 2*24² - 1 = 1151 = 1*24² + 23*24¹ + 23. Since the base is 24, we get two new coefficients of 23. Each time the units digit reaches zero, the value at which it has to start the next time doubles. The square term in the base representation does not vanish until the base reaches 402653184. And at this point the sequence has barely begun. The largest value it reaches is 3*2^402653210 - 1 at base 3*2^402653209, after which the sequence remains stable for a while before finally declining to zero. This maximum value is so astronomically large that if the digits of the number were printed at a typical font size, front and back, it would fill a stack of paper over 10 feet tall! And this is just G₄. Goodstein sequences with higher initial values increase much, much faster.

If we start with 18, for instance, since 18 = 1*2^1*21*21 + 1*2¹, replacing all the 2's with 3's gives G₁₈(2) = 1*3^1*31*31 + 1*3¹ - 1 = 7625597484989. The third term is G₁₈(3) = 1*4^1*41*41 + 2 - 1, which is about 10¹⁵⁴. The values this sequence reaches quickly become difficult to even write down. However, Reuben Goodstein himself, after whom the sequences are named, proved in 1944 a statement that became known as Goodstein's Theorem. His remarkable result showed that no matter how incalculably large the sequences become, they always terminate at 0. That is, after some finite, though possibly immense, series of steps, each sequence stops increasing eventually and decreases to 0.

The theorem's proof has significance beyond demonstrating this surprising fact about Goodstein sequences. For more, see the next post.

Source: https://www.jstor.org/stable/2268019, http://mathworld.wolfram.com/GoodsteinSequence.html

Voronoi Diagrams and Metrics

In mathematics and visual art, a Voronoi diagram is a type of partition on a surface (usually a plane). Such a diagram is determined from some set of points (called "seeds") on the surface and a notion of distance on the surface by assigning each point a "cell," namely the region in the plane within which the given seed is closer than any other seed. The diagrams are named for the Ukrainian mathematician Georgy Voronoy.

Our first example of a Voronoi diagram consists of only two seeds (the black dots) and two cells, where the line connecting the two seeds is also shown. The maroon region contains the points in the plane closest to the left-hand seed, and the blue region the right. The divider between the two regions bisects the line between the two seeds (since the midpoint is by definition equidistant from the two endpoints) and is in particular the perpendicular bisector of this line. We now present a more complicated example.

In this image, the dots again represent the seeds, while the differently colored regions are the cells of the diagram. The inner region is bounded by a polygon (specifically a pentagon) whose sides are perpendicular bisectors of the lines connecting each of the outer seeds to the center seed. Note also that the central region is finite, since the center seed is surrounded by other seeds, while the other regions extend outward forever. Finally, each point at which three regions meet is the circumcenter of the triangle formed by three nearby seeds. The image below illustrates this fact for our example with six seeds.

Three of the seeds have been connected to form a triangle (white). The circumcenter of the triangle is the center of the circle containing the triangle's three vertices (black). By the definition of a circle, the circumcenter (red) is equidistant from the three seeds and is therefore the point at which the three neighboring regions meet.

Further, regular patterns of seeds produce correspondingly regular patterns of the cells. For example, a repeating square lattice of points produces a repeating pattern of square cells, as shown below.

The reader may experiment with different seed placements using the interactive feature found here. There are many ways to generalize the Voronoi Diagram concept beyond the two-dimensional plane. For example, it is possible to construct three-dimensional Voronoi diagrams, again using points as seeds, except that space will now be divided into three-dimensional cells instead of two.

The above image shows a number of seeds scattered in three-dimensional space and a single cell corresponding to the seed at the center. The lines connecting the center seed to the surrounding ones are also shown. Instead of a polygon, the cell is a polyhedron, bounded by faces which are sections of the planes that form the perpendicular bisectors of the line segments connecting the seeds.

In mathematics, Voronoi diagrams are useful for visualizing the notion of a metric. Metrics are generalizations of the familiar concept of distance to a number of different spaces in addition to the normal Euclidean plane and space (which we have worked with so far). For example, consider the surface of a sphere, such as the Earth. Typically, we define the distance between two points to be the length of the straight line connecting them (which in Euclidean space is the shortest path between the points). However, given two points on the Earth (a sphere), the line connecting them might go through the interior. When we speak of "distance" on the sphere, we want the shortest path along the surface between the two given points, or in other words the fastest travel route from one to the other!

The shortest distance between the points A and B above on the sphere is not the latitude line that they share (though this would be the straight path between them on the 2D map projection) but the arc of a circle passing through the sphere's center. These circles are known as great circles. The distance between two points on a sphere is defined to be the length of the great circle arc connecting them. This is also why planes take what appear to be inefficient paths on two-dimensional maps: they are in fact following a great circle (see below).

Having defined a metric for the sphere, we may choose some collection of points on it and create Voronoi diagrams, just as before. The diagram below takes major airports around the world as seeds and constructs a Voronoi diagram on the Earth's surface (which, of course, is nearly a sphere).

Voronoi diagrams also have a number of applications outside mathematics in settings where understanding distances from a fixed set of sources is important. They are used in modeling the spread of disease, the growth of forests, cell development, the distribution of minerals in the Earth's crust, and rainfall maps, among other things. They are a beautiful visual tool for comprehending the relative positions of points in a given space.

Sources: http://alexbeutel.com/webgl/voronoi.html, http://www.iue.tuwien.ac.at/phd/klima/node21.html, http://www.pitt.edu/~jdnorton/teaching/HPS_0410/chapters/non_Euclid_curved/Geodesic3.gif, http://beautifulnow.is/bnow/the-quest-for-beautiful-data

The Projective Plane: An Algebraic Exploration II

This is the third post in a series discussing the projective plane. For the first, see here.

The previous post explained how certain types of polynomials, namely the homogeneous polynomials, define curves in the projective plane called projective varieties. This post will explicate the relation between projective varieties and affine varieties (typical curves in the plane) and indicate how projective varieties are in a way the extensions of affine varieties to include their points at infinity.

First, we consider how projective varieties naturally give rise to normal affine plane curves. Consider the projective variety defined by the equation F(x:y:z) = 0, where F is a homogeneous polynomial. In the first post of this series, we saw that the plane z = 1 in three-dimensional space can represent the subset of the projective plane that corresponds to the normal affine plane (i.e., without the points at infinity). We repeat the image from the first post for convenience, where each line through the origin (a point of projective space) is represented by the point at which it intersects the plane.

Since we obtain the affine plane by setting z = 1, it seems reasonable that we should be able to "collapse" projective varieties algebraically by setting z = 1 in the equation F(x:y:z) = 0. This is indeed the case, since substituting z = 1 yields a polynomial in only two variables: f(x,y) = F(x,y,1). For example, if F(x:y:z) = x²y + 2yz² - 5z³ (note that F is homogeneous and therefore defines a projective variety), then f(x,y) = F(x,y,1) = x²y + 2y*1² - 5*1³ = x²y + 2y - 5. The projective variety F(x,y,z) = 0 therefore corresponds to an affine variety f(x,y), as desired.

There is also an algebraic process that does the reverse by taking a polynomial f(x,y) and producing a corresponding homogeneous polynomial in three variables, F(x:y:z). The process works as follows:

1. Add up the powers of x and y in each term of f and let n be the greatest degree that appears
2. Multiply each term by z^n-k, where k is the degree of the term (this ensures that the resulting polynomial is homogeneous)

Let us take the polynomial f(x,y) = x²y + 2y - 5 from above and apply the new process. The degrees of the three terms are 3, 1, and 0, respectively (-5 = -5x⁰y⁰). The maximum of these is 3, so we multiply the first term by z^3-3 = z⁰ = 1, the second by z^3-1 = z², and the third by z^3-0 = z³. The resulting polynomial is F(x:y:z) = x²y + 2yz² - 5z³, exactly the same as the original polynomial! It is easy to verify that these two processes are mutually inverse in general, except in certain special cases such as when F is only a function of z.

Now we may apply these algebraic tools to solve the problems introduced in the last post that cannot be solved visually. First, regarding the hyperbola, algebra confirms our intuition. To see this, take the equation xy - 1 = 0 and transform it into the corresponding projective variety. The result is easily calculated as xy - z² = 0. The asymptotes x = 0 and y = 0 to this hyperbola (see image in previous post) are unchanged by the process since they only have one term, clearly of maximal degree.

Next, recall that the points at infinity in the projective plane are those for which z = 0 in the homogeneous coordinates (x:y:z). This can be seen in the above visualization, where only points of the form (a:b:1) belong to the affine subset of the projective plane. Now any (x:y:z) can be scaled to this form by multiplying each component by 1/z (remember, only the ratio of the coordinates matters), but only when z is nonzero. Therefore, we substitute z = 0 and solve the equations to see which points at infinity each curve intersects. For the hyperbola, this gives xy = 0, so x = 0 or y = 0. Therefore, the two points at infinity the hyperbola intersects are (0:1:0) and (1:0:0). Other coordinate triples satisfying xy = 0 such as (3:0:0) differ only by a scale factor from one of the two solutions above and therefore define the same point in the projective plane. It follows that (0:1:0) and (1:0:0) are the only solutions. But the asymptotes x = 0 and y = 0 hit exactly the same points, (0:1:0) and (1:0:0), respectively! This confirms our intuition: a hyperbola and its asymptotes really do intersect at infinity.

The cubic y - x³ = 0 has no asymptote, but clearly goes off to infinity in some manner. We may use our algebraic tools to investigate the function's behavior in the projective plane. The highest degree term is x³, of degree 3, so we must multiply the other term (namely the expression y, of degree 1) by z^3-1 = z². The projective variety corresponding to the cubic is therefore defined by the equation yz² - x³ = 0. Substituting z = 0 yields x³ = 0, which has the single point (0:1:0) in the projective plane as a solution (since z is already set to 0). Note that even though the cubic goes to infinity in both the positive and negative directions, it meets only one point at infinity because opposite directions are identified (see the representation of the projective plane in a sphere in the first post). This indicates that the projective variety induced by the cubic meets that induced by the y-axis with equation x = 0 at infinity. Indeed, this makes some intuitive sense: as x becomes very large, it becomes insignificant relative to y = x³ and therefore the point (x,y) is "close" to the y-axis x = 0 (this can also be seen by zooming out a graph of the cubic - the graph eventually becomes nearly indistinguishable from the y-axis). We can also visualize the projective variety yz² - x³ = 0 that extends the cubic on the sphere (see below).

This image shows the cubic curve in the affine plane as well as its projection (via lines through the origin, the center of the sphere) onto the surface of the sphere. It differs slightly from our earlier sphere representation since the plane is below and not above the sphere, but this makes little difference. At the bottom of the sphere, the origin of the plane touches the sphere (which is a point on the curve). At first, the path veers away from the y-axis (the grid line from top to bottom through the origin), but notice how when the curve approaches the equator of the sphere (infinity), it comes back to hover above the y-axis. Images like these help to interpret the results of our algebraic manipulations.

The projective plane has very elegant geometric properties (every two lines in the plane intersect in exactly one point, for example) and gives us a sturdy mathematical grounding for the slippery concept of behavior "at infinity." Generalizations of this concept are crucial in the study of polynomial curves and their corresponding equations.

Sources: http://voltage.typepad.com/.a/6a00e55375ef1c8833014e610f8df7970c-pi

The Projective Plane: An Algebraic Exploration I

This is the second post in a series on projective space. For the first, see here.

The idea of "adding points at infinity" to the plane introduces new behavior to the study of the intersections of lines and curves. Since there are different points of infinity for each direction in the affine plane (as discussed in the last post) and parallel lines intersect at infinity, it is reasonable to suppose that certain lines and curves also intersect at infinity (see below).

For example, the hyperbola above is given by the equation xy = 1. Away from the origin, the two branches of this curve approach the x- and y-axes, defined by the equations y = 0 and x = 0, respectively. Since the distance between the curve and these lines (called asymptotes of the curve) approaches 0 far from the origin, it makes sense to suppose that the hyperbola intersects with these asymptotes at infinity. On the other hand, for other curves that clearly "go off to infinity" like the cubic curve y = x³ shown below, there is no asymptote. What point at infinity, if any, does the cubic intersect?

Answering this question is difficult in our as yet fuzzy picture of the structure of the projective plane. However, the algebraic definition of the projective plane provides the tools necessary for solving this and many other related problems. Introducing this machinery is the purpose of this post.

Lines, parabolas, cubics, hyperbolas and many other curves in the plane may be expressed in the following algebraic form: f(x,y) = 0, where f is a polynomial function of x and y. This means that it is a sum of terms of the form a*xⁱy^j where i and j are nonnegative integers and a is a constant coefficient. For example, the equation for the hyperbola written above may be written xy - 1 = 0 and the equation for the cubic y - x³ = 0. Any curve defined by an equation of this form is known as an affine variety.

The previous post introduced the projective plane as the set of lines through the origin in three-dimensional space. It then illustrated two different ways in which certain representatives may be chosen from the lines to get a "picture" of the projective plane in three-dimensional space. We show that for equations of certain forms, it does not matter which representative we choose from a given line through the origin. First, let P = (x,y,z) be a point distinct from the origin in three-dimensional space (that is, at least one of x, y, and z is nonzero). Then since any two distinct points determine a line, P determines a unique line L through the origin. The point (ax,ay,az) is then on L for any constant a and every point on L is of this form. In other words, only the ratio of the coordinates to one another is required to determine on which line through the origin a given point lies. This fact can more easily be seen in two dimensions, as in the figure below.

The line above has equation y = 2/3*x. It passes through the origin and has slope 2/3, so any point (x,y) for which y/x = 2/3 is on the line (as demonstrated by the construction of a suitable triangle, as above). With this fact in mind, we introduce the concept of homogeneous coordinates. Homogeneous coordinates (x:y:z), where at least one is nonzero, define a point of the projective plane, with the understanding that only the ratio of x, y, and z matters. Thus (1:2:3) = (3:6:9), for example. With these identifications in mind, every point in the projective plane may be assigned homogeneous coordinates (though in many equivalent ways).

Next we consider projective varieties, i.e. certain types of curves in the projective plane. As before, they are defined as the set of points satisfying a certain polynomial equation, but in three variables instead of two: F(x,y,z) = 0. However, in light of the equivalence between points with different x-y-z coordinates, we must consider only polynomial equations that have the same points of the projective plane as solutions for any coordinate representation of the given points. These are called homogeneous polynomials. A polynomial is homogeneous if each one of its terms, or monomials, is of the same degree, meaning that the sum of the exponents in each term are the same. For example, F(x,y,z) = x²yz³ is trivially homogeneous of degree 6 because it has only one term and the sum of its powers are 2 + 1 + 3 = 6. F(x,y,z) = xy² + z³ is homogeneous of degree 3 because the sum of the exponents of the xy² term is 1 + 2 = 3 and is obviously also 3 for the second term, z³. The crucial property of homogeneous polynomials is that if F(x,y,z) = 0, then F(ax,ay,az) = 0 for any constant a:

The crucial fact used in the proof (click to enlarge) is that the exponents of each term (the p's, q's, and r's) must always add up to the same degree n. The aⁿ term can then be factored out, confirming that F(x,y,z) = 0 always implies F(ax,ay,az) = 0. This means that for any point in the projective plane, a homogeneous polynomial that is zero on one representative is zero on all. Conversely, if F(ax,ay,az) = 0, then the same proof (using 1/a) shows that F(x,y,z) = 0 so long as a is not zero. All this manipulation distills down to the following crucial statement: it is meaningful to say that a homogeneous polynomial is zero at a point in the projective plane since any representative gives the same result. We can thus denote projective varieties by the equation F(x:y:z) = 0 in homogeneous coordinates.

It follows that a homogeneous polynomial in three coordinates has a solution set of points (a curve) in the projective plane. These solution sets are the projective varieties. The next post (coming soon) continues to fill in the algebraic picture of the projective plane and relates affine varieties to projective ones, ultimately answering the questions posed at the beginning of this post.

Sources: http://intmstat.com/plane-analytic-geometry/xyis1.gif, http://www.s-cool.co.uk/assets/learn_its/gcse/maths/graphs/algebraic-graphs/g-mat-graph-dia04.gif

The Projective Plane: A Visual Introduction

The statement "any two distinct lines intersect in a point" is almost true in normal plane geometry. The exception, of course, is the case of two parallel lines. However, from real experience we know from the rules of perspective that two parallel lines "converge" very far away, even if we know that they in fact maintain the same distance apart.

From this, we naturally comes the intuition that "parallel lines intersect at infinity." Certainly this tidies up our intersection statement because it provides a way for even parallel lines to intersect. But what does "at infinity" mean? Is there really a "point" there? The notion of projective space makes these ideas explicit and rigorous.

We focus on the (real) projective plane, the extension of the normal plane to include these "points at infinity" where parallel lines intersect. The set of points in the projective plane is defined, somewhat enigmatically, as "the set of lines through the origin in three-dimensional space." Defining each point to be a line in a different space seems extremely confusing at first, but there are multiple ways to visualize this concept.

The first method of visualization illustrates how the projective plane is related to the ordinary plane (sometimes called the affine plane). Consider three-dimensional space with ordinary coordinates x,y, and z as shown. The plane labeled z = 1 contains all points for which the z coordinate is 1, namely all those of the form (x,y,1). Clearly this plane is just like the ordinary two-dimensional plane (under the correspondence (x,y,1) → (x,y)), only embedded in three dimensions, like a flat sheet of paper in our world (but infinite). The dotted line shown that passes through the origin intersects the plane at the particular point (a,b,1). Remembering that the projective plane is meant to be an extension of the affine plane, we identify the dotted line with the point where it intersects the plane. Clearly, for each point in the z = 1 plane, there exists exactly one line through the origin and the given point. This shows how the ordinary plane is a subset of projective space (the set of lines through the origin)!

However, not every line through the origin intersects the plane z = 1. For instance, the x-axis, the y-axis (both shown), and any other line in the plane of these two axes only contain points for which the z coordinate is 0 and can never intersect the plane z = 1 (to be clear, the three-dimensional space considered here does not have its own points at infinity!). Therefore, these lines cannot correspond to points on the ordinary plane. These special lines, in fact, are the points at infinity in the projective plane.

The above visualization illustrates the connection between the projective plane and the affine plane. It also indicates that there are many points at infinity, one for each line through the origin "lying flat" in the xy-plane. However, it fails to indicate how points at infinity are truly the intersections of parallel lines. For this, we use another visualization that chooses different representative points.

Using a sphere (or a hemisphere, to be more precise) to represent the projective plane is just as legitimate as using a plane: all that matters is that there is one point for each line through the origin. It does not matter which points we choose.

In fact, nearly every person is intimately familiar with this representation of projective space! Imagine that it is a clear night and you go out to look at the stars. You catch sight of the familiar constellation Orion, the hunter. The stars marking Orion's shoulders are Betelgeuse and Bellatrix, which we perceive to be neighboring stars that connect to form the figure of Orion. In fact, however, Betelgeuse is between two and three times as distant as Bellatrix. When we look up at the sky, we do not perceive the true three-dimensional space but points of light etched into the inner surface of the celestial sphere passing overhead. Stars in similar directions, regardless of their distances, are projected onto nearby points. This is why the result of treating all points along a line through the origin as equivalent is known as projective space.

It is clear, however, that every line through the origin intersects the sphere at exactly two points, while there can only be one representative for a point of projective space. Thus, by convention we consider only intersections with the upper hemisphere (just as in our example of the night sky - one cannot see stars looking downward!). This leaves only the "horizontal" lines intersecting the equator of the sphere twice. For these, we choose the points of intersection for positive y-values (the area colored dark green above) and finally the x-axis is represented by the dark red point of positive x. The projective plane is therefore the union of the yellow upper hemisphere, the dark green semicircle, and the dark red point. The latter two parts are the points at infinity.

The above image shows how the affine plane (and our first visualization) relate to our second visualization of the projective plane as (part of) a sphere. Lines through the origin (O) and a point in the upper hemisphere intersect the plane to form a one-to-one correspondence. As we would expect, points at infinity correspond to lines through the sphere's equator that are parallel to the plane and are therefore not part of our original affine plane.

Finally, the sphere illustrates how the projective plane solves the motivating problem of parallel lines than began this post.

Two parallel lines in the plane correspond to precisely the same lines in our first visualization, which indeed embeds a "copy" of the affine plane in three-dimensional space. When these parallel line are transferred to the sphere in the same manner that the point was above (remember: each transferred point represents a line through the origin and "transferring" a point is merely choosing a different representative), the figure above is the result. However, it is evident that the resulting arcs on the sphere intersect at the equator (green circle) and we know the equator contains the points at infinity! Though there appear to be two intersections, recall that points diametrically opposite from one another are on the same line through the center, so that these points are identified as one in the projective plane. We have our desired result: two parallel lines intersect in exactly one point.

The next post provides an algebraic description of the projective plane and explores more of its properties.

Sources: Algebraic Curves: An Introduction to Algebraic Geometry by William Fulton, https://www.math.toronto.edu/mathnet/questionCorner/qc_hlimgs1/image87.gif, http://jwilson.coe.uga.edu/EMAT6680Fa11/Chun/Final1/4.png, http://courses.cs.washington.edu/courses/cse557/98wi/readings/xforms/diagram/homogeneous.gif, http://earthsky.org/astronomy-essentials/how-far-is-betelgeusehttp://en.wikipedia.org/wiki/Projective_space