Exhibiting a non-sofic or non-hyperlinear group: the soficity problem sharpened by MIP* = RE

The quantum-complexity theorem MIP* = RE (Ji–Natarajan–Vidick–Wright–Yuen, 2021) refuted Connes' embedding problem through Tsirelson's problem, and Section 1.4 of the paper explicitly asks whether the construction 'can eventually lead to a construction of a group that is not sofic, or even not hyperlinear'. The open problem is to exhibit an explicit, ideally finitely presented, group that is not sofic (weakest form, refuting the soficity conjecture) or not hyperlinear (stronger form), or to prove that every group is sofic/hyperlinear. The problem is open: no non-sofic and no non-hyperlinear group is known to exist, even nonconstructively; adjacent invariant-random-subgroup analogues were resolved negatively in 2024–2025 and explicit non-Connes-embeddable operator algebras now exist, but the routes currently available to a group counterexample remain conditional.

Background

A nonlocal game is a one-round test in which a verifier sends questions $x$ and $y$ to two isolated provers, who reply with answers $a$ and $b$; the verifier accepts according to a fixed public predicate $V(a,b,x,y)$. The classical value of the game is the maximum acceptance probability over deterministic provers; the entangled value $\operatorname{val}^*(G)$ allows the provers to share arbitrary finite-dimensional entanglement (a quantum state on which they perform measurements), and the commuting-operator value $\operatorname{val}^{co}(G)$ allows the more general commuting-operator model of infinite-dimensional shared quantum resources. MIP* is the complexity class of languages decidable by such two-prover one-round protocols with entangled provers. Ji, Natarajan, Vidick, Wright and Yuen proved MIP* = RE, the class of recursively enumerable languages, by an iterated 'gap-preserving compression' procedure; the halting problem (indeed, any RE language) is encoded into a game that is perfect in the commuting-operator model but far from perfect for entangled provers. The construction needs 'anchored parallel repetition' — a transformation of Bavarian, Vidick and Yuen in which each repeated question is replaced with a fixed dummy question with small probability — because ordinary parallel repetition (playing $k$ independent simultaneous copies and accepting only if all accept) is not known to exponentially decrease $\operatorname{val}^*$ for arbitrary games.

The complexity result feeds a long-standing problem in operator algebras. A von Neumann algebra is a self-adjoint algebra of bounded operators on a Hilbert space, closed in the weak operator topology; a type II$_1$ factor is an infinite-dimensional one with trivial center and a faithful trace; the hyperfinite II$_1$ factor $R$ is the unique one approximable by finite-dimensional matrices in trace norm. Connes' embedding problem (CEP) asked whether every type II$_1$ factor embeds into some ultrapower $R^{\mathcal{U}}$ of $R$ (an elementary limiting construction). Tsirelson's problem asked whether the finite-dimensional (tensor-product) and commuting-operator correlation sets of quantum mechanics coincide, i.e. whether $\operatorname{val}^* = \operatorname{val}^{co}$ for all games in the appropriate formulation. Fritz, and independently Junge et al., showed that a positive answer to CEP would imply a positive answer to Tsirelson's problem, so the explicit MIP* = RE game with $\operatorname{val}^*(G) < \operatorname{val}^{co}(G) = 1$ refutes both. The paper's discussion notes, however, that the refutation is only semi-explicit, and poses further algebraic targets that its techniques do not reach.

