On Turing dynamical systems and the Atiyah problem

Abstract

Main theorems of the article concern the problem of Atiyah on possible values of $l^2$-Betti numbers. It is shown that all non-negative real numbers are $l^2$-Betti numbers, and that “many” (for example all non-negative algebraic) real numbers are $l^2$-Betti numbers of simply connected manifolds with respect to a free cocompact action. Also an explicit example is constructed which leads to a simply connected manifold with a transcendental $l^2$-Betti number with respect to an action of the threefold direct product of the lamplighter group $\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z}$. The main new idea is embedding Turing machines into integral group rings. The main tool developed generalizes known techniques of spectral computations for certain random walk operators to arbitrary operators in groupoid rings of discrete measured groupoids.

$\textit{To my family}$

1 Introduction

Main theorems of the article concern studying countable discrete groups through so called $l^2$-Betti numbers. These are certain invariants, originally introduced by Atiyah in [1] to study free cocompact actions of discrete groups on manifolds. Subsequently, they were studied and used in many different contexts in geometry and group theory (e.g. [5, 7, 12]).

A particular question Atiyah asked in [1] was whether $l^2$-Betti numbers can be irrational. Since then, various statements about restrictions on possible values of $l^2$-Betti numbers bear the name the Atiyah conjecture (e.g. [8]). We depart somewhat from this tradition. Given a countable discrete group $G$, the following question will be referred to as the Atiyah problem for G.

Question

What is the set of $l^2$-Betti numbers arising from $G$?

Let us right away introduce the notation ${\mathcal C}(G)$ for the set in the above question. Over time it has been realized (see [9, 14]) that $l^2$-Betti numbers arising from a given group can be defined purely in terms of $G$, without mentioning manifolds. Consequently, the Atiyah problem can also be phrased purely in terms of $G$. This is the approach we adopt in the article and which we now briefly present.

The rational group ring $\mathbb {Q}G$ acts on the Hilbert space $l^2G$ by convolution, and similarly matrices $M_k(\mathbb {Q}G) \cong M_k(\mathbb {Q})\otimes \mathbb {Q}G$ act on $(l^2G)^k$. We have a trace $\tau _G$ on $\mathbb {Q}G$ defined by $\tau _G(T) : = \langle T\zeta _e, \zeta _e \rangle$, where $\zeta _e\in l^2G$ is the vector corresponding to the neutral element of $G$, and we have the induced trace $\mathrm{tr }\otimes \tau _G$ on $M_k(\mathbb {Q}G)$, also denoted by $\tau _G$.

Recall that when $R$ is a ${}^*$-ring of operators on a Hilbert space, together with a trace $\tau$ which is normal (i.e., extends in a continuous way to the weak closure of $R$), positive (i.e., $\tau (T^*T)\ge 0$) and faithful (i.e., $\tau (T^*T)=0$ implies $T=0$), then for a self-adjoint $T\in R$ we can compose the usual projection-valued spectral measure with $\tau$, to obtain the (scalar-valued) spectral measure of $T$. In particular, spectral measure of the set $\{0\}$ is called the von Neumann dimension of the kernel of $T$, and is denoted by $\dim _\text {vN}\ker T$. For a non-self-adjoint $T$, one defines $\dim _\text {vN}\ker T := \dim _\text {vN}\ker T^*T$.

It turns out that $\tau _G$ is a positive faithful normal trace on $M_k(\mathbb {Q}G)$ and thus we have a von Neumann dimension. A real number $r$ is said to be an $l^2$-Betti number arising from $G$ if and only if there exists a matrix $T\in M_k(\mathbb {Q}G)$ such that $\dim _\text {vN}\ker T = r$.

Much is known about the Atiyah problem for various particular groups. If $G$ is torsion-free, then ${\mathcal C}(G)$ is conjectured to be the set of non-negative integers. This statement is known as the Atiyah conjecture for torsion-free groups (there is a similar conjecture for groups whose torsion subgroups have bounded orders). Cases for which the Atiyah conjecture is known include elementary amenable groups, free groups (see [21] for both classes) and braid groups (see [20]). Many results follow by applying versions of Lück’s approximation theorem (see [8, 22], [25, Lemma 5.2]) to already established results. Perhaps the most familiar consequence of the Atiyah conjecture is the zero divisors conjecture for torsion-free groups. For other results see [23, Chapter 10].

Before the work of Grigorchuk and Żuk in [15], it had been conjectured that ${\mathcal C}(G) \subset \mathbb {Z}(\frac{1}{a_1}, \frac{1}{a_2},\ldots )$, where $a_i$ are orders of torsion subgroups in $G$. However, in [15] the authors showed that $\dim _\text {vN}\ker T = \frac{1}{3}$ for a certain operator $T$ from the group ring of the lamplighter group $\,\mathbb {Z}{/2\mathbb {Z}}\, \wr \mathbb {Z}$. Recall that the latter group is a semi-direct product of $\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}}$ with $\mathbb {Z}$ with respect to the shift action of $\mathbb {Z}$ on $\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}}$. In particular, torsion subgroups of the lamplighter group have orders which are powers of $2$.

Shortly afterwards Dicks and Schick described in [6] an operator $T$ from the group ring of $(\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^2$ and an heuristic evidence on why $\dim _\text {vN}\ker T$ is probably irrational. Nonetheless, the question of irrationality of that specific number has remained open.

A breakthrough came in 2009, when Austin showed the following theorem.

Theorem

[2] The set of $l^2$-Betti numbers arising from finitely generated groups is uncountable.

In particular there exist irrational $l^2$-Betti numbers. However, [2] did not provide a particular group which gives rise to irrational $l^2$-Betti numbers.

1.1 Results

Theorem 1.1

The set of $l^2$-Betti numbers arising from the group $(\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^3$ contains

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}}, \end{aligned}$$

which is an irrational number.

Irrationality of the number above follows from the fact that its binary expansion is non-periodic. The author does not know whether the current transcendence results cover this number.

It is of some theoretical interest to have explicit finitely presented examples, so we point out also the following corollary.

Corollary 1.2

Let $G$ be a group given by the presentation

$$\begin{aligned} \langle a,t,s\,|\,a^2=1,[t,s]=1,[t^{-1}at,a]=1,s^{-1}as=at^{-1}at\rangle . \end{aligned}$$

The set of $l^2$-Betti numbers arising from $G^3$ contains

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}}. \end{aligned}$$

In both Theorem 1.1 and Corollary 1.2, the appropriate matrix whose kernel dimension is as stated can be explicitly written down in terms of the standard generators.

Theorem 1.3

The set of $l^2$-Betti numbers arising from finitely generated groups is equal to the set of non-negative real numbers.

The group which realizes a given real number $r$ is “as explicit as the binary expansion of $r$”.

In other words, measures of atoms in spectral measures of rational group ring elements are arbitrary real numbers. The atoms themselves however are, at least for sofic groups, algebraic numbers (see [28]).

We can also say something about the set of $l^2$-Betti numbers arising from finitely presented groups. Recall that a set ${\Sigma }$ of natural numbers is called computable if there exists a Turing machine which lists the elements of ${\Sigma }$ in the increasing order (in other words, there exists an algorithm which allows to compute subsequent elements of ${\Sigma }$).

We say that a real number $r$ has computable binary expansion if the fractional part of $r$ is of the form

$$\begin{aligned} \sum _{i\in {\Sigma }} \frac{1}{2^i} \end{aligned}$$

for some computable set ${\Sigma }$.

Theorem 1.4

The set of $l^2$-Betti numbers arising from finitely presented groups contains all numbers with computable binary expansions.

Examples of numbers with computable binary expansion include all algebraic numbers, $\pi$ and $e$. A fairly well-known example of a number whose binary expansion is not computable is Chaitin’s constant encoding the halting problem (see [4]).

Theorem 1.3 has been independently proven by Pichot, Schick and Żuk in [26]. They also proved a result similar to Theorem 1.4. Let us also mention two later developments: (1) In [19], Lehner and Wagner show that ${\mathcal C}(\,\mathbb {Z}{/p\mathbb {Z}}\, \wr F_d)$ contains irrational algebraic numbers, where $F_d$ is the free group on $d$ generators, $d>2$, $p\ge 2d-1$; (2) In [13] the present author shows that ${\mathcal C}(\,\mathbb {Z}{/p\mathbb {Z}}\,\wr {\Gamma })$ contains transcendental numbers, for all $p>1$ and all groups ${\Gamma }$ which contain an element of infinite order.

1.2 Summary

Section 2 deals with discrete measured groupoids, which seem to be the right context to generalize known spectral computations of random walk operators on groups of the form ${\widehat{X}} \rtimes {\Gamma }$, where ${\widehat{X}}$ is discrete abelian. In short, the spectrum of an operator from a groupoid ring is shown to be the expected spectral measure of the convolution operator on a random (groupoid) Schreier diagram associated to the operator. The main computational tools are Proposition 2.10 and Corollary 2.11. Section 3 explains how they generalize a computation of Grigorchuk and Żuk from [15], and a theorem of Lehner, Neuhauser and Woess from [18].

Section 4 introduces Turing dynamical systems, which are a natural generalization of Turing machines (possibly with oracles). The computational tool is used in Theorem 4.3 to show a connection between dynamical properties of a system and spectral properties of certain operator in the groupoid ring of the associated groupoid.

Section 5 presents examples of Turing dynamical systems which are then used in Sect. 6 to prove results about the Atiyah problem.

1.3 Open questions

All questions are well-known to the experts.

Question 1.5

What is the set of $l^2$-Betti numbers arising from finitely presented groups?

Note that the set in question is countable. In [26] different numbers appear than those covered by Theorem 1.4. On the other hand, note that every $l^2$-Betti number is, by functional calculus, a limit of a sequence $\tau _G( (1-T)^n)$, where $T \in M_k (\mathbb {Q}G)$ and $\tau _G$ is the group trace. If the group $G$ is sofic, then there are bounds known on what $n$ one has to take to be ${\varepsilon }$-close to the limit (this follows from the determinant conjecture, see [10]). It follows that if $G$ is a sofic group, then elements of ${\mathcal C}(G)$ are computable by a Turing machine with an oracle for the word problem of $G$. If $G$ is finitely presented then the word problem of $G$ is known to be not harder than the halting problem. This gives some bound on what $l^2$-Betti numbers can arise from (sofic) finitely presented groups; however this bound seems to be far away for the techniques presented here or in [26].

Question 1.6

For a group $G$ and a ring $k\subset \mathbb {C}$, define ${\mathcal C}(G, k)$ to be the set of those $r$ such that there exists $T\in kG$ with $\dim _\text {vN}\ker T = r$. By definition, ${\mathcal C}(G, \mathbb {Q}) = {\mathcal C}(G)$. Is it true that for every group $G$ we have ${\mathcal C}(G) = {\mathcal C}(G, \mathbb {C})$? In particular, is it true that the set ${\mathcal C}(G, \mathbb {C})$ is countable?

The answers are trivially yes for those torsion-free groups (or groups with bounded torsion subgroups) for which the so called strong Atiyah conjecture holds: ${\mathcal C}(G, \mathbb {C}) = \mathbb {N}$ (this has to be modified appropriately for bounded torsion groups). Examples include free groups and bounded-torsion elementary amenable groups (see [21]). On the other hand, the answers are not known even for $\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z}$. This motivates the next question.

Question 1.7

What is ${\mathcal C}(\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})$?

