Introduction
A C∗ ^* ∗ -algebra A A A is nuclear if the identity map on A A A is the point-norm limit of maps that factor through finite-dimensional matrix algebras by unital completely positive (ucp) maps, that is, for every finite tuple a ⃗ \vec{a} a from A A A and every ϵ > 0 \epsilon> 0 ϵ > 0 , there are n ≥ 1 n \ge1 n ≥ 1 and ucp maps ϕ : A → M n ( C ) \phi: A \to M_n(\mathbb{C}) ϕ : A → M n ( C ) and ψ : M n ( C ) → A \psi: M_n(\mathbb{C}) \to A ψ : M n ( C ) → A satisfying max i ∥ ( ψ ∘ ϕ ) ( a i ) − a i ∥ < ϵ \max_i \|(\psi\circ\phi)(a_i) - a_i\| < \epsilon max i ∥ ( ψ ∘ ϕ ) ( a i ) − a i ∥ < ϵ . Nuclearity is one of the central finiteness conditions in operator algebras: it is equivalent to the uniqueness of the C∗ ^* ∗ -norm on algebraic tensor products A ⊙ B A \odot B A ⊙ B , it is the C∗ ^* ∗ -algebraic analogue of amenability for groups (a discrete group G G G being amenable exactly when C r ∗ ( G ) C_r^*(G) C r ∗ ( G ) is nuclear), and it is a standing hypothesis in the Elliott classification programme. This paper is concerned with the computable content of nuclearity. The setting is the computable structure theory of C ∗ C^* C ∗ -algebras developed by Fox [11 ] , in which a presentation A # A^\# A # of a C ∗ C^* C ∗ -algebra A A A consists of a distinguished sequence of points whose rational ∗ * ∗ -polynomial combinations are dense; the presentation is c.e. if the norms of these generated points are uniformly right-c.e., and computable if they are uniformly computable. In our previous papers [10 , 8 ] , we began a programme of computable K K K -theory for C ∗ C^* C ∗ -algebras, carried out in detail for UHF and AF algebras; several of the tools developed there—the uniformly computable presentations of matrix amplifications [8 Proposition 1.7] , the passage from computably weakly stable relations to c.e. closed sets [8 Theorem 1.12] , and computable AF-certificates [10 Main Theorem 1] —are used throughout the present paper. The index set computations of [10 ] , showing that the set of indices of computable presentations of UHF algebras, and likewise of (simple) AF algebras, are Π 2 0 \Pi^0_2 Π 2 0 -complete, are the direct precursors of Section 6 below.
The basic question we address is: what does it mean for a presentation to be nuclear in an effective way, and is this stronger than being a computable presentation of a nuclear algebra? Given that our earlier works considered very special subclasses of the class of nuclear algebras, zooming out and considering the broader class as a whole is a natural next step. There are several reasonable ways to effectivize the definition above. The most direct is to ask that the ucp maps witnessing the completely positive approximation property be computable and be produced by an algorithm; we call such a presentation effectively nuclear (Definition 3.1 (1)). One may instead effectivize the Choi–Effros form of nuclearity, asking for a uniformly computable sequence of finite-rank ucp maps A # → A # A^\# \to A^\# A # → A # with computably bounded ranks converging computably pointwise to the identity; we call this effectively Choi–Effros nuclear (Definition 3.1 (2)). Our first main result is that none of these distinctions is real: nuclearity effectivizes automatically.
Theorem A (Theorem 3.5 ). Let A # A^\# A # be a presentation of a C ∗ C^* C ∗ -algebra A A A . The following are equivalent:
(1) A # A^\# A # is computable and A A A is nuclear;
(2) A # A^\# A # is effectively nuclear;
(3) A # A^\# A # is computable and effectively Choi–Effros nuclear.
Moreover, the passage from (1) to (2) is uniform in a unital index for A # A^\# A # .
We note that the implication (2) ⇒ \Rightarrow ⇒ (1) contains the observation that effective nuclearity already forces the presentation to be computable (Lemma 3.2). It is natural to compare Theorem A with the situation for groups, where the analogous phenomenon holds: a computable presentation of a group admits a computable Følner sequence precisely when the group is amenable (see [6 ] ).
The engine behind Theorem A is an effective form of the Arveson extension theorem, which we believe is of independent interest and which occupies § 3 . Given a tuple a ⃗ = ( a 1 , … , a k ) \vec{a}=(a_1,\ldots,a_k) a = ( a 1 , … , a k ) in A A A and n ≥ 1 n\geq1 n ≥ 1 , consider the n n n -th matrix numerical range
K a ⃗ , n : = { ( Φ ( a 1 ) , … , Φ ( a k ) ) : Φ : A → M n ( C ) u c p } , K_{\vec{a},n}:=\{(\Phi(a_1),\ldots,\Phi(a_k)):\Phi:A\to M_n(\mathbb{C})\ \mathrm{ucp}\}, K a , n := {( Φ ( a 1 ) , … , Φ ( a k )) : Φ : A → M n ( C ) ucp } ,
a compact convex subset of the finite-dimensional space E k , n = ( M n ( C ) ) k E_{k,n}=(M_n(\mathbb{C}))^k E k , n = ( M n ( C ) ) k ; for n = 1 n=1 n = 1 this is the classical joint numerical range. The key technical point is that K a ⃗ , n K_{\vec{a},n} K a , n is computably compact, uniformly in all of its data. This is proved by identifying, via Choi’s correspondence, the support function of K a ⃗ , n K_{\vec{a},n} K a , n with a constrained supremum over the state space of M n ( A ) M_n(A) M n ( A ) , and then dualising: the constrained supremum is shown to equal an infimum of a computable quantity over a computably bounded set of self-adjoint matrices (Lemma 2.4). With computable compactness in hand, one can decide whether a prescribed tuple b ⃗ \vec b b of matrices is approximately attainable, and then produce an actual computable ucp map attaining it:
Theorem B (Theorem 2.8). There is an algorithm which, on input a unital index for a computable presentation A # A^\# A # of a unital C ∗ C^* C ∗ -algebra A A A , integers n , k ≥ 1 n,k \ge1 n , k ≥ 1 , codes for generated points a ⃗ \vec a a of A # A^\# A # , a code for a rational b ⃗ ∈ E k , n \vec b \in E_{k,n} b ∈ E k , n , and a rational δ > 0 \delta> 0 δ > 0 such that d ( b ⃗ , K a ⃗ , n ) < δ d(\vec b,K_{\vec a,n}) < \delta d ( b , K a , n ) < δ , outputs an index for a computable ucp map Φ : A → M n ( C ) \Phi:A \to M_n(\mathbb{C}) Φ : A → M n ( C ) with max 1 ≤ i ≤ k ∥ Φ ( a i ) − b i ∥ < δ \max_{1\le i\le k}\|\Phi(a_i)-b_i\| < \delta max 1 ≤ i ≤ k ∥Φ ( a i ) − b i ∥ < δ .
The apparent uncomputability of the Arveson extension theorem is what obstructs the naive attempts to prove Theorem A, and Theorem B removes that obstruction in exactly the approximate, matrix-valued form that the definition of nuclearity requires. A pleasant byproduct of the case n = 1 n=1 n = 1 is that the computable states of any computable presentation of a unital C ∗ C^* C ∗ -algebra are weak∗ ^* ∗ -dense in its state space (Corollary 2.9); in particular, every such presentation has a computable state, a fact we use repeatedly and which was previously available to us only through ad hoc constructions in concrete examples.
Sections 4 and 5 turn to the Cuntz algebra O 2 O_2 O 2 and to the strongest of the effective nuclearity conditions we consider. In Section 4 we prove:
Theorem C (Theorem 4.4). For every n ≥ 2 n \ge2 n ≥ 2 , the Cuntz algebra O n O_n O n is computably categorical, that is, any two computable presentations of O n O_n O n are computably isomorphic.
The proof combines an effective Baire category theorem with the fact that every computable presentation of O n O_n O n contains a computable generating Cuntz n n n -tuple; the genericity input is a density theorem of Rørdam [21 ] on unitaries inducing inner automorphisms. Theorem C allows us to speak of the computable presentation of O 2 O_2 O 2 , and it yields an effective form of the Kirchberg-Phillips absorption theorem: for a simple, separable C ∗ C^* C ∗ -algebra A A A with computable presentation A # A^\# A # , the algebra A A A is nuclear if and only if the tensor product presentation ( A ⊗ O 2 ) # (A\otimes O_2)^\# ( A ⊗ O 2 ) # is computably isomorphic to O 2 O_2 O 2 (Corollary 4.5).
Kirchberg’s theorem also characterises nuclearity of a separable unital C ∗ C^* C ∗ -algebra by the existence of a unital embedding into O 2 O_2 O 2 whose image is the range of a conditional expectation. Effectivizing this characterisation seems more challenging than those conditions considered in Theorem A, and so we isolate it as Definition 5.1: A # A^\# A # is effectively Kirchberg nuclear if there is a computable embedding A # ↪ O 2 A^\# \hookrightarrow O_2 A # ↪ O 2 admitting a computable conditional expectation O 2 → A # O_2 \to A^\# O 2 → A # . Unlike the conditions in Theorem A, we do not know whether this one is automatic:
Question A (Question 5.4). Is every computable presentation of a nuclear C ∗ C^* C ∗ -algebra effectively Kirchberg nuclear?
The difficulty is that the classical proof of Kirchberg’s theorem is of a quite different character from the approximation arguments underlying Theorem A and we see no route to effectivizing it directly. We offer a useful reformulation of this property, namely that A # A^\# A # is effectively Kirchberg nuclear if and only if it embeds computably, with computable expectation, into some computable presentation of a simple nuclear C ∗ C^* C ∗ -algebra (Lemma 5.2(3)). We then exhibit such an ambient algebra in several classes of interest. In the commutative case, the ambient algebra is the CAR algebra, reached through an effective version of the Miljutin–Pełczyński theorem [19 , 20 ] on embeddings of C ( X ) C(X) C ( X ) into C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) with expectation; in the AF case it is a UHF algebra built from a computable AF-certificate.
Theorem D. (Corollary 5.8, Proposition 5.9). Every computable presentation of a commutative unital C ∗ C^* C ∗ -algebra is effectively Kirchberg nuclear, and so is every computable presentation of an AF algebra.
Since commutative C ∗ C^* C ∗ -algebras other than C \mathbb{C} C are never simple, Theorem D is not a consequence of the (straightforward) fact that computable presentations of simple nuclear algebras are effectively Kirchberg nuclear.
For group C ∗ C^* C ∗ -algebras, our approach is dynamical and the point of entry is the observation that the conditional expectation one needs comes from an invariant state. Precisely, if G # ↷ α A # G^\# \curvearrowright_\alpha A^\# G # ↷ α A # is a computable action and φ \varphi φ is an α \alpha α -invariant state on A A A which is computable on A # A^\# A # , then ∑ s a s u s ↦ ∑ s φ ( a s ) u s \sum_s a_su_s \mapsto\sum_s\varphi(a_s)u_s ∑ s a s u s ↦ ∑ s φ ( a s ) u s is a computable conditional expectation from A ⋊ α G A\rtimes_\alpha G A ⋊ α G onto C ∗ ( G ) C^*(G) C ∗ ( G ) (Lemma 5.12). (In fact, the existence of some conditional expectation onto C ∗ ( G ) C^*(G) C ∗ ( G ) forces the existence of an invariant state, so the hypothesis is necessary and sufficient.) Invariant states form a co-c.e. closed set in the (computably compact) state space of a computably presented nuclear C ∗ C^* C ∗ -algebra (Lemma 5.14), and amenability of G G G guarantees that this class is nonempty; when it is moreover a singleton , its unique member is computable member. This yields:
Theorem E. (Theorem 5.15, Corollaries 5.18 and 5.19). Let G # G^\# G # be a computable presentation of an amenable group G G G , and suppose G G G admits a computable action on a computably compact presentation of a compact metric space which is topologically free, minimal, and uniquely ergodic. Then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear. In particular, this holds whenever G G G admits a computable descending chain of finite-index normal subgroups with trivial intersection, and hence for every finitely presented, residually finite, amenable group.
Section 6 concerns the complexity of nuclearity as a property of indices. Writing Nuc for the set of indices of computable presentations of nuclear C ∗ C^* C ∗ -algebras, the proof of Theorem A shows in particular that Nuc is Π 2 0 \Pi^0_2 Π 2 0 (Proposition 6.1); we conjecture that it is Π 2 0 \Pi^0_2 Π 2 0 -complete (Question 6.2). Towards this end, we settle the analogous question for groups, in the sharper form that the hardness is visible already within the class of (indices of) groups:
Theorem F. (Theorems 6.5 and 6.9). The set Amen of indices of computable amenable groups is Π 2 0 \Pi^0_2 Π 2 0 -complete within the class Grp of indices of computable groups. The same is true of the set InnAmen of indices of computable inner amenable groups.
The construction interleaves two strategies: at stages where a fixed c.e. set W e W_e W e receives no new element, we build one more step of a copy of the free group F 2 F_2 F 2 (respectively, of S L 2 ( F 2 ( t ) ) SL_2(\mathbb{F}_2(t)) S L 2 ( F 2 ( t )) ), and at stages where W e W_e W e grows, we collapse the fragment built so far into a finite group. That the second strategy is always available rests on a theorem of Iwasawa [17 ] to the effect that the finite-index normal subgroups of a free group intersect trivially.
Transferring this through the universal group C ∗ C^* C ∗ -algebra construction gives the hardness half of the picture for C ∗ C^* C ∗ -algebras:
Theorem G (Corollary 6.10). The set of indices of c.e. presentations of nuclear C∗ ^* ∗ -algebras is Π 2 0 \Pi^0_2 Π 2 0 -hard.
The gap between Theorem G and a complete answer to Question 6.2 is precisely the question of whether that set is Π 2 0 \Pi^0_2 Π 2 0 (Question 6.11); the proof that Nuc is Π 2 0 \Pi^0_2 Π 2 0 uses computability of the presentation in an essential way, through the effective Arveson extension theorem, and so does not apply to merely c.e. presentations.
The paper is organised as follows. Section 2 develops the effective Arveson extension theorem and the computable compactness of matrix numerical ranges. Section 3 introduces the effective forms of nuclearity and proves Theorem A. Section 4 proves the computable categoricity of O n \mathcal{O}_n O n and deduces an effective Kirchberg–Phillips absorption result. Section 5 treats effective Kirchberg nuclearity, with subsections on commutative algebras, AF algebras, and group C∗ ^* ∗ -algebras. Section 6 is devoted to the Π 2 0 \Pi^0_2 Π 2 0 complexity results.
We assume familiarity with the basics of computable presentations of metric structures as it pertains to C∗ ^* ∗ -algebras; our earlier papers [10 ] and [8 ] as well as the recent textbook [13 ] are suitable references. A good source for the requisite C∗ ^* ∗ -algebra theory is [3 ] .
Conventions
Conventions. Throughout the paper, all C∗ ^* ∗ -algebras are assumed to be unital and all presentations of C∗ ^* ∗ -algebras are assumed to be computably unital , meaning that the unit is a computable point of the presentation. Note that a computably unital presentation need not be computable. A unital index for a computable and computably unital presentation consists of an index for the presentation together with an index for the unit. Since we will be assuming presentations are computably unital, when we say a presentation is computable we mean it is computable and computably unital.
AI Declaration Statement
While working on an initial draft of the paper, we uploaded our results to Claude Opus 5 for its opinion. It suggested an improvement to our results via the Effective Arveson Extension Theorem that is proved in Section 2. The arguments were reworked and rewritten to accommodate this suggestion. Also, it suggested an extension and application of our work on computability of crossed products (Proposition 5.11) which we then incorporated into Section 5. All of the writing of this paper was done by the authors and as such we take full responsibility for the contents of the paper.
Effective Arveson Extension
Throughout this section, we set E k , n : = ( M n ( C ) ) k E_{k,n} := (M_n(\mathbb{C}))^k E k , n := ( M n ( C ) ) k , which we view as a real vector space equipped with the real inner product
⟨ b ⃗ , c ⃗ ⟩ : = Re ∑ i = 1 k Tr ( c i ∗ b i ) \langle\vec{b},\vec{c}\rangle:= \operatorname{Re}\sum_{i=1}^{k}\operatorname{Tr}(c_i^*b_i) ⟨ b , c ⟩ := Re i = 1 ∑ k Tr ( c i ∗ b i )
and associated norm ∣ ⋅ ∣ \lvert\cdot\rvert ∣ ⋅ ∣ . Recall that for a matrix b ∈ M n ( C ) b \in M_n(\mathbb{C}) b ∈ M n ( C ) , the Hilbert-Schmidt norm ∥ b ∥ H S = Tr ( b ∗ b ) 1 / 2 \lVert b\rVert_{\mathrm{HS}} = \operatorname{Tr}(b^*b)^{1/2} ∥ b ∥ HS = Tr ( b ∗ b ) 1/2 satisfies ∥ b ∥ o p ≤ ∥ b ∥ H S \lVert b\rVert_{\mathrm{op}} \le\lVert b\rVert_{\mathrm{HS}} ∥ b ∥ op ≤ ∥ b ∥ HS , so bounds measured in ∣ ⋅ ∣ \lvert\cdot\rvert ∣ ⋅ ∣ give bounds in operator norm coordinatewise. We view E k , n E_{k,n} E k , n as equipped with its obvious standard presentation (see also [8 Subsection 1.2] ).
We write UCP ( A , M n ( C ) ) \operatorname{UCP}(A,M_n(\mathbb{C})) UCP ( A , M n ( C )) for the set of ucp maps A → M n ( C ) A \to M_n(\mathbb{C}) A → M n ( C ) . Given a tuple a ⃗ = ( a 1 , … , a k ) \vec{a}=(a_1,\ldots,a_k) a = ( a 1 , … , a k ) in A A A , set
K a ⃗ , n : = { ( Φ ( a 1 ) , … , Φ ( a k ) ) : Φ ∈ UCP ( A , M n ( C ) ) } ⊆ E k , n , K_{\vec{a},n}:=\{(\Phi(a_1),\ldots,\Phi(a_k)):\Phi\in\operatorname{UCP}(A,M_n(\mathbb{C}))\}\subseteq E_{k,n}, K a , n := {( Φ ( a 1 ) , … , Φ ( a k )) : Φ ∈ UCP ( A , M n ( C ))} ⊆ E k , n ,
which we think of as the n n n -th matrix (joint) numerical range of a ⃗ \vec{a} a . For n = 1 n=1 n = 1 this is exactly the usual joint numerical range
W ( a ⃗ ) : = { ( ω ( a 1 ) , … , ω ( a k ) ) : ω ∈ S ( A ) } , W(\vec{a}):=\{(\omega(a_1),\ldots,\omega(a_k)):\omega\in S(A)\}, W ( a ) := {( ω ( a 1 ) , … , ω ( a k )) : ω ∈ S ( A )} ,
where S ( A ) S(A) S ( A ) denotes the state space of A A A . The following fact is well-known:
Fact 2.1. UCP ( A , M n ( C ) ) \operatorname{UCP}(A,M_n(\mathbb{C})) UCP ( A , M n ( C )) is compact in the topology of pointwise weak convergence, and K a ⃗ , n K_{\vec{a},n} K a , n is a nonempty compact convex subset of E k , n E_{k,n} E k , n satisfying
∣ b ⃗ ∣ ≤ R ( a ⃗ ) : = ( n ∑ i ≤ k ∥ a i ∥ 2 ) 1 / 2 |\vec{b}|\leq R(\vec{a}):=\left(n\sum_{i\leq k}\lVert a_i\rVert^2\right)^{1/2} ∣ b ∣ ≤ R ( a ) := ( n i ≤ k ∑ ∥ a i ∥ 2 ) 1/2 for all b ⃗ ∈ K a ⃗ , n \vec{b}\in K_{\vec{a},n} b ∈ K a , n .
Our first main goal is to show that the function b ⃗ ↦ d ( b ⃗ , K a ⃗ , n ) : E n , k → R \vec{b}\mapsto d(\vec{b},K_{\vec{a},n}):E_{n,k}\to\mathbb{R} b ↦ d ( b , K a , n ) : E n , k → R is a computable function, uniformly in n , k , a ⃗ n,k,\vec{a} n , k , a . We will achieve this by showing that the support function for K a ⃗ , n K_{\vec{a},n} K a , n is a computable function. (Recall that, for a nonempty, closed, convex set A ⊆ R m A\subseteq\mathbb{R}^m A ⊆ R m , the support function of A A A is the function h A : K → R h_A:K\to\mathbb{R} h A : K → R given by h A ( x ) : = sup { ⟨ x , a ⟩ : a ∈ A } . ) h_A(x):=\sup\{\langle x,a\rangle:a\in A\}.) h A ( x ) := sup {⟨ x , a ⟩ : a ∈ A } . ) We first need some preparation.
Choi's correspondence with a trace constraint
Set tr n : = 1 n Tr \operatorname{tr}_n:=\frac{1}{n}\operatorname{Tr} tr n := n 1 Tr , the normalised trace on M n ( C ) M_n(\mathbb{C}) M n ( C ) . Put
S n ( A ) : = { ω ∈ S ( M n ( A ) ) : ω ↾ ( M n ( C ) ⊗ 1 ) = tr n } . S_n(A):=\{\omega\in S(M_n(A)):\omega\upharpoonright(M_n(\mathbb{C})\otimes1)=\operatorname{tr}_n\}. S n ( A ) := { ω ∈ S ( M n ( A )) : ω ↾ ( M n ( C ) ⊗ 1 ) = tr n } .
Lemma 2.2. The assignments
ω Φ ( ( a p q ) ) : = 1 n ∑ p , q = 1 n ⟨ Φ ( a p q ) ε q , ε p ⟩ , Φ ω ( a ) : = n ∑ p , q = 1 n ω ( e p q ⊗ a ) e p q \omega_\Phi((a_{pq})):=\frac{1}{n}\sum_{p,q=1}^{n}\langle\Phi(a_{pq})\varepsilon_q,\varepsilon_p\rangle,\qquad
\Phi_\omega(a):=n\sum_{p,q=1}^{n}\omega(e_{pq}\otimes a)e_{pq} ω Φ (( a pq )) := n 1 p , q = 1 ∑ n ⟨ Φ ( a pq ) ε q , ε p ⟩ , Φ ω ( a ) := n p , q = 1 ∑ n ω ( e pq ⊗ a ) e pq are mutually inverse affine bijections between UCP ( A , M n ( C ) ) \operatorname{UCP}(A,M_n(\mathbb{C})) UCP ( A , M n ( C )) and S n ( A ) S_n(A) S n ( A ) . (Here ( ε p ) (\varepsilon_p) ( ε p ) is the standard basis of C n . ) \mathbb{C}^n.) C n . )
Proof. This is the usual Choi correspondence (see, for example, [3 Proposition 1.5.12] ) together with a bookkeeping of the unitality constraint; we record the computation because we use the exact normalisations.
Let Φ \Phi Φ be cp and let ξ : = ∑ p ε p ⊗ ε p ∈ C n ⊗ C n \xi:=\sum_p\varepsilon_p\otimes\varepsilon_p\in\mathbb{C}^n\otimes\mathbb{C}^n ξ := ∑ p ε p ⊗ ε p ∈ C n ⊗ C n , so ∥ ξ ∥ 2 = n \lVert\xi\rVert^2=n ∥ ξ ∥ 2 = n . Regarding the n n n -th amplification Φ n : M n ( A ) → M n ( M n ( C ) ) = B ( C n ⊗ C n ) \Phi_n:M_n(A)\to M_n(M_n(\mathbb{C}))=B(\mathbb{C}^n\otimes\mathbb{C}^n) Φ n : M n ( A ) → M n ( M n ( C )) = B ( C n ⊗ C n ) (the first tensor factor indexing the block), we have
⟨ Φ n ( ( a p q ) ) ξ , ξ ⟩ = ∑ p , q ⟨ Φ ( a p q ) ε q , ε p ⟩ = n ω Φ ( ( a p q ) ) , \langle\Phi_n((a_{pq}))\xi,\xi\rangle=\sum_{p,q}\langle\Phi(a_{pq})\varepsilon_q,\varepsilon_p\rangle=n\omega_\Phi((a_{pq})), ⟨ Φ n (( a pq )) ξ , ξ ⟩ = p , q ∑ ⟨ Φ ( a pq ) ε q , ε p ⟩ = n ω Φ (( a pq )) ,
so ω Φ = 1 n ⟨ Φ n ( ⋅ ) ξ , ξ ⟩ \omega_\Phi=\frac{1}{n}\langle\Phi_n(\cdot)\xi,\xi\rangle ω Φ = n 1 ⟨ Φ n ( ⋅ ) ξ , ξ ⟩ is positive; conversely positivity of ω Φ \omega_\Phi ω Φ forces complete positivity of Φ \Phi Φ by the usual argument (apply positivity to x ∗ ( a ⊗ e 11 ) x x^*(a\otimes e_{11})x x ∗ ( a ⊗ e 11 ) x -type elements). Taking ( a p q ) = e p q ⊗ a (a_{pq})=e_{pq}\otimes a ( a pq ) = e pq ⊗ a gives ω Φ ( e p q ⊗ a ) = 1 n ⟨ Φ ( a ) ε q , ε p ⟩ \omega_\Phi(e_{pq}\otimes a)=\frac{1}{n}\langle\Phi(a)\varepsilon_q,\varepsilon_p\rangle ω Φ ( e pq ⊗ a ) = n 1 ⟨ Φ ( a ) ε q , ε p ⟩ , which is exactly the statement that Φ ω Φ = Φ \Phi_{\omega_\Phi}=\Phi Φ ω Φ = Φ ; symmetrically ω Φ ω = ω \omega_{\Phi_\omega}=\omega ω Φ ω = ω .
For the constraint: if Φ ( 1 ) = 1 n \Phi(1)=1_n Φ ( 1 ) = 1 n , then ω Φ ( m ⊗ 1 ) = 1 n ∑ p , q m p q δ p q = tr n ( m ) \omega_\Phi(m\otimes1)=\frac{1}{n}\sum_{p,q}m_{pq}\delta_{pq}=\operatorname{tr}_n(m) ω Φ ( m ⊗ 1 ) = n 1 ∑ p , q m pq δ pq = tr n ( m ) . Conversely, if ω ↾ ( M n ( C ) ⊗ 1 ) = tr n \omega\upharpoonright(M_n(\mathbb{C})\otimes1)=\operatorname{tr}_n ω ↾ ( M n ( C ) ⊗ 1 ) = tr n , then Φ ω ( 1 ) = n ∑ p , q tr n ( e p q ) e p q = ∑ p e p p = 1 n \Phi_\omega(1)=n\sum_{p,q}\operatorname{tr}_n(e_{pq})e_{pq}=\sum_p e_{pp}=1_n Φ ω ( 1 ) = n ∑ p , q tr n ( e pq ) e pq = ∑ p e pp = 1 n . Finally, any positive ω \omega ω with ω ↾ ( M n ( C ) ⊗ 1 ) = tr n \omega\upharpoonright(M_n(\mathbb{C})\otimes1)=\operatorname{tr}_n ω ↾ ( M n ( C ) ⊗ 1 ) = tr n has ω ( 1 B ) = tr n ( 1 n ) = 1 \omega(1_B)=\operatorname{tr}_n(1_n)=1 ω ( 1 B ) = tr n ( 1 n ) = 1 and so is a state. □ \square □
For c ⃗ ∈ E k , n \vec{c} \in E_{k,n} c ∈ E k , n and a ⃗ \vec{a} a in A A A put
y a ⃗ , c ⃗ : = 1 2 ( z + z ∗ ) ∈ M n ( A ) s a , z : = ∑ i = 1 k c ˉ i ⊗ a i , y_{\vec{a},\vec{c}} := \frac{1}{2}(z+z^*) \in M_n(A)_{\mathrm{sa}}, \qquad z := \sum_{i=1}^{k} \bar{c}_i \otimes a_i, y a , c := 2 1 ( z + z ∗ ) ∈ M n ( A ) sa , z := i = 1 ∑ k c ˉ i ⊗ a i ,
where c ˉ \bar{c} c ˉ denotes the entrywise complex conjugate of c c c and c ⊗ a : = ( c p q a ) p q c \otimes a := (c_{pq}a)_{pq} c ⊗ a := ( c pq a ) pq .
Lemma 2.3. For every Φ ∈ UCP ( A , M n ( C ) ) \Phi\in\operatorname{UCP}(A,M_n(\mathbb{C})) Φ ∈ UCP ( A , M n ( C )) with associated state ω = ω Φ \omega=\omega_\Phi ω = ω Φ and every c ⃗ ∈ E k , n \vec{c} \in E_{k,n} c ∈ E k , n , we have
⟨ ( Φ ( a 1 ) , … , Φ ( a k ) ) , c ⃗ ⟩ = n ω ( y a ⃗ , c ⃗ ) . \left\langle(\Phi(a_1),\ldots,\Phi(a_k)),\vec{c}\right\rangle=n\omega(y_{\vec{a},\vec{c}}). ⟨ ( Φ ( a 1 ) , … , Φ ( a k )) , c ⟩ = nω ( y a , c ) . Consequently, letting h a ⃗ , n : = h K a ⃗ , n h_{\vec{a},n}:=h_{K_{\vec{a},n}} h a , n := h K a , n denote the support function of K a ⃗ , n K_{\vec{a},n} K a , n , we have
h a ⃗ , n ( c ⃗ ) = n ⋅ sup { ω ( y a ⃗ , c ⃗ ) : ω ∈ S n ( A ) } . (1) h_{\vec{a},n}(\vec{c})=n\cdot\sup\{\omega(y_{\vec{a},\vec{c}}):\omega\in S_n(A)\}. \tag*{(1)} h a , n ( c ) = n ⋅ sup { ω ( y a , c ) : ω ∈ S n ( A )} . (1) Moreover y a ⃗ , c ⃗ y_{\vec{a},\vec{c}} y a , c is a generated point of M n ( A ) # M_n(A)^\# M n ( A ) # whenever a ⃗ \vec{a} a consists of generated points of A # A^\# A # and c ⃗ \vec{c} c is rational, and a code for it is computable from codes for a ⃗ , c ⃗ \vec{a},\vec{c} a , c .
Proof. Writing Φ ( a ) q p = ⟨ Φ ( a ) ε p , ε q ⟩ = n ω ( e q p ⊗ a ) \Phi(a)_{qp}=\langle\Phi(a)\varepsilon_p,\varepsilon_q\rangle=n\omega(e_{qp}\otimes a) Φ ( a ) q p = ⟨ Φ ( a ) ε p , ε q ⟩ = nω ( e q p ⊗ a ) by Lemma 2.2 , we have
Tr ( c ˉ i ∗ Φ ( a i ) ) = ∑ p , q ( c i ) q p ‾ Φ ( a i ) q p = n ω ( ∑ p , q ( c i ) q p ‾ e q p ⊗ a i ) = n ω ( c ˉ i ⊗ a i ) . \operatorname{Tr}(\bar{c}_i^*\Phi(a_i))=\sum_{p,q}\overline{(c_i)_{qp}}\Phi(a_i)_{qp}=n\omega\left(\sum_{p,q}\overline{(c_i)_{qp}}e_{qp}\otimes a_i\right)=n\omega(\bar{c}_i\otimes a_i). Tr ( c ˉ i ∗ Φ ( a i )) = p , q ∑ ( c i ) q p Φ ( a i ) q p = nω ( p , q ∑ ( c i ) q p e q p ⊗ a i ) = nω ( c ˉ i ⊗ a i ) .
Summing over i i i gives ∑ i Tr ( c ˉ i ∗ Φ ( a i ) ) = n ω ( z ) \sum_i\operatorname{Tr}(\bar{c}_i^*\Phi(a_i))=n\omega(z) ∑ i Tr ( c ˉ i ∗ Φ ( a i )) = nω ( z ) ; since ω \omega ω is self-adjoint, Re ω ( z ) = ω ( 1 2 ( z + z ∗ ) ) \operatorname{Re}\omega(z)=\omega\left(\frac{1}{2}(z+z^*)\right) Re ω ( z ) = ω ( 2 1 ( z + z ∗ ) ) . The last assertion is immediate from the description of the generated points of M n ( A ) # M_n(A)^\# M n ( A ) # .
The duality identity
The point of (1) is that the constrained supremum on the right has an exactly dual description as an infimum over a finite-dimensional space, and that both the objective and the constraint region of that infimum are computable:
Lemma 2.4. Let B B B be a unital C ∗ C^* C ∗ -algebra containing M n ( C ) M_n(\mathbb{C}) M n ( C ) unitally. For z ∈ B s a z\in B_{\mathrm{sa}} z ∈ B sa , set λ max ( z ) : = max sp ( z ) = inf { t ∈ R : z ≤ t 1 } \lambda_{\max}(z):=\max\operatorname{sp}(z)=\inf\{t\in\mathbb{R}:z\le t1\} λ m a x ( z ) := max sp ( z ) = inf { t ∈ R : z ≤ t 1 } . Set S : = { ω ∈ S ( B ) : ω ↾ M n ( C ) = tr n } S:=\{\omega\in S(B):\omega\mathbin{\upharpoonright}M_n(\mathbb{C})=\operatorname{tr}_n\} S := { ω ∈ S ( B ) : ω ↾ M n ( C ) = tr n } . Then for every y ∈ B s a y\in B_{\mathrm{sa}} y ∈ B sa , we have
max ω ∈ S ω ( y ) = inf m ∈ ( M n ( C ) ) s a [ λ max ( y + m ) − tr n ( m ) ] . (2) \max_{\omega\in S}\omega(y)=\inf_{m\in(M_n(\mathbb{C}))_{\mathrm{sa}}}\left[\lambda_{\max}(y+m)-\operatorname{tr}_n(m)\right]. \tag*{(2)} ω ∈ S max ω ( y ) = m ∈ ( M n ( C ) ) sa inf [ λ m a x ( y + m ) − tr n ( m ) ] . (2) Moreover, the infimum on the right hand side of the above equation is in fact attained.
First, we will need the following:
Lemma 2.5. In the situation of Lemma 2.4 , put g ( m ) : = λ max ( y + m ) − tr n ( m ) g(m):=\lambda_{\max}(y+m)-\operatorname{tr}_n(m) g ( m ) := λ m a x ( y + m ) − tr n ( m ) for m ∈ ( M n ( C ) ) s a m\in(M_n(\mathbb{C}))_{\mathrm{sa}} m ∈ ( M n ( C ) ) sa . Then:
g ( m + t 1 n ) = g ( m ) g(m+t1_n)=g(m) g ( m + t 1 n ) = g ( m ) for all t ∈ R t\in\mathbb{R} t ∈ R . In particular, the infimum in (2) may be taken over the trace 0 0 0 self-adjoint matrices.
∣ g ( m ) − g ( m ′ ) ∣ ≤ 2 ∥ m − m ′ ∥ |g(m)-g(m')|\le2\lVert m-m'\rVert ∣ g ( m ) − g ( m ′ ) ∣ ≤ 2 ∥ m − m ′ ∥ for all m , m ′ ∈ ( M n ( C ) ) s a m,m'\in(M_n(\mathbb{C}))_{\mathrm{sa}} m , m ′ ∈ ( M n ( C ) ) sa .
If m ∈ ( M n ( C ) ) s a m\in(M_n(\mathbb{C}))_{\mathrm{sa}} m ∈ ( M n ( C ) ) sa has trace 0 0 0 , then λ max ( m ) ≥ ∥ m ∥ / n \lambda_{\max}(m)\ge\lVert m\rVert/n λ m a x ( m ) ≥ ∥ m ∥ / n , and thus
g ( m ) ≥ ∥ m ∥ / n − ∥ y ∥ . g(m)\ge\lVert m\rVert/n-\lVert y\rVert. g ( m ) ≥ ∥ m ∥ / n − ∥ y ∥ . Consequently, the right hand side of (2) equals
min { λ max ( y + m ) : m ∈ ( M n ( C ) ) s a , Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥ } . \min\{\lambda_{\max}(y+m):m\in(M_n(\mathbb{C}))_{\mathrm{sa}},\ \operatorname{Tr}(m)=0,\ \lVert m\rVert\le2n\lVert y\rVert\}. min { λ m a x ( y + m ) : m ∈ ( M n ( C ) ) sa , Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥} .
Proof. (1) follows from the equations λ max ( y + m + t 1 ) = λ max ( y + m ) + t \lambda_{\max}(y+m+t1)=\lambda_{\max}(y+m)+t λ m a x ( y + m + t 1 ) = λ m a x ( y + m ) + t and tr n ( m + t 1 n ) = tr n ( m ) + t \operatorname{tr}_{n}(m+t1_{n})=\operatorname{tr}_{n}(m)+t tr n ( m + t 1 n ) = tr n ( m ) + t .
(2) From z ≤ z ′ + ∥ z − z ′ ∥ 1 z\le z^{\prime}+\lVert z-z^{\prime}\rVert1 z ≤ z ′ + ∥ z − z ′ ∥ 1 we get λ max ( z ) ≤ λ max ( z ′ ) + ∥ z − z ′ ∥ \lambda_{\max}(z)\le\lambda_{\max}(z^{\prime})+\lVert z-z^{\prime}\rVert λ m a x ( z ) ≤ λ m a x ( z ′ ) + ∥ z − z ′ ∥ and hence ∣ λ max ( z ) − λ max ( z ′ ) ∣ ≤ ∥ z − z ′ ∥ \lvert\lambda_{\max}(z)-\lambda_{\max}(z^{\prime})\rvert\le\lVert z-z^{\prime}\rVert ∣ λ m a x ( z ) − λ m a x ( z ′ )∣ ≤ ∥ z − z ′ ∥ ; also ∣ tr n ( m ) − tr n ( m ′ ) ∣ ≤ ∥ m − m ′ ∥ \lvert\operatorname{tr}_{n}(m)-\operatorname{tr}_{n}(m^{\prime})\rvert\le\lVert m-m^{\prime}\rVert ∣ tr n ( m ) − tr n ( m ′ )∣ ≤ ∥ m − m ′ ∥ .
(3) Let μ 1 ≥ ⋯ ≥ μ n \mu_{1}\ge\cdots\ge\mu_{n} μ 1 ≥ ⋯ ≥ μ n be the eigenvalues of m m m , so ∑ p μ p = 0 \sum_{p}\mu_{p}=0 ∑ p μ p = 0 and ∥ m ∥ = max ( μ 1 , − μ n ) \lVert m\rVert=\max(\mu_{1},-\mu_{n}) ∥ m ∥ = max ( μ 1 , − μ n ) . If ∥ m ∥ = μ 1 \lVert m\rVert=\mu_{1} ∥ m ∥ = μ 1 we are done. Otherwise ∥ m ∥ = − μ n \lVert m\rVert=-\mu_{n} ∥ m ∥ = − μ n and n ≥ 2 n\ge2 n ≥ 2 (a traceless self-adjoint 1 × 1 1\times1 1 × 1 matrix is 0 0 0 ), and ∑ p < n μ p = − μ n = ∥ m ∥ \sum_{p<n}\mu_{p}=-\mu_{n}=\lVert m\rVert ∑ p < n μ p = − μ n = ∥ m ∥ , so μ 1 ≥ ∥ m ∥ / ( n − 1 ) ≥ ∥ m ∥ / n \mu_{1}\ge\lVert m\rVert/(n-1)\ge\lVert m\rVert/n μ 1 ≥ ∥ m ∥ / ( n − 1 ) ≥ ∥ m ∥ / n . For the second inequality, use the inequality λ max ( y + m ) ≥ λ max ( m ) − ∥ y ∥ \lambda_{\max}(y+m)\ge\lambda_{\max}(m)-\lVert y\rVert λ m a x ( y + m ) ≥ λ m a x ( m ) − ∥ y ∥ , which follows from the more general inequality mentioned in the proof of item (2).
(4) By (1), we may take the infimum over m m m of trace 0. Next note that g ( 0 ) = λ max ( y ) ≤ ∥ y ∥ g(0)=\lambda_{\max}(y)\le\lVert y\rVert g ( 0 ) = λ m a x ( y ) ≤ ∥ y ∥ . If, on the other hand, m m m has trace 0 and ∥ m ∥ > 2 n ∥ y ∥ \lVert m\rVert>2n\lVert y\rVert ∥ m ∥ > 2 n ∥ y ∥ , we have g ( m ) > 2 ∥ y ∥ − ∥ y ∥ = ∥ y ∥ ≥ g ( 0 ) g(m)>2\lVert y\rVert-\lVert y\rVert=\lVert y\rVert\ge g(0) g ( m ) > 2 ∥ y ∥ − ∥ y ∥ = ∥ y ∥ ≥ g ( 0 ) by (3). So the infimum over m m m of trace 0 equals the infimum over the indicated (compact) ball, which is therefore attained.
Proof of Lemma 2.4. Write α \alpha α for the left-hand side; note that the supremum is attained since S S S is weak∗ ^{*} ∗ -compact and S ≠ ∅ S\ne\varnothing S = ∅ since tr n \operatorname{tr}_{n} tr n extends to a state of B B B by Hahn–Banach, positivity being automatic for a norm-one extension of a state on a unital subalgebra. Let β \beta β denote the right-hand side infimum, which we know equals the minimum appearing in item (4) of the previous lemma.
We first show that α ≤ β \alpha\le\beta α ≤ β . For ω ∈ S \omega\in S ω ∈ S and m ∈ ( M n ( C ) ) s a m\in(M_{n}(\mathbb{C}))_{\mathrm{sa}} m ∈ ( M n ( C ) ) sa , we have
ω ( y ) = ω ( y + m ) − ω ( m ) = ω ( y + m ) − tr n ( m ) ≤ λ max ( y + m ) − tr n ( m ) , \omega(y)=\omega(y+m)-\omega(m)=\omega(y+m)-\operatorname{tr}_{n}(m)\le\lambda_{\max}(y+m)-\operatorname{tr}_{n}(m), ω ( y ) = ω ( y + m ) − ω ( m ) = ω ( y + m ) − tr n ( m ) ≤ λ m a x ( y + m ) − tr n ( m ) ,
using that ω \omega ω is a state and y + m y+m y + m is self-adjoint.
We now show that β ≤ α \beta\le\alpha β ≤ α . Suppose, towards a contradiction, that this is not the case and fix γ ∈ R \gamma\in\mathbb{R} γ ∈ R with α < γ < β \alpha<\gamma<\beta α < γ < β . Set V : = ( M n ( C ) ) s a ⊆ B s a V:=(M_{n}(\mathbb{C}))_{\mathrm{sa}}\subseteq B_{\mathrm{sa}} V := ( M n ( C ) ) sa ⊆ B sa (again identified with its image).
We first dispose of a degenerate case: if y ∈ V y\in V y ∈ V , say y = m 0 y=m_{0} y = m 0 , then every ω ∈ S \omega\in S ω ∈ S has ω ( y ) = tr n ( m 0 ) \omega(y)=\operatorname{tr}_{n}(m_{0}) ω ( y ) = tr n ( m 0 ) , so α = tr n ( m 0 ) \alpha=\operatorname{tr}_{n}(m_{0}) α = tr n ( m 0 ) ; taking m = − m 0 m=-m_{0} m = − m 0 in the right-hand side of (2) gives β ≤ λ max ( 0 ) + tr n ( m 0 ) = α \beta\le\lambda_{\max}(0)+\operatorname{tr}_{n}(m_{0})=\alpha β ≤ λ m a x ( 0 ) + tr n ( m 0 ) = α , contradicting α < β \alpha<\beta α < β . So y ∉ V y\notin V y ∈ / V and W : = R y ⊕ V W:=\mathbb{R}y\oplus V W := R y ⊕ V is a direct sum. Define a real-linear functional φ \varphi φ on W W W by
φ ( s y + m ) : = s γ + tr n ( m ) ( s ∈ R , m ∈ ( M n ( C ) ) s a ) . \varphi(sy+m):=s\gamma+\operatorname{tr}_{n}(m)\qquad(s\in\mathbb{R},\ m\in(M_{n}(\mathbb{C}))_{\mathrm{sa}}). φ ( sy + m ) := s γ + tr n ( m ) ( s ∈ R , m ∈ ( M n ( C ) ) sa ) .
Claim: φ ≤ λ max \varphi\le\lambda_{\max} φ ≤ λ m a x on W W W .
To prove the claim, we consider three cases:
s = 0 s=0 s = 0 : tr n \operatorname{tr}_{n} tr n is a state of M n ( C ) M_{n}(\mathbb{C}) M n ( C ) and λ max ( m ) \lambda_{\max}(m) λ m a x ( m ) is computed in M n ( C ) M_{n}(\mathbb{C}) M n ( C ) as well (a unital inclusion of C∗ ^{*} ∗ -algebras preserves spectra), so tr n ( m ) ≤ λ max ( m ) \operatorname{tr}_{n}(m)\le\lambda_{\max}(m) tr n ( m ) ≤ λ m a x ( m ) .
s > 0 s>0 s > 0 : dividing by s s s and writing m ′ = m / s m^{\prime}=m/s m ′ = m / s , the claim reads γ ≤ λ max ( y + m ′ ) − tr n ( m ′ ) \gamma\le\lambda_{\max}(y+m^{\prime})-\operatorname{tr}_{n}(m^{\prime}) γ ≤ λ m a x ( y + m ′ ) − tr n ( m ′ ) , which holds for every m ′ m^{\prime} m ′ because γ < β \gamma<\beta γ < β .
s < 0 s<0 s < 0 : dividing by ∣ s ∣ \lvert s\rvert ∣ s ∣ and writing m ′ = m / ∣ s ∣ m^{\prime}=m/\lvert s\rvert m ′ = m / ∣ s ∣ , the claim reads − γ + tr n ( m ′ ) ≤ λ max ( − y + m ′ ) -\gamma+\operatorname{tr}_{n}(m^{\prime})\le\lambda_{\max}(-y+m^{\prime}) − γ + tr n ( m ′ ) ≤ λ m a x ( − y + m ′ ) . Pick ω ∈ S \omega\in S ω ∈ S with ω ( y ) = α \omega(y)=\alpha ω ( y ) = α ; then λ max ( − y + m ′ ) ≥ ω ( − y + m ′ ) = − α + tr n ( m ′ ) > − γ + tr n ( m ′ ) \lambda_{\max}(-y+m^{\prime})\ge\omega(-y+m^{\prime})=-\alpha+\operatorname{tr}_{n}(m^{\prime})>-\gamma+\operatorname{tr}_{n}(m^{\prime}) λ m a x ( − y + m ′ ) ≥ ω ( − y + m ′ ) = − α + tr n ( m ′ ) > − γ + tr n ( m ′ ) since α < γ \alpha<\gamma α < γ .
Now λ max : B s a → R \lambda_{\max}:B_{\mathrm{sa}}\to\mathbb{R} λ m a x : B sa → R is sublinear, so by the Hahn–Banach theorem there is a real-linear φ ~ : B s a → R \widetilde{\varphi}:B_{\mathrm{sa}}\to\mathbb{R} φ : B sa → R extending φ \varphi φ with φ ~ ≤ λ max \widetilde{\varphi}\le\lambda_{\max} φ ≤ λ m a x . Then φ ~ \widetilde{\varphi} φ is positive: if z ≥ 0 z\ge0 z ≥ 0 then λ max ( − z ) ≤ 0 \lambda_{\max}(-z)\le0 λ m a x ( − z ) ≤ 0 , so − φ ~ ( z ) = φ ~ ( − z ) ≤ 0 -\widetilde{\varphi}(z)=\widetilde{\varphi}(-z)\le0 − φ ( z ) = φ ( − z ) ≤ 0 . Also φ ~ ( 1 ) = φ ( 1 n ) = tr n ( 1 n ) = 1 \widetilde{\varphi}(1)=\varphi(1_{n})=\operatorname{tr}_{n}(1_{n})=1 φ ( 1 ) = φ ( 1 n ) = tr n ( 1 n ) = 1 . Complexifying, ω 0 ( z ) : = φ ~ ( Re z ) + i φ ~ ( Im z ) \omega_{0}(z):=\widetilde{\varphi}(\operatorname{Re}z)+i\widetilde{\varphi}(\operatorname{Im}z) ω 0 ( z ) := φ ( Re z ) + i φ ( Im z ) is a state of B B B ; it satisfies ω 0 ∣ M n ( C ) = tr n \omega_{0}|_{M_{n}(\mathbb{C})}=\operatorname{tr}_{n} ω 0 ∣ M n ( C ) = tr n (true for self-adjoints by construction, hence everywhere by linearity), so ω 0 ∈ S \omega_{0}\in S ω 0 ∈ S , and ω 0 ( y ) = φ ( y ) = γ > α \omega_{0}(y)=\varphi(y)=\gamma>\alpha ω 0 ( y ) = φ ( y ) = γ > α , contradicting the definition of α \alpha α .
Finally, the infimum β \beta β is attained by Lemma 2.5 . □
Computability of the support function
Using the lemma from the previous subsection, we can now prove:
Proposition 2.6. Let A # A^\# A # be a computable presentation of a C ∗ \mathrm{C}^* C ∗ -algebra A A A , let a ⃗ = ( a 1 , … , a k ) \vec{a}=(a_1,\ldots,a_k) a = ( a 1 , … , a k ) be a k k k -tuple of generated points of A A A , and let n ≥ 1 n\ge1 n ≥ 1 . Then the support function h a ⃗ , n h_{\vec{a},n} h a , n of K a ⃗ , n K_{\vec{a},n} K a , n is computable. Moreover, an index for h a ⃗ , n h_{\vec{a},n} h a , n can be computed from a unital index for A # A^\# A # , indices for a 1 , … , a k a_1,\ldots,a_k a 1 , … , a k , and n n n .
Proof. By Lemmas 2.3 , 2.4 and Lemma 2.5 (4) applied to B = M n ( A ) B=M_n(A) B = M n ( A ) , y : = y a ⃗ , c ⃗ y:=y_{\vec{a},\vec{c}} y := y a , c , we have h a ⃗ , n ( c ⃗ ) = n β h_{\vec{a},n}(\vec{c})=n\beta h a , n ( c ) = n β , where
β = min { λ max ( y + m ⊗ 1 ) : m ∈ ( M n ( C ) ) s a , Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥ } . \beta=\min\{\lambda_{\max}(y+m\otimes1):m\in(M_n(\mathbb{C}))_{\mathrm{sa}},\ \operatorname{Tr}(m)=0,\ \lVert m\rVert\le2n\lVert y\rVert\}. β = min { λ m a x ( y + m ⊗ 1 ) : m ∈ ( M n ( C ) ) sa , Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥} .
We check that each ingredient is computable.
First, since M n ( A ) # M_n(A)^\# M n ( A ) # is a computable presentation uniformly in n n n (see [8 Prop. 1.7] ), a code for the generated point y y y of M n ( A ) # M_n(A)^\# M n ( A ) # is computable from a ⃗ , c ⃗ \vec{a},\vec{c} a , c , and, moreover, ∥ y ∥ \lVert y\rVert ∥ y ∥ is computable. Fix a rational N > ∥ y ∥ + 2 n ∥ y ∥ + 1 N>\lVert y\rVert+2n\lVert y\rVert+1 N > ∥ y ∥ + 2 n ∥ y ∥ + 1 .
Next, for m m m a rational self-adjoint matrix, y + m ⊗ 1 y+m\otimes1 y + m ⊗ 1 is a computable point of M n ( A ) # M_n(A)^\# M n ( A ) # with a modulus computable from m m m , and ∥ y + m ⊗ 1 ∥ < N \lVert y+m\otimes1\rVert<N ∥ y + m ⊗ 1 ∥ < N . Since y + m ⊗ 1 + N 1 ≥ 0 y+m\otimes1+N1\ge0 y + m ⊗ 1 + N 1 ≥ 0 , we have
λ max ( y + m ⊗ 1 ) = ∥ y + m ⊗ 1 + N ⋅ 1 ∥ − N . \lambda_{\max}(y+m\otimes1)=\lVert y+m\otimes1+N\cdot1\rVert-N. λ m a x ( y + m ⊗ 1 ) = ∥ y + m ⊗ 1 + N ⋅ 1 ∥ − N .
and the right-hand side is computable uniformly in m m m .
Finally, the set C : = { m ∈ ( M n ( C ) ) s a : Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥ } C:=\{m\in(M_n(\mathbb{C}))_{\mathrm{sa}}:\operatorname{Tr}(m)=0,\ \lVert m\rVert\le2n\lVert y\rVert\} C := { m ∈ ( M n ( C ) ) sa : Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥} is a compact subset of a ( n 2 − 1 ) (n^2-1) ( n 2 − 1 ) -dimensional real vector space with a computable rational basis, and from a rational upper bound for ∥ y ∥ \lVert y\rVert ∥ y ∥ we can compute a finite rational δ \delta δ -net of C C C (of size computable in δ \delta δ ) lying in the slightly larger set
C ′ : = { m : Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥ + 1 } . C':=\{m:\operatorname{Tr}(m)=0,\ \lVert m\rVert\le2n\lVert y\rVert+1\}. C ′ := { m : Tr ( m ) = 0 , ∥ m ∥ ≤ 2 n ∥ y ∥ + 1 } .
note that, by Lemma 2.5 (4), the minimum of λ max ( y + ⋅ ) \lambda_{\max}(y+\cdot) λ m a x ( y + ⋅ ) over C ′ C' C ′ still equals β \beta β . By Lemma 2.5 (2) the function λ max ( y + ⋅ ) \lambda_{\max}(y+\cdot) λ m a x ( y + ⋅ ) is 2-Lipschitz in m m m , so evaluating it to precision ε / ( 4 n ) \varepsilon/(4n) ε / ( 4 n ) on an ( ε / ( 8 n ) ) (\varepsilon/(8n)) ( ε / ( 8 n )) -net of C ′ C' C ′ and taking the minimum returns a rational within ε / n \varepsilon/n ε / n of β \beta β , hence within ε \varepsilon ε of n β n\beta n β . □
Corollary 2.7. Uniformly in the data of Proposition 2.6 , we have:
The distance function b ⃗ ↦ d ( b ⃗ , K a ⃗ , n ) : E k , n → R \vec{b}\mapsto d(\vec{b},K_{\vec{a},n}):E_{k,n}\to\mathbb{R} b ↦ d ( b , K a , n ) : E k , n → R is computable.
K a ⃗ , n K_{\vec{a},n} K a , n is a computably compact subset of E k , n E_{k,n} E k , n .
Proof. (1) It is a well-known fact that, for a nonempty compact convex K ⊆ E K\subseteq E K ⊆ E with support function h h h , one has
d ( x , K ) = max ∣ c ∣ ≤ 1 ⟨ x , c ⟩ − h ( c ) . (3) d(x,K)=\max_{\lvert c\rvert\le1}\langle x,c\rangle-h(c). \tag*{(3)} d ( x , K ) = ∣ c ∣ ≤ 1 max ⟨ x , c ⟩ − h ( c ) . (3)
By Proposition 2.6 , the function being maximized is computable. Consequently, its maximum over the (computably compact) unit ball is computable.
(2) follows from general computable analysis: in M n ( C ) M_n(\mathbb{C}) M n ( C ) , closed rational balls are computably compact; in such a space, a compact set satisfying (1) is automatically computably compact [5 Proposition 3.29] . □
The effective Arveson extension theorem
We can now prove the main result of this section:
Theorem 2.8 (Effective ε \varepsilon ε -Arveson). There is an algorithm that, given
a unital index for a computable presentation A # A^{\#} A # of a unital C ∗ C^* C ∗ -algebra A A A ,
n , k ≥ 1 n,k \ge1 n , k ≥ 1 and codes for generated points a ⃗ = ( a 1 , … , a k ) \vec{a}=(a_1,\ldots,a_k) a = ( a 1 , … , a k ) of A # A^{\#} A # , and
a code for a rational b ⃗ ∈ E k , n \vec{b}\in E_{k,n} b ∈ E k , n and a rational δ > 0 \delta>0 δ > 0 such that d ( b ⃗ , K a ⃗ , n ) < δ d(\vec{b},K_{\vec{a},n})<\delta d ( b , K a , n ) < δ ,
outputs an index for a computable ucp map Φ : A → M n ( C ) \Phi:A\to M_n(\mathbb{C}) Φ : A → M n ( C ) with
max 1 ≤ i ≤ k ∥ Φ ( a i ) − b i ∥ < δ . \max_{1\le i\le k}\|\Phi(a_i)-b_i\|<\delta. 1 ≤ i ≤ k max ∥Φ ( a i ) − b i ∥ < δ .
Proof. Fix an effective enumeration x 1 , x 2 , x 3 , … x_1,x_2,x_3,\ldots x 1 , x 2 , x 3 , … of the generated points of A # A^{\#} A # with x i = a i x_i=a_i x i = a i for i ≤ k i\le k i ≤ k . For l ≥ k l\ge k l ≥ k set:
x ⃗ ( l ) : = ( x 1 , … , x l ) \vec{x}^{(l)}:=(x_1,\ldots,x_l) x ( l ) := ( x 1 , … , x l ) ;
K l : = K x ⃗ ( l ) , n ⊆ E l , n K_l:=K_{\vec{x}^{(l)},n}\subseteq E_{l,n} K l := K x ( l ) , n ⊆ E l , n , and
π l : E l + 1 , n → E l , n \pi_l:E_{l+1,n}\to E_{l,n} π l : E l + 1 , n → E l , n for the projection onto the first l l l coordinates.
Since K l K_l K l and K l + 1 K_{l+1} K l + 1 are the images of the same set UCP ( A , M n ( C ) ) \operatorname{UCP}(A,M_n(\mathbb{C})) UCP ( A , M n ( C )) under evaluation at x ⃗ ( l ) \vec{x}^{(l)} x ( l ) and x ⃗ ( l + 1 ) \vec{x}^{(l+1)} x ( l + 1 ) respectively, we have
π l ( K l + 1 ) = K l . (4) \pi_l(K_{l+1})=K_l. \tag*{(4)} π l ( K l + 1 ) = K l . (4)
Using Corollary 2.7 , compute a rational δ 0 \delta_0 δ 0 with d ( b ⃗ , K k ) < δ 0 < δ d(\vec{b},K_k)<\delta_0<\delta d ( b , K k ) < δ 0 < δ , and fix a rational θ > 0 \theta>0 θ > 0 with δ 0 + 4 θ < δ \delta_0+4\theta<\delta δ 0 + 4 θ < δ . Set
η k : = δ 0 , η l : = θ 2 − ( l − k ) ( l > k ) . \eta_k:=\delta_0,\qquad\eta_l:=\theta2^{-(l-k)}\quad(l>k). η k := δ 0 , η l := θ 2 − ( l − k ) ( l > k ) .
We construct rational v ( l ) ∈ E l , n v^{(l)}\in E_{l,n} v ( l ) ∈ E l , n for l ≥ k l\ge k l ≥ k with
d ( v ( l ) , K l ) < η l and ∣ π l ( v ( l + 1 ) ) − v ( l ) ∣ < η l + η l + 1 . (5) d(v^{(l)},K_l)<\eta_l
\qquad\text{and}\qquad
\left|\pi_l(v^{(l+1)})-v^{(l)}\right|<\eta_l+\eta_{l+1}. \tag*{(5)} d ( v ( l ) , K l ) < η l and π l ( v ( l + 1 ) ) − v ( l ) < η l + η l + 1 . (5)
Start with v ( k ) : = b ⃗ v^{(k)}:=\vec{b} v ( k ) := b , which satisfies the first condition. Given v ( l ) v^{(l)} v ( l ) , by Corollary 2.7 (1) we may search for a rational v ( l + 1 ) v^{(l+1)} v ( l + 1 ) satisfying the above two conditions; the search terminates because such a point exists. Indeed, choose u ∈ K l u\in K_l u ∈ K l with ∣ u − v ( l ) ∣ < η l |u-v^{(l)}|<\eta_l ∣ u − v ( l ) ∣ < η l , lift it by (4) to u ′ ∈ K l + 1 u'\in K_{l+1} u ′ ∈ K l + 1 with π l ( u ′ ) = u \pi_l(u')=u π l ( u ′ ) = u , and take any rational v ( l + 1 ) v^{(l+1)} v ( l + 1 ) with ∣ v ( l + 1 ) − u ′ ∣ < η l + 1 |v^{(l+1)}-u'|<\eta_{l+1} ∣ v ( l + 1 ) − u ′ ∣ < η l + 1 ; then d ( v ( l + 1 ) , K l + 1 ) < η l + 1 d(v^{(l+1)},K_{l+1})<\eta_{l+1} d ( v ( l + 1 ) , K l + 1 ) < η l + 1 and
∣ π l ( v ( l + 1 ) ) − v ( l ) ∣ ≤ ∣ π l ( v ( l + 1 ) ) − u ∣ + ∣ u − v ( l ) ∣ < η l + 1 + η l . \left|\pi_l(v^{(l+1)})-v^{(l)}\right|
\le\left|\pi_l(v^{(l+1)})-u\right|+\left|u-v^{(l)}\right|
<\eta_{l+1}+\eta_l. π l ( v ( l + 1 ) ) − v ( l ) ≤ π l ( v ( l + 1 ) ) − u + u − v ( l ) < η l + 1 + η l .
By (5) , for each i i i the sequence ( v i ( l ) ) l ≥ max ( i , k ) (v_i^{(l)})_{l\ge\max(i,k)} ( v i ( l ) ) l ≥ m a x ( i , k ) satisfies ∣ v i ( l + 1 ) − v i ( l ) ∣ ≤ η l + η l + 1 |v_i^{(l+1)}-v_i^{(l)}|\le\eta_l+\eta_{l+1} ∣ v i ( l + 1 ) − v i ( l ) ∣ ≤ η l + η l + 1 , and ∑ l ≥ k ( η l + η l + 1 ) \sum_{l\ge k}(\eta_l+\eta_{l+1}) ∑ l ≥ k ( η l + η l + 1 ) converges with a computable rate. As a result,
Φ ( x i ) : = lim l → ∞ v i ( l ) \Phi(x_i):=\lim_{l\to\infty}v_i^{(l)} Φ ( x i ) := l → ∞ lim v i ( l )
exists and is a computable matrix, uniformly in i i i . Moreover for i ≤ k i\le k i ≤ k , we have
∣ Φ ( a i ) − b i ∣ ≤ ∑ l ≥ k ( η l + η l + 1 ) ≤ η k + 2 ∑ l > k η l = δ 0 + 4 θ < δ , |\Phi(a_i)-b_i|
\le\sum_{l\ge k}(\eta_l+\eta_{l+1})
\le\eta_k+2\sum_{l>k}\eta_l
=\delta_0+4\theta<\delta, ∣Φ ( a i ) − b i ∣ ≤ l ≥ k ∑ ( η l + η l + 1 ) ≤ η k + 2 l > k ∑ η l = δ 0 + 4 θ < δ ,
and ∥ ⋅ ∥ o p ≤ ∥ ⋅ ∥ H S \|\cdot\|_{\mathrm{op}}\le\|\cdot\|_{\mathrm{HS}} ∥ ⋅ ∥ op ≤ ∥ ⋅ ∥ HS gives the stated norm estimate.
We next note that Φ \Phi Φ is the restriction of a ucp map A → M n ( C ) A\to M_n(\mathbb{C}) A → M n ( C ) . To see this, fix l l l . For l ′ > l l'>l l ′ > l , (5) gives
∣ π l ( v ( l ′ ) ) − v ( l ) ∣ ≤ ∑ j = l l ′ − 1 ( η j + η j + 1 ) , \left|\pi_l(v^{(l')})-v^{(l)}\right|
\le\sum_{j=l}^{l'-1}(\eta_j+\eta_{j+1}), π l ( v ( l ′ ) ) − v ( l ) ≤ j = l ∑ l ′ − 1 ( η j + η j + 1 ) ,
so letting l ′ → ∞ l'\to\infty l ′ → ∞ , we have
d ( ( Φ ( x 1 ) , … , Φ ( x l ) ) , K l ) ≤ η l + ∑ j ≥ l ( η j + η j + 1 ) → l → ∞ 0. d\left((\Phi(x_1),\ldots,\Phi(x_l)),K_l\right)
\le\eta_l+\sum_{j\ge l}(\eta_j+\eta_{j+1})
\mathrel{\xrightarrow[l\to\infty]{} }0. d ( ( Φ ( x 1 ) , … , Φ ( x l )) , K l ) ≤ η l + j ≥ l ∑ ( η j + η j + 1 ) l → ∞ 0.
Since π l ( K l ′ ) = K l \pi_l(K_l') = K_l π l ( K l ′ ) = K l by (4) and projections are contractive, the left-hand side dominates d ( ( Φ ( x 1 ) , … , Φ ( x l ) ) , K l ) d((\Phi(x_1),\ldots,\Phi(x_l)),K_l) d (( Φ ( x 1 ) , … , Φ ( x l )) , K l ) , which is therefore 0 0 0 ; as K l K_l K l is closed, we have
( Φ ( x 1 ) , … , Φ ( x l ) ) ∈ K l for every l . (\Phi(x_1),\ldots,\Phi(x_l)) \in K_l \qquad\text{for every } l. ( Φ ( x 1 ) , … , Φ ( x l )) ∈ K l for every l .
Thus, for each l l l there is Φ l ∈ UCP ( A , M n ( C ) ) \Phi_l \in\operatorname{UCP}(A,M_n(\mathbb{C})) Φ l ∈ UCP ( A , M n ( C )) with Φ l ( x i ) = Φ ( x i ) \Phi_l(x_i)=\Phi(x_i) Φ l ( x i ) = Φ ( x i ) for i ≤ l i\leq l i ≤ l . By Fact 2.1, the net ( Φ l ) (\Phi_l) ( Φ l ) has a point-weak cluster point Φ ∞ ∈ UCP ( A , M n ( C ) ) \Phi_\infty\in\operatorname{UCP}(A,M_n(\mathbb{C})) Φ ∞ ∈ UCP ( A , M n ( C )) , and for each fixed i i i we have Φ l ( x i ) = Φ ( x i ) \Phi_l(x_i)=\Phi(x_i) Φ l ( x i ) = Φ ( x i ) for all l ≥ i l\geq i l ≥ i , so Φ ∞ ( x i ) = Φ ( x i ) \Phi_\infty(x_i)=\Phi(x_i) Φ ∞ ( x i ) = Φ ( x i ) . Thus Φ ∞ \Phi_\infty Φ ∞ is a ucp map agreeing with our computed values on all generated points. Being contractive, it is the unique continuous extension of those values, and the algorithm above witnesses that it is computable. □
The previous theorem has the following interesting consequence:
Corollary 2.9. Let A # A^{\#} A # be a computable presentation of a unital C∗ ^* ∗ -algebra. Then, uniformly in a unital index for A # A^{\#} A # , we have:
The joint numerical range of any tuple of generated points is a computably compact convex subset of C k \mathbb{C}^k C k .
Given generated points a ⃗ \vec{a} a , a rational b ⃗ ∈ C k \vec{b}\in\mathbb{C}^k b ∈ C k , and rational δ > 0 \delta>0 δ > 0 with d ( b ⃗ , W ( a ⃗ ) ) < δ d(\vec{b},W(\vec{a}))<\delta d ( b , W ( a )) < δ , one can compute a state ω \omega ω of A A A , computable as a functional on A # A^{\#} A # , with max i ∣ ω ( a i ) − b i ∣ < δ \max_i|\omega(a_i)-b_i|<\delta max i ∣ ω ( a i ) − b i ∣ < δ .
In particular, the states on A A A that are computable with respect to A # A^{\#} A # are weak∗ ^* ∗ -dense in S ( A ) S(A) S ( A ) .
Proof. (1) and (2) follow by taking n = 1 n=1 n = 1 in Corollary 2.7 and Theorem 2.8, using that UCP ( A , C ) = S ( A ) \operatorname{UCP}(A,\mathbb{C})=S(A) UCP ( A , C ) = S ( A ) and S 1 ( A ) = S ( A ) S_1(A)=S(A) S 1 ( A ) = S ( A ) . (Note that, in this case, (2) degenerates to the triviality max ω ∈ S ( A ) ω ( y ) = λ max ( y ) \max_{\omega\in S(A)}\omega(y)=\lambda_{\max}(y) max ω ∈ S ( A ) ω ( y ) = λ m a x ( y ) , and (1) says the support function of W ( a ⃗ ) W(\vec{a}) W ( a ) is computable because norms are.) (3) is an immediate consequence of (2). □
Effective nuclearity
Definition 3.1. Suppose that A # A^{\#} A # is a presentation of a C∗ ^* ∗ -algebra A A A . We say that A # A^{\#} A # is:
effectively nuclear if there is an algorithm such that, upon input a finite tuple a ⃗ \vec{a} a of generated points of A # A^{\#} A # and rational ϵ > 0 \epsilon>0 ϵ > 0 , returns:
a positive integer n ∈ N n\in\mathbb{N} n ∈ N , and
indices for computable ucp maps ϕ : A # → M n ( C ) \phi:A^{\#}\to M_n(\mathbb{C}) ϕ : A # → M n ( C ) and ψ : M n ( C ) → A # \psi:M_n(\mathbb{C})\to A^{\#} ψ : M n ( C ) → A #
such that
∥ ( ψ ∘ ϕ ) ( a ⃗ ) − a ⃗ ∥ < ϵ . \|(\psi\circ\phi)(\vec{a})-\vec{a}\|<\epsilon. ∥ ( ψ ∘ ϕ ) ( a ) − a ∥ < ϵ . effectively Choi-Effros nuclear if there is a uniformly computable sequence ϕ n : A # → A # \phi_n:A^{\#}\to A^{\#} ϕ n : A # → A # of finite rank ucp maps such that:
there is a computable function f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N such that rank ( ϕ n ) ≤ f ( n ) \operatorname{rank}(\phi_n)\leq f(n) rank ( ϕ n ) ≤ f ( n ) for all n ∈ N n\in\mathbb{N} n ∈ N , and
ϕ n \phi_n ϕ n computably converges pointwise to the identity, that is, there is an algorithm such that, given a generated point a a a of A # A^{\#} A # and ϵ > 0 \epsilon>0 ϵ > 0 , returns n ∈ N n\in\mathbb{N} n ∈ N such that ∥ ϕ m ( a ) − a ∥ < ϵ \|\phi_m(a)-a\|<\epsilon ∥ ϕ m ( a ) − a ∥ < ϵ for all m ≥ n m\geq n m ≥ n .
Recall our standing assumption is that the presentations of C∗ ^* ∗ -algebras that we consider must have the unit as a computable point. In fact, this property follows from being effectively nuclear, as does computability of the presentation.
Proposition 3.2. Suppose that A # A^{\#} A # is a presentation (not assumed to be computable or computably unital) of a unital C∗ ^{*} ∗ -algebra A A A . If A # A^{\#} A # is effectively nuclear then A # A^{\#} A # is computable and computably unital, and from an index for the algorithm witnessing the effective nuclearity of A # A^{\#} A # we can compute a unital index for A # A^{\#} A # .
Proof. Fix a generated point a a a of A # A^{\#} A # and ϵ > 0 \epsilon> 0 ϵ > 0 . Compute ucp maps ϕ : A → M n ( C ) \phi: A \to M_n(\mathbb{C}) ϕ : A → M n ( C ) and ψ : M n ( C ) → A \psi: M_n(\mathbb{C}) \to A ψ : M n ( C ) → A such that ∥ ( ψ ∘ ϕ ) ( a ) − a ∥ < ϵ \|(\psi\circ\phi)(a)-a\| < \epsilon ∥ ( ψ ∘ ϕ ) ( a ) − a ∥ < ϵ . Note then that ∥ a ∥ ≥ ∥ ϕ ( a ) ∥ ≥ ∥ ψ ( ϕ ( a ) ) ∥ ≥ ∥ a ∥ − ϵ \|a\| \ge\|\phi(a)\| \ge\|\psi(\phi(a))\| \ge\|a\|-\epsilon ∥ a ∥ ≥ ∥ ϕ ( a ) ∥ ≥ ∥ ψ ( ϕ ( a )) ∥ ≥ ∥ a ∥ − ϵ . Since ϕ \phi ϕ is computable, we can effectively approximate ∥ ϕ ( a ) ∥ \|\phi(a)\| ∥ ϕ ( a ) ∥ to within ϵ \epsilon ϵ , resulting in an effective approximation of ∥ a ∥ \|a\| ∥ a ∥ within 2 ϵ 2\epsilon 2 ϵ . Moreover, the standard presentation of M n ( C ) M_n(\mathbb{C}) M n ( C ) allows us to compute an index for the n × n n \times n n × n identity matrix 1 n 1_n 1 n , and thus we can compute an A # A^{\#} A # -index for computable point 1 A 1_A 1 A since 1 A = ψ ( 1 n ) 1_A=\psi(1_n) 1 A = ψ ( 1 n ) . □
Question 3.3. If A # A^{\#} A # is effective Choi-Effros nuclear, does it follows that A # A^{\#} A # is computable and computably unital?
We return to our convention that presentations of C∗ ^{*} ∗ -algebras are computably unital.
Before proving the main theorem of this section, we note the following result, which simply notes that the fact that perturbing an almost unital cp map to a ucp map can be carried out effectively:
Lemma 3.4. There is an an algorithm such that, upon input a unital index for a presentation A # A^{\#} A # of a C∗ ^{*} ∗ -algebra A A A and a computable cpc map ψ ′ : M n ( C ) → A \psi' : M_n(\mathbb{C}) \to A ψ ′ : M n ( C ) → A satisfying ∥ ψ ′ ( 1 ) − 1 ∥ < ϵ \|\psi'(1)-1\| < \epsilon ∥ ψ ′ ( 1 ) − 1∥ < ϵ with ϵ ≤ 1 / 2 \epsilon\le1/2 ϵ ≤ 1/2 , returns the index for a computable ucp map ψ : M n ( C ) → A \psi: M_n(\mathbb{C}) \to A ψ : M n ( C ) → A such that ∥ ψ − ψ ′ ∥ ≤ 2 ϵ \|\psi-\psi'\| \le2\epsilon ∥ ψ − ψ ′ ∥ ≤ 2 ϵ .
Proof. Since ϵ < 1 \epsilon< 1 ϵ < 1 , we have that ψ ′ ( 1 ) \psi'(1) ψ ′ ( 1 ) is an invertible, positive element of A A A . We thus know that ψ ′ ( 1 ) − 1 / 2 \psi'(1)^{-1/2} ψ ′ ( 1 ) − 1/2 exists. The desired ucp map is defined by
ψ ( x ) : = ψ ′ ( 1 ) − 1 / 2 ψ ′ ( x ) ψ ′ ( 1 ) − 1 / 2 . \psi(x) := \psi'(1)^{-1/2}\psi'(x)\psi'(1)^{-1/2}. ψ ( x ) := ψ ′ ( 1 ) − 1/2 ψ ′ ( x ) ψ ′ ( 1 ) − 1/2 .
One checks easily that ∥ ψ − ψ ′ ∥ ≤ ϵ / ( 1 − ϵ ) ≤ 2 ϵ \|\psi-\psi'\| \le\epsilon/(1-\epsilon) \le2\epsilon ∥ ψ − ψ ′ ∥ ≤ ϵ / ( 1 − ϵ ) ≤ 2 ϵ . If ψ ′ \psi' ψ ′ is computable, then ψ \psi ψ is computable, whence so is ψ ′ ( 1 ) − 1 / 2 \psi'(1)^{-1/2} ψ ′ ( 1 ) − 1/2 by the computable functional calculus [9 Corollary 4.6] . □
We again recall that our presentations are assumed to be computably unital.
Theorem 3.5. Suppose that A # A^{\#} A # is a presentation of a C∗ ^{*} ∗ -algebra A A A . The following are equivalent:
A # A^{\#} A # is computable and A A A is nuclear.
A # A^{\#} A # is effectively nuclear.
A # A^{\#} A # is computable and effectively Choi-Effros nuclear.
Proof. The implications (2)⇒ \Rightarrow ⇒ (3) and (3)⇒ \Rightarrow ⇒ (1) are clear. To see that (1) implies (2), suppose one is given a finite k k k -tuple a ⃗ \vec{a} a of generated points of A # A^{\#} A # and a rational ϵ > 0 \epsilon> 0 ϵ > 0 . Choose rational δ ∈ ( 0 , min ( ϵ / 4 , 1 / 2 ) ) \delta\in(0,\min(\epsilon/4,1/2)) δ ∈ ( 0 , min ( ϵ /4 , 1/2 )) . Search for a triple ( n , b ⃗ , w ) (n,\vec{b},w) ( n , b , w ) , where n ≥ 1 n \ge1 n ≥ 1 , b ⃗ \vec{b} b is a rational k k k -tuple from M n ( C ) M_n(\mathbb{C}) M n ( C ) , and w w w is a generated point of M n ( A ) # M_n(A)^{\#} M n ( A ) # such that:
d ( b ⃗ , K a ⃗ , n ) < δ d(\vec{b},K_{\vec{a},n}) < \delta d ( b , K a , n ) < δ ,
∥ ∑ j l π j l ( w ∗ w ) − 1 ∥ < δ \left\|\sum_{j l}\pi_{j l}(w^{*}w)-1\right\| < \delta ∑ j l π j l ( w ∗ w ) − 1 < δ
max 1 ≤ i ≤ k ∥ a i − ∑ j l π j l ( b i ) π j l ( w ∗ w ) ∥ < δ \max_{1\le i\le k}\left\|a_i-\sum_{j l}\pi_{j l}(b_i)\pi_{j l}(w^{*}w)\right\| < \delta max 1 ≤ i ≤ k a i − ∑ j l π j l ( b i ) π j l ( w ∗ w ) < δ .
By Corollary 2.7 above, this can be effectively done, and since A A A is nuclear, the search is successful. By Theorem 2.8 above, we can then compute an index for a computable ucp map ϕ : A → M n ( C ) \phi:A\to M_n(\mathbb{C}) ϕ : A → M n ( C ) such that max 1 ≤ i ≤ k ∥ ϕ ( a i ) − b i ∥ < δ \max_{1\leq i\leq k}\|\phi(a_i)-b_i\|<\delta max 1 ≤ i ≤ k ∥ ϕ ( a i ) − b i ∥ < δ . Let ψ ′ : M n ( C ) → A \psi':M_n(\mathbb{C})\to A ψ ′ : M n ( C ) → A be the unique linear map for which ψ ′ ( e j l ) = π j l ( w ∗ w ) \psi'(e_{jl})=\pi_{jl}(w^*w) ψ ′ ( e j l ) = π j l ( w ∗ w ) . Then ψ ′ \psi' ψ ′ is a computable cpc map with ∥ ψ ′ ( 1 ) − 1 ∥ < δ \|\psi'(1)-1\|<\delta ∥ ψ ′ ( 1 ) − 1∥ < δ . Note that
∥ ψ ′ ( ϕ ( a i ) ) − a i ∥ ≤ ∥ ψ ′ ( ϕ ( a i ) ) − ψ ′ ( b i ) ∥ + ∥ ψ ′ ( b i ) − a i ∥ ≤ 2 δ . \|\psi'(\phi(a_i))-a_i\|\leq\|\psi'(\phi(a_i))-\psi'(b_i)\|+\|\psi'(b_i)-a_i\|\leq2\delta. ∥ ψ ′ ( ϕ ( a i )) − a i ∥ ≤ ∥ ψ ′ ( ϕ ( a i )) − ψ ′ ( b i ) ∥ + ∥ ψ ′ ( b i ) − a i ∥ ≤ 2 δ .
By Lemma 3.4 , we may computably perturb ψ ′ \psi' ψ ′ to a computable ucp map ψ : M n ( C ) → A \psi:M_n(\mathbb{C})\to A ψ : M n ( C ) → A such that ∥ ψ − ψ ′ ∥ < 2 δ \|\psi-\psi'\|<2\delta ∥ ψ − ψ ′ ∥ < 2 δ . It follows that ∥ ψ ( ϕ ( a i ) ) − a i ∥ < 4 δ < ϵ \|\psi(\phi(a_i))-a_i\|<4\delta<\epsilon ∥ ψ ( ϕ ( a i )) − a i ∥ < 4 δ < ϵ .
We note that the proof of Theorem 3.5 is uniform if we are given a unital index for A # A^\# A # . On the other hand, it cannot be made uniform given just an index for A # A^\# A # without the index for the unit. Indeed, the third author has shown in [18 Theorem 5.3] that there is a commutative (hence nuclear) unital C*-algebra B B B for which there is no algorithm taking each index for a computable presentation of B B B to an index for the unit in that presentation, although the unit is a computable point in every computable presentation of B B B by [4 Theorem 4.1] . By Proposition 3.2 , for this B B B there is no algorithm taking each index for a computable presentation of B B B to an index for the algorithm witnessing effective nuclearity.
Computable categoricity of O2 _2 2
For separable, simple C*-algebras A A A , the Kirchberg-Phillips theorem states that A A A is nuclear if and only if A ⊗ O 2 ≅ O 2 A\otimes O_2\cong O_2 A ⊗ O 2 ≅ O 2 . It is tempting to effectivize this condition by insisting that ( A ⊗ O 2 ) # (A\otimes O_2)^\# ( A ⊗ O 2 ) # be computably isomorphic to O 2 O_2 O 2 , where O 2 O_2 O 2 is equipped with its standard presentation (which is computable, see [11 Corollary 3.16] ) and ( A ⊗ O 2 ) # (A\otimes O_2)^\# ( A ⊗ O 2 ) # is the associated tensor product presentation (see [15 Subsection 2.3] ). In this section, we will see that such a condition is equivalent to A # A^\# A # being computable and nuclear. This will follow from a result that is important in its own right, namely that O 2 O_2 O 2 is computably categorical, meaning any two computable presentations of O 2 O_2 O 2 are computably isomorphic. We now work towards proving that goal.
Definition 4.1. A tuple ( r 1 , … , r n ) (r_1,\ldots,r_n) ( r 1 , … , r n ) in O n O_n O n is a Cuntz n n n -tuple if it satisfies the Cuntz relations
r j ∗ r j = 1 r_j^*r_j=1 r j ∗ r j = 1 for all j = 1 , … , n j=1,\ldots,n j = 1 , … , n
∑ j = 1 n r j r j ∗ = 1 \sum_{j=1}^n r_jr_j^*=1 ∑ j = 1 n r j r j ∗ = 1
A generating Cuntz n n n -tuple is a Cuntz n n n -tuple that generates the entire ambient algebra O n O_n O n .
The proof of computable categoricity of O n O_n O n relies on the fact that every computable presentation of O n O_n O n contains a computable generating Cuntz n n n -tuple, that is, a generating Cuntz n n n -tuple consisting of computable points of the presentation. To prove this, we will need the following effective version of the Baire category theorem:
Lemma 4.2. Let X # X^\# X # be a computable presentation of a metric space. Suppose that D 0 ⊇ D 1 ⊇ ⋯ D_0\supseteq D_1\supseteq\cdots D 0 ⊇ D 1 ⊇ ⋯ are c.e. open sets of X # X^\# X # , each of which is dense in X X X . Then the set of computable points in ⋂ n ∈ N D n \bigcap_{n\in\mathbb{N}}D_n ⋂ n ∈ N D n is dense in X X X .
Proof. Fix a rational open ball B B B of X # X^\# X # . Since D 0 D_0 D 0 is dense in X X X , B ∩ D 0 ≠ ∅ B\cap D_0\ne\varnothing B ∩ D 0 = ∅ . Since B B B is a rational ball and D 0 D_0 D 0 is c.e. open, we can find a rational open ball B 0 B_0 B 0 such that B 0 ⊆ B ∩ D 0 B_0\subseteq B\cap D_0 B 0 ⊆ B ∩ D 0 and diam ( B 0 ) < 1 \operatorname{diam}(B_0)<1 diam ( B 0 ) < 1 . Now B 0 ∩ D 1 ≠ ∅ B_0\cap D_1\ne\varnothing B 0 ∩ D 1 = ∅ , and B 0 B_0 B 0 is a rational
open ball and D 1 D_1 D 1 is c.e. open, so we can find a rational open ball B 1 B_1 B 1 such that B 1 ⊆ B 0 ∩ D 1 B_1 \subseteq B_0 \cap D_1 B 1 ⊆ B 0 ∩ D 1 and diam ( B 1 ) < 1 / 2 \operatorname{diam}(B_1) < 1/2 diam ( B 1 ) < 1/2 . Continuing in this way we obtain rational open balls B ⊇ B 0 ⊇ B 1 ⊇ ⋯ B \supseteq B_0 \supseteq B_1 \supseteq\cdots B ⊇ B 0 ⊇ B 1 ⊇ ⋯ with each B j + 1 ⊆ B j ∩ D j + 1 B_{j+1} \subseteq B_j \cap D_{j+1} B j + 1 ⊆ B j ∩ D j + 1 and diam ( B j ) < 2 − j \operatorname{diam}(B_j) < 2^{-j} diam ( B j ) < 2 − j . The centres of the balls B 0 , B 1 , … B_0, B_1, \ldots B 0 , B 1 , … thus form a computably Cauchy sequence that converges to a computable point in B ∩ ⋂ n ∈ N D n B \cap\bigcap_{n\in\mathbb{N}} D_n B ∩ ⋂ n ∈ N D n . □
Lemma 4.3. For every n ∈ N n \in\mathbb{N} n ∈ N and every computable presentation O n # \mathcal{O}_n^\# O n # of O n \mathcal{O}_n O n , there is a computable generating Cuntz n n n -tuple of O n # \mathcal{O}_n^\# O n # .
Proof. The Cuntz relations are computably weakly stable (see [12 Example 12] ), so by [8 Theorem 1.12] the set of Cuntz n n n -tuples is a c.e. closed set of O n # \mathcal{O}_n^\# O n # . In particular, we can find a computable Cuntz n n n -tuple, say ( r 1 , … , r n ) (r_1,\ldots,r_n) ( r 1 , … , r n ) . For any unitary u u u , ( u r 1 , … , u r n ) (ur_1,\ldots,ur_n) ( u r 1 , … , u r n ) is clearly a Cuntz n n n -tuple. It therefore suffices to find a computable unitary u u u such that ( u r 1 , … , u r n ) (ur_1,\ldots,ur_n) ( u r 1 , … , u r n ) is generating.
Let U ( O n ) U(\mathcal{O}_n) U ( O n ) denote the set of unitaries in O n \mathcal{O}_n O n . Let ( a k ) k ∈ N (a_k)_{k\in\mathbb{N}} ( a k ) k ∈ N be a computable enumeration of the generated points of O n # \mathcal{O}_n^\# O n # , and let ( p k ( x 1 , … , x n ) ) k ∈ N (p_k(x_1,\ldots,x_n))_{k\in\mathbb{N}} ( p k ( x 1 , … , x n ) ) k ∈ N be a computable enumeration of the rational ∗ * ∗ -polynomials in n n n variables. For each m , k ∈ N m,k \in\mathbb{N} m , k ∈ N and each rational ϵ > 0 \epsilon> 0 ϵ > 0 , define
D m , k , ϵ = { u ∈ U ( O n ) : ∥ p m ( u r 1 , … , u r n ) − a k ∥ < ϵ } . D_{m,k,\epsilon} = \{u \in U(\mathcal{O}_n) : \lVert p_m(ur_1,\ldots,ur_n) - a_k \rVert< \epsilon\}. D m , k , ϵ = { u ∈ U ( O n ) : ∥ p m ( u r 1 , … , u r n ) − a k ∥ < ϵ } . For each k , ϵ k,\epsilon k , ϵ , let D k , ϵ = ⋃ m ∈ N D m , k , ϵ D_{k,\epsilon} = \bigcup_{m\in\mathbb{N}} D_{m,k,\epsilon} D k , ϵ = ⋃ m ∈ N D m , k , ϵ , and let D = ⋂ k ∈ N , ϵ ∈ Q > 0 D k , ϵ D = \bigcap_{k\in\mathbb{N},\epsilon\in\mathbb{Q}_{>0}} D_{k,\epsilon} D = ⋂ k ∈ N , ϵ ∈ Q > 0 D k , ϵ . Observe that u ∈ D u \in D u ∈ D if and only if ( u r 1 , … , u r n ) (ur_1,\ldots,ur_n) ( u r 1 , … , u r n ) is a generating Cuntz n n n -tuple. It thus remains to be shown that there is a computable point in D D D .
Let ( s 1 , … , s n ) (s_1,\ldots,s_n) ( s 1 , … , s n ) be a generating Cuntz n n n -tuple. Let
Y = { u ∈ U ( O n ) : ( u s 1 , … , u s n ) is generating } . Y = \{u \in U(\mathcal{O}_n) : (us_1,\ldots,us_n)\text{ is generating}\}. Y = { u ∈ U ( O n ) : ( u s 1 , … , u s n ) is generating } . Note that u ∈ Y u \in Y u ∈ Y if and only if the endomorphism determined by ( s 1 , … , s n ) ↦ ( u s 1 , … , u s n ) (s_1,\ldots,s_n) \mapsto(us_1,\ldots,us_n) ( s 1 , … , s n ) ↦ ( u s 1 , … , u s n ) is an automorphism. Rørdam [21 ] showed that the set of unitaries for which the corresponding endomorphism is an inner automorphism is dense (see [2 Proposition 7] for a self-contained proof). It follows that Y Y Y is also dense. Let v v v be the (unique) unitary such that ( r 1 , … , r n ) = ( v s 1 , … , v s n ) (r_1,\ldots,r_n) = (vs_1,\ldots,vs_n) ( r 1 , … , r n ) = ( v s 1 , … , v s n ) . Then for any unitary u u u we have u ∈ D u \in D u ∈ D if and only if u v ∈ Y uv \in Y uv ∈ Y , so D = Y v ∗ D = Yv^* D = Y v ∗ . Since multiplication on the right by v ∗ v^* v ∗ is an isometry of U ( O n ) U(\mathcal{O}_n) U ( O n ) , it follows that D D D is dense in U ( O n ) U(\mathcal{O}_n) U ( O n ) , and hence also that each D k , ϵ D_{k,\epsilon} D k , ϵ is dense in U ( O n ) U(\mathcal{O}_n) U ( O n ) .
The property of being a unitary is given by computably weakly stable relations, so U ( O n ) U(\mathcal{O}_n) U ( O n ) is a c.e. closed set of O n # \mathcal{O}_n^\# O n # . In particular, it contains a dense set of computable points, which we take to be the computable presentation U ( O n ) # U(\mathcal{O}_n)^\# U ( O n ) # of U ( O n ) U(\mathcal{O}_n) U ( O n ) induced by O n # \mathcal{O}_n^\# O n # . Observe that each D m , k , ϵ D_{m,k,\epsilon} D m , k , ϵ is a c.e. open set of U ( O n ) # U(\mathcal{O}_n)^\# U ( O n ) # , and therefore each D k , ϵ D_{k,\epsilon} D k , ϵ is also a c.e. open set of U ( O n ) # U(\mathcal{O}_n)^\# U ( O n ) # . Thus Lemma 4.2 implies that there is a computable point in D D D .
With the previous lemma in hand, we can now prove the main result of this section:
Theorem 4.4. For every n ≥ 2 n \ge2 n ≥ 2 , the Cuntz algebra O n \mathcal{O}_n O n is computably categorical.
Proof. Let O n # \mathcal{O}_n^\# O n # be a computable presentation of O n \mathcal{O}_n O n . Let O n † \mathcal{O}_n^\dagger O n † be the standard presentation of O n \mathcal{O}_n O n , that is, the presentation whose special points are a generating Cuntz n n n -tuple ( s 1 , … , s n ) (s_1,\ldots,s_n) ( s 1 , … , s n ) . By [11 Corollary 3.16] , O n † \mathcal{O}_n^\dagger O n † is a computable presentation. By Lemma 4.3 there is a generating Cuntz n n n -tuple ( r 1 , … , r n ) (r_1,\ldots,r_n) ( r 1 , … , r n ) with each r j r_j r j a computable point of O n # \mathcal{O}_n^\# O n # . The map induced by mapping each r j r_j r j to s j s_j s j is thus a computable isomorphism from O n # \mathcal{O}_n^\# O n # onto O n † \mathcal{O}_n^\dagger O n † .
Corollary 4.5. If A A A is a separable, simple C ∗ C^* C ∗ -algebra and A # A^\# A # is a computable presentation of A A A , then A A A is nuclear if and only if there is a computable isomorphism ( A ⊗ O 2 ) # ≅ O 2 (A \otimes O_2)^\# \cong O_2 ( A ⊗ O 2 ) # ≅ O 2 .
We remark that the proof of Theorem 4.4 does not seem to cover the case of the Cuntz algebra O ∞ O_\infty O ∞ (whose standard presentation is computable by [11 Corollary 3.16] ).
Question 4.6. Is the Cuntz algebra O ∞ O_\infty O ∞ computably categorical?
Effectively Kirchberg nuclear
General discussion
Definition 5.1. We say that A # A^\# A # is effectively Kirchberg nuclear if there is a computable embedding A # ↪ O 2 A^\# \hookrightarrow O_2 A # ↪ O 2 which admits a computable conditional expectation map O 2 → A # O_2 \to A^\# O 2 → A # .
Note that A # A^\# A # being effectively Kirchberg nuclear implies that A # A^\# A # is computable; in fact, this follows only from the assumption that there is a computable embedding A # ↪ O 2 A^\# \hookrightarrow O_2 A # ↪ O 2 .
Lemma 5.2.
Suppose that there is a computable embedding A # ↪ B # A^\# \hookrightarrow B^\# A # ↪ B # that admits a computable expectation B # → A # B^\# \to A^\# B # → A # . Further suppose that B # B^\# B # is effectively Kirchberg nuclear. Then A # A^\# A # is effectively Kirchberg nuclear.
If A # A^\# A # is a computable presentation of a simple nuclear C ∗ C^* C ∗ -algebra A A A , then A # A^\# A # is effectively Kirchberg nuclear.
For a presentation A # A^\# A # of a C ∗ C^* C ∗ -algebra A A A , we have that A # A^\# A # is effectively Kirchberg nuclear if and only if there is a computable presentation B # B^\# B # of a simple nuclear C ∗ C^* C ∗ -algebra B B B and a computable embedding A # ↪ B # A^\# \hookrightarrow B^\# A # ↪ B # with computable expectation B # → A # B^\# \to A^\# B # → A # .
Proof. (1) is immediate from the definitions. For (2), note that the obvious embedding A # ↪ ( A ⊗ O 2 ) # A^\# \hookrightarrow(A \otimes O_2)^\# A # ↪ ( A ⊗ O 2 ) # is computable. Moreover, if ϕ \phi ϕ is a computable state on O 2 O_2 O 2 (see Corollary 2.9 ), the slice map a ⊗ b ↦ ϕ ( b ) a : A ⊗ O 2 → A a \otimes b \mapsto\phi(b)a : A \otimes O_2 \to A a ⊗ b ↦ ϕ ( b ) a : A ⊗ O 2 → A is a computable conditional expectation for this embedding. It remains to use (1) and computable categoricity of O 2 O_2 O 2 . (3) then follows immediately from (1) and (2). □
Remark 5.3. In the above proof, one can explicitly construct a computable state on O 2 O_2 O 2 . Indeed, if we view the generators of O 2 O_2 O 2 as the transformations T 1 T_1 T 1 and T 2 T_2 T 2 on the separable Hilbert space H H H with orthonormal basis ( e n ) n ∈ N (e_n)_{n \in\mathbb{N}} ( e n ) n ∈ N for which T 1 ( e n ) = e 2 n T_1(e_n) = e_{2n} T 1 ( e n ) = e 2 n and T 2 ( e n ) = e 2 n + 1 T_2(e_n) = e_{2n+1} T 2 ( e n ) = e 2 n + 1 , then the vector state ⟨ ⋅ e 0 , e 0 ⟩ \langle\cdot e_0, e_0 \rangle ⟨ ⋅ e 0 , e 0 ⟩ is easily seen to be computable.
Question 5.4. Is every computable presentation of a nuclear C ∗ C^* C ∗ -algebra effectively Kirchberg nuclear?
While we do not have an answer to this question at the moment, in the next sections we give an affirmative answer for all computable presentations of commutative C ∗ C^* C ∗ -algebras, AF C ∗ C^* C ∗ -algebras, and group C ∗ C^* C ∗ -algebras associated to certain (but not all) amenable groups.
Commutative algebras
In this subsection we show that computable presentations of commutative unital C ∗ C^* C ∗ -algebras are effectively Kirchberg nuclear. Aside from C \mathbb{C} C , commutative C ∗ C^* C ∗ -algebras are never simple, so Lemma 5.2 (2) does not apply.
We begin by establishing effective Kirchberg nuclearity for the C ∗ C^* C ∗ -algebra C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) of continuous complex-valued functions on the Cantor space. This C ∗ C^* C ∗ -algebra is computably categorical [18 Corollary 6.7] , so we do not need to specify which computable presentation to consider.
Theorem 5.5. C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) is effectively Kirchberg nuclear.
Proof. Let B \mathbf{B} B be the CAR algebra, that is, the UHF algebra with supernatural number 2 ∞ 2^\infty 2 ∞ . The CAR algebra is the universal C ∗ C^* C ∗ -algebra generated by a sequence ( b n ) n ∈ N (b_n)_{n\in\mathbb{N}} ( b n ) n ∈ N satisfying the CAR relations for all n n n and m m m :
b n b m + b m b n = 0 and b n b m ∗ + b m ∗ b n = { 1 n = m , 0 n ≠ m . b_n b_m+b_m b_n=0 \qquad\text{and}\qquad b_n b_m^*+b_m^* b_n=\begin{cases}1 & n=m,\\0 & n\ne m.\end{cases} b n b m + b m b n = 0 and b n b m ∗ + b m ∗ b n = { 1 0 n = m , n = m .
Let B # \mathbf{B}^{\#} B # be the presentation of B \mathbf{B} B whose special points are ( b n ) n ∈ N (b_n)_{n\in\mathbb{N}} ( b n ) n ∈ N . By [11 Theorem 3.11] , the presentation B # \mathbf{B}^{\#} B # is c.e., and since B \mathbf{B} B is simple, by [11 Theorem 3.14] , B # \mathbf{B}^{\#} B # is computable. For each n n n , let d n = b n ∗ b n d_n=b_n^*b_n d n = b n ∗ b n . Let D \mathbf{D} D be the C ∗ C^* C ∗ -subalgebra of B \mathbf{B} B generated by ( d n ) n ∈ N (d_n)_{n\in\mathbb{N}} ( d n ) n ∈ N . It is well-known that D ≅ C ( 2 N ) \mathbf{D}\cong C(2^{\mathbb{N}}) D ≅ C ( 2 N ) . Let D # \mathbf{D}^{\#} D # be the presentation of D \mathbf{D} D whose special points are also ( d n ) n ∈ N (d_n)_{n\in\mathbb{N}} ( d n ) n ∈ N . There is a uniform procedure for writing any generated point of D # \mathbf{D}^{\#} D # as a generated point of B # \mathbf{B}^{\#} B # , whence computability of D # \mathbf{D}^{\#} D # follows from computability of B # \mathbf{B}^{\#} B # . As mentioned above, C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) is computably categorical; by Lemma 5.2 (3), it thus suffices to show that the computable embedding of D # \mathbf{D}^{\#} D # into B # \mathbf{B}^{\#} B # admits a computable conditional expectation.
Indeed, there is a canonical conditional expectation map for this embedding, defined as follows. Fix n ∈ N n\in\mathbb{N} n ∈ N and t = ( t 1 , … , t n ) ∈ { 0 , 1 } n t=(t_1,\ldots,t_n)\in\{0,1\}^n t = ( t 1 , … , t n ) ∈ { 0 , 1 } n , and define
P t : = ∏ i = 1 n d i t i ( 1 − d i ) 1 − t i . P_t:=\prod_{i=1}^{n}d_i^{t_i}(1-d_i)^{1-t_i}. P t := i = 1 ∏ n d i t i ( 1 − d i ) 1 − t i .
The expectation map E : B → D E:\mathbf{B}\to\mathbf{D} E : B → D is defined on elements of C ∗ ( b 1 , … , b n ) C^*(b_1,\ldots,b_n) C ∗ ( b 1 , … , b n ) by
E ( x ) : = ∑ t ∈ { 0 , 1 } n P t x P t . E(x):=\sum_{t\in\{0,1\}^n}P_t xP_t. E ( x ) := t ∈ { 0 , 1 } n ∑ P t x P t .
In particular, this shows that E E E is computable on generated points of B # \mathbf{B}^{\#} B # . Since E E E is contractive, this suffices to show that E E E is a computable map from B # \mathbf{B}^{\#} B # to D # \mathbf{D}^{\#} D # . □
Miljutin [19 ] showed (in different terminology) that C ( [ 0 , 1 ] ) C([0,1]) C ([ 0 , 1 ]) embeds into C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) with a conditional expectation. This result was then extended from [ 0 , 1 ] [0,1] [ 0 , 1 ] to arbitrary compact metric spaces by Pełczyński [20 ] . We now prove an effective version of this result.
Suppose that X X X is a compact Polish space. Recall from [18 ] that a presentation C ( X ) † C(X)^\dagger C ( X ) † of C ( X ) C(X) C ( X ) is evaluative over a presentation X # X^{\#} X # of X X X if the map ( f , p ) ↦ f ( p ) (f,p)\mapsto f(p) ( f , p ) ↦ f ( p ) is from the presentation of C ( X ) × X C(X)\times X C ( X ) × X induced by C ( X ) † C(X)^\dagger C ( X ) † and X # X^{\#} X # . It was shown in [18 Theorem 1.3] that, given a computably compact presentation X # X^{\#} X # of X X X , there is a unique (up to computable isomorphism) computable presentation C ( X # ) C(X^{\#}) C ( X # ) of C ( X ) C(X) C ( X ) that is evaluative over X # X^{\#} X # .
Lemma 5.6. Suppose that X # X^\# X # is a computably compact presentation of a compact Polish space X X X . For each f : X → C f:X\to\mathbb{C} f : X → C , the following are equivalent:
Moreover, a C ( X # ) C(X^\#) C ( X # ) -name for f f f can be computed from an index for f f f as a computable map, and vice-versa.
Proof. Suppose first that f f f is a computable map. Given any computable g : X # → C g:X^\#\to\mathbb{C} g : X # → C , the function ∣ f − g ∣ \lvert f-g\rvert ∣ f − g ∣ is also computable, and hence by [5 Proposition 3.5(1)] , ∥ f − g ∥ \lVert f-g\rVert ∥ f − g ∥ is computable, uniformly in the pair ( f , g ) (f,g) ( f , g ) . Let ( a n ) n ∈ N (a_n)_{n\in\mathbb{N}} ( a n ) n ∈ N be an effective enumeration of the generated points of C ( X # ) C(X^\#) C ( X # ) . By definition of C ( X # ) C(X^\#) C ( X # ) , each a n a_n a n is a computable map from X # X^\# X # to C \mathbb{C} C , uniformly in n n n . Therefore, given k ∈ N k\in\mathbb{N} k ∈ N , we can search until an n ( k ) n(k) n ( k ) is located such that ∥ f − a n ( k ) ∥ < 2 − k \lVert f-a_{n(k)}\rVert<2^{-k} ∥ f − a n ( k ) ∥ < 2 − k . Then ( a n ( k ) ) k ∈ N (a_{n(k)})_{k\in\mathbb{N}} ( a n ( k ) ) k ∈ N is a C ( X # ) C(X^\#) C ( X # ) -name for f f f , so f f f is a computable point of C ( X # ) C(X^\#) C ( X # ) .
Now suppose that f f f is a computable point of C ( X # ) C(X^\#) C ( X # ) . Let E : C ( X ) × X → C E:C(X)\times X\to\mathbb{C} E : C ( X ) × X → C be the evaluation map E ( f , x ) = f ( x ) E(f,x)=f(x) E ( f , x ) = f ( x ) . Since C ( X # ) C(X^\#) C ( X # ) is evaluative over X # X^\# X # , E E E is computable. It follows that f f f is a computable map, and an index for f f f can be computed from a C ( X # ) C(X^\#) C ( X # ) -name for f f f and an index for E E E . □
Theorem 5.7. Let X # X^\# X # be a computably compact presentation of a compact Polish space X X X . Then there is a computable embedding of C ( X # ) C(X^\#) C ( X # ) into C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) with a computable conditional expectation.
Proof. Using the computable compactness of X # X^\# X # , we can compute a positive integer N N N such that diam ( X ) < N \operatorname{diam}(X)<N diam ( X ) < N . We next use computable compactness to construct a tree of open balls in X X X . Specifically, we compute:
An increasing sequence ( k s ) s ∈ N (k_s)_{s\in\mathbb{N}} ( k s ) s ∈ N of positive integers.
An array ( B s , n ) s ∈ N , n < k s (B_{s,n})_{s\in\mathbb{N},n<k_s} ( B s , n ) s ∈ N , n < k s of rational open balls of X # X^\# X # .
An array ( j s + 1 , n ) s ∈ N , n ≤ k s (j_{s+1,n})_{s\in\mathbb{N},n\leq k_s} ( j s + 1 , n ) s ∈ N , n ≤ k s of nonnegative integers.
We require that:
The formal diameter of B s , n B_{s,n} B s , n is at most 2 − s N 2^{-s}N 2 − s N .
X = ⋃ n < k s B s , n X=\bigcup_{n<k_s}B_{s,n} X = ⋃ n < k s B s , n .
0 = j s + 1 , 0 < ⋯ < j s + 1 , k s = k s + 1 0=j_{s+1,0}<\cdots<j_{s+1,k_s}=k_{s+1} 0 = j s + 1 , 0 < ⋯ < j s + 1 , k s = k s + 1 .
B s + 1 , n ⊆ B s , n ′ B_{s+1,n}\subseteq B_{s,n'} B s + 1 , n ⊆ B s , n ′ when j s + 1 , n ′ ≤ n < j s + 1 , n ′ + 1 j_{s+1,n'}\leq n<j_{s+1,n'+1} j s + 1 , n ′ ≤ n < j s + 1 , n ′ + 1 .
Call a sequence σ ∈ N < ω ∖ { ∅ } \sigma\in\mathbb{N}^{<\omega}\setminus\{\emptyset\} σ ∈ N < ω ∖ { ∅ } valid if σ ( 0 ) < k 0 \sigma(0)<k_0 σ ( 0 ) < k 0 and j s + 1 , σ ( s ) ≤ σ ( s + 1 ) < j s + 1 , σ ( s ) + 1 j_{s+1,\sigma(s)}\leq\sigma(s+1)<j_{s+1,\sigma(s)+1} j s + 1 , σ ( s ) ≤ σ ( s + 1 ) < j s + 1 , σ ( s ) + 1 whenever s + 1 < ∣ σ ∣ s+1<\lvert\sigma\rvert s + 1 < ∣ σ ∣ . Observe that a non-empty subsequence of a valid sequence is again valid. Let T = { σ ∈ N < ω ∖ { ∅ } : σ is valid } ∪ { ∅ } T=\{\sigma\in\mathbb{N}^{<\omega}\setminus\{\emptyset\}:\sigma\text{ is valid}\}\cup\{\emptyset\} T = { σ ∈ N < ω ∖ { ∅ } : σ is valid } ∪ { ∅ } .
When σ ∈ T \sigma\in T σ ∈ T , set
B σ = { X σ = ∅ , B ∣ σ ∣ − 1 , σ ( ∣ σ ∣ − 1 ) σ ≠ ∅ . B_\sigma=
\begin{cases}
X & \sigma=\emptyset,\\
B_{\lvert\sigma\rvert-1,\sigma(\lvert\sigma\rvert-1)} & \sigma\ne\emptyset.
\end{cases} B σ = { X B ∣ σ ∣ − 1 , σ (∣ σ ∣ − 1 ) σ = ∅ , σ = ∅.
Let [ T ] [T] [ T ] denote the set of branches through T T T , equipped with the usual ultrametric d ( β 1 , β 2 ) = 2 − n d(\beta_1,\beta_2)=2^{-n} d ( β 1 , β 2 ) = 2 − n , where n n n is the length of the longest common initial segment of β 1 \beta_1 β 1 and β 2 \beta_2 β 2 . Note that T T T is a computable tree with no dead ends, and it is computably branching, in the sense that there is a computable binary function B B B such that if σ ∈ T \sigma\in T σ ∈ T and ρ ∈ T \rho\in T ρ ∈ T extends σ \sigma σ , then for all i < ∣ ρ ∣ i<\lvert\rho\rvert i < ∣ ρ ∣ , ρ ( i ) ≤ B ( σ , i ) \rho(i)\leq B(\sigma,i) ρ ( i ) ≤ B ( σ , i ) . It follows that there is a computable presentation [ T ] # [T]^\# [ T ] # of [ T ] [T] [ T ] and a computable surjection from 2 N 2^{\mathbb{N}} 2 N onto [ T ] [T] [ T ] (see [5 Theorem 3.40, proof of Claim 1] ; the presentation has special points of the form v σ v_{\sigma} v σ where σ ∈ T \sigma\in T σ ∈ T and v σ v_{\sigma} v σ is the leftmost branch of T T T extending σ \sigma σ ); by [5 Lemma 3.31] , [ T ] # [T]^{\#} [ T ] # is computably compact.
Since [ T ] [T] [ T ] is a compact 0-dimensional Hausdorff space without isolated points, it is homeomorphic to 2 N 2^{\mathbb{N}} 2 N , and hence C ( [ T ] ) ≅ C ( 2 N ) C([T]) \cong C(2^{\mathbb{N}}) C ([ T ]) ≅ C ( 2 N ) . By computable categoricity of C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) , C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) is computably isomorphic to the standard presentation of C ( 2 N ) C(2^{\mathbb{N}}) C ( 2 N ) . Thus it suffices to find a computable embedding of C ( X # ) C(X^{\#}) C ( X # ) into C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) with a computable conditional expectation.
Conditions (1) and (4) ensure that if β ∈ [ T ] \beta\in[T] β ∈ [ T ] , then { B ‾ σ : σ ⊂ β } \{\overline{B}_{\sigma} : \sigma\subset\beta\} { B σ : σ ⊂ β } is a nested family of closed balls whose diameters shrink to 0, and moreover ⋂ σ ⊂ β B σ = ⋂ σ ⊂ β B ‾ σ \bigcap_{\sigma\subset\beta} B_{\sigma} = \bigcap_{\sigma\subset\beta} \overline{B}_{\sigma} ⋂ σ ⊂ β B σ = ⋂ σ ⊂ β B σ . We define F : [ T ] → X F : [T] \to X F : [ T ] → X by setting F ( β ) F(\beta) F ( β ) to be the unique point of ⋂ σ ⊂ β B σ \bigcap_{\sigma\subset\beta} B_{\sigma} ⋂ σ ⊂ β B σ . It follows from condition (2) that F F F is surjective. Condition (1) ensures that the centers of the balls B σ B_{\sigma} B σ for σ ⊂ β \sigma\subset\beta σ ⊂ β form a computably Cauchy sequence in X X X , and hence F F F is a computable map from [ T ] # [T]^{\#} [ T ] # to X # X^{\#} X # . Let F ~ : C ( X ) → C ( [ T ] ) \widetilde{F} : C(X) \to C([T]) F : C ( X ) → C ([ T ]) be the Gelfand dual of F F F . By [18 Proposition 6.2] , F ~ \widetilde{F} F is a computable embedding of C ( X # ) C(X^{\#}) C ( X # ) into C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) .
We next turn to finding the associated computable conditional expectation map.
By [24 Theorem 3] , for each s s s we can find a computable partition of unity subordinate to the cover { B s , n : n < k s } \{B_{s,n} : n < k_s\} { B s , n : n < k s } , and moreover we can do this uniformly in s s s . More specifically, there exists an array ( ψ s , n ) s ∈ N , n < k s (\psi_{s,n})_{s \in\mathbb{N},n<k_s} ( ψ s , n ) s ∈ N , n < k s so that:
ψ s , n \psi_{s,n} ψ s , n is a computable map of X # X^{\#} X # into [ 0 , 1 ] [0,1] [ 0 , 1 ] uniformly in s , n s,n s , n .
ψ s , n ( x ) = 0 \psi_{s,n}(x) = 0 ψ s , n ( x ) = 0 whenever x ∉ B s , n x \notin B_{s,n} x ∈ / B s , n .
For each s s s , ∑ n ψ s , n = 1 \sum_n \psi_{s,n} = 1 ∑ n ψ s , n = 1 .
For each p ∈ X p \in X p ∈ X , define μ p \mu_p μ p to be the unique Borel probability measure on [ T ] [T] [ T ] so that, for each σ ∈ T \sigma\in T σ ∈ T , we have
μ p ( [ σ ] ) = ∏ j < ∣ σ ∣ ψ j , σ ( j ) ( p ) \mu_p([\sigma]) = \prod_{j<|\sigma|} \psi_{j,\sigma(j)}(p) μ p ([ σ ]) = j < ∣ σ ∣ ∏ ψ j , σ ( j ) ( p )
(where we define the product over the empty set to be 1).
Let E : C ( [ T ] ) → C ( X ) E : C([T]) \to C(X) E : C ([ T ]) → C ( X ) be defined by
E ( g ) ( p ) = ∫ F − 1 ( { p } ) g d μ p . E(g)(p) = \int_{F^{-1}(\{p\})} g \,d\mu_p. E ( g ) ( p ) = ∫ F − 1 ({ p }) g d μ p .
This map E E E is a conditional expectation for the embedding F ~ : C ( X ) → C ( [ T ] ) \widetilde{F} : C(X) \to C([T]) F : C ( X ) → C ([ T ]) . Our construction ensures that for each p p p we have μ p ( [ T ] ∖ F − 1 ( { p } ) ) = 0 \mu_p([T] \setminus F^{-1}(\{p\})) = 0 μ p ([ T ] ∖ F − 1 ({ p })) = 0 , so we can equivalently write
E ( g ) ( p ) = ∫ [ T ] g d μ p . E(g)(p) = \int_{[T]} g \,d\mu_p. E ( g ) ( p ) = ∫ [ T ] g d μ p .
It remains to be shown that E E E is computable as a map from C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) to C ( X # ) C(X^{\#}) C ( X # ) . Let S : C ( [ T ] ) × X → C S : C([T]) \times X \to\mathbb{C} S : C ([ T ]) × X → C be defined by
S ( g , p ) = ∫ [ T ] g d μ p . S(g,p) = \int_{[T]} g \,d\mu_p. S ( g , p ) = ∫ [ T ] g d μ p .
Let P ( [ T ] ) P([T]) P ([ T ]) denote the space of Radon probability measures on [ T ] [T] [ T ] with the Prokhorov metric (which we denote by d P d_P d P ). Define P ( [ T ] # ) P([T]^{\#}) P ([ T ] # ) to be the presentation of P ( [ T ] ) P([T]) P ([ T ]) whose special points are the convex rational linear combinations of point masses at the special points of [ T ] # [T]^{\#} [ T ] # . It was shown in [16 Proposition 4.1.1] that the presentation P ( [ T ] # ) P([T]^{\#}) P ([ T ] # ) is computable.
Suppose we have computable points g g g of C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) and p p p of X # X^{\#} X # . We describe an algorithm for computing S ( g , p ) S(g,p) S ( g , p ) . First, since the map ( q , σ ) ↦ μ q ( [ σ ] ) (q,\sigma) \mapsto\mu_q([\sigma]) ( q , σ ) ↦ μ q ([ σ ]) is computable, it follows that q ↦ μ q q \mapsto\mu_q q ↦ μ q is a computable map from X # X^{\#} X # to P ( [ T ] # ) P([T]^{\#}) P ([ T ] # ) . Thus we can compute a sequence ( μ n ) n ∈ N (\mu_n)_{n\in\mathbb{N}} ( μ n ) n ∈ N in P ( [ T ] ) P([T]) P ([ T ]) of special points of P ( [ T ] # ) P([T]^{\#}) P ([ T ] # ) that effectively converges to μ p \mu_p μ p . By definition of the presentation P ( [ T ] # ) P([T]^{\#}) P ([ T ] # ) and the fact that C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) is evaluative over T # T^{\#} T # , the map n ↦ ∫ [ T ] g d μ n n \mapsto\int_{[T]}g\,d\mu_n n ↦ ∫ [ T ] g d μ n is computable, uniformly in g g g .
By [22 Theorem 4.3 and Theorem 4.10] , ( μ n ) n ∈ N (\mu_n)_{n\in\mathbb{N}} ( μ n ) n ∈ N uniformly effectively weakly converges to μ p \mu_p μ p . By definition, this means that from a name for f ∈ C ( [ T ] ) f\in C([T]) f ∈ C ([ T ]) and a bound on ∥ f ∥ \lVert f\rVert ∥ f ∥ we can compute a modulus of convergence for ( ∫ [ T ] f d μ n ) n ∈ N (\int_{[T]}f\,d\mu_n)_{n\in\mathbb{N}} ( ∫ [ T ] f d μ n ) n ∈ N converging to ∫ [ T ] f d μ p \int_{[T]}f\,d\mu_p ∫ [ T ] f d μ p . Since g g g is a computable point of C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) we can compute ∥ g ∥ \lVert g\rVert ∥ g ∥ . We therefore have a computable sequence of computable complex numbers that effectively converges to S ( g , p ) S(g,p) S ( g , p ) , uniformly in g g g and p p p , as required to show that S S S is computable. Since S S S is computable, the map p ↦ S ( g , p ) p\mapsto S(g,p) p ↦ S ( g , p ) is computable, uniformly in g g g . That is, E ( g ) : [ T ] # → C E(g):[T]^{\#}\to\mathbb{C} E ( g ) : [ T ] # → C is a computable map, uniformly in g g g . By Lemma 5.6 it follows that E ( g ) E(g) E ( g ) is a computable point of C ( [ T ] # ) C([T]^{\#}) C ([ T ] # ) , uniformly in g g g , so E E E is computable. □
Lemma 5.2 and Theorems 5.5 and 5.7 immediately imply:
Corollary 5.8. Every computable presentation of a commutative unital C -∗ * ∗ -algebra is effectively Kirchberg nuclear.*
AF-algebras
In this subsection, we establish that any computable presentation of an AF-algebra is effectively Kirchberg nuclear.
Proposition 5.9. Suppose that A A A is an AF algebra with computable presentation A # A^{\#} A # . Then A # A^{\#} A # is effectively Kirchberg nuclear.
Proof. By Lemma 5.2, it suffices to show that A # A^{\#} A # admits a computable embedding into a computable presentation B # B^{\#} B # of a UHF algebra B B B that admits a computable expectation. To carry this out, fix a computable AF-certificate ( F j , ψ j ) (F_j,\psi_j) ( F j , ψ j ) for A # A^{\#} A # (see [10 Main Theorem 1] ). One may then compute unital embeddings F j ↪ M k ( j ) ( C ) F_j\hookrightarrow M_{k(j)}(\mathbb{C}) F j ↪ M k ( j ) ( C ) into full matrix algebras in a coherent way. Set B : = lim M k ( j ) ( C ) B:=\lim M_{k(j)}(\mathbb{C}) B := lim M k ( j ) ( C ) , which is then a UHF algebra. By construction, the embedding A # ↪ B # A^{\#}\hookrightarrow B^{\#} A # ↪ B # is computable, where B # B^{\#} B # is the inductive limit presentation of B B B corresponding to the standard presentation the M k ( j ) M_{k(j)} M k ( j ) ’s. Finally, note that the embeddings F j ↪ M k ( j ) ( C ) F_j\hookrightarrow M_{k(j)}(\mathbb{C}) F j ↪ M k ( j ) ( C ) admit canonical conditional expectation maps, which are clearly computable, and moreover these conditional expectation maps are coherent throughout the sequence. It follows that they yield a computable conditional expectation map B # → A # B^{\#}\to A^{\#} B # → A # , completing the proof. □
Group C*-algebras
In this section, we show that certain group C*-∗ * ∗ -algebras associated to amenable groups are effectively Kirchberg nuclear. Our approach is dynamical and so we need not take a short detour through crossed product C*-∗ * ∗ -algebras and their presentations.
First, we recall that a presented group (in the sense of Fox [11 Definition 3.19] ) is a pair G # : = ( G , ( g n ) n ∈ N ) G^{\#}:=(G,(g_n)_{n\in\mathbb{N}}) G # := ( G , ( g n ) n ∈ N ) , where G G G is a group and ( g n ) n ∈ N (g_n)_{n\in\mathbb{N}} ( g n ) n ∈ N is a countable sequence in G G G generating G G G as a group; in this case, we say that G # G^{\#} G # is a presentation of G G G . We say that the presentation G # G^{\#} G # is computable if there is an algorithm such that, upon input a finite word in the sequence ( g n ) n ∈ N (g_n)_{n\in\mathbb{N}} ( g n ) n ∈ N , determines whether or not the word equals the identity in G G G .
Suppose now that G ↷ α A G \curvearrowright^{\alpha} A G ↷ α A is an action of a group G G G on a C*-algebra A A A . Then the universal crossed product C*-algebra A ⋊ α G A \rtimes_{\alpha} G A ⋊ α G can be described by the universal C*-algebra generated by unitaries u s u_s u s for s ∈ G s \in G s ∈ G and the elements of A A A subject to the relations on G G G and the relations stating that α s ( a ) = u s a u s ∗ \alpha_s(a)=u_sau_s^* α s ( a ) = u s a u s ∗ for all s ∈ G s \in G s ∈ G and a ∈ A a \in A a ∈ A . (If G = ⟨ S ∣ R ⟩ G=\langle S\mid R\rangle G = ⟨ S ∣ R ⟩ , then the above description can consider only unitaries coming from S S S , relations coming from R R R , and conjugation relations using only elements from S S S .) As such, if G # G^\# G # and A # A^\# A # are presentations of G G G and A A A respectively, one obtains a canonical induced presentation ( A ⋊ α G ) # (A\rtimes_{\alpha}G)^\# ( A ⋊ α G ) # of A ⋊ α G A\rtimes_{\alpha}G A ⋊ α G . In this context, we say that the action G # ↷ α A # G^\# \curvearrowright^{\alpha} A^\# G # ↷ α A # is computable if there is an algorithm such that, upon input of a special point g g g of G # G^\# G # , generated point a a a of A # A^\# A # , and rational ϵ > 0 \epsilon>0 ϵ > 0 , returns a generated point b b b of A # A^\# A # such that ∥ α g ( a ) − b ∥ < ϵ \lVert\alpha_g(a)-b\rVert<\epsilon ∥ α g ( a ) − b ∥ < ϵ . If this is the case and G # G^\# G # and A # A^\# A # are additionally assumed to be computable, then ( A ⋊ α G ) # (A\rtimes_{\alpha}G)^\# ( A ⋊ α G ) # is c.e. (In fact, it suffices for G # G^\# G # and A # A^\# A # to be merely c.e.)
Let C c ( G , A ) C_c(G,A) C c ( G , A ) denote the set of finite formal sums ∑ s ∈ G a s u s \sum_{s\in G}a_su_s ∑ s ∈ G a s u s with each a s ∈ A a_s\in A a s ∈ A . C c ( G , A ) C_c(G,A) C c ( G , A ) is naturally a *-algebra under the twisted multiplication and involution operations given by
( ∑ s a s u s ) ( ∑ s b s u s ) = ∑ s , t a s α s ( b t ) u s t \left(\sum_s a_su_s\right)\left(\sum_s b_su_s\right)=\sum_{s,t}a_s\alpha_s(b_t)u_{st} ( s ∑ a s u s ) ( s ∑ b s u s ) = s , t ∑ a s α s ( b t ) u s t
and
( ∑ s a s u s ) ∗ = ∑ s α s − 1 ( a s ∗ ) u s − 1 . \left(\sum_s a_su_s\right)^*=\sum_s\alpha_{s^{-1}}(a_s^*)u_{s^{-1}}. ( s ∑ a s u s ) ∗ = s ∑ α s − 1 ( a s ∗ ) u s − 1 .
Note that A A A can be viewed as a *-subalgebra of C c ( G , A ) C_c(G,A) C c ( G , A ) by identifying a ∈ A a\in A a ∈ A with the formal sum ∑ s a s u s \sum_s a_su_s ∑ s a s u s with a e = a a_e=a a e = a and a s = 0 a_s=0 a s = 0 for s ≠ e s\ne e s = e . Note also that C c ( G , A ) C_c(G,A) C c ( G , A ) sits naturally as a dense subalgebra of A ⋊ α G A\rtimes_{\alpha}G A ⋊ α G .
Suppose now that A ⊆ B ( H ) A\subseteq B(H) A ⊆ B ( H ) is a faithful representation of A A A . We define a representation of the -algebra C c ( G , A ) C_c(G,A) C c ( G , A ) on the Hilbert space H ⊗ ℓ 2 ( G ) H\otimes\ell^2(G) H ⊗ ℓ 2 ( G ) by defining a u s ( v ⊗ δ t ) : = α t − 1 ( a ) ( v ) ⊗ δ s t au_s(v\otimes\delta_t):=\alpha_{t^{-1}}(a)(v)\otimes\delta_{st} a u s ( v ⊗ δ t ) := α t − 1 ( a ) ( v ) ⊗ δ s t . One defines the reduced crossed product A ⋊ r , α G A\rtimes_{r,\alpha}G A ⋊ r , α G to be the C -subalgebra of B ( H ⊗ ℓ 2 ( G ) ) B(H\otimes\ell^2(G)) B ( H ⊗ ℓ 2 ( G )) generated by the image of C c ( G , A ) C_c(G,A) C c ( G , A ) . It is known that this C*-algebra is independent on the choice of faithful representation A ⊆ B ( H ) A\subseteq B(H) A ⊆ B ( H ) (see, for example, [3 Proposition 4.1.5] ). If G # G^\# G # and A # A^\# A # are presentations of G G G and A A A respectively, then there is a canonical induced presentation ( A ⋊ r , α G ) # (A\rtimes_{r,\alpha}G)^\# ( A ⋊ r , α G ) # of A ⋊ r , α G A\rtimes_{r,\alpha}G A ⋊ r , α G consisting of finite formal sums ∑ s a s u s \sum_s a_su_s ∑ s a s u s with each a s a_s a s a generated point of A # A^\# A # .
Once again suppose that A # A^\# A # is a presentation of A A A and further assume that H # H^\# H # is a presentation of H H H . We say that the representation A # ⊆ B ( H # ) A^\#\subseteq B(H^\#) A # ⊆ B ( H # ) is computable if there is an algorithm such that, upon input a generated point a a a of A # A^\# A # , a generated point v v v of H # H^\# H # , and ϵ > 0 \epsilon>0 ϵ > 0 , returns a generated point w w w of H # H^\# H # such that ∥ a v − w ∥ < ϵ \lVert av-w\rVert<\epsilon ∥ a v − w ∥ < ϵ . The following lemma follows immediately from the definitions:
Lemma 5.10. Suppose that G # G^\# G # is a computable presentation, G # ↷ α A # G^\# \curvearrowright^{\alpha} A^\# G # ↷ α A # is a computable action, and A # ⊆ B ( H # ) A^\#\subseteq B(H^\#) A # ⊆ B ( H # ) is a computable representation. Then the induced presentation ( A ⋊ r , α G ) # (A\rtimes_{r,\alpha}G)^\# ( A ⋊ r , α G ) # is left-c.e.
If the action G ↷ α A G\curvearrowright^{\alpha} A G ↷ α A is amenable (for example, when G G G is amenable), then the canonical surjective morphism A ⋊ α G → A ⋊ r , α G A\rtimes_{\alpha}G\to A\rtimes_{r,\alpha}G A ⋊ α G → A ⋊ r , α G is an isomorphism (see [3 Theorem 4.3.4] ). In this case, we have:
Proposition 5.11. Suppose that G # G^{\#} G # is a computable presentation of G G G , A # A^{\#} A # is a computable presentation of A A A , and G # ↷ α A # G^{\#} \curvearrowright_{\alpha} A^{\#} G # ↷ α A # is a computable, amenable action. Furthermore, suppose that there is a computable representation A # ⊆ B ( H # ) A^{\#} \subseteq B(H^{\#}) A # ⊆ B ( H # ) . Then the induced presentation ( A ⋊ α G ) # (A \rtimes_{\alpha} G)^{\#} ( A ⋊ α G ) # is computable.
We now need to discuss situations where an embedding of a group C ∗ C^* C ∗ -algebra into a crossed product admits a conditional expectation. This is essentially standard fare; we are simply paying attention to the computability aspects of the expectation:
Lemma 5.12. Let G # ↷ α A # G^{\#} \curvearrowright_{\alpha} A^{\#} G # ↷ α A # be a computable action of a computable presentation of a group on a computable presentation of a unital C ∗ C^* C ∗ -algebra, and let φ \varphi φ be a α \alpha α -invariant state on A A A which is computable with respect to A # A^{\#} A # . Then:
The canonical map ι : C ∗ ( G ) → A ⋊ α G \iota: C^*(G) \to A \rtimes_{\alpha} G ι : C ∗ ( G ) → A ⋊ α G , u s ↦ 1 A u s u_s \mapsto1_Au_s u s ↦ 1 A u s , is an isometric ∗ * ∗ -isomorphism onto its image, and it is computable as a map C ∗ ( G ) # → ( A ⋊ α G ) # C^*(G)^{\#} \to(A \rtimes_{\alpha} G)^{\#} C ∗ ( G ) # → ( A ⋊ α G ) # .
The formula
E ( ∑ s a s u s ) : = ∑ s φ ( a s ) u s E\left(\sum_s a_su_s\right) := \sum_s \varphi(a_s)u_s E ( s ∑ a s u s ) := s ∑ φ ( a s ) u s defines a conditional expectation E : A ⋊ α G → C ∗ ( G ) E : A \rtimes_{\alpha} G \to C^*(G) E : A ⋊ α G → C ∗ ( G ) with E ∘ ι = id E \circ\iota= \operatorname{id} E ∘ ι = id , and E E E is computable as a map ( A ⋊ α G ) # → C ∗ ( G ) # (A \rtimes_{\alpha} G)^{\#} \to C^*(G)^{\#} ( A ⋊ α G ) # → C ∗ ( G ) # .
Proof. That ι \iota ι is an isometric ∗ * ∗ -isomorphism onto its image and that E E E is a conditional expectation map is probably standard fare, but we sketch a proof for the reader’s convenience. Let ( π , H , ξ ) (\pi,H,\xi) ( π , H , ξ ) be the result of applying the GNS construction to φ \varphi φ . Since φ \varphi φ is invariant, we obtain a unitary representation V V V of G G G on H H H so that V g π ( a ) V g ∗ = π ( α g ( a ) ) V_g\pi(a)V_g^*=\pi(\alpha_g(a)) V g π ( a ) V g ∗ = π ( α g ( a )) for all a ∈ A a\in A a ∈ A and such that V g ξ = ξ V_g\xi=\xi V g ξ = ξ . We then get a ∗ * ∗ -homomorphism Λ : A ⋊ α G → B ( H ) ⊗ max C ∗ ( G ) \Lambda: A\rtimes_{\alpha}G\to B(H)\otimes_{\max}C^*(G) Λ : A ⋊ α G → B ( H ) ⊗ m a x C ∗ ( G ) given by Λ ( a u g ) = π ( a ) V g ⊗ u g \Lambda(au_g)=\pi(a)V_g\otimes u_g Λ ( a u g ) = π ( a ) V g ⊗ u g . The expectation E E E is the result of composing with the ucp slice map ω ξ ⊗ id \omega_\xi\otimes\operatorname{id} ω ξ ⊗ id . Since E ∘ ι = id E\circ\iota=\operatorname{id} E ∘ ι = id , we see that ι \iota ι is isometric.
The computability of ι \iota ι is immediate. It remains to see that E E E is computable. To see this, given a generated point x = ∑ s ∈ F a s u s x=\sum_{s\in F}a_su_s x = ∑ s ∈ F a s u s of ( A ⋊ α G ) # (A\rtimes_{\alpha}G)^{\#} ( A ⋊ α G ) # with F ⊆ G F\subseteq G F ⊆ G finite, and rational ϵ > 0 \epsilon>0 ϵ > 0 , compute rationals q s q_s q s with ∣ φ ( a s ) − q s ∣ < ϵ / ∣ F ∣ |\varphi(a_s)-q_s|<\epsilon/|F| ∣ φ ( a s ) − q s ∣ < ϵ /∣ F ∣ ; then ∑ s q s u s \sum_s q_su_s ∑ s q s u s is a generated point of C ∗ ( G ) # C^*(G)^{\#} C ∗ ( G ) # with
∥ E ( x ) − ∑ s q s u s ∥ ≤ ∑ s ∈ F ∣ φ ( a s ) − q s ∣ < ϵ . \left\|E(x)-\sum_s q_su_s\right\|\leq\sum_{s\in F}|\varphi(a_s)-q_s|<\epsilon. E ( x ) − s ∑ q s u s ≤ s ∈ F ∑ ∣ φ ( a s ) − q s ∣ < ϵ .
In order to apply the previous lemma, we need to know when computable invariant states exist. In order to achieve that goal, we first mention the following recent fact of the first-named author:
Fact 5.13 ([7 ] ). Suppose that A # A^{\#} A # is a computable presentation of a nuclear C ∗ C^* C ∗ -algebra A A A . Then the state space S ( A ) S(A) S ( A ) , with the weak∗ ^* ∗ topology, admits a computably compact presentation S ( A ) # S(A)^{\#} S ( A ) # such that the evaluation map ( φ , a ) ↦ φ ( a ) (\varphi,a)\mapsto\varphi(a) ( φ , a ) ↦ φ ( a ) is computable on the induced presentation of S ( A ) × A S(A)\times A S ( A ) × A .
Lemma 5.14. Let A # A^{\#} A # be a computable presentation of a nuclear C ∗ C^* C ∗ -algebra and G # ↷ α A # G^{\#}\curvearrowright_{\alpha} A^{\#} G # ↷ α A # a computable action. Then the set S ( A ) G S(A)^G S ( A ) G of α \alpha α -invariant states is a co-c.e. closed set of S ( A ) # S(A)^{\#} S ( A ) # .
Proof. Fix g ∈ G g\in G g ∈ G , i ∈ ω i\in\omega i ∈ ω , and rational ϵ > 0 \epsilon>0 ϵ > 0 . Using computability of the action, compute (an index for) a generated point a j ( g , i , ϵ ) a_{j(g,i,\epsilon)} a j ( g , i , ϵ ) with ∥ α g ( a i ) − a j ( g , i , ϵ ) ∥ < ϵ \|\alpha_g(a_i)-a_{j(g,i,\epsilon)}\|<\epsilon ∥ α g ( a i ) − a j ( g , i , ϵ ) ∥ < ϵ . We
claim that S ( A ) G S(A)^G S ( A ) G is the set of φ ∈ S ( A ) \varphi\in S(A) φ ∈ S ( A ) satisfying
∣ φ ( a j ( g , i , ϵ ) ) − φ ( a i ) ∣ ≤ 2 ϵ for all g ∈ G , i ∈ ω , ϵ ∈ Q > 0 , (6) \left|\varphi(a_{j(g,i,\epsilon)})-\varphi(a_i)\right|\leq2\epsilon\qquad\text{for all }g\in G,\ i\in\omega,\ \epsilon\in\mathbb{Q}_{>0}, \tag*{(6)} φ ( a j ( g , i , ϵ ) ) − φ ( a i ) ≤ 2 ϵ for all g ∈ G , i ∈ ω , ϵ ∈ Q > 0 , (6)
which is a countable computable conjunction of Π 1 0 \Pi^0_1 Π 1 0 conditions on computable coordinates, hence Π 1 0 \Pi^0_1 Π 1 0 . Indeed, if φ \varphi φ is invariant then ∣ φ ( a j ) − φ ( a i ) ∣ = ∣ φ ( a j ) − φ ( α g ( a i ) ) ∣ ≤ ϵ \left|\varphi(a_j)-\varphi(a_i)\right|=\left|\varphi(a_j)-\varphi(\alpha_g(a_i))\right|\leq\epsilon ∣ φ ( a j ) − φ ( a i ) ∣ = ∣ φ ( a j ) − φ ( α g ( a i )) ∣ ≤ ϵ ; conversely if (6) holds then ∣ φ ( α g ( a i ) ) − φ ( a i ) ∣ ≤ 3 ϵ \left|\varphi(\alpha_g(a_i))-\varphi(a_i)\right|\leq3\epsilon ∣ φ ( α g ( a i )) − φ ( a i ) ∣ ≤ 3 ϵ for every ϵ \epsilon ϵ , so φ ∘ α g \varphi\circ\alpha_g φ ∘ α g and φ \varphi φ agree on generated points and hence, being bounded, on all of A A A . □
We can now present our main criterion for effective Kirchberg nuclearity of group C ∗ C^* C ∗ -algebras for amenable groups:
Theorem 5.15. Let G # G^\# G # be a computable presentation of an amenable group, let A # A^\# A # be a computable presentation of a nuclear C ∗ C^* C ∗ -algebra admitting a computable representation, and let G # ↷ α A # G^\#\curvearrowright_\alpha A^\# G # ↷ α A # be a computable action such that
A ⋊ α G A\rtimes_\alpha G A ⋊ α G is simple, and
α \alpha α admits a unique invariant state on A A A .
Then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear. Moreover the conclusion is uniform in indices for G # G^\# G # , A # A^\# A # and α \alpha α .
Proof. Since G G G is amenable, C ∗ ( G ) = C r ∗ ( G ) C^*(G)=C^*_r(G) C ∗ ( G ) = C r ∗ ( G ) and, by [11 Corollary 3.22] , C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is a computable presentation. By Proposition 5.11, ( A ⋊ α G ) # (A\rtimes_\alpha G)^\# ( A ⋊ α G ) # is a computable presentation of A ⋊ G A\rtimes G A ⋊ G . Moreover, A ⋊ α G A\rtimes_\alpha G A ⋊ α G is nuclear, being the crossed product of a nuclear algebra by an amenable group (see [3 Theorem 4.3.4] ).
By Lemma 5.14 , S ( A ) G S(A)^G S ( A ) G is a co-c.e. closed set in the computably compact space S ( A ) # S(A)^\# S ( A ) # , and it is nonempty by amenability; by hypothesis (2), it is a singleton { φ } \{\varphi\} { φ } . Therefore, φ \varphi φ is a computable point of S ( A ) # S(A)^\# S ( A ) # and is thus a computable state on A # A^\# A # . Lemma 5.12 now supplies a computable embedding ι : C ∗ ( G ) # ↪ ( A ⋊ α G ) # \iota:C^*(G)^\#\hookrightarrow(A\rtimes_\alpha G)^\# ι : C ∗ ( G ) # ↪ ( A ⋊ α G ) # together with a computable conditional expectation E : ( A ⋊ α G ) # → C ∗ ( G ) # E:(A\rtimes_\alpha G)^\#\to C^*(G)^\# E : ( A ⋊ α G ) # → C ∗ ( G ) # .
Since A ⋊ α G A\rtimes_\alpha G A ⋊ α G is simple and nuclear, Lemma 5.2 (2) gives that ( A ⋊ α G ) # (A\rtimes_\alpha G)^\# ( A ⋊ α G ) # is effectively Kirchberg nuclear. By Lemma 5.2 (1), it follows that C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear. □
We now specialize to the case of groups acting on commutative C ∗ C^* C ∗ -algebras. In order to apply the above theorem, we need to know computable presentations of commutative algebras always admit computable representations:
Lemma 5.16. Suppose X # X^\# X # is a computably compact presentation. Then the associated evaluative presentation C ( X # ) C(X^\#) C ( X # ) of C ( X ) C(X) C ( X ) admits a computable faithful state, and thus a computable faithful representation.
Proof. Suppose that ( x i ) i ∈ N (x_i)_{i\in\mathbb{N}} ( x i ) i ∈ N are the special points of X X X and set μ = ∑ i = 1 ∞ 2 − i δ x i \mu=\sum_{i=1}^{\infty}2^{-i}\delta_{x_i} μ = ∑ i = 1 ∞ 2 − i δ x i , a probability measure on X X X . Define ϕ : C ( X ) → C \phi:C(X)\to\mathbb{C} ϕ : C ( X ) → C by ϕ ( f ) : = ∫ f d μ \phi(f):=\int f\,d\mu ϕ ( f ) := ∫ f d μ . Then ϕ \phi ϕ is a faithful state (faithful as the measure is strictly positive). It is also computable since
∥ ∫ f d μ − ∑ i = 1 N 2 − i f ( x i ) ∥ ≤ 2 − N ∥ f ∥ ∞ \left\|\int f\,d\mu-\sum_{i=1}^{N}2^{-i}f(x_i)\right\|\leq2^{-N}\|f\|_\infty ∫ f d μ − i = 1 ∑ N 2 − i f ( x i ) ≤ 2 − N ∥ f ∥ ∞
and the presentation C ( X # ) C(X^\#) C ( X # ) is computable and evaluative. The fact that C ( X # ) C(X^\#) C ( X # ) admits a computable faithful representation follows from applying the GNS construction with respect to the state ϕ \phi ϕ (see [7 ] for more details). □
Recall that if G ↷ α X G \curvearrowright_\alpha X G ↷ α X is an action, then one obtains an induced action G ↷ α C ( X ) G \curvearrowright_\alpha C(X) G ↷ α C ( X ) defined by α ( g , f ) ( x ) : = f ( α ( g − 1 , x ) ) \alpha(g,f)(x):=f(\alpha(g^{-1},x)) α ( g , f ) ( x ) := f ( α ( g − 1 , x )) .
Lemma 5.17. Suppose that G # G^\# G # is a computable presentation of G G G , X # X^\# X # is a computably compact presentation of X X X , and the action G # ↷ α X # G^\# \curvearrowright_\alpha X^\# G # ↷ α X # is a computable action. Then the induced action G # ↷ α C ( X # ) G^\# \curvearrowright_\alpha C(X^\#) G # ↷ α C ( X # ) is also computable.
Proof. By Lemma 5.6 , it suffices to show that α ( g , f ) \alpha(g,f) α ( g , f ) is a computable function, uniformly in indices for g g g and f f f . However, this is immediate from computability of the action and from C ( X # ) C(X^\#) C ( X # ) being computable and evaluative. □ \square □
Corollary 5.18. Let G # G^\# G # be a computable presentation of an amenable group admitting a computable action on a computably compact presentation X # X^\# X # of a metric space X X X which is
topologically free,
minimal, and
uniquely ergodic.
Then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear.
Proof. C ( X # ) C(X^\#) C ( X # ) is a computable presentation of C ( X ) C(X) C ( X ) by [11 Theorem 4.3] , and the induced action on it is computable by Lemma 5.17 . Topological freeness together with minimality gives simplicity of C ( X ) ⋊ G C(X)\rtimes G C ( X ) ⋊ G by a result of Archbold and Spielberg [1 ] , and unique ergodicity is precisely the uniqueness of the invariant state. It remains to apply Theorem 5.15 . □ \square □
Corollary 5.19. Let G # G^\# G # be a computable presentation of an amenable group. Suppose further that there is a computable descending sequence N 0 ⊇ N 1 ⊇ ⋯ N_0 \supseteq N_1 \supseteq\cdots N 0 ⊇ N 1 ⊇ ⋯ of finite-index normal subgroups of G G G with ⋂ k N k = { 1 } \bigcap_k N_k=\{1\} ⋂ k N k = { 1 } , where computable meaning that membership in N k N_k N k is decidable uniformly in k k k as is the index [ G : N k ] [G:N_k] [ G : N k ] . Then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear.
Proof. Let X : = l i m ← k G / N k X:=\varprojlim_k G/N_k X := lim k G / N k . We first equip X X X with a computable presentation. For g ∈ G g\in G g ∈ G , write g ^ : = ( g N k ) k ∈ N ∈ X \hat{g}:=(gN_k)_{k\in\mathbb{N}}\in X g ^ := ( g N k ) k ∈ N ∈ X . The map g ↦ g ^ : G → X g\mapsto\hat{g}:G\to X g ↦ g ^ : G → X is an injective group homomorphism with dense image. Let ( w n ) n ∈ N (w_n)_{n\in\mathbb{N}} ( w n ) n ∈ N be an effective enumeration of the words in the generators of G # G^\# G # and their inverses. Define X # X^\# X # to be the presentation of ( X , d ) (X,d) ( X , d ) whose n n n -th special point is w n ^ \widehat{w_n} w n . To see that this presentation is computable, observe first that for words u , v u,v u , v and k ∈ N k\in\mathbb{N} k ∈ N , we have
u ^ k = v ^ k ⟺ u N k = v N k ⟺ u − 1 v ∈ N k . \widehat{u}_k=\widehat{v}_k\Longleftrightarrow uN_k=vN_k\Longleftrightarrow u^{-1}v\in N_k. u k = v k ⟺ u N k = v N k ⟺ u − 1 v ∈ N k .
which is decidable uniformly in ( u , v , k ) (u,v,k) ( u , v , k ) . Since the N k N_k N k are nested, the set of k k k at which u ^ \widehat{u} u and v ^ \widehat{v} v agree is an initial segment of N \mathbb{N} N . Hence the algorithm to compute the metric proceeds by first deciding whether u − 1 v = 1 u^{-1}v=1 u − 1 v = 1 in G G G . If so, output d ( u ^ , v ^ ) = 0 d(\widehat{u},\widehat{v})=0 d ( u , v ) = 0 . Otherwise, search for the least k k k with u − 1 v ∉ N k u^{-1}v\notin N_k u − 1 v ∈ / N k and output 2 − k 2^{-k} 2 − k . The second step indeed terminates whenever u − 1 v ≠ 1 u^{-1}v\ne1 u − 1 v = 1 as ⋂ k N k = { 1 } \bigcap_k N_k=\{1\} ⋂ k N k = { 1 } .
We next observe that X # X^\# X # is computably compact. To see this, fix j j j and compute a transversal t 1 , j , … , t m j , j t_{1,j},\ldots,t_{m_j,j} t 1 , j , … , t m j , j of N j N_j N j . Then the finite set { t i , j ^ : 1 ≤ i ≤ m j } \{\widehat{t_{i,j}}:1\le i\le m_j\} { t i , j : 1 ≤ i ≤ m j } of special points is easily seen to be a 2 − ( j + 1 ) 2^{-(j+1)} 2 − ( j + 1 ) -net of X X X .
We next note that G G G acts on X X X by left translation; the action is computable since membership in each N k N_k N k is decidable. The action is free since ⋂ k N k = { 1 } \bigcap_k N_k=\{1\} ⋂ k N k = { 1 } by normality and minimal since G G G acts transitively on each finite level G / N k G/N_k G / N k . As the N k N_k N k are normal, X X X is a profinite group and G G G acts by translation through a dense image, so the Haar measure of X X X is the unique invariant measure and unique ergodicity holds. The result now follows from Corollary 5.18 .
Examples 5.20. We list some examples of computable presentations of amenable groups for which the computable chain appearing in the previous theorem exists and thus the reduced group C*-algebra is effectively Kirchberg nuclear.
Suppose that G G G is a finitely presented, residually finite amenable group. One may then find such a computable chain of quotients as in the previous theorem. Indeed, the finite quotients of a finitely presented group are computably enumerable (only finitely many relators need checking), so one may search for finite quotients separating a given element from the identity and intersect the kernels found so far.
The wreath product Z 2 ≀ Z \mathbb{Z}_2 \wr\mathbb{Z} Z 2 ≀ Z is finitely generated but not finitely presented, yet the quotients Z 2 ≀ Z n k \mathbb{Z}_2 \wr\mathbb{Z}_{n_k} Z 2 ≀ Z n k furnish the chain, where ( n k ) k ∈ N (n_k)_{k \in\mathbb{N}} ( n k ) k ∈ N is any computable sequence tending to infinity and satisfying n k ∣ n k + 1 n_k \mid n_{k+1} n k ∣ n k + 1 for all k ∈ N k \in\mathbb{N} k ∈ N .
We note that there are examples of computable presentations of amenable groups for which Corollary 5.19 does not necessarily apply and yet the corresponding presentation of the group C*-algebra is effectively Kirchberg nuclear. For example, if G # G^\# G # is a computable presentation of an abelian group, then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is computable by [11 Corollary 3.22] ; since C ∗ ( G ) C^*(G) C ∗ ( G ) is abelian, C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear by Corollary 5.8 . Similarly, if G # G^\# G # is a computable presentation of a locally finite group, then C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is easily seen to be a computable presentation; since C ∗ ( G ) C^*(G) C ∗ ( G ) is AF, we obtain that C ∗ ( G ) # C^*(G)^\# C ∗ ( G ) # is effectively Kirchberg nuclear by Proposition 5.9 .
20-completeness
Set Nuc to be the set of indices of computable presentations of nuclear C*-algebras. We begin with the following:
Proposition 6.1. Nuc is Π 2 0 \Pi^0_2 Π 2 0 .
Proof. The set of indices of computable presentations of C*-algebras is itself a Π 2 0 \Pi^0_2 Π 2 0 -set (see [10 Theorem 12.1] ). Moreover, the proof of the direction (1) implies (2) in Theorem 3.5 shows that being nuclear is indeed a Π 2 0 \Pi^0_2 Π 2 0 -condition on computable presentations of C*-algebras. Indeed, letting X k X_k X k denote the set of tuples ( a ⃗ , n , b ⃗ , w ) (\vec{a}, n, \vec{b}, w) ( a , n , b , w ) satisfying the three bullet points appearing in Theorem 3.5 (where a ⃗ \vec{a} a is a k k k -tuple), we see that X k X_k X k is computable uniformly in the presentation A # A^\# A # ; the proof of Theorem 3.5 shows that the algebra is nuclear if and only if, for each k k k and each k k k -tuple a ⃗ \vec{a} a , there is a triple ( n , b ⃗ , w ) (n,\vec{b},w) ( n , b , w ) such that ( a ⃗ , n , b ⃗ , w ) ∈ X k (\vec{a},n,\vec{b},w) \in X_k ( a , n , b , w ) ∈ X k , establishing that being nuclear is Π 2 0 \Pi^0_2 Π 2 0 . Nuc is thus the intersection of Π 2 0 \Pi^0_2 Π 2 0 -sets, hence Π 2 0 \Pi^0_2 Π 2 0 .
The motivating question considered in this section is the following:
Question 6.2. Is Nuc Π 2 0 \Pi^0_2 Π 2 0 -complete within the class of indices of computable presentations of C*-algebras?
Here Π 2 0 \Pi^0_2 Π 2 0 -completeness within the class means that for every Π 2 0 \Pi^0_2 Π 2 0 set A A A , there is a computable total function f f f mapping ω \omega ω into the class of indices of computable presentations of C*-algebras such that n ∈ A ⟺ f ( n ) ∈ N u c n \in A \Longleftrightarrow f(n) \in\mathrm{Nuc} n ∈ A ⟺ f ( n ) ∈ Nuc . Contrast this with the requirement for ordinary Π 2 0 \Pi^0_2 Π 2 0 -completeness, where one would only need f : ω → ω f : \omega\to\omega f : ω → ω . Ordinary Π 2 0 \Pi^{0}_{2} Π 2 0 -completeness of Nuc (which is not difficult to prove) would imply only that being the index of a nuclear C*-algebra – as opposed to being the index of something that is maybe not even a C*-algebra at all – is Π 2 0 \Pi^{0}_{2} Π 2 0 -hard. Π 2 0 \Pi^{0}_{2} Π 2 0 -completeness within the class of indices of computable presentations of C*-algebras, if true, would mean that even as a property of C*-algebras, nuclearity is still Π 2 0 \Pi^{0}_{2} Π 2 0 -hard.
There is some precedence for a positive answer to Question 6.2 . In [10 Theorem 12.4] , it was proven that the set of indices for computable presentations of UHF algebras is Π 2 0 \Pi^{0}_{2} Π 2 0 -complete, whereas in [10 Theorems 12.2 and 12.5] , it was shown that the set of indices for computable presentations of (simple) AF-algebras is Π 2 0 \Pi^{0}_{2} Π 2 0 -complete.
In this section, we describe partial progress towards settling Question 6.2 . We begin with a detour giving a positive answer to the analogous question for groups, which we believe is of independent interest.
Amenability
First consider the set
Grp = { e ∈ ω : ϕ e computes a group on the domain ω } . \operatorname{Grp} = \{e \in\omega: \phi_e \text{ computes a group on the domain } \omega\}. Grp = { e ∈ ω : ϕ e computes a group on the domain ω } .
Here we consider ϕ e \phi_e ϕ e as a function ϕ e : ω 2 → ω \phi_e : \omega^{2} \to\omega ϕ e : ω 2 → ω and require this binary function to be total and to satisfy the group axioms.
Lemma 6.3. Grp \operatorname{Grp} Grp is a Π 2 0 \Pi^{0}_{2} Π 2 0 set.
Proof. It suffices to note that Grp \operatorname{Grp} Grp is the intersection of Tot : = { e ∈ ω : ϕ e is total } \operatorname{Tot} := \{e \in\omega: \phi_e \text{ is total}\} Tot := { e ∈ ω : ϕ e is total } with the following sets:
{ e ∈ ω : ( ∃ x ∈ ω ) ϕ e ( x , x ) = x } \{e \in\omega: (\exists x \in\omega)\phi_e(x,x)=x\} { e ∈ ω : ( ∃ x ∈ ω ) ϕ e ( x , x ) = x } .
{ e ∈ ω : ( ∀ x , y ∈ ω ) ( ( ϕ e ( x , x ) = x ∧ ϕ e ( y , y ) = y ) → x = y ) } \{e \in\omega: (\forall x,y \in\omega)((\phi_e(x,x)=x \land\phi_e(y,y)=y) \to x=y)\} { e ∈ ω : ( ∀ x , y ∈ ω ) (( ϕ e ( x , x ) = x ∧ ϕ e ( y , y ) = y ) → x = y )} .
{ e ∈ ω : ( ∀ x ∈ ω ) ( ∃ y ∈ ω ) ( ϕ e ( ϕ e ( x , y ) , ϕ e ( x , y ) ) = ϕ e ( x , y ) ∧ ϕ e ( ϕ e ( y , x ) , ϕ e ( y , x ) ) = ϕ e ( y , x ) ) } \{e \in\omega: (\forall x \in\omega)(\exists y \in\omega)(\phi_e(\phi_e(x,y),\phi_e(x,y))=\phi_e(x,y) \land\phi_e(\phi_e(y,x),\phi_e(y,x))=\phi_e(y,x))\} { e ∈ ω : ( ∀ x ∈ ω ) ( ∃ y ∈ ω ) ( ϕ e ( ϕ e ( x , y ) , ϕ e ( x , y )) = ϕ e ( x , y ) ∧ ϕ e ( ϕ e ( y , x ) , ϕ e ( y , x )) = ϕ e ( y , x ))} .
{ e ∈ ω : ( ∀ x , y , z ∈ ω ) ϕ e ( ϕ e ( x , y ) , z ) = ϕ e ( x , ϕ e ( y , z ) ) } \{e \in\omega: (\forall x,y,z \in\omega)\phi_e(\phi_e(x,y),z)=\phi_e(x,\phi_e(y,z))\} { e ∈ ω : ( ∀ x , y , z ∈ ω ) ϕ e ( ϕ e ( x , y ) , z ) = ϕ e ( x , ϕ e ( y , z ))} .
Now consider the set
Amen = { e ∈ ω : ϕ e computes an amenable group on the domain ω } . \operatorname{Amen} = \{e \in\omega: \phi_e \text{ computes an amenable group on the domain } \omega\}. Amen = { e ∈ ω : ϕ e computes an amenable group on the domain ω } .
Lemma 6.4. Amen \operatorname{Amen} Amen is a Π 2 0 \Pi^{0}_{2} Π 2 0 set.
Proof. Recall that amenability can be characterized by the following condition:
( ∀ finite F 0 ⊆ G ) ( ∀ ϵ > 0 ) ( ∃ finite F 1 ⊆ G ) ( ∀ x ∈ F 0 ) ∣ x F 1 △ F 1 ∣ ∣ F 1 ∣ < ϵ . (\forall\text{ finite }F_{0}\subseteq G)(\forall\epsilon>0)(\exists\text{ finite }F_{1}\subseteq G)(\forall x\in F_{0})\frac{\lvert xF_{1}\mathbin{\triangle}F_{1}\rvert}{\lvert F_{1}\rvert}<\epsilon. ( ∀ finite F 0 ⊆ G ) ( ∀ ϵ > 0 ) ( ∃ finite F 1 ⊆ G ) ( ∀ x ∈ F 0 ) ∣ F 1 ∣ ∣ x F 1 △ F 1 ∣ < ϵ . By standard coding tricks, this is easily seen to be a Π 2 0 \Pi^{0}_{2} Π 2 0 -condition.
We now prove the main result of this subsection.
Theorem 6.5. Amen \operatorname{Amen} Amen is a Π 2 0 \Pi^{0}_{2} Π 2 0 -complete set. Indeed, it is Π 2 0 \Pi^{0}_{2} Π 2 0 -complete within the class Grp \operatorname{Grp} Grp .
Proof of Theorem 6.5. We define a computable total function R : ω → Grp R : \omega\to\operatorname{Grp} R : ω → Grp such that
( ∀ e ) [ e ∈ Inf ⟺ R ( e ) ∈ Amen ] . (\forall e)\ [e \in\operatorname{Inf} \Longleftrightarrow R(e) \in\operatorname{Amen}]. ( ∀ e ) [ e ∈ Inf ⟺ R ( e ) ∈ Amen ] . Here Inf : = { e : W e is infinite } \operatorname{Inf} := \{e : W_e \text{ is infinite}\} Inf := { e : W e is infinite } . R R R can then be converted into an injective total computable function, by the Padding Lemma, showing the Π 2 0 \Pi^{0}_{2} Π 2 0 -complete set Inf \operatorname{Inf} Inf to
be 1-reducible to Amen and thus giving the result. Further details on all of these concepts may be found in [23 chs. I-IV] .
In what follows, a fragment of a group G G G is a substructure of G G G in the relational signature with a ternary predicate defining the group operation. (Thus, a fragment retains the group’s structure but need not be closed under the group operation.)
For a given e ∈ ω e \in\omega e ∈ ω , we define R ( e ) R(e) R ( e ) to be the index of the group operation ⋅ \cdot ⋅ on the domain ω \omega ω in the computable group F F F that we now build effectively as the increasing union of group fragments F s F_s F s at each stage s s s . Every time a new element appears in W e W_e W e , say at stage s s s , we will see this and will make F s + 1 F_{s+1} F s + 1 into a finite group. At stages when no new element appears in W e W_e W e , we will take one step towards building a copy of F G 2 FG_2 F G 2 , the free group on two generators, within F F F . If e ∉ I n f e \notin\mathbf{Inf} e ∈ / Inf , then F F F will contain a copy of F G 2 FG_2 F G 2 , built without interruption starting at the stage after the last element of W e W_e W e appeared, and hence will not be amenable (so R ( e ) ∉ A m e n R(e) \notin\mathrm{Amen} R ( e ) ∈ / Amen ). On the other hand, if e ∈ I n f e \in\mathbf{Inf} e ∈ Inf , then F F F will be a nested union of finite groups F s 1 ⊆ F s 2 ⊆ ⋯ F_{s_1} \subseteq F_{s_2} \subseteq\cdots F s 1 ⊆ F s 2 ⊆ ⋯ , and therefore amenable.
We start with F 0 F_0 F 0 containing the first three domain elements 0 , 1 , 2 0,1,2 0 , 1 , 2 from ω \omega ω . We define U 0 U_0 U 0 to be the trivial group and fix a computable presentation G 0 = U 0 × F G 2 G_0 = U_0 \times FG_2 G 0 = U 0 × F G 2 with two specific generators ( 0 , a 0 ) (0,a_0) ( 0 , a 0 ) and ( 0 , b 0 ) (0,b_0) ( 0 , b 0 ) of the F 2 F_2 F 2 factor, (The first factor may become nontrivial as the construction proceeds.) Then we create the fragmentary embedding f 0 : F 0 → G 0 f_0 : F_0 \to G_0 f 0 : F 0 → G 0 with f 0 ( 0 ) = ( 0 , λ ) f_0(0) = (0,\lambda) f 0 ( 0 ) = ( 0 , λ ) the identity in G 0 G_0 G 0 , f 0 ( 1 ) = ( 0 , a 0 ) f_0(1) = (0,a_0) f 0 ( 1 ) = ( 0 , a 0 ) , and f 0 ( 2 ) = ( 0 , b 0 ) f_0(2) = (0,b_0) f 0 ( 2 ) = ( 0 , b 0 ) . This embedding will serve as a guideline to our construction of F F F as long as W e W_e W e stays empty.
At each stage s + 1 s+1 s + 1 , we know the fragment ( F s , ⋅ ) (F_s,\cdot) ( F s , ⋅ ) and the current embedding f s f_s f s , which maps F s F_s F s into a group G s ≅ U s × F G 2 G_s \cong U_s \times FG_2 G s ≅ U s × F G 2 , where U s U_s U s is finite. If W e , s + 1 = W e , s W_{e,s+1} = W_{e,s} W e , s + 1 = W e , s , then we keep U s + 1 = U s U_{s+1} = U_s U s + 1 = U s and G s + 1 = G s G_{s+1} = G_s G s + 1 = G s , find the least element y s + 1 ∈ G s + 1 y_{s+1} \in G_{s+1} y s + 1 ∈ G s + 1 that is not yet in the (finite) image of f s f_s f s , define f s + 1 = f s ∪ ( x s + 1 , y s + 1 ) f_{s+1} = f_s \cup(x_{s+1},y_{s+1}) f s + 1 = f s ∪ ( x s + 1 , y s + 1 ) , where x s + 1 = ∣ F s ∣ x_{s+1} = |F_s| x s + 1 = ∣ F s ∣ is the least number in ω − F s \omega- F_s ω − F s , and extend ⋅ \cdot ⋅ to F s + 1 F_{s+1} F s + 1 so that this f s + 1 f_{s+1} f s + 1 remains a fragmentary embedding. Thus we have taken one more step towards building a copy of F G 2 FG_2 F G 2 within F F F .
If W e , s + 1 ≠ W e , s W_{e,s+1} \ne W_{e,s} W e , s + 1 = W e , s , we find a finite group V s + 1 V_{s+1} V s + 1 such that the finite image f s ( F s ) f_s(F_s) f s ( F s ) , when projected onto the second coordinate F 2 F_2 F 2 of G s G_s G s , can be extended to a copy of V s + 1 V_{s+1} V s + 1 via some group homomorphism g s + 1 : F 2 → V s + 1 g_{s+1} : F_2 \to V_{s+1} g s + 1 : F 2 → V s + 1 that is injective on the subdomain π 1 ( f s ( F s ) ) \pi_1(f_s(F_s)) π 1 ( f s ( F s )) . The heart of this proof is Lemma 6.6 and its corollary below, which shows that such a V s + 1 V_{s+1} V s + 1 and such a g s + 1 g_{s+1} g s + 1 exist. (Since they exist, we can find such V V V and g s + 1 g_{s+1} g s + 1 just by searching systematically: when we stumble across them, we will recognize that they suffice.) Using g s + 1 g_{s+1} g s + 1 , we extend F s F_s F s to a copy F s + 1 F_{s+1} F s + 1 of U s × V s + 1 U_s \times V_{s+1} U s × V s + 1 with an isomorphism f s + 1 : F s + 1 → U s × V s + 1 f_{s+1} : F_{s+1} \to U_s \times V_{s+1} f s + 1 : F s + 1 → U s × V s + 1 such that for each x ∈ F s x \in F_s x ∈ F s ,
f s + 1 ( x ) = ( ( π 0 ( f s ( x ) ) , g s + 1 ( π 1 ( f s ( x ) ) ) ) , i d ) ∈ ( U s × V s + 1 ) × F G 2 . f_{s+1}(x) = ((\pi_0(f_s(x)),g_{s+1}(\pi_1(f_s(x)))),\mathrm{id}) \in(U_s \times V_{s+1}) \times FG_2. f s + 1 ( x ) = (( π 0 ( f s ( x )) , g s + 1 ( π 1 ( f s ( x )))) , id ) ∈ ( U s × V s + 1 ) × F G 2 .
(Here π 0 \pi_0 π 0 and π 1 \pi_1 π 1 represent projection onto the first and second coordinates, respectively.) We define U s + 1 = U s × V s + 1 U_{s+1} = U_s \times V_{s+1} U s + 1 = U s × V s + 1 and create the new computable group G s + 1 = U s + 1 × F 2 G_{s+1} = U_{s+1} \times F_2 G s + 1 = U s + 1 × F 2 . Notice that this step does not redefine the (partial) group operation ⋅ \cdot ⋅ on F s F_s F s in any way: we are continuing to construct a computable group, with no adjustment of the portion already constructed.. This completes stage s + 1 s+1 s + 1 .
Since the notation above is dense, we summarize here the action when W e , s + 1 ≠ W e , s W_{e,s+1} \ne W_{e,s} W e , s + 1 = W e , s . First we find a finite group V s + 1 V_{s+1} V s + 1 such that the portion of F G 2 FG_2 F G 2 already used (as second coordinates) in the finite subset F s F_s F s of G s G_s G s can be consistently extended to a copy of V V V . Having found it (by blind search, with an appeal to Corollary 6.7), we extend the currently-defined finite portion F s F_s F s of U s × F G 2 U_s \times F G_2 U s × F G 2 consistently to a full copy of U s × V U_s \times V U s × V , adding fresh elements to it to make F s + 1 ≅ U s × V F_{s+1} \cong U_s \times V F s + 1 ≅ U s × V . This U s × V U_s \times V U s × V becomes the new U s + 1 U_{s+1} U s + 1 , which is finite, and the new “target group” G s + 1 G_{s+1} G s + 1 is the direct product of this U s + 1 U_{s+1} U s + 1 with an entirely new copy of F G 2 F G_2 F G 2 . The new embedding f s + 1 f_{s+1} f s + 1 maps F s + 1 F_{s+1} F s + 1 onto U s + 1 × { λ } U_{s+1} \times\{\lambda\} U s + 1 × { λ } within G s + 1 G_{s+1} G s + 1 .
Now we show that R R R is an m m m -reduction. If e ∈ Inf e \in\operatorname{Inf} e ∈ Inf , then there are infinitely many stages s 1 < s 2 < ⋯ s_1 < s_2 < \cdots s 1 < s 2 < ⋯ at which W e , s i ≠ W e , s i − 1 W_{e,s_i} \ne W_{e,s_i-1} W e , s i = W e , s i − 1 . (By convention each W e , s ⊆ { 0 , 1 , … , s } W_{e,s} \subseteq\{0,1,\ldots,s\} W e , s ⊆ { 0 , 1 , … , s } , so only finitely many elements enter W e W_e W e at any single stage.) Consequently, for each stage in this sequence, F s i ≅ F s i − 1 × V s i F_{s_i} \cong F_{s_i-1} \times V_{s_i} F s i ≅ F s i − 1 × V s i , with F s i − 1 F_{s_i-1} F s i − 1 embedding into F s i F_{s_i} F s i as the first factor. The group F F F that we construct across all ω \omega ω -many stages is thus isomorphic to the algebraic direct product V s 1 ⊕ V s 2 ⊕ ⋯ V_{s_1} \oplus V_{s_2} \oplus\cdots V s 1 ⊕ V s 2 ⊕ ⋯ . It follows that F F F is locally amenable, as every finite subset of F F F lies within some finite (hence amenable) group V s 1 ⊕ ⋯ ⊕ V s k V_{s_1} \oplus\cdots\oplus V_{s_k} V s 1 ⊕ ⋯ ⊕ V s k , and consequently F F F is amenable.
Conversely, if e ∉ Inf e \notin\operatorname{Inf} e ∈ / Inf , let t t t be minimal (possibly 0 0 0 ) such that W e , t = W e W_{e,t}=W_e W e , t = W e . Then at every stage s + 1 > t s+1>t s + 1 > t , we simply extended F s + 1 F_{s+1} F s + 1 by one more element, defining the group operation so that f s + 1 f_{s+1} f s + 1 can map the new element to the least available element of G s G_s G s and remain a partial group embedding. In the limit, f = lim s f s f=\lim_s f_s f = lim s f s will thus be a group isomorphism from F = ⋃ s F s F=\bigcup_s F_s F = ⋃ s F s onto G = G t = U t × F G 2 G=G_t=U_t \times F G_2 G = G t = U t × F G 2 . Thus F F F contains a copy of F G 2 F G_2 F G 2 and consequently cannot be amenable. This completes our proof, modulo Corollary 6.7. □
The key lemma for this theorem was proven by Iwasawa in [17 Satz 2] (in German, translated here).
Lemma 6.6 (Iwasawa [17 ] ). Let F F F be a free group on any number of generators. Then the intersection of all finite-index normal subgroups of F F F is the trivial subgroup of F F F .
Corollary 6.7. Whenever F 0 F_0 F 0 is a finite fragment of the group F G 2 F G_2 F G 2 (or indeed of any free group), there exists a finite group V V V such that the (finite, partial) atomic diagram of F 0 F_0 F 0 within F F F extends to the atomic diagram of a copy of V V V .
Proof. To prove this, we need a finite-index normal subgroup N ◃ F G 2 N \triangleleft F G_2 N ◃ F G 2 such that N ∩ ( F 0 F 0 − 1 ) = { λ } N \cap(F_0 F_0^{-1})=\{\lambda\} N ∩ ( F 0 F 0 − 1 ) = { λ } , where λ \lambda λ is the empty word in F 2 F_2 F 2 . Then G / N G/N G / N will be finite and the quotient map will send each x ≠ y x \ne y x = y in F 0 F_0 F 0 to distinct cosets (since x y − 1 ∉ N xy^{-1} \notin N x y − 1 ∈ / N ), so the atomic diagram of G / N G/N G / N will realize the Corollary.
By Lemma 6.6, for each non-identity z ∈ F 0 F 0 − 1 z \in F_0 F_0^{-1} z ∈ F 0 F 0 − 1 , there is a finite-index normal subgroup N z ◃ F G 2 N_z \triangleleft F G_2 N z ◃ F G 2 with z ∉ N z z \notin N_z z ∈ / N z . Their intersection
N = ⋂ z ∈ F 0 F 0 − 1 z ≠ λ N z N=\bigcap_{\substack{z\in F_0F_0^{-1}\\z\ne\lambda}}N_z N = z ∈ F 0 F 0 − 1 z = λ ⋂ N z
is then also normal of finite index in F G 2 F G_2 F G 2 and contains none of the proscribed elements. □
Inner amenability
Although it will not be relevant to our study of nuclear C*-algebras, we add here a strengthening of Theorem 6.5 . Set
InnAmen : = { e ∈ ω : ϕ e computes an inner amenable group on the domain ω } \operatorname{InnAmen}:=\{e\in\omega:\phi_e\text{ computes an inner amenable group on the domain }\omega\} InnAmen := { e ∈ ω : ϕ e computes an inner amenable group on the domain ω } .$
This is a superset of Amen, as all amenable groups are inner amenable.
Lemma 6.8. InnAmen \operatorname{InnAmen} InnAmen is a Π 2 0 \Pi^0_2 Π 2 0 set.
Proof. It suffices to recall that inner amenability also admits a Folner-type criteria, namely G G G is inner amenable if and only if
( ∀ finite F 0 ⊆ G ) ( ∀ ϵ > 0 ) ( ∃ finite F 1 ⊆ G ) ( ∀ x ∈ F 0 ) ∣ x F 1 x − 1 △ F 1 ∣ ∣ F 1 ∣ < ϵ . (\forall\text{ finite }F_0\subseteq G)(\forall\epsilon>0)(\exists\text{ finite }F_1\subseteq G)(\forall x\in F_0)\frac{\lvert xF_1x^{-1}\mathbin{\triangle}F_1\rvert}{\lvert F_1\rvert}<\epsilon. ( ∀ finite F 0 ⊆ G ) ( ∀ ϵ > 0 ) ( ∃ finite F 1 ⊆ G ) ( ∀ x ∈ F 0 ) ∣ F 1 ∣ ∣ x F 1 x − 1 △ F 1 ∣ < ϵ .
Theorem 6.9. InnAmen is Π 2 0 \Pi^0_2 Π 2 0 -complete within the class Grp.
Proof. The construction is quite similar to that in the proof of Theorem 6.5 . The only difference is that here, instead of trying (at stages s + 1 s+1 s + 1 where W e , s + 1 = W e , s W_{e,s+1}=W_{e,s} W e , s + 1 = W e , s ) to build a copy of the free group F 2 F_2 F 2 within our computable group G G G , we will try instead to build G G G isomorphic to the group S L 2 ( F 2 ( t ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t)}\right) SL 2 ( F 2 ( t ) ) , which is known (see [14 §2] ) not to be inner amenable. (Here F 2 \mathbb{F}_2 F 2 is the two-element field, which we extend by a transcendental element t t t and then take the algebraic closure F 2 ( t ) ‾ \overline{\mathbb{F}_2(t)} F 2 ( t ) .) Now if any stage s s s exists for which W e = W e , s W_e=W_{e,s} W e = W e , s (that is, if W e W_e W e is finite), then from stage s + 1 s+1 s + 1 on, our construction will succeed in making G G G isomorphic to S L 2 ( F 2 ( t ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t)}\right) SL 2 ( F 2 ( t ) ) . On the other hand, if W e W_e W e is infinite, the construction will produce a G G G that is a direct limit of finite subgroups of itself, hence amenable and thus inner amenable.
The construction begins with K 0 = F 2 K_0=\mathbb{F}_2 K 0 = F 2 and G 0 = S L 2 ( K 0 ) G_0=\mathrm{SL}_2(K_0) G 0 = SL 2 ( K 0 ) , with the latter viewed as a finite fragment of (a fixed computable presentation of) the matrix group S L 2 ( F 2 ( t 0 ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t_0)}\right) SL 2 ( F 2 ( t 0 ) ) , where t 0 t_0 t 0 is transcendental over F 2 \mathbb{F}_2 F 2 . We now explain the procedure at each stage s + 1 s+1 s + 1 . At such a stage, we begin with a finite subfield K s K_s K s of the algebraic closure F 2 ‾ \overline{\mathbb{F}_2} F 2 and a finite fragment G s G_s G s of the group S L 2 ( K s ( t s ) ‾ ) \mathrm{SL}_2\left(\overline{K_s(t_s)}\right) SL 2 ( K s ( t s ) ) . If W e , s + 1 = W e , s W_{e,s+1}=W_{e,s} W e , s + 1 = W e , s , then we simply extend G s + 1 G_{s+1} G s + 1 to include the next matrix in S L 2 ( F 2 ( t s ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t_s)}\right) SL 2 ( F 2 ( t s ) ) , setting t s + 1 = t s t_{s+1}=t_s t s + 1 = t s and K s + 1 K_{s+1} K s + 1 equal to the finite subfield of F 2 ‾ \overline{\mathbb{F}_2} F 2 generated by all elements of F 2 ( t s + 1 ) ‾ \overline{\mathbb{F}_2(t_{s+1})} F 2 ( t s + 1 ) that appear in the matrices now in G s + 1 G_{s+1} G s + 1 and are algebraic over F 2 \mathbb{F}_2 F 2 . Thus, if in fact W e = W e , s + 1 W_e=W_{e,s+1} W e = W e , s + 1 , then the execution of this step at all subsequent stages will keep t s + 1 t_{s+1} t s + 1 transcendental over F 2 \mathbb{F}_2 F 2 forever and build G = ⋃ n G n = S L 2 ( F 2 ( t s + 1 ) ‾ ) G=\bigcup_nG_n=\mathrm{SL}_2\left(\overline{\mathbb{F}_2(t_{s+1})}\right) G = ⋃ n G n = SL 2 ( F 2 ( t s + 1 ) ) as desired.
If W e , s + 1 ≠ W e , s W_{e,s+1}\ne W_{e,s} W e , s + 1 = W e , s , however, then we wish to increase the current fragment G s G_s G s of S L 2 ( K s ( t s ) ‾ ) \mathrm{SL}_2\left(\overline{K_s(t_s)}\right) SL 2 ( K s ( t s ) ) to a finite group. G s G_s G s uses only finitely many elements of the algebraic closure F 2 ( t s ) ‾ \overline{\mathbb{F}_2(t_s)} F 2 ( t s ) , so we can effectively convert the current t s t_s t s into a field element algebraic over F 2 \mathbb{F}_2 F 2 , in a way consistent with the current field fragment. (That is, we embed the current field fragment into the algebraic closure of F 2 \mathbb{F}_2 F 2 .) This is possible because the type of a transcendental over F 2 \mathbb{F}_2 F 2 is nonprincipal, hence cannot be generated by the finitely many atomic facts given by the current field fragment. Since the current fragment is finite, so is its image in F 2 ‾ \overline{\mathbb{F}_2} F 2 , and therefore so is our new K s + 1 K_{s+1} K s + 1 , which is the subfield generated in F 2 ‾ \overline{\mathbb{F}_2} F 2 by the current fragment and the new algebraic element t s t_s t s . Next we use this field-fragment embedding to embed the current finite group fragment G s G_s G s of S L 2 ( F 2 ( t ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t)}\right) SL 2 ( F 2 ( t ) ) into S L 2 ( K s + 1 ) \mathrm{SL}_2(K_{s+1}) SL 2 ( K s + 1 ) and then extend it to the full (finite) group S L 2 ( K s + 1 ) \mathrm{SL}_2(K_{s+1}) SL 2 ( K s + 1 ) , defining G s + 1 = S L 2 ( K s + 1 ) G_{s+1}=\mathrm{SL}_2(K_{s+1}) G s + 1 = SL 2 ( K s + 1 ) . Thus G s G_s G s , which was a fragment of S L 2 ( F 2 ( t s ) ‾ ) \mathrm{SL}_2\left(\overline{\mathbb{F}_2(t_s)}\right) SL 2 ( F 2 ( t s ) ) , has now been enlarged to an actual finite group G s + 1 G_{s+1} G s + 1 , not just a fragment. Therefore, if W e W_e W e increases infinitely often, then G G G will turn out to be the limit of the sequence G 0 → G s 1 → G s 2 → ⋯ G_0\to G_{s_1}\to G_{s_2}\to\cdots G 0 → G s 1 → G s 2 → ⋯ of finite groups, as desired, where s 1 < s 2 < ⋯ s_1 < s_2 < \cdots s 1 < s 2 < ⋯ are the stages at which W e W_e W e acquires new elements.
Since amenability implies inner amenability, Theorem Theorem 6.5 actually follows directly from the proof of Theorem Theorem 6.9. We included our proof of Theorem Theorem 6.5 on grounds that it is both simpler and purely group-theoretic, while the latter proof required substantial use of basic field theory as well.
Back to Question 6.2
Let Nuc′ ' ′ denote the set of indices of computably enumerable presentations of nuclear C∗ ^* ∗ -algebras.
Corollary 6.10. Nuc′ ' ′ is Π 2 0 \Pi^0_2 Π 2 0 -hard within the class of indices of c.e. presentations of C∗ ^* ∗ -algebras.
Proof. Let h : ω → ω h : \omega\to\omega h : ω → ω be the following computable function: given e ∈ ω e \in\omega e ∈ ω , first compute R ( e ) R(e) R ( e ) , where R : ω → Grp R : \omega\to\operatorname{Grp} R : ω → Grp is the computable injective function defined in the proof of Theorem Theorem 6.5 . Let G e G_e G e denote the group on ω \omega ω whose group operation is computed by φ R ( e ) \varphi_{R(e)} φ R ( e ) . Now let h ( e ) h(e) h ( e ) be the index for the “induced” c.e. presentation of the universal group C∗ ^* ∗ -algebra C∗ ( G e ) ^*(G_e) ∗ ( G e ) . More precisely, C∗ ( G e ) ^*(G_e) ∗ ( G e ) is the universal C∗ ^* ∗ -algebra on countably many generators subject to the relations given by the multiplication table φ R ( e ) \varphi_{R(e)} φ R ( e ) and such presentations admit canonical c.e. presentations as described in [11 Theorem 3.3] . It remains to show that, for all e ∈ ω e \in\omega e ∈ ω , we have that e ∈ Inf e \in\operatorname{Inf} e ∈ Inf just if h ( e ) ∈ Nuc ′ h(e) \in\operatorname{Nuc}' h ( e ) ∈ Nuc ′ . On the one hand, if e ∈ Inf e \in\operatorname{Inf} e ∈ Inf , then R ( e ) ∈ Amen R(e) \in\operatorname{Amen} R ( e ) ∈ Amen , whence C∗ ( G e ) ^*(G_e) ∗ ( G e ) is nuclear. Moreover, by [11 Corollary 3.22] , the presentation coded by h ( e ) h(e) h ( e ) is in fact computable, whence h ( e ) ∈ Nuc ′ h(e) \in\operatorname{Nuc}' h ( e ) ∈ Nuc ′ . On the other hand, if e ∉ Inf e \notin\operatorname{Inf} e ∈ / Inf , then G e G_e G e is not amenable, whence C∗ ( G e ) ^*(G_e) ∗ ( G e ) is not nuclear and thus h ( e ) ∉ Nuc ′ h(e) \notin\operatorname{Nuc}' h ( e ) ∈ / Nuc ′ , yet h ( e ) h(e) h ( e ) is still the index of a computable (non-nuclear) C∗ ^* ∗ -algebra. □
Question 6.11. Is Nuc′ ' ′ Π 2 0 \Pi^0_2 Π 2 0 ?
In light of Corollary Corollary 6.10 , a positive answer to this question would show that Nuc′ ' ′ is Π 2 0 \Pi^0_2 Π 2 0 -complete within the class of indices of c.e. presentations of C∗ ^* ∗ -algebras, lending some credence to a positive answer to Question Question 6.2 .
In [10 Theorem 12.1] , it was remarked that the set of indices of c.e. presentations of C∗ ^* ∗ -algebras is Π 2 0 \Pi^0_2 Π 2 0 . On the other hand, note that the proof that Nuc is Π 2 0 \Pi^0_2 Π 2 0 used computability of the presentation in an essential way via its use of the effective Arveson extension. (C. J. Eagle) Department of Mathematics and Statistics, University of Victoria, PO Box 1700 STN CSC, Victoria, British Columbia, Canada. V8W 2Y2
Email address: eaglec@uvic.ca URL: http://www.math.uvic.ca/~eaglec
(I. Goldbring) University of California, Irvine Email address: igoldbri@uci.edu URL: https://www.math.uci.edu/~isaac
(T. H. McNicholl) Iowa State University Email address: mcnichol@iastate.edu URL: https://faculty.sites.iastate.edu/mcnichol/
(R. Miller) Queens College, 65-30 Kissena Blvd, Queens, NY 11367 & CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016, U.S.A. Email address: russell.miller@qc.cuny.edu