2.1 The algebra of an IRS

We will formalize the notion of quotienting against an IRS in this section. The idea is to go through traces on the universal group $C^*$ algebra $C^*(\Gamma)$ of $\Gamma$ . This is a $C^*$ -algebra densely containing the group ring $\mathbb{C}[\Gamma]$ that encodes all the representation-theoretic data of $\Gamma$ . More precisely, there is a correspondence between representations of $C^*(\Gamma)$ on Hilbert spaces and unitary representations of $\Gamma$ on the same Hilbert space (for exposition, see [Reference Brown and OzawaBO08, 2.5]).

Definition 2.8. Let $\Gamma$ be a discrete group, and let $H\in \operatorname{IRS}(\Gamma)$ . Then one can define a trace $\tau_H$ on $C^*(\Gamma)$ by

\begin{align*}\tau_H(g) := \mathbb{P}(g\in H).\end{align*}

Note that invariance gives $\tau_H$ conjugation invariance, but one still needs to check positivity. We get this from Proposition 2.11. If $H=\mathrm{Stab}(\alpha)$ , where $\alpha$ is a p.m.p. action of $\Gamma$ on some Borel probability space $(X,\mu)$ , then

\begin{align*}\tau_H(g) = \mu(x: gx=x).\end{align*}

In group theory, these objects are called characters of $\Gamma$ (positive-definite conjugation-invariant functions). Naimark’s dialation theorem gives this equivalence (for exposition, see [Reference PaulsenPau03, Theorem 4.8]).

Denote the trace complex of $\Gamma$ by $T(\Gamma)$ , and equip it with the weak $^*$ topology. This is the topology of pointwise convergence on $C^*(\Gamma)$ , which is the same as pointwise convergence when restricted to $\Gamma$ . Then note that there is an affine map $\operatorname{IRS}(\Gamma)\to T(\Gamma)$ given by $\operatorname{IRS}(\Gamma) \owns H \mapsto \tau_H \in T(\Gamma)$ . This map is neither injective nor surjective generally.

Not being surjective is clear, as a trace $\tau \in T(\Gamma)$ can be negative on a group element, which is not the case for $\tau_H$ for $H \in \operatorname{IRS}(\Gamma)$ . For non-injectivity consider $S_3$ , which has four conjugacy classes of subgroups but $T(S_3)$ has three irreducible characters. An IRS on a finite group is simply a probability measure on the set of conjugacy class of subgroups, while a character on a finite group is in the convex hull of the irreducible characters. So a dimension argument forces this map to not be injective. This map is, however, $w^*-w^*$ continuous, as $\{H: g\in H\}$ is a clopen set making its indicator continuous. So the image of this, call it $T_{\mathrm{IRS}}(\Gamma)$ , is compact.

One of the main themes in this paper will be to look at the von Neumann algebra that corresponds to a trace. This is done by looking at the Gelfand–Naimark–Segal (GNS) representation of a trace.

Let $\mathcal{A}$ be a $C^*$ -algebra and let $\tau$ be a trace on it. Then the GNS representation of $\tau$ is a representation $\pi_\tau: \mathcal{A}\to B(H_\tau)$ and a vector $\xi \in H_\tau$ with $\tau(a) = \langle\xi\rvert\pi(a)\lvert\xi\rangle$ . The von Neumann algebra of $\tau$ will be $\pi_\tau(\mathcal{A})'' \subset B(H_\tau)$ , and note that $\tau$ extends to this algebra by

\begin{align*}\tilde{\tau}(a) = \langle\xi\rvert\pi(a)\lvert\xi\rangle,\quad a\in \pi_\tau(\mathcal{A})''.\end{align*}

This algebra is well defined due to uniqueness of GNSs: any two cyclic representations inducing $\tau$ will be unitarily equivalent. We will denote this von Neumann algebra as $\tau(\mathcal{A})''$ . If $\mathcal{A}=C^*(\Gamma)$ , we will denote this as $\tau(\Gamma)''$ . It will be implicit that we are considering this von Neumann algebra with the extension of $\tau$ as its trace.

Consider the left regular representation $\lambda:\Gamma \to U( \ell^2(\Gamma))$ , where $(\lambda(g)f)(h) = f(g^{-1}h)$ for $g,h \in \Gamma$ . Then we define the group von Neumann algebra to be $\lambda(\Gamma)''\subset B(\ell^2(\Gamma))$ . We consider it with the trace $\tau(g) = 1$ if $g=e$ and 0 otherwise on group elements.

Before defining our IRS algebras, let us make one observation.

Proposition 2.9. Let $\Gamma$ be a discrete group and let N be a normal subgroup. If $\tau_N$ is the trace on $\Gamma$ corresponding to the point mass $\delta_N \in \operatorname{IRS}(\Gamma)$ , then

\begin{align*}\tau_N(\Gamma)''= L(\Gamma/N),\end{align*}

where $L(\Gamma/N)$ is the group von Neumann algebra of $\Gamma/N$ with its standard trace.

Proof. First note that $\tau_N(g) = 1$ if $g\in N$ and 0 otherwise. Now take the representation:

\begin{align*}\pi: \Gamma \to U(\ell^2(\Gamma/N)),\end{align*}

where $(\pi(g)f)([h]) = f([g^{-1}h])$ for $g\in \Gamma, [h]\in \Gamma/N$ . Note that all elements of N act trivially, so this is actually a homomorphism $\tilde{\pi}: \Gamma/N \to U(\ell^2(\Gamma/N))$ . Note that this is just the left regular representation of $\Gamma/N$ .

