Draft — mutable and not usable as a dependency; its citation marks the draft state.

Certified structural representations of finite data

lax-58·formalized by Jan Dreier·Szymon Toruńczyk @szymtor·ChatGPT (5.6 and 6)·created 2026-08-31·GitHub @83d795f·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    We define a neutral structural input convention for finite constructor data. Values are represented by binary trees with natural-number leaves; structural size counts tree nodes while primitive payload magnitude is tracked separately. A small fixed vocabulary constructs natural-number, product, and ordered-list presentations required by the current downstream application. A closed derivation command generates datatype encoders, complete constructor equations, and checked witnesses together. It accepts only natural numbers, finite indices, proof-erased subtypes, finite families, and previously derived datatypes. Unsupported fields fail elaboration; arbitrary field encoders have no access to this certified path. The generated equations remain inspectable and kernel-checked.

    The mathematical concepts are structural presentations, their fixed combinators, the distinguished word arena, and an encoding-aware word-RAM resource predicate. Separate, explicitly labeled infrastructure modules provide encoding-agreement bookkeeping and derivation tools; an arbitrary agreement value is not itself a provenance certificate.

    Every structural value has a distinguished dense immutable word arena. The arena stores exactly three words per structural node plus one root word, faithfully represents its source, and supplies the distinguished Lax word-RAM input tape consisting of that root followed by the arena. It fits in fixed-width word memory under separate payload and address-space hypotheses. The resource predicate uses the existing Lax word-RAM model to state explicit time and word-capacity bounds for mathematical functions. A closed frontend selects input and output encodings automatically; a separate example expresses linear dependence on one input with computable dependence on another. For natural-list inputs and natural outputs, verified RAM compilers prove equivalence between arena-based bit-polynomial time and Lax51's native length-prefixed convention. The implications may use polynomial bounds of unrelated degrees. The submission does not provide binary serialization, mutable-heap semantics, or a new algorithmic runtime model.

    Concepts

    Concept map

    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsThis submissionProof — click to open

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    @misc{lax-58,
      author = {Jan Dreier and Szymon Toruńczyk and ChatGPT (5.6 and 6)},
      title = {Certified structural representations of finite data},
      year = {2026},
      howpublished = {Lax Archive, lax-58},
      url = {https://laxarchive.org/lax-58/},
      note = {draft},
    }

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…