Monthly Archives: January 2009

The Continuum Hypothesis Solved: All Infinities are the Same? Nope.

Of all of the work in the history of mathematics, nothing seems to attract so much controversy, or even outright hatred as Cantor’s diagonalization. The idea of comparing the sizes of different infinities – and worse, of actually concluding that there are different infinities, where some infinities are larger than others – drives some people absolutely crazy. As a result, countless people bothered by this have tried to come up with all sorts of arguments about why Cantor was wrong, and there’s only one infinity.

Today’s post is another example of that. This one is sort of special. Unless I’m very much mistaken, the author of this sent me his argument by email last year, and I actually exchanged several messages with him, before he concluded, roughly “We’ll just have to agree to disagree.” (I didn’t keep the email, so I’m not certain, but it’s exactly the same argument, and the authors name is vaguely familiar. If I’m wrong, I apologize.)

Anyway, this author actually went ahead and wrote the argument up as a full technical paper, and submitted it to arXiv, where you can download it in all it’s glory. I’ll be honest, and admit that I’m a little bit impressed by this. The proof is still completely wrong, and the arguments that surround it range from wrong to, well, not even wrong. But at least the author has the Chutzpah to treat his work seriously, and submit it to a place where it can actually be reviewed, instead of ranting about conspiracies.

For those who aren’t familiar with the work of Cantor, you can read my article on it here. A short summary is that Cantor invented set theory, and then used it to study the construction of finite and infinite sets, and their relationships with numbers. One of the very surprising conclusions was that you can compare the size of infinite sets: two sets have the same size if there’s a way to create a one-to-one mapping between their members. An infinite set A is larger than another infinite set B if every possible mapping from members of B to members of A will exclude at least one member of A. Using that idea, Cantor showed that if you try to create a mapping from the integers to the real numbers, for any possible mapping, you can generate a real number that isn’t included in that mapping – and therefore, the set of reals is larger than the set of integers, even though both are infinite.

This really bothers people, including our intrepid author. In his introduction, he gives his motivation:

Cantor’s theory mentioned in fact that there were several dimensions for infinity. This, however, is questionable. Infinity can be thought as an absolute concept and there should not exist several dimensions for the infinite.

Philosophically, the idea of multiple infinities is uncomfortable. Our intuitive notion of infinity is of an absolute, transcendent concept, and the idea of being able to differentiate – or worse, to be able to compare the sizes of different infinities seems wrong.

Of course, what seems wrong isn’t necessarily wrong. It seems wrong that the mass of something can change depending on how fast it’s moving. It seems even more wrong that looked at from different viewpoints, the same object can have different masses. But that doesn’t change the fact that it’s true. Reality – and even worse, abstract mathematics – isn’t constrained by what makes us comfortable.

Back to the paper. In the very next sentence, he goes completely off the rails.

Continue reading

Ropes: Twining Together Strings for Editors

It’s been a while since I’ve written about any data structures. But it just so happens that I’m actually really working on implementing a really interesting and broadly useful data structure now, called a Rope.

A bit of background, to lead in. I’ve got this love-hate relationship with some of the development tools that Rob Pike has built. (Rob is one of the Unix guys from Bell labs, and was one of the principal people involved in both the Plan9 and Inferno operating systems.) Rob has implemented some amazing development tools. The two that fascinate me were called Sam and Acme. The best and worst features of both are a sort of extreme elegant minimalism. There’s no bloat in Rob’s tools, no eye-candy, no redundancy. They’re built to do a job, and do it well – but not to do any more than their intended job. (This can be contrasted against Emacs, which is a text editor that’s grown into a virtual operating system.) The positive side of this is that they’re incredibly effective, and they demonstrate just how simple a programmers text editor should be. I’ve never used another tool that is more effective than Acme or Sam. In all seriousness, I can do more of my work more easily in Sam than I can in Emacs (which is my everyday editor). But on the other hand, that extreme minimalist aesthetic has the effect of strictly eliminating any overlaps: there’s one way to do things, and if you don’t like it, tough. In the case of Acme and Sam, that meant that you used the mouse for damn-near everything. You couldn’t even use the up and down arrows to move the cursor!

This is a non-starter for me. As I’ve mentioned once or twice, I’ve got terrible RSI in my wrists. I can’t use the mouse that much. I like to keep my hands on my keyboard. I don’t mind using the mouse when it’s appropriate, but moving my hand from the keyboard to the mouse every time I want to move the cursor?. No. No damned way. Just writing this much of this post, I would have had to go back and forth between the keyboard and mouse over 50 times. (I was counting, but gave up when I it 50.) A full day of that, and I’d be in serious pain.

I recently got reminded of Acme, because my new project at work involves using a programming language developed by Rob Pike. And Acme would really be incredibly useful for my new project. But I can’t use it. So I decided to bite the bullet, and use my free time to put together an Acme-like tool. (Most of the pieces that you need for a prototype of a tool like that are available as open-source components, so it’s just a matter of assembling them. Still a very non-trivial task, but a possible one.)

Which finally, leads us back to today’s data structure. The fundamental piece of a text editor is the data structure that you use to represent the text that you’re editing. For simplicity, I’m going to use Emacs terminology, and refer to the editable contents of a file as a Buffer.

How do you represent a buffer?

As usual with data structures, you start by asking: What do I need it to do? What performance characteristics are important?

In the case of a text buffer, you can get by with a fairly small set of basic operations:

  • Fast concatenation: concatenating blocks of text needs to be really fast.
  • Fast insert: given a point in a block of text, you need to be able to quickly insert text at that point.
  • Fast delete: given two points in a block of text, you need to be able to quickly remove the text between those points.
  • Reasonably fast traversal: Lots of algorithms, ranging from printing out the text to searching it are based on linear traversals of the contents. This doesn’t have to be incredibly fast – it is an intrinsically linear process, and it’s usually done in the context of something with a non-trivial cost (I/O, regular-expression scanning). But you can’t afford to make it expensive.
  • Size: you need to be able to store effectively unlimited amounts of text, without significant performance degradation in the operations described above.

Continue reading

Lottery Probabilities and Clueless Reporters

A simple, silly, but entertaining example of mathematical illiteracy by way of the Associated Press:

OMAHA, Neb. (AP) — The odds are against something this odd. But a Nebraska Lottery official says there was no mistake: The same three numbers in Nebraska’s Pick 3 lottery were drawn two nights in a row this week.

Lottery spokesman Brian Rockey said one of two lottery computers that randomly generate numbers produced the numbers 1, 9 and 6 — in that order — for Monday night’s Pick 3 drawing. Rockey says the next night, the lottery’s other computer produced the same three numbers in the same sequence.

The odds of such an occurrence? One in a million.

Close… Only off by three orders of magnitude…

Continue reading

Can 20 People Stand on a Wing? Can a Conspiracy Theorist Be Stupid?

I’m sure you’ve all heard about the airplane that ditched in the Hudson last week. (Just 30 blocks from my office!) When it happened, after we found out more about what caused the plane to ditch, I wondered how long it would take before the 911 Truthers came up with a conspiracy theory about it.

Not long. Via SkepticBlog comes news of a conspiracy theorist claiming that the ditching doesn’t make any sense. Brian Dunning at SkepticBlog does a good
job explaining what’s so stupid about this, but there were two things about
it that I thought were particularly interesting from the point of view of a math and computer science geek.

Continue reading

Apples vs Orchards: Comparing Inauguration Costs

People keep sending me links to this, so I’ll make a short post about it.

In the hubbub surrounding the Obama inauguration, there’ve been all sorts of incredulous press pieces discussing the supposed outrageousness of the costs of this inauguration compared to others. I’ve personally heard this reported on the BBC world service, CNN, Fox, and MSNBC. In these
reports, the cost of the Obama inauguration is generally reported as
between 150 and 160 million dollars. When they provide a contrast, they talk about how Bush’s second inauguration cost $40 million.

The problem is, this is a metric error. They’re comparing apples to orchards.

When they cite the Bush inauguration cost as $40 million, they’re talking
about the cost of the inauguration parties – that is, the cost of the festivities themselves. That cost does not include security. It does
not include the cost of paying police to shut down the city streets. It doesn’t include the cost of cleaning up after the crowds. It’s just
the cost of the parties.

The Obama figure of $150-$160 million includes everything – police, security, setup, and cleanup.

A fair comparison? If you exclude the security costs, Bush’s second
inauguration cost $42 million; Obama’s is expected to cost around $45 million. If you include the security costs, Bush’s second inauguration
cost somewhere around $155 million. (The exact figures are still not public
knowledge; Bush and company treated it as a “national security matter” which
did not need to be disclosed.)

Yet another fake controversy brought to you by the supposedly liberal-biased media.

Excuse the brief interruption…

Just a brief note, to let you all know why there’s a lack of new posts.

Once again, I managed to kill my laptop. The machine died suddenly, with no warning. I’m currently waiting for a replacement, and once I get it, I’ll need some time to set everything up to my liking. I also had three posts in progress on the machine; I’m not sure whether they were backed up or not, and won’t be able to find out until I get a new machine.

Things will be back to normal as soon as possible, but don’t expect much for the next couple of days.

Blaming Bush: This time, it wasn't his fault.

And now for a short gripe from the other side of the political spectrum.

Normally, I like Media Matters. I personally think that the whole “left-wing media” thing
is a crock. The media has become so sensitive to the accusation of left-wing bias that they actually shy away from even dreaming of criticizing a conservative, and attack liberals with great fervor as a way of showing that they’re not being unfairly nice to them. In general,
I find Media Matters does a good job of showing how the modern press really works.

But the fact is, they are a biased organization, and you need to be very careful
to look at the details of what they write. Just like right-wing media-watch organizations,
they do look for interpretations of facts that support their bias, even if it requires
significant abuse of those facts to make the interpretation fit.

This morning, they provided an excellent demonstration of that. President Bush gave his final press conference this morning. The people at the conference showed a lot of deference to him, and let him get away with a lot. But one thing that Media Matters focused on
touches on math, and it’s bad.

Continue reading

Social Security vs Ponzi Schemes

Naturally, since this friday was the first time that the SB server has really been down since I start blogging (planned downtime, as it happens, for a major system upgrade), there
was spectacularly bad math in the local news here in NYC friday afternoon.

I’m not sure how long this has been the case, but Mayors of NYC have a radio show. It’s a mixture of them spouting off about whatever they feel like babbling about, and call-in questions. I don’t generally listen, but once in a while, if the mayor says something either particularly interesting or particularly insane, I’ll hear the segment repeated on the local NPR station.

In this friday’s show, he sprung a really shockingly stupid line. The supposed
topic was Bernard Madoff and his pyramid scheme. Bloomberg responded by saying
that “Madoff’s isn’t the biggest ponzi scheme ever. If you really want to see the
worlds biggest ponzi scheme, just look at social security.” He continued along
those lines for a few minutes.

This is, to put it mildly, bullshit. Incredibly, stupid, rampant, bullshit.

Continue reading

Cryptographic Padding in RSA

Ok, away from politics, and back to the good stuff. When I left off talking about
encryption, we were looking at
, as an example of an asymmetric encryption system.

Since it’s been a while, I’ll start off with a quick review of RSA.

Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don’t. In the specific case
of RSA, everything is based on a pair of very large prime numbers. If you know those two
primes, and you know the public key, it’s really easy to compute the private key. But
if you don’t know the two prime numbers, then even given the public key,
it’s incredibly difficult to compute the private key.

To be a bit more specific, in RSA, you get a pair of large prime numbers, P and Q. You
compute from them a totient of their product, which is the number
N=(P-1)×(Q-1). Then you arbitrarily pick a public exponent, E, which is
smaller than N, and which is prime relative to N. You can then compute
the private key exponent, D. If you know what P and Q are, it’s pretty easy to compute

Once you’ve got D and E, your public key is the pair is (N,E), and the private key is the pair is (N,D).

If you’ve got a plaintext message M, then encrypting it with the public key
is done by computing ME mod N. If you’ve got a ciphertext C encrypted
with the public key, then decrypting it is done by computing CD mod N.

Encrypting a plaintext with the public key is exactly the same process
as decrypting a ciphertext produced with the private key. And vice versa.

Continue reading

Circling Around The Speed of Light

One of the many great things about my readers is how you folks keep me up to date with any new crap that springs up, so that I don’t need to spend so much time hunting down the real good stuff. There’s a beautiful piece of crap on youtube that was pointed out to me by one of you guys. It’s really a wonderful bit of circularity.

Circularity is something that I find beautiful in math. What I mean by circularity is that because numbers are closed, you can run around in circles playing games with that closure. Another post that I’ve got in progress is talking about RSA encryption, which is a beautiful example of circularity. You start with a message, encoded as a number, M. Then you take a particular set of three numbers, N, D, and E. If you raise M to the Dth power modulo N, you get a new number. M’. If you raise M’ to the Eth power modulo N, you get the original M. You’re never taking roots – but the two exponentiations cancel each other out modulo N. It’s beautiful, and astonishing, and yet it makes perfect sense.

That’s a complicated example of circularity. A simpler one, also involving modulo arithmetic, is to look at the tempered music scale. Let A=0, Bb=1, B=2, C=3, Db=4, D=5, Eb=6, E=7, F=8, Gb=9, G=10, Ab=11. Now, start at A, and follow through musical fifths – that is, go from A(0) to E(7). Then E(7) to E+7=14 mod 12 = 2 = B. Then B to Gb(9). Then Gb to Db(4). Then Db to Ab. Then Ab to Eb. Then Eb to Bb. Then Db to F. Then F to C. Then C to G. Then G to D. Then D to A. You’ve taken twelve steps of fifths, and wound up where you started. So by following through one of the natural musical elements of harmony, you’ve got a circle that visits each note exactly once. Looked at mathematically, it’s trivial. But it’s still pretty cool.

It’s pretty easy to trick yourself with circularity of you’re not careful. You can find what appear to be amazing numerical coincidences, because you don’t realize that you’ve created a circle.

The target of this posts isn’t an example of that. It’s a really trivial circle.

Continue reading