# When is non amenablity witnessed by a single non measurable set?

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

• 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). – David Fernandez-Breton Apr 1 '11 at 3:13
• @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. – Stefan Geschke Apr 1 '11 at 5:35
• 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. – 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$.

• Justin, how does this address you original question? How do you construct the set $E$, you were asking for? – Andreas Thom Apr 2 '11 at 13:34
• 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. – Andreas Thom Apr 2 '11 at 16:23
• 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? – Andreas Thom Apr 3 '11 at 1:08
• @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. – Justin Moore Apr 3 '11 at 13:18
• 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. – Andreas Thom Apr 3 '11 at 13:35