Linear estimates for solutions of quadratic equations in free groups.

DOI10.1142/S0218196711006704MaRDI QIDQ2882397zbMATH OpenOpenAlexFDO

Authors Olga Kharlampovich, Alina Vdovina

Publication date 4 May 2012

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.2843

zbMATH Keywords

complexityfree groupsquadratic equationshyperbolic groups

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Free nonabelian groups (20E05) Geometric group theory (20F65) Combinatorics on words (68R15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Abstract: We prove that in a free group the length of the value of each variable in a minimal solution of a standard quadratic equation is bounded by $2s$ for orientable equation and by $12s^4$ for non-orientable equation, where $s$ is the sum of the lengths of the coefficients

Recommendations

• A polynomial bound on solutions of quadratic equations in free groups.
• Solutions d'une équation quadratique dans le groupe libre. (Solutions of a quadratic equation in the free group)
• On the rank of quadratic equations in free groups
• scientific article; zbMATH DE number 4083904
• scientific article; zbMATH DE number 3910618

Cites work

• A DESCRIPTION OF SOLUTIONS OF QUADRATIC EQUATIONS IN HYPERBOLIC GROUPS
• Compressed words and automorphisms in fully residually free groups.
• Constructing of orientable wicks forms and estimation of their number
• Implicit function theorem over free groups.
• ON RESIDUALING HOMOMORPHISMS AND G-SUBGROUPS OF HYPERBOLIC GROUPS
• On quasiconvex subgroups of word hyperbolic groups
• On the number of nonorientable Wicks forms in a free group
• PRODUCTS OF COMMUTATORS AND PRODUCTS OF SQUARES IN A FREE GROUP
• Permutations and cubic graphs
• Powers as products of commutators
• Quadratic equations over free groups and free products
• The existential theory of equations with rational constraints in free groups is PSPACE-complete

Cited in

(11)

• Solutions d'une équation quadratique dans le groupe libre. (Solutions of a quadratic equation in the free group)
• On the length of nonsolutions to equations with constants in some linear groups
• On the rank of quadratic equations in free groups
• Solutions of quadratic equations in groups with small cancellation condition
• scientific article; zbMATH DE number 6496908 (Why is no real title available?)
• Explicit solutions of certain orientable quadratic equations in free groups
• A polynomial bound on solutions of quadratic equations in free groups.
• scientific article; zbMATH DE number 4083904 (Why is no real title available?)
• Non-∀-homogeneity in free groups
• Quadratic equations in hyperbolic groups are NP-complete
• Spherical quadratic equations in free metabelian groups.

This page was built for publication: Linear estimates for solutions of quadratic equations in free groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2882397)