## THE ALDOUS-LYONS CONJECTURE I: SUBGROUP TESTS

## LEWIS BOWEN, MICHAEL CHAPMAN, ALEXANDER LUBOTZKY, AND THOMAS VIDICK

Abstract. This paper, and its companion [BCV24], are devoted to a negative resolution of the Aldous-Lyons Conjecture [AL07, Ald07]. This conjecture, originated in probability theory, is well known (cf. [Gel18]) to be equivalent to the statement that every invariant random subgroup of the free group is co-sofic. We disprove this last statement.

In this part we introduce subgroup tests . These tests are finite distributions over continuous functions from the space of subgroups of the free group to { 0 1 , } . Subgroup tests provide a general framework in which one can study invariant random subgroups of the free group. Classical notions such as group soficity and group stability arise naturally in this framework. By the correspondence between subgroups of the free group and Schreier graphs, one can view subgroup tests as a property testing model for certain edge-labeled graphs. This correspondence also provides the connection to random networks.

Subgroup tests have values , which are their asymptotic optimal expectations when integrated against co-sofic invariant random subgroups. Our first main result is that, if every invariant random subgroup of the free group is co-sofic, then one can approximate the value of a subgroup test up to any positive additive constant.

Our second main result is an essentially value preserving correspondence between certain non-local games and subgroup tests. By composing this correspondence with a stronger variant of the reduction in MIP ∗ = RE [JNV + 21], proved in the companion paper [BCV24], we deduce that approximating the sofic value of a subgroup test is as hard as the Halting Problem, and in particular, undecidable. The combination of our two main results proves the existence of non co-sofic invariant random subgroups of the free group.

## Contents

| 1.         | Introduction                                               |   1 |
|------------|------------------------------------------------------------|-----|
| 2.         | Group theoretic preliminaries                              |  12 |
| 3.         | Main Theorem I: Approximating the values of subgroup tests |  17 |
| 4.         | Examples of tests                                          |  19 |
| 5.         | Robustness                                                 |  21 |
| 6.         | Tailored non-local games                                   |  26 |
| 7.         | Main Theorem II: Tests associated with tailored games      |  37 |
| 8.         | Proving Theorem 7.3                                        |  40 |
| References | References                                                 |  50 |

## 1. Introduction

In their seminal paper [AL07], Aldous and Lyons ask whether every unimodular network is sofic. Conditional on a certain result which will be addressed in a companion paper [BCV24], we prove the answer is 'no'. This conjecture, which originated in probability theory, can also be expressed in the language of invariant random subgroups, and this is the one we will use in this paper. We explain and motivate this conjecture before discussing our approach. The formal definitions and results will start in Section 1.1.

## The Aldous-Lyons Conjecture.

What is soficity? Roughly speaking, a countable group Γ is sofic if it admits a sequence of partial actions on finite sets which approximates the action of Γ on itself by left-translations. If Γ = 〈 S R | 〉 is finitely presented then this is equivalent to the existence of a sequence of finite graphs which converge to the Cayley graph of Γ in the sense of Benjamini-Schramm, which is a kind of local-on-average convergence.

To be more precise, a rooted graph is a pair ( G,o ) where G = ( V, E ) is a graph and o ∈ V is a distinguished vertex called the root . A random rooted graph ( G,o ) is sofic if there exists a sequence ( G i ) i ∈ N of finite graphs such that, if o i is a uniformly random vertex of G i , then ( G , o i i ) converges to ( G,o ) in distribution (this means: for every r &gt; 0, the radius r neighborhood of the root in G i converges in distribution to the radius r neighborhood of the root in G ). This notion of convergence is due to Benjamini and Schramm [BS01]: They proved that if each finite graph G i is planar and there is a uniform degree bound, then the limit ( G,o ) is almost surely recurrent.

The notions of Benjamini-Schramm convergence and soficity naturally generalize from graphs to labeled graphs or networks [AL07], simplicial complexes [Ele10], manifolds [AB22], measured equivalence relations [EL10], measured groupoids [DKP14] and most generally, measured metric spaces [Khe23].

Again, a finitely presented group is sofic if one of its Cayley graphs is sofic. 1 For example, amenable groups are sofic. In fact, the Cayley graph of an amenable group admits a sequence of finite sub-graphs in which the isoperimetric ratio (number of boundary vertices to number of vertices) tends to zero, which implies this sequence Benjamini-Schramm converges to the Cayley graph. Also, residually finite groups are sofic because they admit sequences of finite quotient groups whose Cayley graphs approximate the Cayley graph of the given group.

Gromov implicitly introduced sofic groups in [Gro99]. He was motivated by Gottshalk's Conjecture: If Γ is a countable group and k ∈ N , then any Γ-equivariant continuous map φ : [ k ] Γ → [ k ] Γ which is injective is necessarily surjective. This is obviously true when Γ is finite. Gromov proved that it holds when Γ is sofic. Benjy Weiss gave another proof and coined the term 'sofic' from the Hebrew word for finite [Wei00].

The soficity property has been useful in obtaining positive results about L 2 and spectral theory invariants [ABB + 17], group rings [ES04,Tho08], invariant couplings of random fields [LT16], and in constructing dynamical invariants of groups actions [Bow10,KL11,Li13,Hay14,LL19]. See [CL13,PK13] for more background on sofic groups. The basic idea is roughly the same in each case: One transfers properties of the finite approximating objects to properties of the limit.

It is a major open problem to determine whether all countable groups are sofic. We do not directly address this problem because the class of objects we study, described next, is more general than the class of groups.

What is unimodularity? The main tool for analyzing Benjamini-Schramm limits is called the Mass Transport Principle which makes precise the intuitive notion of statistical homogeneity. To explain, a doubly-rooted graph is an ordered triple ( G,o , o 1 2 ), where o , o 1 2 are vertices of G . A transport function is a function f , satisfying some measurability condition, which takes as input a doubly rooted graph and outputs a non-negative real number. The interpretation is that f ( G,o , o 1 2 ) is the amount of mass the first root o 1 sends to the second root o 2 . So if ( G,o ) is a random rooted graph then E ( G,o ) [ ∑ x ∈ V ( G ) f ( G,o,x ) ] is the average amount of mass sent out of the root. Symmetrically, E ( G,o ) [ ∑ x ∈ V ( G ) f ( G,x,o ) ] is the average amount of mass sent into the root. If these two quantities are equal for every transport function f , then we say ( G,o ) satisfies the Mass Transport Principle . Equivalently, we say it is unimodular (this is the term used by Aldous and Lyons in

1 If one of the Cayley graphs is sofic, then all those that use finitely many generators are.

[AL07]). Alternatively, unimodularity can be formulated in terms of graphings or as invariance with respect to the root-changing equivalence relation on the space of rooted graphs. The former arises from the ergodic theory of measured equivalence relations (e.g. [AL91]). The latter point-of-view was introduced in [Kai98] and further developed in [Ka˘ ı15].

The term unimodular comes from the following special case. Suppose G is a connected transitive graph; this means that its automorphism group Aut( G ) acts transitively on its vertex set. Then ( G,o ) is unimodular if and only if the automorphism group Aut( G ) is unimodular in the sense that its left and right Haar measures agree.

The Mass Transport Principle arose in H¨ggstr¨m's study of percolation clusters on trees [H¨g97]. In fact, it a o a is an exercise to show that if ( G,o ) is unimodular and p ∈ [0 , 1] is given, then the Bernoulli p -percolation cluster containing o is also unimodular. Unimodularity was further developed in [BLPS99] (see also [BS11] where it was used to construct a version of the Euler characteristic for unimodular planar maps).

It is straightforward to verify that (1) unimodularity is closed under weak limits and (2) if G is a finite graph and o is a uniformly random vertex of G then ( G,o ) is unimodular. It follows from these observations that soficity implies unimodularity. Question 10.1 of [AL07] asks whether unimodularity implies soficity.

As above, unimodularity has been generalized to random rooted labeled graphs, simplicial complexes, manifolds and so on. Benjamini and Schramm note that many results which are known to hold in the deterministic setting of unimodular transitive graphs can be generalized to unimodular random graphs [BS01]. Aldous and Lyons demonstrate this with results about random walks, amenability, ends of graphs, spanning forests, percolation, and so on [AL07].

What is an invariant random subgroup? As a first step towards our goal, let us describe the algebraic formulation of the Aldous-Lyons Conjecture in terms of invariant random subgroups, which were introduced in [Ver10], [AGV14], [Bow14] (and implicitly in [SZ94]). The concept of invariant random subgroups has been profitably studied in the context of locally compact groups (e.g. [SZ94, ABB + 17, Gel18]). However, we will restrict our focus to the case of most relevance to this paper: finitely generated groups. Already in this discrete setup, invariant random subgroups play an important role in graph convergence [HLS14], stability properties of groups [BLT19] and the analysis of dynamical systems [SZ94,Bow14] for example.

So, fix a finitely generated group Γ. An invariant random subgroup (or IRS) of Γ is a random variable taking values in the space of all subgroups of Γ, whose law is invariant under the conjugation action of Γ. For example, every normal subgroup of Γ is an IRS. More generally, if H ≤ Γ has only finitely many conjugates, then a uniformly random sample of its conjugates is an IRS. As finite index subgroups have only finitely many conjugates, they induce IRSs which are called elementary . To generate more examples, one can take convex combinations and weak* limits of elementary IRSs, and the IRSs that arise this way are called co-sofic . It turns out that for some groups every IRS is co-sofic, and for others there are non co-sofic IRSs (cf. [BLT19]). The Aldous-Lyons Conjecture can be formulated as follows:

## Are all IRSs of a (non-commutative) free group co-sofic?

For the rest of the paper, this is the formulation that we tackle, and it is known - and we explain it in the following paragraphs - to be equivalent to the probability theoretic formulation on Benjamini-Schramm limits of finite graphs.

The law (or distribution) of an IRS is a Borel probability measure µ on sub (Γ), the space of subgroups of Γ. We let IRS(Γ) denote the space of all such measures. By abuse of language, we say that µ is an IRS if µ ∈ IRS(Γ). To see the relation between the two formulations of the Aldous-Lyons Conjecture, note that if H is a subgroup of Γ, then the Schreier coset graph of H \ Γ with respect to some generating set S is a rooted

(directed, edge-labeled) graph, with the root being the coset of the identity. This gives a map from the space of subgroups sub (Γ) to the space of isomorphism classes of rooted (edge-labeled, directed) graphs.

If µ ∈ IRS(Γ) then µ pushes forward under this map to a unimodular measure [AGV14, Proposition 14]. Moreover, if µ is elementary, then its pushforward is induced by uniformly choosing a root of some finite connected graph. Therefore, if µ is co-sofic, then its pushforward is sofic.

Now, consider the special case in which Γ = F ( S ) is the free group generated by a finite set S . Suppose µ is an invariant random subgroup of Γ, and that the (random) Schreier coset graph of µ is sofic (in the directed, edge-labeled rooted graph category). This means there exists a sequence of finite directed, edge-labeled graphs G i which Benjamini-Schramm converge to the (random) Schreier coset graph of µ . After perturbing the given sequence if necessary, we may assume that each G i is itself a Schreier coset graph with respect to some finiteindex subgroup H i of F ( S ) - the existence of such perturbations is exactly where the freeness of the group F ( S ) plays a role. Moreover, if ˜ H i is a uniformly random conjugate of H i , then the distribution of ˜ H i converges to µ . Therefore, a positive solution to the Aldous-Lyons Conjecture implies that every IRS of F ( S ) is co-sofic. 2

## Our approach.

What is a subgroup test? The set IRS( F ) of all IRSs of the free group and the set IRS sof ( F ) of co-sofic IRSs of the free group are both convex. Thus, the Aldous-Lyons Conjecture is asking whether certain convex sets can be separated. A natural way to distinguish between two convex sets is to use (continuous) linear functionals. So, in order to separate the above, one should search for a rich enough collection of functionals. Subgroup tests and their values will play this exact role.

A challenge is a continuous map from sub ( F ) to { 0 1 , } . A subgroup test T is a probability distribution on a finite set of challenges. One can integrate any subgroup test against any probability measure over sub ( F ). If π is in IRS( F ), then this integral is called the value of the strategy π against the test T . Many natural and well studied properties of groups, specifically soficity and pointwise permutation stability, can be formulated as properties of subgroup tests.

The terminology of 'tests' and 'values' originates in the field of interactive proofs in computer science. An interactive proof designates an interaction between two entities, a 'verifier' and a 'prover'. The goal of the prover is to convince the verifier of the validity of a certain claim, and the goal of the verifier is to test the prover so that it accepts the interaction only if the claim is indeed correct. Examples of 'claims' studied in computer science are the 3-colorability of a given input graph, or that a Turing machine whose description is passed as input halts. In our approach, the methods of the verifier and the prover are restricted. The prover is required to sample an element of sub ( F ). The sampling method itself is restricted to some sub-class of IRSs (e.g., elementary IRSs); the choice of distribution according which to sample is the only degree of freedom the prover has, and is called its strategy . The verifier gets access to (the indicator function of) the prover's sampled subgroup H , and it makes a decision whether to accept or reject this subgroup. To decide, the verifier holds some finite set K ⊆ F -known beforehand to the prover - and according to which combinations of elements of K are contained in H , it accepts or rejects; the rules that control which combinations of elements result in acceptance and which combinations result in rejection are also know to the prover beforehand. The value of a strategy in a game is the probability, taken over the prover's sampling and the verifier's probabilistic choices, that the verifier makes the decision to accept when interacting with a prover using this strategy.

2 There is a standard 'decoration of graphs' technique that allows one to show that the directed, edge labeled (with finitely many labels) version of the Aldous-Lyons conjecture is equivalent to the non-directed, non-edge labeled version. As B´ alint Vir´g pointed a to us, the same technique is used, e.g., to show that every group is the automorphism group of some graph. As this is standard, we do not elaborate on it anymore.

In spite of these restrictions, it is possible to verify hard computational problems in this setup. 3 For example, it is not difficult to design a subgroup test such that there is a value-1 strategy for this test if and only if a given graph is 3-colorable. Jumping ahead, the correct analogy is with the theory of multiprover interactive proofs, and even more specifically interactive proofs with quantum provers sharing entanglement, also known as non-local games. We explain below this connection, which plays an essential role in the second part of this paper.

