On Certain Computations of Pisot Numbers

Abstract

This paper presents two algorithms on certain computations about Pisot numbers. Firstly, we develop an algorithm that finds a Pisot number $\alpha$ such that $\Q[α] = \F$ given a real Galois extension $\F$ of $\Q$ by its integral basis. This algorithm is based on the lattice reduction, and it runs in time polynomial in the size of the integral basis. Next, we show that for a fixed Pisot number $\alpha$, one can compute $[{\alpha }^n](\mathrm{mod}m)$ in time polynomial in $(\log (mn){)}^{O(1)}$, where $m$ and $n$ are positive integers.

10 pages