Elements of Algebraic Geometry and the Positive Theory of Partially Commutative Groups

Casals-Ruiz, Montserrat

Canadian journal of mathematics, Tome 62 (2010) no. 3, pp. 481-519

Résumé

The first main result of the paper is a criterion for a partially commutative group $\mathbb{G}$ to be a domain. It allows us to reduce the study of algebraic sets over $\mathbb{G}$ to the study of irreducible algebraic sets, and reduce the elementary theory of $\mathbb{G}$ (of a coordinate group over $\mathbb{G}$ ) to the elementary theories of the direct factors of $\mathbb{G}$ (to the elementary theory of coordinate groups of irreducible algebraic sets).Then we establish normal forms for quantifier-free formulas over a non-abelian directly indecomposable partially commutative group $\mathbb{H}$ . Analogously to the case of free groups, we introduce the notion of a generalised equation and prove that the positive theory of $\mathbb{H}$ has quantifier elimination and that arbitrary first-order formulas lift from $\mathbb{H}$ to $\mathbb{H}\,*\,F$ , where $F$ is a free group of finite rank. As a consequence, the positive theory of an arbitrary partially commutative group is decidable.

Détail

DOI : 10.4153/CJM-2010-035-5

Mots-clés : 20F10, 03C10, 20F06

Bibliographie

[1] [1] Baumslag, G., Myasnikov, A. G., and Remeslennikov, V. N., Algebraic geometry over groups I. Algebraic sets and Ideal Theory. J. Algebra 219(1999), no. 1, 16–79. doi: 10.1006/jabr.1999.7881 Google Scholar

[2] [2] Baumslag, G., Discriminating completions of hyperbolic groups. Geom. Dedicata 92(2002), 115–143. doi: 10.1023/A:1019687202544 Google Scholar

[3] [3] Brady, N., Short, H., and Riley, T., The Geometry of the Word Problem for Finitely Generated Groups. Advanced Courses in Mathematics. CRM Barcelona. Birkhauser Verlag, Basel, 2007. Google Scholar

[4] [4] Charney, R., An introduction to right-angled Artin groups. Geom. Dedicata 125(2007), 141–158. doi: 10.1007/s10711-007-9148-6 Google Scholar

[5] [5] Crisp, J. and Wiest, B., Embeddings of graph braid groups and surface groups in right-angled Artin groups and braid groups. Algebr. Geom. Topol. 4(2004), 439–472. doi: 10.2140/agt.2004.4.439 Google Scholar

[6] [6] Diekert, V., Gutierrez, C., and Hagenah, C., The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inform. and Comput. 202(2005), no. 2, 105–140. doi: 10.1016/j.ic.2005.04.002 Google Scholar

[7] [7] Diekert, V., and Lohrey, M., Word equations over graph products. In: FST TCS 2003. Lecture Notes in Comput. Sci. 2450, Springer, Berlin, 2003, pp. 156–167. Google Scholar

[8] [8] Diekert, V.,and Lohrey, M., Existential and positive theories of equations in graph products. Theory Comput. Syst. 37(2004), no. 1, 133–156. doi: 10.1007/s00224-003-1110-x Google Scholar

[9] [9] Diekert, V. and Muscholl, A., Solvability of equations in free partially commutative groups is decidable. Internat. J. Algebra Comput. 16(2006), no. 6, 1047–1070. doi: 10.1142/S0218196706003372 Google Scholar

[10] [10] Diekert, V. and Rozenberg, G., eds. The Book of Traces. World Scientific Publishing, River Edge, NJ, 1995. Google Scholar

[11] [11] Duchamp, G. and Krob, D., Partially commutative Magnus transformations. Internat. J. Algebra Comput. 3(1993), no. 1, 15–41. doi: 10.1142/S0218196793000032 Google Scholar

[12] [12] Duncan, A. J., Kazachkov, I. V., and Remeslennikov, V. N., Centraliser dimension and universal classes of groups. Sib. Èlektron. Mat. Izv. 3(2006), no. 2, 197–215. Google Scholar

[13] [13] Duncan, A. J., Centraliser dimension of partially commutative groups. Geom. Dedicata 120(2006), 73–97. doi: 10.1007/s10711-006-9046-3 Google Scholar

[14] [14] Duncan, A. J., Parabolic and quasiparabolic subgroups of free partially commutative groups. J. Algebra 318(2007), no. 2, 918–932. doi: 10.1016/j.jalgebra.2007.08.032 Google Scholar

[15] [15] Esyp, E. S., Kazachkov, I. V.,and Remeslennikov, V. N., Divisibility theory and complexity of algorithms for free partially commutative groups. In: Groups, Languages, Algorithms. Contemp. Math. 378. American Mathematical Society, Providence, RI, 2005, pp. 319–348. Google Scholar

[16] [16] Feferman, S. and Vaught, L., The first order properties of products of algebraic systems. Fund. Math. 47(1959), 57–103. Google Scholar

[17] [17] Hsu, T. and Wise, D., On linear and residual properties of graph products. Mich. Math. J. 46(1999), no. 2, 251–259. doi: 10.1307/mmj/1030132408 Google Scholar

[18] [18] Humphries, S., On representations of Artin groups and the Tits conjecture. J. Algebra 169(1994), no. 3, 847–862. doi: 10.1006/jabr.1994.1312 Google Scholar

[19] [19] Kharlampovich, O. and Myasnikov, A., Implicit function theorem over free groups. J. Algebra 290(2005), no. 1, 1–203. doi: 10.1016/j.jalgebra.2005.04.001 Google Scholar

[20] [20] Kvaschuk, A., Myasnikov, A. G., and Remeslennikov, V. N., Algebraic geometry over groups. III. Elements of Model Theory. J. Algebra 288(2005), no. 1, 78–98. doi: 10.1016/j.jalgebra.2004.07.038 Google Scholar

[21] [21] Makanin, G. S., Equations in a free group (Russian). Izv. Akad. Nauk SSSR, Ser. Mat. 46, 1199-1273, 1982. transl. in Math. USSR Izv., V. 21, 1983. Google Scholar

[22] [22] Makanin, G. S., Decidability of the universal and positive theories of a free group. (Russian). Izv. Akad. Nauk SSSR Ser. Mat. 48(1984) no. 4, 735–749; Math. USSR Izv. 25(1985), no. 1, 75–88. Google Scholar

[23] [23] Mal’cev, A. I., On the equation zxyx−1 y−1z−1 = aba−1b−1 in a free group. (Russian), Algebra i Logika Sem. 1(1962), no. 5, 45–50. Google Scholar

[24] [24] Merzlyakov, Ju. I.. Positive formulae on free groups. Algebra i Logika Sem. 5(1966), no. 4, 25–42. Google Scholar

[25] [25] Myasnikov, A. G. and Remeslennikov, V. N., Algebraic geometry over groups. II. Logical Foundations. J. Algebra 234(2000), no. 1, 225–276. doi: 10.1006/jabr.2000.8414 Google Scholar

[26] [26] Myasnikov, A. and Shumyatsky, P., Discriminating groups and c-dimension. J. Group Theory 7(2004), no. 1, 135–142. doi: 10.1515/jgth.2003.039 Google Scholar

[27] [27] Ol’shanskii, A. Yu., The Geometry of Defining Relations in Groups. [in Russian] Nauka, Moscow, 1989. Google Scholar

[28] [28] Schulz, K., Makanin's algorithm for word equations–two improvements and a generalization. In: Word Equations and Related Topics. Lecture Notes in Comput. Sci. 572. Springer, Berlin, 1992, pp. 85–150. Google Scholar

[29] [29] Shestakov, S. L., The equation [x, y] = g in partially commutative groups. Sibirsk. Mat. Zh. 46(2005), no. 2, 466-477; translation in Siberian Math. J. 46(2005), no. 2, 364–372. Google Scholar