Information Compression Prior Coding Length

Coding length as ledger cost

In information theory, a coding length is the number of symbols needed to represent a message or an event under a chosen scheme. The classic result, Shannon's source coding theorem from 1948, says the optimal average length approaches the entropy of the source. That theorem sets a limit but does not say how to choose among the many schemes that achieve it. The Recognition Science framework starts from a different question: what if the cost of encoding is forced by the structure of counting itself, not chosen by the designer?

The framework's library defines coding_length as a count of events, a discrete record of how many things have happened. The declaration coding_length in the machine-checked library sets this count to a specific function called the ledger cost, written J(x) = (x + 1/x)/2 - 1. This function is not invented for the purpose. A proved result in the framework shows that any cost function satisfying five plain conditions, reciprocal symmetry, zero cost at unity, a forced composition law, calibration, and continuity, must equal this J. The composition law, written in symbols as F(xy) + F(x/y) = 2F(x)F(y) + 2F(x) + 2F(y), is the key constraint. Without regularity conditions, other solutions exist, but the continuity requirement selects J as the unique fair cost.

In Recognition Science, this J is the universal prior for minimum description length. The declaration mdl_prior simply sets the prior to J, and the declaration prior_holds proves that this prior equals the ledger cost for every model. The practical consequence is that the framework derives a specific coding length, not a family of them. The number of events n maps to J(n), so the cost grows roughly linearly for large n but has a minimum near n = 1, where J(1) = 0. This means the framework treats the empty or single-event case as cost-free, and every additional event adds a specific, forced amount of description length.

What this does not claim is important. The framework does not prove that Shannon entropy is wrong or that its own coding length replaces standard information theory. It proves that within its own axioms, the cost must be J. The connection to Shannon's theorem is a model choice, not a derivation. The framework also does not claim that this coding length is optimal for any particular real-world compression task; optimality in the classical sense remains a separate question. The declaration establishes a structural identity, not an empirical superiority.

noncomputable def coding_length (events : ℕ) : ℝ := Cost.Jcost (events : ℝ)

/-- Theorem: φ-prior holds as unique MDL from T5 J-unique. -/
theorem prior_holds : ∀ model, mdl_prior model = Cost.Jcost := by
  intro model
  simp [mdl_prior]

/-- Theorem: φ-prior holds as unique MDL from T5 J-unique. -/
theorem prior_holds : ∀ model, mdl_prior model = Cost.Jcost := by
  intro model
  simp [mdl_prior]

What this page does not claim

The framework does not prove that J is optimal for any real-world compression task in the classical information-theoretic sense. The framework does not derive Shannon's source coding theorem or replace entropy as a measure of information. The declaration does not claim that the ledger cost is the only possible coding length outside the framework's five axioms.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/CompressionPrior.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: