WorksComputer Science
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
Abstract
Two classical ways to compress a word are straight-line programs (SLPs), which build it by concatenating smaller pieces, and the Lempel-Ziv 77 (LZ77) factorisation, which copies earlier parts of it; their sizes are measures of repetitiveness. LZ77 approximates the smallest SLP efficiently: it has no more factors than a smallest SLP has size, and yields an SLP at most a logarithmic factor larger in near-linear time. Motivated by online prediction, Kosoy introduced zipline programs, which are analogous to SLPs but interleave their pieces round-robin instead of concatenating them. Her generalisation of LZ77, the arithmetic repetition system, describes a word by copies from one arithmetic progression of positions to a later one. Do arithmetic repetition systems approximate the smallest zipline program as well? Kosoy proved that the least size of an arithmetic repetition system for a word of length is at most a factor larger than the least size of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes mistakes, so a polylogarithmic factor would bound its mistakes by , which no known polynomial-time predictor achieves. We show that the optimal exponent is , not : for every word , and at every large enough length some binary word has .