# Bound on $a,b,c,d$ and truth of statement $\forall \, x \in \mathbb N, \exists \, a,b,c,d \le {l(x)} \in \mathbb N:x=a^b+c^d$

To render the statement in the title in relatively simple English, "For every natural number $x$, there exist four natural numbers $a,b,c,d \le l(x)$, where $l(x)$ is a function of $x$ which bounds these numbers, such that $x=a^b+c^d$. I have attempted to do some research on whether this statement is true, with no success. Obviously if $0$ is included as a possible value for $a,b,c,d$ then the statement is always true and an obvious bound on $l(x)$ is $x$, but I am excluding it for the sake of a more interesting problem. I haven't done much numerical testing of this one, so it is possible that there very low numbers that prove this false.

On a different but related question, we look at the similar statement $$\forall \, x \in \mathbb N, \exists \, a,b,c,d \le {L(x)} \in \mathbb N:x=a*3^b+c*2^d$$. Similarly, the statement is always true if $0$ is included as a possible value of $a,b,c,d$, as $b$ and $c$ can be set to $0$ and $a$ to $x$. If we exclude $0$, for all numbers that I have tested greater than $6$ the statement holds true for some value of $L$. I have, however, completely failed at determining any good bounds on $L$, other than that it appears to be in $O(x^c)$ where $\frac 1 4 \lt c \lt \frac 1 2$. I don't have a proof for that, just numerical evidence.

Truth of these statements, expressions for $l$ and $L$?

-
Take $b=c=d=1, a=x-1$. – vadim123 Jul 14 '14 at 18:52
So what is your question? – Crostul Jul 14 '14 at 18:55
@Crostul I'm trying to find a) whether these two statements are always true, under the given conditions, and b) expressions for the functions $l$ and $L$. vadim123: Thank you, I should have thought of that. Is it possible to get an expression for $l$? – Laertes Jul 14 '14 at 18:59
@AdamHughes: He meant that for any $x$, the statement is true because $b,c,d$ can be $1$ and $a$ can be $x-1$. – Laertes Jul 14 '14 at 19:19
If you allow either $b$ or $d = 1$, then for any $x > 4$, you can pick $a = \lceil \sqrt{x}\rceil - 1$, $b = 2$, $c = x - a^2$ and $d = 1$. this leads to a bound $$l(x) \le \max( a, c ) \le 2\lceil\sqrt{x}\rceil -1$$ – achille hui Jul 14 '14 at 19:59

For the second problem, if $u,v$ are relatively prime, then every integer can be written as $xu+yv$, if we allow $x,y\in\mathbb Z$. This is because there exists a solution of $xu+yv=1$ with $x,y\in\mathbb Z$ and we can simply multiply this. Next, if $n=xu+yv$, then also $n=(x\pm v)u+(y\mp u)v$ so that a solution with $0<x\le v$ must exist. We conclude that a solution with $x,y>0$ exists for all $n>uv$.

Now for given $n\ge 10$, let $d=\lfloor \log_2\sqrt {n-1}\rfloor$ and let $b=\lfloor \log_3\frac {n-1}{2^d}\rfloor$. Then

• $n\ge 10$ implies $d\ge 1$ as required
• $2^d\le \sqrt{n-1}$ implies $\frac{n-1}{2^d}\ge\sqrt{n-1}\ge3$ and hence $b\ge1$ as required.
• By the preceding paragraph, there exist integers $a,c>0$ such that $a\cdot 3^b+c\cdot 2^d=n$.
• From $2^{d+1}> \sqrt{n-1}$ we conclude $c<\frac n{2^d}< \frac{2n}{\sqrt{n-1}}=O(\sqrt n)$
• From $3^{b+1}>\frac{n-1}{2^d}\ge\sqrt{n-1}$, we conclude $a<\frac{n}{3^b}<\frac{3n}{\sqrt{n-1}}=O(\sqrt n)$.

This confirms your observation that $L=O(\sqrt n)$ (and you can extract an exact expression from the above).

You cannot expect any substantially better bound: Assume $L=O(n^\alpha)$ with $\alpha<\frac12$, say $L\le Cn^\alpha$ for all $n>n_0$. For $N\in\mathbb N$, there are about $CN^{2\alpha}\log_2 N\log_3N$ tuples $(a,b,c,d)$ with $a,c\le CN^\alpha$ and $3^b, 2^d<N$. For large $N$, we have $CN^{2\alpha}\log_2 N\log_3N\ll N$, hence there are not enough tuples to provide solutions for all $n$ with $n_0<n\le N$.

-