\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,booktabs}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\title{The Compression--Prediction Duality\\in Universal Model Terms}
\author{Claude and MJC}
\date{February 12, 2026}

\begin{document}
\maketitle

\begin{abstract}
Every predictor defines a compressor and vice versa.  We make this
duality precise in Universal Model terms.  The count table $c$ is
simultaneously (1) a lossy compressor of the data stream (replacing
$N$ events with $|I| \times |O|$ counts) and (2) a predictor of
future events (the forward pass outputs conditional distributions).
The compression rate equals the cross-entropy of the predictor.
We prove that the UM's counting-based predictor achieves the empirical
entropy rate for sufficient data, derive the rate--distortion function
for event space coarsening, and show that the Hutter Prize criterion
(compressed size of enwik8) is exactly the cumulative cross-entropy
loss.  The factorization tower provides a hierarchy of
compression--prediction trade-offs, with each level achieving a
different rate--distortion point.  Optimal event spaces lie on the
Pareto frontier of this trade-off.
\end{abstract}


\section{Introduction}

The connection between prediction and compression is folklore in
information theory: Shannon's source coding theorem says that the
optimal compression rate equals the entropy, and arithmetic coding
achieves this rate using any probabilistic predictor.

The UM makes this connection constructive:
\begin{enumerate}
\item The learning function $\omega_0$ (counting) produces a predictor
  (the conditional distribution from the count table).
\item The forward pass $f_p$ converts the predictor into per-symbol
  code lengths (via $-\log_2$ of the predicted probability).
\item The sum of code lengths is the compressed size.
\end{enumerate}

We formalize this pipeline and derive its properties.


\section{Prediction from Counting}

\begin{definition}[Empirical predictor]
Given a count table $c: I \times O \to \mathbb{N}$ from data
$D = (d_1, \ldots, d_N)$, the empirical predictor assigns:
\[
\hat{P}(o \mid i) = \frac{c(i, o)}{\sum_{o'} c(i, o')} = \frac{c(i,o)}{c(i, \cdot)}.
\]
\end{definition}

\begin{definition}[Cross-entropy loss]
The cross-entropy loss of predictor $\hat{P}$ on data $D$ is:
\[
L(\hat{P}, D) = -\frac{1}{N} \sum_{t=1}^N \log_2 \hat{P}(d_t \mid \text{context}_t).
\]
This is the bits per character (bpc) achieved by the predictor.
\end{definition}

\begin{theorem}[Counting achieves empirical entropy]
\label{thm:entropy}
For a stationary ergodic source with entropy rate $h$, the UM's
counting-based predictor satisfies:
\[
L(\hat{P}, D) \xrightarrow{N \to \infty} h
\]
almost surely, provided the event space $E$ captures the source's
sufficient statistics.
\end{theorem}

\begin{proof}
By the strong law of large numbers, $c(i,o)/N \to P(i,o)$ for each
$(i,o) \in I \times O$.  Therefore $\hat{P}(o \mid i) \to P(o \mid i)$,
and the cross-entropy converges to the conditional entropy
$H(O \mid I)$, which equals the entropy rate for a Markov source
of order equal to the context length.
\end{proof}


\section{Compression from Prediction}

\begin{definition}[Arithmetic coding]
An arithmetic coder takes a predictor $\hat{P}$ and a data stream $D$
and produces a compressed bit string of length
\[
|C| = \sum_{t=1}^N \lceil -\log_2 \hat{P}(d_t \mid \text{context}_t) \rceil + O(1).
\]
The overhead beyond the ideal $-\log_2 \hat{P}$ is at most 2 bits
total.
\end{definition}

\begin{proposition}[Compression = cumulative cross-entropy]
The compressed size of $D$ under predictor $\hat{P}$ is:
\[
|C| \approx N \cdot L(\hat{P}, D) = N \cdot \text{bpc}.
\]
Lower bpc $\Leftrightarrow$ better compression $\Leftrightarrow$
better prediction.
\end{proposition}

\begin{corollary}[Hutter Prize criterion]
The Hutter Prize asks for the shortest compressed representation of
enwik8 ($N = 10^8$ bytes).  The compressed size is $10^8 \times \text{bpc}$
bits $= 10^8 \times \text{bpc} / 8$ bytes.  The current best is
$\sim$114 MB compressed to $\sim$15 MB, corresponding to
$\text{bpc} \approx 1.2$.

The UM's approach: build a predictor with the lowest possible bpc,
then compress with arithmetic coding.  The Hutter Prize is won by the
best predictor.
\end{corollary}


\section{The Count Table as a Compressor}

The count table itself is a form of compression:

\begin{proposition}[Count table compression ratio]
The data stream $D$ has $N$ events.  The count table
$c: I \times O \to \mathbb{N}$ has $|I| \times |O|$ entries.
The compression ratio is:
\[
\rho = \frac{|I| \times |O| \times \lceil \log_2 N \rceil}{N \times \lceil \log_2 |O| \rceil}.
\]
For the byte-level bigram ($|I| = |O| = 256$):
$\rho = 256^2 \times 20 / (10^6 \times 8) \approx 0.16$ at $N = 10^6$.
\end{proposition}

