% ============================================================================
% Section: formal framework (generated from research/framework.md; proofs kept in full)
% ============================================================================
\section{A formal framework: institutions as codes}
\label{sec:theory}

This section states the theory behind the Social Compression Hypothesis in a form that separates what is
\emph{proved} from what is \emph{conjectured}. Definitions are conventions; theorems are statements proved below
or standard results whose proofs are reproduced; conjectures are statements we believe worth testing, each with its
falsifier. Nothing in this section is an empirical finding. The results concern an idealized communication system;
Section~\ref{sec:theory-notclaimed} states what is not claimed and which pre-registered test, if any, can speak to
each statement.

\subsection{Primitives and definitions}
\label{sec:theory-primitives}

\begin{definition}[agents, tasks, plans]
\label{def:primitives}
A society has $N$ agents. In each period, coordination tasks arrive at rate $\lambda$ per agent. A task requires
that $k \ge 2$ participants settle on a common element of a finite \emph{plan set} $S$, $|S| = s$, the required plan
being drawn independently across tasks from a distribution $p$ on $S$ with Shannon entropy
$H(p) = -\sum_{x \in S} p(x)\log_2 p(x) \le \log_2 s$ \citep{shannon1948,cover2006}. Communication is counted in
\emph{messages} (one transmission between two agents) and in \emph{bits} (the length of what is transmitted).
Verification and record-keeping use a second channel whose cost is counted separately as \emph{administrative
overhead} (Definition~\ref{def:costs}).
\end{definition}

\begin{definition}[coordination demand]
\label{def:demand}
The coordination demand of a period is the task volume that must be settled: $D = N \lambda k$ participant-slots
per period. In the worst case in which every pair of agents must be reconciled, $D$ is bounded by the number of
pairs, $N(N-1)/2$, i.e.\ $D = \Theta(N^2)$; under bounded $\lambda$ and $k$, $D = \Theta(N)$. Either way $D$ is
increasing in $N$.
\end{definition}

\begin{definition}[coordination capacity]
\label{def:capacity}
Fix a tolerated error rate $\varepsilon \in (0,1)$. The coordination capacity $K$ of an institutional system is the
maximal number of tasks it can settle per period such that the fraction of tasks settled on a wrong or inconsistent
plan is at most $\varepsilon$. $K$ depends on the available communication budget (bits per period), the code in use
(Section~\ref{sec:theory-coding}), the routing structure (Section~\ref{sec:theory-hierarchy}) and the overhead
(Section~\ref{sec:theory-breakeven}).
\end{definition}

\begin{definition}[utilization]
\label{def:utilization}
$\rho = D/K$. When $D$ and $K$ are measured in the same units (tasks per period), $\log D - \log K = \log \rho$
exactly.
\end{definition}

\paragraph{Limitation (not a theorem).}
The pre-registered empirical index $P = z(\log D) - z(K)$ uses standardized proxies (population, territory,
settlement hierarchy for $D$; shares of administrative, legal/monetary, communication and record-keeping indicators
for $K$). It is a monotone proxy for $\log\rho$ only under Conjecture~\ref{conj:c1}; it is not a measurement of
$\rho$, and the Seshat and V-Dem indicators are not Shannon quantities.

\subsection{Coding gain of a shared code}
\label{sec:theory-coding}

\begin{definition}[code]
\label{def:code}
A \emph{shared code} is an injective map $c: S \to \{0,1\}^*$ known to all participants, with lengths
$\ell(x) = |c(x)|$. It is \emph{prefix-free} if no codeword is a prefix of another. Institutions in the sense of
this paper (standardized names, units, legal forms, accounting categories, calendars) are shared codes in exactly
this sense \citep{arrow1974,cremer2007}.
\end{definition}

\begin{assumption}
\label{ass:settle}
Settling a task means that the initiating participant identifies the required plan $x \in S$ to the other $k-1$
participants without ambiguity; messages to different participants are counted separately in messages but
identically in bits per recipient, so the result is stated per recipient.
\end{assumption}

\begin{theorem}[coding gain]
\label{thm:coding}
\begin{enumerate}[label=(\roman*)]
\item Without a shared code, identifying an arbitrary element of $S$ without error requires at least
$\lceil \log_2 s \rceil$ bits per recipient in the worst case.
\item With a shared prefix-free code that is optimal for $p$, the expected length per recipient
$L_p^{*} = \min_{c\ \text{prefix-free}} \sum_x p(x)\ell(x)$ satisfies
\begin{equation}
H(p) \le L_p^{*} < H(p) + 1 .
\end{equation}
\item Hence the expected saving per recipient, $G(p) = \lceil\log_2 s\rceil - L_p^{*}$, obeys
$G(p) > \lceil\log_2 s\rceil - H(p) - 1 \ge 0$ whenever $\lceil\log_2 s\rceil \ge H(p)+1$, and $G(p)$ is strictly
positive as soon as $p$ is sufficiently concentrated ($H(p) < \lceil\log_2 s\rceil - 1$).
\end{enumerate}
\end{theorem}

\begin{proof}
(i) Without a shared code there is no prior agreement on which binary string denotes which plan, so the only
error-free strategy is a fixed-length enumeration of $S$ agreed by the trivial convention of listing; any scheme
that distinguishes $s$ alternatives with binary strings of a fixed length $m$ needs $2^m \ge s$, i.e.\
$m \ge \lceil\log_2 s\rceil$. (The point is not that $\log_2 s$ is a lower bound for \emph{all} conceivable codes;
it is the cost of the \emph{codeless} baseline, in which the message must be self-describing.)

(ii) \emph{Lower bound.} For any prefix-free code the Kraft inequality holds: $\sum_x 2^{-\ell(x)} \le 1$
\citep[Thm.~5.2.1]{cover2006}. Put $q(x) = 2^{-\ell(x)}/Z$ with $Z = \sum_x 2^{-\ell(x)} \le 1$. Then
\[
\sum_x p(x)\ell(x) - H(p) = \sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}}
= \sum_x p(x)\log_2\frac{p(x)}{q(x)} - \log_2 Z = D_{KL}(p\|q) - \log_2 Z \ge 0,
\]
because $D_{KL} \ge 0$ (Gibbs' inequality) and $-\log_2 Z \ge 0$. \emph{Upper bound.} Choose
$\ell(x) = \lceil -\log_2 p(x)\rceil$. Then $\sum_x 2^{-\ell(x)} \le \sum_x p(x) = 1$, so by the converse Kraft
theorem \citep[Thm.~5.2.1]{cover2006} a prefix-free code with these lengths exists, and
$\sum_x p(x)\ell(x) < \sum_x p(x)(-\log_2 p(x) + 1) = H(p) + 1$. The optimal code does at least as well.

(iii) Subtract (ii) from (i).
\end{proof}

\paragraph{Remark.}
Theorem~\ref{thm:coding} is the source-coding theorem of \citet{shannon1948} applied to the plan set. Its content
for the paper is only this: \emph{a shared code converts a worst-case identification cost into an average-case
cost that is lower exactly to the extent that tasks are predictable.} The ``compression'' in the name of the
hypothesis refers to this step and to nothing else. The same economy appears in the mechanism-design bounds on
message-space size \citep{mount1974,segal2007,nisan2006} and in communication complexity
\citep{yao1979,kushilevitz1997}; the rate--distortion view of \citet{marzen2017} and the coarse-graining view of
\citet{dedeo2017} are the closest conceptual neighbours.

\subsection{Break-even scale of an institution}
\label{sec:theory-breakeven}

\begin{definition}[institutional cost structure]
\label{def:costs}
Adopting a code costs a fixed set-up $F \ge 0$ (designing and promulgating the standard), a learning cost
$\ell \ge 0$ per agent (each of the $N$ agents must learn the code), and an administrative overhead $a \ge 0$ bits
per task (verification, record-keeping, enforcement). It saves $G > 0$ bits per task (Theorem~\ref{thm:coding}, per
recipient; multiply by $k-1$ if desired; the argument is unchanged).
\end{definition}

\begin{theorem}[break-even]
\label{thm:breakeven}
Over a horizon with $T$ tasks, the institution lowers total communication cost if and only if
\begin{equation}
T\,(G - a) > F + N\ell .
\end{equation}
With $T = N\lambda\tau$ over $\tau$ periods, this is equivalent to
\begin{equation}
\lambda\tau > \frac{F/N + \ell}{G - a}\quad\text{when } G > a,
\end{equation}
and the inequality can never hold when $a \ge G$.
\end{theorem}

\begin{proof}
Total cost without the institution is $C_0 = T\lceil\log_2 s\rceil$. With it,
$C_1 = F + N\ell + T(L_p^{*} + a)$. Then $C_1 < C_0$ if and only if
$F + N\ell < T(\lceil\log_2 s\rceil - L_p^{*} - a) = T(G - a)$. If $a \ge G$ the right-hand side is
$\le 0 < F + N\ell$ unless $F = \ell = 0$ and $a = G$, in which case the costs are equal, so strict improvement is
impossible. If $G > a$, substitute $T = N\lambda\tau$ and divide both sides by $N(G-a) > 0$.
\end{proof}

\begin{corollary}[scale advantage]
\label{cor:scale}
The threshold $(F/N + \ell)/(G-a)$ is decreasing in $N$: holding $\lambda,\tau$ fixed, a larger society crosses the
break-even point sooner, because the set-up cost is spread over more agents. It is \emph{not} decreasing in $N$
through $\ell$: per-agent learning costs do not benefit from scale.
\end{corollary}

This is the formal version of the observation that institutions ``pay off at scale''
\citep{johnson1982,garicano2000,bolton1994}, and it also makes precise when they do not: when overhead $a$ is close
to the coding gain $G$, or when horizons $\tau$ are short.

\subsection{Mismatched code penalty: institutional rigidity}
\label{sec:theory-stale}

\begin{theorem}[cost of a stale code]
\label{thm:stale}
Let the code be optimal for $p$ in the sense of using lengths $\ell_p(x) = \lceil -\log_2 p(x) \rceil$, and let the
true task distribution be $q$ with $q \ll p$ (every plan with positive $q$-probability has positive
$p$-probability). Then the expected length under $q$ satisfies
\begin{equation}
H(q) + D_{KL}(q\|p) \le \mathbb{E}_q[\ell_p(X)] < H(q) + D_{KL}(q\|p) + 1 .
\end{equation}
The excess cost of using the $p$-code when the world is $q$, relative to the $q$-optimal code, lies in
$(D_{KL}(q\|p) - 1,\ D_{KL}(q\|p) + 1)$ bits per task.
\end{theorem}

\begin{proof}
Since $-\log_2 p(x) \le \ell_p(x) < -\log_2 p(x) + 1$,
\[
\mathbb{E}_q[\ell_p(X)] \ge \sum_x q(x)\bigl(-\log_2 p(x)\bigr)
= \sum_x q(x)\log_2\frac{q(x)}{p(x)} + \sum_x q(x)\bigl(-\log_2 q(x)\bigr) = D_{KL}(q\|p) + H(q),
\]
and the same computation with the $+1$ gives the strict upper bound. The $q$-optimal code has expected length in
$[H(q), H(q)+1)$ by Theorem~\ref{thm:coding}(ii), which yields the stated interval for the excess. This is the
``wrong code'' result of \citet[Thm.~5.4.3]{cover2006}.
\end{proof}

\begin{corollary}[fragility]
\label{cor:fragility}
A shock that moves the task distribution from $p$ to $q$ raises the per-task communication cost of an existing
institution by about $D_{KL}(q\|p)$ bits. Combined with Theorem~\ref{thm:breakeven}, the institution remains
worthwhile after the shock only if $G(p) - D_{KL}(q\|p) > a$ (up to the $\pm 1$ rounding).
\end{corollary}

An institution can therefore \emph{lower} efficiency after a shock, and the more specialized the code (the smaller
$H(p)$ relative to $\log_2 s$), the larger the divergence a given shock can produce. This is the precise sense in
which standardization trades efficiency for rigidity; it echoes the declining marginal returns of
\citet{tainter1988} but gives the mechanism a unit (bits per task) and a magnitude (a divergence).

\subsection{Hierarchical routing bound and root load}
\label{sec:theory-hierarchy}

\begin{definition}[hierarchy]
\label{def:hierarchy}
A hierarchy is a rooted tree whose $N$ leaves are the agents and whose internal nodes are administrative units;
every internal node has at most $b \ge 2$ children; the depth (leaf-to-root distance) is $d = \lceil \log_b N \rceil$
for a complete $b$-ary tree. A task between two leaves is \emph{settled by relay} when each participant sends a
message up to their lowest common ancestor (LCA) and the LCA sends the settlement down.
\end{definition}

\begin{theorem}[routing and root load]
\label{thm:routing}
\begin{enumerate}[label=(\roman*)]
\item \emph{Message bound.} Any pairwise task can be settled with at most $2d$ messages (up-path plus down-path
through the LCA), versus up to $N-1$ messages for a flat broadcast in which the initiator must reach every other
agent. For $M$ pairwise tasks the total is at most $2M\lceil\log_b N\rceil$.
\item \emph{Root load.} In a complete $b$-ary tree with $N = b^d$ leaves, if the two participants of a task are
drawn uniformly at random among leaves (independently, with replacement), the probability that their LCA is the
root is $1 - 1/b$. Hence the expected number of tasks that pass through the root is $M(1 - 1/b)$.
\item \emph{Federated or modular coordination.} If a fraction $\theta \in [0,1]$ of tasks is \emph{local} (both
participants belong to the same first-level module, i.e.\ child subtree of the root, by construction of the task
process) and the remaining $1-\theta$ are drawn uniformly as in (ii), the expected root load is
$M(1-\theta)(1 - 1/b)$.
\end{enumerate}
\end{theorem}

\begin{proof}
(i) In a tree there is a unique simple path between two leaves; it passes through their LCA and has length at most
$2d$ since each leaf is at depth $\le d$ and the LCA is at depth $\ge 0$. Sending one message per edge along the two
leaf-to-LCA paths settles the task in $\le 2d$ messages. A flat broadcast from one initiator to the other $N-1$
agents uses $N-1$ messages. Summing over $M$ tasks gives (i).

(ii) The root has $b$ children, each the root of a subtree with $b^{d-1}$ leaves. The first participant lies in some
child subtree $j$; the second participant, drawn uniformly and independently, lies in the same subtree $j$ with
probability $b^{d-1}/b^d = 1/b$. The LCA is the root exactly when the two participants lie in different child
subtrees, which has probability $1 - 1/b$. Expectation of a sum of $M$ indicators gives $M(1-1/b)$.

(iii) Local tasks never reach the root (their LCA lies inside a module); the non-local fraction behaves as in (ii).
By linearity of expectation the load is $M(1-\theta)(1-1/b)$.
\end{proof}

\paragraph{Remark.}
Theorem~\ref{thm:routing} formalizes the trade-off between centralized administration and federated coordination
\citep{radner1993,bolton1994}: a hierarchy cuts the \emph{message} cost of coordination from linear to logarithmic in
$N$, but concentrates a constant fraction $1 - 1/b$ of all non-local tasks on the apex, whose processing rate then
bounds $K$ (Definition~\ref{def:capacity}). Modularity reduces apex load by the locality fraction $\theta$ at the
price of \emph{not} reconciling across modules. These are the five regimes compared in the pre-registered
simulations (no institution, shared norms, standardized records, centralized administration, federated), and the
simulations measure messages and bits directly rather than assuming the bounds.

\subsection{Backlog dynamics under mismatch}
\label{sec:theory-backlog}

\begin{definition}[backlog]
\label{def:backlog}
Let $D_t$ be the number of tasks arriving in period $t$ and $K_t$ the number the system can settle in period $t$.
The backlog of unsettled tasks follows the Lindley recursion
\begin{equation}
B_{t+1} = \max\{0,\ B_t + D_t - K_t\},\qquad B_0 \ge 0 .
\end{equation}
\end{definition}

\begin{theorem}[backlog dynamics]
\label{thm:backlog}
\begin{enumerate}[label=(\roman*)]
\item \emph{Deterministic case.} If $D_t = D$ and $K_t = K$ for all $t$, then: if $D \le K$,
$B_t \le \max\{B_0 - t(K-D), 0\}$, so the backlog reaches $0$ after at most $\lceil B_0/(K-D) \rceil$ periods when
$D < K$ and stays constant at $B_0$ when $D = K$; if $D > K$, $B_t = B_0 + t(D-K) \to \infty$ linearly.
\item \emph{Stochastic case.} If $(D_t - K_t)_{t\ge0}$ is i.i.d.\ with finite mean, then when
$\mathbb{E}[D_t] < \mathbb{E}[K_t]$ the backlog has a proper stationary distribution to which $B_t$ converges from
any $B_0$, and when $\mathbb{E}[D_t] > \mathbb{E}[K_t]$, $B_t \to \infty$ almost surely.
\item \emph{Delay under a Markovian approximation.} If arrivals are Poisson with rate $\lambda_D$ and settlements
are exponential with rate $\mu$ (an M/M/1 queue), with $\rho = \lambda_D/\mu < 1$, the expected sojourn time is
$W = 1/(\mu - \lambda_D) = (1/\mu)/(1-\rho)$, which is increasing and convex in $\rho$ on $[0,1)$ and diverges as
$\rho \uparrow 1$.
\end{enumerate}
\end{theorem}

\begin{proof}
(i) If $D \le K$, then $B_{t+1} = \max\{0, B_t - (K-D)\}$; by induction $B_t \le \max\{0, B_0 - t(K-D)\}$, with
equality as long as the argument is nonnegative, which gives the hitting time when $D < K$ and constancy when
$D = K$. If $D > K$, then $B_t + D - K > 0$ for all $t$ (since $B_t \ge 0$), so the maximum is never binding and
$B_{t+1} = B_t + (D-K)$, hence $B_t = B_0 + t(D-K)$.

(ii) The recursion is the single-server waiting-time recursion of \citet{lindley1952}, and the stability dichotomy
is the theorem of \citet{loynes1962}; the proof is not reproduced here and the result is cited.

(iii) The M/M/1 stationary number in system is geometric with parameter $\rho$, so the mean is $\rho/(1-\rho)$ and
Little's law gives $W = \rho/((1-\rho)\lambda_D) = 1/(\mu(1-\rho)) = 1/(\mu - \lambda_D)$. The function
$f(\rho) = (1-\rho)^{-1}$ has $f' = (1-\rho)^{-2} > 0$ and $f'' = 2(1-\rho)^{-3} > 0$ on $[0,1)$, and
$f(\rho) \to \infty$ as $\rho \uparrow 1$.
\end{proof}

\paragraph{Scope of Theorem~\ref{thm:backlog}.}
This is a \emph{mechanism}, not evidence. Polities are not single-server queues: capacity is endogenous
(institutions are built in response to backlog), arrivals are correlated across periods and agents, and
``unsettled tasks'' are not observed in the historical record. The theorem is used only to motivate two qualitative
predictions, that costs rise smoothly and convexly in utilization and that sustained $\rho > 1$ is qualitatively
different from $\rho < 1$, and both are stated as conjectures below.

\subsection{Conjectures}
\label{sec:theory-conjectures}

The following statements are unproved. Each is given with its reason and its falsifier.

\begin{conjecture}[proxy monotonicity]
\label{conj:c1}
The pre-registered Seshat and V-Dem proxies are monotone in the model's primitives: the scale variables
(population, territory, largest settlement, settlement hierarchy) increase with $D$ of Definition~\ref{def:demand},
and the four indicator blocks (administration, standardized rules and money, communication infrastructure,
record-keeping) increase with $K$ of Definition~\ref{def:capacity}, so that $P = z(\log D) - z(K)$ is monotone in
$\log\rho$ up to measurement error.
\end{conjecture}

\noindent\emph{Reason:} population and territory raise the number and the dispersion of participants; written
records, legal codes, money and measurement systems are shared codes (Theorem~\ref{thm:coding}); roads, couriers
and postal systems raise bits per period; administrative levels implement the routing of
Theorem~\ref{thm:routing}. \emph{Falsifier:} the proxies for $D$ and $K$ are so collinear (as Seshat's first
principal component suggests; \citealp{shin2020}) that $P$ retains almost no variance, or alternative defensible $K$
weightings reverse the sign of $P$ for a substantial share of polities; both are reported in the measurement
section.

\begin{conjecture}[sustained overload raises breakdown probability]
\label{conj:c2}
Periods with $\rho > 1$ sustained longer than the time needed to build capacity raise the probability of
institutional breakdown.
\end{conjecture}

\noindent\emph{Mechanism family (not proved):} unsettled tasks accumulate (Theorem~\ref{thm:backlog}), so
participants cannot form the common knowledge required for coordinated action \citep{chwe2000} and local defection
spreads by contagion through the interaction network \citep{morris2000}; institutions whose codes are stale after a
shock lose their cost advantage (Theorem~\ref{thm:stale}) and are abandoned. \emph{Falsifier:} the pre-registered
H2 tests find $\beta_P$ not positive, or $P$ does not beat the population-only and capacity-only baselines out of
sample.

\begin{conjecture}[smooth, not step]
\label{conj:c3}
The relation between $P$ and instability is convex and smooth away from $\rho \approx 1$ and steepens near it,
rather than a discrete threshold.
\end{conjecture}

\noindent\emph{Reason:} Theorem~\ref{thm:backlog}(iii) gives a smooth, convex delay in $\rho$; discontinuities
would require an additional tipping mechanism (e.g.\ a critical mass in a contagion model) that the framework does
not supply. \emph{Falsifier:} the pre-registered H4 comparison finds that a hinge or step model beats the smooth
model out of sample in at least 80\% of folds, which would favour a tipping mechanism; conversely, if neither
nonlinear form beats the linear model, the ``steepening'' clause of the conjecture is unsupported.

\subsection{What is not claimed, and which test speaks to each statement}
\label{sec:theory-notclaimed}

\begin{itemize}
\item \textbf{No Shannon measurement of history.} Theorems~\ref{thm:coding} and~\ref{thm:stale} are about codes for
a plan set with a known distribution. Seshat indicators (presence of writing, coins, courts, roads) are not message
lengths, and no entropy or divergence is computed from historical data anywhere in this paper. Shannon quantities
appear only in the simulations, where the plan distribution $p$ and the messages are defined by the experimenter and
can be measured.
\item \textbf{No causal claim.} The theorems describe an idealized communication system; the empirical tests are
associational and were pre-registered as such; the identification discussion is in Section~\ref{sec:identification}.
\item \textbf{Endogeneity of capacity.} The framework takes $K$ as given within a period; historically, $K$ is built
in response to $D$ \citep{johnson1982,shin2020}. This is why H1 is pre-registered as an association without a
direction.
\end{itemize}

\begin{table}[htbp]
\centering
\caption{Which evidence can speak to each statement of the framework.}
\label{tab:theory-map}
\small
\begin{tabular}{p{3.2cm} p{6.2cm} p{5.2cm}}
\toprule
Statement & What can speak to it & Pre-registered test \\
\midrule
Theorem~\ref{thm:coding} (coding gain) & Simulated messages and bits with vs.\ without a shared code & H3 (regimes b, c vs.\ a) \\
Theorem~\ref{thm:breakeven} (break-even) & Simulated total cost across $N$, $\lambda$, horizon, overhead $a$ & H3 factorial cells; search for cells where institutions lose \\
Theorem~\ref{thm:stale} (stale code) & Simulated shocks to the task distribution & H3 adverse regimes (shock treatment) \\
Theorem~\ref{thm:routing} (routing, root load) & Simulated messages and apex load under centralized vs.\ federated regimes & H3 (regimes d, e) \\
Theorem~\ref{thm:backlog} (backlog) & Not testable with the historical data (backlog unobserved); illustrated in simulation only & none (stated as mechanism) \\
Conjecture~\ref{conj:c1} & Measurement diagnostics: collinearity of $D$ and $K$ proxies, sensitivity of $P$ to weights & Measurement section \\
Conjecture~\ref{conj:c2} & Lagged $P$ and subsequent instability vs.\ baselines, out of sample & H2 (Seshat Y1--Y3; V-Dem Y4--Y6), H5 \\
Conjecture~\ref{conj:c3} & Linear vs.\ hinge vs.\ spline in $P$, out of sample & H4 \\
\bottomrule
\end{tabular}
\end{table}