The Setting
The exact correction works on a matrix of transition weights between vertices, at a level of the copy hierarchy, a hierarchy of levels in which level has retention rate . A column of such a matrix is overloaded when too many of its rows carry a large entry, large meaning a fixed multiple of . The library tests a column for overload with a randomized detector over , for a prime . The question is what the detector’s value says about the number of rows at with a large entry, and what a positive multiplier of the correction, defined below for a stage, says about that number.
Channels, Boxes and Retained Vertices
Let .✦ A rank channel over is a pair of a nonzero vector , its direction, and a vector , its offset✦; its point at a residue modulo is ✦.
The box side length at level is ✦, and the box of level is the set of vectors of whose four coordinates have least nonnegative representatives below .✦ The hit probability is the probability that a uniformly random vector of lies in .✦
A finite set of natural numbers, the vertices, is legal for when ; a vertex is read as a residue modulo .✦ For a channel , the retained vertices of at level are those whose point on lies in the box: (1)✦
Averages are plain means: is the mean over all rank channels .✦ A padded channel of level is a pair of a nonzero direction and a short offset , whose widening has as coordinates the least nonnegative representatives of those of .✦ For a column , the conditional average of a real function of channels is the mean of over the padded channels of level .✦
Heavy Rows and the Detector
The constants are ✦, ✦ and ✦. For a real matrix on the vertices, the heavy rows and the light rows of at a column are (2) and the overload threshold of a natural number is .✦ The column is overloaded when .
Let be the clamp of a real number to .✦ The fade function and the ramp from to are (3) The light ramp is ✦, and the gate is .✦
The padded rank at depth of a real function on a finite set is its -st largest value, padded with : (4)✦
Fix natural numbers and . The panel rank of a row under a channel is ✦, and the throttle of the row is .✦ The mark of the entry under , and the score of the column under a pair of channels and , are (5)
The detector at a column is the mean score over a uniformly random channel and a channel conditioned on its point at lying in : (6)✦ It depends also on , , , and .
Stages and Their Matrices
For finite sets and of vertices and reals and , a matrix is a bounded support matrix on with active set , rate and bound when for all and , every row weight is at most , and only for and in with .✦ A stochastic step matrix on at rate is a bounded support matrix on with active set , rate and bound .✦
An iteration count is admissible when and .✦ Parameter constants are natural numbers , , and , with an admissible iteration count, , a number of copies , and .✦ A stage consists of parameter constants, a level , a finite set of vertices and a matrix of transition weights✦; its rate is the rate of the level.
For matrices and on , the combined matrix of and is , where the product is taken over : .✦
The pilot pairs of a stage, each a real vector and a matrix, start from the zero vector and the zero matrix and are advanced step by step by the update rule of the stage; is the probed vector of step .✦ With the cutoff ✦, the pilot multiplier of step at a vertex is , and the actual multiplier is . The correction matrices start from , and is the entrywise correction at scale of the combined matrix with weights . The test matrix and the next matrix of step are (7)
The Claim
Theorem 1. Let be a prime, a finite set of vertices, a real matrix, a level with rate , and natural numbers, and a column. Suppose that is legal for , that and , and that is a bounded support matrix on , with some active set, at rate and with bound . If and the column is overloaded, then (8)✦ Without any of these hypotheses, (9)✦ Now let a stage have constants , , , , level , a legal set with , and a stochastic step matrix on at rate , and let and . If the pilot multiplier is positive, then (10)✦ and if the actual multiplier is positive, then (11)✦
In the paper, the result reads: with , and , if more than rows have then , if then more than rows have , and a positive pilot or actual multiplier at leaves at most rows with , respectively with , where stands for the paper’s ; , and are its detector and matrices; and are its two thresholds; is its row bound and the quantity defined above; and , , , and are its constants.
What Is Checked
The four statements (8), (9), (10) and (11) are stated over the detector (6), built from rank channels over , the retained vertices, padded ranks, marks and scores; over the heavy and light rows (2) of a column; over bounded support and stochastic step matrices; and over the test and next matrices (7) of a stage with its pilot and actual multipliers.