7
$\begingroup$

Let $G$ be a countable finitely generated group, with word metric $d_S$ induced by some generating set $S$. Let $B_r$ be the ball of radius $r$ around the identity under $d_S$.

We say that $A \subset G$ has positive upper density if $\limsup_{n\to\infty} \frac{|A\cap B_n|}{|B_n|}>0$ for some, hence any word metric $d_S$.

Question: For any $A\subset G$ with positive upper density, does it hold that there exists some $a \in A$, and nonzero $g \in G$ such that $a, a + g, a + 2g$ are in $A$?

Edit: The original question asked about abelian groups, which is answered in the positive by Roth’s theorem as stated by Sean Eberhard in the comments.

$\endgroup$
8
  • 6
    $\begingroup$ Since $G$ is abelian and finitely generated, $G \cong \mathbf{Z}^r \times T$ for some finite group $T$. By passing to an appropriate coset you can reduce to $G = \mathbf{Z}^r$, so this reduces to Roth's theorem in a usual form. The question is more interesting if you drop the word abelian. $\endgroup$ Apr 21, 2021 at 15:47
  • 1
    $\begingroup$ Note that a counterexample is easy for monoids. Specifically, let $G$ be a free monoid with three generators $x,y,z$, and let $A$ be the set of all elements of $G$ that do not end with any word of the form $w^2$ for nontrivial $w\in G$. Observe that only $1/3$ of words end in $xx$, $yy$, or $zz$, only $1/9$ of words end in $w^2$ for $|w|=2$, and so on, and since $1/3 + 1/9 + \cdots < 1$ the elements of $A$ have positive density in $G$. $\endgroup$
    – Jim Belk
    Apr 24, 2021 at 10:39
  • 5
    $\begingroup$ Is it that clear that positive upper density is independent of the choice of finite generating subset? $\endgroup$
    – YCor
    Jun 17, 2021 at 12:04
  • 1
    $\begingroup$ @Matk Sapir $ab^2$. $\endgroup$
    – Nate River
    Jun 17, 2021 at 20:46
  • 1
    $\begingroup$ @NateRiver sorry but I'm aware of bilipschitzness but then? if $B_n,B'_n$ is the $n$-ball with respect to two metrics, $B_n\cap B'_n$ can be negligible in $B_n$ and/or $B'_n$. Just take $G=F_2$, $B_n$ the standard $n$-ball, and $B'_n$ the standard $2n$-ball, which equals the $n$-ball for $B'_1=B_2$. $\endgroup$
    – YCor
    Jun 17, 2021 at 21:40

1 Answer 1

3
$\begingroup$

I hope this might be of interest, I'll consider a simpler problem and present a couple $(G,A)$ where one can't find a progression of length four: $a, ag, ag^2, ag^3$.

Example. Let $G$ be the free group $F_2$ on $2$ generators with generating set $x_1, x_1^{-1}, x_2, x_2^{-1}$. Take $A$ as the union of all words of length $\varphi(n)=4^n$ for $n\ge 2$. It is easy to see that $A$ has positive upper density. However one can not find elements $a, ag, ag^2,ag^3\in A$ with $g\ne 1$. The reason here is the following.

Observation. Fix $a$ and $g$ and consider the sequence of words $\ldots, ag^{-1},a,ag,\ldots, ag^n,\ldots$. Let $l(n)$ be equal to the length of $ag^n$. Then $l(n)$ is given by formula $d|n-x|+b$, where $d>0$, $x$ a fixed (half integer) number $b\ge 0$.

I don't want to write a complete proof of this observation. But the idea is that the multiplication by $g$ is acting by isometry of the Cayley graph of $F_2$ and it sends a unique geodesic (in the graph) to itself, and points $ag^{-n}$ are on the same distance to this geodesic (maybe there is a more obvious reasoning).

From this observation it is very easy to deduce the claim. Consider for example the case when $l(a)=l(ag)<l(ag^2)<l(ag^3)$. Suppose by contradiction these elements are all in $A$. In this case distance in the Cayley graph between $a$ and $ag$ is at most $2\cdot 4^n$ for some $n$. But the distance between $ag$ and $ag^2$ is at least $3\cdot 4^{n}$, a contradiction (the distance should be the same). Other cases are similar.

$\endgroup$
2
  • $\begingroup$ Minor remark: both a and b have multiple meanings in your answer. Actually, I think you never use the names of the generators. $\endgroup$ Jun 17, 2021 at 21:05
  • $\begingroup$ Thanks Stefan, you are right, I'll rename them. I implicitly use them when I say that the density is positive. In fact, after thinking a bit about the remark of Ycor I am not sure that positivity of such density is independent of the choice of generators. Maybe it is not in case when the growth of the group is exponential. $\endgroup$
    – aglearner
    Jun 17, 2021 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.