Simultaneous Integer Relation Detection and Its an Application
For researchers in computational number theory and symbolic computation, this work offers a more efficient method for integer relation detection and minimal polynomial computation, though it is an incremental improvement over existing approaches.
The paper proposes an algorithm SIRD for detecting simultaneous integer relations among real vectors, achieving O(n^4 + n^3 log λ(X)) arithmetic operations, and demonstrates its practicality and superiority over existing methods. It also presents a new algorithm for finding the minimal polynomial of an algebraic number from an approximation, with a precision condition based on height and degree.
Let $\mathbf{x_1}, ..., \mathbf{x_t} \in \mathbb{R}^{n}$. A simultaneous integer relation (SIR) for $\mathbf{x_1}, ..., \mathbf{x_t}$ is a vector $\mathbf{m} \in \mathbb{Z}^{n}\setminus\{\textbf{0}\}$ such that $\mathbf{x_i}^T\mathbf{m} = 0$ for $i = 1, ..., t$. In this paper, we propose an algorithm SIRD to detect an SIR for real vectors, which constructs an SIR within $\mathcal {O}(n^4 + n^3 \log λ(X))$ arithmetic operations, where $λ(X)$ is the least Euclidean norm of SIRs for $\mathbf{x_1}, >..., \mathbf{x_t}$. One can easily generalize SIRD to complex number field. Experimental results show that SIRD is practical and better than another detecting algorithm in the literature. In its application, we present a new algorithm for finding the minimal polynomial of an arbitrary complex algebraic number from its an approximation, which is not based on LLL. We also provide a sufficient condition on the precision of the approximate value, which depends only on the height and the degree of the algebraic number.