In Theorem 1.1 we prove ${\mathcal C} ((\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^3)\nsubseteq \mathbb {Q}$. After the first version of this article was submitted to arXiv, F. Lehner and S. Wagner showed in [19] that ${\mathcal C}(\,\mathbb {Z}{/p\mathbb {Z}}\, \wr F_d)$ contains irrational algebraic numbers, where $F_d$ is the free group on $d$ generators, $d>2$, $p\ge 2d-1$, which subsequently led the author to show in [13] that ${\mathcal C}(\,\mathbb {Z}{/p\mathbb {Z}}\,\wr \mathbb {Z})$ contains transcendental numbers, for all $p>1$. This raises the question whether ${\mathcal C}(\,\mathbb {Z}{/p\mathbb {Z}}\,\wr \mathbb {Z})$ contains irrational algebraic numbers. In fact, ${\mathcal C}((\,\mathbb {Z}{/p\mathbb {Z}}\,\wr \mathbb {Z})^k)$ contains algebraic numbers of degree $k$, as will be shown in a future version of [13].

Question 1.8

Are $l^2$-Betti numbers of a countable discrete group rational?

For a precise definition of $l^2$-Betti numbers of a group, see e.g. [9, 23] for a more general definition. If $r$ is an $l^2$-Betti number of a group $G$, then it is in particular an $l^2$-Betti number arising from $G$, but not the other way around. All the examples in the literature so far, of groups which give rise to irrational $l^2$-Betti number, have an infinite normal amenable subgroup. This implies that all their $l^2$-Betti numbers are $0$ (see [23, Theorem 7.2]).

1.4 Notation, conventions and a lemma

The term measurable space refers to a standard Borel space. The word subset means measurable subset, whenever it makes sense; similarly for functions. We do not always explicitely check that the sets and functions we work with are measurable, but in all the cases such checks are standard. Axiom of Choice is not used.

The cardinality of a set $S$ is denoted by $|S|$. The Hilbert space whose orthonormal basis consists of elements of $S$ is denoted by $l^2(S)$ or $l^2S$. The standard basis vectors are denoted by $\zeta _s$, $s\in S$. If $U$ is a subset of $S$ then $\chi _U:S \rightarrow \{0,1\}$ and $\chi (U):S \rightarrow \{0,1\}$ denote the characteristic function of $U$.

A sequence $(\ldots , x_{i-1}, x_i, x_{i+1}, \ldots )$ is denoted by $(x_i)$ or $\dot{x}_i$.

Graphs and diagrams If $g$ is a graph then its sets of vertices and edges are denoted by $V(g)$ and $E(g)$. If $g$ is an oriented graph and $e\in E(g)$, then the starting and ending points of $e$ are denoted by $s(e)$ and $r(e)$ ($r$ stands for range). The Hilbert space $l^2(V(g))$ is denoted also by $l^2g$.

A full subgraph of a graph $g$ is a subgraph $h$ with the property that if $e\in E(g)$ is an edge between two vertices in $V(h)$, then $e\in E(h)$.

A vertex in an oriented graph with no incoming edges, perhaps with an exception of a self-loop, is called a starting vertex. Similarly for a final vertex.

When $A$ is a set or a sequence, an $A$-diagram is an oriented graph of bounded degree with edge labels in $A$. $\mathbb {C}$-diagrams are called simply diagrams. Given a diagram $g$, the associated convolution operator is the unique operator $T:l^2g \rightarrow l^2g$ such that $\langle T(\zeta _x), \zeta _y\rangle$ is equal to $0$ if there are no edges between $x$ and $y$ and to sum of all the labels between $x$ and $y$ otherwise. If $g$ is a rooted diagram then the rooted spectral measure of the convolution operator $T_g$ on $g$ is the usual projection-valued spectral measure composed with the functional $P \mapsto \langle P \zeta _x, \zeta _x\rangle$, where $x$ is the root of $g$.

If $A$ is a sequence, then the labels are assumed to “remember” the order of elements of $A$, e.g. if $A$ is the sequence $(a_1, a_2)$ then the two $A$-diagrams consisting of one oriented edge with label $a_1$ or $a_2$ are not the same $A$-diagram, even if $a_1=a_2$.

Given an oriented graph $g$, we use the expression “diagram $g$” for the diagram which has $g$ as the underlying graph and all the labels are $1$. If $g$ is an $A$-diagram we say “graph $g$” for the underlying oriented graph of $g$.

Rings and operators Given a ring $R$, the ring of $k\times k$-matrices over $R$ is denoted by $M_k(R)$. A trace $\tau$ on $R$ is a function $\tau :R \rightarrow \mathbb {C}$ such that $\tau (ab)=\tau (ba)$. The standard trace (i.e. sum of diagonal elements) on $M_k(\mathbb {C})$ is denoted by $\mathrm{tr }$. If $R$ is a ${}^*$-ring of operators on a Hilbert space then we also require that $\tau (T^*T)$ is a non-negative real number, for all $T\in R$. If $R$ is an algebra over a field ${\mathbb F} \subset \mathbb {C}$ and $\tau$ is a trace on $R$, then we have an induced trace on $M_k(R) \cong M_k({\mathbb F}) \otimes R$ given by $\mathrm{tr }\otimes \tau$, The induced trace is also denoted by $\tau$.

If $R$ is a ${}^*$-ring of operators on a Hilbert space, then a trace $\tau$ on $R$ is called normal if it extends to a continuous trace on the weak completion of $R$. A trace is faithful if, for every $T$, $\tau (T^*T)=0$ implies $T=0$. All traces we will consider are faithful and normal.

If $R$ is a ${}^*$-ring of operators on a Hilbert space, $\tau$ is a faithful normal trace on $R$, and $T^*=T\in R$ then the spectral measure of T is the usual projection-valued spectral measure of $T$ composed with $\tau$ (it makes sense to evaluate $\tau$ on spectral projections of $T$, since the latter are in the weak completion of $R$). The spectral measure of the set $\{0\}$ is called von Neumann dimension of kernel of T, denoted by $\dim _\text {vN}\ker (T)$. For a non-self-adjoint $T$ we define $\dim _\text {vN}\ker (T) = \dim _\text {vN}\ker (T^*T)$.

We say that the spectral measure of $T^*=T \in R$ is pure-point, or that $T$ has pure-point spectrum, if the spectral measure of $T$ is a countable sum of measures supported on single points.

Lemma 1.9

Let $A$ and $B$ be ${}^*$-rings of operators Hilbert spaces $H_A$ and $H_B$ with faithful normal traces $\tau _A$ and $\tau _B$. Let $\phi : A\rightarrow B$ be a trace preserving ${}^*$-homomorphism and $T^*=T\in A$. Then the spectral measure of $T$ with respect to $\tau _A$ is the same as the spectral measure of $\phi (T)$ with respect to $\tau _B$.

Proof

Since $\phi$ is ${}^*$-preserving, $\phi (T)$ is also self-adjoint. The spectral measure, as any ${\sigma }$-additive measure, is determined by measures of intervals. Let $I$ be an interval and $p_n$ be a sequence of polynomials converging to $\chi _I$ pointwise, everywhere on $\mathbb {R}$. By the definition of the spectral measure, we need to show $\tau _A(\chi _I(T)) = \tau _B(\chi _I(\phi (T))$.

By the spectral theorem, we have $p_n(T) \rightarrow \chi _I(T)$, and $p_n(\phi (T)) \rightarrow \chi _I(\phi (T))$. Since $\phi$ is a homomorphism, we have $p_n(\phi (T)) = \phi (p_n(T))$. Since $\tau$ is normal, we have $\tau _A(p_n(T)) \rightarrow \tau _A(\chi _I(T))$, and $\tau _B(\phi (p_n(T))) \rightarrow \tau _B (\chi _I(\phi (T))$. The claim follows since $\phi$ is assumed to be trace preserving, in particular $\tau _B(\phi (p_n(T))) = \tau _A(p_n(T))$.

2 Groupoids

2.1 Definitions

For more information on groupoids see [27] and references therein.

A groupoid ${\mathcal G}$ is a small category whose morphisms are all invertible. The sets of objects and morphisms are denoted respectively by ${\mathcal G}_0$ and ${\mathcal G}$. The embedding $\mathbf 1:{\mathcal G}_0 \rightarrow {\mathcal G}$ sends an object $x$ to the identity morphism on $x$. The space ${\mathcal G}_0$ will be often identified with a subset of ${\mathcal G}$ via this embedding.

The maps $s,r:{\mathcal G} \rightarrow {\mathcal G}_0$, source and range maps, associate to a morphism its domain and codomain. Composition is a map ${\mathcal G} {}_r\!\times _s {\mathcal G} \rightarrow {\mathcal G}$; composition of morphisms ${\gamma }:x\rightarrow y$ and ${\gamma }':y\rightarrow z$ is denoted by ${\gamma }{\gamma }'$ ot ${\gamma }\cdot {\gamma }'$. Given ${\gamma }:x\rightarrow y$, the inverse of ${\gamma }$ is denoted either by $i({\gamma })$ or by ${\gamma }^{-1}$. Note that the symbol $\circ$ stays reserved for the standard composition of functions.

For $x\in {\mathcal G}_0$, the sets $s^{-1}(x)$ and $r^{-1}(x)$ are denoted by $s^*x$ and $r^*x$. The set of those objects $y$ for which there exists a morphism between $x$ and $y$ is the orbit of x, denoted by ${\mathcal G}x$.

A discrete measurable groupoid is a groupoid together with a structure of a measurable space on ${\mathcal G}$, and such that ${\mathcal G}_0$ is a measurable subset, fibers of the maps $s$ and $r$ are countable, and the structure maps $s$, $r$, $i$ and composition are measurable.

A discrete measured groupoid is a discrete measurable groupoid ${\mathcal G}$ together with a measure $\mu$ on ${\mathcal G}_0$, such that the measures

$$\begin{aligned} {\mathcal G} \supset U \mapsto \int _{{\mathcal G}_0} |r^{-1}(x)\cap U| d\mu (x) \end{aligned}$$

and

$$\begin{aligned} {\mathcal G} \supset U \mapsto \int _{{\mathcal G}_0} |s^{-1}(x)\cap U| d\mu (x) \end{aligned}$$

are equal. This measure on ${\mathcal G}$ is also denoted by $\mu$.

From now on all groupoids will be discrete measured, unless explicitly stated otherwise. The following lemma is a direct consequence of the definition of measure on ${\mathcal G}$.

Lemma 2.1

Suppose $U\subset {\mathcal G}$ is such that $r$ restricted to $U$ is an injection. Then the measure of $U$ in ${\mathcal G}$ is the same as the measure of $r(U)$ in ${\mathcal G}_0$.

For $x \in {\mathcal G}_0$ let stabilizer $\varvec{\mathrm{St }(x,{\mathcal G})}$ of $x$ be the group of those ${\alpha }\in {\mathcal G}$ such that $s({\alpha })=r({\alpha })=x$ We say that a groupoid ${\mathcal G}$ is a relation groupoid, if for almost all $x$ we have $\varvec{|\mathrm{St }(x, {\mathcal G})|=1}$. If ${\mathcal G}$ is a relation groupoid then we freely use the identification of $s^*x$ with ${\mathcal G}x$ given by $s^*x \ni {\gamma }\mapsto r({\gamma })$.

Lemma 2.2

Let ${\mathcal G}$ be a groupoid, $A, B \subset {\mathcal G}_0$, and $f:{\mathcal G}_0 \rightarrow \mathbb {C}$ be constant on orbits of ${\mathcal G}$. Then

$$\begin{aligned} \int _A \!f(x)\cdot |\mathrm{St }(x,{\mathcal G})|\cdot |{\mathcal G}x \cap B| \,d\mu (x) \!=\! \int _B \!f(x)\cdot |\mathrm{St }(x,{\mathcal G})|\cdot |{\mathcal G}x \cap A| \,d\mu (x) \end{aligned}$$

Proof

Let $U\subset {\mathcal G}$ denote the set $\{{\gamma }\in {\mathcal G}:s({\gamma })\in A, r({\gamma })\in B\}\subset {\mathcal G}$, and ${\widetilde{f}}:= f\circ s$. Both quantities are equal to

$$\begin{aligned} \int _{U} {\widetilde{f}}(x) \,d\mu (x) \end{aligned}$$

A measurable edge is a pair $(U, \phi )$, where $U\subset {\mathcal G}_0$ and $\phi : U \rightarrow {\mathcal G}$, such that $s\circ \phi :U\rightarrow {\mathcal G}_0$ is the identity embedding, and $r\circ \phi :U \rightarrow {\mathcal G}_0$ is injective. Note that $\phi$ and $r\circ \phi$ are automatically measure preserving. For the most part, we write simply $\phi$, with the understanding that $U = \mathrm{Dom }( \phi )$ is the domain of definition of $\phi$. If $\phi$ is a measurable edge, then $\phi ^{-1}$, the inverse of $\phi$, is the measurable edge with $\mathrm{Dom }(\phi ^{-1}) = r\big (\mathrm{Im }(\phi )\big )$, and such that $\phi ^{-1}\Big ( r\big (\phi (x)\big ) \Big ) = i(\phi (x))$.

Lemma 2.3

There exists a countable family of measurable edges whose images are disjoint and such that the union of all their images is all of ${\mathcal G}$.

Proof

The statement follows from a theorem of Luzin and Novikov (see [17], Theorem 18.10): there exists a division of ${\mathcal G}$ into countably many disjoint sets such that the restriction of $s$ to any of them is injective (this is true for any measurable map with countable fibers).

Let $\Phi = (\phi _1, \ldots , \phi _n)$ be a sequence of measurable edges. The Schreier diagram $\mathrm{Schr }_\Phi ({\mathcal G})$ of ${\mathcal G}$ with respect to $\Phi$ is the $\Phi$-diagram whose vertices are points of ${\mathcal G}_0$, and there is an oriented edge between $x$ and $y$ with label $\phi _i$ iff there is a morphism between $x$ and $y$ in the image of $\phi _i$. Similarly the Cayley diagram $\mathrm{Cay }_\Phi ({\mathcal G})$ is the $\Phi$-diagram whose vertices are points of ${\mathcal G}$, and there is an oriented edge between ${\alpha }$ and ${\beta }$ with label $\phi _i$ if there is a morphism ${\gamma }$ in the image of $\phi _i$ such that ${\alpha }{\gamma }={\beta }$.

The full subdiagrams of $\mathrm{Schr }_\Phi ({\mathcal G})$ and $\mathrm{Cay }_\Phi ({\mathcal G})$ whose vertices are respectively ${\mathcal G}x$, and $s^*x$, where $x\in {\mathcal G}_0$, are denoted by $\mathrm{Schr }_\Phi (x, {\mathcal G})$ and $\mathrm{Cay }_\Phi (x, {\mathcal G})$, and called Schreier and Cayley diagrams of x. Both $\mathrm{Schr }_\Phi (x, {\mathcal G})$ and $\mathrm{Cay }_\Phi (x, {\mathcal G})$ are often considered as being rooted with root being the point $x$. If ${\mathcal G}$ is a relation groupoid then $\mathrm{Schr }_\Phi (x, {\mathcal G})$ and $\mathrm{Cay }_\Phi (x, {\mathcal G})$ are naturally identified with each other. The underlying oriented graphs of $\mathrm{Schr }_\Phi (x, {\mathcal G})$ and $\mathrm{Cay }_\Phi (x, {\mathcal G})$ are called Schreier and Cayley graphs and they are denoted by the same symbols.

Let $T$ be a finite sum $\sum _{i=1}^n \phi _i f_i$ (for now purely formal), where $\phi _i$ are measurable edges and $f_i\in L^\infty ({\mathcal G}_0)$, and let $\Phi$ be the sequence $(\phi _1, \ldots , \phi _n)$. The $\mathbb {C}$-diagram $\mathrm{Cay }_T(x, {\mathcal G})$ is obtained from the $\Phi$-diagram $\mathrm{Cay }_\Phi (x, {\mathcal G})$ by replacing each edge labeled $\phi _i$ starting at a vertex ${\alpha }\in {\mathcal G}$ by an edge labeled $f_i\circ r({\alpha })$. Similarly for $\mathrm{Schr }_T(x, {\mathcal G})$ we replace each edge labeled $\phi _i$ starting at a vertex $x\in {\mathcal G}_0$ by an edge labeled $f_i(x)$.

2.2 Groupoid ring

Given a measurable edge $\phi$, define a bounded operator on $L^2 {\mathcal G}$, denoted also by $\phi$, by

$$\begin{aligned} \phi (F)({\gamma }) = \left\{ \begin{array}{ll} F\big ({\gamma }\cdot (\phi ^{-1}\circ r)({\gamma })\big ) &{}\quad \text{ if } \, r({\gamma })\in \mathrm{Dom }(\phi ^{-1}),\\ 0 &{} \quad \text{ otherwise, }\\ \end{array} \right. \end{aligned}$$

(2.1)

where $F\in L^2({\mathcal G})$.

Given $f\in L^\infty ({\mathcal G}_0)$ and $F\in L^2({\mathcal G})$, we define $f(F)\in L^2({\mathcal G})$ to be $f(F)({\alpha }):= (f\circ r)({\alpha }) \cdot F({\alpha })$. This is an action of $L^\infty ({\mathcal G}_0)$ on $L^2({\mathcal G})$.

The groupoid ring of ${\mathcal G}$, denoted by $\mathbb {C}{\mathcal G}$, is the ring of bounded operators on $L^2({\mathcal G})$ generated by measurable edges and $L^\infty ({\mathcal G}_0)$. By Lemma 2.4 below, $\mathbb {C}{\mathcal G}$ is ${}^*$-closed.

Given a measurable edge $\phi$ and a set $U\subset \mathrm{Dom }(\phi )$, we let $\phi _{|U}$ and $\phi _U$ denote the restriction of $\phi$ to $U$.

Lemma 2.4

Let $\phi$ be a measurable edge and $f\in L^\infty ({\mathcal G}_0)$. Then, in $\mathbb {C}G$, we have

• 1. $\phi f = \phi _{|{\mathrm{supp }}(f)\cap \mathrm{Dom }(\phi )} f$,

• 2. If $\mathrm{Dom }(\phi ) \subset U$, and $\chi$ is the characteristic function of $U$ then $\phi \chi = \phi$.

• 3. $\phi ^* = \phi ^{-1}$,

• 4. $\phi f = \phi (f) \phi ,$

where $\phi (f)\in L^\infty ({\mathcal G}_0)$ is defined by the formula

$$\begin{aligned} \phi (f)(x) = \left\{ \begin{array}{ll} (f\circ r\circ \phi ^{-1})(x) &{}\quad \text{ if } \, x\in \mathrm{Dom }(\phi ^{-1}),\\ 0 &{} \quad \text{ otherwise. }\\ \end{array} \right. \end{aligned}$$

(2.2)

Proof

We only prove (4). The other statements are proved similarly and left to the reader as an exercise.

Let $F\in L^2 ({\mathcal G})$. Then $f(F) ({\alpha }) = f\circ r( {\alpha })\cdot F ({\alpha })$ and therefore $\big [(\phi f)(F)\big ] ({\alpha })$ equals

$$\begin{aligned} \begin{array}{ll} (f\circ r)\big ({\alpha }\cdot (\phi ^{-1}\circ r)({\alpha })\big )\cdot F \big ({\alpha }\cdot (\phi ^{-1}\circ r)({\alpha })\big ) &{} \quad \text{ if } r({\alpha }) \in \mathrm{Dom }(\phi ^{-1}),\\ 0 &{} \quad \text{ otherwise. }\\ \end{array} \end{aligned}$$

From (2.1) we get

$$\begin{aligned} \big [(\phi (f)\phi )(F)\big ] ({\alpha }) \!=\!\left\{ \! \begin{array}{ll} \big (\phi (f)\circ r\big )({\alpha }) \cdot F ({\alpha }\cdot (\phi ^{-1}\circ r)({\alpha })) &{}\quad \text{ if } r({\alpha }) \!\in \! \mathrm{Dom }(\phi ^{-1}),\\ 0 &{} \quad \text{ otherwise, }\\ \end{array} \right. \end{aligned}$$

but, from (2.2) we see that, if $r({\alpha }) \in \mathrm{Dom }(\phi ^{-1})$ then $(\phi (f)\circ r)({\alpha }) = (f\circ r\circ \phi ^{-1}\circ r)({\alpha })$, and so the claim follows from noting that $r({\alpha }{\beta })=r({\beta })$ for every composable pair ${\alpha }, {\beta }$ of morphisms.

In particular, each element of $\mathbb {C}{\mathcal G}$ can be (non-uniquely) represented by a finite linear combination of operators $\phi \cdot f$, where $f\in L^\infty ({\mathcal G}_0)$, and $\phi$ is a measurable edge. If $T\in {\mathcal G}$ is represented by $\sum \phi _i f_i$ then we abuse notation by denoting the sum $\sum \phi _i f_i$ also by $T$.

The trace $\tau _{{\mathcal G}}$ on $\mathbb {C}{\mathcal G}$ is defined by the formula

$$\begin{aligned} \tau _ {{\mathcal G}}(T) := \langle T\chi _0, \chi _0 \rangle _{L^2 {\mathcal G}}, \end{aligned}$$

where $\chi _0$ is the characteristic function of ${\mathcal G}_0 \subset {\mathcal G}$. It is positive, faithful and normal.

2.3 Action groupoids and Pontryagin duality

Let ${\Gamma }$ be a discrete countable group, $(X,\mu )$ be a probability measure space and $\rho :{\Gamma }{\curvearrowright }X$ be a right measure preserving action, which is not necessarily free. The action groupoid ${\mathcal G}(\rho )$ is a measured groupoid whose space of objects is $X$, and whose space of morphisms is $X\times {\Gamma }$. The structure maps are given by $s(x,{\gamma }) =x$, $r(x,{\gamma }) = \rho ({\gamma })(x)$. Composition of $(x, {\alpha })$ and $(\rho ({\alpha })(x), {\beta })$ is $(x, {\alpha }{\beta })$. The inverse of $(x,{\gamma })$ is $(\rho ({\gamma })(x), {\gamma }^{-1})$.

Each element ${\gamma }\in {\Gamma }$ gives rise to a measurable edge $x\mapsto (x,{\gamma })$, denoted also by ${\gamma }$, whose domain of definition is all of $X$.

For the rest of this subsection, $(X, \mu )$ is a compact abelian group with the normalized Haar measure and the action $\rho :{\Gamma }{\curvearrowright }X$ is by continuous group automorphisms. The action ${\widehat{\rho }}$ of ${\Gamma }$ on the Pontryagin dual ${\widehat{X}}$ of $X$ is defined as ${\widehat{\rho }}({\gamma }) (f) (x) = f(\rho ({\gamma }^{-1})(x))$, where $f:X \rightarrow \mathbb {C}$ is an element of ${\widehat{X}}$.

For more information on Pontryagin duality see e.g. [11]. In particular, Pontryagin duality induces a map $P:{\widehat{X}} \rightarrow L^\infty (X)$. If ${\widehat{x}} \in {\widehat{X}}$ then $P({\widehat{x}})$ is denoted also by $x$.

Proposition 2.5

There is a trace-preserving ${}^*$-embedding of the complex group ring $\mathbb {C}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$ into the groupoid ring $\mathbb {C}{\mathcal G}(\rho )$, which sends $f\in {\widehat{X}}$ to $P(f)$, and ${\gamma }\in {\Gamma }$ to a measurable edge ${\gamma }$. This embedding will be denoted by $P\otimes 1$.

In particular, if $T=T^* \in \mathbb {C}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$, then $T$ and $P\otimes 1(T)$ have the same spectral measures.

Proof

To begin with, we show that the map $\sum c_i \cdot {\widehat{a}}_i \cdot {\gamma }_i \mapsto \sum c_i\cdot a_i \cdot {\gamma }_i$, $c_i \in \mathbb {C}$, ${\widehat{a}}_i\in {\widehat{X}}$, ${\gamma }_i \in {\Gamma }$, is a ring homomorphism. It is well-defined, since every element of $\mathbb {C}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$ can be written in a unique way as $\sum c_i \cdot {\widehat{a}}_i \cdot {\gamma }_i$. It certainly is a ring homomorphism when restricted to $\mathbb {C}{\Gamma }$ and to $\mathbb {C}{\widehat{X}}$. The standard presentation of a semi-direct product and Lemma 2.4(4) imply that it is a homomorphism on all of $\mathbb {C}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$.

Lemma 2.4(3) implies that the ${}^*$-operation is preserved.

By linearity, it is enough to check the trace-preservation on an element of the form ${\widehat{a}} \cdot {\gamma }\in \mathbb {C}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$, where ${\widehat{a}} \in {\widehat{X}}$, ${\gamma }\in {\Gamma }$. The group ring trace of ${\widehat{a}} \cdot {\gamma }$ is equal to $1$ if ${\widehat{a}}$ and ${\gamma }$ are the neutral elements of ${\widehat{X}}$ and ${\Gamma }$ respectively, and is equal to $0$ otherwise.

We consider three cases.

• (1) Both ${\widehat{a}}$ and ${\gamma }$ are the neutral elements. Then $a$ is the function on $X$ constantly equal to $1$ and $\tau _{{\mathcal G}(\rho )}(P\otimes 1({\widehat{a}} \cdot {\gamma })) = \langle \chi _0, \chi _0 \rangle = 1$.

• (2) ${\gamma }$ is not the neutral element. Then the functions $\chi _0$ and ${\gamma }(\chi _0)$ have disjoint supports and, therefore, also $\chi _0$ and $(a{\gamma })(\chi _0)$ have disjoint supports, so $\langle (a{\gamma })(\chi _0), \chi _0 \rangle = 0$.

• (3) ${\gamma }$ is the neutral element, but ${\widehat{a}}$ is not. Then, it follows from Pontryagin duality that $a$ is a non-constant function on ${\mathcal G}_0$, and the trace we have to compute is equal to $\langle a, \chi _0 \rangle = \int a\, d\mu$. Let $x, y\in {\mathcal G}_0$ with $a(x) \ne a(y)$. We use that $a$ is a group homomorphism and invariance of Haar measure to get

  $$\begin{aligned} \int a(z) \, d\mu (z) = \int a(xz) \, d\mu (z) = a(x)\int a(z) \, d\mu (z). \end{aligned}$$

  Repeating with $y$ in place of $x$ we obtain $a(x)\int a(z) \, d\mu (z)=a(y)\int a(z) d\mu (z)$, which is possible only if $\int a(z) \, d\mu (z) = 0$.

The statement about the spectral measures follows from Lemma 1.9.

Lemma 2.6

Let $\mathbb {Z}(\frac{1}{2})$ be the subring of $\mathbb {Q}$ generated by $\mathbb {Z}$ and $\frac{1}{2}$. If $X$ is a product of infinitely many copies of $\,\mathbb {Z}{/2\mathbb {Z}}\,$ indexed by a set $I$, then the image of $\mathbb {Z}(\frac{1}{2}) ({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$ under $P\otimes 1$ is generated over $\mathbb {Z}(\frac{1}{2})$ by measurable edges ${\gamma }\in {\Gamma }$ and the characteristic functions of cylinder sets.

Proof

Let $R\subset \mathbb {C}{\mathcal G}$ be the ring generated by characteristic functions of cylinder sets and measurable edges ${\gamma }\in {\Gamma }$.

First, we show that image of $\mathbb {Z}(\frac{1}{2}) ({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma })$ is contained in $R$. Clearly, $(P\otimes 1)({\Gamma }) \subset R$. Note that ${\widehat{X}}$ is a direct sum of infinitely many copies of $\,\mathbb {Z}{/2\mathbb {Z}}\,$ indexed by $I$. Let $g_i$ be the generator of $\,\mathbb {Z}{/2\mathbb {Z}}\,$ corresponding to the index $i\in I$. Direct computation shows that $P\otimes 1( \frac{e+g_i}{2})$ is the characteristic function of the cylinder set $\{(x_j)\in \prod _I \,\mathbb {Z}{/2\mathbb {Z}}\,:x_i = 0\}$. Also $P\otimes 1 (e)$ is a characteristic function of a cylinder set (namely, of the whole $X$). The statement follows, since $\mathbb {Z}(\frac{1}{2}) ({\widehat{X}})$ is generated, as a $\mathbb {Z}(\frac{1}{2})$-ring, by $\frac{e+g_i}{2}$ and $e$.

In the other direction, we just saw that the characteristic functions of cylinder sets $\{(x_j)\in \prod _I \,\mathbb {Z}{/2\mathbb {Z}}\,:x_i = 0\}$ are in the image. Since the constant function $1$ is also in the image, it follows that characteristic function of $\{(x_j)\in \prod _I \,\mathbb {Z}{/2\mathbb {Z}}\,:x_i = 1\}$ is in the image as well. Every cylinder set is an intersection of sets of those two types, so the claim follows.

2.4 Groupoid ring and convolution operators on random diagrams

For definitions and notation on direct integrals of spaces and operators see [11], Chapter 7.4. Unless explicitly stated otherwise, all integrals are taken over the space ${\mathcal G}_0$.

Consider the field $x \mapsto l^2(s^* x)$ of Hilbert spaces over ${\mathcal G}_0$. For a measurable edge $\phi$, define a section $S_\phi$, by

$$\begin{aligned} S_\phi (x) = \left\{ \begin{array}{ll} 0 &{} \quad \text{ if } \, x\notin \mathrm{Dom }(\phi )\\ \zeta _{\phi (x)} &{} \quad \text{ otherwise }\\ \end{array} \right. \end{aligned}$$

Let $\psi _i$ be a countable family of measurable edges from Lemma 2.3. We make $l^2(s^*x)$ into a measurable field by equipping it with the family of sections $S_{\psi _i}$.

Given $T\in \mathbb {C}{\mathcal G}$ represented by a finite sum $\sum _{i=1}^n \phi _i \cdot f_i$, we define a field of operators $T_x :l^2 (s^*x) \rightarrow l^2 (s^*x)$ by setting $T_x$ to be the convolution operator on the diagram $\mathrm{Cay }_T(x, {\mathcal G})$. The following proposition says that the spectral measure of $T$ is equal to the expected rooted spectral measure of the convolution operator $T_x$ on the random diagram $\mathrm{Cay }_T(x,{\mathcal G})$.

Proposition 2.7

There is an isomorphism of Hilbert spaces $L^2({\mathcal G})$ and

$$\begin{aligned} \int ^\oplus l^2( s^*x) \, d\mu (x) \end{aligned}$$

which sends a function $F:{\mathcal G} \rightarrow \mathbb {C}$ to a section

$$\begin{aligned} x \mapsto \sum _{{\gamma }\in s^*x} F({\gamma })\cdot \zeta _{\gamma }. \end{aligned}$$

(2.3)

Under this isomorphism elements of $\mathbb {C}{\mathcal G}$ are decomposable. Operator $T\in \mathbb {C}{\mathcal G}$ corresponds to the operator $\int ^\oplus T_x \, d\mu (x)$. Furthermore,

$$\begin{aligned} \tau _{{\mathcal G}}(T) = \int \langle T_x( \zeta _x), \zeta _x\rangle _{l^2(s^*x)} \, d\mu (x). \end{aligned}$$

Proof

The statements about the decomposition of $T$ and the trace follow from the formula (2.3) through a direct computation.

We need to check (i) that the formula (2.3) defines a measurable element of the field $\int ^\oplus l^2( s^*x) \, d\mu (x)$, (ii) that this field is square-summable, and that the resulting map of Hilbert spaces is (iii) isometric and (iv) surjective.

(i) For each measurable edge $S_\phi$ we need to check that the function

$$\begin{aligned} x\mapsto \langle S_\phi (x), \sum _{{\gamma }\in s^*x} F({\gamma })\cdot \zeta _{\gamma }\rangle _{l^2s^*x} \end{aligned}$$

is measurable. By definition of $S_\phi$, this function is non-zero only on $\mathrm{Dom }(\phi )$, where it is equal to

$$\begin{aligned} \langle \zeta _{\phi (x)}, \sum _{{\gamma }\in s^*x} F({\gamma })\cdot \zeta _{\gamma }\rangle _{l^2s^*x}, \end{aligned}$$

which is equal to $F(\phi (x))$.

(ii) and (iii) Due to Lemma 2.3, we have

$$\begin{aligned} \langle F, F \rangle _{L^2 {\mathcal G}} = \int _{{\mathcal G}} |F({\gamma })|^2 \, d\mu ({\gamma }) = \int \sum _{{\gamma }\in s^*x} | F({\gamma })|^2 \,d\mu (x), \end{aligned}$$

which is equal to

$$\begin{aligned} \int \left\langle \sum _{{\gamma }\in s^*x} F({\gamma })\cdot \zeta _{\gamma }, \sum _{{\gamma }\in s^*x} F({\gamma })\cdot \zeta _{\gamma }\right\rangle _{l^2s^*x} \, d\mu (x). \end{aligned}$$

(iv) Let an element of $\int ^\oplus l^2( s^*x) \, d\mu (x)$ be given by a measurable section $F(x)\in l^2(s^*x)$. Define $F \in L^2({\mathcal G}_0)$ as $F({\gamma }) = \langle F(s({\gamma })), \zeta _{\gamma }\rangle$. By (2.3), the image of $F$ is the section $F(x)$.

2.5 Subgroupoids

Let $\Phi = (\phi _1, \ldots )$ be a sequence of measurable edges. The subgroupoid generated by $\varvec{\Phi }$, denoted by ${\mathcal G} (\Phi )$, is the discrete measured groupoid whose space of objects is equal to ${\mathcal G}_0$ and whose morphisms are generated by all morphisms in the images of $\phi _i$, $\phi _i^{-1}$, and by all identity morphisms.

A subgroupoid of a groupoid is a subgroupoid generated by a sequence of measurable edges.

Proposition 2.8

Let ${\mathcal H}$ be a subgroupoid of ${\mathcal G}$. Note that if $\phi$ is a measurable edge in ${\mathcal H}$, then it is also a measurable edge in ${\mathcal G}$. Similarly, elements of $L^\infty {\mathcal H}_0$ are at the same time elements of $L ^\infty {\mathcal G}_0$. These two identifications extend to a trace-preserving ${}^*$-embedding $\mathbb {C}{\mathcal H} \hookrightarrow \mathbb {C}{\mathcal G}$.

Proof

Let $T\in \mathbb {C}{\mathcal H}$ be represented by a finite sum $\sum _{i=0}^n \phi _i f_i$, and let $\Phi$ be the sequence $(\phi _1, \ldots , \phi _n)$. Let $S\in \mathbb {C}{\mathcal G}$ be represented by the same finite sum. By Proposition 2.7 and the remark before, $\tau _{{\mathcal H}} (T)$ is the expected rooted spectral measure of the convolution operator on the diagram $\mathrm{Cay }_T(x, {\mathcal H}(\Phi ))$, and $\tau _{{\mathcal G}} (S)$ is the expected rooted spectral measure of the convolution operator on the diagram $\mathrm{Cay }_S(x, {\mathcal G}(\Phi ))$. But those two diagrams have isomorphic connected components of the root, and the rooted spectral measure depends only on the connected component of the root, and so $\tau _{{\mathcal H}} (T)= \tau _{{\mathcal G}} (S)$.

Therefore, we have a map from the set of finite sums representing elements of $\mathbb {C}{\mathcal H}$ to the set of finite sums representing elements of $\mathbb {C}{\mathcal G}$, which is trace preserving and ${}^*$-preserving. It follows that this map induces a well-defined linear ${}^*$-embedding of $\mathbb {C}{\mathcal H}$ into $\mathbb {C}{\mathcal G}$ because both $\tau _{{\mathcal H}}$ and $\tau _{{\mathcal G}}$ are faithful.

Corollary 2.9

Let $T^*=T\in \mathbb {C}{\mathcal G}$ be represented by a sum $\sum _{i=1}^n \phi _i f_i$, and let $\Phi =(\phi _1, \ldots , \phi _n)$. Then $T$ is in the image of the embedding $\mathbb {C}{\mathcal G} (\Phi ) \hookrightarrow \mathbb {C}{\mathcal G}$, and the corresponding element of $\mathbb {C}{\mathcal G}(\Phi )$ is also denoted by $T$. The spectral measure of $T$ in $\mathbb {C}{\mathcal G}(\Phi )$ is the same as the spectral measure of $T$ in $\mathbb {C}{\mathcal G}$.

Proof

Follows from Lemma 1.9

2.6 Finite groupoids

A groupoid ${\mathcal G}$ is finite if for almost all points $x\in {\mathcal G}_0$ the set $s^*x$ is finite. We say that a groupoid ${\mathcal G}$ has finite orbits, if almost all points in ${\mathcal G}_0$ have finite orbits. Note that a relation groupoid with finite orbits is finite, and that a finite groupoid has finite orbits.

In particular if ${\mathcal G}$ is a finite groupoid, then there exists a fundamental domain, i.e. a measurable subset $D\subset {\mathcal G}_0$ such that every finite orbit intersects $D$ exactly once.

Proposition 2.10

Let ${\mathcal G}$ be a finite groupoid, and let $D$ be a fundamental domain of ${\mathcal G}$. There is a ${}^*$-representation of $\mathbb {C}{\mathcal G}$ on $\int _D^\oplus l^2(s^*x) \, d\mu (x)$, which sends an operator $T \in \mathbb {C}{\mathcal G}$ to

$$\begin{aligned} \int _D^\oplus T_x \, d\mu (x). \end{aligned}$$

Under this representation

$$\begin{aligned} \tau _{{\mathcal G}} (T) = \int _D \frac{\mathrm{tr }(T_x)}{|\mathrm{St }(x,{\mathcal G})|} \, d\mu (x). \end{aligned}$$

In particular

$$\begin{aligned} \dim _\text {vN}\ker T = \int _D \frac{\dim \ker T_x}{|\mathrm{St }(x, {\mathcal G})|} \,d\mu (x). \end{aligned}$$

Proof

Let $D^c$ be the complement of $D$. We have the direct sum decomposition

$$\begin{aligned} \int ^\oplus l^2(s^*x) \, d\mu (x) = \int _D^\oplus l^2(s^*x) \, d\mu (x) \oplus \int _{D^c}^\oplus l^2(s^*x) \, d\mu (x), \end{aligned}$$

and the corresponding decomposition of the operator $T$:

$$\begin{aligned} \int T_x \, d\mu (x) = \int _D^\oplus T_x \, d\mu (x) \oplus \int _{D^c}^\oplus T_x \, d\mu (x). \end{aligned}$$

It follows that $T \mapsto \int _D^\oplus T_x$ is a ${}^*$-representation. Thus, we need only to show the statement about the trace. The right hand side is equal to

$$\begin{aligned} \int _D \sum _{{\gamma }\in s^*x} \frac{1}{|\mathrm{St }(x,{\mathcal G})|}\langle T_x\zeta _{\gamma }, \zeta _{\gamma }\rangle \, d\mu (x). \end{aligned}$$

Note that for all $x\in {\mathcal G}_0$ and ${\alpha }\in G$ such that $r({\alpha })=x$ we have $\langle T_x \zeta _{\gamma }, \zeta _{\gamma }\rangle = \langle T_{s(x)}\zeta _{{\alpha }{\gamma }}, \zeta _{{\alpha }{\gamma }}$, therefore, by putting ${\alpha }= i({\gamma })$, the above is equal to

$$\begin{aligned} \int _D \sum _{{\gamma }\in s^*x} \frac{1}{|\mathrm{St }(x,{\mathcal G})|}\langle T_{r({\gamma })}\zeta _{r({\gamma })}, \zeta _{r({\gamma })} \rangle \, d\mu (x), \end{aligned}$$

which is the same as

$$\begin{aligned} \int _D \sum _{y\in {\mathcal G}x} \langle T_{y}\zeta _y, \zeta _y \rangle \, d\mu (x), \end{aligned}$$

which, by Lemma 2.1 and the definition of fundamental domain, equals

$$\begin{aligned} \int _{{\mathcal G}_0} \langle T_{x} \zeta _x, \zeta _x \rangle \, d\mu (x) = \tau _{{\mathcal G}} (T). \end{aligned}$$

The “in particular” statement follows from Lemma 1.9.

Corollary 2.11

Let ${\mathcal G}$ be a finite groupoid and let $T\in \mathbb {C}{\mathcal G}$. Then

$$\begin{aligned} \tau _{{\mathcal G}}(T) = \int \frac{1}{|{\mathcal G}x||\mathrm{St }(x,{\mathcal G})|} \mathrm{tr }(T_x) \,d\mu (x)= \int \frac{1}{|s^*x|} \mathrm{tr }(T_x) \,d\mu (x). \end{aligned}$$

Proof

The second equality is clear. The first one follows from the proposition and Lemma 2.2 for $A={\mathcal G}_0$, $B=D$ and $f(x)=\mathrm{tr }(T_x)$.

3 Examples

We show how Proposition 2.10 and Corollary 2.11 generalize known computations of spectra of random walk operators.

3.1 Computation of Grigorchuk and Żuk

We start by computing the von Neumann dimension of the kernel of a random walk operator on the group $\,\mathbb {Z}{/2\mathbb {Z}}\, \wr \mathbb {Z}$. This was originally done, by different methods, by Grigorchuk and Żuk in [15]. Compare also [6].

The lamplighter group $\,\mathbb {Z}{/2\mathbb {Z}}\, \wr \mathbb {Z}$ is defined as $\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}} \rtimes \mathbb {Z}$, where the action of $\mathbb {Z}$ on $\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}}$ is by the shift, i.e. $[t((x_i))]_j = x_{j+1}$,

Let $X=\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}$. Given ${\varepsilon }_{-k}, \ldots , {\varepsilon }_l \in \,\mathbb {Z}{/2\mathbb {Z}}\,$, the set

$$\begin{aligned} \{(x_i)\in X:x_{-k} = {\varepsilon }_{-k}, \ldots , x_l = {\varepsilon }_l \} \end{aligned}$$

is denoted by $[{\varepsilon }_{-k}\,\ldots \,\underline{{\varepsilon }_0}\,\ldots \,{\varepsilon }_l]$ and its characteristic function is denoted by

$$\begin{aligned} \chi [{\varepsilon }_{-k}\,\ldots \,\underline{{\varepsilon }_0}\,\ldots \,{\varepsilon }_l]. \end{aligned}$$

Similarly the set $\{(x_i)\in X:x_{-1}=0\}$ is denoted by $[0\underline{\,\cdot \,}]$ and its characteristic function by $\chi [0\underline{\,\cdot \,}]$. Concrete elements from the set $[{\varepsilon }_{-k}\,\ldots \,\underline{{\varepsilon }_0}\,\ldots \,{\varepsilon }_l]$ are denoted by $({\varepsilon }_{-k}\,\ldots \,\underline{{\varepsilon }_0}\,\ldots \,{\varepsilon }_l)$.

Theorem 3.1

[15] Let $T$ be the element in the rational group ring of the lamplighter group given by $T = \frac{1}{2}(t + t^{-1} + tg + gt^{-1})$, where $t$ is the generator of $\mathbb {Z}$, and $g \in \,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}}$ is a characteristic function $\mathbb {Z}\rightarrow \,\mathbb {Z}{/2\mathbb {Z}}\,$ of $\{0\} \subset \mathbb {Z}$. Then $\dim _\text {vN}\ker T = \frac{1}{3}$.

Proof

Let $X = \{0,1\}^\mathbb {Z}$ with the standard product measure, and let $\rho :\mathbb {Z}\, {\curvearrowright }X$ be the Bernoulli shift action, i.e. $[\rho (t)((x_i))]_j = x_{j+1}$, where $t$ is the distinguished generator of $\mathbb {Z}$. Let ${\mathcal G}$ denote the action groupoid ${\mathcal G}(\rho )$

Note that $T = t \cdot \frac{1+g}{2} + t^{-1}\cdot \frac{1+t(g)}{2}$, and that the Pontryagin dual of $\frac{1+g}{2}$ is $\chi [\,\underline{0}\,]$ and of $\frac{1+t(g)}{2}$ is $\chi [0\underline{\,\cdot \,}]$. Therefore, by Proposition 2.5, the spectral measure of $T$ is the same as the spectral measure of the operator $t_{[\,\underline{0}\,]} + t^{-1}_{[0\underline{\,\cdot \,}]} \in \mathbb {C}{\mathcal G}$. Let us call the latter operator $T$ as well and let $\Phi$ be the sequence $(t_{[\,\underline{0}\,]}, t^{-1}_{[0\underline{\,\cdot \,}]})$ of measurable edges.

The set

$$\begin{aligned} D := [1\underline{1}] \cup \bigcup _{k>1} [1\underline{0} 0^{k-1}1] \end{aligned}$$

is a fundamental domain for ${\mathcal G}(\Phi )$. For $x\in (1\underline{0} 0^{k-1}1)$ the Schreier graph $\mathrm{Schr }_T(x, {\mathcal G}(\Phi ))$ is

$$\begin{aligned} \bullet \leftrightarrows \bullet \leftrightarrows \cdots \leftrightarrows \bullet \leftrightarrows \bullet \end{aligned}$$

with $k$ vertices. The kernel of the convolution operator is $1$-dimensional if $k$ is odd and $0$-dimensional otherwise. For $x\in [1\underline{]}$, the Schreier graph consists of one vertex and no edges, and so the kernel of the convolution operators is $1$-dimensional.

Applying Proposition 2.10 we get

$$\begin{aligned} \dim _\text {vN}\ker T = \frac{1}{4}+\sum _{k>1,\ 2|k\,} \frac{1}{2^{k+2}} = \sum _{l=0}^\infty \frac{1}{2^{2l+2}} = \frac{1}{3}. \end{aligned}$$

If we put more effort into computing the spectra of the convolution operators on the Schreier graphs in the proof, we could compute the whole spectral measure of $T$ (see [6, 15]).

3.2 Percolation theory, theorem of Lehner, Neuhauser and Woess

We now present a theorem of Lehner, Neuhaser and Woess from [18].

Let ${\Gamma }$ be a finitely generated group, $\Psi =({\gamma }^1,\ldots , {\gamma }^n)$ be a finite sequence of generators for ${\Gamma }$ which is symmetric, i.e. for each ${\gamma }\in {\Gamma }$ the number of times ${\gamma }$ appears in $\Psi$ is equal to the number of times ${\gamma }^{-1}$ appears in $\Psi$. Let ${\mathcal C}$ be the associated directed Cayley graph. An animal is a full connected subgraph of ${\mathcal C}$ which contains the neutral element $e\in {\Gamma }$. The root of an animal is defined to be the neutral element $e\in {\Gamma }$. For an animal ${\mathcal L}$ let us put

$$\begin{aligned} {\partial }_\Psi {\mathcal L} := \{{\alpha }\in V({\mathcal C})-V({\mathcal L}):\exists {\beta }\in V({\mathcal L}) \text { such that there is an edge from } {\alpha }\; \text {to}\; {\beta }\}. \end{aligned}$$

Given a point $x \in \,\mathbb {Z}{/p\mathbb {Z}}\,^{\Gamma }$ let ${\mathcal C}_0(x)$ be the full subgraph of ${\mathcal C}$ with $V({\mathcal C}_0(x))=\{{\alpha }\in {\Gamma }:x({\alpha }) =0\}$, and let ${\mathcal L}(x)$ be the animal whose set of vertices is equal to the connected component of ${\mathcal C}_0(x)$ containing $e\in {\Gamma }$ (if $e\notin {\mathcal C}_0G$ then ${\mathcal L}(x)$ is the empty animal).

Let $T_{{\mathcal L}}$ denote the (oriented) convolution operator $l^2 {\mathcal L} \rightarrow l^2 {\mathcal L}$.

For $q\in [0,1]$, let $\nu _q$ denote the product measure on $\,\mathbb {Z}{/p\mathbb {Z}}\,^{\Gamma }$ of a fixed measure $\nu$ on $\,\mathbb {Z}{/p\mathbb {Z}}\,$ such that $\nu (\{0\}) = q$, $\nu (\{1,2,\ldots , p-1\})=1-q$. We say that a parameter $q$ is subcritical for ${\Gamma }$ with respect to $\Psi$ if animals ${\mathcal L}(x)$ are $\nu _q$-almost surely finite. Subcriticality does not depend on $p$ or a choice of $\nu$. For example, for the free group $F_k$ with the standard generating set every $q<\frac{1}{2k-1}$ is subcritical. See [3] for more information on percolation theory.

Theorem 3.2

[18] Let $G = \,\mathbb {Z}{/p\mathbb {Z}}\, \wr {\Gamma }$, let $\pi \in \mathbb {Q}\,\mathbb {Z}{/p\mathbb {Z}}\,$ be the projection $\pi := \frac{1}{p}\cdot \sum _{a\in \,\mathbb {Z}{/p\mathbb {Z}}\,} a$, let $T\in \mathbb {Q}G$ be defined as

$$\begin{aligned} T := \pi \cdot \left( \sum _{i=1}^n {\gamma }^i \right) \cdot \pi . \end{aligned}$$

Suppose that the parameter $\frac{1}{p}$ is subcritical for ${\Gamma }$ with respect to $\Psi$. Then the spectral measure of $T$ is pure-point and

$$\begin{aligned} \dim _\text {vN}\ker T = \sum _{{\mathcal L}} \frac{1}{|{\mathcal L}|}\cdot \left( \frac{1}{p}\right) ^{|{\mathcal L}|} \cdot \left( \frac{p-1}{p}\right) ^{|{\partial }_\Psi {\mathcal L}|} \cdot \dim \ker T_{{\mathcal L}}, \end{aligned}$$

where the sum is over all finite animals.

Proof

Let $X = \,\mathbb {Z}{/p\mathbb {Z}}\,^{\Gamma }$ with the normalized Haar measure $\mu$ and let the action $\rho :{\Gamma }{\curvearrowright }X$ be the Bernoulli shift, i.e.

$$\begin{aligned}{}[\rho ({\gamma })(x_{\alpha })]_{\beta }:= x_{{\beta }{\gamma }}. \end{aligned}$$

The action groupoid ${\mathcal G}(\rho )$ is denoted by ${\mathcal G}$.

For ${\gamma }\in {\Gamma }$ let $[\underline{0}\xrightarrow {{\gamma }}0] \subset X$ be the set $\{f\in X:f(e) = 0, f({\gamma })=0\}$ and $\chi [\underline{0}\xrightarrow {{\gamma }}0]$ be its characteristic function. Computation shows that the image of $T$ under the Pontryagin duality map $P\otimes 1:\mathbb {Q}(\,\mathbb {Z}{/p\mathbb {Z}}\, \wr {\Gamma }) \rightarrow \mathbb {C}{\mathcal G}(\rho )$ is the element

$$\begin{aligned} \sum _{i=1}^n {\gamma }^i \cdot \chi [\underline{0}\xrightarrow {{\gamma }}0], \end{aligned}$$

which we also denote by $T$. Let $\Phi$ be the sequence of ${\gamma }_i$ of measurable edges defined as ${\gamma }^i$ restricted to the set $[\underline{0}\xrightarrow {{\gamma }^i}0]$. For an animal ${\mathcal L}$ define

$$\begin{aligned} X({\mathcal L}) = \{x\in X: {\mathcal L}(x) = {\mathcal L}\}. \end{aligned}$$

and note

$$\begin{aligned} \mu (X({\mathcal L})) = \left( \frac{1}{p}\right) ^{|{\mathcal L}|} \cdot \left( \frac{p-1}{p}\right) ^{|{\partial }_\Psi {\mathcal L}|}, \end{aligned}$$

since for a point $x$ being in $X({\mathcal L})$ means $x({\alpha }) = 0$ for ${\alpha }\in V({\mathcal L})$ and $x({\alpha }) \ne 0$ for ${\alpha }\in {\partial }_\Psi {\mathcal L}$. The sets $X({\mathcal L})$ are disjoint for different animals and by subcriticality

$$\begin{aligned} \mu \left( \bigcup _{\text {finite } {\mathcal L}} X({\mathcal L})\right) = 1. \end{aligned}$$

Computation shows that for a point $x\in X({\mathcal L})$ the Schreier graph $\mathrm{Schr }_\Phi (x,{\mathcal G}(\Phi ))$ is isomorphic to ${\mathcal L}$. It follows that under this isomorphism $T_x$ corresponds to $T_{{\mathcal L}}$, because both operators are the convolution operators. In particular the groupoid ${\mathcal G}$ is finite, so Corollary 2.11 gives us

$$\begin{aligned} \dim _\text {vN}\ker T = \int \frac{1}{|{\mathcal G}x|} \dim \ker T_x \,d\mu (x) = \sum _{{\mathcal L}} \frac{1}{|{\mathcal L}|}\cdot \int _{X({\mathcal L})} \dim \ker T_{{\mathcal L}} \,d\mu (x), \end{aligned}$$

where the sum is over all finite animals. This shows the statement about $\dim _\text {vN}\ker T$.

The spectral measure of $T$ is pure-point because $T$ is similar to the operator $\oplus _{{\mathcal L}} T_{{\mathcal L}}$, were the sum is again over all finite animals.

The author was informed by Franz Lehner that it is an open problem to determine whether $\frac{1}{p} > q_c$ implies that the continuous part appears in the spectral measure of the operator $T$ above, even for groups ${\Gamma }=\mathbb {Z}^k$, $k>1$. Surprisingly to the author, a conjecture in mathematical physics states that for $k=2$ the continuous part does not appear.

4 Turing dynamical systems

4.1 Definitions and basic properties

Let $(X, \mu )$ be a probability measure space and $\rho :{\Gamma }\curvearrowright X$ be a right probability measure preserving action of a countable discrete group ${\Gamma }$ on $X$. A dynamical hardware is the following data: $(X,\mu )$, the action $\rho$, and a division $X = \bigcup _{i=1}^n X_i$ of $X$ into disjoint measurable subsets. For brevity, we denote such a dynamical hardware by $(X)$.

Suppose now that we are given a dynamical hardware $(X)$ and we choose three additional distinguished disjoint subsets of $X$, each of which is a union of certain $X_i$’s: the initial set $I$, the rejecting set $R$, and the accepting set $A$ (all or some of them might be empty). Furthermore, suppose that for every set $X_i$, we choose one element ${\gamma }_i$ of the group ${\Gamma }$ in such a way that the elements corresponding to the sets $X_i$ which are subsets of $R\cup A$ are equal to the neutral element of ${\Gamma }$.

Define a map $T_X: X\rightarrow X$ by

$$\begin{aligned} T_X(x):= \rho ({\gamma }_i)(x) \quad \text { for } x\in X_i. \end{aligned}$$

A dynamical software for a given dynamical hardware $(X)$ is the following data: the distinguished sets $I, A$ and $R$, the choice of elements ${\gamma }_i$, and the map $T_X$, subject to the conditions above. The map $T_X$ will be called the Turing map, and the whole dynamical software will be denoted by $(T_X)$. A Turing dynamical system is a dynamical hardware $(X)$ together with a dynamical software $(T_X)$ for $(X)$. We will denote such a Turing dynamical system by $(X, T_X)$.

Proposition 4.1

In any Turing system $(X,T_X)$, the Turing map $T_X$ is measure-contracting, i.e., for every measurable set $U\subset X$ the set $T_X(U)$ is measurable and $\mu (T_X(U)) \le \mu (U)$. If $T_X$ is injective on $U$ then $\mu (T_X(U)) = \mu (U)$.

Proof

$T_X(U)$ is measurable since $T_X$ is finite-to-one and measurable.

Define $U_i:= U\cap X_i$. By the definition of $T_X$, we have that $T_X(U_i)=\rho ({\gamma }_i) (U_i)$. But all the maps $\rho ({\gamma }_i)$ are measure-preserving, and so the claim follows.

Let $(X,T_X)$ be a Turing dynamical system. If $x\in X$ is such that for some $k$ we have $T_X^k(x)= T_X^{k+1}(x)$ then put $T_X^\infty (x):= T_X^k(x)$. Otherwise leave $T_X^\infty$ undefined.

The first fundamental set, or simply the fundamental set of $(X,T_X)$ is the subset ${\mathcal F}_1(T_X)$ of $I$ consisting of all those points $x$ such that $T^\infty (x) \in A$ and for no point $y\in X$ one has $T_X(y)=x$. The second fundamental set of $(X,T_X)$ is the subset ${\mathcal F}_2(T_X):= T^\infty ({\mathcal F}_1(T_X))$. Both the first and the second fundamental set of $(X,T_X)$ are measurable. Indeed, for example, the first fundamental set is nothing but

$$\begin{aligned} \bigcup _{i=1}^\infty (T_X^{-i}(A)\cap I)-T_X(X), \end{aligned}$$

and $T_X(X)$ is measurable by Proposition 4.1. Therefore, we define the first fundamental value, or simply the fundamental value, of $(X,T_X)$ as the measure of its first fundamental set, and similarly for the second fundamental value. They are denoted by ${\Omega }_1(T_X)$ and ${\Omega }_2(T_X)$.

We say that $(X,T_X)$ stops on any configuration, if for almost any $x$ $T_X^\infty (x)\ A\cup R$; it has disjoint accepting chains, if for almost all different points $x, y\in {\mathcal F}_1(T_X)$ we have $T^\infty (x) \ne T^\infty (y)$; finally it does not restart, if $\mu (T_X(X)\cap I)=0$.

Proposition 4.2

If $(X,T_X)$ has disjoint accepting chains, then ${\Omega }_1 = {\Omega }_2$.

Proof

By assumption, the map $T_X^\infty :{\mathcal F}_1 \rightarrow {\mathcal F}_2$ is injective almost everywhere. We can express ${\mathcal F}_1$ as a countable disjoint union

$$\begin{aligned} {\mathcal F}_1 = \bigcup _{i=1}^\infty T_X^{-i}({\mathcal F}_2)\cap {\mathcal F}_1, \end{aligned}$$

and it is clear that $T_X^\infty$ restricted to $T_X^{-i}({\mathcal F}_2)\cap {\mathcal F}_1$ is equal to $T_X^i$. Therefore, the claim follows by Proposition 4.1.

4.2 Expressing the fundamental values as von Neumann dimensions

Let $(X,T_X)$ be a Turing dynamical system. Let ${\mathcal G}$ denote the groupoid ${\mathcal G}(\rho )$ and define $T$ to be an element of the groupoid ring $\mathbb {C}{\mathcal G}$ given by $T:= \sum _{i=1}^n {\gamma }_i\chi _i$, where $\chi _i$’s are characteristic functions of the respective $X_i$’s.

Given two operators $A$ and $B$ on a Hilbert space, note that $\ker A^*A + B^*B =\ker A \cap \ker B$.

Let $S\in \mathbb {C}{\mathcal G}$ be defined as

$$\begin{aligned} S:= (T+ \chi _X - \chi _I - \chi _A - \chi _R)^*(T+ \chi _X - \chi _I - \chi _A - \chi _R) + \chi _A. \end{aligned}$$

Theorem 4.3

If $(X, T_X)$ stops on any configuration and doesn’t restart then $\dim _\text {vN}\ker S$ is equal to $\mu (I) - {\Omega }_2(T_X)$.

Proof

Let $\Phi$ be the sequence ${{\gamma }_i}_{|X_i}$ of measurable edges. In order to use Proposition 2.10 we show that ${\mathcal G}(\Phi )$ is a relation groupoid with finite orbits.

Lemma

• (1) The orbit ${\mathcal G}(\Phi )x$ of almost any point $x$ is finite.

• (2) For almost every point $x$ the $\Phi$-diagram $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$ is a tree with one self-loop labeled by the neutral element of ${\Gamma }$ restricted to some set.

Proof

Note that in $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$ there is an oriented edge between two points $y$ and $z$ precisely when $T_X(y) = z$. Therefore the second statement follows.

Let $X^0\subset X$ be the set of fixed points of $T_X$. Since the system is strongly attracting, $X^0$ is equal to $A\cup R\cup Z$, where $Z$ is some set of measure $0$.

Similarly define $X^i, i>0$, as

$$\begin{aligned} X^i := \{ x\in X: \quad T_X^i(x)\in X^0, T^j(x)\notin X^0 \text { for } j<i\}. \end{aligned}$$

Since $X^{i+1} = T_X^{-1}(X^{i})-\cup _{j\le i} X^j$, we see inductively that the sets $X^i$ are measurable. It is clear that they are disjoint, and because the system is strongly attracting we know that

$$\begin{aligned} \mu \left( \bigcup _{i\ge 0} X^i\right) = 1 \end{aligned}$$

In particular $\lim _{j\rightarrow +\infty } \mu (X^j) = 0$, and so the set

$$\begin{aligned} \bigcap _{j\ge 0} T_X^{j} (X^j). \end{aligned}$$

is of measure $0$. But every infinite ${\mathcal G}(\Phi )$-orbit intersects the above set. The set of points with infinite ${\mathcal G}(\Phi )$-orbits is contained in countably many translates of the above set, and so it is also of measure $0$.

By assumption $A\cup R$ is a fundamental domain for ${\mathcal G}(\Phi )$ and so by Proposition 2.10 we have that

$$\begin{aligned} \dim _\text {vN}\ker S = \int _{A\cup R} \dim \ker S_x \,d\mu (x) \end{aligned}$$

Lemma

Let $x\in X$. Statement of the theorem follows if we show that $\dim \ker S_x$ is equal to $0$ if $|{\mathcal G}(\Phi )x \cap I|=0$ and

$$\begin{aligned} |{\mathcal G}(\Phi )x \cap I | -| {\mathcal G}(\Phi )x \cap A| \end{aligned}$$

(4.1)

otherwise.

Proof

We get

$$\begin{aligned} \dim _\text {vN}\ker S&= \int _{A\cup R} \dim \ker S_x \,d\mu (x) \\&= \int _{T_X^\infty (I)} |{\mathcal G}(\Phi )x\cap I| - | {\mathcal G}(\Phi )x \cap A| \,d\mu (x) \\&= \int _{T_X^\infty (I)} |{\mathcal G}(\Phi )x\cap I| \,d\mu (x) - \int _{T_X^\infty (I)\cap A} | {\mathcal G}(\Phi )x \cap A| \,d\mu (x) \\&= \int _{T_X^\infty (I)} |{\mathcal G}(\Phi )x\cap I| \,d\mu (x) - {\Omega }_2(T_X), \end{aligned}$$

and the statement follows from Lemma 2.2.

Let us first compute the kernel of $T_{x}+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x$. From the definition $T_x$ is the convolution operator on the Schreier graph $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$, and the operator $(\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x$ acts identically on vectors $\zeta _v$ for $v\notin A\cup I \cup R$ and is null on other vectors $\zeta _v$.

Let $x_1$ be any starting vertex of $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$ which belongs to the initial set $I$, and let $(x_1, x_2, \ldots , x_k)$ be such that $T_X(x_i) =x_{i+1}$ when $i<k$ and $T_X(x_k)=x_k$. Computation shows that the vector

$$\begin{aligned} \xi (x_1) := \zeta _{x_1} - \zeta _{x_2} + \ldots \pm \zeta _{x_k} \end{aligned}$$

is in the kernel of $T_{x}+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x$. Furthermore, if $u,v,\ldots ,w$ are different starting vertices then the vectors $\xi (u), \xi (v), \ldots , \xi (w)$ are linearly independent.

Lemma

The linear span of the set $\{\xi (x): x\in V(g)\cap I \}$ is equal to the kernel of $T_{x}+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x$

Proof

We just saw containment. On the other hand, suppose there is a vector $\eta$ in the kernel such that $\langle \eta , \zeta _v \rangle =0$ for every $v\in I$. Let $w$ be a maximal (with respect to the relation $w\ge v \iff T_X^k(w)=v$ for some $k$) vertex of ${\mathcal G}(\Phi )x$ such that $\langle \eta , \zeta _w \rangle \ne 0$.

Write $\eta = \zeta _w +\eta '$, where $\eta '$ is a linear combination of vectors $\zeta _u$ for $w>u$. It follows that $\langle (T_x+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x) \eta ', \zeta _w \rangle = 0$, and so

$$\begin{aligned} 0&= \langle (T_x+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x) \eta , \zeta _w \rangle \\&= \langle (T_x+ (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x) \zeta _w, \zeta _w \rangle . \end{aligned}$$

But if $w$ is not a final vertex then $\langle T_x \zeta _w, \zeta _w \rangle =0$, and $\langle (\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x) \zeta _w, \zeta _w\rangle = 1$ (the last equality follows, since by assumption also $w\notin I$), which is a contradiction. And if $w$ is a final vertex then $\langle T_x \zeta _w, \zeta _w \rangle =1$, and $\langle ((\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x) \zeta _w, \zeta _w \rangle = 0$, which also is a contradiction.

Now we need to consider two cases: the final point of $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$ is in $R$ or $A$. If it is in $R$ then $(\chi _A)_x=0$ and $\ker S_x = \ker T_{x}+(\chi _X)_x - (\chi _I)_x - (\chi _A)_x - (\chi _R)_x$. Therefore the formula 4.1 holds because the dimension of linear span of $\{\xi (v): v\in I \}$ is precisely $|I|$.

If the final point of $\mathrm{Schr }_\Phi (x, {\mathcal G}(\Phi ))$ is in $A$ then kernel of $(\chi _A)_x$ is of codimension $1$, and it non-trivially intersects span of $\{\xi (x): x\in I \}$, as soon as the latter set is non-empy. This shows that the formula (4.1) holds also in this case.

Corollary 4.4

If $(X, T_X)$ stops on any configuration, is strongly attracting, and has disjoint accepting chains, then $\dim _{vN} \ker S = \mu (I) - {\Omega }_1(X,T_X).$

Proof

Follows from Proposition 4.2.

5 Turing dynamical systems-examples

We want to use presented examples later together with Theorem 4.3 and Proposition 2.5, so we have to assure that the actions are by continuous group automorphisms, which is the reason for an extra degree of complicacy.

5.1 Turing dynamical system associated to a set of natural numbers

Definition of X and ${\Gamma }$ Let $X$ be a measure space $M^\mathbb {Z}\times S$, where $M := \,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,$ should be interpreted as the set of symbols, and $S:=\,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,$ as the set of states of a Turing machine.

Let $\mathrm{Aut }(M)$ be the group of group automorphisms of $M$; similarly for $\mathrm{Aut }(S)$. Recall that $\mathrm{Aut }(M) \wr \mathbb {Z}$ is defined as $\mathrm{Aut }(M)^{\oplus \mathbb {Z}} \rtimes \mathbb {Z}$, and put

$$\begin{aligned} {\Gamma }= [(\mathrm{Aut }(M)\wr \mathbb {Z}) *\,\mathbb {Z}{/2\mathbb {Z}}\,]\times \mathrm{Aut }(S), \end{aligned}$$

where $*$ denotes the free product.

Notation for elements of X Let $m_{-k} \ldots m_0 \ldots m_l \in M$ and ${\sigma }\in S$. The set

$$\begin{aligned} \{(\dot{n}_i, \tau ) \in M^\mathbb {Z}\times S: n_{-k} = m_{-k}, \ldots , n_l = m_l, \,\, \tau = {\sigma }\} \end{aligned}$$

is denoted by

$$\begin{aligned}{}[m_k\, m_{k-1} \ldots m_{-1}\, \underline{m_0}\, m_1 \ldots m_l][{\sigma }]. \end{aligned}$$

Given ${\sigma }\in S$, let

$$\begin{aligned}{}[][{\sigma }]:= \bigcup _{m\mathrm{im }M} [\underline{m}][{\sigma }], \end{aligned}$$

and given $m\in M$, let

$$\begin{aligned}{}[\underline{m}][]:= \bigcup _{{\sigma }\in S} [\underline{m}][{\sigma }]. \end{aligned}$$

A concrete element from the set $[m_k\, m_{k-1}\ldots m_{-1}\, \underline{m_0}\, m_1 \ldots m_l][{\sigma }]$ is denoted by

$$\begin{aligned} (m_k\, m_{k-1} \ldots m_{-1}\, \underline{m_0}\, m_1 \ldots m_l)[{\sigma }], \end{aligned}$$

and similarly for $()[{\sigma }]$ and $(\underline{m})[]$.

Definition of the action Let us fix a set of positive natural numbers ${\Sigma }$. The action $\rho$ of ${\Gamma }$ on $X$ will depend on ${\Sigma }$. Whenever we want to stress this dependence we use the symbol $\rho _{\Sigma }$.

Let ${\beta }'$ be the unique automorphism of $M$ such that ${\beta }'((1,0,0)) = (1,0,0)$, ${\beta }'((0,1,0)) = (0,0,1)$, ${\beta }'((0,0,1))=(0,1,0)$. Let $M^{\beta }$ be the set of fixed points of ${\beta }'$. Note that it consists of $4$ elements. Let $\beta$ be the automorphism of $M^\mathbb {Z}$ defined by

$$\begin{aligned} \big (\beta (\dot{x}_i)\big )_j := \left\{ \begin{array}{ll} {\beta }'(x_0) &{} \quad \text{ if } \, j= 0\\ x_j &{} \quad \text{ otherwise }\\ \end{array}\right. \end{aligned}$$

(5.1)

The automorphism ${\beta }$ will be referred to as normal flip.

Let $B=B_{\Sigma }$ be the following automorphism of $M^\mathbb {Z}$:

$$\begin{aligned} \big (B(\dot{x}_i)\big )_j := \left\{ \begin{array}{ll} x_j &{} \quad \text{ if } \, j\notin {\Sigma }\\ {\beta }'(x_j) &{} \quad \text{ otherwise }\\ \end{array}\right. \end{aligned}$$

(5.2)

The automorphism $B$ will be referred to as oracle flip.

We proceed to describe $\rho$. The subgroup $\mathrm{Aut }(M)\wr \mathbb {Z}<{\Gamma }$ acts in the standard way on the $M^\mathbb {Z}$ coordinate of $X$: $\mathrm{Aut }(M)$ acts on the $0$-coordinate of $M^\mathbb {Z}$ in the natural way, and the generator $t$ of $\mathbb {Z}$ acts by

$$\begin{aligned} \big (\rho (t)(\dot{m}_i)\big )_j := m_{j+1}. \end{aligned}$$

(5.3)

The maps $\rho (t)$ and $\rho (t^{-1})$ will be called respectively shift forward, and shift backward.

The subgroup $\mathrm{Aut }(S) < {\Gamma }$ acts on the $S$ coordinate of $X$ in the natural way.

The generator of $\,\mathbb {Z}{/2\mathbb {Z}}\,$ acts by the oracle flip $B$ on $M^\mathbb {Z}$; it will be also denoted by $B$.

Division of X into disjoint subsets We choose the following division:

$$\begin{aligned} X = \bigsqcup _{m\in M, {\sigma }\in S} [\underline{m}][{\sigma }]. \end{aligned}$$

We just finished defining a dynamical hardware $(X)$. When we need to stress its dependence on ${\Sigma }$, we denote it by $(X^{\Sigma })$.

Elements of $S = \,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,\oplus \,\mathbb {Z}{/2\mathbb {Z}}\,$ will be referred to as [Start], [Search forward for $(0,1,0)$], [Search backward for $(0,1,0)$], [Search forward for either $(0,1,0)$ or $(0,0,1)$], [Dummy state 1], [Dummy state 2], [Dummy state 3], [Dummy state 4]. We do not specify which names correspond to which elements of $S$ - the only important thing is that this assignment is made in such a way that $\mathrm{Aut }(S)$ acts transitively on the first four elements.

We proceed to define a dynamical software for $(X^{\Sigma })$. It will be denoted by $(T_X)$ or $(T^{\Sigma }_X)$.

Choice of elements of ${\Gamma }$ for the sets $[\underline{m}][{\sigma }]$ This is done in Fig. 2: arrow between two states ${\sigma }$ and $\tau$ with a label, for example,

$$\begin{aligned} (0,1,0): \hbox {normal flip, shift backward} \end{aligned}$$

means that the element of ${\Gamma }$ corresponding to $[\underline{(0,1,0)}][{\sigma }]$ is $a \cdot {\beta }\cdot t^{-1}$, where $a\in \mathrm{Aut }(S)$ is any group automorphism sending ${\sigma }$ to $\tau$. Since the action is a right action it means in particular that in this example flipping is done before shifting.

Similarly, an arrow with label

$$\begin{aligned} m\in M^{\beta }: \hbox {shift forward} \end{aligned}$$

joining a state ${\sigma }$ with itself means that the element of ${\Gamma }$ corresponding to $[\underline{m}][{\sigma }]$ for $m\in M^{\beta }$ is $t$.

Finally, if for some state ${\sigma }$ there is no label with a given symbol $m\in M$ then it means that the element of ${\Gamma }$ corresponding to $[\underline{m}][{\sigma }]$ is the neutral element.

Choice of the sets I, A and R. We specify them as follows:

$$\begin{aligned} I&:= \big [\underline{(0,1,0)}\big ]\big [Start\big ],\\ A&:= \big [\underline{(0,1,0)}\big ]\big [Search\;forward\;for\; (0,1,0)\; or\; (0,0,1)\big ]. \end{aligned}$$

As to the set $R$, it is defined as the union of all the sets $[\underline{m}][{\sigma }]$ whose associated group element is the neutral element, apart from $A$.

5.2 Properties of the system $(X,T_X)$

Proposition 5.1

The first fundamental set of $(X, T_X)$ is equal to the union

$$\begin{aligned} \bigcup _{k\in {\Sigma }} F_k \cup Z, \end{aligned}$$

where $F_k$ is equal to

$$\begin{aligned} \bigcup _{m_1,\ldots ,m_{k-1}\in M^{\beta }} \big [\underline{(0,1,0)}\,m_1\,m_2\ldots m_{k-1}\,(0,1,0)\!\big ]\big [\!Start \big ], \end{aligned}$$

and $Z$ is some set of measure $0$.

Proof

This proposition follows from chasing through Fig. 2. First, we show that $F_k$ is in the fundamental set for $k\in {\Sigma }$.

Let $x=(\underline{(0,1,0)}\, m_1 \, m_2 \ldots m_{k-1} \,(0,1,0))[Start]$, $m_i\in M^{\beta }$, $k\in {\Sigma }$. Because of the arrow between the first and the second level of Fig. 1, we have

$$\begin{aligned} T(x) = \big ({(0,1,0)}\, \underline{m_1} \, m_2 \ldots m_{k-1} \,(0,1,0)\big )\big [ Search\ forward\ for\ (0,1,0)\big ]. \end{aligned}$$

Then, because of the arrow “$m \in M^{\beta }:$ shift forward” on the second level of Fig. 2, we get

Fig. 1

An example Schreier graph of a point. Some of the starting points belong to $I$, and the final point belongs to either $A$ or $R$. The only loop in the graph is the self-loop at the final point whose label is the neutral element of ${\Gamma }$

Fig. 2

Turing dynamical system $(X^{\Sigma }, T^{\Sigma }_X)$

$$\begin{aligned} T^{k}(x) = \big ({(0,1,0)}\, m_1 \, m_2 \ldots {m_{k-1}} \,\underline{(0,1,0)}\big )\big [Search\ forward\ for\ (0,1,0) \big ]. \end{aligned}$$

Because of the arrow between the second and the third level, we see

$$\begin{aligned} T^{k+1}(x) \!=\! \big ({(0,1,0)}\, {m_1} \, m_2 \ldots \underline{m_{k-1}} \,(0,0,1)\big ) \big [ Search\ backward\ for\ (0,1,0) \big ]. \end{aligned}$$

Because of the arrow “$m \in M^{\beta }:$ shift backward” on the third level, we conclude

$$\begin{aligned} T^{2k}(x)\! =\! \big (\underline{(0,1,0)}\, m_1 \, m_2 \ldots m_{k-1} \,(0,0,1)\big ) \big [ Search\ backward\ for\ (0,1,0) \big ]. \end{aligned}$$

Because of the arrow between the third and the fourth level, and since $k\in {\Sigma }$, we get that $T^{2k+1}(x)$ is equal to

$$\begin{aligned} \big ((0,1,0)\, \underline{m_1} \, m_2 \ldots m_{k-1} \,(0,0,1)\big ) \big [ Search\ forward\ for\ either\ (0,1,0)\ or \ (0,0,1) \big ]. \end{aligned}$$

Finally, because of the arrow “$m \in M^{\beta }:$ shift forward” on the fourth level, we see that $T^{3k}(x)$ equals

$$\begin{aligned} \big ((0,1,0)\, {m_1} \, m_2 \ldots m_{k-1} \,\underline{(0,0,1)}\big ) \big [ { Search \ forward \ for \ either}\ (0,1,0)\ or\ (0,0,1) \big ], \end{aligned}$$

which is an element of the accepting set.

In the other direction, let

$$\begin{aligned} x = (\underline{m_0}\,m_1\ldots m_{k-1}\,m_{k})[{\sigma }] \end{aligned}$$

be an element of the fundamental set of $(X,T_X)$. We can assume $m_1,\ldots , m_{k-1} \in M^{\beta }$, and $m_k\notin M^{\beta }$, since points $(\dot{x}_i,{\sigma })\in X$ such that $x_i\in M^{\beta }$ for $i>0$ form a set of measure $0$. We have to prove that (1) ${\sigma }=$[Start], (2) $m_0= (0,1,0)$, (3) $m_k=(0,1,0)$, and (4) $k\in {\Sigma }$.

(1) and (2) follow from $I=\underline{(0,1,0)}\,[Start]$. As before we have

$$\begin{aligned} T_X^k(x) = ({m_0}\,m_1\,\ldots \, {m_{k-1}}\,\underline{m_{k}})[Search\;forward\;for\;(0,1,0)], \end{aligned}$$

and therefore from the fact that $T_X^{k}(x) \notin R$ we get (3). Again, as before we see $T_X^{2k}(x)$ is equal to

$$\begin{aligned} \big (\underline{m_0}\,{m_1}\,\ldots \, {m_{k-1}}\,(0,0,1)\!\big )\big [Search\;backward\;for\;(0,1,0) \big ]. \end{aligned}$$

Now, suppose that (4) does not hold, i.e. $k\notin {\Sigma }$. Then because of the arrow between the third and the fourth level, and by the definition of the oracle flip, we get that $T_X^{2k+1}(x)$ is

$$\begin{aligned} \big ({m_0}\,\underline{m_1}\,\ldots \, {m_{k-1}}\,(0,0,1)\big ) \big [ Search\, forward\, for\, either\, (0,1,0)\, or\, (0,0,1) \big ], \end{aligned}$$

which implies that $T_X^{3k}(x)$ is

$$\begin{aligned} \big (\!{m_0}\,{m_1}\,\ldots \, {m_{k-1}}\,\underline{(0,0,1)}\big )\big [Search\;forward\;for\;either\;(0,1,0)\;or\;(0,0,1) \big ], \end{aligned}$$

which is an element of $R$, which contradicts the assumption that $x$ is in the fundamental set.

Corollary 5.2

The first fundamental value of $(X, T_X)$ is equal to

$$\begin{aligned} \frac{2}{8^3} \sum _{i\in {\Sigma }} \frac{1}{2^i} \end{aligned}$$

Proof

The sets $F_k$ are disjoint, and the measure of $F_k$ is equal to $\frac{1}{8} (\frac{1}{2})^{k-1}\frac{1}{8}\frac{1}{8} = \frac{2}{8^3} \frac{1}{2^k}$.

Proposition 5.3

The Turing system $(X, T_X)$ (i) doesn’t restart, (ii) has disjoint accepting chains, and (iii) stops on any configuration.

Proof

• (i) We have to show that $T_X(I) \cap I = \emptyset$. Recall $I =[\underline{(0,1,0)}][Start]$; from Fig. 2 we see that (1) points from outside of $[][Start]$ are not mapped into $[][\text {Start}]$, and in particular are not mapped into $I$; (2) points from $I$ are mapped outside of $[][Start]$ and in particular outside of $I$; and (3) Points from $[][Start]$ which are not in $I$ are mapped identically to themselves, and so are also not mapped to $I$.

• (ii) We need to check that there exists a subset of the fundamental set, which has the same measure as the fundamental set, and on which the map $T_X^\infty$ is injective. But in the proof of Proposition 5.1 we saw that if $x\in F_k$, $k\in {\Sigma }$, and we write $x = (\underline{(0,1,0)}\, m_1 \, m_2 \ldots m_{k-1} \,(0,1,0))[Start]$ then $T_X^\infty (x)$ is equal to $T^{3k}(x)$, which is

  $$\begin{aligned} \,\,\,((0,1,0)\, {m_1} \, m_2 \ldots m_{k-1} \,\underline{(0,0,1)}) [{ Search \;forward \; for \; either}\; (0,1,0)\ or\ (0,0,1)], \end{aligned}$$

  from which we can recover $x$. In particular $T_X^\infty$ is injective on $\bigcup _{k\in {\Sigma }} F_k$.

For (iii), note the following claim.

Claim

Suppose $x= (\dot{m}_i, {\sigma }) \in M^\mathbb {Z}\times S = X$ is such that $T^\infty _X(x) \notin A\cup R$ or is undefined. Then there exists $N\in \mathbb {Z}$ such that $m_j\in M^{\beta }$ for all $j\ge N$ or for all $j\le N$.

Proof

The only elements of ${\Gamma }$ which are applied to the $M^\mathbb {Z}$-coordinate are shifts, normal flip and oracle flip. Since they preserve the property “exists $N$ such that $m_j\in M^{\beta }$ for all $j \ge N$ or all $j \le N$”, it is enough to show that some power $T_X^j(x)$ has this property. But this is clear from Fig. 1: first, there exists a state $\tau$ and $K$ such that $T_X^k(x)\in [][\tau ]$ for $k \ge K$. But the only way it is possible is if either (1) for some $k$, $T_X^k(x)$ is in a set $[m][{\sigma }]$ for which the corresponding element of ${\gamma }$ is the neutral element, or (2) if we write $T^K(x) = (\dot{n}_i, \tau )$ then exists $N$ such that $n_j\in M^{\beta }$ for all $j> N$ or all $j<N$. The second case is what we want to show, and the first case is not possible because it implies that $T^{k}(x) \in A\cup R$.

Now, (iii) follows, since the set of points $\dot{m}_i\in M^\mathbb {Z}$ such that there exists $N$ such that $m_j\in M^{\beta }$ for $j> N$ is of measure $0$.

5.3 A “read only” system with irrational fundamental values

Definition of Y and ${\Delta }$ Let $Y$ be the measure space $(\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}$ $\times$ $\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}$ $\times$ $\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z})$ $\times$ $S$, where $S=\,\mathbb {Z}{/2\mathbb {Z}}\,\times \,\mathbb {Z}{/2\mathbb {Z}}\,\times \,\mathbb {Z}{/2\mathbb {Z}}\,$ should again be interpreted as the set of states. However, in this example $\,\mathbb {Z}{/2\mathbb {Z}}\,$ should be interpreted as the set of symbols, and $\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}\times \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}\times \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}$ should be interpreted as the set of triples of tapes.

Let ${\Delta }$ be the group $\mathbb {Z}^3\times \mathrm{Aut }(S)$, and let standard generators of $\mathbb {Z}^3$ be denoted by $t_1$, $t_2$, and $t_3$. They will be also referred to as shift forward tape 1, shift forward tape 2 , and shift forward tape 3. Similarly $t_i^{-1}$ will be referred to as shift backward tape $i$.

Definition of the action The action $\rho : {\Delta }\curvearrowright Y$ is defined as follows. Let $V: \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}\rightarrow \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}$ be the shift automorphism, i.e. $(V(\dot{x}_i))_j = x_{j+1}$. Define

$$\begin{aligned} \rho (t_1)(\dot{x}_i, \dot{y}_i, \dot{z}_i)&:= (V(\dot{x}_i), \dot{y}_i, \dot{z}_i) \\ \rho (t_2)(\dot{x}_i, \dot{y}_i, \dot{z}_i)&:= (\dot{x}_i, V(\dot{y}_i), \dot{z}_i) \\ \rho (t_3)(\dot{x}_i, \dot{y}_i, \dot{z}_i)&:= (\dot{x}_i, \dot{y}_i, V(\dot{z}_i)). \end{aligned}$$

$\mathrm{Aut }(S)$ acts in the natural way on the $S$-coordinate.

Notation Notation is similar to that in Subsect. 5.1. Given $a_{-k_a}, \ldots , a_{l_a}$, $b_{-k_b}, \ldots , b_{l_b}$, $c_{-k_c},\ldots c_{l_c} \in \,\mathbb {Z}{/2\mathbb {Z}}\,$ and ${\sigma }\in S$, the set

$$\begin{aligned} \{(\dot{x}_i,\dot{y}_i,\dot{z}_i,\tau ) \in (\,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}\times \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}\times \,\mathbb {Z}{/2\mathbb {Z}}\,^\mathbb {Z}) \times S :\\ x_{-k_a} = a_{-k_a} ,\ldots , z_{l_c} = c_{l_c}, \tau = {\sigma }\} \end{aligned}$$

