check_access_kraft.py

"""Finite controls for the adaptive-access Kraft/entropy theorem.

The theorem is mathematical; this checker keeps three easy-to-break seams
executable:

1. every fixed-configuration query tree has prefix-free leaf transcripts;
2. its fibrewise Kraft sum is at most one;
3. a nonuniform dyadic example makes

       H(configuration) + E[distinct queried bits] = H(payload)

   while the coarser maximum-depth bound is strictly weaker.

All payload cells are binary.  Query-tree nodes are represented by a payload
coordinate and two children; a leaf is represented by ``None``.
"""

from __future__ import annotations

from dataclasses import dataclass
from fractions import Fraction
from math import log2
from typing import Optional


@dataclass(frozen=True)
class Node:
    coordinate: int
    zero: Optional["Node"]
    one: Optional["Node"]


def leaf_transcripts(tree: Optional[Node], prefix: str = "") -> list[str]:
    if tree is None:
        return [prefix]
    return (
        leaf_transcripts(tree.zero, prefix + "0")
        + leaf_transcripts(tree.one, prefix + "1")
    )


def is_prefix_free(words: list[str]) -> bool:
    return all(
        not right.startswith(left)
        for i, left in enumerate(words)
        for j, right in enumerate(words)
        if i != j
    )


def kraft_sum(words: list[str]) -> Fraction:
    return sum((Fraction(1, 2 ** len(word)) for word in words), Fraction(0))


def entropy(probabilities: list[Fraction]) -> float:
    return -sum(float(p) * log2(float(p)) for p in probabilities if p)


def full_binary_tree(coordinates: tuple[int, ...]) -> Optional[Node]:
    if not coordinates:
        return None
    child = full_binary_tree(coordinates[1:])
    return Node(coordinates[0], child, child)


def check_tree_controls() -> None:
    # Complete depths 0 through 7 saturate Kraft.
    for depth in range(8):
        words = leaf_transcripts(full_binary_tree(tuple(range(depth))))
        assert is_prefix_free(words)
        assert kraft_sum(words) == 1

    # A deliberately non-complete tree still obeys Kraft.  Its leaf depths
    # are 1, 2, 3, 3.
    uneven = Node(
        0,
        None,
        Node(1, None, Node(2, None, None)),
    )
    words = leaf_transcripts(uneven)
    assert sorted(map(len, words)) == [1, 2, 3, 3]
    assert is_prefix_free(words)
    assert kraft_sum(words) == 1


def check_dyadic_equality_witness() -> None:
    # Uniform X in {0,1}^3.  The deterministic configuration fibres have
    # sizes 4,2,1,1 and access depths 2,1,0,0 respectively.
    fibre_sizes = [4, 2, 1, 1]
    access_depths = [2, 1, 0, 0]
    probabilities = [Fraction(size, 8) for size in fibre_sizes]

    # Each fibre has an exact binary decision tree for its residual members.
    for size, depth in zip(fibre_sizes, access_depths):
        words = leaf_transcripts(full_binary_tree(tuple(range(depth))))
        assert len(words) == size
        assert is_prefix_free(words)
        assert kraft_sum(words) == 1

    h_configuration = entropy(probabilities)
    expected_access = sum(
        float(probability) * depth
        for probability, depth in zip(probabilities, access_depths)
    )
    h_payload = 3.0

    assert abs(h_configuration - 1.75) < 1e-12
    assert abs(expected_access - 1.25) < 1e-12
    assert abs(h_configuration + expected_access - h_payload) < 1e-12

    # Replacing actual access by the global maximum depth loses 3/4 bit in
    # the resulting lower bound on configuration entropy.
    coarse_configuration_lower_bound = h_payload - max(access_depths)
    exact_configuration_lower_bound = h_payload - expected_access
    assert coarse_configuration_lower_bound == 1.0
    assert exact_configuration_lower_bound == 1.75

    # Cardinality/partition-function form: sum_c 2^a(c) = |X|.
    assert sum(2**depth for depth in access_depths) == 8


if __name__ == "__main__":
    check_tree_controls()
    check_dyadic_equality_witness()
    print("adaptive-access Kraft checks passed")
    print("complete and uneven prefix trees checked")
    print("dyadic witness: H(C)=1.75, E[L]=1.25, H(X)=3")
    print("partition function: 4+2+1+1=8 (equality)")