Suppose $A \subseteq \{1,\dots,n\}$ does not contain any arithmetic progressions of length $k+1$. What is the largest number of $k$-term arithmetic progressions that $A$ can have? (one may also wish to put some lower or upper on the size of $A$) We can work over $\mathbb{Z}_p$ if it makes the answer any easier. The "degenerate" case $k=2$ asks for the largest size of the set without arithmetic progressions and it is known that there exist $A$'s with this property of almost linear size.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Nb. for graphs (i.e. asking for the maximal number of $l$-cliques a graph can contain before it contains a $k$-clique) there are explicit bounds. $\endgroup$– Marcin KotowskiCommented Mar 4, 2013 at 17:25
-
2$\begingroup$ Dear Marcin This is nice and natural question, but I doubt if much is known. Did you look at the number of k-term APs in Berend-type examples for sets without (k+1)-terms arthmetic progressions? This looks like the best shot for an answer presently. $\endgroup$– Gil KalaiCommented Mar 6, 2013 at 7:27
-
$\begingroup$ What would working over $\mathbb Z_p$ mean in this instance? $\endgroup$– Will SawinCommented Aug 25, 2013 at 17:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Let $B\geq2k$ and let $$A=\left\{\sum_{i=0}^na_iB^i:n=0,1,...;a_i=0,1,...,k-1\right\}$$ It's not hard to show that $A$ has no $k+1$-long arithmetic progression. Using the density Hales-Jewett theorem we get that any subset $B\subset A$ with positive relative density has a $k$-long arithmetic progression.
I don't know the best bounds on the density Hales-Jewett, but I think there are some from the polymath proof, so in principle this would give an answer to your question.
-
$\begingroup$ I upvote the answer, but the conclusion "any subset B⊂A with positive relative density has a k-long arithmetic progression." seems too weak to say anything about the number of such k-progressions in the whole set. $\endgroup$ Commented Mar 4, 2013 at 16:23
-
$\begingroup$ I think one can in principle use a Varnavides-type argument, but I am not sure how that would work out exactly (I am using the term "Varnavides-type" from a section on this blog post: terrytao.wordpress.com/2008/02/10/…) $\endgroup$ Commented Mar 4, 2013 at 18:48
-
1$\begingroup$ $A$ has at least $2^{n+1}-1$ arithmetic progressions and occupies an interval of length $(2k)^n$, so if $N$ is the length of the interval, this gives a lower bound of about $N^{\log 2/\log 2k}$. $\endgroup$ Commented Aug 25, 2013 at 16:55
$\begingroup$
$\endgroup$
3
I assume that $k$ as fixed. The answer to this problem is closely related to the maximum density $p=p_{k+1}(n)=r_{k+1}(n)/n$ of a subset of $\{1,\ldots,n\}$ without a $(k+1)$-term arithmetic progression.
Indeed, let $S \subset \{1,\ldots,n\}$ be a set of cardinality $r_{k+1}(n)$ without a $(k+1)$-term arithmetic progression. Now construct a random subset $A \subset [4kn]$ as follows. The set $A$ consists of the union of $k$ random translations $S_i$ of $S$, where $S_i=S+d_i$ and $d_i$ for $1 \leq i \leq k$ is picked uniformly at random from the interval $\{4(i-1)n,4(i-1)n+1,\ldots,4(i-1)n+2n-1\}$ of $2n$ integers. It is easy to check that $A$ cannot contain a $(k+1)$-term arithmetic progression. It is also not difficult to check that the expected number of $k$-term arithmetic progressions in $A$ is at least $(cp)^k n^2$ where $c>0$ is an absolute constant. Hence, letting $N=4kn$ and changing $c$ slightly, there is a subset of $[N]$ with no $(k+1)$-term arithmetic progression but the number of $k$-term arithmetic progressions is at least $(cp)^k N^2$.
In the other direction, any subset $B \subset \{1,\ldots,N\}$ with no $(k+1)$-term arithmetic progression has density at most $2p$. A $k$-term arithmetic progression is determined by its first two terms. The number of possible first two terms in $B$ is at most ${2pN \choose 2} < 2p^2N^2$. Hence, there are at most $2p^2N^2$ total $k$-term arithmetic progressions in $B$.
In summary, the number of $k$-term arithmetic progression in $\{1,\ldots,N\}$ which can be in a set with no $(k+1)$-term arithmetic progression is between $(cp)^k N^2$ and $2p^2N^2$. However, there is still a large gap between Rankin's lower bound and Gowers' upper bound on $p=r_{k+1}(n)/n$. Hence, the bound on this problem is closely tied to quantitative bounds for Szemerédi's theorem.
-
$\begingroup$ If $f(k,N)$ is the maximum number of $k$-term progressions in subsets of $\{1,\dots,N\}$ with no $k+1$-term progressions, we have: $$ N^2 c^k e^{-k\left(\log_C N\right)^{1/k}} \leq f(k,N) \leq N^2 \frac{2}{k-1} (\log_2 \log_2 N) ^{ - 2^{-2^{k+10}}} $$ This lower bound improves on the lower bound which I noted follows from Joel Moreira's construction. $\endgroup$ Commented Aug 25, 2013 at 17:18
-
-
$\begingroup$ I should add that the upper bound can be improved further to $o(p^2N^2)$, where the $o$ term can be explicitly computed. However, the proof is a little more involved and requires using the following lemma: every set $B$ of integers with no $(k+1)$-term arithmetic progression (again $k$ is fixed) has $o(|B|^2)$ $3$-term arithmetic progressions. The proof uses the Balog-Szemerédi-Gowers theorem, Freiman's theorem, and Szemerédi's theorem. $\endgroup$ Commented Aug 26, 2013 at 1:38