9
$\begingroup$

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.

$\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$ 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 Kalai
    Mar 6, 2013 at 7:27
  • $\begingroup$ What would working over $\mathbb Z_p$ mean in this instance? $\endgroup$
    – Will Sawin
    Aug 25, 2013 at 17:22

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\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$ 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$ 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$
    – Will Sawin
    Aug 25, 2013 at 16:55
2
$\begingroup$

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.

$\endgroup$
3
  • $\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$
    – Will Sawin
    Aug 25, 2013 at 17:18
  • $\begingroup$ Nice seeing you here! $\endgroup$ Aug 25, 2013 at 17:32
  • $\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$
    – Jacob Fox
    Aug 26, 2013 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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