Non-Sofic Groups

A group is a set of actions that you can combine and undo. One example is the four rotations of a square: by 0, 90, 180 and 270 degrees. Two rotations combine into another rotation, and every rotation can be undone. Another example is the whole numbers with addition: "add 3" and "add 5" combine to give "add 8", and "add $-3$" undoes "add 3".

A group has a multiplication table, which says what each pair of actions combines into. Some groups are infinite, so their tables never end.

Now try to imitate a group with shuffles. A shuffle rearranges a finite list of positions. Give each action its own shuffle, so that doing two shuffles in a row matches the table.

The whole numbers show how this works. Use a clock with 12 positions, as in the figure. "Add 1" moves every position one step, and "add 5" moves every position five steps. Doing both moves six steps, which matches $1+5=6$.

This works until you reach 12: "add 12" does nothing on this clock, although 12 is not 0. The fix is a larger clock, because a large enough clock imitates any finite part of the table.

A group is sofic if every finite part of its table can be imitated in this way on some finite list. A small fraction of positions can give wrong results. Each action other than "do nothing" must move almost every position. That last condition stops the useless model in which every action does nothing.

So a sofic group looks finite when you look at any finite part of it, even if the whole group is infinite. All finite groups are sofic, and so are many infinite groups, such as the whole numbers. Nobody could find a group that fails. The open question was whether every countable group is sofic. A group is countable if its actions can be put in one endless list.

OpenAI reports that the answer is no. Its example comes from operations on endless strings of 0s and 1s. The operation $s_0$ puts a 0 at the front of a string. The operation $t_0$ removes a 0 from the front, and it gives nothing if the string starts with 1. The operations $s_1$ and $t_1$ do the same with 1.

These operations have a strange property. If you do $s_0$ and then $t_0$, you get your string back. If you do $t_0$ and then $s_0$, a string that starts with 1 is lost. So $t_0$ undoes $s_0$, but $s_0$ does not undo $t_0$. Finite square tables of numbers cannot behave in this way.

The new group is built from these operations. It contains the combinations that can be fully undone. The theorem says that this group is not sofic, so no finite list of shuffles can imitate it, even with small errors. The proof builds on work of Gábor Kun and Andreas Thom, and later papers give further examples.

So some groups cannot be studied through finite models. Many theorems had proofs only for sofic groups, and those proofs do not apply to these groups.