YOI 751：縮む列があれば伸びる列があり、圧縮の余地を作るのは列ではなく源の偏りである

論文751 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/751 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23015140）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi751,
  author = {Yamagishi, Yuuki},
  title = {If Some Strings Shrink, Others Must Grow, and What Makes Room for Compression Is Not the String but the Bias of the Source},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/751},
  doi = {10.5281/zenodo.23015140},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

圧縮器はたいていのファイルを縮める。けれど、どんな列でも縮める可逆な圧縮器は作れない。縮められない理由と、それでも縮む理由を、数え上げとエントロピーで分ける。新しい定理も法則も主張しない。

第一に、短い列は、いつも $1$ 通り足りない。$32$ ビットの列 $4294967296$ 通りに対し、短い列は $4294967295$ 通り（第2節）。

第二に、だから縮まない列が必ず在る。縮む列があれば、どこかで伸びる列がある（第2節）。

第三に、これが本稿の芯である。すべての列を平等に並べると、大きく縮む列はわずかしか無い。$20$ ビットの列で $1$ バイト縮められるのは、すべての列の $\mathbf{0.007812}$ 未満（第2節）。

第四に、縮める割合は、縮める量に対して指数で落ちる。$k$ ビット縮む割合は $2^{1-k}$ を超えない（第2節）。

第五に、それでも縮むのは、源が偏っているからである。$1$ の出る確率 $0.90$ で $\mathbf{0.468996}$、$0.99$ で $\mathbf{0.080793}$ ビット／記号（第3節）。

第六に、分離子は、相手にしているのが、あり得るすべての列を平等に並べた集まりか、偏った源が出す列かである。「よく縮む」は、どの列の集まりを相手にしているかを言うまで意味が決まらない（第4節）。

キーワード：可逆圧縮、鳩の巣原理、数え上げ、圧縮の限界、エントロピー、源の偏り

Abstract

Compressors shrink most files. Yet no lossless compressor can shrink every string.Why strings cannot be shrunk, and why they still shrink, are separated by counting and by entropy.No new theorem or law is claimed.

First, shorter strings are always one too few、against $4294967296$ strings of $32$ bits there are $4294967295$ shorter ones (Section 2).

Second, so an unshrinkable string always exists、if some strings shrink, others must grow (Section 2).

Third, and this is the core. Taking all strings equally, few can shrink much、among $20$-bit strings, those shrinkable by a byte are below $\mathbf{0.007812}$ of all (Section 2).

Fourth, the share falls exponentially with the amount saved、the share shrinkable by $k$ bits never exceeds $2^{1-k}$ (Section 2).

Fifth, compression still works because the source is biased、$\mathbf{0.468996}$ bits per symbol at probability $0.90$, $\mathbf{0.080793}$ at $0.99$ (Section 3).

Sixth, the separator is whether one faces the set of all possible strings taken equally or the strings a biased source emits、“compresses well” has no fixed meaning until one says which set of strings is faced (Section 4).

Keywords: lossless compression, pigeonhole principle, counting argument, limits of compression, entropy, bias of the source

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/751/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/751 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