5
$\begingroup$

I would really appreciate some help with the following problem.

It resembles Van der Waerden a lot but I don't know how to proceed. I was told an averaging argument might do the trick but I can't see it.

Let $N, r$ be positive integers. Then, there exists a subset $X$ of $\left\{1,2,\ldots,N\right\}$ which contains arithmetic progression of length $r$ with at least $k \geq N/r \cdot \text{some constant}$ ratios (more precisely, it contains arithmetic progressions of length $r$ of the form $a,\ a+b,\ \ldots,\ a+rb$, where $b$ varies over $k$ values), and which is of size at most $N^{1-\epsilon(r)}$.

Thanks in advance!

  • 0
    $X$ should be of size at most $N^{1-\epsilon(r)}$.2012-05-13

0 Answers 0