What is a non-local game? Morally, non-local games originated in Bell's resolution [Bel64] of the EinsteinPodolsky-Rosen paradox [EPR35]. Einstein was famously concerned by the ability of space-time separated particles to correlate in ways that might violate relativity, a possibility that seemed to be suggested by the mathematical modeling of quantum mechanics. Einstein argued for a local hidden variable theory - namely, that the particles did share some information beforehand, which allowed them to correlate - and that physicists should search for this hidden information. Bell provided a thought experiment, that in modern jargon is an instance of a non-local game, which proves that the kinds of correlations that arise from isolated quantum mechanical systems are intrinsically different from those that could be generated in any hidden variable model. Bell's work lay the foundation for the subsequent design, and execution, of experiments which verify the existence of quantum entanglement (and thus refute Einstein's approach; see also [CHSH69]). The 2022 Nobel prize in physics was awarded to Aspect, Clauser and Zeilinger, partly for performing non-local games as experiments and verifying that the winning statistics in the games exceeds what local hidden variable models allow.

A correlation is a function p : A × A × X × X → [0 , 1], where X and A are finite sets, such that for every pair x, y ∈ X the function p ( · , ·| x, y ) is a probability distribution over A × A -the quantity p a, b x, y ( | ) should be thought of as the answer to 'what is the probability a and b are provided as answers given that x and y were asked as questions?'; this cryptic phrase will soon be clarified. A correlation p is said to be deterministic if there are two functions f , f 1 2 : X → A such that p a, b x, y ( | ) = 1 only if f 1 ( x ) = a and f 2 ( y ) = b . The convex hull C c of deterministic correlations is the set of local or classical correlations. 4 On the other hand, the quantum correlations C q are those that can be generated by performing quantum measurements on a (finite-dimensional) bipartite physical system, where the measurement on one part depends only on x and generates a , while the measurement on the other part depends only on y and generates b . For a formal description, see Remark 6.8. The set C q is convex, but interestingly it is not closed [Slo19].

A non-local game G is specified by a probability distribution µ on the set X × X , and a decision function D : X × X × A × A →{ 0 1 , } . 5 The interpretation of this combinatorial object as a 'game' comes from thinking of it (similarly to subgroup tests) as an interactive proof, but this time with two provers, a la [BOGKW88]. The common dramatization goes as follows: Two provers are spatially separated. The verifier samples a pair of 'questions' x, y ∼ µ , and 'asks' one prover x and the other y . The provers then apply some local procedure to choose their 'answers' a and b respectively. Finally, the verifier accepts if D x,y,a,b ( ) = 1 and rejects otherwise.

Since the process by which the provers generate their answers is hidden to us, we can only 'observe' (samples from) the distribution of answers given questions, namely, the underlying correlation. So, the correlation can be thought of as the 'strategy' used by the provers (similar to the way IRSs are seen as strategies for the prover

3 For the expert, we note that restrictions on the prover and verifier can affect both the completeness and soundness properties of a proof system. Hence, a priori, they may either lower or raise the complexity of the associated class of interactive proofs compared to classical single-prover interactive proofs.

4 An example of a non-local correlation is p a, b x, y ( | ) = 1 only when a = y and b = x . Intuitively, this is because this correlation implies signaling from one system to the other.

5 As can be seen in Section 1.5, our definition of non-local games is slightly different. This difference is mainly cosmetic, and is driven by our motivation to relate non-local games to subgroup tests.

in a subgroup test). Bell's separation of C c from C q amounts to devising a game that is 'easy' for players that use quantum correlations, yet 'hard' for players that use only classical ones.

Now, there is more than one candidate mathematical model for entanglement in quantum mechanics. A slightly generalized model, suggested by Tsirelson [Tsi93], gives birth to a set of correlations known as quantum commuting correlations C qc . This set is closed and contains the quantum correlations. Tsirelson famously asked whether the closure of C q is equal to C qc [Tsi06]. At this point, we hope the type of problem already resonates with the reader, as this is again a separation of convex sets type of problem. 6

Harnessing undecidability. It was known that if the quantum correlations are dense in the quantum commuting correlations, then the complexity class of multiprover interactive proofs with entangled provers ( MIP ∗ ) contains only decidable languages. By proving that the Halting Problem, which is undecidable, is in MIP ∗ , the authors of [JNV + 21] were able to resolve Tsirelson's problem in the negative.

In this paper a similar path is followed: Rather than directly find a functional that separates the co-sofic and general IRSs of the free group, we describe a computational problem - approximating the sofic value of a subgroup test - whose undecidability implies a negative resolution of the Aldous-Lyons conjecture. Our approach can be described in two steps: First, show that a positive solution to the Aldous-Lyons Conjecture implies that approximating the sofic value of a subgroup test is decidable. Second, prove that this computational task is undecidable.

Elaborating on the first, given a subgroup test T , we prove that its optimal value against co-sofic IRSs which we call the sofic value of T -can be approximated from below, and its optimal value against any IRS which we call the ergodic value of T -can be approximated from above. Thus, if the Aldous-Lyons Conjecture has a positive answer, then the sofic and ergodic value of a test always agree, and using the aforementioned approximation procedures they can be calculated to any predetermined accuracy.

Elaborating on the second, we provide a mechanism for translating certain non-local games (see Section 1.5), which we call tailored non-local games , to subgroup tests. This translation is essentially value preserving. Namely, if the non-local game had a (certain kind) of perfect quantum strategy - which we call a Z -aligned permutation strategy that commutes along edges - then the analogous subgroup test has a perfect (co-sofic) strategy. In the other direction, if the subgroup test has an almost perfect (co-sofic) strategy, then the non-local game has an almost perfect strategy. Hence, a certain strengthening of the reduction in [JNV + 21], which states that small additive constant approximations to the value of tailored non-local game are undecidable (Theorem 7.4), implies that the sofic value of a game cannot be approximated to arbitrary precision. Thus, the AldousLyons Conjecture has a negative solution.

The rest of the introduction provides a deeper dive into the definitions, results and ideas of this paper.

- 1.1. Subgroup Tests. Let S be a finite set, F = F ( S ) be the free group with basis S , sub ( F ) the collection of subgroups of F and Prob( sub ( F )) the set of all Borel probability measures on sub ( F ). A challenge is a pair ( K D ; ) such that K is a finite subset of F , and D is a function from subsets of K to { 0 1 , } . A subset A ⊆ F passes the challenge ( K D ; ) if D A ( ∩ K ) = 1, and fails it otherwise. A test T is a finite collection of challenges { ( K D i ; i ) } i ∈ Q , where Q is a finite index set, together with a probability distribution µ over the set Q . A strategy

6 Connes' embedding problem (CEP) is also a separation of convex sets type of problem, specifically, separating all characters of the free group from those that are limits of finite dimensional characters. This problem was shown [Fri12, JNP + 11, Oza13] to be equivalent to Tsirelson's problem, and also has close connections with invariant random subgroups - as every IRS induces a character. We omit discussions on the relations between this work and CEP from the text, as they are not particularly helpful for understanding our approach.

is a (Borel) probability distribution over subgroups of the free group, namely an element π ∈ Prob( sub ( F )). One can run the test T against π , as follows. First the verifier samples i ∈ Q according to µ . Next, the prover samples a subgroup H according to π . Finally, the verifier makes the decision to accept if H passes the i th challenge ( K D i ; i ), and reject if H fails the i th challenge.

The value of using the strategy π against the test T is its acceptance probability, namely

$$\text{val} ( \mathcal { T }, \pi ) = \mathbb { E } _ { H \sim \pi } \mathbb { E } _ { i \sim \mu } [ D _ { i } ( H \cap K _ { i } ) ].$$

For a fixed T , the value is a continuous linear functional from probability distributions over subgroups of F to R . Hence, it enables us to study convex subsets of Prob( sub ( F )) by their optimal value against a given test.

Remark 1.1 . As mentioned earlier, a challenge is, essentially, a continuous map from the space of subgroups of F to { 0 1 , } . One can extract from any such continuous map a challenge ( K D ; ) that describes it and vice versa. Therefore, a test is a convex combination of continuous maps from sub ( F ) to { 0 1 , } , and the value is integration of this map against a (probability) measure.

- 1.2. Invariant random subgroups. As sub ( F ) inherits the product topology from the power set { 0 1 , } F , it is compact. Every action of a group Γ on a set X extends naturally to an action of Γ on the power set { 0 1 , } X by

$$\forall \gamma \in \Gamma, A \subseteq X \ \colon \ \gamma. A = \{ \gamma. a \ | \ a \in A \} \. \\ \psi \quad \dots \quad \psi \cdot \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta \ \ \delta.$$

Hence, the conjugation action of F on itself is inherited by { 0 1 , } F . Also, sub ( F ) ⊆ { 0 1 , } F is preserved by this action. Hence, the conjugation action extends to its power set { 0 1 , } sub ( F ) by

$$\forall w \in \mathcal { F }, A \subseteq \text{sub} ( \mathcal { F } ) \ \colon \ w. A = \{ w H w ^ { - 1 } \ | \ H \in A \} \.$$

The conjugation action of F further extends to Prob( sub ( F )): For every Borel set B ⊆ sub ( F ) and µ ∈ Prob( sub ( F )), we have

$$( w. \mu ) ( B ) = \mu ( w ^ { - 1 }. B ) \,.$$

Definition 1.2. The set of invariant random subgroups IRS( F ) consists of all probability measures in Prob( sub ( F )) that are invariant under the action of F .

The ergodic value of a test T is the best performance of a strategy π ∈ IRS( F ) against it, namely

$$\text{(1.1)} & & \text{val} _ { \text{erg} } ( \mathcal { T } ) = \sup \{ \text{val} ( \mathcal { T }, \pi ) \ | \ \pi \in \text{IRS} ( \mathcal { F } ) \} \.$$

Remark 1.3 . The extremal points in the convex set IRS(Γ) are commonly referred to as ergodic IRSs . As we take the supremum of a linear functional over a convex compact set, the optimum is obtained on an extremal point, which explains the phrase ergodic value .

- 1.3. Finitely described invariant random subgroups. Let X be a finite set, and let Sym( X ) be the symmetric group acting on X . Every map σ : S → Sym( X ) extends uniquely to an action of F = F ( S ) on X . For a vertex x ∈ X , we can define its stabilizer to be

$$\text{Stab} ( \sigma, x ) & = \left \{ w \in \mathcal { F } \, | \, \sigma ( w ). x = x \right \} \,,$$

which is a subgroup of F . Hence, we can associate with σ : S → Sym( X ) an IRS of F via the following sampling procedure: (1) Choose x ∈ X uniformly at random. (2) Output Stab( σ, x ). We denote by Φ the map from finite actions of F to IRS( F ) defined by this procedure, namely

$$\Phi ( \sigma ) = \underset { r \in X } { \mathbb { E } } \left [ \mathbf 1 _ { \text{Stab} ( \sigma, x ) } \right ] \,,$$

$$\tau \tau, \, \text{maxy} \\ = \frac { \mathbb { E } } { x \in X } \left [ 1 _ { \text{Stab} ( \sigma, x ) } \right ],$$

where 1 H is the Dirac measure concentrated on the subgroup H and E x ∈ X is the expectation according to the uniform measure over X . The set of finitely described invariant random subgroups IRS fd ( F ) is the image of the map Φ in IRS( F ).

Definition 1.4. The sofic value of a test T is the (asymptotic) best performance of a strategy π ∈ IRS fd ( F ) against it, namely

$$\Lambda \quad \ v a _ { \text{so} } ( \mathcal { T } ) = \sup \left \{ \text{val} ( \mathcal { T }, \Phi ( \sigma ) ) \, | \, | X | < \infty, \, \sigma \colon S \to \text{Sym} ( X ) \right \}. \\ \text{Remark 1.5. The name soic value is appropriate, as demonstrated in Section 4.2. Furthermore, we of}$$

Remark 1.5 . The name sofic value is appropriate, as demonstrated in Section 4.2. Furthermore, we often abuse notation and use val( T , σ ) instead of val( T , Φ( σ )), even though the action itself is not an IRS.

Since IRS fd ( F ) ⊆ IRS( F ), we have val sof ( T ) ≤ val erg ( T ) for every test T . The Aldous-Lyons conjecture [AL07] can be formulated as follows:

Conjecture 1.6 (Aldous-Lyons, cf. Section 6 of [Gel18]) . Is IRS fd ( F ) weak* dense in IRS( F ) ?

Remark 1.7 . In their paper [AL07], Aldous and Lyons ask this as a question. In the passing of time, the positive form of this problem, namely that IRS fd ( F ) is dense in IRS( F ), received the name The Aldous-Lyons Conjecture (cf. [Ald07]). Thus, we use the more common 'Conjecture' phrasing instead of Problem.

The algebraic formulation we provided earlier, which can also be found in Section 6 of [Gel18], may seem different from the above. The question was whether every invariant random subgroup of F is co-sofic , where co-sofic means an IRS which is the weak* limit of convex combinations of uniform distributions over finite index subgroups. Since the finitely described IRSs are dense in the co-sofic ones, the formulation in Conjecture 1.6 is equivalent to this standard (algebraic) formulation.

Lastly, the term co-sofic is closely related to the better known term of a sofic group (cf. Definition 4.4). A finitely presented group F /N is sofic if and only if the Dirac measure concentrated on N is a co-sofic IRS (cf. Proposition 6.1 in [Gel18]). Thus, a positive solution to the Aldous-Lyons Conjecture 1.6 implies in particular that every group is sofic. 7

Corollary 1.8. Since val( T , · ) is a continuous functional, a positive solution to the Aldous-Lyons Conjecture 1.6 implies that for every test T , val sof ( T ) = val erg ( T ) .

Remark 1.9 . Due to the relation between subgroups of the free group and Schreier graphs, one can view subgroup tests as a new property testing model for (edge-labeled) graphs: Let X be a finite set and σ : S → X a transitive action (the non-transitive case is a convex combination of transitive ones). For x ∈ X , the stabilizer Stab( σ, x ) is exactly the set of labeled paths in the Schreier graph of F ( S ) with respect to Stab( σ, x ) and S that begin and end at x , namely, closed paths originating from x . Thus, when the finitely described IRS Φ( σ ) is put against a test T , we actually test the aforementioned Schreier graph in the following way: First, choose a vertex x ∈ X uniformly at random and sample i ∼ µ . List the paths from K i and for each one check whether it is closed or open. According to this check, decide using D i whether to accept or reject.

1.4. Decidability of approximating the sofic value. If the challenge distribution µ in a subgroup test T is rational, then T can be encoded as a finite bit string. There are many (non-equivalent) ways of doing so. Assume we fixed some encoding for tests with rational challenge distributions such that, given the encoding, all underlying combinatorial data of the test can be calculated in finite time. Namely, the set of generators S ,

7 The way we formulate it, a positive solution to the Aldous-Lyons Conjecture only implies that all finitely presented groups are sofic. It is standard to deduce it for all groups from the finitely presented ones [ES04].

the indexing set of challenges Q , the collection of challenges { ( K D i ; i ) } i ∈ Q and the distribution µ can all be read from the encoding in finite time.

Theorem 1.10 (Main Theorem I) . For every fixed encoding of tests such that all combinatorial data of the test can be read from it in finite time:

- (1) There is a Turing machine M 1 that takes as an input (the encoding of) a test T , and outputs an infinite sequence of non-decreasing numbers ( α t ) ∞ t =1 ⊆ [0 , 1] such that lim t →∞ α t = val sof ( T ) .
- (2) There is a Turing machine M 2 that takes as an input (the encoding of) a test T , and outputs an infinite sequence of non-increasing numbers ( β t ) ∞ t =1 ⊆ [0 , 1] such that lim t →∞ β t = val erg ( T ) .

Remark 1.11 . Clause (2) of Theorem 1.10 should be compared to the Navascu´s-Pironio-Ac´ ın (NPA) hierarchy e in the study of non-local games [NPA08]. See also the introduction of [JNV + 21].

Corollary 1.12. If the Aldous-Lyons Conjecture 1.6 has a positive solution, then for every θ &gt; 0 , there is a Turing machine which accepts a subgroup test T as input and outputs its sofic value val sof ( T ) up to an additive error of at most θ .

- 1.5. Tailored non-local games and their associated subgroup tests. As described before, the standard definition of a (non-local) game consists of two finite sets, a questions set X and an answers set A , together with a probability distribution µ over X × X and a decision function D X : × X × A × A →{ 0 1 , } . In this paper, we use a slightly modified definition, that makes the connection with subgroup tests clearer. Before diving into our alternative definition, note first that the distribution µ defines a graph structure on X , by associating edges with its support. Furthermore, as the exact choice of A is irrelevant, we can assume it is the set of all bit strings up to some length Λ.
- A (synchronous, non-local) game consists of a graph G = ( V, E ), a distribution µ over E , a length function /lscript : V → N , formal sets of generators S x = { X x,i | 1 ≤ i ≤ /lscript ( x ) } -the union of which is denoted by S = ⋃ x ∈ V S x -and decision functions D xy : { 0 1 , } S xy →{ 0 1 , } for every edge xy ∈ E , where S xy = S x ∪ S y . 8 A (synchronous, quantum) strategy for G is a map ρ : ⋃ x ∈ V S x → U n ( ), where the images are involutions, and ρ S ( x ) commute for every fixed x ∈ V . 9 Such a strategy defines for every xy ∈ E a probability distribution over maps γ : S xy →{ 0 1 , } in the following way: For every X ∈ S , let P X 0 be the projection on the (+1)-eigenspace of ρ ( X ), and P X 1 the projection on its ( -1)-eigenspace. Furthermore, let τ be the dimension normalized trace on n × n matrices. Then, the probability that γ : S xy →{ 0 1 , } is sampled according to ρ is by definition

A map γ sampled that way is said to be sampled according to ρ , and we denote it by γ ∼ ρ . 10 Relating to standard notations, we remark that by letting a = γ | S x and b = γ | S y , the correlation p a, b x, y ( | ) induced by the

$$1 \text{hen, the probability that } \gamma \colon S _ { x y } \to \{ 0, 1 \} \, \text{is sampled according to } \rho \, \text{is by death} \, \\ ( 1. 5 ) & & \tau \left ( \prod _ { X \in S _ { x } } P _ { \gamma ( X ) } ^ { X } \prod _ { Y \in S _ { y } } P _ { \gamma ( Y ) } ^ { Y } \right ). \\ A \, \text{map } \gamma \, \text{sampled that way is said to be sampled according to } \rho, \text{and we denot}$$

8 So, the main difference in our definition, is that the decision function D rejects automatically answers that are not of the appropriate length according to /lscript .

9 This is again not the standard definition of a quantum strategy. Unpacking our definition, ρ associates an observable (Hermitian operator on a finite-dimensional Hilbert space that squares to the identity) with each bit of the answer when asked for x ∈ V . Since the answer must be totally measured, all the observables associated with a specific vertex must commute. The fact there is a single map ρ , and not one for each prover, is the synchronicity of this strategy.

10 Note that this sampling depends on the chosen edge xy ∈ E . Namely, though implicit in the notation, γ is defined from S xy for some edge xy ∈ E . It is important to note that γ is not globally defined on all of S .

quantum strategy ρ (as in Remark 6.8) agrees with formula (1.5). In a similar manner to subgroup tests, one can run the game G against the strategy ρ : First, the verifier samples an edge xy ∈ E according to µ . Then, the prover samples γ : S xy →{ 0 1 , } according to ρ . Finally, the verifier accepts if D xy ( γ ) = 1, and rejects otherwise.

As for subgroup tests, the value of the strategy ρ against the non-local game G is its acceptance probability when ran against the game. Namely,

$$\text{val} ( \mathcal { G }, \rho ) = \mathbb { E } _ { x y \sim \mu } \mathbb { E } _ { \gamma \sim \rho } [ D _ { x y } ( \gamma ) ] \,.$$

The (synchronous) quantum value of G , val ∗ ( G ), is the supremum of val( G , ρ ) over all possible quantum strategies against G .

The main result in [JNV + 21] (recalled in detail in Theorem 6.10 herein) is a reduction from the Halting Problem to approximating the quantum value of a game. Our main contribution in the second half of this paper (Sections 6,7 and 8) is a mapping from a specific sub-class of non-local games - which we term tailored non-local games and describe further below - to subgroup tests, that (almost) preserves their values.

Theorem 1.13 (Main Theorem II, informal. For the formal version see Theorem 7.3) . There is a transformation that takes as input a tailored non-local game (see Definition 6.22) and outputs a subgroup test (which we call the associated synchronous subgroup test, see Definition 7.1), such that:

- (1) If the game had a perfect (i.e., a value 1 ) Z -aligned, commuting along edges, permutation strategy (see Definitions 6.11 and 6.24), then the associated subgroup test has a perfect strategy.
- (2) Every almost perfect finitely described strategy for the associated subgroup test can be transformed into an almost perfect quantum strategy to the original tailored non-local game.

Informally, a tailored game is one where the decision function D xy takes the following form. First, D xy examines the value taken by γ on a subset of the generators S x ∪ S y (we refer to these as readable variables). Based on this, D xy determines a collection of linear equations on the entire string γ . Finally, D xy accepts if and only if all these equations are satisfied. This form for the game can be seen as a generalization of binary linear constraint system games (Example 6.26), which corresponds to the case where the set of readable variables is empty.

A permutation strategy , as its name suggests, is a quantum strategy which is induced by permutations. Such a strategy is said Z -aligned when the observables associated with the readable variables (i.e. the bits of the answer γ that control the parity checks in the tailored game) are all diagonal matrices (with respect to some natural basis). The restriction to Z -aligned strategies is crucial for item (1) in Theorem 7.3 above to hold.

In a companion paper [BCV24], we prove that the reduction of the Halting Problem to approximating the quantum value of a game presented in [JNV + 21] can be modified such that the resulting non-local game is tailored and satisfies the required stronger assumptions (Theorem 7.4): If the input Turing machine halts, then the game has a perfect Z -aligned permutation strategy that commutes along edges, and if the input Turing machine does not halt, then the value of the game is bounded from above by 1 2 / . Therefore, together with our mapping from non-local games to subgroup tests, we deduce that approximating the sofic value of a game is undecidable. In turn, by Corollary 1.12, the Aldous-Lyons Conjecture 1.6 has a negative solution.

Remark 1.14 . In [JNV + 21, Section 12.3], the authors were able to specify a non-local game whose quantum value is bounded above by 1 2 / but has a perfect quantum commuting strategy. Using the results of [KPS18], which we elaborate on further in the next remark, this implies the existence of a finitely presented ∗ -algebra which can be endowed with a tracial state and cannot be embedded into an ultrapower of the hyperfinite II 1

factor. This is a somewhat constructive counter example, but the state itself is only proven to exist and does not have a constructive form (at this point). By the various formulations of Connes' embedding problem, this proves that there is a non-hyperlinear character of the free group, which is the analogue of a non co-sofic IRS of the free group, but it is provided in a non-constructive form.

By applying the 'same' construction as in [JNV + 21, Section 12.3] with the algorithm constructed in Theorem 1.10 replacing the NPA hierarchy algorithm, one can pin down an explicit subgroup test with perfect ergodic strategy but all sofic strategies bounded above by some constant (which can be approximated by following the proofs). This is the most constructive we can get in this case, namely, the specific non co-sofic IRS which is the perfect strategy for this subgroup test is proven only to exist, and is not constructed. Thus, we decided not to specify this test.

It would be very interesting to find an explicit non co-sofic IRS, namely separate between IRS( F ) and IRS fd ( F ) in a constructive manner.

Remark 1.15 . We comment on a natural attempt to extend the construction of [JNV + 21] so as to directly deduce the existence of a non-sofic group, a result which would imply a negative answer to the Aldous-Lyons Conjecture.

The idea (which is folklore, and explicitly mentioned in [PS23]) is as follows. It is well-known that to every synchronous game G one can associate an algebra A ( G ) such that there is a tight connection between the C ∗ -representation theory of this algebra and perfect values for the game in various correlation sets [PSS + 16, KPS18,HMPS19]. In the special case where G is a linear constraint system (LCS) game, there is a group Γ such that A ( G ) is (isomorphic to the completion of) the complex group algebra C [Γ] [KPS18,Gol21]. 11

Now, if the reduction given in [JNV + 21] returned only LCS games, then one would obtain the following result: there exists an LCS game with a perfect quantum commuting strategy, but no (asymptotically) perfect quantum strategy. By the connection mentioned above this implies that the group Γ associated with A ( G ) is non-hyperlinear. As every sofic group is hyperlinear, one would thus obtain an example of a non-sofic group.

Since the reduction in [JNV + 21] does not return LCS games, a workaround could be to find an embedding from the algebra A ( G ), where G is returned by [JNV + 21], into A ( G ′ ) where G ′ is an LCS game. Obstacles to this 'black-box' approach are discussed in [PS23].

One can view our approach as finding a 'sweet spot' that is in some sense half-way between synchronous games, which were used in [JNV + 21], and LCS games. This is because tailored games are a natural generalization of LCS games. In the companion paper we show that [JNV + 21] can be adapted to return tailored games, and in the present paper we show that this suffices to resolve the Aldous-Lyons Conjecture. The existence of non-sofic groups (and non-hyperlinear groups) remains an elusive open problem.

- 1.6. Structure of the paper. In Section 2, we prove structural results about invariant random subgroups, some of which are standard and well known to experts. In Section 3, we prove our first main theorem, Theorem 1.10, and draw corollaries from it. In Section 4, we provide several examples of subgroup tests, inspired by both group theory and complexity theory. In Section 5, we discuss a rigidity property of tests that generalizes group stability and which is analogous to robustness of non-local games. In Section 6, we define tailored non-local games and analyze their properties. In Section 7, we describe the (almost) value preserving correspondence between tailored non-local games and synchronous subgroup tests, informally outlined in Theorem 1.13. This allows us in Corollary 7.5 to provide a negative solution to the Aldous-Lyons Conjecture 1.6. The proof of the aforementioned value preserving correspondence, Theorem 7.3, is proved in Section 8. Theorem 7.4, which

11 Actually, it is isomorphic to the completion of C [Γ] / 〈 J +1 〉 , where J is a special generator in Γ and 〈 J +1 is the two-sided ideal 〉 generated by J +1 in C [Γ].

is the other main ingredient in our refutation, is proved in a companion paper [BCV24]. There is no open problems section, but further research directions can be found in Remarks 1.14, 1.15 and 8.13.

For a reader who seeks the main ideas of the paper without diving too deep into the proofs, we suggest reading, in addition to the introduction, only Sections 3 and 7.

Acknowledgements. We thank Alon Dogon for reading an early draft of this paper and providing many useful improvements to the presentation. We would also like to thank Mikael de la Salle for various discussions along the way. Finally, we want to thank Peter Sarnak for organizing a seminar on 'strong convergence' in Princeton and asking the second author to give a talk, as it organized his thoughts and led to the current presentation of ideas.

Lewis Bowen is supported by NSF grant DMS-2154680. Michael Chapman acknowledges with gratitude the Simons Society of Fellows and is supported by a grant from the Simons Foundation (N. 965535). Alex Lubotzky is supported by the European Research Council (ERC) under the European Union's Horizon 2020 (N. 882751), and by a research grant from the Center for New Scientists at the Weizmann Institute of Science. Thomas Vidick is supported by a research grant from the Center for New Scientists at the Weizmann Institute of Science, a Simons Investigator award, AFOSR Grant No. FA9550-22-1-0391, and ERC Consolidator Grant VerNisQDevS (101086733).

## 2. Group theoretic preliminaries

- 2.1. Topology (and other properties) of invariant random subgroups. 12 We first go through some properties of the space { 0 1 , } F (induced with the product topology). For every K,L ⊆ F , let

$$\mathcal { C } ( K, L ) = \{ A \subseteq \mathcal { F } \ | \ K \subseteq A, \ L \cap A = \emptyset \} \subseteq \{ 0, 1 \} ^ { \mathcal { F } }.$$

Then,

- (1) When K and L are finite, the set C ( K,L ) is open and closed. Moreover, the collection

$$\{ \mathcal { C } ( K, L ) \ | \ K, L \subseteq \mathcal { F }, \ | K |, | L | < \infty \}$$

is a basis for the topology of { 0 1 , } F . In addition, { 0 1 , } F is compact.

- (2) For every w ∈ F and subsets K,L ⊆ F we have

$$w. \mathcal { C } ( K, L ) = \mathcal { C } ( w K w ^ { - 1 }, w L w ^ { - 1 } ).$$

The following is a standard fact. A proof is added because elements of it are later used in Lemma 2.12.

Claim 2.1. The set of subgroups sub ( F ) is closed in the collection of all subsets { 0 1 , } F .

Proof. A subset A ⊆ F is a subgroup if it satisfies the following three conditions:

$$( 1 ) \, \text{Id} _ { \mathcal { F } } \in A \, \ \ ( 2 ) \ w \in A \implies w ^ { - 1 } \in A \, \ \ ( 3 ) \ w, w ^ { \prime } \in A \implies w \cdot w ^ { \prime } \in A.$$

12 The content of this section is standard. For example, it appears in Section 3 of [AGV14].

For every w,w ′ ∈ F , define the following open sets: The subsets not containing Id F , C Id = C ∅ { ( , Id F } ). The subsets containing w ∈ F but not w -1 , C w = C { ( w , } { w -1 } ). The subsets containing w,w ′ ∈ F but not w · w ′ , C w,w ′ = C { ( w,w ′ } { , w · w ′ } ). Then,

$$\left ( \bigcup _ { w, w ^ { \prime } \in \mathcal { F } } ^ { \prime } C _ { w, w ^ { \prime } } \right ) \cup \left ( \bigcup _ { w \in \mathcal { F } } C _ { w } \right ) \cup C _ { \text{Id} } = \{ 0, 1 \} ^ { \mathcal { F } } \, \sum \mathfrak { s u b } ( \mathcal { F } ), \\ \mathfrak { s u b } \,. \quad \,. \quad \,.$$

which proves that sub ( F ) is a closed set.

/square

Recall the definition of IRS( F ), the invariant random subgroups of the free group F (Definition 1.2).

Fact 2.2. Let µ, ν ∈ Prob( 0 1 { , } F ) . Then,

- (1) µ = ν if and only if µ ( C ( K,L )) = ν ( C ( K,L )) for every finite K,L ⊆ F .
- (2) µ is conjugation invariant if and only if for every s ∈ S we have s.µ = µ . Hence, µ ∈ IRS( F ) if and only if for all s ∈ S and finite K,L ⊆ F we have µ ( C ( K,L )) = µ s. ( C ( K,L )) .

A sequence of measures µ n ∈ Prob( 0 1 { , } F ) is said to weak* converge to µ if for all continuous f : { 0 1 , } F → R ,

$$\underset { H \sim \mu _ { n } } { \mathbb { E } } [ f ( H ) ] \xrightarrow { n \to \infty } \underset { H \sim \mu } { \mathbb { E } } [ f ( H ) ].$$

We denote weak convergence by µ n w ∗ - -→ µ .

Remark 2.3 . In our context, there is a more 'down to earth' way of viewing weak* convergence. For every finite subset A ⊆ F , and every probability measure µ ∈ Prob( 0 1 { , } F ), we can define a probability measure µ ∩ A ∈ Prob( 0 1 { , } A ) ⊆ R 2 A by

$$\forall B \subseteq A \ \colon \ \mu \cap A ( B ) = \mu ( \{ H \subseteq \mathcal { F } \, | \ H \cap A = B \} ).$$

Then, where the convergence on the right is the standard one in the Euclidean space R 2 A .

$$\mu _ { n } & \xrightarrow { w ^ { * } } \mu \iff \forall A \subseteq \mathcal { F }, | A | < \infty \ \colon \ \mu _ { n } \cap A \xrightarrow { n \to \infty } \mu \cap A, \\ \cdot \ \dots \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ - \ \dots \quad - \in A$$

Claim 2.4. The space Prob( 0 1 { , } F ) is compact in the weak* topology.

Proof. Since { 0 1 , } F is compact, the fact can be deduced from the Banach-Alaoglu Theorem (cf. Theorem 3.15 in [Rud91]). /square

- 2.2. Pseudo subgroups. For every B ⊆ C ⊆ F , the restriction map R B ⊆ C : { 0 1 , } C →{ 0 1 , } B is

$$\forall A \subseteq C \ \colon \ R _ { B \subseteq C } ( A ) = A \cap B.$$

When C = F we remove it from the notation and write R B instead of R B ⊆F . For sets K,L ⊆ B ⊆ F we can define

$$\mathcal { C } _ { B } ( K, L ) = \{ A \subseteq B \ | \ K \subseteq A, \ A \cap L = \emptyset \}.$$

Note that C F ( K,L ) = C ( K,L ).

Claim 2.5. Let K,L ⊆ B ⊆ C ⊆ F . Then R B ⊆ C ( C C ( K,L )) = C B ( K,L ) and R -1 B ⊆ C ( C B ( K,L )) = C C ( K,L . )

Proof. Let A ⊆ B and A ′ ⊆ C such that A = A ′ ∩ B . As K,L ⊆ B , the intersection of A ′ with K and L depends only on A ′ ∩ B = A . Hence

$$A \in \mathcal { C } _ { B } ( K, L ) \iff A ^ { \prime } \in \mathcal { C } _ { C } ( K, L ).$$

Adding this observation to the fact R B ⊆ C is onto proves the desired claim.

/square

Now, we can pushforward measures along the inverse system of restrictions. Namely, given B ⊆ C ⊆ F and a probability measure π on { 0 1 , } C we can define the probability measure R B ⊆ C ∗ π on { 0 1 , } B by

$$\forall Y \subseteq _ { \text{Borel} } \{ 0, 1 \} ^ { B } \, \colon \, \ R _ { B \subseteq C * } \pi ( Y ) = \pi ( R _ { B \subseteq C } ^ { - 1 } ( Y ) ).$$

Corollary 2.6. Claim 2.5 implies that R B ⊆ C is continuous. Therefore, R B ⊆ C ∗ : Prob( 0 1 { , } C ) → Prob( 0 1 { , } B ) is continuous.

Definition 2.7. Let B ⊆ F . A subset A ⊆ B is said to be a pseudo subgroup of B if there is a subgroup H ≤ F such that R B ( H ) = H ∩ B = A . Denote by P sub ( B ) the collection of pseudo subgroups of B . 13

Claim 2.8. Let A ⊆ B ⊆ F . Then, A is a pseudo subgroup of B if and only if 〈 A 〉 ∩ B = A , where 〈 A 〉 is the subgroup of F generated by A .

Proof. If there is a subgroup H for which A = R B ( H ) = H ∩ B ⊆ H , then in particular 〈 A 〉 ⊆ H . Because A is always contained in 〈 A 〉 ∩ B , we can conclude. /square

Corollary 2.9. Let A ⊆ B ⊆ C ⊆ F . If A is not a pseudo subgroup of B , and A ′ ⊆ C restricts to A (i.e., A ′ ∩ B = A ), then A ′ is not a pseudo subgroup of C .

Proof. By Claim 2.8, if A is not a pseudo subgroup of B , then there is a w ∈ B such that w / A ∈ while w ∈ 〈 A 〉 . Since w ∈ B ⊆ C , and A ′ ∩ B = A , the same w satisfies that w / A ∈ ′ while w ∈ 〈 A 〉 ⊆ 〈 A ′ 〉 , proving that A ′ is not a pseudo subgroup of C . /square

Definition 2.10. Let B ⊆ F be a subset.

- (1) The set P B is the collection of all π ∈ Prob( 0 1 { , } B ) that are concentrated on pseudo subgroups of B , namely π P ( sub ( B )) = 1. Equivalently, π ( { 0 1 , } B \ P sub ( B )) = 0.
- (2) The set Q B is the subset of P B of distributions that are S -invariant when defined . Namely, assuming K,L ⊆ B are finite subsets such that

$$\forall s \in S \cup S ^ { - 1 } \, \colon \, \ s K s ^ { - 1 }, s L s ^ { - 1 } \subseteq B,$$

we have π ( C B ( K,L )) = π ( C B ( sKs -1 , sLs -1 )). We call probability distributions in Q B pseudo invariant random subgroups over B , or pseudo IRSs in short.

- (3) Let ˜ P B = R -1 B ∗ ( P B ) and ˜ Q B = R -1 B ∗ ( Q B ).

Remark 2.11 . Note that P F = ˜ P F = Prob( sub ( F )) and Q F = ˜ Q F = IRS( F ).

Lemma 2.12. Let B ⊆ C ⊆ F be subsets.

13 Note that this collection is a closed subset of the subsets of B .

- (1) The restriction to B of a distribution over pseudo subgroups of C , is a distribution over pseudo subgroups of B . Namely,

$$\forall \pi \in \mathcal { P } _ { C } \, \colon \, R _ { B \subseteq C * } \pi \in \mathcal { P } _ { B }. \\ \theta \, \quad. \, \quad \dots \, \sim \, \sim \,.$$

Similarly, the restriction to B of a pseudo IRS of C is a pseudo IRS of B . Namely,

$$\forall \pi \in \mathcal { Q } _ { C } \ \colon \ R _ { B \subseteq C * } \pi \in \mathcal { Q } _ { B }.$$

- (2) The (Borel) probability distributions over subgroups of F are the intersection of pull-backs of all distributions over pseudo subgroups in finite subsets. Similarly, the IRSs of F are the intersection of pull-backs of all pseudo IRSs of finite subsets. Namely,

$$\bigcap _ { B \subseteq \mathcal { F }, | B | < \infty } \tilde { \mathcal { P } } _ { B } = \text{Prob} ( \text{sub} ( \mathcal { F } ) ), \quad \bigcap _ { B \subseteq \mathcal { F }, | B | < \infty } \tilde { \mathcal { Q } } _ { B } = \text{IRS} ( \mathcal { F } ).$$

Proof. Let π ∈ P C . By definition,

$$\pi ( \{ 0, 1 \} ^ { C } \, \slash \, P \text{sub} ( C ) ) = 0.$$

By Corollary 2.9,

$$R _ { B \subseteq C } ^ { - 1 } ( \{ 0, 1 \} ^ { B } \, \sum P \mathfrak { s u b } ( B ) ) \subseteq \{ 0, 1 \} ^ { C } \, \sum P \mathfrak { s u b } ( C ).$$

Hence, by the definition of the pushforward,

$$R _ { B \subseteq C * } \pi ( \{ 0, 1 \} ^ { B } \, \sum P \text{sub} ( B ) ) & = \pi ( R _ { B \subseteq C } ^ { - 1 } ( \{ 0, 1 \} ^ { B } \, \sum P \text{sub} ( B ) ) ) \\ & \leq \pi ( \{ 0, 1 \} ^ { C } \, \sum P \text{sub} ( C ) ) \\ & = 0,$$

and so R B ⊆ C ∗ π ∈ P B .

Assume further that π ∈ Q C . By Claim 2.5, for every finite K,L ⊆ B ,

$$R _ { B \subseteq C } ^ { - 1 } ( \mathcal { C } _ { B } ( K, L ) ) = \mathcal { C } _ { C } ( K, L ).$$

Thus

$$R _ { B \subseteq C _ { * } } \pi ( \mathcal { C } _ { B } ( K, L ) ) = \pi ( R _ { B \subseteq C } ^ { - 1 } ( \mathcal { C } _ { B } ( K, L ) ) ) = \pi ( \mathcal { C } _ { C } ( K, L ) ).$$

If K,L ⊆ B such that sKs -1 , sLs -1 ⊆ B for every s ∈ S ∪ S -1 , then the same applies to C since it contains B , and hence

$$R _ { B \subseteq C * } \pi ( \mathcal { C } _ { B } ( K, L ) ) & = \pi ( \mathcal { C } _ { C } ( K, L ) ) \\ & = \pi ( \mathcal { C } _ { C } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ) \\ & = R _ { B \subseteq C * } \pi ( \mathcal { C } _ { B } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ). \\ \int \in \mathcal { O } _ { - } \text{ and } ( 1 \ll \text{word}$$

Therefore R B ⊆ C ∗ π is in Q B and (1) is proved.

By clause (1), for every B ⊆ C ⊆ F we have ˜ P C ⊆ P ˜ B and ˜ Q C ⊆ Q ˜ B . In particular, when C = F we have Prob( sub ( F )) ⊆ P ˜ B and IRS( F ) ⊆ Q ˜ B . Hence

$$\div \theta _ { D } \colon \colon \colon \colon \colon \colon \colon \\ \text{Prob} ( \text{sub} ( \mathcal { F } ) ) \subseteq \bigcap _ { B \subseteq \mathcal { F }, | B | < \infty } \tilde { \mathcal { P } } _ { B }, \text{ \ IRS} ( \mathcal { F } ) \subseteq \bigcap _ { B \subseteq \mathcal { F }, | B | < \infty } \tilde { \mathcal { Q } } _ { B }.$$

We are left to prove the reverse containments. Recall the open cover of the complement of the subgroups described in the proof of Claim 2.1. Given π ∈ Prob( 0 1 { , } F ) such that π / ∈ Prob( sub ( F )), we have

Hence, by the union bound (Boole's inequality), there is either a pair w,w ′ ∈ F such that π C ( w,w ′ ) &gt; 0, or a single element w ∈ F such that π C ( w ) &gt; 0, or π C ( Id ) &gt; 0. Thus, if B = Id { F , w, w , w ′ · w , w ′ -1 } , then π / ∈ P ˜ B . In particular π / ∈ ⋂ ˜ P B , proving the first reverse containment.

$$\int \ln \text{the proof of $\Gamma$} \, \text{lam $2.1$. Given $\pi \in \text{rProd}(\{0,1)^{\prime}\mathcal{ }$} ) \, \text{such} \, \text{that $\pi \notin \text{rProd}(\mathcal{ }V\mathcal{ })$}, \, \text{we have} \\ \pi \left ( \left ( \bigcup _ { w, w ^ { \prime } \in \mathcal { F } } C _ { w, w ^ { \prime } } \right ) \cup \left ( \bigcup _ { w \in \mathcal { F } } C _ { w } \right ) \cup C _ { \text{Id} } \right ) = \pi ( \{ 0, 1 \} ^ { \mathcal { F } } \, \sum \, \text{sub} ( \mathcal { F } ) ) > 0. \\ y \, \text{ the union bound (Boole} ^ { \prime } s \, \text{inequality} ), \, \text{there is either a pair } w, w ^ { \prime } \in \mathcal { F } \, \text{such that $\pi (C _ { w, w ^ { \prime } } ) } \, ;$$

Lastly, let π ∈ ⋂ ˜ Q B . For every finite K,L ⊆ F , there is a larger enough finite set B such that K,L ⊆ B and also sKs -1 , sLs -1 ⊆ B for every s ∈ S ∪ S -1 . Since π ∈ Q ˜ B , by Claim 2.5 applied to C = F , we have for every s ∈ S ∪ S -1 that

$$\pi ( \mathcal { C } ( K, L ) ) & = \pi ( R _ { B } ^ { - 1 } ( \mathcal { C } _ { B } ( K, L ) ) ) \\ & = R _ { B * } \pi ( \mathcal { C } _ { B } ( K, L ) ) \\ & = R _ { B * } \pi ( \mathcal { C } _ { B } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ) \\ & = \pi ( R _ { B } ^ { - 1 } ( \mathcal { C } _ { B } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ) ) \\ & = \pi ( \mathcal { C } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ). \\ \text{ed.}$$

Hence, by Fact 2.2, (2) is deduced.

/square

Remark 2.13 . The system of finite subsets of F forms a directed system induced by inclusion. The pushforwards along restriction maps R B ⊆ C ∗ thus form an inverse system of maps between the compact sets Prob( B ) for B ⊆ F | , B &lt; | ∞ . In this language, Lemma 2.12 says that

$$\text{Prob} ( \mathfrak { s u b } ( \mathcal { F } ) ) = \varprojlim _ { B } \mathcal { P } _ { B } \quad \text{and} \quad \text{IRS} ( \mathcal { F } ) = \varprojlim _ { B } \mathcal { Q } _ { B }.$$

## 2.3. Computational aspects of pseudo invariant random subgroups.

Claim 2.14. Given A ⊆ B ⊆ F where | B &lt; | ∞ , there is an algorithm deciding whether A is a pseudo subgroup of B .

Proof. Given a finite set of elements A = { w , ..., w 1 k } ⊆ F , and another element w ∈ F , there is an algorithm to decide whether w ∈ 〈 A 〉 . Indeed, one can use the following:

- (1) Construct Core( A ) the core graph of 〈 A 〉 via the method of Stallings' foldings [Sta91,KM02].
- (2) Check whether the path that begins at the basepoint of Core( A ) and traverses w is closed.
- (3) If the path is closed, then w ∈ 〈 A 〉 . Otherwise w / ∈ 〈 A 〉 .

By Claim 2.8, A is not a pseudo subgroup of B if and only if there exists a w ∈ B such that w / A ∈ but w ∈ 〈 A 〉 . Hence, a sufficient and necessary condition for A to be a pseudo subgroup of B is to be accepted by the following algorithm:

- (1) Construct Core( A ).
- (2) For every w ∈ B satisfying w / A ∈ , reject if w is a closed path in Core( A ).

- (3) Accept if A passed (2) for every w ∈ B .

/square

Remark 2.15 . Recall that a free group is LERF (locally extended residually finite), i.e., for every finite set A = { w , ..., w 1 k } and every w ∈ F such that w / ∈ 〈 A 〉 , there exists a finite index subgroup H for which

$$A \subseteq H \text{ and } w \notin H.$$

This was originally proved by M. Hall [Hal49], and can be proven using the method of Stallings' foldings [Sta91,KM02]. It follows that for every A a pseudo subgroup of a finite B , there exists a finite index subgroup H for which R B ( H ) = A .

Lemma 2.16. Let B ⊆ F be a finite set. Then, the set P B of distributions over pseudo subgroups of B and the set Q B of pseudo IRSs over B are computable polytopes in R { 0 1 , } B . Namely, they are defined by (computable) integral linear equations and inequalities.

Proof. Recall that Q B ⊆ P B ⊆ Prob( 0 1 { , } B ) ⊆ R { 0 1 , } B . Namely, all these distributions are vectors which are indexed by subsets of B . We describe the defining system of equations and inequalities forcing a vector π ∈ R { 0 1 , } B to belong to P B . First, it needs to be a probability measure, hence

$$\forall A \subseteq B \, \colon \, \pi ( A ) \geq 0, \\ \sum _ { A \subseteq B } \pi ( A ) = 1. \\ e \, \text{algorithm in claim } 2 \, 1 4 \, \text{to}$$

Further, for every A ⊆ B , we can run the algorithm in Claim 2.14 to decide whether A is a pseudo subgroup, and if not to add the constraint π A ( ) = 0. This is the defining system of P B . To get the defining system of Q B , we need to add the following: For every K,L ⊆ B , we can check whether for all s ∈ S ∪ S -1 , the sets sKs -1 and sLs -1 are also contained in B , and if so add the constraints

$$\text{are also contained in } B, \text{ and if so add the constraints} \\ \forall s \in S \cup S ^ { - 1 } \, \colon \, \sum _ { \substack { A \in \mathcal { C } _ { B } ( K, L ) \\ \pi ( \mathcal { C } _ { B } ( K, L ) ) } } \pi ( A ) = \sum _ { \substack { A \in \mathcal { C } _ { B } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) \\ \pi ( \mathcal { C } _ { B } ( s K s ^ { - 1 }, s L s ^ { - 1 } ) ) } } \pi ( A ) \,.$$

## 3. Main Theorem I: Approximating the values of subgroup tests

Recall the definitions of challenges, tests and values from Section 1.1. Let T be a test over the generating set S , with challenges ( K D i ; i ) i ∈ Q and rational distribution µ over Q . Let K = ⋃ i ∈ Q K i , which is a finite subset of F ( S ) = F . We can extend the definition of val( T , · ) in the following way: For every B satisfying K ⊆ B ⊆ F , and for every distribution π ∈ Prob( 0 1 { , } B ), let

$$\text{val} ( \mathcal { T }, \pi ) = \underset { A \sim \pi } { \mathbb { E } } \underset { i \sim \mu } { \mathbb { E } } [ D _ { i } ( A \cap K _ { i } ) ].$$

The next claim is formalizing the following intuitive idea: Since D i depends only on the restriction of H to K i , then replacing π by its push-forward along any restriction R B will not change its value against T .

Claim 3.1. Under the extended definition of the value, for every B and C such that K ⊆ B ⊆ C ⊆ F , and for every π ∈ Prob( 0 1 { , } C ) , we have

$$\text{val} ( \mathcal { T }, \pi ) = \text{val} ( \mathcal { T }, R _ { B \subseteq C * } \pi ).$$

Proof. By definition, sampling A ∼ R B ⊆ C ∗ π is the same as sampling A ′ ∼ π and outputting A = A ′ ∩ B . Also, K i = B ∩ K i since K i ⊆ K ⊆ B . Hence,

$$\Lambda \subseteq D. \text{ENE,} \\ \quad \text{val} ( \mathcal { T }, R _ { B \subseteq C * } \pi ) & = \underset { A \sim R _ { B \subseteq C * } \pi } { \mathbb { E } } \underset { i \sim \mu } { \mathbb { E } } \left [ D _ { i } ( A \cap K _ { i } ) \right ] \\ & = \underset { A ^ { \prime } \sim \pi } { \mathbb { E } } \underset { i \sim \mu } { \mathbb { E } } \left [ D _ { i } ( ( A ^ { \prime } \cap B ) \cap K _ { i } ) \right ] \\ & = \underset { A ^ { \prime } \sim \pi } { \mathbb { E } } \underset { i \sim \mu } { \mathbb { E } } \left [ D _ { i } ( A ^ { \prime } \cap K _ { i } ) \right ] \\ & = \text{val} ( \mathcal { T }, \pi ).$$

/square

Recall the first clause of Theorem 1.10: There is a Turing machine M 1 that takes as an input the encoding of a test T , and outputs an infinite sequence of non-decreasing numbers ( α t ) ∞ t =1 ⊆ [0 , 1] such that lim t →∞ α t = val sof ( T ).

Proof of Theorem 1.10 (1) . Let σ : S → Sym( X ) be a finite action. The value of Φ( σ ) against T is

$$\cdot \cdot \cdot \cdot \cdot \\ \quad \text{val} ( \mathcal { T }, \Phi ( \sigma ) ) & = \mathbb { E } _ { H \sim \Phi ( \sigma ) } \underset { i \sim \mu } { \mathbb { E } } _ { i \sim \mu } D _ { i } ( H \cap K _ { i } ) \\ & = \sum _ { x \in X } \sum _ { i \in Q } \frac { \mu ( i ) } { | X | } \cdot D _ { i } ( \text{Stab} ( \sigma, x ) \cap K _ { i } ) \\ \text{hination of evaluations of $D$} \colon \text{ Since the sets $K$} \colon \text{ functions $D$} \text{ and } \colon$$

which is a rational combination of evaluations of D i . Since the sets K i , functions D i and coefficients µ i ( ) can be calculated in finite time from the encoding of T , and Stab( σ, x ) ∩ K i can be calculated from σ for every x ∈ X , the value of Φ( σ ) against T can be computed in finite time.

There is a computable countable enumeration of all (equivalence classes of) finite F ( S )-actions. To see that, note that a map σ : S → Sym( n ) is defined by the tuple ( n ; { σ s ( ) } s ∈ S ). Since the elements of Sym( n ) can be ordered (e.g., lexicographically), as well as the elements of S , the infinite set of tuples ( n ; { σ s ( ) } s ∈ S ) inherits a countable enumeration. Denote by σ t the t th action according to this enumeration. For t ∈ N , let

$$\alpha _ { t } = \max _ { s \leq t } \{ \text{val} ( \mathcal { T }, \Phi ( \sigma _ { s } ) ) \}.$$

By our discussion so far, the number α t can be computed in finite time. Moreover, ( α t ) ∞ t =1 is a non-decreasing sequence by definition. Since Im(Φ) = IRS fd ( F ), the sequence ( α t ) ∞ t =1 tends to the supremum of val( T , · ) over IRS fd ( F ), which is, by (1.4), val sof ( T ). /square

We now recall the second clause of Theorem 1.10: There is a Turing machine M 2 that takes as an input the encoding of a test T , and outputs an infinite sequence of non-increasing numbers ( β t ) ∞ t =1 ⊆ [0 , 1] such that lim t →∞ β t = val erg ( T ).

Proof of Theorem 1.10 (2) . Let K = ⋃ K i as before, and let B ⊆ F be a finite subset containing K . Recall the definition of Q B the pseudo invariant random subgroups over B (Definition 2.10), and its pre-image ˜ Q B . Recall also Claim 3.1 and the discussion before it, where we extended the notion of the value to probability distributions over subsets of F that contain K . The B -approximation to the ergodic value of T is defined to be

$$\text{val} _ { B } ( \mathcal { T } ) = \sup \{ \text{val} ( \mathcal { T }, \pi ) \ | \ \pi \in \mathcal { Q } _ { B } \} = \sup \{ \text{val} ( \mathcal { T }, \pi ) \ | \ \pi \in \tilde { \mathcal { Q } } _ { B } \}.$$

Let { B t } ∞ t =1 be a sequence of finite subsets of F , all containing K , such that B t ⊆ B t +1 and ⋃ ∞ t =1 B t = F . We now claim the following:

- (1) val B t ( T ) is computable.
- (2) The sequence val B t ( T ) is non-increasing.
- (3) lim t →∞ val B t ( T ) = val erg ( T ).

By Lemma 2.16, Q B is defined by a computable integral system of equations and inequalities. Thus, maximizing a linear functional val( T , · ) over it can be done using linear programming in finite time, proving (1).

Moreover, IRS( F ) = ˜ Q F ⊆ Q ˜ B t which implies val B t ( T ) ≥ val erg ( T ). On the other hand, by Claim 2.4 the space Prob( { 0 1 , } F ) is compact, and since ˜ Q B are closed sets they are also compact. Hence there is a distribution π t ∈ Q ˜ B t satisfying val B t ( T ) = val( T , π t ). By the compactness of Prob( { 0 1 , } F ), there is a weak limit to some subsequence of ( π t ) ∞ t =1 , which we denote by π ∞ . Without loss of generality the subsequence is the original sequence. Since π s ∈ Q ˜ B t for every s ≥ t , and since ˜ Q B are closed, we deduce that π ∞ ∈ ⋂ ˜ Q B t = IRS( F ). By the definition of a weak limit, since val( T , · ) is a continuous functional, we have

By Lemma 2.12, whenever B ⊆ C ⊆ F we have R B ⊆ C ∗ ( Q C ) ⊆ Q B . Hence ˜ Q B t +1 ⊆ Q ˜ B t , which implies val B t +1 ( T ) ≤ val B t ( T ), proving (2).

$$\lim _ { t \to \infty } \, \text{val} _ { B _ { t } } ( \mathcal { T } ) = \lim _ { t \to \infty } \, \text{val} ( \mathcal { T }, \pi _ { t } ) = \text{val} ( \mathcal { T }, \lim _ { w ^ { * } } \pi _ { t } ) = \text{val} ( \mathcal { T }, \pi _ { \infty } ) \leq \text{val} _ { \text{erg} } ( \mathcal { T } ),$$

proving (3). Therefore, choosing β t = val B t ( T ) finishes the proof.

/square

## 4. Examples of tests

4.1. Relations verification test. Given a finite subset R ⊆ F ( S ), the R -verification test V R checks whether R is contained in the sampled subgroup H . It contains a single challenge ( R D ; ) with D = 1 R , namely

$$\omega _ { \text{$\varphi$} } \, \iota \, \circ \text{comamon a omp} \, \text{many} \, \iota, \\ \forall A \subseteq R \, \colon \, \ D ( A ) = \begin{cases} 1 & A = R, \\ 0 & A \neq R. \end{cases}$$

/negationslash

The sofic value of V R is always 1, e.g., using the Dirac measure concentrated on the group F itself (which associates via Φ with the trivial action of F on a singleton). Moreover, if the conjugation orbit of a finite index subgroup H passes V R with probability 1, then R ⊆ ⋂ w ∈F wHw -1 .

Remark 4.1 . Though the value of the R -verification test does not give us much information about R , we will see in Section 5 that the potential robustness of this test is an important property of R . Moreover, this test has variations where you sample r ∈ R according to some distribution and check only that r ∈ H and not that all of R is in H . See for example [CL23,CVY23] for more on that.

- 4.2. Separation test. Given two finite subsets R,L ⊆ F ( S ), the ( R,L )-separation test V R L || checks whether R is contained in the sampled subgroup H but L \ R is not. It contains a single challenge ( R ∪ L D ; ) with D = 1 R , namely

/negationslash

$$\forall A \subseteq R \cup L \ \colon \ D ( A ) = \begin{cases} 1 & A = R, \\ 0 & A \neq R. \end{cases}$$

Definition 4.2. A group Γ is residually finite if for every finite subset L ⊆ Γ where Id Γ / L ∈ , there is a finite index normal subgroup N /triangleleftequal Γ such that L ∩ N = . ∅

Claim 4.3. A finitely presented group Γ = 〈 S R | 〉 is residually finite if and only if for every finite L ⊆ F such that L ∩ 〈〈 R 〉〉 = ∅ 14 there is a finitely described IRS passing V R L || with probability 1 .

14 The subgroup 〈〈 R 〉〉 is the smallest normal subgroup containing R .

Proof. Let Γ = F ( S ) / 〈〈 R 〉〉 be residually finite, and L ⊆ F a finite set disjoint from 〈〈 R 〉〉 . By Definition 4.2, there is a finite index normal subgroup N /triangleleftequal Γ such that L 〈〈 R 〉〉 ∩ N = . Using the sequence of epimorphisms ∅

$$\mathcal { F } \twoheadrightarrow \Gamma \twoheadrightarrow \Gamma / N$$

we can define the left action of F on X = Γ /N which passes V R L || with probability 1.

On the other hand, given a finite subset Id Γ / ∈ L ⊆ Γ, let L ′ ⊆ F be any set of representatives for L . Since Id Γ / L ∈ , we have L ′ ∩ 〈〈 R 〉〉 = ∅ . Hence, by our assumption, there is an action ρ : S → Sym( X ) with val( V R L || ′ , Φ( )) = 1. ρ Without loss of generality, ρ is transitive (otherwise, its restriction to any orbit will do). The fact val( V R L || ′ , Φ( )) = 1 implies in particular that ρ R ⊆ Stab( ρ, x ) for any x ∈ X . Thus, ρ factors through Γ and defines an action ρ ′ : Γ → Sym( X ) by ρ ′ ( w 〈〈 R 〉〉 ) = ρ w ( ). By the fact val( V R L || ′ , Φ( )) = 1, the ρ permutation ρ w ( ) has no fixed points for every w ∈ L ′ , and thus ρ ′ ( u ) has no fixed points for every u ∈ L . Hence N = ⋂ x ∈ X Stab( ρ , x ′ ) is a normal subgroup of Γ satisfying N ∩ L = ∅ , as required to deduce Γ is residually finite. /square

Let X be a finite set. Given two permutations σ, τ ∈ Sym( X ), we define their normalized Hamming distance to be

/negationslash

$$d _ { H } ( \sigma, \tau ) \coloneqq \frac { | \{ x \in X \ | \ \sigma ( x ) \neq \tau ( x ) \} | } { | X | } = \mathbb { P } _ { x \in X } [ \sigma ( x ) \neq \tau ( x ) ]. \\ - \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon$$

/negationslash

Definition 4.4. A finitely presented group Γ = 〈 S R | 〉 is sofic if for every L ⊆ F ( S ) such that L ∩ 〈〈 R 〉〉 = ∅ , and for every ε &gt; 0, there is a finite set X and an action ρ : S → Sym( X ) such that

$$\forall r & \in R \, \colon \ \ d _ { H } ( \rho ( r ), \text{Id} _ { X } ) \leq \varepsilon, \\ \forall w & \in L \, \colon \ \ d _ { H } ( \rho ( w ), \text{Id} _ { X } ) \geq 1 - \varepsilon.$$

Remark 4.5 . It is straightforward to see that soficity is a relaxation of residual finiteness.

Proposition 4.6. A finitely presented group Γ = 〈 S R | 〉 is sofic if and only if for every finite L ⊆ F such that L ∩ 〈〈 R 〉〉 = ∅ we have val sof ( V R L || ) = 1 .

Proof. Assume Γ is sofic, and let L ⊆ F be a finite set such that L ∩ 〈〈 R 〉〉 = ∅ . For every ε &gt; 0, there is an action ρ ε : S → Sym( X ε ), such that

$$\forall r & \in R \ \colon \ \ & d _ { H } ( \rho _ { \varepsilon } ( r ), \text{Id} _ { X _ { \varepsilon } } ) \leq \varepsilon, \\ \cup \dots & \varepsilon \ r \ \colon \ \ & \ r \ r \ r \dots \ \mathbf r \ a \ \searrow \ \cdots \ \mathbf r \quad.$$

$$\forall w \in L \ \colon \ d _ { H } ( \rho _ { \varepsilon } ( w ), \text{Id} _ { X _ { \varepsilon } } ) \geq 1 - \varepsilon.$$

Hence,

$$\text{val} ( \mathcal { V } _ { R | | L }, \Phi ( \rho _ { \varepsilon } ) ) & = \mathbb { P } _ { x \in X _ { \varepsilon } } \left [ \forall r \in R, \forall w \in L \, \colon \, \rho _ { \varepsilon } ( r ). x = x, \ \rho _ { \varepsilon } ( w ). x \neq x \right ] \\ & \geq 1 - \sum _ { r \in R } \mathbb { P } _ { x \in X _ { \varepsilon } } \left [ \rho _ { \varepsilon } ( r ). x \neq x \right ] - \sum _ { w \in L } \mathbb { P } _ { x \in X _ { \varepsilon } } \left [ \rho _ { \varepsilon } ( w ). x = x \right ] \\ & \geq 1 - \sum _ { r \in R } d _ { H } ( \rho _ { \varepsilon } ( r ), \text{Id} _ { X _ { \varepsilon } } ) - \sum _ { w \in L } ( 1 - d _ { H } ( \rho _ { \varepsilon } ( w ), \text{Id} _ { X _ { \varepsilon } } ) ) \\ & \geq 1 - | R | \varepsilon - | L | \varepsilon. \\ \stackrel { \sim } { \sim } \quad \text{$\tau$} \quad \varepsilon \quad \text{$\tau$} \quad \text{$\tau$} \quad \text{$\tau$} \quad \text{$\tau$} \quad \text{$\tau$} \quad \text{$\tau$} \quad \text{$\tau$}.$$

/negationslash

$$\geq 1 - | R | \varepsilon - | L | \varepsilon.$$

Since | R | and | L | are fixed, and ε &gt; 0 is arbitrarily small, we have val sof ( V R L || ) = 1.

/negationslash

On the other hand, if for every L we have val sof ( V R L || ) = 1, then for every ε &gt; 0 there is an action ρ : S → Sym( X ) with val( V R L || , Φ( )) ρ ≥ 1 -ε . Now, since

/negationslash

/negationslash

$$\forall r & \in R \, \colon \, \ d _ { H } ( \rho ( r ), \text{Id} _ { X } ) \leq \varepsilon, \\ \forall w & \in L \, \colon \, \ d _ { H } ( \rho ( w ), \text{Id} _ { X } ) \geq 1 - \varepsilon.$$

and Γ is sofic.

/square

4.3. Formula satisfaction test. Let ϕ y , ..., y ( 1 n ) be a boolean formula. The test T ϕ is defined over the formal set of generators S = { x , ..., x 1 n } . It has a single challenge ( K D ; ), where K = S . Note that the characteristic function of every subset A ⊆ S is already in the form 1 A : { x , ..., x 1 n } → { 0 1 , } , and thus induces an assignment for the formal variables. The decision predicate D accepts A ⊆ S if 1 A induces a satisfying assignment for ϕ , i.e.,

$$D ( A ) = \varphi ( \mathbf 1 _ { A } ( x _ { 1 } ), \dots, \mathbf 1 _ { A } ( x _ { n } ) ).$$

It is straightforward that val( T ϕ ) = 1 if and only if ϕ is satisfiable.

There is a more interesting version of this test, when the formula ϕ is a 3CNF. Recall that a 3CNF is an and of clauses of the form ϕ t = y ε 1 i ∨ y ε 2 j ∨ y ε 3 k , where y , y i j , y k are taken from a fixed set of formal generators (as before), ε , ε 1 2 , ε 3 ∈ { 0 1 , } , and we interpret y 0 = y and y 1 = ¬ y . Now, checking that ϕ is satisfied by 1 A is the same as going over all the clauses and checking that they are all satisfied. Thus, we can define a randomized version of this check by associating a challenge ( K D t ; t ) with each clause ϕ t , by letting K t = { x , x i j , x k } and D A t ( ) = ϕ t ( 1 A ( x i ) , 1 A ( x j ) , 1 A ( x k )). Then, by choosing a uniform distribution over challenges, the associated test T ϕ checks whether a uniformly chosen clause is satisfied by 1 A . The famous PCP theorem [ALM + 98] says that any 3CNF ϕ can be (efficiently) transformed into a not much larger 3CNF ϕ ′ , such that if val sof ( T ϕ ) = 1, then val sof ( T ϕ ′ ) = 1, and if val sof ( T ϕ ) = 0, then val sof ( T ϕ ′ ) ≤ 1 2 / . The scaled up version of this argument shows that any NEXP problem (see [BFL91]) can be reduced to approximating the sofic value of a test. 15

## 5. Robustness

In this section we define a rigidity property of tests called robustness (see Definition 5.7). Loosely, a test is robust if every almost optimal strategy against it is close to an optimal one. Though this notion is natural, one needs to clarify what is the measure of distance between strategies.

15 This last remark is meaningless as long as we do not specify the exact way we encode tests. The point is that there is a natural way to encode tests such that NEXP can be reduced to approximating the sofic value immediately from [BFL91]. In any case, this paper is devoted to proving a much stronger conclusion, which is that approximating the sofic value is as hard as the Halting Problem .

$$\text{val} ( \mathcal { V } _ { R | | L }, \Phi ( \rho ) ) & = \mathbb { P } _ { x \in X } [ \forall r \in R, \forall w \in L \ \colon \ \rho ( r ) x = x, \ \rho ( w ) x \neq x ] \\ & \leq \min ( \min _ { r \in R } ( \mathbb { P } _ { x \in X } [ \rho ( r ) x = x ] ), \ \min _ { w \in L } ( \mathbb { P } _ { x \in X } [ \rho ( w ) x \neq x ] ) ) \\ & = \min ( \min _ { r \in R } ( 1 - d _ { H } ( \rho ( r ), \text{Id} _ { X } ) ), \ \min _ { w \in L } ( d _ { H } ( \rho ( w ), \text{Id} _ { X } ) ) ),$$

we deduce that

5.1. Edit distance. We first define a generalized version of the normalized Hamming distance (4.1). Let X and Y be two finite sets, and assume X ⊆ Y . Given two permutations σ ∈ Sym( X ) and τ ∈ Sym( Y ), we define their normalized Hamming distance with errors to be

$$d _ { H } ( \sigma, \tau ) & = 1 - \frac { | \{ x \in X \ | \ \sigma ( x ) = \tau ( x ) \} | } { | Y | }. \\ \intertext { r e e } \tau \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \ \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \quad \, \cdot \, \, \,$$

If for every y / X ∈ we let σ y ( ) = error / Y, ∈ then we can define equivalently

$$d _ { H } ( \sigma, \tau ) = \mathbb { P } _ { y \in Y } [ \sigma ( y ) \neq \tau ( y ) ],$$

/negationslash which is the way we defined the normalized Hamming distance in (4.1). Since the generalized version is the same as the usual Hamming distance when Y = X , we use the same notation for both and just call them the Hamming distance from now on.

Let s : S → R &gt; 0 be a function, which we call the significance function. Given two actions ρ : S → Sym( X ) and ϕ : S → Sym( Y ), we define their s -weighted distance as follows:

$$\lambda \dots \dots \dots \dots \dots \dots \dots \dots \\ d ^ { s } ( \rho, \varphi ) = \sum _ { s \in S } \mathfrak { s } ( s ) \cdot d _ { H } ( \rho ( s ), \varphi ( s ) ). ^ { 1 6 } \\ \alpha \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \ dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots........................................................................................................................................................................................................$$

For every θ ∈ Sym( Y ), let ϕ θ : S → Sym( Y ) be ϕ θ ( s ) = θϕ s θ ( ) -1 . Now, the s -weighted edit distance 17 of ρ and ϕ is the following minima:

$$d _ { \text{edit} } ^ { s } ( \rho, \varphi ) = \min _ { \theta \in \text{Sym} ( Y ) } ( d ^ { s } ( \rho, \varphi ^ { \theta } ) ).$$

Note that the edit distance is independent of the specific embedding of X in Y . The edit distance induces a metric on IRS fd ( F ). For every π, π ′ ∈ IRS fd ( F ), let

$$d _ { \text{edit} } ^ { s } ( \pi, \pi ^ { \prime } ) = \inf \{ d _ { \text{edit} } ^ { s } ( \rho, \varphi ) \ | \ \rho \in \Phi ^ { - 1 } ( \pi ), \varphi \in \Phi ^ { - 1 } ( \pi ^ { \prime } ) \}$$

where recall the definition of Φ in (1.3).

5.1.1. A graph theoretic perspective.

Definition 5.1. Let Γ be a group with S a finite generating set. Let X be a set and σ : Γ → Sym( X ) an action of Γ on X . The generalized Schreier graph Sch( σ, S ) is a directed graph with vertex set X and edges labeled by S . The edges of Sch( σ, S ) are defined as follows: For every x ∈ X and s ∈ S , there is a directed edge from σ s .x ( ) to x labeled by s , namely

σ s .x

(

)

s

x.

We may say that an edge is labeled by some inverse of s ∈ S , such as x s -1 - - → y . By that we mean the edge labeled by s and oriented in the other direction, namely y s -→ x . This is natural as σ s ( -1 ) = σ s ( ) -1 . Moreover, when S generates Γ, it includes words with inverses, and so when one associates words in the generators to paths in a labeled graph, this interpretation is natural (cf. [KM02]).

-

→

Remark 5.2 . This generalizes the usual notion of a Schreier coset graph Sch(Γ , H, S ) by choosing σ : Γ → H \ Γ to be the natural action of Γ on right H -cosets.

16 Though the Hamming distance is always bounded by 1, the weighted distance may be larger than 1.

17 There is a more graph theoretical way of viewing the edit distance, in the spirit of the section 5.1.1. It essentially measures how much one Schreier graph needs to be changed to get to the other graph. For more on that, see Section 4 of [CL23] and the Γ-graph notion in [BC22].

The Schreier graph does not provide any new data about σ , but it provides a graph theoretic perspective for approaching IRSs. For example, a fact that we repeatedly use is that orbits of the action are in correspondence with the connected components of the Schreier graph. Moreover, the edit distance is better understood as a distance between graphs: Given two labeled graphs, one wants to transform one to the other. Whenever the endpoint of an edge labeled by s is changed, there is an associated cost s ( s ). The same cost is incurred when deleting completely or adding such an s -labeled edge. The goal is to minimize the cost of moving between the graphs (up to isomorphism). The edit distance is exactly the minimal cost of such a transformation.

5.1.2. Topology induced by the edit distance. It turns out that regardless of the significance function s , the topology induced by the edit distance is strictly stronger than the weak ∗ topology:

Proposition 5.3 (Topology induced by the edit distance) . We have the following:

- (1) Given two sequences π , π n ′ n ∈ IRS fd ( F ) such that π n converges to π ∞ ∈ IRS( F ) in the weak ∗ topology and lim n →∞ d s edit ( π , π n ′ n ) = 0 , then π ′ n converge to the same π ∞ in the weak ∗ topology.
- (2) There are sequences π n ∈ IRS fd ( F ) that converge in the weak ∗ topology but are not Cauchy sequences in the edit distance topology.

Remark 5.4 . The above proposition should be contrasted with the amenable case, studied in [BLT19, Proposition 6.8], where the authors showed that the converse of (1) is true when the free group is replaced by an amenable group. See [BLT19, Remark 6.9] for a different proof of the above clause (2).

Proof of Proposition 5.3. Let min( ) be the minimum value of s s . Since S is finite, min( ) s &gt; 0. So d s edit ≥ min( ) s d edit where d edit is the edit distance with significance function equal to the constant 1. So lim n →∞ d edit ( π , π n ′ n ) = 0. This reduces the problem to the ordinary edit distance.

Let K,L be finite subsets of F . By Remark 2.3, we have

$$\lim _ { n \to \infty } \pi _ { n } ( \mathcal { C } ( K, L ) ) = \pi _ { \infty } ( \mathcal { C } ( K, L ) ).$$

So it suffices to prove

$$\lim _ { n \to \infty } | \pi _ { n } ( \mathcal { C } ( K, L ) ) - \pi _ { n } ^ { \prime } ( \mathcal { C } ( K, L ) ) | = 0. \lim _ { \mu \to \infty } | \pi _ { n } ( \mathcal { C } ( K, L ) ) | = 0. \lim _ { \mu \to \infty } | \pi _ { n } ( \mathcal { C } ( K, L ) ) |$$

Let r &gt; 0 be a large enough radius so that K ∪ L is contained in the ball B r ( ) ⊂ F of radius r with respect to the word metric induced by S .

Because π n and π ′ n are finitely described, there are actions ρ n : S → Sym( X n ) and ρ ′ n : S → Sym( Y n ) which induce π n and π ′ n respectively. We may assume that for each n , either X n ⊂ Y n or Y n ⊂ X n . After conjugating if necessary, we may further assume

$$\text{:under assume} \\ d _ { \text{edit} } ( \rho _ { n }, \rho _ { n } ^ { \prime } ) = d ( \rho _ { n }, \rho _ { n } ^ { \prime } ) = \sum _ { s \in S } d _ { H } ( \rho _ { n } ( s ), \rho _ { n } ^ { \prime } ( s ) ). \\ 1 \text{ let Rad} ( k ) \text{ he the set of all } n \in X + Y \text{ such that there exists}$$

Given an integer k ≥ 1, let Bad( k ) be the set of all v ∈ X n ∪ Y n such that there exists g in the ball B k ( ) ⊂ F with ρ n ( g ) -1 v = ρ ′ n ( g ) -1 v . The definition of edit distance gives

/negationslash

$$| \text{Bad} ( 1 ) | \leq d _ { \text{edit} } ( \rho _ { n }, \rho _ { n } ^ { \prime } ) | X _ { n } \cup Y _ { n } |.$$

/negationslash

Suppose v ∈ Bad( k ) \ Bad( k -1) for some k ≥ 2. Then there is a g ∈ B k ( ) such that ρ n ( g ) -1 v = ρ ′ n ( g ) -1 v . Let g = s 1 · · · s k with s i ∈ S ∪ S -1 . Since v / ∈ Bad( k -1), if h = s 1 · · · s k -1 , then w := ρ n ( h ) -1 v = ρ ′ n ( h ) -1 v and ρ n ( s k ) -1 w = ρ ′ n ( s k ) -1 w . Hence w ∈ Bad(1) and so v ∈ B k ( -1)Bad(1). Therefore,

/negationslash

$$| \text{Bad} ( k ) | \leq | B ( k - 1 ) | | \text{Bad} ( 1 ) | \leq | B ( k - 1 ) | d _ { \text{edit} } ( \rho _ { n }, \rho _ { n } ^ { \prime } ) | X _ { n } \cup Y _ { n } |.$$

Since | B k ( -1) | is independent of n , and d edit ( ρ n , ρ ′ n ) n →∞ -- - → 0, we can deduce that

$$\lim _ { n \to \infty } \frac { | \text{Bad} ( k ) | } { | X _ { n } \cup Y _ { n } | } = 0$$

for all k .

Because K ∪ L ⊂ B r ( ), if v / ∈ Bad( ), then Stab( r ρ n , v ) ∈ C ( K,L ) if and only if Stab( ρ ′ n , v ) ∈ C ( K,L ). Hence

$$| \pi _ { n } ( \mathcal { C } ( K, L ) ) - \pi _ { n } ^ { \prime } ( \mathcal { C } ( K, L ) ) | & \leq \frac { | \text{Bad} ( k ) | } { | X _ { n } \cup Y _ { n } | } \to 0 \\ \intertext { + \text{the new $\tilde{f}$} \, \varphi \, \varphi \, / 1 \, \vee }$$

as n →∞ . This finishes the proof of (1).

To prove item (2), recall that if G = ( V, E ) is a graph then a subset I ⊂ V is independent if no edge in E has both endpoints in I . If G is finite then the independence ratio of G is α G ( ) = | I / V | | | where I is an independent set of maximum cardinality. If ρ : S → Sym( n ) is an action then we let α ρ ( ) = α G ( ) where G is the associated action graph.

For any actions ρ and ρ ′ , we have d edit ( ρ, ρ ′ ) ≥ | α ρ ( ) -α ρ ( ′ ) . | So it suffices to show there exist action sequences { ρ n } n , { ρ ′ n } n whose corresponding IRSs weak ∗ converge to the same IRS and | α ρ ( ) -α ρ ( ′ ) | &gt; c for some constant c &gt; 0.

By using a first moment argument, it can be shown that if ρ n : S → Sym( n ) is chosen uniformly at random and if G n is the associated action graph then with high probability α G ( n ) &lt; 1 2 / -c where c &gt; 0 is a constant depending only on | S | (which we assume is at least 2). Moreover, there are sets Ω n ⊂ Sym( n ) S with | Ω n | / | Sym( n ) S | → 1 as n →∞ such that if ρ n ∈ Ω n for all n and π n are the corresponding IRSs then π n weak ∗ converges to the trivial subgroup { Id } . This can be derived by estimating the expected number of short cycles in the graph G n [Wor99]. A more precise estimate on Ω n is obtained in [ABL22].

Therefore, there exists a sequence { ρ n } of actions such that if π n are the corresponding IRSs then π n weak ∗ converges to the trivial subgroup { Id } and α G ( n ) &lt; / 1 2 -c .

On the other hand, there exist ρ ′ n : S → Sym( n ) whose action graphs are bi-partite such that if π ′ n is the corresponding IRS then π ′ n also weak ∗ converges to the trivial subgroup { Id } . Since the independence ratio in this case is 1/2, it follows that the sequence π , π 1 ′ 1 , π 2 , π ′ 2 , . . . cannot be Cauchy in the edit distance.

/square

5.2. Robustness. Given s ∈ S , we can define a map v s : F → N that given a reduced word w ∈ F counts the number of appearances of s or s -1 in w . Namely, if w = ∏ /lscript j =1 s ε j j , where s j ∈ S and ε j ∈ {± } 1 , is a reduced word, then v s ( w ) = ∑ /lscript j =1 1 s ( s j ).

Let T be a test with its usual associated data S , ( K D i ; i ) i ∈ Q and µ . We define s T : S → R &gt; 0 , the significance function associated with T , as follows:

$$\mathfrak { s } _ { \mathcal { T } } ( s ) = \underset { i \sim \mu } { \mathbb { E } } \left [ \sum _ { w \in K _ { i } } v _ { s } ( w ) \right ].$$

Claim 5.5. Let ε &gt; 0 , and T be a test. Let X and Y be finite sets, and ρ : S → Sym( X ) and ϕ : S → Sym( Y ) be actions. Assume d s T edit ( ρ, ϕ ) ≤ ε . Then | val( T , Φ( )) ρ -val( T , Φ( ϕ )) | ≤ ε .

$$\mathbb { E } _ { \sim \mu } & \left [ \sum _ { w \in K _ { i } } v _ { s } ( w ) \right ]. \\ Y \ b e \ f i n i t e \ s e t s, \, a$$

Proof. Assume without loss of generality that X ⊆ Y and that d s T edit ( ρ, ϕ ) = d s T ( ρ, ϕ ). Let i ∈ Q . For every w = ∏ /lscript j =1 s ε j j ∈ F , we have

$$\mathbb { P } _ { y \in Y } ^ { \left [ 1 _ { \text{Stab} ( \varphi, y ) } ( w ) \neq 1 _ { \text{Stab} ( \varphi, y ) } ( w ) \right ] } \leq \mathbb { P } _ { y \in Y } ^ { \left [ \varphi ( w ). y \neq \varphi ( w ). y \right ] }.$$

/negationslash

$$\mathbb { P } _ { y \in Y } ^ { \left [ \mathbf 1 _ { \text{Stab} ( \rho, y ) } ( w ) \neq \mathbf 1 _ { \text{Stab} ( \varphi, y ) } ( w ) \right ] } \leq \mathbb { P } _ { y \in Y } ^ { \left [ \mathbf 1 _ { \text{Stab} ( \rho, y ) } ( w ) \right ] }$$

/negationslash

Inequality (5.4) is a consequence of the following implication: If ρ w ( ) acts on y the same way as ϕ w ( ), then in particular w is either in both Stab( ρ, y ) and Stab( ϕ, y ) or in none of them. For 1 ≤ k ≤ /lscript , let w k be the suffix of w from position k , namely w k = ∏ /lscript j = k s ε j j . Moreover, let w /lscript +1 be the empty word Id F . Then

/negationslash

/negationslash

Inequality (5.5) is a consequence of the following implication: If the endpoint of the path beginning at y and labeled by w -1 in Sch( ρ, S ) is different than the endpoint of the same path in Sch( ϕ, S ), then the two paths diverged at some point. Now,

$$& \text{or} \, \text{from position} \, \kappa, \text{money} \, w _ { k } = 1 1 _ { j = k } s _ { j } ^ { \cdot } \,. \text{ improveover, let} \, w _ { \ell + 1 } \, \text{be the empty word} \, \text{in} \, \text{$\mathcal{F}$} \,. \text{ in} \\ & ( 5. 5 ) \quad & \mathbb { P } _ { y \in Y } [ \rho ( w ). y \neq \varphi ( w ). y ] \leq \mathbb { P } _ { y \in Y } \left [ \bigvee _ { 1 \leq k \leq \ell } \rho ( w _ { k } ). y \neq \varphi ( w _ { k } ). y \right ]. \\ & \text{Inequality} \, ( 5. 5 ) \text{ is a consequence of the following implication: } \text{If the endpoint of the path begin} \text{n}$$

/negationslash

/negationslash

Inequality (5.6) is a consequence of the union bound and the logic tautology ∨ m j =1 ϕ j = ∨ m j =1 ( ϕ j ∧ ¬ ϕ j -1 ), where ϕ 0 = False. But, since

$$& \text{derived at some point. Now}, \\ & ( 5. 6 ) & \mathbb { P } _ { y \in Y } \left [ \bigvee _ { 1 \leq k \leq \ell } \rho ( w _ { k } ). y \neq \varphi ( w _ { k } ). y \right ] \leq \sum _ { k = 1 } ^ { \ell } \mathbb { P } _ { y \in Y } [ \rho ( w _ { k } ). y \neq \varphi ( w _ { k } ). y \wedge \rho ( w _ { k + 1 } ). y = \varphi ( w _ { k + 1 } ). y ]. \\ & \text{Imequality $(5.6)$ is a consequence of the union bound and the logic tautology $\bigvee_{j=1}^{m} \varphi_{j} = \bigvee_{j=1}^{m}(\varphi_{j} \wedge -\varphi_{j-1}$} ),$$

$$\rho ( w _ { k } ). y \neq \varphi ( w _ { k } ). y \wedge \rho ( w _ { k + 1 } ). y = \varphi ( w _ { k + 1 } ). y \implies \rho ( s _ { k } ^ { \varepsilon _ { k } } ) \circ \rho ( w _ { k + 1 } ). y \neq \varphi ( s _ { k } ^ { \varepsilon _ { k } } ) \circ \rho ( w _ { k + 1 } ). y,$$

/negationslash

/negationslash and since ρ w ( k +1 ) .y is uniformly distributed given that y is uniformly distributed, we can deduce that

/negationslash

$$\mathbb { P } _ { y \in Y } [ \rho ( w _ { k } ). y \neq \varphi ( w _ { k } ). y \wedge \rho ( w _ { k + 1 } ). y = \varphi ( w _ { k + 1 } ). y ] \leq \underbrace { \mathbb { P } _ { y \in Y } [ \rho ( s _ { k } ). y \neq \varphi ( s _ { k } ). y ] } _ { = d _ { H } ( \rho ( s _ { k } ), \varphi ( s _ { k } ) ) } \,.$$

/negationslash

All in all,

$$\ell \right ] \leq \underbrace { \mathbb { P } _ { y \in Y } [ \rho ( s _ { k } ). y \neq \varphi ( s _ { k } ). y ] } _ { = d _ { H } ( \rho ( s _ { k } ), \varphi ( s _ { k } ) ) }.$$

/negationslash

$$& \mathbb { P } \left [ \mathbf 1 _ { \text{Stab} ( \rho, y ) } ( w ) \neq \mathbf 1 _ { \text{Stab} ( \varphi, y ) } ( w ) \right ] \leq \sum _ { j = 1 } ^ { \ell } d _ { H } ( \rho ( s _ { j } ), \varphi ( s _ { j } ) ) = \sum _ { s \in S } v _ { s } ( w ) d _ { H } ( \rho ( s ), \varphi ( s ) ) \\ & \text{Home to how the union bound and inequality } ( 5 8 ) \text{ } \text{ was have}$$

Hence, by the union bound and inequality (5.8), we have

/negationslash

$$& \cdot & j = 1 & s \in S \\ \text{Hence, by the union bound and inequality (5.8), we have} \\ & \mathbb { P } _ { i \sim \mu } \mathbb { P } _ { y \in \mathcal { Y } } [ \text{Stab} ( \rho, y ) \cap K _ { i } \neq \text{Stab} ( \varphi, y ) \cap K _ { i } ] & \leq \mathbb { E } _ { i \sim \mu } \left [ \sum _ { w \in K _ { i } } \sum _ { s \in S } v _ { s } ( w ) d _ { H } ( \rho ( s ), \varphi ( s ) ) \right ] \\ & \quad = \sum _ { s \in S } \underbrace { \mathbb { E } _ { i \sim \mu } \left [ \sum _ { w \in K _ { i } } v _ { s } ( w ) \right ] } _ { ( 5. 3 ) } d _ { H } ( \rho ( s ), \varphi ( s ) ) \\ & \quad = \sum _ { s \in S } s _ { \mathcal { T } } ( s ) d _ { H } ( \rho ( s ), \varphi ( s ) ) \\ & \quad = d ^ { s \mathcal { T } } ( \rho, \varphi ) \leq \varepsilon. \\ \text{Lastly, by combining} \\ & \quad | \text{val} / \mathcal { T } _ { \ \lambda } \wedge \text{val} / \mathcal { T } _ { \ \lambda } | < \mathbb { P } _ { \ \Phi } | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal{ T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _{ \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal{ D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathfrak { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D }_ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathfrak { T } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathfra } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \matrix } | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathchrak { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D  _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \mathcal { D } _ { \mathcal { T } } | | \extract \quad \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \end{$$

Lastly, by combining

/negationslash

$$| \text{val} ( \mathcal { T }, \rho ) - \text{val} ( \mathcal { T }, \varphi ) | & \leq \underset { i \sim \mu } { \mathbb { P } } \underset { y \in \mathcal { Y } } { \mathbb { P } } [ D _ { i } ( \text{Stab} ( \rho, y ) \cap K _ { i } ) \neq D _ { i } ( \text{Stab} ( \varphi, y ) \cap K _ { i } ) ] \\ & \leq \underset { i \sim \mu } { \mathbb { P } } \underset { y \in \mathcal { Y } } { \mathbb { P } } [ \text{Stab} ( \rho, y ) \cap K _ { i } \neq \text{Stab} ( \varphi, y ) \cap K _ { i } ]$$

/negationslash with (5.9), we deduce the claim.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00110v1-figure-5d741684-73a8-43a2-b1f7-d73465e5a223.jpg)

Remark 5.6 . For those familiar with robustness of non-local games, d s T edit plays a somewhat analogous role to the state-dependent distance (cf. Section 4 of [CS17], for example).

Robustness is a reverse implication to the one in Claim 5.5.

Definition 5.7. Let T be a test and δ : R ≥ 0 → R ≥ 0 a function satisfying δ ε ( ) ε → 0 - - -→ 0. We say that T is δ -robust if:

- (1) There exists an optimal strategy , namely π ∈ IRS fd ( F ) such that val( T , π ) = val sof ( T ).
- (2) Almost optimal strategies are close to optimal ones , namely, if π ′ ∈ IRS fd ( F ) satisfies val( T , π ′ ) ≥ val sof ( T ) -ε , then there is an optimal strategy π such that d s T edit ( π, π ′ ) ≤ δ ε ( ).

Definition 5.8 (See [CL23]) . Let Γ = 〈 S R | 〉 be a finitely presented group. Then, Γ is said to be δ -homomorphism stable, where δ ε ( ) ε → 0 - - -→ 0, if for every ρ : S → Sym( X ) where E r ∈ R [ d H ( ρ r , ( ) Id X )] ≤ ε there is a Γ-action ϕ : S → Sym( Y ), where X ⊆ Y and such that E s ∈ S [ d H ( ρ s , ϕ s ( ) ( ))] ≤ δ ε . ( )

Remark 5.9 . This notion is more commonly known as flexible pointwise group stability in permutations . See [GR09,AP15,BLT19,BL20,CL23,CVY23] for various results in this theory.

Fact 5.10. The group Γ = 〈 S R | 〉 is δ -homomorphism stable if and only if the R -verification test V R is δ ′ -robust. The exact relation between δ and δ ′ can be calculated explicitly - they are constant multiples of one another, where the constants depend only on S and R .

## 6. Tailored non-local games

We commonly use both { 0 1 , } and F 2 for the set with 2-modular arithmetic.

- 6.1. Non-local games preliminaries. We repeat the definitions which appeared in Section 1.5 of the introduction. Since this paper is not focused on non-local games, we treat them somewhat technically. For formal definitions associated with the complexity class MIP ∗ , we refer to [Wat09,VW + 16]. For the connection between MIP ∗ and nonlocal games, a good starting point is [CHTW04].

Definition 6.1. A (synchronous) non-local game G consists of a finite graph G = ( V, E ), a length function /lscript : V → N , formal sets of generators S x = { X x,i | 1 ≤ i ≤ /lscript ( x ) } for every vertex x ∈ V , a distribution µ over the edges E , and decision functions D xy : { 0 1 , } S xy →{ 0 1 , } for every edge xy ∈ E , where S xy = S x ∪ S y . We denote by S the set ⋃ x ∈ V S x .

/negationslash

It is quite straightforward to move between the definitions. A way one can extract the data of Definition 6.1 from the above is as follows: Let /lscript be the constant function Λ = /ceilingleft log | A |/ceilingright , and fix an embedding of A into { 0 1 , } Λ . The vertices V of the underlying graph G will be X , and the support of µ will be the edge set E ⊆ X × X . The formal generator X x,i corresponds to the i th bit of the answer a when x ∈ X is asked as a question. Then, given that x, y were asked, a pair of answers a, b can be encoded as a map γ : S x ∪ S y →{ 0 1 , } , where

Remark 6.2 . Anyone familiar with the definition of a non-local game will immediately notice that the standard formalism is different than the one we chose here. Usually, a (synchronous) non-local game is defined as a pair of finite sets X,A , commonly referred to as the question and answer sets respectively, together with a distribution µ over pairs of questions X × X and a decision predicate D X : × X × A × A →{ 0 1 , } satisfying D x,x,a,b ( ) = 0 for any x ∈ X and a = b ∈ A .

The notation (6.1) will be used repeatedly in the text. Lastly, D xy ( γ ) = D x,y,a,b ( ), where γ is the aforementioned encoding.

/negationslash

In the other direction, we can define A to be all bit strings shorter than Λ = max x ∈ V /lscript ( x ), X to be the vertex set V , and µ stays the same. Finally, D x,y,a,b ( ) = D xy ( γ ) when a, b are of the correct lengths, i.e. a = ( ) /lscript x , b = ( ), and is 0 when either of them is of the incorrect length. /lscript y Since we consider only synchronous strategies, the condition D x,x,a,b ( ) is never checked in practice for a = b and we can assume it was satisfied beforehand. Because of this correspondence, we may refer to /lscript as the answer length function.

Non-local games are often dramatized as two-prover interactive proofs with one round [BOGKW88]. This perspective may help some readers to absorb the upcoming technicalities better. Two players, that can share some resources beforehand (random bits in the classical case and entangled qubits in the quantum case), are separated spatially - e.g., they are seated in far away rooms. A referee samples a pair of questions and sends one to each player. The players then use their shared resources to come up with answers, and send them back to the referee. The referee then decides, using the decision predicate, whether the players won or lost. The decision predicate as well as the distribution over possible questions are assumed to be known to the players beforehand. We demonstrate this dramatization in Example 6.26.

The following is the quantum mechanics' analogue of a probability distribution. Similar to the way probability distributions (over finite sets) are collections of non-negative real numbers that add up to 1, the quantum analogue would be 'non-negative' matrices that add up to the identity.

Definition 6.3. A positive operator valued measure (POVM) of dimension n with outcomes in a set A is a mapping P : A → M n × n ( C ) such that P a is a positive (semi-definite) matrix for every a ∈ A and ∑ a ∈ A P a = Id n . It is called projective , or a projection valued measure (PVM), if in addition P a is an orthogonal projection for every a ∈ A , namely ( P a ) 2 = P a = ( P a ) ∗ , where ∗ is the conjugate transpose operation. Given that P is a PVM and A = 0 1 { , } Λ , we define for 1 ≤ i ≤ Λ the i th marginal of P to be P i : { 0 1 , } → M n × n ( C ) by

$$P _ { 0 } ^ { i } = \sum _ { \substack { a \colon \Lambda \to \{ 0, 1 \} \\ a _ { i } = 0 } } P _ { a } \quad \text{and} \ \ P _ { 1 } ^ { i } = \sum _ { \substack { a \colon \Lambda \to \{ 0, 1 \} \\ a _ { i } = 1 } } P _ { a }.$$

Thus, P a = ∏ Λ i =1 P i a i . Furthermore, the matrix U i = P i 0 -P i 1 is an order 2 unitary, which we call the i th binary observable. All in all, a PVM can be given either as a map P : { 0 1 , } Λ → M n × n ( N ), or as a map U : [Λ] → U n ( ) such that the images of U are commuting involutions - i.e., they square to the identity.

As its name suggests, every POVM P defines a probability distribution over its answer set A as follows

$$\mathbb { P } [ a \text{ is sampled} ] & = \tau ( P _ { a } ),$$

where τ is the dimension normalized trace on n × n matrices. Such an answer is said to be sampled according to P and we denote it by a ∼ P .

Remark 6.4 . In the case of a PVM with outcome set A = { 0 1 , } Λ , the observables { U i } Λ i =1 generate a unitary representation of F Λ 2 . The P a 's in this case can be read from the unitary representation using the Fourier transform of the representation. Hence, for the case of A = { 0 1 , } Λ , a PVM can be given as a collection of mutually perpendicular ortohgonal projections that sum up to the identity, or as a unitary representation of F Λ 2 , and one can move from one perspective to the other without losing information.

Definition 6.5. A (synchronous quantum) n -dimensional strategy for G is a map ρ : S → U n ( ), where the images are involutions, and ρ S ( x ) commutes for every fixed x ∈ V - by saying that a set of matrices (or later permutations) commutes, we mean that every pair of elements in this set commute. Another way of viewing strategies is by saying that they associate with every vertex x ∈ V an n -dimensional PVM (in observable form). The strategy ρ is said to be commuting along edges if ρ S ( xy ) commutes for every edge xy ∈ E .

Such a strategy defines for every edge xy ∈ E a probability distribution over functions γ : S xy → { 0 1 , } as follows:

$$& \text{follows} \colon \\ & ( 6. 4 ) & \mathbb { P } [ \gamma \colon S _ { x y } \to \{ 0, 1 \} \text{ is sampled} ] = \tau \left ( \prod _ { X \in S _ { x } } P _ { \gamma ( X ) } ^ { X } \prod _ { Y \in S _ { y } } P _ { \gamma ( Y ) } ^ { Y } \right ), \\ & \text{where} \, \tau \text{ is again the dimension normalized trace on } n \times n \text{ matrices, } P _ { n } ^ { X } \colon \mathbb { C } ^ { n } \to \mathbb { C } ^ { n } \text{ is the project}$$

For γ : S xy → { 0 1 , } , let P x γ = ∏ X ∈ S x P X γ ( X ) . Then, the map P xy : { 0 1 , } S xy → M n × n ( C ) defined by P xy γ = P P P x γ y γ x γ is a POVM. Thus, γ ∼ ρ is a special case of sampling according to a POVM (6.3), which in this case is P xy . In the spirit of the notation in (6.1), it may be appropriate to write P x γ = P x a and P y γ = P y b .

where τ is again the dimension normalized trace on n × n matrices, P X 0 : C n → C n is the projection on the (+1)-eigenspace of ρ ( X ), and P X 1 : C n → C n is the projection on its ( -1)-eigenspace. 18 We say that γ was sampled according to ρ if it has this distribution, and we denote it by γ ∼ ρ .

Remark 6.6 . The images of X according to ρ are usually called binary observables , and the value γ ( X ) is usually called the measurement outcome .

Claim 6.7. There is a procedural (i.e., algorithmic) way of sampling γ : S xy → { 0 1 , } according to ρ : Since ρ S ( x ) ⊆ U n ( ) commutes, these matrices have a mutual orthonormal basis of eigenvectors B x . Similarly, ρ S ( y ) have a mutual orthonormal basis of eigenvectors B y . First, sample /vector v ∈ B x uniformly at random. Then, sample /vector u ∈ B y according to the squared length of its projection on v , namely

$$\mathbb { P } [ \vec { u } \in B _ { y } \text{ is sampled } | \, \vec { v } \in B _ { x } \text{ was sampled} ] = | \langle \vec { v } | \vec { u } \rangle | ^ { 2 },$$

where 〈·|·〉 is the standard inner product on C n , i.e., 〈 /vector v /vector | u 〉 = ∑ n i =1 v i · u i . Finally, γ : S xy →{ 0 1 , } is determined as follows - for X ∈ S x , γ ( X ) = { 0 ρ ( X ) /vector v = /vector , v 1 ρ ( X ) /vector v = -/vector , v , and for Y ∈ S y , γ ( Y ) = { 0 ρ ( Y ) /vector u = /vector u, 1 ρ ( Y ) /vector u = -/vector u. . All in all,

$$\mathbb { P } [ ( \vec { v }, \vec { u } ) \text{ is sampled} ] = | \langle \vec { v } | \vec { u } \rangle | ^ { 2 } / _ { n },$$

which is independent of the ordering between x and y . Note also that the probability a specific γ is measured is independent of the chosen bases B x and B y .

Proof. The function γ : S xy → F 2 is sampled in the above procedure if for the resulting pair ( /vector , v /vector u ) we have /vector v ∈ Im ( ∏ X ∈ S x P X γ ( X ) ) and /vector u ∈ Im ( ∏ Y ∈ S y P Y γ ( Y ) ) . Denote by P x γ the product ∏ X ∈ S x P X γ ( X ) , and similarly P y γ . So,

$$\mathbb { P } [ \gamma \text{ is sampled} ] = \sum _ { \substack { \vec { v } \in \text{Im} ( P _ { \gamma } ^ { x } ) \\ \vec { u } \in \text{Im} ( P _ { \gamma } ^ { y } ) } } \frac { | \langle \vec { v } | \vec { u } \rangle | ^ { 2 } } { n }.$$

18 Note that ρ ( X ) = P X 0 -P X 1 , which exactly shows how to move from this observable form of the PVMs induced by ρ back to its projection based form.

By the fact that B x is a mutual orthonormal basis of eigenvectors for ρ S ( X ), every /vector v ∈ B x is either in the image of P x γ or in its kernel. Therefore, the above sum can be written as

$$\sum _ { \substack { \vec { v } \in \text{Im} ( \mathbf P _ { \gamma } ^ { x } ) \\ \vec { u } \in \text{Im} ( \mathbf P _ { \gamma } ^ { y } ) } } \frac { | \langle \vec { v } | \vec { u } \rangle | ^ { 2 } } { n } = \sum _ { \substack { \vec { v } \in B _ { x } \\ \vec { u } \in B _ { y } } } \frac { | \langle \mathbf P _ { \gamma } ^ { x } \vec { v } | \mathbf P _ { \gamma } ^ { y } \vec { u } \rangle | ^ { 2 } } { n } = \sum _ { \substack { \vec { v } \in B _ { x } \\ \vec { u } \in B _ { y } } } \frac { | \langle \mathbf P _ { \gamma } ^ { y } \mathbf P _ { \gamma } ^ { x } \vec { v } | \vec { u } \rangle | ^ { 2 } } { n }.$$

Since B y is an orthonormal basis and P x γ , P y γ are orthogonal projections, for every /vector v ∈ B x we have

$$\sum _ { \vec { u } \in B _ { y } } | \langle P _ { \gamma } ^ { y } \Gamma _ { \gamma } ^ { x } \vec { v } | \vec { u } \rangle | ^ { 2 } = \| P _ { \gamma } ^ { y } \Gamma _ { \gamma } ^ { x } \vec { v } \| ^ { 2 } = \langle P _ { \gamma } ^ { y } \Gamma _ { \gamma } ^ { x } \vec { v } | \Gamma _ { \gamma } ^ { y } \Gamma _ { \gamma } ^ { x } \vec { v } \rangle = \langle P _ { \gamma } ^ { x } \Gamma _ { \gamma } ^ { y } \Gamma _ { \gamma } ^ { x } \vec { v } | \vec { v } \rangle.$$

Thus,

$$\sum _ { \substack { \vec { v } \in B _ { x } \\ \vec { u } \in B _ { y } } } \frac { | \langle P _ { \gamma } ^ { y } \mathbf P _ { \gamma } ^ { x } \vec { v } | \vec { u } \rangle | ^ { 2 } } { n } = \sum _ { \vec { v } \in B _ { x } } \frac { \langle \mathbf P _ { \gamma } ^ { x } \mathbf P _ { \gamma } ^ { y } \mathbf P _ { \gamma } ^ { x } \vec { v } | \vec { v } \rangle } { n } = \tau ( \mathbf P _ { \gamma } ^ { x } \mathbf P _ { \gamma } ^ { y } \mathbf P _ { \gamma } ^ { x } ) = \tau ( \mathbf P _ { \gamma } ^ { x } \mathbf P _ { \gamma } ^ { y } ), \\ \dots \quad \dots \quad \dots \quad \dots \quad \dots \quad \dots \quad \dots$$

where the last equality uses the cyclicity of the trace and the fact P x γ is a projection. All in all,

$$\mathbb { P } [ \gamma \text{ is sampled} ] = \tau ( \mathsf P _ { \gamma } ^ { x } \mathsf P _ { \gamma } ^ { y } ),$$

as needed.

$$d ] = \tau ( P _ { \gamma } ^ { x } P _ { \gamma } ^ { y } ),$$

Remark 6.8 . The formula (6.4) for the probability a specific γ is sampled is motivated by the Born measurement rule from quantum mechanics. In quantum mechanics, a (projective) measurement is specified by choosing a PVM P : A → B ( H ) acting on a separable Hilbert space H (Definition 6.3 provided the finite dimensional case). Given a quantum state (unit vector) ψ ∈ H , a measurement of ψ returns the outcome a with probability

$$\mathbb { P } [ a \, \text{is the measurement outcome} ] = \psi ^ { * } \mathbb { P } _ { a } \psi.$$

If there are two systems (e.g. two 'players'), then a Hilbert space H A , H B is associated to each of them respectively, such that the joint Hilbert space is H = H A ⊗ H B . The joint distribution on outcomes is then given by probabilities

$$\mathbb { P } [ ( a, b ) \text{ are the measurement outcomes} ] = \psi ^ { * } ( P _ { a } ^ { x } \otimes ( P _ { b } ^ { y } ) ^ { \dagger } ) \psi,$$

where † is transposition with no complex conjugation, as opposed to ∗ . 19 The case where H A and H B have the same (finite) dimension n , and ψ = n -1 2 / ∑ i e x,i ⊗ e y,i for orthonormal bases { e x,i } and { e y,i } of H A and H B respectively, termed 'maximally entangled,' yields

$$\mathbb { P } [ ( a, b ) \text{ are the measurement outcomes} ] = \tau ( P _ { a } ^ { x } P _ { b } ^ { y } ).$$

Definition 6.9. The value of the strategy ρ against the non-local game G is

$$\text{val} ( \mathcal { G }, \rho ) = \mathbb { E } _ { x y \sim \mu } \mathbb { E } _ { \gamma \sim \rho } [ D _ { x y } ( \gamma ) ]$$

The (synchronous) quantum value of G , val ∗ ( G ), is the supremum over all possible strategies against G .

$$\text{val} ( \mathcal { Y }, \rho ) & = \mathbb { E } _ { x y \sim \mu } \mathbb { E } _ { \gamma \sim \rho } [ \mathcal { U } _ { x y } ( \gamma ) ] \\ & = \sum _ { x y \in E } \sum _ { \gamma \colon S _ { x y } \to \mathbb { F } _ { 2 } } \mu ( x y ) D _ { x y } ( \gamma ) \tau \left ( \prod _ { X \in S _ { x } } P _ { \gamma ( X ) } ^ { X } \prod _ { Y \in S _ { y } } P _ { \gamma ( Y ) } ^ { Y } \right ). \\ \text{antum value of $\mathcal{G}$, val} ^ { * } ( \mathcal { G } ), \, \text{is the supremum over all possible strategies again}$$

19 It is common to drop the transposition † on the H B POVM in (6.5). But, in this case, a transposition will appear in the calculation using traces (6.6). So, we decided on this equivalent formulation.

The main result in [JNV + 21] is a reduction from the Halting Problem to approximating the quantum value of a game:

Theorem 6.10 ( MIP ∗ = RE ) . There exists a polynomial time algorithm that takes as input (the encoding of) a Turing machine M and outputs (the encoding of) a non-local game G M such that:

- (1) Sampling xy ∈ E according to µ and evaluating D xy ( ) · from the encoding of the game G M can be done in time poly( | M | ) , where | M | is the bit-length of the encoding of M .
- (2) If M halts, then there exists a quantum strategy ρ that commutes along edges, for which val( G M , ρ ) = 1 . In particular, val ∗ ( G M ) = 1 .
- (3) If M never halts, then val ∗ ( G M ) ≤ 1 2 / .

The goal of the next section is to show that a somewhat stronger variation of Theorem 6.10, which is proved in [BCV24], provides a negative solution to the Aldous-Lyons Conjecture 1.6.

6.2. Permutation strategies. Our goal in Section 7 is to relate values of subgroup tests to values of nonlocal games and vice versa. The strategies for subgroup tests are finitely described IRSs, which are (induced by) maps of the form σ : S → Sym( n ), while quantum strategies for non-local games are maps of the form ρ : S → U n ( ) adhering to certain conditions. These already seem quite related, as embedding Sym( n ) into U n ( ) as permutation matrices is natural, and indeed transforms every (nice enough) finitely described IRS into a quantum strategy. But, there is a problem with doing this naively: Say that we want to construct a quantum strategy, such that for a certain X ∈ S , regardless of anything else, γ ( X ) will always be 1. Then, we can achieve it by choosing ρ ( X ) = -Id. But, -Id is not a permutation matrix. Therefore, any σ that will be naively transformed into a quantum strategy by embedding Sym( n ) into U n ( ) as permutation matrices cannot ensure a specific X is always evaluated to 1. To amend that, we use a tool developed in the study of solution groups of linear constraint system games (cf. [Slo19]): We add a special generator J that plays the role of -Id. Since -Id is a central involution without fixed points, the image of J under σ needs to behave the same. This forces σ to act on an even sized set. Now, if we want σ ( X ) = σ ( J ) to translate into γ ( X ) being always 1, we will need to restrict ourselves to the ( -1)-eigenspace of σ ( J ). This leads us to the following two definitions.

Definition 6.11. A permutation strategy for a non-local game G is a map σ : S ∪ { } → J Sym(2 n ) with the following properties:

- (1) The image of J is a central involution with no fixed points . Namely,

$$& \sigma ( J ) ^ { 2 } = \text{Id}, \ d _ { H } ( \sigma ( J ), \text{Id} ) = 1, \\ & \forall X \in S \ \colon \ \sigma ( J ) \sigma ( X ) = \sigma ( X ) \sigma ( J ).$$

- (2) The rest of the images are involutions as well . Namely,

$$\forall X \in S \ \colon \ \sigma ( X ) ^ { 2 } = \text{Id}.$$

- (3) The image of S x commutes . Namely, for every fixed vertex x ∈ V ,

$$\forall X, X ^ { \prime } \in S _ { x } \ \colon \ \sigma ( X ) \sigma ( X ^ { \prime } ) = \sigma ( X ^ { \prime } ) \sigma ( X ).$$

Remark 6.12 . Let σ : S ∪ { } J → Sym(2 n ) be a permutation strategy for G . Embed Sym(2 n ) in U (2 n ) as permutation matrices. Note that in this viewpoint, U (2 n ) is acting naturally on functions f : [2 n ] → C , and the matrices are represented with respect to the standard basis, which consists of the indicators

$$\text{respect to the standalone basis, with this this} \\ \forall \ast \in [ 2 n ] \, \colon \, \ 1 _ { \ast } ( \diamond ) = \begin{cases} 1 & \diamond = \ast, \\ 0 & \diamond \neq \ast. \end{cases} \\ \text{$\mathfrak { m } / \mathfrak { m } \mathfrak { m }$ and function $f$.} \, [ \mathfrak { m } ] \, \cdots \, \mathcal { C } ^ { \prime } \, \text{ was above} \end{cases}$$

/negationslash

Moreover, for a permutation ζ ∈ Sym(2 n ) and function f : [2 n ] → C , we have

$$\forall * \in [ 2 n ] \ \colon \ ( \zeta. f ) ( * ) = f ( \zeta ^ { - 1 }. * ).$$

By (1) of Definition 6.11, σ ( J ) is a fixed point free involution, and thus its (+1)-eigenspace W + and ( -1)eigenspace W -are of the same dimension n . Note that W + consists of all functions f : [2 n ] → C that are constant along J -labeled edges in the Schreier graph 20 Sch( σ, S ∪ { J } ), while W -consists of all functions that flip their signs along J -labeled edges. Let Q = Q J 1 : C 2 n → W -be the orthogonal projection on W -. Note that Q Q ∗ = P J 1 and QQ ∗ = Id W -.

We can choose bases for W + and W -as follows. If we denote

$$\ast ^ { \prime } = \sigma ( J ). \ast$$

for every /star ∈ [2 n ], then /star J ← → /star ′ is the perfect matching induced by J -labeled edges in Sch( σ, S ∪ { } J ). So, an orthogonal basis of W + may be taken to be B + = { 1 /star + 1 /star ′ } /star ∈ [2 n ] , while for W -one takes B -= { 1 /star -1 /star ′ } /star ∈ [2 n ] -B -contains for each vector also its opposite, so this is a basis when choosing a representative for each such pair. The union of these bases is an orthogonal basis for C 2 n . Furthermore, we later refer to B -as the standard basis of W -∼ = C n .

Remark 6.13 . Given that ρ : S ∪ { } → J Sym(2 n ) is a permutation strategy, there are n orbits of σ ( J ), and σ acts on them in a well-defined manner. If we arbitrarily denote each orbit as { + /star, - } /star , instead of { /star, /star ′ } a la (6.8), then σ acts naturally on the set Ω ± = {±} × Ω in a way that commutes with the sign flip. Hence, a permutation strategy can be defined as a map into signed permutations, where J is mapped to the sign flip, and such that the variables at each vertex are mapped to commuting involutions. This point of view may be helpful for understanding some of the next claims and remarks. We decided not to use the language of signed permutations in this paper, though in the companion paper [BCV24] it is more pronounced.

Definition 6.14. Let σ : S ∪ { J } → Sym(2 n ) be a permutation strategy for G . Recall from Remark 6.12 that W -is the ( -1)-eigenspace of σ ( J ), and that Q : C 2 n → W -is the orthogonal projection on W -. Then, the quantum strategy ρ : S → End( W -) induced by σ is the mapping to the W --corners

$$\rho ( X ) = Q \sigma ( X ) Q ^ { * }.$$

Claim 6.15. Let σ be a permutation strategy. Then, the quantum strategy ρ induced by σ , as in Definition 6.14, is indeed a quantum strategy for G , as in Definition 6.5.

Proof. The criterion for being a quantum strategy as in Definition 6.5 is to be a map into unitaries such that the image of the generators S x associated with any specific vertex commute , and all the images are involutions . First,

$$\rho ( X ) ^ { * } = ( Q \sigma ( X ) Q ^ { * } ) ^ { * } = Q \sigma ( X ) ^ { * } Q ^ { * } = Q \sigma ( X ) ^ { - 1 } Q ^ { * }.$$

20 Generalized Schreier graphs were defined in Section 5.1.1.

Now, the fact that σ ( J ) commutes with σ ( X ) for any X ∈ S implies that Q Q ∗ σ ( X ) = σ ( X Q Q ) ∗ . Therefore,

$$\dots \dots \dots \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \\ \rho ( X ) ^ { * } \rho ( X ) & = Q \sigma ( X ) ^ { - 1 } Q ^ { * } Q \sigma ( X ) Q ^ { * } \\ & = Q \underbrace { \sigma ( X ) ^ { - 1 } \sigma ( X ) } _ { \text{Id} _ { 2 n } } Q ^ { * } \underbrace { \underbrace { \Omega Q ^ { * } } _ { \text{Id} _ { W ^ { - } } } } _ { \text{Id} _ { W ^ { - } } } \\ & = Q Q ^ { * } = \text{Id} _ { W ^ { - } }, \\ \dots \ r r / \pi \pi - \underbrace { \pi } _ { \text{Id} _ { 2 n } } \dots / \varpi \cdot \cdot \cdot \cdot \varpi \cdot \cdot \varpi \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \, \text{$\frac{1}{1}$} - \frac{1}{1}$} \frac { 1}{1}$} \frac { 1}{1}$} \frac { 1}{1}$}$$

and the image of ρ is contained in U W ( -). Item (2) of Definition 6.11 states that σ ( X ) -1 = σ ( X ) for all X ∈ S , and combined with (6.9) gives

$$\rho ( X ) ^ { * } = Q \sigma ( X ) ^ { - 1 } Q ^ { * } = Q \sigma ( X ) Q ^ { * } = \rho ( X ),$$

i.e., the images of ρ are involutions. Finally, since σ S ( x ) commutes for every fixed x ∈ V , we have

$$\text{novations, run any, since } \sigma ( \vartheta _ { x } ) & \text{commutes for every issue } x \in \\ \forall X, Y \in S _ { x } \, \colon \, \ \rho ( X ) \rho ( Y ) & = Q \sigma ( X ) Q ^ { * } Q \sigma ( Y ) Q ^ { * } \\ & = Q Q ^ { * } Q \sigma ( X ) \sigma ( Y ) Q ^ { * } \\ & = Q Q ^ { * } Q \sigma ( Y ) \sigma ( X ) Q ^ { * } \\ & = Q \sigma ( Y ) Q ^ { * } Q \sigma ( X ) Q ^ { * } \\ & = \rho ( Y ) \rho ( X ),$$

which finishes the proof.

/square

Example 6.16 (Classical permutation strategies) . Let Sym(2) = { Id , ζ } be the group of permutations acting on two elements. For every fixed f : S →{ 0 1 , } , we can define an action σ : S ∪{ } → J Sym(2) as follows

