THE UNIVERSAL THEORY OF THE HYPERFINITE II$_1$ FACTOR IS NOT COMPUTABLE

Abstract

We show that the universal theory of the hyperfinite II$_1$ factor is not computable. The proof uses the recent result that MIP*=RE. Combined with an earlier observation of the authors, this yields a proof that the Connes Embedding Problem has a negative solution that avoids the equivalences with Kirchberg’s QWEP Conjecture and Tsirelson’s Problem.

1 Introduction

In this note, $\mathcal R$ denotes the hyperfinite II $_1$ factor. The main result of this note is the following result (see Corollary 3.9):

Theorem. The universal theory of $\mathcal R$ is not computable.

In the next section, we will define this statement precisely. Roughly speaking, this says that there is no algorithm which takes as inputs a universal sentence and rational tolerance $\epsilon>0$ and produces an interval of radius less than $\epsilon $ containing the truth value of the sentence in $\mathcal R$ .

In Section 4, we offer an alternative formulation which shows that our main result is really a result about matrices and traces. Given positive integers n and d, we fix variables $x_1,\ldots ,x_n$ and enumerate all *-monomials in the variables $x_1,\ldots ,x_n$ of total degree at most d, $m_1,\ldots ,m_L$ . (Of course, $L=L(n,d)$ depends on both n and d.) We consider the map $\mu _{n,d}:\mathcal R_1^n \rightarrow D^L$ given by $\mu _{n,d}(\vec a)=(\tau (m_i(\vec a)) \ : \ i=1,\ldots ,L)$ . (Here, D is the complex unit disk.)

We let $X(n,d)$ denote the range of $\mu _{n,d}$ and $X(n,d,p)$ be the image of the unit ball of $M_p(\mathbb C)$ under $\mu _{n,d}$ . Notice that $\bigcup _{p\in \mathbb N} X(n,d,p)$ is dense in $X(n,d)$ . Thus, there is a function $F:\mathbb N^3\to \mathbb N$ such that $X(n,d,F(n,d,k))$ is $\frac {1}{k}$ -dense in $X(n,d)$ for all $n,d,k\in \mathbb N$ . The fact that the universal theory of $\mathcal R$ is not computable is equivalent to the fact that no such F is a computable function.

The proof of our main theorem appears in Section 3 and uses the recent result from [13] that shows that the complexity classes MIP* and RE are the same. As noted in [13], that result can be used to show that the Connes Embedding Problem (CEP) has a negative solution. Recall that CEP asks whether or not every II $_1$ factor embeds into an ultrapower of $\mathcal R$ . The argument presented in [13] that MIP*=RE implies the failure of CEP is complicated. First, one shows that MIP*=RE implies that Tsirelson’s Problem has a negative solution; this fact first appears in [9]. Next, one uses that the failure of Tsirelson’s Problem implies that Kirchberg’s QWEP Conjecture has a negative solution; this fact is due to Fritz and Junge et al. [8, 14]. (That Tsirelson’s Problem is actually equivalent to the QWEP conjecture is due to Ozawa [17].) Finally, one uses that the failure of the QWEP Conjecture implies the failure of CEP, which appears in [16].

The current authors showed in [10] that a positive solution to CEP implies that the universal theory of $\mathcal R$ is computable. The proof is essentially an immediate application of the Completeness Theorem for continuous first order logic [3] and the fact that the theory of II $_1$ factors has a recursively enumerable axiomatization. Thus, the main theorem here yields a proof that MIP*=RE implies that CEP has a negative solution using just basic facts from continuous logic.

In Section 5, we offer a general perspective on embedding problems and point out how our techniques give a stronger refutation of the CEP in the spirit of the Gödel Incompleteness Theorem. In particular, we prove the following result (a consequence of Corollary 5.3):

Theorem. If T is any consistent, recursively axiomatizable extension of the theory of II $_1$ factors, then there is a II $_1$ factor which satisfies T which does not embed into an ultrapower of  $\mathcal R$ .

This theorem allows us to prove that there are “many” counterexamples to CEP in a sense we now make precise. In [7], the authors proved the existence of so-called locally universal II $_1$ factors, that is, separable II $_1$ factors M such that every separable II $_1$ factor embeds into an ultrapower of M. The negative solution to CEP provided by MIP* $=$ RE thus asserts that $\mathcal R$ is not a locally universal II $_1$ factor. It is a priori possible that all II $_1$ factors fall into one of two categories: those that are embeddable into an ultrapower of $\mathcal R$ and those that are locally universal. Our previous theorem can be used to show that this is emphatically not the case (see Corollary 5.5):

Theorem. There is a sequence $M_1,M_2,\ldots $ of separable II $_1$ factors, none of which embed into an ultrapower of $\mathcal R$ , and such that, for all $i<j$ , $M_i$ does not embed into an ultrapower of  $M_j$ .

In Section 6, we present some applications of our techniques to a large class of C*-algebras. When applied to the universal UHF algebra $\mathcal {Q}$ , we obtain a Gödelian-style refutation of the MF problem, which asks whether every stably finite $\mathrm {C}^*$ -algebra embeds into an ultrapower of $\mathcal {Q}$ . On the other hand, when applied to the case of the Jiang–Su algebra $\mathcal {Z}$ , we obtain the following purely operator-algebraic consequence, which appears to be new (see Corollary 6.6):

Theorem. There is a stably projectionless $\mathrm {C}^*$ -algebra that does not embed into an ultrapower of the Jiang–Su algebra $\mathcal {Z}$ .

In the final section, we offer alternative proofs to the negative solutions of Tsirelson’s problem and Kirchberg’s QWEP conjecture from MIP*=RE, replacing the semidefinite programming argument from [9] with a simple application of the Completeness Theorem.

In order to keep this note short, we include very little background information on continuous logic (the material that is truly necessary for our proof appears in the next section) or quantum games. We refer the reader to [2] for continuous logic or [6] for an operator algebraic approach; the introduction to [13] contains an excellent guide to the necessary work on quantum games. A first version of the proof of the main theorem was given in a talk at the Canadian Operator Symposium in May 2020. We would like to thank Se-Jin Kim, Vern Paulsen, and Chris Schafhauser for pointing out the simplification possible by considering synchronous correlation sets and a special thanks to Thomas Vidick for providing the additional information regarding the role of such correlation sets in the proof in [13]. We would also like to thank Thomas Sinclair, Aaron Tikuisis, Mikael Rørdam, and Jamie Gabe for enlightening discussions around the MF and other embedding problems, and to Ward Henson for useful comments about the computability-theoretic issues under discussion.

2 A little continuous logic

For the purposes of this paper, we need to state what we mean by a computable language, theory, and structure in the continuous setting. There are some choices involved, but we make the following definitions, following [5]:

By a computable uniform continuity modulus we will mean a strictly increasing computable function $\mu \colon \mathbb {N} \rightarrow \mathbb {N}$ . We say that a function $f:(X,d) \rightarrow (X',d')$ between two metric spaces has uniform continuity modulus $\mu $ if: for all $k\geq 1$ and for all $a,b \in X$ , if $d(a,b) < 1/\mu (k)$ , then $d'(f(a),f(b)) \leq 1/k$ . We say that a function $g:\mathbb {N}^n \rightarrow \mathbb {R}$ is computable if there is an algorithm which, when given $k_1,\ldots ,k_n\in \mathbb N$ and $m\geq 1$ as inputs, returns a rational number $q\in \mathbb Q$ such that $|g(k_1,\ldots ,k_n) - q| < 1/m$ .

Recall that a language in continuous logic is a triple ${\mathcal L} = (\mathcal {S}, \mathcal {F}, \mathcal {R})$ consisting of a set of sorts, a set of function symbols, and a set of relation symbols. We say that such a language is computable if:

1. (1) there is a computable enumeration of all pairs $(S,d_S)$ , where $S \in \mathcal S$ and $d_S$ is the metric symbol for S;

2. (2) there is a computable enumeration of all tuples $(f,D,C,\mu )$ , where $f \in \mathcal F$ , D is the domain of f, C is the codomain of f, and $\mu $ is a computable continuity modulus which acts as the uniform continuity modulus for f; and

3. (3) there is a computable enumeration of all tuples $(R,D,B,\mu )$ , where $R \in \mathcal R$ , D is the domain of R, B is a positive integer representing the bound on R, and $\mu $ is a computable continuity modulus which acts as the uniform continuity modulus for R.

Notice that necessarily a computable language has only countably many symbols. We will have to address this when we consider theories like the theory of tracial von Neumann algebras which a priori have continuum many symbols. A similar consideration appears when we consider formulas in continuous logic, the issue being the number of connectives. On this front we will be explicit and say that the only connectives we will consider are compositions of rational polynomials in several variables together with the binary function . We will call this set of connectives restricted.

For a separable ${\mathcal L}$ -structure M, we call an $\mathcal S$ -indexed sequence of maps $p = (p_S : S \in \mathcal {S})$ , with $p_S:\mathbb {N} \rightarrow S(M)$ for every $S \in \mathcal S$ , a presentation of M if the range of $p_S$ is dense in $S(M)$ for all $S \in \mathcal {S}$ . If ${\mathcal L}$ is a computable language, then we say that such a presentation p is computable if for every ${\mathcal L}$ -atomic formula $\varphi (x_1,\ldots ,x_n)$ with variables $x_1,\ldots ,x_n$ from sorts $S_1,\ldots ,S_n$ , the map $\operatorname {val}_\varphi :\mathbb {N}^n \rightarrow \mathbb {R}$ given by

$$\begin{align*}\operatorname{val}_\varphi(k_1,\ldots,k_n) = \varphi^M(p_{S_1}(k_1),\ldots,p_{S_n}(k_n)) \end{align*}$$

is computable, uniformly in $\varphi $ .

We now fix a computable continuous language ${\mathcal L}$ . (In the next section, ${\mathcal L}$ will be the language of tracial von Neumann algebras, restricted to complex rational scalars.) We call an ${\mathcal L}$ -formula restricted if it only uses restricted connectives and an ${\mathcal L}$ -sentence is restricted if it is a restricted ${\mathcal L}$ -formula which has no free variables.

Given an ${\mathcal L}$ -structure M, the theory of M is the function $\operatorname {Th}(M)$ whose domain is the set of ${\mathcal L}$ -sentences and which is defined by $\operatorname {Th}(M)(\sigma ):=\sigma ^M$ . The universal theory of M, denoted $\operatorname {Th}_\forall (M)$ , is the restriction of $\operatorname {Th}(M)$ to the set of universal ${\mathcal L}$ -sentences.

Definition 2.1. Let M be an ${\mathcal L}$ -structure. We say that the (universal) theory of M is computable if there is an algorithm which takes as inputs a restricted (universal) ${\mathcal L}$ -sentence $\sigma $ and a rational number $\delta>0$ and returns rational numbers $a<b$ with $b-a<\delta $ and for which $\sigma ^M\in (a,b)$ .

One also uses the word theory in continuous logic as a synonym for a set of ${\mathcal L}$ -sentences. In this case, given an ${\mathcal L}$ -structure M, the theory of M is the set $\{\sigma \ : \ \sigma ^M=0\}$ and the universal theory of M is the intersection of the theory of M with the set of nonnegative universal ${\mathcal L}$ -sentences.

Given a set of ${\mathcal L}$ -sentences T, an ${\mathcal L}$ -structure N is a model of T if $\sigma ^N=0$ for all $\sigma \in T$ . Note that an ${\mathcal L}$ -structure N is a model of the universal theory of M if and only if N embeds into an ultrapower of M.

If T is a set of restricted ${\mathcal L}$ -sentences, then via usual Gödel coding, it makes sense to speak of T being decidable, effectively enumerable, etc. Since a theory is a set of sentences, we believe the following terminology is appropriate:

Definition 2.2. A theory T is decidable if there is an algorithm which, upon input a restricted ${\mathcal L}$ -sentence $\sigma $ , decides whether or not $\sigma $ belongs to T. Similarly, T is effectively enumerable if there is an algorithm which enumerates the restricted ${\mathcal L}$ -sentences that belong to T.

It is clear that each version of the theory of M can be recovered from the other version, whence, from the point of view of model theory, there is no harm in blurring the distinction. However, from the computability-theoretic perspective, there is a difference. Indeed, while it is clear that the decidability of the theory of M implies its computability, the converse need not be true.

Given an ${\mathcal L}$ -structure M, a nonnegative ${\mathcal L}$ -formula $\varphi (x)$ is called an almost-near formula for M if, for any $\epsilon>0$ , there is $\delta =\delta (\epsilon )>0$ so that, for any $a\in M$ , if $\varphi ^M(a)<\delta (\epsilon )$ , then there is $b\in M$ such that $\varphi ^M(b)=0$ and $d(a,b)\leq \epsilon $ . In this case, we refer to the function $\delta (\epsilon )$ as an almost-near modulus for $\varphi $ . If $\varphi $ is an almost-near formula for M, then we refer to the zeroset of $\varphi ^M$ in M, denoted $Z(\varphi ^M)$ , as the definable set corresponding to  $\varphi $ .

The utility of definable sets is that one can quantify over them in a first-order way. In order to explain explicitly how we use this fact, we note that, given an almost-near formula $\varphi (x)$ , [2, Remark 2.12] establishes the existence of a nondecreasing, continuous function $\alpha :[0,\infty )\to [0,\infty )$ with $\alpha (0)=0$ and with the property that, for any $a\in M$ , we have $d(a,Z(\varphi ^M))\leq \alpha (\varphi ^M(a))$ ; moreover, the function $\alpha $ depends only on the modulus $\delta (\epsilon )$ for $\varphi $ . As shown in the proof of [2, Proposition 9.19], it follows that

$$ \begin{align*}d(a,Z(\varphi^M))=(\inf_{x}(\alpha(\varphi(x))+d(a,x)))^M. \quad \quad (\dagger)\end{align*} $$

The import of $(\dagger )$ is that the formula on the right-hand side of $(\dagger )$ is an actual formula of continuous logic. We note that the proof appearing in [2, Remark 2.12] shows that if the almost-near modulus $\delta $ is computable (when restricted to rational $\epsilon $ ), then the corresponding $\alpha $ is also a computable function. We summarize this discussion as follows:

Proposition 2.3. There is an algorithm that takes as inputs a computable almost-near formula $\varphi (x)$ for M that has a computable modulus and a rational $\eta>0$ and returns a restricted formula $\psi (x)$ so that, for all $a\in M$ , we have $|d(a,Z(\varphi ^M))-\psi (a)^M|<\eta $ . Moreover, if $\varphi $ is quantifier-free, then $\psi $ is existential.

In connection with the previous proposition, a sentence is existential (resp. universal) if it is of the form $\inf _x \varphi (x)$ (resp. $\sup _x \varphi (x)$ ), where x is a tuple of variables and $\varphi $ is quantifier-free.

We note also that if $\varphi $ is an almost-near formula for M, then it is also an almost-near formula for any ultrapower $M^{\mathcal {U}}$ of M with the same almost-near modulus and that the formula $(\dagger )$ and the conclusion of the previous proposition also hold for $M^{\mathcal {U}}$ as well.

There is a proof system for continuous logic, first introduced in [3]. There, one defines the relation $T\vdash \sigma $ , where T is a restricted ${\mathcal L}$ -theory and $\sigma $ is a restricted ${\mathcal L}$ -sentence. A feature of this proof system is that, if T is effectively enumerable, then so is the set of $\sigma $ such that $T\vdash \sigma $ . The following version of the completeness theorem, first proven in [3], will play a large role in the sequel:

Fact 2.4. For any restricted ${\mathcal L}$ -theory T and any restricted ${\mathcal L}$ -sentence $\sigma $ , we have

Suppose, in the previous display, that $\sigma $ is a nonnegative universal sentence and that the common value is $0$ . If T is effectively enumerable and we begin to enumerate the theorems of T, then we may never see the fact that $T\vdash \sigma $ even though for all n. This motivates the following definition:

Definition 2.5. Given an ${\mathcal L}$ -structure M, we say that the universal theory of M is weakly effectively enumerable if one can effectively enumerate the sentences , where $\sigma $ is a nonnegative restricted universal sentence, ${r\in \mathbb Q^{>0}}$ , and $\sigma ^M< r$ .

For some structures (such as $\mathcal R$ ), the computability of the universal theory of the structure is equivalent to it being weakly effectively enumerable:

Proposition 2.6. Suppose that M is a separable ${\mathcal L}$ -structure that has a computable presentation. Then $\operatorname {Th}_\forall (M)$ is computable if and only if it is weakly effectively enumerable.

As mentioned in [10] (and elaborated on in [11]), $\mathcal R$ has a computable presentation. The proof of the nontrivial direction of the previous proposition follows by using the computable presentation to perform a brute force lower bound approximation to the value of any positive universal sentence.

3 Proof of the main theorem

Definition 3.1. Fix $n,m\in \mathbb N$ .

1. (1) Given a Hilbert space H, a sequence of projections $(C_a : a \leq m)$ on H such that $\sum _a C_a = 1$ is called a projection valued measure (PVM) on H. If N is a subalgebra of $B(H)$ and each $C_a\in N$ , then we say that $(C_a : a \leq m)$ is a PVM in N.

2. (2) The set $C_q(n,m)$ of quantum correlations consists of the $n^2m^2$ -tuples of the form $p(a,b|x,y)= \langle A^x_a \otimes B^y_b\xi ,\xi \rangle $ for $x,y \leq n$ and $a,b \leq m$ , where H is a finite-dimensional Hilbert space, $\xi \in H \otimes H$ is a unit vector, and for every $x, y \leq n$ , $(A^x_a: a\leq m)$ and $(B^y_b:b\leq m)$ are PVMs on H.

3. (3) We set $C_{qa}(n,m)$ to be the closure in $[0,1]^{n^2m^2}$ of $C_q(n,m)$ .

4. (4) Given an element $p\in C_{qa}(n,m)$ , we say that p is synchronous if

   $p(i,j|v,v)=0$ whenever $i\not =j$ . We let $C_{qa}^s(n,m)$ denote the set of synchronous correlation matrices.

We remind the reader that if $(C_a : a\leq m)$ is a PVM on H, then the projections are automatically pairwise orthogonal, that is, $C_aC_b=0$ for all distinct $a,b\leq m$ .

Definition 3.2. A nonlocal game $\mathfrak G$ with n questions and m answers is a probability distribution $\mu $ on $n \times n$ together with a decision function

