Escher, Droste and Lenstra
23 June 2004, the wee hours
I attended a talk today by Henrik Lenstra on Escher and the Droste Effect. The talk examines the mathematics behind M.C. Escher’s print of a man viewing a painting in a gallery that turns in to the gallery itself. Escher left the middle of this print blank, thought it apparently need not be. The talk was quite interesting, and the art produced from the research is really quite amazing to see.
I was already aware of Lenstra from his work in cryptography. Lenstra seems to have been involved in number theory for quite some time. His name comes up when discussions turn to factoring integers, in particular the Number Field Sieve. The Number Field Sieve is the fastest algorithm to factor integers. It is based on another factoring method called Random Squares.
I think the notation used to talk about running times of algorithms similar to the Number Field Sieve was developed by Lenstra, though I could be mistaken on this. The running time for an algorithm is the number of primitive operations needed to solve an input problem of a given size. The running time for algorithms based on the Random Square method generally have the form e(c + o(1))(ln n)α(ln ln n)1-α, where α and c are constants, and n is the size of the input. This is usually abbreviated to Ln[α,c]. The running time of the Number Field Sieve is Ln[1/3,1.98], which is a sub-exponential algorithm.
Although it’s been linked to elsewhere, this is a good place to drop this link.
by Hass on June 23 2004, 1:28 am #
Cool. I didn’t know Lenstra was into Number Theory. It’s seems like a weird combination though. Escher and NFS. I guess NFS has been around for a little while though.
by Ryan on June 23 2004, 1:33 am #
Yeah. This work on Escher seems a bit out of left field, but I guess even number theory can get a bit tired after a while.
Also, the lego Escher is way cool, it was on Metafilter a while back. Actually, this project was also featured on Metafilter a while ago, much to my surprise.
by ramanan on June 23 2004, 4:57 am #
Have you read “Gödel, Escher, Bach: An Eternal Golden Braid” by Douglas Hofstadter yet?
by Ryan on June 23 2004, 4:45 pm #
No, I haven’t read it. The book has been recommended to me by several people mind you.
by ramanan on June 24 2004, 5:03 am #
Yeah. I know. I was one of those several people. (That’s when you and Daniel recommended Cryptomonicon, which I still haven’t read).
by Ryan on June 24 2004, 4:26 pm #
You should also read Metamagical Themas.
by mk on June 24 2004, 4:28 pm #