The group-theoretic target sits in sofic group theory, introduced by Gromov and named by Weiss (see the account and references in Capraro–Lupini and in Goldbring's surveys). A countable discrete group $G$ is sofic if, for every finite subset $F \subseteq G$ and every $\varepsilon > 0$, there is an integer $n$ and a map $\varphi: F \to S_n$ into the symmetric group (equipped with the normalized Hamming metric measuring the fraction of points on which two permutations disagree) that is approximately multiplicative, $\varphi(g)\varphi(h) \approx \varphi(gh)$, and approximately injective on $F$. Replacing the symmetric groups $S_n$ by unitary groups $U(n)$ with the normalized Hilbert–Schmidt metric defines hyperlinear groups. Every sofic group is hyperlinear (realize permutations by permutation matrices), so a non-hyperlinear group is automatically non-sofic. Amenable groups, residually finite groups, linear groups, and hyperbolic groups are all known to be sofic; whether every group is sofic (the soficity problem) has been open for over two decades, and several major conjectures — among them Gottschalk's surjunctivity conjecture (every injective shift-commuting continuous self-map of a configuration space over the group is surjective) and Lück's determinant conjecture (a lower bound on Fuglede–Kadison determinants, the von Neumann-algebraic analogue of ordinary determinants, for matrices over the group ring) — are known to hold within the class of sofic groups.

The bridge between the two problems is an observation of Radulescu, recounted in Goldbring's surveys: a group $G$ is hyperlinear if and only if its group von Neumann algebra $L(G)$ — the algebra generated by the left-regular representation of $G$ on $\ell^2(G)$, equipped with its canonical trace — embeds into an ultrapower $R^{\mathcal{U}}$. Hence 'every group is hyperlinear' is exactly CEP restricted to group von Neumann algebras. MIP* = RE refutes full CEP, but the separating correlation it produces is not known to come from a group von Neumann algebra, and nothing is known about the restricted case: no non-hyperlinear group and no non-sofic group has ever been exhibited, even nonconstructively. In Section 1.4 of the paper the authors ask whether their example 'can eventually lead to a construction of a group that is not sofic, or even not hyperlinear'. Recent work has clarified the routes such a construction could take. To each linear constraint system game (a nonlocal game whose verifier checks a system of linear equations over $\mathbb{F}_2$) one can associate a finitely presented 'solution group' such that perfect quantum strategies correspond to finite-dimensional unitary representations of the group, a correspondence developed by Cleve–Mittal and Kim–Paulsen–Schafhauser in the synchronous-game framework; and flexible Hilbert–Schmidt stability — the property that approximate unitary representations are close to exact ones — provides a candidate-based route through lattices such as $\mathrm{SL}_2(\mathbb{Z}[1/p])$.

Problem Statement

Exhibit a group that is not sofic — equivalently, refute the soficity conjecture that every group is sofic — or, in the stronger form posed by the MIP* = RE discussion, a group that is not hyperlinear; the desired strongest form is an explicit group given by a finite presentation. (Recall: a countable group is sofic if for every finite subset of it and every error tolerance there is a map into some finite symmetric group that is approximately multiplicative and approximately injective; it is hyperlinear if the same holds with finite unitary groups in place of symmetric groups.) A complete answer may take any of the following shapes, each of which settles the source question in full generality over all countable groups:

1. Explicit witness: a finite presentation $\langle S \mid R \rangle$ (or an explicit computable description) of a group $G$, together with a rigorous proof that $G$ is not sofic (or not hyperlinear).
2. Existence proof: a demonstration, constructive or not, that some non-sofic (or non-hyperlinear) group exists.
3. Universality proof: a proof that every group is sofic (or hyperlinear), resolving the soficity problem positively.

Because every sofic group is hyperlinear, a non-hyperlinear group is automatically non-sofic; the hyperlinear version is the stronger claim and the finitely presented version the strongest. Equivalent or sufficient formulations a solution may rely on: a countable group is non-hyperlinear exactly when its group von Neumann algebra $L(G)$ fails the Connes embedding property; Taller–Vidick (2025) shows that proving $\mathrm{LIN}^*_{1,s} = \mathrm{RE}$ at perfect completeness ($\varepsilon = 0$) for linear constraint system games would imply existence of a non-hyperlinear group; Dogon–Vigdorovich (2025) shows that flexible Hilbert–Schmidt stability of $\mathrm{SL}_2(\mathbb{Z}[1/p])$ would produce a non-hyperlinear finite central extension. Each of the three shapes above is a complete resolution; an answer that addresses only a restricted class of groups, or only a weakened target, answers a different, derived question. The open core is the existence of a non-sofic or non-hyperlinear group, constructive or not, with no restriction on the class of groups.

References

1. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen. MIP* = RE. Communications of the ACM 64(11):131–138, 2021. DOI: 10.1145/3485628, https://doi.org/10.1145/3485628. Full version: arXiv:2001.04383, https://arxiv.org/abs/2001.04383
2. Valerio Capraro, Martino Lupini. Introduction to Sofic and Hyperlinear Groups and Connes' Embedding Conjecture. Lecture Notes in Mathematics 2136, Springer, 2015. DOI: 10.1007/978-3-319-19333-5, https://doi.org/10.1007/978-3-319-19333-5. Also arXiv:1309.2034, https://arxiv.org/abs/1309.2034
3. Isaac Goldbring. The Connes Embedding Problem: A guided tour. 2021. arXiv:2109.12682, https://arxiv.org/abs/2109.12682
4. Isaac Goldbring. Undecidability and incompleteness in quantum information theory and operator algebras. 2024. arXiv:2409.08342, https://arxiv.org/abs/2409.08342
5. Lewis Bowen, Michael Chapman, Alexander Lubotzky, Thomas Vidick. The Aldous–Lyons Conjecture I: Subgroup Tests. 2024. arXiv:2408.00110, https://arxiv.org/abs/2408.00110
6. Lewis Bowen, Michael Chapman, Thomas Vidick. The Aldous–Lyons Conjecture II: Undecidability. 2025. arXiv:2501.00173, https://arxiv.org/abs/2501.00173
7. Aareyan Manzoor. There Is An Equivalence Relation Whose von Neumann Algebra Is Not Connes Embeddable. 2025. arXiv:2502.06697, https://arxiv.org/abs/2502.06697
8. Alon Dogon, Itamar Vigdorovich. Hyperlinearity, stability and asymptotic spectral gap of higher rank lattices. 2025. arXiv:2506.20843, https://arxiv.org/abs/2506.20843
9. Aviv Taller, Thomas Vidick. Approximating the quantum value of an LCS game is RE-hard. 2025. arXiv:2507.22444, https://arxiv.org/abs/2507.22444
10. Mohammad Bavarian, Thomas Vidick, Henry Yuen. Anchored Parallel Repetition for Nonlocal Games. SIAM Journal on Computing 51(2):214–253, 2022. DOI: 10.1137/21m1405927, https://doi.org/10.1137/21m1405927
11. Irit Dinur, David Steurer, Thomas Vidick. A parallel repetition theorem for entangled projection games. Computational Complexity 24(2):201–254, 2015. DOI: 10.1007/s00037-015-0098-3, https://doi.org/10.1007/s00037-015-0098-3
12. Rahul Jain, Attila Pereszlenyi, Penghui Yao. A parallel repetition theorem for entangled two-player one-round games under product distributions. In IEEE 29th Conference on Computational Complexity (CCC), 2014, pages 209–216. DOI: 10.1109/CCC.2014.29, https://doi.org/10.1109/CCC.2014.29
13. Tobias Fritz. Tsirelson's problem and Kirchberg's conjecture. Reviews in Mathematical Physics 24(5):1250012, 2012. DOI: 10.1142/S0129055X12500122, https://doi.org/10.1142/S0129055X12500122
14. Mikael de la Salle. Spectral gap and stability for groups and non-local games. Journal de l'École polytechnique — Mathématiques 12:1417–1444, 2025. DOI: 10.5802/jep.314, https://doi.org/10.5802/jep.314. Also arXiv:2204.07084, https://arxiv.org/abs/2204.07084
15. Honghao Fu, Carl A. Miller, William Slofstra. The membership problem for constant-sized quantum correlations is undecidable. 2021. arXiv:2101.11087, https://arxiv.org/abs/2101.11087
16. Ben Hayes, Srivatsav Kunnawalkam Elayavalli. On sofic approximations of non amenable groups. Mathematische Zeitschrift 307(2), 2024. DOI: 10.1007/s00209-024-03509-5, https://doi.org/10.1007/s00209-024-03509-5
17. Se-Jin Kim, Vern Paulsen, Christopher Schafhauser. A synchronous game for binary constraint systems. Journal of Mathematical Physics 59(3):032201, 2018. DOI: 10.1063/1.4996867, https://doi.org/10.1063/1.4996867
18. Narutaka Ozawa. About the Connes embedding conjecture. Japanese Journal of Mathematics 8(1):147–183, 2013. DOI: 10.1007/s11537-013-1280-5, https://doi.org/10.1007/s11537-013-1280-5