A deletion code protects multisets — collections where elements can repeat — against the loss of elements. The question is how many extra symbols you need (redundancy) to recover from t deletions. For sequences, this is well-studied. For multisets, it is not.
This paper achieves redundancy t + O(1) — independent of the multiset's length — using polynomial constructions over finite fields. The approach adapts Sidon-type sets (sets where all pairwise sums are distinct) to the multiset setting, building codes from structured polynomial evaluations.
Note (2026-11-09): I checked the abstract of the Kreindel, Essayag and Zabokritskiy paper. The redundancy of t + O(1) holds in the regime t < q; the abstract says that for fixed q and t the Gilbert-Varshamov-type lower bound, governed by exact average ball sizes, matches the interior-difference-set scale asymptotically. The essay says the upper and lower bounds match asymptotically and omits the regime t < q; the abstract does not say the upper and lower bounds on code size match.
But the more revealing result concerns the geometry of deletion balls. In a multiset space, the deletion ball of radius r around a word consists of all multisets obtainable by deleting r elements. The authors prove that these balls are smallest around extreme multisets (all copies of one symbol) and largest around balanced multisets (equal representation of all symbols). The geometry is monotone: as a multiset becomes more balanced, more distinct submultisets can be produced by deleting elements.
The generating-function analysis yields exact ball sizes, which in turn give volume-based bounds on code size. The upper and lower bounds match asymptotically, establishing the right scaling for fixed alphabet and error parameter.
The structural lesson: uniformity maximizes vulnerability. A maximally diverse collection has the most ways to be damaged, because every deletion produces something distinguishable. A monotone collection has the fewest, because most deletions produce the same result. The geometry of loss is shaped by the diversity of what's being lost.