Suppose $G$ is a finitely generated discrete group and that there is a subset $E$ of $G$ such that if $\mu$ is a finitely additive probability measure on $G$, then there is a $g$ in $G$ such that $\mu(E \cdot g) \ne \mu(E)$. Certainly $G$ is non amenable. Can more be said about $G$? Must $G$ contain $\mathbb{F}_2$?

It should be noted that the above situation can happen: let $E$ be all elements of $\mathbb{F}_2$ which ``begin'' with $a$ or $a^{-1}$. Then both $E$ and its complement have infinitely many disjoint translates (by powers of $b$ and $a$, respectively).

  • $\begingroup$ As far as I know, the question of whether every non-amenable group must contain $\mathbb F_2$ remains open (I heard it just last week in a talk by Steprans). $\endgroup$ – David Fernandez-Breton Apr 1 '11 at 3:13
  • $\begingroup$ @David: I heard the same in the same talk by Steprans, and he said that there is an example by Olshanskii of a non-amenable group that doesn't have a copy of $\mathbb F_2$. But what Justin is asking is whether it is the case that if the non-amenability is witnessed by a single set $E$ (the same set witnesses for all finitely additive probability measures that they are not translation invariant), then the group contains the free group on two generators? $\mathbb F_2$ is non-amenable for the reason Justin describes, but I have no idea what the situation with Olshanskii's groups is. $\endgroup$ – Stefan Geschke Apr 1 '11 at 5:35
  • $\begingroup$ The non amenability of Olshanskii's group is established by seeing it as a quotient of a free group and then looking at the limit of the number of words of length n in the kernel. (Actually, you look at the $n^{th}$ root of the number of words of length 2n.) This is unlikely to establish, one way or the other, the answer to Justin's question in that group. $\endgroup$ – Juris Steprans Apr 1 '11 at 16:34

The answer is that the above is equivalent to non amenability. Fix a group $(G,*)$. Since $(G,*)$ is non amenable if and only if every finitely generated subgroup is non amenable, we may assume that $G$ is finitely generated.

If $\mu$ and $\nu$ are finitely supported probability measures on $G$, define $$ \mu * \nu (Z) = \sum_{x * y \in Z} \mu (\{x\}) \nu (\{y\}) $$ Observe that $g * \nu (E) = \nu ( g^{-1} * E)$. If $S$ is a subset of $S$, let $P(S)$ denote all probability measures on $S$ (which are identified with probability measures on $G$ which are supported on $S$). I will identify $G$ with the point masses in $P(G)$.

If $A$ and $B$ are subsets of $G$ and $A$ is finite, we say that $B$ is $\epsilon$-Ramsey with respect to $A$ if for every $E \subseteq B$, then there is a $\nu$ in $P(B)$ such that $P(A) * \nu \subseteq P(B)$ and $$ |\mu * \nu (E) - \nu (E)| < \epsilon $$ for all $\mu$ in $P(A)$. Notice that in some sense $E$ is defining a partition of $P(B)$ and we are postulating the existence of a copy of $P(A)$ in $P(B)$ which is homogeneous for $E$ up to an error of $\epsilon$.

It can be shown with an argument similar to the one below that if $B$ is $\epsilon$-Ramsey with respect to $A$, then for every $f:B \to [0,1]$ there is a $\nu$ in $P(B)$ such that $$ |f(\mu * \nu) - f(\nu)| < \epsilon $$ where $f$ has been extended linearly to $P(B)$.

We say that $(G,*)$ is Ramsey if for every finite subset $A \subseteq G$ and every $\epsilon > 0$, there is a finite subset $B$ of $G$ with is $\epsilon$-Ramsey with respect to $A$. Notice that if $B$ satisfies that for every $E \subseteq B$ there is a $\nu$ in $P(B)$ such that $$ |g * \nu (E) - \nu (E)| < \epsilon $$ for all $g$ in $A$, then $B$ is contained in a finite set which is $\epsilon$-Ramsey (we need only to replace $B$ by $A * B \cup B$).

