n \cdot 2^{\modsu(k_{n+2}+2)-m_{n+2}+k_{n+2}-k_{n+1}}
\big)
\eqnsp .
\end{align}

If $f|_S$ is bi-Hölder continuous, then its moduli are of form
$\modcont(n) = \ol{\alpha}^{-1}(n+\ol{c})$ and
$\modsu(n) = \ul{\alpha}^{-1} (n + \ul{c})$ with $\ol{c} \dfeq \lb\ol{C}$,
$\ul{c} \dfeq \lb\ul{C}$.

\[
\modsu(k_{n+2}+2) - m_{n+2}
= n \cdot ((\ol{\alpha}\ul{\alpha}^2)^{-1} - \ul{\alpha}^{-1})
+ 2 \cdot (\ol{\alpha}\ul{\alpha}^2)^{-1}
+ k_0/\ul{\alpha}
\]

and $k_{i+1} - k_{i} = (\ol{\alpha}\ul{\alpha})^{-1}$.
Assuming $\ol{\alpha}\ul{\alpha} = 1$ (which holds exactly for
bi-Lipschitz functions) allows to rewrite <ref>
$\bigO\big( n \cdot 2^{k_0} \big)$
by applying the identities we just obtained.

Note that the encoding length of each $p$ and $q_{p,i}$ is bounded linearly
in $b + k_{n+2} + \len{\enc{q}}$.
Finally, this bound combined with the former bound on the number of points
to check gives the claimed parameterized polynomial-time bound for $\dsoinv$
over $\lfun$.

Follows directly from the proof of <ref>(2) by replacing the
one-way function with a partial one-way permutation as in
Since $\psi$ is length-preserving it satisfies
$p(\len{s}) = \len{\psi^{-1}(s)}$ with $p \dfeq \id$.
By the remarks following <ref>(2), the moduli of the function
constructed to prove this direction are of form
$\mu(n) = cn + p(n) + \mathrm{const}$
a bound linear in $n$.

Let $\varphi$ be a total one-way permutation and $p \in \IN[X]$ such that
$\len{s} \leq p(\len{\varphi(s)})$ for all $s \in \Sast$.
\[
\Gamma_n \dfeq \sum\nolimits_{i=0}^n \big( p(i) + 2 \big)
\eqnsp , \quad
\gamma_n \dfeq \Gamma_n - \big( p(n) + 2 \big)
\eqnsp , \quad
\delta_{s,n} \dfeq p(n) - \len{s}
\eqnsp ,
\]

and construct a partial function $\psi \parcol \Sast \to \Sast$ by

\[
\psi \dffn
0^{\gamma_n} \, 1 \, 0^{\delta_{s,n}} \, 1 \, s
\longmapsto
0^{\Gamma_n - (n+1)} \, 1 \, \varphi(s)
\quad
\text{for } \varphi(s) \in \Sigma^n
\eqnsp .
\]

The idea behind the construction of $\psi$ is to first pad the all
arguments to $\varphi$ with length-$n$ images to be of length $\Gamma_n$,
and then to pad the image of each $t \in \Sigma^{\gamma_n}$ also to length
This way, $\psi$ will be length-preserving.

Concerning (2):
Given a $t \in \Sast$, use $\len{t}$ to determine whether $t$ is contained
in $\Sigma^{\Gamma_n}$ for some $n$.
To this end, check if $t$ is of form $0^{\gamma_n}\,1\,0^{\delta_{s,n}}\,1\,s$
for some $s \in \Sigma^{\leq p(n)}$ and also if $\varphi(s) \in \Sigma^n$.
Note that the respective $n$ is bounded from above by $\len{t}$.
If $t$ is not of this particular form, then $t \not\in \dom(\psi)$ follows
If, on the contrary, $t$ is of this form, but $\varphi(s) \not\in \Sigma^n$,
then $t \not\in \dom(\psi)$ follows, too.
If, however, $\varphi(s) \in \Sigma^n$,
then the (easy to compute) string $0^{\Gamma_n-(n+1)}\,1\,\varphi(s)$
is the image of $t$ under $\psi$.

Concerning (3):
Let $\psi^{-1} \in \FPTime$.
Given $t \in \Sast$, construct $t' \dfeq 0^{\Gamma_n}\,1\,t$.
Note that by surjectivity of $\varphi$ we know that elements of $\dom(\psi)$
can only be of the above form.
It thus suffices to compute
$s' \dfeq \psi^{-1}(t') = 0^{\gamma_n}\,1\,0^{\delta_{s,n}}\,1\,s$ and extract
$s$ from it which by construction of $\psi$ satisfies $\varphi^{-1}(t) = s$.

§.§ $\dsoimg$

The operator $\dsoimg \dffn \usubseteq \cfn(\IR^d,\IR^e) \times \compset[d]
\ni (f,S) \mapsto f[S] \in \compset[e]$ has been proved to be
$(\parfunrep[d,e] \times \gridrep[d], \setrep[e])$-computable
<cit.> which, however, fails if we relax the restriction
on $S$ from compact to closed <cit.>.
The respective proof unfortunately does not yield any complexity bounds.
However: Restricting $\dsoimg$ to Hölder functions does give parameterized

To this end,
define a representation $\imgfunrep[d,e]$ as follows:
A $\phi'$ is a $\imgfunrep[d,e]$-name of
$(f,S) \in \hfun \times \compset[d]$ if $\phi' = \enc{\phi,\varphi}$ with
$\parfunrep[d,e](\phi) = f$, $\gridrep[d](\varphi) = S$, and
$S \subseteq \dom(f)$.
Further denote by $\ens{\upalpha C}$ the enrichment by Hölder parameters, ,

\[
\ens{\upalpha C} \dffn \hfun \mto \Sast
\eqnsp , \quad
\ens{\upalpha C} \dffn f \mmapsto \st
{ \enc{ \unatrep(1/\alpha), \bnatrep(C) } }
{ f \text{ is } (\alpha,C)\text{-Hölder continuous} }
\eqnsp .
\]

Then the complexity of $\dsoimg$ restricted to Hölder functions follows
immediately from <ref>.

$\dsoimg|_{\hfun \times \compset}$ is parameterized
polynomial-time $(\imgfunrep[d,e] \enp{\upalpha C}, \gridrep[e])$-computable,
and $\dsoimg|_{\lfun \times \compset}$ is fully polynomial-time
$(\imgfunrep[d,e] \enp{\upalpha C}, \gridrep[e])$-computable.

For the proof it essentially suffices to modify the proof of <ref>
as follows:
Replace all $k_i$ with $\modcont(i+1)+1$, $m_i$ with $i$, and instead of
deterministically picking a point $p \in S_{n+2}$ we check whether $S_{n+2}$
is empty.
If $S_{n+2}$ is empty, then it is a witness for $d_S(q) \geq 2^{-n}$,
while a non-empty $S_{n+2}$ witnesses $d_S(q) \leq 2^{-n+1}$.

§ FUTURE RESEARCH

<Ref> can be understood as the base for further
interesting questions about operators and parameters that render them to be
polynomial-time computable; like the complexity of preimage
$\mathsf{PreImage} \colon (f,S') \mapsto f^{-1}[S']$
<cit.>, or generalizations of the solution operator
for Poisson equations to arbitrary compact domains <cit.>.
We also left open questions raised about the complexity of $\dsoinv$ for more
restricted classes of functions (continuous, smooth, Gevrey
<cit.>); but also about improvements of <ref>.
For example:
Can Ko's construction be modified to produce a smooth function instead of
only a continuous one?
And do Ziegler and McNicholl's computability results on the implicit and
inverse function theorem <cit.> (parameterized)
polynomial-time if restricted to a subset of $\cfn^2$ or Gevrey functions?

§ ACKNOWLEDGEMENTS

I am grateful to Martin Ziegler for continuous advice and many helpful
suggestions; and to Akitoshi Kawamura, Ulrich Kohlenbach, Robert Rettinger,
and Florian Steinberg for seminal discussions, hints and lots of advice.
I also like to express my gratitude to the anonymous referees who have provided
invaluable suggestions on how to improve both the structure of this paper and
the presentation of results plus their respective proofs.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

titleClosed Choice and a Uniform Low Basis Theorem
journaltitleAnnals of Pure and Applied Logic

titleComputational Geometry: Algorithms and Applications

titleEffective Choice and Boundedness Principles in Computable
journaltitleThe Bulletin of Symbolic Logic

booktitleNew Computational Paradigms
titleA Tutorial on Computable Analysis

titleConvex Analysis and Nonlinear Optimization: Theory and

titleComputability on Subsets of Metric Spaces
journaltitleTheoretical Computer Science

titleComputational Complexity of Euclidean Sets: Hyperbolic
Julia-Sets are Poly-Time Computable
University of Toronto

titleHyperbolic Julia Sets are Poly-Time Computable
journaltitleElectronic Notes in Theoretical Computer Science

IEEE Computer Society

booktitleFoundations of Computer Science, 2005. FOCS 2005. 46th
Annual IEEE Symposium on
titleOn the Complexity of Real Functions

* Invalid format of field 'month'

titleComputable Invariance
journaltitleTheoretical Computer Science

titleBegründung der Mengenlehre unabhängig vom logischen
Satz vom ausgeschlossenen Dritten. Zweiter Teil. Verhandelingen Akad.
journaltitleWet. Amsterdam Natuurk. Sect. I

titleComputability on Subsets of Euclidean Space I: Closed and
Compact Subsets
journaltitleTheoretical Computer Science

titleThe Computational Complexity of Distance Functions of
Two-Dimensional Domains
journaltitleTheoretical Computer Science

titleComputational Complexity of Two-Dimensional Regions
journaltitleSIAM Journal on Computing

title10th International Workshop on Computability and Complexity in
Analysis (CCA 2013), Nancy, France, Proceedings

* Invalid format of field 'month'

Springer Heidelberg

titleParameterized Complexity Theory

noteExtended abstract
titleHigher-Order Complexity in Analysis

* Invalid format of field 'month'

Academic Press

titleThe Computational Complexity of Maximization and Integration
journaltitleAdvances in Mathematics

Springer, Berlin

titleGeometric Algorithms and Combinatorial Optimization

titleOn Extreme Points of Convex Compact Turing Located Sets
journaltitleLogical Foundations of Computer Science

titleOn the Definition of Computable Real Continuous Functions
journaltitleFundamenta Mathematicae

titleComplexity Measures for Public-Key Cryptosystems
journaltitleSIAM Journal on Computing

titleEffectivity on Continuous Functions in Topological Spaces
journaltitleElectronic Notes in Theoretical Computer Science

titleA Comparison of certain Representations of Regularly Closed
journaltitleElectronic Notes in Theoretical Computer Science

titleOne-Way Permutations and Self-Witnessing Languages
journaltitleJournal of Computer and System Sciences

titleComputational Complexity in Analysis and Geometry
University of Toronto

titleComplexity Theory for Operators in Analysis
journaltitleACM Transactions on Computation Theory (TOCT)

titleA new Characterization of Type-2 Feasibility
journaltitleSIAM Journal on Computing

titleComputational Complexity of Real Functions
journaltitleTheoretical Computer Science

titleParameterized Uniform Complexity in Numerics: from Smooth to
Analytic, from NP-Hard to Polytime

titleOn Some Natural Completeness Operators
journaltitleSIAM Journal on Computing

Birkhäuser Boston Inc.

titleComplexity Theory of Real Functions

titlePolynomial-Time Computability in Analysis
journaltitleStudies in Logic and the Foundations of Mathematics

titleTheorie der majorisierbaren und stetigen Funktionale und ihre
Anwendungen bei der Extraktion von Schranken aus inkonstruktiven Beweisen:
Effektive Eindeutigkeitsmodule bei besten Approximationen aus ineffektiven
Goethe-Universität Frankfurt (Main)

titleEffective Moduli from ineffective uniqueness proofs. An
Unwinding of de La Vallée Poussin's proof for Chebycheff approximation
journaltitleNum. Funct. Anal. Optim.

titleComputability of Convex Sets

* Invalid format of field 'month'

titleOn the Computational Complexity of Poisson's and Laplace's

* Invalid format of field 'month'

titleOn the Complexity of Convex Hulls of Subsets of the
Two-Dimensional Plane
journaltitleElectronic Notes in Theoretical Computer Science

noteComputability and Complexity in Analysis
titleThe Basic Feasible Functionals in Computable Analysis
journaltitleJournal of Complexity

titleEspaces métriques rationnellement présentés et
complexité, le cas de l’espace des fonctions réelles
uniformément continues sur un intervalle compact
journaltitleTheoretical Computer Science

titleA Uniformly Computable Implicit Function Theorem
journaltitleMathematical Logic Quarterly

titlePolynomial and Abstract Subrecursive Classes
journaltitleJournal of Computer and System Sciences

seriesLecture Notes in Computer Science
titleThe iRRAM: Exact Arithmetic in C++

* Invalid format of field 'month'

noteHabilitation thesis
titleComputability and Complexity Aspects of Univariate Complex

noteExtended abstract
titleComputational Complexity in Analysis

* Invalid format of field 'month'

titleThe Computational Complexity of Some Julia Sets
journaltitleElectronic Notes in Theoretical Computer Science

titleParametrisierte uniforme Berechnungskomplexität in
Geometrie und Numerik

Technische Universität Darmstadt

titleExtended Admissibility
journaltitleTheoretical Computer Science

Academic Press

titleInformation-Based Complexity

titleComputable Analysis: An Introduction

titleRepresentations of the Real Numbers and of the Open Subsets of
the Set of Real Numbers
journaltitleAnnals of Pure and Applied Logic

titleComputability in Linear Algebra
journaltitleTheoretical Computer Science

Wiley Online Library

titleComputable Real-Valued Functions on Recursive Open and Closed
Subsets of Euclidean Space
journaltitleMathematical Logic Quarterly

titleComputability on Regular Subsets of Euclidean Space
journaltitleMathematical Logic Quarterly

Wiley Online Library

titleComputable Operators on Regular Sets
journaltitleMathematical Logic Quarterly

titleEffectively Open Real Functions
journaltitleJournal of Complexity

titleComplexity of Operators on Compact Sets
journaltitleElectronic Notes in Theoretical Computer Science

Hoover, H.J.H.

titleFeasible Real Functions and Arithmetic Circuits
journaltitleSIAM Journal on Computing


# Orthogonalization of Positive Operator Valued Measures

Mikael De La Salle  Université de Lyon, Université Claude Bernard Lyon 1,
CNRS, France<EMAIL_ADDRESS>
###### Abstract.

We show that a partition of the unity (or POVM) on a Hilbert space that is
almost orthogonal is close to an orthogonal POVM in the same von Neumann
algebra. This generalizes to infinite dimension previous results in matrix
algebras by Kempe-Vidick and Ji-Natarajan-Vidick-Wright-Yuen. Quantitatively,
our result are also finer, as we obtain a linear dependance, which is optimal.

We also generalize to infinite dimension a duality result between POVMs and
minimal majorants of finite subsets in the predual of a von Neumann algebra.

MdlS was funded by the ANR grants AGIRA ANR-16-CE40-0022 and Noncommutative
analysis on groups and quantum groups ANR-19-CE40-0002-01

##  1\. Orthonormalization of partitions of unity in infinite dimensional
Hilbert space

Stability is a term coined in [11] to describe a situation when mathematical
objects that almost satisfy certain properties are close to objects exactly
satisfying these properties. It has been recently much studied for groups,
mainly motivated by the question of whether every group is hyperlinear/sofic.
The same phenomena but for quantum strategies for two-player non-local games
are also central in the recent work by Ji-Natarajan-Vidick-Wright-Yuen [4, 6].
The goal of this note is to explore a small portion of [4] and discuss its
possible generalizations to infinite dimension and some consequence in terms
of stability.

The objects that we study in this note are finite families
$(t_{1},\dots,t_{n})$ of positive operators on a complex Hilbert space
$\mathcal{H}$ which sum to the identity: $t_{1}+\dots+t_{n}=1_{\mathcal{H}}$.
They are called _partitions of unity_ by operator algebraists, and _Positive
Operator Valued Measures_ (POVM) by quantum information theorists. We will use
POVM here as it is shorter, and the integer $n$ is called the number of
outputs. And we talk about Projection Valued Measures (PVM) if in addition all
the $t_{i}$’s are projections ($t_{i}^{2}=t_{i}$). The main result of this
note is the following. The question whether a form of this result holds in
infinite dimension answers a question asked by Henry Yuen (private
communication). This result is used in the subsequent work [5].

######  Theorem 1.1.

Let $(a_{1},\dots,a_{n})$ be a POVM on a complex Hilbert space $\mathcal{H}$,
let $\xi\in\mathcal{H}$ be a unit vector and $\varepsilon\in[0,1]$ satisfying
$\sum_{i}\|a_{i}\xi\|^{2}>1-\varepsilon$.

There exists an orthogonal decomposition
$\mathcal{H}=\mathcal{H}_{1}\oplus\mathcal{H}_{2}\oplus\dots\oplus\mathcal{H}_{n}$
such that

  1. (1)

if $\xi_{i}$ denotes the orthogonal projection on $\mathcal{H}_{i}$, then
$\sum_{i}\|a_{i}\xi-\xi_{i}\|^{2}<9\varepsilon$,

  2. (2)

every operator $b\in B(\mathcal{H})$ which commutes with each $a_{i}$
preserves each $\mathcal{H}_{i}$.

In other words, the condition $\sum_{i}\|a_{i}\xi\|^{2}>1-\varepsilon$ implies
that: (1) $(a_{1},\dots,a_{n})$ is $9\varepsilon$-close on $\xi$ to a PVM
$(p_{1},\dots,p_{n})$ (2) which preserves the symmetries of the original POVM.

This theorem generalizes to infinite dimension and slightly strengthens a
result from [4] (see also [8, Lemma 19]), which proves a form of this theorem
with finite dimensional Hilbert spaces. More precisely, we can rephrase [4,
Theorem 5.2] as follows: if
$\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ is a tensor product of
_finite dimensional_ Hilbert spaces and the $a_{i}$ are of the form
$A_{i}\otimes\mathrm{id}_{B}$, then the theorem holds, but with $9\varepsilon$
in (1) (which is essentially optimal, see Remark 1.3) replaced by
$100\varepsilon^{\frac{1}{4}}$. Formally, the conclusion (2) is replaced by a
slightly weaker conclusion, as it only requires that the orthogonal
projections on each factor in the orthogonal decomposition are of the same
tensor product form $P_{i}\otimes\mathrm{id}_{B}$, or equivalently that the
decomposition is of the form

$\mathcal{H}=(\mathcal{H}_{1}\otimes\mathcal{H}_{B})\oplus\dots\oplus(\mathcal{H}_{n}\otimes\mathcal{H}_{B}).$

But the main contribution here is to deal with infinite dimensional Hilbert
spaces.

If one only requires the conclusion (1), Theorem 1.1 becomes a small exercise
in euclidean geometry, and the dimension of $\mathcal{H}$ is irrelevant as
everything happens in the space spanned by the $n$ vectors $a_{i}\xi$. It is
the conclusion (2) that makes the statement dependant on the dimension of
$\mathcal{H}$ and of the structure of the algebra of operators commuting with
$a_{i}$. So, although it is stated in Hilbert-space vocabulary, Theorem 1.1 is
a result about von Neumann algebras and states. This paper might be read by
non-experts in von Neumann algebras, so we will try to recall basic
definitions in section 2, and to give complete proofs or precise references
for the statements we need. We refer to standard textbooks such as [12] for
more background.

The following is an equivalent reformulation of Theorem 1.1 in von Neumann
algebraic language.

######  Theorem 1.2.

Let $\mathcal{M}$ be a von Neumann algebra with a normal state $\varphi$, and
let $(a_{i})$ be a POVM in $\mathcal{M}$ such that
$\varphi(\sum_{i}a_{i}^{2})>1-\varepsilon$.

Then there is a PVM $(p_{i})\subset\mathcal{M}$ (made of projections) such
that $\varphi(\sum_{i}|a_{i}-p_{i}|^{2})<9\varepsilon$.

######  Remark 1.3.

Conversely, if there is a PVM $(p_{i})$ such that
$\sum_{i}\varphi(|a_{i}-p_{i}|^{2})\leq\delta$, then by the triangle
inequality

$\varphi(\sum\nolimits_{i}a_{i}^{2})\geq\bigg{(}1-\sqrt{\varphi(\sum\nolimits_{i}|a_{i}-p_{i}|^{2})}\bigg{)}^{2}\geq
1-2\sqrt{\delta}.$

This could have suggested that the upper bound $9\varepsilon$ in Theorem 1.2
is not optimal and can be replaced by $O(\varepsilon^{2})$. This is not the
case, and the $9\varepsilon$ cannot be replaced by anything smaller than
$\varepsilon$, as the following simple example illustrates.

Consider $\mathcal{M}=\ell_{\infty}^{2}$ ($\mathbf{C}^{2}$ with the
$\ell_{\infty}$ norm), $a_{1}=(1,\frac{1}{2})$ and $a_{2}=(0,\frac{1}{2})$,
and $\varphi$ is the state $\varphi(x,y)=(1-c)x+cy$, then we have

$\varphi(a_{1}^{2}+a_{2}^{2})=1-\frac{1}{2}c,$

and for every PVM $(p_{1},p_{2})$ we have

$\varphi(|p_{1}-a_{1}|^{2})+\varphi(|p_{2}-a_{2}|^{2})\geq\frac{1}{2}c.$

Before we prove the main Theorem 1.2, let us state one consequence, which says
that almost commuting PVMs are close to commuting PVMs.

Let us denote, for an element $a$ in a von Neumann algebra and a normal state
$\varphi$, $\|a\|_{\varphi}=\sqrt{\varphi(a^{*}a)}$.

######  Theorem 1.4.

Let $(p_{i})_{i}$ and $(q_{j})_{j}$ be two PVMs in a von Neumann algebra
$\mathcal{M}$ and $\varphi$ be a normal state on $\mathcal{M}$. If
$\sum_{i,j}\|p_{i}q_{j}-q_{j}p_{i}\|_{\varphi}^{2}<\varepsilon$, then there is
another PVM $(p_{i}^{\prime})_{i}$ in $\mathcal{M}$ such that
$[p^{\prime}_{i},q_{j}]=0$ for every $i,j$ and

$\sum_{i}\|p_{i}-p^{\prime}_{i}\|_{\varphi}^{2}<10\varepsilon.$

By Fourier transform (Pontryagin duality), PVM’s with $n$ outputs are in one-
to-one correspondence with unitaries $u$ of order $n$ ($u^{n}=1$): to
$(p_{1},\dots,p_{n})$ corresponds $u=\sum_{k=1}^{n}e^{\frac{2ik\pi}{n}}p_{k}$.
The inverse maps $u$ to $(p_{1},\dots,p_{n})$ where
$p_{j}=\frac{1}{n}\sum_{k}e^{-\frac{2ijk\pi}{n}}u^{k}$. Therefore, the
previous theorem is formally equivalent to the following. It is a new form of
a statement asserting that almost commuting unitaries are close to unitaries,
that does not seem to be comparable with existing results, even when $\varphi$
is a trace. Comparing with the probabilistic results in [2] for permutation
actions (that Michael Chapman kindly pointed out to me) raises the question
whether there is a form of Corollary 1.5 that is valid for arbitrary amenable
groups and not just $\mathbf{Z}/n\mathbf{Z}\times\mathbf{Z}/m\mathbf{Z}$.

######  Corollary 1.5.

Let $(\mathcal{M},\varphi)$ be a von Neumann algebra with a normal state, and
$u,v\in\mathcal{M}$ be unitaries of finite order $n,m$.

If
$\frac{1}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\|u^{i}v^{j}-v^{j}u^{i}\|_{\varphi}^{2}<\varepsilon$,
then there is a unitary $v^{\prime}\in\mathcal{M}$ that commutes with $u$ and
satisfies

$\frac{1}{n}\sum_{i}\|v^{i}-{v^{\prime}}^{i}\|_{\varphi}^{2}<10\varepsilon.$

The proof of the main result is not very involved and follows the same general
strategy as in [4], but it requires a bit of familiarity with von Neumann
algebras and some adaptations to obtain the optimal order in the constants. We
present the necessary background in Section 2, and then prove the Theorem by
decomposing it into three different cases. We deduce Theorem 1.4 in Section 6.
Finally, Section 7 generalizes to infinite dimensional von Neumann algebras a
semidefinite program considered in [4].

### Acknowledgements

I thank Thomas Vidick and Henry Yuen their patience answering my questions,
and for encouraging me to write down this note. Thanks also to Michael
Chapman, Gilles Pisier and Thomas Vidick for comments and corrections on
preliminary versions of this note. Finally, thanks are due to Gilles Pisier
and the referee who pointed out mistakes in the initial proof of Proposition
7.1 and in my dealing of separability issues respectively. I also thank Amine
Marrakchi for many interesting discussions.

##  2\. Facts on von Neumann algebras

A von Neumann algebra is a self-adjoint subalgebra of the algebra
$B(\mathcal{H})$ of bounded operators on a complex Hilbert space $\mathcal{H}$
that is equal to its bicommutant. Here the _commutant_ of a subset $F\subset
B(\mathcal{H})$ is the algebra $F^{\prime}$ of operators that commute with all
elements of $F$, and its _bicommutant_ is the commutant of its commutant. The
von Neumann bicommutant theorem [12, Theorem II.3.9] is a fundamental result
of the theory, which asserts that the bicommutant of a self-adjoint subset
$F\subset B(\mathcal{H})$ coincides with the weak-* closure of the self-
adjoint unital algebra generated by $F$, where we see $B(\mathcal{H})$ as the
dual of the trace-class operators on $\mathcal{H}$. In particular, a von
Neumann algebra is a dual space. Another fundamental theorem [12, Corollary
III.3.9] asserts that a von Neumann algebra admits a unique predual. This
allows to talk about _the_ weak-* topology on $\mathcal{M}$; it coincides with
the ultraweak operator topology, the smallest topology making continuous all
linear maps of the form $x\mapsto\sum_{k}\langle x\xi_{k},\eta_{k}\rangle$ for
sequences $\xi_{k},\eta_{k}\in\mathcal{H}$ satisfying
$\sum_{k}\|\xi_{k}\|\|\eta_{k}\|<\infty$.

A _normal state_ on a von Neumann algebra $\mathcal{M}\subset B(\mathcal{H})$
is a linear map $\varphi\colon\mathcal{M}\to\mathbf{C}$ that is positive
($\varphi(x^{*}x)\geq 0$ for every $x\in\mathcal{M}$), normalized by
$\varphi(1)=1$ and weak-* continuous. The typical example of a state is a
vector state $x\mapsto\langle a\xi,\xi\rangle$ for a unit vector
$\xi\in\mathcal{H}$. The Gelfand-Naimark-Segal (GNS) construction asserts that
(up to changing the Hilbert space), every normal state can be realized as a
vector state.

We will prove the theorem by a reduction to two main cases (finite and type
III). To state the reduction we need to recall some basic definitions on the
type of a von Neumann algebra (see [12, Chapter V]). Throughout this note, by
projection we always mean self-adjoint projection: $p=p^{*}=p^{2}$. Given a
von Neumann algebra $\mathcal{M}$, we say that

  * •

$\mathcal{M}$ is finite if for every $u\in\mathcal{M}$, $u^{*}u=1$ implies
$uu^{*}=1$. A projection $p\in\mathcal{M}$ is finite if the von Neumann
algebra $p\mathcal{M}p$ is finite.

  * •

$\mathcal{M}$ is of type $\mathrm{II}_{1}$ if it is finite and if $0$ is the
only projection $p\in\mathcal{M}$ such that $p\mathcal{M}p$ is commutative.

  * •

$\mathcal{M}$ is semi-finite if every nonzero projection $p\in\mathcal{M}$
majorizes a non-zero finite projection.

  * •

$\mathcal{M}$ has type III if it does not contain any nonzero finite
projection.

We know from general theory [12, Theorem V.1.19] that every von Neumann
algebra $\mathcal{M}$ can be written as a direct sum of a semifinite and a
type III von Neumann algebra. So it is enough to separately prove Theorem 1.2
when $\mathcal{M}$ is semi-finite and when $\mathcal{M}$ has type III. The
semi-finite case can easily be reduced to the finite case, which is the most
interesting one.

##  3\. Proof of Theorem 1.2 when $\mathcal{M}$ is finite

Let $\mathcal{M},\varphi,(a_{i})$ be as in Theorem 1.2, with $\mathcal{M}$
finite. By [12, Theorem V.2.6], the finiteness assumption is equivalent to the
existence of a _normal center-valued trace_ , that is a normal conditional
expectation $E\colon\mathcal{M}\to Z(\mathcal{M})$ onto the center of
$\mathcal{M}$ such that $E(ab)=E(ba)$ for every $a,b\in\mathcal{M}$.

The first lemma contains all the difficulty in the proof of Theorem 1.2.

######  Lemma 3.1.

There are projections $q_{i}$ commuting with $a_{i}$ such that

(3.1) $\sum_{i=1}^{n}E(q_{i})=1,$ (3.2)
$\varphi\left(\sum_{i=1}^{n}q_{i}a_{i}\right)\geq 1-\varepsilon.$

Before we prove the Lemma, let us observe that it is not possible to replace
(3.1) by the stronger condition $\sum_{i}q_{i}=1$. Indeed, if
$\mathcal{M}=M_{2}(\mathbf{C})$ and if the $a_{i}^{\prime}s$ do not have any
common eigenvector, then the only families $(q_{i})$ of projections commuting
with $a_{i}$ satisfying $\sum_{i}q_{i}=1$ are when one of the $q_{i}$’s is the
identity and the other are $0$, and so (3.2) would become
$\max_{i}\varphi(a_{i})\geq 1-\varepsilon$. A concrete example is given by
$n=3$, $\varphi$ the normalized trace on $M_{2}(\mathbf{C})$ and

$\displaystyle a_{1}$
$\displaystyle=\frac{1}{1+6\delta}\begin{pmatrix}1+4\delta&0\\\
0&0\end{pmatrix},$ $\displaystyle a_{2}$
$\displaystyle=\frac{1}{1+6\delta}\begin{pmatrix}\delta&\sqrt{3}\delta\\\
\sqrt{3}\delta&1+3\delta\end{pmatrix},$ $\displaystyle a_{3}$
$\displaystyle=\frac{1}{1+6\delta}\begin{pmatrix}\delta&-\sqrt{3}\delta\\\
-\sqrt{3}\delta&3\delta\end{pmatrix}.$

This example satisfies $\varphi(\sum_{i}a_{i}^{2})\geq 1-5\delta+o(\delta)$,
but $\max_{i}\varphi(a_{i})\leq\frac{1}{2}$.

###### Proof.

Consider the subset $C\subset\mathcal{M}^{n}$

$C=\\{(x_{1},\dots,x_{n})\in\mathcal{M}^{n}\mid\forall i,0\leq x_{i}\leq
1,x_{i}a_{i}=a_{i}x_{i},\sum\nolimits_{i}E(x_{i})=1\\}.$

$C$ is a convex subset in the unit ball of $\mathcal{M}^{n}$, and contains
$(a_{1},\dots,a_{n})$. It is clearly weak-* closed, and therefore compact as
the unit ball of $\mathcal{M}^{n}$ is weak-* compact. By the Krein-Milman
theorem, $C$ is the closure of the convex hull of its extreme points, and in
particular the continuous affine map

$f\colon(x_{1},\dots,x_{n})\in C\mapsto\varphi(\sum\nolimits_{i}x_{i}a_{i})$

attains its maximum (which is $\geq f(a_{1},\dots,a_{n})\geq 1-\varepsilon$)
at an extreme point.

So all we have to do is to show that

(3.3) if $(x_{1},\dots,x_{n})$ is an extreme point of $C$, then each $x_{i}$
is a projection.

We know from general theory [12, Theorem V.1.19 and V.1.27] that there is a
sequence $(z_{d})_{d\in\mathbf{N}}$ of orthogonal projections in
$Z(\mathcal{M})$ such that $z_{d}\mathcal{M}$ is isomorphic to
$M_{d}(\mathbf{C})\otimes z_{d}Z(\mathcal{M})$ and
$(1-\sum_{d}z_{d})\mathcal{M}$ is of type $\mathrm{II}_{1}$. If $x_{i}$ was
not a projection, then either there is $d\in\mathbf{N}$ such that $z_{d}x_{i}$
is not a projection, or $(1-\sum_{d}z_{d})x_{i}$ is not a projection. So we
are reduced to showing (3.3) when $\mathcal{M}=M_{d}(\mathbf{C})\otimes Z$ for
an abelian von Neumann algebra $Z$, or when $\mathcal{M}$ is of type
$\mathrm{II}_{1}$.

The latter case is easier, as the extremality of $(x_{1},\dots,x_{n})$ in $C$
in particular implies that, for each $i$, $x_{i}$ is extremal inside

$C_{i}:=\\{y_{i}\in\mathcal{M}\mid 0\leq y_{i}\leq
1,y_{i}a_{i}=a_{i}y_{i},E(y_{i})=E(x_{i})\\},$

and this weaker condition already implies that $x_{i}$ is a projection.
Indeed, if $x_{i}$ was not a projection, there would exist $\delta>0$ such
that the spectral projection $p:=\chi_{[\delta,1-\delta]}(x_{i})$ is nonzero
and commutes with $a_{i}$. By the definition of $\mathcal{M}$ being of type
$\mathrm{II}_{1}$, we know that $p\mathcal{M}p$ is not abelian. In particular,
there is a self-adjoint element $b\in p\mathcal{M}p$ which commutes with
$pa_{i}$ but does not belong to $pZ(\mathcal{M})$ (we can take $b=pa_{i}$ if
$pa_{i}\notin pZ(\mathcal{M})$ and an arbitrary selfadjoint element of
$p\mathcal{M}p\setminus pZ(\mathcal{M})$ otherwise). We can moreover assume
that $0\leq b\leq p$. Using that the center valued trace $E:\mathcal{M}\to
Z(\mathcal{M})$ is (completely) positive, we obtain that $0\leq E(b)\leq
E(p)$, and in particular there is $z\in Z(\mathcal{M})$ such that $E(b)=zE(p)$
and $0\leq z\leq 1$. Then $b^{\prime}:=b-zp$ is a nonzero selfadjoint element
of $(\\{pa_{i}\\}^{\prime}\cap p\mathcal{M}p)\setminus pZ(\mathcal{M})$, which
moreover satisfies $E(b^{\prime})=E(b)-zE(p)=0$. It has norm $\leq 1$. So we
can write $x_{i}$ as the midpoint between $x_{i}+\delta b^{\prime}$ and
$x_{i}-\delta b^{\prime}$, which both belong to $C_{i}$. This contradicts the
extremality of $x_{i}$ in $\mathcal{M}$ and proves (3.3) when $\mathcal{M}$ is
of type $\mathrm{II}_{1}$.

In the first case, we can write equivalently
$\mathcal{M}=M_{d}(\mathbf{C})\otimes L_{\infty}(\Omega,\mu)$ for a measure
space $(\Omega,\mu)$ [12, Theorem III.1.18]. We first consider the simpler
situation when $\mathcal{M}=M_{d}(\mathbf{C})$. Then (3.3) becomes that any
extreme point in $\\{(x_{1},\dots,x_{n})\in M_{d}(\mathbf{C})\mid 0\leq
x_{i}\leq 1,[x_{i},a_{i}]=0,\operatorname{Tr}(\sum_{i}x_{i})=d\\}$ is made of
projections. Assume for a contradiction that this is not the case, and that
$(x_{1},\dots,x_{n})$ is an extreme point not entirely made of projections.
If, for some $i$, $x_{i}$ has at least two nonzero eigenvalues different from
$0$ and $1$ (counting with multiplicities), then we can do as in the
$\mathrm{II}_{1}$ case, choose orthogonal rank one projections $p_{1},p_{2}$
corresponding to these eigenvalues of $x_{i}$ and commuting with $a_{i}$, and
for $\delta>0$ small enough the decomposition

$x_{i}=\frac{1}{2}\left((x_{i}+\delta p_{1}-\delta p_{2})+(x_{i}-\delta
p_{1}+\delta p_{2})\right)$

will contradict the extremality. Otherwise, using that
$\sum_{k}\operatorname{Tr}(x_{k})$ is an integer, there are at least two
indices $i\neq j$ such that $x_{i}$ and $x_{j}$ both have exactly one
eigenvalue not in $\\{0,1\\}$, counting multiplicities. In that case, if
$p_{i}$ and $p_{j}$ are the corresponding rank one projections, they
necessarily commute with $a_{i}$ and $a_{j}$ respectively, and we can define
for $\delta\in[-1,1]$

$x_{k}(\delta)=\begin{cases}x_{i}+\delta p_{i}&\textrm{if }k=i\\\ x_{j}-\delta
p_{j}&\textrm{if }k=j\\\ x_{k}&\textrm{if }k\notin{i,j}.\end{cases}.$

For $|\delta|$ small enough $(x_{1}(\delta),\dots,x_{n}(\delta))$ belongs to
$C$, and the expression $x_{k}=\frac{1}{2}(x_{k}(\delta)+x_{k}(-\delta))$ also
contradicts the extremality of $(x_{1},\dots,x_{n})$.

To summarize, when $\mathcal{M}=M_{d}(\mathbf{C})$ we have constructed, for
every $x\in C$ that is not made of projections, two distinct points
$x^{\prime},x^{\prime\prime}\in C$ such that
$x=\frac{1}{2}(x^{\prime}+x^{\prime\prime})$. An inspection of the proof
reveals that the map $x\mapsto(x^{\prime},x^{\prime\prime})$ can be made
Borel-measurable. As a consequence, the proof applies also to
$\mathcal{M}=M_{d}(\mathbf{C})\otimes L_{\infty}(\Omega,\mu)$. ∎

We shall use the following elementary fact about finite von Neumann algebras.

######  Lemma 3.2.

Let $\mathcal{M}$ be a finite von Neumann algebra with center-valued trace
$E$, and $x\in\mathcal{M}$. If $p$ and $q\in\mathcal{M}$ are projections such
that $E(p)=E(q)$ and

$xp=qx=x,$

then we can decompose $x=u|x|$ where $u^{*}u=p$ and $uu^{*}=q$.

###### Proof.

Denote by $p_{0}\in\mathcal{M}$ the left support of $x$ and
$q_{0}\in\mathcal{M}$ the right support of $x$ (that is, if
$\mathcal{M}\subset B(\mathcal{H})$, $p_{0}$ and $q_{0}$ are the smallest
projection in $B(\mathcal{H})$ such that $xp_{0}=x$ and $q_{0}x=x$
respectively). Write $x=u_{0}|x|$ be the usual polar decomposition of $x$,
where $|x|=(x^{*}x)^{1/2}$, and $u_{0}\in\mathcal{M}$ is a partial isometry
with $u_{0}^{*}u_{0}=p_{0}$ and $u_{0}^{*}u_{0}=q_{0}$ (see [1, Proposition
2.2.4]). By definition, we have $p_{0}\leq p$ and $q_{0}\leq q$. Moreover,

$E(p-p_{0})=E(p)-E(u_{0}^{*}u_{0})=E(q)-E(u_{0}u_{0}^{*})=E(q-q_{0}).$

By [1, Proposition 9.1.8], we have that $p-p_{0}\sim q-q_{0}$. That is, there
is a partial isometry $v$ such that $v^{*}v=p-p_{0}$ and $vv^{*}=q-q_{0}$. The
lemma holds with $u=v+u_{0}$. ∎

We can now prove the main result. With Lemma 3.1 and Lemma 3.2 in hand, the
proof is very close to [4].

###### Proof of Theorem 1.2 when $\mathcal{M}$ is finite.

Let $q_{i}$ be given by Lemma 3.1. Consider the matrix
$x=\sum_{i}e_{i,1}\otimes q_{i}a_{i}^{1/2}$, that we see in
$M_{n}(\mathcal{M})$. What is important for us is that $M_{n}(\mathcal{M})$ is
a finite von Neumann algebra. Specifically, its center is $1_{n}\otimes
Z(\mathcal{M})$ and the corresponding central-valued trace is

$E_{n}:(a_{i,j})\mapsto 1_{n}\otimes(\frac{1}{n}\sum\nolimits_{i}E(a_{i,i})).$

Let $p=\sum_{i}e_{i,i}\otimes q_{i}$ and $q=e_{1,1}\otimes 1$. Then
$E_{n}(p)=1_{n}\otimes\frac{1}{n}\sum_{i}E(q_{i})=\frac{1}{n}=E_{n}(q)$, so by
Lemma 3.2 we can write $x=u|x|$ with $uu^{*}=\sum_{i}e_{i,i}\otimes q_{i}$ and
$u^{*}u=e_{1,1}\otimes 1$. In the following, we identify $\mathcal{M}$ with
$\\{e_{1,1}\otimes a\mid a\in\mathcal{M}\\}$. If $t_{i}=e_{i,i}\otimes q_{i}$,
then $u^{*}t_{i}u$ is a projection $p_{i}$ in $\mathcal{M}$ (formally it is of
the form $e_{1,1}\otimes p_{i}$, but we decided to identify this with $p_{i}$)
for projections $p_{i}\in\mathcal{M}$ which sum to $1$. Moreover, we have

$|x|p_{i}|x|=|x|u^{*}t_{i}u|x|=x^{*}t_{i}x=q_{i}a_{i}.$

Let us denote by $\|\cdot\|_{\varphi}$ the norm on $\mathcal{M}^{n}$ given by

$\|(B_{i})_{i}\|_{\varphi}^{2}=\sum\nolimits_{i=1}^{n}\varphi(B_{i}^{*}B_{i}).$

By the triangle inequality, decomposing
$a_{i}-p_{i}=a_{i}-q_{i}a_{i}+(|x|-1)p_{i}|x|+p_{i}(|x|-1)$, we obtain

$\|(a_{i}-p_{i})_{i}\|_{\varphi}\leq\|(a_{i}-q_{i}a_{i})_{i}\|_{\varphi}+\|((1-|x|)p_{i}|x|)_{i}\|_{\varphi}+\|(p_{i}(1-|x|))_{i}\|_{\varphi}.$

We shall bound each term. The first term is easy:

$\|(a_{i}-q_{i}a_{i})_{i}\|_{\varphi}^{2}=\sum_{i}\varphi((1-q_{i})a_{i}^{2})\leq\sum_{i}\varphi((1-q_{i})a_{i})\leq\varepsilon.$

The third term is also easy:

$\|(p_{i}(1-|x|))_{i}\|_{\varphi}^{2}=\sum_{i}\varphi((1-|x|)p_{i}(1-|x|))=\varphi((1-|x|)^{2})\leq\varphi(1-|x|^{2})\leq\varepsilon.$

