5D Library › Hundred-Volume Knowledge Hypergraphs, Multimodal Personal Prior Compilation and Autonomous Empire Scaling · 中文

Chapter 3. Compression and Coverage: How Much Do Fifteen Primitives Really Explain?

Description length

The claim that “15 core mathematical primitives cover 100 application domains” is a claim about compression: a library that defines each primitive once and refers to it from each volume should be much shorter than a hundred volumes that each spell everything out. Kolmogorov complexity, the length of the shortest program that produces a text, measures this ideally but cannot be computed (Kolmogorov 1965); the minimum description length principle replaces it with lengths under explicit codes (Rissanen 1978), and any real compressor gives an upper bound. p06 builds a synthetic library of 100 volumes with incompressible definitions.

Calculation

# Chapter 3. p06: How much does a shared library of primitives compress
# a hundred-volume description? Synthetic incidence (shared with p07 and
# p08): 100 volumes each use 2 to 5 of 15 core primitives (popularity
# falling as 1 / rank^0.8) and, with chance 0.25, one of 30 rare ones.
# Each primitive has a random definition of 300 to 580 letters from a
# 32-letter alphabet (5 bits a letter, incompressible by design); each
# use carries 24 letters of parameters. "Separate": every volume spells
# out each definition it uses. "Library": each used definition once,
# then a reference per use. Kolmogorov complexity cannot be computed; bz2
# and lzma sizes are upper bounds on it. (bz2 rather than zlib: zlib's
# output size varies between zlib builds.) Seed 100.
import bz2
import lzma
import random

ALPHA = "abcdefghijklmnopqrstuvwxyz012345"

def incidence(rng):
    w = [1 / (j + 1) ** 0.8 for j in range(15)]
    vols = []
    for _ in range(100):
        k = rng.choice((2, 2, 3, 3, 3, 4, 4, 5))
        use = set()
        while len(use) < k:
            use.add(rng.choices(range(15), weights=w)[0])
        use = sorted(use)
        if rng.random() < 0.25:
            use.append(15 + rng.randrange(30))
        vols.append(use)
    return vols

if __name__ == "__main__":
    rng = random.Random(100)
    vols = incidence(rng)
    defs = ["".join(rng.choice(ALPHA) for _ in range(300 + 7 * j % 281))
            for j in range(45)]
    used = sorted({j for v in vols for j in v})
    sep, ref = [], ["".join("{}:{};".format(j, defs[j]) for j in used)]
    for v in vols:
        for j in v:
            par = "".join(rng.choice(ALPHA) for _ in range(24))
            sep.append(defs[j] + par)
            ref.append("#{}{}".format(j, par))
    a, b = "".join(sep).encode(), "".join(ref).encode()
    print("   description      raw bytes    bz2 bytes   lzma bytes")
    for name, s in (("separate", a), ("library", b)):
        print("   {:<14}  {:10,d}  {:11,d}  {:11,d}".format(
            name, len(s), len(bz2.compress(s, 9)),
            len(lzma.compress(s, preset=9))))
    print("   primitives used: {} ({} core, {} rare)".format(
        len(used), sum(j < 15 for j in used), sum(j >= 15 for j in used)))
    print("   raw ratio separate / library: {:.2f}".format(len(a) / len(b)))
    print("   lzma ratio separate / library: {:.2f}".format(
        len(lzma.compress(a, preset=9)) / len(lzma.compress(b, preset=9))))
    print("   ideal bits (5 per letter): separate {:,}, library {:,}".format(
        5 * sum(len(x) for x in sep), 5 * sum(len(x) for x in ref)))
#    description      raw bytes    bz2 bytes   lzma bytes
#    separate           124,389       20,291       13,864
#    library             20,387       13,167       13,376
#    primitives used: 28 (15 core, 13 rare)
#    raw ratio separate / library: 6.10
#    lzma ratio separate / library: 1.04
#    ideal bits (5 per letter): separate 621,945, library 101,935

Spelled out separately the descriptions take 124,389 bytes; with a shared library, 20,387: a ratio of 6.10. But a general-purpose compressor that knows nothing of primitives brings the separate text down to 13,864 bytes with lzma, almost the same as the compressed library (13,376), a ratio of only 1.04. The repeated definitions were never information; any good compressor removes the repetition. The compression ratio of a primitive library is therefore large only against a naive baseline. Its real value is not fewer bits but named, checked, reusable pieces.

Coverage

p07 asks how many primitives are needed to cover the volumes completely, using the same synthetic incidence: a volume is covered only when every primitive it uses is in the set.

Calculation

# Chapter 3. p07: How many primitives cover how many volumes? The
# synthetic incidence of p06 (same seed, same generator). A volume is
# covered when every primitive it uses is in the chosen set. Greedy
# choice: at each step add the primitive that completes the most
# volumes (ties: the most uses). Seed 100.
import random

NAMES = ("markov", "phase-lock", "weibull", "bregman", "bayes", "kelly",
         "power-law", "queue", "entropy", "equilibrium", "stopping",
         "diffusion", "least-squares", "fourier", "centrality")

def incidence(rng):
    w = [1 / (j + 1) ** 0.8 for j in range(15)]
    vols = []
    for _ in range(100):
        k = rng.choice((2, 2, 3, 3, 3, 4, 4, 5))
        use = set()
        while len(use) < k:
            use.add(rng.choices(range(15), weights=w)[0])
        use = sorted(use)
        if rng.random() < 0.25:
            use.append(15 + rng.randrange(30))
        vols.append(use)
    return vols

if __name__ == "__main__":
    vols = incidence(random.Random(100))
    chosen, curve = set(), []
    allp = sorted({j for v in vols for j in v})
    while len(chosen) < len(allp):
        def score(j):
            s = chosen | {j}
            return (sum(set(v) <= s for v in vols),
                    sum(j in v for v in vols))
        j = max((j for j in allp if j not in chosen), key=score)
        chosen.add(j)
        curve.append((len(chosen), sum(set(v) <= chosen for v in vols)))
    for n, c in curve:
        if n in (3, 5, 8, 10, 12, 15) or c == 100:
            print("   {:2d} primitives cover {:3d} volumes".format(n, c))
            if c == 100:
                break
    top = sorted(range(15), key=lambda j: -sum(j in v for v in vols))[:4]
    print("   most used: " + ", ".join("{} ({})".format(
        NAMES[j], sum(j in v for v in vols)) for j in top))
    print("   volumes needing a rare primitive: {}".format(
        sum(max(v) >= 15 for v in vols)))
#     3 primitives cover   6 volumes
#     5 primitives cover  18 volumes
#     8 primitives cover  36 volumes
#    10 primitives cover  49 volumes
#    12 primitives cover  65 volumes
#    15 primitives cover  82 volumes
#    28 primitives cover 100 volumes
#    most used: markov (65), phase-lock (41), bregman (34), weibull (30)
#    volumes needing a rare primitive: 18

Coverage grows slowly at first, because a volume needs all of its primitives: 5 primitives cover 18 volumes, 10 cover 49. The fifteen core primitives cover 82 volumes. The other 18 each need a rare, domain-specific operator, and covering all 100 takes 28 primitives. The most used primitive, the Markov chain, appears in 65 volumes. “Fifteen primitives cover a hundred domains” is a statement about the head of a long-tailed distribution; the tail is where each domain keeps something of its own.

Volumes completely covered as primitives are added greedily, synthetic incidence (p07).

Hypothesis · not established

The author’s interpretation (not yet tested): when the actual programs of this library are tagged by the primitives they use, the fifteen most used primitives cover at least three quarters of the volumes completely, and full coverage needs fewer than twice as many primitives. What would show it wrong: a tagging of all programs by two independent readers, reconciled, in which the fifteen most used primitives cover fewer than three quarters of the volumes, or full coverage needs thirty or more primitives.

Summary

A shared library of primitives shortens a naive description sixfold, but a good compressor gets almost the same result on its own, so the “Kolmogorov reduction” claimed for a primitive library is mostly a reduction relative to repetition. In the synthetic library fifteen core primitives covered 82 of 100 volumes; full coverage needed 28.

References

Kolmogorov, Andrei N. 1965. “Three Approaches to the Quantitative Definition of Information.” Problems of Information Transmission 1 (1): 1 to 7.
Rissanen, Jorma. 1978. “Modeling by Shortest Data Description.” Automatica 14 (5): 465 to 471.

Fan, Y. (2026). Hundred-Volume Knowledge Hypergraphs, Multimodal Personal Prior Compilation and Autonomous Empire Scaling: Cross-Disciplinary Isomorphisms, Zero-Marginal-Cost Replication and Century-Scale Knowledge Preservation [百卷知识超图拓扑、多模态个人先验编译与自主知识帝国标度律] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090260 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).