Computing area in presentations of the trivial group

Riley, Timothy

doi:10.1090/proc/13625

Computing area in presentations of the trivial group
HTML articles powered by AMS MathViewer

by Timothy Riley PDF

Proc. Amer. Math. Soc. 145 (2017), 5059-5069 Request permission

Abstract:

We give polynomial-time dynamic-programming algorithms finding the areas of words in the presentations $\langle a, b \mid a, b \rangle$ and $\langle a, b \mid a^k, b^k; \ k \in \mathbb {N}\rangle$ of the trivial group.

In the first of these two cases, area was studied under the name spelling length by Majumdar, Robbins and Zyskin in the context of the design of liquid crystals. We explain how the problem of calculating it can be reinterpreted in terms of RNA-folding. In the second, area is what Jiang called width and studied when counting fixed points for self-maps of a compact surface, considered up to homotopy. In 1991 Grigorchuk and Kurchanov gave an algorithm computing width and asked whether it could be improved to polynomial-time. We answer this affirmatively.

References

K. Bringmann, F. Grandoni, B. Saha, and V. Williams, Truly sub-cubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product, In FOCS (2016).
Noel Brady, Tim Riley, and Hamish Short, The geometry of the word problem for finitely generated groups, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser Verlag, Basel, 2007. Papers from the Advanced Course held in Barcelona, July 5–15, 2005. MR 2281936
R. I. Grigorchuk and P. F. Kurchanov, On the width of elements in free groups, Ukrain. Mat. Zh. 43 (1991), no. 7-8, 911–918 (Russian, with Ukrainian summary); English transl., Ukrainian Math. J. 43 (1991), no. 7-8, 850–856 (1992). MR 1148843, DOI 10.1007/BF01058681
S. Ivanov., The bounded and precise word problems for presentation of groups, Preprint, 2016. arXiv:1606.08036.
Bo Ju Jiang, Surface maps and braid equations. I, Differential geometry and topology (Tianjin, 1986–87) Lecture Notes in Math., vol. 1369, Springer, Berlin, 1989, pp. 125–141. MR 1001182, DOI 10.1007/BFb0087529
M.-Y. Kao, editor. Encyclopedia of Algorithms. Springer, 2008.
Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
K. Koiliaris and C. Xu, A faster pseudopolynomial time algorithm for subset sum, To appear in SODA 2017. arXiv:1507.02318.
Apala Majumdar, J. M. Robbins, and Maxim Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, C. R. Math. Acad. Sci. Paris 347 (2009), no. 19-20, 1159–1164 (English, with English and French summaries). MR 2566995, DOI 10.1016/j.crma.2009.09.002
A. Majumdar, J. M. Robbins, and M. Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, Acta Math. Sci. Ser. B (Engl. Ed.) 30 (2010), no. 5, 1357–1399. MR 2778607, DOI 10.1016/S0252-9602(10)60131-2
R. Nussinov and A. B.Jacobson, Fast algorithm for predicting the secondary structure of single-stranded rna, Proceedings of the National Academy of Sciences of the United States of America (1980), 77(11):6309–6313.