# Mixed Leader-Follower Dynamics

Hsin-Lun Li<EMAIL_ADDRESS>
###### Abstract.

Leader-Follower (LF) dynamics originated from Hegselmann-Krause (HK) dynamics.
The original HK model consists of a finite number of agents whose opinion is a
number in $[0,1]$. Agent $i$ updates its opinion $x_{i}$ by taking the average
opinion of its neighbors, the agents whose opinion is at most $\epsilon$ apart
from $x_{i}$ for $\epsilon>0$ a confidence threshold. The LF model involves
two types of groups–the leader group and the follower group. All leader groups
have their target opinion. The original LF model partitions all agents whose
opinion is a number in $[-1,1]$ to a follower group, a leader group with a
positive target opinion in $[0,1]$ and a leader group with a negative target
opinion in $[-1,0]$. A leader group agent has a constant degree to its target
and mix it with the average opinion of its group neighbors at each update. A
follower has a constant degree to the average opinion of each leader group
neighbors and mix it with the average opinion of its group neighbors at each
update. In this paper, we consider a variant of the LF model, namely the mixed
model, in which the degrees can vary over time, the opinions can be high
dimensional, and the number of leader groups can be more than two. The LF
model can be applied to e-commerce and the mixed model covers it when there is
only one confidence threshold. We study the mixed model theoretically and
investigate circumstances under which all agents achieve a consensus.

###### Key words and phrases:

Hegselmann-Krause dynamics, mixed Leader-Follower dynamics, consensus

###### 1991 Mathematics Subject Classification:

91D25, 91D30

Hsin-Lun Li

School of Mathematical and Statistical Sciences,

Arizona State University, Tempe, AZ 85287, USA

##  1\. introduction

Leader-Follower (LF) dynamics originated from Hegselmann-Krause (HK) dynamics.
The original Hegselmann-Krause model consists of a finite number of agents
whose opinion is a number in $[0,1]$. Agent $i$ updates its opinion $x_{i}$
via taking the average opinion of its neighbors, the agents whose opinion is
at most $\epsilon$ apart from $x_{i}$ for $\epsilon>0$ a confidence threshold.
The authors in [3] proposed a leader-follower model that partitions agents
whose opinion is in $[-1,1]$ to a follower group, a leader group with a
positive target opinion in $[0,1]$ and a leader group with a negative target
opinion in $[-1,0]$. Define $[n]=\\{1,2,\ldots,n\\}$. Say $N$ agents including
$N_{1}$ followers, $N_{2}$ positive target agents and $N_{3}$ negative target
agents, set as $[N_{1}]$, $[N_{1}+N_{2}]-[N_{1}]$ and $[N]-[N_{1}+N_{2}]$. The
mechanism is as follows:

$\begin{array}[]{l}\displaystyle
x_{i}(t+1)=\frac{1-\alpha_{i}-\beta_{i}}{|N_{i}^{F}(t)|}\sum_{j\in
N_{i}^{F}(t)}x_{j}(t)+\frac{\alpha_{i}}{|N_{i}^{P}(t)|}\sum_{j\in
N_{i}^{P}(t)}x_{j}(t)\vspace{2pt}\\\ \displaystyle\hskip
55.0pt+\frac{\beta_{i}}{|N_{i}^{N}(t)|}\sum_{j\in N_{i}^{N}(t)}x_{j}(t),\quad
i=1,\ldots,N_{1},\vspace{2pt}\\\ \displaystyle
x_{i}(t+1)=\frac{(1-w_{i})}{|N_{i}^{P}(t)|}\sum_{j\in
N_{i}^{P}(t)}x_{j}(t)+w_{i}d,\quad
i=N_{1}+1,\ldots,N_{1}+N_{2},\vspace{2pt}\\\ \displaystyle
x_{i}(t+1)=\frac{1-z_{i}}{|N_{i}^{N}(t)|}\sum_{j\in
N_{i}^{N}(t)}(t)x_{j}(t)+z_{i}g,\quad
i=N_{1}+N_{2}+1,\ldots,N,\par\end{array}$

where

$\begin{array}[]{rcl}\displaystyle x_{i}(t)&=&\hbox{opinion of agent $i$ at
time $t$},\vspace{2pt}\\\ \displaystyle d&\in&[0,1]\ \hbox{is the positive
target opinion},\vspace{2pt}\\\ \displaystyle g&\in&[-1,0]\ \hbox{is the
negative target opinion},\vspace{2pt}\\\
\displaystyle\epsilon_{i}&=&\hbox{confidence threshold of agent
}i,\vspace{2pt}\\\ \displaystyle
N_{i}^{F}(t)&=&\\{j\in[N_{1}]:\|x_{i}(t)-x_{j}(t)\|\leq\epsilon_{i}\\},\vspace{2pt}\\\
N_{i}^{P}(t)&=&\\{j\in[N_{1}+N_{2}]-[N_{1}]:\|x_{i}(t)-x_{j}(t)\|\leq\epsilon_{i}\\},\vspace{2pt}\\\
\displaystyle
N_{i}^{N}(t)&=&\\{j\in[N]-[N_{1}+N_{2}]:\|x_{i}(t)-x_{j}(t)\|\leq\epsilon_{i}\\},\vspace{2pt}\\\
\displaystyle\alpha_{i}&=&\hbox{degree to the average opinion of agent $i$'s
positive target neighbors},\vspace{2pt}\\\
\displaystyle\beta_{i}&=&\hbox{degree to the average opinion of agent $i$'s
negative target neighbors},\vspace{2pt}\\\ w_{i}&=&\hbox{degree to the
positive target of agent }i,\vspace{2pt}\\\ \displaystyle z_{i}&=&\hbox{degree
to the negative target of agent }i,\vspace{2pt}\\\ \alpha_{i},&\beta_{i},&\
w_{i},\quad z_{i}\in[0,1].\end{array}$

The authors in [2] pointed out that it can be an application in e-commerce. In
this paper, we consider a variant of the leader-follower model, namely the
mixed model. The differences are:

  * •

opinions can be high dimensional,

  * •

the number of leader groups can be more than two,

  * •

the degree of a leader group agent to its group target and the degree of a
follower group agent to the average opinion of each of its leader group
neighbors can vary over time,

  * •

only one confidence threshold, $\epsilon$.

In the leader group, each agent can choose its degree to the target opinion
and mix its opinion with the average opinion of its group neighbors at each
update. In the follower group, each agent can choose its degree to the average
opinion of its neighbors in each leader group and mix its opinion with the
average opinion of its group neighbors at each update. In a nutshell, leader
group members only can interact in its group, whereas follower group members
can interact out of its group. Considering a finite set of agents partitioned
to a follower group, $F$, and $m$ leader groups, $L_{1},\ldots,L_{m}$, the
mixed model is as follows:

$\begin{array}[]{l}\displaystyle
x_{i}(t+1)=\frac{\alpha_{i}^{k}(t)}{|N_{i}^{L_{k}}(t)|}\sum_{j\in
N_{i}^{L_{k}}(t)}x_{j}(t)+(1-\alpha_{i}^{k}(t))g_{k},\quad i\in
L_{k},\vspace{2pt}\\\ \displaystyle
x_{i}(t+1)=\frac{\big{(}1-\sum_{k=1}^{m}\beta_{i}^{k}(t)\big{)}}{|N_{i}^{F}|}\sum_{k\in
N_{i}^{F}}x_{k}+\sum_{k=1}^{m}\frac{\beta_{i}^{k}(t)}{|N_{i}^{L_{k}}|}\sum_{k\in
N_{i}^{L_{k}}}x_{k},\quad i\in F,\end{array}$

where

$\begin{array}[]{rcl}\displaystyle\alpha_{i}^{k}(t)&\in&[0,1]\hbox{ is the
degree to the average opinion of agent $i$'s group neighbors},\vspace{2pt}\\\
\displaystyle g_{k}&\in&\mathbf{R^{d}}\hbox{ is the target opinion of leader
group }k,\vspace{2pt}\\\ N_{i}^{F}(t)&=&\\{j\in
F:\|x_{j}(t)-x_{i}(t)\|\leq\epsilon\\},\vspace{2pt}\\\
N_{i}^{L_{k}}(t)&=&\\{j\in
L_{k}:\|x_{j}(t)-x_{i}(t)\|\leq\epsilon\\},\vspace{2pt}\\\
\beta_{i}^{k}(t)&=&\hbox{degree to the average opinion of agent $i$'s
neighbors in leader group $k$,}\vspace{2pt}\\\ \beta_{i}^{k}(t)&\in&[0,1]\
\hbox{and equals}\ 0\ \hbox{if}\ N_{i}^{L_{k}}(t)=\emptyset.\end{array}$

