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!

## Wednesday, April 3, 2013

### 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.

## Friday, January 18, 2013

### 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

We say f has the

$$ \Delta f=0$$

where \( \Delta f = f'' \) is the second derivative operator, 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.

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.

## 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.

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

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

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

Euler's main tool in these types of questions related to primes was an amazing formula that he found, now called the

$$\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.

*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

*p*is the largest amongst them._{n}
Take the finite
list of prime numbers

*p*_{1},*p*_{2}, ...,*p*and let_{n}*P*be the product of all the prime numbers in the list:*P*=*p*_{1}*p*_{2}...*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”

## 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:

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:

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!

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,

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

Subscribe to:
Posts (Atom)