Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

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 $\mathrm{ARC}(x)$ of an arithmetic repetition system for a word $x$ of length $n$ is at most a factor $O(n^{1/3})$ larger than the least size $\mathrm{ZLC}(x)$ of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes $O(\mathrm{ARC}(x)\log n)$ mistakes, so a polylogarithmic factor would bound its mistakes by $\mathrm{ZLC}(x)\,\mathrm{polylog}(n)$, which no known polynomial-time predictor achieves. We show that the optimal exponent is $1/4$, not $1/3$: $\mathrm{ARC}(x) \le 2n^{1/4}\,\mathrm{ZLC}(x)$ for every word $x$, and at every large enough length $n$ some binary word has $\mathrm{ARC}(x) \ge n^{1/4-o(1)}\,\mathrm{ZLC}(x)$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.20980
Primary Topic
Algorithms and Data Compression
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

Matthias Georg Mayer
arXiv (Cornell University)
Algorithms and Data Compression
preprint

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

Matthias Georg Mayer
preprint en

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 $\mathrm{ARC}(x)$ of an arithmetic repetition system for a word $x$ of length $n$ is at most a factor $O(n^{1/3})$ larger than the least size $\mathrm{ZLC}(x)$ of a zipline program for it, and asked whether this factor is tight. Her polynomial-time next-letter predictor makes $O(\mathrm{ARC}(x)\log n)$ mistakes, so a polylogarithmic factor would bound its mistakes by $\mathrm{ZLC}(x)\,\mathrm{polylog}(n)$, which no known polynomial-time predictor achieves. We show that the optimal exponent is $1/4$, not $1/3$: $\mathrm{ARC}(x) \le 2n^{1/4}\,\mathrm{ZLC}(x)$ for every word $x$, and at every large enough length $n$ some binary word has $\mathrm{ARC}(x) \ge n^{1/4-o(1)}\,\mathrm{ZLC}(x)$.

arXiv (Cornell University)
Algorithms and Data Compression
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon