3
$\begingroup$

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}$?

$\endgroup$
4
  • 2
    $\begingroup$ How «efficient» should it be? What is the complexity you have at your disposal right now? $\endgroup$ Jul 11, 2014 at 10:26
  • 1
    $\begingroup$ At the moment I only have brute force. Anything better would be helpful. $\endgroup$ 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$ Jul 11, 2014 at 10:38
  • 2
    $\begingroup$ The motivation for this question can be found here. $\endgroup$ Jul 11, 2014 at 14:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.