MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 substantially improved the 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)?

share|cite|improve this question
up vote 4 down vote accepted

Your question is quite broad, I won't be able to answer everything.

Let me start by answering your most concrete question regarding the pattern $ \{1,2,m\} $. I prefer to use $\{0,1,k\}$, which is equivalent.

Recall that the existence of a three term arithmetic progression can be recast as asking for a soution to $x-2y+z=0$ with distinct $x,y,z$ in the subset. Similarly, for the set you ask for one can recast the question whether there is such a pattern into the question whether there is a solution to the equation $$(k-1)x - k y + z =0$$ with distinct $ x, y, z$ in the subset. (Note that the sum of the coefficients is $0$.)

By contrast, one cannot encode the existence of a $k$-term arithmetic progressions, for $k>3$, by a single equation of the above form. Instead, one needs to consider a system of linear equations.

For all I know this is the crucial difference between $3$-term and $k$-term, with larger $k$, arithmetic progressions; at least, if a Fourier-analytic approached is used (as in the papers you mentioned); other approaches often yield only much weaker bounds or no explcit bounds at all.

So, the problem for $\{1,2,m\}$ is 'close' to $3$-term arithemtic progressions.

When comparing problems of this form a way to compare them is to compare the encoding of the 'pattern' as a solution to a (system) of linear equations. Roughly, if you can encode it with one equation (and the sum of the coefficients is $0$) then it is close to $3$-term arithemtic progressions if not, then not. In particualr, the number of variables in the equation is not the main problem (in some sence, it even helps to have more variables; however to guarantee that the variables all have distinct values can then become more of a problem), it is the number of equations.

See for example this paper by Liu and Spencer dealing with arbitrary linear equations (subject to some technical conditions) in finite abelian groups; but the integer problem is basically the problem for cyclic groups. (There is also a second part of this paper.)

So, it really depends on the precise form of the pattern how hard the problem is; as you suspected its maximum is not a very good measure.

To compare different systems of linear equations with respect to problems of this form one needs to compare the right parameters. I am not the right person to explain this in detail; however, for example, the recent paper of Gowers and Wolf 'The true complexity of a system of linear equations' should give an impression of this.

And, there is a large variety of (recent) work related to this circle of ideas, also studying higher dimensional analogues or 'polynomial progressions' (e.g., Bergelson and Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems).

A final remark: as far as I know, the fact that the bounds for $r_3$ and $r_k$ are so relatively far appart might well not be due to the true behavior of these functions, but due to the fact that in one case the bound was provable and in the other case it is not (yet) provable. For example, it is a conjecture of Erdős that for $S$ a subset of the natural numbers the divergence of $\sum_{s\in S}1/s$ implies the existence of $k$ arithmetic progression,for any $k$, in $S$, which roughly translates into a bound of $N/\log N$ for $r_k$ for any $k$.

Moreover, while the recent progress for $r_3$ that you mentioned is impressive, it is not (or at least not known to be) close to optimal; however, it is close to establishing the above mentioned conjecture for $k=3$. The best known lower bound (Behrend recently improved by Elkin) is roughly only of the form $N \exp(- c \sqrt{N})$ for a $c > 0$, which is smaller than $N/ (\log N)^D$ for any $D$; and as far as I know some people believe this might be closer to the truth than the upper bound.

Thus, if you ask about the size of your fucntions it is difficult to say close to which of the classical functions the functions you mentioned are, as even the classical ones are not completely understood (I believe not even conjecturally). However, how difficult it would be to prove bounds for your functions can be judged to some extent by what I said in the middle.

Much more could be said, but I have to stop.

share|cite|improve this answer
Sorry to comment on my own post, but I do not want to bump it three times in an hour and noticed something I ought to clarify: while it is true that the integer case is essentially the cyclic case, in the Liu and Spencer paper the rank and not the exponent of the group tends to infinity (somehow in the spirit of 'finite field models'). The results there are thus, contrary to what one might infer from what I wrote, not directly applicable to the integer case; yet the paper demonstrates the phenomenon I describe. – user9072 Mar 23 '11 at 21:27
Thanks for the comprehensive answer. From what you say, it would be a good exercise in understanding the proofs in the $k=3$ case to extend them to set of the form $\\{0,1,m\\}$. I've updated the statement to reflect your correction on Sanders' bound. – Pablo Shmerkin Mar 24 '11 at 1:51
I'm not familiar enough with the details of the proof to judge how difficult this would be in detail. Yet, L&S result shows that in the finite field setting, so subsets of $F^N$ for some fixed finite field $F$, which heuristically should predict what happens in the cyclic/integer case, the bounds were (essentially) the same; so in princ. it should work somehow. [The 'same' for ff ignores some very recent (weeks) improvement for 3AP in the ff context, but this is more recent then the cyclic result, and there are efforts to now further improve the cyclic result, details on Gowers's blog]. – user9072 Mar 24 '11 at 2:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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