Search

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R -specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the LLL algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Z n to K n , and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). [ABSTRACT FROM AUTHOR]

Abstract: A practical computational system is described for computing with an algebraic closure of a field. The system avoids factorization of polynomials over extension fields, but gives the illusion of a genuine field to the user. All roots of an arbitrary polynomial defined over such an algebraically closed field can be constructed and are easily distinguished within the system. The difficult case of inseparable extensions of function fields of positive characteristic is also handled properly by the system. A technique of modular evaluation into a finite field critically ensures that a unique genuine field is simulated by the system but also provides fast optimizations for some fundamental operations. Fast matrix techniques are also used for several non-trivial operations. The system has been successfully implemented within the Magma Computer Algebra System, and several examples are presented, using this implementation. [Copyright &y& Elsevier]

Abstract: Text: By a result of G. Freiman and A. Geroldinger [G. Freiman, A. Geroldinger, An addition theorem and its arithmetical application, J. Number Theory 85 (1) (2000) 59–73] it is known that the set of lengths of factorizations of an algebraic integer (in the ring of integers of an algebraic number field), or more generally of an element of a Krull monoid with finite class group, has a certain structure: it is an almost arithmetical multiprogression for whose difference and bound only finitely many values are possible, and these depend just on the class group. We establish a sort of converse to this result, showing that for each choice of finitely many differences and of a bound there exists some number field such that each almost arithmetical multiprogression with one of these difference and that bound is up to shift the set of lengths of an algebraic integer of that number field. Moreover, we give an explicit sufficient condition on the class group of the number field for this to happen. Video: For a video summary of this paper, please visit http://www.youtube.com/watch?v=c61xM-5D6Do. [Copyright &y& Elsevier]

Abstract: The groups in this paper are abelian. Let G be a reduced torsion-free finite rank group. Then G is cocommutative if is commutative modulo the nil radical. The class number of G, , is the number of isomorphism classes of groups H that are locally isomorphic ( isomorphic) to G. We say that G satisfies the power cancellation property if for some group H and integer implies that . We say that G has a Σ-unique decomposition if has a unique direct sum decomposition for each integer . Let for some group and some integer . We say that G has internal cancellation if given such that then . We use the class number to study the torsion-free finite rank groups G that have the power cancellation property, or a Σ-unique decompositions, or the internal cancellation property. Furthermore, we show that the power cancellation property for cocommutative strongly indecomposable reduced torsion-free finite rank groups is equivalent to the problem of determining the class number of an algebraic number field. Let be the integral closure of G. Using the Mayer–Vietoris sequence we show that there are finite groups associated with G of orders , , and such that . Let where p is a rational prime and is the ring of algebraic integers in the algebraic number field . Let be a group such that . We show that the sequence is asymptotically equal to the sequence where . Furthermore, for quadratic number fields k, iff is asymptotically equal to the sequence of rational primes. This connects unique factorization in number fields with the sequence of rational primes, and with direct sum properties of integrally closed cocommutative strongly indecomposable torsion-free finite rank groups. [Copyright &y& Elsevier]