Fix the vector $\xi \in \ell^2(\Gamma/N)$ that is 1 on the identity coset and 0 everywhere else. Then it is clear that

\begin{align*}\tau_N(g) = \langle\xi\rvert\pi(g)\lvert\xi\rangle.\end{align*}

So the corresponding algebra is $\pi(\Gamma)'' =\tilde{\pi}(\Gamma/N)''$ and by definition this is the group von Neumann algebra $L(\Gamma/N)$ . Note that the extension of the trace is 1 on elements of N and 0 on every other group element, i.e. the standard trace on the group von Neumann algebra.

Based on this, we can now define the quotient of a group by an IRS.

Definition 2.10. Let $\Gamma$ be a discrete group and let $H\in \operatorname{IRS}(\Gamma)$ . Then define the quotient of $\Gamma$ by H as the tracial von Neumann algebra:

\begin{align*}L(\Gamma/H):= \tau_H(\Gamma)''.\end{align*}

A natural question now is this: Can we write the GNS representation of $\tau_H$ explicitly? The answer is yes.

To see this, let $H\in \operatorname{IRS}(\Gamma)$ correspond to the p.m.p. action $\alpha$ of $\Gamma$ on some $(x,\mu)$ . Let $\mathcal{R}_\alpha\subset X\times X$ be the relation defined by the orbits, i.e. $x\equiv gx$ . Let $\pi_0: \mathcal{R}_\alpha\to X$ be given by $(x,y)\mapsto x$ and let $\Gamma$ act on $\mathcal{R}_\alpha$ on the first coordinate, i.e. $g(x,y)= (gx,y)$ . Define

\begin{align*}\nu(E) := \int |\pi_0^{-1}(x) \cap E|\, d \mu(x).\end{align*}

This is a $\sigma$ -finite measure on $\mathcal{R}_\alpha$ [Reference Anantharaman and PopaAP17, § 1.5].

Proposition 2.11 [Reference VershikVer11, Theorem 9]. Let H be an IRS of $\Gamma$ . Suppose that it corresponds to p.m.p. action $\alpha$ of $\Gamma$ on $(X,\mu)$ , i.e $H=\mathrm{Stab}(\alpha)$ . Let $\pi: \Gamma\to U(L^2(\mathcal{R}_\alpha,\nu))$ correspond to the action described above. Let $\Delta\subset \mathcal{R}_\alpha$ be the diagonal of X. Then

\begin{align*}\tau_H(g) = \langle1_\Delta\rvert\pi(g)\lvert1_\Delta\rangle.\end{align*}

In particular, the algebra $L(\Gamma/H) = \pi(\Gamma)''$ .

Proof. Note that $\pi(g)1_\Delta$ is the characteristic function on $g^{-1}\Delta=\{(g^{-1}x,x):x\in X\}$ . So

\begin{align*}\begin{aligned} \langle1_\Delta\rvert\pi(g)\lvert1_\Delta\rangle &= \int_{\mathcal{R}} 1_{\Delta}1_{g^{-1}\Delta} \,d\nu\\ &= \int_{\mathcal{R}} 1_{\{(x,x): x=gx\}}\, d\nu\\ &= \nu\{(x,x): x=gx\} \end{aligned}\end{align*}

\begin{align*} \hphantom{\langle1_\Delta\rvert\pi(g)\lvert1_\Delta\rangle} &= \int_X |\pi_0^{-1}(x) \cap \{(x,x): x=gx\}|\, d\mu \\ &= \int_X 1_{x=gx}\, d\mu\\ &= \mu(x: gx=x). \end{align*}

This can be extended to a larger algebra.

Definition 2.12. Let $\alpha$ be a p.m.p. action of $\Gamma$ on $(X,\mu)$ , and let $(\mathcal{R}_\alpha,\nu)$ be as in Proposition 2.11. For $f\in L^\infty(X,\mu)$ , define $M_f \in B(L^2(\mathcal{R}_\alpha,\nu))$ as

\begin{align*}(M_f \xi) (x,y) = f(x) \xi(x,y).\end{align*}

Then the von Neumann algebra generated by $\pi(\Gamma)$ and $\{M_f: f\in L^\infty(X,\mu)\}$ is defined to be von Neumann algebra $L(\mathcal{R}_\alpha)$ of the relation $\mathcal{R}_\alpha$ . We consider this with the trace

\begin{align*}\tau_\alpha(a) = \langle1_\Delta\rvert a\lvert1_\Delta\rangle,\quad a\in L(\mathcal{R}_\alpha)\end{align*}

This can be defined for any measurable relation on a Borel space, but essentially reduces to this case. These algebras are useful as the inclusion $L^\infty(X)\subset L(\mathcal{R}_\alpha)$ is a complete invariant for the action $\alpha$ (up to orbit equivalence). These are also canonical examples of Cartan Inclusions. Note, in particular, $L(\Gamma/\mathrm{Stab}(\alpha))\subset L(\mathcal{R}_\alpha)$ . Also note that if $\alpha$ is ergodic, then $L(\mathcal{R}_\alpha)$ is a $II_1$ factor. For a discussion of all of these, see [Reference Anantharaman and PopaAP17, §§1.5 and 12.1].

2.2 Co-hyperlinear IRS

Now that we can talk about IRSs algebraically, it is easy to define co-hyperlinearity for them. Recall that a group $\Gamma$ is called hyperlinear if its von Neumann algebra $L(\Gamma)$ is Connes embeddable, i.e. there is a trace-preserving embedding $L(\Gamma)\hookrightarrow R^\omega$ of the group algebra into an ultrapower of the hyperfinite $II_1$ factor. So we want co-hyperlinearity of a $H\in \operatorname{IRS}(\Gamma)$ to line up with Connes embeddability of $L(\Gamma/H)$ .

A crucial point for us is that a tracial von Neumann algebra being Connes embeddable is something we can express in terms of traces.

Definition 2.13. A trace $\tau$ on a C* algebra $\mathcal{A}$ is called amenable if there are contractively completely positive (c.c.p.) maps $\phi_n: \mathcal{A}\to M_{k_n}(\mathbb{C})$ with

\begin{align*}\lVert\phi_n(ab)-\phi_n(a)\phi_n(b)\rVert_2 \to 0, \quad \forall a,b\in \mathcal{A},\end{align*}

so that $\tau(a) = \lim \mathrm{tr}_{k_n} \circ \phi_n(a)$ . Here, $\lVert A\rVert_2^2 = \mathrm{tr}_n(A^*A)$ is the normalized Hilbert–Schmidt norm.

This is a finite-dimensional approximation property for the trace, and it turns out that the corresponding finite-dimensional approximation property for the algebra is Connes embeddability. We state the following proposition for groups satisfying either the local lifting property or Hilbert–Schmidt stability. The important fact is that free groups have both of these properties (see [Reference Brown and OzawaBO08, Theorem 13.1.3] and [Reference Hadwin and ShulmanHS18, Theorem 1]).

1. (1) $\tau(\Gamma)''$ has a trace-preserving embedding into $R^\omega$ ; and

2. (2) $\tau$ is amenable.

   In addition, if $\Gamma$ is Hilbert–Schmidt stable, then the above are also equivalent to the following by [Reference Hadwin and ShulmanHS18, Theorem 3].

3. (3) There is a sequence of finite-dimensional representations $\pi_n:\Gamma \to U_n(\mathbb{C})$ , with $\tau$ being the weak $^*$ limit of $\operatorname{tr}_n\circ \pi_n$ .

4. (4) There is a sequence of traces $\tau_n$ with finite-dimensional GNS representation whose weak $^*$ limit is $\tau$ .

Here, $R^\omega$ is an ultrapower of the hyperfinite $II_1$ factor.

Note that the above proposition is not true for a general $C^*$ -algebra $\mathcal{A}$ . In general, amenability of the trace means that $\tau(A)''$ has an embedding into $R^\omega$ with a completely positive lift onto $\prod_\mathbb{N} R$ . The local lifting property gives this lift for free. For a detailed discussion of the local lifting property, see [Reference Brown and OzawaBO08, § 13.1]. We will use this property in our proof of Theorem 3.5 in a minor way. Hilbert–Schmidt stability allows the completely positive lift of the embedding of $\tau(A)''\hookrightarrow R^\omega$ to actually be a $*$ -homomorphism. This gives the equivalence of (1) and (3).

Let us call the collection of traces with finite-dimensional GNS representation the finite-dimensional traces of $\Gamma$ , and let us denote this set by $T_{f.d}(\Gamma) \subset T(\Gamma)$ .

We also remark that while the traces are called amenable, the corresponding algebras are not amenable von Neumann algebras. For that, one would need to restrict to a class of traces called uniformly amenable traces.

Of course, one of the nice things about the free group is that it is an universal object. It turns out that every tracial von Neumann algebra arises from a trace on some free group (the extreme points correspond to factors). So the fact that there is a non-Connes-embeddable tracial von Neumann algebra can be stated as follows.

For more details, see [Reference BrownBro06, Proposition 6.3.5]. It is now clear how to generalize the notion of hyperlinearity to IRSs.

1. (1) H is co-hyperlinear if and only if $L(\Gamma/H)$ is Connes embeddable; and

2. (2) $H=\delta_N$ is co-hyperlinear if and only if $\Gamma/N$ is hyperlinear as a group.

Let us make explicit what the difference is between co-hyperlinear and co-sofic.

Then H being finitely described implies that $\tau_H$ is a finite-dimensional trace.

Furthermore, if $\Gamma$ is finitely generated, then $\tau_H$ being a finite-dimensional trace implies that H is finitely described.

$(\!\impliedby\!)$ We can find an ergodic action $\alpha$ of $\Gamma$ on some probability space $(X,\mu)$ with $H=\mathrm{Stab}(\alpha)$ .

Let $F_n\subset X$ denote the set of points with orbits of size less than n. Note that a point having orbit of size n is the same as the stabilizer K having index n. Since the action $\Gamma$ on $\Gamma/K$ uniquely determines K (by looking at the stabilizer of the identity coset), the corresponding homomorphism $\Gamma \to \operatorname{Sym}(n)$ uniquely determines K. In particular, since $\Gamma$ is finitely generated, there are finitely many subgroups of index n of $\Gamma$ . So

\begin{align*}F_n = \bigcup_{K: |\Gamma/K|\leqslant n} \{x : gx=x \,\forall g\in K\}.\end{align*}

This is a finite union of measurable sets, and hence measurable. $F_n$ is $\Gamma$ invariant and hence has measure 0 or 1. If it has measure 1, then H is supported on subgroups of index $\leqslant n$ , and this is a finite set; call it $\operatorname{Supp}(H)$ . Now ergodicity of H forces $\operatorname{Supp}(H)$ to be the set of conjugates of a given subgroup K’, and this is the IRS induced by the action of $\Gamma$ on the finite set of cosets $\Gamma/K'$ .

If all $F_n$ have measure 0, then the action has infinite orbits almost everywhere. By [Reference Peterson and ThomPT16, Proposition 3.1], the representation $\Gamma \to U(L^2(\mathcal{R}_\alpha,\nu))$ is weakly mixing, i.e. it has no finite-dimensional sub-representations. In particular, $\tau_H$ cannot be finite dimensional, ruling this case out.

This immediately gives us the following.

Let $\Gamma$ be a free group. Note that showing a separation between co-sofic IRSs and all IRSs is implied by showing a separation between $T_{\mathrm{IRS}}(\Gamma)$ and $\overline{T_{\mathrm{IRS}}(\Gamma)\cap T_{\mathrm{f.d.}}(\Gamma)}$ . On the other hand, showing a separation between co-hyperlinear IRSs and all IRSs is showing a separation between $T_{\mathrm{IRS}}(\Gamma)$ and $T_{\mathrm{IRS}}(\Gamma)\cap \overline{T_{\mathrm{f.d.}}(\Gamma)}$ . The latter is an a priori harder problem, as one might be able to approximate an IRS trace with finite-dimensional traces, but not finite-dimensional traces arising from IRSs. Actually, these notions agreeing would imply that hyperlinearity and soficity agree for groups, by specializing to Dirac measures.

We also remark that the set of co-hyperlinear IRSs of free group $\Gamma$ is a $w^*$ closed convex subset of $\operatorname{IRS}(\Gamma)$ containing the co-sofic IRSs. This is because it is the pre-image of $T_{\mathrm{IRS}}(\Gamma)\cap \overline{T_{\mathrm{f.d.}}(\Gamma)}$ under the affine continuous $H\mapsto \tau_H$ .

3.1 Strategies

Note that the only thing Alice and Bob can do, when asked questions $(x,y)\in Q^2$ , is give answers $(a,b) \in (\{0,1\}^m)^2$ . So a strategy for Alice and Bob will be some conditional distribution $(p(a,b|x,y))_{ (\{0,1\}^m)^2\times Q^2}$ . We will call these correlations. The idea in these games is that Alice and Bob can discuss a strategy beforehand but cannot communicate during the game: so Alice has no idea what question Bob got and vice versa. Therefore, a strategy in which Alice’s answer is independent of Bob’s answer would be a classical strategy.

However, if Alice and Bob share quantum entanglement, then there can be correlation between their choices of their answer. This works precisely in the following way.

1. (i) $\rho(u)^2=1$ for each $u\in S$ ; and

2. (ii) $\rho(u)$ and $\rho(v)$ commuting whenever $u,v\in S_x$ , i.e. different bits corresponding to the same answer should commute.

Define

\begin{align*}e_x^a = \prod_{i\leqslant m} \dfrac{1 + (-1)^{a_i}\rho(u_{x,i})}{2}.\end{align*}

This is the product of the spectral projections of each bit onto $(-1)^{a_i}$ . Then, the corresponding correlation is defined as

\begin{align*}p(a,b|x,y) = \mathrm{tr}_n(e_x^a e_y^b).\end{align*}

A quantum approximate correlation is a pointwise limit of quantum correlations.

The value of a game $\mathfrak{G}$ on strategy $\rho$ , $\operatorname{Val}(\mathfrak{G},\rho)$ is just the expected value of winning if Alice and Bob answer (a,b) on questions (x,y) with probability $p(a,b|x,y)$ . We define the quantum value of the game as

\begin{align*}\omega^*(\mathfrak{G}):= \sup_{\rho}\operatorname{Val}(\mathfrak{G},\rho)\end{align*}

the best probability of winning with a quantum strategy.

Actually, in the literature these are called synchronous quantum approximate strategies, but we will not consider any non-synchronous strategies, so we omit that word. This is also defined slightly differently than the standard literature, but Theorem 3.3 shows the equivalence. Note that if the dimension was 1, this would just be a classical correlation, since we would have $p(a,b|x,y) = p(a|x)p(b|y)$ .

There are two perspectives: one of them is that we can associate to each bit of the answer a formal variable, to be interpreted as a matrix. This is what we are doing. In this case, the spectral projections of these variables correspond to what bit that variable outputs. On the other hand, one can associate a variable $v_x$ to each question $x\in Q$ with $v_x^{2^m}=1$ . So now $v_x$ will have $2^m$ spectral projections, and they will correspond to the $2^m$ different outputs on question x. These perspectives are equivalent.

Let $\mathfrak{G}$ be a non-local game with question set Q, answers of size m, and variable set S. By $\mathcal{F}(S,2)$ , we denote the group generated by elements of S with the condition that they have order 2. By , we will denote the quotient of $\mathcal{F}(S,2)$ by $\{[u_{x,i}, u_{x,j}]: x\in X, i,j\leqslant m\}$ . That is, we are imposing the condition that the variables corresponding to the same question commute. Let $U_{x,i}$ denote the group unitaries corresponding to $u_{x,i}$ in , and let $e_x^a$ be the spectral projections as above, for $a\in \mathbb{Z}_{2}^{m}$ . That is,

\begin{align*}e_x^a = \prod_{i\leqslant m} \dfrac{1 + (-1)^{a_i}U_{x,i}}{2}.\end{align*}

Note that these projections generate the algebra and have no relation between each other except that $e_x^a e_x^b = \delta_{ab}$ and $\sum_a e_x^a = 1$ . Hence we can find an isomorphism by looking at the $2^m$ spectral projections of the defining unitaries in the latter. In particular, this algebra has the local lifting property (see [Reference Enders and ShulmanES24, Corollary 4.6]).

Any set of projections satisfying the same properties as $e_x^a$ are called projective valued measurements (PVMs). One should think of these as ‘quantum probabilities’ of answering a on question x. To get actual probabilities out of these, one needs to use traces.

Theorem 3.3 [Reference Kim, Paulsen and SchafhauserKPS18, Theorem 3.6]. Let $\mathfrak{G}$ be a non-local game with question set Q and answers of size m. Then p is a quantum approximate correlation if and only if there is an amenable trace $\tau$ on so that

\begin{align*}p(a,b|x,y) = \tau(e_x^a e_y^b).\end{align*}

If we remove the restriction to amenable traces and allow any trace, then the resulting classes of correlations are called quantum commuting. The idea of $\mathsf{MIP}^*=\mathsf{RE}$ was separating the quantum commuting value and quantum value of some game, and that would give a non-amenable trace on this group.

Of course, we do not want just any old trace to induce our correlations, but specifically the ones coming from IRSs. So let us define the following.

• – $\mu(x: \sigma(J)x=x)=0$ and $\sigma(J)^2=1$ ;

• – for $u\in \sigma(S)$ , we have $u^2=1$ and $u\sigma(J)=\sigma(J)u$ ; and

• – for $u,v \in \sigma(S_x)$ we have $uv=vu$ .

If $\mu$ was the uniform measure on a finite set, call this a permutation strategy.

Note that $\sigma$ extends to a homomorphism . That is, it is a p.m.p. action of the group $\mathbb{Z}_{2}^{m} \times \mathbb{Z}_{2}$ on $(X,\mu)$ . So we can consider the IRS $\mathrm{Stab}(\tilde{\sigma})$ and then the corresponding trace $\tau$ on has

\begin{align*}\tau(g) = \mu(x: gx=x).\end{align*}

So we can define the correlation

\begin{align*}p(a,b|x,y) = \tau((1-J) e_x^ae_y^b).\end{align*}

Note that this is positive as $\tau((1-J)a) = \frac{1}{2} \tau((1-J)a(1-J))$ and these sum up to 1 as $\tau(J)=0$ . We will define $\omega_{\mathrm{IRS}}(\mathfrak{G})$ to be the best winning probability over all IRS strategies.

We remark that this definition agrees with that of [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24, Definition 6.11] for permutation strategies. The authors defined permutation strategies as maps $\sigma: S\cup\{J\} \to \operatorname{Sym}(2n)$ with the same conditions, and if $W^{-}$ is the negative eigenspace of the image of J in U(2n), then they defined the correlation as

\begin{align*}p(a,b|x,y) = \mathrm{tr}_n(e_x^ae_y^b|_{W^{-}}).\end{align*}

Since $({1-J})/{2}$ is the projection onto $W^{-}$ , this is the same correlation as our definition. This is why we have had to add this $(1-J)$ to our construction, as without it we would not be able to use the resulting TailoredMIP $^*$ $=$ RE of [Reference Bowen, Chapman and VidickBCV24]. What we have done is, in essence, to define the dual of the permutation strategies of [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24], which will allow us a direct separation of the convex sets in question without going through some intermediary-like subgroup tests.

Now, if we had a game with an IRS strategy that was not quantum approximate, then intuitively that should arise from an IRS trace that is not amenable, which is what we want. Formally, we have the following.

Theorem 3.5. Suppose that there is a game $\mathfrak{G}$ with

\begin{align*}\omega_{\mathrm{IRS}}(\mathfrak{G})\gt\omega^*(\mathfrak{G}).\end{align*}

Then there is a non-co-hyperlinear IRS on some free group.

Proof. Let $\mathfrak{G}$ be a game with $\omega_{\mathrm{IRS}}(\mathfrak{G})\gt\omega^*(\mathfrak{G})$ . Let $\sigma:S\cup \{J\}\to \mathrm{Aut}(X,\mu)$ be an IRS strategy with $\operatorname{Val}(\mathfrak{G}, \sigma)\gt\omega^*(\mathfrak{G}).$ Let $\tau$ be the corresponding trace on $C^*(\mathcal{F}(Q,2^m))\otimes C^*(\mathbb{Z}_2)$ so that

\begin{align*}p(a,b|x,y) = \tau((1-J)e_x^a e_y^b)\end{align*}

is the correlation.

Note that there is a natural inclusion $ C^*(\mathcal{F}(Q,2^m))\subset C^*(\mathcal{F}(Q,2^m))\otimes C^*(\mathbb{Z}_2)$ induced by the natural group inclusion [Reference Brown and OzawaBO08, Proposition 2.5.8]. Note that $a\mapsto \tau((1-J)a)$ for $ a \in C^*(\mathcal{F}(Q,2^m))\otimes C^*(\mathbb{Z}_2)$ is a trace as J commutes with everything. Call this trace $\tau'$ . Then $\tau'|_{C^*(\mathcal{F}(Q,2^m))}$ is also a trace, and has

\begin{align*}p(a,b|x,y) = \tau'|_{C^*(\mathcal{F}(Q,2^m))} (e_x^a e_y^b).\end{align*}

