show/hide this revision's text 3 tagging
show/hide this revision's text 2 added 12 characters in body

Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, for any $k\ge 3$, $r_k(N)/N\to 0$ as $N\to\infty$.

It follows that the same is true for any finite pattern. i.e. if $A\subset\mathbb{N}$ is a finite set, then, if $r_A(N)$ is the largest cardinality of a subset of $[N]$ which does not contain a set of the form $t+n.A$, we again have $r_A(N)/N\to 0$ as $N\to\infty$. This is obvious since $A\subset [\max A]$.

For $k=3$, Tom Sanders has recently obtained substantially improved the nearly sharp best known upper bound for $r_k(N)$, namely $O(N/\log^{1-o(1)}N)$. I believe for $k=4$ the current "world-record" is due to Green and Tao and for $k>4$ to Gowers (corrections welcome).

My question is about quantitative bounds for $r_A(N)$. Obviously, $r_A(N)\le r_{\max A}(N)$, but if $A$ is sparse this is likely to be far from optimal. Can one do better? Are there any quantitative results for more general sets $A$?

In particular, is it true that $r_A(N)$ ``behaves like'' $r_{|A|}(N)$?

To be concrete, what type of bounds can one get for $r_A(N)$ when $A=\{1,2,m\}$? Will they be more like $r_3(N)$, or more like $r_m(N)$ (or something strictly in between)?

show/hide this revision's text 1

Bounds on the size of sets not containing a given finite pattern

Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, for any $k\ge 3$, $r_k(N)/N\to 0$ as $N\to\infty$.

It follows that the same is true for any finite pattern. i.e. if $A\subset\mathbb{N}$ is a finite set, then, if $r_A(N)$ is the largest cardinality of a subset of $[N]$ which does not contain a set of the form $t+n.A$, we again have $r_A(N)/N\to 0$ as $N\to\infty$. This is obvious since $A\subset [\max A]$.

For $k=3$, Tom Sanders has recently obtained the nearly sharp upper bound for $r_k(N)$, namely $O(N/\log^{1-o(1)}N)$. I believe for $k=4$ the current "world-record" is due to Green and Tao and for $k>4$ to Gowers (corrections welcome).

My question is about quantitative bounds for $r_A(N)$. Obviously, $r_A(N)\le r_{\max A}(N)$, but if $A$ is sparse this is likely to be far from optimal. Can one do better? Are there any quantitative results for more general sets $A$?

In particular, is it true that $r_A(N)$ ``behaves like'' $r_{|A|}(N)$?

To be concrete, what type of bounds can one get for $r_A(N)$ when $A=\{1,2,m\}$? Will they be more like $r_3(N)$, or more like $r_m(N)$ (or something strictly in between)?