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 .
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.
Advertisement
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 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 ĐÓ°ÉÔ´´ 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â.
