sum of binary and ternary digits

Question

A problem in group theory (indices of imprimitive groups) gives rise to the following conjectures in number theory. Suppose a positive integer $n$ has binary and ternary expansions $n=\sum_{k\geqslant0}b_k2^k=\sum_{k\geqslant0}t_k3^k$. For example, $6=2^2+2=2\cdot 3$; $81=2^6+2^4+1=3^4$.

Conjecture 1. If $\sum_{k\geqslant0}b_k=\sum_{k\geqslant0}t_k=2$, then $n\in\{6,10,12,18,36\}$.

Conjecture 2. If $\sum_{k\geqslant0}(b_k+t_k)=4$, then $n\in\{6,10,12,18,36,81\}$.

Terry Tao discusses the separation of powers of 2 and powers of 3; see his blog:

http://terrytao.wordpress.com/2011/08/21/hilberts-seventh-problem-and-powers-of-2-and-3/

Conjectures 1 and 2 are related to separation problems. For example, the four $n$ with $(\sum_{k\geqslant0}b_k,\sum_{k\geqslant0}t_k)=(1,2)$ or $(2,1)$ are related to the solutions to $|3^p-2^q|=1$, namely $(p,q)=(1,1),(2,3),(0,1),(1,2)$. More trivially, $(\sum_{k\geqslant0}b_k,\sum_{k\geqslant0}t_k)=(1,1)$ is related to the solution to $|3^p-2^q|=0$, namely $(p,q)=(0,0)$. I wonder whether one needs the values for the `effective constants' in Tao's blog, or whether elementary arguments suffice to prove these conjectures.

Answers to the question " $3^n - 2^m = \pm 41$ is not possible. How to prove it? " may help.

Answer 1

You can prove your conjecture by combining local methods, linear forms in logarithms, and computations (either brute force or continued fractions).

Suppose you have $\sum t_k=\sum b_k = 2$, i.e. $2^x+2^y=3^u+3^v$, $x>y$, $u\geq v$. Then $2^{2(x-y)}-1$ is divisible by $3^v$. Since 2 is a primitive root modulo 9, it is primitive modulo $3^k$, hence $2\cdot 3^{v-1}|2(x-y)$. In particular, $3^{v-1}\leq x$. In the same way we find that $2^{y-2}\leq u$.

Baker's method gives lower bounds for linear forms in logarithms. In this case the most appropriate result google gave me is due to Bugeaud ( http://www.birs.ca/workshops/2012/12ss131/files/bugeaud_LFL.pdf , Theorem C):

Let $a_1, a_2, b_1, b_2$ be rational integers, $a_1, a_2$ multiplicative independent. Let $A_1, A_2$ be real numbers satisfying $A_i\geq\max(3, a_i)$. Put $B=\frac{b_1}{\log A_2}+\frac{b_2}{\log A_1}$. Then for $\Lambda := |b_1\log a_1 + b_2\log a_2|$ we have the bound $$ \log \Lambda \geq -30.9\log A_1\log A_2\left(\max\left(21, 0.66+\log B\right)\right)^2. $$ In our case we have $a_1=2$, $a_2=3$, $b_1=x$, $b_2=u$. Then Baker gives us a lower bound for $\Lambda$, on the other hand we have $$ \Lambda = \log\frac{2^x}{3^u} = \log\frac{2^x+2^y}{3^u+3^v} + \log\frac{2^x}{2^x+2^y} + \log\frac{3^u+3^v}{3^u}, $$ and the first of the three terms on the right is 0, while the other two are very small and differ in sign, hence $\Lambda<\max(\frac{6u}{2^x}, \frac{3x}{3^u})$. I don't optimize $A_1$ and $A_2$, and just put $A_1=A_2=3$ and get $$ \max\left(\frac{6u}{2^x}, \frac{3x}{3^u}\right) > \exp\left(-37.3(0.57+\log(x+u))^2\right). $$ For $x\geq 10000$ this is impossible.

You could now check all quadruples $(x,y,u,v)$ with $x<10000$ by a computer, which is easy, since $u$ is uniquely determined by $x$, and $y$ and $v$ are small, or check that $2^x-3^u$ is large for all $x,u$ in this range by computing the continued fraction expansion of $\frac{\log 3}{\log 2}$.

Answer 2

A paper of Stewart [J. reine angew. Math., 1980] proves that your $\sum_{k \geq 0} (b_k+t_k)$ grows like $\log\log n/\log\log\log n$. This result is effective and rather much more general, but not explicit.

To actually resolve your conjectures, one can mostly argue locally. A paper where this is done somewhat systematically is one of Brenner and Foster [Pacific J. Math., 1982]. I think a couple of the exponential equations you require solved might need something more, like lower bounds for linear forms in $p$-adic and complex logarithms. These are applied to a problem very similar to yours in a pair of papers of Tijdeman and Wang [Pacific J. Math., 1988] and Wang [Indagationes Math., 1989]. THe applications of these techniques to your problem date back somewhat earlier to work of Ellison and of Stroeker and Tijdeman, both in conference proceedings (sorry, can't recall the references).

Answer 3

Both conjectures and generalizations of them follow from the n-term conjecture.

You want sums of small multiples of powers of $2$ and $3$ to be equal and the the number of terms to be small. In the n-term conjecture the radical is $6$, which implies effective bound on the largest power.