Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow with N. But how fast? For instance, are there arbitrarily large N admitting a subset of [1..N] with no three-term AP and no gap longer than $N^\epsilon$? Does the subset constructed by Behrend have this property, or might it have unexpectedly long gaps?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ If Behrend's set had large gaps (that is a gap much larger than the typical gap suggested by the density) then one of the "sides" of the set excluding the gap would have increased density and still not contain three-term AP's. It seems that one should be able to iterate this observation to obtain either (a) a set more dense than Behrend without 3-term APs, or (b) a set of similar density to Behrend where the maximal gap is near the expected size. $\endgroup$– Mark LewkoCommented Oct 29, 2015 at 4:38
-
1$\begingroup$ To be precise, and to eliminate trivial examples such as a set containing just a single point, we should include the wrap around gap. Say $l,s\in S$ are the largest and smallest elements in $S$ respectively, then include the gap $N-l+s$. $\endgroup$– Eric NaslundCommented Oct 29, 2015 at 13:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
For the sake of having a reference, Ron Graham shows in "On the growth of a van der Waerden-like function" that for a fixed $k$, there exists a 3AP-free subset of $\{1,2,\dots,N\}$ with gaps bounded by $k$ and $N\geq k^{c\log k}$, where $c$ is some absolute constant that doesn't depend on $k$. Therefore you can get gaps to be even bounded by $\exp(c\sqrt{\log N})$.
answered Oct 29, 2015 at 5:53
-
2$\begingroup$ And you can't do better than this without improving Behrend's construction since if $g(N)$ is the upper bound for the size of the gap, then we have an arithmetic progression free set of size $\geq N/g(N)$ $\endgroup$ Commented Oct 29, 2015 at 13:43