L 2 -Betti numbers and computability of reals

Abstract

We study the computability degree of real numbers arising as $L^{2}$ -Betti numbers or $L^{2}$ -torsion of groups, parametrised over the Turing degree of the word problem.

Keywords

computability of reals

1. Introduction

A real number r is computable if there exists a computable sequence of rational numbers that converges to r in a computably controlled way. Similarly, one obtains notions of right- and left-computability, as well as versions that are parametrised over Turing degrees (Section 3.2).

Several real-valued invariants from group theory and geometric topology are known to lead to values with a computable structure. In particular, such results give rise to corresponding non-realisability results: sufficiently non-computable values cannot occur.

For example, for each recursively presented group, all values of stable commutator length are right-computable; conversely, every right-computable real can be realised as the stable commutator length of some recursively presented group [12]. Another example is that the simplicial volume of each oriented closed connected manifold is a right-computable real number [13]. The intrinsic computable structure of values also appears in other places: for instance, the set of mapping degrees between two oriented closed connected manifolds is recursively enumerable, which leads to examples of sets of integers that cannot be realised as sets of mapping degrees (Appendix A).

In the present article, we focus on the values of $L^{2}$ -Betti numbers and $L^{2}$ -torsion arising from groups. $L^{2}$ -Betti numbers can be described as limits of characteristic sequences, whose elements are traces of powers of matrices over the group ring (Section 2.3). Computing traces of such powers involves determining specific coefficients of elements in the group ring, and thus requires solving the word problem.

1.1. Main results

A straightforward spectral estimate shows that the right-computability degree of $L^{2}$ -Betti numbers is bounded from above by the Turing degree of the word problem of the underlying group.

Theorem 1.1 (Theorem 4.2).

Let G be a finitely generated group with word problem of degree at most a . Moreover, let $m, n \in N$ and $A \in M_{m \times n} (Z G)$ . Then, the $L^{2}$ -Betti number ${dim}_{R G} ker (R_{A}^{(2)})$ is a -right-computable.

Left-computability requires additional control on the spectrum (Theorem 4.5).

Theorem 1.2 (Theorem 5.7).

Let a be a Turing degree. There is an algorithm of Turing degree a that,

given a finitely generated group G, given by a finite generating set S,

an algorithm of Turing degree a , solving the word problem of G,

a matrix $A \in M_{n \times n} (Z S^{*})$ whose image in $M_{n \times n} (Z G)$ is of determinant class, and

a rational number, testifying that A is of determinant class (see Lemma 5.5 ),

computes a sequence $N \to Q$ effectively converging to ${dim}_{R G} ker (R_{A}^{(2)})$ .

In particular,

{dim}_{R G} ker (R_{A}^{(2)})

is a -computable.

In the presence of positive Novikov–Shubin invariants, also the values of $L^{2}$ -torsion are computable reals:

Theorem 1.3 (Theorem 7.1).

Let G be a finitely generated group with word problem of Turing degree at most a . Let X be a finite free G-CW-complex all of whose $L^{2}$ -Betti numbers are zero and all of whose Novikov–Shubin invariants are positive. Then the $L^{2}$ -torsion $ϱ^{(2)} (G ↷ X)$ is a -computable.

In Turing degree $0$ , the corresponding versions of Theorem 1.1 and Theorem 1.2 had already been established by Groth [11].

Spectral estimates as in the proofs of Theorem 1.1 and Theorem 1.2 also lead to a quantitative version of Lück’s approximation theorem (Proposition 6.6). This gives more explicit computability statements in the case of finitely presented residually finite groups (Corollary 6.7).

Following work of Pichot, Schick, and Żuk [25] for the Turing degree $0$ , we show a realisation result for computable numbers parametrised over the Turing degree of the word problem:

Theorem 1.4 (Corollary 5.12).

Let a be a Turing degree. The set of $L^{2}$ -Betti numbers arising from finitely generated groups of determinant class with word problem of degree at most a is equal to the set of nonnegative, a -computable real numbers.

However, not every single group gives rise to $L^{2}$ -Betti numbers of the Turing degree of the word problem.

Remark 1.5.
Let G be a finitely generated, torsion-free, solvable group with unsolvable word problem (such groups exist, see Corollary B.2). Because G is solvable, it is in Linnell’s class $C$ . Since G is in this class and torsion-free, all $L^{2}$ -Betti numbers arising from G are integral [16, Theorem 1.5, p. 564], hence in particular effectively computable. But the word problem in G is not of Turing degree $0$ by assumption.

Ordinary Betti numbers of finitely presented groups can be computed by an algorithm of Turing degree $3$ [22]. With analogous arguments, we obtain for $L^{2}$ -Betti numbers:
Theorem 1.6 (Theorem 8.1).

Let a be a Turing degree. Then there exists an algorithm of Turing degree at most $a^{(4)}$ that

given a finitely generated group G, a finite generating set S, and an algorithm of degree at most a solving the word problem for G with respect to S, and given $k \in N$ ,

computes the binary expansion for $b_{k}^{(2)} (G)$ (or detects that this value is $+ \infty$ ).

We do not know whether the bound “ $a^{(4)}$ ” is optimal. The realisation result Theorem 1.4 suggests that there might not be a version of Theorem 1.6 with a uniform finite Turing degree instead of “ $a^{(4)}$ ”.

1.2. Related work on computability and $L^{2}$ -invariants

The most prominent open problem on the range of values of $L^{2}$ -Betti numbers is the Atiyah problem [20, Chapter 10]. One version of this problem asks whether all $L^{2}$ -Betti numbers arising from torsion-free groups are integers. While many positive examples are known, several generalised versions for groups with torsion have been disproved. Austin showed in a non-constructive way that irrational values occur [2, Corollary 1.2]. Grabowski established that all non-negative reals arise from finitely generated groups and gave the first explicit examples with irrational values [8, Theorem 1.1]. The following question remains open: Are all $L^{2}$ -Betti numbers over finitely generated torsion-free groups integers?

In the direction of Theorem 1.6, it was already known that $L^{2}$ -Betti numbers of matrices/groups are not computable from finite presentations: a concrete example comes from lamplighter groups. For finitely presented groups G that contain the group $Z / 2 ≀ Z$ as a subgroup, the problem of determining whether a given matrix over $Z [G^{3}]$ leads to a trivial $L^{2}$ -Betti number or not is known to be undecidable [9, Theorem 1.1].

Less specifically, a simple witness construction argument shows that $L^{2}$ -Betti numbers and cost of finitely presented groups are not computable from finite presentations [7, Remark 8.11].

1.3. Implementation in $Lean$

We formalised the results and proofs on computability of values of $L^{2}$ -Betti numbers of groups in the proof assistant $Lean$ [3]. $Lean$ is based on dependent type theory and offers a library that covers a substantial part of undergraduate mathematics [31].

On the one hand, the implementation in a proof assistant gives a verification of correctness of the formalised proofs. On the other hand, the implementation process can also lead to new mathematical insights: in proof assistants such as $Lean$ it is often easier to model abstract concepts than concrete constructions. For example, it is easier to formalise tracial algebras than the group ring and it is easier to formalise a relative version of computability than absolute computability. In this way, working with proof assistants encourages a declarative and modular style of mathematics.

Our implementation is available online [17] and is explained in an earlier version of this article [18, Section 9].

1.4. Organisation of this article

We recall basics on $L^{2}$ -Betti numbers in Section 2 and basics on computability in Section 3. Section 4 contains the proofs of Theorem 1.1 and the characterisation of left-computability. In Section 5, we consider the determinant class case; in particular, we prove Theorem 1.2 and Theorem 1.4. The quantitative approximation theorem is established in Section 6. In Section 7, we prove Theorem 1.3 on $L^{2}$ -torsion. Theorem 1.6 on the computation of $L^{2}$ -Betti numbers from a description of the group is shown in Section 8.

2. Preliminaries on $L^{2}$ -Betti numbers

Originally, $L^{2}$ -Betti numbers were introduced by Atiyah in a geometric setting by analytic means [1]. By now, many extensions and descriptions are available in view of the work of Eckmann, Dodziuk, Farber, and Lück. In this article, we will mostly refer to the books by Lück [20] and Kammeyer [14].

In this section, let G be a finitely generated group.

2.1. $L^{2}$ -Betti numbers

Topologically, $L^{2}$ -Betti numbers can be defined as follows: Let X be a proper G-CW-complex of finite type. Then, the $L^{2}$ -Betti numbers of X are the von Neumann-dimensions of the homology groups of the $L^{2}$ -completion of the cellular chain complex of X [14, Chapter 3.3]. We say that a real number is an $L^{2}$ -Betti number arising from G if there is a G-CW-complex that has this number as one of its $L^{2}$ -Betti numbers. Equivalently, these numbers admit an algebraic description [20, Lemma 10.5][14, Proposition 3.29]:

Definition 2.1 ( $L^{2}$ -Betti numbers arising from a group).

Let $b \in R_{⩾ 0}$ . We say that b is an $L^{2}$ -Betti number arising from G if there are $n, m \in N$ and a matrix $A \in M_{m \times n} (Z G)$ such that $\begin{matrix} b = {dim}_{R G} ker (R_{A}^{(2)}) . \end{matrix}$ We explain the occuring terms below:

By $ℓ^{2} G$ , we denote the Hilbert space of square-summable complex sequences on G, i.e., functions $a : G \to C$ such that $\sum_{g \in G} | a_{g} |^{2} < \infty$ .

By $R_{A}^{(2)}$ , we denote the bounded linear map ${(ℓ^{2} G)}^{m} \to {(ℓ^{2} G)}^{n}$ that is given by right-multiplication with A, and $ker (R_{A}^{(2)})$ denotes its kernel, which is a G-submodule of ${(ℓ^{2} G)}^{m}$ .

By ${dim}_{R G}$ , we denote the von Neumann dimension. One should keep in mind that this number is a priori a non-negative real number and not necessarily an integer. For details on the construction of the von Neumann dimension, we refer to the literature [20, Chapter 1.1][14, Chapter 2.3].

We abbreviate

b^{(2)} (A; G) : = {dim}_{R G} ker (R_{A}^{(2)})

Remark 2.2 (self-adjointness).

In Definition 2.1, we can equivalently also demand that $m = n$ and that A is self-adjoint, i.e., that $A^{*} = A$ (because A and $A A^{*}$ have the same kernel). Here, the involution $\cdot^{*}$ is given by taking the transpose of the matrix and applying the elementwise involution $\sum_{g \in G} a_{g} \cdot g \mapsto \sum_{g \in G} a_{g} \cdot g^{- 1}$ on $Z G$ .

Special $L^{2}$ -Betti numbers arising from a group G are the $L^{2}$ -Betti numbers $b_{*}^{(2)} (G)$ of the group G itself [20, Chapter 1 and 6.5]: If G is a group that admits a classifying space X of finite type and $k \in N$ , then the k-th $L^{2}$ -Betti number of G is equal to $b^{(2)} (Δ_{k}; G)$ , where $Δ_{k}$ is the cellular Laplacian in degree k of the universal covering of X.

2.2. Spectral measures

We recall basic properties of spectral measures. The spectral measure of a self-adjoint matrix over the group ring is characterised by the property in Proposition 2.4, relating integration over the spectral measure to traces.

Definition 2.3 (trace [20, Equation 3.170]).

Let $n \in N$ . We define the trace by $\begin{array}{l} {tr}_{C G} : M_{n \times n} (C G) & ⟶ C \\ A & ⟼ \sum_{i = 1}^{n} {(A_{i i})}_{e}, \end{array}$ where ${(A_{i i})}_{e}$ is the contribution of the neutral element of G to the i-th diagonal element of A.

Proposition 2.4 (characterisation of the spectral measure [14, Definition 5.9]).

Let $n \in N$ and $A \in M_{n \times n} (Z G)$ be self-adjoint. Let $‖ R_{A}^{(2)} ‖$ denote the operator norm of $R_{A}^{(2)}$ .