Since p is not a quantum approximate correlation, $\tau'|_{C^*(\mathcal{F}(Q,2^m))}$ is not an amenable trace. Since amenability of traces is preserved under restriction [Reference Brown and OzawaBO08, Proposition 6.3.5], we get that $\tau'$ itself is not amenable. We now have

\begin{align*}\tau(a) = \tfrac12 \tau((1-J)a) + \tfrac12 \tau(Ja)\end{align*}

and both are traces, and since the amenable traces are a face [Reference Brown and OzawaBO08, Proposition 6.3.7], we have that $\tau$ is not amenable.

Note that has the local lifting property [Reference Brown and OzawaBO08, Exercise 13.2]. Note that there is a natural quotient map and it induces a quotient on the $C^*$ level. Here, $\mathcal{F}(S\cup\{J\})$ is the free group generated by $S\cup \{J\}$ , so we can lift up $\tau$ to $\tilde{\tau} = \tau\circ q$ on $C^*(\mathcal{F}(S\cup\{J\}))$ . Note that $\tilde{\tau}$ corresponds to an action of $\mathcal{F}(S\cup\{J\})$ on $(X,\mu)$ , so it is an IRS trace. We also have

\begin{align*}\tilde{\tau}(\mathcal{F}(S\cup\{J\}))^{\prime\prime} = \tau(\mathop{\ast}_{Q} \mathbb{Z}_{2}^{m} \times \mathbb{Z}_{2})^{\prime\prime}.\end{align*}

Since the latter has the local lifting property, the non-amenability of $\tau$ implies that the algebra is not Connes embeddable, and hence that $\tilde{\tau}$ is not amenable.

Since this implies the negation to Aldous–Lyons by Proposition 2.19, this proof allows us to skip [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24]. That is, we reduce to non-local games without having to go through subgroup tests. In that paper, the authors also reduced to the a priori harder problem of finding this separation for a restricted class of games called tailored games, which have a sort of linearization baked into them, allowing translation as group-like objects. However, we do not require this, as these IRS strategies already bake in a group-like structure.

This highlights two different approaches when one wants to use these non-local games: restrict the class of strategy or restrict the class of games. In [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24], the authors ended up doing both but their ideas were based off of the latter. If there was a linear constraint game with a perfect quantum commuting strategy but $\omega^*\lt1$ , then there would be a non-hyperlinear group. Based off of this, the tailored games of [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24] were designed to be ‘semi-linear’.

3.2 NPA hierarchy

To get the separation, we will need an analogue of the NPA hierarchy for these IRS strategies. That is, we will need the following.

Recall that this means there is a Turing machine that takes as input the description of some non-local game, and enumerates the sequence $\alpha_n$ .

To see this, we will recall some notions from [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24, § 2]. Our NPA hierarchy for IRS value of a game is inspired by the one in [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24] for subgroup tests, and is using some of the authors’ lemmas leading up to that. Throughout this section, fix a non-local game $\mathfrak{G}$ and its variable set S. Then let $\mathcal{F}=\mathcal{F}(S\cup\{J\})$ be the free group generated by $S\cup\{J\}$ .

A random pseudo-subgroup $\pi$ is, in addition, invariant if for each $K,L\subset B$ so that $sKs^{-1}, sLs^{-1}\subset B$ for each $s\in S\cup S^{-1}$ , we have

\begin{align*}\pi\{A\subset B: K\subset A,\, A\cap L =\varnothing\} = \pi\{A\subset B: sKs^{-1}\subset A,\, A\cap sLs^{-1} =\varnothing\}\end{align*}

Denote the set of invariant random pseudo-subgroups of B as $\mathcal{Q}_B$ , and let $\tilde{\mathcal{Q}}_B = R_{B*}^{-1} (\mathcal{Q}_B)$ : that is, the set of measures on $\{0,1\}^\mathcal{F}$ whose pushforward to $\{0,1\}^B$ is an invariant random pseudo-subgroup.

For each $\pi \in \tilde{\mathcal{Q}}_B$ , we will extend the value of a non-local game to it. Here is the idea: if $\sigma: S\cup \{J\} \to \mathrm{Aut}(X,\mu)$ is an IRS strategy, then it corresponds to an IRS $H=\mathrm{Stab}(\sigma)$ on $\mathcal{F}$ . Now the correlations with respect to this are

\begin{align*}p(a,b|x,y) = \tau_H((1-J) e_x^ae_y^b), \quad e_x^a = \prod_{i\leqslant m} \dfrac{1+(-1)^{a_i}U_{x,i}}{2}.\end{align*}

In particular, each $p(a,b|x,y)$ only requires the data of $\tau$ on a finite number of group elements. One can see this by expanding out $e_x^a$ and $e_y^b$ . The only group elements appearing in this will be those that are a product of elements $J, U_{x,i}, U_{y,i}$ of length $\leqslant m+1$ .

So we can find a finite set K with

\begin{align*}p(a,b|x,y) = \sum_{g\in K} c_g^{abxy} \mathbb{P}(g\in H).\end{align*}

We can assume that K contains $S\cup \{J\}$ , all of the squares from $S\cup \{J\}$ , and all the commutators from it, simply by unioning this finite set with K.

Now, for a probability distribution $\pi$ on $\{0,1\}^B$ for some set $B\supset K$ , we can define $\operatorname{Val}(\mathfrak{G},\pi)$ as the expected value of winning with correlation

\begin{align*}p(a,b|x,y) = \sum_{g\in K} c_g^{abxy} \pi(A: g\in A).\end{align*}

Note that this will typically not actually be a conditional probability distribution, as these can become negative. This is because $\pi$ is not actually invariant and so we are not dealing with traces. But we can still find the value of the game on it. That is, if q is the distribution on the question set $Q\times Q$ and D is the decider, then define

\begin{align*}\operatorname{Val}(\mathfrak{G},\pi) =\sum_{x,y}\sum_{a,b} q(x,y)D(a,b|x,y) \bigg( \sum_{g\in K} c_g^{abxy}\pi(A: g\in A)\!\bigg).\end{align*}

Now we prove the following.

Lemma 3.10. Let $K\subset B\subset C\subset \mathcal{F}$ , and let $\pi$ be a probability measure on $\{0,1\}^C$ . Then

\begin{align*}\operatorname{Val}(\mathfrak{G},\pi) = \operatorname{Val}(\mathfrak{G},R_{B\subset C*}\pi).\end{align*}

Proof. Note that

\begin{align*}R_{B\subset C*}(\pi) (A\subset B : g\in A) = \pi(A \subset C : g \in R_{B\subset C}(A)) = \pi(A \subset C : g \in A)\end{align*}

for $g\in K$ . Note that we have used that $g\in B$ always. Since these determine the value of the game, we are done.

Only one thing is missing: not all IRSs will define a strategy for our game. For example, we want all members of S to square to identity in the action. But this is easy to enforce.

1. (i) $\{A: J\not\in A\}$ ;

2. (ii) $\{A: [u,v] \in A \text{ for } u,v\in S_{x}\}$ for each $x\in Q$ ;

3. (iii) $\{A: u^2\in A\text{ for } u\in S\cup\{J\}\}$ ; and

4. (iv) $\{A: [u,J] \in A \text{ for } u\in S\}$ .

Note that $R_{B\subset C*}^{-1} \mathcal{T}_B= \mathcal{T}_C$ .

The point of this is that $\operatorname{IRS}(\mathcal{F})\cap \mathcal{T}_\mathcal{F}$ correspond precisely to the IRSs that induce strategies on $\mathfrak{G}$ . To see this, take any IRS H of $\mathcal{F}$ , and any action $\sigma$ of $\mathcal{F}$ on some Borel probability space $(X,\mu)$ that has $H=\mathrm{Stab}(\alpha)$ . Then having measure 1 on, e.g., $\{A: u^2\in A\text{ for } u\in S\cup\{J\}\}$ is simply saying that $u^2$ stabilizes almost all points of X, i.e. $u^2=1$ .

Now, we can finally construct the NPA hierarchy (the proof follows the structure of [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24, Proof of Theorem 1.10], with the appropriate modification for our setting).

Proof of Theorem 3.6. Let K be as above and let $B\supset K$ be a finite set. We can then define

\begin{align*}\operatorname{Val}_B(\mathfrak{G}) = \sup(\operatorname{Val}(\mathfrak{G},\pi): \pi \in \mathcal{Q}_B\cap \mathcal{T}_B) =\sup(\operatorname{Val}(\mathfrak{G},\pi): \pi \in \tilde{\mathcal{Q}}_B\cap \mathcal{T}_\mathcal{F}).\end{align*}

Here, we use that $R_{B*}^{-1} (\mathcal{T}_B) =\mathcal{T}_\mathcal{F}$ . Let $B_t$ be a sequence of sets, $B_1\supset K$ and $B_{t+1}\supset B_t$ . Also suppose that $\bigcup_t B_t = \mathcal{F}$ . Then we prove the following.

• – That $\mathrm{Val}_{B_t}(\mathfrak{G})$ is computable. To see this, first from [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24, Lemma 2.16], $\mathcal{Q}_{B_t}$ can be considered as a computable polytope of $\mathbb{R}^{\{0,1\}^{B_t}}$ (i.e. assigning to each subset of $B_t$ a real number). This means that $\mathcal{Q}_{B_t}$ can be computably defined using integer linear equations and inequalities. Note that $\mathcal{Q}_{B_t}\cap \mathcal{T}_{B_t}$ just adds finitely more linear equations to this: for fixed subsets of $B_t$ , we are asking the sum over subsets of those to add up to 1. Hence we can do a linear program over $\mathcal{Q}_{B_t}\cap \mathcal{T}_{B_t}$ to compute $\mathrm{Val}_{B_t}(\mathfrak{G})$ in finite time.

• – That $\mathrm{Val}_{B_t}(\mathfrak{G})\geqslant \mathrm{Val}_{B_{t+1}}(\mathfrak{G})$ . To see this, note that $R_{B\subset C*}(\mathcal{Q}_C) = \mathcal{Q}_B$ . So

  \begin{align*}\tilde{\mathcal{Q}}_{B_t} \cap \mathcal{T}_\mathcal{F} \supset\tilde{\mathcal{Q}}_{B_{t+1}} \cap \mathcal{T}_\mathcal{F},\end{align*}
  giving the result.

