7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Mark Bennet
    Commented Jan 22, 2011 at 17:09
  • $\begingroup$ I think what the previous commenter meant was the best rational approximation to $ln(a)/ln(b)$. (See en.wikipedia.org/wiki/…) $\endgroup$
    – Carl Feynman
    Commented Jan 22, 2011 at 19:17
  • $\begingroup$ @carl - correct, continued fractions. $\endgroup$
    – Mark Bennet
    Commented Jan 22, 2011 at 19:27
  • $\begingroup$ Corrected spelling in title. It was irking me... $\endgroup$
    – David Roberts ♦
    Commented Feb 2, 2011 at 22:38

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
5
$\begingroup$

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$

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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) $\endgroup$
    – Gottfried Helms
    Commented Feb 5, 2011 at 11:21
  • $\begingroup$ 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... $\endgroup$
    – Gottfried Helms
    Commented Feb 5, 2011 at 12:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .