Emile Lemoine

Through the MacTutor archive I learn that today’s the birthday of Émile Michel Hyacinthe Lemoine (1840 – 1912), a mathematician I admit I don’t remember hearing of before. His particular mathematical interests were primarily in geometry (though MacTutor notes professionally he became a civil engineer responsible for Paris’s gas supply).

What interests me is that Lemoine looked into the problem of how complicated a proof is, and in just the sort of thing designed to endear him to my heart, he tried to give a concrete measurement of, at least, how involved a geometric construction was. He identified the classic steps in compass-and-straightedge constructions and classified proofs by how many steps these took. MacTutor cites him as showing that the usual solution to the Apollonius problem — construct a circle tangent to three given circles — required over four hundred operations, but that he was able to squeeze that down to 199.

However, well, nobody seems to have been very interested in this classification. That’s probably because the length doesn’t really measure how complicated a proof (or a construction) is: proofs can have a narrative flow, and a proof that involves many steps each of which seems to flow obviously (or which look like the steps in another, already-familiar proof) is going to be easier to read and to understand than one that involves fewer but more obscure steps. This is the sort of thing that challenges attempts to measure how difficult a proof is, even though it’d be interesting to know.

Here’s one of the things that would be served by being able to measure just how long a proof is: a lot of numerical mathematics depends on having sequences of randomly generated numbers, but, showing that you actually have a random sequence of numbers is a deeply hard problem. If you can specify how you get a particular digit … well, they’re not random, then, are they? Unless it’s “use this digit from this randomly generated sequence”. If you could show there’s no way to produce a particular sequence of numbers in any way more efficiently than just reading them off this list of numbers you’d at least have a fair chance at saying this is a truly unpredictable sequence. But, showing that you have found the most efficient algorithm for producing something is … well, it’s difficult to even start measuring that sort of thing, and while Lemoine didn’t produce a very good measure of algorithmic complexity, he did have an idea, and it’s difficult to see how one could get a good measure if one didn’t start with trying not-very-good ones.


Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s