# Algorithm for least distance of powers of integers

From Michailescu's theorem (Catalan's conjecture) we have that the only $a,b,m,n \in \mathcal{Z}^{+}$ with $m,n>1$ such that $a^{m} - b^{n} = 1$ are: $a=3$, $b=2$, $m=2$, $n=3$.

1) Is there an algorithm which, for any $a,b \in \mathcal{Z}^{+}$ finds the minimum of $|a^{m} - b^{n}|$ $\forall m,n \in \mathcal{Z}^{+}$ (with $m,n>1$ )?

2) Do we know for how many different values of $m,n$ this minimum distance can be achieved?

3) If we do not have such an algorithm, do we know if this problem is decidable?

-
So we have $a^{m} = c + b^{n}$ or approximately $m\ln(a) = n\ln(b)$ (with c small) and convert $ln(b)/ln(a)$ to partial fractions to get some potentially good values of m and n. –  Mark Bennet Jan 22 '11 at 17:09
I think what the previous commenter meant was the best rational approximation to $ln(a)/ln(b)$. (See en.wikipedia.org/wiki/…) –  Carl Feynman Jan 22 '11 at 19:17
@carl - correct, continued fractions. –  Mark Bennet Jan 22 '11 at 19:27
Corrected spelling in title. It was irking me... –  David Roberts Feb 2 '11 at 22:38

When a, b are given, I presume you can get a lower bound for |a^m - b^n| by using lower bounds for linear forms in logarithms (applied to the form m log a - n log b.) This reduces you to finitely many possibilities for the mininum of |a^m - b^n|. For each possibility c, the equation a^m - b^n = c is an S-unit equation (where S contains all primes dividing a and b) and this again you can solve effectively by transcendental means.

The constants here might end up being pretty large. For the particular problem you ask about, there is a nice theorem of Mike Bennett which asserts there is at most one pair (m,n) such that a^m - b^n is small. Earlier work of Scott and Styer cited in Bennett's paper also seems relevant to your question.

-

I'd be curious to know how often the closest pair has $\min(m,n)>2$. Bennett shows that $|a^m-b^n|<\frac{\max(\sqrt{a^m},\sqrt{b^n})}{4}$ happens at most once. However this might not happen for most pairs $a,b$ and even when this happens, it might not be a min. (And it seems rare for it to happen with $\min(m,n)>1$.) A rather spectacular (to my mind) case is $13^3-3^7=10$. The first few convergents of the continued fraction for the ratio of the logs are $1/2,2/5,3/7,239/558$ This shows that 3/7 is an extremely good approximation (of course). But the closest pair is $13^1-3^2=4$.

later I looked for instances of $|a^m-b^n|<b$ with $2 \le a \le 99$ $n\ge 3$ and $m<200$ (also $a<b$ and neither a nor b a power of a smaller integer ). The only instances are $2^7-5^3=3$ and $13^3-3^7=10$. Both of these happen to have $|a^m-b^n|=b-a$

-
@Aaron: the fact that 13 in $13^3-3^7=10$ is a q-binomial with q=3 gave me the idea to write the both solutions in your "later" statement in the base 3 and base 2 numbersystem respective and also put the minus-term to the rhs. then we have $[base 3]: 111^3=10000101$ and $[base 2]: 101^3 = 10000011$ and the left number 111 and 101 are greater than the nonzero tail of the rhs-number. Maybe this view adds a useful restriction to your last idea and might make it solvable with this.(I remember vaguely there is something with max. consecutive zeros in binomial expansions) –  Gottfried Helms Feb 5 '11 at 11:21
upps - the "restriction" in the previous comment was lost. Initially I meant to restrict the lhs to be a repunit/q-analogue of the base-number like in the 13^3 example. For the analogy to the 5^3 example another meaningful might then be to use $[base]^k + 1$ but this is only a shot in the dark... –  Gottfried Helms Feb 5 '11 at 12:10