Tuesday, November 27, 2012

Discovery Cafe Day 3: guest post by Jonathan Herman

In the cafe today, more insight was given as to how mathematics is an ongoing process. In order to discover and learn, a mathematician needs to be constantly asking why, and how? Indeed, we had previously proved that there are infinitely many primes. But the question today was, now what? What other questions can we ask to further understand prime numbers? Who cares that there are infinitely many primes? How is this theorem useful in discovering new concepts and ideas?

Some questions asked by the group included: Is there a pattern among the distribution of prime numbers? Are there infinitely many primes of the form \(n^2 + 1\)? How many prime numbers are there less than n, for any integer n? This last question was actually conjectured by Gauss and  Legendre, and a strong approximation is given in the famous Prime Number Theorem. We discussed this interesting result: 
$$ \pi(x) \sim  \frac{x}{\log x} $$
i.e. \(\lim  \frac{\pi(x) }{\log  x /x} = 1 \, \,  x\to \infty \), where  \( \pi (x) \) is the number of primes less than \( x \). The group spent the rest of the time proving Euler’s amazing Product Formula and one of its consequences. See the other post about Day 3.   
This powerful formula gave a classic example as to why a mathematician, or anyone, should be constantly asking “now what?” Indeed the group then proved an amazing corollary to this formula: that \( \sum \frac{1}{p}  =  \infty \). This proposition seems very strange indeed.

Sunday, November 25, 2012

Discovery Cafe Day 3: A Prime Day

Here is a quick account of what happened in our third Cafe meeting on Nov. 20th.  As I was walking down the hall to go to our weekly meeting, I got the idea of expanding a bit on a theme that was touched on last week. As we saw in the last post, Euclid had proved in 300 BC that there are infinitely many  prime numbers (I think his actual statement  is that there is no biggest prime number). His method of proof was  proof by  contradiction as students saw last week.

Now this result opened the doors to  so many questions about the statistics of primes, many  of which are  still unanswered! I tried to expand on this  theme of how many primes are out there.

After nearly 2000 years Euler took the next giant step in this question. Around  1737 he not only gave a different proof of Euclid's theorem, but  he went  way beyond  that  and showed that the  set of primes is not too thin and in a sense there are many primes! See below for more about this.  One of his  statements  is so intriguing when  he writes
$$ \sum \frac{1}{p} =\log \log \infty $$
What he meant by this? Not so clear, but on a heuristic level one can argue that this hints at the famous prime number theorem which was precisely conjectured many years later and proved even many more years later down the road in 1890's. But we are  of course not yet ready to discuss all this. 

To prepare for all this  we decided to discuss and prove a simpler    well formulated statement.  More precisely  we settled to prove another statement of Euler's    that
$$ \sum \frac{1}{p} =\infty,$$
where the sum is over all primes of course. This statement not only shows that there are infinitely many  primes, it shows that in a sense the set of primes cannot be  thin! Taking a clue from the fact that the harmonic series
  \( \sum \frac{1}{n} =\infty \) is divergent, let us call  a subset \( S \) of integers fat if \( \sum_{n\in S} \frac{1}{n} =\infty \) and thin if  \( \sum_{n\in S} \frac{1}{n} < \infty.\) For example the set  of perfect squares is thin since we know that \( \sum \frac{1}{n^2} <\infty. \) So we set out to show that the set of all primes is a `fat'  subset of the set of natural numbers. Students noticed  that this is already a huge improvement over Euclid's theorem.

Euler's  main tool  in these types of questions related to primes  was an amazing formula that he found,    now called the Euler Product Formula:
$$\sum_n \frac{1}{n^s}= \prod_p (1-\frac{1}{p^s})^{-1}, \quad s>1.$$
(The sum is over all natural numbers and the product is over all primes). We spent some time proving this. To do this we
1. Carefully defined  infinite products,
2. Showed that in an infinite product
$$ \prod_n(1+a_n)$$
if  \( \sum_n |a_n| \) is convergent then the product is convergent and in that case the product is zero iff one of its terms is zero.
3. Used unique factorization of integers into primes to prove the identity.
4. Take limits  as \( s \to 1\) and use the fact that the harmonic series is divergent, to derive the divergence of the inverse primes series \(\sum \frac{1}{p}\),  and  hence the fact that the set of primes is not thin.

Tuesday, November 20, 2012

Discovery Cafe Day 2. Guest Post by Hanbo Xiao

This week we had another 3 fascinating topics brought up.
They are:
  •            Euclid’s proof of infinite primes
  •          The formulation of the quadratic formula
  •          The “Passengers on a Plane” Problem
What we can conclude from our journey into these topics is that problems that are shocking, ie that are very non intuitive, are actually quite simple with the proper point of view. Sometimes when we are stumped, if something seems impossible to prove, a slight out of the box thinking brings the problem to light, which turns into a light bulb moment leaving us with that warm and fuzzy feeling. So, as I have discovered for myself, if there ever is a time where something seems impossible, don’t be afraid to do something random. Perhaps it can open the door to something that no one has thought of before!

Infinite Primes
This proof, brought up by Euclid in 300BC, is one of the most extraordinary examples of ingenuity. His proof  that there exist an infinite number of primes,  he offered in his book “Elements”. He did so by contradiction:
First we need to establish a fact: Any integer can be broken down into a product of primes. As we have learned in grade school a number tree not only looks cool, it provides us with apples and those apples are the prime factors
With that in mind we can continue……….
Suppose there exist an infinite number of primes and pn is the largest amongst them.
Take the finite list of prime numbers p1, p2, ..., pn and let P be the product of all the prime numbers in the list: P = p1p2...pn.
Let Q= P + 1. Then, Q is either prime or not:
   If Q is a prime, then Q would be the largest prime and thus concludes the proof
2      If Q is not prime then some prime factor F divides Q. And the proof is that this F cannot be in the list of primes that we’ve already established.
See the simplicity in this proof? Neat eh?

Passengers on a Plane
Question: An airplane has 100 seats and is fully booked. Every passenger has an assigned seat. Passengers board one by one. Unfortunately, passenger 1 loses his boarding pass and can't remember his seat. So he picks a seat at random (among the unoccupied ones) and sits on it. Other passengers come aboard and if their seat is taken, they choose a vacant seat at random. What is the probability that the last passenger ends up on his own seat?

Think about this question for a while before reading forward

You may think the answer involves a massive beast of a series and you’re right! If you’ve tried to calculate this series……you are a hero. You should have gotten ½, this is the correct answer, which does make some sense. But here’s the funny thing: no matter how many people there are in this question: 100 people or 1000 people or 10000000 people. The last person who steps on the plane will be faced with two possibilities: either the last vacant seat is his own seat, or the vacant seat belongs to the first person who stepped on the plane. No other seat is a possibility.

My question is: does this make any intuitive sense? I will leave that up to you to think about…….

Thus concludes another day in the Discovery CafĂ©. Some very interesting things have appeared before our eyes. What I want to end with is this conclusion: Once a problem is solved, the problem becomes simple. But before we can see the path to the solution, even easy problem seems rather hard. This mirrors life. Things only become “easy” when we know the solution, but this rarely happens. My advice is to change your point of view, change your attitude and perhaps you will come up with something ingenious. And when you do share it with the rest of the world, it will make life “easier” 

Until next time………………

Thursday, November 8, 2012

Discovery Cafe Opens!

On  Tuesday, Nov 6, we opened the discovery cafe to all our undergrad students in mathematical sciences here at Western. We plan to have meetings on  a regular weekly basis for the whole year.
The regular cafe hours are Tuesdays, 4:30-5:30 PM, in Room 108 in Middlesex College building.

For a long time I thought we can enhance the training and education of our undergraduate students, beyond regular classes, tests, and exams etc. For  several years we had  round table discussions on an irregular basis. Now I think there is enough energy in the department   to test derive this idea on a regular weekly basis. And we have got a new name for this  event too: The Discovery Cafe!

For the record, I put here the  e-mail that was sent out to our undergrad students:

The Math Department invites all undergrad students in math and applied math to the new "Math Discovery Cafe".

The mathematics you see in books and lectures tends to be very polished. But it has not always been like this! At the beginning, new ideas are rough and sometimes fuzzy. Only after decades or even centuries of research and teaching does one arrive at the polished form you are used to. This might help to understand the theories, but it does not teach how to get to new ideas yourself. 

The goal of the Math Discovery Cafe is to give an idea of how research is actually done in mathematics. Through informal discussions, we will see how problems can be approached, and we will look at how mathematical ideas evolved over time. The Math Discovery Cafe is aimed at interested undergrad students in math and applied math. Its core group will consist of the Math Scholars group in our department, but it is open to all and we certainly encourage all our undergraduates to take part and become active in Cafe. It opens every Tuesday 4:30-5:30PM in room MC 107 (except when there is a conflict with the Pizza Seminar).  

What you can expect to happen during each math discovery cafe? A free, informal, impromptu, and in depth discussion of any math issues that may be raised or asked by participants. We won't leave any stone unturned!  Behind the counter you will meet, alternately, the Cafe owners Prof. Franz and Prof. Khalkhali! We look forward to meet you there!

Okay, now for the record I want to tell you what happened  during  our first Discovery  Cafe meeting. I am planing to post  later events as well  on a regular basis so that   hopefully it can be used as a resource by our students. I was surely amazed  by the number of questions and topics that we touched! Obviously we did not have time to go through any of them in any details, but surely planing to revisit all these questions in due time and with due respect! So this first meeting was a kind of brainstorming session and getting to know who is interested in what at the moment.

The first question was asked by Hanbo. He was wondering why it is  hard to prove that a closed curve in the plane divides it into two pieces. Rightly formulated, which we carefully did in class,  this is the famous  Jordan Curve Theorem. I was  not prepared to give an elementary  proof on the spot! I later checked that Wiki has a very good introduction to this and so I cite it here Jordan Curve Theorem. We just tried to prove special cases and surely  students  proved that a circle divides the plane in two pieces.

Then somehow our discussions turned into major shocking counterexamples (or examples!) in analysis that shaped the modern form of the subject  from late  19th century onward. They included:

  • Cantor's one-to-one correspondence between line and plane,
  • Invariance of domain and why the above cannot happen in a continuous  world, 
  •  Cantor's theory of cardinal numbers.

Again we were either not prepared or did not have time to discuss these in any details, but surely can go back to them in time.

If you think that was it, you will surely be surprised  to know that at the end  we brought up the  example of the Dirichlet function  and, for easy landing!,  we carefully proved that it is  continuous at irrationals and discontinuous at rational and is nowhere differentiable. It was asked  how this functions looks like? I should say this question had never occurred to me before, but  Johnathan could find a  graph in his textbook.We also very briefly touched the issue of how well an irrational number can be approximated by a rational number and if there is a hierarchy of irrationality in this way. That is,    can we somehow measure/decide if one irrational number is more irrational than the other?   Is there a most irrational number out there? Again no time to discuss this, but I promised we shall look at some of the amazing rational approximations to the number pi that were discovered by Archimedes and go from there.

So that was it for the first meeting, but of course we shall go in much slower pace next time and spend more time at each question or topics that we touch!