is denoted by

$$\begin{aligned} \left[ \begin{array}{l@{\quad }l@{\quad }l} a_{-k_a}\,\ldots \, &{}\underline{a_0}&{}\, \ldots \, a_{l_a}\\ b_{-k_b}\,\ldots \, &{}\underline{b_0}&{}\, \ldots \, b_{l_b}\\ c_{-k_c}\,\ldots \, &{}\underline{c_0}&{}\, \ldots \, c_{l_c}\\ \end{array} \right] [{\sigma }]. \end{aligned}$$

Given $v = (v_1, v_2, v_3) \in \,\mathbb {Z}{/2\mathbb {Z}}\,^3$ and ${\sigma }\in S$, the set

$$\begin{aligned} \left[ \begin{array}{ll} \underline{v_1} \\ \underline{v_2}\\ \underline{v_3}\\ \end{array} \right] [{\sigma }]. \end{aligned}$$

is also denoted by $[\underline{v}][{\sigma }]$ and $[\underline{(v_1,v_2,v_3)}][{\sigma }]$.

Within the context of above notation, given a natural number $k$ and ${\varepsilon }\in \,\mathbb {Z}{/2\mathbb {Z}}\,$ we denote by ${\varepsilon }^k$ the sequence of $k$ consecutive ${\varepsilon }$’s.

