Formal Computer Science / Mathematical structures

Kenton Labs / Mathematical structures

Information theory

Make code structure and exact expected length visible. Prefix validity and optimality are different questions.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Prefix-free code
No symbol’s codeword is a prefix of another symbol’s codeword.
Expected length
The probability-weighted sum of codeword lengths.
Instantaneous decoding
A prefix-free stream can identify a codeword without waiting for the next symbol.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Require one binary codeword for every declared symbol.
  2. Check every ordered pair for the prefix relation.
  3. Verify symbol probabilities form an exact rational distribution.
  4. Compute the average code length using rational arithmetic.

Cost and scope

With n symbols and maximum code length L, naive pairwise prefix checking is O(n²L).

A common failure

Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-055
Information theoryA probability-shaped prefix codeComplete codeword-pair check + exact rational average

The problem

Check binary prefix-freeness and compute exact mean codeword length.

The checked result

Prefix free: yes; Expected bits per symbol: 7/4.

The pairwise check reveals every possible prefix collision. Expected length is an exact fraction, avoiding rounding in the acceptance artifact.

Why the checker accepts it

  1. Require one binary codeword for every declared symbol.
  2. Check every ordered pair for the prefix relation.
  3. Verify symbol probabilities form an exact rational distribution.
  4. Compute the average code length using rational arithmetic.

Formal specification

{
  "probabilities": {
    "A": "1/2",
    "B": "1/4",
    "C": "1/8",
    "D": "1/8"
  }
}

Claim and evidence

{
  "claim": {
    "prefix_free": true,
    "expected_bits": "7/4"
  },
  "witness": {
    "codes": {
      "A": "0",
      "B": "10",
      "C": "110",
      "D": "111"
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 12 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

With n symbols and maximum code length L, naive pairwise prefix checking is O(n²L).

No entropy estimate or code optimality claim is made. A rejected prefix code is retained as an instructive checked negative result.

A boundary to investigate

Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length. Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-056 ↘Related KL-FCS-057 ↘
KL-FCS-056
Information theoryA fixed-length four-symbol codeComplete codeword-pair check + exact rational average

The problem

Check binary prefix-freeness and compute exact mean codeword length.

The checked result

Prefix free: yes; Expected bits per symbol: 2.

The pairwise check reveals every possible prefix collision. Expected length is an exact fraction, avoiding rounding in the acceptance artifact.

Why the checker accepts it

  1. Require one binary codeword for every declared symbol.
  2. Check every ordered pair for the prefix relation.
  3. Verify symbol probabilities form an exact rational distribution.
  4. Compute the average code length using rational arithmetic.

Formal specification

{
  "probabilities": {
    "A": "1/4",
    "B": "1/4",
    "C": "1/4",
    "D": "1/4"
  }
}

Claim and evidence

{
  "claim": {
    "prefix_free": true,
    "expected_bits": "2"
  },
  "witness": {
    "codes": {
      "A": "00",
      "B": "01",
      "C": "10",
      "D": "11"
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 12 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

With n symbols and maximum code length L, naive pairwise prefix checking is O(n²L).

No entropy estimate or code optimality claim is made. A rejected prefix code is retained as an instructive checked negative result.

A boundary to investigate

Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length. Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-055 ↘Related KL-FCS-057 ↘
KL-FCS-057
Information theoryA prefix collision as negative evidenceComplete codeword-pair check + exact rational average

The problem

Check binary prefix-freeness and compute exact mean codeword length.

The checked result

Prefix free: no; Expected bits per symbol: 3/2.

The pairwise check reveals every possible prefix collision. Expected length is an exact fraction, avoiding rounding in the acceptance artifact.

Why the checker accepts it

  1. Require one binary codeword for every declared symbol.
  2. Check every ordered pair for the prefix relation.
  3. Verify symbol probabilities form an exact rational distribution.
  4. Compute the average code length using rational arithmetic.

Formal specification

{
  "probabilities": {
    "A": "1/2",
    "B": "1/2"
  }
}

Claim and evidence

{
  "claim": {
    "prefix_free": false,
    "expected_bits": "3/2"
  },
  "witness": {
    "codes": {
      "A": "0",
      "B": "01"
    }
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 2 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

With n symbols and maximum code length L, naive pairwise prefix checking is O(n²L).

No entropy estimate or code optimality claim is made. A rejected prefix code is retained as an instructive checked negative result.

A boundary to investigate

Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length. Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-055 ↘Related KL-FCS-056 ↘

Go further.

Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

Questions to investigate

  1. Short-looking codewords can be ambiguous; a prefix check does not establish minimum expected length.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add Huffman construction traces, lossless round trips, and exact small-tree optimality certificates.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

Finite probabilityLinear algebra over GF(2)