7
$\begingroup$

I'm playing with some methods of comparing two real numbers of the form $x + y \log(z)$, where $x,y,z$ are rational numbers and $z$ is positive. There are various estimates on irrationality measures of logarithms of rational numbers (e.g. Wu, below).

But I wonder what the best algorithm is for comparing two such real numbers. And how does the time depend on the height of $x_1,x_2$, $y_1,y_2$, and $z_1,z_2$, in the worst case, if one wishes to know whether $$x_1 + y_1 \log(z_1) < x_2 + y_2 \log(z_2)?$$ Is something proven or conjectured here?

Wu, Qiang, On the linear independence measure of logarithms of rational numbers, Math. Comput. 72, No. 242, 901-911 (2003). ZBL1099.11037.

$\endgroup$
1
  • 3
    $\begingroup$ I guess the question can be restated without reference to algorithm as follows: consider $f(n)=\inf X_n\smallsetminus\{0\}$ with $$X_n=\left\{\left|\frac{n_1}{m_1}+\frac{n_2}{m_2}\log\big(\frac{n_3}{m_3}\big)-\frac{n_4}{m_4}-\frac{n_5}{m_5}\log\big(\frac{m_6}{n_6}\big)\right|:\;|m_1|,\dots,|n_6|\le n\right\},$$ with all $n_i,m_i$ understood to be integers with $m_i$ nonzero: estimate/ find a lower bound to $f(n)$. $\endgroup$
    – YCor
    Nov 12, 2019 at 6:08

1 Answer 1

7
$\begingroup$

We can get an algorithm by constructively recasting a standard proof of the transcendence of $e$, and simplifying it since we need only that $e$ is not a root of a rational number. The result may not be the best algorithm, but it makes the time-analysis easy.

Algorithm

To start, we assume without loss of generality that $x_1, x_2, y_1, y_2$ are all integers.

Let $t=x_2-x_1$ and $u=z_1^{y_1}/z_2^{y_2}$, so the question is equivalent to deciding whether $e^t>u$.

Let $u=a/b$, with $a$ and $b$ integers. Choose an odd $p$ with $p>3t^2$ and $2^p>b 3^t t$. (We do not need $p$ to be prime, though it was in the source.)

Then let $$f(p,t,x)=\frac{x^p(x-t)^p}{p!\ e^x}$$ $$M=\int_0^\infty f(p,t,x) dx$$ $$M_t=e^t \int_t^\infty f(p,t,x) dx$$ $$\epsilon=e^t \int_0^t f(p,t,x) dx$$

Now we are looking to determine whether \begin{align} e^t &> u \\ (M_t + \epsilon)/M &> a/b \\ bM_t - aM &> -b \epsilon \end{align} where all three expressions are equivalent.

On the left hand side, we can evaluate the integral for $M$ using the identity $\int_0^\infty x^n e^{-x} dx = n!$, and conclude that $M$ is an integer. Using the change of variables $y=x-t$, we conclude that $M_t$ is also an integer, and so is $bM_t - aM$.

On the right hand side, $p>3t^2$ makes $|f(p,t,x)|<1/2^p$, so the second condition on $p$ gives $0<-b\epsilon<1$.

Thus the inequality holds iff $bM_t-aM>0$, and the algorithm is just to compare those as integers.

Time Analysis

The significant time in this algorithm is in calculating $M$ and $M_t$. To calculate $M$, we added $p+1$ summands, each of which is bounded by $$\frac{(2p)!}{p!}\binom{p}{p/2}t^p < (3pt)^p$$ The time for the algorithm is roughly the time to write out all those summands, which is $O(p^2\log(pt))$ or $$O(t^4 \log t +(\log b)^2\log\log b)$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.