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
    I would have thought that "translates" refers to the same thing with "$a$ varies" instead of "$b$ varies". These are more like scaled versions. Are you sure it's $b$ and not $a$?2012-05-11
  • 0
    The term "translates" made things unclear, yes. I edited; now things should be correct.2012-05-11
  • 0
    What does $k\ge O(N/r)$ mean? Usually $O$ is an upper bound (see e.g. [here](http://en.wikipedia.org/wiki/Big_O_notation)) and for instance the constant zero function is in $O(N/r)$, so that condition doesn't really tell us anything. Do you mean $k(N,r)\in\Theta(N/r)$? If so, that can't be true; all the $k$ values of $a+b$ are different, and if $k(N,r)\in\Theta(N/r)$, then that's already asymptotically more than $N^{1-\epsilon(r)}$ elements in the set.2012-05-11
  • 0
    @joriki: Perhaps what is meant by ratios is the ratios $\ell_1/\ell_2$ of terms $\ell_1,\ell_2\in X$?2012-05-11
  • 0
    I abused the big $O$ notation; edited again2012-05-11
  • 0
    @Anna: As far as I can tell, what you've written now is just $k(N,r)\in\Theta(N/r)$, as I suspected. Don't you have any reaction to my counterargument?2012-05-11
  • 0
    Well, your new $a+b$ can be some $a'+l b'$ for some other $a'$ and $b'$ used before; so the problem basically asks for an example when this happens a lot2012-05-11
  • 0
    @Anna: I see. It wasn't clear to me from the question that $a$ can vary.2012-05-13
  • 0
    @Anna : Just what "is of size at most $N^{1-\varepsilon(r)}$ ? The union of the progressions? Each progression individually?2012-05-13
  • 0
    $X$ should be of size at most $N^{1-\epsilon(r)}$.2012-05-13

0 Answers 0