Theorem 1.1 — Følner sets of F have at least tower-many elements (Moore's conventions)

The objects involved

Order automorphisms of the unit interval. Let $I = [0,1] \subset \mathbb{R}$. An order automorphism of $I$ is a bijection $f : I \to I$ such that $x \le y \iff f(x) \le f(y)$ for all $x, y \in I$. These form a group under composition, with product

$$(fg)(x) = f(g(x)),$$

the identity map as identity element, and the inverse map as inverse.

Dyadic numbers. A real number $b$ is dyadic if $b = m/2^k$ for some integer $m$ and some natural number $k \ge 0$.

Admissible automorphisms. Call an order automorphism $f$ of $I$ admissible if there is a finite set $B \subset \mathbb{R}$, all of whose elements are dyadic, with the following property: for every pair of points $x < y$ of $I$ such that the open interval $(x, y)$ contains no point of $B$, there exist an integer $n$ (which may be negative, zero or positive) and a real number $c$ such that

$$f(z) = 2^{n} z + c \qquad \text{for every } z \in I \text{ with } x \le z \le y.$$

The intercept $c$ is only required to be real, and the points of $B$ need not lie in $I$.

The group $F$. Let $F$ be the subgroup of the group of order automorphisms of $I$ generated by the admissible automorphisms, that is, the smallest subgroup containing all of them, with composition as its operation.

The opposite group $F^{\mathrm{op}}$. The statement is made in the opposite group $F^{\mathrm{op}}$. It has the same elements as $F$, but its product is

$$f \star g \;=\; g \circ f \qquad (\text{apply } f \text{ first, then } g).$$

It has the same identity as $F$, and the same inverses: $f^{-1}$ is the inverse map in either group. Every group-theoretic notion below (products, inverses, generation, translates) refers to $F^{\mathrm{op}}$.

The Følner condition. For finite subsets $\Gamma, A \subseteq F^{\mathrm{op}}$ and a real number $\varepsilon$, call $A$ $(\Gamma, \varepsilon)$-Følner if

$$\sum_{\gamma \in \Gamma} \bigl|\, (A \star \gamma) \,\triangle\, A \,\bigr| \;<\; \varepsilon \, |A| .$$

Here:

• $A \star \gamma = \{\, a \star \gamma : a \in A \,\}$ is the right translate of $A$ by $\gamma$ in $F^{\mathrm{op}}$. Written with composition in $F$, it is $\{\, \gamma \circ a : a \in A \,\}$, so each term is the size of $\gamma A \,\triangle\, A$ with $\gamma A$ the left translate in $F$.
• $\triangle$ is symmetric difference, $X \triangle Y = (X \setminus Y) \cup (Y \setminus X)$, and $|\cdot|$ is the number of elements.
• The sum runs over the distinct elements of $\Gamma$, each counted once. It is a sum of natural numbers, compared with $\varepsilon |A|$ as real numbers.
• The inequality is strict. The quantity is a sum over $\gamma$, not a maximum, and it is not divided by $|\Gamma|$.

The tower function. Define $t : \mathbb{N} \to \mathbb{N}$ by

$$t(0) = 0, \qquad t(n+1) = 2^{\,t(n)} .$$

So $t(0)=0$, $t(1)=1$, $t(2)=2$, $t(3)=4$, $t(4)=16$, $t(5)=65536$, and so on. It is a tower of $n$ twos, started from $0$.

The statement

Let $\Gamma$ be any finite subset of $F^{\mathrm{op}}$ satisfying both of the following.

1. Symmetry. For every $\gamma \in \Gamma$, also $\gamma^{-1} \in \Gamma$.
2. Generation. The subgroup of $F^{\mathrm{op}}$ generated by $\Gamma$ is all of $F^{\mathrm{op}}$. A subset of the underlying set is a subgroup of $F^{\mathrm{op}}$ exactly when it is a subgroup of $F$, so this is the same as saying that $\Gamma$, viewed as a set of elements of $F$, generates $F$.

Then there is a real number $C$ with

$$C > 1$$

such that for every natural number $n \ge 0$ and every finite subset $A \subseteq F^{\mathrm{op}}$:

$$\text{if}\quad \sum_{\gamma \in \Gamma} \bigl|\, (A \star \gamma) \,\triangle\, A \,\bigr| \;<\; C^{-n}\, |A|, \quad\text{then}\quad |A| \;\ge\; t(n).$$

Here $C^{-n} = 1/C^{n}$, an integer power of the real number $C$.

The order of quantifiers is: for all $\Gamma$ satisfying 1 and 2, there exists $C > 1$ (which may depend on $\Gamma$) such that for all $n$ and all $A$, the implication holds. $C$ is chosen before $n$ and $A$, so a single $C$ serves every $n$ and every $A$. Nothing else is assumed: there are no conditions on $A$ besides finiteness and the displayed inequality, and none on $\Gamma$ besides finiteness, symmetry and generation.

Edge cases and degenerate instances

• $n = 0$. Then $C^{-0} = 1$ and $t(0) = 0$, so the conclusion $|A| \ge 0$ always holds. The case $n = 0$ asserts nothing.
• $A = \varnothing$. The hypothesis then reads $0 < 0$, which is false. So the empty set never satisfies the Følner inequality, and every $A$ that does is nonempty. For $n = 1$ the conclusion $|A| \ge t(1) = 1$ therefore follows from the hypothesis alone.
• Size of the threshold. Because $C > 1$, the threshold $C^{-n}$ lies in $(0, 1]$, equals $1$ at $n = 0$, and strictly decreases as $n$ grows.
• $\Gamma = \varnothing$. The empty set generates only the trivial subgroup, so the generation hypothesis rules out $\Gamma = \varnothing$ unless $F^{\mathrm{op}}$ has only one element.
• The identity in $\Gamma$. $\Gamma$ may contain the identity; its term in the sum is $|A \triangle A| = 0$.
• Vacuous instances. The statement does not claim that any $A$ satisfies the Følner inequality for a given $n$. If none does, the implication for that $n$ holds vacuously.