The Setting
In a periodic source string, tagged slots can appear at different observed ranks after deletion. The quantity of interest is the squared norm of a mixed positional difference of their conditional rank probabilities, summed over increasing observed-rank tuples. For a requested deletion probability , each bit survives with probability ; the working deletion rate is , denoted in the construction theorems. All slot, rank, tag and period indices are zero-based, and .
A finite probability law on a finite set is a real mass function with nonnegative masses summing to one.✦ A fixed-size subset of size of is an -element subset of .✦ For , the uniform fixed-size subset law assigns each such subset the mass in (1); write for these subsets and for this law when . (1)✦
For and , the slot at observed rank is the entry of the increasing enumeration of .✦ Given tagged slots and requested ranks , the tagged rank event is the event in (2), and the conditional subset rank kernel is its probability under . (2)
An increasing rank tuple is a map satisfying (3); all norms here use counting measure on these tuples. (3)✦
For periods of length with offsets , the period defect slot and the tags selected by are given in (4); denotes their periodic rank kernel. (4)
The tuple gap lower and upper bounds of a tuple are the endpoint sequences in (5), and its open tuple gap is their nonnegative difference. For increasing , these gaps count the untagged slots outside and between consecutive tags. (5)
The doubled coarse period gap of an increasing period tuple is the natural integer in (6). (6)✦
A tuple of separated interior tags is a tuple satisfying (7). (7)✦
A positional difference choice is the unchanged operator , the centered first difference , or the centered second difference .✦ Its positional difference coefficients and order are given in (8); coefficient indices correspond to displacements . (8)
For separated interior tags and displacement assignments , the displaced tag tuple and the mixed positional rank difference are defined by (9), with one choice at each tag and total difference order . (9)
The Claim
For and , the length difference smoothing constant is defined in (10); the period rank difference prefactor is the accompanying expression. (10)
Theorem 1. Let be nonnegative integers with , and . Suppose the offsets satisfy for every period and for every pair of periods. Let select separated interior tags , and choose a positional difference at each tag. Suppose satisfies and . Then the periodic rank difference bound is (11): (11)✦
In the paper, the result reads: for , where is the upper cutoff on the number of tags, an admissible central retained count and a tagged tuple in periods with coarse gaps , disjoint with satisfy , with constants depending only on .
What Is Checked
The bound (11) is stated over the uniform fixed-size subset law and its tagged rank events, for separated interior tags selected from periods with the stated offset conditions and a retention parameter satisfying the mean and variance conditions of the theorem. For , the binomial coefficient is positive, and the uniform fixed-size subset law has nonnegative masses summing to one.