1% ============================================================================2% Section: formal framework (generated from research/framework.md; proofs kept in full)3% ============================================================================4\section{A formal framework: institutions as codes}5\label{sec:theory}67This section states the theory behind the Social Compression Hypothesis in a form that separates what is8\emph{proved} from what is \emph{conjectured}. Definitions are conventions; theorems are statements proved below9or standard results whose proofs are reproduced; conjectures are statements we believe worth testing, each with its10falsifier. Nothing in this section is an empirical finding. The results concern an idealized communication system;11Section~\ref{sec:theory-notclaimed} states what is not claimed and which pre-registered test, if any, can speak to12each statement.1314\subsection{Primitives and definitions}15\label{sec:theory-primitives}1617\begin{definition}[agents, tasks, plans]18\label{def:primitives}19A society has $N$ agents. In each period, coordination tasks arrive at rate $\lambda$ per agent. A task requires20that $k \ge 2$ participants settle on a common element of a finite \emph{plan set} $S$, $|S| = s$, the required plan21being drawn independently across tasks from a distribution $p$ on $S$ with Shannon entropy22$H(p) = -\sum_{x \in S} p(x)\log_2 p(x) \le \log_2 s$ \citep{shannon1948,cover2006}. Communication is counted in23\emph{messages} (one transmission between two agents) and in \emph{bits} (the length of what is transmitted).24Verification and record-keeping use a second channel whose cost is counted separately as \emph{administrative25overhead} (Definition~\ref{def:costs}).26\end{definition}2728\begin{definition}[coordination demand]29\label{def:demand}30The coordination demand of a period is the task volume that must be settled: $D = N \lambda k$ participant-slots31per period. In the worst case in which every pair of agents must be reconciled, $D$ is bounded by the number of32pairs, $N(N-1)/2$, i.e.\ $D = \Theta(N^2)$; under bounded $\lambda$ and $k$, $D = \Theta(N)$. Either way $D$ is33increasing in $N$.34\end{definition}3536\begin{definition}[coordination capacity]37\label{def:capacity}38Fix a tolerated error rate $\varepsilon \in (0,1)$. The coordination capacity $K$ of an institutional system is the39maximal number of tasks it can settle per period such that the fraction of tasks settled on a wrong or inconsistent40plan is at most $\varepsilon$. $K$ depends on the available communication budget (bits per period), the code in use41(Section~\ref{sec:theory-coding}), the routing structure (Section~\ref{sec:theory-hierarchy}) and the overhead42(Section~\ref{sec:theory-breakeven}).43\end{definition}4445\begin{definition}[utilization]46\label{def:utilization}47$\rho = D/K$. When $D$ and $K$ are measured in the same units (tasks per period), $\log D - \log K = \log \rho$48exactly.49\end{definition}5051\paragraph{Limitation (not a theorem).}52The pre-registered empirical index $P = z(\log D) - z(K)$ uses standardized proxies (population, territory,53settlement hierarchy for $D$; shares of administrative, legal/monetary, communication and record-keeping indicators54for $K$). It is a monotone proxy for $\log\rho$ only under Conjecture~\ref{conj:c1}; it is not a measurement of55$\rho$, and the Seshat and V-Dem indicators are not Shannon quantities.5657\subsection{Coding gain of a shared code}58\label{sec:theory-coding}5960\begin{definition}[code]61\label{def:code}62A \emph{shared code} is an injective map $c: S \to \{0,1\}^*$ known to all participants, with lengths63$\ell(x) = |c(x)|$. It is \emph{prefix-free} if no codeword is a prefix of another. Institutions in the sense of64this paper (standardized names, units, legal forms, accounting categories, calendars) are shared codes in exactly65this sense \citep{arrow1974,cremer2007}.66\end{definition}6768\begin{assumption}69\label{ass:settle}70Settling a task means that the initiating participant identifies the required plan $x \in S$ to the other $k-1$71participants without ambiguity; messages to different participants are counted separately in messages but72identically in bits per recipient, so the result is stated per recipient.73\end{assumption}7475\begin{theorem}[coding gain]76\label{thm:coding}77\begin{enumerate}[label=(\roman*)]78\item Without a shared code, identifying an arbitrary element of $S$ without error requires at least79$\lceil \log_2 s \rceil$ bits per recipient in the worst case.80\item With a shared prefix-free code that is optimal for $p$, the expected length per recipient81$L_p^{*} = \min_{c\ \text{prefix-free}} \sum_x p(x)\ell(x)$ satisfies82\begin{equation}83H(p) \le L_p^{*} < H(p) + 1 .84\end{equation}85\item Hence the expected saving per recipient, $G(p) = \lceil\log_2 s\rceil - L_p^{*}$, obeys86$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 strictly87positive as soon as $p$ is sufficiently concentrated ($H(p) < \lceil\log_2 s\rceil - 1$).88\end{enumerate}89\end{theorem}9091\begin{proof}92(i) Without a shared code there is no prior agreement on which binary string denotes which plan, so the only93error-free strategy is a fixed-length enumeration of $S$ agreed by the trivial convention of listing; any scheme94that distinguishes $s$ alternatives with binary strings of a fixed length $m$ needs $2^m \ge s$, i.e.\95$m \ge \lceil\log_2 s\rceil$. (The point is not that $\log_2 s$ is a lower bound for \emph{all} conceivable codes;96it is the cost of the \emph{codeless} baseline, in which the message must be self-describing.)9798(ii) \emph{Lower bound.} For any prefix-free code the Kraft inequality holds: $\sum_x 2^{-\ell(x)} \le 1$99\citep[Thm.~5.2.1]{cover2006}. Put $q(x) = 2^{-\ell(x)}/Z$ with $Z = \sum_x 2^{-\ell(x)} \le 1$. Then100\[101\sum_x p(x)\ell(x) - H(p) = \sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}}102= \sum_x p(x)\log_2\frac{p(x)}{q(x)} - \log_2 Z = D_{KL}(p\|q) - \log_2 Z \ge 0,103\]104because $D_{KL} \ge 0$ (Gibbs' inequality) and $-\log_2 Z \ge 0$. \emph{Upper bound.} Choose105$\ell(x) = \lceil -\log_2 p(x)\rceil$. Then $\sum_x 2^{-\ell(x)} \le \sum_x p(x) = 1$, so by the converse Kraft106theorem \citep[Thm.~5.2.1]{cover2006} a prefix-free code with these lengths exists, and107$\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.108109(iii) Subtract (ii) from (i).110\end{proof}111112\paragraph{Remark.}113Theorem~\ref{thm:coding} is the source-coding theorem of \citet{shannon1948} applied to the plan set. Its content114for the paper is only this: \emph{a shared code converts a worst-case identification cost into an average-case115cost that is lower exactly to the extent that tasks are predictable.} The ``compression'' in the name of the116hypothesis refers to this step and to nothing else. The same economy appears in the mechanism-design bounds on117message-space size \citep{mount1974,segal2007,nisan2006} and in communication complexity118\citep{yao1979,kushilevitz1997}; the rate--distortion view of \citet{marzen2017} and the coarse-graining view of119\citet{dedeo2017} are the closest conceptual neighbours.120121\subsection{Break-even scale of an institution}122\label{sec:theory-breakeven}123124\begin{definition}[institutional cost structure]125\label{def:costs}126Adopting a code costs a fixed set-up $F \ge 0$ (designing and promulgating the standard), a learning cost127$\ell \ge 0$ per agent (each of the $N$ agents must learn the code), and an administrative overhead $a \ge 0$ bits128per task (verification, record-keeping, enforcement). It saves $G > 0$ bits per task (Theorem~\ref{thm:coding}, per129recipient; multiply by $k-1$ if desired; the argument is unchanged).130\end{definition}131132\begin{theorem}[break-even]133\label{thm:breakeven}134Over a horizon with $T$ tasks, the institution lowers total communication cost if and only if135\begin{equation}136T\,(G - a) > F + N\ell .137\end{equation}138With $T = N\lambda\tau$ over $\tau$ periods, this is equivalent to139\begin{equation}140\lambda\tau > \frac{F/N + \ell}{G - a}\quad\text{when } G > a,141\end{equation}142and the inequality can never hold when $a \ge G$.143\end{theorem}144145\begin{proof}146Total cost without the institution is $C_0 = T\lceil\log_2 s\rceil$. With it,147$C_1 = F + N\ell + T(L_p^{*} + a)$. Then $C_1 < C_0$ if and only if148$F + N\ell < T(\lceil\log_2 s\rceil - L_p^{*} - a) = T(G - a)$. If $a \ge G$ the right-hand side is149$\le 0 < F + N\ell$ unless $F = \ell = 0$ and $a = G$, in which case the costs are equal, so strict improvement is150impossible. If $G > a$, substitute $T = N\lambda\tau$ and divide both sides by $N(G-a) > 0$.151\end{proof}152153\begin{corollary}[scale advantage]154\label{cor:scale}155The threshold $(F/N + \ell)/(G-a)$ is decreasing in $N$: holding $\lambda,\tau$ fixed, a larger society crosses the156break-even point sooner, because the set-up cost is spread over more agents. It is \emph{not} decreasing in $N$157through $\ell$: per-agent learning costs do not benefit from scale.158\end{corollary}159160This is the formal version of the observation that institutions ``pay off at scale''161\citep{johnson1982,garicano2000,bolton1994}, and it also makes precise when they do not: when overhead $a$ is close162to the coding gain $G$, or when horizons $\tau$ are short.163164\subsection{Mismatched code penalty: institutional rigidity}165\label{sec:theory-stale}166167\begin{theorem}[cost of a stale code]168\label{thm:stale}169Let the code be optimal for $p$ in the sense of using lengths $\ell_p(x) = \lceil -\log_2 p(x) \rceil$, and let the170true task distribution be $q$ with $q \ll p$ (every plan with positive $q$-probability has positive171$p$-probability). Then the expected length under $q$ satisfies172\begin{equation}173H(q) + D_{KL}(q\|p) \le \mathbb{E}_q[\ell_p(X)] < H(q) + D_{KL}(q\|p) + 1 .174\end{equation}175The excess cost of using the $p$-code when the world is $q$, relative to the $q$-optimal code, lies in176$(D_{KL}(q\|p) - 1,\ D_{KL}(q\|p) + 1)$ bits per task.177\end{theorem}178179\begin{proof}180Since $-\log_2 p(x) \le \ell_p(x) < -\log_2 p(x) + 1$,181\[182\mathbb{E}_q[\ell_p(X)] \ge \sum_x q(x)\bigl(-\log_2 p(x)\bigr)183= \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),184\]185and the same computation with the $+1$ gives the strict upper bound. The $q$-optimal code has expected length in186$[H(q), H(q)+1)$ by Theorem~\ref{thm:coding}(ii), which yields the stated interval for the excess. This is the187``wrong code'' result of \citet[Thm.~5.4.3]{cover2006}.188\end{proof}189190\begin{corollary}[fragility]191\label{cor:fragility}192A shock that moves the task distribution from $p$ to $q$ raises the per-task communication cost of an existing193institution by about $D_{KL}(q\|p)$ bits. Combined with Theorem~\ref{thm:breakeven}, the institution remains194worthwhile after the shock only if $G(p) - D_{KL}(q\|p) > a$ (up to the $\pm 1$ rounding).195\end{corollary}196197An institution can therefore \emph{lower} efficiency after a shock, and the more specialized the code (the smaller198$H(p)$ relative to $\log_2 s$), the larger the divergence a given shock can produce. This is the precise sense in199which standardization trades efficiency for rigidity; it echoes the declining marginal returns of200\citet{tainter1988} but gives the mechanism a unit (bits per task) and a magnitude (a divergence).201202\subsection{Hierarchical routing bound and root load}203\label{sec:theory-hierarchy}204205\begin{definition}[hierarchy]206\label{def:hierarchy}207A hierarchy is a rooted tree whose $N$ leaves are the agents and whose internal nodes are administrative units;208every internal node has at most $b \ge 2$ children; the depth (leaf-to-root distance) is $d = \lceil \log_b N \rceil$209for a complete $b$-ary tree. A task between two leaves is \emph{settled by relay} when each participant sends a210message up to their lowest common ancestor (LCA) and the LCA sends the settlement down.211\end{definition}212213\begin{theorem}[routing and root load]214\label{thm:routing}215\begin{enumerate}[label=(\roman*)]216\item \emph{Message bound.} Any pairwise task can be settled with at most $2d$ messages (up-path plus down-path217through the LCA), versus up to $N-1$ messages for a flat broadcast in which the initiator must reach every other218agent. For $M$ pairwise tasks the total is at most $2M\lceil\log_b N\rceil$.219\item \emph{Root load.} In a complete $b$-ary tree with $N = b^d$ leaves, if the two participants of a task are220drawn uniformly at random among leaves (independently, with replacement), the probability that their LCA is the221root is $1 - 1/b$. Hence the expected number of tasks that pass through the root is $M(1 - 1/b)$.222\item \emph{Federated or modular coordination.} If a fraction $\theta \in [0,1]$ of tasks is \emph{local} (both223participants belong to the same first-level module, i.e.\ child subtree of the root, by construction of the task224process) and the remaining $1-\theta$ are drawn uniformly as in (ii), the expected root load is225$M(1-\theta)(1 - 1/b)$.226\end{enumerate}227\end{theorem}228229\begin{proof}230(i) In a tree there is a unique simple path between two leaves; it passes through their LCA and has length at most231$2d$ since each leaf is at depth $\le d$ and the LCA is at depth $\ge 0$. Sending one message per edge along the two232leaf-to-LCA paths settles the task in $\le 2d$ messages. A flat broadcast from one initiator to the other $N-1$233agents uses $N-1$ messages. Summing over $M$ tasks gives (i).234235(ii) The root has $b$ children, each the root of a subtree with $b^{d-1}$ leaves. The first participant lies in some236child subtree $j$; the second participant, drawn uniformly and independently, lies in the same subtree $j$ with237probability $b^{d-1}/b^d = 1/b$. The LCA is the root exactly when the two participants lie in different child238subtrees, which has probability $1 - 1/b$. Expectation of a sum of $M$ indicators gives $M(1-1/b)$.239240(iii) Local tasks never reach the root (their LCA lies inside a module); the non-local fraction behaves as in (ii).241By linearity of expectation the load is $M(1-\theta)(1-1/b)$.242\end{proof}243244\paragraph{Remark.}245Theorem~\ref{thm:routing} formalizes the trade-off between centralized administration and federated coordination246\citep{radner1993,bolton1994}: a hierarchy cuts the \emph{message} cost of coordination from linear to logarithmic in247$N$, but concentrates a constant fraction $1 - 1/b$ of all non-local tasks on the apex, whose processing rate then248bounds $K$ (Definition~\ref{def:capacity}). Modularity reduces apex load by the locality fraction $\theta$ at the249price of \emph{not} reconciling across modules. These are the five regimes compared in the pre-registered250simulations (no institution, shared norms, standardized records, centralized administration, federated), and the251simulations measure messages and bits directly rather than assuming the bounds.252253\subsection{Backlog dynamics under mismatch}254\label{sec:theory-backlog}255256\begin{definition}[backlog]257\label{def:backlog}258Let $D_t$ be the number of tasks arriving in period $t$ and $K_t$ the number the system can settle in period $t$.259The backlog of unsettled tasks follows the Lindley recursion260\begin{equation}261B_{t+1} = \max\{0,\ B_t + D_t - K_t\},\qquad B_0 \ge 0 .262\end{equation}263\end{definition}264265\begin{theorem}[backlog dynamics]266\label{thm:backlog}267\begin{enumerate}[label=(\roman*)]268\item \emph{Deterministic case.} If $D_t = D$ and $K_t = K$ for all $t$, then: if $D \le K$,269$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 when270$D < K$ and stays constant at $B_0$ when $D = K$; if $D > K$, $B_t = B_0 + t(D-K) \to \infty$ linearly.271\item \emph{Stochastic case.} If $(D_t - K_t)_{t\ge0}$ is i.i.d.\ with finite mean, then when272$\mathbb{E}[D_t] < \mathbb{E}[K_t]$ the backlog has a proper stationary distribution to which $B_t$ converges from273any $B_0$, and when $\mathbb{E}[D_t] > \mathbb{E}[K_t]$, $B_t \to \infty$ almost surely.274\item \emph{Delay under a Markovian approximation.} If arrivals are Poisson with rate $\lambda_D$ and settlements275are exponential with rate $\mu$ (an M/M/1 queue), with $\rho = \lambda_D/\mu < 1$, the expected sojourn time is276$W = 1/(\mu - \lambda_D) = (1/\mu)/(1-\rho)$, which is increasing and convex in $\rho$ on $[0,1)$ and diverges as277$\rho \uparrow 1$.278\end{enumerate}279\end{theorem}280281\begin{proof}282(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)\}$, with283equality as long as the argument is nonnegative, which gives the hitting time when $D < K$ and constancy when284$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 and285$B_{t+1} = B_t + (D-K)$, hence $B_t = B_0 + t(D-K)$.286287(ii) The recursion is the single-server waiting-time recursion of \citet{lindley1952}, and the stability dichotomy288is the theorem of \citet{loynes1962}; the proof is not reproduced here and the result is cited.289290(iii) The M/M/1 stationary number in system is geometric with parameter $\rho$, so the mean is $\rho/(1-\rho)$ and291Little's law gives $W = \rho/((1-\rho)\lambda_D) = 1/(\mu(1-\rho)) = 1/(\mu - \lambda_D)$. The function292$f(\rho) = (1-\rho)^{-1}$ has $f' = (1-\rho)^{-2} > 0$ and $f'' = 2(1-\rho)^{-3} > 0$ on $[0,1)$, and293$f(\rho) \to \infty$ as $\rho \uparrow 1$.294\end{proof}295296\paragraph{Scope of Theorem~\ref{thm:backlog}.}297This is a \emph{mechanism}, not evidence. Polities are not single-server queues: capacity is endogenous298(institutions are built in response to backlog), arrivals are correlated across periods and agents, and299``unsettled tasks'' are not observed in the historical record. The theorem is used only to motivate two qualitative300predictions, that costs rise smoothly and convexly in utilization and that sustained $\rho > 1$ is qualitatively301different from $\rho < 1$, and both are stated as conjectures below.302303\subsection{Conjectures}304\label{sec:theory-conjectures}305306The following statements are unproved. Each is given with its reason and its falsifier.307308\begin{conjecture}[proxy monotonicity]309\label{conj:c1}310The pre-registered Seshat and V-Dem proxies are monotone in the model's primitives: the scale variables311(population, territory, largest settlement, settlement hierarchy) increase with $D$ of Definition~\ref{def:demand},312and the four indicator blocks (administration, standardized rules and money, communication infrastructure,313record-keeping) increase with $K$ of Definition~\ref{def:capacity}, so that $P = z(\log D) - z(K)$ is monotone in314$\log\rho$ up to measurement error.315\end{conjecture}316317\noindent\emph{Reason:} population and territory raise the number and the dispersion of participants; written318records, legal codes, money and measurement systems are shared codes (Theorem~\ref{thm:coding}); roads, couriers319and postal systems raise bits per period; administrative levels implement the routing of320Theorem~\ref{thm:routing}. \emph{Falsifier:} the proxies for $D$ and $K$ are so collinear (as Seshat's first321principal component suggests; \citealp{shin2020}) that $P$ retains almost no variance, or alternative defensible $K$322weightings reverse the sign of $P$ for a substantial share of polities; both are reported in the measurement323section.324325\begin{conjecture}[sustained overload raises breakdown probability]326\label{conj:c2}327Periods with $\rho > 1$ sustained longer than the time needed to build capacity raise the probability of328institutional breakdown.329\end{conjecture}330331\noindent\emph{Mechanism family (not proved):} unsettled tasks accumulate (Theorem~\ref{thm:backlog}), so332participants cannot form the common knowledge required for coordinated action \citep{chwe2000} and local defection333spreads by contagion through the interaction network \citep{morris2000}; institutions whose codes are stale after a334shock lose their cost advantage (Theorem~\ref{thm:stale}) and are abandoned. \emph{Falsifier:} the pre-registered335H2 tests find $\beta_P$ not positive, or $P$ does not beat the population-only and capacity-only baselines out of336sample.337338\begin{conjecture}[smooth, not step]339\label{conj:c3}340The relation between $P$ and instability is convex and smooth away from $\rho \approx 1$ and steepens near it,341rather than a discrete threshold.342\end{conjecture}343344\noindent\emph{Reason:} Theorem~\ref{thm:backlog}(iii) gives a smooth, convex delay in $\rho$; discontinuities345would require an additional tipping mechanism (e.g.\ a critical mass in a contagion model) that the framework does346not supply. \emph{Falsifier:} the pre-registered H4 comparison finds that a hinge or step model beats the smooth347model out of sample in at least 80\% of folds, which would favour a tipping mechanism; conversely, if neither348nonlinear form beats the linear model, the ``steepening'' clause of the conjecture is unsupported.349350\subsection{What is not claimed, and which test speaks to each statement}351\label{sec:theory-notclaimed}352353\begin{itemize}354\item \textbf{No Shannon measurement of history.} Theorems~\ref{thm:coding} and~\ref{thm:stale} are about codes for355a plan set with a known distribution. Seshat indicators (presence of writing, coins, courts, roads) are not message356lengths, and no entropy or divergence is computed from historical data anywhere in this paper. Shannon quantities357appear only in the simulations, where the plan distribution $p$ and the messages are defined by the experimenter and358can be measured.359\item \textbf{No causal claim.} The theorems describe an idealized communication system; the empirical tests are360associational and were pre-registered as such; the identification discussion is in Section~\ref{sec:identification}.361\item \textbf{Endogeneity of capacity.} The framework takes $K$ as given within a period; historically, $K$ is built362in response to $D$ \citep{johnson1982,shin2020}. This is why H1 is pre-registered as an association without a363direction.364\end{itemize}365366\begin{table}[htbp]367\centering368\caption{Which evidence can speak to each statement of the framework.}369\label{tab:theory-map}370\small371\begin{tabular}{p{3.2cm} p{6.2cm} p{5.2cm}}372\toprule373Statement & What can speak to it & Pre-registered test \\374\midrule375Theorem~\ref{thm:coding} (coding gain) & Simulated messages and bits with vs.\ without a shared code & H3 (regimes b, c vs.\ a) \\376Theorem~\ref{thm:breakeven} (break-even) & Simulated total cost across $N$, $\lambda$, horizon, overhead $a$ & H3 factorial cells; search for cells where institutions lose \\377Theorem~\ref{thm:stale} (stale code) & Simulated shocks to the task distribution & H3 adverse regimes (shock treatment) \\378Theorem~\ref{thm:routing} (routing, root load) & Simulated messages and apex load under centralized vs.\ federated regimes & H3 (regimes d, e) \\379Theorem~\ref{thm:backlog} (backlog) & Not testable with the historical data (backlog unobserved); illustrated in simulation only & none (stated as mechanism) \\380Conjecture~\ref{conj:c1} & Measurement diagnostics: collinearity of $D$ and $K$ proxies, sensitivity of $P$ to weights & Measurement section \\381Conjecture~\ref{conj:c2} & Lagged $P$ and subsequent instability vs.\ baselines, out of sample & H2 (Seshat Y1--Y3; V-Dem Y4--Y6), H5 \\382Conjecture~\ref{conj:c3} & Linear vs.\ hinge vs.\ spline in $P$, out of sample & H4 \\383\bottomrule384\end{tabular}385\end{table}386