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

Christian Elsholtz, Péter Pál Pach

Published 2019-03-19Version 1

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) \geq 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 \vert G \vert^{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|\leq 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) \geq (85-o(1))^n$. For $r_3(\mathbb{Z}_4^n)$ we determine the exact values, when $n \leq 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 \leq 4$, e.g. $r_4(\mathbb{Z}_4^4)=128$.