← All papers
First page of Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

Matthias G. Mayer

cs.DS Nov 16, 2026 · v1 cs.FL
All numbered definitions, statements and proof steps on ARC versus zipline program size bounds are formalised in Lean 4 with Mathlib, written by AI agents.
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)$.

Kosoy showed that the smallest arithmetic repetition system for a word, ARC(x), is at most O(n^{1/3}) times the smallest zipline program, ZLC(x). She asked whether this factor is tight. A polylogarithmic factor would give a polynomial-time next-letter predictor with ZLC(x)·polylog(n) mistakes.

The authors prove an upper bound ARC(x) ≤ 2n^{1/4} ZLC(x) and build binary words that give a matching lower bound. Every numbered definition, statement and proof step is formalised in Lean 4 with Mathlib, using only the standard axioms. Cited results not formalised are taken as hypotheses. AI agents (Claude, Codex) found the constructions and proofs and wrote the formalisation, with cross-model review and author oversight.

The optimal exponent is 1/4, not 1/3. ARC(x) ≤ 2n^{1/4} ZLC(x) holds for every word, and at every large enough length some binary word has ARC(x) ≥ n^{1/4−o(1)} ZLC(x). The technical development is machine-checked in Lean.