Asymptotic dimension and hyperfiniteness of generic Cantor actions
Sumun Iyer Forte Shinko



^†Carnegie Mellon University; sumuni@andrew.cmu.edu



^*University of California Berkeley; forteshinko@berkeley.edu

This research was partially conducted at the Spring 2023 thematic program in Set Theoretic Methods in Algebra, Dynamics and Geometry at the Fields Institute for Research in Mathematical Sciences. The first author was supported by NSF GRFP grant DGE – 2139899 and the second author was supported by the Fields Institute.


§ ABSTRACT 
    We show that for a countable discrete group
    which is locally of finite asymptotic dimension,
    the generic continuous action on Cantor space
    has hyperfinite orbit equivalence relation.
    In particular,
    this holds for free groups,
    answering a question of Frisch-Kechris-Shinko-Vidnyánszky.

GraphEx: A Graph-based Extraction Method for Advertiser Keyphrase Recommendation
    Forte Shinko^*
    September 9, 2024
================================================================================



For this entire article,
fix a countable discrete group Γ.



§ INTRODUCTION

A countable Borel equivalence relation (CBER)
is an equivalence relation E on a standard Borel space X
which is Borel as a subset of X^2,
and for which every equivalence class is countable
(see <cit.> for more background on CBERs).

The theory of CBERs seeks to classify these equivalence relations
based on their relative complexity.
More precisely,
there is a natural preorder on CBERs,
called the Borel reducibility preorder,
defined as follows:
if E and F are CBERs on X and Y respectively,
then E ≤_B F if there is a Borel map f : X → Y
such that for all x, x' ∈ X,
we have

    x  E x'
         f(x)  F f(x').

If E ≤_B F,
then we think of E as “simpler” than F.

The simplest CBERs are the so-called smooth CBERs,
which are those CBERs E satisfying E ≤_B Δ_,
where Δ_ is the equality relation on .
The canonical non-smooth CBER is E_0 on 2^ defined as follows:

    x  E_0 y ∃ k ∀ n > k   [x_n = y_n]

A CBER E is hyperfinite if E ≤_B E_0.
Hyperfiniteness is the next level up from smoothness in the following sense:
by the Harrington-Kechris-Louveau theorem,
a CBER E is non-smooth iff E_0 ≤_B E
(see <cit.>).
Hyperfiniteness is a very active area of research,
in part due to the deep connection with amenability.
Given a Borel action Γ X on a standard Borel space X,
denote by E_Γ^X the orbit equivalence relation of X.
By the Connes-Feldman-Weiss theorem <cit.>,
every orbit equivalence relation
of every amenable group is measure-hyperfinite,
where a CBER E on X is measure-hyperfinite
if for every Borel probability measure μ on X,
there is a Borel subset Y ⊆ X with μ(Y) = 1
such that E Y is hyperfinite.
A long-standing open question of Weiss
asks whether we can remove the measure condition
(see <cit.>):

    Is every orbit equivalence relation of every amenable group hyperfinite?
    

This problem is far from being resolved,
and in fact it is still open for solvable groups,
although it is known that the answer is positive for nilpotent and polycyclic groups
(see <cit.>).
To answer Weiss's Question in the positive,
it would be enough to have a positive resolution to the following question
(see <cit.>):

    Is every measure-hyperfinite CBER hyperfinite?

It is possible for this question to have a strong negative answer.
For instance,
measure-hyperfiniteness is a ^1_1 property,
and it is possible that hyperfiniteness is ^1_2-complete
(see <cit.>),
which in particular would imply that there are “many”
measure-hyperfinite CBERs which are not hyperfinite.

Another possible approach to a strong negative answer
is to apply Baire category in a Polish space of CBERs,
which we make precise.
A Cantor action of Γ is a group homomorphism Γ→(2^),
which we view as a continuous action Γ 2^.
Viewing (2^) as a Polish group with the compact-open topology,
let (Γ) be the Polish subspace of
(2^)^Γ consisting of Cantor actions of Γ.
It was shown by Suzuki (see <cit.>)
that if Γ is an exact group,
meaning that its reduced C*-algebra is exact,
then the set
{ a ∈(Γ) : a is measure-hyperfinite}
is comeager,
where we say that an action is hyperfinite
or measure-hyperfinite
if its orbit equivalence relation is.
This raises the following natural question,
which appears as Problem 8.0.16 in <cit.>
(note that there it is stated in terms of the space of subshifts,
but this is is equivalent by a result of Hochman,
see <cit.>):

    If Γ is an exact group,
    is the set
    { a ∈(Γ) : a is hyperfinite}
    comeager?


A negative answer to <Ref>
would immediately give a negative answer to <Ref>.
However,
we show that <Ref> has a positive answer
for a wide class of exact groups,
in particular for free groups,
for which the problem had been open:

    If Γ is locally of finite asymptotic dimension,
    then the set
    { a ∈(Γ) : a is hyperfinite}
    is comeager.

Asymptotic dimension is a coarse invariant of discrete groups
taking values in ∪{∞}.
Groups which are locally of finite asymptotic dimension
include free groups,
hyperbolic groups,
and mapping class groups of finite type surfaces
(see <cit.>
for background on asymptotic dimension of groups).
In particular,
this theorem exhibits examples of amenable groups,
such as (/2 ≀)^2,
for which it is now known that the generic Cantor action is hyperfinite,
but for which it is open whether all of its Cantor actions are hyperfinite.
There are still many amenable groups,
such as the solvable group ≀,
for which it not yet known that the generic Cantor action is hyperfinite.







§ BACKGROUND

We denote by (2^) the homeomorphism group of the Cantor space 2^,
viewed as a Polish group with the compact-open topology.

We describe an explicit basis for (2^).
We view every ϕ∈(2^) as a directed graph
whose vertex set is 2^,
and where there is a directed edge from x to y iff ϕ(x) = y.
Ranging over all finite directed graphs G
and over all continuous maps c : 2^→ V(G),
the sets

    {ϕ∈(2^)
        : c is a homomorphism of directed graphs from ϕ to G}

form an open basis for the topology of (2^).

For the rest of this section,
fix a countable group Γ.

We write S ⋐Γ
to mean that S is a finite subset of Γ
such that 1 ∈ S and S^-1 = S.

Let (Γ) be the set of continuous actions of Γ on 2^.
We view (Γ) as the (2^)-invariant Polish subspace of (2^)^Γ
consisting of all group homomorphisms Γ→(2^),
where the action (2^) (2^)^Γ is by conjugation on each coordinate.

We describe an explicit basis for (Γ).
A Γ-graph is a pair G = (V(G), E(G)),
where V(G) is a set,
and E(G) is a subset of Γ× V(G) × V(G).
We view every action Γ X as an Γ-graph G
where V(G) = X
and (γ, x, y) ∈ E(G) iff γ· x = y.
For Γ-graphs G and G',
a function f : V(G) → V(G') is an Γ-map from G to G'
if for every (γ, v, w) ∈ E(G),
we have (γ, f(v), f(w)) ∈ E(G').
A finite Γ-graph is a Γ-graph G
such that V(G) is finite
and such that E(G) is a cofinite subset of Γ× V(G) × V(G).
Ranging over all finite Γ-graphs G
and over all continuous maps c : 2^→ V(G),
the sets

    { a ∈(Γ) :
            c is a Γ-map from a to G}

form an open basis for the topology of (Γ).



§ LOCALLY CHECKABLE LABELLING PROBLEMS

For this section,
fix a countable group Γ.

We describe another basis for (Γ).


    An LCL on Γ
    (short for Locally Checkable Labelling problem)
    is a set of functions
    each of whose domains is a finite subset of Γ.

We think of an LCL as a set of “allowed patterns” for a coloring.

    Let Γ X be an action,
    and let Π be an LCL on Γ.
    A function c with domain X is a Π-coloring
    if there is some finite Π_0 ⊆Π
    such that for all x ∈ X,
    there is some P ∈Π_0
    such that for all γ∈(P),
    we have c(γ x) = P(γ).

So c is a Π-coloring
iff there is some finite Π_0 ⊆Π
for which c is a Π_0-coloring.


    Ranging over all LCLs Π
    and over all continuous maps c from 2^ to a discrete space,
    the sets
    
    { a ∈(Γ) : c is a Π-coloring}

    form an open basis for the topology of (Γ).


    First we show that each such set is open.
    Let a ∈(Γ),
    let Π be an LCL,
    and let c be a continuous map from 2^ to a discrete space,
    such that c is a Π-coloring of a.
    Fix a total order on Π,
    and let f : 2^→Π be the function defined as follows:
    for x ∈ 2^,
    let f(x) be the first element P ∈Π
    such that for all γ∈(P),
    we have c(γ x) = P(γ).
    This is continuous since c is continuous.
    Endow Π with a Γ-graph structure as follows:
    say that (γ, P, Q) is an edge
    if (γ P) ∪ Q is a function.
    Then f is a Γ-map from a to Π,
    and for every b ∈(Γ) for which f is a Γ-map,
    we have that c is a Π-coloring of b.

    To show that it is a basis,
    we will show that every set in the previous basis is of the new form.
    Fix a finite Γ-graph G and a continuous map f : 2^→ V(G).
    Fix S ⋐Γ such that
    (Γ∖ S) × V(G) × V(G) ⊆ E(G).
    Consider the LCL Π consisting of all functions P : S → V(G)
    such that (s, P(1), P(s)) ∈ E(G),
    Then for every a ∈(Γ),
    we have that f is a Γ-map from a to V(G)
    iff f is a Π-coloring.



Notice that every set of the form 

    { a ∈(Γ) :
        a has a continuous Π-coloring}

is an open set
since it is a union of the basic open sets considered in <Ref>. 

We show that nonempty such sets are dense.

    Let Π be an LCL on Γ.
    Then the following are equivalent:
    
        
  * Γ has a Π-coloring.
        
  * { a ∈(Γ) :
        a has a continuous Π-coloring} is nonempty.
        
  * { a ∈(Γ) :
        a has a continuous Π-coloring} is dense.
    


We will need the following.

    The set { a ∈(Γ) : a is free}
    is dense G_δ.

For a proof of <Ref>,
see <cit.> or <Ref>.

    
    
  * (1  2):
    
        It suffices to find some zero-dimensional compact Γ-space
        with a continuous Π-coloring,
        since its product with 2^ yields a Cantor action with the same property.
        
        Fix a finite subset Π_0 ⊆Π such that Γ has a Π_0-coloring,
        and let K = ⋃_P ∈Π_0(P).
        View K^Γ as a compact Γ-space
        equipped with the action (γ· x)_δ = x_δγ.
        Then the compact Γ-invariant subspace of K^Γ
        defined by
        
    X = {x ∈ K^Γ : x is a Π_0-coloring}

        is nonempty,
        and it has a continuous Π_0-coloring given by c(x) = x_1.

    
  * (2  3):
    
         The action (2^) (Γ) is generically ergodic,
         i.e. has a dense orbit
         (see <cit.>),
         so since this set is non-empty and (2^)-invariant,
         it is dense.
         
    
  * (3  1):
    
        By <Ref>,
        there is a free a ∈(Γ)
        with a continuous Π-coloring.
        By freeness,
        there is a Γ-equivariant map Γ→ a,
        and the composition of this with the Π-coloring of a
        is a Π-coloring of Γ.
    



    We can also prove <Ref> using LCLs.
    One can show using a coloring result like <cit.>
    that a zero-dimensional Polish Γ-space is free
    iff for every γ∈Γ,
    it has a continuous coloring for the LCL
    consisting of injections {1, γ}{0, 1, 2}.
    Then <Ref> immediately follows from
    (1  2  3)
    of <Ref>,
    whose proof never used <Ref>.































































































§ ASYMPTOTIC DIMENSION AND HYPERFINITENESS

For this section,
fix a countable group Γ.


    Let n ∈.
    An n-coloring is a function
    whose image is a subset of
    {0, 1, 2, …, n - 1}.


    Let Γ X be an action and let S ⋐Γ.
    A function c with domain X is S-separated
    if there is a uniform bound on the sizes of the components
    of the graph with vertex set X
    where x and x' are adjacent iff x' ∈ Sx and c(x) = c(x').



    The asymptotic dimension of an action
    Γ X of a group on a set,
    denoted (Γ X),
    is defined as follows:
    
    (Γ X)
            = sup_S ⋐Γmin{n ∈ :
            Γ X has an S-separated n-coloring} - 1




We define the asymptotic dimension of a group.

    The asymptotic dimension of a group Γ,
    denoted (Γ),
    is the asymptotic dimension of the left-multiplication action
    ΓΓ.



    A group Γ is locally of finite asymptotic dimension
    if all of its finitely generated subgroups have finite asymptotic dimension.


Note that every free action of Γ has asymptotic dimension (Γ).
In particular,
if Δ is a subgroup of Γ,
then (ΔΓ) = (Δ).

Asymptotic dimension can be encoded by LCLs.

    Let S ⋐Γ and let n ∈.
    The LCL Π_S, n is the set of n-colorings P with (P) such that
    
        
  * (P) is a finite subset of Γ;
        
  * 1 ∈(P);
        
  * for every γ∈(P) with P(γ) = P(1),
            we have S γ⊆(P).
    



    Let Γ X be an action,
    let S ⋐Γ,
    and let n ∈.
    Then every Π_S, n-coloring of X is an S-separated n-coloring.
    Moreover,
    if the action is free,
    then the converse also holds.


    Fix a function c with domain X.
    
    Let G be the graph with vertex set X
    where x and x' are adjacent iff x' ∈ Sx and c(x) = c(x').
    
    Suppose c is a Π_S, n-coloring.
    Then c is a Π_0-coloring for some finite Π_0 ⊆Π_S, n.
    Let x ∈ X.
    Since c is a Π_0-coloring,
    there is some P ∈Π_0 such that for every γ∈(P),
    we have P(γ) = c(γ x).
    Then [x]_G ⊆(P) x.
    Hence every component of G has size at most max_P ∈Π_0 |(P)|.

    Now suppose that the action is free,
    and suppose that c is an S-separated n-coloring.
    Then there is some k ∈
    such that for every x ∈ X,
    the G-component [x]_G of x satisfies [x]_G ⊆ S^k x.
    Let Π_0 ⊆Π_S, n consist of those P
    with (P) ⊆ S^k+1.
    Now suppose x ∈ X.
    Consider the function P
    with domain {γ∈Γ : γ x ∈ S[x]_G}
    defined by P(γ) = c(γ x).
    Then P ∈Π_S, n,
    and we have (P)x ⊆ S[x]_G ⊆ S^k+1 x,
    so by freeness we have (P) ⊆ S^k+1,
    and hence P ∈Π_0.
    Thus c is a Π_S, n-coloring.


For Cantor actions,
we use a topological version of asymptotic dimension.

    The continuous asymptotic dimension of a continuous action
    Γ X on a topological space,
    denoted _c(Γ X),
    is defined as follows:
    
    _c(Γ X)
            = sup_S ⋐Γmin{n ∈ :
            Γ X has a continuous S-separated n-coloring} - 1




    Let Δ≤Γ be a subgroup.
    Then the set
    
    { a ∈(Γ) :
            a is free and
                _c( aΔ) = (Δ)}

    is dense G_δ,
    and hence comeager.


    For free a ∈(Γ),
    we have _c( a Δ)
    ≥( a Δ)
    = (Δ),
    so we need only consider the inequality
    _c( aΔ) ≤(Δ).
    
    Freeness is dense G_δ by <Ref>.
    If (Δ) = ∞,
    then the set in question is just the set of free actions,
    so we are done.

    So suppose (Δ) < ∞.
    By <Ref>,
    for a ∈(Γ),
    we have that a is free and satisfies
    _c( aΔ) ≤(Δ)
    iff a is free and has a continuous Π_S, (Δ) + 1-coloring
    for every S ⋐Δ,
    The latter condition is dense G_δ by <Ref>,
    so we are done.

In particular,

    { a ∈(Γ) :
        a is free and _c( a) = (Γ)}

is dense G_δ and hence comeager,
so if (Γ) is finite,
then the generic element of (Γ) is hyperfinite
by <cit.>.
We can sharpen this to obtain <Ref> from the introduction:

    The set
    
    { a ∈(Γ) :
            a is free and _c( aΔ) = (Δ)
                for every finitely generated Δ≤Γ}

    is dense G_δ,
    and hence comeager.
    
    In particular,
    if Γ is locally of finite asymptotic dimension,
    then
    
    { a ∈(Γ) :
            a is hyperfinite}

    is comeager.


    For every finitely generated Δ≤Γ,
    the set
    
    { a ∈(Γ) :
            a is free and _c( aΔ) = (Δ)}

    is dense G_δ by <Ref>.
    There are countably many finitely generated Δ≤Γ,
    so the intersection over all of them is still dense G_δ.

    Now suppose that Γ is locally of finite asymptotic dimension.
    It suffices to show that every element a
    of this dense G_δ set is hyperfinite.
    Fix an increasing sequence (Δ_n)_n of finitely generated
    subgroups whose union is Γ.
    Then for every n,
    we have _c( a Δ_n) = (Δ_n) < ∞.
    Thus a is hyperfinite by <cit.>.




