Algorithms for commutative algebras over the rational numbers

DOI10.1007/S10208-016-9336-6MaRDI QIDQ1704817zbMATH OpenOpenAlexFDO

Authors H. W. jun. Lenstra, Alice Silverberg

Publication date 13 March 2018

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsfinite-dimensional commutative algebrasJordan-Chevalley decompositionlifting idempotents

Mathematics Subject Classification ID

Commutative Artinian rings and modules, finite-dimensional algebras (13E10) Computational aspects and applications of commutative rings (13P99) Symbolic computation and algebraic computation (68W30)

Abstract: The algebras considered in this paper are commutative rings of which the additive group is a finite-dimensional vector space over the field of rational numbers. We present deterministic polynomial-time algorithms that, given such an algebra, determine its nilradical, all of its prime ideals, as well as the corresponding localizations and residue class fields, its largest separable subalgebra, and its primitive idempotents. We also solve the discrete logarithm problem in the multiplicative group of the algebra. While deterministic polynomial-time algorithms were known earlier, our approach is different from previous ones. One of our tools is a primitive element algorithm; it decides whether the algebra has a primitive element and, if so, finds one, all in polynomial time. A methodological novelty is the use of derivations to replace a Hensel-Newton iteration. It leads to an explicit formula for lifting idempotents against nilpotents that is valid in any commutative ring.

Recommendations

• scientific article; zbMATH DE number 3880115
• Idempotent computation over finite fields
• scientific article; zbMATH DE number 1254290
• Prime decompositions of radicals in polynomial rings
• Efficient decomposition of associative algebras over finite fields

Cites work

• Decomposition of algebras over \(F_ q(X_ 1,\dots,X_ m)\)
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 871949 (Why is no real title available?)
• scientific article; zbMATH DE number 5486283 (Why is no real title available?)
• Modern computer algebra
• Revisiting the Gentry-Szydlo Algorithm
• Roots of unity in orders
• Testing isomorphism of lattices over CM-orders

Cited in

(14)

• Universal gradings of orders
• Finding binomials in polynomial ideals
• scientific article; zbMATH DE number 3880115 (Why is no real title available?)
• Polynomial-time locality tests for finite rings
• Toric varieties from cyclic matrix semigroups
• Testing isomorphism of lattices over CM-orders
• The XL-Algorithm and a Conjecture from Commutative Algebra
• Realizing orders as group rings
• Computing the binomial part of a polynomial ideal
• Efficient algorithms for finite \(\mathbb{Z}\)-algebras
• Computing the unit group of a commutative finite \(\mathbb{Z}\)-algebra
• Efficient computations in central simple algebras using Amitsur cohomology
• An affine representation of de Casteljau's and de Boor's rational algorithms
• Recognition of division algebras.

This page was built for publication: Algorithms for commutative algebras over the rational numbers

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