strings

quiverlab.strings

The gentle / string subsystem (Plan 46 / C5).

Butler-Ringel string & band module classification, string-module tau by hooks/cohooks, the Avella-Alaminos-Geiss derived invariant for gentle algebras, and the algebra-only strings compute block. Everything is exact combinatorics + exact linear algebra over a Domain; float-free by design.

Public surface (reach via import quiverlab or quiverlab.strings): - walks: Letter alphabet, string_signs, is_valid_walk, enumerate_strings, find_bands, StringCensus. - modules: string_module, band_module. - ar_strings: string_tau, string_tau_minus. - ag: permitted_threads, forbidden_threads, ag_invariant, AGInvariant. - block: strings_block.

AGInvariant dataclass

AGInvariant(pairs: tuple)

The AG invariant: a MULTISET of (n, m) pairs (sorted). n counts the permitted threads in an AAG-orbit, m the forbidden-thread arrows; a cyclic forbidden thread gives (0, m). A DERIVED invariant, honestly NOT complete.

ag_invariant

ag_invariant(A) -> AGInvariant

The Avella-Alaminos-Geiss derived invariant of the gentle algebra A. Loud on non-gentle input. DERIVED-INVARIANT, NOT COMPLETE (documented).

Source code in src/quiverlab/strings/ag.py

def ag_invariant(A) -> AGInvariant:
    """The Avella-Alaminos-Geiss derived invariant of the gentle algebra ``A``.
    Loud on non-gentle input. DERIVED-INVARIANT, NOT COMPLETE (documented)."""
    _require_gentle(A)
    Mp, Mf, orig = _blossom_matchings(A)
    source_blossoms = [a for a in Mp if _is_blossom_in(a)]

    # permitted path from each source blossom: follow M_p to a sink blossom
    ends = {}          # source blossom -> ending blossom-out tau
    for s in source_blossoms:
        cur = s
        while True:
            nxt = Mp[cur]
            if _is_blossom_out(nxt):
                ends[s] = nxt
                break
            cur = nxt

    # antipath ending at tau_p: follow M_f backward to a source blossom = Phi(p);
    # count the original arrows crossed (the forbidden-thread length delta_p)
    Mf_inv = {out: inp for inp, out in Mf.items()}
    Phi, anti_len = {}, {}
    for s in source_blossoms:
        cur = ends[s]
        length = 0
        while True:
            pred = Mf_inv[cur]
            if _is_blossom_in(pred):
                Phi[s] = pred
                break
            length += 1
            cur = pred
        anti_len[s] = length

    # orbits of Phi -> pairs (|orbit|, sum forbidden lengths)
    pairs = []
    seen = set()
    for s in source_blossoms:
        if s in seen:
            continue
        orbit = []
        cur = s
        while cur not in seen:
            seen.add(cur)
            orbit.append(cur)
            cur = Phi[cur]
        n = len(orbit)
        m = sum(anti_len[t] for t in orbit)
        pairs.append((n, m))

    # cyclic forbidden threads (anticycles) -> (0, length)
    seen2 = set()
    for a in orig:
        if a in seen2:
            continue
        cyc, cur, cyclic = [], a, True
        while True:
            cyc.append(cur)
            seen2.add(cur)
            nxt = Mf.get(cur)
            if nxt is None or _is_blossom(nxt):
                cyclic = False
                break
            if nxt == a:
                break
            if nxt in seen2:
                cyclic = False
                break
            cur = nxt
        if cyclic:
            pairs.append((0, len(cyc)))

    return AGInvariant(tuple(sorted(pairs)))

band_module

band_module(A, walk, eigenvalue, mult=1, name=None)

The band module M(walk, lambda, mult): a cyclic string of length L; dim = mult * L. Identity mult x mult blocks for all letters but the closing one, which carries J_mult(lambda) -- the loop monodromy is a single Jordan block, so the module is indecomposable for any nonzero lambda in the field. eigenvalue MUST be a nonzero field element (coerced via A.domain) -- loud otherwise. Self-certifies via check_module.

Source code in src/quiverlab/strings/modules.py

def band_module(A, walk, eigenvalue, mult=1, name=None):
    """The band module ``M(walk, lambda, mult)``: a cyclic string of length ``L``;
    dim = ``mult * L``. Identity ``mult x mult`` blocks for all letters but the closing
    one, which carries ``J_mult(lambda)`` -- the loop monodromy is a single Jordan
    block, so the module is indecomposable for any nonzero ``lambda`` in the field.
    ``eigenvalue`` MUST be a nonzero field element (coerced via ``A.domain``) -- loud
    otherwise. Self-certifies via ``check_module``."""
    if A.quiver is None or A.relations is None:
        raise QuiverlabError("strings: band_module needs a quiver-presented algebra",
                             hint="build the algebra via Quiver.algebra(...)")
    if mult < 1:
        raise QuiverlabError("strings: band multiplicity must be >= 1")
    dom = A.domain
    try:
        lam = dom.coerce(eigenvalue)
    except Exception as exc:
        raise QuiverlabError(
            f"strings: band eigenvalue {eigenvalue!r} is not in the field",
            hint="the eigenvalue must be a nonzero element of A.domain") from exc
    if dom.is_zero(lam):
        raise QuiverlabError("strings: band eigenvalue must be nonzero")
    # primitive-band guard (devil's-advocate fix, 2026-08-05): a proper power
    # b^k materialises as a DECOMPOSABLE module -- silently wrong under the
    # docstring's indecomposability promise. Refuse loudly instead.
    from quiverlab.strings.walks import _is_band_walk, _is_proper_power
    if _is_proper_power(tuple(walk)):
        raise QuiverlabError(
            "strings: the walk is a proper power of a shorter band -- a band "
            "module needs a PRIMITIVE band",
            hint="pass the primitive band once and use mult= for multiplicity")
    if not _is_band_walk(A, tuple(walk)):
        raise QuiverlabError(
            "strings: the walk is not a band (cyclic, reduced, composable, "
            "relation-avoiding at the closure)",
            hint="find_bands(A) enumerates the primitive bands")
    Q = A.quiver
    L = len(walk)
    if L < 1:
        raise QuiverlabError("strings: a band walk must have length >= 1")
    verts = [letter_source(Q, walk[k]) for k in range(L)]
    dim = L * mult
    vertex_of_index = [verts[k] for k in range(L) for _ in range(mult)]
    action = {a: lm.zeros(dim, dim, dom) for a in Q.arrows}
    for k, (nm, d) in enumerate(walk):
        if d > 0:                                      # arrow: block k -> block (k+1)
            src_blk, tgt_blk = k, (k + 1) % L
        else:                                          # inverse letter
            src_blk, tgt_blk = (k + 1) % L, k
        B = _jordan(mult, lam, dom) if k == L - 1 else lm.identity(mult, dom)
        for r in range(mult):
            for c in range(mult):
                action[nm][tgt_blk * mult + r][src_blk * mult + c] = B[r][c]
    return _materialise(A, vertex_of_index, action, name or "band")

enumerate_strings

enumerate_strings(A, max_length=8, budget=4096)

Enumerate the string modules of a string algebra as canonical reduced walks.

HONEST CONTRACT: status == "complete" ONLY when find_bands(A, max_length) is empty (rep-finite) AND the depth-first search closed within budget without any walk hitting max_length -- then the list is ALL indecomposable string modules (every non-band indecomposable). Bands present, or a budget/length cut, => status == "budget" (a length-capped sample, never a "complete" claim).

Every valid walk is reached as a right-extension prefix from its first letter (all prefixes of a valid walk are valid), so no left-growth is needed; the output is canonicalised up to inversion.

Source code in src/quiverlab/strings/walks.py

def enumerate_strings(A, max_length=8, budget=4096):
    """Enumerate the string modules of a string algebra as canonical reduced walks.

    HONEST CONTRACT: ``status == "complete"`` ONLY when ``find_bands(A, max_length)``
    is empty (rep-finite) AND the depth-first search closed within ``budget`` without
    any walk hitting ``max_length`` -- then the list is ALL indecomposable string
    modules (every non-band indecomposable). Bands present, or a budget/length cut,
    => ``status == "budget"`` (a length-capped sample, never a "complete" claim).

    Every valid walk is reached as a right-extension prefix from its first letter
    (all prefixes of a valid walk are valid), so no left-growth is needed; the output
    is canonicalised up to inversion.
    """
    _require_string(A)
    rs = reduction_system_of(A)
    Q = A.quiver
    alphabet = [(a, +1) for a in Q.arrows] + [(a, -1) for a in Q.arrows]
    out = set()
    state = {"truncated": False}

    for v in Q.vertices:                               # trivial walks = the simples
        out.add(((None, v),))

    def dfs(walk):
        out.add(_canonical(walk))
        if len(out) > budget:
            state["truncated"] = True
            return
        children = [walk + (ell,) for ell in alphabet]
        children = [c for c in children if is_valid_walk(A, c, rs)]
        if len(walk) >= max_length:
            if children:
                state["truncated"] = True
            return
        for c in children:
            dfs(c)

    for ell in alphabet:
        dfs((ell,))

    bands = find_bands(A, max_length)
    walks = tuple(sorted(out, key=_sort_key))
    complete = (not bands) and (not state["truncated"])
    return StringCensus(walks, "complete" if complete else "budget",
                        max_length, len(walks), bool(bands))

