Under the ultrafilter lemma, the Folner condition is equivalent to amenability

Assume $G$ satisfies the Folner condition. Let $D$ be the directed set of triples $(S,n,F)$ with $S\subseteq G$ finite, $n\ge 1$, and $F$ an $(S,1\mathrm{/}n)$-Folner set, ordered by enlarging $S$ and $n$. For $d=(S,n,F)$, define $m_d(f)=\mathrm{\mid }F{\mathrm{\mid }}^{-1}{\sum }_{x\in F}f(x)$. These $m_d$ are means, and [L3] implies that if $g\in S$ then $\mathrm{\mid }{m}_d(g\cdot f)-m_d(f)\mathrm{\mid }\le \mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}n$. The cofinal tails $D_{g,N}=\{(S,n,F):g\in S,n\ge N\}$ have the finite intersection property, so by [A1] some ultrafilter on $D$ contains all of them. The ultrafilter limit of the bounded family $(m_d(f){)}_{d\in D}$ is therefore a left-invariant mean on $G$.

Assume instead that $G$ is amenable but not Folner. Then some finite $S\subseteq G$ and $\epsilon >0$ satisfy: for every finite nonempty $F\subseteq G$, some $s\in S$ has $\mathrm{\mid }sF\mathrm{△}F\mathrm{\mid }\ge \epsilon \mathrm{\mid }F\mathrm{\mid }$. Put $S_0=S\cup \{e\}$ and $\delta =\epsilon \mathrm{/}2$. Since $\mathrm{\mid }sF\mathrm{\mid }=\mathrm{\mid }F\mathrm{\mid }$, [L3] gives $\mathrm{\mid }sF\setminus F\mathrm{\mid }\ge \delta \mathrm{\mid }F\mathrm{\mid }$ for that $s$, and hence $\mathrm{\mid }{S}_{0}F\mathrm{\mid }\ge (1+\delta )\mathrm{\mid }F\mathrm{\mid }$.

Choose $m\ge 1$ with $(1+\delta {)}^m\ge 2$ and put $K=S_0^m$. Applying step 1.2 successively to $F,S_{0}F,\dots ,S_0^{m-1}F$ gives $\mathrm{\mid }KF\mathrm{\mid }\ge 2\mathrm{\mid }F\mathrm{\mid }$ for every finite nonempty $F\subseteq G$.

Form the bipartite graph with left vertices $G\times \{1,2\}$, right vertices $G$, and edges $(g,r)\sim kg$ for $k\in K$. If $P$ is a finite set of left vertices and $Q$ is its projection to $G$, then $N(P)=KQ$ and $\mathrm{\mid }P\mathrm{\mid }\le 2\mathrm{\mid }Q\mathrm{\mid }\le \mathrm{\mid }KQ\mathrm{\mid }$ by step 2.1. Thus [L4] gives a matching saturating every prescribed finite left set.

Let $\mathcal{M}$ be the set of finite partial matchings in this graph, and for finite $P\subseteq G\times \{1,2\}$ let $X_P$ be the set of members of $\mathcal{M}$ whose domains contain $P$. Step 3.1 shows that the family $(X_P)$ has the finite-intersection property. By [A1], an ultrafilter $\mathcal{U}$ on $\mathcal{M}$ contains every $X_P$. For a left vertex $\mathrm{\ell }$, the set $X_{\{\mathrm{\ell }\}}$ is the disjoint union of the finitely many sets on which the partial matching assigns a fixed neighbour $y\in N(\mathrm{\ell })$. Exactly one such cell belongs to $\mathcal{U}$; call its neighbour $\mathrm{\Phi }(\mathrm{\ell })$. If distinct left vertices had the same $\mathrm{\Phi }$-value, the two corresponding cells would have empty intersection, contradicting closure of $\mathcal{U}$ under intersections. Hence $\mathrm{\Phi }:G\times \{1,2\}\to G$ is injective and satisfies $\mathrm{\Phi }(g,r)\in Kg$.

Write ${\mathrm{\Phi }}_r(g)=\mathrm{\Phi }(g,r)$ and, for $r\in \{1,2\}$ and $k\in K$, put $D_{r,k}=\{g:{\mathrm{\Phi }}_r(g)=kg\}$. For each fixed $r$, the sets $D_{r,k}$ partition $G$, while the sets $k{D}_{r,k}$ partition the range $R_r$ of ${\mathrm{\Phi }}_r$; injectivity of $\mathrm{\Phi }$ makes $R_1$ and $R_2$ disjoint. If $m_G$ is a left-invariant mean, write $m_G(E)=m_G({\mathbf{1}}_E)$. Finite additivity and invariance give $m_G(R_r)={\sum }_{k\in K}{m}_G(k{D}_{r,k})={\sum }_{k\in K}{m}_G(D_{r,k})=m_G(G)=1$ for $r=1,2$. But $R_1\cap R_2=\mathrm{\varnothing }$, so positivity gives $2=m_G(R_1)+m_G(R_2)=m_G(R_1\bigsqcup R_2)\le m_G(G)=1$, a contradiction.

Therefore an amenable group cannot fail the Folner condition. Together with step 1.1, this proves the equivalence.