8
$\begingroup$

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

  • 0
    @TonyK yes, I mean "at most $n$"2011-10-27

4 Answers 4

3

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.

  • 0
    Well, I'm far from an expert in p-adic theory, but: There is a subring called "p-adic integers" -- which includes your sequences (in fact your sequence conditions correspond exactly to the "algebraic approach" in the Wi$k$ipedia article). The full field of p-adic numbers is its field of fractions. So even if you could order the p-adic integers in a reasonable way, the ordering that induces on the fraction field cannot be nice -- which seems to me to indicate that the ordering on the p-adic integers _wouldn't_ be nice in the first place either.2011-10-26
3

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

  • 0
    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](http://www-math.mit.edu/~kedlaya/18.787/exponents.pdf), which is rather more advanced.2011-10-27
2

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.

  • 0
    @Henning, no blinder than I was when I wrote $1/\log n$ at that other question.2011-10-27
0

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