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

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.

share|cite|improve this question
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. – Marcin Kotowski Mar 4 '13 at 17:25
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. – Gil Kalai Mar 6 '13 at 7:27
What would working over $\mathbb Z_p$ mean in this instance? – Will Sawin Aug 25 '13 at 17:22

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.

share|cite|improve this answer
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. – Will Sawin Aug 25 '13 at 17:18
Nice seeing you here! – Andrés E. Caicedo Aug 25 '13 at 17:32
Andres, thanks! – Jacob Fox Aug 26 '13 at 1:37
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. – Jacob Fox Aug 26 '13 at 1:38

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.

share|cite|improve this answer
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. – Marcin Kotowski Mar 4 '13 at 16:23
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:…) – Joel Moreira Mar 4 '13 at 18:48
$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}$. – Will Sawin Aug 25 '13 at 16:55

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.