We used that $(1-|x|)^{2}\leq 1-|x|^{2}$, which is true because $0\leq|x|\leq
1$. For the second term we proceed similarly but with more care:

$\displaystyle\|((1-|x|)p_{i}|x|)_{i}\|_{\varphi}^{2}$
$\displaystyle=\sum_{i}\varphi(|x|p_{i}(1-|x|)^{2}p_{i}|x|)$
$\displaystyle\leq\sum_{i}\varphi(|x|p_{i}(1-|x|^{2})p_{i}|x|)$
$\displaystyle=\sum_{i}\varphi(|x|p_{i}|x|-(|x|p_{i}|x|)^{2}).$

Using that $|x|p_{i}|x|=q_{i}a_{i}$, we obtain

$\|((1-|x|)p_{i}|x|)_{i}\|_{\varphi}^{2}\leq\sum_{i}\varphi(q_{i}(a_{i}-a_{i}^{2}))\leq\sum_{i}(a_{i}-a_{i}^{2})\leq\varepsilon.$

To conclude, we obtain

$\|(a_{i}-p_{i})_{i}\|_{\varphi}\leq 3\sqrt{\varepsilon},$

which is the desired conclusion. ∎

##  4\. Proof of Theorem 1.2 when $\mathcal{M}$ is semi-finite

We deduce easily the case when $\mathcal{M}$ is semi-finite from the finite
case, thanks to the following basic fact.

######  Lemma 4.1.

If $(\mathcal{M},\varphi)$ is a von Neumann algebra with a normal state and
$(p_{\alpha})$ is a net of projections tending to $1$, then for every finite
family $C_{1},\dots,C_{k}\in\mathcal{M}$, we have

$\lim_{\alpha}\varphi(p_{\alpha}C_{1}p_{\alpha}C_{2}\dots
p_{\alpha}C_{k}p_{\alpha})=\varphi(C_{1}C_{2}\dots C_{k}).$

###### Proof.

This follows simply from the fact that, on the unit ball $B$ of $\mathcal{M}$
equipped with the strong operator topology, multiplication $B\times B\to B$ is
continuous.

∎

So let $\mathcal{M},\varphi,(a_{i})$ be as in Theorem 1.2, with $\mathcal{M}$
semi-finite. By [12, Theorem V.1.37]), there is an increasing net $p_{\alpha}$
of finite projections in $\mathcal{M}$ such that $\lim_{\alpha}p_{\alpha}=1$.
Let $\varphi_{\alpha}$ be the state $\frac{1}{\varphi(p_{\alpha})}\varphi$ on
$\mathcal{M}_{\alpha}:=p_{\alpha}\mathcal{M}p_{\alpha}$, and define a POVM
$a_{i,\alpha}=p_{\alpha}a_{i}p_{\alpha}$ in $\mathcal{M}_{\alpha}$. It follows
from Lemma 4.1 that for every $\alpha$ large enough,
$\varphi_{\alpha}(\sum_{i}a_{i,\alpha}^{2})>\varepsilon$, and the (already
proven) finite case of Theorem 1.2 provides us with a PVM $p_{i,\alpha}$ in
$p_{\alpha}\mathcal{M}p_{\alpha}$ satisfying the conclusion of the theorem.
Then for $\alpha$ large enough, the PVM
$(1-p_{\alpha}+p_{1,\alpha},p_{2,\alpha},\dots,p_{n,\alpha})$ satisfies the
conclusion of Theorem 1.2.

##  5\. Proof of Theorem 1.2 when $\mathcal{M}$ is type III

The type III case will be proven with the same strategy as the finite case,
but the details are simpler, and the constants are a bit better (the $9$ can
be replaced by $1$ in that case). We shall need the following. Recall that the
central support of an element $x\in\mathcal{M}$ is the smallest projection
$z(x)$ in the center of $\mathcal{M}$ such that $z(x)x=x$. We shall use the
standard terminology on comparision of projections [12, Chapter V]: we say
that two projections $p,q\in\mathcal{M}$ are equivalent and write $p\sim q$ if
there is $u\in\mathcal{M}$ such that $u^{*}u=p$, $uu^{*}=q$. We write $p\prec
q$ if there is a projection $p^{\prime}$ equivalent to $p$ such that
$q-p^{\prime}$ is positive.

######  Lemma 5.1.

If $\mathcal{M}$ is a type III von Neumann algebra, then there is a net
$(q_{\alpha})$ of projections in $\mathcal{M}$ converging weak-* to $1$ and
such that $1-q_{\alpha}\sim 1$ for every $\alpha$.

###### Proof.

Let $\psi\in\mathcal{M}_{*}$ be a state. In the first step of the proof, we
shall construct an increasing sequence $(q_{k})_{k\in\mathbf{N}}$ of
projections such that $\psi(q_{k})\geq 1-2^{-k}$ and $(1-q_{k})\sim 1$. The
construction is by induction. Define $q_{0}=0$. If $q_{k}$ is defined, then
$(1-q_{k})\mathcal{M}(1-q_{k})$ is of type III, so by [12, Proposition
V.1.36], there is projection $e_{k}\in(1-q_{k})\mathcal{M}(1-q_{k})$ such
that, if $f_{k}=1-q_{k}-e_{k}$, then $e_{k}\sim f_{k}\sim 1-q_{k}$. In
particular, both $f_{k}$ and $e_{k}$ are equivalent to $1$ in $\mathcal{M}$.
Moreover, we have $\psi(e_{k})+\psi(f_{k})=\psi(1-q_{k})\leq 2^{-k}$, so
$\min(\psi(e_{k}),\psi(f_{k}))\leq 2^{-k-1}$. It remains to define
$q_{k+1}=1-e_{k}$ if $\psi(e_{k})\leq\psi(f_{k})$ and $q_{k+1}=1-f_{k}$
otherwise.

This sequence $q_{k}$ depends on $\psi$, so let us denote it $q_{k,\psi}$.

Consider the set $A$ of all finite sets of normal states on $\mathcal{M}$,
ordered by inclusion. For every $\alpha=\\{\psi_{1},\dots,\psi_{d}\\}\in A$,
we define $q_{\alpha}$ to be $q_{d,\psi}$ where
$\psi=\frac{1}{d}\sum_{i=1}^{d}\psi_{i}$. It satisfies
$\psi_{i}(1-q_{\alpha})\geq 1-d2^{-d}$ for every $1\leq i\leq d$. In other
words, the net $(q_{\alpha})$ satisfies $\lim_{\alpha}\psi(q_{\alpha})=1$ for
every normal state $\psi$. That is, it converges to $1$ weak-*. ∎

So let $\mathcal{M},\varphi,(a_{i})$ be as in Theorem 1.2, with $\mathcal{M}$
type III, and let $q_{\alpha}$ be as in the previous lemma. Consider
$v_{\alpha}=\sum_{i}e_{i,1}\otimes a_{i}^{1/2}q_{\alpha}$, that we see in
$M_{n}(\mathcal{M})$. Observe that
$v_{\alpha}^{*}v_{\alpha}=\sum_{i}e_{1,1}\otimes
q_{\alpha}a_{i}q_{\alpha}=e_{1,1}\otimes q_{\alpha}$, so $v_{\alpha}$ is a
partial isometry. It is well-known that the projections $e_{1,1}\otimes 1$ and
$1_{n}\otimes 1$ are equivalent in $M_{n}(\mathcal{M})$. Indeed, it follows
from a repeated use of [12, Proposition V.1.36] that there are isometries
$u_{i}\in\mathcal{M}$ (that is $u_{i}^{*}u_{i}=1$) such that
$1=\sum_{i=1}^{n}u_{i}u_{i}^{*}$. Then $u:=\sum_{i}e_{1,i}\otimes
u_{i}\in\mathcal{M}$ realizes the equivalence between $u^{*}u=1_{n}\otimes 1$
and $uu^{*}=e_{1,1}\otimes 1$. So by the properties of $q_{\alpha}$ given in
Lemma 5.1, we have

$e_{1,1}\otimes 1-v_{\alpha}^{*}v_{\alpha}=e_{1,1}\otimes(1-q_{\alpha})\sim
e_{1,1}\otimes 1\sim 1\textrm{ in }M_{n}(\mathcal{M}).$

In particular, we have

$1_{n}\otimes 1-v_{\alpha}v_{\alpha}^{*}\prec e_{1,1}\otimes
1-v_{\alpha}^{*}v_{\alpha},$

and there is $w_{\alpha}\in M_{n}(\mathcal{M})$ such that
$w_{\alpha}w_{\alpha}^{*}=1_{n}\otimes 1-v_{\alpha}v_{\alpha}^{*}$ and
$w_{\alpha}^{*}w_{\alpha}\leq e_{1,1}\otimes 1-v_{\alpha}^{*}v_{\alpha}$.
Letting $u_{\alpha}=v_{\alpha}+w_{\alpha}$, we therefore have

$u_{\alpha}^{*}u_{\alpha}\leq e_{1,1}\otimes 1,\ \
u_{\alpha}u_{\alpha}^{*}=1_{n}\otimes 1.$

We can therefore define $p_{i,\alpha}\in\mathcal{M}$ by
$u_{\alpha}^{*}(e_{i,i}\otimes 1)u_{\alpha}=e_{1,1}\otimes p_{i,\alpha}$. The
fact that $u_{\alpha}u_{\alpha}^{*}=1$ implies that $p_{i,\alpha}$ are
pairwise orthogonal projections, but a priori we only have
$\sum_{i}p_{i,\alpha}\leq 1$. However, the sum is close to $1$ as

(5.1) $e_{1,1}\otimes(\sum_{i}p_{i,\alpha})=u_{\alpha}^{*}u_{\alpha}\geq
v_{\alpha}^{*}v_{\alpha}=e_{1,1}\otimes q_{\alpha}.$

Moreover, by the definition of $p_{i,\alpha}$, we have

$\displaystyle e_{1,1}\otimes q_{\alpha}p_{i,\alpha}q_{\alpha}$
$\displaystyle=v_{\alpha}^{*}v_{\alpha}u_{\alpha}^{*}(e_{i,i}\otimes
1)u_{\alpha}v_{\alpha}^{*}v_{\alpha}$
$\displaystyle=v_{\alpha}^{*}(e_{i,i}\otimes 1)v_{\alpha}$
$\displaystyle=e_{1,1} \otimes q_{\alpha}a_{i}q_{\alpha}.$

That is,

(5.2) $q_{\alpha}p_{i,\alpha}q_{\alpha}=q_{\alpha}a_{i}q_{\alpha}.$

As in the finite case, let us denote by $\|\cdot\|_{\varphi}$ the norm on
$\mathcal{M}^{n}$ given by

$\|(b_{i})_{i}\|_{\varphi}^{2}=\sum_{i=1}^{n}\varphi(b_{i}^{*}b_{i}).$

Remembering (5.2), we can decompose
$a_{i}-p_{i,\alpha}=a_{i}-q_{\alpha}a_{i}q_{\alpha}-(1-q_{\alpha})p_{i,\alpha}q_{\alpha}-p_{i,\alpha}(1-q_{\alpha})$
and obtain by the triangle inequality

$\|(a_{i}-p_{i,\alpha})_{i}\|_{\varphi}\leq\|(a_{i}-q_{\alpha}a_{i}q_{\alpha})_{i}\|_{\varphi}+\|((1-q_{\alpha})p_{i,\alpha}q_{\alpha})_{i}\|_{\varphi}+\|(p_{i,\alpha}(1-q_{\alpha}))_{i}\|_{\varphi}.$

It follows from Lemma 4.1 that the first term goes to $0$ as
$\alpha\to\infty$. The last term is straightforward to bound:

$\|(p_{i,\alpha}(1-q_{\alpha}))_{i}\|_{\varphi}^{2}=\varphi((1-q_{\alpha})(\sum_{i}p_{i,\alpha})(1-q_{\alpha}))\leq\varphi(1-q_{\alpha})\to
0.$

The middle term is bounded as follows

$\displaystyle\|((1-q_{\alpha})p_{i,\alpha}q_{\alpha})_{i}\|_{\varphi}^{2}$
$\displaystyle=\sum_{i}\varphi(q_{\alpha}p_{i,\alpha}(1-q_{\alpha})p_{i,\alpha}q_{\alpha})$
$\displaystyle=\sum_{i}\varphi(q_{\alpha}a_{i}q_{\alpha}-(q_{\alpha}a_{i}q_{\alpha})^{2}),$

which goes to $\sum_{i}\varphi(a_{i}-a_{i}^{2})<\varepsilon$. All in all, this
implies that

$\limsup_{\alpha}\|(a_{i}-p_{i,\alpha})_{i}\|_{\varphi}<\sqrt{\varepsilon}.$

We are not completely done yet, as $p_{i,\alpha}$ do not sum to $1$. But
almost. Indeed, by (5.1), we have $\sum_{i}p_{i,\alpha}$ converges to $1$ and
in particular

$\lim_{\alpha}\varphi(\sum_{i}p_{i,\alpha})=1.$

This implies that if we replace $p_{1,\alpha}$ by
$p_{1,\alpha}+(1-\sum_{i}p_{i,\alpha})$, we obtain a PVM in $\mathcal{M}$
which still satisfies

$\limsup_{\alpha}\|(a_{i}-p_{i,\alpha})_{i}\|_{\varphi}<\sqrt{\varepsilon}.$

This concludes the proof of the Theorem in the type III case.

##  6\. Almost commuting PVMs are close to commuting PVMS

This short section is devoted to the proof of Theorem 1.4.

Denote by $(a_{i})$ the POVM $a_{i}=\sum_{j}q_{j}p_{i}q_{j}$. We can compute

$\displaystyle\varepsilon$
$\displaystyle>\sum_{i,j}\|p_{i}q_{j}-q_{j}p_{i}\|_{\varphi}^{2}$
$\displaystyle=\varphi(\sum_{i,j}p_{i}q_{j}p_{i}+q_{j}p_{i}q_{j}-(p_{i}q_{j})^{2}-(q_{j}p_{i})^{2})$
$\displaystyle=2-2\Re(\sum_{i}\varphi(a_{i}p_{i}))$
$\displaystyle=\sum_{i}\|p_{i}-a_{i}\|_{\varphi}^{2}+(1-\varphi(\sum_{i}a_{i}^{2})).$

We can apply Theorem 1.2 to the $a_{i}$ in the von Neumann algebra
$\mathcal{N}$ generated by the $a_{i}$’s, and obtain a PVM $p^{\prime}_{i}$
belonging to $\mathcal{N}$ such that

$\sum_{i}\|a_{i}-p^{\prime}_{i}\|_{\varphi}^{2}<9(\varepsilon-\sum_{i}\|p_{i}-a_{i}\|_{\varphi}^{2}).$

But since $a_{i}$ belongs to the commutant of $\\{q_{j}\\}$, the same is true
for $\mathcal{N}$, so $[p^{\prime}_{i},q_{j}]=0$ for all $i,j$. Using the
triangle inequality and the Cauchy-Schwarz inequality, we conclude as follows