Then, the spectral measure of A is the unique measure $μ_{A}$ on the interval $[0, ‖ R_{A}^{(2)} ‖]$ (with the Borel σ-algebra) such that: for all polynomials $p \in R [x]$ , we have $\begin{matrix} {tr}_{C G} (p (A)) = \int_{0}^{‖ R_{A}^{(2)} ‖} p (x) d μ_{A} (x) . \end{matrix}$

Conveniently, we can express $L^{2}$ -Betti numbers via the spectral measure.

Proposition 2.5 ( $L^{2}$ -Betti numbers via spectral measure [19][14, p. 97]).

Let $n \in N$ and $A \in M_{n \times n} (Z G)$ be self-adjoint. Then, we have $\begin{matrix} b^{(2)} (A; G) = μ_{A} ({0}) . \end{matrix}$

2.3. Characteristic sequences

As in the proofs of approximation theorems for $L^{2}$ -Betti numbers, we will use characteristic sequences to approximate $L^{2}$ -Betti numbers. The characteristic sequences are defined in terms of the trace on matrices over $C G$ (Definition 2.3).

Definition 2.6 (characteristic sequence [20, Definition 3.171]).

Let $A \in M_{m \times n} (C G)$ and $K ⩾ ‖ R_{A}^{(2)} ‖$ . Then, we define the characteristic sequence $c (A, K) : = {(c {(A, K)}_{p})}_{p \in N}$ of A by $\begin{matrix} c {(A, K)}_{p} : = {tr}_{C G} ({(1 - K^{- 2} \cdot A A^{*})}^{p}) \in R_{⩾ 0} . \end{matrix}$

Proposition 2.7 ( $L^{2}$ -Betti numbers via characteristic sequences [20, Theorem 3.172 (1), (2)]).

Let $A \in M_{m \times n} (C G)$ and $K ⩾ 0$ with $K ⩾ ‖ R_{A}^{(2)} ‖$ . Then, the characteristic sequence ${(c {(A, K)}_{p})}_{p \in N}$ is a monotone decreasing sequence of non-negative real numbers satisfying $\begin{matrix} b^{(2)} (A; G) = lim_{p \to \infty} c {(A, K)}_{p} . \end{matrix}$

This approximation can be proved via the spectral measure. Moreover, the rate of convergence is controlled by the spectral measure (see Theorem 4.5).

3. Preliminaries on computability

We collect basic notions from computability such as Turing degrees, the computability of reals and limits, how to represent elements of finitely generated groups and matrices over the group ring, and the word problem for finitely generated groups.

3.1. Turing degrees

We quickly recall the concept of Turing degrees. More details can be found in the work of Simpson [30]. Algorithms always refer to algorithms in the sense of Turing machines (possibly amended by an oracle).

Definition 3.1 (Turing reducible, equivalent, degree).

Let $f, g : N \to N$ .

We say that f is Turing reducible to g, denoted $f ⩽_{T} g$ if there is an algorithm that computes f, given an algorithm, called an oracle, that computes g.

We say that f is Turing equivalent to g if $f ⩽_{T} g$ and $g ⩽_{T} f$ .

The Turing degree of f, denoted $deg (f)$ is the set of all functions $N \to N$ that are Turing equivalent to f.

We introduce the same notions for subsets

A \subset N

by considering their characteristic functions

χ_{A} : N \to {0, 1}

Proposition 3.2 ([30, Proposition 1.2]).

The following statements hold for Turing degrees of functions $N \to N$ and subsets of $N$ (as functions $N \to {0, 1}$ ).

There is an uncountable number of degrees.

The relation $⩽_{T}$ induces a partial ordering on the set of degrees: For $f, g : N \to N$ , we define $deg (f) ⩽_{T} deg (g)$ if $f ⩽_{T} g$ .

The degree $0 : = deg (\emptyset)$ is the least degree under this partial ordering. It is the set of all computable functions. When dealing with subsets of $N$ , the degree $0$ is the set of all decidable sets.

For every Turing degree a, there is bigger Turing degree $a^{(1)} : = j (a)$ , defined via the jump operator [30, p. 634] (see also the proof of Proposition 3.10).

Using a standard encoding of $Q$ as a sequence over $N$ , we may also speak of Turing degrees of functions $N \to Q$ etc.

3.2. Computability of real numbers

We recall different notions of computability of real numbers, parametrised by Turing degrees. The definitions in the computable case can be found in the survey by Rettinger and Zheng [26].

Definition 3.3 (a-computability).

Let a be a Turing degree of functions $N \to Q$ and let $r \in R$ .

The real number r is called a-computable if there is a sequence $q : N \to Q$ of degree at most a such that $\begin{matrix} \forall_{n \in N} | r - q_{n} | ⩽ 2^{- n} . \end{matrix}$ In this sitation, we say that ${(q_{n})}_{n \in N}$ effectively converges to r. We denote the set of a-computable real numbers by ${EC}_{a}$ .

The real number r is called a-left-computable (resp. a-right-computable) if there is a sequence $q : N \to Q$ of degree at most a such that $\begin{matrix} r = lim_{n \to \infty} q_{n} \end{matrix}$ and $q_{n} ⩽ r$ (resp. $q_{n} ⩾ r$ ) for all $n \in N$ . We denote the set of a-left-computable (resp. a-right-computable) real numbers by ${LC}_{a}$ (resp. ${RC}_{a}$ ).

In the case

a = 0

, we speak of (effective) computability and left-/right-computability, respectively.

Proposition 3.4 (characterisation of computability).

Let a be a Turing degree of functions $N \to Q$ and let $r \in R$ . The following are equivalent:

The number r is a -computable.

There are sequences $q : N \to Q$ and $ϵ : N \to Q$ of degree at most a such that ${lim}_{n \to \infty} ϵ_{n} = 0$ and for all $n \in N$ , we have $\begin{matrix} | r - q_{n} | ⩽ ϵ_{n} . \end{matrix}$

The Dedekind cut ${x \in Q ∣ x < r}$ is a set of degree at most a .

There exist $k \in Z$ and a subset $A \subset N_{> 0}$ of degree at most a such that $\begin{matrix} r = k + \sum_{n \in A} 2^{- n} . \end{matrix}$

Proof.
The equivalence of 1 and 2 is a straightforward argument. In the following, we show the equivalence of 1 and 4. The equivalence of 1 and 3 then follows in a similar fashion.

If $r \in Q$ , then 1 holds (take a constant sequence) and so does 4 as the binary expansion of r is periodic in this case. We therefore suppose that $r \in R ∖ Q$ .

