The Setting
Take a finitely presented group in which every element has finite order. Must be finite, or can finitely many generators and defining relations produce an infinite group whose elements all have finite order?
These notes go through the theorem addressing that question via a Steinberg group of rank over a concrete algebra over the two-element field , together with the definitions it is built on.
Steinberg Groups and Periodicity
A group is periodic if every element satisfies for some positive integer .✦
For elements and of a group , the commutator is the product .✦
Let be a unital associative ring and let be a nonnegative integer. For a nonnegative integer , a root of rank is an ordered pair of distinct indices .✦ For a unital associative ring and a nonnegative integer , a Steinberg generator of rank over is a pair of a root of rank and a scalar , corresponding to the free generator in the free group on all such pairs.✦ The Steinberg group is the quotient of by the normal closure of the Steinberg relators (1) for indices and scalars : (1)✦
The Steinberg group statement is the assertion that there exists a unital associative -algebra such that is infinite, finitely presented, and periodic.✦ The Burnside group statement is the assertion that there exists an infinite, finitely presented periodic group.✦
Word-rewriting Algebras
For a set , the free monoid is the monoid of finite words over under concatenation.✦ Over a unital associative ring , the monoid algebra is the free -module with basis monomials indexed by words and multiplication determined by for all .✦
A rewriting table on is a pair consisting of a replacement relation and a zero set .✦ Over a unital associative ring , the defining relation set of is given by (2), (2)✦ and the algebra of over is the quotient by the two-sided ideal generated by .✦
Circuits, Schedules, and Finite-table Rewriting
For a positive integer , a circuit wire on signals is either a Boolean constant in or an index in .✦ A three-wire circuit clause on signals consists of three circuit wires on signals together with a Boolean truth function .✦ A combinational not-AND (NAND) circuit on inputs with gates is a sequence of two-input NAND gates whose inputs are wires on earlier signals; evaluating at an assignment in produces values on all signals, and its defining clauses form a list of three-wire clauses on signals.✦
A single-tape Turing machine with finite alphabet and state set is specified by a transition rule , which determines the local update of each tape cell label (carrying a symbol in , an origin bit, and either a head state in or none) from itself and its two neighbors. A binary coding of width for consists of an encoding map from tape cell labels to together with a left-inverse decoding map✦, and a circuit realization of consists of a combinational NAND circuit of gates on inputs and output wires computing the encoded local update.✦ Compiling a universal stack-machine interpreter wrapped with a bit-packet input decoder of positive packet width (the number of input token packets) onto one tape yields a concrete transition rule equipped with a one-hot coding of width and a NAND circuit realization of gates.
Fix an integer scale . For an integer scale , a table memory address of scale is either a data address or a certificate address .✦ A verification task is a pair consisting of an arity and a zero-task flag .✦ A verification clause of scale consists of three memory addresses of scale and a Boolean truth function on , holding on a Boolean assignment to data and certificate addresses when its truth function evaluates to on its three address readings.✦ A clause schedule of scale assigns to each verification task a positive clause count and a family of verification clauses indexed by .✦
For a nonnegative integer , the binary length is the number of bits in the binary expansion of (with )✦, and the prefix encoding is the bitstring obtained by prepending ones and a zero to the -bit binary expansion of .✦ For bitstrings and , the program specialization is the concatenation of , , , , and .✦ A tableau layout of scale for bit width , gate count , time , and width is an origin column together with the capacity bounds and ✦; it indexes the tape cell bits and interior gate bits as certificate addresses of scale and compiles a combinational NAND circuit, initial row input bits, boundary blanks, and an accepting origin pattern into a clause schedule of scale . Given a program , a height parameter with , and a task , the initial row configuration places along row starting after the concatenation of , , , , and followed by data addresses for blocks of bits (doubled to both sides when ).
For an integer scale , a finite-table cell of scale consists of a syntactic skeleton (a core position in , palette color in , or stop position; an idle, left, boundary, full, or right marker; and block metadata specifying task arity in , zero-task flag, and block index at most the arity), a palette checker state (idle, passed, or head seeking a color), two data bits, an certificate bit, and a head state (side flag, clause index in , one of nine execution phases, and a three-bit register).✦ Relative to a schedule of scale and a data bound , formatted cells undergo symmetric unary transitions on single cells and symmetric binary transitions on compatible adjacent pairs that sweep across blocks, accumulate clause address bits in , test the truth predicates of , and check palette color distinctness, defining the cell replacement relation .✦ A single cell belongs to the unary zero set if it fails formatting, hits a register or truth-predicate violation in an execution phase (or reaches success with zero-task flag ), or holds a passed palette check on its own color✦, while a pair of cells belongs to the binary zero set if it violates local adjacency compatibility, repeats a palette color adjacently, or places a head checker seeking another color immediately before a stop position.✦
For an integer , set and let be the alphabet of -bit strings.✦ Encoding each cell of scale into integer bits and flag bits yields a partial decoding map from to cells of scale . For a schedule of scale and a data bound , the finite-table rewriting table on has replacement relation lifting to decoded words of length one or two, and zero set consisting of all decoded unary or binary zero words together with all one-letter words whose letter fails to decode✦; given a flag and words , the table entry predicate for holds when either , is empty, and is a zero word of , or and lies in the replacement relation of .✦
Machine Hierarchies and the Coordinate Ring
Let and be integers, and set and . For integers and , bit width , and gate count , a program of length satisfies the layout fit condition at for if , , , , both the tableau certificate count and clause count for are at most , and .✦
A self-simulating machine hierarchy of dilation consists of a finite bitstring program and a threshold height such that for every integer , the self-specialized program satisfies the layout fit condition at for , and the tableau schedule at height (compiled from the circuit and the initial row configuration for and with origin ) satisfies the certification equivalence: for every verification task and data assignment , there exists a certificate assignment satisfying all clauses of together with if and only if the table entry predicate holds for , where and are the candidate words of length in read from the two sides of (with empty when ).✦ For any unital associative ring and integer , the hierarchy algebra is the table algebra .✦
For the dilation factor , let be the threshold height of the concrete self-simulating machine hierarchy of dilation constructed from and . The coordinate ring is the unital associative -algebra defined by (3): (3)✦
The Claim
Theorem 1. Let be the coordinate ring defined in (3). Then (4) and (5) hold: (4)✦ (5)✦ Moreover, (6), (7), (8), and (9) hold: (6)✦ (7)✦ (8)✦ (9)✦ In addition, (10) holds: (10)✦
What Is Checked
The claims are stated over the Steinberg groups (at rank and for integers ), the periodicity predicate on groups, the statements and , and the concrete -algebra determined by the self-simulating machine hierarchy of dilation at threshold height .
For these constructions, the library proves that and that the bit width , packet width, tableau clause count, heights , and data sizes are positive; it also constructs the one-hot tape coding with its left inverse, a combinational NAND circuit realizing , and a concrete self-simulating machine hierarchy of dilation .