The Setting
A randomized machine with a clock moves through its configurations forward in time. Number its configurations so that every transition goes to a larger number, and the transition weights form a substochastic matrix whose positive entries lie strictly above the diagonal. The exact correction and copy hierarchy work with such matrices level by level: at level the scale of the entries of the level’s matrix is the rate , and is corrected by a matrix computed from probed values. What is left of the walk is a residual , a signed combination of , and the product .
The question is whether is again strictly forward and substochastic, how large its entries become, in particular in the columns the probed values mark as good, and how compares with the unsigned terms , and .
Matrices on a Finite Domain
The nodes are the natural numbers, and a finite domain is a finite set of nodes.✦ A real vector assigns a real number to each node , and a matrix of reals assigns a real entry to each pair of nodes . The product over of two matrices of reals and is the ordinary product with the middle index restricted to , (1)✦ and the row weight of at a node over is .✦
Given finite domains and and reals and , a bounded support matrix over with active set , scale and bound is a matrix of reals such that, for all nodes and , (2)✦ we write for the set of these matrices. A step matrix on at rate is a matrix of reals in .✦
The Corrected Iteration
Fix a finite domain , a scale , a real vector and a matrix of reals , with products taken over . The entrywise correction at scale with weights is the operation that adjusts each entry of a matrix at scale according to the weights . The corrected iteration of at scale with weights is the sequence of matrices in which is the zero matrix and is the entrywise correction of .✦ The residual of and is (3)✦ A column is good when .
The cutoff scale is .✦ An iteration count is admissible when it is positive and (4)✦
Stages
Parameter constants are four natural numbers: an admissible iteration count , a parameter , a number of copies and a parameter , subject to (5)✦ where ✦ and is the map .✦ A stage consists of parameter constants, a level , a finite domain of nodes and a matrix of reals of transition weights✦; its rate is , the retention rate of level .✦
Let be a prime, the field size of the stage’s channels, which are taken over the group . A pilot pair consists of a real vector of probed values and a matrix of reals , the correction.✦ The pilot sequence of a stage starts from the zero vector and the zero matrix, and each of its terms is obtained from the one before by the update of , a map from pilot pairs to pilot pairs; the probed vector after rounds is the vector of its term of index .✦
The cutoff is assembled from the clamp to , the smooth fade function and the smooth rising ramp from to : (6) The cutoff function is ; it equals for and vanishes for .✦
The stage correction after steps, , is the term of the corrected iteration of on at scale with weights , the cutoff of the probed values after rounds.✦ The corrected residual of the stage is the residual of and : (7)✦
The Claim
Theorem 1. Let be a finite domain, a real number, a real vector with values in and a matrix of reals, and let and be the corrected iteration and its residual (3). If for a finite domain , then for every natural number (8)✦ If is a step matrix on at rate , then for every natural number and all nodes and (9)✦ and if moreover is admissible and is a good column, then for every node (10)✦ For a stage with domain , matrix , rate and iteration count , for every field size and every finite domain with , the corrected residual (7) satisfies (11)✦
In the paper, the result reads: with , and , the residual is nonnegative, strictly forward and substochastic, , implies , , every unsigned term of the paper’s level- matrices and is bounded by the input, and and , where and are the paper’s operators on matrices (not the iteration count ), the paper’s is the page’s , and , and is the paper’s parameter occurring in .
What Is Checked
The claim is stated over finite domains of natural-number nodes, matrices of reals with their products and row weights over a domain, bounded support and step matrices, the corrected iteration and its residual, the cutoff scale and the admissible iteration counts, and, in (11), stages with their parameter constants, rate , pilot sequence and probed vectors, the cutoff built from the clamp, the fade function and the rising ramp, and the stage correction. The library also states that, when is a bounded support matrix over with active set at a positive scale and the weights take values in , every term of the corrected iteration is substochastic.