Skip to main content
3 of 3
k's versus n's
Paul McKenney
  • 1.3k
  • 9
  • 14

A "yes" answer to your question is equivalent to the statement "there exists a large set of natural numbers that admits no arithmetic progression of length three." I'm submitting the proof of this equivalence as an answer since I don't expect to see an actual answer unless it shows up in Annals too :)

So, to the proof. You've already noted the forward direction.

For the backward direction, suppose $A$ is a large set of natural numbers with no arithmetic progression of length three, $k\in\mathbb{N}$, and $s\subseteq k$ has no arithmetic progressions of length three. We'll show that there's a large set $B$ such that $B\cap k = s$, and $B$ has no arithmetic progressions of length three. This is clearly sufficient.

The "naiive" choice for $B$ is the set $s\cup (A\setminus k)$, which is large and has no length-3 AP's which are entirely below $n$ or entirely above $k$; but of course there may be an AP of length 3 which crosses $k$. There are only finitely-many APs of length 3 with two points in $s$, so we may remove the corresponding points from $A$ (if they exist) and still have a large set. So we'll assume that we've already done this, i.e. $A\cap k = \emptyset$, and there are no APs of length 3 with two points in $s$.

If the AP has two points in $A$, then it's more complicated. Suppose $i\in s$. Let $B_i$ be the set you get from $A$ by removing the possible third points, i.e. $$ B_i = A\setminus\{2n - i \;|\; n\in A\}$$ We'll show that $B_i$ is still large. Let $N$ be a large natural number. Note that $$ \sum_{n\in B_i\cap N} \frac{1}{n} \ge \sum_{n\in A\cap N} \frac{1}{n} - \frac{1}{2n-i}$$ If $n$ is large enough, say $n > 3i$, then $\frac{1}{2n - i} < \frac{2}{3n}$, so if $A\cap 3k = \emptyset$ then the above sum is at least $$ \sum_{n\in A\cap N} \frac{1}{3n} = \frac{1}{3} \sum_{n\in A\cap N} \frac{1}{n} $$ Hence, as the sums on the right go to $\infty$ as $N\to\infty$, it follows that $B_i$ is large.

Applying this process multiple times, once for each member of $s$, we eventually get a large set $B$ such that $s\cup B$ has no AP's of length 3.

Paul McKenney
  • 1.3k
  • 9
  • 14