$$\begin{align*}D:n\times n \times m \times m \rightarrow \{0,1\}. \end{align*}$$

We call the nonlocal game synchronous if $D(v,v,i,j)=0$ whenever $i\not =j$ .

Definition 3.3. For each nonlocal game $\mathfrak G$ , the entangled value of $\mathfrak G$ is the quantity

$$ \begin{align*}\operatorname{val}^*(\mathfrak G)=\sup_{p\in C_{qa}(n,m)}\sum_{v,w}\mu(v,w)\sum_{i,j}D(v,w,i,j)p(i,j|v,w).\end{align*} $$

We also define the synchronous value of $\mathfrak G$ to be the quantity

$$ \begin{align*}\operatorname{s-val}^*(\mathfrak G)=\sup_{p\in C_{qa}^s(n,m)}\sum_{v,w}\mu(v,w)\sum_{i,j}D(v,w,i,j)p(i,j|v,w).\end{align*} $$

In general, $\operatorname {s-val}^*(\mathfrak G)\leq \operatorname {val}^*(\mathfrak G)$ .

The following is the main result of [13]:

Theorem 3.4. There is an effective map $\mathcal M\mapsto \mathfrak G_{\mathcal {M}}$ from Turing machines to synchronous nonlocal games such that $:$

• • if $\mathcal M$ halts, then $\operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})=1$ ;

• • if $\mathcal M$ does not halt, then $\operatorname {val}^*(\mathfrak G_{\mathcal {M}})\leq \frac {1}{2}$ .

Remark 3.5. The fact that the games in the statement of the previous theorem are synchronous does not appear explicitly in [13] but is an artifact of their proof. Moreover, in the case that $\mathcal M$ halts, the fact that a winning strategy can be taken to be synchronous is also an artifact of the proof (see Remark 5.12 in [13]).

We let $\varphi _{n,m}(x_{v,i})$ ( $i=1,\ldots ,m$ , $v=1,\ldots ,n$ ) denote the (computable!) formula

$$ \begin{align*}\max\left(\max_{v,i}\|x_{v,i}^2-x_{v,i}\|_2,\max_{v,i}\|x_{v,i}^*-x_{v,i}\|_2,\max_v\|\sum_ix_{v,i}-1\|_2\right).\end{align*} $$

We let $X^N_{n,m}$ denote the zeroset of $\varphi _{n,m}$ in N. Note that elements of $X^N_{n,m}$ are n-tuples of PVMs in N, where each PVM in the tuple consists of m orthogonal projections.

Theorem 3.6. Each formula $\varphi _{n,m}$ is an almost-near formula for $\mathcal R$ with a computable modulus.

Proof This follows immediately from [15, Lemma 3.5] and its proof.

Given a nonlocal game $\mathfrak G$ , let $\psi _{\mathfrak {G}}(x_{v,i})$ denote the formula

$$ \begin{align*}\sum_{v,w}\mu(v,w)\sum_{i,j}D(v,w,i,j)\operatorname{\mathrm{tr}}(x_{v,i}x_{w,j}).\end{align*} $$

Theorem 3.7. For any game $\mathfrak G$ , we have

$$ \begin{align*}\operatorname{s-val}^*(\mathfrak G)=\left(\sup_{x_{v,i}\in X_{n,m}}\psi_{\mathfrak{G}}(x_{v,i})\right)^{\mathcal R}.\end{align*} $$

Proof This follows immediately from the equivalence of (1) and (4) in [15, Theorem 3.6].

Theorem 3.8. Suppose that $\operatorname {Th}_\forall (\mathcal R)$ is computable. Then for any computable game $\mathfrak G$ (meaning that the $\mu (v,w)$ are computable reals), we have that $\operatorname {s-val}^*(\mathfrak G)$ is a computable real, uniformly in the description of $\mathfrak G$ , that is, there is an algorithm that takes as input a code for the game $\frak G$ and a rational number $\delta $ and returns an interval with rational endpoints of length at most $\delta $ containing $\operatorname {s-val}^*(\frak G)$ .

Proof For simplicity, set $X:=X_{n,m}$ and $x:=(x_{v,i})$ . Set $\sigma :=\sup _{x\in X}\psi _{\mathfrak {G}}(x_{v,i})$ . Note first that, since $\psi _{\mathfrak {G}}$ is 1-Lipshitz, we have . Now given $\eta>0$ , one can effectively find an existential restricted formula $\varphi _n$ such that, for all $x\in \mathcal R^{\mathcal {U}}$ , we have $|d(x,X^{\mathcal R^{\mathcal {U}}})-\varphi _n(x)^{\mathcal R^{\mathcal {U}}}|<\eta $ . It follows that

Since the latter formula in the above display is equivalent to a universal restricted formula, the computability of the universal theory of $\mathcal R$ allows us to compute it to within $\eta $ , and thus we can compute $\sigma ^{\mathcal {R}}$ to within $2\eta $ . By the previous theorem, this is equivalent to being able to compute $\operatorname {s-val}^*(\mathfrak G)$ to within $2\eta $ .

It is clear that these considerations are uniform in the description of $\mathfrak G$ .

Corollary 3.9. $\operatorname {Th}_\forall (\mathcal R)$ is not computable.

Proof Suppose, towards a contradiction, that $\operatorname {Th}_\forall (\mathcal R)$ is computable. Given a Turing machine $\mathcal M$ , we use the effective map from Theorem 3.4 to construct the computable game $\mathfrak G_M$ . Using the previous theorem, we can compute an interval $(a,b):=(a_{\mathcal {M}},b_{\mathcal {M}})\subseteq [0,1]$ of radius smaller than $\frac {1}{4}$ such that $\operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})\in (a,b)$ . If $a>\frac {1}{2}$ , then $\operatorname {val}^*(\mathfrak G_{\mathcal {M}})\geq \operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})>\frac {1}{2}$ , whence $\operatorname {val}^*(\mathfrak G_{\mathcal {M}})=1$ and $\mathcal M$ halts. If $a\leq \frac {1}{2}$ , then $b<\frac {3}{4}$ , whence $\operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})<\frac {3}{4}$ and hence $\mathcal M$ does not halt. Since this allows us to decide the halting problem, we have reached a contradiction.

4 A reformulation in terms of noncommutative moments

In this section, we offer a reformulation of our main theorem in terms that might be more appealing to operator algebraists.

Given positive integers n and d, we fix variables $x_1,\ldots ,x_n$ and enumerate all *-monomials in the variables $x_1,\ldots ,x_n$ of total degree at most d, $m_1,\ldots ,m_L$ . (Of course, $L=L(n,d)$ depends on both n and d.) We consider the map $\mu _{n,d}:\mathcal R_1^n \rightarrow D^L$ given by $\mu _{n,d}(\vec a)=(\tau (m_i(\vec a)) \ : \ i=1,\ldots ,L)$ . (Here, D is the complex unit disk.)

We let $X(n,d)$ denote the range of $\mu _{n,d}$ and $X(n,d,p)$ be the image of the unit ball of $M_p(\mathbb C)$ under $\mu _{n,d}$ . Notice that $\bigcup _{p\in \mathbb N} X(n,d,p)$ is dense in $X(n,d)$ .

Theorem 4.1. The following statements are equivalent $:$

1. (1) The universal theory of $\mathcal R$ is computable.

2. (2) There is a computable function $F:\mathbb N^3\to \mathbb N$ such that, for every $n,d, k\in \mathbb N$ , $X(n,d,F(n,d,k))$ is $\frac {1}{k}$ -dense in $X(n,d)$ .

Proof First suppose that the universal theory of $\mathcal R$ is computable. We produce a computable function F as in (2). Fix n, d, and k, and set $\epsilon :=\frac {1}{3k}$ . Computably find $s_1,\ldots ,s_t$ , an $\epsilon $ -net in $D^L$ . For each $i=1,\ldots ,t$ , ask the universal theory of $\mathcal R$ to compute intervals $(a_i,b_i)$ with $b_i-a_i<\epsilon $ and with $\left (\inf _{\vec x}|\mu _{n,d}(\vec x)-s_i|\right )^{\mathcal {R}}\in (a_i,b_i)$ . For each $i=1,\ldots ,t$ such that $b_i<2\epsilon $ , let $p_i\in \mathbb N$ be the minimal p such that when you ask the universal theory of $\mathbb M_p(\mathbb C)$ to compute intervals of shrinking radius containing $\left (\inf _{\vec x}|\mu _{n,d}(\vec x)-s_i|\right )^{M_p(\mathbb C)}$ , there is a computation that returns an interval $(c_i,d_i)$ with $d_i<2\epsilon $ . Let p be the maximum of these $p_i$ ’s. We claim that setting $F(n,d,k):=p$ is as desired. Indeed, suppose that $s\in X(n,d)$ and take $i=1,\ldots ,t$ such that $|s-s_i|<\epsilon $ . Then $\left (\inf _{\vec x}|\mu _{n,d} (\vec x)-s_i|\right )^{\mathcal {R}}<\epsilon $ , whence $b_i<2\epsilon $ . It follows that there is an interval $(c_i,d_i)$ as above with $\left (\inf _{\vec x}|\mu _{n,d}(\vec x)-s_i|\right )^{M_p(\mathbb C)}<d_i<2\epsilon $ . Let $a\in M_p(\mathbb C)$ realize the infimum. Then $|\mu _{n,d}(\vec a)-s|<3\epsilon =\frac {1}{k}$ , as desired.

Now suppose that F is as in (2). We show that the universal theory of $\mathcal R$ is computable. Towards this end, fix a restricted universal sentence

$$\begin{align*}\sigma = \sup_{\vec x} f(\tau(m_1),\ldots,\tau(m_\ell)), \end{align*}$$

where $\vec x = x_1,\ldots ,x_n$ and $m_1,\ldots ,m_\ell $ are *-monomials in $\vec x$ of total degree at most d. Fix also rational $\epsilon>0$ . We show how to compute the value of $\sigma ^{\mathcal {R}}$ to within $\epsilon $ . Since f is a restricted connective, it has a computable modulus of continuity $\delta $ . Consequently, we can find $k\in \mathbb N$ computably so that $\frac {1}{k} \leq \delta (\epsilon )$ . Set $p = F(n,d,2k)$ . Computably construct a sequence $\vec a_1,\ldots ,\vec a_t\in (M_p(\mathbb {C})_1)^n$ that is a $\frac {1}{2k}$ cover of $(M_p(\mathbb C)_1)^n$ (with respect to the $\ell ^1$ metric corresponding to the 2-norm). Consequently, $\mu _{n,d}(\vec a_1),\ldots ,\mu _{n,d}(\vec a_t)$ is a $\frac {1}{2k}$ -cover of $X(n,d,p)$ . Set

$$\begin{align*}r:=\max_{i=1,\ldots,t}f(\tau(m_1(\vec a_i)),\ldots,\tau(m_l(\vec a_i))). \end{align*}$$

By assumption, $X(n,d,p)$ is $\frac {1}{2k}$ -dense in $X(n,d)$ . It follows that $r\leq \sigma ^{\mathcal {R}}\leq r+\epsilon $ , as desired.

Remark 4.2. Notice that the *-monomials used in the proof of Theorem 3.8 are of very low degree (at most 4—we compute the trace of products of two variables and the sup is over a definable set which uses *-polynomials of degree 2 in its definition) and so we have the stronger result that there is no computable function of the form $F(n,4,k)$ in the theorem above.

5 A general perspective on Embedding Problems

As stated above, a structure N embeds into an ultrapower of another structure M (in the same language) if and only if N is a model of the universal theory of M. All of the embedding problems in operator algebras attempt to find a small subset of the universal theory of some canonical object so that modeling that small subset suffices to conclude that one models the entire universal theory. For example, the Connes Embedding Problem asks whether or not modeling the theory of tracial von Neumann algebras (which is a subset of the universal theory of $\mathcal R$ ) is enough to know that one models the entire universal theory of $\mathcal R$ . Similarly, the MF Problem asks whether or not modeling the theory of stably finite C*-algebras (which, again, is part of the universal theory of $\mathcal Q$ ) is enough to know that one models the entire universal theory of $\mathcal Q$ .

Now that we know that the Connes Embedding Problem is false, it is natural to ask whether or not one can “reasonably” enlarge the theory of tracial von Neumann algebras in such a way that then modeling that enlarged theory does indeed imply that you model the entire universal theory of $\mathcal R$ . We show that, under one interpretation of “reasonable,” this is impossible. We first offer the following general definition:

Definition 5.1. Given a structure M in a language ${\mathcal L}$ , we call the MEP the statement that there is an effectively enumerable subset T of the full theory of M such that, for any ${\mathcal L}$ -structure N, if $N\models T$ , then N embeds into an ultrapower of M.

Note that this definition allows the possibility that the extra information being allowed need not be universal information, but rather can have arbitrary quantifier-complexity. On the other hand, the restriction that T be effectively enumerable is somewhat severe (although natural from the logical point of view).

We have the following general statement:

Theorem 5.2. If the MEP has a positive solution, then the universal theory of M is weakly effectively enumerable.

Proof Suppose that there is an effectively enumerable subset T of the theory of M such that whenever $N\models T$ , then N embeds into an ultrapower of M. It follows that, for any universal sentence $\sigma $ , we have, using the Completeness Theorem, that

The result now follows.

Recalling that weak effective enumerability is equivalent to computability for the universal theory of $\mathcal R$ , we now have the following strengthening of the fact that CEP has a negative solution:

Corollary 5.3. $\mathcal R$ EP has a negative solution.

Remark 5.4. In the case of the $\mathcal R$ EP, we can make an even stronger statement, namely that there is no effectively enumerable theory T extending the theory of II $_1$ factors with the property that every model of T embeds into an ultrapower of $\mathcal R$ . Note that we are not requiring that $\mathcal R$ itself be a model of T, but instead require that every model of T be a II $_1$ factor. Indeed, since every II $_1$ factor contains a copy of $\mathcal R$ , the proof of Theorem 5.2 goes through and we obtain this stronger statement.

Recall that a tracial von Neumann algebra $\mathcal S$ is called locally universal if every tracial von Neumann algebra embeds into an ultrapower of $\mathcal S$ . As shown in [7], there is a locally universal tracial von Neumann algebra and it is clear that they all have the same universal theory. Since the theory of tracial von Neumann algebras is recursively axiomatizable, it follows that if $\mathcal S$ is a locally universal tracial von Neumann algebra, then the $\mathcal S$ EP has a positive solution. The same remark can be made for locally universal C*-algebras.

As stated in the introduction, Corollary 5.3 allows us to provide “many” counterexamples to CEP:

Corollary 5.5. There is a sequence $M_1,M_2,\ldots $ of separable II $_1$ factors, none of which embed into an ultrapower of $\mathcal R$ , and such that, for all $i<j$ , $M_i$ does not embed into an ultrapower of $M_j$ .

Proof We construct the sequence inductively. Set $M_1$ to be any separable II $_1$ factor that does not embed into an ultrapower of $\mathcal R$ . Suppose now that $M_1,\ldots ,M_n$ have been constructed satisfying the conclusion of the Corollary. For each $i=1,\ldots ,n$ , let $\sigma _i$ be a nonnegative restricted sentence such that $\sigma _i^{\mathcal R}=0$ but $\sigma _i^{M_i}>0$ . For each $i=1,\ldots ,n$ , fix a rational number ${\delta _i\in (0,\sigma _i^{M_i})}$ . Let T be the theory of II $_1$ factors together with the single condition . It is clear that T is a recursively enumerable subset of the theory of $\mathcal R$ . Thus, by Corollary 5.3, there is a separable model $M_{n+1}$ of T such that $M_{n+1}$ does not embed into an ultrapower of $\mathcal R$ . Given $i=1,\ldots ,n$ , since $\sigma _i^{M_i}>\delta _i$ while $\sigma _i^{M_{n+1}}\leq \delta _i$ , it follows that $M_i$ does not embed into an ultrapower of $M_{n+1}$ . This indicates how to continue the recursive construction, completing the proof.

6 An application to C*-algebras

Recall that the MF problem, first posed by Blackadar and Kirchberg, asks whether or not every stably finite $\mathrm {C}^*$ -algebra embeds into an ultrapower of the universal UHF algebra $\mathcal Q$ . The following consequence of the failure of CEP was pointed out to us by Thomas Sinclair and Aaron Tikuisis:

Proposition 6.1. The MF problem has a negative solution.

Proof Suppose that M is a II $_1$ factor that does not embed into $\mathcal R^{\mathcal {U}}$ (here we mean the tracial ultrapower). We claim then that M does not embed (as a C*-algebra) into a nonprincipal C*-ultrapower of $\mathcal Q$ . Indeed, suppose, towards a contradiction, that $i:M\hookrightarrow \mathcal Q^{\mathcal {U}}$ is such an embedding. Let ${\pi :\mathcal Q^{\mathcal {U}} \to \mathcal R^{\mathcal {U}}}$ denote the composition of the quotient map $\mathcal Q^{\mathcal {U}}\to \mathcal Q^{\mathcal {U}}/I$ , where I is the trace ideal, with the natural inclusion $\mathcal Q^{\mathcal {U}}/I\hookrightarrow \mathcal R^{\mathcal {U}}$ . Since M has a unique trace, which is faithful, we get that the composition $\pi \circ i:M\to \mathcal R^{\mathcal U}$ is an embedding and a *-homomorphism, yielding a contradiction.

Remark 6.2. The counterexample to the MF problem in the proof above is not separable. One can easily obtain a separable counterexample, e.g., by taking a separable elementary substructure in the language of $\mathrm {C}^*$ -algebras.

In this section, we improve upon this result by showing that the $\mathcal Q$ EP has a negative solution. This result will follow from a more general result applying to a wider class of C*-algebras.

Definition 6.3. Given $m\in \mathbb N$ and $0<\gamma <1$ , we say that a unital $\mathrm {C}^*$ -algebra A has the $(m,\gamma )$ -uniform Dixmier property if, for all self-adjoint $a\in A$ , there are unitaries $u_1,\ldots ,u_m\in U(A)$ and $z\in Z(A)$ such that

$$ \begin{align*}\left\|\sum_{i=1}^m \frac{1}{m}u_iau_i^*-z\right\|\leq \gamma\|a\|.\end{align*} $$

We say that A has the uniform Dixmier property if it has the $(m,\gamma )$ -Dixmier property for some m and $\gamma $ .

