3
$\begingroup$

I am trying to find some weak bounds on the largest subset of a set, such that the subset has the property that it contains no three elements in arithmetic progression. The elements of the original set are in an arithmetic progression of length 1, i.e. $S=\{n,n+1,...,n+k-1\}$.

For example, if $S=\{5,6,7,8,9,10\}$ then one subset satisfying the property I stated above is $\{5,7,8,10\}$ since no three elements of this set are in arithmetic progression. So we immediately know that a bound for this set is $\ge 4$.

I am trying to find a weak bound in general for the set $\{n,n+1,...,n+k-1\}$. In other words, what roughly is the largest possible subset of this set such that no three elements of this subset are in arithmetic progression.

$\endgroup$
  • 1
    $\begingroup$ Note that this is the same as asking for the largest subset $S\subseteq \{1, 2, ..., k\}$ that contains no 3-term AP. It may be easier to think about if you remove the shift. $\endgroup$ – TravisJ Apr 25 '15 at 0:24
3
$\begingroup$

Roth's Theorem will give you an upper bound: http://wiki.math.toronto.edu/TorontoMathWiki/images/2/2d/Expo_paper.pdf In that paper it is Theorem 1.3 (bottom of first page). It says:

Theorem (Roth, 1953) For any $\delta>0$ if $k>\exp(\exp(c\delta^{-1}))$ (for some absolute constant $c>0$) and $A\subseteq \{1, 2, 3, ..., k\}$ and $|A|\geq \delta k$ then $A$ contains a non-trivial 3-term AP.

Later, there was a nice proof of Roth's theorem by Gowers. The statement is also in the above paper (and proof). It gives an easier to interpret upperbound.

Theorem (Gowers, 2001) There exists a positive constant $c_{r}$ and an absolute constant $C$ such that any $A\subseteq \{1, 2, 3, ..., k\}$ with size $|A|>Ck/(\log\log(k))^{c_{r}}$ contains a non-trivial $r$-term AP.

In the same paper (right at the end) they have a section about generating large sets with no 3-AP. It is Behrend's theorem from 1946.

$\endgroup$
3
$\begingroup$

As for an upper bound, we get into work related to Erdos' conjecture on arithmetic progressions (which has not been proven even in the case of arithmetic progression of length 3). I believe the strongest known result is Sander's proof that, if $f(k)$ is the size of the largest subset of a $k$-element progression free from arithmetic progression of length $3$, then $$f(k)= O\left(\frac{k (\log \log k)^5}{\log k}\right).$$ For more general lengths of arithmetic progression, we have the Szemerédi theorem, which provides a very weak bound (but suffices to show that any subset of $\mathbb N$ free of arithmetic progressions of length $c$ has natural density $0$).

$\endgroup$
2
$\begingroup$

The bound should depend only on $k$, not at all on $n$.

It suffices to find a lower bound on the size of the largest subset of the first $k$ positive integers with no arithmetic progression of length $3$. In other words, as user TravisJ explains it, we want the largest subset of $\{1,2,\dots, k\}$.

We can achieve a very weak but easy lower bound by simply taking all of the powers of $2$ less than $k$. This works because there are no arithmetic progressions in the list of powers of $2$.

This gives a lower bound of $$\left\lceil\log_2 k\right\rceil$$

This is the ceiling function of the binary logarithm of $k$. Alternatively, it is the number of digits in the binary representation of $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.