Tree Data Structure Redesign

Problem

The current nested-tuple tree representation requires full recursive traversal for every structural query (weight, arity, leaves, min_leaf, subtree_degree). Since these queries are called repeatedly in performance-critical paths—especially the bar/cobar differentials _d2_on_basis—this causes O(v²) or worse overhead per differential computation.

Current Representation

Trees are encoded as nested Python tuples:

• Leaf: int in {1, ..., n}

• Internal vertex: (decoration, child_1, ..., child_k) where decoration is an operad/cooperad basis key (a tuple) and each child_j is a leaf or subtree.

Example: ((1, 2), ((1,), 1, 2), 3) — arity 3, weight 2.

Bottlenecks

1. subtree_degree recomputation in _d2_on_basis: For each internal edge, the degrees of all sibling subtrees are recomputed from scratch. This is O(v² × lookup) per tree.

2. min_leaf recomputation in shuffle normalization: Called O(k) times per vertex during to_shuffle_tree_bar/cobar, each O(n) traversal.

3. leaves() recomputation: O(n) set union called in after_cobar_deg, tree_arity, validate_tree, and others.

4. weight() recomputation: O(v) recursive count called in enumeration.

5. Full recursive copy on every structural operation: relabel_leaves, graft, contract_edge, expand_vertex all rebuild the entire tree.

New Design: RootedTree Class

Core Idea

Replace nested tuples with an immutable RootedTree class that eagerly computes and caches structural properties at construction time. Since every tree operation already rebuilds the tree from scratch anyway, the per-node overhead of caching is amortized over the many subsequent queries.

Invariants

• Leaves remain as plain int values (no wrapping).

• RootedTree is immutable and hashable — works as SageMath @cached_method arguments and CombinatorialFreeModule basis keys.

• Identity comparison (is) continues to work for DFS-extracted vertices.

Cached Properties (computed at construction, O(1) access)

Property	Type	Old cost	New cost
weight	int	O(v)	O(1)
tree_arity	int	O(n)	O(1)
leaves	frozenset[int]	O(n)	O(1)
min_leaf	int	O(n)	O(1)
arity (vertex)	int	O(1)	O(1)
decoration	tuple	O(1)	O(1)
children	tuple	O(1)	O(1)

Construction Cost

Each RootedTree(decoration, children) call computes cached properties by merging child properties in O(k) time (where k = number of children). Since every tree modification already takes O(tree_size) for the recursive rebuild, this adds at most a constant factor per node during construction.

Class API

class RootedTree:
    __slots__ = (
        '_decoration', '_children', '_weight', '_tree_arity',
        '_leaves', '_min_leaf', '_arity', '_hash',
    )

    def __init__(self, decoration: tuple, *children):
        # children: tuple of (RootedTree | int)
        # Eagerly compute: weight, leaves, min_leaf, tree_arity

Comparison & Hashing

• __hash__: Based on (decoration, children) tuple — structurally equivalent trees hash identically.

• __eq__: Recursive structural comparison (with short-circuit on hash mismatch).

• __lt__: Lexicographic comparison for SageMath basis ordering.

Migration Strategy

1. Add RootedTree class to trees.py.

2. Update all functions in trees.py to accept and return RootedTree.

3. Add RootedTree.from_tuple() for backward compatibility.

4. Update bar/cobar constructions, tree_module, and morphisms.

5. Update tests.

Operations on RootedTree

All existing operations are preserved with the same semantics:

• relabel_leaves(tree, mapping) → returns new RootedTree

• graft(tree_top, i, tree_bot) → returns new RootedTree

• contract_edge(tree, parent, pos, dec) → returns new RootedTree

• expand_vertex(tree, target, pos, ...) → returns new RootedTree

• split_at_vertex(tree, target) → returns (RootedTree, int, RootedTree)

• vertices_dfs(tree) → returns list of RootedTree references (identity-safe)

Future Optimizations (Not in This PR)

• Degree caching: Store context-specific degrees (bar, cobar, free) via a degree_cache dict on each node. This would make subtree_degree O(1).

• Persistent/structural sharing: Use path-copying so that contract_edge only rebuilds nodes on the root-to-target path, sharing unchanged subtrees. This is already partially achieved since RootedTree children are references.

• Flat array representation: For very large trees, store nodes in a flat DFS-ordered array with parent/child indices for cache-friendly traversal.

---

Status Update (2026-04): Planar Coinvariant Enumeration

In parallel with tree-level optimization, profiling showed a separate dominant cost in cofree coalgebra basis enumeration: explicit S_n orbit-sum construction for invariants. The current implementation now enumerates planar representatives directly and canonicalizes boundary output back to planar keys.

Mathematical Setup

For invariants of the form

X ⊗_{S_n} Y with X = X_pl ⊗ k[S_n],

we use the canonical identification

(X_pl ⊗ k[S_n]) ⊗_{S_n} Y  ≅  X_pl ⊗ Y

to avoid explicit orbit sums in basis enumeration.

Boundary Strategies Compared

Two methods were tested.

1. Orbit-sum method (reference):

   • Build orbit-sum representative.

   • Apply boundary.

   • Renormalize to planar representatives.

2. Planar-first method:

   • Keep only planar representative in the basis.

   • Apply boundary there.

   • Canonicalize non-planar output terms to planar keys.

Result

The two methods are not coefficient-identical in general when the module tuple m has repeated entries. The difference is a stabilizer factor |Stab(m)|.

• Over QQ, this appears as multiplicative factors (for example factor 2 in binary symmetry cases).

• Over positive characteristic, this factor can vanish (for example 2 = 0 in GF(2)), so matrix entries can differ by zero/nonzero behavior.

Despite this, the two complexes are chain-isomorphic under the coinvariant identification above. The planar-first implementation satisfies d^2 = 0 and computes the same homology.

Implementation Notes

• basis_iter / basis_weight_iter enumerate planar terms term((c_pl, m)) directly (no orbit-sum construction during enumeration).

• Boundary matrix assembly canonicalizes non-planar terms via a full canonicalization routine that returns all planar contributions.

• This fixes a subtle lossy behavior from single-term canonicalization when planarization has multiple terms (for example with Lie-type factors).

Validation Summary

• d^2 = 0 checked at weights 2-4 over both QQ and GF(2).

• Regression tests added for planar basis counting/canonical keys and boundary canonicalization behavior.

• Observed speedup on heavy layers around 2.8x (example: 226s to 80s), with full test suite passing.