Friday, February 28, 2003

Experience Mathematics #28 -- How fast do functions grow?

In the last column, we talked about the explosive growth of the exponential function. The number of computers infected by the SQL Slammer worm increased dramatically, bringing the Internet crashing down in a couple of hours.

Computer scientists measure the speed of computer algorithms by comparing them to functions.
Some of the functions they use are logarithmic: $\log(n)$, linear: $n$; the power functions: $n^2, n^3, n^4,\dots $; and the exponential functions: $2^n, 10^n,$ etc.

Usually $n$ is the size of the input. Computer scientists make statements such as: The “order” of an algorithm is $n^2$. For example, if you have to sort $n$ numbers, the algorithm is of order $n^2$. This means that the computer has to make approximately $n^2$ calculations. To get an idea of which algorithms are faster, consider when $n=1000$. $\log(n)$ is just $3$. The linear function $n$ is also manageable, at $1000$. However, $n^2$ is $1,000,000$ (one million) and $n^3$, is one billion. And $10^n$ is a huge number, 1 followed by a thousand zeros. This number of calculations is more than what Deep Junior had to perform to defeat Kasparov in Chess.

All these functions go to infinity as $n$ goes to infinity. That is to say, they become bigger and bigger as $n$ becomes bigger. What matters (to computer scientists) is how fast or slow this increase is. The slower the increase, the faster the algorithm.

Logarithmic, linear and Polynomial time algorithms the only algorithms that are fast enough to work in practical situations.

Computer scientists are continuously finding faster and faster algorithms. Recently, Maninder Agarwal, Neeraj Kayal, and Nitin Saxena, of IIT, Kanpur, found a deterministic polynomial-time algorithm to determine whether a number is a prime number.

This solved a problem that mathematicians have been trying to solve for centuries.

Friday, February 07, 2003

Experience Mathematics # 27 -- The exponential function



“It only took 10 minutes for the SQL Slammer worm to race across the globe and wreak havoc on the Internet two weeks ago” is what newspapers reported on February 7, 2003. The number of computers doubled every 8.5 seconds in the first minute of the worm’s existence. So how many computers got infected in the first minute?

The number of computers infected in $t$ seconds can be modelled by the function $N(t)$, where
$$N(t)=2^{t/8.5}.$$

This is a reasonable model. In the beginning (when $t=0$) we assume that the worm has infected only $1$ computer, and indeed, $N(0)=1$. In 8.5 seconds, the number becomes $N(8.5)=2$, so it doubles. In another $8.5$ seconds, $N(17)=4$. This doesn’t sound like very fast growth, but at the end of one minute ($t=60$) the number becomes more than $133$. In two minutes, $28995$ computers are infected, and in $5$ minutes, the number of computers infected is in the billions. Which means that the rate of growth must have slowed down, because there aren’t so many computers in the world! I hope this helps you understand why it caused the slowdown of the Internet traffic in Korea.

