Kraft–McMillan Inequality: The Partition Function Condition for Uniquely Decodable Codes — E8 Intelligence Research

Abstract

FINDING: Kraft–McMillan inequality is the fundamental existence condition for uniquely decodable prefix codes, linking code-length sets to probability-like sums. MATH: For a D-ary alphabet, a set of codeword lengths {l₁,…,lₙ} admits a uniquely decodable code iff ∑ᵢ D^(−lᵢ) ≤ 1. Equality holds for complete (maximal) prefix codes. This is a necessary and sufficient condition (Kraft for prefix, McMillan for any uniquely decodable code). CONNECTION: The sum ∑ D^(−lᵢ) is a partition function. For D=2, the binary case, the inequality ∑ 2^(−lᵢ) ≤ 1 mirrors the packing condition for dyadic intervals on [0,1] — a 1D lattice packing. This generalises to higher dimensions: the E8 root system (8D) has a theta series whose coefficients satisfy a similar packing bound (Hermite constant, kissing number 240). The golden ratio appears in the *optimal* binary code lengths for geometric distributions (e.g., Huffman codes for Fibonacci probabilities yield lengths approaching log_φ(n)), and the constan Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com