Fast factorization in diagram monoids

1. Introduction

• Minimal runtime concerns how quickly an algorithm finds any valid factorization, whereas shortest-word length measures the minimum number of generators.A short factorization need not be easy to find, and a fast algorithm need not return a shortest one.Source: §1 · p. 2
• The treatment prioritizes established diagram monoids, leaving extension to other families as an open question.The authors name annular, blob, and framed monoids among possible extensions.Source: §1 · p. 3
• The factorization problem generalizes sorting by expressing diagrams in standard local generators that act on at most four adjacent vertices.The diagram families include structures allowing same-row pairs, isolated vertices, larger blocks, or planarity constraints.Source: §1 · p. 3
• For all nine families, O(n^2) factorization algorithms match the Ω(n^2) lower bound for explicitly writing the factors, so worst-case runtime is asymptotically optimal.The produced words need not be shortest.Source: §1 · p. 4
• Average runtimes are Θ(n^3/2) for planar monoids and Θ(n^2) for symmetric monoids, making quadratic behavior typical in some families and exceptional in others.The paper attributes the planar distinction to restricted displacement and nesting in random diagrams.Source: §1 · p. 4
• The average analysis identifies combinatorial features behind the algorithms’ work, using tools including Dyck paths, Motzkin numbers, Bell numbers, and the Lambert W function.The precise averages explain the reported exponents.Source: §1 · p. 4
• The paper presents a uniform treatment of explicit algorithms, optimal worst-case runtimes, and average word lengths for the standard diagram-monoid families it considers.The averages use uniformly chosen diagrams.Source: §1 · p. 5
• For proposed noncommutative cryptographic platforms, the algorithms provide computational infrastructure but neither solve factorization search nor establish protocol security.Exploring this application further is identified as a future goal.Source: §1 · p. 5

• A degree-n partition diagram is a set partition of two rows of n vertices, where only block connectivity matters and crossings add no vertices.Source: §2 · p. 6
• Brauer diagrams have size-two blocks, rook–Brauer blocks have size at most two, and rook diagrams allow singleton blocks or transversal pairs.Source: §2 · p. 6
• Planar submonoids include Temperley–Lieb, planar rook, Motzkin, and planar partition monoids; planar rook diagrams are order-preserving partial bijections.Source: §2 · p. 6
• The local generators p_i join adjacent top and bottom vertices into one block, e_i pairs adjacent vertices within each row, s_i swaps neighboring transversal strings, and d_i creates two singleton blocks.Source: §2 · p. 7
• Runtime includes the cost of writing the output, and the reported averages use the uniform distribution on the relevant monoid family.Source: §2 · pp. 8–9
• The general method factors top blocks first, transversal blocks next, and bottom blocks last; nonplanar cases also require top and bottom permutations, while partition diagrams need an extra step for arbitrary-size blocks.Source: §2 · p. 8
• Returned words need not be minimal, but their worst-case lengths have optimal order of growth, and the algorithms are easy to implement.Source: §2 · p. 8

3A. Temperley–Lieb

• The rainbow diagram forces at least n^2/4 factors for even n and (n^2−1)/4 for odd n, making quadratic worst-case complexity necessary for Temperley–Lieb factorization.These bounds are also the reduced lengths of the rainbow diagrams.Source: Figure 1 · p. 9, §3 · p. 9
• Algorithm 1 factors every Temperley–Lieb diagram in O(n + L(X)) time, where L(X) is its output length, and its worst-case complexity is Θ(n^2).The algorithm’s words need not be reduced; its correctness follows from the block-processing order.Source: §3 · pp. 9, 11, 12
• The paper derives the average output length and average runtime of Algorithm 1 for Temperley–Lieb diagrams.The supplied passages state that the runtime uses the step count T(X) = 2n + 2L(X), but omit the displayed average formulas.Source: §3 · p. 13

3B. Planar Rook

• Any algorithm factoring every planar rook diagram into the chosen generators {ri, li} has worst-case complexity Ω(n^2); Algorithm 2 has worst-case complexity Θ(n^2).Source: §3 · pp. 13, 16
• Algorithm 2 factors every planar rook diagram in O(n + L(X)) time by processing singleton dots and order-preserving strings in the order forced by planarity.The proof states that the algorithm reads 2n labels and writes L(X) generators.Source: §3 · p. 14
• The paper derives the average output length and average runtime of Algorithm 2 for planar rook diagrams.The supplied passages state that the runtime uses T(X) = 2n + 2L(X), but omit the displayed average formulas.Source: §3 · p. 16

3C. Motzkin

• Every factorization algorithm for Mon using {e_i, r_i, l_i} has worst-case output length Ω(n^2), and the rainbow diagram yields a lower bound of ⌊n^2/4⌋ factors.The rainbow’s edges cross the vertical cuts Θ(n^2) times, while each generator accounts for at most two crossings.Source: §3 · p. 16
• Algorithm 3 factors every X ∈ Mon in O(n + L(X)) time by assembling words for singleton blocks, cups, transversal pairs, and caps.The construction uses vertical reflection for caps and orders local words so planarity prevents interference.Source: §3 · p. 17
• The expected worst-case complexity is Θ(n^2), and the bounds are attained by Motzkin rainbow diagrams; maxima for n = 2 and n = 4 are 8 and 16, respectively.Source: §3 · pp. 18–19
• The section derives average output-length and runtime results for Algorithm 3, using the step count T(X) = 2n + 2L(X).The supplied passages do not expose the full average formulas.Source: §3 · p. 19

