Binary representation of powers of 3

Question

I asked this question at Mathematics Stack Exchange but since I didn't got a satisfactory answer I decided to ask it here as well.

We write a power of 3 in bits in binary representation as follows. For example $3=(11)$, $3^2=(1001)$ which means that we let the $k$-th bit from the right be $1$ if the binary representation of this power of 3 contains $2^{k-1}$, and $0$ otherwise.

1. Prove that the highest power of 3 that has a palindromic binary representation is $3^3 = (11011)$.

2. Prove that $3 = (11)$ is the only power of 3 with a periodic binary representation (in the sense that it consists of a finite sequence of $1$s and $0$s repeated two or more times, like "$11$" consists of two repetitions of the bitstring "$1$").

Answer 1

Here is an extended hint for proving 2 (an almost complete proof is in the Update below). If $3^s$ base 2 is periodic, then you can represent it as $u(1+2^m+2^{2m}+...+2^{(t-1)m})=u\frac{2^{tm}-1}{2^m-1}$ for some numbers $u,m,t$. Therefore if $q_n(x)$ denotes the $n$-th cyclotomic polynomial, then $q_{tm}(2)$ must be a power of 3 (as a divisor of $3^s$). But it looks like $q_n(2)$ is never 0 modulo 9 (this should be possible to prove rigorously but I do not have time). Hence $q_{tm}(2)$ must be equal to 3 or 1 which gives a bound on $s$.

Update Since $2^m-1=0 \mod 9$ only when $m=0 \mod 6$. it is enough to consider $q_{6k}(2)$. Since $2^3=-1 \mod 9$, we only need remainders of cyclotomic polynomials modulo $x^3+1$ with coefficients modulo 9. Here are all 50 of them $$ \begin{array}{l} 1,3,{x}^{2},8x,8{x}^{2},1+8x,5+5{x}^{2},x+1,x+8,x+8 {x}^{2},\\\ 4x+5{x}^{2},{x}^{2}+1,1+8{x}^{2}+8x,2+3x+2{x}^{2}, 2+5x+4{x}^{2},2+8x+{x}^{2},2+{x}^{2}+7x,\\\ 2+2{x}^{2}+8x,2+6 {x}^{2}+7x,3+x+8{x}^{2},3+5x+3{x}^{2},\\\ 3+6x+2{x}^{2},3+2 {x}^{2}+7x,4+6x+3{x}^{2},4+7x+4{x}^{2},4+2{x}^{2}+5x,4 +3{x}^{2}+5x,\\\ 4+4{x}^{2}+6x,5+2x+7{x}^{2},5+4x+4{x}^{2} ,5+4{x}^{2}+5x, \\\ 6+2x+6{x}^{2}, \\\ 6+4x+5{x}^{2},6+7x+2{x}^{ 2},6+5{x}^{2}+3x,6+6{x}^{2}+4x,\\\ 6+7{x}^{2}+3x,7+2x+6{x} ^{2},7+4x+7{x}^{2},\\\ 7+6{x}^{2}+3x,8+2x+7{x}^{2},8+6x+8{ x}^{2},8+8x+{x}^{2}, \\\ 8+7{x}^{2}+x,8+8{x}^{2}+2x,{x}^{2}+x+1,{x} ^{2}+8x+1 \end{array}$$ None of these polynomials become 0 when evaluated at $2 \mod 9$.

As for the last claim about the size of $q_{mt}(2)$: every root of the cyclotomic polynomial is on the unit circle, so the values at 2 grow with the degree.

This almost completes the proof of 2 (one needs to show that the set of 50 polynomials is complete, but that can be done by induction).

Answer 2

Here is an alternative (and complete) proof of 2. Following Mark Sapir, we show that the only solution of $$ \frac{2^{tm}-1}{2^m-1} = 3^r $$ in positive integer triplets $(t,m,r)$ is $(2,1,1)$ and $(2,3,2)$. I am sure this was written down before, by the way.

Our main tool is the observation that $\mathrm{ord}_{3^n}(4)=3^{n-1}$ when $n\geq 1$ (in other words $2$ is a primitive root modulo $3^n$), which implies that $v_3(4^k-1)=1+v_3(k)$. The observation follows from $4^{3^{n-2}}\equiv 1+3^{n-1}\pmod{3^n}$ when $n\geq 2$, which in turn can be proved by induction or by the binomial theorem.

In the diophantine equation $r\geq 1$, hence $tm$ is even. If $m$ is even, then $$ r=v_3\left (\frac{2^{tm}-1}{2^m-1}\right)=(1+v_3(tm))-(1+v_3(m))=v_3(t), $$ so that $t$ is divisible by $3^r$. This is a contradiction: $$ 3^r=\frac{2^{tm}-1}{2^m-1} > t \geq 3^r, $$ which proves that $m$ is odd and $t$ is even. In that case $4^m-1\mid 2^{tm}-1$, and $$ \frac{2^{tm}-1}{4^m-1} = 3^s $$ for some $0\leq s\leq r$. As before $$ s=v_3\left (\frac{2^{tm}-1}{4^m-1}\right)=(1+v_3(tm))-(1+v_3(m))=v_3(t), $$ so that $t$ is divisible by $3^s$. This is a contradiction when $t\geq 4$: $$ 3^s=\frac{2^{tm}-1}{4^m-1} > 4(t/2-1)\geq t \geq 3^s, $$ which proves that $t=2$. Now the original diophantine equation becomes $$ 2^m+1=3^r,$$ where $m$ is odd. Then $1+v_3(m)=v_3(4^m-1)=r$, so that $m$ is divisible by $3^{r-1}$. It follows that $1+2^{3^{r-1}}\leq 3^r$. It is easy to see that this holds only for $r=1$ and $r=2$, which yields $m=1$ and $m=3$, respectively.