Sofic group

Template:Short description Template:Use dmy dates

Two balls of radius 2 in the Cayley graph of the dihedral group $D_{4}$ . Both balls contain 7 of the 8 group elements and are isomorphic as edge-colored graphs. Furthermore, for *any* radius $r$ and $ε > 0$ , we can use the approximating graph $G_{0}$ as the full Cayley graph itself, where the set $W$ of all vertices satisfies $| W | / | V | = 8 / 8 = 1 > 1 - ε$ . Since all 8 vertices have isomorphic $r$ -balls (by the vertex-transitivity of Cayley graphs), $D_{4}$ is sofic.

In mathematics, a sofic group is a group whose Cayley graph is an initially subamenable graph, or equivalently a subgroup of an ultraproduct of finite-rank symmetric groups such that every two distinct elements of the group have distance 1.Template:Sfnp They were introduced by Gromov as a common generalization of amenable and residually finite groups.Template:Sfnp The name "sofic", from Hebrew Template:Lang 'finite', was later applied by Weiss,Template:Sfnp following his use of the word as a generalization of finiteness in sofic subshifts. A non-sofic group is a group that is not a sofic group.

The class of sofic groups is closed under the operations of taking subgroups, extensions by amenable groups, and free products. A finitely generated group is sofic if it is the limit of a sequence of sofic groups. The limit of a sequence of amenable groups (that is, an initially subamenable group) is necessarily sofic, but there exist sofic groups that are not initially subamenable groups.Template:Sfnp

Gromov proved that Sofic groups are surjunctive.Template:Sfnp That is, they obey a form of the Garden of Eden theorem for cellular automata defined over the group (dynamical systems whose states are mappings from the group to a finite set and whose state transitions are translation-invariant and continuous) stating that every injective automaton is surjective and therefore also reversible.Template:Sfnp

Existence of non-sofic groups

In 2026, artificial intelligence research company OpenAI announced a machine-checkable proof by construction of the existence of a non-sofic countable discrete group.^[1]^[2] The existence of such groups was previously an open question.