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
    You mean multiplication by $a \cdot b$, correct?2011-10-26
  • 0
    yes: where i say $a_n \cdot b_n$ I mean the ordinary multiplication between natural numbers.2011-10-26
  • 0
    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\}$?2011-10-26
  • 0
    Your sequences (as well as the product) are [2-adic numbers](http://en.wikipedia.org/wiki/P-adic_number). It does not feel intuitively likely that multiplication would preserve "thinness". Do you have any particular reason to expect that it would?2011-10-26
  • 0
    @ 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\}$2011-10-26
  • 0
    @HenningMakholm if both $a_n$ and $b_n$ are convergent, so is $(a \cdot b )_n$. So I thought the notion of thinnes could be a useful generalization, since a convergent sequence of this kind is always "thin".2011-10-26
  • 0
    @Lorenzo, what does "convergent" mean for you here? Your second condition guarantees that $a_n$ and $b_n$ will converge in the 2-adic metric whether or not it they are thin.2011-10-26
  • 0
    ... sorry, I just meant $a_n$ seen as a sequence of natural numbers was convergent ... i.e. $a_n=l$ from a certain $n_0$2011-10-26
  • 0
    "$\forall n \in \mathbb{N}$ the number $a_n$ is represented with $n$ binary digits": You mean "at most $n$ binary digits", right?2011-10-26
  • 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
    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!).2011-10-26
  • 0
    Well, congratulations on (almost) rediscovering them, then.2011-10-26
  • 0
    ^^ Just a question, is there a way to define an order relation over the field of p-adic numbers?2011-10-26
  • 0
    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](http://en.wikipedia.org/wiki/Ordered_field) axioms.2011-10-26
  • 0
    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!2011-10-26
  • 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 Wikipedia 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}$.

  • 1
    **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.](http://mathoverflow.net/questions/49348/what-is-the-simplest-most-elementary-proof-that-a-particular-number-is-transcend/49359#49359)2011-10-27
  • 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
    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}$.2011-10-26
  • 0
    @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.2011-10-27
  • 0
    @Gerry, are there few enough sums-of-two-squares?2011-10-27
  • 0
    @Henning, yes, as Ross notes in his comment. Sums of two squares are thin.2011-10-27
  • 0
    Hm, yes. I must be blind, sorry.2011-10-27
  • 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$.