$$\dots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ \sigma ( \mathbf J ) = \zeta \quad ; \quad \sigma ( X ) = \begin{cases} \text{Id} \quad f ( X ) = 0, \\ \zeta \quad \ f ( X ) = 1. \end{cases}$$

It is straightforward to see that the quantum strategy associated with σ satisfies ρ ( X ) = ( -1) f ( X ) , and thus γ : S xy → { 0 1 , } that is sampled according to ρ is deterministically f | S xy . Strategies of this form are usually called deterministic . By taking direct sums of such actions (for potentially different f 's), we can get any (rational) distribution over deterministic strategies. These strategies are usually called classical . So, every (rational) classical strategy can be obtained as a permutation strategy.

Claim 6.17. Let σ : S ∪ { } → J Sym(2 n ) be a permutation strategy, and ρ the associated quantum strategy. Then, if for a word w ∈ F ( S ∪ { J } ) we have ρ w ( ) = Id , then σ w ( ) = Id .

Proof. Recall from Remark 6.12 that the images of ρ act naturally, and in the same way as σ , on W -, the ( -1)-eigenspace of σ ( J ), which consist of functions f : [2 n ] → C that flip along J -edges. Recall also the notation /star ′ = σ ( J ) ./star from (6.8). So, the fact that ρ w ( ) = Id means that for any function f ∈ W -, σ w .f ( ) = f as well. This is true in particular for B -= { 1 /star -1 /star ′ } /star ∈ [2 n ] , the basis of W -described in the same remark. Note that for every ζ ∈ Sym(2 n ) we have ζ. 1 /star = 1 ζ./star . Hence, for every /star ∈ [2 n ], we have

$$1 _ { * } - 1 _ { * ^ { \prime } } = \sigma ( w ). ( 1 _ { * } - 1 _ { * ^ { \prime } } ) = 1 _ { \sigma ( w ). * } - 1 _ { \sigma ( w ). * ^ { \prime } }.$$

By evaluating the functions on both sides of the above equation on the point /star ∈ [2 n ], we get

$$1 = 1 _ { \sigma ( w ). * } ( * ) - 1 _ { \sigma ( w ). * ^ { \prime } } ( * ),$$

which means σ w ./star ( ) = . Since /star /star was any point in [2 n ], σ w ( ) = Id and we are done.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00110v1-figure-5d741684-73a8-43a2-b1f7-d73465e5a223.jpg)

Definition 6.18. A non-local game G is said to have a perfect permutation strategy if there exists a permutation strategy σ such that the quantum strategy ρ induced by it, as in Definition 6.14, satisfies val( G , ρ ) = 1.

In the rest of this subsection we further analyze permutation strategies, and specifically discuss a procedural sampling - similar to Claim 6.7 - of a γ : S xy → { 0 1 , } according to ρ which is induced by a permutation strategy σ .

## 6.3. Interlude - Fourier bases of F m 2 actions.

Definition 6.19. Let σ : F k 2 → Sym( F k 2 ) be the standard action of F k 2 on itself, namely σ w .v ( ) = v + w for every v, w ∈ F k 2 . The Fourier basis of σ is the following collection of functions, denoted by ̂ F k 2 : For every u ∈ F k 2 , let u : F k 2 → C be where 〈 u, w 〉 = ∑ k i =1 u w i i is the standard bilinear form on F k 2 . 21

$$& v, w \in \mathbb { F } _ { 2 } ^ { r }. \,'I \text{the Fourier basis of $\sigma$ is the following collection of functions, denoted $t$} \\ & \widehat { u } \colon \mathbb { F } _ { 2 } ^ { k } \to \mathbb { C } \text{ be} \\ & ( 6. 1 0 ) & & \forall w \in \mathbb { F } _ { 2 } ^ { k } \, \colon \, \widehat { u } ( w ) = \frac { ( - 1 ) ^ { \langle u, w \rangle } } { \sqrt { 2 ^ { k } } }, \\ & \text{where $\langle u, w \rangle = \sum _ { i = 1 } ^ { k } u _ { i } w _ { i } \text{ is the standard bilinear form on $\mathbb{ F } _ { 2 } ^ { k }. } ^ { 2 1 }$$

Claim 6.20. The collection ̂ F k 2 is an orthonormal basis of eigenvectors for the action σ .

Proof. The action σ acts as permutations on the standard basis of C F k 2 , and thus extends to act on the whole vector space of functions from F k 2 to C . Using the standard inner product 〈·|·〉 on C F k 2 as before, we can check that

Furthermore,

$$\forall u \in \mathbb { F } _ { 2 } ^ { k } \, \colon \, \langle \widehat { u } | \widehat { u } \rangle = \sum _ { w \in \mathbb { F } _ { 2 } ^ { k } } \overline { \widehat { u } ( w ) } \cdot \widehat { u } ( w ) = \sum _ { w \in \mathbb { F } _ { 2 } ^ { k } } \frac { 1 } { 2 ^ { k } } = 1.$$

/negationslash

$$\forall u \neq v \in \mathbb { F } _ { 2 } ^ { k } \, \colon \, \langle \widehat { v } | \widehat { u } \rangle & = \sum _ { w \in \mathbb { F } _ { 2 } ^ { k } } \overline { \widehat { v } ( w ) } \cdot \widehat { u } ( w ) \\ & = \frac { 1 } { 2 ^ { k } } \sum _ { w \in \mathbb { F } _ { 2 } ^ { k } } ( - 1 ) ^ { \langle v + u, w \rangle } \\ & = 0,$$

where the last equality is derived from the fact v + u = 0. Lastly, /vector

/negationslash

$$\text{ty is derived from the fact $v+u\neq 0$.  Lastly,} \\ \forall u, v, w \in \mathbb { F } _ { 2 } ^ { k } \, \colon \, \left ( \sigma ( w ). \widehat { v } \right ) ( u ) & = \widehat { v } ( u + w ) \\ & = \frac { ( - 1 ) ^ { ( u + w, v ) } } { \sqrt { 2 ^ { k } } } \\ & = ( - 1 ) ^ { ( w, v ) } \cdot \frac { ( - 1 ) ^ { ( u, v ) } } { \sqrt { 2 ^ { k } } } \\ & = ( - 1 ) ^ { ( w, v ) } \widehat { v } ( u ), \\ \text{llection of mutual eigenvectors for $\sigma$}. \\ \text{for the bilinear form over a finite vector since and $(i.l.)} \, \text{for the monlev inner n}.$$

21 We try to keep 〈· , ·〉 for the bilinear form over a finite vector space, and 〈·|·〉 for the complex inner product.

and ̂ F k 2 is indeed a collection of mutual eigenvectors for σ .

/square

Recall basic group actions definitions. Let G be a group, and σ : G → Sym( X ,τ ) : G → Sym( Y ) be two homomorphisms, which induce actions of G on X and Y respectively. A map f : X → Y is a factor (of G -actions) - also known as a morphism of G actions or a ( σ, τ )-equivariance - if for all w ∈ G and x ∈ X , we have f ( σ w .x ( ) ) = τ ( w .f ) ( x . ) Note that for every set S ⊆ G , such a map induces a morphism of oriented edgelabeled graphs between Sch( σ, S ) and Sch( τ, S ). The actions σ and τ are said to be equivalent if there exists a bijective factor between them, which in the graph case would be a (edge-labeled oriented) graph isomorphism between Sch( σ, S ) and Sch( τ, S ). Given two actions, we can define their sum σ ⊕ τ : G → Sym( X /unionsq Y ), where /unionsq is the disjoint union, to be

$$\forall w \in G, z \in X \sqcup Y \, \colon ( \sigma \oplus \tau ( w ) ). z = \begin{cases} \sigma ( w ). z & z \in X, \\ \tau ( w ). z & z \in Y. \end{cases} \\.. \quad \cdot \quad \cdot \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \end{cases}$$

If σ is a transitive action and x ∈ X , then it is equivalent to the action of G on G / Stab( σ,x ) , where Stab( σ, x ) is defined (as in Section 1.3) to be Stab( σ, x ) = { w ∈ G | σ w .x ( ) = x . } The bijective factor in this case is associating with σ w .x ( ) the coset w · Stab( σ, x ), and recalling that by transitivity every y ∈ X is of the form σ w .x ( ) for some w ∈ G . So, every action σ : G → Sym( X ) is equivalent to the sum of actions of G on quotients of it G H / , for some collection of subgroups H ≤ G .

∀ v ∈ F k 2 : σ g .v ( ) ̂ = ( -1) 〈 v,g ˜ 〉 ̂ v. In particular, for s ∈ S ⊆ F m 2 , the action of s on ̂ v can be read from what happens along edges labeled by s in Sch( σ, S ) - if ̂ v /star ( ) = ̂ v σ s ./star ( ( ) ), then ̂ v is in the (+1)-eigenspace of σ s ( ), and otherwise it is in its ( -1)-eigenspace.

Assume now that G is F m 2 for some positive integer m . Let σ : G → Sym( X ) be a transitive action. Since every subgroup H of G is normal, this action factors through some F k 2 for k ≤ m . Namely, we can find a bijective factor between X and the action of F k 2 on itself: Fix some /star ∈ X ; Stab( σ, /star ) is a subspace of F m 2 , and we implicitly assumed it is isomorphic to F m k -2 ; for every /diamondmath ∈ X , there is an element g of F m 2 for which σ g ./star ( ) = /diamondmath , and thus σ g ( ′ ) ./star = /diamondmath for every g ′ ∈ g + Stab( σ, /star ); so we can associate g + Stab( σ, /star ) with /diamondmath and F m 2 / Stab( σ,/star ) with F k 2 . For every g ∈ F m 2 , let ˜ g ∈ F k 2 be its image in the bijection between the quotient space F m 2 / Stab( σ,/star ) and F k 2 . Then,

All in all, given a not necessarily transitive action σ of F m 2 on X , its orbits have Fourier bases as in Definition 6.19 (extended to being zero on all vertices outside of the orbit), and the disjoint union of these will be called the Fourier basis of σ . Note that since the bijections between the orbits and F k 2 can be chosen in many ways, the Fourier basis of σ is determined only up to the sign of each basis vector.

↦

- 6.4. Procedural sampling according to permutation strategies. Let σ : S ∪{ } → J Sym(2 n ) be a permutation strategy for G , and recall Remark 6.12 and the notation therein. By Definition 6.11, σ S ( x ∪{ } J ) consists of commuting involutions. Therefore, the group generated by σ S ( x ∪ { } J ) is a quotient of F S x ∪{ } J 2 - this can be acquired by linearly extending the map 1 X → σ ( X ) for every X ∈ S x ∪ { J } , where 1 X : S x ∪{ } → J F 2 is the indicator of X . This means that

$$\sigma _ { x } & = \sigma | _ { S _ { x } \cup \{ \mathbb { J } \} }$$

induces an action of F S x ∪{ } J 2 on [2 n ]. Choose B x ⊂ C 2 n to be the Fourier basis of σ x , as was defined in the Interlude Section 6.3. Let B -x = B x ∩ W -⊂ B x be the collection of n eigenvectors in B x on which σ ( J ) acts as ( -1), namely all /vector v ∈ B x such that σ ( J ) ./vector v = -/vector v . These are the Fourier basis elements that flip along edges labeled by J in Sch( σ , S x x ∪ { J } ). Then, B -x is an orthonormal basis of eigenvectors for ρ S ( x ).

Claim 6.21. Let σ : S ∪ { } → J Sym(2 n ) be a permutation strategy for G , and ρ : S → U W ( -) the quantum strategy associated to σ . Then, the sampling procedure of γ : S xy → { 0 1 , } according to ρ can be described as follows:

- · Sample /star ∈ [2 n ] uniformly at random. Then, it is part of an orbit O x ⊆ [2 n ] of σ x (defined in (6.11) ) and O y ⊆ [2 n ] of σ y .
- · Choose a pair /vector v ∈ B -x and /vector u ∈ B -y such that /vector v is supported on O x and /vector u is supported on O y , with probability

$$& \frac { 2 \langle \vec { v } | \vec { u } \rangle ^ { 2 } } { | O _ { x } \cap O _ { y } | }. \\ & \dots \dots.$$

- · For X ∈ S x , let γ ( X ) = 0 if ρ ( X ) ./vector v = /vector v and 1 otherwise. Similarly, for Y ∈ S y , let γ ( Y ) = 0 if ρ ( Y ) ./vector u = /vector u and 1 otherwise.

We may use the notation γ ∼ σ instead of γ ∼ ρ to refer to sampling according to a permutation strategy.

Proof. The probability of sampling /star ∈ [2 n ] which is in O x ∩ O y is | O x ∩ O y | 2 n . Thus, the probability of sampling a specific pair /vector v ∈ B ,/vector -x u ∈ B -y whose intersection of supports is O x ∩ O y is

$$\frac { | O _ { x } \cap O _ { y } | } { 2 n } \cdot \frac { 2 \langle \vec { v } | \vec { u } \rangle ^ { 2 } } { | O _ { x } \cap O _ { y } | } = \frac { \langle \vec { v } | \vec { u } \rangle ^ { 2 } } { n }. \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots.$$

This shows that the above sampling procedure provides the same distribution as the one in Claim 6.7.

/square

6.5. Tailored games. As permutation strategies allow us to translate finitely described strategies of subgroup tests to quantum strategies of non-local games, the soon to be defined Z -aligned permutation strategies of tailored non-local games will allow us to move in the other direction. It is harder to motivate our choices beforehand in this case, but we hope that Section 7 clarifies what may seem cryptic in this section. We begin by restricting the family of non-local games that we focus on - for the reader familiar with linear constraint system games, we note that this family is a generalization of them.

Definition 6.22. Colloquially, a tailored non-local game is one where D xy reads part of γ , and decides according to this partial view which parity checks to apply on the whole of γ . 22

Formally, a tailored non-local game G is equipped with an extra structure, described shortly, and its decision functions D xy behave canonically with respect to this extra data. Instead of a single length function /lscript , G has two length functions /lscript R : V → N and /lscript L : V → N , and /lscript = /lscript R + /lscript L . Before, the length function described the size of the formal generating set at each vertex. Now, the formal set of generators S x at x ∈ V will be a disjoint union of the sets S R x and S L x , where S R x = { X x, R ,i | 1 ≤ i ≤ /lscript R ( x ) } and S L x = { X x, L ,i | 1 ≤ i ≤ /lscript L ( x ) } . The elements of S R x are called readable variables at x ∈ V and the elements of S L x the linear or unreadable variables at x . Let R : S →{ 0 1 , } be the readability function , namely, the indicator of whether X ∈ S is readable or not. In addition, G is equipped with a collection of controlled linear constraints functions L xy that take as input a function γ R : S R x ∪ S R y → F 2 , and outputs a collection of subsets of S xy ∪ { J } . Namely,

$$L _ { x y } \colon \mathbb { F } _ { 2 } ^ { S _ { x } ^ { \mathfrak { R } } \cup S _ { y } ^ { \mathfrak { R } } } \rightarrow \mathbb { F } _ { 2 } ^ { \mathbb { F } _ { 2 } ^ { S _ { x y } \cup \{ J \} } }.$$

22 We considered calling such games controlled linear , since it is more informative. But, since conditionally linear is a term used in [JNV + 21,BCV24], and terms containing linear are generally overused, we decided to use a less informative notion.

The image of L xy is interpreted as a collection of linear constraints that will be verified by the decision function. Finally, the decision function D xy ( γ ) behaves as follows: It restricts γ to the readable variables, namely looks at γ R = γ | S R x ∪ S R y : S R x ∪ S R y → F 2 , and calculates L xy ( γ ) = L xy ( γ R ). Then, it extends γ such that γ ( J ) = 1. Finally, for every α ∈ L xy ( γ ), we have α : S xy ∪ { J } → F 2 , and D xy verifies that

$$\begin{array} { c } \Phi _ { \sigma } & \Phi _ { \sigma } & \Phi _ { \sigma } \\ \langle \alpha, \gamma \rangle = \sum _ { X \in S _ { x y } \cup \{ J \} } \alpha ( X ) \cdot \gamma ( X ) = 0. \end{array}$$

Namely, L xy ( γ ) consists of linear constraints that γ needs to satisfy.

Remark 6.23 . Though being tailored seems to be quite a restrictive form for a non-local game, every game can be tailored in a trivial manner. First, all variables are declared readable, namely /lscript R = /lscript and /lscript L = 0. Then, if the decision function D xy decided to accept γ according to the original game, then it lets L xy ( γ ) be empty (and thus all linear conditions will be satisfied regardless of what γ is). And, if D xy decided to reject γ according to the original game, then it chooses L xy ( γ ) to contain the singleton { } J as the single subset appearing in L xy . Note that { } J represents the linear equation 1 · γ ( J ) = 0, which is 1 = 0, and thus cannot be satisfied.

The last remark raises the question: What have we gained by defining tailored non-local games, if any game can be tailored in a straightforward manner?

Definition 6.24. A permutation strategy σ for a tailored non-local game G is said to be Z -aligned if the assignments σ ( X ) for readable variables act on each point in [2 n ] either like the identity or like σ ( J ). This is equivalent to ρ ( X ) being a diagonal matrix when presented according to the standard basis B -of W -. 23

Remark 6.25 . The classical permutation strategies described in Example 6.16 are Z -aligned. But, one can construct permutation strategies that induce a classical strategy in the usual sense (i.e., whose images are all commuting) without being Z -aligned.

It is clearer now why the way one tailors a non-local game matters: The existence of a perfect Z -aligned permutation strategy for the game depends on it. Let us demonstrate this with binary linear constraint system (LCS) games, and specifically with the magic square game. For a full description of the magic square game we refer to [Ara02] or [BCV24, Example 2.19], and for a general introduction to LCS games see [CLS17].

Example 6.26 (Linear constraint system games) . Let A be an m × n matrix with F 2 coefficients, and let /vector b be a column vector in F m 2 . Classically, such a pair defines a system of linear equations A/vector x = /vector b over F 2 . It also defines a certain non-local game G ( A, /vector b ) which is the quantum counterpart of this classical system of equations. Let us provide a dramatization of this game, in the spirit of Remark 6.2. In G ( A, /vector b ), the referee chooses a random linear constraint in A/vector x = /vector b (i.e., a row) and sends it to one of the players, and chooses a random variable that appears in the chosen constraint (i.e., a column whose intersection with the chosen row is non-zero) to the other player. It then expects the row player to respond with an assignment to the variables appearing in this constraint, and from the column player to respond with an assignment to its single variable. The referee declares this to be a winning condition if the row player's assignment satisfied the constraint, and both players agree on the value of the variable given to the column player. The column player is thought to hold a global assignment and answer according to it, while the row player is assumed to have a satisfying assignment to each constraint - intuitively, by checking consistency between the players, the referee verifies that the global assignment of the column player indeed satisfies all the constraints.

23 The standard basis is usually called the Z -basis in quantum information theory, and thus the name Z -aligned strategies.

Let us define this game rigorously. The vertices in the underlying graph of G ( A, /vector b ) will be indexed by the rows and columns of the matrix A , namely { r i | i ∈ [ m ] } and { c j | j ∈ [ n ] } . There is an edge between a row r i and a column c j if and only if A ij = 1. The length of every column vertex is 1, and we denote by X j the variable associated with the j th column c j . The length of each row vertex is the number of 1's in the row, and we associate variables S r i = { R ij ′ | A ij ′ = 1 } to every row r i . The decision function D r c i j gets as input an assignment γ to X j and { R ij ′ | A ij ′ = 1 , and accepts if and only if }

$$( 6. 1 2 ) & & \sum _ { j ^ { \prime } \colon A _ { i j ^ { \prime } } = 1 } \gamma ( R _ { i j ^ { \prime } } ) = b _ { i } \quad \text{and} \quad \gamma ( X _ { j } ) = \gamma ( R _ { i j } ).$$

Though for our discussion the distribution µ over edges in this game is not important, one can consider the following standard sampling scheme: 1) Choose a row uniformly at random. 2) Choose a uniform column out of the support of the chosen row.

Let us describe a non-trivial tailoring of G ( A, /vector b ). First, all variables are unreadable , namely /lscript R = 0 and /lscript L = . Given that the edge /lscript r c i j was sampled, the system L r c i j will consist of two checks, which are derived from (6.12): 24

$$\begin{cases} \cdot \\ \cdot \end{cases}$$

/negationslash

Then, α consistency will force D r c i j to check that γ ( X j ) = γ ( R ij ), and α linear will force it to check that ∑ j ′ : A ij ′ =1 γ ( R ij ′ ) =

$$\alpha _ { \text{consistency} } ( X ) & = \begin{cases} 0 & X \neq X _ { j }, R _ { i j } \\ 1 & \text{otherwise} \end{cases} \\ \alpha _ { \text{linear} } ( X ) & = \begin{cases} 0 & X = X _ { j } \\ 1 & X = R _ { i j ^ { \prime } } \in S _ { r _ { i } } \\ b _ { i } & X = J \end{cases} \\. _ { j } \text{ to check that } \gamma ( X _ { j } ) & = \gamma ( R _ { i j } ), \text{ and } \alpha _ { \text{linear} } \text{ will for} \end{cases}$$

b i , and thus it acts the same way as before.

The difference between the above tailored form of G ( A, /vector b ) and the one suggested in Remark 6.23 may seem technical. But, here all the variables are unreadable, and in the version of Remark 6.23 version all variables are readable. If all variables of a tailored game are readable, for it to have a perfect Z -aligned permutation strategy is the same as having a perfect classical strategy - which in turn is the same as for the linear system A/vector x = /vector b to have a solution. But, when all the variables are unreadable, there could be a perfect Z -aligned permutation strategy without A/vector x = /vector b having a solution. For example, the perfect strategy for the Mermin-Peres magic square game (see for example [Ara02]) can be derived from a permutation strategy (see our companion paper [BCV24, Example 2.19]), and since there are no readable variables in this case, it is automatically Z -aligned. Furthermore, the magic square game has no perfect classical strategy. This shows that if we care about perfect Z -aligned permutation strategies, the way we tailor a game matters .

## 7. Main Theorem II: Tests associated with tailored games

The goal of this section is to define a mapping from tailored non-local games to subgroup tests such that:

- (1) Completeness : Perfect Z -aligned permutation strategies that commute along edges for the tailored game are translated to perfect finitely described strategies of the subgroup test.

24 note that since there are no readable variables, L r c i J is constant.

- (2) Soundness : Almost perfect finitely described strategies for the subgroup test are close to almost perfect Z -aligned permutation strategies for the tailored non-local game.

Throughout this section, G is a tailored non-local game with underlying graph G = ( V, E ), length functions /lscript R , /lscript L : V → N with /lscript = /lscript R + /lscript L and Λ = max( ( x ∈ V /lscript x )), formal sets of generators S x = S R x ∪ S L x for every vertex x ∈ V , where S R x = { X x, R ,i | 1 ≤ i ≤ /lscript R ( x ) } and S L x = { X x, L ,i | 1 ≤ i ≤ /lscript L ( x ) } , a readability function R : S →{ 0 1 , } where S = ⋃ x ∈ V S x , a distribution µ over edges E , and decision functions D xy : F S xy 2 → F 2 for every edge xy ∈ E with a controlled linear constraints map L xy : F S R x ∪ S R y 2 → F F Sxy ∪{ } J 2 2 .

Definition 7.1. The synchronous subgroup test ˜ T = ˜ ( T G ) associated with the tailored non-local game G is defined as follows: The set of generators ˜ in the test S ˜ is T S ∪{ } J . The set ˜ which parametrizes the challenges Q of ˜ T is the edge set E of G , and the distribution ˜ over challenges is µ µ of G . The decision function ˜ D xy works as follows (and the subsets ˜ K xy can be derived from this description): Given a subgroup H of F ( ˜ ), S

Check 1. It verifies that

$$\mathbb { J } \notin H \ \ ; \ \mathbb { J } ^ { 2 } \in H \ \ ; \ \forall \mathbb { X } \in S _ { x y } \ \colon \ [ \mathbb { J }, \mathbb { X } ] \in H.$$

$$\forall X \in S _ { x y } & \colon \ X ^ { 2 } \in H, \\ \forall X, X ^ { \prime } \in S _ { x } & \colon \ [ X, X ^ { \prime } ] \in H, \\ \forall Y, Y ^ { \prime } \in S _ { y } & \colon \ [ Y, Y ^ { \prime } ] \in H.$$

Check 2. It verifies that

Check 3. It verifies that

$$\forall X \in S _ { x } ^ { \Re } \cup S _ { y } ^ { \Re } \ \colon \ \mathbb { X } \in H \quad \text{or} \quad \mathbb { J } X \in H.$$

Check 4. If H passed all the previous checks, then the following function ˜ γ R : S R x ∪ S R y → F 2 can be calculated: ˜ γ R ( X ) = 0 if X ∈ H and ˜ γ R ( X ) = 1 if JX ∈ H . After recovering this ˜ γ R , the subset

$$\tilde { L } _ { x y } ( H ) = L _ { x y } ( \tilde { \gamma } ^ { \mathfrak { R } } )$$

can be calculated. So, the decision function verifies that

$$\omega, \, \chi, \, \chi \, \cos \cos \pi \, \max \, \max \, \\ \forall \alpha \in \tilde { L } _ { x y } ( H ) \, \colon \, \int _ { X \in S _ { x } } ^ { \alpha ( J ) } X ^ { \alpha ( X ) } \cdot \prod _ { Y \in S _ { y } } Y ^ { \alpha ( Y ) } \in H, \\ \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \end{array}$$

where the product is according to some pre-fixed ordering of S x and S y .

If any of the above checks did not go through, ˜ D xy rejects H , and otherwise it accepts it.

Remark 7.2 . Let us motivate the checks that the decision function ˜ D xy is applying on H . Let σ : ˜ S → Sym( X ) be a finitely described strategy. If σ always passes Check 1, it means that J acts as a fixed point free central involution on X , which is part of the requirement of a permutation strategy for G (see Definition 6.11). If σ always passes Check 2, then the images of all other variables in ˜ are involutions, and for any fixed S x ∈ V , σ S ( x ) commutes, which are again requirements for σ to be a permutation strategy of G . If σ always passes Check 3, then the readable variables always act as either Id or J , which implies σ is a Z -aligned permutation strategy for G (see Definition 6.24). So, the goal of the first three Checks is to force any finitely described strategy of ˜ T to be a permutation Z -aligned strategy for G . Lastly, Check 4 verifies 'the same' linear relations as G , which means that the winning probability of σ against ˜ T and G are similar.

We are ready to formulate our main theorem:

Theorem 7.3. Let G be a tailored non-local game with max( ( x ∈ V /lscript x )) = Λ &gt; 0 , and let ˜ = ˜ ( T T G ) be its associated synchronous subgroup test, as in Definition 7.1.

- (1) Completeness : If G has a perfect Z -aligned permutation strategy that commutes along edges, then ˜ T has a perfect finitely described strategy.
- (2) Soundness : If ˜ T has a finitely described strategy σ with val( ˜ T , σ ) ≥ 1 -ε , then there exists a quantum strategy ρ such that val( G , ρ ) ≥ 1 -C Λ 4 · 2 6Λ ε , where C &gt; 0 is a universal constant.

The next section is devoted to the proof of Theorem 7.3.

Theorem 7.4 ( TailoredMIP ∗ = RE , see [BCV24]) . There exists a polynomial time algorithm that takes as input (the encoding of) a Turing machine M and outputs (the encoding of) a tailored non-local game G M such that:

- (1) Sampling xy ∈ E according to µ and evaluating D xy ( ) · from the encoding of the game G M can be done in time poly( | M | ) , where | M | is the bit-length of the encoding of M .
- (2) If M halts, then G M has a perfect Z -aligned permutation strategy that commutes along edges.
- (3) If M never halts, then val ∗ ( G M ) ≤ 1 2 / .

Theorem 7.4 is proved in [BCV24].

Corollary 7.5. The Aldous-Lyons Conjecture 1.6 has a negative solution.

Proof. The idea is as follows. Given a Turing machine M , we can define the tailored non-local game G M calculated in Theorem 7.4, and then calculate the associated subgroup test ˜ ( T G M ) from Definition 7.1. In the next paragraph, the following two facts are proved:

- · If M halts, then ˜ ( T G M ) has sofic value 1.
- · On the other hand, if M does not halt, then the sofic value of ˜ ( T G M ) is smaller than 1 -λ M ( ), where λ M ( ) = 2 - | c M | c for some universal constant c &gt; 0 independent of M .

Recall that by Theorem 1.10, there is a computable sequence approaching val erg ( ˜ ( T G M )) from above and another computable sequence approaching val sof ( ˜ ( T G M )) from below. If the Aldous-Lyons Conjecture 1.6 has a positive solution, then these values are the same, and as Corollary 1.12 states, one can approximate val sof ( ˜ ( T G M )) up to any predetermined additive error θ . As λ M ( ) can be computed directly from | M | , one can choose θ = λ M ( ) 2 , and thus deduce whether val sof ( ˜ ( T G M )) &lt; 1 or val sof ( ˜ ( T G M )) &gt; 1 -λ M ( ). This in turn allows one to decide whether M halts or not. Since the Halting Problem is undecidable, this is a contradiction, which implies that Conjecture 1.6 must have a negative solution.

Let us prove the two bullets above. Since the running time of the verification procedure of G M bounds Λ = max( ( x ∈ V /lscript x )), we can use (1) of Theorem 7.4 to deduce that Λ = poly( | M | ). If M halts, then by (2) of Theorem 7.4 and (1) of Theorem 7.3, we have val sof ( ˜ ( T G M )) = 1. If M does not halt, then by (3) of Theorem 7.4, we have val ∗ ( G M ) ≤ 1 2 . Hence, by (2) of Theorem 7.3, we have

$$\frac { 1 } { 2 } \geq 1 - C \Lambda ^ { 4 } \cdot 2 ^ { 6 \Lambda } ( 1 - \text{val} _ { \text{sof} } ( \tilde { \mathcal { T } } ( \mathcal { G } _ { M } ) ) ).$$

Rearranging this inequality, we get

$$\text{val} _ { \text{soft} } ( \tilde { \mathcal { T } } ( \mathcal { G } _ { M } ) ) & \leq 1 - \frac { 1 } { 2 C \Lambda ^ { 4 } \cdot 2 ^ { 6 \Lambda } }. \\ \text{and} \, \frac { \dots } { \dots } \, \frac { \dots } { \dots } \, \frac { \dots } { \dots } \, \sum \, \frac { \dots } { \dots } \, \frac { \dots } { \dots } \, M ^ { | c } \, \dots \, \frac { \dots } { \dots } \,.$$

The quantity 1 2 C Λ 4 · 2 6Λ can be bounded from below by λ M ( ) = 2 - | c M | c , where c &gt; 0 is a universal constant that depends on the constants implicit in the notation Λ = poly( | M | ) (guaranteed by Theorem 7.4), as well as the constant C &gt; 0 appearing in Theorem 7.3. This finishes the proof. /square

## 8. Proving Theorem 7.3

8.1. Proving the completeness in Theorem 7.3. This is the easy direction, we have done most of the work towards it, and here we use the notation that we have established before. Recall that ˜ = S S ∪ { } J . Let σ : S ∪{ } → J Sym(2 n ) be a perfect Z -aligned permutation strategy that commutes along edges for the tailored non-local game G . Further recall that the finitely described IRS Φ( σ ) samples a subgroup H of F as follows it takes a uniform /star ∈ [2 n ] and outputs H = Stab( σ, /star ). By Definition 6.11,

$$d _ { H } ( \sigma ( J ), \text{Id} ) = 1 \ \ ; \ \ \sigma ( J ) ^ { 2 } = \text{Id} \ \ ; \ \ \forall X \in S \ \colon \ \sigma ( J ) \sigma ( X ) = \sigma ( X ) \sigma ( J ).$$

Therefore, for every /star ∈ [2 n ],

$$J \notin Stab ( \sigma, * ) \ \ ; \ \ J ^ { 2 } \in Stab ( \sigma, * ) \ \ ; \ \forall X \in S \ \colon \ [ X, J ] \in Stab ( \sigma, * ),$$

and when Φ( σ ) runs against ˜ T it always passes Check 1. Also by Definition 6.11,

$$\forall X \in S \ \colon \sigma ( X ) ^ { 2 } = \text{Id} \ \ ; \ \ \forall x \in V, \ \forall X, X ^ { \prime } \in S _ { x } \ \colon \ \sigma ( X ) \sigma ( X ^ { \prime } ) = \sigma ( X ^ { \prime } ) \sigma ( X ).$$

Therefore, for every /star ∈ [2 n ],

$$\forall X \in S \ \colon X ^ { 2 } \in \text{Stab} ( \sigma, * ) \ \ ; \ \ \forall x \in V, \ \forall X, X ^ { \prime } \in S _ { x } \ \colon \ [ X, X ^ { \prime } ] \in \text{Stab} ( \sigma, * ),$$

and when Φ( σ ) runs against ˜ T it always passes Check 2. By Definition 6.24, for every /star ∈ [2 n ] we have

$$\forall X \in \mathfrak { R } ^ { - 1 } ( 1 ) \ \colon \ \sigma ( X ). * = * \ \text{ or } \ \sigma ( X ). * = \sigma ( J ). * \,.$$

Namely, for every /star ∈ [2 n ],

$$\forall X \in \mathfrak { R } ^ { - 1 } ( 1 ) \ \colon \ \ X \in \text{Stab} ( \sigma, * ) \ \text{ or } \ J X \in \text{Stab} ( \sigma, * ),$$

and when Φ( σ ) runs against ˜ T it always passes Check 3.

We are left to show that Φ( σ ) always passes Check 4. To that end, we need a couple of claims. The first is a well known and commonly used observation in quantum information theory. For the convenience of the reader, we provide a proof.

Claim 8.1. Let S be a finite set, ρ : S → U n ( ) such that ρ S ( ) commutes 25 and all the images are involutions. Then, given a fixed α : S → F 2 , we have ∑ X ∈ S α ( X ) γ ( X ) = 0 with probability 1 when γ ∼ ρ if and only if ∏ X ∈ S ρ ( X ) α ( X ) = Id . Namely,

$$\mathbb { P } _ { \gamma \sim \rho } [ \langle \alpha, \gamma \rangle = 0 ] = 1 \iff \prod _ { X \in S } \rho ( X ) ^ { \alpha ( X ) } = \text{Id}. \\ \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \, \dots \end{array}$$

25 This claim can be generalized so that a weaker assumption is used. See Section 3 of [BCV24].

Proof. Assume without loss of generality that α is fully supported. Otherwise, we can focus on ρ | Supp( α ) and proceed in the same manner. As before, we can write ρ ( X ) = P X 0 -P X 1 , where P X 0 is the projection on the (+1)-eigenspace of ρ ( X ), and P X 1 is the projection on its ( -1)-eigenspace. By Definition 6.5,

$$\mathbb { m } \cdot 1 & \omega \, \ v a p o v$$

Note that P X 0 + P X 1 = Id, and thus ∑ γ : S → F 2 τ ( ∏ X ∈ S P X γ ( X ) ) is always 1. Therefore,

Thus, ∏ ρ ( X ) = Id if and only if τ ( ∏ ρ ( X )) = 1 if and only if P γ ∼ ρ [∑ X ∈ S γ ( X ) = 0 ] = 1, which finishes the proof. /square

