Archive for the ‘Mathematics’ Category

The Poincaré Conjecture Explained

March 13, 2010

The Poincaré Conjecture is first and only of the  Clay Millennium problems to be solved.  It was proved by Grigori Perelman who subsequently turned down the $1 million prize money, left mathematics, and moved in with his mother in Russia.  Most explanations of the problem are overly-simplistic or overly-technical, but on this blog I try to hit a nice middle-ground.  Here is the statement of the conjecture from wikipedia:

Every simply connected, closed 3-manifold is homeomorphic to the 3-sphere.

This is a statement about topological spaces.  Let’s define each of the terms in the conjecture:

simply connected space – This means the space has no “holes.”  A football is simply connected, but a donut is not.  Technically we can say \pi_1(X) = 0 but I’ll explain this notation further on.

closed space – The space is finite and has no boundaries.  A sphere  (more technically a 2-sphere or S^2) is closed, but the plane (R^2) is not because it is infinite.  A disk is also not because even though it is finite, it has a boundary.

manifold – At every small neighborhood on the space, it approximates Euclidean space.  A standard sphere is called a 2-sphere because it is actually a 2-manifold.  Its surface resembles the 2d plane if you zoom into it so that the curvature approaches 0.  Continuing this logic the 1-sphere is a circle.  A 3-sphere is very difficult to visualize because it has a 3d surface and exists in 4d space.

homeomorphic – If one space is homeomorphic to another, it means you can continuously deform the one space into the other.  The 2-sphere and a football are homeomorphic.  The 2-sphere and a donut are not; no matter how much you deform a sphere, you can’t get that pesky hole in the donut, and vice-versa.

A donut and a coffee mug are homeomorphic.

What the conjecture is basically saying then is this:

Any finite 3-dimensional space, which doesn’t have any “holes” in it, can be continuously deformed into a 3-sphere.

This was proven for all dimensions > 3, but 3-manifolds proved to be the trickiest.

Now, how do you show that 2 spaces are homeomorphic to each other?  One way is to show that the spaces share the same fundamental group.  Hopefully you remember what a group is, but basically it’s a collection of elements which includes an identity element, and a  product.  Also each element has an inverse.  The fundamental group basically describes how many ways you can draw a path in a space.  It is organized as follows, where each element is a path which starts and ends at the same point.  The identity fundamental group is the trivial path of length 0, i.e. a single point.  The product in the fundamental group is just combining 2 paths end-to-end.  Since all paths start and end and the same point you can always take their product and get a new element in the group.

The fundamental group of the n-sphere is equivalent to the group with one element (the identity element), because any path can always “shrink” down into a single point due to the fact the n-sphere has no hole.  If a space’s fundamental group is trivial, then that means it is simply connected, as described above.  To say the fundamental group for any n-sphere is trivial you use the following notation:

\pi_1(S^n) = 0

Where \pi_1 means this group contains elements of 1-dimensional closed paths.   A little bit off topic but even more fascinating, is that you can also examine higher dimensional paths and these non-fundamental groups develop an interesting and complex structure.

Anyway, the Poincaré conjecture says that if for any 3-manifold, M^3, if \pi_1(M^3) = 0, then M^3 can be continuously deformed into S^3.

Perelman finally solved this for 3-manifolds by using Ricci flow techniques to show that these manifolds are homeomorphic.

Update: 6 years after his proof of the Poincare Conjecture and 5 days after this post, Clay Mathematics officially awarded the Millennium prize to Grigori Perelman.  If he declines, this could be the first time in modern history where someone living at home refuses $1 million.


3D Movies and Quantum Mechanics

February 3, 2010

As 3D media becomes more popular, it’s interesting look at the technology which allows light to be targeted to the left and right eyes separately.  If you saw Avatar in the theaters you donned glasses which have polarized lenses.  We can call the filter over the left eye “L-polarized” and the right filter “R-polarized”.  The movie projector emits unpolarized light, but that light can be passed through a polarization filter which is synchronized to each frame of the movie.  Frames meant for the left-eye are L-polarized so that they match the left-eye of the glasses, while frames meant for the right-eye are R-polarized.  In the RealD technology, the filter switches between L and R polarization 240 times per second, allowing 120 Hz frame rate for each eye.