$N(t)$ is an example of an exponential function, which increases very fast. The prototypical example is THE exponential function, $f(x)=e^x$. Here the number e is an irrational number (just like the famous $\pi$, whose value is approximately $2.7182818\dots$. The graph of the function (made using desmos.com) is as follows.


The exponential function is not symmetric across the $y$-axis, nor across the origin. That is to say, it is not an even function or an odd function. However, consider the functions:
$$E(x)=(e^x+e^{-x})/2,$$ and $$O(x)=(e^x-e^{-x})/2.$$ $E$ is an even function, and $O$ is an odd function, and the exponential function is the sum of these functions. Draw the function $E(x)$ from $x=-5$ to $x=5$ using MS-Excel (update: try www.desmos.com), and see what the graph looks like. Does it look like a clothesline secured at its two ends?

Friday, January 31, 2003

Experience Mathematics # 26 -- Symmetries


There are two kinds of symmetries in a function. A function may be symmetric across the $y$-axis, or symmetric across the origin. (If a curve is symmetric across the $x$-axis, it is not a function. Can you tell why?)

For example, the function $f(x)= x^2$ is an example of a function that is symmetric across the $y$-axis.


 This symmetry is obvious from the graph. An algebraic way to see that the function $f(x)= x^2$ is symmetric across the $y$-axis, is to replace $x$ by $–x$ in the formula, and note that:
$f(–x) =f(x)$ (since $(–x)^2=x^2$).
For example, the $y$-coordinate corresponding to the point $–2$ is the same as that corresponding to $2$.
The function $f(x)= x^3$ is an example of a function that is symmetric across the origin.


Each point (for example the point $(2, 8)$) maps to a symmetric point (the point $(-2, -8)$) in the graph. An algebraic way to notice that this function is symmetric across the origin is to note that
$f(–x) =–f(x)$ (because $(–x)^3= –x^3$).

Functions symmetric across the $y$-axis are called even functions, and functions symmetric across the origin are called odd functions.

What is remarkable is that any function defined on the set of real numbers can be written as a sum of an odd and an even function. Can you figure out a way to write the exponential function $f(x)=e^x$ as the sum of an even and an odd function? The curve formed by a hanging clothesline  appears in the answer to this question.

Thursday, January 23, 2003

Experience Mathematics # 25 - Functions


A ball thrown in the air follows the path of a parabola. Parabolas are modelled by a function of the form $p(x)=ax^2+bx+c$, where $a$, $b$ and $c$ are real numbers. This kind of function—a polynomial of degree 2—is called a Quadratic Function. While we will not formally define functions, it is helpful to get an intuitive idea of functions from several points of view.

One point of view is to think of functions as a rule. For example, consider the quadratic function:
$f(x)=1-x^2$. Every real number $a$ corresponds to a unique real number denoted by $f(a)$ obtained by replacing $x$ by $a$ in the above equation. For example,
$f(0)=1, f(1)=0, f(-2)=-3.$

This suggests that we can also think of a function as an input-output machine. For each input $a$ we have a unique output $f(a)$. The set of possible input values (in this case the set $R$ of real numbers) is called the domain of the function.

Imagine making a table of all the input-output values of the function. (There are an infinite number of elements in the domain, so you can only imagine making a table!) All these values can be plotted on the coordinate plane. The input values are the $x$-coordinates and the output values are the $y$-coordinates.

If we do this, we will get a graph of the function. We denote the graph by $y=f(x)$, (or $y= 1-x^2$).

This is the third way of thinking about a function: as a graph. The graph is shown below.


Note that this parabola is symmetric about the $y$-axis. It meets the $x$-axis when $x=1$ and when $x=-1.$ These are (graphically speaking) the solutions of the equation $1-x^2=0$. The function has a maximum when $x=0$, corresponding to the highest point a ball reaches, when it is thrown in the air.

Friday, January 10, 2003

Experience Mathematics # 24 -- The Calculus


Happy New Year. The earth has finished another revolution around the sun, taking a little more than 365 days to do so. Meanwhile, the moon continues to rotate around the earth, the planets around the sun, and the same forces that make these things move in an elliptical path ensure that a ball thrown up in the air always falls down, or that a ball thrown in the air (towards a friend) takes a parabolic path.

Over this and the next few columns, I will discuss these natural motivations that are behind the notions that you encounter as you study the Calculus.

The first concept is that of a function. Mathematicians were already familiar with curves from Euclidean and coordinate geometry by 1600 or so A.D. It was natural to begin modelling various physical phenomena with functions. For example, $y=1-x^2$ models the parabola. For each value of the input $x$, we get a unique output $y$. If you plot the curve in the coordinate plane, you obtain a parabola.

It was natural to do two things. To figure out laws that can explain why a ball thrown in the air follows a path traced by such a curve. This led to the laws of Gravitation. And the other thing is to use these laws to predict the answers to common questions that arise. For example: How high will the ball go? How far will the ball go? Given the curve, when does the curve go up (increase)? And when does it come down (decrease)? We will consider such questions and relate them to what you encounter in Calculus.

Curves such as the circle ($x^2+y^2=1$) are not functions since there is not one output $y$ for each input $x$. For example, for $x=0, y$ can be $1$ or $–1$. So, every curve does not give rise to a function.

Friday, December 20, 2002

Experience Mathematics #23 -- Ambigrams (by Punya Mishra)

Symmetry is important in mathematics and in art. Today we will look at a special kind of wordplay based on ideas of symmetry and figure and ground. Consider the word below: 



Can you read it? Now turn the page you are holding upside down and try reading it that way. The word stays the same. This image/word has rotational symmetry—essentially, it stays the same when rotated 1800.

Such visual wordplays are called ambigrams. The word “ambigram” was first coined by the cognitive scientist Douglas Hofstadter. Here is an ambigram of the word ambigram itself.


Ambigrams can be of many different kinds. For instance consider the word “logical” below.



This word has reflection symmetry i.e. it will read the same even when reflected in a mirror.

Some ambigrams are not about symmetry as much as they are about reading words in multiple ways. Here is one titled “good-evil” Can you see both words? Look carefully. This is similar to figure-ground paintings by M. C. Escher.



Creating ambigrams is great fun. Why don’t you try creating some yourself? If you want to see more examples of such wordplay you can search on Google or go to my wordplay gallery: http://punya.educ.msu.edu


This guest column has been written by Professor Punya Mishra, College of Education, Michigan State University, USA. You can email him at punya@msu.edu

Friday, December 13, 2002

Experience Mathematics # 22: The mobius strip

Take a long, thin strip of paper, give it a half twist, and paste the two ends together. What you get is a mobius strip (see picture).



Compare the mobius strip with the cylinder, which you get if you don’t give a half twist. A mobius strip has only one surface. Can you see why? Draw a line along the edge and keep going on. Eventually, you will arrive at the starting point. A cylinder, on the other hand, has an inside and an outside surface. The artist Escher portrayed this idea in Mobius Strip II (woodcut, 1963) (see picture).



If you cut the paper cylinder in half, you will get two cylinders. However, if you cut the mobius strip, you will get something very similar to a mobius strip. How many half-twists does the cut mobius strip have?

The mobius strip is one of the many surfaces that appear in Topology, a branch of mathematics. Topologists have been described as the mathematicians who cannot tell the difference between a coffee mug and a doughnut. This is because a mug can be “continuously deformed” to become a doughnut. A doughnut (which is a tyre tube, topologically speaking) cannot be transformed into a sphere. So, according to topologists, the tyre tube is not the same as a sphere, but a coffee mug is homotopic to a doughnut.

Pic credits: Both were stolen off the web, I don't know from where. 

Thursday, December 05, 2002

Experience Mathematics # 21 -Euclid's fifth axiom


Euclid’s fifth axiom says that given a line $l$ and a point $P$ not on the line, there is exactly one line parallel to $l$ passing through the point $P$. For centuries people thought that Euclid’s fifth axiom was “obvious”. But some mathematicians did not find it obvious. 

Finally, Reimann and Lobachevsky, both modified the axiom and tried to derive a new geometry. 

Reimann began with the axiom: Given a line $l$ and a point $P$ not on the line, there is no line parallel to $l$ passing through the point $P$. Reimann derived many geometrical theorems that are applicable on the surface of a sphere. For example, he showed that the sum of angles of a triangle is always greater than 180 degrees. Try drawing a triangle on a sphere and see why this has to be true.

Similarly, if we take a hyperbola ($y=1/x$) and rotate it around the y-axis, then we obtain a surface where Lobachevsky’s geometry holds. Lobachevsky’s geometry contains the axiom: Given a line $l$ and a point $P$ not on the line, there is more than one line parallel to $l$ passing through the point $P$. In this geometry, the sum of angles of a triangle is always less than $180$ degrees.

There is a property of the surface (known as curvature) that determines the geometry. Only surfaces with curvature zero follow the Euclidean geometry. Another example of a surface is that of a saddle (of a horse). Can you tell which geometry is applicable on this surface?

Friday, November 15, 2002

Experience Mathematics # 20 -- The sum of angles in a triangle

Euclidean or plane geometry begins with notions of points and lines, and the notion that a point lies on a line. Think of lines as sets, and a point as an element belonging to a set. Points and lines satisfy certain axioms. In Euclidean Geometry (or plane geometry), the axioms are based on Euclid’s original axioms. From these axioms, we can use the rules of logic to derive theorems (or propositions) that can be regarded as truthful statements that apply to the plane. Here a plane is a model, or a mini-universe where those axioms and theorems hold.

For example, consider the theorem: The sum of angles in a triangle is $180$ degrees. The various terms in this theorem (angle, triangle etc.) are constructs in the plane that we wish to study. The theorem itself is a property that will hold in our mini-universe. The proof should proceed from the axioms, use the definitions of the various constructs, and follow the rules of logic.

Even though the theorem is true, it does not imply that the sum all triangles is $180$ degrees. For example, consider the surface of the earth. Draw a triangle with a right angle at the North Pole. Suppose the two sides of this angle go down to the equator, and the third side of the triangle is the equator. The sum of angles of this triangle—made on the surface of the earth—is $270$ degrees!

In fact, in this non-euclidean geometry, the sum of angles in a triangle is always greater that $180$ degrees.

Can you find a surface where a sum of angles in a triangle is always less than $180$ degrees?

Friday, November 08, 2002

Experience Mathematics #19 -- Euclid's axioms

Just like elements and sets, Points and Lines are undefined notions.

We can think of a line as a set of points. These satisfy certain axioms, such as: Given a line $l$ and a point $P$ not on the line, there is only one line that is parallel to $l$ containing the point $P$. Axioms are considered to be self-evident truths.

However, several gaps were found in Euclid’s axioms. For example, consider Euclid’s proof that the base angles of an isosceles triangle are equal. Suppose we have an isosceles triangle $ABC$, where the side $AB$ is equal to the side $AC$. Drop a perpendicular $AD$ from a vertex to the side $BC$. There is nothing in Euclid’s axioms that says that the point $D$ is between the points $B$ and $C$. Nevertheless, Euclid proves that the triangles $ABD$ and $ACD$ are congruent. From this it is easy to see that the base angles of an isosceles triangle are equal.

The great mathematician Hilbert completed Euclid’s work by listing a few more axioms. These included the betweenness axioms. For example, given three points $A, B and C$, one of the axioms said either $B$ is between $A$ and $C$, or $C$ is between $A$ and $B$ or $A$ is between $C$ and $B$.

To return to Euclid’s proof, some steps need to be added to show that $D$ is between $B$ and $C$. 

But that is not all. We could consider a geometry where given a line $l$ and a point $P$ not on the line, there are no lines parallel to $l$ containing the point $P$. Such a non-euclidean geometry exists on the surface of the Earth. So one of Euclid’s axioms cannot be considered to be a self-evident truth after all.

Friday, October 25, 2002

Experience Mathematics #18 - All about itself


Russel’s Paradox shows that considering sets that contain themselves (or even asking whether they contain themselves or not) can lead to contradictory situations. But Real Life has many such self-referential situations. In this column, we will collect together many amusing (and not!) statements, such as this one.

“All Cretans are Liars”, said the Cretan Epimenides. Did Epimenides tell the truth? How can he, since he is a Cretan, and hence a liar? But if he lied, maybe he is telling the truth!

What about: This sentence is false. Is it true or false? Go through each sentence in this column and evaluate whether it is true or false.

This sentence has four words. This one, however, has six words. This one has one too too many words.

This sentence has no comma. This sentence does not describe itself.

This article is written by the author of this article. In other words, the author of Experience Mathematics writes Experience Mathematics. It is self-referential, since it refers to itself. In fact, the article refers to itself several times—but only once does the article refer to itself twice in one sentence. The author of this article is careful not to write self-referential statements.

Is this a question or not. How about this statement?

The above two statements beg the question. But what is the question? Was that the question? Does this answer the question?

The sentence below is false. The above sentence is true.

Lets not say any more, and end.

Friday, October 11, 2002

Experience Mathematics # 17 -- If it is, then it is not

A set can be thought of as a collection of objects. But what is it, really? The above sentence does not say: A set is a collection of objects. So is a set a collection of objects, or can it only be thought of as a collection of objects?

Sets can be of two types: those that contain themselves, and those that do not. For example, consider the set $F$ of fruits in your home. This set is not a fruit, so cannot contain itself. Now consider the set $A$. The set $A$ contains all sets that can be described in less than sixteen words. The above sentence has only $15$ words and describes $A$, so $A$ must be a member of itself.

Now consider the set $R$ of all sets that do not contain themselves as a member. In particular, $F$ is a member of $R$. The question is: Is $R$ a member of itself?

Well, if it is, then by definition $R$ consists of sets that do not contain themselves as a member. So $R$ is not a member of $R$. In short, if it is, then it is not.

Conversely, suppose $R$ is not a member of itself. Then since $R$ contains all sets that are not members of themselves, $R$ must be an element of $R$. Thus, if it is not, it is!

This paradox—pointed out the famous philosopher, Bertrand Russell—led to the formalization of set theory. Formally speaking, a ‘set’ and the relation ‘is an element of’ are undefined notions that satisfy certain axioms. However, we can continue to think of a set as a collection of objects. Just make sure that we consider only well defined sets—where we can decide whether any given object is an element of the set or not. That saves us from all Russellian disasters.

Thursday, October 03, 2002

Experience Mathematics #16 -- An apple a day

If you study mathematics, then you will have to deal with many statements that contain expressions of the form: If $A$ then $B$  (or, $A$ implies $B$).

Suppose it is true that if you have an Apple a day, then you keep the doctor away. Is it true that if you did not visit the doctor, then you must have had an Apple everyday? Not necessarily. In other words: “if $A$ then $B$” is a true statement, then “if $B$, then $A$” may be false. The statement “if $B$, then $A$” is the converse of “if $A$ then $B$”.

The converse is not to be confused with the contrapositive of the statement. The contrapositive of “if $A$ then $B$” is: “if not $B$ then not $A$”. Unlike the converse, if a statement is true, its contrapositive is true too. Indeed, either they are both true, or they are both false. For example, suppose that it is true that an Apple a day keeps the doctor away. Now if the doctor comes to visit you, you must not have had an Apple some day. Mathematics contains axioms (that may be regarded as “truths”) together with chains of implications—statements of the form “$A$ implies $B$”, where $A$ and $B$ are mathematical expressions. Suppose your axioms say:

1. An Orange contains the daily requirement of Vitamin C.

2. Having your daily requirement of Vitamin C will keep you healthy.

3. If you are healthy, the doctor will stay away

Then, logic dictates that an Orange a day will keep the doctor away. Unfortunately, an Apple does not contain a lot of Vitamin C.

Friday, September 27, 2002

Experience Mathematics # 15 : OR and AND

Suppose that your mom says that you can have either an Apple or a Banana. Can you have both? One of the most fundamental rules of logic says that the expression either $A$ or $B$ is true only if one of $A$ or $B$ is true. That is to say, you cannot have both the Apple and the Banana (assuming you wish to obey your mom.)

What if your mom says you can have an Apple or a Banana? In this case, you can have both.

Suppose your mom asks you if you have had an Apple or a Banana. Can you honestly say yes if you have had an Apple and an Orange? The answer is yes. If she asks you if you have had an Apple and a Banana, you can answer yes only if you have had both.

Suppose your mom insists that you should not have an Apple. Is it OK to have a Banana? How about Baked Beans? It depends. The alternatives to an Apple allowed by your mom depend on the context. For example, if the alternatives allowed consist of the other fruits in the house, you cannot have baked beans instead of the Apple, but you could have a Banana. However, if the context of discussion is the five servings of fruits and vegetables that you must have every day, then Baked Beans are allowed. In Mathematics, when we refer to a set $A$, then we must specify the universal set $U$ from where the elements of $A$ are picked. Then the complement of $A$ is the set of all the elements that are in $U$ but not in $A$. Then there is no confusion when we claim: $a$ is not an element of $A$. By this statement we mean that $a$ is an element of the complement of $A$.

Tuesday, September 17, 2002

Experience Mathematics #14 - Uncountable sets

Many of the infinite sets we have encountered are countable. Even numbers, the set of prime numbers, integers and rational numbers, all have the same number of elements as $N$, the set of natural numbers. Are there any infinite sets that have more elements than the natural numbers?

This question was answered by Cantor, who showed that the real numbers outnumber the natural numbers. All the real numbers between $0$ and $1$ have a decimal expansion such as $x=0.13212987\dots$. Cantor showed that all numbers of this form cannot be put into one-to-one correspondence with the set of natural numbers. To be able to understand his proof, find a number that differs from $x$ in the first decimal place. Take any number $y$ with $2$ in the first decimal place. Since $2$ is different from $1$, $y$ differs from $x$ in the first decimal place.

To return to Cantor’s proof, suppose that you are able to find a one-to-one correspondence between the natural numbers and all the real numbers in the interval $(0,1)$. Let us denote by $x_1$ the number corresponding to $1$; $x_2$, the number corresponding to $2$, and so on. Now consider a number $y$ (between $0$ and $1$) that is different from $x_1$ in the first place after the decimal; different from $x_2$ in the second place after the decimal; and so on. Clearly, $y$ cannot appear in the list, since it is different from all the $x$’s. Thus we have found a real number between $0$ and $1$ that is not in the above correspondence. This contradiction shows that no such correspondence is possible. In other words, the real numbers are uncountable in number.

Are there any infinite sets that have more elements than $N$ but less elements than the set of real numbers?