⚛️ quantum physics

The Universal Theory of Locally Universal Tracial von Neumann Algebras is not Computable

Building on Lin's breakthrough result that MIP $^{co}$ = coRE, this paper proves that the universal theories of locally universal tracial von Neumann algebras are undecidable, thereby establishing the existence of explicit separable II $_1$ factors without computable presentations and providing strong evidence for a negative solution to the Kirchberg Embedding Problem.

Original authors: Jananan Arulseelan, Aareyan Manzoor

Published 2026-04-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Jananan Arulseelan, Aareyan Manzoor

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the universe of mathematics as a giant library. Inside this library, there are special books called von Neumann algebras. These aren't books you read with words; they are complex mathematical structures used to describe quantum mechanics and the behavior of particles.

For decades, mathematicians had a big question about these books: "Can we write a perfect, step-by-step instruction manual (an algorithm) for any of these structures?"

This paper, by Jananan Arulseelan and Aareyan Manzoor, says: No. For a specific, very important type of these structures, it is impossible to write that manual.

Here is the breakdown using simple analogies.

1. The "Universal Translator" (The Locally Universal Algebra)

Imagine you have a magical dictionary called S. This dictionary is special because it contains the "essence" of every other book in the library. If you have a book about quantum physics, a book about group theory, or any other mathematical structure, you can find a copy of it inside S.

Mathematicians call this a "locally universal" algebra. It's the ultimate "Swiss Army Knife" of this field. For a long time, they wondered: If we have this ultimate dictionary, can we program a computer to understand it perfectly?

2. The "Halting Problem" (The Unsolvable Puzzle)

To understand why the answer is "No," we need to look at a famous computer science puzzle called the Halting Problem.

Imagine you have a computer program. You want to know: Will this program run forever, or will it eventually stop and give you an answer?
In the 1930s, Alan Turing proved that no computer program can ever solve this for every other program. It is fundamentally impossible.

3. The Connection: Games and Math

The authors found a clever way to link the "Halting Problem" to the "Universal Dictionary."

The Setup: They created a special type of game (a "non-local game") involving two players, Alice and Bob, who are far apart but trying to coordinate answers without talking.
The Twist: They proved that the best possible score Alice and Bob can get in this game depends entirely on whether a specific computer program halts or runs forever.
- If the program never stops, the best score is 100%.
- If the program stops, the best score drops to 50%.

4. The "Magic Sentence"

Here is the magic trick: The authors translated this game into a mathematical sentence (a formula) that can be written in the language of these von Neumann algebras.

If the computer program runs forever, this sentence evaluates to 1.
If the computer program stops, this sentence evaluates to 0.5.

Because the "Universal Dictionary" (the locally universal algebra) contains every possible mathematical structure, it must be able to evaluate this sentence to the highest possible value (which is 1 if the program runs forever).

5. The Grand Conclusion

Now, imagine you have a computer trying to calculate the value of this sentence for the Universal Dictionary.

The computer tries to calculate the value.
If it finds the value is 1, it knows the program never stops.
If it finds the value is 0.5, it knows the program stops.

But wait! We already know from Turing that no computer can tell us if a program stops or not.

Therefore, no computer can calculate the value of this sentence for the Universal Dictionary.

What Does This Mean?

No "Instruction Manual": You cannot create a computer program that fully describes or "computes" this Universal Dictionary. It is too complex, too chaotic, and too deep.
The Library is Broken: It turns out that the "Universal Dictionary" (which we thought was a neat, orderly structure) is actually a chaotic mess that defies algorithmic description.
New Examples: The authors didn't just prove this for one weird case. They showed that there are entire families of these mathematical structures (including ones with specific properties like "McDuff factors") that are all impossible to compute.

The Big Picture

Think of it like trying to build a perfect map of a city that is constantly changing its own streets. No matter how good your GPS is, it can never catch up to the city because the city's layout is tied to the unsolvable "Halting Problem."

This paper proves that for a huge class of mathematical objects used in quantum physics, there is no perfect, computer-readable blueprint. They are inherently "uncomputable." This is a massive discovery because it tells us that the universe of these mathematical structures is far more mysterious and resistant to our digital tools than we ever imagined.

1. Problem Statement and Context

The paper addresses fundamental questions in the computable model theory of operator algebras, specifically concerning the decidability and computability of the universal theory of tracial von Neumann algebras.

Background: The Connes Embedding Problem (CEP) asked whether every separable tracial von Neumann algebra embeds into an ultrapower of the hyperfinite $II_1$ factor ( $R$ ). This was resolved negatively by Ji et al. (2020) via the result $MIP^* = RE$ , which implies that the universal theory of $R$ is undecidable.
The Gap: While $MIP^* = RE$ established undecidability for the class of Connes-embeddable algebras, the status of the class of all tracial von Neumann algebras remained less clear regarding uniform approximation properties.
The Core Question: Does there exist a locally universal tracial von Neumann algebra (an algebra $S$ into which every separable tracial von Neumann algebra embeds into an ultrapower) that admits a computable presentation? Furthermore, is the universal theory of such an algebra computable?
Motivation: A locally universal algebra exists (e.g., Sherman's $S$ factor, constructed via compactness arguments). If such an algebra had a computable presentation, it would imply that the universal theory of the entire class of tracial von Neumann algebras is effectively approximable, contradicting recent complexity-theoretic breakthroughs.

2. Methodology

The authors employ a synthesis of quantum complexity theory, continuous model theory, and operator algebra techniques.

A. Theoretical Foundation: $MIP_{co} = coRE$

The paper builds upon a recent breakthrough by Lin (2025), who announced a proof that $MIP_{co} = coRE$ .

$MIP_{co}$ refers to the complexity class of languages decidable by a multi-prover interactive proof system with quantum commuting provers.
$coRE$ is the class of co-recursively enumerable languages (complements of recursively enumerable sets).
Implication: This equivalence implies that the "quantum commuting value" of non-local games can encode the halting problem in a specific way: for any Turing machine $M$ , one can construct a game $G_M$ where the winning probability is 1 if $M$ does not halt, and $\leq 1/2$ if $M$ halts.

B. Encoding Games into Logic

The authors translate the algebraic properties of non-local games into the language of continuous logic for tracial von Neumann algebras:

Non-local Games: They define synchronous non-local games $G = (Q, A, \mu, D)$ .
Algebraic Representation: Strategies are represented by Projection-Valued Measures (PVMs) $\{e^a_x\}$ in a tracial von Neumann algebra $(N, \tau)$ .
Universal Sentences: They construct a formula $\psi_G(\bar{e})$ $ψ_{G} (\overset{e}{ˉ})$ representing the winning probability of the game. By taking the supremum over all possible PVMs in all tracial von Neumann algebras, they define a restricted universal sentence $\sigma_M$ $σ_{M}$ .
- $\sigma_M$ is computable from the description of the Turing machine $M$ .
- The value $\sup_N \sigma_M^N$ corresponds exactly to the quantum commuting value $\omega_{co}^s(G_M)$ .

C. Definability and Stability

A crucial technical step involves proving that the set of valid PVMs is a definable set in continuous logic.

They utilize stability results (from Salter and KPS) to show that if a tuple of operators approximately satisfies the PVM relations (in the 2-norm), it is close to an actual PVM.
This ensures that the supremum over "approximate" solutions equals the supremum over exact solutions, allowing the game value to be captured strictly by a universal sentence.

3. Key Contributions and Results

A. Undecidability of Universal Theories

Theorem: The universal theory of any locally universal tracial von Neumann algebra is not computable.

Proof Sketch: If the universal theory of a locally universal algebra $S$ were computable, one could algorithmically determine the value of $\sigma_M^S$ for any Turing machine $M$ . Since $\sigma_M^S = \sup_N \sigma_M^N$ (by local universality), this value would distinguish between halting and non-halting machines (1 vs. $\leq 1/2$ ). This solves the Halting Problem, a contradiction.
Consequence: The class of tracial von Neumann algebras admits no uniform approximation property that allows algorithmic approximation of universal sentences from below.

B. Non-Existence of Computable Presentations

Theorem: No locally universal tracial von Neumann algebra admits a computable presentation.

Definition: A computable presentation allows a computer to compute the 2-norm of any "rational point" (polynomial in special points) to arbitrary precision.
Logic: If an algebra $S$ had a computable presentation, its universal theory would be computable (a known result in computable model theory). Since the universal theory is proven undecidable, no such presentation exists.
Significance: This provides the first explicit examples of separable $II_1$ factors without computable presentations. While cardinality arguments suggest "most" factors are non-computable, this paper constructs specific, natural families of them.

C. Broad Families of Counterexamples

The authors demonstrate that this phenomenon is not isolated to a single pathological example but applies to broad, natural subclasses of $II_1$ factors:

McDuff factors ( $S \otimes R$ ).
Factors with neither Property $\Gamma$ nor Property (T) ( $S * R$ ).
Factors with Property (T) (via embedding $S$ into a Property (T) factor).

D. Extensions to Other Classes

Semifinite von Neumann Algebras: Using the framework of general von Neumann algebras, they show that locally universal semifinite algebras (e.g., $S \otimes B(H)$ ) also have non-computable universal theories and no computable presentations.
Tracial $C^*$ -algebras: They extend the results to tracial $C^*$ $C^{*}$ -algebras. This is significant because the Kirchberg Embedding Problem (KEP) asks if every separable $C^*$ $C^{*}$ -algebra embeds into an ultrapower of the Cuntz algebra $\mathcal{O}_2$ $O_{2}$ .
- $\mathcal{O}_2$ is known to have a computable presentation.
- If the authors' methods could be extended to general (non-tracial) $C^*$ -algebras, it would imply that a locally universal $C^*$ -algebra cannot have a computable presentation. Since $\mathcal{O}_2$ does have one, $\mathcal{O}_2$ would not be locally universal, resolving KEP negatively.

4. Significance and Implications

Resolution of Approximation Properties: The results definitively rule out the existence of a "nice" approximation property for the entire class of tracial von Neumann algebras. Unlike the Connes-embeddable class (where finite-dimensional matrix algebras provided an approximation), the general class is too complex to be algorithmically approximated.
Computability in Operator Algebras: This work marks a paradigm shift in the computable model theory of operator algebras. It moves from asking "Is this specific algebra computable?" to proving that "The most universal objects in the category are inherently uncomputable."
Connection to Complexity Theory: The paper solidifies the bridge between quantum complexity ( $MIP_{co} = coRE$ ) and the structural properties of operator algebras. It shows that the undecidability of the halting problem manifests directly as the undecidability of the universal theory of the "largest" algebras in the category.
Kirchberg Embedding Problem: While the paper stops short of solving KEP (due to the reliance on traces), it provides the strongest evidence to date for a negative solution. It isolates the exact obstruction: the tension between the computability of $\mathcal{O}_2$ and the uncomputability of locally universal structures.

Summary Conclusion

Arulseelan and Manzoor prove that the universal theory of locally universal tracial von Neumann algebras is undecidable and that no such algebra admits a computable presentation. By encoding the halting problem into the values of universal sentences via non-local games (leveraging $MIP_{co} = coRE$ ), they demonstrate that the class of all tracial von Neumann algebras lacks any uniform algorithmic approximation property. This result generates a vast family of non-computable $II_1$ factors and strongly suggests that the Kirchberg Embedding Problem has a negative solution.