# A minimal formalism for structural description complexity

This is deliverable A: the smallest formulation found for the notions requested in
`prompt.md` §18A. Three primitives suffice; everything else is derived.

*(Terminology note: "certificate" here means a global description of an entire
function — a transformation sequence — not the per-input certificate of Boolean
query complexity, which is an unrelated notion.)*

## 1. The three primitives

**P1 — Structured domain.** A finite set `X` presented by a type expression over
bare finite sets, with connectives `+`, `×`, `→`. A *bare* set carries no
structure except its cardinality; its automorphism group is the full symmetric
group. The type expression canonically induces on `X`:

- an automorphism group `Aut(X)` (computed compositionally from the grammar);
- a family of **derived maps** `q : X → V` into structured value spaces,
  generated by closing the type constructors under a small set of canonical
  operations (below).

**P2 — Structural subset description.** A description is a path through a
prefix-free *choice tree*: at each node, one option is selected among the `n`
options available there, at cost `log₂ n` bits. The described subset is a fiber
(or canonical region) of a tupled derived map:

```
S  =  { x ∈ X  :  q₁(x) ∈ R₁  ∧ … ∧  q_m(x) ∈ R_m }
L(S)  =  Σᵢ ( L(qᵢ) + L(Rᵢ | Vᵢ) )  +  m framing bits
```

where `L(q)` sums the choice costs of the map's derivation and `L(R|V)` the
choice costs of a canonical region of the value space `V` (a point of a bare
space; a point, up-set, down-set of a graded space; a diagonal or shifted
diagonal of a product of graded spaces). The cost of a subset is the minimum
over all of its descriptions — descriptions are syntax, subsets are semantics,
and syntactically distinct descriptions of one extension collapse to the
cheapest.

**P3 — Overwrite.** The single transformation kind:

```
T_{S,y}(g)(x) = y  if x ∈ S,   g(x) otherwise.
```

## 2. Derived notions

**Derived maps (how structure generates structure).** Four canonical
operations generate the map family; each is an instance of "quotient or fiber
of what you already have":

1. *Evaluation*: for `X = A → B`, the maps `eval_a : X → B` (choose `a`, cost
   `log₂|A|`).
2. *Multiplicity quotient*: for a family of interchangeable positions `P` (an
   orbit of `Aut`), the quotient `B^P / Sym(P)` coordinatized by counts
   `m_v(x) = #{p ∈ P : x(p) = v}`. The value space is graded: it carries the
   order and adjacency `m → m − e_i + e_j`, which is what makes thresholds and
   comparisons canonical regions rather than extra primitives.
3. *Fiber families*: for `X = A → B` with `A = C^D`, the fibers of the
   projections `A → C` and the graphs of automorphisms of `C` form canonical
   families of sub-positions (for tic-tac-toe: rows, columns, diagonals — the
   line family, 8 objects, derived rather than listed).
4. *Iteration*: any derived map's output space is again a structured domain, so
   the operations re-apply. Restriction to a line followed by the multiplicity
   quotient gives line profiles in `Sym³(Cell)`; counting *lines* by profile
   gives second-order multiplicities `N_p : X → {0..8}` — multiplicities of
   multiplicities. This is the "higher-order structure" of the task statement,
   and it needs no new mechanism: it is operation 2 applied to the output of
   operation 3.

**Certificate.** A sequence `C = (y₀; (S₁,y₁), …, (S_k,y_k))` denoting
`f_C = T_{S_k,y_k} ∘ … ∘ T_{S₁,y₁} (const_{y₀})`, with prefix-free cost

```
L(C) = log₂|Y|  +  Σᵢ (1 + L(Sᵢ) + log₂|Y|)  +  1 .
```

**Certificate complexity.** `κ(f) = min { L(C) : f_C = f }`.

**Consistency with partial observations.** For `D = {(xⱼ,yⱼ)}`:
`C ⊨ D  ⟺  f_C(xⱼ) = yⱼ` for all `j`. Learning is the outer MDL problem
`min { L(C) : C ⊨ D }`, and the prediction on unobserved points is whatever the
cheapest consistent certificate says.

## 3. Two structural facts the formalism yields for free

**Fact 1 (singletons are the degenerate case).** A singleton `{x}` is the fiber
of the tupled evaluation map over the point `(x(a))_{a∈A}`; its cost is the sum
of the pointwise choice costs — approximately the extensional description cost
of one row of the table. No separate "change one point" primitive exists, and
for an unstructured (bare) `X` every subset degenerates to unions of such
fibers, so κ smoothly approaches extensional table cost as structure becomes
useless. Universality (every `f` has a certificate) follows.

**Fact 2 (settled-set reduction; the discrete geometry).** Because later
overwrites win, only the last write at each point matters. Reading a
certificate backwards, rule `i` *settles* the points `Sᵢ \ (Sᵢ₊₁ ∪ … ∪ S_k)`,
where `f` must equal `yᵢ`. Hence

> κ(f) = weight of the shortest path `∅ = D₀ ⊂ D₁ ⊂ … ⊂ D_k` in the lattice of
> "settled sets", where each step adds one describable subset that is `f`-pure
> on its unsettled part, each step costs `1 + L(S) + log₂|Y|`, and the path may
> stop once the unsettled remainder is `f`-monochromatic.

This is the induced discrete geometry: κ(f) is a weighted word metric — the
distance from a constant function in the (astronomically large) graph whose
edges are overwrites — but the reduction compresses that graph to a shortest
path over settled sets, which never mentions intermediate extensions at all.
The reduction is validated empirically in `tests/test_core.py`
(`test_backward_equals_forward`): on a micro-domain the settled-set optimum
equals brute-force Dijkstra over the full `|Y|^|X|` function graph, for all
targets.

**Learner state (what a new observation changes).** The learner's entire state
is the pair `(C, D)` — one compressed partial function (the certificate) and
one extensional partial function (the observations). A correctly predicted
observation leaves `f_C` fixed but strictly shrinks the admissible cone of
future overwrites: `(S,y)` is *admissible* after `D` iff `S ∩ Dobs ⊆ f⁻¹... `
precisely, iff every observed point in `S` has label `y`. No bookkeeping beyond
`D` itself is needed: "protected points" for a candidate `(S,y)` are simply the
observed points whose label differs from `y` — a mask derived from `D` on
demand, not maintained state. Incremental repair at a wrong point `x` is the
local geodesic step:

```
min  L(S)   s.t.   x ∈ S,   S admissible for (S, y_true(x)).
```

## 4. What is deliberately absent

- No separate primitives for point/orbit/multiplicity-class/threshold changes —
  all are P2 with different derived maps (§3 Fact 1).
- No NonTerminal output class, no per-point protected set, no explicit version
  space, no certificate graph: the pair `(C, D)` plus the admissibility
  predicate carries all of it.
- No Boolean-formula search space: search operates on extensions (bitmasks);
  a conjunction is explored only as the fiber of a tupled map, and
  semantically equal descriptions are collapsed to their minimum cost.

## 5. Honest limitations of the present cost model

The implementation charges each choice point `log₂(#options)` with options
counted *flatly* (e.g. one position among 9 costs `log₂ 9`). The finer scheme
sketched in the task statement — counting options up to the *residual*
symmetry, i.e. successive stabilizer-quotiented choices — is strictly better
when orbit sizes vary, and coincides with two-part symmetry coding
(`L(S) ≈ log₂ #orbits + log₂ |orbit(S)|`). The flat scheme is an upper bound
that keeps the code prefix-free (Kraft mass ≤ 1 per family, tested), so no
information leaks; see the memo §5 for the stabilizer-refined scheme and a
worked example. Reuse discounts (referencing an already-derived structure for
`log₂(#derived-so-far)` bits) are likewise discussed but not implemented.