The Setting
The copy hierarchy carries the acceptance probability of a randomized logspace machine through a sequence of stages. A stage is a weighted graph on a finite set of nodes, read as one step of a random walk whose moves only climb; passing to the next stage replaces every node by a fixed number of copies, one of them primary, and shares the transitions of the walk out among them. Rewards are paid at the nodes, and a reward identity ties them to the probability.
The item asks whether the reward identity survives the passage to the next stage, and how far, after passages, the reward at the copy that was primary at every passage falls below the probability at the node it descends from. On the way it bounds the number of nodes still active.
Stages
Vectors and matrices are indexed by the natural numbers: a real vector assigns a real number to each natural number ✦, and a matrix of reals assigns a real number to each pair .✦ A finite domain is a finite set of natural numbers, its nodes.✦ Products over of a matrix with a matrix or a vector , and the row weight of at a row , sum over the nodes of : (1)
Given finite domains and and reals and , a matrix is a bounded support matrix when for all and , for every , and only when and lie in the active set and .✦ A stochastic step matrix on at rate is a bounded support matrix with and .✦
The parameter constants are four natural numbers , an iteration count , two parameters and , and a number of copies, subject to (2)✦ where is the cutoff scale, and ; an iteration count is admissible when it meets the first two conditions.✦
A stage consists of parameter constants , a level , a finite domain of nodes and a matrix of transition weights.✦ The rate of level is ✦, and it is the stage rate of .✦
The Copy Step
The copy step uses smooth ramps built from the clamp , the point of nearest to a real number . The fade function is (3)✦ a continuously differentiable ramp that vanishes for , equals on and on , and equals for . The smooth rising ramp from to is .✦ The boost function is ✦, the cutoff function is ✦, and the slice function is , which vanishes up to its lower threshold and equals from its upper threshold on.✦
A pilot pair is a real vector of probed values together with a matrix of corrections.✦ The pilot sequence of a stage is the sequence of pilot pairs that starts from the zero vector and the zero matrix and whose term of index is obtained from its term of index by the update of , a map on pilot pairs that depends on , the prime field size of the channels over .✦ The probed vector after rounds is the vector of the term of index .✦
For a finite domain , a scale , a real vector and a matrix , the corrected iteration of is the sequence of matrices with and obtained from the combined matrix by the entrywise correction, the operation on matrices that adjusts each entry at scale with weights .✦ The stage correction matrix of a stage is the term of index in the corrected iteration of its matrix on at its rate , with weights the cutoffs of the probed values after rounds.✦ The residual of against a matrix over is ✦, and the corrected residual of is the residual of against .✦
With copies per node, copy of a node is the radix index , the copy being primary, and every natural number is copy of .✦ The copy zone of is the set .✦ The boost factor of copy of is for the primary copy and for .✦ The share of copy at a ratio is for the primary copy and for , so that the shares sum to .✦
The next stage of is ✦, whose matrix is the next stage matrix (4)✦
The projection to copies of a real vector is the vector with (5)✦
Prize Triples
A prize triple consists of a stage , a real vector of rewards paid at the nodes, and a real vector standing for the true acceptance probability transported to the nodes.✦ With and stage rate , the triple is correct when is a stochastic step matrix on at rate , , lies in for every , and the reward identity holds: (6)✦
The prize step at field size takes to , where (7)✦ The iterates of the prize step at field size starting from are and , written , with and the domain and matrix of . The all-primary copy of a node after steps is , given by and , the primary copy of .✦
The active nodes of a matrix on a finite domain form the set of the for which some has or .✦
The Claim
Theorem 1. Let be a prize triple whose stage has level and domain , let be the field size, and let and be natural numbers. Then (8)✦ If is correct, then (9)✦ and (10)✦ If is correct and , then (11)✦ and (12)✦
In the paper, the result reads: for every stage , , the reward satisfies and , , and at the all-primary copy of a base vertex , , where the paper’s , , and stand for the page’s , , and the domain of the first stage.
What Is Checked
The claim is stated over prize triples on the stages of the copy hierarchy at field size , their correctness, the prize step with its projection and correction matrix , its iterates , the all-primary copy and the active nodes , with the rate in the bound.