Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N \in \mathbb{Z}$. Let $q \in \mathbb{N}_{\geq 2}$, and assume that we have an algorithm which can compute any finite initial segment of the q-adic representation of $x_1,\dots,x_n$. Then do we have an efficient algorithm to actually compute a number $N \in \{1,\dots,K\}$ with $x_1 N,\dots,x_n N \in \mathbb{Z}$?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ How «efficient» should it be? What is the complexity you have at your disposal right now? $\endgroup$– Loïc TeyssierCommented Jul 11, 2014 at 10:26
-
1$\begingroup$ At the moment I only have brute force. Anything better would be helpful. $\endgroup$– Daniel GerigkCommented Jul 11, 2014 at 10:32
-
$\begingroup$ Would it help if we knew a constant $C \in \mathbb{N}$ such that there is $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N \in \mathbb{Z}$ and all prime factors of $N$ are smaller than $C$? $\endgroup$– Daniel GerigkCommented Jul 11, 2014 at 10:38
-
2$\begingroup$ The motivation for this question can be found here. $\endgroup$– Daniel GerigkCommented Jul 11, 2014 at 14:08
Add a comment
|