# A famous packing problem - if you are not smart enough to count the dots then use applied probability

**Presented by: **Phil Howlett, University of South Australia

In around 1935 George Szekeres conjectured that for N = (3^r+1)/2 the largest subset S(r) of the natural numbers {1, 2, . . . , N } which contains no arithmetic progression {n−d, n, n+d} of length three is a set with precisely 2^r elements. These sets can be constructed with a greedy packing algorithm to obtain S(1) = {1,2} ⊆ [1,2], S(2) = {1,2,4,5} ⊆ [1,5], S(3) = {1,2,4,5,10,11,13.14} ⊂ [1,14],... and so on. An even better way to construct them is to write down the non-negative integers using their ternary expansions {0, 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, 110, 111, . . .}, cross out all numbers containing the digit 2 and then add one {0,1,10,11,100,101,110,111,...}+1. In 1946 Felix Behrend employed a similar idea with a more general expansion to show that we could do better by not being quite so greedy. He used applied probability to count the dots (numbers) in his proposed sets and thereby established a lower bound that remained the best known for 62 years. In 2008 Michael Elkind used a very nice embellishment of Behrend’s argument to find a slightly improved (larger) lower bound. In the same year Ben Green and Julia Wolf published a simplified version of Elkin’s proof.

### About Maths Colloquium

The Mathematics Colloquium is directed at students and academics working in the fields of pure and applied mathematics, and statistics.

We aim to present expository lectures that appeal to our wide audience.

Information for speakers

#### Information for speakers

Maths colloquia are usually held on Mondays, from 2pm to 3pm, in various locations at St Lucia.

Presentations are 50 minutes, plus five minutes for questions and discussion.

Available facilities include:

- computer
- data projector
- chalkboard or whiteboard

To avoid technical difficulties on the day, please contact us in advance of your presentation to discuss your requirements.