Thursday, September 25, 2008

My Favorite Living Mathematician

Ionica Smeets, of the Dutch website Wiskundemeisjes (Math girls), recently asked me to name my favorite living mathematician. Her version of my answer, and some additional text, can be found (in Dutch) here.

Smeets also kindly allowed me to post my response here.

1. Who is your favorite still living mathematician?

I have many favorites, and it's hard to choose: Alf van der Poorten, Carl Pomerance, Michel Mendès France, Donald Knuth, Adi Shamir, Manuel Blum, just to name a few. But if you force me to choose, I think I would have to say that my favorite is the Dutch mathematician Hendrik W. Lenstra, Jr.

2. Why do you admire him/her?

I admire the beauty of his results and his talent for exposition. To list just two of his famous results:

- the Lenstra-Lenstra-Lovász algorithm for lattice basis reduction, which led to a fast algorithm for factoring polynomials with integer coefficients, and has also given us new ways to attack cryptosystems

- the Lenstra elliptic curve factoring algorithm, which allows us to efficiently find small factors of very large numbers

3. What is special about his/her work?

First, Hendrik Lenstra has a really deep understanding of algebra, so intimate that he can see almost instantly how to solve problems that would take others hours or days.

Second, his exposition is always precise. Unlike some other top-flight mathematicians, who are often a little too casual in their proofs, Hendrik doesn't feel it is beneath his dignity to provide details. When you read one of his papers, you get the feeling that every sentence has been chosen with economy and clarity in mind.

Third, Lenstra has a wide variety of interests, and doesn't hesitate to think seriously about things that others might dismiss as 'recreational'. I point in particular to his work on the mathematics of the Dutch artist M. C. Escher and his delightful paper on profinite Fibonacci numbers.

4. Have you ever worked together?

Yes, we wrote one paper together, "Continued fractions and linear recurrences", which appeared in the journal Mathematics of Computation in 1993. To explain what we did, I have to remind your readers about the two subjects of the title.

Every real number has an essentially unique expansion as a continued fraction, that is, an expression of the form x = a+1/(b+1/(c+ ....)), where all the terms, except possibly the first, are positive integers. For example, π = 3+1/(7+1/(15+ 1/(1 + ...))). When you truncate a continued fraction after n terms, you get better and better rational approximations to the original number. For example, one term of the continued fraction for π gives 3, two terms gives 22/7, three terms gives 333/106, four terms gives 355/113, etc. These fractions are called the convergents and are usually written as pn / qn .

Another thing your readers probably know about is linear recurrences. A simple example of a linear recurrence is the recurrence that gives the Fibonacci numbers: each term of the Fibonacci sequence is the sum of the two previous. When we generalize this to "each term is a linear combination of a fixed number of previous terms", we get the sequences defined by linear recurrences with constant coefficients.

In our paper we combined these two ideas, and asked, "When are the sequences pn and qn linear recurrences?" The answer is not unexpected: this situation can occur if and only if the original number is the root of a quadratic equation, such as the square root of 2, or the golden ratio. However, the proof was unexpectedly hard, and we had to rely on a very deep theorem, the Hadamard quotient theorem of Alf van der Poorten. Later, Andrew Granville found a simpler argument that avoided the need for this difficult theorem.

5. What kind of person is he/she?

Hendrik Lenstra is very much a picture of the traditional European intellectual: always impeccably dressed in a suit and tie, knowledgeable in many fields, and not afraid to show it, sometimes at the expense of those who know less. (I remember once him laughing at me because I did not know whether the root of a word was Latin or Greek.) But he is also extremely kind. Once, when I was hospitalized in the Netherlands following a talk in Leiden, he came to visit me each day in the hospital, bringing me excellent things to read, including The Assault by Dutch author Harry Mulisch.

Hendrik exhibits a playful sense of humor and appreciates a good pun. It was he who once told me about the longest "square" in English: hotshots, which can be written as (hots)2 . (The longest squares I know in Dutch are tenten and kerker .) I also remember him quipping that "Shakespeare's plays weren't written by Shakespeare, but by another man with the same name." (It gets more profound the more you think about it!)

Hendrik is a collector of unusual and antiquarian books. He has a fondness for the Greek poet Homer. Knowing my interest in the crank mathematical literature, he once gave me a copy of the crackpot work The Life-Romance of an Algebraist by George Winslow Pierce, a book I still treasure in my personal collection.


6. Is there a nice story you know about him/her?

One of my nicest memories of time spent with Hendrik was our trip to watch the annular solar eclipse visible from southern Ontario on May 10, 1994. An annular eclipse occurs when the Moon comes between the Sun and the Earth, but is farther away than normal, so that all but a tiny outer ring of the Sun is covered. The sky took on a very unusual appearance, and you could see images of the sun in the diffraction patterns made by the leaves on the trees.

Hendrik wrote a paper called "Mathematics and misunderstanding" which I have not been able to read, since it has appeared only in Dutch. But a reviewer of the paper summed up the argument as follows: "It is the author's contention that the true motivation for doing mathematical research is insight into one's own lack of understanding. The hallmark of the true researcher is his or her ability to recognize, in a seemingly wholly satisfactory theory, points which on closer inspection appear to be not fully understood and hence need further clarification."

Hendrik does not like saying in a paper that something "must be true". He once wrote to me as follows:

"I am not as dogmatic about this as X, who used to ask me when I was a student: if something MUST be true, then IS it true? I think the answer is yes, but X apparently had a supernatural fear that if you FORCE something it may become recalcitrant and misbehave."

For some other quotes of Hendrik Lenstra, see here.

Wednesday, September 17, 2008

I Won't Be Attending Graduation at the University of Alberta Any Time Soon

...and here's why.

A publicly-funded university shouldn't be instructing its students to do something "for the glory of God".

You can write the President of the University of Alberta, Indira V. Samarasekera, to express your displeasure with her university's actions.

City Puzzle


What country's current capital city has a name that can be cyclically shifted some number of letters to get the name of its former capital?

Wednesday, September 03, 2008

My New Book is Out!

My new book, A Second Course in Formal Languages and Automata Theory, is out!



Here's a web page that tells you a little more about the book. And, if you absolutely have to have your own copy, you can buy it at Amazon or Barnes and Noble.