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

  • $\begingroup$ You mean multiplication by $a \cdot b$, correct? $\endgroup$
    – Bill Cook
    Oct 26, 2011 at 19:08
  • $\begingroup$ yes: where i say $a_n \cdot b_n$ I mean the ordinary multiplication between natural numbers. $\endgroup$ Oct 26, 2011 at 19:13
  • $\begingroup$ 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\}$? $\endgroup$
    – mjqxxxx
    Oct 26, 2011 at 19:53
  • $\begingroup$ 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? $\endgroup$ Oct 26, 2011 at 19:58
  • $\begingroup$ @ 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\}$ $\endgroup$ Oct 26, 2011 at 20:10

4 Answers 4


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.

  • $\begingroup$ 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!). $\endgroup$ Oct 26, 2011 at 21:16
  • $\begingroup$ Well, congratulations on (almost) rediscovering them, then. $\endgroup$ Oct 26, 2011 at 21:20
  • $\begingroup$ ^^ Just a question, is there a way to define an order relation over the field of p-adic numbers? $\endgroup$ Oct 26, 2011 at 21:23
  • $\begingroup$ 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. $\endgroup$ Oct 26, 2011 at 21:30
  • $\begingroup$ 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! $\endgroup$ Oct 26, 2011 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}$.

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 27, 2011 at 3:02
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2011 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.

  • $\begingroup$ 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}$. $\endgroup$ Oct 26, 2011 at 22:42
  • $\begingroup$ @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. $\endgroup$ Oct 27, 2011 at 3:36
  • $\begingroup$ @Gerry, are there few enough sums-of-two-squares? $\endgroup$ Oct 27, 2011 at 18:34
  • $\begingroup$ @Henning, yes, as Ross notes in his comment. Sums of two squares are thin. $\endgroup$ Oct 27, 2011 at 21:39
  • $\begingroup$ Hm, yes. I must be blind, sorry. $\endgroup$ Oct 27, 2011 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .