Rosio Pavoris

I mentioned Diffie-Hellman key exchange in the context of asymmetric cryptography. I think it’s time to look at the algorithm a bit more closely.

As usual, Alice and Bob are trying to securely exchange some information, and they’re trying to agree on a key they can use for a symmetric algorithm. Perhaps they don’t know about asymmetric encryption, or they’re trying to exchange too much data for it to be feasible, or they need a stream cipher. Either way, they want to use symmetric encryption.
They have no secure way to exchange keys, because Eve is listening. After all, this is why they want to use the symmetric cipher as well. This is a very common situation on the internets.

Read the rest of this entry »

This is something most people will have seen in high school, but since this is neat and some people haven’t (like me, though obviously I skipped a year) and it’s a discussion that comes up surprisingly often for a concept so simple, I thought I’d talk about it:
The repeating decimal 0.9999999999999… (which can also be written as 0.(9), which I’ll be doing from now on), and why it’s equal to 1.

This usually comes up in the context of limits.
A lot of people have misgivings over it, usually because they don’t really understand infinity. Maybe they instinctively believe there has to be a last 9, so it doesn’t go on forever, or they don’t think an infinitely small number really is equal to 0, or they feel that a single number can only have a single decimal expansion (which, for 1, would be 1.00000…, I guess).

The simplest and least controversial way to show 0.(9) = 1 seems to be:

(Where 0.(3) is another way of writing 0.333…, as you’ll remember.)

If this seems too easy, or you feel like this just moves the problem to whether or not 0.(3) is equal to 1/3, here’s a fancier one:

The bit that may not be immediately obvious is why 0.(9) * 10 = 9.(9), in the second step.
When you multiply a number by 10 in a base 10 system, you move the decimal separator a step to the right. The number of 9s to the right of the separator is infinite, and ∞ - 1 is still ∞, so all that happens is that a nine gets moved to the position before the period.

There are other, less obvious proofs, but they’re not that important.

The consequences aren’t as fascinating as all that (numbers don’t have a unique decimal expansion, the same principle applies in every base, not just base 10 (0.11111111… = 1 in binary, for example)), and practical applications are few (I’ve been told the Cantor set makes use of it, and you could say Zeno’s paradoxes are kind of like it), but by now the question has become a classic internet argument for reasons that are entirely beyond me, so I thought it was worth addressing.
At least I got to use Mimetex again.

I finished these ages ago, but I never got around to reviewing them.
John Allen Paulos is the guy who wrote Innumeracy, as I’m sure you’ll remember.

Once Upon A Number: The Hidden Mathematical Logic of Stories talks about the relation between statistics and storytelling, in a rather loose sense. He discusses the difference between information and meaning, and how logic and language hang together.
It’s hard to describe, obviously, but quite entertaining to read. It’s sprinkled liberally with random math problems, and along the way he also talks about how probability affects religion, which was a nice unexpected bonus (Paulos, like most intelligent, educated people, is an atheist).

The book’s only about two hundred pages, but it’s definitely worth picking up. It’s not as good or important as Innumeracy, but still quite awesome.

A Mathematician Plays the Market (one edition is titled “A Mathematician Plays the Stock Market”, for some reason) is a completely different book. It describes Paulos’ real-life experience with the stock market, and how he lost a significant sum of money in the WorldCom debacle in 2002, due to a combination of poor planning, bad luck, and ignoring his own advice.

He explores the psychological driving forces behind human decision-making when it comes to probability in general, and how they apply to the stock market itself.
Along the way, he explains some things about how the stock market itself works, and why stock market analysts are a boil on the face of society, and economists are mostly idiots.
Well, maybe he didn’t intend to say that, but it’s quite clear from his writing.

Of course, there are the usual mathematical problems as well, but significant parts of them (as well as his plot suggestion for a movie centered around probability) have just been lifted from Once Upon a Number, which was disappointing.
Still, it’s a very interesting book, and it’s one that should be required reading for anyone planning on buying some stock.

Imagining Numbers (Particularly the Square Root of Minus Fifteen), by Barry Mazur, is about the history and mathematics of imaginary numbers, and how mathematical imagination lines up with the more classic, “poetic” imagination.
That’s quite an ambitious undertaking, and I don’t think the book quite lives up to it.

Maybe I just have a really idiosyncratic way of looking at poetry, but most of the poems he brings into play don’t seem very interesting to me at all, and his interpretations of them strike me as too personal to be of much use in this general kind of topic. I could be wrong.

Either way, the bit I bought the book for was, of course, the history of mathematics, and the mathematics itself.
It’s possible there just isn’t a lot of history to imaginary numbers, but I was disappointed to find he only talks about a handful of European mathematicians, and never even mentions similar concepts in other civilisations. Maybe there just aren’t any.
The mathematics themselves are kind of all over the place, too. It’s like Mazur either couldn’t decide between an entry-level book and a “proper” work on mathematics, or he just got tired of explaining things somewhere along the way. He devotes most of a chapter to very tediously explaining the associative and distributive properties of addition and multiplication, and later on just breezes past important concepts with a simple “Here is an exercise for you”.

The various exercises throughout the book are pretty interesting and fun to do, though, but it does mean it’s hard to read it between classes and on the train and whatnot, which I tend to do.
Still, figuring out what equals (and what that means), while not particularly hard, is the type of mathematics I haven’t been able to do in a long time, and it’s a nice change of pace.

So, on the whole, I thought Imagining Numbers was a pretty good book, though I doubt most people would enjoy it much. It’s not as good as some other popular science type mathematics books I’ve read, but still.
I do think it could have been much better if it had been twice as long, though. It’s about 230 pages (not including notes), and it feels kind of superficial and rushed in places.

I like this proof. It’s simple and easy to follow, but it still gives an idea of the power of mathematics. It’s the sort of thing most people probably saw in high school, but most people forget.

What we’re trying to prove is that the square root of 2 (1.4142135623&c.) is an irrational number. A number is irrational if it cannot be expressed as a fraction; that is, the ratio of two whole numbers.
To prove this, we’ll use a reductio ad absurdum—we’ll assume √2 is rational, and we’ll see if this leads us to a contradiction.

If it is rational, the expression

,

where A and B are integers without common divisors, must be true.
Squaring both sides, we get

.

Let’s also multiply both sides by B².

So, we clearly see A² is even, and since the square of an odd number is always odd itself (right?), it follows that A itself is even as well.
So A is the double of a whole number, let’s say C. Let’s substitute C in the equation.

Dividing both sides by 2, we get

So B is an even number too!
We’ve said that A and B didn’t have any common divisors, and if they’re both even they have 2 as a common divisor, so this is clearly a contradiction. It follows that √2 cannot be expressed as the ratio of two whole number.
As such, √2 is irrational. Quantum electrodynamics Quod erat demonstrandum.

By posting this, I’ve probably done someone’s homework for them. Oh well.
Another interesting thing about √2, and really the square root of any positive integer, is that it can be expressed as a periodic continued fraction.

In a sense, they are the simplest of the irrational numbers. This is rather beyond my ability to prove at the moment, though.

Innumeracy, by John Allen Paulos, is about (surprisingly) innumeracy, or mathematical illiteracy. Distinct from the more pathological dyscalcia, it instead implies something closer to functional analphabetism: an inability to grasp simple mathematical concepts, not because one isn’t smart enough or the concepts are too arcane, but simply because whatever mathematical skills the person once might have had have eroded from lack of use.

Most of the book deals with simple probability and how misunderstanding it is both quite harmful (both to individuals and to society as a whole) and extremely widespread.
The problem, as Paulos sees it, is that it’s harder and harder to get away with being (functionally) illiterate, but society almost encourages innumeracy, with a lot of people seeing no shame in declaring they’re “not a math person” (even taking some perverse pride in it, sometimes), in part because so many people see mathematics as dry and boring, and not a good avenue for creativity. Much of the blame falls on shitty education, of course (and it’s getting worse).

It’s a great little book. Despite the very serious subject, Paulos manages to keep a light-hearted tone, and manages to be pretty engaging and funny. He clearly loves mathematics, and manages to convey this love to the reader quite readily.
There are a lot of small math problems interspersed throughout the book, and even though I didn’t have any problems with it (and nobody should, really), I can clearly imagine the average person just not getting it at all. And that, of course, is why everyone should probably read this.

Well I have an Erdős number of infinity! O\__/O

This book took far longer to finish than it should have. This is in large part due to the silly conclusion Penrose tries to reach, which just makes my brain bleed.
The thesis of the book is simply this:

Consciousness is not deterministic, therefore the brain works by the grace of God through quantum.

It starts promisingly enough, with an explanation of Turing machines, computability, and the Turing test. Having explained these concepts, Penrose then tries to argue that the brain is, in fact, not a deterministic Turing machine.
Central to this claim seem to be the Chinese Room experiment and similar thought experiments (which I’ll grant can be difficult to grasp properly), and various minor things like “flashes of insight” (which clearly can’t be explained deterministically!) and whatnot.

Fortunately, he quickly abandons this line of reasoning and starts talking about mathematics and quantum physics for a few hundred pages. I’m not sure why he does this, since neither has any relevance to the subject at hand, but I’m not complaining.
He tries to return to the brain in the final chapters, but he just makes an ass of himself in the process.

Penrose doesn’t understand psychology, physiology, fetal development, evolution or natural selection (at some points coming perilously close to endorsing ID), the (often counter-intuitive) capabilities of actual computers, or cognitive science, but he tries to venture into each of these fields to make his point and fails spectacularly.
His whole point is essentially a giant, infuriatingly dense argument from incredulity and personal pride (the human brain can’t be a deterministic Turing machine, that would make it too common!), and his attempts to involve quantum physics are more reminiscent of Deepak fucking Chopra than of a theoretical physicist of Penrose’s stature.

Now, does this make The Emperor’s New Mind a bad book? Well, yes. Let me rephrase.
Does this mean The Emperor’s New Mind isn’t worth reading? Absolutely not.

Like I said, most of the book is just seemingly irrelevant stuff about mathematics and quantum physics, and it really is quite interesting. It’s worth keeping in mind that Penrose isn’t just some random woo artist, but an accomplished mathematician and actually a rather competent theoretical physicist.
He talks about Turing, fractals (including the Mandelbrot set), Penrose tilings, the history of physics, and plenty of fascinating concepts in theoretical physics ranging from well-known to rather obscure. If you’re willing to gloss over his forays into cognitive science and AI, and maybe skip the last chapter entirely, it’s actually a very good read.

As far as philosophy of the mind goes, though, I’d just leave that to people like Daniel Dennett.

I read too quickly. The Nothing That Is, by Robert Kaplan, is about the history of zero.

Most of the book is, obviously, about the concept of zero in mathematics. It starts with the Sumerians, who came up with the concept, and then goes back and forth between the Greeks and the Indians, to figure out who came up with the symbol for it, and at which point it went from a type of punctuation to an actual number.
He pauses briefly on the Mayans and their psychopathic obsessions regarding zero and its significance in their calendar, and then moves on to Western Europe. It took a ridiculous amount of time for zero to be accepted as an actual number, apparently.

Like Barrow’s Book of Infinity, Kaplan has to talk about religion and theology a lot because of the nature of the subject matter, but unlike Barrow, he manages to remain neutral about it; not the faux neutrality that affords theology the same kind of credibility reality-based philosophies deserve, but actual neutrality, examining where the march of zero was slowed down because of it, and where it was accelerated.

Near the end, he tries to move away from mathematics and into physics, but it doesn’t really work. He tries to crowbar the concept into a number of places where it doesn’t belong, and is quickly reduced to weak philosophising.
There’s a chapter on the psychological implications of zero that’s really just painful to read as well.

Still, those are only a small part of the book, and the vast majority of it is extremely interesting and very well-written. Somewhere along the way he manages to talk about every mathematical concept twelve years of education tried to address, and explain it in a way that made considerably more sense than anything our teachers ever tried to tell us.

If you’re at all interested in history or mathematics (but aren’t an expert mathematician, probably), you’ll enjoy this book. Buy it.