• – That $\mathrm{Val}_{B_t}(\mathfrak{G}) \to \omega_{\mathrm{IRS}}(\mathfrak{G})$ . The $\tilde{\mathcal{Q}}_B$ and $\mathcal{T}_\mathcal{F}$ are weak $^*$ closed subsets of $\operatorname{Prob}(\{0,1\}^\mathcal{F})$ and hence their intersection is compact. So there is some $\pi_t \in \tilde{\mathcal{Q}}_{B_t}\cap \mathcal{T}_\mathcal{F}$ , which has

  \begin{align*}\mathrm{Val}_{B_t}(\mathfrak{G}) = \mathrm{Val}(\mathfrak{G}, \pi_t).\end{align*}
  We can pick a weak $^*$ cluster of $\pi_t$ ; say, $\pi_\infty$ . By passing to a subsequence, we may assume $\pi_t$ weak $^*$ converge to $\pi_\infty$ . Now note that for all $s\geqslant t$ , we have $\pi_s \in \tilde{\mathcal{Q}}_{B_t}\cap \mathcal{T}_S$ . Since this set is closed, we get $\pi_\infty \in \tilde{\mathcal{Q}}_{B_t}\cap \mathcal{T}_\mathcal{F}$ for all t, i.e.
  \begin{align*}\pi_\infty \in\bigcap_t \tilde{\mathcal{Q}}_{B_t}\cap \mathcal{T}_\mathcal{F}= \operatorname{IRS}(\mathcal{F}) \cap \mathcal{T}_\mathcal{F}.\end{align*}
  For the proof of this intersection, see [Reference Bowen, Chapman, Lubotzky and VidickBCL⁺24, Lemma 2.12].

This means that $\pi_\infty$ is an IRS strategy for the game. And now since $\mathrm{Val}(\mathfrak{G},-)$ is a continuous functional, we get

\begin{align*}\lim_{t\to \infty} \mathrm{Val}_{B_t}(\mathfrak{G}) = \mathrm{Val} (\mathfrak{G}, \pi_t) = \mathrm{Val}(\mathfrak{G},\pi_\infty )\leqslant \omega_{\mathrm{IRS}}(\mathfrak{G}).\end{align*}

But as $\tilde{\mathcal{Q}}_{B_t}\cap \mathcal{T}_\mathcal{F}\supset \operatorname{IRS}(\mathcal{F}) \cap \mathcal{T}_\mathcal{F}$ , we have $\mathrm{Val}_{B_t}(\mathfrak{G})\geqslant \omega_{\mathrm{IRS}}(\mathfrak{G})$ . We are done.

3.3 Separation

We now get the separation directly from the main theorem of [Reference Bowen, Chapman and VidickBCV24].

• – If $\mathcal{M}$ halts, then $\mathfrak{G}_\mathcal{M}$ has a perfect permutation strategy.

• – If $\mathcal{M}$ does not halt, then $\omega^*(\mathfrak{G}_\mathcal{M})\lt\frac{1}{2}$ .

Actually, the authors have proved something a priori stronger; that this is true when restricting to a class of games called tailored non-local games. With this, we can prove the following.

Suppose that for all games we had $\omega^*(\mathfrak{G})\geqslant \omega_{\mathrm{IRS}}(\mathfrak{G})$ . Under this assumption, we will construct an algorithm for the Halting problem.

Let $\mathcal{M}$ be a Turing machine, and let $\mathfrak{G}_\mathcal{M}$ be the game from Theorem 3.12. On this input, our algorithm will alternate enumerating the $\alpha_n$ from Theorem 3.6 and the $\beta_n$ for $\mathfrak{G}_\mathcal{M}$ . The algorithm will accept on the input if ever $\beta_n\geqslant \frac{1}{2}$ . It will reject if ever $\alpha_n \lt1$ .

There are two cases. First suppose that $\mathcal{M}$ halts. This means that there is a perfect permutation strategy and so $\omega_{\mathrm{IRS}}(\mathfrak{G}_\mathcal{M})=1$ and $\omega^*(\mathfrak{G}_\mathcal{M})=1$ . So the $\alpha_n$ are always $\geqslant 1$ and the $\beta_n$ are eventually $\geqslant \tfrac{1}{2}$ . So the algorithm accepts on this input.

Suppose that $\mathcal{M}$ never halts. This means that $\omega^*(\mathfrak{G}_\mathcal{M})\lt\frac{1}{2}$ and so $\omega_{\mathrm{IRS}}(\mathfrak{G}_\mathcal{M})\lt\frac12$ . In particular, $\alpha_n$ is eventually $\lt1$ and the $\beta_n$ are never $\geqslant \tfrac{1}{2}$ . So the algorithm rejects on this input.

We now combine the results of the paper to prove the main theorem.

Proof of Theorems 1.1 and 1.2. By Theorems 3.5 and 3.13, we see that there is a non-co-hyperlinear IRS H on some free group $\Gamma$ .

Since $\operatorname{IRS}(\Gamma)$ and the set of co-hyperlinear IRSs are closed convex sets, a separation between them implies that some extreme point of $\operatorname{IRS}(\Gamma)$ is not co-hyperlinear. So there is some ergodic $H\in \operatorname{IRS}(\Gamma)$ that is not co-hyperlinear.

By Proposition 2.17, this means that $L(\Gamma/H)$ is not Connes embeddable. By the discussion preceding Definition 2.12, we have that $L(\Gamma/H)$ embeds into some $L(\mathcal{R})$ , where $\mathcal{R}$ is a countable p.m.p. relation. $\mathcal{R}$ can be chosen to be ergodic as H was ergodic.

Finally, by [Reference Chifan, Drimbe and IoanaCDI22, Theorem D], we have that $L(\mathcal{R})$ embeds into some $L(\mathcal{R}')$ , where $\mathcal{R}'$ is an ergodic countable p.m.p. relation with property (T). Since $L(\Gamma/H)$ was not Connes embeddable, $L(\mathcal{R}')$ is not either.