The Setting
Let be a commutative ring, a -algebra, and a finite alphabet mapped into . To test eventual vanishing in with matrix coefficients over , one sums matrix-weighted products over all -letter words in , or sums over sequences from a finite chunk alphabet labeled by nonempty words over of length at most whose concatenated labels have length . How can any such chunk test of matrix dimension at most and label bound be realized as a fixed block of a letter test over of controlled dimension, so that eventual vanishing of letter tests forces eventual vanishing of chunk tests?
Matrix Tests and Rewriting Algebras
For an alphabet , the free monoid of words over consists of all finite sequences of letters in under concatenation, with empty word .✦ Given an alphabet , a monoid or ring , and a map , the evaluation of a word of length is in .✦ When is finite and , the set of candidate words up to length is the finite set of all words over of length at most .✦ Over a ring , for a finite alphabet , a map , and , the abstract letter sum of length is (1): (1)✦ For a finite chunk alphabet , a ring , a length function , a weight map , and , with denoting the -th letter of a word , the abstract chunk sum of target length is (2): (2)
Given a finite index set , a ring , and a -algebra , the tensor product of a matrix and an element is the matrix over whose -entry is for all .✦ For finite sets and , a ring , a -algebra , a weight , a map , and , the matrix letter sum is the abstract letter sum of length for .✦ For finite sets and , a ring , and a -algebra , a letter test of dimension over is a pair of a weight and a map . When and are finite, is an alphabet, is a ring, is a -algebra, , , , and , the matrix chunk sum is the abstract chunk sum of target length for the length function and weight . For finite sets and , an alphabet , a ring , and a -algebra , and , a chunk test of dimension and label bound over is a triple of a label map sending each chunk to a nonempty word of length at most , a weight , and a map .
For a semiring and an alphabet , the monoid algebra of words is the monoid algebra of over ✦, in which each word has basis monomial with coefficient at .✦ A word rewriting table over an alphabet consists of a binary replacement relation on and a subset of zero words.✦ Given a ring and a word rewriting table over , the defining two-sided ideal is the two-sided ideal generated by the defining relations of , namely the differences for and the monomials for ; the algebra of the rewriting table over is the quotient algebra , with quotient homomorphism mapping each to the word element .
For , the alphabet of raw bitstrings consists of Boolean vectors of length .✦ A verification clause schedule of capacity assigns to each verification task (an arity below and a zero-task flag) a positive clause count at most and a family of clauses indexed below on three cell memory addresses.✦ Given , a schedule of capacity , and a data size , the algebra table is the word rewriting table over whose replacement relation and zero words encode local cell transitions and invalid patterns; for a ring , each yields a raw letter generator in the algebra of over .✦
For a dilation factor , a self-simulating machine hierarchy consists of a Boolean program and a threshold such that at every height the parameter bounds for the self-specialized code of the program hold and satisfiability of the verification tableau at height matches the rewriting-table membership condition at height with data size .✦ At any height , the hierarchy produces a verification clause schedule of capacity , a rewriting table over , the machine hierarchy algebra defined as the algebra of over a ring , and, when is commutative, the letter map sending each to its raw letter generator in .
A sequence of matrices is eventually vanishing if there exists such that for all . For a self-simulating machine hierarchy , a commutative ring , a height at least the threshold of , and , the algebra satisfies letter vanishing in dimension if eventually vanishes for every letter test over of dimension at most .✦ Given a self-simulating machine hierarchy , a commutative ring , a height at least the threshold of , and , the algebra satisfies chunk vanishing in dimension and label bound when eventually vanishes for every chunk test over of dimension at most and label bound .✦
The Matrix Automaton
For an alphabet and , the automaton state space is the set of all words over of length strictly less than ✦. When , the root state of the automaton state space is the empty word .✦ Given an alphabet , , a ring , a weight , and a letter , with Kronecker delta equal to when and otherwise, and denoting the concatenation of and , the automaton transition matrix indexed by over has entries (3): (3) When and are finite, , is a ring, , and , the block transition matrix indexed by over has -entry for all and , giving a matrix weight .
Given an alphabet and a word , the collection of partitions of is the finite list of all decompositions of into nonempty contiguous subwords satisfying , with consisting solely of the empty decomposition.✦ For a finite alphabet , an alphabet , a ring , a label map , and a weight , the combined weight is defined for each by (4): (4)✦ For an alphabet and , the set of bounded sequences of length at most over is the set of all finite sequences of elements of with ; for an alphabet , a label map , a ring , and a weight , the spelled word of is , and its sequence weight is . When is finite, is an alphabet, is a ring, , and , the word coefficient of any word is given by (5): (5)✦
The Claim
Theorem 1. For any nonempty finite alphabet and , the automaton state space satisfies (6): (6)✦ Given , a finite alphabet , a finite index set , a ring , and a matrix weight such that whenever , every word and all satisfy (7): (7)✦ Suppose , and are finite alphabets, is a finite index set, is a ring, sends every chunk to a nonempty word of length at most , and . Then every word and all satisfy (8): (8)✦ When , and are finite alphabets, is a finite index set, is a ring, is a -algebra, sends every chunk to a nonempty word of length at most , , and , every and satisfy (9): (9)✦ Let be a self-simulating machine hierarchy, a commutative ring, a height at least the threshold of , and with . Suppose satisfies letter vanishing in dimension ; then for every chunk test over of dimension at most and label bound , there exists such that (10) holds: (10)✦
In the paper, the result reads: for a chunk test of dimension and label bound over a nonempty finite alphabet of size , there is a letter test of dimension at most () whose length- sum has the chunk sum as one fixed block for every ; consequently eventual vanishing of all letter tests in that dimension implies eventual vanishing of the chunk test. The library splits this statement into the state-space bound (6), the block identities (7), (8), and (9) over arbitrary finite alphabets and rings, and the transfer from letter vanishing to chunk vanishing (10) in .
What Is Checked
The automaton bound and block identities are stated over the state space , root state , transition and block transition matrices and , partitions , combined weights , word coefficients over bounded sequences, and matrix letter and chunk sums and for finite alphabets (nonempty for the state bound) and , a finite index set , rings and , and a -algebra ; the vanishing implication is stated over a self-simulating machine hierarchy , a commutative ring , a height at least the threshold of , the rewriting-table algebra over the raw bitstrings with letter map , and the letter and chunk vanishing predicates. Beyond the claim, at every height at least the threshold of a self-simulating machine hierarchy with dilation factor , and the data block size are positive.