Division of Y We choose the following decomposition of $Y$:

$$\begin{aligned} Y=\bigsqcup _{v\in \,\mathbb {Z}{/2\mathbb {Z}}\,^3,\, {\sigma }\in S} [\underline{v}][{\sigma }]. \end{aligned}$$

We have just defined a dynamical hardware $(Y)$

The states—i.e. elements of $S$—will be referred to as [Start], [Check if the number of 0’s on tape 1 and on tape 2 is the same], [Search backward for 1 on tape 1], [Search forward for 1 on tape 1 and move forward tape 3], [Dummy state 1], [Dummy state 2], [Dummy state 3], [Dummy state 4]. Again we do not specify which of these names correspond to which elements of $S$, but we demand that $\mathrm{Aut }(S)$ acts transitively on the first four of the above states.

We proceed to define a dynamical software $(T_Y)$ for $(Y)$. This is done using Fig. 3, with the same convention as in Subsect. 3.1, e.g. an arrow with a label

$$\begin{aligned} \left( \begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right) \!\!:\! \left. \begin{array}{ll} \text {shift forward tape 1} \\ \text {shift forward tape 2} \end{array}\right. \end{aligned}$$

between states ${\sigma }$ and $\tau$ means that the element of ${\Delta }$ associated to the set $[\underline{(1,1,1)}][{\sigma }]$ is $a\cdot t_1\cdot t_2$, where $a\in \mathrm{Aut }(S)$ is any group automorphism of $S$ which sends ${\sigma }$ to $\tau$.

Fig. 3

Turing dynamical system $(Y, T_Y)$

Choice of the sets A, I and R We define them as follows:

$$\begin{aligned} I&:= [\underline{(1,1,1)}][Start],\\ A&:= [\underline{(0,1,1)}][Search\ backward\ for\ 1\ on\ tape\ 1], \end{aligned}$$

and the rejecting set $R$ is defined to be the union of all the sets $[\underline{v}][{\sigma }]$ whose associated group element is the neutral element, apart from $A$.

5.4 Properties of the system $(Y,T_Y)$

Proposition 5.4

The first fundamental set of $(Y, T_Y)$ is equal to the union

$$\begin{aligned} \bigcup _{k=1}^\infty F_k \cup Z, \end{aligned}$$

where $Z$ is some set of measure $0$ and

$$\begin{aligned} F_k:=\left[ \begin{array}{l} \underline{1}\,0^k \, 1\\ \underline{1}\,0^k \, 1\\ \underline{1}\,0^{k^2+2k}\, 1 \end{array} \right] [Start]. \end{aligned}$$

Proof

The proof is by chasing Fig. 3, fully analogous to the proof of Proposition 5.1.

Corollary 5.5

The first fundamental value of $(Y, T_Y)$ is equal to

$$\begin{aligned} \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}} \end{aligned}$$

Proof

Indeed, measure of the set $F_k$ is equal to $\frac{1}{8}\cdot \frac{1}{2^{k^2+2k}} \cdot \frac{1}{2^k}\cdot \frac{1}{2^k} \cdot \frac{1}{2^6}$ (i.e. “$\frac{1}{8}$ is for states, $\frac{1}{2^{k^2+2k}}$ and $\frac{1}{2^k}$ are for $0$’s, and $\frac{1}{2^6}$ is for $1$’s”.)

Proposition 5.6

The Turing system $(Y, T_Y)$ (i) doesn’t restart, (ii) has disjoint accepting chains, and (iii) stops on any configuration.

Proof

(i) and (ii) are proved just like (i) and (ii) of Proposition 5.3.

As for (iii), let $y\in Y$ be a point such that $T_Y^k(y)\notin A\cup R$, and let $y_i := T_Y^k(y)$. Let $\{y_i\}_{i\ge k}$ denote the set of elements of the sequence $y_k, y_{k+1}, \ldots$, and $\{y_i\}:= \{y_i\}_{i\ge 0}$.

If $\{y_i\}$ is contained in the first two levels of Fig. 3 then there are infinitely many consecutive $0$’s to the right on the first two tapes of $y$. The set of points which have infinitely many consecutive $0$’s on any tape has measure $0$; and if $y_k$ is on the third or fourth level then $\{y_i\}_{i\ge k}$ is contained in the third and the fourth level. Therefore swe can assume that $\{y_i\}_{i\ge l}$ is for some $l$ contained in the third and the fourth level of Fig. 3.

Consider two possibilities: (1) $\{y_i\}_{i>k}$ is contained in the third level for some $k$, or (2) $y_i$ is in the fourth level for infinitely many $i$’s.

If (1) holds then because of the arrow

$$\begin{aligned} \left( \begin{array}{l} 0 \\ 0 \\ 0 \end{array}\right) \!\!:\! \left. \begin{array}{ll} \text {shift backward tape 1} \end{array}\right. \end{aligned}$$

we see that the first tape of $y$ has infinitely many consecutive $0$’s to the left.

If (2) holds then note that the only element of ${\Delta }$ which acts on the third tape of $y$ is shift forward. From Fig. 3 we see that shift forward on the third tape is applied infinitely many times. We see also that it can be applied only if there is $0$ on the third tape. Therefore in this case there are infinitely many consecutive $0$’s on the third tape of $y$.

6 Atiyah problem

6.1 Preliminaries

Let $G$ be a discrete countable group. Recall that a real number $r$ is an $l^2$-Betti number arising from $G$ if for some $k$ there exists $T\in M_k(\mathbb {Q}G)$ such that

$$\begin{aligned} \dim _{vN} \ker \theta = r. \end{aligned}$$

The set of $l^2$-Betti numbers arising from $G$ is denoted by ${\mathcal C}(G)$. Note that if $r\in {\mathcal C}(G)$ then we can always assume that $r=\dim _\text {vN}\ker T$ for a positive self-adjoint $T$ of norm $<1$, since $\ker T = \ker T^*T = \ker \frac{1}{N} T^*T$ for every positive number $N$.

A set ${\Sigma }$ of natural numbers is called computable if there exists a Turing machine which lists elements of ${\Sigma }$ in the increasing order. Equivalently (see e.g. [24]), ${\Sigma }$ is computable if there exists a Turing machine which lists elements of ${\Sigma }$ in some order (possibly with repetitions) and there exists a Turing machine which lists elements of the complement of ${\Sigma }$ in some order (possibly with repetitions).

