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 $α$ 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 $α$, one can compute $ [α^n] \pmod{m}$ in time polynomial in $(\log (m n))^{O(1)}$, where $m$ and $n$ are positive integers.

10 pages