Assume that 1 holds, i.e., there exists a rational sequence ${(q_{n})}_{n \in N}$ of degree at most a such that $\begin{matrix} | r - q_{n} | ⩽ 2^{- n} \end{matrix}$ for all $n \in N$ . We set $k : = ⌊ r ⌋$ . We give a recursive algorithm of degree at most a which determines whether $n \in A$ : Consider the number $\begin{matrix} r^{'} : = k + (\sum_{i \in A \cap {0, \dots, n - 1}} 2^{- i}) + 2^{- n} . \end{matrix}$ Because $r \notin Q$ , we have $r^{'} \neq r$ , hence there is $j \in N$ such that $| r^{'} - r | > 2^{- j}$ . Because we have $| r - q_{j} | ⩽ 2^{- j}$ by assumption, we must have $q_{j} < r^{'}$ or $q_{j} > r^{'}$ . In the former case, $n \notin A$ , in the latter case, we have $n \in A$ .

Conversely, if 4 holds, then $\begin{matrix} {(k + \sum_{i \in A \cap {0, \dots, n}} 2^{- i})}_{n \in N} \end{matrix}$ is a sequence of degree at most a witnessing that r is a-computable. □
Remark 3.5.
The statements in Proposition 3.4 are not algorithmically equivalent, i.e., in general, there is no algorithm that, given one representation of an effectively computable number, produces one of the other representations.

However, by adding 1 to the Turing degree, we can overcome this problem. This is illustrated by Lemma 3.6.
Lemma 3.6.
Let a be a Turing degree. Then, there is an algorithm of degree $a^{(1)}$ that
given a sequence $q : N \to Q$ of degree a that effectively converges to its limit,

outputs the binary expansion of ${lim}_{n \to \infty} q_{n}$ .

Proof.
Let $n + \sum_{i = 0}^{\infty} a_{i} \cdot 2^{- i}$ be the binary expansion of the limit $q^{*} : = {lim}_{n \to \infty} q_{n}$ , i.e., $n \in Z$ and $a_{i} \in {0, 1}$ ; if this expansion is not unique, we prefer the finite one. Suppose that $k \in N$ and $n, a_{0}, \dots, a_{k - 1}$ are already known. Then, $a_{k} = 0$ if and only if there is $l \in N$ such that $\begin{matrix} q_{l} + 2^{- l} < n + \sum_{i = 0}^{k - 1} a_{i} \cdot 2^{- i} + 1 \cdot 2^{- k}, \end{matrix}$ which can be decided by using an oracle for the halting problem, whence increasing the Turing degree by 1. □

Similarly to the case of effective computability, we have: Proposition 3.7 (characterisation of a-left- and right-computability).

Let a be a Turing degree of functions $N \to Q$ and let $r \in R$ . Then the following are equivalent:

The number r is a -left-computable (resp. a -right-computable).

There exists a monotonically increasing (resp. decreasing) sequence $q : N \to Q$ of degree at most a such that ${lim}_{n \to \infty} q_{n} = r$ .

The Dedekind cut ${x \in Q ∣ x < r}$ (resp. ${x \in Q ∣ x > r}$ ) is the image of a function $N \to Q$ of degree at most a.

There exist $k \in Z$ and a subset $A \subset N_{> 0}$ that is either empty or the image of a function $N \to Q$ of degree at most a (resp. such that $N_{> 0} ∖ A$ is the image of a function $N \to Q$ of degree at most a ) such that $\begin{matrix} r = k + \sum_{n \in A} 2^{- n} . \end{matrix}$

Proof.
One can use the same arguments as for Proposition 3.4. □
Corollary 3.8.
Let a be a Turing degree of functions $N \to Q$ . Then, we have $\begin{matrix} {EC}_{a} = {LC}_{a} \cap {RC}_{a} . \end{matrix}$
Proof.
This follows from Propositions 3.4 and 3.7. □
Example 3.9.

For every Turing degree a, the sets ${EC}_{a}$ , ${LC}_{a}$ and ${RC}_{a}$ are countably infinite.

All algebraic numbers are $0$ -computable [26, p. 6].

The transcendental numbers e and π are $0$ -computable [26, p. 5].

Proposition 3.10.
For every Turing degree a , we have ${LC}_{a} ∖ {EC}_{a} \neq \emptyset$ and ${RC}_{a} ∖ {EC}_{a} \neq \emptyset$ .
Proof.
Let $f : N \to {0, 1}$ be a function such that $a = deg (f)$ . We set $\begin{matrix} x : = \sum_{n \in N} f^{} (n) \cdot 2^{- n} \in [0, 2], \end{matrix}$ where $f^{} : N \to {0, 1}$ is the jump of f. The jump of f is defined as follows: Fix a Gödel numbering of all algorithms. Then, we set $f^{} (n) : = 1$ if the n-th algorithm halts on input n with oracle f, and $f^{} (n) : = 0$ otherwise [30, p. 633].

We have $x \in {LC}_{a}$ : Indeed, the set ${n \in N ∣ f^{} (n) = 1}$ is semi-decided with oracle f by the following algorithm: For $n \in N$ , simulate the n-th algorithm on input n with oracle f. Once this simulation terminates, accept.

Moreover, we have $x \notin {EC}_{a}$ : Assume for a contradiction that $x \in {EC}_{a}$ . Then, by the characterisation of Proposition 3.4, we have that the set ${n \in N ∣ f^{} (n) = 1}$ , whence $f^{}$ , is a-computable. Therefore, $f^{} ⩽_{T} f$ , contradicting an elementary property of the jump operator [30, Proposition 1.1(iv)].

Similarly, one can show that $- x \in {RC}_{a} ∖ {EC}_{a}$ . □

3.3. Computability of limits

We investigate the computability of (iterated) limits. We will use these results in Section 8 to prove Theorem 1.6.

Lemma 3.11 (from limits to effective limits).

Let a be a Turing degree. There is an algorithm of degree at most $a^{(1)}$ that

given a sequence $q : N \to Q$ of degree at most a that is convergent in $R$ ,

outputs a subsequence $r : N \to Q$ of q that converges effectively to $q^{*} : = {lim}_{n \to \infty} q_{n}$ , i.e., for all $n \in N$ , we have $\begin{matrix} | r_{n} - q^{*} | ⩽ 2^{- n} . \end{matrix}$

Proof.
Let $q : N \to Q$ be a convergent sequence of degree at most a and let $q^{} : = {lim}_{n \to \infty} q_{n} \in R$ be the limit. As q converges, it is Cauchy, i.e., $\begin{matrix} \forall_{m \in N} \exists_{N \in N} \forall_{n ⩾ N} | q_{N} - q_{n} | ⩽ 2^{- (m + 1)} . \end{matrix}$ If we have a subsequence ${(q_{N (m)})}_{m \in N}$ with Cauchy indices as above, we also have $\begin{matrix} \forall_{m \in N} | q_{N (m)} - q^{} | ⩽ 2^{- m}, \end{matrix}$ It thus remains to show that we can produce such a sequence algorithmically. We consider the following algorithm T of degree at most a:
On input $m, N \in N$ ,

for $n = N, N + 1, \dots$ , do

if $| q_{n} - q_{N} | > 2^{- m}$ , then halt;

otherwise continue.
We then consider the following algorithm, which uses the halting problem of T as oracle, and thus is of degree at most $a^{(1)}$ :
On input $m \in N$ ,

for $N = 0, 1, 2, \dots$ , do:

use the oracle to decide if T halts on input $(m, N)$ ;

if this is not the case, halt and return $q_{N}$ .
Then, by construction, this second algorithm halts because the sequence q converges. This is an algorithm of degree at most $a^{(1)}$ with the desired properties. □
Lemma 3.12 (from double limits to single limits).

Let a be a Turing degree. There is an algorithm of degree at most $a^{(1)}$ that

given a function $q : N \times N \to Q$ of degree at most a such that ${lim}_{i \to \infty} {lim}_{j \to \infty} q (i, j)$ exists in $R$ or is equal to $+ \infty$ , and additionally ${lim}_{j \to \infty} q (i, j) \in R$ for all $i \in N$ ,

outputs a sequence $r : N \to Q$ such that $\begin{matrix} lim_{n \to \infty} r_{n} = lim_{i \to \infty} lim_{j \to \infty} q (i, j) . \end{matrix}$

Proof.
Let $q : N \times N \to Q$ as above. By applying the algorithm of Lemma 3.11 to the sequences $q (i, \cdot)$ for all $i \in N$ , we obtain a function $\tilde{q} : N \times N \to Q$ of degree at most $a^{(1)}$ . Then, the diagonalisation $r (n) : = \tilde{q} (n, n)$ is also of degree at most $a^{(1)}$ and satisfies the desired property ${lim}_{n \to \infty} r_{n} = {lim}_{i \to \infty} {lim}_{j \to \infty} q (i, j)$ . □
Lemma 3.13 (divergence to $+ \infty$ ).

Let a be a Turing degree. There is an algorithm of degree at most $a^{(2)}$ that

given a function $q : N \to Q$ of degree at most a such that ${lim}_{k \to \infty} q_{k}$ exists in $R$ or is equal to $+ \infty$ ,

decides if ${lim}_{k \to \infty} q_{k} = + \infty$ .

Proof.
Given the present assumptions, divergence to $+ \infty$ is equivalent to (positive) unboundedness of the sequence, i.e., to $\begin{matrix} \forall_{K \in N} \exists_{k \in N} q_{k} > K, \end{matrix}$ which can be checked by an algorithm of degree at most $a^{(2)}$ . □
Lemma 3.14 (iterated limits).

Let a be a Turing degree and $k \in N$ . There is an algorithm of degree at most $a^{(k + 1)}$ that

given a function $q : N^{k} \to Q$ of degree at most a such that $\begin{matrix} lim_{i_{1} \to \infty} \dots lim_{i_{k} \to \infty} q (i_{1}, \dots, i_{k}) \end{matrix}$ exists in $R$ , or is equal to $+ \infty$ , and all of the ‘inner’ limits exist in $R$ ,

outputs either the binary expansion of this limit if it exists in $R$ or detects that the limit is equal to $+ \infty$ .

Proof.
Using an iterated application of the algorithm of Lemma 3.12 (applied to the degrees $a, a^{(1)}, \dots, a^{(k - 2)}$ ), we obtain an algorithm of degree $a^{(k - 1)}$ that produces a sequence $r : N \to Q$ converging to the same limit. We can then check with the algorithm from Lemma 3.13 (applied to the degree $a^{(k - 1)}$ ) if this limit is equal to $+ \infty$ . This combined algorithm is therefore of degree at most $a^{(k - 1 + 2)}$ . If the limit is finite, we apply the algorithms of Lemma 3.11 (applied to degree $a^{(k - 1)}$ ) and Lemma 3.6 (applied to degree $a^{(k)}$ ) to obtain the binary expansion of the limit. This part of the algorithm is therefore also of degree at most $a^{(k - 1 + 2)}$ . □

3.4. Presenting elements and matrices over the group ring

We explain how matrices over group rings can be represented in an algorithmic setting: Let G be a finitely generated group with a finite generating set S. Let $R = Z$ or $R = Q$ . We then write $R [S^{*}]$ for the set of all R-linear combinations of words over $S \cup S^{- 1}$ . Thus, elements in $R [S^{*}]$ represent elements in the group ring $R [G]$ . Similarly, for $m, n \in N$ , we write $M_{m \times n} (R [S^{*}])$ for the set of $m \times n$ -matrices over $R [S^{*}]$ . Elements of $M_{m \times n} (R [S^{*}])$ hence represent $m \times n$ -matrices over the group ring $R [G]$ .

3.5. The word problem and computability of traces over group rings

The word problem of a group is the following problem: For a word in terms of generators of the group, decide whether this word represents the trivial element. More formally:

Definition 3.15 (word problem).

Let G be a finitely generated group with finite generating set S. Denote by $S^{*}$ the set of all words in S and the (formal) inverses of S. Then, we define the word problem of G (with respect to S) to be the set ${w \in S^{*} | w = e in G}$ .

Remark 3.16.
The degree of the word problem of a finitely generated group does not depend on the chosen finite generating set [21, Lemma 2.2].

We say that a finitely generated group has a solvable word problem if its word problem is decidable. This is the case if and only if the word problem is of degree $0 = deg (\emptyset)$ .

We observe that computing traces for matrices over the group ring is as hard as solving the word problem. We will use this later to deduce results on the computability degree of $L^{2}$ -Betti numbers. Proposition 3.17.
Let G be a finitely generated group with finite generating set $S \subset G$ . Then, the following problem is Turing-equivalent to the word problem of G:
Given $n \in N$ and a matrix $A \in M_{n \times n} (Q [S^{}])$ ,

compute* ${tr}_{C G} (A) \in Q$ .

Proof.
The word problem can be reduced to computing traces: For a word $w \in S^{}$ it is equivalent to decide whether $w = e$ in G and to decide whether ${tr}_{C G} (1 \cdot w) = 1$ .

Conversely, we can reduce the computation of traces to the word problem: Given $n \in N$ and a matrix $A \in M_{n \times n} (Q [S^{}])$ , we proceed in the following steps:
We collect all the words on the diagonal of A that have a non-trivial coefficient.

For all of these words, we check if they represent $e \in G$ using an oracle for the word problem of G.

We sum all the coefficients belonging to elements that represent $e \in G$ .

This sum then is the trace of A.
□

4. Right-/left-computability of $L^{2}$ -Betti numbers

In this section, we present sufficient conditions for right- and left-computability of $L^{2}$ -Betti numbers over finitely generated groups.

4.1. Algorithmic computation of dimensions of kernels

Right-computability is based on the following consequence of the descriptions of $L^{2}$ -Betti numbers through characteristic sequences (Section 2.3). We use presentations of matrices as described in Section 3.4.

Lemma 4.1.
Let a be a Turing degree. There is an algorithm of Turing degree at most a that
given a finitely generated group G and a finite generating set S of G, together with an algorithm of degree at most a solving the word problem for G with respect to S, given $m, n \in N$ , and $A \in M_{m \times n} (Z [S^{}])$ ,

computes a monotone decreasing sequence* $N \to Q$ that converges to $b^{(2)} (A; G)$ .

Proof.
We compute the sum of all absolute values of coefficients occurring in A and call this number $K \in N$ . This number satisfies $K ⩾ ‖ R_{A}^{(2)} ‖_{\infty}$ . Hence, the characteristic sequence ${(c {(A, K)}_{p})}_{p \in N}$ is monotone decreasing and converges to $b^{(2)} (A; G)$ (Proposition 2.7).

Moreover, the characteristic sequence is computable from the given data: For $p \in N$ , we can compute ${(1 - K^{- 2} A A^{})}^{p}$ as a matrix in $M_{m \times m} (Q [S^{}])$ . We can then calculate the trace by solving the word problem (Proposition 3.17). □

4.2. Right-computability

The degree of right-computability is bounded by the degree of the word problem.

Theorem 4.2 (right-computability).

Let G be a finitely generated group with word problem of degree at most a . Moreover, let $m, n \in N$ and $A \in M_{m \times n} (Z G)$ . Then, the $L^{2}$ -Betti number $b^{(2)} (A; G)$ is a -right-computable.

Proof.
There exists a finite generating set S of G, an algorithm of degree a solving the word problem of G with respect to S, and a representation of A in $M_{m \times n} (Z [S^{*}])$ . Then, the algorithm of Lemma 4.1 produces an monotone decreasing a-computable sequence converging to $b^{(2)} (A; G)$ . Hence, $b^{(2)} (A; G)$ is a-right-computable. □
Corollary 4.3 (right-computability, finitely presented case).

Let G be a finitely presented group, let $m, n \in N$ , and let $A \in M_{m \times n} (Z G)$ . Then, the $L^{2}$ -Betti number $b^{(2)} (A; G)$ is $1$ -right-computable.

Proof.
For finitely presented groups, the word problem is not necessarily solvable but it is always recursively enumerable [27, Theorem 12.2] and thus of Turing degree at most $1$ [30, p. 645]. Hence, the claim follows from Theorem 4.2. □
Remark 4.4.
The set of $L^{2}$ -Betti numbers arising from all finitely presented groups contains all non-negative weakly computable numbers, i.e., all numbers that can be written as $x - y$ with $x, y \in {LC}_{0}$ and $x ⩾ y$ . This can for instance be deduced from the examples and techniques of Pichot, Schick and Żuk [25, Remark 13.5 and 13.6, Section 11].

On the other hand, by Corollary 4.3, this set is a subset of ${RC}_{1} \cap R_{⩾ 0}$ . It is an open question what the set of $L^{2}$ -Betti numbers arising from all finitely presented groups exactly looks like.

4.3. Left-computability

Left-computability holds under additional control on the spectral measure.

Theorem 4.5 (left- and effective computability).

Let G be a finitely generated group with word problem of degree a. Moreover, let $m, n \in N$ and let $A \in M_{m \times n} (Z G)$ . The following are equivalent:

The $L^{2}$ -Betti number $b^{(2)} (A; G)$ is a -left-computable.

The $L^{2}$ -Betti number $b^{(2)} (A; G)$ is a -computable.

There exists a sequence $ϵ : N \to Q$ of degree at most a such that ${lim}_{k \to \infty} ϵ_{k} = 0$ and for all $k \in N_{> 0}$ , we have $\begin{matrix} \forall_{k \in N} μ_{A A^{*}} ((0, 1 / k)) ⩽ ϵ_{k} . \end{matrix}$

Proof.
The equivalence between items 1 and 2 follows from a-right-computability (Theorem 4.2) and Corollary 3.8.

We write $Δ : = A A^{*} \in M_{m \times m} (Z G)$ . Then Δ is self-adjoint and $ker (R_{Δ}^{(2)}) = ker (R_{A}^{(2)})$ . Therefore, it suffices to prove the claim for $b^{(2)} (Δ; G)$ . We view $μ_{Δ}$ as a measure on $[0, d]$ , where $K ⩾ ‖ R_{A}^{(2)} ‖_{\infty}$ and $d : = K^{2}$ .

For the implication $1 \Rightarrow 3$ , let $b^{(2)} (Δ; G) = μ_{Δ} ({0})$ be left-computable. By Proposition 3.7, there exists a monotonically increasing sequence $q : N \to Q$ of degree at most a such that ${lim}_{k \to \infty} q_{k} = b^{(2)} (Δ; G)$ . To show item 3 we construct a sequence ${(ϵ_{k})}_{k \in N}$ as follows: For $k \in N_{> 0}$ , we set $\begin{matrix} p (k) : = max {p \in N | {(1 - \frac{1}{k d})}^{p} ⩾ \frac{1}{2}} . \end{matrix}$ and $\begin{array}{l} ϵ_{k} : = 2 \cdot (c {(Δ, d)}_{p (k)} - q_{k}) . \end{array}$ The sequence p is computable. Since the characteristic sequence ${(c {(Δ, d)}_{n})}_{n \in N}$ is of degree at most a (Lemma 4.1) and since q is assumed to be a-computable, also the sequence ϵ is of degree at most a.

Moreover, the sequence ${(ϵ_{k})}_{k \in N}$ tends to zero for $k \to \infty$ : Indeed, both the characteristic sequence ${(c {(Δ, d)}_{k})}_{k \in N}$ and q tend to $b^{(2)} (Δ; G)$ and ${lim}_{k \to \infty} p (k) = \infty$ .

Finally, we show for all $k \in N$ that $μ_{Δ} ((0, 1 / k)) ⩽ ϵ_{k}$ . This estimate follows from: $\begin{array}{l} c {(Δ, d)}_{p (k)} & = {tr}_{C G} {(1 - \frac{Δ}{d})}^{p (k)} = \int_{0}^{d} {(1 - \frac{x}{d})}^{p (k)} d μ_{Δ} (x) (Proposition 2.4) \\ ⩾ \int_{{0}} {(1 - \frac{x}{d})}^{p (k)} d μ_{Δ} (x) + \int_{(0, 1 / k)} {(1 - \frac{x}{d})}^{p (k)} d μ_{Δ} (x) \\ ⩾ μ_{Δ} ({0}) + \frac{1}{2} \cdot μ_{Δ} ((0, 1 / k)) (choice of p (k)) \\ = b^{(2)} (Δ; G) + \frac{1}{2} \cdot μ_{Δ} ((0, 1 / k)) (Proposition 2.5) \\ ⩾ q_{k} + \frac{1}{2} \cdot μ_{Δ} ((0, 1 / k)) (q_{k} approx. from below) \end{array}$

Conversely, we show the implication 3 ⇒ 1: Let $ϵ : N \to Q$ be a sequence of degree at most a as in item 3. We will deduce left-computability. We denote $\begin{matrix} q_{k} : = c {(Δ, d)}_{k^{2}} - ϵ_{k} - m \cdot {(1 - \frac{1}{k \cdot d})}^{k^{2}} . \end{matrix}$ By assumption, ${lim}_{k \to \infty} ϵ_{k} = 0$ . By elementary calculus, $\begin{matrix} lim_{k \to \infty} {(1 - \frac{1}{k \cdot d})}^{k^{2}} = 0 . \end{matrix}$ Hence, we obtain with Proposition 2.7 that $\begin{matrix} lim_{k \to \infty} q_{k} = lim_{k \to \infty} c {(Δ, d)}_{k^{2}} = b^{(2)} (Δ; G) . \end{matrix}$ The sequence ${(q_{k})}_{k \in N}$ is of degree a because its summands are of degree at most a; for the characteristic sequence, this follows from Lemma 4.1.

The convergence of q is from below by the following calculation: $\begin{array}{l} c {(Δ, d)}_{k^{2}} & = {tr}_{C G} ({(1 - \frac{1}{d} \cdot Δ)}^{k^{2}}) = \int_{0}^{d} {(1 - \frac{x}{d})}^{k^{2}} d μ_{Δ} (Proposition 2.4) \\ ⩽ μ_{Δ} ({0}) + μ_{Δ} ((0, 1 / k)) + μ_{Δ} ([1 / k, d]) \cdot {(1 - \frac{1 / k}{d})}^{k^{2}} (monotonicity) \\ ⩽ μ_{Δ} ({0}) + ϵ_{k} + μ_{Δ} ([0, d]) \cdot {(1 - \frac{1}{k d})}^{k^{2}} (assumption on ϵ_{k}) \\ = b^{(2)} (Δ; G) + ϵ_{k} + μ_{Δ} ([0, d]) \cdot {(1 - \frac{1}{k d})}^{k^{2}} (Proposition 2.5) \\ = b^{(2)} (Δ; G) + ϵ_{k} + m \cdot {(1 - \frac{1}{k d})}^{k^{2}} (Proposition 2.4 with p = 1) \end{array}$ Hence, $b^{(2)} (Δ; G)$ is a-left-computable. □

5. The determinant class conjecture

We show that matrices of determinant class lead to effectively computable $L^{2}$ -Betti numbers (relative to the Turing degree of the word problem) and the corresponding realisation result (Theorems 1.2 and 1.4).

5.1. The determinant class conjecture

We first recall the definition of the Fuglede–Kadison determinant and the determinant class conjecture. Details can be found in the literature [28, Definition 1.3].

Definition 5.1 (Fuglede–Kadison determinant).

Let G be a group, $A \in M_{n \times n} (Z G)$ be self-adjoint, and let $μ_{A}$ be the spectral measure of A. Then, we define the Fuglede–Kadison determinant of A by $\begin{matrix} ln det (A) : = \{\begin{matrix} \int_{0^{+}}^{\infty} log (x) d μ_{A} (x) & if this integral converges \\ - \infty & otherwise . \end{matrix} \end{matrix}$ Here, $\int_{0^{+}}^{\infty}$ denotes integration on the set $(0, \infty)$ .

Remark 5.2.
There is only a convergence problem near 0 and no problem for “ $x \to \infty$ ”, as $μ_{A}$ is supported on $[0, ‖ R_{A}^{(2)} ‖]$ .
Definition 5.3 (determinant class conjecture).

We say that a group G satisfies the determinant class conjecture if for every $n \in N$ every self-adjoint element $A \times M_{n \times n} (Z G)$ satisfies $ln det A > - \infty$ .

Example 5.4.
Sofic groups satisfy the determinant class conjecture [5, Theorem 5]. For a sofic group G, and a self-adjoint matrix $A \in M_{n \times n} (Z G)$ , we even have $ln det A ⩾ 0$ .

It is not known whether all groups satisfy the determinant class conjecture.
5.2. Effective computability of $L^{2}$ -Betti numbers

From the property of being of determinant class, we can deduce effective computability of the same degree as the word problem. The case of degree $0$ was originally proved by Groth [11, Theorem 6.12].

First, note that the following holds.

Lemma 5.5.
Let G be a finitely generated group and let $A \in M_{n \times n} (Z G)$ be self-adjoint and of determinant class. Then, there is $q \in Q$ such that $\begin{matrix} \int_{0^{+}}^{1} log (x) d μ_{A} (x) ⩾ - q . \end{matrix}$
Proof.
Because A is of determinant class, we have in particular that $\int_{0^{+}}^{1} log (x) d μ_{A} (x) > - \infty$ . Thus, there is a $q \in Q_{⩾ 0}$ satisfying the claim. □

We do not know if we can algorithmically compute such a rational number.
Question 5.6.
Let $S \subset G$ be a finite generating set. Is there an algorithm that, given a matrix $A \in M_{n \times n} (Z S^{})$ whose image in $M_{n \times n} (Z G)$ is of determinant class, computes a $q \in Q_{⩾ 0}$ that satisfies Lemma 5.5?
Theorem 5.7.
Let* a be a Turing degree. There is an algorithm of Turing degree a that,
given a finitely generated group G, given by a finite generating set S,

an algorithm of Turing degree a , solving the word problem of G,

a matrix $A \in M_{n \times n} (Z S^{})$ whose image in* $M_{n \times n} (Z G)$ is of determinant class, and

a rational number $q \in Q_{⩾ 0}$ as in Lemma 5.5 ,

computes a sequence $N \to Q$ that effectively converges to $b^{(2)} (A; G)$ .
In particular, $b^{(2)} (A; G)$ is a -computable.
Proof.
By the proof of Theorem 4.5, it suffices to construct a sequence $ϵ : N \to Q$ of degree at most a such that ${lim}_{k \to \infty} ϵ_{k} = 0$ and for all $k \in N_{> 0}$ , we have $μ_{A} ((0, 1 / k)) ⩽ ϵ_{k}$ . We set $\begin{matrix} {(ϵ_{k} : = \frac{q}{⌊ log k ⌋})}_{k \in N_{⩾ 2}}, \end{matrix}$ which is computable (so in particular of degree at most a). Moreover, ${lim}_{k \to \infty} ϵ_{k} = 0$ and for all $k \in N_{⩾ 2}$ , we have $\begin{matrix} - q ⩽ \int_{0^{+}}^{1} log (x) d μ_{A} (x) ⩽ \int_{0^{+}}^{{(1 / k)}^{-}} log (x) d μ_{A} (x) ⩽ log (1 / k) \cdot μ_{A} ((0, 1 / k)), \end{matrix}$ as desired. □
Remark 5.8 (sofic groups).

For sofic groups, we can prove a result analogous to Theorem 5.7 more directly, using the fact that the Cayley graphs of sofic groups can be approximated by finite graphs. The proof of Elek and Szabó that sofic groups satisfy the determinant class conjecture contains a result on the approximation of traces [5, Lemma 6.3]. We can thus use an approach similar to the one of Section 6 to obtain effective computability.

Alternatively, one can use an estimate given in an article of Grabowski [9, Proposition A1].

One advantage of these approaches is that we obtain a slightly stronger statement: There is an algorithm, that, given A and an algorithm of degree a solving the word problem in G, computes a sequence witnessing that $b^{(2)} (A; G)$ is effectively computable of degree at most a. This algorithm does not need a rational number as in Lemma 5.5 as an input. If Question 5.6 has a positive answer, we can also eliminate this dependence in Theorem 5.7.

We do not expect that computability of $L^{2}$ -Betti numbers can be leveraged into a proof that the underlying group is of determinant class.

Remark 5.9.
There is another perspective on Theorem 5.7: If G is a finitely generated group with word problem of degree a and there is an $L^{2}$ -Betti number arising from G that is not an a-computable real number, then Theorem 5.7 shows that G does not satisfy the determinant class conjecture.

However, it is perfectly possible that for all groups G with word problem of degree a all $L^{2}$ -Betti numbers arising from G are a-computable $L^{2}$ -Betti numbers – independently of the determinant class conjecture.

5.3. Realisation of $L^{2}$ -Betti numbers

Conversely, each non-negative a-computable real arises as an $L^{2}$ -Betti number over a group with a-solvable word problem:

Theorem 5.10.
Let a be a Turing degree and let $b \in {EC}_{a} \cap R_{⩾ 0}$ . Then, there exists a finitely generated group of determinant class with word problem of degree at most a such that b is an $L^{2}$ -Betti number arising from G.

This theorem was first proved by Pichot, Schick and Żuk for $a = 0$ [25, Remark 13.3]. We follow their construction of such groups.
Proof.
In analogy with the approach by Pichot, Schick, and Żuk [25, Proposition 11.4], we have: Lemma 5.11.
Let a be a Turing degree and let $U \subset R_{⩾ 0}$ be a subset with the following properties:
The set U is closed under multiplication with and addition of non-negative rational numbers.

The set U is additively closed: If $r, s \in U$ , then $r + s \in U$ .

There are numbers $a \in Q_{⩾ 0}$ , $q \in Q_{> 0}$ and $d \in N_{> 0}$ such that for every strictly increasing a -computable sequence $n : N \to N$ , we have $\begin{matrix} a + q \cdot \sum_{k = 1}^{\infty} 2^{k - d n_{k}} \in U . \end{matrix}$
Then, we have ${EC}_{a} \cap R_{⩾ 0} \subseteq U$ .

For the proof of Theorem 5.10, we choose U to be the set of all $L^{2}$ -Betti numbers arising from finitely generated groups of determinant class with word problem of degree at most a.

The conditions 1 and 2 of Lemma 5.11 are satisfied, because products of two groups from the given class preserve the desired properties and we can find the sums [25, Lemma 11.2] and products [25, Lemma 11.3] of the $L^{2}$ -Betti numbers as $L^{2}$ -Betti numbers of the product. Moreover, all non-negative rational numbers are $L^{2}$ -Betti numbers of finite groups [14, Example 3.14] and finite groups are sofic and have even solvable word problem.

As for condition 3, let $I \subset N$ denote the image of n. Then, I is an a-decidable set. Pichot, Schick and Żuk construct a group $G_{I}$ with the desired $L^{2}$ -Betti number as follows: Let $Γ : = Z ≀ Z$ , generated by two specific elements $s_{1}$ , $s_{2}$ . We define $\begin{matrix} G_{I} : = ({(Z / 2)}^{\oplus Γ} / V_{F_{l}, I}) ⋊ Γ . \end{matrix}$ Here, we consider the action of Γ by translation on ${(Z / 2)}^{\oplus Γ} = (Z / 2) [Γ]$ . Moreover, consider the basis ${δ_{g} | g \in Γ}$ of ${(Z / 2)}^{\oplus Γ}$ , where $δ_{g}$ denotes the characteristic function of the set ${g}$ . We define $u : = δ_{s_{1}^{- 1}} + δ_{e} + δ_{s_{1}}$ and $V_{F_{l}, I}$ to be the $(Z / 2) [Γ]$ -submodule of $(Z / 2) [Γ]$ spanned by all the elements of the form $\begin{matrix} u - t u \end{matrix}$ with $t \in Λ_{I} : = ⟨ s_{2}^{n} s_{1} s_{2}^{- n} | n \in I ⟩ \subset Γ$ . Pichot, Schick and Żuk show that there are a, q, and d (which do not depend on I) such that $\begin{matrix} a + q^{'} \cdot \sum_{k = 1}^{\infty} 2^{k - d^{'} (3 \cdot n_{k} + 2)} = a + (q^{'} \cdot 2^{- 2 d^{'}}) \cdot \sum_{k = 1}^{\infty} 2^{k - (3 d^{'}) \cdot n_{k}} \end{matrix}$ is an $L^{2}$ -Betti number arising from $G_{I}$ [25, Theorem 10.1].

Hence, it remains to show that $G_{I}$ is finitely generated, of determinant class and has a word problem of degree at most a.

The group $G_{I}$ is generated by $s_{1}$ , $s_{2}$ , and $δ_{0}$ ; moreover, it is the extension of an abelian group with quotient Γ. It is known that $G_{I}$ is sofic [6, Theorem 1(3)], hence satisfies the determinant class conjecture [5, Theorem 5].

Finally, the word problem of $G_{I}$ is of degree at most a. This follows by the same argument as in the case $a = 0$ [25, Theorem 12.4].

Hence, Lemma 5.11 shows that the set U of all $L^{2}$ -Betti numbers arising from finitely generated groups of determinant class with word problem of degree at most a contains ${EC}_{a} \cap R_{⩾ 0}$ . □

In combination with Theorem 5.7, we obtain the following result: Corollary 5.12.
Let a be a Turing degree. The set of $L^{2}$ -Betti numbers arising from finitely generated groups of determinant class with word problem of degree at most a is equal to ${EC}_{a} \cap R_{⩾ 0}$ .

6. A quantitative version of Lück’s approximation theorem

By Lück’s approximation theorem, $L^{2}$ -Betti numbers of finite type free G-CW-complexes can be approximated by the ordinary Betti numbers of the quotient spaces associated with residual chains.

Theorem 6.1 (Lück’s approximation theorem [19, Theorem 0.1]).

Let X be a finite type free G-CW-complex. Let G be residually finite and let ${(G_{k})}_{k \in N}$ be a residual chain of G. Then, for every $n \in N$ , we have $\begin{matrix} b_{n}^{(2)} (G ↷ X) = lim_{k \to \infty} \frac{b_{n} (G_{k} ∖ X)}{[G : G_{k}]} . \end{matrix}$ Here, $b_{n}$ denotes the (ordinary) n-th Betti number of a CW-complex with $C$ -coefficients.

The proof relies on the algebraic counterpart:

Theorem 6.2 (Lück’s approximation theorem for matrices [20, Chapter 13][14, p. 97]).

Let G be a countable residually finite group and let $A \in M_{n \times n} (Z G)$ be self-adjoint. Let ${(G_{k})}_{k \in N}$ be a residual chain of G. For $k \in N$ , let $A_{k} \in M_{n \times n} (Z (G / G_{k}))$ be the image of A under the entrywise projection induced by the canonical projection $G \to G / G_{k}$ . Then, we have $\begin{matrix} b^{(2)} (A; G) = lim_{k \to \infty} b^{(2)} (A_{k}; G / G_{k}) . \end{matrix}$

In this section, we quantify the rate of convergence in order to establish effective computability of $L^{2}$ -Betti numbers. To do so, we need to control the residual chain. We formulate this in terms of adapted sequences:

Definition 6.3 (adapted sequence).

Let G be a countable residually finite group and let $A \in M_{n \times n} (Z G)$ be self-adjoint. Let ${(G_{k})}_{k \in N}$ be a sequence of finite index, normal subgroups of G. For $k \in N$ , let $A_{k} \in M_{n \times n} (Z (G / G_{k}))$ be the image of A under the canonical projection. We say that the sequence ${(G_{k})}_{k \in N}$ is adapted to A if for all $k \in N$ , all entries of the diagonals of $A^{0}, A^{1}, \dots, A^{k^{2}}$ have support in ${e} \cup G ∖ G_{k}$ . Put differently: On these diagonals, all the coefficients belonging to $G_{k} ∖ {e}$ vanish.

Lemma 6.4 (computability of an adapted sequence).

There exists an algorithm that,

given a residually finite group G, given by a finite presentation $⟨ S | R ⟩$ , and a matrix in $M_{n \times n} (Z G)$ , represented by an element $A \in M_{n \times n} (Z [S^{*}])$ ,

determines a sequence of finite index, normal subgroups ${(G_{k})}_{k \in N}$ of G that is adapted to A and outputs the sequence ${(b^{(2)} (A_{k}; G / G_{k}))}_{k \in N}$ .

Again, the $A_{k}$ denote the images of A under the projections $Z G \to Z (G / G_{k})$ .

In particular, every square matrix over $Z G$ admits an adapted sequence.

Proof.
With this kind of input, there exists an algorithm that solves the word problem in the finitely presented residually finite group G with respect to S and such an algorithm can be determined algorithmically from the given presentation $⟨ S | R ⟩$ of G [21, Theorem 5.3].

We consider the following algorithm: On input $k \in N$ , we proceed in the steps:
We compute the matrices $A^{0}, A^{1}, \dots, A^{k^{2}}$ and the elements on their diagonals that are not the neutral element $e \in G$ and that have a non-trivial coefficient; this is possible through the solution of the word problem. We call these the non-trivial diagonal elements.

For $p = 1, 2, 3, \dots$ , do the following:

We enumerate all group homomorphisms $G \to S_{p}$ , where $S_{p}$ is the symmetric group on ${1, \dots, p}$ . This can be accomplished by enumerating all maps $S \to S_{p}$ , and then verifying whether the images of the relators are trivial.

We check whether the non-trivial diagonal elements computed in the first step are not mapped to $e \in S_{p}$ by the group homomorphism $G \to S_{p}$ .

Once such a group homomorphism $f : G \to S_{p}$ is found, we continue with it as below.

We enumerate the subgroup $H : = im f = {⟨ f (s) | s \in S ⟩}_{S_{p}}$ of $S_{p}$ and its composition table.

We write $A_{k} : = f_{} (A) \in M_{n \times n} (Z H)$ .

We fix an isomorphism $Z H ≅ Z^{| H |}$ of $Z$ -modules and rewrite the matrix $A_{k}$ in the form $A_{k}^{'} \in M_{n | H | \times n | H |} (Z)$ .

We return $({dim}_{Q} ker (\cdot A_{k}^{'})) / | H |$ .
It remains to show that this algorithm terminates and returns the correct output.

The non-trivial diagonal elements computed in the first step are finitely many elements of $G ∖ {e}$ . Because G is residually finite, there exists a group homomorphism from G to a finite group such that all these elements are not* in the kernel. Because every finite group is contained in some finite symmetric group, eventually such a homomorphism $f : G \to S_{p}$ is found.

Then, the subgroup $ker f \subset G$ is normal, of finite index, and satisfies the condition on the k-th element of a sequence adapted to A (Definition 6.3). Moreover, $G / ker f ≅ im f = H$ . Because H is finite, we obtain [14, Example 2.39] $\begin{array}{l} b^{(2)} (A_{k}; G / G_{k}) & = b^{(2)} (A_{k}; H) = \frac{{dim}_{C} ker (\cdot A_{k}^{'})}{| H |} = \frac{{dim}_{Q} ker (\cdot A_{k}^{'})}{| H |} . \end{array}$ Therefore, the algorithm outputs a sequence with the claimed properties. □
Remark 6.5.
Note that unlike in the statement of Lück’s approximation theorem, the adapted sequence fixed by the algorithm does not have to be a residual chain.

For adapted sequences, we can estimate the error of the normalised Betti numbers of such sequences to the $L^{2}$ -Betti number $b^{(2)} (A; G)$ . Proposition 6.6 (Lück’s approximation theorem, quantitative version).

Let G be a countable residually finite group. Let $A \in M_{n \times n} (Z G)$ be self-adjoint and let ${(G_{k})}_{k \in N}$ a sequence of finite index, normal subgroups that is adapted to A (see Definition 6.3 ). Then, for all $k \in N$ , we have $\begin{matrix} | b^{(2)} (A; G) - b^{(2)} (A_{k}; G / G_{k}) | ⩽ n \cdot {(1 - \frac{1}{k d})}^{k^{2}} + \frac{n \cdot log d}{log k}, \end{matrix}$ where $d : = ‖ R_{A}^{(2)} ‖$ is the operator norm of $R_{A}^{(2)}$ .

Proof.
Let $k \in N$ . As before, we denote by $μ_{A}$ the spectral measure of A and by $μ_{A_{k}}$ the spectral measure of $A_{k} \in M_{n \times n} (Z (G / G_{k}))$ . We can view both measures as measures on the same interval $[0, d]$ as $‖ R_{A_{k}}^{(2)} ‖$ and $‖ R_{A}^{(2)} ‖$ are bounded by $| A |_{1}$ , i.e., by the sum of the absolute values of the coefficients in A. Without loss of generality, we assume $d ⩾ 1$ .

We consider the polynomials $p_{k} : = {(1 - \frac{1}{d} \cdot x)}^{k^{2}}$ . Because the sequence ${(G_{k})}_{k \in N}$ is adapted to A, and $p_{k}$ is a polynomial of degree $k^{2}$ , the coefficients on the diagonals of $p_{k} (A)$ and $p_{k} (A_{k})$ belonging to the neutral element in the group ring are identical. Hence we have ${tr}_{C G} (p_{k} (A)) = {tr}_{C (G / G_{k})} (p_{k} (A_{k}))$ . Rewriting this equality using Proposition 2.4 yields $\begin{matrix} (1) & \int_{0}^{d} p_{k} (x) d μ_{A} (x) = \int_{0}^{d} p_{k} (x) d μ_{A_{k}} (x) \end{matrix}$

A further ingredient for this proof are logarithmic bounds for spectral measures: for all $λ \in (0, 1)$ , we have [19, Proof of Theorem 2.3.1][14, Proposition 5.18] $\begin{matrix} μ_{A_{k}} ((0, λ)) ⩽ \frac{n \cdot log d}{| log λ |} . \end{matrix}$ Moreover, also $μ_{A}$ has a logarithmic bound: For all $λ \in (0, 1)$ , we have [19, Theorem 2.3(3)] $\begin{matrix} μ_{A} ((0, λ)) ⩽ \frac{n \cdot log d}{| log λ |} . \end{matrix}$ We now calculate for $k ⩾ 2$ (plus and minus-signs in the bounds of an integral suggest that we integrate over (half-)open intervals): $\begin{array}{l} b^{(2)} (A_{k}; G / G_{k}) \\ = μ_{A_{k}} ({0}) (Proposition 2.5) \\ = \int_{0}^{d} p_{k} (x) d μ_{A_{k}} - \int_{0^{+}}^{d} p_{k} (x) d μ_{A_{k}} \\ = \int_{0}^{d} p_{k} (x) d μ_{A} - \int_{0^{+}}^{d} p_{k} (x) d μ_{A_{k}} (Equation (1)) \\ = \int_{0}^{d} p_{k} (x) d μ_{A} - \int_{0^{+}}^{1 / k^{-}} p_{k} (x) d μ_{A_{k}} - \int_{1 / k}^{d} p_{k} (x) d μ_{A_{k}} \\ ⩾ \int_{0}^{d} p_{k} (x) d μ_{A} - μ_{A_{k}} ((0, 1 / k)) - \int_{1 / k}^{d} p_{k} (x) d μ_{A_{k}} (p_{k} (x) ⩽ 1) \\ ⩾ \int_{0}^{d} p_{k} (x) d μ_{A} - \frac{n \cdot log d}{log k} - \int_{1 / k}^{d} p_{k} (x) d μ_{A_{k}} (log bound, λ = 1 / k) \\ ⩾ \int_{0}^{d} p_{k} (x) d μ_{A} - \frac{n \cdot log d}{log k} - \int_{1 / k}^{d} p_{k} (1 / k) d μ_{A_{k}} (p_{k} (x) is mon. decreasing) \\ ⩾ \int_{0}^{d} p_{k} (x) d μ_{A} - \frac{n \cdot log d}{log k} - μ_{A_{k}} ([1 / k, d]) \cdot p_{k} (1 / k) \\ ⩾ \int_{0}^{d} p_{k} (x) d μ_{A} - \frac{n \cdot log d}{log k} - μ_{A_{k}} ([0, d]) \cdot p_{k} (1 / k) (monotonicity of μ_{A_{k}}) \\ = \int_{0}^{d} p_{k} (x) d μ_{A} - \frac{n \cdot log d}{log k} - n \cdot {(1 - \frac{1}{k d})}^{k^{2}} (Proposition 2.4, p = 1) \\ ⩾ μ_{A} ({0}) - \frac{n \cdot log d}{log k} - n \cdot {(1 - \frac{1}{k d})}^{k^{2}} (monotonicity, p_{k} (0) = 1) \\ = b^{(2)} (A; G) - \frac{n \cdot log d}{log k} - n \cdot {(1 - \frac{1}{k d})}^{k^{2}} (Proposition 2.5) \end{array}$ Therefore, we obtain $\begin{matrix} b^{(2)} (A; G) - b^{(2)} (A_{k}; G / G_{k}) ⩽ n \cdot {(1 - \frac{1}{k d})}^{k^{2}} + \frac{n \cdot log d}{log k} . \end{matrix}$ Analogously, we can prove the lower bound by a similar calculation, exchanging the roles of A and $A_{k}$ . Notice that in that argument, the logarithmic bound for A will then replace the one for $A_{k}$ . □
Corollary 6.7.
There is an algorithm that
given a residually finite group G, given by a finite presentation $⟨ S | R ⟩$ , and a self-adjoint element in $A \in M_{n \times n} (Z G)$ , given as an element in $M_{n \times n} (Z [S^{}])$ ,

outputs a computable sequence witnessing that* $b^{(2)} (A; G)$ is effectively computable, i.e., an algorithm for computing a sequence ${(q_{k})}_{k \in N}$ such that for all $k \in N$ , we have $\begin{matrix} | b^{(2)} (A; G) - q_{k} | ⩽ 2^{- k} . \end{matrix}$
In particular, in this situation, the $L^{2}$ -Betti number $b^{(2)} (A; G)$ is effectively computable.
Proof.
By Lemma 6.4, there is an algorithm that given these data, computes a sequence ${(G_{k})}_{k \in N}$ adapted to A and outputs $\begin{matrix} {(b^{(2)} (A_{k}; G / G_{k}))}_{k \in N} . \end{matrix}$ By the quantitative version of Lück’s approximation theorem (Proposition 6.6), we can estimate the difference between these numbers and the $L^{2}$ -Betti number $b^{(2)} (A; G)$ . These estimates are computable and tend to zero for $k \to \infty$ . Thus, we can algorithmically choose a subsequence witnessing the effective computability of $b^{(2)} (A; G)$ . □
Remark 6.8.
In fact, the result of Corollary 6.7 that $L^{2}$ -Betti numbers of finitely presented, residually finite groups are effectively computable also follows from Theorem 5.7, as residually finite groups are sofic (and thus satisfy the determinant class conjecture). Moreover, finitely presented, residually finite groups have a solvable word problem [21, Theorem 5.3], i.e., a word problem of Turing degree $0$ .

The approach in this section shows that we can also use sequences as in Lück’s approximation theorem to computably approximate $L^{2}$ -Betti numbers.

7. $L^{2}$ -torsion

The $L^{2}$ -torsion is the torsion invariant associated with the dimension ${dim}_{R G}$ [20, Chapter 3]: The $L^{2}$ -torsion of an $L^{2}$ -acyclic Hilbert chain complex is the negative of the alternating sum of the Fuglede–Kadison determinants of the boundary operators. In the presence of positive Novikov–Shubin invariants, one can use the characteristic sequences (Definition 2.6) to conclude computability of values of $L^{2}$ -torsion, similarly to Theorem 5.7. We formulate and prove this statement in the context of $L^{2}$ -torsion of spaces.

Theorem 7.1.
Let G be a finitely generated group with word problem of Turing degree at most a . Let X be a finite free G-CW-complex all of whose $L^{2}$ -Betti numbers are zero and all of whose Novikov–Shubin invariants are positive. Then the $L^{2}$ -torsion $ϱ^{(2)} (G ↷ X)$ is a -computable.
Proof.
Under the given hypothesis, X is det- $L^{2}$ -acyclic [20, Theorem 3.93(7)] and so $\begin{array}{l} ϱ^{(2)} (G ↷ X) & = ϱ^{(2)} (C_{}^{(2)} (G ↷ X)) \\ = - \frac{1}{2} \cdot \sum_{p = 0}^{N} {(- 1)}^{p} \cdot p \cdot ln det (R_{Δ_{p}}^{(2)}); \end{array}$ here, $N : = dim X$ and $Δ_{p} : = A_{p} A_{p}^{} + A_{p + 1}^{} A_{p + 1}$ is the cellular Laplacian [20, Lemma 3.30] associated with matrices $A_{p}$ describing the cellular boundary operator of $C_{}^{(2)} (G ↷ X)$ in degree p (with respect to cellular bases chosen in each degree).

The set of a-computable reals is closed under addition and subtraction; this can be seen as in the case $a = 0$ [32, Theorem 1.2(5)]. Therefore, it suffices to show that $ln det (R_{Δ_{p}}^{(2)})$ is a-computable for each $p \in {0, \dots, N}$ .

So, let $p \in {0, \dots, N}$ and let $α (R_{Δ_{p}}^{(2)})$ denote the p-th Novikov–Shubin invariant of $Δ_{p}$ . As the Novikov–Shubin invariants of X are positive, also $α (R_{Δ_{p}}^{(2)})$ is positive [20, Lemma 2.17]. Thus, there exist $M, α \in Q$ with $\begin{array}{l} {‖ R_{Δ_{p}}^{(2)} ‖}_{\infty} < M < \infty and 0 < α < α (R_{Δ_{p}}^{(2)}) . \end{array}$ Let $c_{p}$ denote the number of p-cells of X. Then, the combinatorial description of $L^{2}$ -torsion and the fact that ${dim}_{R G} ker (R_{Δ_{}}^{(2)}) = b_{}^{(2)} (G ↷ X) = 0$ shows that there exists a $C \in Q_{> 0}$ such that [20, Theorem 3.172(5)]: $\begin{matrix} \forall_{K \in N} 0 ⩽ - 2 \cdot ln (det (R_{Δ_{p}}^{(2)})) + 2 \cdot c_{p} \cdot ln M - \sum_{k = 1}^{K} \frac{1}{k} \cdot c {(Δ_{p}, M)}_{k} ⩽ \frac{C}{K^{α}} \end{matrix}$ Because the word problem of G is of degree a, because logarithms of rationals are computable [4], and by Proposition 3.17, the sequence $\begin{matrix} {(c_{p} \cdot ln M - \frac{1}{2} \cdot \sum_{k = 1}^{K} \frac{1}{k} \cdot c {(Δ_{p}, M)}_{k})}_{K \in N} \end{matrix}$ is of degree a. Moreover, the error estimate sequence ${(1 / 2 \cdot C / K^{α})}_{K \in N}$ is computable. Therefore, $ln (det (R_{Δ_{p}}^{(2)}))$ is an a-computable number (Proposition 3.4). □

8. The computation of $L^{2}$ -Betti numbers of groups

In analogy with work of Nabutovsky and Weinberger on the computation of ordinary Betti numbers of finitely presented groups [22], we obtain:

Theorem 8.1.
Let a be a Turing degree. Then there exists an algorithm of Turing degree at most $a^{(4)}$ that
given a finitely generated group G and a finite generating set S of G, together with an algorithm of degree at most a solving the word problem for G with respect to S, and given $k \in N$ ,

computes the binary expansion for $b_{k}^{(2)} (G)$ .

Here, “computing the binary expansion for $b_{k}^{(2)} (G)$ ” means the following: if $b_{k}^{(2)} (G)$ is finite, then the binary expansion of this real number is computed; otherwise, the value $+ \infty$ is returned.

Similarly to Nabutovsky and Weinberger, we rewrite $b_{k}^{(2)} (G)$ as $\begin{array}{l} (2) & b_{k}^{(2)} (G) = sup_{i \in N} inf_{j \in N_{⩾ i}} {dim}_{R G} (im (φ_{i j} : M_{i} \to M_{j})), \end{array}$ where $({(M_{i})}_{i \in N}, {(φ_{i j})}_{i \in N, j \in N_{⩾ i}})$ is a directed family of finitely generated $R G$ -modules that we can compute from S and the given algorithm for the word problem of G with respect to S. The modules $M_{i}$ arise as homology of finitely presented complexes over G with respect to S. We introduce the following terminology:
Definition 8.2 (finitely presented complex).

Let S be a finite generating set of a group G and let $k \in N$ . We write $[k + 1] : = {0, \dots, k + 1}$ . A finitely presented complex of length k over G with respect to S is a pair $({(n_{p})}_{p \in [k + 1]}, {(A_{p})}_{p \in [k + 1]})$ , consisting of natural numbers $n_{0}, \dots, n_{k + 1}$ and matrices $A_{p} \in M_{n_{p} \times n_{p - 1}} (Z [S^{*}])$ for all $p \in [k + 1]$ with the property that for all $p \in {1, \dots, k + 1}$ we have (as matrices over $Z [G]$ ) $\begin{matrix} A_{p} \cdot A_{p - 1} = 0 . \end{matrix}$

In particular, a finitely presented complex over G describes a partial $Z [G]$ -chain complex with based free $Z [G]$ -chain modules of finite rank.

Proof of Theorem 8.1.
We proceed in the following steps: We describe an algorithm that produces chain complexes whose homology groups give a description of $b_{k}^{(2)} (G)$ as in Equation (2). We then go into the details of the computations of ${dim}_{R G} (im φ_{i j})$ and how the sup-inf affects the overall degree of compatibility.

Let T be the given algorithm of degree at most a solving the word problem for G with respect to S. From the given finite generating set S, we obtain the sum of the augmentation maps:

Inductively, we can algorithmically extend this to a resolution up to degree $k + 1$ :

We can recursively enumerate $ker ε$ using the algorithm T. More precisely, we can algorithmically (from S and T) compute an ascending sequence ${(S_{i})}_{i \in N}$ of finite sets and maps ${(π_{i} : S_{i} \to ker ε)}_{i \in N}$ with $⋃_{i \in N} π_{i} (S_{i}) = ker ε$ . We then consider for each $i \in N$ the complex

where $\partial_{1, i} (x \cdot 1) = π_{i} (x)$ for all $x \in S_{i}$ . Inductively over the degrees and the previously constructed finitary intermediate steps, this leads to a sequence ${(C_{}^{i})}_{i \in N}$ of partial $Z [G]$ -chain complexes (up to degree $k + 1$ ) with the following properties:
For each $i \in N$ and each $p \in {0, \dots, k + 1}$ , the chain module $C_{p}^{i} = ⨁_{X_{p, i}} Z [G]$ is free over a finite set $X_{p, i}$ .

We have $X_{p, i} \subset X_{p, j}$ for all $p \in {0, \dots, k + 1}$ , $i \in N$ , $j \in N_{⩾ i}$ .

The union/colimit $⋃_{i \in N} C_{}^{i}$ is a partial resolution of $Z$ over $Z [G]$ up to degree $k + 1$ .

For each $p \in {0, \dots, k + 1}$ , the sequence ${(X_{p, i})}_{i \in N}$ is algorithmically enumerable from S and T.

Moreover, the corresponding matrices of the boundary operators of $C_{}^{i}$ are also algorithmically computable from S and T; similarly, for the matrices that describe the inclusions $C_{}^{i} ↪ C_{}^{j}$ for all $j \in N_{⩾ i}$ .
In other words: we can algorithmically compute from S and T a corresponding sequence of finitely presented complexes of length k over G with respect to S (in the sense of Definition 8.2).

For $i \in N$ , we set $D_{}^{i} : = R G \otimes_{Z G} C_{}^{i}$ . We switch from $ℓ^{2} G$ to the group von Neumann algebra* $R G$ [14, Definition 2.23] so that we can use the full power of the algebraic version of the theory [20, Chapter 6][14, Chapter 4.2]. Because $R G \otimes_{Z G} \cdot$ and homology are compatible with directed colimits, we obtain $\begin{matrix} H_{k} (G; R G) ≅_{R G} \underset{i \in N}{colim} H_{k} (D_{}^{i}) . \end{matrix}$ Hence, we have [20, proof of Theorem 6.54, Equation (6.55)] $\begin{array}{l} b_{k}^{(2)} (G) = sup_{i \in N} inf_{j \in N_{⩾ i}} {dim}_{R G} (im (φ_{i j} : H_{k} (D_{}^{i}) \to H_{k} (D_{}^{j}))), \end{array}$ where $φ_{i j} : H_{k} (D_{}^{i}) \to H_{k} (D_{}^{j})$ is the $R G$ -map induced by the inclusion $C_{}^{i} ↪ C_{}^{j}$ . Given i, the sequence ${(dim im (φ_{i j}))}_{j \in N_{⩾ i}}$ is decreasing. Moreover, the arising sequence in i is increasing. Thus, $\begin{array}{l} (3) & b_{k}^{(2)} (G) = lim_{i \to \infty} lim_{N_{⩾ i} ∋ j \to \infty} {dim}_{R G} (im (φ_{i j} : H_{k} (D_{}^{i}) \to H_{k} (D_{*}^{j}))) . \end{array}$

As second step, we consider the terms ${dim}_{R G} (im φ_{i j})$ : For all $i, j \in N$ with $j ⩾ i$ , the dimension ${dim}_{R G} (im φ_{i j})$ can be algorithmically computed through Lemma 8.5 below from the finite presentations of the complexes constructed above. More precisely, from S and T, we can algorithmically compute a function $q : N^{3} \to Q$ of degree at most a with the following properties:
For all $i, j \in N$ with $j < i$ , we have $q (i, j, n) = 0$ .

For all $i, j \in N$ with $j ⩾ i$ , the sequence ${(q (i, j, n))}_{n \in N}$ converges to ${dim}_{R G} im φ_{i j}$ .

Finally, we resolve the double limit: Note that in Lemma 3.14, only the outer limit can converge to $+ \infty$ . We therefore obtain from Lemma 3.14 that we can algorithmically compute from S and T the binary expansion of $\begin{matrix} b_{k}^{(2)} (G) = lim_{i \to \infty} lim_{j \to \infty} lim_{n \to \infty} q (i, j, n) \end{matrix}$ through an algorithm of Turing degree $a^{(3 + 1)}$ . □
Remark 8.3.
The argument of Nabutovsky and Weinberger for ordinary Betti numbers of groups is based on an algorithmic construction of a sequence of finite complexes that approximate a classifying space of the group in question. In the same way, one could also prove Theorem 8.1; however, in our equivariant setting, the algebraic approach seemed easier to describe.

It remains to prove Lemma 8.5. We first rewrite the dimension of the image as sums and differences of dimensions of kernels.
Lemma 8.4 (dimension of the image of a map in homology).

Let G be a group and let $(D_{*}, \partial_{*}^{D})$ be an $R G$ -chain complex consisting of free $R G$ -modules of finite rank. Let $i_{*} : C_{*} \to D_{*}$ be the inclusion of a subcomplex. Then, for all $k \in N$ , we have $\begin{matrix} {dim}_{R G} im H_{k} (i_{*}) = {dim}_{R G} ker \partial_{k}^{C} + {dim}_{R G} ker \partial_{k + 1}^{D} - {dim}_{R G} ker (\partial_{k + 1}^{D} + i_{k}) \end{matrix}$ where $\partial_{k + 1}^{D} + i_{k}$ denotes the map $\begin{array}{l} \partial_{k + 1}^{D} + i_{k} : D_{k + 1} \oplus C_{k} & \to D_{k} \\ (x, y) & \mapsto \partial_{k + 1}^{D} x + y . \end{array}$

Proof.
The von Neumann dimension is additive for short exact sequences [14, Theorem 4.7(ii)]. In particular, we can compute the von Neumann dimension of quotients and for any $R G$ -linear map, the dimensions of its kernel and its image add up to the dimension of its domain. We have $\begin{matrix} im H_{k} (i_{*}) ≅ (ker \partial_{k}^{C}) / (im \partial_{k + 1}^{D} \cap C_{k}) . \end{matrix}$ Using additivity, we obtain $\begin{array}{l} {dim}_{R G} im H_{k} (i_{k}) & = {dim}_{R G} ker \partial_{k}^{C} - dim (im \partial_{k + 1}^{D} \cap C_{k}) \\ = {dim}_{R G} ker \partial_{k}^{C} - {dim}_{R G} im \partial_{k + 1}^{D} - {dim}_{R G} C_{k} + {dim}_{R G} im (\partial_{k + 1}^{D} + i_{k}) \\ = {dim}_{R G} ker \partial_{k}^{C} - ({dim}_{R G} D_{k + 1} - {dim}_{R G} ker \partial_{k + 1}^{D}) \\ - {dim}_{R G} C_{k} + ({dim}_{R G} (D_{k + 1} \oplus C_{k}) - {dim}_{R G} ker (\partial_{k + 1}^{D} + i_{k})) \\ = {dim}_{R G} ker \partial_{k}^{C} + {dim}_{R G} ker \partial_{k + 1}^{D} - {dim}_{R G} ker (\partial_{k + 1}^{D} + i_{k}), \end{array}$ as claimed. □
Lemma 8.5 (dimension of the image of a map in homology, algorithmically).

Let a be a Turing degree. There is an algorithm of Turing degree at most a that

given a finitely generated group G and a finite generating set S of G, together with an algorithm of degree at most a solving the word problem for G with respect to S, given $k \in N$ , and finitely presented complexes $(m_{*}, A_{*})$ and $(n_{*}, B_{*})$ of length k over G with respect to S with $m_{j} ⩽ n_{j}$ and $B_{j} |_{m_{j} \times m_{j - 1}} = A_{j}$ for all $j \in [k]$ ,

computes a sequence $N \to Q$ that converges to ${dim}_{R G} H_{k} (i_{*})$ , where $i_{*}$ denotes the inclusion between the two complexes.

Proof.

By Lemma 8.4, we have $\begin{array}{l} {dim}_{R G} H_{k} (i_{*}) & = {dim}_{R G} ker R_{A_{k}}^{(2)} + {dim}_{R G} ker R_{B_{k + 1}}^{(2)} - {dim}_{R G} ker R_{E_{k}}^{(2)} \\ = b^{(2)} (A_{k}; G) + b^{(2)} (B_{k + 1}; G) - b^{(2)} (E_{k}; G), \end{array}$ where $E_{k}$ denotes the matrix obtained by stacking $B_{k + 1}$ on top of $(I_{m_{k}} | 0)$ . We can thus apply the algorithm from Lemma 4.1 to the three matrices $A_{k}$ , $B_{k + 1}$ , $E_{k}$ (which are computable from the input) to compute this dimension. □

Footnotes

Sets of mapping degrees

Neofytidis, Shicheng Wang, and Zhongzi Wang [23] study the question of which subsets of $Z$ (containing 0) are realisable as sets of mapping degrees between oriented closed connected manifolds. Comparing cardinalities shows that most subsets of $Z$ are not realisable in this way. Using a computability argument, we can give “explicit” examples of non-realisable sets. Proposition A.1.

Let M and N be oriented closed connected manifolds of the same dimension. Then the set $\begin{matrix} deg (M, N) : = {deg f | f \in map (M, N)} \subset Z \end{matrix}$ of mapping degrees is recursively enumerable.

Proof.

Let $n : = dim M = dim N$ . It is well-known that M and N are homotopy equivalent to finite simplicial complexes [15,29]. Let $M \to | X |$ and $N \to | Y |$ be such homotopy equivalences and let $[X] \in H_{n} (| X |; Z)$ , $[Y] \in H_{n} (| Y |; Z)$ be the corresponding images of the fundamental classes. As mapping degrees can be described in terms of the effect on $H_{n} (\cdot; Z)$ , we obtain that $deg (M, N)$ coincides with the set $\begin{matrix} deg (X, Y) : = {d \in Z | \exists_{f \in map (| X |, | Y |)} H_{n} (f; Z) [X] = d \cdot [Y]} . \end{matrix}$ Therefore, it suffices to show that $deg (X, Y)$ is recursively enumerable.

We use simplicial approximation to show that $deg (X, Y)$ indeed is recursively enumerable: for $k \in N$ , let $X (k)$ the k-th iterated barycentric subdivision of X. In view of the simplicial approximation theorem, we have $\begin{matrix} deg (X, Y) = ⋃_{k \in N} {deg}^{s} (X (k), Y), \end{matrix}$ where $\begin{matrix} {deg}^{s} (X (k), Y) : = {d \in Z | \exists_{f \in {map}^{s} (X (k), Y)} H_{n} (| f |; Z) [X] = d \cdot [Y]} \end{matrix}$ is the set of mapping degrees of simplicial maps on these subdivisions. Recursive enumerability of $deg (X, Y)$ can thus be established as follows:

For every $k \in N$ , the finite simplicial complex $X (k)$ can be algorithmically computed from X.

For every $k \in N$ , the set ${map}^{s} (X (k), Y)$ of all simplicial maps $X (k) \to Y$ is recursive.

For every $k \in N$ and each simplicial map $f : X (k) \to Y$ , we can algorithmically compute the unique $d \in Z$ with $H_{n} (| f |; Z) [X] = d \cdot [Y]$ via simplicial homology.

□

Example A.2.

Let $A \subset Z$ be a set that is not recursively enumerable (e.g., the complement of a halting problem set). Then, $A_{0} : = A \cup {0}$ contains 0, but $A_{0}$ is not recursively enumerable and thus cannot be realised as a set of mapping degrees between oriented closed connected manifolds (Proposition A.1).

Torsion-free solvable groups

The goal of this appendix is to prove the following proposition.

Because there are only countably many algorithms that could solve the word problem and thus only countably many groups (up to isomorphism) with solvable word problem, we obtain:

In order to prove Proposition B.1, we start with the following class of groups.

However, unless P is empty, $Z [P^{- 1}]$ will not be finitely generated. We thus use the following version of the embedding theorem by Neumann–Neumann.

Ultimately, we want to distinguish the isomorphism types of $H (Z [P^{- 1}])$ . For this purpose, we introduce the following invariant, which is an alteration of the notion of type for rank-one torsion-free abelian groups [10, Chapter VII].

This invariant has the following properties:

Acknowledgements

CL is grateful to Nicolaus Heuer for discussions on an earlier incarnation of these questions. We would like to thank Wolfgang Lück and Thomas Schick for pointing us to the estimates for $L^{2}$ -torsion. We appreciate the detailed report and suggestions by the first referee. We would like to thank Vasco Brattka for a discussion on this article. We are grateful to Francesco Fournier-Facio for pointing out to us the strategy for proving Proposition .

This work was supported by the CRC 1085 Higher Invariants (Universität Regensburg, funded by the DFG) and is partially based on MU’s MSc project.

References

M.F.

Atiyah, Elliptic operators, discrete groups and von Neumann algebras, in: Colloque “Analyse et Topologie” en l’honneur de Henri Cartan, Société Mathématique de France (SMF), 1976, pp. 43–72.

Austin, Rational group ring elements with kernels having irrational dimension, Proc. Lond. Math. Soc. (3) 107(6) (2013), 1424–1448. doi:10.1112/plms/pdt029.

Avigad,

de Moura and

Kong, Theorem proving in Lean, 2021. Release 3.23.0, https://leanprover.github.io/theorem_proving_in_lean/.

W.E.

Egbert, Personal calculator algorithms IV: Logarithmic functions, Hewlett-Packard Journal 4 (1978), 29–32.

Elek and

Szabó, Hyperlinearity, essentially free actions and

L^{2}

-invariants. The sofic property, Math. Ann. 332(2) (2005), 421–441. doi:10.1007/s00208-005-0640-8.

Elek and

Szabó, On sofic groups, J. Group Theory 9(2) (2006), 161–171. doi:10.1515/JGT.2006.011.

Fournier-Facio,

Löh and

Moraschini, Bounded cohomology of finitely presented groups: Vanishing, non-vanishing, and computability, Annali della Scuola Normale Superiore di Pisa (2021), to appear.

Ł.

Grabowski, On Turing dynamical systems and the Atiyah problem, Invent. Math. 198(1) (2014), 27–69. doi:10.1007/s00222-013-0497-5.

Ł.

Grabowski, Vanishing of

l^{2}

-cohomology as a computational problem, Bull. Lond. Math. Soc. 47(2) (2015), 233–247. doi:10.1112/blms/bdu114.

10.

P.A.

Griffith, Infinite Abelian Group Theory, University of Chicago Press, Chicago, Ill.–London, 1970.

11.

Groth,

l_{2}

-Bettizahlen endlich präsentierter Gruppen, BSc thesis, Universität Göttingen, 2012.

12.

Heuer, The full spectrum of scl on recursively presented groups, Geometricae Dedicata (2019), to appear.

13.

Heuer and

Löh, Transcendental simplicial volumes, Annales de l’Institut Fourier (2021), to appear.

14.

Kammeyer, Introduction to

ℓ^{2}

-Invariants, Springer, 2019.

15.

R.C.

Kirby and

L.C.

Siebenmann, On the triangulation of manifolds and the Hauptvermutung, Bull. Amer. Math. Soc. 75 (1969), 742–749. doi:10.1090/S0002-9904-1969-12271-8.

16.

P.A.

Linnell, Division rings and group von Neumann algebras, Forum Math. 5(6) (1993), 561–576.

17.

Löh and

Uschold,

L^{2}

-Betti numbers and computability of reals – Lean project. https://gitlab.com/L2-comp/l2-comp-lean, 2022.

18.

Löh and

Uschold,

L^{2}

-Betti numbers and computability of reals, 2022, arXiv:2202.03159v2.

19.

Lück, Approximating

L^{2}

-invariants by their finite-dimensional analogues, Geom. Funct. Anal. 4(4) (1994), 455–481. doi:10.1007/BF01896404.

20.

Lück,

L^{2}

-Invariants: Theory and Applications to Geometry and K-Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], Vol. 44, Springer, 2002.

21.

C.F.

MillerIII, Decision problems for groups – survey and reflections, in: Algorithms and Classification in Combinatorial Group Theory. Lectures of a Workshop on Algorithms, Word Problems and Classification in Combinatorial Group Theory, Held at MSRI, Berkeley, CA, USA, January 1989, Springer-Verlag, 1989, pp. 1–59.

22.

Nabutovsky and

Weinberger, Betti numbers of finitely presented groups and very rapidly growing functions, Topology 46(2) (2007), 211–223. doi:10.1016/j.top.2007.02.002.

23.

Neoftyidis,

Wang and

Wang, Realising sets of integers as mapping degree sets, Bulletin of the London Mathematical Society (2023), doi:10.1112/blms.12813.

24.

B.H.

Neumann and

Neumann, Embedding theorems for groups, Journal of the London Mathematical Society s1-34(4) (1959), 465–479. doi:10.1112/jlms/s1-34.4.465.

25.

Pichot,

Schick and

Zuk, Closed manifolds with transcendental

L^{2}

-Betti numbers, J. Lond. Math. Soc., II. Ser. 92(2) (2015), 371–392. doi:10.1112/jlms/jdv026.

26.

Rettinger and

Zheng, Computability of real numbers, in: Handbook of Computability and Complexity in Analysis, Springer, Cham, 2021, pp. 3–28. doi:10.1007/978-3-030-59234-9_1.

27.

J.J.

Rotman, An Introduction to the Theory of Groups, Graduate Texts in Mathematics, Vol. 148, Springer-Verlag, 1995.

28.

Schick,

L^{2}

-Determinant class and approximation of

L^{2}

-Betti numbers, Trans. Am. Math. Soc. 353(8) (2001), 3247–3265. doi:10.1090/S0002-9947-01-02699-X.

29.

L.C.

Siebenmann, On the homotopy type of compact topological manifolds, Bull. Amer. Math. Soc. 74 (1968), 738–742. doi:10.1090/S0002-9904-1968-12022-1.

30.

S.G.

Simpson, Degrees of unsolvability: A survey of results, Barewise, Jon, 1977, pp. 631–652.

31.

The mathlib Community. The Lean Mathematical Library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP ’2), 2020.

32.

Zheng, On the Turing degrees of weakly computable real numbers, J. Log. Comput. 13(2) (2003), 159–172. doi:10.1093/logcom/13.2.159.

L 2 -Betti numbers and computability of reals

Abstract

Keywords

1. Introduction

1.1. Main results

Theorem 1.1 (Theorem 4.2).

Theorem 1.2 (Theorem 5.7).

Theorem 1.3 (Theorem 7.1).

Theorem 1.4 (Corollary 5.12).

1.2. Related work on computability and L 2 -invariants

1.3. Implementation in Lean

1.4. Organisation of this article

2. Preliminaries on L 2 -Betti numbers

2.1. L 2 -Betti numbers

Definition 2.1 ( L 2 -Betti numbers arising from a group).

Remark 2.2 (self-adjointness).

2.2. Spectral measures

Definition 2.3 (trace [20, Equation 3.170]).

Proposition 2.4 (characterisation of the spectral measure [14, Definition 5.9]).

Proposition 2.5 ( L 2 -Betti numbers via spectral measure [19][14, p. 97]).

2.3. Characteristic sequences

Definition 2.6 (characteristic sequence [20, Definition 3.171]).

Proposition 2.7 ( L 2 -Betti numbers via characteristic sequences [20, Theorem 3.172 (1), (2)]).

3. Preliminaries on computability

3.1. Turing degrees

Definition 3.1 (Turing reducible, equivalent, degree).

Proposition 3.2 ([30, Proposition 1.2]).

3.2. Computability of real numbers

Definition 3.3 (a-computability).

Proposition 3.4 (characterisation of computability).

Lemma 3.11 (from limits to effective limits).

Proof. Given the present assumptions, divergence to + ∞ is equivalent to (positive) unboundedness of the sequence, i.e., to ∀ K ∈ N ∃ k ∈ N q k > K , which can be checked by an algorithm of degree at most a ( 2 ) . □ Lemma 3.14 (iterated limits).

3.5. The word problem and computability of traces over group rings

Definition 3.15 (word problem).

4.1. Algorithmic computation of dimensions of kernels

Theorem 4.2 (right-computability).

Theorem 4.5 (left- and effective computability).

5.1. The determinant class conjecture

Definition 5.1 (Fuglede–Kadison determinant).

Remark 5.2. There is only a convergence problem near 0 and no problem for “ x → ∞ ”, as μ A is supported on [ 0 , ‖ R A ( 2 ) ‖ ] . Definition 5.3 (determinant class conjecture).

Theorem 6.1 (Lück’s approximation theorem [19, Theorem 0.1]).

Theorem 6.2 (Lück’s approximation theorem for matrices [20, Chapter 13][14, p. 97]).

Definition 6.3 (adapted sequence).

Lemma 6.4 (computability of an adapted sequence).

Footnotes

Sets of mapping degrees

Torsion-free solvable groups

Acknowledgements

References

1.2. Related work on computability and $L^{2}$ -invariants

1.3. Implementation in $Lean$

2. Preliminaries on $L^{2}$ -Betti numbers

2.1. $L^{2}$ -Betti numbers

Definition 2.1 ( $L^{2}$ -Betti numbers arising from a group).

Proposition 2.5 ( $L^{2}$ -Betti numbers via spectral measure [19][14, p. 97]).

Proposition 2.7 ( $L^{2}$ -Betti numbers via characteristic sequences [20, Theorem 3.172 (1), (2)]).

Remark 5.2.
There is only a convergence problem near 0 and no problem for “ $x \to \infty$ ”, as $μ_{A}$ is supported on $[0, ‖ R_{A}^{(2)} ‖]$ .
Definition 5.3 (determinant class conjecture).