Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T16:13:47.582Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE CONJUGACY PROBLEM IN CERTAIN METABELIAN GROUPS

Published online by Cambridge University Press:  20 June 2018

JONATHAN GRYAK ,
DELARAM KAHROBAEI  and
CONCHITA MARTINEZ-PEREZ
JONATHAN GRYAK
Affiliation:
Department of Computational Medicine and Bioinformatics, University of Michigan, Ann Arbor, MI, USA e-mail: [email protected]
DELARAM KAHROBAEI
Affiliation:
CUNY Graduate Center, PhD Program in Computer Science and NYCCT, Mathematics Department, City University of New York, New York, NY, USA e-mail: [email protected]
CONCHITA MARTINEZ-PEREZ
Affiliation:
Department of Mathematics, University of Zaragoza, Zaragoza, Spain e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We analyze the computational complexity of an algorithm to solve the conjugacy search problem in a certain family of metabelian groups. We prove that in general the time complexity of the conjugacy search problem for these groups is at most exponential. For a subfamily of groups, we prove that the conjugacy search problem is polynomial. We also show that for a different subfamily the conjugacy search problem reduces to the discrete logarithm problem.

Type
Research Article
Information
Glasgow Mathematical Journal , Volume 61 , Issue 2 , May 2019 , pp. 251 - 269
Copyright
Copyright © Glasgow Mathematical Journal Trust 2018 

References

REFERENCES

1. Auslander, L., On a problem of {P}hilip {H}all, Ann. Math. 86 (1) (1967), 112–116.Google Scholar
2. Babai, L., Beals, R., Cai, J.-Y., Ivanyos, G. and Luks, E. M., Multiplicative equations over commuting matrices, in Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1996.Google Scholar
3. Baumslag, G. and Bieri, R., Constructable solvable groups, Math. Z. 151 (3) (1976), 249–257.Google Scholar
4. Cavallo, B. and Kahrobaei, D., A polynomial time algorithm for the conjugacy problem in $\mathbb{Z}^n \rtimes \mathbb{Z}$, Reports@SCM 1 (1), 2014.Google Scholar
5. Eick, B. and Ostheimer, G., On the orbit-stabilizer problem for integral matrix actions of polycyclic groups, Math. Comput. 72 (243) (2003), 1511–1529.Google Scholar
6. Holt, D. F., Eick, B. and O'Brien, E. A., Handbook of computational group theory (Chapman & Hall/CRC, Boca Raton, 2005).Google Scholar
7. Horn, R. A. and Johnson, C. R., Matrix analysis (Cambridge University Press, New York, 1985).Google Scholar
8. Kannan, R. and Bachem, A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (4) (1979), 499–507.Google Scholar
9. Lennox, J. C. and Robinson, D. J. S., The theory of infinite soluble groups. Oxford mathematical monographs (The Clarendon Press, Oxford University Press, Oxford, 2004).Google Scholar
10. Noskov, G. A., Conjugacy problem in metabelian groups, Math. Notes Acad. Sci. USSR 31 (4) (1982), 252–258.Google Scholar
11. Sims, C. C., Computation with finitely presented groups, vol. 48 (Cambridge University Press, New York, 1994).Google Scholar
12. Yap, C. K., Linear systems, in Fundamental Problems of Algorithmic Algebra, Chapter 10, (Oxford University Press, New York, 2000), 258–299.Google Scholar