I gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group:

https://t.co/vteaqpx7Ix

Existence of a Non-Sofic Group: Lecture Analysis Based on OpenAI’s Proof

TL;DR: This lecture introduces and explains OpenAI’s recent proof of the existence of a non-sofic group, demonstrating how to construct the proof using concepts like Cayley graphs, locally embedding finite (LEF) groups, sofic groups, Thompson group V, and Property T.

Background and Introduction

This lecture is not original work by the speaker; its content is based on two papers published by OpenAI on August 5th and 6th. The speaker became interested in the papers, used a chat assistant to help understand them, and is presenting the explanation here. The speaker clarifies they are not a group theorist and asks the audience to avoid overly deep questions.

Core Concepts: Groups, Cayley Graphs, and Finite Approximations

The lecture begins with fundamental definitions: the groups (\gamma) discussed are finitely presented and finitely generated. For each group, there is a fixed finite generating set (S = {s_1, …, s_k}), which is closed under taking inverses.

The Cayley graph of group (\gamma) with respect to generating set (S) is an infinite graph: each vertex corresponds to an element of the group, and each vertex has a labeled outgoing edge for each generator (s_i). Since the generating set is closed under inverses, edges (s_i) and (s_i^{-1}) are considered inverses, making the Cayley graph an undirected graph.

The core question is: For a well-behaved infinite Cayley graph, can we find a corresponding finite graph that is similar in some sense? To address this, the lecture introduces several terms:

S-Graph and R-Correct Vertices

• S-Graph: A finite graph with edges labeled by the group generating set (S). Each vertex has an outgoing edge for each (s_i), and edges ((v, s_i)) and ((w, s_i^{-1})) are inverses. An S-graph is not necessarily a Cayley graph and does not need to satisfy the group’s relations.
• R-Correct Vertex: For a given radius (R), a vertex (v) in graph (G) is called (R)-correct if its (R)-neighborhood (as a labeled graph) is identical to the neighborhood of any vertex at distance (R) in the Cayley graph of group (\gamma).

Finite Approximability of Groups: From LEF to Sofic

LEF Groups (Locally Embedding Finite)

Defined by Vershik and Gordon (1997): Group (\gamma) is LEF if for any large radius (r), there exists a finite (S)-graph (G) such that all vertices in (G) are (r)-correct.

Example: The additive group of integers (\mathbb{Z}) (generating set ({+1, -1})). Its Cayley graph is an infinite path. For any radius (r), one can construct a cycle (a finite graph) of length approximately (2r+2) that looks like the infinite path within distance (r), making (\mathbb{Z}) an LEF group.

However, not all groups are LEF. Requiring all vertices to be perfectly correct is too strict, leading to the introduction of a more relaxed condition.

Sofic Groups

Proposed by Gromov (1999), with the name suggested by Weiss (meaning “finite” in Hebrew): Group (\gamma) is sofic if for all radii (r) and all (\epsilon > 0), there exists a finite (S)-graph (G) such that at least (1-\epsilon) fraction of the vertices in (G) are (r)-correct.

If all groups were sofic, then any well-behaved infinite Cayley graph could be approximated by a finite graph that “looks pretty close.” But the theorem states: There exists a non-sofic group. This is not entirely unexpected; the idea that every group is sofic was overly optimistic, and the challenge was to find a counterexample.

Core Proposition for Proving Non-LEF (and Non-Sofic)

The lecture will prove a proposition that can be used to show certain groups are not LEF. This proof framework can be upgraded to show groups are non-sofic by incorporating Property T.

Proposition Statement

Let (\gamma) be an infinite group, (H) a subgroup of (\gamma), and (\gamma) generated by (H) along with two other elements (\rho) and (\sigma) (where (H) itself is finitely generated). Assume the following three properties hold:

1. (\rho H \rho^{-1} \subseteq H) (i.e., (\rho) normalizes (H)).
2. (\sigma) commutes with all elements (h) in (H).
3. The element (\tau_L = \rho \sigma \rho^{-1}) does not commute with all elements in (H).

If such a group (\gamma) exists with subgroup (H) and elements (\rho) and (\sigma), then (\gamma) is not an LEF group.

Upgrading from Non-LEF to Non-Sofic (Using Property T)

Property T is a group property implying the group’s Cayley graph is not only an expander graph but its expansion is “local” — there exists some finite radius (e.g., 5) such that expansion can be proven by observing only the radius-5 neighborhood of each vertex (Ozawa’s theorem).

The upgrade思路 is as follows: If both group (\gamma) and subgroup (H) have Property T, then all finite approximation graphs (S-graphs) constructed based on them will also be expander graphs. Expansion helps overcome the issue of “a few incorrect vertices.” Because in an expander graph, if only a few vertices are “wrong,” this error “spreads” and forces many vertices to be incorrect, contradicting the premise that only a very small fraction of errors are allowed. Thus, this proof of non-LEF can be upgraded to a proof of non-soficity by requiring the group to have Property T.

Specific Example: Thompson Group V

The lecture provides a concrete group (\gamma) that satisfies all the conditions of the proposition: Thompson group (V).

Definition of the Group

Thompson group (V) can be understood as the symmetry group of an infinite binary tree (or binary search tree). The image shows a rooted infinite binary tree. The group is generated by operations that swap disjoint subtrees within the tree. For example, one subtree can be swapped with another; these operations generate the entire group. Although it seems to require infinitely many generators, it can be generated by finitely many elements (by combining swaps near the root and swaps at different depths).

Subgroup H, Elements ρ and σ

• Subgroup (H): Isomorphic to (\gamma), but restricted to performing subtree swaps only within the left subtree of the root node. The fact that (H) is isomorphic to (\gamma) is crucial for the upgrade argument requiring Property T.
• Element (\rho): Not a simple subtree swap but a permutation generated by several swaps. It corresponds to a binary search tree rotation operation along the right boundary of the tree. Its inverse (\rho^{-1}) corresponds to the same rotation along the left boundary.
• Element (\sigma): Not detailed in this part of the lecture, but it is a key generator required by the proposition.

Verification of Conditions

1. Since (H) acts only on the left subtree and the rotation operation (\rho) involves the entire tree structure, it can be verified that (\rho H \rho^{-1} \subseteq H).
2. Element (\sigma) is set to commute with all elements in (H).
3. Element (\tau_L = \rho \sigma \rho^{-1}) is proven not to commute with all elements in (H).

Therefore, Thompson group (V) satisfies the conditions of the proposition, making it not an LEF group.

Upgrade to a Non-Sofic Group

To obtain a non-sofic group, a larger group (\gamma’) and subgroup (H’) are needed that not only satisfy the combinatorial conditions above but also both possess Property T. The lecture mentions that such a (\gamma’) can be constructed by “embedding” Thompson group (V) in some way into a larger 3x3 matrix group (for example, a matrix group over an infinite ring, which typically has Property T). The resulting group (\gamma’) (possibly a matrix group in a group algebra over a finite field) will satisfy all conditions and have Property T, thus becoming a non-sofic group.

Summary

The lecture clearly explains the core idea of OpenAI’s proof of the existence of a non-sofic group: by constructing a group with a special internal structure (like Thompson group V), its combinatorial properties of “a subgroup isomorphic to itself but non-commuting after action by elements” are used to break the possibility of finite approximability (non-LEF). Furthermore, by requiring the group to possess Property T, this destructive power is elevated to tolerate a “small fraction of errors,” thereby proving the group is non-sofic.

Source: https://youtu.be/uOQvzLjJK6c