An Effective Framework for Constructing Exponent Lattice Basis of Nonzero Algebraic Numbers
Tao Zheng, Bican Xia · 2019
Computing a basis for the exponent lattice of algebraic numbers is a basic problem in the field of computational number theory with applications to many other areas. The bottleneck of the computation of a well-known algorithm \citege1993, kauers2005 solving the problem is the computation of the primitive element of the extended field generated by the given algebraic numbers. When the extended field is of large degree, the problem seems intractable by the tool implementing the algorithm. In this paper, a special kind of exponent lattice basis is introduced. An important feature of that basis is that it can be inductively constructed, which allows us to deal with the given algebraic numbers one by one and to work in smaller fields while computing the basis. Based on this, an effective framework for constructing exponent lattice basis is proposed. Through computing a so-called pre-basis first and then solving some linear Diophantine equations, the basis can be efficiently constructed. A new certificate for multiplicative independence and some techniques for decreasing degrees of algebraic numbers are provided to speed up the computation. The new algorithm has been implemented with Mathematica and its effectiveness is verified by testing various examples.