# How many solutions to $2^a + 3^b = 2^c + 3^d$?

A few weeks ago, I asked on math.stackexchange.com how many quadruples of non-negative integers $(a,b,c,d)$ satisfy the following equation:

$$2^a + 3^b = 2^c + 3^d \quad (a \neq c)$$

I found 5 quadruples: $5 = 2^2 + 3^0 = 2^1 + 3^1$, $11 = 2^3 + 3^1 = 2^1 + 3^2$, $17 = 2^4 + 3^0 = 2^3 + 3^2$, $35 = 2^5 + 3^1 = 2^3 + 3^3$, $259 = 2^8 + 3^1 = 2^4 + 3^5$

I didn't get an answer, but only a link to an OEIS sequence (no more quadruples below $10^{4000}$), so I'm asking the same question here.

Is there a way to prove that they are [not] infinite?

And, more generally, are there known tuples for which the following equation: $$p_{i_1}^{a_1} + p_{i_2}^{a_2} + ... + p_{i_n}^{a_n}=p_{i_1}^{b_1} + p_{i_2}^{b_2} + ... + p_{i_n}^{b_n}$$ holds for infinitely many (or holds only for finitely many) $a_i,b_i$?

That these are all the solutions to $2^a+3^b=2^c+3^d$ was conjectured by Pillai in the 1930s and proved by Stroeker and Tijdeman in 1982, using lower bounds for linear forms in logarithms. Finiteness was proved by Pillai.

Oh, and I should have added that the answer is "no" to your second question via a result of Evertse, provided you have no "vanishing subsums".

• The reference is R. J. Stroeker and R. Tijdeman, Diophantine equations, in the book Computational methods in number theory, Part II, 321–369, Math. Centre Tracts, 155, Math. Centrum, Amsterdam, 1982, MR0702521 (84i:10014). The proof is on pages 350-351; it's quite simple, but it does use another result that in turn uses Baker's method. The Pillai conjecture is sourced to a paper from 1945. – Gerry Myerson Apr 29 '14 at 0:10
• Mike might also have mentioned his own paper, Pillai's conjecture revisited, J. Number Theory 98 (2003), no. 2, 228–235, MR1955415 (2003j:11030). – Gerry Myerson Apr 29 '14 at 0:25

The answer is yes, there are finitely many for positive $a, b, c, d$, and you've found all of them.

See Theorem 7 of R. Scott, R. Styer, On the generalized Pillai equation $\pm a^x \pm b^y = c$, Journal of Number Theory, 118 (2006), 236–265. I quote:

Theorem 7. Let $a$ be prime, $a>b$, $b = 2$ or $b = 3$, $a$ not a large base-$b$ Wieferich prime, $1 \le x_1 \le x_2$, $1 \le y_1 \le y_2$, and $(x_1, y_1) \neq (x_2, y_2)$. If there is a solution $(a, x_1, y_1, x_2, y_2)$ to the equation $$\left|a^{x_1} - b^{y_1}\right| = \left|a^{x_2} - b^{y_2}\right|$$ then it is one of

\begin{align*} 3-2&=3^2-2^3,\\ 2^3-3&=2^5-3^3,\\ 2^4-3&=2^8-3^5,\\ \cdots&=\cdots \end{align*}

where the omitted cases are irrelevant. The three listed equations are your decompositions of $\fbox{11}$, $\fbox{35}$, and $\fbox{259}$.

Now we show that the answer is yes for non-negative $a, b, c, d$, and you've also found all of them.

The only solutions to your equation not covered by the above result correspond to solutions of $$1 - 2^x + 2^y = 3^z,$$ where we may assume $0 < x < y$.

If $z$ is odd, then the RHS is 3 modulo 4 and so we must have $x = 1$. Hence $3^z - 2^y = 3 - 2$ and so by the above we have the only solution as $(x, y, z) = (1,2,1)$. This is your decomposition of $\fbox{5}$.

If $z$ is even, then the RHS is a perfect square. Working modulo 3 we see that we must have $x$ odd and $y$ even. Write $z' = z/2, y' = y/2, x' = x-1$, and note that $x' > 0$ is even.

If $x' < y'$ then we have $(2^{y'}-1)^2 = 1 - 2^{y'} + 2^y < 1 - 2^x + 2^y < 2^y = (2^{y'})^2$, and so the LHS cannot be a perfect square. Hence $x' \ge y'$.

If we have $x' = y'$, then we have $3^{z'} = 2^{y'} - 1$; this gives the solution $(x,y,z) = (3,4,2)$, corresponding to your decomposition of $\fbox{17}$.

We claim that there are no other solutions.

Any other solution must have $x' > y'$. We rearrange and write $$\left(2^{x'} - 1 + 3^{z'}\right)\left(2^{x'} - 1 - 3^{z'}\right) = 2^{2x'} - 2^{2y'}.$$ Note that we must have $2^{x'}-1 > 3^{z'}$ so that the signs on each side match.

The RHS is divisible by $2^{2y'}$. As $x < y$ we have $2y' \ge x' + 2$.

We have $\gcd(2^{x'} - 1 + 3^{z'}, 2^{x'} - 1 - 3^{z'}) = \gcd(2^{x'} - 1 - 3^{z'},2\cdot3^{z'})$, which is divisible by 2 but not by 4. Hence one of $2^{x'} - 1 + 3^{z'}$ and $2^{x'} - 1 - 3^{z'}$ is divisible by $2^{2y' - 1} \ge 2^{x' + 1}$. But $$2^{x' + 1} = 2^{x'} + 2^{x'} > 2^{x'} - 1 + 3^{z'} > 2^{x'} - 1 - 3^{z'},$$ and so neither can be divisible by $2^{2y' - 1}$. Hence there are no more solutions.

Here is a proof of finiteness, along the lines of Jordan's answer. Assume without loss that $a>c$ and $d>b$. Then $$2^a-2^c=3^d-3^b,$$ or equivalently $$\frac{1-3^{b-d}}{1-2^{c-a}}=\frac{2^a}{3^d}.$$ Since $a>d$, Matveev's explicit bound for linear forms in logarithms implies that $$\Bigl\lvert\frac{2^{c-a}-3^{b-d}}{1-2^{c-a}}\Bigr\rvert=\lvert 2^a 3^{-d}-1\rvert \ge (ea)^{-R}$$ where $$R:=e\cdot 2^{3.5}30^5\log 3.$$

Next, $2^c$ is the largest power of $2$ which divides $3^{d-b}-1$; if $2^i$ denotes the largest power of $2$ which divides $d-b$, then either $[i=0\,\text{ and }\,c=1]$ or $[i>0\,\text{ and }\,c=i+2]$. Likewise, $b=0$ if and only if $a\not\equiv c\pmod{2}$; and if $a\equiv c\pmod{2}$ then $3^{b-1}$ is the largest power of $3$ which divides $a-c$. So in any case we have $c\le 2+\log_2(d-b)$ and $b\le 1+\log_3(a-c)$. For any fixed value of $d$ there are only finitely many possibilities for $a$ (since $2^{a-1}\le 2^a-2^c<3^d$), and hence also for $b$ and $c$. So assume that $d$ (and hence $a$) is sufficiently large; then $c\le 2+\log_2(d)<2+\log_2(a)$ and $b\le 1+\log_3(a)$ while $\log_3(2^{a-1})<d$, so $b\le\log_3(d)+r$ for some absolute constant $r$. Now $$\Bigl\lvert\frac{2^{c-a}-3^{b-d}}{1-2^{c-a}}\Bigr\rvert$$ is at most roughly $2^{-a}$, which is smaller than $(ea)^{-R}$ whenever $a$ is sufficiently large.

The excellent answer by Siksek to [this question]

distance between powers of 2 and powers of 3

may be useful -- the point is that, by bounds on linear forms in logarithms, you can't have a power of 2 and a power of 3 get too close to each other, which should imply that the two exponents of 2 and the two exponents of 3 must be quite close to each other. But this, in turn, implies that (2^a - 2^c) is really "mostly" a power of 2, and (3^b - 3^d) mostly a power of 3, and maybe you can get some mileage out of this.

• Let me complement this answer, for the first step: to show that 2^a-2^c and 3^b-3^d are nearly "pure powers" you can use a lemma of Hensel (sometimes known as lifting the exponent lemma) instead of linear forms in log's. For instance, say that c<a, then c is the 2-adic valuation of (3^b - 3^d) and you can bound it with the lemma (linear forms in p-adic logarithms also work here). – Pasten Apr 28 '14 at 15:42

Finiteness of solutions follows from a generalization of the $abc$ conjecture, the $n$ conjecture for $\mathbb{Z}$: http://cr.yp.to/bib/1994/browkin.pdf

Basically if $a_1 \ldots a_n$ are coprime integers, $a_1 + a_2 + \cdots a_n = 0$ and no proper subset sum vanishes $\log \max {|a_i|} / \log rad(a_1 \cdot a_2 \cdots a_n)$ is bounded by $2n-5$.

Also available here: http://www.math.unicaen.fr/~nitaj/abc.html#Generalizations

There is one route for an answer, which I believe (but was unable to prove yet) gives a definitive answer using elementary means only. This is to look at divisibilities according to the order of cyclic subgroups. Possibly someone else can proceed from the following reformulation of the problem.

We rearrange the original question first to get $$2^a-2^c = 3^d - 3^b$$ then to get $$2^c (2^A-1) = 3^b(3^D - 1)$$ which means, that we introduce the shorthands $A=a-c$ and $D=d-b$

Finally the obvious factors allow the rearrangement: $${2^A-1 \over 3^b} = {3^D - 1 \over 2^c}$$

Here we consider the divisibilities of the numerators by the denominators in general sitautions; we ...

... introduce two useful notations:

1. for extraction of "highest power of the primefactor $p$ in expression $a^n-1$" we write
"$\{a^n-1,p\}$"
2. the "Iverson-bracket" $[a:b]$ meaning $1$ if $b$ divides $a$ and $0$ if not

Then we have for powers of $2$ and primefactor $3$ $$\{2^n-1, 3\} = [n:2](1+\{n,3\}) \implies A=2 \cdot 3^{b-1}\cdot m$$ an "m"-parametrization for the variable $A$ (where $m$ is a positive number but does not contain the primefactor $3$)

For powers of 3 and primefactor 2 we have $$\{3^n-1, 2\} = 1+[n:2]+\{n,2\} \implies D=2 \cdot 2^{c-2}\cdot w$$ a "w"-parametrization for the variable $D$ (where $w$ does not contain the primefactor $2$)

With that parametrization we can write $${2^{2 \cdot 3^{b-1}\cdot m }-1 \over 3^b} = {3^{ 2 \cdot 2^{c-2}\cdot w } - 1 \over 2^c}$$ where we might discern between trivial and nontrivial solutions. "Trivial" for instance for the lhs might be assumed if $m=1$ and $b=1$ and similarly for the rhs.

If $b$ on the lhs is bigger, then the numerator on the lhs contains more additional primefactors which have "cyclic orders" of powers of 3, and if, for instance, m is even then the primefactor $5$ occurs:
From its general determination $$\{2^n-1, 5\} = [n:4](1+\{n,5\})$$ it follows, that if $n$ is divisible by $4$ then we have the primefactor $5$ in the $2^n-1$-expression, ...
... and thus if in the lhs the parameter $m$ is even, we'll have also the primefactor $5$ in the lhs and thus must have it the the rhs as well, and this gives then restrictions for the parameters $c$ and $w$ at the rhs - which then force the inclusion of new primefactors and so on.
One can check the "including" conditions for other primefactors as well in the hope, that with some primefactor a contradiction occurs: say, the inclusion on the left requires a parameter on the rhs which includes a further primefactor but which is not included in the lhs.

I've done this for some small primefactors but did not yet arrive at the wished contradiction. But perhaps there is already a theorem from which such a failing symmetric/parallel inclusion could be derived.

• One thing that makes it hard to construct a fully elementary argument is that the congruence conditions must somehow allow the known sporadic solutions and also the infinite family of trivial solutions $(a,b) = (c,d)$. – Noam D. Elkies Apr 28 '14 at 21:52