Coulomb's law

About a year ago, I discovered a very interesting short video by Richard Feynman responding to the question of what happens when we hold two magnets next to one another. His answer was brilliant.

Recently, I came across a video from the 50s where a physicist is conducting experiments trying to explain electrostatics and, more precisely, Coulomb's force. What is very interesting is that he doesn't merely present facts, but also argues, from various points of view, trying to convince the listener that the force must depend on the distance r between two charges as a linear function of 1/r² (and linearly on each charge). The argument, especially towards the end, is not dissimilar from that of a mathematician who is trying to explain Potential Theory and Laplace's equation. In the end (skip to 17'22'' if you wish), we realize, with a bit of thinking, that a lot of the things we see in the experiment are merely outcomes of geometry and the fact that we live in a 3 dimensional space (this is an experimental observation that works well!) where distances obey the Pythagorean theorem.

I found out that the physicist is Eric Rogers. The video was intended to be for secondary schools. These days, one can find students of electrical engineering who do not understand electrostatics, students of mathematics who do not understand what potential theory has to do with physics, and educators (they are called pedagogues--and, as I have explained, they form a modern type of plague) who insist that education is independent of the discipline. Not that there aren't universities that teach properly and students who understand a lot, but this species (those who strive to understand and, hence, to explain) is becoming rarer and rarer.

Penrose tiling in Helsinki

Downtown Helsinki I stepped on a pedestrian street tiled with the standard nonperiodic Penrose (kite and dart) tiling.

This tiling consists of two basic shapes, the kite and the dart, both derived by taking a canonical pentagon inscribed in a circle, splitting it into 5 triangles with common vertex the center of the circle, and then making a variation on one of these isosceles triangles: take the side of the triangle which corresponds to a chord of the circle and make an inwards bump to obtain the dart (blue figure below) and an outwards one to obtain the kite (red figure).

Then follow some rules on how to join copies of these pieces so as to completely cover the plane. The result is a non-periodic pattern: no finite portion of it can describe the whole tiling. In particular, the tiling has no translational symmetry and is self-similar. Here is another picture and below it my attempt to show you its basic shapes. Kites are red, darts are blue.

The interesting thing with this tiling is that it appears as if it will repeat itself after a while, but it won't (this is a theorem). Nevertheless it is not random because it is created from a set of specific rules.

The tiling was discovered first by Roger Penrose 40 years ago. It was known that one could produce non-periodic tilings with a finite number of shapes but Penrose managed to do this with only 2. In nature, there are materials (quasicrystals) exhibiting such behaviors. Since the Penrose tiling is based on the pentagon, the so-called golden ratio plays a fundamental role. Indeed, if we call  A, B, C, D, E the vertices of a canonical pentagon (in the ordered traversed when going around in one direction) and let X be the point of the intersection of the chords AC and BE then, using similar triangles, we see that AX/AB = AB/AC. (The triangles ABX and ACB are similar, i.e., one is a scaled version of the other.) If we let AB=a and AX=b, then we see that AB=a and XC=a, so AC=AX+XC = b+a. The equality of the ratios above then becomes b/a = a/(a+b), so if we let  φ be the ratio b/a, we have φ = 1/(1+φ) which means that φ² + φ = 1. But (φ+(1/2))² = φ² + φ + (1/4) = 1 + (1/4) = 5/4, and so φ = (√5 -1)/2, a number known and used since times immemorial.

If you have java installed and enabled on your browser, you can play with trying to create variations of non-periodic tilings using the Penrose tiling applet. (Or see the PhD thesis of Craig Caplan.)

But the interesting thing is what a then young PhD postdoctoral physicist, Peter Lu, found out some 10 years ago in (the Islamic) Darb-i Imam shrine in Isfahan, Iran, dating from 1453. He observed that the patterns forming the wall decorations form a non-periodic tiling, just as the Penrose tiling. In fact, you can see the kites and darts in the picture below.

He then wrote a paper with (P Steinhardt) analyzing this.I think that, since then, non-periodic patterns have been discovered in other places in the Islamic world. And businesses have grown out of it.

The fascinating thing about this discovery is two-fold. First, its mathematical interest and the fact that non-periodic tilings had been discovered more than 500 years ago. Second, the fact that they had been discovered empirically. Which makes us wonder why on earth would those Muslim decorators be interested in creating something so complex. My reasoning is as follows. It is known that, in Islam, people are very restricted with what kind of things they are allowed to decorate their temples/mosques/shrines. Gods and the like are not allowed. Human forms are not allowed. Animals or plants are not allowed (exception: in Iran, but that is, I am being told, a remnant of the pre-Islamic religion). Any concrete objects are not allowed. This is why Muslims have very few things they can play with: abstract patterns, tilings, geometric figures. But, even within this restricted framework, humans' minds can be quite creative. Humans have an innate need to be free, to explore, to wonder, to create. When authority or religion impose restrictions and rules, humans will try as much as they can to break them, even unconsciously. It seems that this is a prime example of the innate need for freedom of expression.

Statistics Workbook for Dummies

Some time ago, I came across a book titled "Statistics Workbook for Dummies". The for-dummies series is well-known and is supposed to be a series of popular math/science/etc books. But this book is, really, for morons, written by morons. On page 102 of the book, the central limit theorem is "explained" or "motivated" thus:

Of course, this is misleading and is not an explanation of the central limit theorem at all.

The central limit theorem is a theorem in mathematics which has some physical consequences. Its proof requires some mathematics and cannot be fully understood without it. Can it be explained, however, to a non-specialist? Sure, but the explanation is not as trivial as the phrase above suggests. For those who want to apply the central limit theorem, understanding what it is about is essential. Like many other "popular" books in mathematics, statistics, phsysics, science, ... this one makes a bad job. Not surprising. It's one of many many others.

But the problem, you might think, is that the book is, indeed, for dummies. After all, it says so in its title. So, you might think, if you go to the university and take a statistics class in a "quantitative department" (by this I mean, mathematics or engineering or physics, or some other department which does not shy away from mathematical symbols....) you will understand the central limit theorem. Wrong. I have seen generations of students graduate from various reputable "quantative departments" who never learn a proof of the central limit theorem nor what the theorem is about. What is the problem? Well, many of the people who teach that stuff do not know themselves what mathematics is about and yet insist in teaching mathematics. Amazing as it may sound, it is not far from the truth.

Summary: "Statistics Workbook for Dummies" is doing a bad job but this bad job is not much worse than the job being done in many self-proclaimed reputable universities.

Brain scans and beauty in mathematics

Hot off the press:
Brain scans show a complex string of numbers and letters in mathematical formulae can evoke the same sense of beauty as artistic masterpieces and music from the greatest composers. The same emotional brain centres used to appreciate art were being activated by "beautiful" maths. The researchers, from University College London, suggest there may be a neurobiological basis to beauty and their study was published in the journal Frontiers in Human Neuroscience.

Of course, this is not news to people doing mathematics. But it is nice to know that it can be confirmed independently, or that methods are slowly arising for evaluating such things as "beauty", "elegance", etc. Perhaps, one day, we will have some criteria for other kinds of states which belong to the emotional domain, and, perhaps, we will even be able to quantify such things like morality.

Marcus du Sautoy, mathematician and professor for the public understanding of science [Dawkins' successor in this],  said he "absolutely" found beauty in maths and it "motivates every mathematician". [He is almost right. He should remove the pronoun `every' or define the term `mathematician', for there certainly exist `mathematicians' who are not motivated by beauty but, rather, for example, how much money they can raise or how many papers they can publish (regardless where), and other factors.]

Again, we should be careful in generalizing and cautious in interpreting what the news article linked above says, as it concludes by stating that, "in the study, mathematicians rated Srinivasa Ramanujan's infinite series and Riemann's functional equation as the ugliest of the formulae." At the very minimum, most of us know when something is beautiful or not and also know that beauty may not be apparent from the very beginning, and that it may take a lot of ugly, hard, persistent work, frequently by more than one person, in order that this beauty be revealed and finally be written down so that others may admire [or ignore].

Stopping time property of hitting times

Suppose that F_t, t ≥ 0, is an increasing family of σ-fields of subsets of a set Ω,  such that ⋂_{ε > 0} F_t+ε = F_t, for all t ≥ 0.

Let F be a σ-field on Ω such that F_t ⊂ F for all t ≥ 0.

Let P be a probability measure on (Ω, F). Assume that each F_t contains every subset N of Ω  included in some set A_N ∈ F with P(A_N)=0.

Let, for each t ≥ 0, X_t be a measurable function from (Ω, F_t)  into a Polish space S, where the Polish space is equipped with the Borel σ-field B, i.e., the smallest σ-field containing all its open sets.

Assume that, for all ω ∈ Ω, the function t → X_t(ω) is continuous or right-continuous with discontinuities of first kind only.

Let B ∈ B, and define T_B := inf{t ≥ 0: X_t ∈ B}. Then T_B is a measurable function from Ω into [0, ∞] such that {ω ∈ Ω: T_B(ω) ≤ t} ∈ F_t, for all t.

Probabilities and Potential, by Claude Dellacherie and Paul-André Meyer.

Lévy's forgery theorem

I asked my students in the exam of my graduate probability class to prove Lévy's forgery theorem which, in folk terms, states that if you run a Brownian motion long enough then it will write your signature (provided your signature is performed continuously). The one-dimensional version of this can be stated in mathematical terms as follows.

Let B be a Brownian motion and let f be a continuous function (your "signature"). Assume B(0) = f(0) = 0. Then, no matter how small ε > 0 is we will for sure be able to find a time interval of length 1 such that B will differ from f on that time interval by at most ε.

To prove this, all we have to prove is that there is a positive probability that the above will happen on the time interval 0 ≤ t ≤ 1, and then appeal to ergodicity (a theorem in probability): if you toss a coin sufficiently many times, you will for sure bring a head, provided that the probability of a single head is positive (assuming that coin tosses are independent).

The idea for proving the above is as follows. Split the interval 0 ≤ t ≤ 1 into n subintervals I₁, ... , I_n of length 1/n each and pick n so large that the maximum change of f within any interval of length 1/n is at most ε. (This can be done because f is uniformly continuous.)

Then observe that on each interval  I_k, the maximum deviation of B from its value at the beginning of the interval is smaller than ε with positive probability. This requires understanding that the maximum of a Brownian motion has density which leaves no gaps.

Also, observe that the difference of B and f at the beginning of the interval I_k can also be made smaller than ε with positive probability because when we observe a Brownian motion on equally spaced times, such as 0, 1/n, 2/n,..., then we are observing a random walk with normal increments.

Putting these things together we obtain a proof.

Intuitively, the proof was based on the following observation: The maximum difference of B(t) from f(t) will be small if 
(i) the maximum deviation of B(t) from its value at the beginning of the interval I_k containing t is small,
(ii) the difference between B and f at the beginning of this interval is small, and
(iii) f does not change much on this interval.

You might say, well, yes, this result is correct, but I might have to wait really long time to see my signature. And you'd be right. The analogy is this: if the probability of heads is 10^-10 then you will have to wait on the average  10¹⁰ billion seconds (more than 300 years) to see a single head, if you toss one coin per second.

We spoke of  "an interval of length 1'' above. Why? Is there any reason? No, absolutely none. By scaling, we can prove the same thing for any length. But this means that you don't have to wait too long, provided you don't mind if your signature is written in tiny letters. That is, the following holds:

When you wake up in the morning, pick a particle and make it move like a Brownian motion. Arrange things so that the particle's motion is monitored by a computer which keeps track of all places it visits. Go make a cup of coffee and come back and look at the computer files. The trajectory of the particle is stored in there. Zoom in, and zoom, and zoom, and zoom, and move around, and you will see your name. In fact, you will see the whole Bible, both in Greek and in Hebrew.

Is that amazing or what? You may say, "I don't believe this". This is a false statement. It's not a matter of belief. It's a matter of proof. Assuming that the hypotheses hold, the conclusion is true. The catch is, of course, that the hypotheses are mathematical ones and whether they are met in reality is a different matter. Of course, there is no such thing as "complete independence'' in real life, and there is no such thing as ``particle with infinitesimal size'' in real life. (Also, there is no such thing as a straight line...) However, a physicist can assure us that, with high precision, the assumptions are not unrealistic, meaning that, yes, even in real life the above claims are true. When it comes to seeing your signature some time far in the future, yes, you will see it, but it will take long time. When it comes to seeing your signature before you have finished your cup of coffee, all you'll see is black space because when you zoom and zoom and zoom, after a while you'll hit the limit imposed by the particle's size.

There is no problem with mathematics. There is no problem with physics. However, there is a problem with the word "belief". Simply, the word does not exist.

Arithmetica Universalis

Staffan Rodhe's office door was open today, I was passing by, so I dropped in. I was admiring the collection of ancient mathematical texts on his shelves. I first picked up a book by Lagrange, then one by Euler, and then the Arithmetica Universalis by Newton. I opened it somewhere in the middle and found a square piece of paper  (size around 10 cm) with some equations on one side and a couple of geometric drawings on the other. Clearly, it belonged to an careful reader of some past century. Most likely, Staffan explained, it was written some time in the 18th c. I took a couple of photos of both sides, as well as a copy of the title page of the book because they are, in my opinion, like pieces of art. It also makes me wonder how people thought back then, how similar to us they were, etc. Note that this edition of Arithmetica Universalis was published in 1732 in Lugdunum Batavorum, i.e., Leiden. There is a free version on the internet from a 1752 copy from Amstelodamum (Amsterdam). The original edition dates from 1707.

The theorem of option pricing made EZ

I am writing this to convince an analyst friend of mine that the so-called theorem of option pricing has nothing to do with probability and that, philosophically, is very simple.

I will prove the fundamental theorem of option pricing in a trivial case.

Suppose there is a box which transforms the dollars you put in into something of different value. For example, I put 1 dollar in the box and this becomes either 10 dollars or 0.01 dollars. The problem is that I don't know what the output of the box is and also I know nothing about the probability of the outcome. All I know is that 1 dollar turns magically into something else: either 10 dollars or 1 cent.

More generally, suppose that the box takes a token that is valued at $S$ dollars and spits out another token that is valued $S'$ dollars which could be higher or lower than $S$. To be concrete, and also keep things simple, let's say that $S'$ is either $(1+b)S$ or $(1-a)S$. If we put $u$ tokens in the machine, then the machine will spit out exactly the same number tokens all of which will be valued the higher price or all at the lower price. We allow the number of tokens to be any positive number, for example 2/3 of a token is possible. Assume that $0 < a < 1$ and $b >0$.

Now, me being a smartass, tell you the following: "Listen buddy, the machine makes money, not all the time, but sometimes. I give you the following option: You won't have to do anything. I will operate the machine for you. If it makes money I will give you some. If not, you won't get anything."Oh, great", you reply, "go ahead". "Well," I say, "you know, you have to pay me a bit now, so that you get the benefits later." "How much," you ask. "We'll figure it out", I reply.

To make things general let's say that our contract is a certain function

$f(S')$

meaning that if the machine turns changes the value of one token to $S'$ dollars then I will give you $f(S')$ dollars.

My rationale is as follows. I'm not a sucker. I won't risk anything at all. I will charge you $X$ dollars and, with this, I will buy $u$ tokens, costing me $uS$ dollars, and put the difference $c = X-uS$ aside. I will put the $u$ tokens in the machine and the machine will change the value of each token to $S'$. In the end, I will have $uS'$ dollars from the machine, plus $c$ aside, which means that I wil have

$Y = uS' + c$ dollars

and since I am a gentleman, I will have to fulfil my promise, meaning that

$Y = f(S')$.

Since $Y-X = u(S'-S)$, we see that

$X+u(S'-S) = f(S')$

must be fulfilled. And this leads to two equations with two unknowns, $X$ and $u$. The equations are:

$X+ubS = f((1+b)S)$,     if the price goes up,
$X-uaS = f((1-a)S)$,    if the price goes down.

Subtracting the second from the first gives

$u = \frac{ f((1+b)S)- f((1-a)S)}{(a+b)S}$.

Putting this back into the second equation, we find

$X = \frac{a}{a+b} f((1+b)S) + \frac{b}{a+b}  f((1-a)S)$.

I observe that my solution is good, because $u \ge 0$ and because both $u$ and $X$ depend on nothing else (not on my astrologer, neither on my mood) except the price $S$ of the token. So I tell you that: I will charge you $X$ dollars. (If $uS$ turns out to be larger than $X$, then I will temporarily borrow $c$ dollars and return them at the end.)

That is all.

Now that you have learned the above, you can create a dictionary of jargon:

1. Market: it is the box you see above in the picture.
2. Share: the token.
3. Stock: a set of tokens.
4. Bond: the quantity $c$; with $c$ positive (respectively, negative) interpreted as buying (respectively, selling).
5. Portfolio: the pair $(u,c)$.
6. Hedging strategy: it refers to the number of tokens $u$.
7. Option: the function $f$.
8. Price: the variable $X$.
9. Completeness: it refers to the fact that there is a unique solution $(u,X)$ to the system of equations. (If $S'$ takes not two, but three values, completeness is lost.)
10. Arbitrage: the absence of arbitrage is that I make no money. 
11. Transaction cost: I may charge you an extra fee.
12. Equivalent martingale measure: You can think of a random variable $R$ taking value $a$ with probability $b/(a+b)$ or value $b$ with probability $a/(a+b)$ (these probabilities constitute the probability measure), write $S'=(1+R)S$ and rewrite the equation for $X$ as $X= E[f(S')] = E[Y]$ (one says that $(X,Y)$ is a martingale).

Who could have ever thought that there is such a rich dictionary behind a simple equation?

By the way, what theorem have we proved? Cast in the fancy terminology, we have proved a theorem saying that, in our complete market with no arbitrage, any option can be priced fairly by using a unique hedging strategy which specifies our portfolio in terms of shares of stock and bonds.

In reality we have proved that I lure you to put your money in the magic box, that I have no risk of losing anything, and that it is you who bears all the risk. However, by charging a bit more than the fair price $X$, by doing the same not just with you but with a few thousand other people whom I attract by designing fancy options $f$, I surely make some money.

Unlearning bad habits

One of the major obstacles in teaching at an advanced level is that we often have students with preconceived ideas. (The term "students" should be intepreted in the broader sense. It may include ourselves, for example.) Here is an example I have come across to many times, in the teaching of probability.

I ask the students to prove that if we take the points of a homogeneous Poisson process on the real line and translate each one of them by an independent random variable then we get again a Poisson process with the same rate.

For example, we may perform the translations by independent standard normal random variables.

The student often has a preconceived idea that a Poisson process is a random function of time $(N_t, t \ge 0)$ such that

1. It starts from zero: $N_0=0$
2. It is right-continuous, non-decreasing with values in $\{0,1,2,\ldots\}$
3. It has stationary and independent increments.

One problem that the student faces (if he or she does not remember the definition I gave in class) is that the question above says to consider a Poisson process on the real line. So, after some thought, the student realizes that the following definition works:
Let $N'$ be an independent copy of $N$. Extend $N$ on $t \in (-\infty, 0)$ by letting $N_t := N'_{t-}$. It can then be checked that the process $(N_t, -\infty < t < \infty)$ satisfies

1. $N_0=0$
2. It is right-continuous, non-decreasing with integer values
3. It has stationary and independent increments.

Rightly then, one can say that $(N_t, -\infty < t < \infty)$ is a Poisson process on the real line. Next, the student attempts to solve the problem by, say, doing this. They define the times of discontinuities of $N$ by $\cdots < S_{-1} < S_0 < S_1 < S_2 < \cdots$, agreeing, for instance, that $S_0 \le 0 < S_1$ (after all, the origin of time must be placed somewhere--and this agreement is up to us), then define $T_n := S_n +X_n$, for each integer $n$, where the $X_n$ are independent identically distributed random variables, and then try to show that the process with discontinuities at the times $T_n$ has exactly the same law as $N$.

This is an almost impossible task. The reason is that the student immediately realizes that the new points are not even ordered in the same way as their indices (something that was true for the old points). In fact, the ordering of the new points is random! Definitely, there is a first new point to the right of the origin of time, but this is not necessarily the point $T_1$. In fact, if the $X_n$ are standard normal, the first point to the right of $0$ could be the point $T_{517}$ with some probability, or the point $T_{-29}$, etc.

The student then may ask me for a hint. I try to bring in to them the idea that the above definition may be OK for some purposes, but that it has fundamental drawbacks. It is much better to first define a Poisson process as a random discrete subset of the real line such that the number of points contained in fixed (nonrandom) disjoint subsets of the real line are independent random variables. From this, it follows that the number of points in a set is a Poisson random variable with mean depending on a deterministic function of the set (this function being a nonnegative measure which, in the homogeneous case, is a multiple of the Lebesgue measure). From this definition it is not hard to show that the previous one is a theorem. Moreover, this is a definition which extends to higher dimensions and even to infinite dimensions.

But getting rid of preconceived ideas is very hard. Especially when teachers insist on a traditional way of approaching things.

One should not, actually, underestimate the fact the inertia of many teachers (as I said, the term "student" includes ourselves) to unlearn something and learn it from a different point of view. This is a major obstacle in the teaching of Mathematics.

Swedish tabloid on mathematicians and gods

Earlier this year, some guy called Marcus Birro wrote a silly article in a Swedish tabloid called Expressen, where, among other things, he tells us that he couldn't undestand why use symbols instead of numbers in school, that he doesn't like mathematicians because they sit down all day doing nothing, that they have no feelings, and that, therefore (!!!), god exists.

I sent him the following email:

From: Takis Konstantopoulos

Date: Thu, Oct 27, 2011 at 7:00 PM

Subject: matematik och gudar

To: marcus.birro@expressen.se

Mr Birro,

I "read" your article in Expressen, as far as I could understand it via google-translate. You are, actually, so very wrong about your impression of what a mathematician is. Mathematics is much more than what you learned in high school. Most likely, your teachers were pretty bad, uninspiring, boring,... just as many mathematics schoolteachers world-wide. They gave you the impression that doing mathematics with numbers is not the same as doing mathematics with letters. You do not understand that 1, 2, 3, and so on, are mere symbols, just as a, b, c. You do not understand that mathematics is not about numbers. You also do not understand what a proof means. I do not blame you. I also do not understand how DNA works, because I lack knowledge of biology and chemistry. However, I do understand that molecular biologists are not spending their time merely memorizing the sequence of atoms comprising a DNA molecule. Just as I understand that a journalist doesn't, simply, take a piece of gossip he or she has heard from his or her buddies and write an article about it. I'm afraid you have not done your homework and are simply expressing an opinion which is the equivalent of shouting slogans in a football match.

I will not try to comment on your opinion of god or gods. (Who knows how many there are?) Your proof of existence of gods is that mathematicians are useless. How absurd!  Think a little bit, if you can, and see how unsubstantiated your claims are. I can tell you that no mathematical formula can measure what is happening in my heart when reading a poem of Cavafy, just as no formula can measure what is happening in your heart when you read a poem by Dan Andersson (in your words). But this is neither an argument against mathematics, nor an argument for the existence of gods, my friend. What is happening in our hearts, the love you feel for your children, is what is happening in other primates' hearts too. Being the product of a complicated evolution, which is beyond your understanding (and mine, for that matter), love and hate, and the ability to write silly articles like the one you did, emotions and feelings keep us alive and can be explained via chemistry and physics and biology and neuroscience. But you have to be patient for science to evolve too. And also try very very very hard to understand (some) science and learn (some) mathematics.

The easy solution is to say "gods exist and therefore this explains the love I feel". And you think you're done. This is the lazy approach. Just as the fact that I need an incredible amount of training in order to play a little piano piece well, so you too (and everybody who is outside a field) need a lot of training in science and mathematics in order to be able to understand why letters and numbers can express human thought and lead to a proof. However, even though I do not have the time (or ability) to learn piano like, say, Andrei Gavrilov, I can and do appreciate not only his playing, but also his effort and thinking. Why? because I can compare judiciously. Likewise, even though you may have no time (or ability) to learn any mathematics, you can, with a bit of effort and comparison and extrapolation, appreciate something which lies beyond your sphere of understanding.

Just try it. You can.

And then you can correct your article.

Sincerely,

Takis Konstantopoulos

He hasn't replied to me. I wonder why.

Mathematics screening test for university students

I am writing this in response to my friend Joe who tends to believe that things in US education are bad. In fact, for anyone who thinks that things are bad in the particular place he or she happens to work.

This is a screening test I gave to second year university students (school of mathematical sciences of a UK  university I worked at earlier). The rationale behind a screening test is to alert the students that they should not take a further course without having basic skills acquired in earlier courses and that, if they have not learnt earlier material, they should repeat the courses before proceeding further.

The front page of the linked document contains statistics of students' responses. The remaining pages contain the questions I asked, together with sample responses. I would say that out of 60 students who took the test, there was probably one who could, perhaps, qualify as a university student. The remaining ones had no clue.

Although the document is self-explanatory, here are some of the questions, along with the most funny answers:

Q:  Given two polynomials $p(x) = \sum_{k=0}^n a_k x^k$ and $q(x) = \sum_{k=0}^m b_k x^k$, express the coefficient of the term $x^k$ of the product $r(x) = p(x)q(x)$ in terms of the coefficients $(a_k)$ and $(b_k)$.
A: $a_{k^{1/2}} b_{k^{1/2}}$.

Q: Define the concept of the derivative of a function $f : R \rightarrow R$ at a point $x$.
A: This is the distance of the point $x$ from the origin on a plain  [sic].

Q: Explain what we mean by the integral $\int_0^1 f(x) dx$ of a function $f : [0; 1]  \rightarrow R$. (The answer "area under the curve" is not acceptable.)
A: By integrating this function, we are being asked to calculate an area, and by providing definate [sic] integrals, the question asks us to provide a specific area.

Q: In how many ways can you put 5 indistinguishable balls in 7 distinctly numbered boxes and why?
A: 21/5.

Q: Expand $(a + b)^5$, where $a, b$ are real numbers.
A: $(a + b)^5 = \binom{a}{0} + \binom{a}{1} a^4 b + \binom{a}{2} \frac{a^3 b^2}{2!} + \binom{a}{3} \frac{a^2 b^3}{3!} + \binom{a}{4} \frac{ab^4}{4!} + \binom{a}{5} \frac{b^5}{5!}$.

Q: Compute the (indefinite) integral $\int dx/\sqrt{x}$.
A: $-2u+C$.

The huge problem in education, around the world, is that the meaning of the verb "to learn" is frequently disassociated from the verb "to understand". This is convenient for students. It is also convenient for many teachers who do not want to bother to understand and explain. It is convenient for politicians. It is convenient for administrators. In short, it is convenient for everyone. Except that the result is the production of generations of students who get a degree in, say, mathematics, but know very little mathematics. What is worse, is that they think they know. It is more dangerous to have people who believe they know rather than people who know they do not know (and, therefore, may try to learn whenever necessary). Someone who is convinced of his/her skills will do nothing to improve them.

A new very short proof of the fundamental theorem of algebra

I've always been intrigued by the fundamental theorem of algebra (every nonconstant polynomial with complex coefficients has a root), not least because I don't know any proof which uses algebra only. Earlier, I posted an easy proof in this blog, one that uses Cauchy's theorem.There is a recent proof (Oswaldo Rio Branco de Oliveira, Mathem. Intellig., March 2011), which is almost trivial. It goes as follows (and this is a chance for me to see if the embedded LaTeX script works...):

Let $P(z)$ be a polynomial of degree $n$. Since $|P(z)|$ is a nonnegative continuous function, tending to $\infty$ as $|z|$ tends to $\infty$, it has a minimum at some point $z_0$:

$|P(z)| \ge |P(z_0)|$, for all $z$.

By division of $P(z)-P(z_0)$ by $z-z_0$, write

$P(z) = P(z_0) + (z-z_0)^k Q(z-z_0),$

where $Q(0) \not = 0$. Since $P(z)$ is nonconstant, the integer $k$ is $\ge 1$.
Therefore

$|P(z_0) + (z-z_0)^k Q(z-z_0)|^2 \ge |P(z_0)|^2$, for all $z$,

and, expanding the square,

$|z-z_0|^{2k} |Q(z-z_0)|^2 + 2 \Re \{ (z-z_0)^k Q(z-z_0) \overline{P(z_0)}\} \ge 0$, for all $z$.

Let $z=z_0 + r e^{i \theta}$, divide by $r^k$, and let $r$ tend to $0$. We obtain

$\Re \{ e^{i k \theta}  Q(0) \overline{P(z_0)}\} \ge 0$,  for all real $\theta$.

It is an easy exercise in algebra that, if $\alpha$ is a complex number such that $\Re \{ e^{i k \theta} \alpha\} \ge 0$ for all $\theta$, then $\alpha=0$. Hence $Q(0) \overline{P(z_0)}=0$. Since $Q(0) \neq 0$, we obtain $P(z_0)=0$.

The fear of OMEGA

A few weeks ago I finished teaching (yet another time) a sort-of upper division undergraduate probability course. What I want to talk about is the beauty and fear of Ω.

As everybody knows, many undergraduate texts in probability start (pompously so) by putting the subject in its proper basis: A probability space is a triplet (Ω, F, P), where Ω is a set, F is a sigma-algebra of subsets of Ω and P is a countably additive function from F to the nonnegative real numbers such that P(Ω)=1.

And then they go on by giving the reader (only) some trite (silly) examples of probability spaces (such as the set {1,2,3,4,5,6}). After going throuh this rite, the quickly forget Ω.

Poor Ω, you seem to be condemned to death right away, from the start. We talk about you, we make you appear stupid, and then we tell the students: We shall not use this from now on.

What makes things worse is that when we speak of random variables, we immediately tell our students that we shall never write X(ω), but, simply, X. There are, of course, very good reasons for doing so, and, indeed, many times, we need not think of random variables as functions, but, simply, be able to handle probabilities associated with them.

In doing so, we immediately destroy the power of Ω, and tell the student that it's not really there. We condemn it to death. We make students fear of them. Some students graduate, they go to get a Master's, maybe a PhD later, and they reach the professorial levels, all the way having the fear of Ω. So much so, that they often miss a huge part of Probability because they are unwilling to delve into Ω and see that it is there and exists!

I am starting a campaign: Re-introduce Ω and keep it up to the surface, by giving, right from the beginning, meaningful examples where the construction (rather than the axiomatization) of Ω is used.

It took people long time to talk about Probability correctly and now what? Should we pretend we don't know what it is? And keep going on teaching the subject as if it were not understood?

No, I am NOT claiming we should teach it a la Bourbaki. No. I am just saying that, while we do speak of Probability in terms of dice, coins, coincidences, noise, etc., let us not forget that it lives on some Ω which can be used, whenever convenient.

P is not equal to NP ?

A few days ago, Vinay Deolalikar of HP Research Labs, Palo Alto made public a paper claiming that P ≠ NP. The proof in this 100-page document remains to be checked and scrutinized.

If correct, it will be a staggering achievement.

It is quite interesting that the approach of the paper is based on Probability. If correct, it will be a triumph for the author, a triumph for humanity, and a triumph for Probability. We strongly feel that Probability plays a very important role in mainstream Mathematics and, if correct, this result will be yet another affirmation of this feeling.

Let us not forget that the P vs NP Problem is one of the Clay Mathematics Institute Millennium problems.

Harmonic series (further test in LaTeX)

I learned yesterday, through Evolutionblog, that I can write LaTeX as long as I put a little script at the bottom of the posting, which can be found here. This is my attempt to make it work.

Well, since the actual posting on Evolution blog was on harmonic series, let me write Pietro Mengoli's proof of its divergence. Recall that the harmonic series is
\[
S = 1 + \frac{1}{2} + \frac{1}{3} + \cdots.
\]
Let us prove that $S=\infty$. Mengoli did the following. He grouped all terms, except the first one, in triples:
\[
S = 1 + \left(\frac{1}{2} + \frac{1}{3} + \frac{1}{4} \right)
+ \left(\frac{1}{5} + \frac{1}{6} + \frac{1}{7} \right)
+ \left(\frac{1}{8} + \frac{1}{9} + \frac{1}{10} \right) + \cdots
\]
Then he observed that each triple is larger than three times the middle term:
\[
\frac{1}{n-1} + \frac{1}{n} + \frac{1}{n+1} > \frac{3}{n}.
\]
And so he wrote
\[
S > 1 + \frac{3}{3} + \frac{3}{6} + \frac{3}{9} + \cdots = 1 + 3S.
\]
Since no finite positive number can be larger than 3 times itself plus 1, he concluded that $S=\infty$.

To see that the inequality above is true write it as
\[
\frac{1}{n-1} + \frac{1}{n+1} > \frac{2}{n},
\]
which is equivalent to
\[
\frac{2n}{n^2-1} > \frac{2}{n}
\]
which is obviously true.

Another way to see the inequality (and more) is to observe that if $X$ is a positive random variable, which is not a constant, then $E(1/X) > 1/E(X)$. To see this, let $Y$ have the same distribution as $X$ but be independent of it. Since $X^2+Y^2 > 2 XY$ we have $2 < \frac{X}{Y} + \frac{Y}{X}$, and, by taking expectations, $2 < E(X) E(1/Y) + E(Y) E(1/X) = 2 E(X) E(1/X)$, as claimed. Then apply this to a random variable $X$ which takes values $n-1$ or $n$ or $n+1$, each with probability $1/3$. This gives Mengoli's inequality. Mengoli also showed that the alternating harmonic series converges to the natural logarithm of 2:
\[
1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - \cdots = \log 2.
\]
Mengoli was born in 1626 in Bologna and died in 1686 in the same town. He also computed the sums
\[
 \sum_{n=1}^\infty \frac{1}{n(n+k)},
\]
for $k=1,2,3,\ldots$ and showed that the result is always a rational number. He naturally wondered what the sum equals to when $k=0$. This was the famous Basel problem, which he posed in 1644. It was shown by Leonhard Euler in 1735 that the sum, for $k=0$, equals $\pi^2/6$. It is not surprising that Mengoli could not find this.

I'm still not happy with this way of writing LaTeX. I can't figure out how to number equations. If only html and LaTeX were fully compatible...

Combinatorial species and a masterpiece in the philosophy and practice of mathematics research

I recently discovered the book Combinatorial Species and Tree-like Structures by Bergeron, Labelle and Leroux, a systematic treatment of combinatorial species, a rigorous formalization of the concept of a discrete structure.

What I would like to discuss here is the extremely interesting, for many reasons, foreword written by Gian-Carlo Rota. He talks about the dynamics of progress in mathematics, pointing out of the ways that the disciplines moves forward.

The first way, Rota writes, occurs when a long-standing problem is solved; e.g., Bieberbach's conjecture or Fermat's last theorem. These are holy grails in mathematics, problems which puzzle generations of mathematicians, leading to surprising developments in the field, until, one day, someone finally gets credit for the solution. While the person who finally obtains the solution rightly deserves the credit, Rota points out that the `genius' does not, simply, belong to one individual but it is a collective, cumulative intelligence belonging to generations of hard-working people.

The second way is also very interesting. There are ideas circulating in mathematics for years and years, collective intuition, one might say, things that people work on, use, but no one dares to put down rigorously for fear (perhaps) of formalizing a triviality, or, simply because nobody knows how to formalize the intuition, or because nobody wants to do that. The second way that mathematics advances is when a commonplace idea finally finds a proper, solid, rigorous home. Rota tells us that mathematicians are reluctant to publicize this second way that the field advances. But when it happens, properly so, that is, it opens a new window into a new way of thinking.

Rota gives a few examples belonging to the second way. The first is the formalization of group theory. The second is category theory. And, of course, Rota points out that the topic of the Combinatorial Species book is, precisely, an advancement of the second kind: someone (André Joyal) found a correct way of associating a combinatorial structure to a generating function and formalized the notion of combinatorial species. Rota points out that species relate to generating functions in much the same way that random variables relate to distribution functions.

My favorite example of the second kind of advancement is Stokes' theorem. Stokes' theorem is a generalization of the fundamental theorem of calculus to higher dimensions and, indeed, in a geometric setup. It states that the integral of a differential form over the boundary of a smooth oriented manifold equals to the integral of the derivative of the form over the manifold. The proof of the theorem is a `triviality'. It is a triviality that takes lots and lots of pages of setting up the scene properly: multilinear algebra, differential forms, manifolds. Once the scene is established, and once dozens of `trivial' lemmas are proven, Stokes' theorem comes out easily.

When progress of the second kind occurs in mathematics, Rota points out, it is met with distrust until many papers are written, using the theory and showing to the old fogies that things are done in a much nicer way using the newly established setup. After this happens, the old fogies will take notice. (Some will pretend they "knew that all along''.)

At first, the old fogies will pretend the book [Bergeron et al.] does not exist. This pretense will last until sufficiently many younger combinatorialists publish papers in which interesting problems are solved using the theory of species. Eventually, a major problem will be solved in the language of species, and from that time on everyone will have to take notice.

He makes an analogy:

Those probabilists of the thirties who held on to distributions, while rejecting random variables as “superfluous,” were eventually wiped out, and their results are not even acknowledged today.

People, including mathematicians, are very protective of their way of doing things. I have met mathematicians who are completely reluctant in accepting a new way of seeing things, a different point of view. Once, when I was a fresh MSc student at Berkeley, Eugene Wong told me that there are two ways of thinking: one is geometric, the other is analytical; but the best progress is made by people who can use both.

Now, I daresay add something more to Rota's prediction. You see,  once the distrust phase is gone and everybody is happily using the ``new math'', it is the old, pedestrian, way of doing things that is forgotten: everybody (even the enemies of the new field) has converted. But there still remain problems which are best attacked by the good-old intuitionistic way, the one used before the formalization occurred. At this point, the ones who are going to have an advantage are those who can effortlessly combine both points of view.

Here is then the exact article by Rota. It is taken from Bergeron's webpage:





Forward [to Combinatorial Species and Tree-like Structures by Bergeron, Labelle and Leroux]
by Gian-Carlo Rota

Advances in mathematics occur in one of two ways.

The first occurs by the solution of some outstanding problem, such as the Bieberbach conjecture or Fermat’s conjecture. Such solutions are justly acclaimed by the mathematical community. The solution of every famous mathematical problem is the result of joint effort of a great many mathematicians. It always comes as an unexpected application of theories that were previously developed without a specific purpose, theories whose effectiveness was at first thought to be highly questionable.

Mathematicians realized long ago that it is hopeless to get the lay public to understand the miracle of unexpected effectiveness of theory. The public, misled by two hundred years of Romantic fantasies, clamors for some “genius” whose brain power cracks open the secrets of nature. It is therefore a common public relations gimmick to give the entire credit for the solution of famous problems to the one mathematician who is responsible for the last step.

It would probably be counterproductive to let it be known that behind every “genius” there lurks a beehive of research mathematicians who gradually built up to the “final” step in seemingly pointless research papers. And it would be fatal to let it be known that the showcase problems of mathematics are of little or no interest for the progress of mathematics. We all know that they are dead ends, curiosities, good only as confirmation of the effectiveness of theory. What mathematicians privately celebrate when one of their showcase problems is solved is Polya's adage “no problem is ever solved directly.”

There is a second way by which mathematics advances, one that mathematicians are also reluctant to publicize. It happens whenever some commonsense notion that had heretofore been taken for granted is discovered to be wanting, to need clarification or definition. Such foundational advances produce substantial dividends, but not right away. The usual accusation that is leveled against mathematicians who dare propose overhauls of the obvious is that of being “too abstract”, As if one piece of mathematics could be “more abstract” than another, except in the eyes of the beholder (it is time to raise a cry of alarm against the misuse of the word “abstract,” which has become as meaningless as the word “Platonism.”)

An amusing case history of an advance of the second kind is uniform convergence, which first made headway in the latter quarter of the nineteenth century. The late Herbert Busemann told me that while he was a student, his analysis teachers admitted their inability to visualize uniform convergence, and viewed it as the outermost limit of abstraction. It took a few more generations to get uniform convergence taught in undergraduate classes.

The hostility against groups, when groups were first “abstracted” from the earlier “group of permutations” is another case in point. Hadamard admitted to being unable to visualize groups except as groups of permutations. In the thirties, when groups made their first inroad into physics via quantum mechanics, a staunch sect of reactionary physicists, repeatedly cried “Victory!” after convincing themselves of having finally rid physics of the “Gruppenpest.” Later, they tried to have this episode erased from the history of physics.

In our time, we have witnessed at least two displays of hostility against new mathematical ideas. The first was directed against lattice theory, and its virulence all but succeeded in wiping lattice theory off the mathematical map. The second. still going on, is directed against the theory of categories. Grothendieck did much to show the simplifying power of categories in mathematics. Categories have broadened our view all the way to the solution of the Weil conjectures. Today, after the advent of braided categories and quantum groups, categories are beginning to look downright concrete, and the last remaining anticategorical reactionaries are beginning to look downright pathetic.

There is a common pattern to advances in mathematics of the second kind. They inevitably begin when someone points out that items that were formerly thought to be “the same” are not really “the same,” while the opposition claims that “it does not matter,” or “these are piddling distinctions.” Take the notion of species that is the subject of this book. The distinction between “labeled graphs” and “unlabeled graphs” has long been familiar. Everyone agrees on the definition of an unlabeled graph, but until a while ago the notion of labeled graph was taken as obvious and not in need of clarification. If you objected that a graph whose vertices are labeled by cyclic permutations – nowadays called a “fat graph” – is not the same thing as a graph whose vertices are labeled by integers, you were given a strange look and you would not be invited to the next combinatorics meeting.

The correct definition of a labeled graph turned out to be more sophisticated than the definition of an unlabeled graph. A labeled graph – or any “labeled” combinatorial construct – is a functor from the groupoid of finite sets and bijections to itself. This definition of a labeled object is not “abstract”: on the contrary, it expresses in precise terms the commonsense idea of “being able to label the vertices of a graph either by integers or by colors, it does not matter,” and it is the only way of making this commonsense idea precise. The notion of groupoid, which is one of the key ideas of contemporary mathematics, makes it possible to withhold the assignement of a specific set of labels to the vertices of a graph without making the graph unlabeled.

Joyal’s definition of “labeled object” as a species discloses a vast horizon of new combinatorial constructions, which cannot be seen if one holds on to the reactionary view that “labeled objects” need no definition. The simplest, and the most remarkable, application of the definition of species is the rigorous combinatorial rendering of functional composition, which was formerly dealt with by handwaving – always a bad sign. But it is just the beginning.

Species are related to generating functions in much the same way as random variables are related to probability distributions. Those probabilists of the thirties who held on to distributions, while rejecting random variables as “superfluous,” were eventually wiped out, and their results are not even acknowledged today.

I dare make a prediction on the future acceptance of this book. At first, the old fogies will pretend the book does not exist. This pretense will last until sufficiently many younger combinatorialists publish papers in which interesting problems are solved using the theory of species. Eventually, a major problem will be solved in the language of species, and from that time on everyone will have to take notice. The rewriting, copying and imitating will start, and mathematicians who capitulate to the new theory will begin to tell us what species really are. Considering the speed at which mathematics progresses in our day, that time is more likely to come sooner than later.

The present book is the first thorough treatment in English of the theory of species. It is lucidly and clearly written, and it should go a long way to making this fundamental chapter of combinatorial mathematics available to the entire spectrum of mathematicians, computer scientists and cultivated scientists generally.

What is mathematics (education) for?

Underwood Dudley, in a critical article in the latest Notices of the AMS, states it accurately:

What mathematics education is for is not for
jobs. It is to teach the race to reason. It does not,
heaven knows, always succeed, but it is the best
method that we have. It is not the only road to
the goal, but there is none better. Furthermore,
it is worth teaching. Were I given to hyperbole I
would say that mathematics is the most glorious
creation of the human intellect, but I am not given
to hyperbole so I will not say that. However, when I
am before a bar of judgment, heavenly or otherwise,
and asked to justify my life, I will draw myself up
proudly and say, “I was one of the stewards of
mathematics, and it came to no harm in my care.”
I will not say, “I helped people get jobs.”

Ancient and early modern mathematics online

The Internet resources are getting better and better. What a luxury to be able to browse through Euler's Opera Omnia, Diophantus' Arithmetica, Einstein's Grundlage der allgemeinen Relativitätstheorie, Fermat's Oeuvres, or Euclid's Elements, among many many others. Here are some links:

• Wilbour Hall
• Cornell University Historical Math Monographs
• Internet Archive
• Open Library
• Rare Book Room
• Libraries Without Walls
• Clay Mathematics Institute
• Gallica
• Digital Library of India
• The University of Michigan Historical Mathematics Collections
• The Penn State Online Books Page
• The American Mathematical Society Books Online

There is still a lot of non-uniformity in how the documents are presented, searched or read. But I believe that, with time, we will have the whole lot there for everyone to read.

A totally nontrivial prisoners problem

(I promised the guys in a Nadder! to post this, so here I go! Keeping my promise!)

Some time ago, Panos Papasoglu, a friend of mine, over dinner at the (highly recommended) Khukuri Nepalese restaurant in Edinburgh, told me a simple probability problem which, in his words, was the most interesting mathematical puzzle he's ever heard:

There are 100 prisoners who are sentenced to death. However, the prison's head, being merciful, offers them a possible way out: He puts 100 identical boxes, perfectly arranged in a row, in the death chamber and places the prisoner's names in them, one name per box. The prisoners wait in a room outside the death chamber. Each prisoner is asked to proceed to the death chamber and open at most 50 boxes. If he finds his name in one of them he is transferred to the mercy room where he waits. If all prisoners succeed in finding their names then they are all spared from death and are released. On the event that one of them fails to find his name in one of the 50 boxes of his choice, the process is stopped and all prisoners are immediately executed. The prisoners can talk to one another whilst in the waiting room, but, once a prisoner gets transferred to the death chamber or the mercy room, he cannot tell the others anything at all.

The question is: Can the prisoners devise a strategy to increase their chance of survival?

To see why the question makes sense, let's see what the chance is in the absence of any strategy: The chance that a prisoner will find his name is 50/100=1/2. So, if the prisoners act independently from one another, the chance that they all find their names is 1/2¹⁰⁰ = 0.000000000000000000000000000000789. (That is, if the experiment is repeated in one thousand billion billion billion prisons then in roughly one of them the prisoners will survive.) So any strategy at all is welcome.

But is there any? What can the prisoners do? They are completely ignorant about the boxes' contents and each prisoner cannot talk to the others.

After hearing the problem, I though the same as everybody else. No way. I then went home and thought harder. I realised that, indeed, there is something that the prisoners can do. In a sense, there is one source of randomness (the random placement of names in boxes) and another one (the ordering of prisoners). If, somehow, we can couple the two (the worst we can do is keep them independent!), then, certainly, we can increase the probability of success. I thought of some schemes but none of them gave me the fantastic increase as the one presented next.


THINK IF YOU WISH ...

AND WHEN YOU ARE READY TO GIVE UP...
CLICK HERE

Away for 6 months

As of 2 weeks ago, I'm spending my time here:

Blogging is not my top priority, so I'll do it when convenient. The problem is that there are so many issues I'd like to talk about, but so little time...