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.