## Archive for **January 2010**

## Fibonacci ties it all together

In the past few posts I have discussed a diverse set of topics, from number representation to recurrence relations, Pythagorean triples.

All of these topics are related, and this is particularly illustrated when we consider the work of Leonardo of Pisa, better known as Fibonacci (from the Latin “de filiis Bonacci”, or “of the family of Bonacci”). Fibonacci was born in 1175, in Pisa, Italy, shortly after the start of the construction of the famous leaning tower. The city of Pisa was a maritime republic which had its own colonies, including Bugia (in modern day Algeria), where Leonardo’s father moved in 1192 to be a clerk in the customs house. It was here that Fibonacci became acquainted with the Hindu numerals and zero, and where his Muslim teacher introduced him to the the great book *Al-Jabr wal-Muqabalah*. Fibonacci subsequently travelled broadly, where he learnt from mathematicians of different cultures. Around 1200 he returned to Pisa and began work on his masterpiece *Liber Abaci*, which was published in 1202, and begins with these words:

“The nine Indian figures are 9 8 7 6 5 4 3 2 1.

With these nine figures, and with the sign 0, which the Arabs call zephyr, any number whatsoever is written”.

This is the earliest known formal mention of the decadic Hindu-Arabic number system in the Western world.

The *Liber Abaci* contains a large collection of problems, some aimed at merchants, but most related to algebra and what would now days be considered number theory. One of these problems concerned the rate of reproduction of rabbits, and how the number of pairs of rabbits grows over successive generations assuming each pair spawns another at each generation. If each pair takes one generation to mature, then the number of adult pairs is given by the sequence:

1, 1, 2, 3, 5, 8, 13, 21, …

which are the now-famous Fibonacci numbers, defined by the recurrence relation:

These numbers are a source of endless fascination, as they appear in various guises throughout nature, art, architecture, and mathematics. For example, the number of spirals of bracts on pineapples and pinecones are Fibonacci numbers, as are the number of branches on some species of trees, the number of ancestors at each generation of male bees, and more. Furthermore, the ratio between consecutive Fibonacci numbers approaches phi, the golden ratio, which again appears throughout art and science. Many of these relationships only began to be noticed in the 1800’s, and it was in the mid-1800’s that the name “Fibonacci numbers” was given them by Edouard Lucas – the inventor of the Tower of Hanoi puzzle. Today they still command attention, so much so that there is a quarterly journal dedicated to their exploration!

Many of these interesting properties of the Fibonacci numbers will be discussed in future posts; for now, I wish to focus on the relationship of the Fibonacci numbers to the Pythagorean triples. Before doing so I need to point out one of the many interesting properties of the Fibonacci numbers; the proof will be left for another day although you may want to try obtain it yourself:

Can you prove the following?

- If we have a succession of four consecutive Fibonacci numbers , then form a Pythagorean triple
- Is it possible to have a triangle whose sides are all
*distinct*Fibonacci numbers? It should be obvious that this is not possible with consecutive Fibonacci numbers, but what if we can choose any Fibonacci numbers?

The first problem is quite easy to prove if we just note that and , and then expand the three operations in the triple in terms of just and :

If we then square these results it is trivial to see that holds.

Interestingly, if we use two consecutive Fibonacci numbers as the coefficients in the Babylonian formulae for Pythagorean triples (i.e. the formulae given by Diophantus), then one of the numbers in the triple is a Fibonacci number. This should be clear from the property mentioned above, which stated that the sum of the squares of two consecutive Fibonacci numbers is a Fibonacci number

For the second problem, assume we have three distinct Fibonacci numbers, , and , ordered by size, so that:

Then:

So:

which contradicts the *triangle inequality* – namely that the sum of any two sides of a triangle must be greater than the third side.

## The Horn of Gabriel

“*And the seventh angel sounded [his horn]; and there were great voices in heaven, saying, The kingdoms of this world are become the kingdoms of our Lord, and of his Christ; and he shall reign for ever and ever.”* (Revelations 11.15, King James Edition)

In Christian and Islamic folklore, it is the angel Gabriel who is considered to be the seventh angel, who announced the coming of judgement day. An angel with such a huge responsibility clearly needs an instrument worthy of the task, and indeed there is one: Gabriel’s horn, also known as Torricelli’s trumpet, after its discoverer, Evangelista Torricelli, a student of Galileo. Gabriel’s horn has infinite surface area but finite volume, and is described the rotating the curve for around the axis.

It is easy to see that this shape, which extends to infinity along the positive axis but gets thinner and thinner, must have infinite surface area. It is less obvious that it has finite volume, although this can be shown with elementary calculus (if you’re unfamiliar with the calculus needed for surface area of revolution and solid volume of revolution, just bear with me).

The volume is given by:

While the surface area is given by:

Clearly in the limit, we have:

At the time that Torricelli discovered this (1641), calculus had not yet been invented, and he obtained the results by a technique developed by his friend Cavalieri, called the summation of plane slices – essentially a technique similar to the calculus of limits using successively smaller slices. This itself required a leap of faith at the time and only became solidified later, as the idea of limits took hold, and the concept of infinitely many infinitely thin slices was given a rigorous mathematical foundation.

Torricelli’s trumpet caused some consternation and disbelief – in 1672, for example, Thomas Hobbes, the English philosopher, claimed that to believe Torricelli would be madness. It appears to result in a paradox, the *painter’s paradox*: if the volume is finite, the horn can be filled with a finite amount of paint, and yet to cover its interior surface would require an infinite amount of paint! Before reading on, can you resolve this paradox?

The paradox comes from confusing our mental model of real paint with “mathematical” paint. Real paint has a finite thickness – say the thickness of a paint molecule. At some point the trumpet becomes thinner than this, and so with real paint we could neither fill the trumpet nor cover its surface. The only paint that could do this would be “mathematical” paint that has infinitely small thickness. A finite amount of infinitely thin paint could cover an infinite surface.

While he made a number of contributions to mathematics, Torricelli is more well known for his contributions to physics. He was the first scientist to create a sustained vacuum and suggested the experiments that led to the invention of the barometer; later he went on to use the much more effective mercury in place of water. In his honour the vacuum in a barometer is known as a Torricelli vacuum, and the Torr is a measure of vacuum. He gave the first scientific explanation for wind, which he recognized as being caused by variations in air density caused by temperature differences. He was a skilled lens maker and his telescopes and microscopes provided much of his income. Sadly, he contracted typhoid and died at the age of 39 in 1647; not all his writing and research was preserved, and had he lived longer he may well have been credited with being the inventor of integral calculus; he was well on the way to understanding its principles.

"*We live submerged at the bottom of an ocean of air*." – Evangelista Torricelli, 1644.

## More on Pythagoras

Pythagoras is known for two great contributions to mathematics – he established the need for formal proofs instead of just conjecture and rules of thumb, and he established the existence of the irrationals. In popular culture of course, Pythagoras is more well known for the Pythagorean theorem – that the square of the hypotenuse of a right angled triangle is the sum of the squares of the other two sides – but this was one of the oldest known results in mathematics and in fact predates Pythagoras by as much as a thousand years. Nonetheless, Pythagoras provided a formal proof, and the result led him to ask whether there were rational numbers that worked in the case where the hypotenuse had the length two. That is, what was the fractional representation of the square root of two? Pythagoras managed to show there was none, leading to the discovery of the irrational numbers.

His proof was quite simple. Assume that can be expressed as a fraction of two whole numbers and. Assume these are the two smallest such whole numbers – that is, they have no common divisor allowing the fraction to be further reduced. Then:

so:

The right hand side is even, which means is even, and thus must be even, or for some. But then:

so:

So the left hand side is even, and thus must be even. But if both and are even, then they have a common factor 2, which contradicts the assumption that they were the smallest such numbers.

There are, of course, infinitely many cases where the Pythagorean triangles have sides with rational length, and for that matter, integer length. In a recent post I mentioned the method described by Diophantus that inspired Fermat’s last theorem. It is easy to derive this method. Assume and are relatively prime, and that is odd. Then:

Thus. So we can write for some positive. Then:

So:

From this we can see must be even. Let; then:

So:

Thus is even, and as we assumed is odd, must be even. Since the sum of an even and an odd is an odd, must be odd and so must be odd.

So is even, and and are odd. We can write and for some integers and. Then:

or:

Simplifying:

So must be a perfect square. We can write and. Thus:

So:

So we have shown that a Pythagorean triple takes the form:

## Much Ado about Nothing

Many people have heard that the number zero was introduced later than the other digits. Upon hearing this it seems fantastical – how could people have managed even elementary arithmetic without zero? However, it is not the concept of “nothing” that was missing, but rather the use of a zero in other places when representing or recording numbers. For example, in the number 101, zero is used as a separator, and it is this concept that was lacking in early number systems.

We are used to our modern decimal representation where each digit represents units, tens, hundreds, thousands, etc. Not all systems worked that way – the Roman system is a well-known example of a different approach. Throughout history there have been many alternative ways of recording numbers. In ancient China and the South Sea islands knots in string were used. Creating notches in sticks is another (the word *score* has its roots in this method, as do the Roman numerals I, II, III). Contracts were often formalized by scoring a piece of wood with an appropriate count then splitting it in two with each party taking half; the halves would be matched up later to ensure no alteration. In Britain such Exchequer tallies were used from the 12th century and were legally binding until 1826; in 1834 the burning of the no-longer required tallies started a fire that destroyed the old Parliament buildings.

The use of simple score marks developed with writing into more sophisticated forms. Different symbols were used for values of different magnitudes, and they were repeated as necessary (e.g. III for 3, and CCC for 300 in Rome). The use of subtractive methods (IV instead of IIII) was a later innovation.

This simple grouping approach evolved into a multiplicative approach, where instead of repeating a symbol it was preceded with a count. For example, if that were applied to Roman numbers we might write 3C3V for 315. A real example is the Chinese-Japanese number system.

A different approach is a ciphered approach, where there are separate symbols for the ten symbols 0 through 9, then the nine symbols 10 , 20, 30 through 90, then 100, 200, 300 through 900, and so on. Examples of this are the Hindu Brahmi and the Egyptian hieratic and demotic systems. Variations on this, where alphabetic characters were repurposed for numbers, are the Greek numerals, Hebrew, Syrian and Gothic systems.

Unfortunately, many of these systems are ill-suited for calculations, as anyone who has attempted math on Roman numerals will know. Performing arithmetic was thus considered an advanced art and required the assistance of tools such as the abacus. It was only with the spread of the Hindu-Arabic decadic positional system around 800AD that arithmetic operations became easy to perform without assistance. It was positional systems that necessitated the introduction of a symbol to represent no value at a particular position, to distinguish, for example, 31 from 301. The lack of a zero made the earlier positional systems such as the Babylonian sexagesimal system highly ambiguous, although the Mayans developed an early positional representation system that included a zero, which may account for why their mathematical calculations were considerably more advanced and accurate than other cultures.

The spread of the Hindu-Arabic system was largely facilitated by the translation into Latin of the text *Al-Jabr wal-Muqabalah* (hence: algebra) by the great Arab mathematician Mohammed ibn Musa al-Khowarizmi. The use of this system became known as algorism (leading to the modern word algorithm) , but its adoption took time; the abacists who adhered to the Roman system resisted the algorismic system and it took until the 16th century for it to become predominant in Europe.

## Primal Soup

Number theory really began with Euclid, around 300BC, in books 7 through 9 of his masterwork, *The Elements*. It is here that we find the original definitions of odd and even numbers, prime and composite numbers, perfect numbers (numbers which are the sum of their factors, e.g. 6 = 3 + 2 + 1), and more. But the greatest achievements of all were his proofs that composite numbers are the products of primes, that this factorization is unique, and that there are an infinity of primes. Most introductory algebra or number theory classes cover these three great proofs, but they are worth revisiting for those who may have forgotten.

Before doing so, it is worth revisiting Euclid’s clever algorithm for calculating the greatest common divisor (GCD) of two numbers. We made use of this when solving the Monkey and Coconuts puzzle.

We divide the smaller number into the larger and keep track of the remainder. Then we divide that remainder into the smaller number to get a second remainder, then divide the second remainder into the first remainder to get a third remainder, and so on. Eventually we get a remainder of zero; the remainder just before this is the GCD. If this happens to be one, we say the numbers are coprime. For example, consider 64 and 10:

- 64 = 10 x 6 + 4
- 10 = 4 x 2 + 2
- 4 = 2 x 2 + 0

So the GCD is 2.

For another example, consider 77 and 65:

- 77 = 65 x 1 + 12
- 65 = 12 x 5 + 5
- 12 = 5 x 2 + 2
- 5 = 2 x 2 + 1
- 2 = 1 x 2 + 0

So the GCD is 1 and the numbers are coprime.

In the proofs below we make use of a special case of Bézout’s identity, which states that if two numbers and have a GCD, then there exists some and such that. In our case we care about the situation where and are coprime, so that there exists some and such that. We aren’t proving that here but it is exactly equivalent to solving the Diophantine equations we solved for the Monkey and Coconuts problem (where and where the number of coconuts at the start and end).

**Proof that Composite Numbers have Prime Factors**

Let be a composite number. Then by definition must be divisible by some smaller number. If is prime we are done; if is not prime it is must be divisible by some smaller number, and so on. Continuing in this way, we find:

This sequence must terminate with a prime number in the last position before 1; if not, that is, if each successive number is still composite, then the series is infinite, but we cannot have an infinite series of decreasing whole numbers.

**Prime Factorization Theorem (aka the Unique Factorization Theorem aka the Fundamental Theorem of Arithmetic)**

There are two steps: first we show that if a prime divides a composite, then must divide at least one of or. Assume does not divide – then the GCD (greatest common divisor) of and must be 1, as is prime. By Bézout’s identity, there must be some integers and satisfying. Multiplying both sides by gives, and both terms on the left hand side are products of, thus must be a product of.

Now for the main proof. Let be the smallest natural number that can be written as a product of prime numbers in more than one way (ignoring ordering, of course). Let one factorization be and another be. The previous result proves that divides either or. Because both and must have unique prime factorizations, must equal some. If we then remove and we have two different factorizations of a number which is smaller than, which contradicts our assumption that is the smallest such number.

**Proof of the Infinitude of the Primes**

Assume the set of primes is finite, given by. Consider the number . This is not divisible by any of the primes in the set; it always leaves a remainder of 1. Therefore it is either itself prime or has other prime divisors not in the set, and so the set is incomplete.

Further reading: William Dunham’s Journey through Genius: The Great Theorems of Mathematics has two chapters on Euclid’s elements and covers much of this material (although he omits the proofs apart from the last one). Proofs from THE BOOK has about six different proofs of the infinitude of the primes, each using a different branch of mathematics, from algebra to set theory to topology. To dust off my rusty memory of these proofs I had to pull out my well-thumbed college textbook Rings, Fields and Groups: An Introduction to Abstract Algebra, but while it is a great text I wouldn’t recommend it to those faint of heart!

## Archimedes counts the sand

In a previous post I described the Babylonian/Sumerian sexagesimal (base 60) counting system. Unlike this system, most cultures adopted a base 10 counting system due to the natural inclination to count with the fingers (leading to the term *digits*). Less common were quinary (base 5) systems, but vigesimal (base 20) were not unusual – for example, this was widespread in native American culture, including (with a novel variation) the Mayans. Duodecimal (base 12) has also played a role; we still have remnants in the groupings of dozens and gross.

Once the numbers in the base group are exceeded, we need to group to represent larger numbers – for example in decimal we have units, tens, tens of tens (hundreds), and so on. The Mayans used a novel variation where the second grouping only went up to 18, although after this the groupings reverted to base 20 again. This means the second order group represents numbers up to 360 rather than 400, and may relate to the Mayan calendar of 18 months of 20 days plus 5 extra days.

The larger groupings have names that are often quite recent introductions to language; while the term *hundred* can be traced back to a root meaning *ten times (ten)*, the word *thousand* has no clear relation to the roots of Indo-European languages and is likely quite a late construction, seemingly from an early Germanic term meaning *great hundred*. An exception was the Hindus who seemed attracted to large numbers; there is a story from the life of the Buddha which mentions numbers up to. The Greeks typically stopped at *myriad* (ten thousand), and for a long time the Roman number system stopped at 100,000; the term for a *million* appeared around 1400AD in Italy. Numbers larger than a million have appeared so recently in European language that there is no common agreement – a *billion* in Europe is while in America it is (called a *milliard* in Europe), and things get worse for trillion and quadrillion.

One of the first known efforts to systematize the number system to encompass large numbers is Archimedes’ *The Sand Reckoning*, a treatise addressed to his relative King Gelo of Syracuse, in which Archimedes constructs a systematic method for representing arbitrarily large numbers while addressing the problem of estimating the number of grains of sand in the universe. In his preface, he stated “There are some, King Gelo, who think that the number of the sand is infinite in multitude; and I mean by the sand not only that which exists about Syracuse and the rest of Sicily but also that which is found in every region whether inhabited or uninhabited.” Archimedes went on to use myriads raised to the the power of myriads, successively, to represent the very large numbers he needed for his calculations. In the process of doing this Archimedes discovered and proved the law of exponents:

Archimedes had to estimate the size of the universe. He assumed a heliocentric model, with the earth revolving around the sun, the sun at the center, and the stars at the periphery. By his estimates the universe was about two light years across. Given we now know the next closest star to our sun is about 4 lights years away this was quite impressive for the time!

## More on Diophantus and Fermat

In a previous post I wrote about how Fermat scribbled his famous “last theorem” in the margin of Diophantus’ *Arithmetica*. This is called Fermat’s last theorem not because it was the last thing Fermat wrote but because of all the incomplete theorem’s we know were left by Fermat it was the last to be proved, taking about 350 years.

The section of the book where Fermat wrote his comment was on finding *Pythagorean triples*: square numbers whose sums also form squares. Such numbers can be the sides of Pythagorean (right-angled) triangles, the most well know being 3-4-5.

The *Arithmetica* was a book of computational methods rather than theoretical mathematics. In modern terms we would call it a book of numerical algorithms. Much of the material was not invented by Diophantus but was collected by him. This includes his method for finding Pythagorean triples, which was as follows. Take any two whole numbers and. Then the following three numbers are the sides of a Pythagorean triangle:

Furthermore, any such triple can be multiplied by a constant to get another triple (e.g. the triple 3-4-5 can be multiplied by 3 to get the triple 9-12-15, etc).

Fermat’s theorem asserts that while there are an infinite number of Pythagorean triples, there are no solutions in whole numbers for higher powers. Fermat did leave a proof for the fourth power. Euler proved the theorem for the third power. Dirichlet proved the theorem for fifth and 14th powers. Lame and Kummer managed to prove the theorem for all powers up to 100 except for 37, 59 and 67. By 1980, the theorem had been proven for all powers up to 125,000!

It took some modern developments in elliptic functions to proceed further. Elliptic functions are functions in two unknowns where one unknown is squared and the other cubed (e.g. ). It was found that if Fermat was wrong, and there is a solution for some power higher than two, then that solution describes a very unusual elliptic curve, so unusual it seems unlikely it could exist.

In 1986 Kenneth Ribet showed that such an elliptic curve would violate the 1955 Taniyama-Shimura conjecture, which claims that every elliptic curve is associated with a modular function. While the Taniyama-Shimura conjecture was not itself proven this did provide a link between two fields of mathematics, and it was this conjecture that was ultimately proven by Andrew Wiles and a former student in 1993 and 1994, thus finally proving Fermat correct.

If Fermat really did have a proof, though, then there is a much simpler proof still waiting to be found…