# RePair + LZ/addition-chain bounds — Siebert et al. (2026)

Publication-based design record, 2026-09-20. Protocol ID: `siebert-bounds`.
This method pairs the published RePair assembly construction with the lower
relaxations used in Figures 6 and 7. It does not change the existing
`repair-upper-bound` method's choices or guarantees.

## Primary sources

- Siebert, Chowdhury, Slocombe and Walker, *Assembly Spaces: Formal Definitions
  and Fast Methods for Approximating Assembly Indices*,
  [arXiv:2606.15499v1](https://arxiv.org/abs/2606.15499v1), pp. 28–33:
  RePair upper bounds, LZ string lower bounds and integer-addition-chain
  molecular lower bounds. Pages 24–25 describe the string/grammar correspondence.
- Charikar et al. (2005), *The Smallest Grammar Problem*,
  [DOI](https://doi.org/10.1109/TIT.2005.850116), Section VII-D, Lemma 9:
  greedy LZ parsing with references entirely contained in the preceding prefix.
  The paper's grammar size counts RHS symbols; that is not this application's
  count of binary joins with free elementary units. See the conversion below.
- Brauer (1939), *On Addition Chains*,
  [DOI](https://doi.org/10.1090/S0002-9904-1939-07068-7): increasing integer
  addition chains and the doubling lower bound.
- RePair's original source and our molecular partition conventions are recorded
  in [REPAIR_FIDELITY.md](REPAIR_FIDELITY.md).

These are papers, not software sources. No authors' code is consulted, copied,
translated or ported for this implementation. RePair uses the project's existing
independently written C++ construction, with unchanged replacement decisions.
Earlier project research inspected upstream software; this is therefore not
represented as a formal clean-room implementation. Publication attribution
does not assign the papers' or authors' software licenses to our new code. No
new repository license or patent/freedom-to-operate conclusion is asserted.

## Published scope and cost conventions

For strings the lower bound is `z - 1`, where `z` is the number of greedy
non-self-referencing LZ phrases (a new character is a one-character literal).
References may have length one; an occurrence must end before its phrase starts.
Characters are Unicode scalar values, matching the existing directed string
assembly model. No normalization or reverse-string equivalence is applied.

The subtraction is essential: a one-character string has one phrase and zero
assembly joins. More generally, take a rooted optimal binary assembly grammar
with `a` distinct nonterminal definitions. Traverse its derivation left to right,
expanding only the first occurrence of each nonterminal. The resulting partial
binary tree has `a` internal nodes and `a+1` leaves. Each leaf is a literal or
a non-overlapping reference to an earlier fully expanded occurrence. This is
a valid non-self-referencing LZ factorization; greedy longest-prefix parsing
uses no more phrases. Thus `z <= a+1`, hence `z-1 <= a`. This explicit
cost conversion is needed to use the published LZ relaxation in our join metric;
it is not a claim that the paper counts grammar size in the same way.

For molecules we use Figure 7's scalar specialization: map every fragment to its
number of bonds and every join to integer addition. The elementary scalar is 1.
Sorting distinct produced sizes and retaining a producing pair for each size
gives an increasing addition chain no longer than the molecular pathway.
Therefore the minimum addition-chain length `l(m)` is a molecular lower bound.
A single atom or a one-bond molecule has index zero in the application's model.
The initial certified scalar bound is `ceil(log2(m))`, computed with integers.

The article also describes the more general vector relaxation, with Cartesian
basis vectors, but does not give a specific vector-chain search algorithm.
This option implements the string and scalar molecular pairings demonstrated
in its figures; it does not claim to compute the stronger vector relaxation.
Neither an LZ bound on an arbitrary molecular serialization nor the project's
chain-specific Rytter extensions is used here.

## Unspecified implementation choices

| Choice | Convention in this implementation |
| --- | --- |
| LZ ties | Earliest prior source among equally long matches |
| LZ evaluation | Direct source comparisons; quadratic worst-case character comparisons, with deadline checkpoints |
| RePair construction | Exactly the independently documented deterministic choices in `REPAIR_FIDELITY.md` |
| Scalar-chain evaluation | Iterative depth exclusions over increasing chains; enumerate sums of **all** pairs of previous terms, not only star chains |
| Chain traversal | Distinct candidate sums in descending order; terms larger than the target are unnecessary |
| Chain impossibility test | Prune only when repeated doubling of the largest term cannot reach the target in the remaining steps |
| Pipeline | Compute the inexpensive lower bound, run RePair directly, then refine the scalar-chain bound |
| Stop | Return after the published bounds are evaluated, or when the bounds meet, or at a resource limit |

The article specifies the addition-chain relaxation, not how to solve its
minimum-length problem. The complete depth evaluator is our explicit
implementation choice, not an algorithm attributed to Siebert or Brauer and
not a claim of polynomial-time scalar-chain evaluation. It has its own state
counter. RePair decisions never use lower bounds, other algorithms' incumbents,
alternative partitions, Rytter constructions, or branch-and-bound extensions.
The paired wrapper does not first compute the standalone worker's unrelated
elementary safety pathway. That preparatory work was measured to prevent even
the first upper certificate within five seconds on the 192-bond chain; calling
the same RePair construction directly avoids it. This is a wrapper scheduling
choice, not a change to the published pair replacement or path partition.
During an interrupted construction the already computed lower bound survives.

## Evidence and interruption contract

Every upper bound includes a checked complete assembly witness. Lower evidence
names the relaxation and its cost convention, input length/bond count, and
completed LZ phrase count or chain depth exclusions. A chain witnessing length
`d` alone is an **upper** bound on `l(m)`, not a molecular lower bound. We raise
the molecular lower bound to `d` only after excluding every smaller permitted
depth. A partially searched depth never raises it. Finding a chain at the first
feasible depth completes evaluation of the scalar relaxation, not necessarily
of molecular assembly.

Negative depth exclusions are claims of the exhaustively tested trusted native
solver, as with the existing exact solvers; a list of excluded depths alone is
not an independently checkable mathematical proof certificate. The API checks
evidence structure, monotonicity and consistency, validates any supplied chain,
and independently recomputes the inexpensive LZ/doubling bounds. Tests compare
the chain solver with an independently written exhaustive oracle.

A normally completed interval has `exact: false, reason: bounds_computed`.
Only matching certified lower and checked upper bounds, completed and validated
within the deadline, can yield `exact: true, reason: proved`. Timeout,
cancellation, memory and output limits never produce an exact result. Already
established bounds survive interruption, including a lower-only result when no
complete construction was produced. Bounds are plotted at the time received,
not retroactively at search start. Dashed upper and lower traces are labelled
separately; other algorithms retain their existing upper-bound plots.

`candidate_pathways_considered` counts completed RePair pathway candidates
(normally one). `addition_chain_states` separately counts visited relaxation
states; neither is described as a molecular exhaustive-search subspace count.
This method promises a certified interval, not a universal tightness factor.