Observe that the system of leader group $k$ becomes a HK model if
$\alpha_{i}^{k}(t)=0$ for all $i\in L_{k}$, and the follower group system
becomes a HK model if $\beta_{i}^{k}(t)=0$ for all $i\in F$ and $k\in[m]$. The
differences between HK dynamics and LF dynamics are:

  * •

HK dynamics has only one group and one interaction rule, whereas LF dynamics
has two types of groups–the leader group and the follower group– in which each
has its interaction rule,

  * •

the update of an agent in HK dynamics only depends on its neighbors, whereas
the update of an agent in LF dynamics may also depend on a target.

##  2\. The model

We first investigate the behavior of a leader group. Let $L$ be a leader group
and $g$ be its target. It turns out that the maximum distance between its
opinions and target, $\max_{i\in L}\|x_{i}(t)-g\|$, is nonincreasing over
time.

######  Lemma 1.

We have

$\|x_{i}(t+1)-g\|\leq\alpha_{i}(t)\max_{j\in N_{i}(t)}\|x_{j}(t)-g\|\
\hbox{for all }i\in L.$

In particular,

$\max_{i\in L}\|x_{i}(t+1)-g\|\leq\max_{i\in L}\alpha_{i}(t)\max_{i\in
L}\|x_{i}(t)-g\|.$

###### Proof.

Observe that

$\|x_{i}(t+1)-g\|=\frac{\alpha_{i}(t)}{|N_{i}(t)|}\|\sum_{j\in
N_{i}(t)}[x_{j}(t)-g]\|\leq\alpha_{i}(t)\max_{j\in N_{i}(t)}\|x_{j}(t)-g\|.$

Therefore,

$\max_{i\in L}\|x_{i}(t+1)-g\|\leq\max_{i\in L}\alpha_{i}(t)\max_{i\in
L}\|x_{i}(t)-g\|.$

∎

The next theorem shows circumstances under which all agents in a leader group
achieve their target. It turns out that the degree to their target,
$1-\alpha_{i}(t)$, can be very small to achieve their target for all agents in
$L$.

######  Theorem 2.

Assume that $\limsup_{t\to\infty}\max_{i\in L}\alpha_{i}(t)<1$. Then,

$\lim_{t\to\infty}\max_{i\in L}\|x_{i}(t)-g\|=0.$

In particular, $\lim_{t\to\infty}\|x_{i}(t)-g\|=0$ if
$\lim_{t\to\infty}\alpha_{i}(t)=0$ for some $i\in L$.

###### Proof of Theorem 2 .

Since $\limsup_{t\to\infty}\max_{i\in L}\alpha_{i}(t)<1$, there is
$(t_{k})_{k\geq 0}\subset\mathbf{N}$ strictly increasing such that $\max_{i\in
L}\alpha_{i}(t_{k})\leq\delta<1$ for some $\delta$. For all $t\geq 1$,
$t_{s}<t\leq t_{s+1}$ for some $s\in\mathbf{N}$. Via Lemma 1,

$\displaystyle\max_{i\in L}\|x_{i}(t)-g\|$ $\displaystyle\leq\max_{i\in
L}\alpha_{i}(t-1)\ldots\max_{i\in L}\alpha_{i}(t_{0})\max_{i\in
L}\|x_{i}(t_{0})-g\|$ $\displaystyle\leq\delta^{s+1}\max_{i\in
L}\|x_{i}(t_{0})-g\|.$

As $t\to\infty$, $s\to\infty$. Therefore,

$\limsup_{t\to\infty}\max_{i\in L}\|x_{i}(t)-g\|\leq 0.$

Hence,

$\lim_{t\to\infty}\max_{i\in L}\|x_{i}(t)-g\|=0.$

Also, due to Lemma 1 and $\max_{j\in L}\|x_{j}(t)-g\|$ bounded over time,

$\limsup_{t\to\infty}\|x_{i}(t+1)-g\|\leq 0\ \hbox{therefore
}\lim_{t\to\infty}\|x_{i}(t)-g\|=0.$

∎

In other words, all leader group agents achieve their target as long as the
minimum degree to their target has a lower bound larger than 0 for infinitely
many times. Now, considering a LF system consisting of a follower group F and
a leader group L, let $B(c,r)$ be a ball centered at $c$ of radius $r$.

######  Definition 3.

The convex hull generated by $v_{1},\ldots,v_{n}$,
$C(\\{v_{1},\ldots,v_{n}\\})$, is the smallest convex set containing
$v_{1},\ldots,v_{n}$, i.e.,

$C(\\{v_{1},\ldots,v_{n}\\})=\\{\sum_{i=1}^{n}a_{i}v_{i}:(a_{i})_{i=1}^{n}\
\hbox{is stochastic}\\}.$

Observe that $x_{i}(t+1)\in C(\\{x_{k}(t)\\}_{k\in L\cup F}\cup\\{g\\})$ for
all $i\in L\cup F$; therefore we have the following lemma.

######  Lemma 4.

For all $\delta\geq 0$, if

$\big{\\{}x_{k}(t)\big{\\}}_{k\in L\cup F}\subset B(g,\delta),\ \hbox{then}\
\big{\\{}x_{k}(t+1)\big{\\}}_{k\in L\cup F}\subset B(g,\delta).$

Next, we investigate circumstances under which all agents achieve a consensus.
It turns out that a consensus can be achieved as long as their opinion lies in
$B(g,\delta)$ for some $\delta<\epsilon$ at some time, and the minimum degree
of all leader group agents to their goal and the minimum degree of all
followers to the average opinion of their leader neighbors have a lower bound
after some time.

######  Theorem 5.

Assume that $\big{\\{}x_{i}(t)\big{\\}}_{i\in L\cup F}\subset B(g,\delta)$ for
some $\delta<\epsilon$ and that

$\sup_{s\geq t}\big{\\{}\max_{i\in F}(1-\beta_{i}(s)),\ \max_{i\in
L}\alpha_{i}(s)\big{\\}}<1.$

Then,

$\lim_{t\to\infty}\max_{i\in L\cup F}\|x_{i}(t)-g\|=0.$

###### Proof of Theorem 5.

Via Theorem 2,

$\max_{k\in L}\|x_{k}(s)-g\|<\epsilon-\delta\hbox{ for some }p\geq t\hbox{ and
for all }s\geq p.$

For all $s\geq p$, $i\in F$ and $j\in L$, via Lemma 4,

$\|x_{i}(s)-x_{j}(s)\|\leq\|x_{i}(s)-g\|+\|g-x_{j}(s)\|<\delta+\epsilon-\delta=\epsilon$

therefore $N_{i}^{L}=L$. Let $\gamma=\sup_{s\geq t}\big{(}\max_{i\in
F}(1-\beta_{i}(s))\vee\max_{i\in L}\alpha_{i}(s)\big{)}$,
$\alpha_{t}=\max_{k\in L}\alpha_{k}(t)$, $\beta_{t}=\max_{k\in
F}(1-\beta_{k}(t))$, $A_{t}=\max_{k\in F}\|x_{k}(t)-g\|$ and $C_{t}=\max_{k\in
L}\|x_{k}(t)-g\|$. By Lemma 1 and the triangle inequality, for all $i\in F$
and $t>p$,

$\displaystyle A_{t+1}\leq\ $ $\displaystyle\beta_{t}A_{t}+C_{t}$
$\displaystyle\leq\ $
$\displaystyle\beta_{t}\beta_{t-1}\ldots\beta_{p}A_{p}+\beta_{t}\ldots\beta_{p+1}C_{p}+\ldots+\beta_{t}C_{t-1}+C_{t}$
$\displaystyle\leq\ $
$\displaystyle\gamma^{t-p+1}A_{p}+(t-p+1)\gamma^{t-p}C_{p}$

therefore

$\limsup_{t\to\infty}A_{t+1}\leq 0.$

Via Theorem 2, we are done. ∎

Now, consider a LF system consisting of a follower group and $m$ leader group.
Similarly as Theorem 5, we have the following corollaries.

######  Corollary 6.

Assume that $\big{\\{}x_{i}(t),\
g_{k}\big{\\}}_{i\in(\bigcup_{k=1}^{m}L_{k})\cup F,\ k\in[m]}\subset
B(g_{j},\delta)$ for some $\delta<\epsilon$ and $j\in[m]$ and that

$\sup_{s\geq t}\big{\\{}\max_{i\in F}(1-\sum_{k=1}^{m}\beta_{i}^{k}(s)),\
\max_{k\in[m]}\max_{i\in L_{k}}\alpha_{i}^{k}(s)\big{\\}}<1.$

Then,

$\lim_{t\to\infty}\max_{i\in(\bigcup_{k=1}^{m}L_{k})\cup
F}\|x_{i}(t)-\sum_{k=1}^{m}\frac{\beta_{i}^{k}(t)}{\sum_{j=1}^{m}\beta_{i}^{j}(t)}g_{k}\|=0.$

In particular for all $i\in(\bigcup_{k=1}^{m}L_{k})\cup F$,

$\lim_{t\to\infty}x_{i}(t)=\sum_{k=1}^{m}\frac{\beta_{i}^{k}}{\sum_{j=1}^{m}\beta_{i}^{j}}g_{k}\hbox{
if }\beta_{i}^{k}(t)\to\beta_{i}^{k}\hbox{ as }t\to\infty\hbox{ for all
}k\in[m].$

######  Corollary 7.

Assume that all leader groups are independent systems and

$(x_{i}(t))_{i\in L_{k}}\subset B(g_{k},\delta_{k})\ \hbox{for some}\
t\in\mathbf{N}\ \hbox{and}\ \delta_{k}<\epsilon\ \hbox{and for all}\ k\in[m],$

and all followers belong to one of them, and that

$\sup_{s\geq t}\big{\\{}\max_{i\in F}(1-\sum_{k=1}^{m}\beta_{i}^{k}(s)),\
\max_{k\in[m]}\max_{i\in L_{k}}\alpha_{i}^{k}(s)\big{\\}}<1.$

Then, all systems eventually achieve their target.

## References

  * [1] H Li,  Mixed Hegselmann-Krause Dynamics,  _Discrete and Continuous Dynamical Systems-B_ , (2021), https://arxiv.org/abs/2010.03050
  * [2] Q Zha, G Kou, H Zhang, H Liang, X Chen, CC Li and Y Dong,  Opinion dynamics in finance and business: a literature review and research opportunities,  _Financial Innovation_ , 44 (2020).
  * [3] Y Zhao, G Kou, Y Peng and Y Chen,  Understanding influence power of opinion leaders in e-commerce networks: An opinion dynamics theory perspective,  _Information Sciences_ , 426 (2018), 131–147.


# Locally universal $\mathrm{C}^{*}$-algebras with computable presentations