$$+ P _ { 1 } ^ { X } = \text{Id, and thus} \sum _$$

Claim 8.2. Let σ : S ∪{ } → J Sym(2 n ) be a Z -aligned permutation strategy for a tailored game G , and let ρ be the quantum strategy associated with σ (as in Definition 6.14). Then, the restriction of γ ∼ ρ to the readable variables in S xy (which we denoted by γ R ) depends only on the vertex /star ∈ [2 n ] sampled in the beginning of the procedure outlined in Claim 6.21. Furthermore, if we denote the sampled L xy ( γ ) by L xy ( /star ) , emphasizing its dependence on the sampled vertex, then ˜ L xy (Stab( σ, /star )) = L xy ( /star ) , where ˜ L xy was defined in (7.1) .

Proof. Let /star ∈ [2 n ] be some fixed vertex, O x be the σ x orbit of /star , and X ∈ S x be a readable variable. Since σ is Z -aligned, either σ ( X ) ./star = /star or σ ( X ) ./star = σ ( J ) ./star . Now, as discussed in Section 6.4, σ acting on O x is equivalent to an action of F k 2 on itself. Furthermore, checking whether /vector v ∈ B -x that is supported on O x is in the (+1) or ( -1) eigenspace of σ ( X ) depends only on whether /vector v flips along an X -labeled edge in Sch( σ, S ) for some vertex in O x . Since /vector v ∈ B -x , it must flip along J -labeled edges. So, if σ ( X ) ./star = /star then σ ( X ) /vector v = /vector v and γ ( X ) = 0, and if σ ( X ) ./star = σ ( J ) ./star then σ ( X ) /vector v = -/vector v and γ ( X ) = 1. Since this was independent of the specific /vector v that we considered, the first part of the claim is deduced. This proves that ˜ γ R ( X ) = γ R ( X ), where ˜ γ R ( X ) was defined in Check 4 of Definition 7.1, and therefore ˜ L xy (Stab( σ, /star )) = L xy (˜ γ R ) = L xy ( γ R ) = L xy ( /star ) which is the second part of the claim. /square

We can now come back to our proof. Let us, in the spirit of previous notations, denote σ xy = σ | S xy ∪{ } J . Let /star ∈ [2 n ], and let O xy be the orbit of /star under σ xy . Since σ commutes along edges (see Definition 6.5), σ xy induces an action of F S xy ∪{ } J 2 . Since Im( σ xy ) is commuting, the action of readable variables in O xy is constant, namely if a readable variable acts as Id on some /star ∈ O xy , it will act that way on all /star ∈ O xy , and similarly for acting

as J . Furthermore, by Claim 8.2, the linear constraints sampled in the associated game ˜ L xy at a specific vertex /star ∈ O xy are the same as the ones sampled by the tailored non-local game. Joining these observations, there is a set of constraints L such that for every /star ∈ O xy we have ˜ L xy (Stab( σ, /star )) = L xy ( /star ) = L . So, we can focus on the orbit O xy , and study the corner of ρ , which was the quantum strategy induced by σ , with respect to the projection Q O xy : C 2 n → C O xy . Since ρ is a perfect strategy, for every γ that was sampled (according to Claim 6.21) by first choosing /star ∈ O xy , and for every α ∈ L , we have ∑ α ( X ) γ ( X ) = 0. By Claim 8.1, this means that ∏ ρ ( X ) α ( X ) is the identity when restricted to functions supported on O xy that flip along J -labeled edges. By Claim 6.17, we can deduce that ∏ σ ( X ) α ( X ) acts as the identity on O xy . Since this was true for every α in L , and L = ˜ L xy (Stab( σ, /star )) for every /star ∈ O xy , we can conclude that σ always passes Check 4 when run against ˜ . T All in all, σ is a perfect strategy for ˜ , T proving the completeness clause of Theorem 7.3.

## 8.2. Proving the soundness in Theorem 7.3. The plan is as follows:

- · Recall that ˜ = S S ∪{ } J . Given a finitely described strategy σ : ˜ S → Sym( n ) for ˜ , with val( ˜ T T , σ ) ≥ 1 -ε , we perturb it bit by bit until it passes with probability 1 Check 1, Check 2 and Check 3 from the definition of ˜ T (while potentially worsening the probability of passing Check 4).
- · Then, we can bound from below the value of this perturbed strategy using the mechanisms of Section 5.
- · Since the resulting perturbed strategy satisfies the first three checks of ˜ , T it is a Z -aligned permutation strategy for G . For such strategies, we prove that their value against ˜ T induces a lower-bound on their value against G . This will conclude the proof.

The following three propositions are the manifestation of the above plan. We abuse notations and denote by µ the marginal distribution on vertices of G , namely

$$\begin{array} {$$

Also, recall the notion of the significance function s T associated with a test T , defined in (5.3), and the notion of the edit distance d s edit (5.2) between finitely described IRSs. Finally, recall that Λ = max( ( x ∈ V /lscript x )), and assume Λ &gt; 0.

Proposition 8.3. Let σ : ˜ S → Sym( n ) be a finitely described strategy for ˜ T , with val( ˜ T , σ ) ≥ 1 -ε . Denote by ε x the losing probability in ˜ T given that an edge containing x ∈ V was sampled as the challenge - note that E x ∼ µ [ ε x ] = ε . Then, there is a strategy σ ′ : ˜ S → Sym(2 m ) , where m = /ceilingleft n 2 /ceilingright , that passes with probability 1 Check 1, Check 2 and Check 3 in the definition of the associated test ˜ T , and which is close to σ in the following sense:

$$d _ { H } ( \sigma ( \mathbf J ), \sigma ^ { \$$

for some universal constant C 0 &gt; 0 .

Proposition 8.4. Every finitely described strategy σ : ˜ S → Sym(2 n ) for ˜ T that passes with probability 1 Check 1, Check 2 and Check 3 in the definition of the associated test ˜ T is a Z -aligned permutation strategy for G and vice versa. Moreover, there is a universal constant C &gt; 1 0 such that if val( ˜ T , σ ) ≥ 1 -ε , then val( G , ρ ) ≥ 1 -C 1 · 2 2Λ ε where ρ is the quantum strategy associated with σ (Definition 6.14).

Proposition 8.5. Let ˜ T be the test associated with the tailored non-local game G . Then, there is a universal constant C &gt; 2 0 , such that the significance s ˜ τ associated with the test ˜ T satisfies

$$& ( 8. 1 ) & & & \mathfrak { s } _ { \tilde {$$

$$\forall x \in V, \, X \in S _ { x } \, \colon \, \ s _ { \tilde { \Gamma } } ( X ) \leq \mu ( x ) \cdot C _ { 2 } \cdot 2 ^ { 2 \Lambda }.$$

Remark 8.6 . We did not try to optimise the parameters in the three preceding propositions. Actually, we decided to choose a simpler version of the associated synchronous test (Definition 7.1) that provides an exp(Λ) deterioration in the value, as seen in Proposition 8.3. We have variations of tailored games and the associated synchronous test which allow for only a poly(Λ) deterioration in the value, but we could not find any reduction that is independent of Λ.

Now, we can deduce the soundness clause of Theorem 7.3 as a corollary of the preceding propositions.

Proof of (2) in Theorem 7.3. Let σ : ˜ S → Sym( n ) be the given finitely described strategy with value ≥ 1 -ε . By Proposition 8.3 and Proposition 8.5, there is a strategy σ ′ : ˜ S → Sym(2 /ceilingleft n 2 /ceilingright ) passing Check 1, Check 2 and Check 3 with probability 1, and such that the significance weighted distance between σ and σ ′ is

$$\Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \that { \nu } } \right ) \Phi _ { \tilde { \nu } } \left ( \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \that { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right ) \Phi _ { \tilde { \nu } } \right.$$

Therefore, by Claim 5.5,

$$\text{val} ( \tilde { \mathcal { T } }, \sigma ^ { \prime } ) \geq 1 - \varepsilon - 3 C _ { 0 } C _ { 2 } \Lambda ^ { 4 } \cdot 2 ^ { 4 \Lambda } \varepsilon \geq 1 - 4 C _ { 0 } C _ { 2 } \Lambda ^ { 4 } \cdot 2 ^ { 4 \Lambda } \varepsilon.$$

By applying Proposition 8.4 on σ ′ , its associated quantum strategy ρ ′ satisfies

$$\text{val} ( \mathcal { G }, \rho ^ { \prime } ) \geq 1 - 4 C _ { 0 } C _ { 1 } C _ { 2 } \Lambda ^ { 4 } \cdot 2 ^ { 6 \Lambda } \varepsilon.$$

By choosing C = 4 C C C 0 1 2 , we deduce the claim.

/square

We are left to prove Propositions 8.3, 8.4 and 8.5. This is done in a reverse manner.

Proof of Proposition 8.5. Note that J participates in most of the checks in ˜ regardless of the specific challenge. T In Check 1, it appears 3 + 2 | S xy | times, and since | S xy | ≤ 2Λ, this is bounded by 3 + 4Λ. In Check 2 it is not used. In Check 3 it is used at most | S xy | times, which is bounded from above by 2Λ. Lastly, the number of

times J appears in L xy ( γ ) is bounded by the number of subsets of S xy ∪{ } J that contain it, which is 2 | S xy | ≤ 2 2Λ . All in all, the significance of J is at most (3 + 4Λ) + 2Λ + 2 2Λ ≤ 4 · 2 2Λ .

Now, a variable X in S x appears only if we sampled an edge in E with x as one of its endpoints. If this happened, it will appear twice in Check 1, 2 + 2 | S x | times in Check 2, at most twice in Check 3, and at most 2 | S xy ∪{ }|-J 1 times in Check 4. Again, | S x | ≤ Λ and | S xy | ≤ 2Λ, and thus X appears at most 2+2+2Λ+2+2 2Λ ≤ 3 · 2 2Λ times when an edge containing x is sampled. This means that the significance of X is at most µ x ( ) · 3 · 2 2Λ . Choosing C 2 = 4 completes the proof. /square

Proof of Proposition 8.4. Let σ : ˜ S → Sym(2 n ) be a finitely described strategy that passes Check 1, Check 2 and Check 3 of ˜ T with probability 1. Then, from perfectly passing Check 1 and Check 2, σ is a permutation strategy, and by perfectly passing Check 3 it is Z -aligned. The other direction was proved in the completeness analysis in Section 8.1. We are going to prove that

$$\text{val} ( \mathcal { G }, \rho ) \geq 1 - 2 \cdot 2 ^ { 2 \Lambda } ( 1 - \text{val} ( \tilde { \mathcal { T } }, \sigma ) ),$$

and thus C 1 = 2 satisfies the claim.

/negationslash

We start by giving expressions for the success probability of σ in ˜ , and of the associated T ρ in G respectively. Fix an edge xy ∈ E , and denote by σ x = σ | S x ∪{ } J and σ y = σ | S y ∪{ } J the appropriate restrictions of the permutation strategy σ . The intersection of orbits O x ∩ O y , where O x is an orbit of σ x and O y is an orbit of σ y , partitions [2 n ] into disjoint sets. Fixing a pair of orbits O ,O x y such that O x ∩ O y = , by Claim 8.2, there ∅ is a set L O ,O x y xy of subsets of S xy ∪{ } J such that

$$\forall \ast \in O _ { x } \cap O _ { y } \ \col$$

For α ∈ F S xy ∪{ } J 2 , define

$$( 8. 4 ) \sum _ { \substack { x \in S _ { z } \$$

/negationslash

Let Υ ˜ O ,O x y ( α ) be the set of all vertices /star ∈ O x ∩ O y such that σ ( X α ) ./star = σ ( Y α ) ./star , namely all vertices in the intersection of orbits that do not satisfy the subgroup test constraint induced by α . Let

$$\begin{array} {$$

and let

˜

Υ

xy

=

˜

Υ

O ,O

x

y

xy

,

O ,O

⋃

x

y

where the union is over all orbits of σ x and σ y that have a non-empty intersection. Then ˜ Υ xy is the set of all /star ∈ [2 n ] such that ˜ D xy (Stab( σ, /star )) = 0, hence

$$\text{val} ( \tilde { \mathcal { T } }, \sigma )$$

where

$$\varepsilon _ { x y } ( * ) = \frac { | \tilde {$$

and O x and O y are the unique σ x and σ y orbits for which /star ∈ O x ∩ O y .

/negationslash

Recall that according to the procedural sampling described in Claim 6.21, any pair /vector v ∈ B ,/vector -x u ∈ B -y of Fourier basis elements supported on σ x -orbit O x and σ y -orbit O y respectively, is sampled with probability 2 〈 /vector v /vector | u 〉 2 | O x ∩ O y | (conditional on the sampled /star being in O x ∩ O y ), and it induces an 'assignment' γ : S xy ∪ { } → J F 2 for which γ ( J ) = 1. Let Υ O ,O x y ( α ) be the set of all such ( /vector v, /vector u ) for which γ does not satisfy a specific linear constraint α ∈ F S xy ∪{ } J 2 , namely ∑ X ∈ S xy ∪{ } J γ ( X ) α ( X ) = 0. Let

$$\in \mathcal { S } _ { x y } \cup \{ \mathbf I \$$

be the collection of Fourier basis pairs ( /vector v, /vector u ) ∈ B -x × B -y supported on O ,O x y , such that the assignment γ induced by the pair is rejected by D xy . Finally let

$$\mathcal { V } _ { x y } \cdot \mathcal { I m a y$$

which is exactly the collection of possible sampled pairs by the quantum strategy ρ induced by σ , given that the edge xy was asked, that produce an assignment γ satisfying D xy ( γ ) = 0. Hence,

$$& \quad \text{val} ( \mathcal { G }, \rho ) = 1$$

where

$$\delta _ { x y } ( * ) & = \sum _ { ( \vec { v$$

and O ,O x y are the unique orbits for which /star ∈ O x ∩ O y . Observe the following claim.

$$\begin{array} {$$

Claim 8.7. For every α ∈ F S xy ∪{ } J 2 , σ x -orbit O x and σ y -orbit O y such that O x ∩ O y = ∅ , we have

/negationslash

(8.10)

Let us show how to deduce our conclusion assuming the validity of this claim, and then we will address the claim itself. Given /star ∈ O x ∩ O y , we have

$$\mathfrak { A } _ { x } \cap O _ { y }, & \text{ we have } \\ \delta _ { x y } ( * ) & \overset { ( 8. 9 ) } { = } \sum _ { \substack { ( \vec { v }, \vec { u } ) \in \Upsilon _ { x y } ^ { O _ { x }, O _ { y } } } } \frac { 2 \langle \vec { v } | \vec { u } \rangle ^ { 2 } } { | O _ { x } \cap O _ { y } | } \\ & \leq \sum _ { \alpha \in L _ { x y } ^ { O _ { x }, O _ { y } } } \sum _ { \substack { ( \vec { v }, \vec { u } ) \in \Upsilon _ { X } ^ { O _ { x }, O _ { y } ( \alpha ) } } } \frac { 2 \langle \vec { v } | \vec { u } \rangle ^ { 2 } } { | O _ { x } \cap O _ { y } | } \\ & \text{Claim} \leq 8. 7 \sum _ { \alpha \in L _ { x y } ^ { O _ { x }, O _ { y } } } \frac { | \tilde { \Upsilon } ^ { O _ { x }, O _ { y } ( \alpha ) | } } { | O _ { x } \cap O _ { y } | } \. \\ O _ { y }, & \text{ we have by } ( 8. 5 ) \text{ that } \tilde { \Upsilon } ^ { O _ { x }, O _ { y } ( \alpha ) \subseteq \tilde { \Upsilon } _ { x y } ^ { O _ { x }, O _ { y } }, \text{ which using th}$$

Now, for every α ∈ L O ,O x y xy , we have by (8.5) that Υ ˜ O ,O x y ( α ) ⊆ ˜ Υ O ,O x y xy , which using the above analysis means

$$\delta _ { x y } ( * ) \leq \sum _ { \alpha \in L ^ { O _ { x }, O _ { y } } _ { x y } } \, \frac { | \tilde { \Upsilon } ^ { O _ { x }, O _ { y } } _ { x y } | } { | O _ { x } \cap O _ { y } | } \leq 2 ^ { 2 \Lambda + 1 } \cdot \varepsilon _ { x y } ( * ),$$

where the last inequality uses (8.7) and the fact | L O ,O x y xy | ≤ | F S xy ∪{ } J 2 | ≤ 2 2Λ+1 . Therefore,

$$1 - \text{val} ( \mathcal { G }, \rho ) \stackrel { ( 8. 8 ) } { = } \mathbb { E } _ { x y \sim \mu \ast \in [ 2 n ] } \mathbb { E } _ { x y } [ \delta _ { x y } ( \ast ) ] \leq 2 \cdot 2 ^ { 2 \Lambda } \mathbb { E } _ { x y \sim \mu \ast \in [ 2 n ] } [ \varepsilon _ { x y } ( \ast ) ] \stackrel { ( 8. 6 ) } { = } 2 \cdot 2 ^ { 2 \Lambda } ( 1 - \text{val} ( \tilde { \mathcal { T } }, \sigma ) ),$$

proving (8.3) and thus the proposition.

Proof of Claim 8.7. Let ˜ Γ O ,O x y ( α ) be the complement of Υ O ,O x y ( α ) in O x ∩ O y , namely

$$\tilde { \Gamma } ^ { O _ { x }, O _ { y } } ( \alpha ) = ( O _ { x } \cap O _ { y } ) \, \bar { \Upsilon } ^ { O _ { x }, O _ { y } } ( \alpha ).$$

Recall the notation X α and Y α from (8.4). For /star ∈ O x ∩ O y , we have σ ( X α ) ./star ∈ O x and σ ( Y α ) ./star ∈ O y by the fact O x is a σ x -orbit and O y is a σ y -orbit. If /star ∈ ˜ Γ O ,O x y ( α ), then by its definition we have /diamondmath := σ ( X α ) ./star = σ ( Y α ) ./star , and /diamondmath ∈ O x ∩ O y . As σ ( X α ) and σ ( Y α ) are involutions, we have σ ( X α ) . /diamondmath = /star = σ ( Y α ) . /diamondmath , which implies /diamondmath ∈ ˜ Γ O ,O x y ( α ). All in all, ˜ Γ O ,O x y ( α ) is invariant under the actions of X α and Y α - graphically, if we add X α and Y α labels to the Schrier graph of the action σ on [2 n ], then they agree on every /star ∈ ˜ Γ O ,O x y ( α ) and are contained in it.

For ( /vector v, /vector u ) ∈ Υ O ,O x y ( α ) we know that σ ( X α ) /vector v = ± /vector v while σ ( Y α ) /vector u = ∓ /vector u . This means that for every Y α -labeled edge between vertices in ˜ Γ O ,O x y ( α ), /vector v and /vector u agree on one of its endpoints and evaluate to opposites on the other endpoint. This implies

$$\ e v e w e n { \ v e \nolimits \Omega _ { z } \cap O _ { y } } \\ \text{point. This implies} \\ & \langle \vec { v } | \vec { u } \rangle = \sum _ { \ast \in O _ { z } \cap O _ { y } } \vec { v } ( \ast ) \vec { u } ( \ast ) \\ & = \sum _ { \ast \in \hat { T } ^ { O _ { z }, O _ { y } } ( \alpha ) } \vec { v } ( \ast ) \vec { u } ( \ast ) + \sum _ { \ast \in \hat { T } ^ { O _ { z }, O _ { y } } ( \alpha ) } \vec { v } ( \ast ) \vec { u } ( \ast ) \\ & = \sum _ { \ast \in \hat { T } ^ { O _ { z }, O _ { y } } ( \alpha ) } \vec { v } ( \ast ) \vec { u } ( \ast ) + \frac { 1 } { 2 } \sum _ { \ast \in \hat { T } ^ { O _ { z }, O _ { y } } ( \alpha ) } \frac { \vec { v } ( \ast ) \vec { u } ( \ast ) + \vec { v } ( \sigma ( Y ^ { \alpha } ) \ast ) \vec { u } ( \sigma ( Y ^ { \alpha } ) \ast ) } { = 0 } \\ & = \langle \vec { v } \cdot 1 _ { \hat { T } ^ { O _ { z }, O _ { y } } ( \alpha ) } | \vec { u } \rangle, \\ \text{re 1} _ { \hat { T } ^ { O _ { z }, O _ { y } } } \text{ is the indicator function of the set } \hat { T } ^ { O _ { z }, O _ { y } }, \text{and} \cdot \text{is the pointwise product of functions. Thus}$$

where 1 ˜ Υ Ox,Oy is the indicator function of the set Υ ˜ O ,O x y , and · is the pointwise product of functions. Thus,

$$. \tilde { \gamma } ^ { o _ { x }, O _ { y } } & \text{$i$ the indicator function of the set $\tilde{\Upsilon}^{\mathcal{O}_{x}$, and} \cdot$ is the pointwise product of functions. $i$} \\ \sum _ { ( \vec { v }, \vec { u } ) \in \Upsilon ^ { O _ { x }, O _ { y } ( \alpha ) } } \langle \vec { v } | \vec { u } \rangle ^ { 2 } & = \sum _ { \vec { v } \colon \text{Supp} ( \vec { v } ) = O _ { x } } \left ( \sum _ { ( \vec { v }, \vec { u } ) \in \Upsilon ^ { O _ { x }, O _ { y } ( \alpha ) } } \langle \vec { v } \cdot 1 _ { \vec { v } ^ { O } _ { x }, O _ { y } ( \alpha ) } | \vec { u } \rangle ^ { 2 } \right ) \\ & \leq \sum _ { \vec { v } \colon \text{Supp} ( \vec { v } ) = O _ { x } } \left ( \sum _ { \vec { u } \colon \text{Supp} ( \vec { u } ) = O _ { y } } \langle \vec { v } \cdot 1 _ { \vec { v } ^ { O } _ { x }, O _ { y } ( \alpha ) } | \vec { u } \rangle ^ { 2 } \right ) \\ & = ( * ), \\ \intertext { c $1_{\tilde{\Upsilon }^{\mathcal{O}_{x}$, O _ { y } ( \alpha ) } } \text{ is supported on $O_{y}$, we have}$$

and since 1 ˜ Υ Ox,Oy ( α ) is supported on O y , we have

$$\sum _ { \vec { u } \colon \text{Supp} ( \vec { u } ) = O _ { y } } \langle \vec { v } \cdot \mathbf 1 _ { \tilde { \Upsilon } ^ { O _ { x }, O _ { y } ( \alpha ) } } | \vec { u } \rangle ^ { 2 } = \| \vec { v } \cdot \mathbf 1 _ { \tilde { \Upsilon } ^ { O _ { x }, O _ { y } ( \alpha ) } } \| ^ { 2 } = \frac { | \tilde { \Upsilon } ^ { O _ { x }, O _ { y } ( \alpha ) } | } { | O _ { x } | } \.$$

Since there are | O x | / 2 many /vector v ∈ B -x which are supported on O x , we deduce that ( ∗ ) ≤ | ˜ Υ Ox,Oy ( α ) | / 2 , as desired. /square

A short detour into (quite elementary) group stability results is needed for proving Proposition 8.3.

/square

## 8.3. Interlude - Group stability.

Claim 8.8 (Almost involutions are close to involutions) . Let ζ ∈ Sym( X ) . Then, there is τ ∈ Sym( X ) such that τ 2 = Id and d H ( ζ, τ ) = d H ( ζ 2 , Id ) .

$$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdot \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ \tau ( x ) = \begin{cases} \zeta ( x ) & x \in W, \\ x & x \notin W. \end{cases} \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \ddots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\. \end{cases}$$

Proof. Let W = { x ∈ X | ζ 2 .x = x } . Note that the restriction ζ | W is an involution W → W . Define

Then τ 2 = Id and d H ( ζ, τ ) = 1 -| W | | X | = d H ( ζ 2 , Id )

$$d _ { H } ( \zeta ^ { 2 }, \text{Id} ).$$

Claim 8.9 (Almost fixed point free are close to fixed point free) . Let ζ ∈ Sym( X ) be an involution. Assume d H ( ζ, Id) ≥ 1 -ε . Then, there is an involution with no fixed points τ ∈ Sym( Y ) , where | Y | = 2 · /ceilingleft | X | / 2 /ceilingright , such that d H ( ζ, τ ) ≤ 2 ε .

Proof. Let W = { x ∈ X | ζ.x = x } . Since d H ( ζ, Id) = 1 -| W | / | X | , we can deduce that | W | ≤ ε X | | . If W is odd, add a vertex to it and make it even. Now that W is even sized, we can choose any perfect matching on it and define τ to be the involution induced by this perfect matching. Extend τ to the rest of X by letting it act as ζ on the vertices out of W . Then the resulting τ is an involution with no fixed points, and

$$d _ { H } ( \zeta, \tau ) \leq \frac { | W | + 1 } { | X | } \leq 2 \varepsilon.$$

$$\zeta, \tau ) \leq \frac { | W | + 1 } { | X | } \leq 2 \varepsilon.$$

Claim 8.10 (Almost commuting involutions are close to commuting involutions) . Given two involutions ζ, τ ∈ Sym( X ) , there is an involution τ ′ ∈ Sym( X ) such that

$$[ \tau ^ { \prime }, \zeta ] = \text{Id} \quad \text{and} \quad d _ { H } ( \tau, \tau ^ { \prime } ) \leq d _ { H } ( [ \tau, \zeta ], \text{Id} ).$$

Proof. Let δ = d H ([ τ, ζ ] , Id), and let W = { x ∈ X | ζτ.x = τζ.x } . Then | W | = (1 -δ ) | X | . Moreover, for every x ∈ W ,

$$\zeta \tau. ( \zeta. x ) & = \zeta. ( \tau \zeta. x ) = \zeta ^ { 2 } \tau. x = \tau. x = \tau \zeta. ( \zeta. x ) \implies \zeta. x \in W ; \\ \nearrow \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu \nu.$$

$$\tau \zeta. ( \tau. x ) = \tau. ( \zeta \tau. x ) = \tau ^ { 2 } \zeta. x = \zeta. x = \zeta \tau. ( \tau. x ) \implies \tau. x \in W.$$

Hence, W is invariant under the actions of ζ and τ . Thus, the following is well defined

$$\psi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Psi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Pi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phis \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phip \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phim \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phi \circ \Phigma \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \OC \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \lor \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \prod \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \Phi \circ \circ \circ \circ \Phi \circ \circ \Phi \circ \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Psi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi\Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Ph
\Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psigma \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ
\psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi\Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Phi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi
\psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi\Psi\Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \Psi \$$

We therefore can conclude that d H ( τ, τ ′ ) ≤ 1 -| W | | X | = , and δ

$$\dots \, \varphi ^ { \prime } \, - \, \quad & | \Lambda | \quad \varphi ^ { \prime } \\ \forall x \in W \ \colon \ \tau ^ { \prime } \underbrace { \zeta. x } _ { \in W } = \tau \zeta. x = \zeta \tau. x = \zeta \tau ^ { \prime }. x ; \\ \forall x \notin W \ \colon \ \tau ^ { \prime } \underbrace { \zeta. x } _ { \notin W } = \zeta. x = \zeta \tau ^ { \prime }. x, \\ \intertext { required }.$$

which implies [ τ , ζ ′ ] = Id as required.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00110v1-figure-39dac02d-f315-4aa6-9a1b-a79fbf9ff7a2.jpg)

Remark 8.11 . Claim 8.10 can be proved even without assuming that the permutations are involutions (while allowing both permutations to change and not only τ ). This was originally proved in [AP15] and was later reproved with effective bounds in [BM18].

The following is a special case of item 1 of Theorem 2 in [GR09].

Claim 8.12 (Almost actions of finite groups are close to actual actions) . Let G be a finite group, and let f : G → Sym( X ) be a function. Assume that for every g, h ∈ G d , H ( f ( gh , f ) ( g f ) ( h )) ≤ ε . Then, there is a homomorphism ϕ : G → Sym( X ) such that

$$\forall g \in G \ \colon \ d _ { H } ( f ( g ), \varphi ( g ) ) \leq | G | ^ { 2 } \varepsilon.$$

Proof. Let x ∈ X be a vertex such that

$$\forall g, h \in G \ \colon \ \ f ( g h ). x = f ( g ) f ( h ). x.$$

Then, if O ⊆ X is the orbit of x with respect to the action of (the group generated by) Im( f ), then for every y ∈ O we have f ( gh .y ) = f ( g f ) ( h .y ) . To prove that, it is enough to prove it for a single step, namely for y = f ( k .x ) for some k ∈ G (the rest is by induction). So, for every g, h ∈ G , we have

$$f ( g h ). y = f ( g h ) f ( k ). x = f ( g h k ). x = f ( g ) f ( h k ). x = f ( g ) f ( h ) f ( k ). x = f ( g ) f ( h ). y,$$

where all equalities are either f ( k .x ) = y or (8.11). This means that the restriction of f to its action on O induces a homomorphism from G to Sym( O ).

/negationslash

We assumed for every g, h ∈ G , that d H ( f ( gh , f ) ( g f ) ( h )) ≤ ε . Therefore, there are at most | G ε | 2 many vertices z in X for which there is some g, h ∈ G such that f ( gh .z ) = f ( g f ) ( h .z ) . So, the union of orbits as O consists of at least (1 -| G ε X | 2 ) | | of the vertices in X . So, if we define ϕ g .x ( ) = f ( g .x ) whenever x satisfies (8.11), and ϕ g .x ( ) = x otherwise, then ϕ is an action of G it satisfies for every g ∈ G d , H ( f ( g , ϕ g ) ( )) ≤ | G ε | 2 . /square

## 8.4. Proof of Proposition 8.3. Throughout this proof, we use the term triangle inequality for iterative applications of the Hamming distance's triangle inequality, as was used in the proof of Claim 5.5.

Let σ : ˜ S → Sym( n ) be a finitely described strategy for ˜ , with val( ˜ T T , σ ) ≥ 1 -ε . By Check 1, d H ( σ ( J ) 2 , Id) ≤ ε . By Claim 8.8, there is a function σ 1 : ˜ S → Sym( n ) that agrees with σ on all X ∈ S , but σ 1 ( J ) is an involution and d H ( σ ( J ) , σ 1 ( J )) ≤ ε . Again by Check 1, d H ( σ ( J ) , Id) ≥ 1 -ε , and by the triangle inequality d H ( σ 1 ( J ) , Id) ≥ 1 -2 . ε Let m = /ceilingleft n 2 /ceilingright . Then, by Claim 8.9, there is a function σ 2 : ˜ S → Sym(2 m ) such that for every /star ∈ [ n ] ⊆ [2 m ], we have σ 2 ( X ) ./star = σ 1 ( X ) ./star = σ ( X ) ./star , and σ 2 ( J ) is a fixed point free involution with d H ( σ 1 ( J ) , σ 2 ( J )) ≤ 4 . ε All in all, for every X ∈ S ∪{ } J we have d H ( σ 2 ( X ) , σ ( X )) ≤ 5 . ε

Now, let ε x be the losing probability when an edge containing x is sampled in ˜ . T Then, E x ∼ µ [ ε x ] = ε . Furthermore, by Check 2, for every X ∈ S x we have d H ( σ ( X ) 2 , Id) ≤ ε x . Therefore, by the triangle inequality, d H ( σ 2 ( X ) 2 , Id) ≤ d H ( σ 2 ( X ) 2 , σ ( X ) 2 ) + d H ( σ ( X ) 2 , Id) ≤ 10 ε + ε x . By Claim 8.8, there is a function σ 3 : ˜ S → Sym(2 m ) such that σ 3 ( J ) = σ 2 ( J ), and for every x ∈ V and X ∈ S x both σ 3 ( X ) 2 = Id and d H ( σ 3 ( X ) , σ 2 ( X )) ≤ 10 ε + ε x . Now, by Check 1, for every X ∈ S x we have d H ( σ ( X ) σ ( J ) , σ ( J ) σ ( X )) ≤ ε x . Thus, by the triangle inequality, d H ( σ 3 ( X ) σ 3 ( J ) , σ 3 ( J ) σ 3 ( X )) ≤ 30 ε + 2 ε x . Since σ 3 ( X ) and σ 3 ( J ) are involutions, we may apply Claim 8.10 and find a function σ 4 : ˜ S → Sym(2 m ) such that σ 4 ( J ) = σ 3 ( J ), σ 4 ( X ) σ 4 ( J ) = σ 4 ( J ) σ 4 ( X ) and d H ( σ 4 ( X ) , σ 3 ( X )) ≤ 30 ε +2 ε x . Again by the triangle inequality, we deduce that d H ( σ ( J ) , σ 4 ( J )) ≤ 5 , and that ε for X ∈ S x we have d H ( σ ( X ) , σ 4 ( X )) ≤ 40 ε +3 ε x .

Recall that S x = { X x,i | i ≤ /lscript ( x ) } (ignoring readability). We extend σ 4 to F S x 2 in the following way: For ξ : S x → F 2 , let where the product is ordered according to the index i . By Check 2, for every X X , ′ ∈ S x we have

$$\sigma _ { 4 } ( \xi ) = \prod _ { i = 1 } ^ { \ell ( x ) } \sigma _ { 4 } ( X ) ^ { \xi ( X ) }, \\ o \text{ the index $i$}. \text{ By Check $2$, fc}$$

$$d _ { H } ( \sigma ( X ) \sigma ( X ^ { \prime } ), \sigma ( X ^ { \prime } ) \sigma ( X ) ) \leq \varepsilon _ { x }. \\. \. \. \ \dots \ \dots \ \dots.$$

Thus, by the triangle inequality, d H ( σ 4 ( X ) σ 4 ( X ′ ) , σ 4 ( X ′ ) σ 4 ( X )) ≤ 160 ε +13 ε x . Note also that the images of σ 4 are involutions. Therefore, for every ξ , ξ 1 2 : S x → F 2 we have

$$d _ { H } ( \sigma _ { 4 } ( \xi _ { 1 } + \xi _ { 2 } ), \sigma _ { 4 } ( \xi _ { 1 } ) \sigma _ { 4 } ( \xi _ { 2 } ) ) \leq \ell ( x ) ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ) \leq \Lambda ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ). \\........................................................................................................................................................................................................$$

By Claim 8.12 applied to each F S x 2 individually, we have a function σ 5 : ˜ S → Sym(2 m ) such that σ 5 ( S x ) commutes and consists only of involutions, and

$$d _ { H } ( \sigma _ { 4 } ( X ), \sigma _ { 5 } ( X ) ) & \leq | \mathbb { F } _ { 2 } ^ { S _ { x } } | ^ { 2 } \cdot \Lambda ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ) \leq 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ). \\. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.$$

Furthermore, because of the way σ 5 is constructed in the proof of Claim 8.12, by letting σ 5 ( J ) = σ 4 ( J ), the image of J is still a central involution with no fixed points. So, σ 5 always passes Check 1 and Check 2.

Since σ passes Check 3 with probability ε x when an edge with x ∈ V is sampled, we deduce that every readable variable X ∈ S R x satisfies

$$\overset { \mathbb { P } } { \times } [ \sigma ( X ). * = * \text{ or } \sigma ( X ). * = \sigma ( J ). * ] \geq 1 - \varepsilon _ { x }.$$

Hence, by the triangle inequality,

$$\L ^ { \ } v \quad \succeq \quad \L ^ { \ } v \quad \\ \mathbb { P } _ { \ast \in [ 2 m ] } [ \sigma _ { 5 } ( X ), \ast = \ast \text{ or } \sigma _ { 5 } ( X ), \ast = \sigma _ { 5 } ( J ), \ast ] & \geq 1 - \varepsilon _ { x } - d _ { H } ( \sigma _ { 5 } ( J ), \sigma ( J ) ) - d _ { H } ( \sigma _ { 5 } ( X ), \sigma ( X ) ) \\ & \geq 1 - \varepsilon _ { x } - 5 \varepsilon - 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ) \\ & \geq 1 - 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 5 \varepsilon + 1 4 \varepsilon _ { x } ).$$

$$\geq 1 - 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 5 \varepsilon + 1 4 \varepsilon _ { x } ). \quad \\ \dots \cdot \dots \dots \dots$$

By the fact that σ 5 ( S x ) commutes for every x ∈ V , the property σ 5 ( X ) ./star = /star implies σ 5 ( X ) . /diamondmath = /diamondmath for every /diamondmath ∈ O x , where O x is the orbit of /star induced by σ 5 ( S x ) (which we usually denoted as ( σ 5 ) x beforehand). Since σ 5 ( J ) commutes with all images, the same is true for the property σ 5 ( X ) ./star = σ 5 ( J ) ./star . Hence, in each orbit of σ 5 ( S x ), either all vertices /star satisfy σ 5 ( X ) ./star = /star or σ 5 ( X ) ./star = σ 5 ( J ) ./star or none of them. We can thus define a function σ 6 that agrees with σ 5 on the orbits in which all readable variables X ∈ S R x act appropriately, and on the other orbits we just define for every X ∈ S x that σ 6 ( X ) ./star = /star (note that we keep J acting the same no matter what). So, we have

$$\forall x \in V, \ X \in S _ { x } \, \colon \ d _ { H } ( \sigma _ { 6 } ( X ), \sigma _ { 5 } ( X ) ) & \leq | S _ { x } ^ { \Re } | \cdot 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 5 \varepsilon + 1 4 \varepsilon _ { x } ) \\ & \leq 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 3 } ( 1 6 5 \varepsilon + 1 4 \varepsilon _ { x } ), \\ \intertext { a l u r a n e o n c e } \text{the book 1} \text{ $Cbook 2$ and $Cbook 2$ $R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$} \text{$R$}$$

and now σ 6 always passes Check 1, Check 2 and Check 3. By the triangle inequality, d H ( σ 6 ( J ) , σ ( J )) ≤ 5 ε and for every X ∈ S x we have

$$\ < \sim _ { x } \Re \quad \Re \quad \\ d _ { H } ( \sigma _ { 6 } ( X ), \sigma ( X ) ) & \leq 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 3 } ( 1 6 5 \varepsilon + 1 4 \varepsilon _ { x } ) + 2 ^ { 2 \Lambda } \cdot \Lambda ^ { 2 } ( 1 6 0 \varepsilon + 1 3 \varepsilon _ { x } ) \\ & \quad + 3 0 \varepsilon + 2 \varepsilon _ { x } + 1 0 \varepsilon + \varepsilon _ { x } + 5 \varepsilon \\ & \quad \leq 2 ^ { 2 \Lambda } \Lambda ^ { 3 } ( 3 7 0 \varepsilon + 3 0 \varepsilon _ { x } ). \\ \quad = \sigma _ { \mathcal { A } } \text{ and } C _ { n } = 3 7 0. \text{ we deduce the claim}.$$

Choosing σ ′ = σ 6 and C 0 = 370, we deduce the claim.

Remark 8.13 . How better can the parameters in Propositions 8.3, 8.4 and 8.5 be? We know how to make the parameters in Proposition 8.3 polynomial in Λ by implementing a Hadmamard code in every vertex x ∈ V and using [BC22] or [GH17] in the analysis instead of [GR09] - since we did not see any theoretical gain by doing that, and it was a lengthier proof, we decided not to implement this parameter improvement. We are also not sure whether the dependence in Proposition 8.4 is needed or not. Finally, the significance analysis performed in Section 5 is very crude. Can a better analysis allow to remove the dependence on Λ altogether, at least for some rich enough family of games?

## References

- [AB22] M. Ab´ ert and I. Biringer, Unimodular measures on the space of all Riemannian manifolds , Geom. Topol. 26 (2022), no. 5, 2295-2404. MR4520306 ↑ 2
- [ABB + 17] M. Abert, N. Bergeron, I. Biringer, T. Gelander, N. Nikolov, J. Raimbault, and I. Samet, On the growth of L 2 -invariants for sequences of lattices in Lie groups , Ann. of Math. (2) 185 (2017), no. 3, 711-790. MR3664810 ↑ 2, 3
- [ABL22] D. Airey, L. Bowen, and Y. F. Lin, A topological dynamical system with two different positive sofic entropies , Trans. Amer. Math. Soc. Ser. B 9 (2022), 35-98. MR4383230 ↑ 24
- [AGV14] M. Ab´ ert, Y. Glasner, and B. Vir´g, a Kesten's theorem for invariant random subgroups , Duke Mathematical Journal 163 (2014), no. 3, 465-488. ↑ 3, 4, 12
- [AL07] D. Aldous and R. Lyons, Processes on Unimodular Random Networks , Electronic Journal of Probability 12 (2007), no. none, 1454 -1508. ↑ 1, 2, 3, 8
- [AL91] S. Adams and R. Lyons, Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations , Israel J. Math. 75 (1991), no. 2-3, 341-370. MR1164598 ↑ 3
- [Ald07] D. Aldous, Local weak limits and unimodularity , Blog post (2007), available at https://www.stat.berkeley.edu/ ~ aldous/Research/OP/unimodular.html . ↑ 1, 8
- [ALM + 98] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems , J. ACM 45 (1998may), no. 3, 501-555. ↑ 21
- [AP15] G. Arzhantseva and L. P˘unescu, a Almost commuting permutations are near commuting permutations , J. Funct. Anal. 269 (2015), no. 3, 745-757. ↑ 26, 48
- [Ara02] P. Aravind, A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities , arXiv preprint quant-ph (2002). ↑ 36, 37
- [BC22] O. Becker and M. Chapman, Stability of approximate group actions: uniform and probabilistic , J. Eur. Math. Soc. (2022). ↑ 22, 50
- [BCV24] L. Bowen, M. Chapman, and T. Vidick, The Aldous-Lyons Conjecture II: Undecidability , preprint (2024). ↑ 1, 10, 12, 30, 31, 35, 36, 37, 39, 40
- [Bel64] J. S Bell, On the Einstein Podolsky Rosen paradox , Physics Physique Fizika 1 (1964), no. 3, 195. ↑ 5

- [BFL91] L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols , computational complexity 1 (1991), no. 1, 3-40. ↑ 21
- [BL20] O. Becker and A. Lubotzky, Group stability and Property (T) , J. Funct. Anal. 278 (2020), no. 1. ↑ 26
- [BLPS99] I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Group-invariant percolation on graphs , Geom. Funct. Anal. 9 (1999), no. 1, 29-66. MR1675890 (99m:60149) ↑ 3
- [BLT19] O. Becker, A. Lubotzky, and A. Thom, Stability and invariant random subgroups , Duke Math. J. 168 (2019), no. 12, 2207-2234. ↑ 3, 23, 26
- [BM18] O. Becker and J. Mosheiff, Abelian Groups Are Polynomially Stable , International Mathematics Research Notices (IMRN) (2018). ↑ 48
- [BOGKW88] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson, Multi-prover interactive proofs: how to remove intractability assumptions , Proceedings of the twentieth annual acm symposium on theory of computing, 1988, pp. 113-131. ↑ 5, 27
- [Bow10] L. Bowen, Measure conjugacy invariants for actions of countable sofic groups , J. Amer. Math. Soc. 23 (2010), no. 1, 217-245. MR2552252 ↑ 2
- [Bow14] L. Bowen, Random walks on random coset spaces with applications to Furstenberg entropy , Invent. Math. 196 (2014), no. 2, 485-510. MR3193754 ↑ 3
- [BS01] I. Benjamini and O. Schramm, Recurrence of distributional limits of finite planar graphs , Electron. J. Probab. 6 (2001), no. 23, 13. MR1873300 ↑ 2, 3
- [BS11] I. Benjamini and O. Schramm, Percolation in the hyperbolic plane , Selected works of Oded Schramm. Volume 1, 2, 2011, pp. 729-749. MR2883390 ↑ 3
- [CHSH69] J. F Clauser, M. A Horne, A. Shimony, and R. A Holt, Proposed experiment to test local hiddenvariable theories , Physical review letters 23 (1969), no. 15, 880. ↑ 5
- [CHTW04] R. Cleve, P. Hoyer, B. Toner, and J. Watrous, Consequences and limits of nonlocal strategies , Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, pp. 236-249. ↑ 26
- [CL13] V. Capraro and M. Lupini, Introduction to Sofic and Hyperlinear groups and Connes' embedding conjecture (2013), available at https://arxiv.org/abs/1309.2034 . ↑ 2
- [CL23] M. Chapman and A. Lubotzky, Stability of homomorphisms, coverings and cocycles I: Equivalence , preprint (2023). ↑ 19, 22, 26
- [CLS17] R. Cleve, L. Liu, and W. Slofstra, Perfect commuting-operator strategies for linear system games , Journal of Mathematical Physics 58 (2017), no. 1. ↑ 36
- [CS17] A. Coladangelo and J. Stark, Robust self-testing for linear constraint system games , arXiv preprint arXiv:1709.09267 (2017). ↑ 26

- [CVY23] M. Chapman, T. Vidick, and H. Yuen, Efficiently stable presentations from error-correcting codes , Preprint (2023). ↑ 19, 26
- [DKP14] K. Dykema, D. Kerr, and M. Pichot, Sofic dimension for discrete measured groupoids , Trans. Amer. Math. Soc. 366 (2014), no. 2, 707-748. MR3130315 ↑ 2
- [EL10] G. Elek and G. Lippner, Sofic equivalence relations , J. Funct. Anal. 258 (2010), no. 5, 1692-1708. MR2566316 ↑ 2
- [Ele10] G. Elek, Betti numbers are testable , Fete of combinatorics and computer science, 2010, pp. 139149. MR2797963 ↑ 2
- [EPR35] A. Einstein, B. Podolsky, and N. Rosen, Can quantum-mechanical description of physical reality be considered complete? , Physical review 47 (1935), no. 10, 777. ↑ 5
- [ES04] G. Elek and E. Szab´, o Sofic groups and direct finiteness , J. Algebra 280 (2004), no. 2, 426-434. MR2089244 ↑ 2, 8
- [Fri12] T. Fritz, Tsirelson's problem and Kirchberg's conjecture , Reviews in Mathematical Physics 24 (2012), no. 05, 1250012. ↑ 6
- [Gel18] T. Gelander, A view on invariant random subgroups and lattices , Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018 (2018). ↑ 1, 3, 8
- [GH17] W. T. Gowers and O. Hatami, Inverse and stability theorems for approximate representations of finite groups , Mat. Sb. 208 (2017), no. 12, 70-106. ↑ 50
- [Gol21] A. Goldberg, Synchronous linear constraint system games , Journal of Mathematical Physics 62 (2021), no. 3. ↑ 11
- [GR09] L. Glebsky and L. M. Rivera, Almost solutions of equations in permutations , Taiwanese J. Math. 13 (2009), no. 2A, 493-500. ↑ 26, 48, 50
- [Gro99] M. Gromov, Endomorphisms of symbolic algebraic varieties , J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109-197. MR1694588 ↑ 2
- [H¨ ag97] O. H¨ aggstr¨m, o Infinite clusters in dependent automorphism invariant percolation on trees , Ann. Probab. 25 (1997), no. 3, 1423-1436. MR1457624 ↑ 3
- [Hal49] M. Hall, Subgroups of finite index in free groups , Canadian Journal of Mathematics 1 (1949), no. 2, 187-190. ↑ 17
- [Hay14] B. Hayes, An l p -version of von Neumann dimension for Banach space representations of sofic groups , J. Funct. Anal. 266 (2014), no. 2, 989-1040. MR3132735 ↑ 2
- [HLS14] H. Hatami, L. Lov´ asz, and B. Szegedy, Limits of locally-globally convergent graph sequences , Geometric and Functional Analysis 24 (2014), no. 1, 269-296. ↑ 3
- [HMPS19] J W. Helton, K. P Meyer, V. I Paulsen, and M. Satriano, Algebras, synchronous games, and chromatic numbers of graphs , New York J. Math 25 (2019), 328-361. ↑ 11

- [JNP + 11] M. Junge, M. Navascues, C. Palazuelos, D. Perez-Garcia, V. B Scholz, and R. F Werner, Connes' embedding problem and Tsirelson's problem , Journal of Mathematical Physics 52 (2011), no. 1. ↑ 6
- [JNV + 21] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, MIP*=RE , Commun. ACM 64 (2021), no. 11, 131-138. ↑ 1, 6, 9, 10, 11, 30, 35
- [Ka˘ ı15] V. A. Ka˘ ımanovich, Invariance, quasi-invariance and unimodularity for random graphs , Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 441 (2015), no. Veroyatnost i ′ Statistika. 22, 210-238. MR3504507 ↑ 3
- [Kai98] V. A. Kaimanovich, Hausdorff dimension of the harmonic measure on trees , Ergodic Theory Dynam. Systems 18 (1998), no. 3, 631-660. MR1631732 ↑ 3
- [Khe23] A. Khezeli, Unimodular random measured metric spaces and palm theory on them , 2023. ↑ 2
- [KL11] D. Kerr and H. Li, Entropy and the variational principle for actions of sofic groups , Invent. Math. 186 (2011), no. 3, 501-558. MR2854085 ↑ 2
- [KM02] I. Kapovich and A. Myasnikov, Stallings foldings and subgroups of free groups , Journal of Algebra 248 (2002), no. 2, 608-668. ↑ 16, 17, 22
- [KPS18] S.-J. Kim, V. Paulsen, and C. Schafhauser, A synchronous game for binary constraint systems , Journal of Mathematical Physics 59 (2018), no. 3. ↑ 10, 11
- [Li13] H. Li, Sofic mean dimension , Adv. Math. 244 (2013), 570-604. MR3077882 ↑ 2
- [LL19] H. Li and B. Liang, Sofic mean length , Adv. Math. 353 (2019), 802-858. MR3993930 ↑ 2
- [LT16] R. Lyons and A. Thom, Invariant coupling of determinantal measures on sofic groups , Ergodic Theory Dynam. Systems 36 (2016), no. 2, 574-607. MR3503036 ↑ 2
- [NPA08] M. Navascu´ es, S. Pironio, and A. Ac´ ın, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations , New Journal of Physics 10 (2008), no. 7, 073013. ↑ 9
- [Oza13] N. Ozawa, About the Connes embedding conjecture: algebraic approaches , Japanese Journal of Mathematics 8 (2013), no. 1, 147-183. ↑ 6
- [PK13] V. G. Pestov and A. Kwiatkowska, An introduction to hyperlinear and sofic groups , Appalachian set theory 2006-2012, 2013, pp. 145-185. MR3821628 ↑ 2
- [PS23] C. Paddock and W. Slofstra, Satisfiability problems and algebras of boolean constraint system games , arXiv preprint arXiv:2310.07901 (2023). ↑ 11
- [PSS + 16] V. I Paulsen, S. Severini, D. Stahlke, I. G Todorov, and A. Winter, Estimating quantum chromatic numbers , Journal of Functional Analysis 270 (2016), no. 6, 2188-2222. ↑ 11
- [Rud91] W. Rudin, Functional analysis , McGraw-Hill Science/Engineering/Math, 1991. ↑ 13
- [Slo19] W. Slofstra, The set of quantum correlations is not closed , Forum of mathematics, pi, 2019, pp. e1. ↑ 5, 30

- [Sta91] J. R. Stallings, Foldings of G-trees , Arboreal group theory, 1991, pp. 355-368. ↑ 16, 17
- [SZ94] G. Stuck and R. J. Zimmer, Stabilizers for ergodic actions of higher rank semisimple groups , Annals of Mathematics-Second Series 139 (1994), no. 3, 723-748. ↑ 3
- [Tho08] A. Thom, Sofic groups and Diophantine approximation , Comm. Pure Appl. Math. 61 (2008), no. 8, 1155-1171. MR2417890 (2009j:46143) ↑ 2
- [Tsi06] B. Tsirelson, Bell inequalities and operator algebras , Open Quantum Problems (2006). ↑ 6
- [Tsi93] B. S Tsirelson, Some results and problems on quantum bell-type inequalities , Hadronic Journal Supplement 8 (1993), no. 4, 329-345. ↑ 6
- [Ver10] A. M. Vershik, Nonfree actions of countable groups and their characters , Zap. Nauchn. Sem. S.Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 378 (2010), no. Teoriya Predstavleni˘ ı, Dinamicheskie Sistemy, Kombinatornye Metody. XVIII, 5-16, 228. MR2749291 ↑ 3
- [VW 16] T. Vidick, J. Watrous, et al., + Quantum proofs , Foundations and Trends ® in Theoretical Computer Science 11 (2016), no. 1-2, 1-215. ↑ 26
- [Wat09] J. Watrous, Quantum computational complexity , Encyclopedia of Complexity and Systems Science (2009), 7174-7201. ↑ 26
- [Wei00] B. Weiss, Sofic groups and dynamical systems , Sankhy¯ a Ser. A 62 (2000), no. 3, 350-359. Ergodic theory and harmonic analysis (Mumbai, 1999). MR1803462 (2001j:37022) ↑ 2

[Wor99] N. C. Wormald, Models of random regular graphs , Surveys in combinatorics, 1999 (Canterbury), 1999, pp. 239-298. MR1725006 ↑ 24

Lewis Bowen Department of Mathematics 1 University Station C1200 University of Texas at Austin Austin, TX, 78712 USA. Email address : lpbowen@math.utexas.edu Michael Chapman Courant Institute of Mathematical Sciences New York University, 251 Mercer St, New York, NY 10012, USA. Email address : mc9578@nyu.edu Alexander Lubotzky Weizmann institute of Science Rehovot, Israel. Email address : alex.lubotzky@mail.huji.ac.il Thomas Vidick Weizmann institute of Science Rehovot, Israel. Email address : thomas.vidick@weizmann.ac.il
Lewis Bowen Michael Chapman Alexander Lubotzky Thomas Vidick
The Aldous--Lyons Conjecture I: Subgroup Tests
This paper, and its companion [BCV24], are devoted to a negative resolution
of the Aldous--Lyons Conjecture [AL07, Ald07]. This conjecture, originated in
probability theory, is well known (cf. [Gel18]) to be equivalent to the
statement that every invariant random subgroup of the free group is co-sofic.
We disprove this last statement.
  In this part we introduce subgroup tests. These tests are finite
distributions over continuous functions from the space of subgroups of the free
group to $\{0,1\}$. Subgroup tests provide a general framework in which one can
study invariant random subgroups of the free group. Classical notions such as
group soficity and group stability arise naturally in this framework. By the
correspondence between subgroups of the free group and Schreier graphs, one can
view subgroup tests as a property testing model for certain edge-labeled
graphs. This correspondence also provides the connection to random networks.
  Subgroup tests have values, which are their asymptotic optimal expectations
when integrated against co-sofic invariant random subgroups. Our first main
result is that, if every invariant random subgroup of the free group is
co-sofic, then one can approximate the value of a subgroup test up to any
positive additive constant. Our second main result is an essentially value
preserving correspondence between certain non-local games and subgroup tests.
By composing this correspondence with a stronger variant of the reduction in
MIP*=RE [JNV+21], proved in the companion paper [BCV24], we deduce that
approximating the sofic value of a subgroup test is as hard as the Halting
Problem, and in particular, undecidable. The combination of our two main
results proves the existence of non co-sofic invariant random subgroups of the
free group.