Caps and progression-free sets in ${\mathbb{Z}}_m^n$

Abstract

We study progression-free sets in the abelian groups $G=({\mathbb{Z}}_m^n,+)$. Let $r_k({\mathbb{Z}}_m^n)$ denote the maximal size of a set $S\subset {\mathbb{Z}}_m^n$ that does not contain a proper arithmetic progression of length $k$. We give lower bound constructions, which e.g. include that $r_3({\mathbb{Z}}_m^n)\ge C_m\frac{((m+2)/2{)}^n}{\sqrt{n}}$, when $m$ is even. When $m=4$ this is of order at least $3^n/\sqrt{n}\gg |G{|}^{0.7924}$. Moreover, if the progression-free set $S\subset {\mathbb{Z}}_4^n$ satisfies a technical condition, which dominates the problem at least in low dimension, then $|S|\le 3^n$ holds. We present a number of new methods which cover lower bounds for several infinite families of parameters $m,k,n$, which includes for example: $r_6({\mathbb{Z}}_{125}^n)\ge (85-o(1){)}^n$. For $r_3({\mathbb{Z}}_4^n)$ we determine the exact values, when $n\le 5$, e.g. $r_3({\mathbb{Z}}_4^5)=124$, and for $r_4({\mathbb{Z}}_4^n)$ we determine the exact values, when $n\le 4$, e.g. $r_4({\mathbb{Z}}_4^4)=128$.