7
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – YCor
    Commented Apr 9, 2017 at 9:42
  • $\begingroup$ Should not $b^{jn}$ be simply $b^j$? And should we add that $b\ne 1$? $\endgroup$
    – Fedor Petrov
    Commented Apr 9, 2017 at 10:52
  • $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Commented Apr 9, 2017 at 13:58
  • $\begingroup$ 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. $\endgroup$
    – Huichi Huang
    Commented Apr 9, 2017 at 14:57
  • $\begingroup$ What about $\mathbf{Z}^2$? $\endgroup$
    – YCor
    Commented Apr 9, 2017 at 15:24

2 Answers 2

Reset to default
2
$\begingroup$

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.

I would assume that a similar argument works for any group of exponential word growth.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Huichi Huang
    Commented Apr 9, 2017 at 14:31
  • $\begingroup$ "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$) $\endgroup$
    – YCor
    Commented Apr 9, 2017 at 15:42
  • $\begingroup$ 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. $\endgroup$
    – Huichi Huang
    Commented Apr 9, 2017 at 16:12
2
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure we can say that a definition is wrong, but certainly one can argue that in a wider context some more elaborate definition fits better. $\endgroup$
    – YCor
    Commented Apr 10, 2017 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .