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

Given two integers $a \ge b >1$, can we encode them as a unique integer $a^b + b^a$?


I asked this question on math.SE, and after surviving a week with a bounty, it seems that this question is harder than I initially thought.

Apparently these things have been named Leyland Numbers, but none of the literature I've been able to find on them provides proof that there are no repeats.

share|improve this question
9  
A numerical check shows that $a^b+b^a$ is unique for $2\leq a<b\leq 1000$. –  Joonas Ilmavirta Aug 14 at 17:55
    
Since nobody answered the question until now (after 8 vote), it seems that it is hard. But where am I wrong? Let $a=b+x$, so for every fixed $b$, the function $f_b(x)=(b+x)^b+b^{b+x}$ is increasing in variable $x$. So induction on $b$ must solve the problem. –  Shahrooz Janbaz Aug 14 at 19:15
    
@Shahrooz, finding an inductive argument doesn't seem simple. If you have one, do show. If there is a counterexample $a^b+b^a=c^d+d^c$, we can assume wlog that $1<a<c<d<b$, and the trivial increasing argument fails. –  Joonas Ilmavirta Aug 14 at 19:35
10  
The problem looks at least as hard as the Catalan conjecture en.wikipedia.org/wiki/Catalan's_conjecture , which concerns the equation $a^b = c^d + 1$ instead of $a^b + b^a = c^d + d^c$, and an unconditional solution is likely out of reach of current methods. The 4-variable version of the abc conjecture (see jstor.org/stable/2153551 ) may be able to imply the conjecture (or at least a large fraction of it), though. –  Terry Tao Aug 14 at 22:05
2  
Given a little time for this to settle in, this might be a candidate for "MO-Hard": meta.mathoverflow.net/questions/1820/mo-hard-questions –  Todd Trimble Aug 14 at 23:48

2 Answers 2

up vote 22 down vote accepted

I will show that if we assume the $abcd$ conjecture (which is the case $n=4$ of Browkin and Brzezinski's $n$-conjecture that generalizes the $abc$ conjecture), then $a^b+b^a=c^d+d^c$ has only finitely many solutions with $\{a,b\}\neq \{c,d\}$.

The $abcd$ conjecture claims that if $a,b,c,d$ are integers with $a+b+c+d=0$ and nonzero subsums (i.e. $a+b+c\neq 0$ etc.), $\gcd(a,b,c,d)=1$ and $\varepsilon>0$, then $$\max\{|a|,|b|,|c|,|d|\}\leq K_{\varepsilon} \text{rad}(abcd)^{3+\varepsilon}$$ (it is enough for us to assume the conjecture with any absolute constant in place of $3+\varepsilon$). Here $\text{rad}(m)$ is the product of the prime divisors of $m$. Given that Mochizuki seems to have proved the $abc$ conjecture and some generalizations of it, perhaps the $abcd$ conjecture is not that distant an assumption.

If $a^b+b^a=c^d+d^c$ and $\gcd(a,b,c,d)=1$, we obtain $$\max\{a^b,b^a,c^d,d^c\}\leq K_{\varepsilon}\text{rad}(a^bb^ac^dd^c)^{3+\varepsilon}=K_{\varepsilon}\text{rad}(abcd)^{3+\varepsilon}\leq K_{\varepsilon}(abcd)^{3+\varepsilon},$$ unless some subsum of $a^b+b^a-c^d-d^c=0$ is zero, which would give $a^b=c^d$ and $b^a=d^c$ (or vice versa), but then $a$ and $c$ have the same prime factors, and writing $a=\prod_{i=1}^s p_i^{\alpha_i}, b=\prod_{i=1}^s p_i^{\beta_i}$, we see from $a^b=c^d$ that $\frac{\alpha_i}{\beta_i}=\frac{d}{b}$, which is independent of $i$, so $a\mid c$ or $c\mid a$. Similarly $b\mid d$ or $d\mid b$. After this it is easy to see that $a^b=c^d$, $b^a=d^c$ has no nontrivial solutions. In fact, if for instance $d=kb,a=\ell c$, then after simplification the equations become $\ell=c^{k-1},k=b^{\ell-1}$, so $k\geq 2^{\ell-1}$ and then $\ell\geq 2^{2^{\ell-1}-1}$. Hence $\ell=2$ and similarly $k=2$ (or $\{a,b\}=\{c,d\}$), but then $b=c$, and thus $a=d$.

Now we may assume that the subsums are nonzero. Choose $\varepsilon=1,$ say, and let $d=\max\{a,b,c,d\}$. Then $2^d\leq c^d\leq K_1\text{rad}(abcd)^4\leq K_1\cdot d^{16}$, so $d$ is bounded by an absolute constant, and hence $a,b,c,d$ are all bounded.

Now assume $r=\gcd(a,b,c,d)>1$. The next step is to show that $r$ is bounded. Now $a^b+b^a=c^d+d^a$ is of the form $x^r+y^r=z^r+w^r$, where $x=a^{\frac{b}{r}},...,w=d^{\frac{c}{r}}$. We will show that if $r$ is large and $(x,y,z,w)$ is any quadruple of positive integers satisfying $x^r+y^r=z^r+w^r$, then $\{x,y\}=\{z,w\}$. By homogeneity, it suffices to show that the coprime solutions satisfy $\{x,y\}=\{z,w\}.$ Since we were allowed to make the assumption $\gcd(x,y,z,w)=1$, the $abcd$ conjecture implies $$\max\{x^r,y^r,z^r,w^r\}\leq K_1\text{rad}(x^ry^rz^rw^r)^4\leq K_1(xyzw)^4,$$ unless a subsum of $x^r+y^r-z^r-w^r$ vanishes, which leads to $\{x,y\}=\{z,w\}$. If the subsums are nonzero and $w=\max\{x,y,z,w\}$, then $w^r\leq K_1w^{16}$, so $r$ is bounded or $w=1$. The last case leads to $x=y=z=w=1$. Therefore, for large $r$, the only solutions to $x^r+y^r=z^r+w^r$ are those where $\{x,y\}=\{z,w\}$. Thus also $\{a^b,b^a\}=\{c^d,d^c\}$, which was already seen to give no nontrivial solutions.

Finally, let $M$ be an absolute constant that is an upper bound for $r$. Let $R=\gcd(a^b,b^c,c^d,d^c)$. We apply the $abcd$ conjecture once again to see that $\max\{\frac{a^b}{R},\frac{b^a}{R},\frac{c^d}{R},\frac{d^c}{R}\}\leq K_1\text{rad}(abcd)^4$. Now if $abcd$ has no prime divisor greater than $M$, we have $$\min\{a^b,b^a,c^d,d^c\}\geq R\geq c_0\max\{a^b,b^a,c^d,d^c\}$$ for some absolute constant $c_0>0$. Now if there exists a prime $p_1$ that divides some of $a,b,c,d$ but not all of them, then $$R\leq \prod_{p\leq M, p\neq p_1}p^{\min\{v_p(a^b),v_p(b^a),v_p(c^d),v_p(d^c)\}}\leq \frac{\max\{a^b,b^a, c^d, d^c\}}{2^{\min\{a,b,c,d\}}}\quad \quad (1).$$ If no such $p_1$ exists, all the numbers $a,b,c,d$ have the same prime factors. Let $a=\prod_{i=1}^s p_i^{\alpha_i},...,d=\prod_{i=1}^s p_i^{\delta_i}$. The condition $\gcd(a,b,c,d)\leq M$ tells $\min\{\alpha_i,\beta_i,\gamma_i,\delta_i\}\leq M$. Let $P^{\delta}$ be the largest prime power dividing $d$. Then $\min\{v_{P}(a),v_{P}(b),v_{P}(c)\}\leq M$ if $d$ is large. For example, let $v_{P}(c)\leq M$. Write $d=P^{\delta}D,c=P^{\gamma}C$, where $P\nmid C,D$. Then $$R=\gcd(a^b,b^a,c^d,d^c)\leq \gcd(c^d,d^c)\leq P^{Md} D^c=P^{Md-c\delta}d^c\leq M^{Md}d^{-\frac{c}{s}}d^c,$$ where $s\leq M$ is the number of prime factors of $d$. The last quantity is at most $\left(\frac{d}{2}\right)^c$ if $\frac{1}{2}d^{\frac{1}{s}}\geq M^{\frac{Md}{c}},$ which holds for large enough $d$ if $\frac{d}{c}$ is bounded. It must indeed be bounded since we had $\frac{c^d}{d^c}\geq c_0$. Therefore $(1)$ holds again for all large $d$.

Next we show that $(1)$ holds also if $a,b,c,d$ have some prime factors greater than $M$, and then use $(1)$ to deduce a contradiction.

Now one of $a,b,c,d$ has a prime factor $p_0>M$. For example, let $p_0\mid d$. Then $$R\leq \prod_{p\leq M}p^{v_p(d^c)}\leq \left(\frac{d}{p_0}\right)^c\leq \frac{\max\{a^b,b^a,c^d,d^c\}}{2^{\min\{a,b,c,d\}}},$$ so $(1)$ must always hold for large $d$. However, we had $R\geq \frac{\max\{a^b,b^a,c^d,d^c\}}{K_1\text{rad}(abcd)^4}\geq \frac{\max\{a^b,b^a,c^d,d^c\}}{K_1 d^{16}}$. Thus $K_1d^{16}\geq 2^{\min\{a,b,c,d\}}$. But
$$\min\{a,b,c,d\}^d\geq \min\{a^b,b^a,c^d,d^c\}\geq R\geq \frac{\max\{a^b,b^a,c^d,d^c\}}{K_1d^{16}}\geq \frac{c^d}{K_1d^{16}},$$ implies $\min\{a,b,c,d\}\geq k_0c$ for some constant $k_0$,so $K_1d^{16}\geq 2^{k_0c}$. Still we have $\frac{d^c}{c^d}\geq \frac{1}{K_1d^{16}}$. In particular, $d^c\geq \frac{2^d}{K_1d^{16}}$, so $c\geq k_2 \frac{d}{\log d}$. But then $K_1d^{16}\geq 2^{k_0c}\geq 2^{k_3\frac{d}{\log d}}$ shows that $d$ is bounded and hence all $a,b,c,d$ are bounded.

share|improve this answer
    
Please, You could repost this answer (or just a link to it) at M.SE. –  Krokop Aug 17 at 19:12

Long for a comment. I posted this at the other site, no positive feedback and a downvote, so I deleted it. I think I will leave this one here, as it provides clues for those who may actually know Diophantine approximation.

Apparently, the only way to get such values anywhere near each other (relative to the approximate size of the numbers) is this: with $a \leq b$ and $c \leq d,$ require that $a^b = c^d:$

        a^b   + b^a                                   a    b   

3381391913522726342930221472392241170198527453108273  3   108
3381391913522726342930221472392241174102833364161905  9   54
3381391914570258878524555694985750092390198488063857  27   36


1532495540865888858358347027150309183618739122183634576  2   180
1532495540865888858358347027150309183618739122249212176  4   90
1532495540865888858358347027150309183618907083783602176  8   60
1532495540865888858358347027433057625521180681021492801  16   45
1532558881152551831636053189437255995505349018645430272  32   36

If you look at nearby pairs that do not fit this pattern, they stay well away from each other, essentially no more than two agreeing initial decimal digits, no matter how large the numbers get. So, I think there is a Diophantine approximation approach to this, because it is easy to show, in the pattern i show above, that the numbers are not really equal. For what it may be worth, I was able to fit the 744 smallest values at http://math.stackexchange.com/questions/882987/is-abba-unique-for-all-integers-a-and-b/887719#887719

If anyone would like a copy to stare at, I have a text file of the smallest 1203 numbers with the a,b values, goes up to just below 10^55. They do not show the a,b value at https://oeis.org/A076980 and https://oeis.org/A076980/b076980.txt

Alright, ran it up to $10^{100}$ and told the machine to post only when neither $a$ nor $c$ is a power of the other; the best possible was ratio 1.00019 in $a=21,b= 75; \; \; c= 18,d= 79:$

1.00019   1467057395569175013279367871218018520179137565145308058766161340110629908834258848825913627259358376   21   75 ::  18   79

from 
1467057395569175013279367871218018520179137565145308058766161340110629908834258848825913627259358376         21    75     ====
1467330358978795477359675119796677254153876536271837501594000043530917147104689722542557490436631393         18    79     ====

We can do a little better with a variant of the $a^b = c^d$ thing above, but these are not impressive, as proof of inequality is still evident:

1.00002   33554432   8   8 ::  2   25
1   36893488147419103232   16   16 ::  2   65
1   2923003274661805836407369665432566039311865085952   32   32 ::  2   161

So, for example, $32^{32} + 32^{32} = 2^{161},$ but there is still a difference of $161^2,$ which is tiny in comparison but nonzero. Anyway, same general offer, I have the two text files if anyone wants to look, my gmail address is better.

share|improve this answer
5  
Although the conclusions you're drawing from your empirical observations are probably true, it seems unlikely that current techniques can prove them unconditionally. After all, it's already very difficult to show that $a^b - c^d=1$ has only one solution (Catalan's conjecture), so it will be even harder to show that $a^b - c^d$ can't be "small". –  Timothy Chow Aug 15 at 1:24
1  
@TimothyChow, it's a pity. Very impressive to see thousands of these huge numbers, 100 digits long but no more than four agree. –  Will Jagy Aug 15 at 2:11
    
No real matter; the best I could do up to $10^{1000}$ was $a=46,b=154,c=7,d=303,$ both about $1.16066 \cdot 10^{256}.$ Ratio about 1.000000104, relative error about 1 part in 9,574,939. –  Will Jagy Aug 15 at 4:34
    
Your $(a,b,c,d)=(21,75,18,79)$ example was $a-c=3,d-b=4$. This $(46,154,7,303)$ looks "different", and is, but it yields the (half as good) case $(46,308,49,303)$ with $c-a=3,b-d=5.$ Fix smallish $i,j$ and set $a^b=c^d$ with $a-c=i,d-b=j.$ So $b\ln{a}=(b+j)\ln{(a-i)}$ This determines $b$ as a real function of $a.$ Run through integer $a$ and try to find $b$ nearly an integer. I don't know if anything better turns up easily. –  Aaron Meyerowitz Aug 15 at 9:27
    
In any case, it seems worth asking if we can have $a^b+b^a$ "real close" to $c^d+d^c$ (say ratio less than $1.1$) with $a \lt b$ and $c \lt d$ (sneakily ruling out $a=b=2^m$) without having $a^b$ and $c^d$ essentially as close. –  Aaron Meyerowitz Aug 15 at 9:33

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.