Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer

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$

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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