The Setting
Several binary choices can be placed in a word of prescribed length. A reconstruction rule receives independent complete deletion traces and may randomize over all candidate words of that length.
A binary word has zero-based positions . For a binary word , a deletion mask is a binary sequence that retains position when ; the retained subsequence is the binary list of those retained bits in their original order. A binary trace is a finite binary list, including its surviving length.✦ The complete trace space and the deletion mask probability at requested deletion rate are given in (1); a bounded trace of bound belongs to this space. (1)
A finite probability law on a finite set is a mass function with and .✦ The deletion mask law has masses .✦ The complete trace law of a binary word of length is the probability law on with masses given in (2). For a source list of length at most , the same law is considered on .✦ The complete trace expectation of a real trace test for a binary source word is its mean under the trace law , given in (2). (2)
For a finite law on , a real function on , and a natural sample count , the expectation is the mean of , and the product law is the probability law of independent samples; their formulas at a sample tuple are given in (3), with samples indexed by the zero-based slots . For a finite law on and laws on a finite set , indexed by , the mixture is a probability law on with masses given by the last formula in (3). The point mass at assigns mass one to and zero elsewhere; for a map and a finite law on , the pushforward is the probability law on obtained by mixing the point masses at with weights . (3)
For finite probability laws on a common finite space, their total variation distance and probability overlap are the real quantities given in (4). The complete trace overlap of two source lists uses their trace laws on the common space with bound equal to the larger source length.✦ (4)
A randomized reconstruction estimator for binary words of length , using traces, is a rule that assigns every trace tuple a probability distribution over .✦ The reconstruction success of a randomized reconstruction estimator on a binary word of length is the probability of reporting , given in (5), where each is a deletion mask of length . For a word length , a requested deletion rate , and a target success probability , a sufficient sample budget for is a natural number for which some randomized reconstruction estimator using traces has success at least on every word of length .✦ (5)✦
Gadget and Exponent Parameters
Write for a working deletion rate. The parametrization , for uses ; the construction theorems call their working rate . An approximate trace simulation of a source list at rate , with error , is a finite law on and a decoder into binary lists satisfying (6) for every trace test valued in . (6)✦
For a finite probability law on , a real function on , and a natural half-order , the squared even moment is the probability-weighted quantity in (7). At a zero-based level , the corresponding even score exponent is . (7)✦
A concrete level pair at rate , scale , allowance , decay exponent , overlap threshold , count multiplier , zero-based level , and half-order consists of distinct equal-length binary lists , finite laws on , and a common decoder giving approximate trace simulations of with the same error . The likelihood score of a concrete level pair with finite laws on is a real function on that, together with the natural repetition count of , satisfies (8), where and is the concatenation of copies of . (8)
For a natural block dimension , the block gain is given in (9); for a natural block dimension and real parameters , that display also defines the warmup block count , induction depth , and final exponent slope . Here is the floor truncated below at zero, and is the natural logarithm. (9) The total score exponent at natural depth is (10), with zero-based block indices . (10)✦
The Claim
Theorem 1. Let be the requested deletion rate.
Let be a concrete level pair as above at a working rate with . For natural satisfying , there is an injective family for which (11) holds for every and natural ; denotes the all-zero choice. (11)✦
Suppose is an injective family whose -sample trace law at every is within in total variation of its law at . If is a sufficient sample budget for , then (12) holds. (12)✦
Let be finite laws on , and let be a probability distribution on for every . Set and . Independent binary recovery satisfies (13). (13)✦
Suppose the real sequences tend to infinity and the sequence is real. Suppose , , and eventually , for a fixed real . Then (14) holds for all sufficiently large . (14)✦
Let be natural and real, with . The score exponent satisfies (15). (15)✦
In the paper, the result reads: choose a fixed number of independent hard gadgets with , construct them at length using the same requested , use stronger separated observations and posterior factorization to multiply optimal successes, and use a strict exponent margin to exclude every budget up to .
What Is Checked
The statements concern finite mask and complete trace laws, concrete level pairs with decoded finite experiments, and arbitrary randomized reporting rules, at natural sample counts and exact word lengths.
For , the mask probabilities in (1) are nonnegative✦; their sum over all masks is one for every real .✦