3D. Planar Partition

• Fattening computes the planar-partition map Φ in O(n) time and maps each generator e_j to d_(j+1)/2 for odd j or p_j/2 for even j.The map is the standard fattening of a noncrossing partition.Source: §3 · p. 20
• Any algorithm that factors every X ∈pPan into a product of generators {pi, dj} has worst-case complexity Ω(n^2); Algorithm 5 factors every X ∈pPan in worst-case O(n^2).Source: §3 · pp. 20–21
• The average output-length analysis for Algorithm 5 transfers from Temperley–Lieb diagrams through a uniform-distribution bijection that preserves word length, with linear fattening cost added to runtime.The supplied passages do not expose the full average formula.Source: §3 · p. 21

4A. Symmetric Group

• Algorithm 6 uses a Fenwick tree to factor permutations with n log(n) + O(#factors) work, where #factors is the inversion number, and has optimal Θ(n^2) worst-case complexity.The reverse permutation attains the maximum inversion number, yielding the quadratic worst case.Source: §4 · p. 22
• The average complexity of Algorithm 6 follows from the average inversion number under the uniform distribution on permutations.Each pair contributes an inversion with probability one half; the passage's displayed final formula is incomplete.Source: §4 · p. 22
• Brauer, rook, Rook–Brauer, and partition monoids share an Ω(n^2) worst-case lower bound because extra generators cannot shorten a reverse-permutation factorization.The reverse permutation has n through strands, while each additional generator has fewer, and multiplication cannot increase the number of through strands.Source: §4 · p. 22

4B. Brauer

• For Brauer diagrams, Algorithm 7 creates standard cups and caps, then uses two symmetric-group factorizations to place them and the surviving strands, giving Θ(n^2) worst-case complexity.Its cost is O(n) plus the cost of factoring the two permutations with Algorithm 6.Source: §4 · pp. 23–24
• The Brauer average analysis separates the cup/cap generators from the inversion counts of the two permutations; the total average is stated asymptotically.The supplied passages do not preserve the displayed asymptotic formulas.Source: §4 · pp. 24–25

4C. Rook

• The rook construction replaces Brauer cups and caps with dots: dot generators place them initially, and two permutations move the dots and remaining strings to their required positions.The supplied rook passages introduce this construction and its algorithm.Source: §4 · p. 26

Factorization algorithm

• Algorithm 8 factors every X ∈ R_on with computational complexity O(n) + O(sym).It constructs standard-position dots and strings, then uses symmetric-group factorizations to move them to the endpoints of X.Source: §4 · p. 26

Complexity

• Θ(n^2) is Algorithm 8’s worst-case complexity.This follows together with Proposition 4A.6.Source: §4 · p. 27

Average complexity

• The average analysis separates the dot portion from the permutation portion of Algorithm 8.The dot portion is counted by the number of dots; the permutation portion sums inversion numbers, where top-half dot–line swaps and bottom-half line–line swaps contribute.Source: §4 · pp. 27–28

• The preceding average-complexity result is stated asymptotically as 8 + 2n log(n) · n! Pn.Source: §2 · p. 28

4D. Rook–Brauer; 4E. Partition

• Θ(n^2) is the worst-case complexity of both the rook–Brauer and partition factorization algorithms.For rook–Brauer, the algorithm has complexity O(n) + O(sym); for partitions, the construction uses top and bottom permutations and a planar-rook middle factorization.Source: §2 · pp. 28, 31

4D. Rook–Brauer

• The total average complexity for the rook–Brauer algorithm is asymptotically 2/8 n^(3/2) + 45/8 n.Its local cup/cap and dot contribution and its permutation contribution are analyzed separately before being combined.Source: §2 · pp. 28, 30

4E. Partition

• The partition algorithm builds standard top and bottom blocks, rearranges them with permutations, and uses a planar-rook middle diagram to encode transversal blocks.Unused positions in the middle become dots, and the top, middle, and bottom words are concatenated.Source: §2 · p. 31
• The average number of generators p1, ..., pn−1 in partition-diagram factorizations is SPa_n ∼ 2n − 4n W(2n).The average-cost analysis treats the p generators, the two permutation words, and the planar-rook middle word as three contributions.Source: §2 · p. 31

2. Hence

• Proposition 4E.5 gives an asymptotic average-complexity result for the permutation portion of Algorithm 10.Its displayed formula is not legible in the supplied passages.Source: §2 · p. 33
• The planar-rook portion’s transversal-block contribution dominates its dot contribution in the average-complexity analysis.Dots contribute one generator each when a block has unequal numbers of top and bottom vertices; the analysis concludes that this contribution is dominated by the transversal contribution.Source: §2 · pp. 34–35
• The average complexity of Algorithm 10 is obtained by combining the analyzed permutation and planar-rook portions.The supplied passages state the combined result but do not expose its full formula legibly.Source: §2 · p. 35

5. Experimental Average Complexity

• Monte Carlo estimates match the theoretical average results in Table 1.The experiments compare average factorization lengths to avoid differences arising from software and hardware.Source: §5 · p. 35
• Figure 3 plots average factorization length ratios across n = 100 to 5000, with Pan stopping at n = 1000 because of computation time.Each estimate uses 1000 Monte Carlo samples.Source: Figure 3 · p. 36
• The figure captions report AFL normalized by n^(3/2) for Mon and pPan, and by n^2 for Sn, Brn, RoBrn, and Ron, respectively.Source: §5 · pp. 36–37