RElf (relf) wrote in ru_math,

про задачи и чеки от Эрдеша

Статья Erdös's Hard-to-Win Prizes Still Draw Bounty Hunters.
Для тех, у кого нет доступа:

Science, Vol 296, Issue 5565, 39-40 , 5 April 2002

Erdös's Hard-to-Win Prizes Still Draw Bounty Hunters

Charles Seife

Half a decade after his death, a colorful mathematician continues to spur his colleagues with challenges--and 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 6-decade frenzy of near-nonstop 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.

Figure 1
Puzzle master. Although he once called himself "a device for turning coffee into theorems," Paul Erdös was equally adept at posing problems.


During Erdös's lifetime, the mounting most-wanted 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, bank-free 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ös-signed 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 framing--he 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 record-holding $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."

Figure 2

Figure 3
You may be a winner! Along with offering cash for proofs, Erdös signed some of mathematician Ron Graham's checks as award certificates.


How rare that knack for problem-framing 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 world-record prize." The two settled on $1000 as the bounty.

Such cautionary tales are few; for most mathematicians, Erdös's beyond-the-grave sweepstakes remains the only game in town. Graham still has a few Erdös-signed 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 there--although 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."


  • Help

    Дорогие коллеги, помогите, если можете, получить доступ (нужно довольно срочно) к книге М.С Пинскера "Информация и информационная устойчивость…

  • Топологический вопрос о проективном пространстве

    Можно ли на каждой прямой трёхмерного проективного пространства выбрать точку, чтобы точка от прямой зависела непрерывно? При желании трёхмерное…

  • Дело Лузина

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded