While drifting off in my last Variational Principles lecture before I discovered Tim Gowers was doing a more interesting course at the same time, I had a few thoughts about ‘random’ sets of natural numbers and whether or not they contain arithmetic progressions. After sitting down at the CMS today to properly think about some of these, the following amusing open-ended problem came into my mind:

Question: For A \subset \mathbb{N} we define the density \delta(A,N) = \frac{|A \cap \{1,2,...,N\}|}{N}. How large can \Delta(N) = \delta(A,N) be if A contains no nontrivial arithmetic progressions?

Finding upper bounds on \Delta(N) is probably very difficult. Szemeredi’s theorem, which is highly nontrivial, gives the bound \Delta(N) = o(1). If there is a better bound, it will probably be harder to prove.

However, finding lower bounds is actually very possible and perhaps the ideal distraction for exam term. My first attempts in the CMS gave a bound of \Delta(N) \geq N^{-c} for c = \frac{1}{3}\log \frac{3}{2}. I’ll try to optimise this tomorrow and over the course of the next month, but will not yet post any of my constructions to allow the reader the opportunity to try this problem.

I’d be glad to hear any bounds readers of this post manage to find. We could even turn it into something of a competition in the comments box if several people get involved, and perhaps at some point we could reveal our methods of construction.