Escher, Droste and Lenstra

   23 June 2004, evening time

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.

A piece of scrap paper from my crypto class.

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.



  1. Although it’s been linked to elsewhere, this is a good place to drop this link.

  2. 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.

  3. 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.

  4. Have you read “Gödel, Escher, Bach: An Eternal Golden Braid” by Douglas Hofstadter yet?

  5. No, I haven’t read it. The book has been recommended to me by several people mind you.

  6. Yeah. I know. I was one of those several people. (That’s when you and Daniel recommended Cryptomonicon, which I still haven’t read).

  7. You should also read Metamagical Themas.

Don't be shy, you can comment too!

Some things to keep in mind: You can style comments using Textile. In particular, *text* will get turned into text and _text_ will get turned into text. You can post a link using the command "linktext":link, so something like "google": will get turned in to google. I may erase off-topic comments, or edit poorly formatted comments; I do this very rarely.