Clearly if A has the $(m,\gamma )$ -Dixmier property, then it has the $(m,\gamma ')$ -Dixmier property for any $0<\gamma <\gamma '<1$ , whence we may always assume that $\gamma $ is dyadic rational.

Given m and $\gamma $ , let $\theta _{m,\gamma }$ denote the following sentence in the language of $\mathrm {C}^*$ -algebras:

Here, the supremum is over self-adjoint contractions, the first infimum is over contractions, and the second infimum is over the unit disk in $\mathbb C$ . If A is a simple unital $\mathrm {C}^*$ -algebra with the $(m,\gamma )$ -uniform Dixmier property, then $\theta _{m,\gamma }^A=0$ . Conversely, if $\theta _{\gamma ,m}^B=0$ and B admits a trace, then this trace on B is unique (see [1, Proposition 1.4 and Theorem 3.2]).

Given a tracial C*-algebra $(A,\tau _A)$ , one lets $N_{(A,\tau _A)}$ denote the weak closure of A in the GNS representation corresponding to $\tau _A$ . It is known that $N_{(A,\tau _A)}$ is isomorphic to the algebra obtained from taking the $\|\cdot \|_{2,\tau _A}$ -completion of each bounded ball of A.

We are now ready to prove our main theorem of this section:

Theorem 6.4. Suppose that $(A,\tau _A)$ is an infinite-dimensional, unital, simple tracial C*-algebra with the uniform Dixmier property such that $N_{(A,\tau _A)}$ embeds into an ultrapower of $\mathcal R$ . Then the AEP has a negative solution.

Proof Suppose, towards a contradiction, that the AEP has a positive solution as witnessed by the theory $T_0$ . Fix m and $\gamma $ with $\gamma $ a dyadic rational such that A has the $(m,\gamma )$ -uniform Dixmier property. Let ${\mathcal L}$ be the language of tracial $\mathrm {C}^*$ -algebras and let T be the union of the following three ${\mathcal L}$ -theories:

• • $T_0$ ;

• • the ${\mathcal L}$ -theory of tracial $\mathrm {C}^*$ -algebras;

• • the single condition $\theta _{m,\gamma }=0$ .

Note that T is recursively axiomatizable. Clearly $(A,\tau _A)\models T$ . Now suppose that $(M,\tau _M)\models T$ . Since $M\models T_0$ , there is an embedding $M\hookrightarrow A^{\mathcal {U}}$ . Since $ \theta _{m,\gamma }^M=0$ , $\tau _M$ is the unique trace on M, whence this embedding is trace preserving, that is, we have an embedding $(M,\tau _M)\hookrightarrow (A,\tau _A)^{\mathcal {U}}$ . Consequently, for any universal ${\mathcal L}$ -sentence $\sigma $ , we have that

where the second equality follows from the Completeness Theorem. Thus, by running proofs from T, we obtain approximations from above to the value of $\sigma ^{(A,\tau _A)}$ . If $\sigma $ is a sentence in the language of tracial von Neumann algebras, then $\sigma $ can be construed in the language of tracial $\mathrm {C}^*$ -algebras. In this case, set $N:=N_{(A,\tau _A)}$ . Since A has a unique trace, N is a II $_1$ factor; call its trace $\tau _N$ . Note that since A is simple, $\tau _A$ is faithful and so A embeds into N. It follows that we have $\sigma ^{(A,\tau _A)}=\sigma ^{(N,\tau _N)}$ . Since N is a II $_1$ factor that embeds into an ultrapower of $\mathcal R$ , we have that $\sigma ^{(N,\tau _N)}=\sigma ^{(\mathcal R,\tau _{\mathcal {R}})}$ . We thus have that the universal theory of $\mathcal R$ is weakly effectively enumerable, which is a contradiction.

We remind the reader of a theorem of Haagerup and Zsidó [12], namely that a simple unital $\mathrm {C}^*$ -algebra has the Dixmier property if and only if it is monotracial. In particular, $\mathcal Q$ and $\mathcal Z$ have the Dixmier property. Relevant for our discussion is the following:

Fact 6.5. $\mathcal Q$ and $\mathcal Z$ have the uniform Dixmier property.

Proof [1, Corollary 3.11] states that all unital AF $\mathrm {C}^*$ -algebras with the Dixmier property have the uniform Dixmier property, whence $\mathcal Q$ has the uniform Dixmier property. [1, Remark 3.18 and Corollary 3.22] show that $\mathcal Z$ has the uniform Dixmier property.

Corollary 6.6. The $\mathcal Q$ EP and $\mathcal Z$ EP have negative solutions.

Remark 6.7. A specific consequence of the previous corollary is that there is a unital, stably projectionless C*-algebra that does not embed into $\mathcal Z^{\mathcal {U}}$ . Here, a C*-algebra A is said to be stably projectionless if, for every n, the only projections in $M_n(A)$ are, up to Murray–von Neumann equivalence, 0 or of the form $p \otimes 1$ , where p is a projection in $M_n(\mathbb {C})$ . (Note that this is indeed expressible by a set of $\forall \exists $ axioms true of $\mathcal Z$ .) It would be interesting to see if one could derive this conclusion from the failure of CEP alone using purely operator algebra techniques.

7 Tsirelson’s problem and Kirchberg’s QWEP Conjecture revisited

As discussed in the introduction, the result MIP*=RE implies a negative solution to Tsirelson’s problem. This conclusion is achieved by applying a semidefinite programming argument coupled with a noncommutative Positivstellensatz result. In this section, we show how to replace this latter argument with a simple argument using the Completeness Theorem and a result from [18], whose proof is essentially just an application of the Cauchy–Schwarz inequality.

We first remind the reader of the definitions relevant to state Tsirelson’s problem.

Definition 7.1. The set $C_{qc}(n,m)$ of quantum commuting correlations consists of the correlations of the form $p(a,b|x,y)= \langle A^x_a B^y_b\xi ,\xi \rangle $ for ${x,y \leq n}$ and $a,b \leq m$ , where H is a separable Hilbert space, $\xi \in H$ is a unit vector, and for every $x, y \leq n$ , $(A^x_a: a\leq m)$ and $(B^y_b:b\leq m)$ are PVMs on H for which $A^x_a B^y_b=B^y_bA^x_a$ . As before, if $p(a,b|x,x)=0$ whenever $a\not =b$ , we call the quantum correlation synchronous and we let $C_{qc}^s(n,m)$ denote the set of synchronous quantum commuting correlations. If $\mathfrak G$ is a nonlocal game, we set

$$ \begin{align*}\operatorname{s-val}^{co}(\mathfrak G)=\sup_{p\in C_{qc}^s(n,m)}\sum_{v,w}\mu(v,w)\sum_{i,j}D(v,w,i,j)p(i,j|v,w).\end{align*} $$

Tsirelson’s problem asks whether or not $C_{qa}(n,m)=C_{qc}(n,m)$ for all n and m. Our derivation of a negative solution to Tsirelson’s problem from MIP*=RE also establishes a complexity-theoretic fact, which we now state. (To be fair, this result is also derivable from the aforementioned semidefinite programming/Positivstellensatz argument.)

Definition 7.2. Fix $0<r\leq 1$ . We define $\operatorname {MIP}^{co,s}_{0,r}$ to be the set of those languages ${\mathcal L}$ (in the sense of complexity theory) for which there is an efficient mapping $z\mapsto \mathfrak G_z$ from strings to nonlocal games such that $z\in L$ if and only if $\operatorname {s-val}^{co}(\mathfrak G_z)\geq r$ .

The terminology $\operatorname {MIP}^{co}_0$ already exists in the literature and denotes the set of languages for which there exists an efficient mapping $z\mapsto \mathfrak G_z$ as above such that $z\in L$ if and only if $\operatorname {val}^{co}(\mathfrak G_z)=1$ , where $\operatorname {val}^{co}$ of a game is defined as $\operatorname {s-val}^{co}$ except one takes the supremum over $C_{qc}(n,m)$ instead of just over $C_{qc}^s(n,m)$ . Our aim is to prove the following:

Theorem 7.3. For any $0<r\leq 1$ , every language in $\operatorname {MIP}^{co,s}_{0,r}$ belongs to the complexity class coRE.

In other words, if $L\in \operatorname {MIP}^{co,s}_{0,r}$ , then there is an algorithm which enumerates the complement of ${\mathcal L}$ .

The following is [18, Corollary 5.6].

Fact 7.4. The correlation $p(i,j|v,w)$ belongs to $C_{qc}^s(n,k)$ if and only if there is a C*-algebra A, a tracial state $\tau $ on A, and a generating family of projections $p_{v,i}$ such that $\sum _{i=1}^k p_{v,i}=1$ for each $v=1,\ldots ,n$ and such that $p(i,j|v,w)=\tau (p_{v,i}p_{w,j})$ .

Recall the formula $\psi _{\mathfrak {G}}(x_{v,i})$ from Section 3. Let $\theta _{\mathfrak G,r}$ be the sentence

Let T be the theory of tracial C*-algebras as in the previous section. The following is immediate from Fact 7.4:

Proposition 7.5. For any nonlocal game $\mathfrak G$ , we have $\operatorname {s-val}^{co}(\mathfrak G)\geq r$ if and only if the theory $T\cup \{\theta _{\mathfrak G,r}=0\}$ is satisfiable.

We will also need the following immediate consequence of the Completeness Theorem. In the displayed expression, the symbol “ $1$ ” refers to the ${\mathcal L}$ -sentence $1$ , while the symbol “ $\frac {1}{2}$ ” refers to the “truth value” $\frac {1}{2}$ .

Lemma 7.6. Let U be a continuous theory. Then U is satisfiable if and only if

We can now prove Theorem 7.3. Let ${\mathcal L}$ belong to $\operatorname {MIP}^{co,s}_{0,r}$ . Given a string z, let $\mathfrak G_z$ be the corresponding game. By Proposition 7.5 and Lemma 7.6, $z\notin L$ if and only if ; since this latter condition is recursively enumerable, the proof of Theorem 7.3 is complete.

One can now deduce the failure of Tsirelson’s problem from MIP*=RE as follows. Suppose, towards a contradiction, that $C_{qa}^s(n,m)=C_{qc}^s(n,m)$ for every n and m. Let $\mathcal M\mapsto \mathfrak G_{\mathcal {M}}$ be the efficient mapping from Turing machines to nonlocal games described in Theorem 3.4. Given a Turing machine $\mathcal M$ , one simultaneously starts computing lower bounds on $\operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})$ while running proofs from $T\cup \{\theta _{\mathfrak G_{\mathcal M,1}}=0\}$ . Either the first computation eventually yields the fact that $\operatorname {s-val}^*(\mathfrak G_{\mathcal M})>\frac {1}{2}$ , in which case $\mathcal M$ halts, or else the second computation eventually yields the fact that , in which case $\operatorname {s-val}^*(\mathfrak G_{\mathcal {M}})<1$ , and $\mathcal M$ does not halt. In this way, we can decide the halting problem, a contradiction. Note that we derived the a priori stronger statement that $C_{qa}^s(n,m)\not =C_{qc}^s(n,m)$ for some n and m.

Although somewhat implicit in [15], we can now quickly derive a negative solution to Kirchberg’s QWEP conjecture. Indeed, based on the previous paragraph, it suffices to show that if the QWEP conjecture had a positive solution, then $C_{qa}^s(n,m)=C_{qc}^s(n,m)$ for all n and m. Towards this end, fix $p\in C_{qc}^s(n,m)$ and take a tracial C*-algebra $(A,\tau )$ generated by projections $p_{v,i}$ as in Fact 7.4. Recall from [15] that $C^*(\mathbb F(n,m))$ is the universal C*-algebra generated by projections as in Fact 7.4. Letting $e_{v,i}$ denote the corresponding projections in $C^*(\mathbb F(n,m))$ , we fix a surjective *-homomorphism $\pi :C^*(\mathbb F(n,m))\to A$ sending $e_{v,i}$ to $p_{v,i}$ . Let $\tau '$ be the trace on $C^*(\mathbb F(n,m))$ defined by $\tau '(a):=\tau (\pi (a))$ . Since $C^*(\mathbb F(n,m))$ has the local lifting property, if the QWEP conjecture were true, it would also have the weak expectation property, whence $\tau '$ would be an amenable trace. (See [4] for all the of the terms and facts described in the previous sentence.) By the equivalence of (1) and (3) in [15, Theorem 3.6], it follows that $p\in C_{qa}^s(n,m)$ , as desired.