Since the expression 2^k-3^x comes up a lot in analyzing the Collatz process, deep theorems like 2^k-3^x > 2^{2.56} come in handy. They were pioneered by Alan Baker in the 1960s and 70s.
Baker was actually interested in how closely a real number (like 1 / \log 3) could be approximated by a fraction (like p / q). Sort of like \pi being estimated by 22/7.
This is what Baker proved (for some “effective” constants a,b):
\cfrac{1}{\log_2 3}\ -\ \cfrac{p}{q}\ >\ \cfrac{a}{q^b}
The higher q gets, the better you can approximate. But there’s always a limit: you can never get closer than a / q^b.
I have no idea how Baker gets this. There’s a Terence Tao blog post about it, but man, the last time I tried to decipher one of those blog posts! Well, a good “explainer” on that would be great!
Anyway, I couldn’t figure out how people get from Baker’s inequality to something like 2^k-3^x > 2^{2.56}, so I tried to work it out.
Let’s give a name to Baker’s RHS, so that r stands for a / q^b. Then,
\cfrac{1}{\log 3}\ -\ \cfrac{p}{q}\ >\ r
\cfrac{q}{\log 3} - p > q r
3^{q / \log 3 - p} > 3^{q r}
3^p (3^{q / \log 3 - p} - 1) > 3^p (3^{q r} - 1)
3^{q / \log 3} - 3^p > 3^p (3^{q r} - 1)
3^{q \cdot \log_3 2} - 3^p > 3^p (3^{q r} - 1)
2^q - 3^p > 3^p (3^{q r} - 1)
Plugging Baker’s a/q^b back in for r:
2^q - 3^p > 3^p (3^{q \cdot (a / q^b)} - 1)
2^q - 3^p > 3^p (3^{a / q^{b-1}} - 1) \hspace{0.3in} (*)
2^q - 3^p > 3^p \cfrac{a}{q^{b-1}} \hspace{0.75in} (**)
which, if you like k and x better, is
2^k - 3^x > 3^x \cfrac{a}{k^{b-1}}
Anyway, this inequality is of use to Collatz people. The difference rises almost as fast as 3^x itself.
= = =
Justifying the (*) \rightarrow (**) step is utterly wack.
Let n stand for \frac{q^{b-1}}{a}.
3 > e \hspace{0.3in} (a true fact of nature)
3 > e > (\frac{n+1}{n})^n
3^{1/n} > \frac{n+1}{n}
3^{1/n} - 1 > \frac{n+1}{n}- 1
3^{1/n} - 1 > \frac{1}{n}
Substituting \frac{q^{b-1}}{a} back in for n,
3^{a/ q^{b-1}}- 1 = 3^{1/a^{-1} q^{b-1}}- 1 > \cfrac{1}{(a^{-1} q^{b-1})} = \cfrac{a}{q^{b-1}}
= = =
Baker doesn’t divulge his secret a and b, but Rhin gives an explicit formula:
q \cdot ln(2) - p \cdot ln(3) > e^{-13.3 (0.46057 + ln(p))}
which if you want to try your hand, can be cajoled into
2^k - 3^x > \cfrac{3^x}{250\ x^{13.3}}