Metadata-Version: 2.5
Name: zero-sum-sequences
Version: 0.2.0
Summary: Computations with additive and zero-sum sequences
Project-URL: Repository, https://github.com/behackl/zero-sum-sequences
Author: Benjamin Hackl
License-Expression: MIT
License-File: LICENSE
Requires-Python: >=3.12
Requires-Dist: networkx>=3.2
Provides-Extra: dev
Requires-Dist: pytest>=8.3; extra == 'dev'
Provides-Extra: sage
Requires-Dist: sagelite[gap]==10.9.post1; extra == 'sage'
Provides-Extra: tutorial
Requires-Dist: ipykernel>=6.29; extra == 'tutorial'
Requires-Dist: matplotlib>=3.8; extra == 'tutorial'
Requires-Dist: nbconvert>=7.16; extra == 'tutorial'
Description-Content-Type: text/markdown

# Zero-sum sequences

`zero-sum-sequences` provides immutable finite additive sequences and tools for
enumerating their factorizations into minimal zero-sum sequences. The runtime
is ordinary Python with NetworkX; SageMath is supported as an optional source
of additive parents, but is not required.

The package keeps group-specific mathematics explicit. Callers configure the
ambient parent and provide an upper bound for its Davenport constant; the
package does not infer structural invariants from the parent.

## Installation

Install the latest release from PyPI into Python 3.12 or newer:

```console
python -m pip install zero-sum-sequences
```

The optional `sage` extra installs the `sagelite` runtime on supported
platforms:

```console
python -m pip install "zero-sum-sequences[sage]"
```

For a reproducible development environment using the committed `uv.lock`,
clone the repository and run:

```console
uv sync --extra dev
uv run python -m pytest
```

Alternatively, install the package and its test tools with `pip`:

```console
python -m pip install -e '.[dev]'
python -m pytest
```

To include the Sage integration tests, use `uv sync --extra dev --extra sage`
or install the editable `.[dev,sage]` extra.

## Tutorial

