Pattern master wins million-dollar mathematics prize

Imagine I present you with a line of cards labelled 1 through to n, where n is some incredibly large number. I ask you to remove a certain number of cards ? which ones you choose is up to you, inevitably leaving ugly random gaps in my carefully ordered sequence. It might seem as if all order must now be lost, but in fact no matter which cards you pick, I can always identify a surprisingly ordered pattern in the numbers that remain.

As a magic trick it might not equal sawing a woman in half, but mathematically proving that it is always possible to find a pattern in such a scenario is one of the feats that today garnered Endre Szemer?di mathematics' prestigious Abel prize.

The Norwegian Academy of Science and Letters in Oslo awarded Szemer?di the one million dollar prize today for "fundamental contributions to discrete mathematics and theoretical computer science". His specialty was combinatorics, a field that deals with the different ways of counting and rearranging discrete objects, whether they be numbers or playing cards.

The trick described above is a direct result of what is known as Szemer?di's theorem, a piece of mathematics that answered a question first posed by the mathematicians Paul Erd?s and P?l Tur?n in 1936 and that had remained unsolved for nearly 40 years.

Irregular mind

The theorem reveals how patterns can be found in large sets of consecutive numbers with many of their members missing. The patterns in question are arithmetic sequences ? strings of numbers with a common difference such as 3, 7, 11, 15, 19.

Such problems are often fairly easy for mathematicians to pose, but fiendishly difficulty to solve. The book An Irregular Mind, published in honour of Szemer?di's 70th birthday in 2010, stated that "his brain is wired differently than for most mathematicians".

"He's more likely than most to come up with an idea from left field," agrees mathematician Timothy Gowers of the University of Cambridge, who gave a presentation in Oslo on Szemer?di's work following the prize announcement.

Szemer?di actually came late to mathematics, initially studying at medical school for a year and then working in a factory before switching to become a mathematician. His talent was discovered by Erd?s, who was famous for working with hundreds of mathematicians in his lifetime.

Modest winner

When Szemer?di proved his theorem in 1975 he also provided mathematicians with a tool known as the Szemer?di regularity lemma, which gives a deeper understanding of large graphs ? mathematical objects often used to model networked structures such as the internet.

The lemma has also helped computer scientists better understand a technique in artificial intelligence known as "probably approximately correct learning". Szemer?di also worked on another important computing problem related to sorting lists, demonstrating a theoretical limit for sorting using parallel processors, which are found in modern computers.

Speaking on the phone to Gowers after receiving his award, Szemer?di said he was "very happy" but suggested that there were other mathematicians more deserving than himself. Gowers told New Scientist that Szemer?di was "very modest", adding that "he is a worthy winner and a lot of people think this sort of recognition is long overdue in his case".

If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.

Have your say

Only subscribers may leave comments on this article. Please log in.

Only personal subscribers may leave comments on this article

Subscribe now to comment.

All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.

If you are having a technical problem posting a comment, please contact technical support.

Source: http://feeds.newscientist.com/c/749/f/10897/s/1da8ef3f/l/0L0Snewscientist0N0Carticle0Cdn216160Epattern0Emaster0Ewins0Emilliondollar0Emathematics0Eprize0Bhtml0DDCMP0FOTC0Erss0Gnsref0Fonline0Enews/story01.htm

powell the last lecture syracuse basketball kim jong un josh powell madonna halftime show linsanity