MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n$ be a positive integer. Given an integer base $b\ge 2$, let $C_b(n)$ be the number of non-zero digits in the expansion of $N$ in base $b$. Further, let $M(n)=\max\{C_b(n):b\ge 2\}$ be the maximum of all $C_b$. Obviously, for each $n$ only $b\le n$ count, and $M(n)\le 1+\log_2 n$.

I would like to understand the relation between the $C_b(n)$ for different bases $b$. It seems reasonable to conjecture (and I'm sure stronger conjectures exist) that if $b, b'$ are multiplicatively independent, then $C_b(n)+C_{b'}(n)>\varepsilon \log n$ for some $\varepsilon(b,b')>0$ and all $n$. However, this seems to be out of reach. The best I have found are estimates of the form $C_b(n)+C_{b'}(n)\ge \frac{\log\log n}{\log\log\log n}$, using Baker's Theorem.

My question is:

Can we do better by considering more bases? In particular, is it true that there is $\varepsilon>0$ such that $M(n) \ge \varepsilon \log n$ for all $n$?

The special case in which $n$ is a power would already be interesting, and is perhaps a little easier:

Does there exist $\varepsilon>0$ such that $M(2^k) > \varepsilon k$ for all $k$?

This question came up in studying the absolute continuity of the convolution of certain self-similar measures, a question at the interface of fractal geometry/dynamics/number theory.

share|cite|improve this question
Looks interesting - is there direct relevance to questions about intersections of Cantor sets, Furstenberg's conjecture etc? A numerical test (limit $10^{18}$) gives for the largest integer $n$ with $\max{C_2(n),C_3(n)}=k$ for $k=1\ldots 6$ as $2,513,65664, 272630016,10737942552,20342038921218$ This sequence is rather rapidly growing, but plausibly exponential, consistent with the first conjecture. – Carl Mar 20 '13 at 11:27
Carl - It is related in spirit to Furstenberg's conjectures but not directly. If the conjecture is true, I can use it to show that the arithmetic sum of $A_{1/3}$ and $A_{1/4}$ has positive Lebesgue measure, where $A_r$ is the central Cantor set with rate of dissection $r$. Morally this says something about the intersections, but far too weak to give a dimension bound on all of them. – Pablo Shmerkin Mar 21 '13 at 1:01
For a fixed value of k, do you know anything about numbers which, when expressed in bases 2, 3, and 6, have at most k nonzero digits? Gerhard "Guesses They Are Finitely Many" Paseman, 2013.03.20 – Gerhard Paseman Mar 21 '13 at 2:11
Gerhard - for every $k$ there is $N(k)$ such that for every $n\ge N(k)$, the expansion of $n$ in one of the bases $2$, $3$ has at least $k$ nonzero digits. This follows from the lower bound on $C_2(n)+C_3(n)$ in my post (so ultimately from Baker's Theorem), and gives a lower bound for $N(k)$ which is (roughly) doubly exponential in $k$. It'd be interesting to get better bounds for this as well. – Pablo Shmerkin Mar 21 '13 at 2:24

A full answer to your question seems tough, because for any fixed value of $\epsilon$, only finitely many bases are available to establish the bound. However, there is an elementary partial answer to your second question: The digits of $2^{n^2}$ in base $2^n-1$ are exactly the $n$th row of Pascal's triangle. A variation of this idea yields $M(2^k) = \Omega(\sqrt{k})$. This suggests the following strategy for general $n$: Choose a base $b$ so that $n = d+\prod_i (b+c_i)$ with $d \ll n$ and $0 < c_i \ll b$, in such a way that the leading digits of $n$ in base $b$ are the same as the coefficients of the polynomial $p(x) = \prod_i (x+c_i)$. I have not done a calculation, but maybe this could give you $M(n) = \Omega((\log n)^\alpha)$ for some $\alpha > 0$.

share|cite|improve this answer
Thanks! It is interesting that an elementary argument can go far beyond what one gets from Baker's Theorem at least when $n=2^k$. I'll check the details of your idea for the general case. – Pablo Shmerkin Mar 23 '13 at 20:51

Your Answer


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.