Banach density with respect to a single Folner sequence

In this short post I show that in any countable amenable group {G} the (left) upper Banach density of a set {E\subset G} can be obtained by looking only at translations of a given Følner sequence. Definitions and the precise statement are given below.

This result is well know among experts but this fact doesn’t seem to be explicitly stated in the literature. The proof usually uses some functional analytic machinery, but the proof in this post is purely combinatorial in nature, which may give some additional information (as functional analytic tools are usually based on the axiom of choice, which prevents by principle the deduction of quantitative bounds).

Definition 1 Let {G} be a countable group. A sequence {(F_N)} of finite sets is a (left) Følner sequence if for all {g\in G} we have

\displaystyle \lim_{N\rightarrow\infty}\frac{|F_N\cap gF_N|}{|F_N|}=1

A countable group with a Følner sequence is called amenable and we will only deal with such groups. The canonical example is {G={\mathbb Z}} with the Følner sequence formed by the sets {F_N=\{1,2,\dots,N\}}. Every solvable group (and in particular every abelian group) is amenable.

The following proposition follows directly from the definition of Følner sequence:

Proposition 2 Let {G} be a countable amenable group, let {(F_N)} be a Følner sequence and let {(x_n)} be any sequence taking values on {G}. The sequence {(F_Nx_N)} is a Følner sequence.

The Følner {(F_Nx_N)} will be called a shift of {(F_N)}. In the example when {G={\mathbb Z}} we obtain the Følner sequences {\big(\{x_N+1,x_N+2,\dots,x_N+N\}\big)_{N\in{\mathbb N}}} by shifts of {F_N=\{1,2,\dots,N\}}.

Definition 3 Let {G} be an amenable group and {(F_N)} a Følner sequence on {G}. Let {E\subset G}.

  • The upper density of {E} with respect to {(F_N)} is:

    \displaystyle \bar d_{(F_N)}(E)=\limsup_{N\rightarrow\infty}\frac{|E\cap F_N|}{|F_N|}

  • The upper Banach density of {E} is:

    \displaystyle d^*(E)=\sup\left\{\bar d_{(F_N)}(E): (F_N)\text{ is a Følner sequence in }G\right\}

  • The upper Banach density of {E} with respect to {(F_N)} is:

    \displaystyle d_{(F_N)}^*(E)=\sup\left\{\bar d_{(G_N)}(E): (G_N)\text{ is a shift of }(F_N)\right\}

The last definition is not standard, and the following theorem, whose proof is the main purpose of this post, explains why:

Theorem 4 The upper Banach density with respect to a Følner sequence is the same as the upper Banach density. More precisely, let {G} be an amenable group, let {E\subset G} and let {(F_N)} be any Følner sequence on {G}. Then {d_{(F_N)}^*(E)=d^*(E)}.

It follows directly from the definitions that, for any Følner sequence {(F_N)_{N\in{\mathbb N}}} in {G} we have {d_{(F_N)}^*(E)\leq d^*(E)}. Thus it suffices to prove that, given any other Følner sequence {(G_N)_{N\in{\mathbb N}}} in {G} we have {\bar d_{(G_N)}(E)\leq d_{(F_N)}^*(E)}. The idea of the proof is to tile the each set {G_N} (or, more precisely, an approximation for {G_N}) when {N} is large, with shifts from {F_N}.

From now on we fix the Følner sequences {(F_N)_{N\in{\mathbb N}}} and {(G_N)_{N\in{\mathbb N}}} in {G} and a set {E\subset G}. Also we define

\displaystyle \delta:=d_{(F_N)}^*(E)

Lemma 5 For each {\epsilon>0} there exists {m\in{\mathbb N}} such that for all {x\in G} we have

\displaystyle |E\cap F_mx|\leq(\delta+\epsilon)|F_m|

The main point of this lemma is that {m} does not depend on {x}.

Proof: The proof goes by contradiction. Assume for each {m\in{\mathbb N}} there is some {b_m\in G} such that {|E\cap F_mb_m|>(\delta+\epsilon)|F_m|}. Then the upper density of {E} with respect to shift {(F_mb_m)} of the Følner sequence {(F_N)} would be larger than {\delta}, which is a contradiction. \Box

The following lemma gives us an asymptotically perfect tilling of {(G_N)} by shifts of a finite set {F}.

Lemma 6 Let {(G_N)} be a Følner sequence and let {F\subset G} be a finite set. For each {N\in{\mathbb N}}, define

\displaystyle A_N(F):=\{x\in G_N:Fx\subset G_N\}

Define, for each {n\in G_N}, the number

\displaystyle h_n(F)=\left|F^{-1}n\cap A_N(F)\right|=\left|\left\{x\in A_N(F):n\in Fx\right\}\right|

(note that {h_n(F)} also depends on {N}, we do not make this explicit to avoid notation even more cumbersome). Finally let {B_N(F):=\{n\in G_N:h_n(F)=|F|\}}.

Then {|B_N(F)|/|G_N|\rightarrow1} as {N\rightarrow\infty}.

The set {B_N\subset G_N} is constructed so that it can be tiled by shifts of {F}. This lemma shows that {B_N} occupies essentially all of {G_N}.

Proof: Note that for {n\in G_N} we have

\displaystyle n\in B_N(F)\iff F^{-1}n\subset A_N(F)\iff FF^{-1}n\subset G_N

Let {\tilde F=FF^{-1}} and note that {\tilde F} is a finite set. Rephrasing we have that {n\notin B_N(F)\iff (\exists g\in \tilde F)gn\notin G_N}. Thus we have

\displaystyle G_N\setminus B_N(F)=\bigcup_{g\in\tilde F}\{n\in G_N:gn\notin G_N\}

Since {(G_N)} is a Følner sequence we get that

\displaystyle \lim_{N\rightarrow\infty}\frac{|\{n\in G_N:gn\notin G_N\}|}{|G_N|}=0

for all {g\in G}. Thus, taking the union over the finite set {\tilde F} we obtain that

\displaystyle \lim_{N\rightarrow\infty}\frac{|G_N\setminus B_N|}{|G_N|}=\lim_{N\rightarrow\infty}\frac1{|G_N|}\left|\bigcup_{g\in\tilde F}\{n\in G_N:gn\notin G_N\}\right|=0

From this we conclude that {|B_N(F)|/|G_N|\rightarrow1} as desired. \Box

As a Corollary we deduce that the density of {E} with respect to {(G_N)} can be calculated by looking at the intersections of {E} with {B_N(F)}.

Corollary 7 For any finite set {F\subset G} we have

\displaystyle \bar d_{(G_N)}(E)=\limsup_{N\rightarrow\infty}\frac{|E\cap B_N(F)|}{|G_N|}

We now prove Theorem 4. Let {\epsilon>0} and let {m} be given by Lemma 5. Let {N} be very large and let {A_N(F_m)}, {h_n(F_m)} and {B_N(F_m)} be all as in Lemma 6. We now have:

\displaystyle \frac1{|G_N|}\sum_{x\in A_N(F_m)}\frac{|E\cap F_mx|}{|F_m|}\leq\frac{|A_N|}{|G_N|}(\delta+\epsilon)\leq\delta+\epsilon

On the other hand:

\displaystyle \begin{array}{rcl} \displaystyle\sum_{x\in A_N(F_m)}\frac{|E\cap F_mx|}{|F_m|}&=&\displaystyle\sum_{x\in A_N(F_m)}\sum_{n\in F_mx}\frac{1_E(n)}{|F_m|}=\sum_{n\in G_N}1_E(n)\frac{h_n(F_m)}{|F_m|}\\&\geq&\displaystyle\sum_{n\in B_N(F_m)}1_E(n)=|E\cap B_N(F_m)| \end{array}

Putting both together we get

\displaystyle \frac{|E\cap B_N(F_m)|}{|G_N|}\leq\delta+\epsilon

By Corollary 7 we conclude that {\bar d_{(G_N)}(E)\leq\delta+\epsilon}. Since {\epsilon} was arbitrarily chosen we conclude the proof of Theorem 4.

This entry was posted in Classic results, Combinatorics, Tool and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s