# Arithmetic progressions in finitely generated groups

Suppose $\Gamma$ is a finitely generated countable discrete torsion free group with a generating set $S$. Let $l$ be the word length function given by $S$. Let $F_n=\{s\in\Gamma| l(s)\leq n\}$.

Assume that $\Lambda$ is a subset of $\Gamma$ such that $$\limsup_{n\to\infty} \frac{|\Lambda\cap F_n|}{|F_n|}>0.$$

Question: For every positive integer $k$, do there exist $b$ and $a$ in $\Gamma$ such that $\{b^{j}a\}_{j=0}^{k-1}\subseteq\Lambda$?

When $\{b^{j}a\}_{j=0}^{k-1}$has $k$ distinct elements, we call it a left arithmetic progression of length $k$ in $\Gamma$.

Remark: One would avoid the trivial case that $b=e_\Gamma$. In fact, let $\Gamma=\mathbb{Z}$ with $S=\{1\}$, the answer to the above question is affirmative by Szemeredi's theorem, which says that a subset of $\mathbb{Z}$ with positive upper density contains arbitrarily long arithmetic progressions.

• You need to exclude some more trivial counterexamples (and thus maybe at least assume that $\Lambda$ consists of elements of infinite order). Otherwise, take $\Gamma$ the infinite dihedral group, and $\Lambda$ its set of elements of order 2, which is a coset of a subgroup of index 2. – YCor Apr 9 '17 at 9:42
• Should not $b^{jn}$ be simply $b^j$? And should we add that $b\ne 1$? – Fedor Petrov Apr 9 '17 at 10:52
• I recently saw a talk by Furstenberg where he defines an appropriate notion of upper density for which such a theorem holds. Basically you choose a random walk and positive upper density means your walk asymptomatically hits your set enough. This depends on the walk but he gets progressions if you have an upper density of this sort for an appropriate walk. – Benjamin Steinberg Apr 9 '17 at 13:58
• Actually, if there exists $b$ such that $\lim_{n\to\infty}\frac{|bF_n\Delta F_n|}{|F_n|}=0$ for a sequence of finite subsets $\{F_n\}$ in $\Gamma$, then for any subset $\Lambda$ of $\Gamma$ satisfying that $\limsup_{n\to\infty} \frac{|\Lambda\cap F_n|}{|F_n|}>0$ contains $\{b^{jn}a\}_{j=0}^{k-1}$ for every $k>0$. I just post an arxiv paper named ''Arithmetic progressions in discrete groups'' to prove this. I don't know whether there is a connection between this result and the one you mentioned. – Huichi Huang Apr 9 '17 at 14:57
• What about $\mathbf{Z}^2$? – YCor Apr 9 '17 at 15:24

Let $\Gamma$ be a free group over the alphabet $X$, $|X|\geq 2$, and put $S=X\cup X^{-1}$. Pick an increasing sequence of integers $n_i$, and put $\Lambda=\{g\in\Gamma|\exists i:\ell(g)=n_i\}$. Under some mild restrictions on the sequence $n_i$ we have that any arithmetic progression of length $\geq 3$ consists of elements of equal length. But then $a$, $ba$ and $b^2a$ have equal length. Hence $\ell(b)$ is even, and we decompose the reduced words for $a$ and $b$ as $a=vw$, $b=uv^{-1}$, where $\ell(u)=\ell(v)$, that is, $ba=uw$. In the same way $\ell(b^2a)=\ell(ba)$ implies $v=u$, thus $b=uu^{-1}=e$. But arithmetic progressions are assumed to consist of different elements, so this choice of $b$ is excluded. On the other hand the set of elements of length $=n_i$ is of positive density among all elements of length $\leq n_i$, so we obtain a set of positive upper density without arithmetic progressions of length 3.
• In this case, even $\lim\frac{|\Lambda\cap F_{n_i}|}{|F_{n_i}|}=1$ since $O|F_{n_i}|=O|\{g\in\Gamma| l(g)=n_i\}|$. I doubt the answer is affirmative for group of polynomial growth. – Huichi Huang Apr 9 '17 at 14:31
• "mild restriction" is not really mild? You seem to mean that in the free group triples $(\ell(a),\ell(ba),\ell(b^2a))$ are not arbitrary, maybe you need to elaborate, I haven't been able to check this (on the other hand I can find relevant constraints on 4-tuples $(c_0,c_1,c_2,c_3)=(\ell(a),\ell(ba),\ell(b^2a),\ell(b^3a))$), namely that if non-constant, it satisfies that there exists two distinct pairs $(i,j)$, $(k,m)$ such that $c_i-c_j$ and $c_k-c_m$ are equal and nonzero. So any sequence $(n_i)$ whose image does not contain such a pair of pairs works (e.g., $n_i=2^i$ for $i\ge 0$) – YCor Apr 9 '17 at 15:42
• Assume that $n_i=2^i$ would be enough. @YCor, as you comment, the answer of this question for groups of polynomial growth is affirmative. – Huichi Huang Apr 9 '17 at 16:12
Your definition of "arithmetic progression" in a group is wrong. It should be as follows. Let $w(x,a_1,...,a_n)$ be a word. Then an arithmetic progression is the sequence $w(a_1,a_1,...,a_n), ..., w(a_n,a_1,...,a_n)$ for some a_1,...,a_n in the group (see https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem). In this formulation the result is true as proved by Furstenberg and Katznelson (it was a \\$100 problem from a list by Ron Graham, as far as I remember, http://www.math.ucsd.edu/~ronspubs/08_06_old_and_new.pdf).