Something interesting about polarization is that it works even with a single photon.  If you send an unpolarized photon through a L-polarization filter there is a 50% chance it will be blocked and a 50% chance it will pass through.  If you then this L-polarized light through another L-polarization filter it will pass through 100% of the time, but with an R-polarization filter it will pass through 0% of the time.  This is a purely quantum mechanical (QM) effect that cannot be explained through classic means.

A basic rule of QM is that if you want to observe the state of a system, you must make an observation by operating on the system.  In this case our observable is the polarity of the photon and our operator is the polarization filter.

Incredibly, QM says that the eigenvalues of a quantum operator are the observables, where the states of the quantum system are the eigenvectors!  If we can remember our eigenvectors and eignvalues from linear algebra we have the following:

H\, \psi = \lambda\, \psi

where, H is the operator, \psi is the eigenvector and \lambda is the eigenvalue.

Now for our observables to be real our eigenvalue solutions to this equation must be real, since QM tells us they are equivalent. (We assume our observables are real because we can only measure real values in nature, not imaginary one.)  In linear algebra, to assure that we have real eigenvalue solutions, the operator should be a Hermitian matrix.  This is a square matrix where the entries on opposite sides of the main diaganol are complex conjugates of each other.

Here is a table which sums up the relations in this equation:

Symbol Math QM 3D Movies
H Hermitian matrix quantum operator L or R polarization filter
\psi eigenvector quantum state L or R polarized light
\lambda eigenvalue observable L or R measurement

What’s bizarre is that when unpolarized light passes through the filter, it must “decohere” into the eigenvectors of L or R polarized light so that we get a real observable. The process of decoherence is one of the great mysteries of QM: particles only exist as probabilities until they are measured, at that point, Nature appears to “reset” them into a well-defined state.

Group Theory

December 14, 2008

I already wrote about Set theory and I eventually want to write about symmetry, so this seems like the perfect opportunity to discuss Group theory.  Let’s start where we left off with Set theory.  We had a very abstract concept of a Set: a collection of “things”.  Then we added some basic structure to that collection (the operation of set concatenation), and before we knew it we were counting and adding.

Well, to formalize it a bit, when you take a set and add a binary operation, and an identity element, then what you get is called a monoid.  Monoids are extremely abstract yet very powerful.  (In a way they even form the underpinning of all of computer science, where the set is a collection of functions, and the product is simply chaining these functions together, called function composition, and the identity is simply a “noop“.)  I’ll talk more about this in a future post because it is so cool how these ideas tie together.

A Group is just like a Monoid, except every element in the set must also contain its inverse.  When an element operates on its inverse, it results in the identity!  Some basic examples, are the integers\mathbb{Z}, where every element also has its addtive inverse, called its “negative”.  Another example are the rationals, \mathbb{Q}, where every element has its multiplicative inverse, called its “reciprocal”.  In the former example, the operation is addition and addtive identity is 0, while in the latter the product is multiplication and the multiplicative identity is 1.  Both of these groups also commute (i.e. the order of operation does not matter), and we call these groups “abelian“.  They are named after the mathematician Niels Henrik Abel, but strangely the word is not capitalized.

These groups may seem pretty abstract at first, but here are a few more tangible examples.  First, is that to physicists, a set with elements and their inverses will immediately remind one of a set of particles and their antiparticles.  But we can actually get much more tangible than that if we pull the same trick we pulled above with our monoid:  instead of thinking about objects, get Categorical, and think about processes.  It’s easy to imagine a set of transformations and their inverses: raise and lower, shrink and grow, cut and paste.  All of these examples have the identity of  “do nothing”.

Groups are strongly related to symmetry because an object which is equivalent to the original after transformations is at the heart of symmetry!  In future posts we will talk about the groups of rotations and reflections to explore these concepts.

Abstract Thinking

November 16, 2008

As a software engineer, abstracting problems is an important step in creating modular code.  Good abstract concepts are not only useful for a given problem, but they can also be applied in a variety of different situations.  It is especially exciting when 2 seemingly completely different problems can be described by the same abstraction, as this can lead to new insights and perspectives.  In fact, this paragraph itself can be abstracted by applying it to various fields besides software engineering!  I’m sure this analysis of the analysis would make Douglas Hofstadter proud ;) .

The most abstract ideas are those in mathematics.  Alone, the rules of math are not terribly useful (like a software interface without an underlying implementation), but they can be applied in extremely powerful ways to all other fields.  Let’s take the simple, yet incredible, example of numbers.

What is a number?  One explanation is to think of a practical example: pretend you have a basket of tomatoes.  You may want to count how many tomatoes you have and assign some label as the result.  These labels are numbers (or more specifically integers).  Why would you perform such a measurement?  Well in this case it seems very useful to take an inventory for storing, selling, cooking, or whatever you would like to do with your tomatoes. Now let’s say someone else gives you some more tomatoes or takes some away from you.  Numbers appear useful here too.  So we can define “operations” of addition and subtraction to accomplish this.

This concept of numbers and operations is abstract enough that you can clearly apply it to more than just baskets of tomatoes! In fact, you can apply it to “sets” composed of any “element” you can possibly imagine!  That is what a good abstraction is all about.

Let’s get formal about this in mathematical terms using Set Theory.  Given a Set S, there is a function f:S\rightarrow \mathbb{Z} which takes a set and counts how many elements are in it. This measure is called the cardinality of the set.

This function is often expressed by inserting the set in between vertical bars . Here are some examples of sets and their cardinality:

  • The empty set: |{}| = 0
  • A set of one tomato: |({tomato}| = 1
  • A set of letters: |({A, B, C, X, Y, Z}| = 6
  • A set of sets: |{{telephone}, {}, {1, 3}}| = 3

We can also talk about adding sets with another function: g:S\times S\rightarrow S.  This function takes two sets and outputs a third.  You can come up with a bunch of simple functions which do this, but one nice example is a function which concatenates the elements from both input sets and puts them into a single output set.  For example:$latex g({1, 3, 5}, {A}) = {1, 3, 5, A}.  What’s nice about this is that we can use this function to perform addition! since |{1, 3, 5}| = 3, |{A}| = 1, and |{1, 3, 5, A}| = 4.  And what is the additive identity?  It’s the empty set of course!  You can obviously cook up a bunch of other functions which relate to other mathematical operations as well.

This is all just scratching the surface, so we’ll have more cool stuff to go over in future posts.

How Polling Works

November 13, 2008

Terrence Tao has a great blog entry about the mathematics of polling.  One thing he points out, which to me at first was unintuitive, is that polling accuracy is independent of the total population size given a few basic assumptions (simple random sampling , honest responses, fixed poll size, etc…)  I higly recommend reading his post, if only for his intuitive examples of why the total population size is irrelevant.

[Update: some of his examples are so good, so I will just share them here. To test the salinity of the ocean accurately how many water samples would you need to take?  Although the ocean contains ~10^{21} liters of water, only a sample of a few milliliters (10^{-3} ) is necessary to get a good estimation.   That’s -24 orders of magnitude (compared to  -5 orders of magnitude for presidential polls).   Although I would guess that the entropy (uniformity) of ocean salinity is much higher than that of political opinions.  Another example is identifying faces.  Faces have their appearance based on millions of cells, however, people can readily identify a face based on only a few bytes of data such as a black and white pixelated image.]

So what can we do with this polling magic?  FiveThirtyEight is a great website where baseball statistician Nate Silver used his techniques to predict the presidential election.   He predicted, before the polls opened, Obama would receive 349 electoral votes and he actually received 365.  The only states he missed were Indiana and Missouri — pretty impressive.

Another great site which deals with predictions is Intrade.  This is where people buy contracts on certain future events.  The price of the contract reflects how likely the market believes it to be true. (although as economist Gregory Mankiw has pointed out this might not necessarily be true, since it is also an effective hedging instrument.)   I believe Intrade also only missed predicting Indiana and Missouri before the polls opened.