Bounds on the size of sets not containing a given finite pattern - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T17:17:58Z http://mathoverflow.net/feeds/question/59339 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59339/bounds-on-the-size-of-sets-not-containing-a-given-finite-pattern Bounds on the size of sets not containing a given finite pattern Pablo Shmerkin 2011-03-23T18:32:54Z 2011-07-29T06:20:37Z <p>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$. </p> <p>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]$.</p> <p>For $k=3$, <a href="http://arxiv.org/abs/1011.0104" rel="nofollow">Tom Sanders</a> 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 <a href="http://arxiv.org/abs/math/0610604" rel="nofollow">Green and Tao</a> and for $k>4$ to <a href="http://www.ams.org/mathscinet-getitem?mr=1844079" rel="nofollow">Gowers</a> (corrections welcome).</p> <p>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$?</p> <p>In particular, is it true that $r_A(N)$ behaves like'' $r_{|A|}(N)$?</p> <p>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)?</p> http://mathoverflow.net/questions/59339/bounds-on-the-size-of-sets-not-containing-a-given-finite-pattern/59345#59345 Answer by quid for Bounds on the size of sets not containing a given finite pattern quid 2011-03-23T20:10:08Z 2011-03-23T20:45:59Z <p>Your question is quite broad, I won't be able to answer everything.</p> <p>Let me start by answering your most concrete question regarding the pattern <code>$\{1,2,m\}$</code>. I prefer to use <code>$\{0,1,k\}$</code>, which is equivalent.</p> <p>Recall that the existence of a three term arithmetic progression can be recast as asking for a soution to <code>$x-2y+z=0$</code> with distinct <code>$x,y,z$</code> 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 <code>$$(k-1)x - k y + z =0$$</code> with distinct $x, y, z$ in the subset. (Note that the sum of the coefficients is $0$.)</p> <p>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.</p> <p>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.</p> <p>So, the problem for ${1,2,m}$ is 'close' to $3$-term arithemtic progressions. </p> <p>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 <em>the number of equations</em>. </p> <p>See for example this paper by Liu and Spencer <a href="http://www.math.ksu.edu/~cvs/liu_spencer-roth_group.pdf" rel="nofollow">http://www.math.ksu.edu/~cvs/liu_spencer-roth_group.pdf</a> 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.)</p> <p>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. </p> <hr> <p>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.</p> <p>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).</p> <hr> <p>A final remark: as far as I know, the fact that the bounds for <code>$r_3$</code> and <code>$r_k$</code> 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 <code>$r_k$</code> for any $k$.</p> <p>Moreover, while the recent progress for <code>$r_3$</code> 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 <code>$N/ (\log N)^D$</code> for any $D$; and as far as I know some people believe this might be closer to the truth than the upper bound.</p> <p>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. </p> <p>Much more could be said, but I have to stop.</p>