# Algorithm for comparing $x + y \cdot \log(z)$ for $x,y,z$ rational?

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.

• 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)$.
– YCor
Nov 12, 2019 at 6:08

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)$$