# physics4me

physicsgg

## Pattern master wins million-dollar mathematics prize

Mathematician Endre Szemerédi is affectionately said to have an "irregular" mind

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…..