Environment v4.30.0. The archive's epoch is v4.33.0; only submissions in v4.30.0 can cite this work.
Certified structural representations of finite data
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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
- def✓
RamPolynomialComparison - def✓
StructuralCombinators - def✓
WordArena
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax58Proofs.RamExponentialExample.exponentialLength_bitPolynomialTime -
⊢
Lax58Proofs.RamPolynomialComparison.bitPolynomialTime_iff_ramPolytime -
⊢
Lax58Proofs.RamPolynomialSeparation.exponentialLength_not_polynomialTime -
⊢
Lax58Proofs.StructuralCombinators.structural_combinator_size_laws -
⊢
Lax58Proofs.StructuralCombinators.structural_combinators_lawful
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
Cite this
This is only the formalizers. The authors of the formalized results may be different (see References).
@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},
}
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments