Category Archives: Numbers

What are the p-adic numbers?

The p-adic numbers are a completion of rational numbers with respect to the p-adic norm and form a non-Archimedean field. They stand in contrast to the real numbers, which are a completion of the rationals with respect to absolute value and which do respect the Archimedean property. The p-adic numbers were first described in 1987 by Kurt Hensel and later generalized in the early 20th century by József Kürschák which paved the way for a myriad of mathematical work involving the P-adics in the just over a century since.

To start talking about the p-adics it makes sense to start with the Archimedean property, which as mentioned above the p-adics do not adhere to.  First we need an absolute value function or valuation, ||, which is basically a function that gives some concept of magnitude to an element of a field (so it’s a mapping from a field to the positive real numbers). Given this, the zero element should map to zero and the valuation of the product of two elements should be the same as the product of the valuation of each element individually. The last condition (which determines whether or not the valuation is Archimedean) is that if the norm of an element is less than or equal to 1, then the norm of 1 plus that element is less than some constant, C, which is independent of the choice of x. If the last condition holds for C equal to 1, then the valuation satisfies the ultrametric inequality: the valuation of 2 elements is less than or equal to the maximum of the valuation of each element. If the ultrametric inequality is satisfied then the valuation is non-Archimedean. Otherwise it is an Archimedean valuation.

While this is a bit opaque, it makes more sense now moving into defining Archimedean fields: a field is Archimedean if given a field with an associated valuation and a non-zero element, x, of that field, then there exists some natural number n such that |Σk=1nx|>1. Otherwise,  the field is non-Archimedean and the ultrametric inequality holds. Basically what this means is that if we can measure distance and we are living in a nice Archimedean world, if we walk forward we can go as far as we want. While if we were to live in a non-Archimedean world and we try to walk forward we would at best stay in place and possibly move backward.

Now that that’s out of the way and (hopefully) the weirdness of a non-Archimedean world has been established, it’s time to talk about the p-adics. Any non-zero rational number, x, may be expressed in the form x ,where a and b are relatively prime to some fixed prime p and r is an integer. Using this, the p-adic norm of x is defined as |x|=p-r , which is non-Archimedean. For example, when p=3, |6|=|2*3|=1/3, |9|=|32|=1/9 and |6+9|=|15|=|3*5|=1/3 or when p=5 , |4/75|=|4/(52*3)|= 25, |13/250|=|13/(2*53)|=125 while |4/75 + 13/250|=|17/325|=|17/(52*13)|=25. So now that we have this we can proceed identically as when constructing the real numbers using the absolute value and define p as the set of equivalence classes of Cauchy sequences with respect the p-adic norm. After some work it can be shown that every element in pcan be written uniquely as Σk=makpk,where am does not equal zero and m may be any integer.

The most common use of p-adics I found was in showing the existence (or lack thereof) of rational or integer solutions to problems. For example, the Hasse principle (also known as the local-global prinicipal ) was discovered by Helmut Hasse in the 1920’s and attempts to give a partial converse of the statement that if a polynomial of the form Σaijxiyj+Σbixi+c=0 has a rational solution then it has a solution for all expansions of Q. The Hasse principal asserts that if such a polynomial has a solution in R and every Qp then it has solution in Q. An example of this is x2-2=0, which has (irrational) solution square root of 2 in R. However, it does not have solution in Q5 , and so by the Hasse principal it does not have a solution in Q, which we know to be true. Another use of the P-adics which is fairly interesting is in transferring standard real or complex polynomial equations to their tropical (the semi ring of the reals with the addition of an infinity element under the laws of composition addition and min (or max)) polynomial counterpart, a process which runs into issues due to the necessity of the ultrametric inequality.

Sources:

http://www.cut-the-knot.org/blue/LocalGlobal.shtml

http://en.wikipedia.org/wiki/P-adic_number

http://mathworld.wolfram.com/p-adicNumber.html

http://mathworld.wolfram.com/p-adicNorm.html

http://mathworld.wolfram.com/Valuation.html

http://www1.spms.ntu.edu.sg/~frederique/antchap5.pdf

http://www.math.ucla.edu/~i707107/HasseMinkowski.pdf

Leonardo of Pisa – The Great Fibonacci

Figure 1-Fibonacci. Image: Public domain, via Wikimedia Commons.

Most mathematically inclined people are familiar with the famous and unique Fibonacci sequence. Defined by the recurrence relation (*) Fn=Fn-1+Fn-2 with initial values F1=1 and F2=1 and (or sometimes F0=1 and F1=1), the Fibonacci sequence is an integer sequence (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …) with many remarkable mathematical and real world applications. However, it seems that few are as well informed on the man behind this sequence as they are on the sequence itself. Did you know that Fibonacci didn’t even discover the sequence? Of course not! Predating Fibonacci by almost a century, the so called “Fibonacci sequence” was actually the brainchild of Indian mathematicians interested in poetic forms and meter who, through studying the unique arithmetic properties of certain linguistic sequences and syllable counts, derived a great deal of insight into some of the most fascinating mathematical patterns known today. But with a little bit of time (few hundred years), some historical distortion, inaccurate accreditation[1], and a healthy dose of blind western ethnocentrism and voila! Every high school kid in America now thinks there is a connection between Fibonacci and pizza. Or is it Pisa? (That’s a pun, laugh.) While often given more credit than deserved for the “discovery” of the sequence, Fibonacci was nonetheless an instrumental player in the development of arithmetic sequences, the spread of emerging new ideas, and in the advancement of mathematics as a whole. We thus postpone discussion of Fibonacci’s sequence – don’t worry, we shall return – to examine some of the other significant and often overlooked contributions of the “greatest European mathematician of the middle ages.”[1]

Born around the year 1175 in Pisa, Italy, Leonardo of Pisa (more commonly known as Fibonacci) would have been 840 years old this year! (Can you guess the two indexing numbers between which Fibonacci’s age falls?[2]) The son of a customs officer, Fibonacci was raised in a North African education system under the influence of the Moors.[3] Fibonacci’s fortunate upbringing and educational experience allowed him the opportunity to visit many different places along the Mediterranean coast. It is during these travels that historians believe Fibonacci may have first developed an interest in mathematics and at some point come into contact with alternative arithmetic systems. Among these was the Hindu-Arabic number system – the positional number system most commonly used in mathematics today. It appears that we owe a great deal of respect to Fibonacci for, prior to introducing the Hindu-Arabic system to Europe, the predominant number system relied on the far more cumbersome use of roman numerals. It is interesting to note that while the Hindu-Arabic system may have been introduced to Europe as early as the 10th century in the book Codex Vigilanus, it was Fibonacci who, in conjunction with the invention of printing in 1482, helped to gain support for the new system. In his book Liber abbaci[4], Fibonacci explains how arithmetic operations (i.e., addition, subtraction, multiplication, and division) are to be carried out and the advantages that come with the adoption of such a system.

Figure 2-Golden spiral. Image: Weisstein, Eric W. "Golden Spiral." From MathWorld--A Wolfram Web Resource.

Figure 2-Golden spiral. Image: Weisstein, Eric W. “Golden Spiral.” From MathWorld–A Wolfram Web Resource.

Whereas the number system most familiar to us uses the relative position of numbers next to each other to represent variable quantities (i.e., the 1’s, 10’s, 100’s, 1000’s, … place), Roman numerals rely on a set of standard measurement symbols which, in combination with others, can be used to express any desired quantity. The obvious problem with this approach is that it severely limits the numbers that can be reasonably represented by the given set of symbols. For example, the concise representation of the number four hundred seventy eight in the Hindu-Arabic system is simply 478 in which “4” is in the hundreds place, “7” is in the tens place, and “8” is in the ones place. In the Roman numeral system, however, this same number takes on the form CDLXXVIII. As numbers increase arbitrarily so does the complexity of their Roman numeral representation. The adoption of the Hindu-Arabic number system was, in large part, the result of Fibonacci’s publications and public support for this new way of thinking. Can you imagine trying to do modern mathematical analysis with numbers as clunky as MMMDCCXXXVIII??? Me either. Thanks, Fibonacci!

Fibonacci’s other works include publications on surveying techniques, area and volume measurement, Diophantine equations, commercial bookkeeping, and various contributions to geometry.[4] But among these works nothing stands out more than that of Fibonacci’s sequence – yes, we have returned! Among the more interesting mathematical properties of Fibonacci’s sequence is undoubtedly its connection to the golden ratio (shall be defined shortly). To illustrate, we look momentarily at the ratios of several successive Fibonacci numbers. Beginning with F1=1 and F2=1 we see that the ratio F2/F1=1. Continuing in this manner using the recurrence relation (*) from above or any suitable Fibonacci table we find that F3/F2=2, F4/F3=3/2, F5/F4=5/3,F6/F5=8/5, F7/F6=13/8, F8/F7=21/13, … As the indexing number tends to infinity, the ratio of successive terms converge to the value 1.6180339887… (the golden ratio) denoted by the Greek letter phi. We may thus concisely represent this convergent value by the expression as the lim n–> infinity (Fn+1/Fn). Studied extensively, the golden ratio is a special value appearing in many areas of mathematics and in everyday life. Intimately connected to the concept of proportion, the golden ratio (sometimes called the golden proportion) is often viewed as the optimal aesthetic proportion of measurable quantities making it an important feature in fields including architecture, finance, geometry, and music. Perhaps surprisingly, the golden ratio has even been documented in nature with pine cones, shells, trees, ferns, crystal structures, and more all appearing to have physical properties related to the value of (e.g., the arrangement of branches around the stems of certain plants seem to follow the Fibonacci pattern). While an interesting number no doubt, we must not forget that mathematics is the business of patterns and all too often we draw conclusions and make big picture claims that are less supported by evidence and facts than we may believe. There is, in fact, a lot of “woo” behind the golden ratio and the informed reader is encouraged to be weary of unsubstantiated claims and grandiose connections to the universe. It is also worth mentioning that, using relatively basic linear algebra techniques, it is possible to derive a closed-form solution of the n-th Fibonacci number.

