Archive Element Relations

Element relations — posets, adjacency, orbits on a collection's own elements

Carried over from the earlier enumeratio, and never built even there (a pglite-evaluated prototype only). The schema below (base_element_relation) is retired-architecture detail, kept for illustration; the open question is: should a collection's own elements carry first-class relations (poset covers, adjacency, group-action orbits), and should a poset's Hasse cover graph and a polytope's 1-skeleton be the same edge data? Neither is built in the current architecture; see Legacy Port §2.

Design chunk for issue #237 (friction 1 in the catalog audit). Grounded by a pglite-evaluated prototype: packages/data/sqlsrc/element_relations.sql (suite element_relations, green in the data gate). This doc is the proposal the maintainer reviews; the data batches, the Hasse figure, and the query-view wiring are deferred follow-ups modelled here, not built.

The gap

base_map / base_relation hold single-valued, cross-collection bijections (domain → codomain, an inverse, an is_order_iso flag). Nothing can hold a relation on a collection's own elements: a poset's covers (Tamari, weak, Bruhat, Young, dominance), a graph's adjacency, or a group action's orbits. That blocks the whole poset side of Sage/FindStat, Hasse diagrams, and orbit maps.

The model

CREATE TABLE base_element_relation (
  collection   text NOT NULL REFERENCES base_collection,
  rel_id       text NOT NULL,
  kind         text NOT NULL CHECK (kind IN ('cover', 'adjacency', 'equivalence')),
  forward_fn   text,          -- forward_fn(x carrier) RETURNS SETOF carrier: covers / neighbours / orbit of x
  related_fn   text,          -- related_fn(x, y carrier) RETURNS boolean: the pair predicate (no cheap successor)
  canonical_fn text,          -- equivalence only, OPTIONAL: idempotent representative map carrier→carrier
  title        text,
  findstat     text,
  PRIMARY KEY (collection, rel_id),
  CHECK (forward_fn IS NOT NULL OR related_fn IS NOT NULL),
  CHECK (canonical_fn IS NULL OR kind = 'equivalence'));

Three moving parts, all proven in the prototype:

1. It keys on ONE collection and returns CARRIER values. forward_fn(x carrier) RETURNS SETOF carrier. Because the carrier is shared across a collection's fibers, a relation can cross fibers with no separate codomain — Young's lattice returns partitions of n+1 from a partition of n, all on the one integer_partition carrier. This is the subtlety the ticket flagged; the prototype asserts every Young cover lands in the n+1 fiber and is a valid partition, n = 0..7.
2. related_fn is the fallback signature. A relation with no cheap single-step successor (a general order given only by a comparison — strong Bruhat given as x ≤ y, dominance) registers related_fn(x, y) RETURNS boolean instead. The CHECK requires at least one of the two.
3. canonical_fn is optional sugar for equivalences. An equivalence's kernel needs a representative. When a fast idempotent map exists (the necklace map word_canonical_rotation) it is named directly; when absent, the representative is derived as the rank-least member of forward_fn(x). The prototype asserts the two agree.

base_element_relation is its own registry, deliberately not a set-valued base_map — see crux (a).

The prototype (grounding)

Three relations spanning the kinds, evaluated in pglite:

collection	rel_id	kind	fn	what the examples prove
permutations	weak_order	cover (same fiber)	perm_weak_order_covers	every cover adds one inversion (graded); total covers on Sₙ = n!·(n−1)/2; unique maximum; undirected graph is (n−1)-regular; rank-GF = Mahonian 1,3,5,6,5,3,1
integer_partitions	young	cover (crosses fibers)	partition_young_covers	every cover lands in the n+1 fiber and is a valid partition (n=0..7); up-cover count = distinct-parts + 1
words	rotation	equivalence	word_rotation_orbit (+ word_canonical_rotation)	the orbit is a well-defined class (one shared representative); derived rep = declared canonical_fn; orbit count = the registered necklace restriction (Pólya), n=1..6

The permutations covers reuse perm_inversions; the equivalence reuses the existing word_canonical_rotation / is_word_necklace from symmetry_orbit_maps.sql, so GROUP BY orbit:rotation and the necklace collection are shown to be the same data.

The four cruxes

(a) A relation is its OWN kind, not a set-valued map

Recommendation: keep base_element_relation separate; do not model a cover as a base_map with a set-valued codomain. Grounded in the cross-fiber case:

• A base_map is single-valued and carries a codomain collection; a cover is multi-valued and endo on one collection, crossing fibers, not collections. The codomain semantics don't match.
• A map's metadata — inverse, is_bijection, is_order_iso — is meaningless for a multi-valued cover.
• The signatures differ: RETURNS SETOF carrier vs the map dispatcher's single-value %I(%s) template (map_compose.sql). One dispatcher cannot drive both.

Where the two registries meet is the kernel, not the relation: an equivalence's canonical_fn is an ordinary single-valued base_map (word_canonical_rotation already lives there), and GROUP BY orbit:<rel> reduces to GROUP BY map:<canonical_fn>. So relations compose through their representative map, and through: / kernels keep working — on the map, not on the set-valued relation.

Open for the maintainer: whether cover/adjacency relations should also auto-expose a derived related_fn (the reflexive-transitive closure predicate) for WHERE x ≤ y queries, or leave the closure to the query planner.

(b) GROUP BY orbit:<rel> and ORDER BY <rel>

Recommendation: both desugar onto existing machinery — no new kernel or sort primitive.

• GROUP BY orbit:<rel> = GROUP BY map:<canonical_fn> (#203's map kernel, kernels.md K0–K11), where the representative is the declared canonical_fn or the derived rank-least orbit member. The codomain is the collection itself restricted to representatives, so the key prints/links/sorts in the collection's own canonical order (K11). The prototype's orbit-count example is exactly this: count(DISTINCT word_canonical_rotation(e)) equals the necklace count — the Pólya count as a plain query, which is what symmetry_orbit_maps.sql already showed.
• ORDER BY <rel> is a linear extension of the cover DAG. For a graded relation this is ORDER BY rank(<rel>) (crux d) plus a tiebreak; grounded — weak order is graded by inversions (proven), so ORDER BY weak_order is ORDER BY inversions, <native rank>. A non-graded cover relation needs a materialized topological sort, feasible only on bounded fibers.

Open for the maintainer: the intra-rank tiebreak (a cover order is partial; a table row order is total). Default proposal: the collection's native rank as the tiebreak. And whether ORDER BY <rel> is offered at all on non-graded relations, or restricted to graded ones in v1.

(c) The Hasse figure and base_polytope are the same edge data

Recommendation: a cover relation's undirected graph is a polytope's 1-skeleton — register the relation as primary and let the polytope/Hasse figures read its edges; do not maintain two edge lists. Grounded:

• The permutahedron base_polytope already draws Sₙ's skeleton (its vertices are the permutations; its edges are adjacent transpositions). The prototype asserts the undirected weak_order cover graph on Sₙ is (n−1)-regular — which is exactly the permutahedron's vertex degree — and that its edge count is n!·(n−1)/2, the permutahedron's edge count. Same graph, two registries.
• So a Hasse figure (one SVG per fiber, drawn from the cover relation, ranked vertically by rank) and a polytope figure (base_polytope's projection) are two layouts of one edge set. The cover relation is the general object (it exists for posets with no polytope); base_polytope is the geometric realization when one exists.

Open for the maintainer: direction of the reference — does base_polytope gain an optional skeleton_rel pointing at a base_element_relation, or does the Hasse figure derive edges and base_polytope stay independent? Recommendation: the former (one edge source), but it can wait until the figure is built.

(d) Rank / interval / rank-GF are derived stats, not new columns

Recommendation: rank is a derived statistic computed from the relation; the rank-generating function is that stat's distribution (a #203 kernel); intervals are a bounded materialization. Grounded:

• Rank of x = length of a saturated chain from the minimum. For a graded poset it coincides with a known statistic — weak-order rank is perm_inversions (the prototype asserts each cover increments it). So rank(<rel>) registers as, or reuses, a base_stat.
• Rank-GF Σ q^rank = the rank stat's distribution: GROUP BY rank(<rel>), counts = coefficients. The prototype asserts the S₄ weak-order rank-GF is the Mahonian row 1,3,5,6,5,3,1 = the coefficients of the q-factorial [4]_q!. No new mechanism — it is the distribution archetype (#203) over the rank stat.
• Interval [x, y] = {z : x ≤ z ≤ y} from the closure of forward_fn; a bounded materialization (a figure/query concern), not a stored column.

Open for the maintainer: whether a graded relation should declare its rank stat (fast path, e.g. rank_stat = 'inversions') or always derive rank by chain-length from the cover DAG (correct but bounded). Recommendation: an optional rank_fn/rank_stat column, deriving when absent — mirroring canonical_fn.

Maintainer decision list

1. (a) Auto-expose a closure related_fn on cover/adjacency relations, or leave WHERE x ≤ y to the planner?
2. (b) Intra-rank tiebreak for ORDER BY <rel> — native rank by default? Offer ORDER BY <rel> on non-graded relations, or graded-only in v1?
3. (c) Reference direction for the skeleton: add base_polytope.skeleton_rel → base_element_relation, or keep the figures independent and derive edges? (Can defer to when the figure lands.)
4. (d) Declared rank_fn / rank_stat on graded relations (fast) with chain-length derivation as fallback — accept the optional-column pattern (as with canonical_fn)?
5. Registry scope: is the optional canonical_fn (and a future rank_fn) the right shape, or should these live in a sibling table keyed by (collection, rel_id) to keep base_element_relation narrow?
6. Cross-collection escape hatch: the model assumes a relation is endo on one collection (fibers may differ). If a genuinely cross-collection relation ever appears, add an optional codomain column defaulting to collection (mirroring base_map). Confirm we don't need it now.

Deferred (modelled here, not built)

• The Hasse figure — one SVG per fiber from the cover relation, ranked vertically; unified with base_polytope per crux (c). Explorer work.
• Query-view wiring — GROUP BY orbit:<rel> and ORDER BY <rel> in the query view, per crux (b). Landed (packages/client/src/rows.ts): GROUP BY orbit:<rel> / map:<map> desugar to the map kernel (a rendered class-representative column, bounded/naive — no registered sibling to accelerate against, so count(DISTINCT rep)); ORDER BY <graded cover> derives rank by chain length from a minimum, orders by it with the native rank as the intra-rank tiebreak, and disables-with-reason on a non-graded / successor-less / non-cover relation. Certified in selfcert-rows.mts. (The #203 map kernel itself was doc-only; the kernel substrate landed here.)
• The data batches (#237's list) — weak/Bruhat/cyclic-shift on permutations; Tamari/Stanley/Kreweras on Dyck paths; Young/dominance on partitions; refinement/non-crossing on set partitions and the Boolean lattice; conjugacy / Knuth / rotation equivalences. Each with cover-count, rank-GF, and lattice-property examples (floors and identities, no exact pins beyond n ≤ 4).