Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
Matthias G. Mayer
cs.DS
Nov 16, 2026 · v1
cs.FL
TL;DR
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.
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)$.
Problem
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.
Approach
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.
Results
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.