Document Open Access Logo

Determinant Equivalence Test over Finite Fields and over Q

Authors Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.62.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Ankit Garg
  • Microsoft Research India, Bangalore, India
Nikhil Gupta
  • Department of Computer Science and Automation, Indian Institute of Science, India
Neeraj Kayal
  • Microsoft Research India, Bangalore, India
Chandan Saha
  • Department of Computer Science and Automation, Indian Institute of Science, India

Acknowledgements

We would like to thank Youming Qiao for pointing us to the module decomposition algorithm in [Alexander L. Chistov et al., 1997]. NG would like to thank Vineet Nair for discussions on the structure of the Lie algebra of Det. We thank him for sharing his proof of Theorem 10. We also thank anonymous reviewers for their comments.

Cite AsGet BibTex

Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant Equivalence Test over Finite Fields and over Q. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.62

Abstract

The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f in F[x], check if f is equivalent to Det_n(x) over F, and if so then output a transformation matrix A in GL(n^2,F). In (Kayal, STOC 2012), a randomized polynomial time determinant equivalence test was given over F = C. But, to our knowledge, the complexity of the problem over finite fields and over Q was not well understood. In this work, we give a randomized poly(n,log |F|) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F). Over Q, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the n=2 case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over Q is a challenging task. Nevertheless, we show that determinant equivalence test over Q is decidable: For bounded n, there is a randomized polynomial-time determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomial-time algorithm that takes input black-box access to a f in Q[x] and if f is equivalent to Det_n over Q then it returns a A in GL(n^2,L) such that f = Det_n(A * x), where L is an extension field of Q and [L : Q] <= n. The above algorithms over finite fields and over Q are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if n is bounded. These reductions, which hold over any F (under mild restrictions on the characteristic and size of F), establish a close connection between the complexity of the two problems. This then leads to our results via applications of known results on the full algebra isomorphism problem over finite fields (Rónyai, STOC 1987 and Rónyai, J. Symb. Comput. 1990) and over Q (Ivanyos {et al}., Journal of Algebra 2012 and Babai {et al}., Mathematics of Computation 1990).

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Determinant equivalence test
  • full matrix algebra isomorphism
  • Lie algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Manindra Agrawal and Nitin Saxena. Automorphisms of Finite Rings and Applications to Complexity of Problems. In STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, pages 1-17, 2005. Google Scholar
  2. Manindra Agrawal and Nitin Saxena. Equivalence of F-Algebras and Cubic Forms. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pages 115-126, 2006. Google Scholar
  3. László Babai and Lajos Rónyai. Computing irreducible representations of finite groups. Mathematics of Computation, 55(192):705-722, 1990. Google Scholar
  4. Alexander L. Chistov, Gábor Ivanyos, and Marek Karpinski. Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC '97, Maui, Hawaii, USA, July 21-23, 1997, pages 68-74, 1997. Google Scholar
  5. Keith Conrad. Quaternion algebras, 2016. Google Scholar
  6. J. E. Cremona, T. A. Fisher, C. O'Neil, D. Simon, and M. Stoll. Explicit n-descent on elliptic curves III. Algorithms. Math. Comput., 84(292):895-922, 2015. URL: http://arxiv.org/abs/1107.3516.
  7. W.A. de Graaf. Algorithms for Finite-Dimensional Lie Algebras. PhD thesis, Technical University of Eindhoven, 1997. Google Scholar
  8. W.A. de Graaf. Calculating the structure of a semisimple Lie algebra. Journal of Pure and Applied Algebra, 117-118:319-329, 1997. Google Scholar
  9. Wayne Eberly. Decompositions of algebras over R and C. computational complexity, 1(3):211-234, September 1991. Google Scholar
  10. W.M. Eberly. Computations for algebras and group representations. PhD thesis, Department of Computer Science, University of Toronto, 1989. Google Scholar
  11. Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant equivalence test over finite fields and over dollarbackslashmathbfQdollar. Electronic Colloquium on Computational Complexity (ECCC), 26:42, 2019. URL: https://eccc.weizmann.ac.il/report/2019/042.
  12. Joshua A. Grochow. Matrix Lie algebra isomorphism. In IEEE Conference on Computational Complexity (CCC12), pages 203-213, 2012. Google Scholar
  13. Joshua Abraham Grochow. Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, Department of Computer Science, The University of Chicago, Chicago, Illinois, 2012. Google Scholar
  14. Gábor Ivanyos, Lajos Rónyai, and Josef Schicho. Splitting full matrix algebras over algebraic number fields. Journal of Algebra, 354:211-223, 2012. URL: http://arxiv.org/abs/1106.6191.
  15. Neeraj Kayal. Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1409-1421, 2011. Google Scholar
  16. Neeraj Kayal. Affine projections of polynomials: extended abstract. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 643-662, 2012. Google Scholar
  17. Neeraj Kayal, Vineet Nair, and Chandan Saha. Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs. Electronic Colloquium on Computational Complexity (ECCC), 25:29, 2018. Google Scholar
  18. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of Full Rank Algebraic Branching Programs. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 21:1-21:61, 2017. Google Scholar
  19. Falko Lorenz. Algebra Volumne 2: Fields with structures, Algebras and advanced topics. Springer, 2008. Google Scholar
  20. Meena Mahajan and V. Vinay. A Combinatorial Algorithm for the Determinant. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 5-7 January 1997, New Orleans, Louisiana, USA., pages 730-738, 1997. Google Scholar
  21. Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. Google Scholar
  22. Ketan Mulmuley and Milind A. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput., 31(2):496-526, 2001. Google Scholar
  23. Jacques Patarin. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, pages 33-48, 1996. Google Scholar
  24. Lajos Rónyai. Simple Algebras Are Difficult. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, New York, New York, USA, pages 398-408, 1987. Google Scholar
  25. Lajos Rónyai. Computing the Structure of Finite Algebras. J. Symb. Comput., 9(3):355-373, 1990. Google Scholar
  26. Lajos Rónyai. A Deterministic Method for Computing Splitting Elements in Simple Algebras over Q. Journal of Algorithms, 16:24-32, 1994. Google Scholar
  27. Alexander J.E. Ryba. Computer construction of split Cartan subalgebras. J. Algebra, 309:455-483, 2007. Google Scholar
  28. Nitin Saxena. Morphisms of rings and applications to complexity. PhD thesis, Indian Institute of Technology Kanpur, 2006. Google Scholar
  29. Thomas Thierauf. The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits. Chicago J. Theor. Comput. Sci., 1998, 1998. Google Scholar
  30. Leslie G. Valiant. Completeness Classes in Algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249-261, 1979. Google Scholar
  31. Lars Ambrosius Wallenborn. Computing the Hilbert symbol, quadratic form equivalence and integer factoring. Diploma thesis, University of Bonn, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact