A property of some sequences of natural numbers (and their binary representation)

Question

Let's consider a sequence of natural numbers $a_n$, represented in binary, with the following properties:

• $\forall n \in \mathbb{N}$ the number $a_n$ is represented with $n$ binary digits
• $\forall n \in \mathbb{N}$ the first $n$ digits (counting from the first to the right) of $a_{n+1}$ are the same as those of $a_n$

We will say that such a sequence $a_n$ is "thin" if, by defining $\alpha_n$ as the number of "ones" in the binary representation of $a_n$, then: $$\lim_{n\rightarrow \infty} \frac{\alpha_n}{n}=0$$ Now, let's define $(a\cdot b)_n$ as the number with binary representation corresponding to that of the first n digits of the binary representation of $a_n\cdot b_n$, (I have already proven this is a valid definition). Is it true that, if $a_n$ and $b_n$ are thin sequences, then so is $(a\cdot b)_n$?

Answer 1

Not a solution, but too long for a comment:

It seems to be hard to construct an explicit counterexample, but here is a heuristic probabilistic argument that they ought to be abundant. Consider random thin $a$ and $b$ -- specifically, let $$a=\sum_{n=1}^\infty A_n2^n,\quad b=\sum_{n=1}^\infty B_n2^n$$ where the limits are taken in the 2-adic metric, and the $A_n$ and $B_n$ are independent $\{0,1\}$-valued random variables such that $$P(A_n=1)=P(B_n=1)=\frac{1}{\sqrt n}$$ Then $a$ and $b$ are thin almost surely. Thus, unless $c=ab$ is also thin almost surely, there must be a counterexample somewhere. We have $$c=\sum_{n=2}^\infty 2^n C_n \qquad\text{where } C_n=\sum_{k=1}^{n-1} A_kB_{n-k}$$ The expected value of $C_n$ is $$E(C_n)=\sum_{k=1}^{n-1} \frac{1}{\sqrt{k}}\frac{1}{\sqrt{n-k}}\ge\sum_{k=1}^{n-1}(\frac{1}{\sqrt{n/2}})^2 = \frac{n-1}{n/2} = 2-\frac{2}{n}$$ Now, the $C_n$'s are not really independent, but if we cheat and pretend they are, then $c$ is the sum of lots of random bits whose density does not go towards zero for high $n$'s. It is still conceivable that carries between the positions will make all of those random bits magically combine to only sparsely many single one-bits in the actual expansion of $c$, but it seems to be a stretch to suggest that such magic happens almost surely.

Answer 2

A different way out might be to strengthen the requirement for thinness. In the question, a 2-adic integer $a$ is called "thin" if $\frac{\alpha_n}{n}\to 0$ for $n\to \infty$ -- that is, if $\alpha_n$ is $o(n)$.

Let's call $a$ radically thin iff $\alpha_n$ is $o(n^\varepsilon)$ for all $\varepsilon>0$. Then it is simple to show that the product of radically thin numbers is itself radically thin, and similarly for the sum. (But, alas, the difference between radically thin numbers can be quite fat, so we don't get a subring. This is probably why we've never heard of the concept before).

There are (uncountably many) radically thin numbers that are not in $\mathbb Z$; an example is $\sum_{n=1}^\infty 2^{2^n}$.

Answer 3

I suspect that the following construction gives a counterexample, but it will be very hard to prove it.

Let $a_n=1$ iff $n$ is an odd prime, let $b_n=1$ iff $n-1$ is an odd prime. These are both thin since the primes are a set of density zero. If we call the product $c$, then $c_n$ will depend on the parity of the number of representations of $n$ as $p+q+1$, where $p$ and $q$ are odd primes, and also on the effect of carries from lower values of $n$. Most odd numbers have at least one such representation, and my guess is that when the effect of the carries is taken into account the limit we want will be at least 1/4, possibly 1/2.

Answer 4

Here is an explicit counterexample.

To restate the question: if $a$ is a 2-adic integer, define $\#_n(a)$ to be the number of $1$ bits in the least significant $n$ bits of the binary expansion of $n$. Then the question is whether $\#_n(ab)$ is $o(n)$ provided that $\#_n(a)$ and $\#_n(b)$ are both $o(n)$.

Let $a:=\sum_{n\ge 0} c_n 2^n$ and $b:=\sum_{n\ge 0} d_n 2^n$, where $c_n$ is $1$ if $n$ is expressible as a sum of distinct powers of $2$ with even exponents and $0$ otherwise and $d_n$ is $1$ if $n$ is expressible as a sum of distinct powers of $2$ with odd exponents and $0$ otherwise. Then $\#_n(a)=O(\sqrt{n})$, $\#_n(b)=O(\sqrt{n})$, but $\#_n(ab)=n$.