Easy as 1, 2, 3?

The natural numbers, 1, 2, 3, 4, ..., are nice. We all understand them and we use them countless times every day. So what could be nicer than discovering interesting patterns within them?

What secrets do the natural numbers hold?

Endre Szemerédi, one of the main speakers at this year's British Mathematical Colloquium (BMC) and winner of the 2012 Abel prize, is interested in the simplest kind of pattern you can find within a collection of natural numbers: sequences of numbers that are all evenly spaced, with successive numbers all having the same distance between them. Examples are

2, 4, 6, 8, 10, 12,

a sequence of length 6 in which successive numbers are a distance 2 apart, or

4, 7, 10, 13, 16, 19, 22, 25,

a sequence of length 8 in which successive numbers are a distance 3 apart.

Such sequences are called arithmetic progressions. One very natural question to ask is this: given a collection of natural numbers, what is the longest arithmetic progression you can find within it? If your collection is small, then you can answer the question just by looking at it. But what if the collection is very large or even infinite? And what if you don't even know the exact numbers your collection contains?

Question like these have led to some very sophisticated mathematics. In 2006 the Australian mathematician Terence Tao was awarded the Fields medal, one of the highest honours in maths, partly for his work on arithmetic progressions within the prime numbers 2, 3, 5, 7, 11 ... . A quick look at the first few primes already reveals two short arithmetic progressions:

3, 5, 7

and

3, 7, 11.

The question is, are there longer ones hidden within the infinitely many primes?

Endre Szemerédi talking at the BMC.

Together with the British mathematician Ben Green Tao proved that the answer is yes. In fact, the primes contain arithmetic progressions of arbitrary length: no matter how large a number n you choose, you can be sure that there is an arithmetic progression of length n hidden somewhere within them. This doesn't mean, however, that you actually know what the prime numbers in this progression are: the proof only tells you that the progression exists. The longest arithmetic progression within the primes we actually know is only 26 numbers long. It was found in February 2014.

At the BMC Szemerédi was talking about another type of number collection within which you can look for arithmetic progressions. Given a collection $A$ of numbers, or a set of numbers as it’s properly called, you can make a new set, called $A+A$ , which consists of all the numbers you get by adding two numbers in $A$ . For example, if $A$ consists of the numbers 1, and 3,

$A = \{ 1,3\} ,$ then \[ A+A = \{ 1+1=2, 1+3=4, 3+3=6\} = \{ 2, 4, 6\} . \] In this example the new set $A+A$ contains an arithmetic progression of length 3 with spacing 2 between numbers, namely 2, 4, 6. This was easy to see, but can you say anything about arithmetic progressions in $A+A$ when you don’t know which numbers the original set $A$ contains? $$

Terence Tao won the 2006 Fields medal for his work on arithmetic progressions.

The answer, surprisingly, is yes. To get a feel for this, suppose that your set $A$ contains all the natural numbers from 1 up to some natural number $N.$ Then it’s not hard to convince yourself that the set $A+A$ contains all the natural numbers from 2 up to $2N$ (as an example, try $A=\{ 1,2\}$ to see that $A+A=\{ 2,3,4\}$ ). This means that $A+A$ contains the longest arithmetic progression possible for its size, namely $2, 3, ... ,2N.$ Now, by contrast, suppose that $A$ consists of one number only, call it $x$ . Then $A+A = \{ 2x\} ,$ so it contains no progression at all (unless you consider a single number as a progression of length 1). The example suggests that the size of the set $A$ relative to $N$ is important when it comes to arithmetic progressions in $A+A.$

And this is indeed true. In 2002 Ben Green, who we already met above, proved a result to show this, extending work done previously by another Fields medallist, Jean Bourgain.

Suppose that $A$ is a set containing some of the natural numbers from 1 up to some number $N$ and that the size of the set $A$ is $d \times N$ , where $d$ is some number between 0 and 1 (so if the size of $A$ is half of $N$ , then $d=1/2$ ). Then you can be sure that $A+A$ contains an arithmetic progression of length at least

$e^{c\sqrt{{\log {N}}}},$

where $c$ is a positive number that only depends on $d$ and not on the original set $A$ or the number $N.$ (Here $e = 2.71828...$ is the basis of the natural logarithm.)

Ben Green has contributed important results to the search for arithmetic progressions. Image: Renate Schmid, copyright MFO.

Your first reaction to this is probably "so what is the value of $c$ ?" The answer may seem a bit weird: that’s another question and we don’t really care right now. The important and surprising thing is that such a constant exists at all; that without knowing anything about the initial set $A$ we can actually say something about arithmetic progressions in $A+A.$ "The set $A$ was chosen arbitrarily, there are no restrictions on $A$ whatsoever," explains Szemerédi. "But we only had to add $A$ to itself and we got something out. This fits with the philosophy that in every chaos there is order. Here we provide the order by adding sets."

But now let’s go a little further. Given a set $A$ you can form a new one by considering, not just the sum of any two numbers in $A$ , but also the sum of any three, four, five, six, etc, numbers in $A$ . The result is a new set called $S_ A$ . It contains all the numbers you can express as sums of numbers in $A$ , where the sums can be as long or short as you like.

In 2006 Szemerédi and his colleague Van Vu proved that, again, you can say something about arithmetic progressions in $S_ A$ without knowing anything about $A$ apart from some information about its size. Suppose that the natural numbers in $A$ are all less than or equal to some natural number $N.$ Then $S_ A$ contains an arithmetic progression of length $N$ as long as the size of $A$ is at least $c\sqrt{N},$ where $c$ is a positive number that does not depend on the original set $A$ or on the number $N.$ (Again, we don’t really care what $c$ is — it’s enough that it exists.)

This is just one Szemerédi’s many beautiful results on arithmetic progressions, and the work on them is far from finished. For example, suppose that instead of considering the set of all numbers that can be written as sums of numbers in some original set $A,$ you only consider the set of all numbers that can be written as sums of distinct numbers in $A$ — so if $A$ contains the number 1, for example, the sum 1+1 = 2 is not allowed. It turns out that in this case the problem of finding arithmetic progressions becomes a whole lot harder. But that’s one of the fascinating things about number theory: the questions you can ask can be so easy that you could explain them to a child, but they can take decades, or even centuries, of hard maths to answer.

We talked to Endre Szemerédi at the British Mathematical Colloquium 2014, which took place at Queen Mary, University of London last week. You can read more about mathematics at the BMC here. To find out more about intriguing number theory questions, see here.