Here is my nomination for the best newspaper headline of the year:
Early birds enjoy undead, ducks.
Sunday, October 05, 2008
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.
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.
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
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.

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.
Sunday, August 24, 2008
Failed Olympic Medal Predictions
Leading up to the Olympics, there was a lot of hype about the work of Colorado College economist Daniel K. N. Johnson and his predictions about the Olympic medal count. For example, he was interviewed on NPR and featured in the Wall Street Journal. Prof. Johnson's method was based on five factors only: GDP per capita, total population, political structure, climate, and home-nation bias, and was touted as "remarkably accurate".
Now the results are in. Here are Johnson's predictions of the top ten medal winners, compared to the actual total these countries won:
Rating a prediction p as good if .75r ≤ p ≤ 1.25r, where r is the actual result, I'd say Johnson made 3 good predictions out of his top 10: China, USA, and Italy. And he made some really bad ones, including Hungary, Great Britain, and Australia. Altogether, Johnson's predictions don't deserve a place at the podium.
Now the results are in. Here are Johnson's predictions of the top ten medal winners, compared to the actual total these countries won:
| Country | Johnson's prediction | Actual result |
| USA | 103 | 110 |
| Russia | 95 | 72 |
| China | 89 | 100 |
| Germany | 66 | 41 |
| Japan | 37 | 25 |
| Hungary | 31 | 10 |
| Italy | 29 | 28 |
| Great Britain | 28 | 47 |
| France | 27 | 40 |
| Australia | 26 | 46 |
Rating a prediction p as good if .75r ≤ p ≤ 1.25r, where r is the actual result, I'd say Johnson made 3 good predictions out of his top 10: China, USA, and Italy. And he made some really bad ones, including Hungary, Great Britain, and Australia. Altogether, Johnson's predictions don't deserve a place at the podium.
Monday, August 18, 2008
Extraordinary Sports Events
Watching the Olympics this week reminds me of some of my favorite extraordinary events in sports:
1. Dorando Pietri's Marathon: Pietri, an unknown entrant in the 1908 London marathon, led the field as the race entered the final segment in the stadium, but was so exhausted and confused that he started going the wrong way around the track. Within sight of the finish line, he collapsed multiple times and had to be helped over the line by race officials. Although apparently the winner, he was later disqualified because of the help he received.
2. Emil Zátopek's Marathon: Having already won the 5K and 10K races at the 1952 Olympics in Helsinki, Zátopek decided at the last minute to enter the marathon, despite having never run the race before. He won.
3. Tom Dempsey's 63-yard field goal: Dempsey, born without a right foot and right hand, kicked a 63-yard field goal, the longest in NFL history, to give the New Orleans Saints a 19-17 win over the Detroit Lions. I think this is one of the most exciting moments in professional football.
4. Berkeley-Stanford football game, 1982: I was listening to this game on the radio, and couldn't believe my ears. With 4 seconds left, and Berkeley trailing 20-19 on a last-minute Stanford field goal, Berkeley returned the kick-off 55 yards to win 25-20. What made the return special was the use of 5 laterals and the fact that the Stanford band, believing the game won, went onto the field and created additional chaos, with the trombone player getting flattened at the conclusion. This event is so special that among Cal alumni it is simply known as "The Play". The next week, Berkeley street vendors were selling a t-shirt with a diagram of the play, ending in a music note representing the trombone.
5. Jordan Snipes' 2005 shot: With 0.6 seconds left in overtime and Guilford College trailing Randolph-Macon 89-88, Jordan Snipes rebounded the ball and launched a full-court shot that swished the hoop at the other hand, giving his team a 91-89 victory. Then a news team asked him to re-enact the shot, and he made it again.
6. Bonnie Richardson, a Texas high school student, won the state's team championship -- all by herself. Richardson, the only student from her school, Rochelle High, to compete, won the high jump and 200 meters, placed second in the long jump and and 100 meters, and finished 3rd in the discus, for a total of 42 team points.
7. Cliff Young's Ultramarathon: Young, a 61-year-old sheep farmer, entered the Sydney-to-Melbourne footrace (a distance of 875 kilometers) in 1983. Despite wearing work boots, Young outran the world-class athletes by not sleeping, finishing 9 hours in front of his closest competitor. He then split the $10,000 first prize among 5 other runners and didn't keep a cent for himself.
8. Jennifer Jones' curling shot: I don't know anything at all about curling, despite having lived in Canada since 1990. But this shot by Jennifer Jones in the 2005 Scott Tournament of Hearts is so spectacular, one can enjoy it just for the geometry.
9. Dave Wottle's 800 m Finish: Wottle, known for wearing a golf cap while running, had an unbelievable kick in the 1972 Olympics to come from behind to win the 800 meters.
1. Dorando Pietri's Marathon: Pietri, an unknown entrant in the 1908 London marathon, led the field as the race entered the final segment in the stadium, but was so exhausted and confused that he started going the wrong way around the track. Within sight of the finish line, he collapsed multiple times and had to be helped over the line by race officials. Although apparently the winner, he was later disqualified because of the help he received.
2. Emil Zátopek's Marathon: Having already won the 5K and 10K races at the 1952 Olympics in Helsinki, Zátopek decided at the last minute to enter the marathon, despite having never run the race before. He won.
3. Tom Dempsey's 63-yard field goal: Dempsey, born without a right foot and right hand, kicked a 63-yard field goal, the longest in NFL history, to give the New Orleans Saints a 19-17 win over the Detroit Lions. I think this is one of the most exciting moments in professional football.
4. Berkeley-Stanford football game, 1982: I was listening to this game on the radio, and couldn't believe my ears. With 4 seconds left, and Berkeley trailing 20-19 on a last-minute Stanford field goal, Berkeley returned the kick-off 55 yards to win 25-20. What made the return special was the use of 5 laterals and the fact that the Stanford band, believing the game won, went onto the field and created additional chaos, with the trombone player getting flattened at the conclusion. This event is so special that among Cal alumni it is simply known as "The Play". The next week, Berkeley street vendors were selling a t-shirt with a diagram of the play, ending in a music note representing the trombone.
5. Jordan Snipes' 2005 shot: With 0.6 seconds left in overtime and Guilford College trailing Randolph-Macon 89-88, Jordan Snipes rebounded the ball and launched a full-court shot that swished the hoop at the other hand, giving his team a 91-89 victory. Then a news team asked him to re-enact the shot, and he made it again.
6. Bonnie Richardson, a Texas high school student, won the state's team championship -- all by herself. Richardson, the only student from her school, Rochelle High, to compete, won the high jump and 200 meters, placed second in the long jump and and 100 meters, and finished 3rd in the discus, for a total of 42 team points.
7. Cliff Young's Ultramarathon: Young, a 61-year-old sheep farmer, entered the Sydney-to-Melbourne footrace (a distance of 875 kilometers) in 1983. Despite wearing work boots, Young outran the world-class athletes by not sleeping, finishing 9 hours in front of his closest competitor. He then split the $10,000 first prize among 5 other runners and didn't keep a cent for himself.
8. Jennifer Jones' curling shot: I don't know anything at all about curling, despite having lived in Canada since 1990. But this shot by Jennifer Jones in the 2005 Scott Tournament of Hearts is so spectacular, one can enjoy it just for the geometry.
9. Dave Wottle's 800 m Finish: Wottle, known for wearing a golf cap while running, had an unbelievable kick in the 1972 Olympics to come from behind to win the 800 meters.
Wednesday, August 06, 2008
Little League's Not For Atheists
When I was a kid, I desperately wanted to play in Little League baseball. I never did, although exactly why is lost in time. Was it because there was no Little League where I lived, or because I wasn't good enough, or some other reason? I can't remember. But maybe it was all for the best, because the Little League thinks that atheists can't be good baseball players.
Want proof? Look at the Little League Pledge, which is
I trust in God
I love my country
And will respect its laws
I will play fair
And strive to win
But win or lose
I will always do my best
Despite protests, Little League refuses to change or modify its pledge. When criticized, LL hides behind the claim that "it is not, and has never been, required to be recited by any person involved with Little League Baseball or Softball". But you can be damn sure if the Pledge said, "I trust in Allah", they'd be really quick to change it.
I don't understand why belief in magical beings has anything to do with playing baseball, and it's too bad that Little League does.
Update: Jerry K. reminds me about this column by my colleague Josh Benaloh.
Want proof? Look at the Little League Pledge, which is
I trust in God
I love my country
And will respect its laws
I will play fair
And strive to win
But win or lose
I will always do my best
Despite protests, Little League refuses to change or modify its pledge. When criticized, LL hides behind the claim that "it is not, and has never been, required to be recited by any person involved with Little League Baseball or Softball". But you can be damn sure if the Pledge said, "I trust in Allah", they'd be really quick to change it.
I don't understand why belief in magical beings has anything to do with playing baseball, and it's too bad that Little League does.
Update: Jerry K. reminds me about this column by my colleague Josh Benaloh.
Our Moral Intuition Says Abortion is not the Same as Murder
This is an very interesting video that demonstrates how our moral intuition about abortion denies its equivalence to murder. Even the video's committed anti-abortion activists could not bring themselves to say that, were abortion made illegal again, women who abort their fetuses should receive a prison term commensurate with murder. Perhaps more surprisingly, most of these anti-abortion activists seemed to think there should be no penalty at all. The interviewer tries to get them to think more deeply about this contradiction, but without much success.
The lesson is that most people do not regard abortion as equivalent to murder, despite the rhetoric of the anti-abortion movement.
The lesson is that most people do not regard abortion as equivalent to murder, despite the rhetoric of the anti-abortion movement.
Danish Hospital Hosts Wacko Medical Meeting
From the Copenhagen Post comes this article about how the Copenhagen University Hospital agreed to host the woo-fest called the European Quantum Energy Medicine Conference, to the disgust of Danish medical professionals. One is quoted as saying, "It's an extremely unfortunate signal to send when we're talking about a conference that primarily consists of completely undocumented claims, and products that don't have a shred of evidence supporting their effectiveness".
I wonder why they didn't get Radovan Karadzic to speak.
Hat-tip: Terry Polevoy.
I wonder why they didn't get Radovan Karadzic to speak.
Hat-tip: Terry Polevoy.
Tuesday, August 05, 2008
I Was Doing It Right All Along
When I was a kid, I used to sneeze and use my shirtsleeve to wipe it off. My teachers and classmates were usually horrified by this practice, but now I learn, to my surprise, that I was right all along. Well, sort of.
My pharmacy was displaying this extremely weird large poster, which is available from www.coughsafe.com:

At the same website, you can even watch a movie that teaches you how to cough and sneeze properly. Four stars!
My pharmacy was displaying this extremely weird large poster, which is available from www.coughsafe.com:
At the same website, you can even watch a movie that teaches you how to cough and sneeze properly. Four stars!
Wednesday, July 30, 2008
"Institute of Advanced Scientific Researches" Changes Name, Threatens Me
I previously commented on the odd solicitation I received from the "Institute of Advanced Scientific Researches". I observed in passing that the name was odd, as most North Americans would be more likely to use "research" instead of "researches".
Over the past couple of days, the Institute has apparently changed its name to the "Institute of Advanced Scientific Research". But instead of thanking me for correcting their English, they are now threatening me.
I have now received several incoherent e-mail messages from "Zahra K. Khalafi" who claims to be the "Director of Institute of Advanced Scientific Research" and accuses me of writing "fake" and "counterfeit" messages. He states he will "take action by the law and we will see you in court in USA or CANAD" [sic] and asks if I am a "Canadian government agent". Really, I have no idea what he is complaining about. I found his institute's solicitation odd, and I said so. I found his Institute's name odd, and he apparently changed it. It seems to me he should be grateful.
If Mr. Khalafi wants to encourage other researchers to join his efforts, inviting people to join editorial boards and then threatening to sue them is probably not the optimal way to go about it.
Over the past couple of days, the Institute has apparently changed its name to the "Institute of Advanced Scientific Research". But instead of thanking me for correcting their English, they are now threatening me.
I have now received several incoherent e-mail messages from "Zahra K. Khalafi" who claims to be the "Director of Institute of Advanced Scientific Research" and accuses me of writing "fake" and "counterfeit" messages. He states he will "take action by the law and we will see you in court in USA or CANAD" [sic] and asks if I am a "Canadian government agent". Really, I have no idea what he is complaining about. I found his institute's solicitation odd, and I said so. I found his Institute's name odd, and he apparently changed it. It seems to me he should be grateful.
If Mr. Khalafi wants to encourage other researchers to join his efforts, inviting people to join editorial boards and then threatening to sue them is probably not the optimal way to go about it.
Saturday, July 26, 2008
Another Healie-Feelie Book
The recent flood in my basement ruined a perfectly good book. Actually, the book was perfectly awful: it is Healing Crystals and Gemstones: From Amethyst to Zircon by Flora Peschek-Böhmer and Gisela Schreiber. (I won't say how it came to be in my basement, but I will say that I don't own it.)
This book is typical of the "healing crystal" literature: a lack of understanding of basic geology and chemistry, combined with healing claims that are not substantiated in any way, resulting in dangerous advice for people with serious health conditions.
The book is littered with errors. Even the very first sentence is incorrect, when it claims that all gemstones originate from hot magma. (Opal, for example, can be sedimentary.) The authors claim "jasper ... always has a trigonal structure", when in fact jasper essentially doesn't form crystals at all. On page 150, the authors claim that fluorite is "also known as feldspar", when in fact feldspar is an entirely different mineral. On page 75, the authors confuse native antimony with the mineral stibnite, which is actually antimony sulfide. On page 85 the authors claim that that aragonite is silicon dioxide, not calcium carbonate. The mineral Charoite is consistently misspelled as "Chaorite". They claim that the crystal structure of Herkimer diamonds is similar to that of real diamond, when in fact they crystallize in completely different systems. They claim that kunzite is "aluminum acetate-lithium", when in fact it is a lithium aluminum silicate; no acetate at all is contained in it. They claim that Magnesite "consists almost entirely of pure magnesium", when in fact it is just magnesium carbonate. They claim that Magnesite "was first discovered in Africa", when in fact its co-type localities are in Greece and Italy.
The authors recommend the use of various minerals without noting health problems associated with them. For example, the authors recommend actinolite to stimulate "the inner organs such as the liver and the kidneys", but fail to note that the tiny fibers of actinolite have been associated with severe and potentially life-threatening respiratory disorders. They recommend using orpiment "externally as a powder to treat sexual disorders", but this is not a good idea, as orpiment is arsenic sulfide.
But the most serious problem with the book is the repeated and unsubstantiated health claims, all made without a single reference to any study in support of them. Someone with serious health problems might be persuaded to use the entirely ineffective remedies suggested in this book instead of seeking effective medical treatment. Cancer is unlikely to be helped by toumaline, sugilite, or lapis lazuli. High blood pressure cannot be improved with sodalite, lapis, or chrysoprase. Diabetes sufferers will find no relief with citrine or pyrite. Kidney ailments will not be improved with jade. For ulcers you should see your family doctor, not wear jasper or topaz.
Ahh, well, I doubt any of this will convince the healie-feelie crowd. When they're done with this, they can move on to the other immortal works of Flora Peschek-Böhmer, such as Urine Therapy: Nature's Elixir for Good Health. Urine therapy, in case you didn't know, consists of drinking your own urine. Great idea! You can use it to wash down some crystals of orpiment.
This book is typical of the "healing crystal" literature: a lack of understanding of basic geology and chemistry, combined with healing claims that are not substantiated in any way, resulting in dangerous advice for people with serious health conditions.
The book is littered with errors. Even the very first sentence is incorrect, when it claims that all gemstones originate from hot magma. (Opal, for example, can be sedimentary.) The authors claim "jasper ... always has a trigonal structure", when in fact jasper essentially doesn't form crystals at all. On page 150, the authors claim that fluorite is "also known as feldspar", when in fact feldspar is an entirely different mineral. On page 75, the authors confuse native antimony with the mineral stibnite, which is actually antimony sulfide. On page 85 the authors claim that that aragonite is silicon dioxide, not calcium carbonate. The mineral Charoite is consistently misspelled as "Chaorite". They claim that the crystal structure of Herkimer diamonds is similar to that of real diamond, when in fact they crystallize in completely different systems. They claim that kunzite is "aluminum acetate-lithium", when in fact it is a lithium aluminum silicate; no acetate at all is contained in it. They claim that Magnesite "consists almost entirely of pure magnesium", when in fact it is just magnesium carbonate. They claim that Magnesite "was first discovered in Africa", when in fact its co-type localities are in Greece and Italy.
The authors recommend the use of various minerals without noting health problems associated with them. For example, the authors recommend actinolite to stimulate "the inner organs such as the liver and the kidneys", but fail to note that the tiny fibers of actinolite have been associated with severe and potentially life-threatening respiratory disorders. They recommend using orpiment "externally as a powder to treat sexual disorders", but this is not a good idea, as orpiment is arsenic sulfide.
But the most serious problem with the book is the repeated and unsubstantiated health claims, all made without a single reference to any study in support of them. Someone with serious health problems might be persuaded to use the entirely ineffective remedies suggested in this book instead of seeking effective medical treatment. Cancer is unlikely to be helped by toumaline, sugilite, or lapis lazuli. High blood pressure cannot be improved with sodalite, lapis, or chrysoprase. Diabetes sufferers will find no relief with citrine or pyrite. Kidney ailments will not be improved with jade. For ulcers you should see your family doctor, not wear jasper or topaz.
Ahh, well, I doubt any of this will convince the healie-feelie crowd. When they're done with this, they can move on to the other immortal works of Flora Peschek-Böhmer, such as Urine Therapy: Nature's Elixir for Good Health. Urine therapy, in case you didn't know, consists of drinking your own urine. Great idea! You can use it to wash down some crystals of orpiment.
Strange Solicitation
Today I received an odd solicitation to join the editorial board of a journal I've never heard of, the Journal of Advanced Researches on Computer Science. It is published by an institute I've never heard of, the "Institute of Advanced Scientific Researches".
The solicitation was strange for a number of reasons. First, this "Institute" seems to publish (or want to publish) 16 different journals; yet as I write this, many of them seem to have no editorial board listed. Second, the name of the Institute itself is odd; no native English speaker would be likely refer to "researches", as "research" is typically a mass noun, like "information". Also, the solicitation letter was filled with grammatical errors. Third, I can find no information about this "Institute" online, nor any of the people associated with it, except for the person who wrote the solicitation letter, "Kavin Kalfi".
So, does anyone else know about this "Institute"?
The solicitation was strange for a number of reasons. First, this "Institute" seems to publish (or want to publish) 16 different journals; yet as I write this, many of them seem to have no editorial board listed. Second, the name of the Institute itself is odd; no native English speaker would be likely refer to "researches", as "research" is typically a mass noun, like "information". Also, the solicitation letter was filled with grammatical errors. Third, I can find no information about this "Institute" online, nor any of the people associated with it, except for the person who wrote the solicitation letter, "Kavin Kalfi".
So, does anyone else know about this "Institute"?
Friday, July 25, 2008
Friday Moose Blogging
Here are some photos by my colleague Doug Payne, taken during his recent trip to Algonquin Park. No surprise, there's a moose or two. Moose twins, too.
Thursday, July 24, 2008
SIGAPL dissolved
A sad day for the APL community: SIGAPL, the ACM special interest group on APL, has been dissolved by the ACM SIG governing board.
I first learned APL in 1973 at the IBM Scientific Center in Philadelphia (long gone). At the insistence of my father, I had written to several large computing companies, asking for a summer job. Only IBM replied favorably, and I had a rather intimidating interview with Ken Iverson and Adin Falkoff in their offices on Market Street. To my delight, they hired me for a vague project about whether it was better to learn APL by reading other people's programs first, or writing one's own.
I remember going home with a copy of the APL\360 user's manual, which was initially very mysterious to me, and had an exotic smell like bacon. I had learned programming from Kemeny's book on BASIC, and APL was a revelation. I immediately took to the language and ended up spending the next few years of my life involved in APL in various ways: coding in APL for financial institutions, writing my own extended precision arithmetic package and selling it to IBM, etc. I was programming on IBM machines, using a printing terminal with an APL typeball.
I soon discovered the newsletter of SIGAPL, called "Quote-Quad". (The unusual name comes from the special APL symbol for character input, which was formed by typing a "quad" (shift-L) and overstriking it with a quote (shift-K).) At that time I eagerly awaited every issue, filled with incredible one-liners that accomplished results you would need hundreds of lines in BASIC to duplicate, puzzles like the self-replicating APL expression puzzle (type it in and you get exactly the same result back), and proposals to extend APL in bizarre and mind-expanding ways. It was really the golden age of APL.
It's clear that the passion and excitement about APL has decreased since then, although I still use APL on at least a weekly basis to do experimental mathematics: Dyalog APL on my Sun workstation, and APLX on my Macintosh. In many ways it is far superior to Maple and Mathematica, although the lack of easy availability of extended precision and symbolic arithmetic is a pain. I can code a quick-and-dirty solution to a problem faster in APL than I can in any other language. People who see it always stare open-mouthed: what is that? they say, and they want to borrow a manual.
The dissolution of SIGAPL is the passing of an age.
I first learned APL in 1973 at the IBM Scientific Center in Philadelphia (long gone). At the insistence of my father, I had written to several large computing companies, asking for a summer job. Only IBM replied favorably, and I had a rather intimidating interview with Ken Iverson and Adin Falkoff in their offices on Market Street. To my delight, they hired me for a vague project about whether it was better to learn APL by reading other people's programs first, or writing one's own.
I remember going home with a copy of the APL\360 user's manual, which was initially very mysterious to me, and had an exotic smell like bacon. I had learned programming from Kemeny's book on BASIC, and APL was a revelation. I immediately took to the language and ended up spending the next few years of my life involved in APL in various ways: coding in APL for financial institutions, writing my own extended precision arithmetic package and selling it to IBM, etc. I was programming on IBM machines, using a printing terminal with an APL typeball.
I soon discovered the newsletter of SIGAPL, called "Quote-Quad". (The unusual name comes from the special APL symbol for character input, which was formed by typing a "quad" (shift-L) and overstriking it with a quote (shift-K).) At that time I eagerly awaited every issue, filled with incredible one-liners that accomplished results you would need hundreds of lines in BASIC to duplicate, puzzles like the self-replicating APL expression puzzle (type it in and you get exactly the same result back), and proposals to extend APL in bizarre and mind-expanding ways. It was really the golden age of APL.
It's clear that the passion and excitement about APL has decreased since then, although I still use APL on at least a weekly basis to do experimental mathematics: Dyalog APL on my Sun workstation, and APLX on my Macintosh. In many ways it is far superior to Maple and Mathematica, although the lack of easy availability of extended precision and symbolic arithmetic is a pain. I can code a quick-and-dirty solution to a problem faster in APL than I can in any other language. People who see it always stare open-mouthed: what is that? they say, and they want to borrow a manual.
The dissolution of SIGAPL is the passing of an age.
Wednesday, July 23, 2008
Christian Compassion
From the Toronto Sun comes this heartwarming story of Christian compassion.
Sex offender Patrick White is really, really sorry that he committed fraud and sex-related offenses in the US and Canada. He's really, really sorry that he sexually abused mentally retarded men. In fact, he's so sorry that he will pay for counselling for his victims, but only if it's "Christian counselling".
How generous!
Never fear, White is assured of a place in his Christian heaven, because, as he says, "God has forgiven me".
Sex offender Patrick White is really, really sorry that he committed fraud and sex-related offenses in the US and Canada. He's really, really sorry that he sexually abused mentally retarded men. In fact, he's so sorry that he will pay for counselling for his victims, but only if it's "Christian counselling".
How generous!
Never fear, White is assured of a place in his Christian heaven, because, as he says, "God has forgiven me".
Mark Shea Thinks Scientists Are Stupid, Makes Gaffe
Over at Catholic Exchange, Mark Shea relates an anecdote that demonstrates, for him, that scientists are sadly lacking in emotional intelligence:
Long ago, I remember watching some film about human evolution narrated by Richard Leakey, Jr. It was interesting as such films go, but you got the sense as it went along that it explained everything at the cost of leaving everything out—like scientists in a Far Side cartoon analyzing humor.
The crowning moment of the film, for me, was when Leakey stood in front of the gorgeous twenty-thousand-year-old cave paintings in Lascaux, France and, with genuine puzzlement in his voice, wondered aloud “Why did they do this? What was the purpose?”
I had the distinct impression he would have expressed equal bafflement were he standing in the Louvre. There seemed to be a gene missing somewhere. He was a man who knew a great deal about human origins and yet, however smart he was, there was something about him that was radically out of touch with, well, what it meant to be human. You felt he needed tape on his glasses, a pocket protector, high water trousers and D&D dice in his pocket to complete the image he seemed to project with such earnest unconsciousness.
I'm a little skeptical that the film went exactly as Shea claims it did. People's memories are notoriously unreliable, and events are rewritten in brains to conform to a person's individual narrative: in this case, Shea's commitment to the Catholic faith as the essential guide to understanding the world.
But assuming Shea's memory was correct, he seems to have entirely missed the point of Leakey's question. Shea doesn't seem to have any awareness that there is a debate among archaeologists about Lascaux's purpose. Was it continuously occupied, or only visited periodically? Was it part of a shaman's ritual to improve chances during the hunt, a record of previous successful hunts, or simply a decoration? Why are there no images of reindeer, which formed a major part of the diet of the artists? Do the painted dots really represent an accurate map of the night sky, as suggested by Michael Rappenglueck?
If you have scientific training, then questions like these seem natural and interesting. If you don't, and are immersed in dogma that preaches simple answers to difficult questions, then even asking this kind of question demonstrates some moral failing. I'd wager that Leakey knows a lot more about people, and their goals, desires, and questions, than Mark Shea does.
Long ago, I remember watching some film about human evolution narrated by Richard Leakey, Jr. It was interesting as such films go, but you got the sense as it went along that it explained everything at the cost of leaving everything out—like scientists in a Far Side cartoon analyzing humor.
The crowning moment of the film, for me, was when Leakey stood in front of the gorgeous twenty-thousand-year-old cave paintings in Lascaux, France and, with genuine puzzlement in his voice, wondered aloud “Why did they do this? What was the purpose?”
I had the distinct impression he would have expressed equal bafflement were he standing in the Louvre. There seemed to be a gene missing somewhere. He was a man who knew a great deal about human origins and yet, however smart he was, there was something about him that was radically out of touch with, well, what it meant to be human. You felt he needed tape on his glasses, a pocket protector, high water trousers and D&D dice in his pocket to complete the image he seemed to project with such earnest unconsciousness.
I'm a little skeptical that the film went exactly as Shea claims it did. People's memories are notoriously unreliable, and events are rewritten in brains to conform to a person's individual narrative: in this case, Shea's commitment to the Catholic faith as the essential guide to understanding the world.
But assuming Shea's memory was correct, he seems to have entirely missed the point of Leakey's question. Shea doesn't seem to have any awareness that there is a debate among archaeologists about Lascaux's purpose. Was it continuously occupied, or only visited periodically? Was it part of a shaman's ritual to improve chances during the hunt, a record of previous successful hunts, or simply a decoration? Why are there no images of reindeer, which formed a major part of the diet of the artists? Do the painted dots really represent an accurate map of the night sky, as suggested by Michael Rappenglueck?
If you have scientific training, then questions like these seem natural and interesting. If you don't, and are immersed in dogma that preaches simple answers to difficult questions, then even asking this kind of question demonstrates some moral failing. I'd wager that Leakey knows a lot more about people, and their goals, desires, and questions, than Mark Shea does.
Sunday, July 20, 2008
Rutgers Graduate Student Finds New Prime-Generating Formula
Studying prime numbers is like playing the guitar. No, really, let me explain.
The guitar is a simple instrument: six strings, some frets, a sound hole. You strum with the right hand, and form chords with the left. What could be simpler? Any reasonably coordinated person can learn to play a simple song, such as "Heart of Gold", passably in a few hours.
In the same way, the prime numbers have a simple definition: the integers greater than 1 that are divisible only by themselves and 1. Any reasonably intelligent person can learn to test a small number for primality, or understand Euclid's proof that there are infinitely many prime numbers, in a short amount of time.
Yet the guitar is also fiendishly difficult. Those studying classical guitar know well how some pieces take hundreds of hours to master. Techniques such as tremolo might take years, especially if you start learning as an adult.
In the same way, the prime numbers contain within them enough subtlety that many problems remain unsolved after hundreds of years. Goldbach conjectured in 1742 that every even number greater than 2 is the sum of two primes, and today this conjecture is still unsolved. (It is known to hold for every even number less than 1018.) And a proof of the Riemann hypothesis, which would have extremely important consequences for the distribution of primes, will net you a million dollars from the Clay Mathematics Institute -- probably more than you'll get from appearing on American Idol.
For a long time mathematicians have sought a simple formula that would generate all the prime numbers, or even infinitely many distinct prime numbers. Some have even gone so far as to claim that no such formula exists -- a statement of very questionable veracity that depends entirely on one's definition of "formula". If you define formula to mean "polynomial with integer coefficients", then it's not hard (and I leave it as a challenge to the reader) to prove that no such polynomial can generate only primes, other than the trivial example of a constant polynomial. Euler's polynomial x2 + x + 41 comes close: it generates primes for x = 0, 1, 2, ..., 39, but fails at x = 40.
A slight variation, though, leads to a genuine prime-generating polynomial. It is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem that there exists a multivariate polynomial with integer coefficients that takes on only negative and prime values when integers are substituted for the variables, and every prime is generated by some choice of the variables. In 1976, Jones, Sato, Wada, and Wiens actually wrote down such a polynomial. It has 26 variables.
Another prime-generating formula comes from a 1947 paper of W. H. Mills. Mills proved that there exists a real number A such that [ A3n ] is a prime number for all integers n ≥ 1. Here [ x ] is the greatest integer function, the greatest integer ≤ x. Unfortunately, nobody knows a good way to calculate A other than testing the numbers the formula is supposed to generate for primality, and then constructing A by working backwards.
So many people have worked on the prime numbers that it seems unlikely that there could be a simple prime-generating function that has been overlooked until now.

Rutgers graduate student Eric Rowland has defied the odds, however, and has found a new one. In a paper just published in a journal I edit, the Journal of Integer Sequences, Rowland defines his formula and proves it generates only 1's and primes. (1 is generally not accepted as a prime number, for a variety of reasons. For one thing, if 1 were a prime, then positive integers would not have a unique factorization into primes.) To be precise, I should say that the unusual property of the formula was originally conjectured by a team led by Matt Frank at a mathematics summer school in 2003 where Rowland was attending, but it was not proved until now.
Here is Rowland's formula. We define a(1) = 7, and for n ≥ 2 we set
a(n) = a(n-1) + gcd(n,a(n-1)).
Here "gcd" means the greatest common divisor. So, for example, we find a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), the so-called first differences of the original sequence.
For example, here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
and here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
If we ignore the 1's, then, the Rowland formula starts by generating the primes 5, 3, 11, 3 (again), and 23. The reader can easily program up the formula and find lots more primes. Removing duplicates, the first few are
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...
Why does it work? The proof is too involved to give here, but it is not that difficult. The interested reader can go to Rowland's paper for the details.
Rowland has been involved with mathematics for some time. He attended UC Santa Cruz and graduated with highest honors in math in 2003. Since then he has been a graduate student at Rutgers University, studying with Doron Zeilberger. Rowland describes himself as an "experimental mathematician", and uses the computer algebra system Mathematica for his experiments. Rowland tells me that he tried to prove the formula from time to time over a four-year period, but once the crucial insight was found, "I had an outline of the proof within a few days and all the details within a few weeks."
Are there any other formulas like Rowland's? Apparently yes. Benoit Cloitre, a French mathematician, recently proved that if you set b(1) = 1 and
b(n) = b(n-1) + lcm(n,b(n-1)) for n ≥ 2,
then b(n)/b(n-1)-1 is either 1 or prime for all n ≥ 2.
Will Rowland's formula lead to more efficient ways to generate large primes? If so, cryptographers would love it. But it seems unlikely. As Rowland explains in his paper, his formula only produces the prime p after first generating (p-3)/2 1's, so it takes a really long time to generate a large prime. He has a method for skipping over those useless 1's, but doing so essentially requires an independent test for primality.
Are there still unsolved properties of Rowland's prime generator? Yes. For example, is there anything special about the choice a(1) = 7? Other choices, such as a(1) = 8, always generate primes and 1's, but others, such as a(1) = 532, do not. (This choice generates 9 after less than 20 steps.) However, Rowland conjectures that for each starting value of a(1), there exists a point after which the first differences are always either 1 or prime. Rowland also doesn't know if his formula eventually generates all odd primes, although he believes it probably does.
Rowland has a number of other projects in the works. He told me, "I'm working on several things, mostly trying to finish up a backlog of papers. But one newer project is putting bounds on the frequency of 1's in the Kolakoski word. Another is something I'm not ready to fully divulge, but it has to do with values of the p-adic logarithm. A longer term project of mine is extending what is known about the arithmetic of Pascal's triangle modulo m and, generally, additive cellular automata."
What problem would Rowland most like to solve? "I'd really like to solve the 3n+1 problem, because I think it would tell us something very interesting about representations of integers. Dividing by 2 in base 2 just means dropping the last 0, and mapping n -> 3n+1 in base 3 just means appending 1. The problem is that we don't know how to get these two bases to talk to each other -- and of course perhaps there isn't a way -- but a solution to the 3n+1 problem might show us how to do this."
Solving the 3n+1 problem would indeed be a great achievement. In the meantime, however, he can take pleasure in his prime formula. Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy.
Update, July 31 2008: Rowland has his own post describing his discovery.
The guitar is a simple instrument: six strings, some frets, a sound hole. You strum with the right hand, and form chords with the left. What could be simpler? Any reasonably coordinated person can learn to play a simple song, such as "Heart of Gold", passably in a few hours.
In the same way, the prime numbers have a simple definition: the integers greater than 1 that are divisible only by themselves and 1. Any reasonably intelligent person can learn to test a small number for primality, or understand Euclid's proof that there are infinitely many prime numbers, in a short amount of time.
Yet the guitar is also fiendishly difficult. Those studying classical guitar know well how some pieces take hundreds of hours to master. Techniques such as tremolo might take years, especially if you start learning as an adult.
In the same way, the prime numbers contain within them enough subtlety that many problems remain unsolved after hundreds of years. Goldbach conjectured in 1742 that every even number greater than 2 is the sum of two primes, and today this conjecture is still unsolved. (It is known to hold for every even number less than 1018.) And a proof of the Riemann hypothesis, which would have extremely important consequences for the distribution of primes, will net you a million dollars from the Clay Mathematics Institute -- probably more than you'll get from appearing on American Idol.
For a long time mathematicians have sought a simple formula that would generate all the prime numbers, or even infinitely many distinct prime numbers. Some have even gone so far as to claim that no such formula exists -- a statement of very questionable veracity that depends entirely on one's definition of "formula". If you define formula to mean "polynomial with integer coefficients", then it's not hard (and I leave it as a challenge to the reader) to prove that no such polynomial can generate only primes, other than the trivial example of a constant polynomial. Euler's polynomial x2 + x + 41 comes close: it generates primes for x = 0, 1, 2, ..., 39, but fails at x = 40.
A slight variation, though, leads to a genuine prime-generating polynomial. It is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem that there exists a multivariate polynomial with integer coefficients that takes on only negative and prime values when integers are substituted for the variables, and every prime is generated by some choice of the variables. In 1976, Jones, Sato, Wada, and Wiens actually wrote down such a polynomial. It has 26 variables.
Another prime-generating formula comes from a 1947 paper of W. H. Mills. Mills proved that there exists a real number A such that [ A3n ] is a prime number for all integers n ≥ 1. Here [ x ] is the greatest integer function, the greatest integer ≤ x. Unfortunately, nobody knows a good way to calculate A other than testing the numbers the formula is supposed to generate for primality, and then constructing A by working backwards.
So many people have worked on the prime numbers that it seems unlikely that there could be a simple prime-generating function that has been overlooked until now.

Rutgers graduate student Eric Rowland has defied the odds, however, and has found a new one. In a paper just published in a journal I edit, the Journal of Integer Sequences, Rowland defines his formula and proves it generates only 1's and primes. (1 is generally not accepted as a prime number, for a variety of reasons. For one thing, if 1 were a prime, then positive integers would not have a unique factorization into primes.) To be precise, I should say that the unusual property of the formula was originally conjectured by a team led by Matt Frank at a mathematics summer school in 2003 where Rowland was attending, but it was not proved until now.
Here is Rowland's formula. We define a(1) = 7, and for n ≥ 2 we set
a(n) = a(n-1) + gcd(n,a(n-1)).
Here "gcd" means the greatest common divisor. So, for example, we find a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), the so-called first differences of the original sequence.
For example, here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69
and here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23
If we ignore the 1's, then, the Rowland formula starts by generating the primes 5, 3, 11, 3 (again), and 23. The reader can easily program up the formula and find lots more primes. Removing duplicates, the first few are
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...
Why does it work? The proof is too involved to give here, but it is not that difficult. The interested reader can go to Rowland's paper for the details.
Rowland has been involved with mathematics for some time. He attended UC Santa Cruz and graduated with highest honors in math in 2003. Since then he has been a graduate student at Rutgers University, studying with Doron Zeilberger. Rowland describes himself as an "experimental mathematician", and uses the computer algebra system Mathematica for his experiments. Rowland tells me that he tried to prove the formula from time to time over a four-year period, but once the crucial insight was found, "I had an outline of the proof within a few days and all the details within a few weeks."
Are there any other formulas like Rowland's? Apparently yes. Benoit Cloitre, a French mathematician, recently proved that if you set b(1) = 1 and
b(n) = b(n-1) + lcm(n,b(n-1)) for n ≥ 2,
then b(n)/b(n-1)-1 is either 1 or prime for all n ≥ 2.
Will Rowland's formula lead to more efficient ways to generate large primes? If so, cryptographers would love it. But it seems unlikely. As Rowland explains in his paper, his formula only produces the prime p after first generating (p-3)/2 1's, so it takes a really long time to generate a large prime. He has a method for skipping over those useless 1's, but doing so essentially requires an independent test for primality.
Are there still unsolved properties of Rowland's prime generator? Yes. For example, is there anything special about the choice a(1) = 7? Other choices, such as a(1) = 8, always generate primes and 1's, but others, such as a(1) = 532, do not. (This choice generates 9 after less than 20 steps.) However, Rowland conjectures that for each starting value of a(1), there exists a point after which the first differences are always either 1 or prime. Rowland also doesn't know if his formula eventually generates all odd primes, although he believes it probably does.
Rowland has a number of other projects in the works. He told me, "I'm working on several things, mostly trying to finish up a backlog of papers. But one newer project is putting bounds on the frequency of 1's in the Kolakoski word. Another is something I'm not ready to fully divulge, but it has to do with values of the p-adic logarithm. A longer term project of mine is extending what is known about the arithmetic of Pascal's triangle modulo m and, generally, additive cellular automata."
What problem would Rowland most like to solve? "I'd really like to solve the 3n+1 problem, because I think it would tell us something very interesting about representations of integers. Dividing by 2 in base 2 just means dropping the last 0, and mapping n -> 3n+1 in base 3 just means appending 1. The problem is that we don't know how to get these two bases to talk to each other -- and of course perhaps there isn't a way -- but a solution to the 3n+1 problem might show us how to do this."
Solving the 3n+1 problem would indeed be a great achievement. In the meantime, however, he can take pleasure in his prime formula. Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy.
Update, July 31 2008: Rowland has his own post describing his discovery.
Friday, July 18, 2008
Friday Moose Blogging
Here's a great youtube video of 2 baby moose and their mother playing in a sprinkler in an Alaskan backyard.
Subscribe to:
Posts (Atom)