To connect this to the question, suppose that $G$ is not Ramsey, as witnessed by a finite $A \subseteq G$ and $\epsilon > 0$. I claim there is a set $E \subseteq G$ such that for every $\mu \in P(G)$, there is a $g \in A$ such that $|\mu(E \cdot g) - \mu (E)| \geq \epsilon/2$. Let $B_n$ $(n < \infty)$ be an increasing sequence of finite sets covering $G$. Let $T_n$ be the set of all subsets $E$ of $B_n$ which witness that $B_n$ is not $\epsilon$-Ramsey with respect to $A$. Observe that if $E$ is in $T_{n+1}$, then $E \cap B_n$ is in $T_n$. Otherwise there would be a $\nu$ in $P(B_n)$ such that $g * \nu$ is in $P(B_n)$ for each $g$ in $A$ and $$ |g * \nu (E \cap B_n) - \nu (E \cap B_n)| < \epsilon $$ Such a $\nu$ would also witness that $E$ is not in $T_{n+1}$. Define $T = \bigcup_n T_n$ and order $E \leq_T E'$ if $E = E' \cap B_m$ where $E$ is in $T_n$. This order makes $T$ into an infinite finitely branching tree. By König's lemma, $T$ has an infinite path whose union is some $E \subseteq G$. If there were a measure $\mu$ which was $\epsilon/2$-invariant for $E$ with respect to translates by elements of $A$, there would be a finitely supported $\nu$ which was $\epsilon$-invariant for $E$ with respect to translates in $A$. But this would be a contradiction since then the support of $\nu$ would be contained in some $B_n$ and $\nu$ would witness that $E \cap B_n$ was not in $T$.

Now the claim is that the Ramsey property of a discrete group is equivalent to its amenability. That amenability implies the Ramsey property follows from Følner's characterization of amenability. Also observe that $G$ is amenable provided that for every $\epsilon > 0$, every finite list $E_i$ $(i < n)$ of subsets of $G$, and $g_i$ $(i < n)$ in $G$, there is a finitely supported $\mu$ such that $$ |\mu (g_i * E_i) - \mu (E_i) | < \epsilon. $$ Set $B_{-1} = \{1_G\} \cup \{g^{-1}_i :i < n\}$ and construct a sequence $B_i$ $(i < n)$ such that $B_{i+1}$ is $\epsilon/2$-Ramsey with respect to $B_i$.

Now inductively construct $\nu_i$ $(i < n)$ by downward recursion on $i$. If $\nu_j$ $(i < j)$ has been constructed, let $\nu_i \in P(B_i)$ be such that $$ |\mu * \nu_{i} * \ldots * \nu_{n-1} (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2 $$ for all $\mu$ in $P(B_{i-1})$. Set $\mu = \nu_0 * \ldots * \nu_{n-1}$. If $i < n$, then since $\nu_0 * \ldots * \nu_{i-1}$ and $g_i^{-1} * \nu_0 * \ldots * \nu_{i-1}$ are in $P(B_{i-1})$, $$ |g_i^{-1} * \mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2 $$ $$ |\mu (E_i) - \nu_i * \ldots * \nu_{n-1} (E_i)| < \epsilon/2 $$ and therefore $|\mu (g_i * E_i) - \mu (E_i)| < \epsilon$.

  • 1
    $\begingroup$ Justin, how does this address you original question? How do you construct the set $E$, you were asking for? $\endgroup$ – Andreas Thom Apr 2 '11 at 13:34
  • 1
    $\begingroup$ Justin, from your comment I understand that existence of such an $E$ implies that $G$ is not Ramsey. Your argument above (in the the answer) then implies that $G$ is not amenable. But wasn't this clear already? (Being just the contra-positive of saying: If $G$ is amenable, then no such set can exist.) I thought the question is about the converse. Given $G$ non-amenable, does there exists and how can one construct the set $E$? I think, I must miss something very basic here. $\endgroup$ – Andreas Thom Apr 2 '11 at 16:23
  • 1
    $\begingroup$ Sorry, I still do not understand. Where do you show that the non-existence of such $E$ implies that $G$ is Ramsey? Don't you show (or claim) the converse in the section that starts with "Observe that if $E$...". There you assume some such $E$ exists and conclude that exists no set which is $\varepsilon$-Ramsey with respect to some finite set $A$. Now, how do you conclude that if no such $E$ exists, $G$ is Ramsey? $\endgroup$ – Andreas Thom Apr 3 '11 at 1:08
  • 1
    $\begingroup$ @Andreas,Kate: I have now edited the proof accordingly. The changes are twofold: argue that the version of "B is epsilon-Ramsey for A" where f is just a characteristic function is as strong as the statement for arbitrary maps into the interval. Then prove that if G is not Ramsey as witnessed by A, epsilon, then there is a E for which we can't invariantly measure all translates by elements of A. This is done by a standard compactness argument. Please let me know if you have more questions. If the proofs is now to your satisfaction, please either post a comment or email me. $\endgroup$ – Justin Moore Apr 3 '11 at 13:18
  • 1
    $\begingroup$ Justin, thanks a lot. Now I understand. This is a very nice argument! I guess, I have to read it once more, but for the moment it looks convincing. $\endgroup$ – Andreas Thom Apr 3 '11 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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