Figure 3-Computing the 18th Fibonacci Number in Mathematica.

Figure 3-Computing the 18th Fibonacci Number in Mathematica.

Omitting the details (see link for thorough derivation), the n-th Fibonacci number may be computed directly using the formula Fn=((φ)(n+1)+((-1)(n-1)/(φ)^(n-1))/((φ2)+1).[5] While initially clunky in appearance, this formula is incredibly useful in determining any desired Fibonacci number as a function of the indexing value n. For example, the 18-th Fibonacci number may be calculated using F18=((φ)(18+1)+((-1)(18-1)/(φ)^(18-1))/((φ2)+1)=2584. Comparing this value to a list of Fibonacci numbers and to a Mathematica calculation (see picture above), we see that the 18-th Fibonacci number is, indeed, 2584. Without having to determine all previous numbers in the sequence, the above formula allows us to calculate directly any desired value in the sequence saving substantial amounts of time and processing power.

From the study of syllables and poetic forms in 12th-century India to a closed-form solution for the n-th Fibonacci number via modern linear algebra techniques, our understanding of sequences and the important mathematical properties they possess is continuing to grow. Future study may reveal even greater mathematical truths whose applications we cannot yet conceive. It is thus the beauty of mathematics and the excitement of discovery that push us onward, compel us to dig deeper, and to learn more from the world we inhabit. Who knows, you might even be the next Leonardo of Pizza – errrrr Pisa. What patterns will you find?
[1] French mathematician Edouard Lucas (1842-1891) was the first to attribute Fibonacci’s name to the sequence. After which point little is ever mentioned of the Indian mathematicians who laid the groundwork for Fibonacci’s research.

[2] Answer: n=15 –> 610 and n=16 –> 987.

[3] Medieval Muslim inhabitants of the Maghreb, Iberian Peninsula, Sicily, and Malta.[2]

[4] Translation: Book of Calculation[3]


Bibliography

 [1] Knott, Ron. Who Was Fibonacci? N.p., 11 Mar. 1998. Web. 27 Apr. 2015.

[2] “Moors.” Wikipedia. Wikimedia Foundation, n.d. Web. 27 Apr. 2015.

[3] Leonardo Pisano – page 3: “Contributions to number theory”. Encyclopædia Britannica Online, 2006. Retrieved 18 September 2006.

[4] “Famous Mathematicians.” The Greatest Mathematicians of All Time. N.p., n.d. Web. 28 Apr. 2015.

 [5] Grinfeld, Pavel. “Linear Algebra 18e: The Eigenvalue Decomposition and Fibonacci Numbers.” YouTube. YouTube, 2 Dec. 2014. Web. 28 Apr. 2015.

 Figure 1: Fibonacci. Digital image. Wikimedia Foundation, n.d. Web. 27 Apr. 2015.

Figure 2: Golden Spiral. Digital image. Mathworld. Wolfram, n.d. Web. 1 May 2015.

Figure 3: Ross, Andrew Q. Closed-Form Computation of Fibonacci. Digital image. Mathematica, 28 Apr. 2015. Web. 28 Apr. 2015.

Convergence of a Divergent Series and other Tests

In class we have been toying with the idea of classifying diverging infinite series, such as the sum: Σ k (k = 1,) = 1 + 2 + 3 + … which, as we add it up, continues on to infinity. We also messed around with some series notations and came to a conclusion that the sum adds up to -1/12. Now, I have no intention to claim, nor prove, that it equals -1/12. In fact, I would like to do the opposite; I would like to show that it in no way converges. If an infinite series converges, that means it sums up to a real number s: Σ ak = s. Likewise, an infinite series diverges if the sum of the series equals ±∞ or it does not add to any value. There are a few methods I will use to prove that this series diverges, and these methods can also be used to determine whether any infinite series converges or diverges.

The first test I want to look at is the Root Test. In this test, we take the sequence ak raise it to the power 1/k, and take the limit of that as k→∞. If this limit is greater than 1, the series diverges; if the limit is less than 1, it converges. For the sum of all integers, that gives us limit as k→∞ of k(1/k) . As k→∞, limit of k(1/k) → 1. Unfortunately the limit equals 1, which means it is inconclusive; there is a chance that this does indeed sum up to -1/12. Let’s leave the score at 0-0.

I will now put the series through the Ratio Test. It is called the Ratio Test because we take a ratio of the k+1 term divided by the k-th term and take the limit of that as k→∞: the limit of ak+1/ak. Similar to the Root Test, if the limit is greater than one it diverges, and if the limit is less than 1 it converges. For the dubious series which is under examination, that limit (k+1)/k, and as k→∞ the limit equals 1. Once again, this test is inconclusive. The score is still 0-0.

Now it’s time to get serious; so far every test I’ve done has been disappointingly empty of an answer. In this test if a series bk > ak and bk converges, then ak must also converge and if bk < ak and bk diverges, then ak diverges as well. My claim is that Σ k (k = 1,∞) diverges and now I will compare it with a series Σ 1 (k = 1,n) = n. We can see that 1+1+1+… grows much more slowly than 1+2+3+… thus we can use it as a comparison. By another test, the Term Test, if the series converges then lim an = 0. The series must diverge then if the limit doesn’t equal 0. The limit of 1 as n→∞ = 1 ≠ 0, thus the sum of 1 on (k=1,∞) diverges. Since Σ 1 (k = 1,∞) < Σ k (k = 1,∞), the latter series must also diverge. Now the score is 1 for divergence, and 0 for -1/12.

While it can now be seen that Σ k (k = 1,∞) does indeed diverge, the comparison test relies on having knowledge that a similar infinite series will either converge or diverge. In this case, I have to know that Σ 1 (k = 1,∞) diverges before I can compare it to the original series. I used the Term Test to show that Σ 1 (k = 1,∞) diverged, but I can also use it to show that Σ k (k = 1,∞) diverges. The limit as n→∞ of k = ∞, and by the Term Test diverges. The problem with the Term Test is that the limit ak can be equal to zero, but the series can still diverge. Therefore, this test is only useful if the limit does not equal 0 or to insure that a converging series does indeed converge.

By both the Term and Comparison tests, I was able to show that Σ k (k = 1,∞) diverges and is not equal to -1/12. In class though, we determined that the infinite series itself doesn’t sum to a negative number, there is no possible way that adding large positive whole numbers together would result in a negative rational number, but rather -1/12 represented a value or categorization of the infinite sum Σ k (k = 1,∞). How did this number come about? The idea is definitely not of “fringe mathematics” and has some excellent arguments. The idea stems from Σ (-1)k (k = 0,∞) = 1 – 1 + 1 – 1 + … The mathematician Srinivasa Ramanujan gave this sum a “value” of ½, since it seems to jump between one and zero equally, with ½ as the average.

The second sum Σ k(-1)k-1 (k = 1,∞) = ¼ as this sum added to itself equals Σ (-1)k (k = 0,∞). That is 1 – (2 – 1) + (3 – 2) + … = 1 – 1 + 1 – 1 + … Finally, Σ k (k = 1,∞) – 4(Σ k (k = 1,∞)) = 1 + (2 – 4) + 3 – (4 – 8) + … equals 1 – 2 + 3 – 4 + … = Σ k(-1)k-1 (k = 1,∞), or rather -3(Σ k (k = 1,∞)) = ¼ Σ k (k = 1,∞) = -1/12.

Ramanujan discovering the value -1/12 for the the infinite series ak = k. Image: Srinivasa Ramanujan via Wikimedia Commons.

The specific stipulation given is that the series must go to its limit. The partial summations of any of these series will produce a number unlike the total summation. For the majority of mathematics, to say Σ k (k = 1,∞) = ∞ makes more sense and requires significantly less head-scratching than -1/12.

There is one more test for convergence that I did not talk about, as the infinite series I was examining did not apply, and that is the Integral Test. For Σ ak, the function f(k) = ak. The reason why I could not apply it is because it only works with positive, non-increasing functions bounded on [1,∞). If the integral of f(x) is a real number, then the series converges, whereas if that same integral diverges, then the series diverges. The first case I will look at is Σ 1/k (k = 1,∞), where f(x) = 1/x and is a positive, non-increasing function. The integral of 1/x = log(x) evaluated from 1 to ∞. This integral turns out to diverge, and therefore the series also diverges. The second case is similar: Σ 1/k2 (k = 1,∞), where f(x) = x-2. The integral of 1/x2 = -(1/x) evaluated over the same interval. The sum of these two bounds is 0 – (-1) = 0 + 1 = 1. Since the indefinite integral converges, the series also converges.

These tests help determine whether a series converges or not. I used them to prove with basic mathematics that Σ k (k = 1,) diverges, rather than converging on a negative rational number. While the values given to divergent indefinite series can provide an idea of how they relate to each other, they require a fair amount of assumption and a lot of counterintuitive work to calculate. It is far easier and more practical to state that Σ k (k = 1,) diverges.

Sources:

http://www.lemiller.net/media/classfiles/notes.pdf (Foundations of Analysis by Joseph L. Taylor)

https://www.math.hmc.edu/calculus/tutorials/convergence/

http://mathworld.wolfram.com/RatioTest.html

http://en.wikipedia.org/wiki/Series_%28mathematics%29

http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

http://en.wikipedia.org/wiki/Srinivasa_Ramanujan

Drop the Base

30957385_bfb4b7fb79_m

A demonstration of exactly how a shift of base can change our perception of time. Image: Jeremy Keith via flickr.

As a kid, when we were first introduced to numbers, they were just something we memorized, learned to accept, and started using on a regular basis. While this seems almost second nature to most of us, there was a time where the idea of a number system was a new thing and, like all new things, it was discovered multiple times by different people who had different setups. One of the more interesting areas of variation between different number systems would be the base that different number systems used.

Before going into detail about what a base is, it is important to understand that base systems are primarily used by number systems which also use position to determine how large a number is. For example, the Arabic numeral system is positional because I can use the same symbol in a different position to change the value of the number. While 01 is only the value one in this system, by switching these numbers around to 10, I have changed the value now to ten. This is different from something like the Roman numeral system which, for the most part, wouldn’t be considered a positional system because in two different numbers, like X and XIII, the value of the symbol X doesn’t change.

Now, what does this have to do with the base of a number system? The thing is, the base of a positional number system is the number of different symbols you can have in any single position. For example, the Arabic numeral system is base 10 because we can have ten different symbols in a single position (1, 2, 3, 4, 5, 6, 7, 8, 9, 0). In addition to defining how many different symbols you can have in any one position, the value of the base will also affect how much of a change in value a symbol will have based on its position. As I had mentioned earlier, different number system have different bases. The primary reason why would most likely be just because they may have had a different system for counting which lead to that decision. Having a base 10 system is the more common one and a lot of people give credit to that due to the fact that the average number of fingers we have on our hands combined is ten and people like to count using their fingers. On the other hand, the Mayans had a numeral system which consisted of base 20. Unlike most people from Europe, the Mayans wouldn’t wear shoes which meant they could count using ten fingers and ten toes. Even the Babylonian’s had a numeral system with base 60. I honestly couldn’t say why but I am sure they had a good reason for doing so.

Even current day computers use a different base than 10. Instead, computers count using base 2 which means they can only have a 0 or 1 in any position. How can something like this work? The reason why different numeral systems can have different bases is because all positional systems use mathematics in combination with the base size to determine how important a certain symbol is based on its position. This means that it is easy to convert from any base system into a different one. For example, if I want to convert the binary number (100010) into a base 10 number, all I need to do is figure out the base 10 value at each position and add them together. Since this is base 2, every position will be multiplied by 2i with i being the current position. This means:

100010 -> 1*25 + 0*24 + 0*23 + 0*22 + 1*21 + 0*20 -> 1*32 + 0*16 + 0*8 + 0*4 + 1*2 + 0*1 -> 32 + 2 = 34

To make things even more bizarre, a base can be found in more than just numeral systems. Another great example of a system which has a base is the alphabet. In our case, the Roman alphabet has a 26 base system or 52 (if you include capitalization). In addition, a lot of the different measuring units we have also have their own setups for bases. There are 12 inches in a foot, 16 ounces in a pound, 60 seconds in a minuet, and even 12 months in a year. And yet, for all of these we use a base 10 counting system instead of creating our own symbols for each measuring units. Then again, imagine how confusing that would be. In most places, people realize how difficult it can be constantly converting from one base system to another which is why certain measuring systems like the metric system uses a constant base of 10 between unit sizes to make things easier.

In the end, the point is that different bases are used everywhere. Whether you are dealing with numbers or some other system entirely, you will usually be able to find a base of some kind connected to the system. While it may be difficult to have to constantly deal with different kinds of bases, bases are necessary for people to be able to have such a large variety with such a limited number of symbols. Bases are here and they are here to stay.

Sources:

http://www-history.mcs.st-and.ac.uk/HistTopics/Babylonian_numerals.html http://mathcentral.uregina.ca/RR/database/RR.09.00/hubbard1/MayanNumerals.html

What even is distance? p-adic numbers and completion of the set of real numbers

I chose this topic for a blog post based on a tangent mentioned in class: p-adic numbers. I was intrigued that there was a different way to complete the rational numbers since it took me long enough to accept that irrational numbers got to be on the number line at all. If it weren’t for 45-45-90 triangles with rational side lengths that needed hypotenuses, I honestly don’t think I would have ever accepted irrationals as more than some theoretical, mathematical construct, that while consistent, had no value to me personally beyond computation. So I was really excited to see if p-adic numbers would make more intuitive sense to me. Sadly, after some initial research it just wasn’t clicking. But after a bit more digging, I found this video:

The direct comparison of the completion of the real numbers using irrational numbers and p-adic numbers was really helpful to ground my understanding of the p-adic numbers. Hopefully this video and my discussion below will also help some of you get a feel for p-adic numbers.

Before we jump into the p-adic completion of the rationals, I’d like to discuss how we can complete the set of rational numbers in general. When we talk about completing the rational numbers, we’re really talking about completing a metric space. A metric space is defined as a set, X, with a metric, or global distance function, g(x,y), such that for every two points x and y in X, the distance between them is a non-negative, real number. A metric space must also satisfy three other properties:

• g(x,y) = 0 iff x=y
• g(x,y) = g(y,x)
• g(x,y) + g(y,z) ≥ g(x,z) (The Triangle Inequality)

This results in a metric space (X,g). (For our familiar completion of the rational numbers, we will use the absolute value function as our global distance function so d(x,y) = |x-y|.)

Now, a metric space (X,g) is called complete if every Cauchy sequence in (X,g) converges in (X,g). This means (spoilers) that if a Cauchy sequence converges to a value not in the metric space, the metric space is not complete. A Cauchy sequence is a sequence whose element become closer to one another as the sequence is extended. Luckily, we already have our metric, g(x,y) which determines the positive distance between any two points in X that we will use to calculate “closeness.” Thus, we call a sequence {x1,x2,x3,…} Cauchy if for every positive, real number E, there is some positive integer N such that all natural numbers m and n greater than N, g(xm,xn) < E.

Because of this, the set of rational numbers is not a complete metric space. Take for example the sequence {2, 2.2, 2.23, 2.236, 2.2360, 2.23606, …}. We will use d(x,y) as our global distance function. By definition, this is a Cauchy sequence of rational numbers, but its limit is √5. Because this is not an element of the rational numbers, the sequence does not converge in (Q,d). Therefore the set of rational numbers cannot be a complete metric space.

To complete this metric space, we simply add the limits of all the Cauchy sequences that can be constructed from the rationals to the rationals to form what we know as the reals. This fills in all the gaps in the metric space so every Cauchy sequence in (R,d) converges in (R,d).

Now for the formation of p-adic numbers. The primary change when working with p-adic numbers is the definition of distance. Before, we used the positive distance between two numbers on a number line, d(x,y) = |x-y|, as the metric for distance. The p-adic numbers are formed using a fundamentally different conception of distance that is still consistent with all the requirements of a metric needed to define a metric space.

We start with the formation of a p-adic number by choosing and fixing a prime, p. Every non-zero, rational number x can be written in the form x=(pn)*(r/s) where p is the fixed prime, r and s are integers, and p, r, and s are all coprime. Using this formation, we can represent all the rationals as p-adic numbers in terms of the fixed prime, p. We can then define the p-adic absolute value to create a different definition of distance to be used as a metric later on. This absolute value is defined as:

|x|p = |(pn)*(r/s)| = p-n

We also define |0|p = 0 for consistency. Notice that this definition of distance means the p-adic absolute values can only take the form of whole numbers, unit fractions, and zero. As a result, when taking the differences between two rational number x and y, this results in a very different formation of distance. The video posted above gives a great example:

When p = 7, 28814 and 2 are ‘closer together’ than 3 and 2.

This works because |28814 – 2|7 = |28812|7 = |74*(12/1)|7 = 7-4 = 1/2401 and
|3 – 2|7 = |1|7 = |04*(1/1)|7 = 70 = 1. Since 1/2401 < 1, the distance between 28814 and 2 is less than the distance between 3 and 2. Because of this, as the distance between two numbers contains factors of larger and larger powers of p, the distance decreases.

So to see if the rationals are complete using this new metric, we must check to see if every Cauchy sequence of rational numbers has a limit that is itself a rational number. Because each p-adic formation of the rationals is unique based on the initial choice of p (written Qp) and because there are infinitely many primes, it is impossible to check every p-adic formation of the rationals. But we can write a general case using p to show one example where the rationals are incomplete which is sufficient to show that the rationals are not complete using any p-adic metric.

{p0, p0+p1, p0+p1+p2, p0+p1+p2+p3, p0+p1+p2+p3+p4, …}

Because each successive term in the sequence adds a higher power of p to the previous term, we are adding smaller and smaller pieces to each term under the p-adic metric. This is because the distance between successive terms is pn and as n increases, p-n decreases. Thus, this is a Cauchy sequence. But the limit of this sequence is infinite, so it is not a term in the set of rational numbers. So again, we find ourselves in a situation where we must add the limit of each Cauchy sequences of rational numbers that can be formed using the p-adic metric to complete the rationals.

The hardest thing for me to wrap my head around while studying the p-adic completion of the rationals is that this completion does not result in the set of real numbers that result from adding the limits of the Cauchy sequences using d(x,y) to the rationals. Unlike infinite decimals that we represent as irrational constants or roots, p-adic numbers have a finite decimal component and can expand indefinitely to the left. So any p-adic number can be represented as a power series such as:

x-mp-m + x-m+1p-m+1 + … + x0 + x1p1 + x2p2 + …

Which can be written in decimal form as:

…x2x1x0…x-m+1x-m

This idea was so foreign to me that I needed it to be explicitly spelled out in the video before I could even consider it a valid way to describe a number. I’m still trying to decide if I like it. It’s definitely cool, but it’s also scary – like nuclear fission. I’m still wary of the repercussions of the p-adic definition of absolute value, but I’m glad to have explored the Wonderland like world that it creates.

Sources:

http://www.asiapacific-mathnews.com/03/0304/0001_0006.pdf
http://mathworld.wolfram.com/MetricSpace.html
http://mathworld.wolfram.com/p-adicNumber.html
http://en.wikipedia.org/wiki/Construction_of_the_real_numbers#Construction_from_Cauchy_sequences

Fermat’s Last Troll

The Urban Dictionary defines the word troll as:

Troll

  1. (n.) Sometimes compared to the Japanese ‘Oni’, a troll is a supernatural creature of Scandinavian folklore, whose race was thought to have carried massive stones into the countryside. Lives in hills, mountains, caves, or under bridges. They are stupid, large, brutish, hairy, long-nosed, and bug-eyed, and may also have multiple heads or horns. Trolls love to eat people, especially small children.
  2. (n.) An ugly little plastic doll with big hair.
  3. (v.) To fish by dragging bait behind a moving motor-boat.
  4. (v.) The act of posting a deliberately provocative message to a newsgroup or message board with the intention of causing maximum disruption and argument

Based on the final definition, I would like to propose that Pierre de Fermat pulled off the greatest troll in mathematical history (possibly unintentionally).

Problem II.8 in the 1621 edition of the Arithmetica of Diophantus. On the right is the margin that was too small to contain Fermat’s alleged proof of his “last theorem”.

Fermat was a French lawyer and mathematician who is remembered for things like discovering an original method of finding the greatest and the smallest ordinates of curved lines, and researching number theory, analytic geometry, probability and optics. Basically, he did a lot of math stuff; however, his most famous contribution to mathematics is referred to as Fermat’s Last Theorem or FLT. This marvelous contribution was written in the margin of a book. Fermat simply wrote:

“It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second, into two like powers. I have discovered a truly marvellous proof of this, which this margin is too narrow to contain.”

 

An incredibly poignant theorem, but he just didn’t have space to write out it’s proof. Fermat later proved FLT for the specific cases n=4, but left his too-wide-for-the-margin proof unwritten.  For the next 358 years mathematicians worked night and day to figure out exactly what couldn’t fit in that little margin.

On Monday 19 September 1994, Andrew Wiles, an English mathematician with a childhood fascination with Fermat’s Last Theorem, finalized a correct and elegant proof for FLT. Almost 400 years of work had finally culminated in a seemingly magical proof. It was a national holiday and people ran from their houses yelling “FERMAT IS SOLVED!!! THE WORLD IS AT PEACE!!!”. I kid. That didn’t actually happen, but someone did write a poem about it:

Fermat’s Last Theorem Proven

By Marion Cohen

Fermat said the proof was too large
to fit in the right or left marg-.
True, back of the paper
or proof made to taper
might help, but he said, “I’m in charge.”

Now Wiles didn’t mind paper waste.
In fact, it was true to his taste
to use up whole reams
to realize his dreams
and he crossed out instead of erased.

Fermat was all snickers and smiles
as he smugly stayed clear of the aisles
and he thought “they’ll be glum
“but that proof will succumb
“though it’s going to take quite a-Wiles.”

Cohen takes the point of view that Fermat was conscious of his choice to never write down his proof. This raises the question – did Fermat actually have a feasible proof? If he didn’t, was he planning on upsetting the mathematical community for 400 years?  Let’s look a little deeper.

Fermat’s note first appeared in a collection of his edited works that was published by his son Samuel in 1670. This wasn’t the only time that Fermat claimed to have a proof, but didn’t have the time or paper or something to write it out. More than a century later, mathematicians like Euler had to reconstruct proofs for many of Fermat’s theorems.

One way to address his note is to claim that Fermat’s comment was simply a private note that he never intended to publish. Simply a little “Hey self, write this awesome, brilliant proof down later. You didn’t write it now because you had no paper. Love, me”. This wouldn’t really make sense. In his day and age it was pretty normal to write and publish commentaries on ancient works. The publishers intentionally left large margins in such works so that modern commentators could write their comments and show their contemporaries how much smarter they were than their forefathers. Basically, we can be pretty confident that Fermat was at least considering that his work would be published.

When I was researching this subject, I came to the realization that this story could have ended differently. Fermat didn’t publish a lot of his work. What if he had decided to publish his commentary on the Diophantus after all? What if he decided to publish his commentary after he had worked out the proof for n=4  and then decided that he didn’t have a proof for the theorem after all? What if he had edited out his comment? We wouldn’t have Fermat’s Last Theorem. He wouldn’t have sent mathematicians on a blind-leading-the-blind hunt in the forest. Wiles may have never had a reason to devote his life to proving FLT. Essentially, it was fortunate for the development of number theory that Fermat wasn’t prone to editing his papers. Or did he intentionally avoid editing so as to troll future generations — make them think he had all these brilliant ideas and proofs, but end up just making them work and argue down (what he thought) was a rabbit hole?

Sir Andrew Wiles. Image copyright C. J. Mozzochi, Princeton N.J.

Wiles’s proof involves mathematics that wasn’t  invented or discovered (that’s the topic of an entirely different blog post) until centuries after his death. The mathematical historian Howard Eves once said that “Fermat’s Last Theorem has the peculiar distinction of being the mathematical problem for which the greatest number of incorrect proofs have been published.” Did Fermat use his version of an online forum to post his version of a troll? Or did he genuinely believe he had a solution that would have been proved incorrect? Or did he actually have a brilliant proof that doesn’t use any of Wiles’s modern math? We will never know, but I think the image of Fermat as the first comment troll is the most fun.

Sources

http://www.urbandictionary.com/define.php?term=troll

Poem: Discovering Patterns in Mathematics and Poetry By Marcia Birken, Anne Christine Coon

http://en.wikipedia.org/wiki/Fermat’s_Last_Theorem#Fermat.27s_conjecture

http://www.mathpages.com/home/kmath195/kmath195.htm

https://cs.uwaterloo.ca/~alopez-o/math-faq/node26.html

Binary numbers: the base of modern science

In the class, we learned about the strange base-60-system of Babylon, and I was wondering were there any other counting system that seems unfamiliar to us.

Because I am taking a programming class, the first thing that came into my mind was the binary system. Binary numbers represent values using only two different symbols: 0(zero) and 1(one). This system seems easier than base-10 system, because we only need to remember two symbols to express all integers. For instance, the first 10 integers in the decimal system (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) can be expressed as : “ 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001.”

  1. Origin of binary numbers

Although occupying more space, the expression of numbers in the binary system seems easier than in the decimal system. Then I am wondering who first invented it? It is said Gottfried Leibniz, a German mathematician and philosopher who is famous for the inventing of Calculus, first discover the modern binary number system and it appears in his article “Explanation of the Binary Arithmetic” . Leibniz also indicated that the ancient ruler of China Fuxi first invented the binary system in his work — “I Ching”; in “I Ching”, the binary numbers are being used to divine the fate of ancient Chinese people, for those people believe that the mysterious secrets of the universe are all in these simple numbers of signs.

Image: BenduKiwi and Machine Elf 1735, via Wikimedia Commons.

  1. The arithmetic of binary numbers

Like the decimal system, binary numbers also have their arithmetic.

  • Addition

Addition is the simplest operation in the binary system. Adding two single-digit binary numbers is relatively easy, like this:

0 + 0 → 0

0 + 1 → 1

1 + 0 → 1

1 + 1 → 0, carry 1 (since 1 + 1 = 2 = 0 + (1 × 21) )

Here when adding two 1s, we carry the value divided by 2, and add the quotient to it the left-next positional value, so multiple-digits number addition is:

0 1 1 0 1

+   1 0 1 1 1

—————–

= 1 0 0 1 0 0

  • Subtraction

The subtraction of binary numbers is the inverse operation of addition, when two single-digit number doing a subtraction, like this :
0 − 0 → 0

0 − 1 → 1, borrow 1(from the left-next position)

1 − 0 → 1

1 − 1 → 0

So, likewise, the multiple-digits numbers’ subtraction are like this:

*   * * *   (starred columns are borrowed from)

1 1 0 1 1 1 0

−    1 0 1 1 1

——————

1 0 1 0 1 1 1

3)Multiplication

Multiplication in binary numbers is simpler than in the decimal system, for two number A and B, there are only two rules:

  1. If the digit in Bis 0, the partial product is also 0
  2. If the digit in B is 1, the partial product is equal to A

For example, the binary numbers 1011 and 1010 are multiplied as follows:

1 0 1 1   (A)

× 1 0 1 0   (B)

———–

0 0 0 0   ← Corresponds to the rightmost ‘zero’ in B

1 0 1 1     ← Corresponds to the next ‘one’ in B

0 0 0 0

+ 1 0 1 1

—————–

= 1 1 0 1 1 1 0

And for division, it is the inverse operation of multiplication.

  1. Transfer between binary number and decimal number

How to transfer a binary number into a decimal number? For example:

11011(2) = 1 * 2^4 + 1*2^3+0*2^2+1*2^1+1=27(10)

And the inverse transfer is to count the power of 2s in a decimal number, like:

36(10) = 1*2^5+ 0*2^4 +0*2^3+1*2^2+0*2^1+0*2^0= 100100(2)

  1. The application of binary numbers

The reason why I introduce the binary numbers is that they are the base of modern science, especially the computer science. The basic element of a computer is the logical circuit, which only has two basic situations: 0 for switch off, and 1 for switch on. As the old saying: less is more. The binary system is coincidentally perfectly fitting the feature of the logical circuit(0 for no, and 1 for yes). And the logical circuit led to the invent of computer. For example, when calculating, the computer will translate the numbers into binary form and do the operations, and then transfer the answer back to decimal number like it shown above.

  • Conclusion

It is unbelievable when you think of the powerful computer is based on the binary system, and considering the huge works computer have done so far, we can say that the binary system is the key of modern science and technologies. Even when I am typing this article, the binary numbers keep working in my computer.

Reference:

http://en.wikipedia.org/wiki/Binary_number

http://en.wikipedia.org/wiki/Logic_gate#Symbols

http://www.ask.com/technology/computers-use-binary-number-system-33ebc182c16b88f