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

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$?

-
You mean multiplication by $a \cdot b$, correct? – Bill Cook Oct 26 '11 at 19:08
yes: where i say $a_n \cdot b_n$ I mean the ordinary multiplication between natural numbers. – Lorenzo Cavallina Oct 26 '11 at 19:13
By "first $n$ digits", you mean "most significant $n$ digits"? I.e., $a_{n+1} = 2a_{n} + \sigma_{n}$, where $\sigma_{n}\in\{0,1\}$? – mjqxxxx Oct 26 '11 at 19:53
Your sequences (as well as the product) are 2-adic numbers. It does not feel intuitively likely that multiplication would preserve "thinness". Do you have any particular reason to expect that it would? – Henning Makholm Oct 26 '11 at 19:58
@ mjqxxxx By "the first $n$ digits" I mean the less significant ones. I.e. $a_{n+1}=a_n+\sigma_n\cdot 2^n$ where $\sigma_n \in \{0,1\}$ – Lorenzo Cavallina Oct 26 '11 at 20:10

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.

-
Thanks a lot, at least it's still a result! Maybe I should start looking for a counterexample! I am only a third year math student and I am new about p-adic numbers (I've just read the wikipedia article about!). – Lorenzo Cavallina Oct 26 '11 at 21:16
Well, congratulations on (almost) rediscovering them, then. – Henning Makholm Oct 26 '11 at 21:20
^^ Just a question, is there a way to define an order relation over the field of p-adic numbers? – Lorenzo Cavallina Oct 26 '11 at 21:23
It's easy to given them some order, but there isn't an order that is compatible with the addition and multiplication according to the ordered field axioms. – Henning Makholm Oct 26 '11 at 21:30
I was looking for something like a totally ordered subset of the set of p-adic numbers (I would say of the p-adic "integers", but I don't know if this makes sense) compatible with addition and multiplication ... never mind ;) And thanks for all your clarifications! – Lorenzo Cavallina Oct 26 '11 at 21:38

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}$.

-
Radically, I love it! Have you seen this coincidence in terminology used before? Also, it seems to provide a nice dual to/generalization of a simple proof that a particular number is transcendental. – Daniel Briggs Oct 27 '11 at 3:02
Google finds nothing relevant for "radically slow-growing" or variants thereof, so possibly no. I did consider calling them "pseudo-Liouville" instead, but I think they may have to grow even slower for the correspondence to be perfect. Apparently there is already something called p-adic Liouville numbers, which is rather more advanced. – Henning Makholm Oct 27 '11 at 11:52

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.

-
I wanted to set bits at the triangular numbers, but OEIS A001481 says a number $n$ is the sum of two triangulars if $4n+1$ is the sum of two squares and the density of these is $C/\sqrt{\log n}$. – Ross Millikan Oct 26 '11 at 22:42
@Ross, I went down the same blind alley. Probably one could set the bits at the numbers that are sums of two squares, since every integer is a sum of four squares, but again a proof is going to need an analysis of the parity of the number of representations, and the effect of carries. – Gerry Myerson Oct 27 '11 at 3:36
@Gerry, are there few enough sums-of-two-squares? – Henning Makholm Oct 27 '11 at 18:34
@Henning, yes, as Ross notes in his comment. Sums of two squares are thin. – Gerry Myerson Oct 27 '11 at 21:39
Hm, yes. I must be blind, sorry. – Henning Makholm Oct 27 '11 at 21:56

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$.

-