Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Integer relations among algebraic numbers


Author: Bettina Just
Journal: Math. Comp. 54 (1990), 467-477
MSC: Primary 11R04; Secondary 11Y40, 68Q25, 68Q40
MathSciNet review: 993930
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A vector $ m = ({m_1}, \ldots ,{m_n}) \in {{\mathbf{Z}}^n}\backslash \{ 0\} $ is called an integer relation for the real numbers $ {\alpha _1}, \ldots ,{\alpha _n}$, if $ \sum {\alpha _i}{m_i} = 0$ holds. We present an algorithm that, when given algebraic numbers $ {\alpha _1}, \ldots ,{\alpha _n}$ and a parameter $ \varepsilon $, either finds an integer relation for $ {\alpha _1}, \ldots ,{\alpha _n}$ or proves that no relation of Euclidean length shorter than $ 1/\varepsilon $ exists. Each algebraic number is assumed to be given by its minimal polynomial and by a sufficiently precise rational approximation.

Our algorithm uses the Lenstra-Lenstra-Lovász lattice basis reduction technique. It performs

$\displaystyle {\operatorname{poly}}\left( {\log 1/\varepsilon ,n,\log \mathop {... ...pha _i}),[{\mathbf{Q}}({\alpha _1}, \ldots ,{\alpha _n}):{\mathbf{Q}}]} \right)$

bit operations. The straightforward algorithm that works with a primitive element of the field extension $ {\mathbf{Q}}({\alpha _1}, \ldots ,{\alpha _n})$ of Q would take

$\displaystyle {\operatorname{poly}}\left( {n,\log \mathop {\max }\limits_i {\te... ...}}({\alpha _i}),\prod\limits_{i = 1}^n {{\text{degree}}({\alpha _i})} } \right)$

bit operations.

In order to prove the correctness of the algorithm, we show a lower bound for $ \left\vert {\sum {\alpha _1}{m_i}} \right\vert$ if m is not an integer relation for $ {\alpha _1}, \ldots ,{\alpha _n}$, which may be interesting in its own right.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R04, 11Y40, 68Q25, 68Q40

Retrieve articles in all journals with MSC: 11R04, 11Y40, 68Q25, 68Q40


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1990-0993930-5
PII: S 0025-5718(1990)0993930-5
Keywords: Integer relation, algebraic number, lattice basis reduction
Article copyright: © Copyright 1990 American Mathematical Society