Shortest division chains in unique factorization domains
| Autor: | Maksim Vaskouski, Nikita Kondratyonok |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Algebra and Number Theory Logarithm 010102 general mathematics Unique factorization domain 010103 numerical & computational mathematics 01 natural sciences Combinatorics Computational Mathematics Euclidean algorithm Norm (mathematics) Euclidean geometry Euclidean domain Polynomial greatest common divisor 0101 mathematics Remainder Mathematics |
| Zdroj: | Journal of Symbolic Computation. 77:175-188 |
| ISSN: | 0747-7171 |
| DOI: | 10.1016/j.jsc.2016.02.003 |
| Popis: | We investigate the problem on the validity of the Lazard theorem analogue (or the Kronecker-Vahlen theorem), which states that the least remainder Euclidean Algorithm (EA) has the shortest length over any other versions of EA, in unique factorization domains. There is obtained the existence criterion to represent a fixed element of the fractions field of a unique factorization domain in the form of a continued fraction of a fixed length. This criterion enables to obtain a formula for the length of the least remainder (on norm) EA as a function of elements, with respect to which EA is applied. This result gives us the class T of unique factorization domains, for which the Lazard theorem analogue is valid. We propose algorithms to check whether the given unique factorization domain belongs to the class T . We find the necessary and sufficient conditions under which the number of steps in the worst case of the least remainder EA grows not faster than logarithm. In particular, these results hold for the least remainder EA in any Euclidean quadratic domain. We provide counterexamples, which show the essentiality of the conditions in the obtained theorems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect