Sofic group

Two balls of radius 2 in the Cayley graph of the dihedral group . Both balls contain 7 of the 8 group elements and are isomorphic as edge-colored graphs. Furthermore, for any radius and , we can use the approximating graph as the full Cayley graph itself, where the set of all vertices satisfies . Since all 8 vertices have isomorphic -balls (by the vertex-transitivity of Cayley graphs), 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.[1] They were introduced by Gromov as a common generalization of amenable and residually finite groups.[2] The name "sofic", from Hebrew סופי 'finite', was later applied by Weiss,[3] 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.[4]

Gromov proved that Sofic groups are surjunctive.[1] 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.[5]

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.[6][7] The existence of such groups was previously an open question.

References

Notes

  1. 1 2 Ceccherini-Silberstein & Coornaert (2010), p. 276.
  2. ↑ Gromov (1999).
  3. ↑ Weiss (2000).
  4. ↑ Cornulier (2011).
  5. ↑ Ceccherini-Silberstein & Coornaert (2010), p. 56.
  6. ↑ "Ten advances in mathematics and theoretical computer science". OpenAI. 1 August 2026. Retrieved 2 August 2026.
  7. ↑ Sparkes, Matthew (3 August 2026). "OpenAI announces solutions to 10 longstanding maths problems". New Scientist. Archived from the original on 3 August 2026. Retrieved 4 August 2026.

Bibliography

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.