How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The rank-n diagram basis is counted by the nth Catalan number
Statement
For every , the set of noncrossing pairings of the boundary points is in bijection with the Dyck paths of semilength , and hence with balanced bracket words with pairs. It is finite with cardinality , so the free -module has a diagram basis indexed by exactly loop-free diagrams for every commutative ring and every .
Facts & Assumptions
Given: , the cyclically ordered top and bottom boundary labels in Temperley–Lieb planar diagram data and endomorphism modules, and the Catalan number .
The basis of is the set of noncrossing pairings of the top and bottom boundary points, read in cyclic order. (Temperley–Lieb planar diagram data and endomorphism modules)
The set of recursively balanced bracket words is exactly the set of equal-count words whose prefixes have at least as many opens as closes, and it is finite of cardinality . (Balanced bracket words, defined by the recursive grammar, is exactly the set of words of length over in which every prefix has at least as many as and the totals are equal, )
Sending an opening bracket to an up-step and a closing bracket to a down-step identifies balanced bracket words with Dyck paths of semilength , using the step-word bijection. (Dyck paths of semilength , For each start point the step word is a bijection onto )
Proof
Read the boundary labels in their fixed cyclic order. Given a noncrossing pairing, mark the earlier endpoint of each pair by an opening parenthesis and the later endpoint by a closing parenthesis. The resulting word has equal numbers of each kind. In every prefix, each closing endpoint is paired with an earlier opening endpoint in that prefix, so the number of closes never exceeds the number of opens; hence the word is balanced. This construction also applies at , where it gives the empty word.
Conversely, scan a balanced word from left to right, placing each opening position on a stack and pairing each closing position with the most recently placed unmatched opening. At the end the stack is empty because the total numbers agree. The pairs are nested or disjoint, so they do not interlace. For a noncrossing pairing, the same rule recovers its original partners: if a close at position were paired with an earlier open while a later open between them remained unmatched until after , then its eventual partner would give interlacing pairs and , contrary to [F1]. Thus the two constructions are inverse bijections.
Replace each opening bracket by an up-step and each closing bracket by a down-step. Equality of the bracket counts gives total height zero, and the prefix inequality proved in step 1.1 gives nonnegative prefix heights; hence this is a Dyck path of semilength . Reading its step word recovers the bracket word, so [F3] gives a bijection. By [F2] the bracket-word set is finite of size . Composing this bijection with the two inverse constructions in steps 1.1 and 2.1 proves that is in bijection with Dyck paths and has size . The free-module definition in [F1] makes these diagrams a basis of ; no coefficient is changed in this count.
Remarks
The cyclic boundary convention matters: the top points are read left to right and the bottom points right to left. This yields ordered endpoints and the semilength- Catalan convention, including the empty diagram at .
Depends on
- Temperley–Lieb planar diagram data and endomorphism modules
- Balanced bracket words, defined by the recursive grammar
- $\mathcal{B}_n$ is exactly the set of words of length $2n$ over $\{\texttt{(},\texttt{)}\}$ in which every prefix has at least as many $\texttt{(}$ as $\texttt{)}$ and the totals are equal
- $\lvert\mathcal{B}_n\rvert=C_n$
- Dyck paths of semilength $n$
- For each start point the step word is a bijection onto $S^n$
- The Catalan number $C_n:=\lvert\mathcal{D}_n\rvert$
Used by
Dependency tree · two levels
22 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- David Ridout and Yvan Saint-Aubin, Standard Modules, Induction and the Structure of the Temperley-Lieb Algebra, §2 (standard reference, not scraped)
- David Guichard, Combinatorics and Graph Theory, Section 3.5: Catalan Numbers (standard reference, not scraped)
- Dana C. Ernst, Michael G. Hastings, and Sarah K. Salmon, Factorization of Temperley–Lieb diagrams (standard reference, not scraped)