Alec Fox, Isaac Goldbring, and Bradd Hart  Department of Mathematics
University of California, Irvine, 340 Rowland Hall (Bldg.# 400), Irvine, CA
92697-3875<EMAIL_ADDRESS>https://www.math.uci.edu/people/alec-fox
<EMAIL_ADDRESS>http://www.math.uci.edu/ isaac Department of Mathematics
and Statistics, McMaster University, 1280 Main St., Hamilton ON, Canada L8S
4K1<EMAIL_ADDRESS>http://ms.mcmaster.ca/ bradd/

###### Abstract.

The Kirchberg Embedding Problem (KEP) asks if every $\mathrm{C}^{*}$-algebra
embeds into an ultrapower of the Cuntz algebra $\mathcal{O}_{2}$. In an effort
to provide a negative solution to the KEP and motivated by the recent
refutation of the Connes Embedding Problem, we establish two computability-
theoretic consequences of a positive solution to KEP. Both of our results
follow from the a priori weaker assumption that there exists a locally
universal $\mathrm{C}^{*}$-algebra with a computable presentation.

Goldbring was partially supported by NSF grant DMS-2054477. Hart was funded by
the NSERC.

##  1\. Introduction

The recent landmark quantum complexity result known as
$\operatorname{MIP}^{*}=\operatorname{RE}$ [11] yielded a negative solution to
a famous problem in the theory of von Neumann algebras, namely the Connes
Embedding Problem (CEP). The CEP, posed in Connes’ seminal paper [4], asks if
every tracial von Neumann algebra embeds into a tracial ultrapower of the
hyperfinite II1 factor. The negative solution to the CEP can be used to give a
negative solution to an analogous problem in the theory of
$\mathrm{C}^{*}$-algebras known as the Blackadar-Kirchberg Problem (or MF
Problem), which asked if every stably finite $\mathrm{C}^{*}$-algebra embeds
into an ultrapower of the universal UHF algebra (see [9, Proposition 6.1]).

The Blackadar-Kirchberg Problem can be viewed as the “finite”
$\mathrm{C}^{*}$-algebra analog of CEP. In this paper, we consider the
“infinite” $\mathrm{C}^{*}$-algebra analog of CEP known as the Kirchberg
Embedding Problem (KEP). KEP asks if every $\mathrm{C}^{*}$-algebra embeds
into an ultrapower of the Cuntz algebra $\mathcal{O}_{2}$.111Incidentally, one
might ask if there is an “infinite”, that is, type III, von Neumann algebra
analog of CEP. For example, one might ask if every von Neumann algebra embeds
with expectation into the Ocneanu ultrapower of the hyperfinite III1 factor
$\mathcal{R}_{\infty}$. In [1], Ando, Haagerup, and Winslow prove that this
question is equivalent to CEP itself (and thus has a negative answer).

The Kirchberg Embedding Problem was studied model theoretically by the second
author and Sinclair in [10]. In that paper, KEP is shown to be equivalent to
the statement that there is a $\mathrm{C}^{*}$-algebra that is both nuclear
and existentially closed. Further model-theoretic equivalents of KEP were
given by the second author in [8], where it was shown that KEP is equivalent
to the statement that $\mathcal{O}_{2}$ is the enforceable
$\mathrm{C}^{*}$-algebra.

In this paper, we take our attention away from the nuclearity of
$\mathcal{O}_{2}$ and instead focus on the fact that it has a so-called
computable presentation. Here, a presentation of a $\mathrm{C}^{*}$-algebra is
computable if there is an algorithm that can effectively approximate the norm
of all rational polynomials applied to the generators. As mentioned in Fact 1
below, the standard presentation of $\mathcal{O}_{2}$ is computable. We then
derive two computability-theoretic consequences of the existence of a locally
universal $\mathrm{C}^{*}$-algebra with a computable presentation, where here,
a $\mathrm{C}^{*}$-algebra $A$ is locally universal if every
$\mathrm{C}^{*}$-algebra embeds into an ultrapower of $A$. We believe that
neither of these consequences should hold generally and thus view these
results as evidence that the KEP has a negative solution.

We now briefly describe our two main results, giving more precise statements
in the two sections that follow.

Our first theorem concerns the notion of a weakly stable
$\mathrm{C}^{*}$-algebra. Roughly speaking, a finitely presented
$\mathrm{C}^{*}$-algebra $A$ is weakly stable if any almost $*$-homomorphisms
of $A$ into a $\mathrm{C}^{*}$-algebra $B$ is near an actual $*$-homomorphism
of $A$ into $B$. Somewhat more precisely, the finitely presented
$\mathrm{C}^{*}$-algebra

$A=C^{*}\langle\bar{x}\ |\ p_{j}(x_{1},\ldots,x_{k})=0\ ,j=1,\ldots,m\rangle$

(see the next section for a precise definition of this notion) is weakly
stable if: for any $\epsilon>0$, there is $\delta>0$ so that, for any
$\mathrm{C}^{*}$-algebra $B$ and elements $z_{1},\ldots,z_{k}\in B$ for which
$\|p_{j}(\bar{z})\|<\delta$ for all $j=1,\ldots,m$, there is a
$*$-homomorphism $\varphi:A\to B$ for which
$\|\varphi(x_{i})-z_{i}\|\leq\epsilon$ for all $i=1,\ldots,k$. Weakly stable
$\mathrm{C}^{*}$-algebras (and other variants) have been studied by other
researchers, perhaps most extensively in the foundational papers [3] and [12].
If we demand that this assignment $\epsilon\mapsto\delta$ is computable (in a
sense we make precise in Definition 5) below, we arrive at the notion of a
computably weakly stable $\mathrm{C}^{*}$-algebra. (To be precise, the
property of being computably weakly stable is a property of a given finite
presentation of a $\mathrm{C}^{*}$-algebra, but is preserved under computable
isomorphism; see Lemma 6 below.)

Our first theorem states that if a locally universal $\mathrm{C}^{*}$-algebra
with a computable presentation exists, then any computably weakly stable
finitely c.e. presentation (meaning that the finitely many polynomials in the
presentation have their coefficients from $\mathbb{Q}(i)$) of a
$\mathrm{C}^{*}$-algebra is actually computable. In short: under the
assumption that a locally universal $\mathrm{C}^{*}$-algebra with a computable
presentation exists, an effective weak stability condition on the
$\mathrm{C}^{*}$-algebra implies that one can effectively approximate the
operator norm in the $\mathrm{C}^{*}$-algebra.

Our second result belongs to the area of quantum complexity theory. In [11], a
particular quantum complexity class $MIP^{co}$ is defined and it is shown that
all of the languages in this class are coRE - complements of recursively
enumerable sets. It is left as an open question if the converse is true,
namely, does $MIP^{co}$ coincide with the class coRE? In the notation
$MIP^{co}$, the “co” stands for “commuting” and comes from the use of
commuting operator strategies in its definition. In this paper, we define a
relaxed version $MIP^{co}_{\delta,op}$ of “almost-commuting” operator
strategies and show that, assuming the existence of a locally universal
$\mathrm{C}^{*}$-algebra with a computable presentation, all languages which
belong to the corresponding quantum complexity class $MIP^{co}_{op,\delta}$
are actually recursively enumerable (and thus decidable!).

We end the introduction with some notation and terminology concerning
ultraproducts of $\mathrm{C}^{*}$-algebras. Throughout this paper, all
$\mathrm{C}^{*}$-algebras are assumed to be unital and all $*$-homomorphisms
are assumed to preserve the unit. Moreover, $\mathcal{U}$ always denotes a
nonprincipal ultrafilter on $\mathbb{N}$. Given a $\mathrm{C}^{*}$-algebra
$C$, its ultrapower with respect to $\mathcal{U}$, denoted $C^{\mathcal{U}}$,
is the quotient of the Banach algebra $\ell^{\infty}(\mathbb{N},C)$ of all
uniformly norm-bounded sequences from $C$ by the ideal of elements
$(A_{m})_{m\in\mathbb{N}}$ for which $\lim_{\mathcal{U}}\|A_{m}\|=0$. It is
well-known that $C^{\mathcal{U}}$ is a $\mathrm{C}^{*}$-algebra once again.
Given $(A_{m})_{m\in\mathbb{N}}\in\ell^{\infty}(\mathbb{N},C)$, we denote its
coset in $C^{\mathcal{U}}$ by $(A_{m})_{\mathcal{U}}$.

The authors would like to thank William Slofstra, Thomas Vidick and Henry Yuen
for useful discussions regarding this work.

##  2\. Computable weak stability

Let $\mathcal{G}$ be a set of noncommuting indeterminates, which we call
generators. By a set of relations for $\mathcal{G}$ we mean a set of relations
of the form $\|p(x_{1},\ldots,x_{n})\|\leq a$, where $p$ is a $*$-polynomial
in $n$ noncommuting variables with no constant term, $x_{1},\ldots,x_{n}$ are
elements of $\mathcal{G}$, and $a$ is a nonnegative real number. We also
require that, for every generator $x\in\mathcal{G}$, there is a relation of
the form $\|x\|\leq M$ in $\mathcal{R}$. A representation of
$(\mathcal{G},\mathcal{R})$ is a function $j:\mathcal{G}\to A$, where $A$ is a
$\mathrm{C}^{*}$-algebra, such that $\|p(j(x_{1}),\ldots,j(x_{n}))\|\leq a$
for every relation $\|p(x_{1},\ldots,x_{n})\|\leq a$ in $\mathcal{R}$.

The universal $\mathrm{C}^{*}$-algebra of $(\mathcal{G},\mathcal{R})$ is a
$\mathrm{C}^{*}$-algebra $A$ along with a representation $\iota:\mathcal{G}\to
A$ of $(\mathcal{G},\mathcal{R})$ such that, for all other representations
$j:\mathcal{G}\to B$ of $(\mathcal{G},\mathcal{R})$, there is a unique
*-homomorphism $\varphi:A\to B$ such that $\varphi(\iota(x))=j(x)$ for all
$x\in\mathcal{G}$. If the universal $\mathrm{C}^{*}$-algebra of
$(\mathcal{G},\mathcal{R})$ exists, then it is unique up isomorphism and will
be denoted by $C^{*}\langle\mathcal{G}|\mathcal{R}\rangle$. Note that
$C^{*}\langle\mathcal{G}|\mathcal{R}\rangle$ is generated by the image of the
generators. If $\mathcal{G}$ is a sequence $\bar{x}$, then we may write
$C^{*}\langle\bar{x}|\mathcal{R}\rangle$ instead of
$C^{*}\langle\bar{G}|\mathcal{R}\rangle$. Given that we remain in the context
of unital $\mathrm{C}^{*}$-algebras throughout this paper, we implicitly
assume that we have a distinguished generator for the unit and include
relations stating that it is a self-adjoint idempotent which acts as a
multiplicative identity.

A $\mathrm{C}^{*}$-algebra $A$ is finitely presented if it is of the form
$A=C^{*}\langle\mathcal{G}|\mathcal{R}\rangle$ for finite sets $\mathcal{G}$
and $\mathcal{R}$.

Let $C$ be a $\mathrm{C}^{*}$-algebra. A presentation of $C$ is a pair
$C^{\dagger}:=(C,(a_{n})_{n\in\mathbb{N}})$, where $\\{a_{n}\ :\
n\in\mathbb{N}\\}$ is a subset of $C$ that generates $C$ (as a
$\mathrm{C}^{*}$-algebra). Elements of the sequence $(a_{n})_{n\in\mathbb{N}}$
are referred to as special points of the presentation while elements of the
form $p(a_{i_{1}},\ldots,a_{i_{k}})$ for $p$ a $*$-polynomial with
coefficients from $\mathbb{Q}(i)$ (a rational polynomial) are referred to as
rational points of the presentation. We say that $C^{\dagger}$ is a computable
presentation of $C$ if there is an algorithm such that, upon input a rational
point $p$ of $C^{\dagger}$ and $k\in\mathbb{N}$, returns a rational number $q$
such that $|\|p\|-q|<2^{-k}$. If $A^{\dagger}$ and $C^{\dagger}$ are
presentations of $\mathrm{C}^{*}$-algebras, we say a *-homomorphism
$\varphi:A\to C$ is a computable map from $A^{\dagger}$ to $C^{\dagger}$ if
there is is an algorithim such that, upon input of a rational point $p$ of
$A^{\dagger}$ and $k\in\mathbb{N}$, returns a rational point $q$ of
$C^{\dagger}$ such that ${\left\lVert\varphi(p)-q\right\rVert}<2^{-k}$.

The standard presentation of a universal $\mathrm{C}^{*}$-algebra
$C^{*}\langle\bar{x}|\mathcal{R}\rangle$ has $\bar{x}$ as its distinguished
generating set. A relation $\|p(x_{1},\ldots,x_{n})\|\leq a$ is called
rational if $p$ is a rational polynomial and $a$ is a nonnegative dyadic
rational. A presentation $A^{\dagger}$ of a $\mathrm{C}^{*}$-algebra $A$ is
called c.e. if it is the standard presentation
$C^{*}\langle\bar{x}|\mathcal{R}\rangle$ of a c.e. set of rational relations
$\mathcal{R}$. When $\bar{x}$ and $\mathcal{R}$ are both finite, we say that
$A^{\dagger}$ is finitely c.e.

We will need the following fact of the first-named author [7]:

######  Fact 1.

If $A$ is a simple $\mathrm{C}^{*}$-algebra, then any c.e. presentation
$A^{\dagger}$ of $A$ is computable.

In particular, given that the standard presentation of $\mathcal{O}_{2}$ is
clearly (finitely) c.e., we conclude from the previous fact that it is a
computable presentation.

It is sensible to write a relation of the form $\|p(x_{1},\ldots,x_{n})\|\leq
0$ in the more familiar form $p(x_{1},\ldots,x_{n})=0$. Note also that in any
c.e. presentation of a $\mathrm{C}^{*}$-algebra, we can replace an arbitrary
relation of the form ${\left\lVert p(x_{1},\ldots,x_{n})\right\rVert}\leq a$
by the two relations $p(x_{1},\ldots,x_{n})-g=0$ and ${\left\lVert
g\right\rVert}\leq a$, where $g$ is a new generator.

######  Definition 2.

A finitely presented $\mathrm{C}^{*}$-algebra
$A=C^{*}\langle\overline{x}\;|\;p_{i}(\overline{x})=0,{\left\lVert
x_{k}\right\rVert}\leq C_{k}\rangle$ is weakly stable if for every
$\epsilon>0$ there is a $\delta>0$ such that for all $\mathrm{C}^{*}$-algebras
$B$ if $\overline{z}\in B$ satisfies ${\left\lVert
p_{i}(\overline{z})\right\rVert}\leq\delta$ for all $i$ and ${\left\lVert
z_{k}\right\rVert}\leq C_{k}+\delta$ for all $k$, then there exists a
*-homorphism $\varphi:A\to B$ such that
${\left\lVert\varphi(x_{k})-z_{k}\right\rVert}\leq\epsilon$ for all $k$.

The following are all examples of weakly stable $\mathrm{C}^{*}$-algebras; see
[2] for proofs.

######  Examples 3.

  1. (1)

$\mathrm{C}^{\mbox{$*$}}(\mathbb{F}_{n})$, the full universal
$\mathrm{C}^{*}$-algebra of the free group on $n$ generators.

  2. (2)

$M_{n}(\mathbb{C})$, or, more generally, any finite-dimensional
$\mathrm{C}^{*}$-algebra.

  3. (3)

Cuntz algebras $\mathcal{O}_{n}=\mathrm{C}^{\mbox{$*$}}\langle
s_{1},\ldots,s_{n}\;|\;s_{i}^{*}s_{j}=\delta_{ij}1,\sum
s_{i}s_{i}^{*}=1\rangle$.

  4. (4)

The Toeplitz algebra $\mathcal{T}$, the universal $\mathrm{C}^{*}$-algebra
generated by an isometry.

Notice that in all of the above examples, the $\mathrm{C}^{*}$-algebra is
either nuclear or else not simple. In fact, we have:

######  Proposition 4.

If KEP has a positive solution, then any simple weakly stable
$\mathrm{C}^{*}$-algebra is exact.

###### Proof.

Suppose that $A$ is a simple, weakly stable $\mathrm{C}^{*}$-algebra. By a
positive solution to KEP, there is an embedding
$A\hookrightarrow\mathcal{O}_{2}^{\mathcal{U}}$. Since $A$ is weakly stable
(recall that $A$ is finitely presented and hence there are only finitely many
conditions to be satisfied), there is a *-homomorphism $A\to\mathcal{O}_{2}$,
which, since $A$ is simple, must be an embedding. It follows that $A$ is
exact. ∎

We now introduce a computable version of weak stability.

######  Definition 5.

A finitely c.e. presentation
$A^{\dagger}=C^{*}\langle\overline{x}\;|\;p_{i}(\overline{x})=0,{\left\lVert
x_{k}\right\rVert}\leq C_{k}\rangle$ is computably weakly stable if there is
an algorithm which when given $n\in\mathbb{N}$ returns $m\in\mathbb{N}$ such
that for all $\mathrm{C}^{*}$-algebras $B$ if $\overline{z}\in B$ satisfies
${\left\lVert p_{i}(\overline{z})\right\rVert}\leq 2^{-m}$ for all $i$ and
${\left\lVert z_{k}\right\rVert}\leq C_{k}+2^{-m}$ for all $k$, then there
exists a *-homorphism $\varphi:A\to B$ such that
${\left\lVert\varphi(x_{k})-z_{k}\right\rVert}<2^{-n}$ for all $k$.

While the definition as written depends on the choice of relations, we show in
the following lemma the notion is computably robust, so any finite set of
rational relations that gives the same presentation will work.

######  Lemma 6.

Let

$A^{\dagger}=\mathrm{C}^{\mbox{$*$}}\langle
x_{1},\ldots,x_{j}\;|\;p_{i}(\overline{x})=0,{\left\lVert
x_{k}\right\rVert}\leq C_{k}\rangle$

and

$A^{\\#}=\mathrm{C}^{\mbox{$*$}}\langle
y_{1},\ldots,y_{\ell}\;|\;q_{i}(\overline{y})=0,{\left\lVert
y_{k}\right\rVert}\leq D_{k}\rangle$

be finitely c.e. presentations of a $\mathrm{C}^{*}$-algebra $A$. If there
exists an isomorphism computable from $A^{\\#}$ to $A^{\dagger}$ and
$A^{\dagger}$ is computably weakly stable, then so is $A^{\\#}$.

###### Proof.

Fix a computable isomorphism $\psi$ from $A^{\\#}$ to $A^{\dagger}$. Let
$n\in\mathbb{N}$. For each $k=1,\ldots,\ell$, we can compute a rational
*-polynomial $t_{k}(\overline{x})$ such that ${\left\lVert
t_{k}(\overline{x})-\psi(y_{k})\right\rVert}<2^{-(n+2)}$. Let $d$ be such that
for any $\mathrm{C}^{*}$-algebra $B$ if ${\left\lVert
u_{i}-v_{i}\right\rVert}_{B}<2^{-d}$ for $i=1,\ldots,j$ then ${\left\lVert
t_{k}(\overline{u})-t_{k}(\overline{v})\right\rVert}_{B}<2^{-(n+2)}$ for all
$k$. Let $s$ witness that $A^{\dagger}$ is computably weakly stable on input
$d$.

For $m\in\mathbb{N}$, let $W_{m}=\mathrm{C}^{\mbox{$*$}}\langle
w_{1},\ldots,w_{\ell}\;|\;{\left\lVert q_{i}(\overline{w})\right\rVert}\leq
2^{-m},{\left\lVert w_{k}\right\rVert}\leq D_{k}+2^{-m}\rangle$. By [7,
Theorem 3.3], given $m\in\mathbb{N}$ and a rational *-polynomial
$r(\overline{w})$ we can effectively enumerate a decreasing sequence of
rationals that converges to ${\left\lVert
r(\overline{w})\right\rVert}_{W_{m}}$. Enumerate over all $m\in\mathbb{N}$ and
rational *-polynomials $r_{1}(\overline{w}),\ldots,r_{j}(\overline{w})$ and
accept if ${\left\lVert
p_{i}(r_{1}(\overline{w}),\ldots,r_{j}(\overline{w}))\right\rVert}_{W_{m}}<2^{-s}$
for all $i$ and ${\left\lVert
r_{k}(\overline{w})\right\rVert}_{W_{m}}<C_{k}+2^{-s}$ for all $k$ and
${\left\lVert
t_{k}(r_{1}(\overline{w}),\ldots,r_{j}(\overline{w}))-w_{k}\right\rVert}_{W_{m}}<2^{-(n+2)}$
for all $k$. Note an acceptance must happen since there is an embedding from
$A$ into $\prod_{\mathcal{U}}W_{m}$ which sends $\psi(y_{k})$ to $w_{k}$.
Hence, for any $\epsilon>0$ there exist rational *-polynomials
$r_{1}(\overline{w}),\ldots,r_{j}(\overline{w})$ in $\prod_{\mathcal{U}}W_{m}$
such that ${\left\lVert
p_{i}(r_{1}(\overline{w}),\ldots,r_{j}(\overline{w}))\right\rVert}<\epsilon$
for all $i$ and ${\left\lVert r_{k}(\overline{w})\right\rVert}<C_{k}+\epsilon$
for all $k$ and ${\left\lVert
t_{k}(r_{1}(\overline{w}),\ldots,r_{j}(\overline{w}))-w_{k}\right\rVert}<\epsilon$
for all $k$.

Let $B$ be a $\mathrm{C}^{*}$-algebra and $\overline{z}\in B$ such that
${\left\lVert q_{i}(\overline{z})\right\rVert}\leq 2^{-m}$ for all $i$ and
${\left\lVert z_{k}\right\rVert}\leq D_{k}+2^{-m}$ for all $k$. Then
${\left\lVert
p_{i}(r_{1}(\overline{z}),\ldots,r_{j}(\overline{z}))\right\rVert}<2^{-s}$ for
all $i$ and ${\left\lVert r_{k}(\overline{z})\right\rVert}<C_{k}+2^{-s}$ for
all $k$ and ${\left\lVert
t_{k}(r_{1}(\overline{z}),\ldots,r_{j}(\overline{z}))-z_{k}\right\rVert}<2^{-(n+2)}$
for all $k$. By the choice of $s$, there exists $\varphi:A\to B$ such that
${\left\lVert\varphi(x_{k})-r_{k}(\overline{z})\right\rVert}<2^{-d}$ for
$k=1,\ldots,j$. Then for $k=1,\ldots,\ell$,

$\displaystyle{\left\lVert\varphi(\psi(y_{k}))-z_{k}\right\rVert}$
$\displaystyle\leq{\left\lVert\varphi(\psi(y_{k}))-\varphi(t_{k}(\overline{x}))\right\rVert}$
$\displaystyle\qquad+{\left\lVert\varphi(t_{k}(\overline{x}))-t_{k}(r_{1}(\overline{z}),\ldots,r_{j}(\overline{z}))\right\rVert}$
$\displaystyle\qquad+{\left\lVert
t_{k}(r_{1}(\overline{z}),\ldots,r_{j}(\overline{z}))-z_{k}\right\rVert}$
$\displaystyle\leq{\left\lVert\psi(y_{k})-t_{k}(\overline{x})\right\rVert}$
$\displaystyle\qquad+{\left\lVert
t_{k}(\varphi(x_{1}),\ldots,\varphi(x_{j}))-t_{k}(r_{1}(\overline{z},\ldots,r_{j}(\overline{z}))\right\rVert}$
$\displaystyle\qquad+{\left\lVert
t_{k}(r_{1}(\overline{z}),\ldots,r_{j}(\overline{z}))-z_{k}\right\rVert}$
$\displaystyle<2^{-n}.$

∎

We next aim to show that all of the above examples of weakly stable
$\mathrm{C}^{*}$-algebras are actually computably weakly stable.

The following result is folklore.

######  Lemma 7.

Suppose that $0<\delta<\epsilon<1$. Then for any unital
$\mathrm{C}^{*}$-algebra $A$ and $a\in A$, if ${\left\lVert
a^{*}a-1\right\rVert}\leq\delta$ and ${\left\lVert
aa^{*}-1\right\rVert}\leq\delta$, then there is a unitary $u\in A$ such that
${\left\lVert a-u\right\rVert}<\epsilon$.

Non-effective versions of the following results can be found in [3] or [12].

######  Lemma 8.

Suppose that $0<\epsilon<1$ and $0<\delta<\epsilon^{2}/8$. Then for any
$\mathrm{C}^{*}$-algebra $A$ and $a\in A$, if ${\left\lVert a\right\rVert}\leq
2$, ${\left\lVert a-a^{*}\right\rVert}\leq\delta$, and ${\left\lVert
a-a^{2}\right\rVert}\leq\delta$, then there is a projection $p\in A$ such that
${\left\lVert a-p\right\rVert}<\epsilon$.

###### Proof.

Let $x=(a+a^{*})/2$, so $x$ is self-adjoint and ${\left\lVert
a-x\right\rVert}\leq\delta/2<\epsilon/2$. Also, by expanding, we see
${\left\lVert x-x^{2}\right\rVert}\leq{\left\lVert
a-a^{2}\right\rVert}+{\left\lVert a\right\rVert}{\left\lVert
a-a^{*}\right\rVert}/2\leq 2\delta<\epsilon^{2}/4$. Hence the spectrum of $x$,
$\sigma(x)\subseteq[-\epsilon/2,\epsilon/2]\cup[1-\epsilon/2,1+\epsilon/2]$.
Let $f$ be continuous on $\sigma(x)$ such that $f=0$ on
$[-\epsilon/2,\epsilon/2]$ and $f=1$ on $[1-\epsilon/2,1+\epsilon/2]$. Let
$p=f(x)$. Then $p$ is a projection and ${\left\lVert
a-p\right\rVert}\leq{\left\lVert a-x\right\rVert}+{\left\lVert
x-f(x)\right\rVert}<\epsilon$. ∎

######  Corollary 9.

If $A_{1}^{\dagger}$ and $A_{2}^{\dagger}$ are computably weakly stable, then
so is $A_{1}^{\dagger}\oplus A_{2}^{\dagger}$.

######  Lemma 10.

Suppose $0<\epsilon<1$ and $0<\delta<2^{-16}\epsilon^{8}$. Then for any
$\mathrm{C}^{*}$-algebra $A$, $a\in A$, and projections $p_{1},p_{2}\in A$, if
${\left\lVert a^{*}a-p_{1}\right\rVert}\leq\delta$ and ${\left\lVert
aa^{*}-p_{2}\right\rVert}\leq\delta$, then there is a partial isometry $v$
such that ${\left\lVert a-v\right\rVert}<\epsilon$, $v^{*}v=p_{1}$, and
$vv^{*}=p_{2}$.

###### Proof.

Let $b=p_{2}ap_{1}$. We have ${\left\lVert
a(1-p_{1})\right\rVert}^{2}={\left\lVert(1-p_{1})(a^{*}a-p_{1})(1-p_{1})\right\rVert}\leq\delta$,
and similarly
${\left\lVert(1-p_{2})a\right\rVert}^{2}={\left\lVert(1-p_{2})aa^{*}(1-p_{2})\right\rVert}\leq\delta$.
Hence ${\left\lVert a-b\right\rVert}\leq{\left\lVert
a(1-p_{1})\right\rVert}+{\left\lVert(1-p_{2})a\right\rVert}\leq
2\sqrt{\delta}$. Furthermore,

$\displaystyle{\left\lVert(b^{*}b)^{2}-b^{*}b\right\rVert}$
$\displaystyle\leq{\left\lVert(b^{*}b)^{2}-(a^{*}a)^{2}\right\rVert}+{\left\lVert(a^{*}a)^{2}-p_{1}^{2}\right\rVert}+{\left\lVert
p_{1}-a^{*}a\right\rVert}+{\left\lVert a^{*}a-b^{*}b\right\rVert}$
$\displaystyle\leq 20{\left\lVert b-a\right\rVert}+4{\left\lVert
a^{*}a-p_{1}\right\rVert}$ $\displaystyle\leq 49\sqrt{\delta}.$

Let $\gamma=7\delta^{1/4}$. Then $\sigma(b^{*}b)$ is a subset of
$[-\gamma,\gamma]\cup[1-\gamma,1+\gamma]$. Let $f$ be a continuous function on
$\sigma(b^{*}b)$ such that $f=0$ on $[-\gamma,\gamma]$ and $f(x)=\sqrt{x}$ for
all $x\in[1-\gamma,1+\gamma]$. Let $w=bf(b^{*}b)$. Then
$w^{*}w=b^{*}bf(b^{*}b)^{2}$ and $ww^{*}=bb^{*}f(bb^{*})^{2}$ are projections.
Also, ${\left\lVert
b-w\right\rVert}^{2}={\left\lVert(b^{*}-w^{*})(b-w)\right\rVert}={\left\lVert
b^{*}b-w^{*}w\right\rVert}\leq\gamma$, so ${\left\lVert
a-w\right\rVert}\leq{\left\lVert a-b\right\rVert}+{\left\lVert
b-w\right\rVert}\leq 2\sqrt{\delta}+\sqrt{\gamma}<\epsilon$. Note $w^{*}w\leq
p_{1}$ and $ww^{*}\leq p_{2}$. Then $p_{1}-w^{*}w$ is a projection with norm

${\left\lVert p_{1}-w^{*}w\right\rVert}\leq{\left\lVert
p_{1}-a^{*}a\right\rVert}+{\left\lVert a^{*}a-b^{*}b\right\rVert}+{\left\lVert
b^{*}b-w^{*}w\right\rVert}<1$

and $p_{2}-ww^{*}$ is a projection with norm

${\left\lVert p_{2}-ww^{*}\right\rVert}\leq{\left\lVert
p_{2}-aa^{*}\right\rVert}+{\left\lVert aa^{*}-bb^{*}\right\rVert}+{\left\lVert
bb^{*}-ww^{*}\right\rVert}<1.$

Thus $w^{*}w=p_{1}$ and $ww^{*}=p_{2}$.

∎

######  Corollary 11.

If $A^{\dagger}$ is computably weakly stable, then so is $M_{n}(A^{\dagger})$.

We now have that the following standard presentations are computably weakly
stable:

######  Examples 12.

  1. (1)

$\mathrm{C}^{\mbox{$*$}}(\mathbb{F}_{n})$.

  2. (2)

$\mathbb{C}$. More generally, the universal $\mathrm{C}^{*}$-algebra generated
by $n$ projections.

  3. (3)

$M_{n}(\mathbb{C})$. More generally, any finite-dimensional
$\mathrm{C}^{*}$-algebra.

  4. (4)

Cuntz algebras $\mathcal{O}_{n}$.

  5. (5)

The Toeplitz algebra $\mathcal{T}$.

For (1), apply Lemma 7; for (2), apply Lemma 8; for (3), apply Corollary 9 and
Lemma 10; and for (4), apply Lemma 8 and Lemma 10.

Note that the previous presenations are all actually computable. The following
is the main result of this section:

######  Theorem 13.

If there exists a locally universal $\mathrm{C}^{*}$-algebra $B$ with a
computable presentation $B^{\dagger}$, then every computably weakly stable
presentation $A^{\dagger}$ of a $\mathrm{C}^{*}$-algebra $A$ is computable.

###### Proof.

Since $A^{\dagger}$ is c.e., by [7, Theorem 3.3] there is an effective
procedure which, when given a rational point $q$ of $A^{\dagger}$, enumerates
a decreasing sequence of rationals that converges to ${\left\lVert
q\right\rVert}$. It is enough to show we can do the same from below.

Given a rational point $q(\overline{x})$ of $A^{\dagger}$, we proceed as
follows. Enumerate through all $j\in\mathbb{N}$. For each $j$, determine
$n\in\mathbb{N}$ such that if ${\left\lVert x_{k}-y_{k}\right\rVert}<2^{-n}$
for all $k$ then ${\left\lVert
q(\overline{x})-q(\overline{y})\right\rVert}<2^{-j}$ in all
$\mathrm{C}^{*}$-algebras. Let $m\in\mathbb{N}$ be given, upon input $n$, by
the effective procedure which witnesses that $A^{\dagger}$ is computably
weakly stable. Enumerate all tuples $\overline{r}$ of rational points of
$B^{\dagger}$ such that ${\left\lVert p_{i}(\overline{r})\right\rVert}<2^{-m}$
for all $i$ and ${\left\lVert r_{k}\right\rVert}<C_{k}+2^{-m}$ for all $k$.
Enumerate over all dyadic rationals $d$. If ever ${\left\lVert
q(\overline{r})\right\rVert}>2^{-j}+d$ where $d$ is greater than all previous
outputs, then output $d$. By the choice of $m$, there exists a *-homorphism
$\varphi:A\to B$ such that
${\left\lVert\varphi(x_{k})-r_{k}\right\rVert}<2^{-n}$. Then ${\left\lVert
q(\overline{x})\right\rVert}\geq{\left\lVert\varphi(q(\overline{x}))\right\rVert}\geq{\left\lVert
q(\overline{r})\right\rVert}-2^{-j}>d$.

We show this sequence does converge to ${\left\lVert q\right\rVert}$ from
below. Indeed, let $d<{\left\lVert q(\overline{x})\right\rVert}$ and let
$j\in\mathbb{N}$ be such that ${\left\lVert
q(\overline{x})\right\rVert}-d>2^{-j}$. Let $n$ and $m$ as above. Since $B$ is
locally universal, for small $\epsilon>0$ there exists $\overline{z}$ in $B$
such that ${\left\lVert p_{i}(\overline{z})\right\rVert}<2^{-m}-\epsilon$ for
all $i$ and ${\left\lVert z_{k}\right\rVert}<C_{k}+2^{-m}-\epsilon$ for all
$k$ and ${\left\lVert q(\overline{z})\right\rVert}>d+2^{-j}+\epsilon$. So,
there exist rational points $\overline{r}$ of $B^{\dagger}$ such that
${\left\lVert p_{i}(\overline{r})\right\rVert}<2^{-m}$ for all $i$ and
${\left\lVert r_{k}\right\rVert}<C_{k}+2^{-m}$ for all $k$ and ${\left\lVert
q(\overline{r})\right\rVert}>d+2^{-j}$. ∎

By Fact 1, we immediately obtain the following:

######  Corollary 14.

If there exists a simple locally universal $\mathrm{C}^{*}$-algebra $B$ with a
c.e. presentation $B^{\dagger}$ (in particular, if KEP holds), then every
computably weakly stable presentation $A^{\dagger}$ of a
$\mathrm{C}^{*}$-algebra $A$ is computable.

##  3\. A quantum complexity result

A nonlocal game with $n$ questions and $k$ answers is a pair
$\mathfrak{G}=(\pi,D)$, where $\pi$ is a probability distribution on $[n]$ and
$D:[n]\times[n]\times[k]\times[k]\to\\{0,1\\}$ is called the decision
predicate for the game. Here, $[n]:=\\{1,\ldots,n\\}$ and analogously for
$[k]$. We also refer to the pair $(n,k)$ as the dimensions of $\mathfrak{G}$.
We view two players, henceforth referred to as Alice and Bob, playing
$\mathfrak{G}$ as follows: a pair of questions $(x,y)\in[n]\times[n]$ is
randomly chosen according to $\pi$ and then Alice and Bob somehow respond with
a pair of answers $(a,b)\in[k]\times[k]$; they win the game if $D(x,y,a,b)=1$
and otherwise they lose the game.

In order to describe their strategies for playing $\mathfrak{G}$, we need the
notion of POVMs. Recall that a positive operator-valued measure or POVM on a
Hilbert space $\mathcal{H}$ is a finite collection $A_{1},\ldots,A_{k}$ of
positive operators on $\mathcal{H}$ such that $A_{1}+\cdots+A_{k}=I$. We refer
to $k$ as the length of the POVM. More generally, one can use the same
definition to define a POVM in any $\mathrm{C}^{*}$-algebra.

For each $k$, let $\varphi_{k}(X)$ denote the formula

$\max\left(\max_{1\leq i\leq
k}\inf_{Z_{i}}\|Z_{i}^{*}Z_{i}-X_{i}\|,\|\sum_{i=1}^{k}X_{i}-I\|\right)$

in the $k$ variables $X=(X_{1},\ldots,X_{k})$. The following lemma is easy but
will be used throughout the paper:

######  Lemma 15.

For each $\epsilon>0$ and $k\geq 1$, there is $\delta>0$ such that: for any
$\mathrm{C}^{*}$-algebra $C$ and any elements $A_{1},\ldots,A_{k}$ from the
unit ball of $C$, if $\varphi_{k}(A_{1},\ldots,A_{k})<\delta$, then there is a
POVM $B_{1},\ldots,B_{k}$ in $C$ such that $\max_{1\leq i\leq
k}\|A_{i}-B_{i}\|<\epsilon$.

We use POVMs to define strategies for nonlocal games. First suppose that
$\mathfrak{G}$ is a nonlocal game with dimensions $(n,k)$ and $C$ is a
$\mathrm{C}^{*}$-algebra. A $\mathfrak{G}$-measurement in $C$ is a tuple
$A:=(A^{x})_{x\in[n]}$ of POVMs in $C$, each of which has length $k$. Of
course, the notion of a $\mathfrak{G}$-measurement in $C$ only depends on the
dimensions of the nonlocal game, but the terminology will prove useful in the
sequel. Thus, corresponding to each possible question and answer pair
$(x,a)\in[n]\times[k]$, we will have a positive element $A^{x}_{a}\in C$, and
for each $x\in[n]$, we have $\sum_{a\in[k]}A^{x}_{a}=I$.

A $\mathfrak{G}$-strategy in $C$ is a tuple $\sigma:=(A,B,\phi)$, where $A$
and $B$ are $\mathfrak{G}$-measurements in $C$ and $\phi\in S(C)$ is a state
on $C$. Given a $\mathfrak{G}$-strategy $\sigma$ in $C$ as above, we define
the corresponding correlation matrix $p_{\sigma}\in[0,1]^{n^{2}k^{2}}$ by
$p_{\sigma}(a,b|x,y)=\phi(A^{x}_{a}\bullet B^{y}_{b})$, where, for any $A,B\in
C$, we define $A\bullet
B:=\frac{1}{2}(A^{1/2}BA^{1/2}+B^{1/2}AB^{1/2})$.222This notation seems to
have first been considered by Ozawa in [14]. The intuition behind this
definition is that if Alice and Bob play $\mathfrak{G}$ according to the
strategy $\sigma$, then upon receiving the question pair $(x,y)$, they both
measure their portion of the state $\phi$ using their POVMs $A^{x}$ and
$B^{y}$; since we are not assuming that these measurements commute, we take
the average of the results obtained from when Alice measures first and from
when Bob measures first. Consequently, $p_{\sigma}(a,b|x,y)$ is the
probability that they answer the question pair $(x,y)$ with the answer pair
$(a,b)$ when using the strategy $\sigma$.

Of course, if each $A^{x}_{a}$ and $B^{y}_{b}$ commute, the above definition
degenerates to the usual situation of calculating
$p_{\sigma}(a,b|x,y)=\phi(A^{x}_{a}B^{y}_{b})$ and we call the strategy
$\sigma$ commuting. Fix a positive real number $\delta>0$. We call the
strategy $\sigma$ $\delta$-op-almost commuting if
$\sum_{a,b\in[k]}\|[A^{x}_{a},B^{y}_{b}]\|<\delta$ for all
$(x,y)\in[n]\times[n]$. Note that the notion of a $\delta$-op-commuting
strategy depends only on the pair of $\mathfrak{G}$-measurements, whence it
makes sense to say that a pair of such measurements is a $\delta$-op-almost
commuting pair.

Given a $\mathfrak{G}$-strategy $\sigma$ in $C$, we define the value of
$\mathfrak{G}$ when playing according to $\sigma$ to be the expected value
Alice and Bob have of winning the game when playing according to $\sigma$,
that is,

$\operatorname{val}(\mathfrak{G},\sigma):=\sum_{x,y}\pi(x,y)\sum_{a,b}D(x,y,a,b)p_{\sigma}(a,b|x,y).$

In the sequel, it will behoove us to define, for every pair $(A,B)$ of
$\mathfrak{G}$-measurements in $C$, the element

$\mathfrak{G}(A,B):=\sum_{x,y}\pi(x,y)\sum_{a,b}D(x,y,a,b)(A^{x}_{a}\bullet
B^{y}_{b}).$

With this notation, we have
$\operatorname{val}(\mathfrak{G},\sigma)=\phi(\mathfrak{G}(A,B))$.

If one considers the supremum of $\operatorname{val}(\mathfrak{G},\sigma)$ as
$\sigma$ ranges over all commuting $\mathfrak{G}$-strategies in
$\mathcal{B}(\mathcal{H})$, one obtains the commuting value of $\mathfrak{G}$,
denoted $\operatorname{val}^{co}(\mathfrak{G})$. Similarly, given $\delta>0$,
we define the $\delta,\operatorname{op}$-commuting value of $\mathfrak{G}$,
denoted $\operatorname{val}^{co}_{\delta,\operatorname{op}}(\mathfrak{G})$, to
be the supremum of $\operatorname{val}(\mathfrak{G},\sigma)$ as $\sigma$
ranges over all $\delta$-op-almost commuting $\mathfrak{G}$-strategies in
$\mathcal{B}(\mathcal{H})$.

Recall that a language (in the sense of complexity theory) is simply a subset
of $2^{<\mathbb{N}}$, that is, is a set of finite sequences of bits.

######  Definition 16.

We say that a language $L$ belongs to $\operatorname{MIP}^{co}$ if there is an
efficient mapping from sequences of bits $z$ to nonlocal games
$\mathfrak{G}_{z}$ such that:

  * •

If $z\in L$, then $\operatorname{val}^{co}(\mathfrak{G}_{z})=1$.

  * •

If $z\notin L$, then
$\operatorname{val}^{co}(\mathfrak{G}_{z})\leq\frac{1}{2}$.

In [13], it was shown that if $L$ belongs to $\operatorname{MIP}^{co}$, then
$L$ belongs to the complexity class coRE of sets whose complement is c.e. and
it was asked if this inclusion is in fact an equality. The main result of this
section shows that the analogous question has a negative answer for a suitably
defined almost-commuting version of the class $\operatorname{MIP}^{co}$:

######  Definition 17.

Fix a computable function $\delta:\mathbb{N}\to[0,1]$. We say that a language
$L$ belongs to $\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$ if there
is an efficient mapping from sequences of bits $z$ to nonlocal games
$\mathfrak{G}_{z}$ such that:

  * •

If $z\in L$, then
$\operatorname{val}^{co}_{\delta(|z|),\operatorname{op}}(\mathfrak{G}_{z})=1$.

  * •

If $z\notin L$, then
$\operatorname{val}^{co}_{\delta(|z|),\operatorname{op}}(\mathfrak{G}_{z})\leq\frac{1}{2}$.

######  Theorem 18.

If there is a locally universal $\mathrm{C}^{*}$-algebra $C$ that has a
computable presentation (in particular, if KEP holds), then for every
computable function $\delta:\mathbb{N}\to[0,1]$, every language in
$\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$ is recursively
enumerable.

###### Proof.

Suppose that $C$ is a locally universal $\mathrm{C}^{*}$-algebra with a
computable presentation $C^{\\#}$. Fix a computable function
$\delta:\mathbb{N}\to[0,1]$ and suppose that $L$ belongs to
$\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$. Here is the algorithm
that shows that $L$ is recursively enumerable. Suppose that one inputs the
sequence of bits $z$. Set $\mathfrak{G}:=\mathfrak{G}_{z}$. Start enumerating
pairs of $\delta(|z|)$-almost commuting $\mathfrak{G}$-measurements $(A,B)$ in
$C$ that consist only of rational points of $C^{\\#}$; this is possible since
the presentation is computable. If $(A,B)$ is such a $\delta(|z|)$-op-almost
commuting pair, approximate $\|\mathfrak{G}(A,B)\|$ to within error
$\frac{1}{4}$. If this approximation exceeds $\frac{1}{2}$, then declare that
$z\in L$.

Here is why the algorithm works. We first show that if $z\in L$, then the
algorithm will tell us so. As above, set $\mathfrak{G}:=\mathfrak{G}_{z}$. Fix
$\epsilon>0$ small enough and let $\sigma:=(A,B,\phi)$ be a
$\delta(|z|)$-$\operatorname{op}$-almost commuting $\mathfrak{G}$-strategy in
$\mathcal{B}(\mathcal{H})$ such that
$\operatorname{val}(\mathfrak{G},\sigma)>1-\epsilon$. It follows that
$\|\mathfrak{G}(A,B)\|>1-\epsilon$. Let $D$ be the $\mathrm{C}^{*}$-algebra
generated by the coordinates of $A$ and $B$ and consider an embedding of $D$
into $C^{\mathcal{U}}$. It follows from Lemma 15 that there are
$\delta(|z|)$-$\operatorname{op}$-almost commuting $\mathfrak{G}$-measurements
$\bar{A}$ and $\bar{B}$ in $C$ for which
$\|\mathfrak{G}(\bar{A},\bar{B})\|>1-2\epsilon$. Without loss of generality,
one can assume that the coordinates of $\bar{A}$ and $\bar{B}$ are rational
points of $C^{\\#}$. If $\epsilon$ is small enough, then approximating
$\|\mathfrak{G}(\bar{A},\bar{B})\|$ to within error $\frac{1}{4}$ will exceed
$\frac{1}{2}$. Thus, our algorithm will eventually tell us that $z\in L$.

We now check that the algorithm makes no mistakes, that is, if the algorithm
tells us that $z\in L$, then in fact $z$ does belong to $L$. If the algorithm
tells us that $(A,B)$ is a $\delta(|z|)$-$\operatorname{op}$-almost commuting
pair of $\mathfrak{G}$-measurements in $C$ for which
$\|\mathfrak{G}(A,B)\|>\frac{1}{2}$, then there will be some state $\phi$ on
$C$ such that $\phi(\mathfrak{G}(A,B))>\frac{1}{2}$. Setting
$\sigma:=(A,B,\phi)$, we see that
$\operatorname{val}^{co}_{\operatorname{op},\delta}(\mathfrak{G})>\frac{1}{2}$.
Consequently, $z\in L$, as desired. ∎

We note two things about Theorem 18. First, as is the case for
$\operatorname{MIP}^{co}$, one can show that every language in
$\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$ is coRE (regardless of
the truth of KEP), whence the theorem implies that every language in
$\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$ is actually decidable
provided that KEP holds. Second, the class
$\operatorname{MIP}^{co}_{\delta,\operatorname{op}}$ differs from the class
$\operatorname{MIP}^{co}_{\delta}$ introduced by Coudron and Slofstra in [5];
in particular, every language in their class is decidable without any KEP
assumption.

## References

  * [1] H. Ando, U. Haagerup, and C. Winslow, _Ultraproducts, QWEP von Neumann algebras, and the Effros-Maréchal topology_ , To appear in Journal für die Reine und Angewandte Mathematik. arXiv 1306.0460.
  * [2] B. Blackadar, _Operator Algebras: Theory of $\mathrm{C}^{*}$-Algebras and von Neumann Algebras_, Springer Berlin, Heidelberg (2005), ISBN: 978-3-540-28486-4
  * [3] B. Blackadar, _Shape theory for $C^{*}$-algebras_, Mathematica Scandinavica 56 (1985), 249-275.
  * [4] A. Connes, _Classification of Injective Factors_ , Annals of Mathematics 104 (1976), 73-115.
  * [5] M. Coudron and W. Slofstra, _Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision_ , to appear in Computational Complexity Conference (CCC) 2019.
  * [6] S. Eilers, T. Shulman, and A. Sørensen, $\mathrm{C}^{*}$-stability of discrete groups, Advances in Mathematics 373 (2020), 107324.
  * [7] A. Fox, _On computable analogies between $\mathrm{C}^{*}$-algebras and groups_, to appear in the Journal of Symbolic Logic. arXiv 2206.01415.
  * [8] I. Goldbring, _Enforceable operator algebras_ , Journal of the Institute of Mathematics of Jussieu 20 (2021), 31-63.
  * [9] I. Goldbring and B. Hart, _The universal theory of the hyperfinite II 1 factor is not computable_, preprint. arXiv 2006.05629.
  * [10] I. Goldbring and T. Sinclair, _On Kirchberg’s embedding problem_ , Journal of Functional Analysis 269 (2015), 155-198.
  * [11] Z. Ji, A. Natarajan, T. Vidick, J. Wright and H. Yuen, MIP* = RE, preprint, arxiv 2001.04383
  * [12] T. A. Loring, _$\mathrm{C}^{*}$ -Algebras Generated by Stable Relations_, Journal of Functional Analysis 112 (1993), 159-203.
  * [13] M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, 2008.
  * [14] N. Ozawa, _Tsirelson’s problem and asymptotically commuting unitary matrices_ , Journal of Mathematical Physics, 54 (2013):032202.