Science, Vol 296, Issue 5565, 3940 , 5
April 2002
MATHEMATICS:
Erdös's HardtoWin Prizes Still Draw Bounty Hunters
Charles Seife
Half a decade after his death, a colorful mathematician
continues to spur his colleagues with challengesand checks
It takes more than death to keep a good mathematician down. Among many
other things, Paul Erdös proved that. In life, the world's premier
number theorist supported himself by wandering from colleague to
colleague, freeloading off friends and strangers, and, in return,
sharing his vast mathematical insight with all comers. His 6decade
frenzy of nearnonstop work resulted in more than 1500 papers that link
him to almost every academic mathematician in the world. Erdös's death
in 1996 has slowed, but not stopped, his publication rate: Over the
past 5 years, journals have published some 62 new papers bearing his
name. And he is still guiding the research of mathematicians with the
problems he left behind.
Problems, problems, problems. Erdös hurled them out
relentlessly, in
lectures, papers, and informal talks: problems in number theory, logic,
graph theory, geometry, combinatorics, and other disciplines. Every
mathematician agrees on their importance. Yet nobody has listed them
all; nobody even knows how many there are.
"I'd say it's in the small number of thousands," says Ronald
Graham, a
mathematician and computer scientist at the University of California
(UC), San Diego, who managed many of Erdös's affairs in the last few
years of Erdös's life. András Hajnal, a set theorist at Rutgers
University in New Brunswick, New Jersey, says he can name at least 100
in set theory alone.
As remarkable as their variety are the incentives Erdös
attached to
them. Early in his career, Erdös began to offer small prizes for
solutions to his problems. "They were $10, $25, $100. It was a way to
stimulate people and calibrate how difficult he thought the problem
was," Graham says. "Some prizes were larger: There is a famous $3000
one, and there's kind of a $10,000 one, but it's not well stated. There
are hundreds and hundreds of such problems." Alert listeners jotted the
figures down in lecture notes; compliant journal editors let Erdös
publish them in his papers.
Puzzle master. Although he once called himself
"a device for turning coffee into theorems," Paul Erdös was equally
adept at posing problems.
CREDIT: GEORGE PAUL CSICSERY
During Erdös's lifetime, the mounting mostwanted list could
reap
unexpected windfalls for his colleagues. "Some years ago, he was
visiting in Athens, Georgia. He was going back into town, and my
colleague Helmut Maier was giving him a ride," says Carl Pomerance, a
mathematician at Lucent Technologies' Bell Labs in Murray Hill, New
Jersey. The conversation naturally turned to mathematics and to a
theorem that Maier had just proven. " 'Maybe I offered a prize for
that,' said Erdös, and instead of going to town, they went to the
library," says Pomerance. Sure enough, Erdös had offered $100 for that
particular problem in a math journal, and he paid up. "I said to Erdös,
'That's a pretty expensive taxi ride,' and he found that hilarious,"
adds Pomerance.
Collecting a bounty could be tricky. Erdös often changed his
mind about
a problem's value, stating one sum in a lecture and another in print,
and he could alter the figure on a whim based on his own sense of
aesthetics. "I solved a $250 problem, but I only got $50 because Erdös
didn't like the proof," says Hajnal. Hajnal's proof, which had to do
with partitioning the real numbers into different sets, hinged upon a
logical trick rather than any special properties of the numbers. Erdös
also abhorred proofs related to Gödel's incompleteness theorem, which
states, in essence, that certain propositions are unprovable and
unfalsifiable. As a result, there are statements that one can simply
declare to be true or false. In the early 1960s, mathematician Paul
Cohen of Stanford University proved that the answer to a crucial
question about set theory was both yes and no. "Erdös didn't like
that," says Hajnal. "He stopped offering prizes for that kind of
question."
Erdös's cashless, bankfree lifestyle also played havoc with
his
incentive system. In 1993, Graham tried to iron out the snags by having
Erdös sign some of Graham's checks to be filled out later, "suitable
for framing." Graham himself provided checks suitable for cashing.
Since Erdös's death, Graham says, his informal foundation has cost him
about $3000 in award money. He estimates that the outstanding bounties
on unsolved problems total about $25,000.
The arrangement has worked smoothly on the whole, Graham says,
but
there have been hiccups. One occurred in 1999, when Ernie Croot,
currently a postdoc at UC Berkeley, solved a $750 Erdös problem related
to the ancient Egyptian style of writing fractions. Instead of writing
a fractional number as a ratio of two numbers, like 7/8, Egyptian
mathematicians expressed it as a sum of "unit fractions" whose
numerator is always one, such as 1/2 1/4 1/8. Erdös challenged his
peers to find out, given certain restrictions, how large the
denominators have to get to represent a given number.
When Croot announced his solution, Graham duly prepared one of
the
Erdössigned checks. "Graham presented it to Ernie at a meeting," says
Pomerance. "But Ernie, being a poor graduate student at the time,
didn't realize that it was only suitable for framinghe went and
cashed it." Graham still marvels that his bank honored Erdös's
posthumous check.
Graham's banking skills, of course, don't explain the staying
power of
Erdös's problems. That rests in the mathematical power of the problems
themselves, some of which have turned out to be incredibly subtle and
important. "One of the attractions of a lot of these problems is that
they are of unknown difficulty," says Graham. "It might be a
marshmallow, tasty and light, or it might be an acorn and grow into
something huge."
At the top end, those acorns can grow into huge oaks indeed.
The
recordholding $10,000 problem may never yield a check, Graham says,
because it's for a "significant improvement" upon a previous result: a
subjective judgment. But the next few in line have proven Herculean in
their difficulty. In the 1930s, for example, Erdös challenged number
theorists to prove a conjecture having to do with a collection of whole
numbers: If the collection has a certain type of "density," then there
must be an arithmetic progression (a set of evenly spaced numbers, such
as 4, 8, 12) of arbitrary length. In 1958, Klaus Roth of University
College London won mathematics' top honor, the Fields Medal, in part
for solving a special case of Erdös's problem. The problem itself will
net $1000 for the person who eventually solves it in full.
The famous $3000 problem is a variation on the same theme: to
prove
that there is an arithmetic progression of arbitrary length if the
reciprocals of the elements in a collection goes off to infinity. If
true, it will imply several important results in number theory. For
instance, it will mean that there are arbitrarily long arithmetic
progressions of prime numbers. So far, however, the proof has resisted
all comers. "Nobody can touch it," says Graham.
Most of the other problems are more accessible. "Erdös had an
unparalleled innate ability to form problems just out of current
reach," says Graham. "You can get it if you stand on your tiptoes and
jump a little bit. Once you're there, it's one more piton into the
cliff."
You may be a winner! Along with offering cash
for proofs, Erdös signed some of mathematician Ron Graham's checks as
award certificates.
CREDITS: (TOP TO BOTTOM) GEORGE PAUL CSICSERY;
COURTESY OF R. GRAHAM
How rare that knack for problemframing is can be seen in the
fate of
some who have dared to emulate it. In 1989, for example, John Conway, a
mathematician at Princeton University, offered $10,000 for the solution
to a problem about a peculiar sequence of numbers. Colin Mallows, a
statistician currently at Avaya Labs in Basking Ridge, New Jersey,
solved it within a few weeks. Conway paid up. "I don't know what kind
of maneuvers he went through to get $10,000, but he sent it," says
Mallows. "I was embarrassed and sent it back." Mallows says that Conway
had misspoken and meant the prize to be $1000 rather than $10,000.
"Most importantly, the problem was not of Erdös caliber, so that both
John and I would be embarrassed to have it enshrined as the
worldrecord prize." The two settled on $1000 as the bounty.
Such cautionary tales are few; for most mathematicians,
Erdös's
beyondthegrave sweepstakes remains the only game in town. Graham
still has a few Erdössigned checks left and will pay for many of the
Erdös problems. So will Andrew Beal, a Texas banker and amateur
mathematician who made a splash in the mathematical world in 1997 when
he offered a prize to anyone who could solve a problem resembling
Fermat's Last Theorem (Science, 21 November 1997, p. 1396).
Graham says he keeps a little extra padding in his bank account to
ensure that he can pay up the odd prize here or therealthough he's no
more concerned about being bankrupted by prize problems than he is
about a run on the bank. Not that it would matter if the money ran out;
becoming a piece of the Erdös legend is enough of a reward for most
mathematicians.
Deciding which claims are bona fide may pose more of a
challenge.
Unfortunately, the problems are in disarray, because Erdös talked at so
many universities and wrote papers in so many journals and languages.
(After hearing a limerick about "a paper by Erdös/Written in Kurdish,"
he allegedly tried, unsuccessfully, to publish a paper in that
language.) Graham and his wife, UC San Diego mathematician Fan Chung,
collected more than 125 Erdös problems in graph theory and published
them in 1998. Hajnal says he hopes someday to compile all the problems
into a single volume. "It's still being planned, but not much is
happening," he sighs.
Despite the disorder, most mathematicians would agree that
their field
has benefited from Erdös's gentle goading. His hit list spurs them to
approach problems they wouldn't normally tackle, says Jerrold Grossman,
a graph theorist at Oakland University in Rochester, Michigan. "It's
sort of like Fermat's Last Theorem, which guided research in number
theory for the good," Grossman says. Graham reaches farther back for an
analogy. "The problems serve as Socratic gadflies," he says, "reminding
us of how much we have to learn."