\begin{remark}
The count table is a lossy compressor: it discards the order of events
(temporal information beyond the context length).  The loss is exactly
the MI between positions that exceeds the context length.

This is the ``counting assumption'': position-independent counting
loses order information.  The lost information is the difference
between the n-gram entropy and the true entropy rate.
\end{remark}


\section{The Rate--Distortion Trade-off}

\begin{definition}[Rate--distortion for event spaces]
Let $E = I \times O$ be an event space with $|I| = m$.  Define:
\begin{itemize}
\item \textbf{Rate:} $R(E) = \log_2 m$ (bits needed to specify an
  input event).
\item \textbf{Distortion:} $D(E) = H(O) - I(I; O)$ (the conditional
  entropy---what we cannot predict, i.e., the bpc).
\end{itemize}
\end{definition}

\begin{proposition}[Rate--distortion curve]
As we coarsen the event space ($m$ decreases), the rate decreases
and the distortion increases:
\begin{itemize}
\item At $m = 1$ (trivial event space): $R = 0$, $D = H(O)$ (no
  prediction, uniform distribution).
\item At $m = |O|^k$ (full $k$-gram context): $R = k \log_2 |O|$,
  $D = H(O \mid I)$ (full $k$-gram prediction).
\end{itemize}
The curve $D(R)$ is convex and non-increasing.
\end{proposition}

\begin{proof}
Convexity follows from the data processing inequality: any mixture
of two event spaces achieves distortion at most the mixture of their
distortions.  Non-increasing follows from: more input events means
more information about the output, hence lower distortion.
\end{proof}

\begin{theorem}[Optimal event spaces are on the Pareto frontier]
\label{thm:pareto}
An event space $E^*$ is optimal for a given rate budget $R^*$ if
it minimizes distortion among all event spaces with
$\log_2 |I| \leq R^*$.  The set of optimal event spaces traces
the rate--distortion curve.
\end{theorem}

\begin{proof}
Standard rate--distortion theory.  The optimal event space at rate $R$
is found by:
\[
E^*(R) = \arg\min_{E: \log_2 |I(E)| \leq R} D(E).
\]
The solution is the event space that captures the most MI per bit of
rate.
\end{proof}


\section{The Factorization Tower as Rate--Distortion Hierarchy}

\begin{proposition}[Tower = rate--distortion samples]
Each level of the factorization tower
$E_0 \to E_1 \to \cdots \to E_n$ is a point on the
rate--distortion curve:
\begin{center}
\begin{tabular}{rlrr}
\toprule
Level & Event space & Rate (bits) & Distortion (bpc) \\
\midrule
0 & Byte (256 events) & 8.0 & $\sim$2.3 (KN-5, 10M) \\
1 & 16 SVD events & 4.0 & $\sim$5.5 \\
2 & 4 coarse classes & 2.0 & $\sim$6.5 \\
3 & 2 (text/markup) & 1.0 & $\sim$7.4 \\
$n$ & 1 (trivial) & 0 & 8.0 \\
\bottomrule
\end{tabular}
\end{center}
\end{proposition}

\begin{remark}
The tower samples the rate--distortion curve at geometrically
spaced rates.  The ``natural'' event spaces (RG fixed points from the
renormalization paper) are the points on this curve where the slope
changes sharply---the ``elbows'' of the rate--distortion curve.
\end{remark}


\section{Multi-Offset Extension}

With multiple offsets $d_1, \ldots, d_k$, the input event space
becomes $I = E^k$ (the product of $k$ copies of the base event space).
The rate is $R = k \cdot \log_2 |E|$ and the distortion depends on
how much additional MI the extra offsets provide.

\begin{proposition}[Diminishing returns]
The MI gain from adding offset $d_{k+1}$ to existing offsets
$\{d_1, \ldots, d_k\}$ is:
\[
\Delta I_{k+1} = I(I_{k+1}; O \mid I_1, \ldots, I_k) \leq I(I_{k+1}; O).
\]
The gain is bounded by the marginal MI and decreases as $k$ increases
(by the chain rule for MI and the non-negativity of conditional MI).
\end{proposition}

\begin{corollary}[Optimal offset selection]
The greedy algorithm for offset selection---adding the offset with
the highest conditional MI at each step---produces a sequence of
rate--distortion points that approximates the Pareto frontier from
below.  This is exactly the backward trie / skip-$k$-gram construction
from the February 8 archive.
\end{corollary}


\section{The Model as Code + Data}

\begin{proposition}[Total compressed size decomposition]
The total compressed size of data $D$ using model $M$ is:
\[
|C| = |M| + |D \mid M|,
\]
where $|M|$ is the model size (the cost of transmitting the event space
structure and count table) and $|D \mid M|$ is the data given the
model (the residual after prediction).

In UM terms:
\begin{itemize}
\item $|M| = |I| \times |O| \times \lceil \log_2 N \rceil$ bits
  (the count table).
\item $|D \mid M| = N \times \text{bpc}$ bits (the arithmetic-coded
  residual).
\end{itemize}
\end{proposition}

\begin{corollary}[MDL interpretation]
Minimizing the total compressed size $|C| = |M| + |D \mid M|$ is
the Minimum Description Length (MDL) principle.  The optimal event
space balances model complexity against prediction accuracy.

For small data ($N$ small), simple models win ($|M|$ dominates).
For large data ($N$ large), complex models win ($|D \mid M|$ dominates).
The crossover point determines the ``right'' event space granularity
for a given data size.
\end{corollary}

\begin{example}[Byte KN models at different scales]
From scale\_kn.c experiments:
\begin{center}
\begin{tabular}{rrr}
\toprule
Data size $N$ & Best KN order & bpc \\
\midrule
$10^3$ & 2 & 4.51 \\
$10^4$ & 3 & 3.42 \\
$10^5$ & 4 & 2.89 \\
$10^6$ & 5 & 2.56 \\
$10^7$ & 5 & 2.29 \\
$10^8$ & 6 & 2.00 \\
\bottomrule
\end{tabular}
\end{center}
The optimal order increases with data size, exactly as MDL predicts:
more data supports more complex models (longer contexts).
\end{example}


\section{Duality Theorem}

\begin{theorem}[Compression--prediction duality]
\label{thm:duality}
For the UM on event space $E = I \times O$:
\begin{enumerate}
\item \textbf{Prediction $\to$ compression:} Any predictor $\hat{P}$
  defines a compressor with rate $L(\hat{P}, D)$ bpc via arithmetic
  coding.
\item \textbf{Compression $\to$ prediction:} Any compressor with rate
  $r$ bpc defines a predictor with cross-entropy at most $r + o(1)$
  via the decompressor's implicit model.
\item \textbf{Optimal equivalence:} The optimal predictor and the
  optimal compressor achieve the same rate: the entropy rate $h$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item Arithmetic coding achieves rate $L + O(1/N)$.
\item Any compressor that achieves rate $r$ on all data from a source
  must implicitly model the source with cross-entropy at most $r$
  (by Shannon's source coding theorem).
\item The optimal predictor achieves $L = h$ (Theorem~\ref{thm:entropy}).
  The optimal compressor achieves $r = h$ (source coding theorem).
  Both converge to the entropy rate.
\end{enumerate}
\end{proof}

\begin{remark}
The duality theorem says: there is ONE mathematical object (the
source's probability distribution) that underlies both compression
and prediction.  The UM's count table is a finite-sample estimate
of this object.  The forward pass extracts predictions; arithmetic
coding extracts compressed bits.  Both are views of the same
information.
\end{remark}


\section{Implications for the Hutter Prize}

\begin{proposition}[Path to winning]
To achieve $k$ bpc on enwik8 ($N = 10^8$), the UM needs:
\begin{enumerate}
\item Event spaces capturing $8 - k$ bits of MI per position.
\item Sufficient data for the count table to converge.
\item An arithmetic coder wrapping the predictor.
\end{enumerate}
Current status (February 2026):
\begin{itemize}
\item Byte KN-6 at $10^8$: 2.00 bpc.  Captures 6.00 bits/position.
\item Sat-RNN at $10^3$: 0.079 bpc.  Captures 7.92 bits/position
  (but only on 1024 bytes of training data).
\item Skip-8-gram at $10^3$: 0.043 bpc.  Captures 7.96 bits/position.
\end{itemize}
The gap between 2.00 bpc (byte KN at scale) and 0.043 bpc
(skip-8-gram at $10^3$) is the scaling challenge: the skip-gram's
MI is available in the data, but the count table grows
combinatorially with context length.
\end{proposition}

\begin{remark}
The compression--prediction duality frames the Hutter Prize purely
as a prediction problem: achieve the lowest possible cross-entropy
on enwik8.  The compressor is mechanical (arithmetic coding).  All
the intelligence is in the predictor (the UM).  And the predictor
is entirely determined by the event space and the counting function.
The Hutter Prize is won by the right event spaces.
\end{remark}


\begin{thebibliography}{99}
\bibitem{cmp}
Michaeljohn Clement.
\newblock \emph{CMP}.
\newblock \url{https://cmpr.ai/cmp.pdf}, 2026.

\bibitem{shannon}
Claude E.\ Shannon.
\newblock A mathematical theory of communication.
\newblock \emph{Bell System Technical Journal}, 27:379--423, 623--656, 1948.

\bibitem{rissanen}
Jorma Rissanen.
\newblock Modeling by shortest data description.
\newblock \emph{Automatica}, 14(5):465--471, 1978.

\bibitem{carrier-signal}
Claude and MJC.
\newblock \emph{The Carrier Signal Problem}.
\newblock Hutter archive, 12 Feb 2026.
\end{thebibliography}

\end{document}
