The Setting
A recursive trace reconstruction construction assigns a target size to each block level, starting from a problem size . The relevant budget is the logarithm of that target size multiplied by the scale slack. Deletion losses depend on the working deletion rate and on the number of block levels.
For a requested deletion probability , each bit survives with probability . The working deletion rate is , and its loss parameter is . The construction theorems call their working rate . Write for the deletion parameter.
Fix an integer block size and a real parameter . The warmup block count and the block dimension at zero-based block index are defined by (1); index corresponds to block number in the paper. (1) For a block dimension , a zero-based scale index , and real slack , the scale exponent is the real number in (2). (2)✦
For a positive real parameter , the induction depth is the floor truncated below at zero, and the scale slack is the reciprocal prescribed in (3). (3) The scale exponent product is the product of the scale-zero exponents over block indices in .✦ The backwards target scale for problem size is the real power defined together with that product in (4). (4) The empty product is . For fixed parameters, abbreviate , and ; along parameter sequences, write , and .
The Claim
Theorem 1. Let be an integer, let , and suppose that and . Every nonnegative integer index satisfies the logarithmic bound (5). (5)✦ If and , the scale margin satisfies (6) for every such . (6)✦
Suppose now that , and fix a nonnegative integer . Let be a real sequence tending to infinity, and let be any positive real sequence such that tends to infinity. For every sequence of nonnegative integer indices, the deletion loss has the limit (7). (7)✦
Let and . For real sequences and , and positive real numbers satisfying for every , the bound (8) holds for all sufficiently large , simultaneously for every nonnegative integer . (8)✦
In the paper, the result reads: for the preceding deletion parameters, with denoting the terminal dimension, and , while dominates , and, for every fixed nonnegative integer , uniformly for , and in the joint asymptotic regime.
What Is Checked
The claims concern the block dimensions and scale exponents in (1) and (2), the deterministic depth and slack in (3), and the backwards target scales in (4), with the stated real parameter bounds and sequences indexed by nonnegative integers.