跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20980 · v1

Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss

首次提交 2026-11-16 20:14
版本更新 2026-11-16 20:14
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

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

作者备注:45 pages. Lean 4 formalisation: https://github.com/matthiasGmayer-research/copying-vs-interleaving-lean

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 20:14 · 最新观测版本

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

查看此版本解读 →查看此版本原文 ↗