11
$\begingroup$

Given coprime $a, b$, what is $$ \min_{x, y > 0} |a^x - b^y| $$

Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? Also, how do we quickly compute the minimizing $x, y$?

$\endgroup$
  • 6
    $\begingroup$ Use rational approximations to $\log b/\log a$. Often the answer is that one of the exponents is 1. You might look at Ribenboim's book on the Catalan Conjecture. Gerhard "Is Presently Computing Small Powers" Paseman, 2017.10.19. $\endgroup$ – Gerhard Paseman Oct 19 '17 at 21:52
  • 1
    $\begingroup$ I think Fermat proved that 26 is the only positive integer "between a square and a cube", that is the only solution of $x^3-y^2=2 $ is $ (x,y)=(3,5) $ . $\endgroup$ – Sylvain JULIEN Oct 20 '17 at 7:14
  • $\begingroup$ Simultaneously cross-posted on on CSTheory: cstheory.stackexchange.com/q/39335/5038. Please don't do that -- it violates site rules. $\endgroup$ – D.W. Oct 21 '17 at 5:56
  • 1
    $\begingroup$ See also Noam Elkies list of integers $x,y$ with $x<10^{18}$, $0<|x^3-y^2|<x^{1/2}$ at math.harvard.edu/~elkies/hall.html which includes the spectacular example $$5853886516781223^3 - 447884928428402042307918^2 = 1641843$$ Elkies links to further work of Calvo, Sáez and Herranz, but the link is broken. Perhaps ams.org/journals/mcom/2009-78-268/S0025-5718-09-02240-6 goes to the right place. $\endgroup$ – Gerry Myerson Oct 23 '17 at 21:38
12
$\begingroup$

You can get a conjectural lower bound for $|a^x-b^y|$ using the $ABC$-conjecture. I'll do the case $a^x > b^y$ for simplicity. Taking $A=a^x$, $B=-b^y$, and $C=a^x-b^y$, we get for every $\epsilon >0$ that there is a $K=K_\epsilon>0$ so that $$ a^x \le K\prod_{p\mid ab(a^x-b^y)} p^{1+\epsilon} \le K(ab(a^x-b^y))^{1+\epsilon}. $$ Replacing $K$ with a $K'=K'_\epsilon$, this gives $$ a^x - b^y \ge K' \left(\frac{a^{x-1}}{b}\right)^{1-\epsilon}. $$ This shows that if $x$ and $y$ are large, you can't make $a^x-b^y$ very much smaller than $a^x$. (You can also prove an effective lower bound using linear forms in logs, but it will be much weaker than this.)

$\endgroup$
2
$\begingroup$

Gerhard says what needs to be said: Try $y=1$ and in very rare case $y=2$ or maybe $3.$

Here is an exceptional example: $1138^2-109^3=15.$

You didn't ask for exceptional cases, just what to do given $a$ and $b.$

For that, find rational numbers $\frac{x}{y}$ which approximate $\frac{\ln{b}}{\ln{a}}$ well. The first few convergents to $\frac{\ln{1138}}{\ln{109 }}$ are $2, \frac{3}{2}, \frac{607547}{405031}.$ The huge jump suggests that it is worth checking $3,2.$

I don't see any reason to assume that $a$ and $b$ are relatively prime.

LATER Inspired by @Gerry let me observe this: Let $a=2$ and $b=\lfloor 2^k \sqrt{2}\rceil.$ Then $b^1-2^k \approx 2^k(\sqrt{2}-1)$ while $|b^2-2^{2k+1}| \lt 2^k \sqrt{2}.$ This suggests to me that with probability about $1-\frac1{\sqrt2} \approx0.3$ it will happen that $|b^2-2^{2k+1}| \lt b-2^k.$ This does happen $26$ times up to $2k+1=201.$ The first and last few are $2k+1=15, 17, 19, 31, 33, 59, \cdots 147, 149, 161, 187, 193.$ I can see why this might even more successful for odd powers $m^{2k+1}$ of larger integers.

$\endgroup$
  • 1
    $\begingroup$ Smaller exceptional examples include $5^3-11^2=4$, $47^2-13^3=12$, $56^2-5^5=11$, $15^3-58^2=11$, $83^2-19^3=30$. $\endgroup$ – Gerry Myerson Oct 20 '17 at 0:02
  • 1
    $\begingroup$ A few more examples: $2^{15}-181^2=7$, $312^2-46^3=8$, $2537^2-23^5=26$, $3788^2-3^{15}=37$. $\endgroup$ – Gerry Myerson Oct 20 '17 at 0:32
1
$\begingroup$

If one looks at the sequence of perfect powers (1,4,8,9,16,25,27,32,36,... found at OEIS at https:/oeis.org/A001597 ), one sees a lot of squares. If one wants to tackle the posted question by looking at this sequence, one can save time looking at odd powers. Note that all pairs listed by Gottfried Helms have one even exponent and one odd exponent.

Indeed, since (a^2 - b^2)=(a-b)(a+b), interesting answers to the question will involve an odd exponent, usually coprime to the other exponent. More specifically, interesting answers will be odd powers near a square, and two distinct odd powers which lie between two squares. Thus, an algorithm which looks only at odd powers which are not squares , and just the squares adjacent to them, saves time by looking at just the interesting cases. Further to avoid answers producing zero (like 225 and 3375), we look only at pairs which give distinct powers.

I generated the first two million cubes, as well as the smattering of higher powers (excepting two or three really large powers of 2 or 3 with the exponent prime) occurring between these cubes. I got less than 100 cases where these powers were within 100 of a square. I counted 14 cases where two odd powers had no squares between them , and 32 where there was only one square. The largest number less than 10^18 that was a perfect power and was within 100 of a square was 8158^3 which is 24 less than a square. The other slightly over 4 million differences I computed were over 1000 or were small known examples of near powers less than 10000, e.g. 2187,2197,2209. This suggests to me to look for powers that are within s^{1/3} of a square s.

Gerhard "Is Feeling Rather Powerfull Presently" Paseman, 2017.10.23.

$\endgroup$
0
$\begingroup$

As an extension of Gerry Myerson's commnt: a short list of small differences, using $a=2..199$ and $b=a+1..3999$ checking the first eight convergents of the continued fraction of $\log(a)/\log(b)$ for differences $d\le 100$

  a       b          d        cont.frac
--------------------------------------------------  
 15^4-   37^3 =     -28 --- .0.1.2.1.1631.1.6
  6^7-   23^4 =      95 --- .0.1.1.2.1.1318.1.30

After that only differences where one exponent is 2 occur

  2^15- 181^2 =       7 --- .0.7.2.1621.1.2
  2^17- 362^2 =      28 --- .0.8.2.1621.1.2

  3^9-  140^2 =      83 --- .0.4.2.129.2.24
  3^11- 421^2 =     -94 --- .0.5.1.1.1034.1.27
  3^15-3788^2 =     -37 --- .0.7.1.1.213025.3.1

  5^5-   56^2 =     -11 --- .0.2.1.1.228.1.1

  6^5-   88^2 =      32 --- .0.2.2.216.1.3
  6^7-  529^2 =      95 --- .0.3.2.2638.1.14

  7^5-  130^2 =     -93 --- .0.2.1.1.175.1.4

  8^5-  181^2 =       7 --- .0.2.2.4866.16.4
 23^5- 2537^2 =     -26 --- .0.2.1.1.388098.1.2
 27^5- 3788^2 =     -37 --- .0.2.1.1.639076.1.3

from here only differences with exponents $3$ and $2$ remain

 13^3-   47^2 =     -12 --- .0.1.1.1.234.1.15
 15^3-   58^2 =      11 --- .0.1.2.414.3.1
 17^3-   70^2 =      13 --- .0.1.2.534.6.3
 18^3-   76^2 =      56 --- .0.1.2.149.3.1
 19^3-   83^2 =     -30 --- .0.1.1.1.336.1.5
 20^3-   89^2 =      79 --- .0.1.2.150.2.3
 20^3-   90^2 =    -100 --- .0.1.1.1.120.13.23
 21^3-   96^2 =      45 --- .0.1.2.312.50.1
 22^3-  103^2 =      39 --- .0.1.2.420.1.2
 23^3-  110^2 =      67 --- .0.1.2.283.2.2
 24^3-  118^2 =    -100 --- .0.1.1.1.219.1.24
 27^3-  140^2 =      83 --- .0.1.2.389.2.7
 28^3-  148^2 =      48 --- .0.1.2.760.1.1
 29^3-  156^2 =      53 --- .0.1.2.773.2.2
 32^3-  181^2 =       7 --- .0.1.2.8110.2.3
 34^3-  198^2 =     100 --- .0.1.2.691.1.1
 35^3-  207^2 =      26 --- .0.1.2.2930.15.1
 37^3-  225^2 =      28 --- .0.1.2.3264.1.2
 40^3-  253^2 =      -9 --- .0.1.1.1.13116.2.3
 43^3-  282^2 =     -17 --- .0.1.1.1.8795.1.3
 44^3-  292^2 =     -80 --- .0.1.1.1.2015.6.1
 45^3-  302^2 =     -79 --- .0.1.1.1.2195.1.9
 46^3-  312^2 =      -8 --- .0.1.1.1.23291.1.341
 52^3-  375^2 =     -17 --- .0.1.1.1.16340.1.35
 55^3-  408^2 =     -89 --- .0.1.1.1.3746.8.3
 56^3-  419^2 =      55 --- .0.1.2.6425.239.2
 63^3-  500^2 =      47 --- .0.1.2.11019.1.1
 65^3-  524^2 =      49 --- .0.1.2.11696.3.12
 72^3-  611^2 =     -73 --- .0.1.1.1.10933.1.5
 99^3-  985^2 =      74 --- .0.1.2.30124.3.2
101^3- 1015^2 =      76 --- .0.1.2.31280.1.1631
109^3- 1138^2 =     -15 --- .0.1.1.1.202515.17.4
136^3- 1586^2 =      60 --- .0.1.2.102977.1.696
152^3- 1874^2 =     -68 --- .0.1.1.1.129727.1.97
$\endgroup$
  • $\begingroup$ I like this list. Will it take long to bump a up to 1000, b to 6000 or 7000, and count interesting cases where the power difference is less than 1000? (Not list, but find how many.) In particular, using Silverman's lower bound with K=1, it is of interest how often the lower bound is violated, especially with both exponents greater than 2. Gerhard "Wants Light On Smooth Numbers" Paseman, 2017.10.20. $\endgroup$ – Gerhard Paseman Oct 20 '17 at 19:15
  • 1
    $\begingroup$ In fact, if you have room to store a few million numbers, try the following: compute all the powers of 2 up to 10^12, and make a list. Observe the distribution of differences. Then repeat with powers of three (insert in list and observe small differences), then powers of five, six,seven,ten, all the way up to 10000. After that, it is just adding squares of numbers from 10001 to a million. Observe how small differences are distributed in each interval of, say 100 million. This should be a quick way to extend your table. Gerhard "Time Is Money And Power" Paseman, 2017.10.20. $\endgroup$ – Gerhard Paseman Oct 20 '17 at 19:57
  • $\begingroup$ Hmm, did not yet make a guess for the function of time-consumption, for the set of combinations of $a=2..199$ with $b=a+1..19999$ it needed about 20 seconds. To change bounds for the differences is just to replace $if (d \gt 100,next())$ into $if (d \gt 1000,next())$ and throw less material away. So far it is only a rough and simple routine which might have options to be optimzed. (For sanity check I've run this a couple of times with modified parameters always arriving at the same list, so it seems to be rather correct.) $\endgroup$ – Gottfried Helms Oct 20 '17 at 19:58
  • $\begingroup$ For programming purposes, it might be best to add to the list in terms of powers, to get interesting examples early. So start with fortieth powers, then 39th powers, and note the slowdown when you get to squares. Gerhard "Algorithm Refactoring Through Domain Revisioning" Paseman, 2017.10.20. $\endgroup$ – Gerhard Paseman Oct 20 '17 at 20:05
  • $\begingroup$ Ah well, I see, @Gerhard. Btw. I just notice, that small powers of $2$ and $3$ are missing, so I should also improve some parameter... It's late, perhaps tomorrow. $\endgroup$ – Gottfried Helms Oct 20 '17 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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