I managed to finish a book before buying new ones!
The Infinite Book, by John D. Barrow, tries to explain the concept of infinity in several fields, and talks about how it has historically been regarded.

The first half of the book deals with infinity in mathematics. It starts with the obvious — Zeno’s paradoxes — and works its way through the history of mathematics all the way up to Georg Cantor and his infinite sets (א is a neat symbol), taking care to introduce complicated concepts in a way anyone could understand.

The second half deals with infinity in physics: infinite density, temperature, &c. in singularities, the infinity of space and time, and the infinity of the multiverse. It touches on things like the Big Bang (obviously), whether or not the universe will continue to expand forever, time travel, &c.
All of it is at least moderately interesting, though it does get repetitive.

The final chapter tries to philosophise a bit about what life would be like if we could live forever, in a stoner stream-of-consciousness kind of way. Barrow may be a good mathematician and theoretical physicist (though if he is, the scope of this book didn’t exactly allow him to show it off), but he’s no great philosopher.

But other than that, it was a pretty decent book. It made for easy reading, but it doesn’t treat readers like idiots, which is a hard balance to find. I certainly learned a few things.

One thing that did bother me, though: he touches on theology rather more than I thought was needed (though some mention is obviously going to be necessary, given the subject matter and the historical context), and he seemed to be extremely careful not to comment on its inanities.
Dunno. Maybe I’m more sensitive to that sort of thing than most. Still, since Barrow apparently won the Templeton Prize in 2006, I don’t think it’s just in my head.

One thing that did amuse me, though: at one point, he points out how advances in science and a deeper understanding of the world around us meant that the concept of God retreated further and further over the course of history, being confined to things science could not yet explain, time and time again.
The punchline? John D. Barrow is a deist.

Anyway. If you’re willing to ignore all that, it really isn’t a bad book. I’ll probably buy more of his books at some point, at least.

You’ll die in your Sleep.

You will die peacefully in your sleep after having a really awesome life.

‘How will you die?’ at QuizGalaxy.com

(Via Pharyngula, obviously.)

In unrelated news, this is an excellent post compiling the various “basic concepts in science” posts. I already linked to Good Math, Bad Math’s contributions a while ago, but I’m guessing the non-mathematics ones will interest most people more.

In more unrelated news, the Magnetic Fields are pretty good. Granted, I’ve only heard two songs so far.

Israeli schools are teaching kids to use ﬩ instead of + (and have been since at least the 1950s), because + looks too much like a Christian cross.
Unicode has this symbol at position U+FB29, as “Hebrew letter alternative plus sign”. It’s not just the Saudis, apparently.

I could understand if they did it to avoid confusion with other uses of + (such as for positiveness, or in some types of logic notations, or for concatenation in some cases), but this is quite possibly the worst excuse to waste a Unicode codepoint they could’ve come up with.

I was reading the xkcd archives a while ago, and I came across this comic. This got me thinking about how to go about constructing this sort of layout; when you have three circles that are tangent to each other, how to you construct a fourth that’s tangent to all three circles?
(This is the type of person I am. I’m sorry. I can’t help it.)

I played with it for a bit, but I got distracted before I figured it out and forgot about it. Then, yesterday, my Sierpinski gasket thing left me browsing Wikipedia looking for random other fractals I could construct. Eventually, I found the Apollonian gasket, and from there, behold, Descartes’ theorem.
I’m not going to prove the theorem, or even say anything the wiki article doesn’t, but I want to talk about it because it’s interesting.

The theorem states the following:

k, in this case, is the curvature of the circle, which is just .
Why plus and minus? Because there are two circles that are tangent to all three circles: one inscribed and one circumscribed.
For example:

Three circles, tangent to each other. As you can see, their radii are 1, 2, and 3, and their curvatures are 1, .5, and 1/3, respectively. (I picked these radii because they make for pretty round numbers in the results, but it works with any numbers.)
According to the theorem:

So the radii for the tangent circles are 6 and (absolute value of the inverse of the curvature). When we construct this, it looks like this:

Ta-dah~
(To construct those circles, you first have to find the center. You can do this by constructing circles with the center of each of the three circles, and a radius equal to the radius of the fourth circle plus or minus the radius of the circle whose center you’re using (actually, the absolute value of the sum of the inverse of the curvature of the fourth circle and the radius of the circle whose center you’re using). These three circles will intersect in the center of the fourth circle.
In this case, the center of the circumscribed circle is on the largest of the initial three circles, because 6 - 3 = 3, obviously.)

I like this. Geometry is intuitive and circles are pretty.

(Told you I’d find a use for that CGI script.)

Took hours to complete. Again, based on this.
If you have Z.u.L./C.a.R., the .zir file is here. It’s hueg. Something like 2,100 points. I’m not sure how many lines it uses. You can move it around, but not resize, for some reason.
Oh well.

These aren’t technically Sierpinski triangles, I guess, since they use lines rather than actual triangles, but they’re an acceptable simplification.
The Sierpinski triangle is actually one of my favorite fractals. More things need to have a surface of 0.

Over at Good Math, Bad Math, MarkCC has written a few posts on the basics of mathematics. I think he’s the only science blogger still bothering with that project, and I’m glad he is.
In particular, I enjoyed the posts on Turing machines and the halting problem, both of which are fundamental concepts in computer science. A lot of people might not consider them “basics” as such, but they’re interesting.

(His other posts on basics are Mean, Median, and Mode, Normal Distributions, Standard Deviation, Margin of Error, Natural Numbers and Integers, Recursion and Induction, Correlation, Logic, aka “It’s illogical to call Mr. Spock logical”, Syntax and Semantics, Sets, Real Numbers, and Multidimensional Numbers. They’re all worth reading.)

Stranger Fruit is a blog on ScienceBlogs I don’t usually read, but this particular post was brought to my attention just now.

Today in 1978, the logician Kurt Gödel died in Princeton, New Jersey. Gödel, of course, is remembered for his incompleteness theorems but also took the ontological proof for the existence of God serious enough to express his own version of it in modal logic.

Which he then follows with the proof itself. You can look at it if you like, but it’s essentially Anselm of Canterbury’s with more maths to confuse the layperson.
The general form of the ontological argument (and a simplification of Anselm’s version), of course, is this:

1. God is, by definition, a being than which nothing greater can be conceived/imagined.
2. Existence in reality is greater than existence in the mind.
3. God must exist in reality, if God did not then God would not be that which nothing greater can be conceived/imagined.

Analogously, it is possible to conceive of a perfect ham sandwich. A ham sandwich which, by definition, is better than any other such sandwich. For such a ham sandwich to exist in reality is greater than for it to simply exist in the mind. Therefore somewhere must exist the perfect ham sandwich.
I’m expecting that sandwich to arrive any moment now.

Anyway, Lynch then goes on to say that because Dawkins refuted the Anselm of Canterbury version but not the Gödel version, clearly The God Delusion is an infantile piece of crap.
John Lynch is apparently an atheist, and he’s bringing this up because he feels the chapter in TGD dealing with the ontological argument is ignorant of sophisticated theology (never mind that all of the various version of it have at its base the same single flaw), and that this weakens the book as a whole.
It’s a textbook example of the Courtier’s Reply, and he reinforces it in the comments.

“I freely admit to not understanding Godel’s argument - I was merely using it to make a broader point about Dawkins’ willingness to caricature the ontological argument.”

“Thanks for playing. Come back when you have actually read something substantial on the ontological argument. And that excludes Dawkins.”

“I’ll stand by my claim that Chapter 3 greatly weakens the overall work and that it does not reflect anything interesting that’s happening in philosophy of religion.”

The ontological argument doesn’t need caricaturing, and Dawkins doesn’t. Essentially saying “other people have written more! I don’t understand it but they can’t all be wrong!” is intellectually void. “Philosophy of religion” is a euphemism for “theology”, and arguably nothing interesting has happened in that area in many, many centuries.

I hope for the sake of ScienceBlogs in general that this is an attempt at satire, but I doubt it. We (and secularism everywhere) have about as much to fear from appeasers as we do from fundamentalists themselves.

Edit: Larry Moran takes apart another one of Lynch’s posts. This is relevant.