Theorem 3.6 — Følner's theorem

What the statement asserts

Setting. $G$ is an arbitrary group (any set with a group structure, of any size; no topology, no countability, no finiteness assumption is made). Group multiplication is written $gx$. For $g \in G$ and a subset $S \subseteq G$, write

$$gS = \{\, g x : x \in S \,\},$$

the image of $S$ under left multiplication by $g$. For subsets $S, T \subseteq G$, write $S \mathbin{\triangle} T = (S \setminus T) \cup (T \setminus S)$ for the symmetric difference, and $|S|$ for the number of elements of a finite set $S$.

Claim. For every group $G$, the following two conditions are equivalent (each implies the other):

Condition (F)

For every finite subset $A \subseteq G$ and every real number $\varepsilon > 0$, there exists a subset $F \subseteq G$ such that

• $F$ is finite,
• $F$ is nonempty, and
• for every $a \in A$,

$$\frac{|\,aF \mathbin{\triangle} F\,|}{|F|} \;\le\; \varepsilon .$$

Notes on this condition:

• The quotient is an ordinary quotient of real numbers. Because $F$ is required to be finite and nonempty, $|F| \ge 1$, so the denominator is never zero; and since $aF$ and $F$ are both finite, $aF \mathbin{\triangle} F$ is finite and its size is its ordinary number of elements.
• The inequality is non-strict ($\le \varepsilon$), and $\varepsilon$ ranges over all strictly positive reals.
• The translate is the left translate $aF$, not the right translate $Fa$.
• The set $F$ may depend on both $A$ and $\varepsilon$.
• $A$ may be empty; for $A = \varnothing$ the requirement is only that some nonempty finite $F$ exists.

Condition (M)

There exists a function $m$ assigning to every subset $S \subseteq G$ a value $m(S) \in [0, \infty]$ (the extended non-negative reals, including $+\infty$) such that all of the following hold:

1. $m(\varnothing) = 0$;
2. finite additivity on disjoint pairs: for all subsets $S, T \subseteq G$ with $S \cap T = \varnothing$,

$$m(S \cup T) = m(S) + m(T),$$

where addition is in $[0,\infty]$ (so $x + \infty = \infty$); 3. normalisation: $m(G) = 1$; 4. left invariance: for every $g \in G$ and every subset $S \subseteq G$,

$$m(gS) = m(S).$$

Notes on this condition:

• $m$ is defined on all subsets of $G$; no $\sigma$-algebra or measurability is involved.
• Only additivity over two disjoint sets is required (hence over any finitely many); no countable additivity is required.
• Invariance is under left translation $S \mapsto gS$ only; nothing is required about right translates.
• Values are allowed a priori to lie in $[0,\infty]$; nothing beyond conditions 1–4 constrains them.

The equivalence

For every group $G$:

$$\text{(F) holds for } G \iff \text{(M) holds for } G .$$