We say that a real number $r$ has computable binary expansion if the fractional part of $r$ is of the form

$$\begin{aligned} \sum _{i\in {\Sigma }} \frac{1}{2^i} \end{aligned}$$

for some computable set ${\Sigma }$.

In this section we prove Theorems 1.1, 1.3, 1.4, and Corollary 1.2:

Theorem

The set of $l^2$-Betti numbers arising from the group $(\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^3$ contains

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}}. \end{aligned}$$

Theorem

The set of $l^2$-Betti numbers arising from finitely generated groups is equal to the set of non-negative real numbers.

Theorem

The set of $l^2$-Betti numbers arising from finitely presented groups contains all numbers with computable binary expansions.

Corollary

Let $G$ be a group given by the presentation

$$\begin{aligned} \langle a,t,s\,|\,a^2=1,[t,s]=1,[t^{-1}at,a]=1,s^{-1}as=at^{-1}at\rangle . \end{aligned}$$

The set of $l^2$-Betti numbers arising from $G^3$ contains

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}}, \end{aligned}$$

Corollary follows from the next lemma and the fact proven in [14]namely $\,\mathbb {Z}{/2\mathbb {Z}}\, \wr \mathbb {Z}$ is a subgroup of $G$.

Lemma 6.1

Let $H$ be a subgroup of a group $G$. Then ${\mathcal C} (H) \subset {\mathcal C}(G)$.

Proof

The map $M_k(\mathbb {C}H) {\hookrightarrow }M_k(\mathbb {C}G)$, induced by the inclusion $H{\hookrightarrow }G$, is a trace-preserving ${}^*$-homomorphism. The claim follows from Lemma 1.9.

Lemma 6.2

If $G$ is a discrete countable group and $H$ is a finite group then $|H|\cdot {\mathcal C}(G\times H) = {\mathcal C} (G)$.

Proof

Let $\pi \in \mathbb {Q}(G\times H)$ be the sum

$$\begin{aligned} \frac{1}{|H|}\sum _{h\in H} h \end{aligned}$$

Clearly $\pi$ is a projection of trace $\frac{1}{|H|}$ which commutes with $\mathbb {Q}G$. Similarly the $k\times k$ matrix $\pi _k$ which has $\pi$ everywhere on the diagonal and $0$’s elsewhere is of trace $\frac{1}{|H|}$ and commutes with $M_k (\mathbb {Q}G)$. We claim that for a positive self-adjoint $T\in M_k( \mathbb {Q}G)$ of norm at most $1$ we have

$$\begin{aligned} \frac{1}{|H|}\cdot \dim _\text {vN}\ker T = \dim _\text {vN}\ker (1-\pi _k +\pi _k T) \end{aligned}$$

Indeed, by functional calculus the right side is equal to the limit of

$$\begin{aligned} \tau _{G\times H} \left( (1 - (1-\pi _k + \pi _kT))^n\right) , \end{aligned}$$

for $n$ going to $+\infty$. The above expression is equal to $\tau _{G\times H}(\pi _k(1+T)^n) = \tau _H (\pi )\cdot \tau ((1+T)^n)$. By functional calculus again limit of the latter expressions is equal to $\frac{1}{|H|} \cdot \dim _\text {vN}\ker T$. This shows the inclusion $C(G) \subset |H|\cdot {\mathcal C}(G\times H)$

For the other inclusion, note that the regular representation of $H$ induces a ${}^*$-embedding $\mathbb {Q}H {\hookrightarrow }M_{|H|}(\mathbb {Q})$ such that for $T\in \mathbb {Q}H$ we have $|H|\tau _H(T) = \mathrm{tr }(T)$. This induces a ${}^*$-embedding

$$\begin{aligned} \iota :\mathbb {Q}(G\times H) \cong \mathbb {Q}(G) \otimes \mathbb {Q}(H) {\hookrightarrow }\mathbb {Q}(G) \otimes M_{|H|}(\mathbb {Q}) \cong M_{|H|}(\mathbb {Q}(G)) \end{aligned}$$

such that for $T\in \mathbb {Q}(G\times H)$ we have $|H|\cdot \tau _{G\times H} (T) = \tau _G (\iota (T))$. The result follows from Lemma 1.9.

Lemma 6.3

Let $G$ be a countable discrete group. The set ${\mathcal C} G$ is closed under addition. Furthermore, if $H$ is another countable discrete group, $a\in {\mathcal C} (G)$, $b\in {\mathcal C}(H)$ then $a+b \in {\mathcal C} (G\times H)$.

Proof

The first claim follows from the fact that if $S\in M_k (\mathbb {Q}G)$ and $T\in M_l(\mathbb {Q}G)$ then $S\oplus T \in M_{k+l}(\mathbb {Q}G)$ has the property

$$\begin{aligned} \dim _\text {vN}\ker (S\oplus T) = \dim _\text {vN}\ker S + \dim _\text {vN}\ker T. \end{aligned}$$

The second claims follows from taking $S\in M_k (\mathbb {Q}G)$ and $T\in M_l(\mathbb {Q}H)$ and observing that for $S\oplus T \in M_{k+l}(\mathbb {Q}(G\times H))$ we also have

$$\begin{aligned} \dim _\text {vN}\ker (S\oplus T) = \dim _\text {vN}\ker S + \dim _\text {vN}\ker T. \end{aligned}$$

Lemma 6.4

Let $(X,T_X)$ be a Turing dynamical system in which $X$ is a compact abelian group $\prod \,\mathbb {Z}{/2\mathbb {Z}}\,$, the action of ${\Gamma }$ on $X$ is by continuous group automorphisms and the distinguished disjoint subsets $X_i$ of $X$ are cylinder sets.

Suppose furthermore that $(X,T_X)$ stops on any configuration, doesn’t restart, and has disjoint accepting chains. Then $\mu (I) - {\Omega }_1(X,T_X)$ is an $l^2$-Betti number arising from the group ${\widehat{X}}\rtimes _{{\widehat{\rho }}} {\Gamma }$.

Proof

By Corollary 4.4, $\mu (I) - {\Omega }_1(X,T_X)$ is equal to $\dim _\text {vN}\ker S$, where $S \in {\mathcal G}(\rho )$ is expressed by a finite sum of elements ${\gamma }_i\chi _i$, where ${\gamma }_i \in {\Gamma }$, and $\chi _i$ are products of characteristic functions of the sets $X_i$. By Lemma 2.6, $S$ is in the image of the Pontryagin map $P\otimes 1:\mathbb {Q}({\widehat{X}} \rtimes _{{\widehat{\rho }}} {\Gamma }) \rightarrow {\mathcal G} (\rho )$. Let ${\widehat{S}}$ be the preimage of $S$. By Proposition 2.5 we get

$$\begin{aligned} \dim _\text {vN}\ker {\widehat{S}} = \dim _\text {vN}\ker S = \mu (I) - {\Omega }_1(X,T_X). \end{aligned}$$

6.2 The lamplighter group

Theorem 6.5

The set of $l^2$-Betti numbers arising from the group $(\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^3$ contains

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}}, \end{aligned}$$

Proof

By Proposition 5.6, the system $(Y,T_Y)$ from Subsect. 5.3 fulfills conditions of Lemma 6.4. We conclude, by Corollary 5.5, that

$$\begin{aligned} \frac{1}{64}- \frac{1}{8}\sum _{k=1}^\infty \frac{1}{2^{k^2+4k+6}} \end{aligned}$$

is an $l^2$-Betti number arising from the group ${\widehat{Y}}\rtimes _{\widehat{\rho }} {\Delta }$, or more explicitly from

$$\begin{aligned} (\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}} \oplus \,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}} \oplus \,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}} \oplus {\widehat{S}}) \rtimes _{\widehat{\rho }} (\mathbb {Z}\oplus \mathbb {Z}\oplus \mathbb {Z}\oplus \mathrm{Aut }(S)). \end{aligned}$$

Note that the copies of $\mathbb {Z}$ act only on respective copies of $\,\mathbb {Z}{/2\mathbb {Z}}\,^{\oplus \mathbb {Z}}$, and that they act by the shift. It follows that the above group is isomorphic to

$$\begin{aligned} (\,\mathbb {Z}{/2\mathbb {Z}}\,\wr \mathbb {Z})^3 \times ({\widehat{S}}\rtimes \mathrm{Aut }(S)), \end{aligned}$$

so the result follows from Lemma 6.2.

6.3 Finitely generated groups

Theorem

The set of $l^2$-Betti numbers arising from finitely generated groups is equal to the set of non-negative real numbers.

Proof

By Proposition 5.3, the system $(X^{\Sigma },T_X^{\Sigma })$ from Subsect. 5.1 fulfills conditions of Lemma 6.4. We conclude, by Corollary 5.2 that

$$\begin{aligned} \frac{1}{64}- \frac{2}{8^3} \sum _{i\in {\Sigma }} \frac{1}{2^i} \end{aligned}$$

is an $l^2$-Betti number arising from the group ${\widehat{X}} \rtimes _{\widehat{\rho ^{\Sigma }}} {\Gamma }$, or more explicitly from

$$\begin{aligned} ({\widehat{M}}^{\oplus \mathbb {Z}} \times {\widehat{S}})\,\, \rtimes _{\widehat{\rho }}\,\, [(\mathrm{Aut }(M)\wr \mathbb {Z}) *\,\mathbb {Z}{/2\mathbb {Z}}\,]\times \mathrm{Aut }(S), \end{aligned}$$

so, by Lemma 6.2, also from

$$\begin{aligned} {\widehat{M}}^{\oplus \mathbb {Z}} \rtimes _{\widehat{\rho }} ((\mathrm{Aut }(M)\wr \mathbb {Z}) *\,\mathbb {Z}{/2\mathbb {Z}}\,), \end{aligned}$$

(6.1)

which is easily seen to be finitely generated. This and the fact that ${\Sigma }$ was arbitrary implies that every number between $\frac{1}{64}- \frac{2}{8^3}$ and $\frac{1}{64}$ is an $l^2$-Betti number arising from a finitely generated group.

By additivity (Lemma 6.3), we see that there exists a natural number $N = \frac{8^3}{64\cdot 2}$ such that every number between $N -1$ and $N$ with is an $l^2$-Betti number arising from a finitely generated group. By additivity again it follows that every number bigger than $N$ is an $l^2$-Betti number arising from a finitely generated group.

Let $r$ be an arbitrary positive real number. By the previous paragraph there exists a natural number $k$ such that $k \cdot r$ is an $l^2$-Betti number arising from a finitely presented group. The result follows from Lemma 6.2.

6.4 Finitely presented groups

Theorem

The set of $l^2$-Betti numbers arising from finitely presented groups contains all numbers with computable binary expansions.

Proof

Recall that a presentation $\langle g_1, g_2, \ldots \,|\, r_1,r_2,\ldots \rangle$ is a recursive presentation if there exists an algorithm which lists all the elements of the set $\{r_1,r_2,\ldots \}$ in some order (perhaps with repetitions).

Theorem

(Higman’s Embedding Theorem, [16]) If a group has a recursive presentation then it can be embedded into a finitely presented group.

Lemma

Let ${\Sigma }$ be a set of natural numbers and let $(X^{\Sigma },T_X^{\Sigma })$ be the Turing dynamical system from Subsect. 5 5.1. If ${\Sigma }$ is computable then the group

$$\begin{aligned} {\widehat{M}}^{\oplus \mathbb {Z}} \rtimes _{\widehat{\rho ^{\Sigma }}} ((\mathrm{Aut }(M)\wr \mathbb {Z}) *\,\mathbb {Z}{/2\mathbb {Z}}\,) \end{aligned}$$

has a recursive presentation.

Proof

We use notation from Subsect. 5 5.1. Recall that when a group $G = \langle g_1, g_2, \ldots \,|\, p_1, p_2, \ldots \rangle$ acts on a group $H = \langle h_1, h_2,\ldots \,|\, r_1,r_2, \ldots \rangle$ through an action ${\alpha }$ then the standard presentation of the semi-direct product $H\rtimes _{\alpha }G$ is

$$\begin{aligned}&\langle h_2,h_2,\ldots ; g_1,g_2,\ldots \,|\, p_1,p_2,\ldots ; r_1,r_2,\ldots ; \,g_ih_jg_i^{-1} = {\alpha }(g_i)(h_j),\\&\quad i,j=1,2,\ldots \rangle . \end{aligned}$$

When we proceed to write this presentation in the case at hand, the only part which could possibly make it non-algorithmic is the action of $\,\mathbb {Z}{/2\mathbb {Z}}\,$. For $m\in {\widehat{\,\mathbb {Z}{/2\mathbb {Z}}\,^3}}$ and $j\in \mathbb {Z}$, let $m_j$ denote the element $(\ldots ,0,m,0,\ldots )\in ({\widehat{\,\mathbb {Z}{/2\mathbb {Z}}\,^3}})^{\oplus \mathbb {Z}}$, with $m$ on the $j$’th place. The relations which we have to write down are of the form:

$$\begin{aligned} \begin{array}{llll} B \cdot m_j \cdot B^{-1} &{}=&{} m_j, &{}\quad \text {for } j\notin {\Sigma }\\ B \cdot m_j \cdot B^{-1} &{}=&{} [{\widehat{{\beta }'}}(m)]_j &{}\quad \text {for } j\in {\Sigma }\end{array} \end{aligned}$$

It is clear that if ${\Sigma }$ is computable, i.e. there is an algorithm which lists all elements of ${\Sigma }$ and there is an algorithm which lists all elements of the complement of ${\Sigma }$, then there exists also an algorithm which lists all of the above relations.

We saw in the previous subsection that the number

$$\begin{aligned} \frac{1}{64}- \frac{2}{8^3} \sum _{i\in {\Sigma }} \frac{1}{2^i} \end{aligned}$$

(6.2)

is an $l^2$-Betti arising from

$$\begin{aligned} {\widehat{M}}^{\oplus \mathbb {Z}} \rtimes _{\widehat{\rho ^{\Sigma }}} ((\mathrm{Aut }(M)\wr \mathbb {Z}) *\,\mathbb {Z}{/2\mathbb {Z}}\,). \end{aligned}$$

By Higman’s Embedding Theorem and the previous lemma we see that for a computable ${\Sigma }$ the number (6.2) is an $l^2$-Betti number arising from a finitely presented group.

By additivity, there exists a natural number $N = \frac{8^3}{64\cdot 2}$ such that every number between $N -1$ and $N$ with a computable binary expansion is an $l^2$-Betti number arising from a finitely presented group. By additivity again, it follows that every number bigger than $N$ with a computable binary expansion is an $l^2$-Betti number arising from a finitely presented group.

Let $r$ be an arbitrary positive number with a computable binary expansion. By the previous paragraph there exists a natural number $k$ such that $2^k \cdot r$ is an $l^2$-Betti number arising from a finitely presented group (since $2^k \cdot r$ has also computable binary expansion). The result follows from Lemma 6.2.