A Stroll on Strange Spaces

Pizza Seminar Talk:   Tuesday, April 9, 2013, 4:30-5:30 PM, MC 108. 
Speaker: Mitsuru Wilson
 

 Like the above ad  promoting a potent Nitro NCG mixture, Noncommutative Geometry (NCG), as created  by  Alain Connes is a potent
 mixture of many ideas in mathematics and physics.

One of the grand themes in mathematics, geometry, dates back for thousands  of years. Starting from Euclidean spaces, many elementary shapes such as circles, disks, spheres have been studied until today; all spaces we learn in school are still studied today! Riemann then generalized Euclidean spaces with his foundation of manifolds, which was then used by Einstein for his theory which successfully encodes our knowledge of space-time and gravity.

With all they knew they did not understand quantum mechanics. The geometry is very fuzzy, uncertain, probabilistic and entangled there. Although it was introduced theoretically, this analogy works to explain noncommutative geometry (NCG) very accurately. The celebrated 1943 paper by Gelfand and Naimark proves the anti-equivalence (functors are contravariant) between (the
category of) compact Hausdor spaces X  and (the category of) commutative C* algebras A. In the construction, A is nothing but C(X), the algebra  of continuous functions . This correspondence gives rise to the viewpoint that any C* algebra is the  space of functions C(X) of some noncomutative space X . They are fuzzy spaces in the sense that we cannot directly see them! My goal in  this talk is to present the basic idea of Noncommutative Geometry in as elementary terms as possible and discuss a few canonical and fascinating examples in NCG.

Absolutely no background is necessary!

First Steps in Quantum Computing

 Discovery Cafe Talk: Tuesday, April 9, 5:30-6:30 PM, MC 108.  Pizza to follow immeditaley after!

Speaker: Masoud Khalkhali

Public-key encryption and security of internet communications is based on a certain mathematical hypothesis:factoring a given integer  N is a computationally difficult problem. The best current methods take about

$$ O(e^{1.9 (\log N)^{1/3} (\log \log N)^{2/3}})$$

operations. This is almost exponential in log N, the number of digits of N

A quantum computer, running Shor's algorithm, can factor N in

$$O((\log N)^3)$$

steps! This is polynomial in log N, or polynomial time,  and a huge improvement over current methods.

This talk will introduce  mathematics and physics ideas behind quantum computing and Shor's fast factoring quantum computing algorithm.

Random Walks and Brownian Motion

This Tuesday, Jan 15,  we had our  first Discovery Cafe  meeting in 2013. I had promised before to give some introductory lectures on random walks and Brownian motions. So  we started the year with this. Notice that now we meet at 3:30 PM on Tuesdays. Ruth took some  notes and I am just  using these notes here. I leave out many details. For references you can check out these two books:  1 and 2

There are two problems that at first look quite unrelated but our first task is to understand  the close relation  between the two. Random walks and the Dirichlet problem.  In one dimension, on a finite set of points 0, 1, .....up to n, a  walker randomly walks around. The chances of going forward or backward is   % 50 each . Let P(i) be the probability of the random walker hitting  the right end  point  n before hitting the end point 0, when he starts at i. Say point n  is the jail, where the police can keep the drunk overnight, and  point 0 can be the drunk's home. So we are looking at the probability that he will end up at the police station, versus ending up at home. This  process is potentially infinite - the drunk can take up to an infinite number of steps back and forth without hitting either boundary. But never mind this at the moment and we neglect this possibility. We come back to this in the  next week when we carefully define our probability space.

Finding  the probability distribution P(i) is closely related to another problem, the discrete Dirichlet problem. We are looking for a function  f(i) for i=1, ....n-1, with given boundary values  f(0)=0 and f(n)=1, and such that f satisfies  the equation

$$f(i) = \frac{f(i + 1) + f(i-1)}{2}$$

We say f has the mean value property. We shall see that this equation is the discrete analogue of
$$ \Delta f=0$$
where \( \Delta  f =  f'' \) is the second derivative operator, the Laplace operator in dimension one. Thus f can be regarded   as a discrete harmonic function with given boundary  values f(0) and f(n).

 We checked that this Dirichlet problem has a unique solution. While a proof of this fact in dimension one is very easy and one can write in fact simple formula for f (what is it ?), existence of solutions in higher dimensions even in this discrete case is not totally trivial and in particular no simple formula exist. So the point of this probabilistic approach is that it works in all dimensions with minor modifications.  First of all uniqueness follows from the following  maximum principle:

Lemma (maximum principle): Any harmonic  function achieves  its maximum on the boundary points.

This easily follows from the mean value property. Then we used this maximum principle to prove uniqueness:
for any two solutions the difference \( f_1-f_2 \) is also a solution with boundary values equal to zero. This  will violate the maximum principle unless \( f_1 = f_2 \) at all points.

Our next goal was to show that the the probability function P(i) has the mean value property. Since it clearly satisfies the required boundary conditions,  this will prove that P is the harmonic function we were looking for. This is the first relation between random walks and the Dirichlet problem.


This all follows from a cute property of probabilities: Let X be a probability space, L and R be two mutually exclusive events that cover the whole X. Then for any event E we have
 $$Prob (E)= Prob (E; L) Prob (L) $$
$$+ Prob (E; R)Prob (R)$$

 Starting your random walk at i, let L = going left,  R = going right, E = the event of getting to the end  point n  before getting to 0. Now it is not difficult to check, using the above probability identity,  that  P has the mean value property and since it clearly satisfies the boundary conditions it must be the solution of the Dirichlet problem. 

Next week we shall carefully defines the probability space X, as the space of all random walks and show how to define a probability measure on it, and will give a general formula for the solution in terms of integration over this path space. We shall then move to higher dimensions where things can get more even interesting!   Here is graphs of some random walks all starting  at the origin and going up to 100 steps.

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.

 

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.

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 p_n is the largest amongst them.

Take the finite list of prime numbers p₁, p₂, ..., p_n and let P be the product of all the prime numbers in the list: P = p₁p₂...p_n.

Let Q= P + 1. Then, Q is either prime or not:

1     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………………

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:

• Peano's space filling curves,

• Weirestrass'  nowhere differentiable continuous function,

• Cantor's one-to-one correspondence between line and plane,

• Invariance of domain and why the above cannot happen in a continuous  world, 

• Smales' sphere eversion (this was asked by Johnathan, and we were surely not prepared to go through it!)

•  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!