$\displaystyle\left(\sum_{i}\|p_{i}-p^{\prime}_{i}\|_{\varphi}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq\left(\sum_{i}\|p_{i}-a_{i}\|_{\varphi}^{2}\right)^{\frac{1}{2}}+\left(\sum_{i}\|a_{i}-p^{\prime}_{i}\|_{\varphi}^{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq\sqrt{10}\left(\sum_{i}\|p_{i}-a_{i}\|_{\varphi}^{2}+\frac{1}{9}\|a_{i}-p^{\prime}_{i}\|_{\varphi}^{2}\right)^{\frac{1}{2}}$
$\displaystyle<\sqrt{10\varepsilon}.$

##  7\. Hahn-Banach

We conclude this note with a quite unrelated subject, except that it is also
an infinite dimensional generalization of a key result in [4], and that is is
also used in [5].

Lemma 9.2 in [4] states that for any finite collection $a_{1},\dots,a_{n}$ of
positive matrices,

(7.1) $\min\\{\operatorname{tr}(z)\mid z\geq a_{i}\forall
i\\}=\max\\{\sum_{i}\operatorname{tr}(a_{i}t_{i})\mid 0\leq t_{i}\leq
1,\sum_{i}t_{i}=1\\},$

and that moreover any pair of minimizer $z$ and maximizer
$(t_{1},\dots,t_{n})$ satisfies

(7.2) $z=\sum_{i}t_{i}a_{i}.$

The equality in (7.1) is known to be true more generally in any semifinite von
Neumann algebra, as a particular case of a duality for Pisier’s operator-space
valued non-commutative $L_{p}$ spaces $L_{p}(\mathcal{M};\ell_{\infty})$ [9].
Formula (7.1) corresponds to the case $p=1$ and
$\mathcal{M}=M_{n}(\mathbf{C})$ in [7, Proposition 2.1 (iii)]. To the author’s
knowledge, (7.2) has not been observed or used earlier in operator space
theory.

It turns out that the preceding is true more generally in arbitrary von
Neumann algebras, as follows. For $t\in\mathcal{M}$ and
$\varphi\in\mathcal{M}_{*}$, we use the standard notation
$t\varphi\in\mathcal{M}_{*}$ and $\varphi t\in\mathcal{M}_{*}$ to denote the
linear forms $x\mapsto\varphi(xt)$ and $x\mapsto\varphi(tx)$ respectively.

######  Proposition 7.1.

Let $\mathcal{M}$ be a von Neumann algebra, and
$\varphi_{1},\dots,\varphi_{n}\in(\mathcal{M}_{*})_{+}$ be normal positive
linear forms. Then

(7.3) $\inf\\{\psi(1)\mid\psi\in\mathcal{M}_{*},\psi\geq\varphi_{i}\forall
i\\}=\sup\\{\sum_{i}\varphi_{i}(t_{i})\mid(t_{i})\textrm{POVM in
}\mathcal{M}\\}.$

Moreover, the infimum and the supremum are both attained, and any pair of a
minimizer $\psi$ and a maximizer $(t_{1},\dots,t_{n})$ satisfies
$t_{i}\psi=t_{i}\varphi_{i}$, $\psi t_{i}=\varphi_{i}t_{i}$and
$\psi=\sum_{i}t_{i}\varphi_{i}=\sum_{i}\varphi_{i}t_{i}$.

######  Corollary 7.2.

For every $\varphi_{1},\dots,\varphi_{n}\in(\mathcal{M}_{*})_{+}$, there is a
unique element of $\mathcal{M}_{*}$ of minimal norm such that
$\psi\geq\varphi_{i}$ for all $i$.

Moreover, there is a POVM $t_{1},\dots,t_{n}\in\mathcal{M}$ such that
$\psi=\sum_{i}t_{i}\varphi_{i}$.

###### Proof of Proposition 7.1.

The inequality $\geq$ in (7.3) is clear: if $t_{1},\dots,t_{n}\in\mathcal{M}$
is any POVM and $\psi\geq\varphi_{i}$ for all $i$, then

$\sum_{i}\varphi_{i}(t_{i})\leq\sum_{i}\psi(t_{i})=\psi(1).$

The converse relies on Hahn-Banach. We rather use the variant given in [10,
Lemma A.16]. Define

$m:=\inf\\{\psi(1)\mid\psi\in\mathcal{M}_{*},\psi\geq\varphi_{i}\forall i\\}.$

Consider the weak-* closed convex subset of $\mathcal{M}^{n+1}$

$S=\\{(t_{0},\dots,t_{n})\in\mathcal{M}^{n+1}\mid 0\leq t_{i}\leq 1\forall
i\\},$

and for every self-adjoint $\psi\in\mathcal{M}_{*}$, define
$f_{\psi}\in\ell_{\infty}(S)$ by

$f_{\psi}(t_{0},\dots,t_{n})=\psi(t_{0})-m+\sum_{i=1}^{n}(\varphi_{i}-\psi)(t_{i}).$

We claim that $\sup_{S}f_{\psi}\geq 0$. Indeed, it is a general fact that if a
self-adjoint element $\rho\in\mathcal{M}_{*}$ has Jordan decomposition
$\rho=\rho_{+}-\rho_{-}$ (see [12, Theorem III.4.2]), then $\sup_{0\leq t\leq
1}\rho(t)=\|\rho_{+}\|=\rho_{+}(1)$. In our situation, we obtain

$\sup_{S}f_{\psi}=\left(\psi_{+}+\sum_{i=1}^{n}(\varphi_{i}-\psi)_{+}\right)(1)-m.$

For every $1\leq j\leq n$, using that $\psi_{+}\geq\psi$,
$(\varphi_{j}-\psi)_{+}\geq\varphi_{j}-\psi$ and $(\varphi_{i}-\psi)_{+}\geq
0$ for $i\neq j$, we see that

$\psi_{+}+\sum_{i=1}^{n}(\varphi_{i}-\psi)_{+}\geq\varphi_{j}.$

By the definition of $m$, this implies $\sup_{S}f_{\psi}\geq 0$ as claimed.

Consider now the convex cone $\mathcal{F}\subset\ell_{\infty}(S)$ generated by
the _convex_ set $\\{f_{\psi}\mid\psi=\psi^{*}\in\mathcal{M}_{*}\\}$ :

$\mathcal{F}=\\{\lambda
f_{\psi}\mid\psi=\psi^{*}\in\mathcal{M}_{*},\lambda\in(0,\infty)\\}.$

The elements of $\mathcal{F}$ are affine weak-* continuous maps on $S$, and we
have just proved that $\forall f\in\mathcal{F}$, $\sup_{S}f\geq 0$. We can
therefore apply [10, Lemma A.16] and obtain $(t_{0},\dots,t_{n})\in S$ such
that $f_{\psi}(t_{0},\dots,t_{n})\geq 0$ for every self-adjoint
$\psi\in\mathcal{M}_{*}$. Equivalently,

$\psi(t_{0}-\sum_{1}^{n}t_{i})+\sum_{1}^{n}\varphi_{i}(t_{i})\geq m.$

This implies that $t_{0}=\sum_{1}^{n}t_{i}$, and that
$\sum_{1}^{n}\varphi_{i}(t_{i})\geq m$. In other words, we have obtained
positive elements $(t_{1},\dots,t_{n})\in\mathcal{M}$ such that
$\sum_{i}t_{i}\leq 1$ and $\sum_{i}\varphi_{i}(t_{i})\geq m$. A fortiori (say
replacing $t_{n}$ by $t_{n}+(1-\sum_{1}^{n}t_{i})$), there are positive
$t_{i}$ with $\sum_{i}t_{i}=1$ and $\sum_{i}\varphi_{i}(t_{i})\geq m$. This
proves at the same time the inequality $\leq$ in (7.3) and that the supremum
in (7.3) is attained.

Let us justify that the infimum is also attained. By the weak-* compactness of
the unit ball of $\mathcal{M}^{*}$, we have that the infimum of $\psi(1)$ over
all $\psi\in\mathcal{M}^{*}$ such that $\psi\geq\varphi_{i}$ for all $i$ is
attained at some $\psi\in\mathcal{M}^{*}$. But using that $\mathcal{M}_{*}$ is
$L$-embedded in $\mathcal{M}^{*}$ [12, Theorem III.2.14], we obtain that
$\psi$ necessarily belongs to $\mathcal{M}_{*}$.

Consider now $\psi$ attaining the infimum, and $(t_{1},\dots,t_{n})$ attaining
the supremum in (7.3). We then have

$\sum_{i}(\psi-\varphi_{i})(t_{i})=0.$

This implies (since $(\psi-\varphi_{i})(t_{i})\geq 0$ is clear) that
$(\psi-\varphi_{i})(t_{i})=0$ for all $i$. By the Cauchy-Schwarz inequality,
we obtain that for every $x\in\mathcal{M}$,

$|(\psi-\varphi_{i})(xt_{i})|^{2}=|(\psi-\varphi_{i})(xt_{i}^{1/2}t_{i}^{1/2})|^{2}\leq(\psi-\varphi_{i})(t_{i})(\psi-\varphi_{i})(xt_{i}x^{*})=0.$

Hence $t_{i}(\psi-\varphi_{i})=0$. Summing over $i$ we also obtain
$\sum_{i}t_{i}\varphi_{i}=\sum_{i}t_{i}\psi=\psi$. Taking the adjoints we
deduce $\psi t_{i}=\varphi_{i}t_{i}$. ∎

## References

  * [1] Claire Anantharaman and Sorin Popa  An introduction to $\mathrm{II}_{1}$ factors,  Book available https://www.idpoisson.fr/anantharaman/publications/IIun.pdf.
  * [2] Oren Becker and Michael Chapman  Stability of approximate group actions: uniform and probabilistic,  arXiv:2005.06652.
  * [3] Richard Kadison and John Ringrose  Fundamentals of the theory of operator algebras. Vol. I.,  Pure and Applied Mathematics, 100. Academic Press, Inc. New York, 1983
  * [4] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen  Quantum soundness of the classical low individual degree test,  arXiv:2009.12982.
  * [5] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen  Quantum soundness of testing tensor codes,  Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, 2021.  arXiv:2111.08131
  * [6] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen  MIP*=RE,  arXiv:2001.04383.
  * [7] Marius Junge and Quanhua Xu  Noncommutative maximal ergodic theorems,  J. Amer. Math. Soc. 20 (2007) 2 385–439.
  * [8] Julia Kempe and Thomas Vidick  Parallel repetition of entangled games,  In Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11 (2011) 353–362.
  * [9] Gilles Pisier  Non-commutative vector valued $L_{p}$-spaces and completely $p$-summing maps,  Astérisque 247 (1998).
  * [10] Gilles Pisier  Tensor Products of C*-Algebras and Operator Spaces – The Connes-Kirchberg Problem,  Cambridge University Press, 2020.
  * [11] Stanisław Ulam  A collection of mathematical problems,  Interscience Tracts in Pure and Applied Mathematics, no. 8, 1960
  * [12] Masamichi Takesaki  Theory of operator algebras. I,  Springer-Verlag, New York-Heidelberg (1979).