Abstract
We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over \(\mathbb {F}_q\)) for computing an isomorphism (if there is any) of a finite-dimensional \(\mathbb {F}_q(x)\)-algebra \(\mathcal{A}\) given by structure constants with the algebra of n by n matrices with entries from \(\mathbb {F}_q(x)\). The method is based on computing a finite \(\mathbb {F}_q\)-subalgebra of \(\mathcal{A}\) which is the intersection of a maximal \(\mathbb {F}_q[x]\)-order and a maximal R-order, where R is the subring of \(\mathbb {F}_q(x)\) consisting of fractions of polynomials with denominator having degree not less than that of the numerator.
Similar content being viewed by others
Notes
A polynomial bound for the dimension of C follows also simply from the polynomiality of the algorithm described here.
References
M. Ajtai: The shortest vector problem in \(L_2\) is NP-hard for randomized reductions, Proceedings of the 30th annual ACM symposium on Theory of computing (1998), Dallas, Texas, United States, ACM. pp. 10-19.
E.R. Berlekamp: Factoring polynomials over finite fields, Bell System Technical Journal 46 (1967), pp. 1853-1859.
D.G. Cantor, H. Zassenhaus: A new algorithm for factoring polynomials over finite fields, Mathematics of Computation 36 (1981), pp. 587-592.
J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves I. Algebra, Journal für die reine und angewandte Mathematik, Vol. 615 (2008), pp. 121-155.
J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves II. Geometry, Journal für die reine und angewandte Mathematik 632 (2009), pp. 63–84.
J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves III. Algorithms, Mathematics of Computation 84 No.292 (2015), 895-922.
W.A. de Graaf, G. Ivanyos, A. Küronya, L. Rónyai: Computing Levi decompositions, Applicable Algebra in Engineering, Communication and Computing 8 (1997), pp. 291-304.
Y. Drozd, V.V. Kirichenko: Finite dimensional algebras, Vyshcha Shkola, Kiev, 1980.
K. Friedl, L. Rónyai: Polynomial time solutions of some problems in computational algebra, Proceedings of the 17th annual ACM symposium on Theory of computing (1985), Providence, Rhode Island, United States, ACM. pp. 153-162.
M. Giesbrecht, Y. Zhang: Factoring and decomposing Ore polynomials over \(\mathbb{F}_q(T)\), Proceedingss of the 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC2003), New York, NY, United States, ACM. pp. 127-134.
J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro: Factoring Ore polynomials over \({\mathbb{F}}_q(t)\) is difficult, (2015) Preprint arXiv:1505.07252.
G. Ivanyos: Algorithms for algebras over global field, Ph.D. thesis, Hungarian Academy of Sciences (1996), http://real-d.mtak.hu/261/1/Ivanyos_Gabor.
G. Ivanyos, M. Karpinski, L. Rónyai, N. Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures, Matematics of Computation 81 (2012), pp. 493-531.
G. Ivanyos, Á. Lelkes, L. Rónyai: Improved algorithms for splitting full matrix algebras, JP Journal of Algebra, Number Theory and Applications 28 (2013), pp. 141-156.
G. Ivanyos, L. Rónyai: On the complexity of finding maximal orders in semisimple algebras over \({\mathbb{Q}}\), Comput. complexity 3 (1993), pp. 245-261.
G. Ivanyos, L. Rónyai, J. Schicho: Splitting full matrix algebras over algebraic number fields, Journal of Algebra 354 (2012), pp. 211-223.
G. Ivanyos, L. Rónyai, Á. Szántó: Decomposition of algebras over \({\mathbb{F}}_q(x_1,... ,x_m)\), Applicable Algebra in Engineering, Communication and Computing 5 (1994), pp. 71-90.
A.K. Lenstra: Factoring multivariate polynomials over finite fields, Journal of Computer and System Sciences 30 (2) (1985), pp. 235-248.
S. Paulus: Lattice basis reduction in function fields, J. Buhler (Ed.), Proceedings of the Third Symposium on Algorithmic Number Theory, Portland, Oregon, United States: ANTS-III, Springer LNCS 1423 (1998), pp. 567-575.
I. Reiner: Maximal orders, Academic Press, London, 1975.
L. Rónyai: Computing the structure of finite algebras, Journal of Symbolic Computation 9 (1990), pp. 355-373.
M-F. Vignéras: Arithmétique des Algèbres de Quaternions, Springer, LNM 800, 1980.
Acknowledgements
Research is supported by the Hungarian National Research, Development and Innovation Office—NKFIH—Grants NK105645 and K115288. The authors are grateful to an anonymous referee for helpful remarks and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by John Cremona.
Rights and permissions
About this article
Cite this article
Ivanyos, G., Kutas, P. & Rónyai, L. Computing Explicit Isomorphisms with Full Matrix Algebras over \(\mathbb {F}_q(x)\) . Found Comput Math 18, 381–397 (2018). https://doi.org/10.1007/s10208-017-9343-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-017-9343-2
Keywords
- Explicit isomorphism
- Function field
- Lattice basis reduction
- Maximal order
- Full matrix algebra
- Polynomial time algorithm