For positive integers $n$ and $d\ge 2$, let $S_d(n)$ be the digit sum of $n$ in base $d$.

When $a$ and $b$ are not powers of each other, is it always true that $$\liminf_{n\to\infty} S_a(n)+S_b(n)=\infty?$$

The limit superior is infinite, e.g. let $x_n=(ab)^{b^n}(a^n-1)+b^n-1$ then $S_a(x_n)+S_b(x_n)\ge (a+b-2)n$, and we know that if there is a counterexample, it will be sparse. This is the case I'm having difficulty eliminating: we need to prove that for any fixed $k$ there are at most finite $n$ such that $S_a(n)+S_b(n)=k$. This is true for $k=2$ when $k\ge n$ by $S_b(a^n)>1$, but I can't see a similar way to prove it for e.g. $k=3$.

I'm originally trying to prove the weaker claim that $$\liminf_{n\to\infty}\sum_{p\text{ prime}}\log(p)\left\lfloor\frac{S_p(n)}{p-1}\right\rfloor=\infty$$ which arises from the ratio $(n!)^{-1}\prod_pp^{\left\lfloor\frac{n}{p-1}\right\rfloor}$. The sum has an upper bound $O(\sqrt{n\log n})$, by considering $\left\lfloor\frac{S_p(n)}{p-1}\right\rfloor$ having at most $\sqrt{n/\log n}$ nonzero values for $p\ge\sqrt{n\log n}$, which fits experimental evidence.

Plot of sum against n.

  • 4
    $\begingroup$ It would follow from this plausible statement (which may be hard to prove on its own): for any fixed integers $m,k\geq1$, $$a^{x_1} + \dots +a^{x_m} = b^{y_1}+\dots+b^{y_k}$$ has a finite number of solutions in nonnegative integers $x_i, y_j$. $\endgroup$ Commented May 29 at 4:37
  • 6
    $\begingroup$ Sounds like a job for the Schmidt subspace theorem (or the theory of the S-unit equation). $\endgroup$
    – Terry Tao
    Commented May 29 at 5:41
  • 2
    $\begingroup$ There is $\Omega(\log\log n/\log\log\log n)$ bound for $\log a/\log b$ irrational by C.L. Stewart (see mathoverflow.net/q/30357) $\endgroup$
    – te4
    Commented May 30 at 5:00
  • 4
    $\begingroup$ The condition "$a$ and $b$ are not powers of each other" is not quite right; try $a=4$, $b=8$, and $n = 2^{6k}+1$ . . . $\endgroup$ Commented May 30 at 5:18
  • $\begingroup$ @NoamD.Elkies you're right, it should be rational powers of each other $\endgroup$
    – Darren Li
    Commented May 30 at 9:44

1 Answer 1


As observed in comments, it suffices to show that for fixed $m,k$, there are only finitely many solutions in non-negative integers to the equation $$ a^{x_1} + \dots + a^{x_m} = b^{y_1} + \dots + b^{y_k}. \tag{1}$$ To prove this we can assume inductively that the claim is already proven for smaller values of $m+k$. In particular we can assume that no non-trivial subsum of the $a^{x_1},\dots,a^{x_m}$ agrees with no non-trivial subsum of the $b^{y_1},\dots,b^{y_k}$, since this would split the above equation (1) into two equations of the form (1) with smaller values of $m+k$, and this would only generate finitely many solutions to (1) by the induction hypothesis.

Let $S$ denote the set of primes dividing at least one of $a$ or $b$, and define an integer $S$-unit to be a (rational) integer with all prime factors lying in $S$. Then (1) is asserting that the $m+k$ integer $S$-units $a^{x_1}, \dots, a^{x_m}, -b^{y_1},\dots,-b^{y_k}$ sum to zero. The claim now follows from the following result (a consequence of the Schmidt(-Schlickewei) subspace theorem):

Theorem Let $S$ be a finite set of primes, and $n \geq 1$. Then up to projective equivalence $(z_1,\dots,z_n) \mapsto (\lambda z_1,\dots,\lambda z_n)$, there are only finitely many solutions to the equation $z_1+\dots+z_n=0$ where $z_1,\dots,z_n$ are integer $S$-units with the property that no non-trivial subsum of these integer $S$-units sum to zero.

See for instance Corollary 1.1 of these notes of Evertse for a proof. (The fact that $a,b$ are not rational powers of each other ensures that each projective class of solutions to $z_1+\dots+z_{k+m}=0$ can generate at most one solution to (1).)

Remark 1. One can illustrate the use of the subspace theorem by focusing on the simple example $3^x = 2^y + 1$. Here we use a special case of the Schmidt--Schlickewei subspace theorem: For any $\delta>0$, and up to projective equivalence, the number of integer solutions $z_1, z_2$ to the inequality $$ \frac{\|z_1\|_\infty \|z_2\|_\infty}{\|z\|_\infty} \frac{\|z_1\|_2 \|z_2\|_2}{\|z\|_2} \frac{\|z_1+z_2\|_3 \|z_2\|_3}{\|z\|_3} \leq H(z)^{-2-\delta}$$ is finite, where $\|z_i\|_p$ is the $p$-adic valuation of $z_i$ (equal to $p^{-\nu}$ if $z_i$ is divisible by exactly $\nu$ powers of $p$), $\|z\|_\infty = |z|$ is the Archimedean valuation, $\|z\|_v := \max(\|z_1\|_v, \|z_2\|_v)$, and $H(z)$ is the absolute height of $z$ (which, if $z_1,z_2$ are coprime, is just $\max(|z_1|, |z_2|)$). But if one plugs in $z_1 = 2^y$ and $z_2=1$ here for some solution to $3^x = 2^y + 1$, one can calculate that the left-hand side decays like $H(z)^{-3}$, so there are only finitely many solutions to $3^x=2^y+1$.

Remark 2. Due to the use of the subspace theorem, this result is ineffective. It would be interesting to get a more effective bound on the solutions here. I experimented with trying to use Baker's theorem, but could not use this theorem to cover all cases (the gaps between consecutive $x_i$ or $y_j$ seem to play a role in whether this theorem is helpful).


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