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

非索菲克群的存在性：基于OpenAI证明的卡内基梅隆大学讲座解析

TL;DR： 本讲座介绍并解释了OpenAI近期证明的非索菲克群的存在性，通过凯莱图、局部嵌入有限（LEF）和索菲克群等概念，展示了如何利用Thompson群V和性质T来构建证明。

背景与介绍

本讲座并非由演讲者原创，其内容基于OpenAI于8月5日和6日先后发表的两篇论文。演讲者对论文产生了兴趣，并借助聊天助手帮助理解，最终在此进行讲解。演讲者声明自己并非群论专家，并请听众避免过于艰深的问题。

核心概念：群、凯莱图与有限近似

讲座从基础定义开始：所讨论的群 (\gamma) 均为有限展示且有限生成。对于每个群，存在一个固定的有限生成元集合 (S = {s_1, …, s_k})，且该集合在取逆下封闭。

群 (\gamma) 关于生成集 (S) 的凯莱图 是一个无限图：图中每个顶点对应群中的一个元素，每个顶点都有一条标有每个生成元 (s_i) 的出边。由于生成集在逆元下封闭，边 (s_i) 和 (s_i^{-1}) 互为反向边，因此凯莱图被视为无向图。

核心问题是：对于一个优秀的无限凯莱图，能否找到一个对应的有限图，使其在某种意义上与原图相似？为此，讲座引入了几个术语：

S-图与 R-正确的顶点

• S-图：一个有限图，其边用群生成集 (S) 标记。每个顶点都有一条标有每个 (s_i) 的出边，且边 ((v, s_i)) 和 ((w, s_i^{-1})) 互为反向边。S-图不一定是一个凯莱图，也无需满足群的关系。
• R-正确的顶点：对于给定半径 (R)，图 (G) 中的一个顶点 (v) 被称为 (R)-正确的，如果以其为中心的 (R)-邻域（作为标记图）与群 (\gamma) 的凯莱图中任意距离 (R) 的邻域完全相同。

群的可有限近似性质：从 LEF 到索菲克

LEF 群（局部嵌入有限）

由 Vershik 和 Gordon（1997）定义：群 (\gamma) 是 LEF 的，如果对于任意大的半径 (r)，都存在一个有限的 (S)-图 (G)，使得其中所有顶点都是 (r)-正确的。

例子：整数加法群 (\mathbb{Z})（生成集 ({+1, -1})）。其凯莱图是一条无限路径。对于任意半径 (r)，可以构造一个长度约为 (2r+2) 的环（有限图），该环在距离 (r) 范围内的邻域看起来与无限路径无异，因此 (\mathbb{Z}) 是 LEF 群。

然而，并非所有群都是 LEF。人们意识到要求所有顶点完全正确过于严格，因此引入了更宽松的条件。

索菲克群

由 Gromov（1999）提出，名称由 Weiss 建议（意为希伯来语中的“有限”）：群 (\gamma) 是 索菲克 的，如果对于所有半径 (r) 和所有 (\epsilon > 0)，都存在一个有限的 (S)-图 (G)，使得其中至少 (1-\epsilon) 比例的顶点是 (r)-正确的。

如果所有群都是索菲克群，那么任何优秀的无限凯莱图都可以用一个“看起来差不多”的有限图来近似。但定理指出：存在一个非索菲克群。这并非意料之外，人们早已认为每个群都是索菲克群的想法过于乐观，挑战在于找到反例。

证明非 LEF（及非索菲克）的核心命题

讲座将证明一个命题，该命题可用于展示某些群不是 LEF。这个证明的框架可以通过引入性质T 升级为证明群是非索菲克的。

命题陈述

设 (\gamma) 是一个无限群，(H) 是 (\gamma) 的一个子群，且 (\gamma) 由 (H) 和另外两个元素 (\rho, \sigma) 生成（(H) 本身是有限生成的）。假设满足以下三条性质：

1. (\rho H \rho^{-1} \subseteq H) （即 (\rho) 正规化 (H)）。
2. (\sigma) 与 (H) 中的所有元素 (h) 交换。
3. 元素 (\tau_L = \rho \sigma \rho^{-1}) 不与 (H) 中的所有元素交换。

如果存在这样的群 (\gamma) 以及子群 (H)、元素 (\rho) 和 (\sigma)，那么 (\gamma) 不是 LEF 群。

从 LEF 到非索菲克的升级（利用性质T）

性质T 是群的一个性质，它意味着群的凯莱图不仅是扩张图，而且这种扩张性是“局部的”——存在某个有限半径（例如5），使得仅通过观察每个顶点半径为5的邻域，就能证明该图是扩张图（Ozawa定理）。

升级思路如下：如果群 (\gamma) 和子群 (H) 都具有性质T，那么基于它们构造的所有有限近似图（S-图）也将是扩张图。扩张性有助于克服“少数顶点不正确”的问题。因为如果一个扩张图只有少数几个顶点是“错的”，这种错误会“传播”并迫使许多顶点出错，但这与只允许极少数错误的前提矛盾。因此，这个关于非LEF的证明可以通过要求群具有性质T来升级为非索菲克性的证明。

具体例子：Thompson 群 V

讲座给出了一个满足上述命题所有条件的具体群 (\gamma)，即 Thompson 群 (V)。

群的定义

Thompson群 (V) 可以被理解为无限二叉树（或二叉搜索树）的对称群。图中显示了一棵有根的无限二叉树。该群由交换树中不相交子树的操作生成。例如，可以交换一棵子树与另一棵子树，这些操作生成了整个群。尽管看似需要无穷多个生成元，但可以通过有限个生成元（通过组合靠近根的交换和深度不同的交换）来生成整个群。

子群 H、元素 ρ 与 σ

• 子群 (H)：与 (\gamma) 同构，但限制为仅在根节点的左子树内进行子树交换。(H) 与 (\gamma) 同构这一事实，对于需要性质T的升级论证至关重要。
• 元素 (\rho)：不是简单的子树交换，而是由几个交换生成的置换。它对应于沿着树的右边界进行的一次二叉搜索树旋转操作。其逆元 (\rho^{-1}) 则对应于沿着左边界进行相同的旋转。
• 元素 (\sigma)：讲座未在此部分详细定义，但它是命题所需的一个关键生成元。

验证条件

1. 由于 (H) 只作用于左子树，而旋转操作 (\rho) 涉及整个树的结构，可以验证 (\rho H \rho^{-1} \subseteq H)。
2. 元素 (\sigma) 被设定为与 (H) 中所有元素交换。
3. 元素 (\tau_L = \rho \sigma \rho^{-1}) 被证明不与 (H) 中所有元素交换。

因此，Thompson群 (V) 满足命题的条件，从而 不是 LEF 群。

升级为非索菲克群

要获得非索菲克群，需要一个更大的群 (\gamma’) 和子群 (H’)，它们不仅满足上述组合条件，还都具有性质T。讲座提到，可以通过将Thompson群 (V) 以某种方式“塞进”一个更大的3x3矩阵群（例如，在一个无限环上的矩阵群，这类群通常具有性质T）中来构造这样的 (\gamma’)。最终得到的群 (\gamma’)（可能是某个有限域上的群代数中的矩阵群）将满足所有条件并具有性质T，从而成为一个非索菲克群。

总结

讲座清晰地阐述了OpenAI证明非索菲克群存在性的核心思想：通过构造一个具有特殊内部结构（如Thompson群V）的群，利用其“子群可嵌入自身但通过元素作用后不能交换”的组合性质来破坏有限近似的可能性（非LEF）。进一步，通过要求群具有性质T，将这种破坏力提升到容忍“小比例错误”的层次，从而证明该群是非索菲克的。

Source: https://youtu.be/uOQvzLjJK6c