Pressing Toward the Prize

Archive for October 2010

After having a really rough week, I decided to search some blog sites for a little humor. Thankfully, I found a couple that fit the bill. In his blog Division by Zero, Dave Richeson offers pumpkin pi, a limerick, exceptional math reviews, and some fun with the concept of infinity. The definition of infinite he shares from “The Hitchhiker’s Guide to the Galaxy” is rivaled only by this sentence in John D. Cook’s blog about a googol: “Inconceivably large numbers pop up in intermediate steps on the way to moderate-sized results.”

For humor of a different sort, Tanya Khovanova shares how mathematics helped her learn to say, “No.” Okay, except for the last couple of sentences, it really has nothing to do with math, unless you want to start adding up the number of  marriage proposals she has received over the years. (Hint: You might need a calculator!!) But like I said, I was looking for something humorous. And if riddles are your cup of tea, Tanya also offers some interesting puzzles. Who says math isn’t fun?

Advertisements

I recently did a review of an article involving Gaussian integers (complex numbers whose real and “imaginary” parts are integers) in which the Euclidean algorithm was used to find the greatest common divisor (gcd) of two complex numbers. I had never heard of the Euclidean algorithm before, and the process described in the article involved complex numbers and several Greek letters, so I had no idea what was going on. Then, as luck would have it, only a few days later we discussed in math class how to use the Euclidean algorithm to find the gcd of two integers, that is, the largest number that divides both of them without leaving a remainder. It is based on the principle that the gcd does not change if the smaller number is subtracted from the larger number. If this process is repeated, the numbers keep getting smaller until one of them is zero. At this point, the gcd is the larger, non-zero number.

Here is a simple video that describes the process used to find the gcd of 123 and 36:

So what happens if the numbers are a bit larger?

Let’s find the gcd of 5,624 and 3,959:

\begin{aligned} 5,624 &= 3,959 \cdot 1 - 1,665\\ 3,959 &= 1,665 \cdot 2 - 629\\ 1,665 &= 629 \cdot 2 - 407\\ 629 &= 407 \cdot 1 - 222\\ 407 &= 222 \cdot 1 - 185\\ 222 &= 185 \cdot 1 - 37\\ 185 &= 37 \cdot 5 - 0 \end{aligned}

So the gcd(5,624, 3,959) = 37.

No matter how large the numbers, the process can be completed in a finite number of steps. It has been found that the maximum number of steps required is five times the number of digits in the smaller integer. If the numbers are sufficiently large, this still could take a very long time. The beauty of this algorithm is that a computer can be programmed to complete the steps in a matter of seconds, rather than the untold hours if calculated by hand. Although I still don’t fully understand this algorithm as applied to Gaussian integers, I have found it to be a wonderful tool for calculations on real integers.

A few days ago, Dr. Daniel Heath, a math professor at Pacific Lutheran University, presented a lecture during Capstone Seminar offering an introduction to knot theory. He will be teaching a special topics class in the spring, and was hoping to pique our interest in the subject. Knot theory is a branch of topology in which a circle is embedded in 3-dimensional Euclidean space, \mathbb{R}^3. According to the Oracle ThinkQuest site, “a knot is a closed, one dimensional, and non-intersecting curve in three-dimensional space. From a more mathematical and set-theoretic standpoint, a knot is a homeomorphism that maps a circle into three-dimensional space and cannot be reduced to the unknot by an ambient isotopy.” So what you have is something like a knot in a string, but with the ends joined together so that it cannot come undone. There are various ways to describe a knot, so an important problem in knot theory is determining when two different representations are describing the same knot.  Wikipedia explains: “Two mathematical knots are equivalent if one can be transformed into the other via a deformation of \mathbb{R}^3 upon itself (known as an ambient isotopy); these transformations correspond to manipulations of a knotted string that do not involve cutting the string or passing the string through itself.”

Professor Heath showed us several knot diagrams, explained three legal “Reidemeister moves” that can be used to transform a knot, and then described how to determine if two knots are the same using “colorability” of the strands of a knot diagram as a classification criterion. Then he presented an important theorem: “If we have an unknot in a diagram with n crossings, then it can be unknotted in less than 2^{n \times 10^{11}} Reideimeister moves.” This was apparently a huge breakthrough in knot theory, because it showed that there is an upper bound on the number of moves necessary to unknot a knot, but it is such a large number, that it is relatively useless from a practical standpoint.

I found the presentation interesting and informative, and was actually able to follow most of it. I found myself becoming a little lost when a theorem was presented about “n-colorability.” It is defined using modular arithmetic, which I understand, but the application to the knot diagrams went a bit “fast” for me. Even though there are important practical applications to knot theory, such as the properties of knotted vs. unknotted chemicals in chemistry, and string theory in physics, I find the whole concept of knot theory somewhat unusual. I know that we were exposed to only a small portion of what knot theory entails, but at this point in time, I don’t think it is a topic I am interested in pursuing. I meant to ask Professor Heath after the lecture why he became interested in knot theory initially, and also why he has continued to study the topic, because I am always interested in what motivates people to do what they do. I guess that will have to wait for another day.

Part of preparing for our Capstone Senior Project is learning how to research information using mathematical resources, including articles, books, and textbooks. Although the database Mathscinet is a great place for gathering references on a particular topic of interest, we have discovered that most of the articles are a bit over our heads. In those research articles, mathematicians are writing to their peers, of which we are not (yet). An alternative for us is to consider using math journals geared more toward the level of undergraduates. This leads me to our current Capstone assignment. After a lesson on how to best read a math article, complete with an appropriate list of do’s and don’ts, each of us was assigned an article to “read” and then do a review in the fashion of a “2nd grade book report.” I found that as simple as this sounds, it was a pretty tall order!

My article was entitled “Gaussian Integers and Arctangent Identities for \pi” by Jack S. Calcut, taken from The Mathematical Association of America, June-July 2009 issue. Not knowing what Gaussian integers were, at least not by name, I was relieved to find that a Gaussian integer is simply a complex number whose real and “imaginary” parts are integers. But as I stated in an earlier blog, my exposure to complex numbers has been minimal, and my exposure to graphing complex numbers has been nonexistent. This made the article a bit of a challenge for me, but the author did a very good job of explaining and defining terms where he thought there might be confusion on the part of the reader; this gave the article the feel of an instructional textbook. Not every term was defined, however, and I was grateful for my current Abstract Algebra course when I had to look up the definition of a commutative ring. Since a commutative ring has to do with binary operations and groups, and we have recently been studying both, I was thrilled to find that I actually understood the definition!

The article began by addressing the connection of arctangent identities for \pi to calculating the decimal digits of \pi. Then a lesson involving unique factorization, primes, and irreducibles in \mathbb{Z}[i], concepts I understood only marginally, led to the main lemma about Gaussian integer z \neq 0 and the conditions under which z^n is real. This was then used to show that a simple form of an arctangent identity for \pi does not exist. The author also expanded the application of the lemma to show connections between rational vs. irrational values in the leg lengths and angles of right triangles, as well as various concepts involving angles created on geoboards. As it turns out, developments in this area have been ongoing since the 14th century, involving a multitude of mathematicians who have discovered, and at times rediscovered, the various concepts, identities, and applications presented. And with the advent of the computer, new calculations, identities, and avenues of study have been made possible. This was a very interesting article, even though there was much I did not fully understand. I am deeply grateful that I only needed to produce a “2nd grade book report” about it!

While reading the September 2010 issue of “Math Horizons” magazine, I ran across some fun and interesting articles. In the “fun” category was an article written by Donald Byrd, a parody, or mathematicizing (is that a word??), of the seemingly endless song “100 Bottles of Beer on the Wall.” For the infinite version, with infinite bottles of beer on the wall, one falls down, and you are left with infinite bottles of beer, forever. The larger infinity version starts with uncountable bottles, if countable bottles fall,  then you still have uncountable bottles of beer. The indeterminate version: start with infinite bottles of beer, if infinite bottles of beer should happen to fall, you are left with indeterminate bottles of beer on the wall, and this is the end of that song! Other versions include geometric progression, Euler’s identity, differentials, identity, topological dimension, and fractal dimension. All in all, pretty entertaining.

Another article, written by Bruce Torrence and still in the “fun” category,  described a convention of magicians, mathematicians, and puzzle masters held in honor of Martin Gardner, “the prolific and magnetic author whose interests spanned the seemingly disparate disciplines of mathematics, puzzles, magic, and the spirited debunking of pseudoscience.” A particularly obscure puzzle was presented by one of the speakers before he abruptly ended his brief talk and sat down: “I have two children. One is a boy born on a Tuesday. What is the probability I have two boys?” …brief pause… “The first thing you think is ‘What has Tuesday got to do with it?’ Well, it has everything to do with it.” As it turns out, this riddle became the talk of the convention, and was finally solved by counting all possible outcomes, including gender, births, and days of the week, and using basic probability theory. By the way, the answer is 13/27.

Finally, of extreme interest to me, was an article about the terrors of Mathematical Analysis. This is the course I will be taking in the spring, and it is the only course I still need to fulfill my major. The bad part is that I am already stressing about taking it. I have heard frightening things about how impossible this course is, and how I should just resign myself to being happy if I pass it, let alone trying to get a good grade in it. So Tina Rapke’s article “Confronting Analysis” was speaking to me. She shares about how she struggled with mathematical analysis in the beginning, actually “drowning” is the word she used, and how she eventually found understanding and success by hard work, tenacity, and consulting multiple resources, some of which she discusses in the article. She is now a Ph.D. candidate pursuing an interdisciplinary degree in mathematics and education, having written her PH.D. candidacy exam in analysis, and passing. Her advice to those who struggle with analysis? a) You are not alone! b) Be open to various textbooks and resources, and  c) Don’t give up!

I think I will keep this article close at hand… spring semester is coming!

On October 6, we had a guest speaker in Capstone, Dr. Julie Eaton from the University of Puget Sound, who gave a presentation on locating critical points of polynomials. First, she presented the Lucas-Gauss Theorem: “The roots of the derivative of polynomials are contained in the convex hull of the roots of that polynomial.” For polynomials with real roots, it was easy to see graphically that the roots of the derivative, which are the critical points of the continuous polynomial curve, would be contained within the same interval as the roots of the polynomial. I had a little more difficulty following what was happening when some of the roots were complex numbers, however, because none of my classes to date have covered graphing in the complex number system. I know that when the root of a polynomial is a complex number, its conjugate is also a root. This made it easier to understand that the graph containing complex roots could be connected to form a region rather than an interval. It was interesting to see that the same principle in the real number system was true in the complex numbers. The region created by the roots of the derivatives was fully contained in the roots of the polynomial. For higher order polynomials, each time a derivative was taken, the shape of the region “decreased” and was still fully contained. For example, a fifth degree polynomial with one real and four complex roots created a pentagon, the first derivative created a quadrilateral, the second a triangle, and so on, each fully contained within the other. One of the things I love about math is finding patterns in “unexpected” places, so this was fascinating to me.

The second concept Dr. Eaton covered had to do with Newton polygons, which Newton created in 1671 along with an algorithm used to approximate the roots of polynomials as functions of their coefficients. I had no difficulty in actually using the technique to approximate the roots, but I didn’t fully understand the explanation of why it works. I guess that will wait for another day! I found the presentation quite interesting, but it went a little “fast” for me. I would like to have had more time to explore with Dr. Eaton a few of the concepts that were new to me, but she was under specific time constraints, and it was a lecture, after all. For me, the best part of the presentation is that, even though I didn’t fully understand everything she shared, it gave me ideas on new avenues of study.

In a recent conversation with my math professor regarding a possible topic for my Capstone, I commented that I really enjoyed studying linear algebra. I told him I might be interested in doing some type of real-world application involving linear algebra for my project, and he began to tell me about Donald Saari. Mr. Saari is a mathematician who studies what he calls “the paradoxes and problems of voting procedures,” and analyzes voting methods using linear algebra. I am currently looking at two books he wrote: “Chaotic Elections!” and “Basic Geometry of Voting.”

In “Basic Geometry” Mr. Saari makes it clear that when there are only two choices up for a vote, there is generally no difficulty in determining the winner. But when there are more than two choices, things can get rather interesting. In order to demonstrate some of the challenges that can arise,  Mr. Saari opens the book with the story of a fictional academic department chair who finds himself in hot water as a result of a departmental vote. The problem is that the same vote can be interpreted different ways, depending on which voting method is used. Even if a method ranking preferences is used, various outcomes can result depending on which way one counts the rankings. In fact, each of the options can be deemed the winner, depending on the method used.

Now things can become even more complicated if a group of voters attempts to manipulate the process. For example, assume Al, Bob, and Chuck are candidates for the new Chair position. Of the 15 people voting, 7 are for Al, 7 are for Bob, and the only one pulling for Chuck is, well, Chuck. A ranking system is used that gives 2 points to one’s first choice, 1 point for one’s second choice, and 0 points for the third. Al receives 14 points from his group, 7 points from Bob’s, and 1 from Chuck. Bob receives 14 points from his group, 7 points from Al’s, and 0 from Chuck. So Al wins, 22-21-2, with Chuck’s vote determining the winner.

Let’s assume now that Bob’s supporters predict this outcome and decide to ensure Bob’s success. They each vote for Bob as their first choice, Chuck for their second, and Al for their third. Now Bob wins 21-15-9. Al’s supporters see this coming, so they decide to be “strategic” and vote for Al as their first choice, Chuck as their second, and Bob as their third. With this turn of events, that is, both groups voting for Chuck as their second choice, even though he was the first choice for only 1 out of the 15 voters, Chuck wins 16-15-14.

With this simple story, Mr. Saari demonstrates that it is not difficult for a candidate to win an election, even though that person was not the first choice of the majority of voters. As it turns out, this is not an anomaly. The outcome of a vote does not necessarily reflect the will of the people. As Mr. Saari states, his intent is simply to share what can go wrong in elections and why, in the hopes that voting errors can be prevented in the future. All in all, I found this to be a very intriguing topic, and with a little more research, it could turn into my Capstone project.



    • gramsonjanessa: I can't wait to listen to your capstone presentation in the spring! Your proposal was really interesting and I'm interested to see how the linear alge
    • dewittda: This is impressive! I thought I was good because I solved a rubik’s cube once in an hour. I served with a guy in the Air Force who could solve a r
    • ZeroSum Ruler: The Euclidean algorithm should me the mainstream way we teach students how to find the GCF. Why isn't it? A mystery.

    Categories