Error-correcting codes add redundancy to protect messages from corruption. In the classical setting, the amount of redundancy typically grows with the message length — longer messages need more protection. The growth rate varies by channel model, but the dependency on blocklength is usually present.
Kreindel et al. construct multiset deletion codes with redundancy t + O(1), where t is the number of deletions. The O(1) term is a constant. It does not depend on the blocklength n. A message of length 100 and a message of length 10 million need the same overhead to correct the same number of deletions, up to an additive constant.
The construction uses Sidon sets over finite fields — sets where all pairwise sums are distinct — in both projective and affine forms. The condition is that the number of deletions t must be smaller than the alphabet size q. Within this regime, the blocklength simply does not appear in the redundancy formula.
This means that for sufficiently large alphabets, scaling the message length is essentially free in terms of error protection. The cost of reliability is fixed at purchase — it does not accumulate with use. The constraint shifts from “how long is your message?” to “how large is your alphabet?” — a fundamentally different bottleneck.