[![Launch the tutorial on Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/behackl/zero-sum-sequences/main?urlpath=lab/tree/notebooks/tutorial.ipynb)

The executable [tutorial](https://github.com/behackl/zero-sum-sequences/blob/main/notebooks/tutorial.ipynb) introduces the public API
with small hand-checkable examples in ordinary Python.
Its execution dependencies are available through
`uv sync --extra tutorial` or the corresponding `pip` extra.

## Additive sequences

Configure an ambient parent and a Davenport upper bound once, then use the
resulting callable space to construct sequences. `FiniteAdditiveGroup` is a
small convenience adapter for groups represented by ordinary Python values:

```python
from zero_sum_sequences import AdditiveSequenceSpace, FiniteAdditiveGroup

group = FiniteAdditiveGroup(
    range(3),
    zero=0,
    add=lambda left, right: (left + right) % 3,
    coerce=lambda value: int(value) % 3,
)
Sequences = AdditiveSequenceSpace(group, davenport_bound=3)

sequence = Sequences([1, 1, 2, 2])
sequence.is_zero_sum()  # True
sequence.is_atom()      # False: 1 * 2 is a proper zero-sum subsequence
sequence.multiplicities
```

Existing algebra systems can be used directly. A compatible parent is
callable for coercion and provides `zero()`; its elements must be hashable and
mutually orderable. Elements may implement `+`, or the parent may provide
`add(left, right)`. Exhaustive catalogue enumeration additionally requires the
parent to be finite, iterable, and to provide `is_finite()`.

A sequence is immutable and hashable. Addition combines multisets,
subtraction removes a subsequence, and multiplication by a non-negative
integer repeats a sequence. Arithmetic preserves the sequence space, and the
empty sequence retains the base parent and its zero element.
`sequence.map_terms(mapping)` applies a map to every term and reconstructs the
result as a canonical multiset; pass `target_space=` when the image belongs to
a different sequence space.

The configured bound must not be smaller than the actual Davenport constant
when complete atom or factorization results are required.

## Factorizations

The factorization engine indexes relevant atom divisors as sparse
multiplicity vectors and merges equal remainders in a directed acyclic graph.
Attained lengths are represented internally as integer bitsets.

```python
lengths = sequence.length_set()
minimum = sequence.minimum_factorization_length()
maximum = sequence.maximum_factorization_length()
witnesses = sequence.factorization_witnesses()
factorizations = list(sequence.factorizations())
length_three = list(sequence.factorizations(factor_count=3))
has_length_three = sequence.has_factorization_of_length(3)
graph = sequence.factorization_digraph()
```

`factorization_witnesses()` retains one factorization for every attained
length. Exhaustive `factorizations()` is necessarily output-sensitive, but it
emits each unordered factorization once. Pass `factor_count=` to enumerate
only factorizations of one length; `has_factorization_of_length()` tests that
length with a targeted search unless complete length data is already cached.
`minimum_factorization_length()` uses a shortest-path search, while
`maximum_factorization_length()` uses integer dynamic programming on the
remainder DAG. Both return `None` when no factorization exists.
`factorization_digraph()` returns a NetworkX `DiGraph` whose vertices are
remainder sequences and whose edges store the removed atom in their `"atom"`
attribute.

For several queries against the same remainder DAG, use the public solver:

```python
from zero_sum_sequences import FactorizationSolver

solver = FactorizationSolver(sequence)
solver.length_set()
solver.minimum_factorization_length()
solver.maximum_factorization_length()
solver.has_factorization_of_length(3)
solver.factorization_witness(3)
list(solver.factorizations(factor_count=3))
solver.factorization_witnesses()
solver.statistics
solver.digraph()
```

To find just one factorization, use `solver.factorization_witness(k)`. It
returns a deterministic tuple of atoms, or `None` if the requested length is
absent, without first constructing the full remainder DAG or computing the
complete length set. Existing fixed-length answers and complete length data
are reused when available. An optional predicate can constrain the witness:

```python
solver.factorization_witness(
    3,
    minimum_matching_factors=2,
    factor_predicate=lambda atom: len(atom) == 2,
)
```

This asks for three factors, at least two of which have term length two.
`None` means that no witness satisfies both constraints; it does not imply
that length three itself is absent. Profile-constrained searches are also
targeted, but may need to explore more alternatives. For the empty sequence,
the length-zero witness is `()` rather than `None`.

Inspecting `solver.statistics` or calling `solver.digraph()` materializes the
full remainder graph, even if preceding queries were targeted.

A complete precomputed catalogue can avoid rediscovering atoms:

```python
from zero_sum_sequences import AtomCatalogue, FactorizationSolver

catalogue = AtomCatalogue(Sequences, atoms)
solver = FactorizationSolver(sequence, atom_catalogue=catalogue)
```

For a small finite parent, a complete reduced catalogue can instead be
generated exhaustively through the configured Davenport bound:

```python
catalogue = Sequences.enumerate_atom_catalogue()
```

The parent must be a finite iterable additive group. Enumeration completes
each sorted prefix with its uniquely determined final term, rather than
testing multisets whose sum is nonzero. Completeness depends on the configured
Davenport bound being valid.

To enumerate only atoms supported on a subset of the ambient group, pass
`support=`:

```python
# Here Sequences is the C_3 space from the first example.
restricted = Sequences.enumerate_atom_catalogue(support=[1])
list(restricted)  # Only the atom 1^3; 2 need not belong to the support.
Sequences([1] * 6).length_set(atom_catalogue=restricted)  # {2}
```

The support can be any iterable of terms, not necessarily a subgroup or a
set closed under negation. Terms are coerced through the ambient parent;
duplicates and zero are ignored. An empty or zero-only support gives an empty
reduced catalogue. Omitting `support` (or passing `None`) enumerates over the
whole ambient group as before.

Only prefixes on the chosen support are generated; the final completing term
must also belong to it. Sums and inverses are still computed in the ambient
group, which must remain finite and iterable. The bound must cover all atom
lengths on the chosen support; a valid ambient Davenport bound suffices. Such
a catalogue is complete for sequences supported there, but is not generally
complete for sequences containing other terms.

The caller is responsible for catalogue completeness. A catalogue used for a
complete result must contain every atom divisor relevant to the input.

Factorizations are computed in the reduced block monoid: identity terms are
not accepted by the solver and are not stored in an `AtomCatalogue`.

## Factorization relations

A `FactorizationRelation` represents an oriented equality between two
unordered factorizations. It canonicalizes the factors on each side, verifies
that all factors use one sequence space and have equal products, and provides
common-factor cancellation and the standard factorization distance.

For example, over $C_3$ let $A=1^3$, $B=2^3$, and $P=1\cdot2$. Since
$AB=P^3$, adjoining one common factor gives a relation between $ABP$ and
$P^4$:

```python
from zero_sum_sequences import FactorizationRelation

A = Sequences([1, 1, 1])
B = Sequences([2, 2, 2])
P = Sequences([1, 2])

relation = FactorizationRelation(
    source=(A, B, P),
    target=(P, P, P, P),
)
relation.common_factor       # (P,)
relation.reduced_source      # (A, B)
relation.reduced_target      # (P, P, P)
relation.distance            # 3

reduced = relation.reduced()
reduced.is_reduced           # True
reduced.product == A + B     # True
```

Relations are immutable and preserve the orientation of their source and
target. Construction assumes that supplied factors are atoms rather than
rerunning potentially expensive atomicity tests. Solver-produced
factorizations and catalogue entries already satisfy that contract. For a
relation with two empty sides, pass its sequence space explicitly as
`space=Sequences`.

## Automorphism orbits

Group automorphisms act on sequences term by term. Because an
`AdditiveSequence` is a multiset, the induced action automatically disregards
the order of its terms. The package can materialize an orbit, test orbit
membership, and return a shortest deterministic word in the configured
automorphism generators.

The convenience constructor for a product of cyclic groups configures the
coordinate group and generators of its full automorphism group together. For
example, the eight maximal-length atoms over $C_2\oplus C_4$ form one orbit:

```python
G = FiniteAdditiveGroup.cyclic_product(2, 4)
C2xC4 = AdditiveSequenceSpace(G, davenport_bound=5)

atom = C2xC4([(0, 1)] * 3 + [(1, 0), (1, 1)])
other = C2xC4([(0, 1), (1, 0)] + [(1, 1)] * 3)

len(atom.orbit())                         # 8
atom.is_in_same_orbit(other)              # True
witness = atom.orbit_witness(other)
witness.show()
# (1, 0) ↦ (1, 0)
# (0, 1) ↦ (1, 1)
```

Automorphism data is resolved only on the first orbit query and then cached on
the sequence space. A returned witness retains this context, so `show()` can
display the induced homomorphism on the base parent's distinguished additive
generators. `FiniteAdditiveGroup.cyclic_product(...)` supplies both the
standard additive generators and elementary coordinate scalings and shears.
Finite-dimensional Sage vector spaces over finite fields are recognized
automatically and use their basis and generators of their general linear
group. A custom `FiniteAdditiveGroup` can receive `additive_generators=` and
callable `automorphism_generators=` at construction; callers can also pass an
`AutomorphismAction` explicitly through the `action=` keyword.

Orbit traversal is breadth-first and therefore requires a finite orbit.
Automatic discovery raises `AutomorphismActionUnavailable` when the parent
does not expose suitable generators, in which case an explicit action is
required.

## Materialized automorphism groups

For a finite parent the whole automorphism group can be materialized, which
gives stabilizers, canonical orbit representatives, transporters and
classification of many objects at once:

```python
G = FiniteAdditiveGroup.cyclic_product(2, 4)
C2xC4 = AdditiveSequenceSpace(G, davenport_bound=5)
group = C2xC4.automorphism_group()        # AutomorphismGroup(order=8)

x = C2xC4([(1, 1), (1, 1), (0, 2)])
group.orbit(x)                            # the four images, sorted
len(group.stabilizer(x))                  # 2
form = group.canonical_form(x)            # orbit minimum + smallest automorphism reaching it
form.automorphism.generator_images()      # ((1, 0), (1, 1)): the "matrix", column by column
group.transporter(x, group.apply(form.automorphism, x))

atoms = tuple(C2xC4.enumerate_atom_catalogue())
group.orbit_representatives(atoms)        # 11 orbits: representative -> members
```

The group acts on sequences and on tuples of sequences; tuples are treated as
multisets unless `ordered=True` (the canonical form of a tuple also records
the permutation that sorts the image). Canonical forms are minima with
respect to the total order on sequences (length first, then the sorted term
list, exposed through `<`), so representatives do not depend on how the group
was found.

The parent decides how the group is obtained: a `FiniteAdditiveGroup` may
receive a callable `automorphism_group=` returning an `AutomorphismGroup`
built from any element type with `apply_term`, `compose` and `inverse`
callbacks (for example units acting on a cyclic group, or CAS matrices);
otherwise its `automorphism_generators` are closed under composition.
Orbit traversals cost proportionally to the orbit size; stabilizers and
smallest transporters scan the whole group once, so they are cheap for
groups of a few thousand elements and expensive beyond that.
`AutomorphismGroupUnavailable` is raised when neither a provider nor
generators exist.

## Indexed and serialized catalogues

An `AtomCatalogue` stores its atoms in the sequence order (length first,
then terms), so `catalogue.index(atom)` and `catalogue[i]` form a stable
identifier namespace. It can be filtered, classified into automorphism
orbits, and written to or read from JSON lines:

```python
catalogue = C2xC4.enumerate_atom_catalogue()
catalogue.index(atom), catalogue[7], atom in catalogue
short = catalogue.restrict(max_length=3)            # also restrict(support=...)
for orbit in catalogue.orbits():                    # AtomOrbit(representative, indices, stabilizer_order)
    ...
catalogue.representative(atom)                      # orbit minimum of an atom
catalogue.transporter(atom)                         # an automorphism mapping atom to it
catalogue.permutation(group.elements[1])            # an automorphism as an index permutation

catalogue.to_jsonl("atoms.jsonl", annotate=lambda atom: {"label": ...})
same = AtomCatalogue.from_jsonl("atoms.jsonl", C2xC4)
same.annotations[atom]["label"]
catalogue.digest()                                  # sha256 of the atoms, annotation-independent
```

`from_jsonl` checks the order, the indices and the digest, and re-verifies
every record as an atom unless `verify=False`. Terms are serialized through
the parent: `FiniteAdditiveGroup` accepts `encode_term=`/`decode_term=`,
coordinate groups and Sage vector spaces use lists of integers by default,
and `sequence.encode()` / `space.decode(data)` apply the codec to whole
sequences.

## Memoized factorization queries

A `FactorizationCache` answers length-set questions over one catalogue with
caching, and can exploit that length sets are automorphism invariants:

```python
cache = C2xC4.factorization_cache(catalogue)
cache.length_set(x), cache.minimum(x), cache.maximum(x)
cache.has_length(x, 3), cache.witness(x, 3), cache.witnesses(x)
cache.statistics()                                      # hits, misses, solver builds

aware = C2xC4.factorization_cache(catalogue, group=group)
aware.length_set(group.apply(a, x)) == aware.length_set(x)   # one solve per orbit
aware.witness(group.apply(a, x), 3)                     # transported back through a^-1

cache.to_jsonl("lengths.jsonl")                         # bound to catalogue.digest()
FactorizationCache.from_jsonl("lengths.jsonl", catalogue)
```

Length sets are kept without bound; solvers are kept in a bounded LRU
(`maxsize=`) so that follow-up questions about a recent sequence reuse its
remainder graph. With `group=` every query is keyed by a canonical form.
The default is the full canonical form, whose orbit traversal is worthwhile
when solving is the expensive part; for large groups pass
`canonicalize=AnchoredCanonicalizer(catalogue, group)`, which only
transports the largest atom dividing the sequence to its orbit
representative and reduces under that representative's stabilizer. Any
callable returning an automorphic image of its argument (optionally with the
automorphism) is accepted as `canonicalize=`.

## Benchmarks

Run the short-to-very-long performance corpus with:

```console
python -m benchmarks.benchmark_factorization --enumerate
```

The cases and their mathematical expectations are documented in
[`benchmarks/README.md`](https://github.com/behackl/zero-sum-sequences/blob/main/benchmarks/README.md).

## License

The source code is available under the MIT License.
