Jun 082009

Some moderately interesting Maxima examples.

First, this is how we can prove that the covariant derivative of the metric vanishes (but only if the metric is symmetric!)


Next, the equation of motion for a perfect fluid:


Finally, the equation of motion in the spherically symmetric, static case:


These examples are probably not profound enough to include with Maxima, but are useful to remember.

 Posted by at 5:07 pm
Apr 252009

Watching the outrage over the DHS memos that purportedly target all Americans on the political right as potential enemies of the state, I have come to the realization that a great many political conspiracy theories are based on a trivial error in formal logic: namely, that the implication operator is not commutative.

The implication operator, AB (A implies B) is true if A is false (B can be anything) or if both A and B are true. In other words, it is only false if A is true but B is false. However, AB does not imply BA; the former is true when A is false but B is true, but the latter isn’t.

Yet this is what is at the heart of many conspiracy theories. For instance, a DHS report might say, that those on the fringe of the political right are motivated by the Obama government’s more permissive stance on stem cell research. Some draw the conclusion that this report implies that all who are troubled by Obama’s stance on this issue must be right-wing extremists. I could write this symbolically as follows: we have

member(e, s) → prop(e, p)

where member(e, s) means that e is a member of set s, and prop(e, p) means that e has property p. This symbolic equation cannot be reversed: it does not follow that prop(e, p) → member(e, s).

A closely related mistake is the confusion of the universal and existential operators. The existential operator (usually denoted with an inverted E, but I don’t have an inverted E on my keyboard, so I’ll just use a regular E), E(s, p) says that the set s has at least one member to which property p applies. The universal operator (denoted with an inverted A; I’ll just use a plain A), A(s, p) says that all members of set s have property p. Clearly, the two do not mean the same. Yet all too often, people (on both sides of the political aisle, indeed a lot of the politically correct outrage happens because of this) make this error and assume that once it has been asserted that E(s, p), it is implied that A(s, p). (E.g., a logically flawless statement such as “some blacks are criminals” is assumed to imply the racist generalization that all blacks are criminals.)

One might wonder why formal logic is not taught to would be politicians. I fear that in actuality, the situation is far worse: that they do know formal logic, and use it to their best advantage assuming that you don’t.

 Posted by at 12:27 pm
Mar 202009

In the Futurama movie, The Beast with a Billion Backs, one scene features a blackboard with two different proofs of the Goldbach conjecture. The Goldback conjecture is one of the oldest unsolved problems in mathematics. One of those problems, like Fermat’s last theorem or the 4-color problem of maps that is deceivingly easy to state and fiendishly hard to prove: that every even number greater than 4 can be expressed as the sum of two primes.

Just how intriguing this problem is, it’s well illustrated by the following plot that shows the number of ways an even number between 4 and 1 million can be split into a sum of two primes:

Golbach to 1000000

Golbach partitioning to 1000000

This plot, taken from Wikipedia, clearly shows that the results cluster along curves (asymptotes? attractors?) that follow some kind of a power law with an exponent between ~0.68 and ~0.77, and there may also be some fractal splitting involved, too. This plot is known as Goldbach’s comet. All I have to do is look at it to understand why many people find number theory endlessly fascinating.

 Posted by at 5:54 pm
Feb 162009

I received some sad news yesterday from Hungary: my high school math teacher, Gusztáv Reményi, died last week, at the age of 88. He was a very kind teacher. Our class was a specialized mathematics class, and we were supposed to be the best in the country. In this class, being good at math didn’t just mean that, say, you got sent to national math competitions; you were expected to win them. Perhaps this made Mr. Reményi’s job easier, but I suspect that he would have done well with less talented pupils, too, if not because of his teaching style then due to his personality. If you met him and remembered nothing else, you’d have remembered his smile. I last met him a few years ago, at our high school reunion. He was old, he was frail, but the huge smile was still there, just as I remembered.

 Posted by at 3:54 pm
Jan 012009

I am starting the new year by reading about a substantial piece of cryptographic work, a successful attack against a widely used cryptographic method for validating secure Web sites, MD5.

That nothing lasts forever is not surprising, and it was always known that cryptographic methods, however strong, may one day be broken as more powerful computers and more clever algorithms become available. What I find astonishing, however, is that even though this particular vulnerability of MD5 has been known theoretically for years, several of the best known Certification Authorities continued to use this broken method to certify secure Web sites. This is hugely irresponsible, and should a real attack actually occur, I’d not be surprised if many lawsuits followed.

The theory behind this attack is complicated, and the hardware is substantial (200 Playstations used as a supercomputing cluster were required to carry out the attack.) One basic reason why the attack was possible in the first place has to do with the “birthday paradox”: it is much easier to construct a fake certificate that has the same signature as a valid certificate than it is to recover the original cryptographic key used to sign the valid certificate.

This has to do with the probability that two persons at a party have the same birthday. For a greater than 50% chance that another person at a party has your birthday, the party has to be huge, with more than 252 guests. However, the probability that at a given party, you find at least two people who share the same birthday (but not necessarily yours) is greater than 50% even for a fairly small party of just over 22 guests.

This apparent paradox is not hard to understand. When you meet another person at a party, the probability that he has the same birthday as you is 1/365 (I’m ignoring leap years here.) The probability that he does NOT have the same birthday as you, then, is 364/365. The probability that two individuals both do NOT have the same birthday as you is the square of this number, (364/365)2. The probability that none of three separate invididuals has the same birthday as you is the cube, (364/365)3. And so on, but you need to go all the way to 253 before this results drops below 0.5, i.e., that the probability that at least one of the people you meet DOES have the same birthday as you becomes greater than 50%.

However, when we relax the condition and no longer require a guest to have the same birthday as you, only that there’s a pair of guests who happen to share their birthday, we need to think in terms of pairs. When there are n guests, they can form n(n – 1)/2 pairs. For 23 guests, the number of pairs they can form is already 253, and therefore, the probability that at least one of these pairs has a shared birthday becomes greater than 50%.

On the cryptographic front, what this basically means is that even as breaking a cryptographic key requires 2k operations, a much smaller number, only 2k/2 is needed to create a rogue cryptographic signature, for instance. It was this fact, combined with other weaknesses of the MD5 algorithm, that allowed these researchers to create a rogue Certification Authority certificate, with which they can go on and create rogue secure certificates for any Web site.

 Posted by at 2:30 pm
Dec 222008

This is not what I usually expect to see when I glance at CNN:

CNN and integrals

CNN and integrals

It almost makes me believe that we live in a mathematically literate society. If only!

The topic, by the way, was a British Medical Journal paper on brain damage caused by a dancing style called headbanging. I must say, even though I grew up during the disco era, I never much liked dancing. But, for what it’s worth, I not only know how to do integrals, I actually enjoy doing them…

 Posted by at 1:25 pm