find_bands

find_bands(A, max_length=8)

Canonical band walks (cyclic strings) of length <= max_length.

A band is a cyclic reduced walk of length >= 1, not a proper power, containing BOTH a direct and an inverse letter (a pure directed / pure inverse cycle is not a band), every rotation a valid walk. Non-empty => A is rep-INFINITE.

Source code in src/quiverlab/strings/walks.py

def find_bands(A, max_length=8):
    """Canonical band walks (cyclic strings) of length <= ``max_length``.

    A band is a cyclic reduced walk of length >= 1, not a proper power, containing
    BOTH a direct and an inverse letter (a pure directed / pure inverse cycle is not
    a band), every rotation a valid walk. Non-empty => ``A`` is rep-INFINITE."""
    _require_string(A)
    rs = reduction_system_of(A)
    Q = A.quiver
    alphabet = [(a, +1) for a in Q.arrows] + [(a, -1) for a in Q.arrows]
    bands, seen = [], set()

    def closes(walk):
        return (letter_target(Q, walk[-1]) == letter_source(Q, walk[0])
                and walk[0] != invert(walk[-1])
                and is_valid_walk(A, walk + (walk[0],), rs))          # wrap pair ok

    def is_band(walk):
        if {d for _, d in walk} != {+1, -1}:            # pure directed/inverse cycle
            return False
        if _is_proper_power(tuple(walk)):
            return False
        return all(is_valid_walk(A, rot, rs) for rot in _rotations(tuple(walk)))

    def grow(walk):
        if len(walk) >= 1 and closes(walk) and is_band(walk):
            cw = _canonical_cyclic(walk)
            if cw not in seen:
                seen.add(cw)
                bands.append(cw)
        if len(walk) >= max_length:
            return
        end = letter_target(Q, walk[-1])
        for ell in alphabet:
            if letter_source(Q, ell) == end and is_valid_walk(A, walk + (ell,), rs):
                grow(walk + (ell,))

    for ell in alphabet:
        grow((ell,))
    return bands

forbidden_threads

forbidden_threads(A)

Maximal paths of relations (forbidden threads / antipaths), as arrow-name tuples. Partition Q_1 (gentle); a cyclic forbidden thread is one tuple.

Source code in src/quiverlab/strings/ag.py

def forbidden_threads(A):
    """Maximal paths of relations (forbidden threads / antipaths), as arrow-name
    tuples. Partition ``Q_1`` (gentle); a cyclic forbidden thread is one tuple."""
    _require_gentle(A)
    _p, _pp, f_succ, f_pred = _succ_maps(A)
    return _threads(list(A.quiver.arrows), f_succ, f_pred)

invert

invert(ell)

The formal inverse of a letter. A trivial letter (None, v) is its own inverse (reversing a one-vertex walk yields itself).

Source code in src/quiverlab/strings/walks.py

def invert(ell):
    """The formal inverse of a letter. A trivial letter ``(None, v)`` is its own
    inverse (reversing a one-vertex walk yields itself)."""
    name, d = ell
    return ell if name is None else (name, -d)

is_valid_walk

is_valid_walk(A, walk, rs=None)

Composable, reduced, relation-avoiding, and sign-consistent.

Source code in src/quiverlab/strings/walks.py

def is_valid_walk(A, walk, rs=None):
    """Composable, reduced, relation-avoiding, and sign-consistent."""
    Q = A.quiver
    if not walk or _is_trivial(walk):
        return True                                   # trivial walk e_v is valid
    if rs is None:
        rs = reduction_system_of(A)
    for i in range(len(walk) - 1):
        if letter_target(Q, walk[i]) != letter_source(Q, walk[i + 1]):
            return False                              # not composable
        if walk[i + 1] == invert(walk[i]):
            return False                              # not reduced (backtrack)
        if not _pair_ok(rs, walk[i], walk[i + 1]):
            return False                              # hits a relation
    return _signs_consistent(A, walk)

permitted_threads

permitted_threads(A)

Maximal nonzero directed paths (permitted threads), as arrow-name tuples. Partition Q_1 (gentle).

Source code in src/quiverlab/strings/ag.py

def permitted_threads(A):
    """Maximal nonzero directed paths (permitted threads), as arrow-name tuples.
    Partition ``Q_1`` (gentle)."""
    _require_gentle(A)
    p_succ, p_pred, _f, _fp = _succ_maps(A)
    return _threads(list(A.quiver.arrows), p_succ, p_pred)

string_module

string_module(A, walk, name=None)

The string module M(walk): dim = #vertices on the walk = len(walk)+1, basis z_0..z_n one per visited vertex, each direct/inverse letter a 0/1 partial map. Self-certifies via check_module.

Source code in src/quiverlab/strings/modules.py

def string_module(A, walk, name=None):
    """The string module ``M(walk)``: dim = #vertices on the walk = len(walk)+1, basis
    ``z_0..z_n`` one per visited vertex, each direct/inverse letter a 0/1 partial map.
    Self-certifies via ``check_module``."""
    if A.quiver is None or A.relations is None:
        raise QuiverlabError("strings: string_module needs a quiver-presented algebra",
                             hint="build the algebra via Quiver.algebra(...)")
    if not _is_trivial(walk) and not is_valid_walk(A, walk):
        raise QuiverlabError(f"strings: {walk!r} is not a valid string over A",
                             hint="use enumerate_strings(A) to get valid walks")
    Q, dom = A.quiver, A.domain
    verts = _walk_vertices(A, walk)
    n = len(verts)
    action = {a: lm.zeros(n, n, dom) for a in Q.arrows}
    if not _is_trivial(walk):
        for i, (nm, d) in enumerate(walk):
            if nm is None:
                continue
            if d > 0:                                  # direct: z_i |-> z_{i+1}
                action[nm][i + 1][i] = dom.one()
            else:                                      # inverse: transposed slot
                action[nm][i][i + 1] = dom.one()
    return _materialise(A, verts, action, name or _walk_name(walk))

string_signs

string_signs(A)

(sigma, epsilon): Q_1 -> {+1,-1}.

(S1) arrows with equal SOURCE get distinct sigma; (S2) arrows with equal TARGET get distinct epsilon; (S3) for beta*gamma NOT in I with target(beta)=source(gamma), sigma(gamma) = -epsilon(beta). Built greedily from the (<=2) branches at each vertex and reconciled for (S3); a string algebra always admits such an assignment. Loud if A is not a string algebra, or the constraints are inconsistent. Memoised by id(A).

Source code in src/quiverlab/strings/walks.py

def string_signs(A):
    """``(sigma, epsilon)``: ``Q_1 -> {+1,-1}``.

    (S1) arrows with equal SOURCE get distinct ``sigma``; (S2) arrows with equal
    TARGET get distinct ``epsilon``; (S3) for ``beta*gamma`` NOT in ``I`` with
    ``target(beta)=source(gamma)``, ``sigma(gamma) = -epsilon(beta)``. Built
    greedily from the (<=2) branches at each vertex and reconciled for (S3); a
    string algebra always admits such an assignment. Loud if ``A`` is not a string
    algebra, or the constraints are inconsistent. Memoised by ``id(A)``."""
    _require_string(A)
    key = id(A)
    hit = _SIGNS_CACHE.get(key)
    if hit is not None and hit[0] is A:
        return hit[1]
    Q = A.quiver
    rs = reduction_system_of(A)
    arrows = list(Q.arrows)
    sigma, epsilon = {}, {}
    for v in Q.vertices:
        outs = [a for a in arrows if Q.source(a) == v]
        for i, a in enumerate(outs):
            sigma[a] = 1 if i == 0 else -1
        ins = [a for a in arrows if Q.target(a) == v]
        for i, a in enumerate(ins):
            epsilon[a] = 1 if i == 0 else -1
    # (S3): reconcile via the nonzero composable pairs. Propagate; if a forced
    # value contradicts an assigned one even after a single class-flip, raise.
    for b in arrows:
        for g in arrows:
            if Q.target(b) == Q.source(g) and not _len2_in_ideal(rs, b, g):
                want = -epsilon[b]
                if sigma[g] != want:
                    _flip_sigma_class(Q, sigma, Q.source(g))
                    if sigma[g] != want:
                        raise QuiverlabError(
                            "strings: sigma/epsilon constraints are inconsistent",
                            hint=f"arrows {b!r}, {g!r} force a contradictory sign; "
                                 "the algebra may violate the string branch condition")
    result = (sigma, epsilon)
    _SIGNS_CACHE[key] = (A, result)
    return result

string_tau

string_tau(A, walk)

The walk w' with string_module(w') ~ tau(string_module(walk)), by the Butler-Ringel hook/cohook combinatorics -- arbitrated against the trusted engine translate. None when M(walk) is projective (tau = 0).

HONESTY NOTE (devil's-advocate round, 2026-08-05): this function COMPUTES the engine translate Module.tau() on every call and then identifies a walk presentation for it (combinatorial rule first, census fallback), with is_isomorphic verification before anything is returned. It is neither faster than nor independent of the engine tau -- its value is the WALK (the combinatorial presentation the engine does not provide). It can raise where the engine succeeds (no walk found within budget); it can never return a wrong walk.

Source code in src/quiverlab/strings/ar_strings.py

def string_tau(A, walk):
    """The walk ``w'`` with ``string_module(w') ~ tau(string_module(walk))``, by the
    Butler-Ringel hook/cohook combinatorics -- arbitrated against the trusted engine
    translate. ``None`` when ``M(walk)`` is projective (``tau = 0``).

    HONESTY NOTE (devil's-advocate round, 2026-08-05): this function COMPUTES
    the engine translate ``Module.tau()`` on every call and then identifies a
    walk presentation for it (combinatorial rule first, census fallback), with
    ``is_isomorphic`` verification before anything is returned. It is neither
    faster than nor independent of the engine tau -- its value is the WALK
    (the combinatorial presentation the engine does not provide). It can raise
    where the engine succeeds (no walk found within budget); it can never
    return a wrong walk."""
    T = string_module(A, walk).tau()
    if T.dim == 0:
        return None
    return _walk_of_module(A, T, prefer=_combinatorial_tau(A, walk))

string_tau_minus

string_tau_minus(A, walk)

The walk w' with string_module(w') ~ tau^-(string_module(walk)). None when M(walk) is injective (tau^- = 0).

Source code in src/quiverlab/strings/ar_strings.py

def string_tau_minus(A, walk):
    """The walk ``w'`` with ``string_module(w') ~ tau^-(string_module(walk))``.
    ``None`` when ``M(walk)`` is injective (``tau^- = 0``)."""
    T = string_module(A, walk).tau_minus()
    if T.dim == 0:
        return None
    return _walk_of_module(A, T, prefer=_combinatorial_tau_minus(A, walk))

strings_block

strings_block(A)

The strings no-code compute block: recognizer verdicts + string census + band presence + rep-type + (gentle) AG invariant. SHARED by both runners.

Source code in src/quiverlab/strings/block.py

def strings_block(A):
    """The ``strings`` no-code compute block: recognizer verdicts + string census +
    band presence + rep-type + (gentle) AG invariant. SHARED by both runners."""
    from quiverlab.strings.ag import ag_invariant
    from quiverlab.strings.walks import enumerate_strings, find_bands

    recognizers = {
        "is_special_biserial": _guard(lambda: is_special_biserial(A)),
        "is_string": _guard(lambda: is_string(A)),
        "is_gentle": _guard(lambda: is_gentle(A)),
    }

    strings = None
    bands = None
    rep_type = "unknown"
    ag = None
    note = None

    string_ok = recognizers["is_string"] is True
    if string_ok:
        try:
            cen = enumerate_strings(A, max_length=_MAX_LENGTH)
            strings = {
                "count": cen.count,
                "status": cen.status,
                "max_length": cen.max_length,
                "sample": [_walk_repr(w) for w in cen.walks[:_SAMPLE]],
            }
            band_walks = find_bands(A, max_length=_MAX_LENGTH)
            bands = {
                "exist": bool(band_walks),
                "sample": [_walk_repr(b) for b in band_walks[:_SAMPLE]],
            }
            # rep-finite iff no bands AND the census closed (honest contract).
            if band_walks:
                rep_type = "infinite"
            elif cen.status == "complete":
                rep_type = "finite"
            else:
                rep_type = "unknown"
        except Exception as exc:
            note = f"string census unavailable: {exc}"
    else:
        note = ("not a string algebra: strings/bands/rep-type are defined for "
                "special-biserial monomial kQ/I")

    if recognizers["is_gentle"] is True:
        try:
            inv = ag_invariant(A)
            ag = [[n, m] for (n, m) in inv.pairs]
        except Exception as exc:
            ag = {"error": str(exc)}

    block = {
        "recognizers": recognizers,
        "strings": strings,
        "bands": bands,
        "rep_type": rep_type,
        "ag_invariant": ag,
        "references": ["butler_ringel", "avella_geiss", "assem_book"],
    }
    if note is not None:
        block["note"] = note
    return block