Counting intersections of normal curves (Q2153340)

The paper concerns computational aspects of mapping class groups \(\mathrm{MCG}(M,\mathcal{P})\) of punctured surfaces. A presentation of elements of \(\mathrm{MCG}(M,\mathcal{P})\) by specific integral \(N\times N\) matrices is proposed, with \(N\) depending on the surface and the number of punctures. To define the matrix presentation, a triangulation \(T\) is fixed on \(M\), with vertices at \(\mathcal{P}\). Elements of a certain subset of \(\mathbb{Z}^N\), where \(N\) is the number of edges of \(T\), are interpreted as multiple curves on \(M\), encoded by their normal coordinates with respect to \(T\). For any two multiple curves \(\gamma,\gamma'\), one defines their geometric intersection number, denoted by \(\langle\gamma,\gamma'\rangle\). A mapping class \(g\in\mathrm{MCG}(M,\mathcal{P})\) can be recovered uniquely from the intersection matrix \(\langle T,g(T)\rangle\), whose \((ij)\)th entry is \(\langle T,g(T)\rangle_{ij}=\langle e_i,g(e_j)\rangle\), where \(e_i\) is the \(i\)th edge of \(T\). The key question about the efficiency of this presentation is how to compute \(\langle T,g_1(g_2(T))\rangle\) from \(\langle T,g_1(T)\rangle\) and \(\langle T,g_2(T)\rangle\) for arbitrary \(g_1,g_2\in\mathrm{MCG}(M,\mathcal{P})\). It turns out that this computation is similar to the ordinary matrix multiplication, namely \(\langle T,g_1(g_2(T))\rangle_{ij}=\langle\gamma,\gamma'\rangle\), where \(\gamma\) and \(\gamma'\) are the normal curves whose normal coordinates with respect to \(T\) form the \(i\)th row of \(\langle T,g_1(T)\rangle\) and the \(j\)th column of \(\langle T,g_2(T)\rangle\), respectively. The main technical result of this paper is an algorithm for computing the geometric intersection index \(\langle\gamma,\gamma'\rangle\) of two multiple curves \(\gamma,\gamma'\) given by their normal coordinates. The asymptotic running time of the algorithm, for fixed \(M\) and \(\mathcal{P}\), is \(O(|\gamma|\cdot|\gamma'|)\), where \(|\gamma|\) stands for a complexity measure comparable to the amount of space needed for writing the normal coordinates of \(\gamma\). The algorithm uses some known ideas, such as representing curves by measured train tracks and simplifying them by a procedure similar to the accelerated Euclidean algorithm. This is used to construct an algorithm solving the word problem for \(\mathrm{MCG}(M,\mathcal{P})\) that accepts as the input ``zipped'' words (meaning that powers of generators \(a^k\) are encoded as pairs \((a,k)\)), and whose running time is quadratic in the size of the input, provided that the generating set satisfies certain conditions. Most of the known generating sets for the mapping class group can be easily modified to satisfy these conditions. A similar result in the particular case of the braid group \(B_n\) was obtained by \textit{I. Dynnikov} and \textit{B. Wiest} [J. Eur. Math. Soc. 9, 801--840 (2007; Zbl 1187.20045)].