Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For any number $x$, I define the "density" $d(x)$ to be the ratio of the number of "one" digits and the number of all digits in the binary expansion of $x$. For example, $d(13)=\frac{3}{4}$ and $d(9)=\frac{2}{4}$.

I run some experiments and have the following observation.

  • $d(x^2)\le0.87$ for all $x \in [2,10^7]$.
  • $d(x^{2^2})\le 0.79$ for all $x \in [2,10^5]$
  • $d(x^{2^3})\le 0.68$ for all $x \in [2,10^5]$
  • ...
  • $d(x^{2^7})\le 0.56$ for all $x \in [2,10^5]$.
  • $d(x^{2^{10}})\le 0.52$ for all $x \in [2,10^4]$.

This suggests that $d(x^{2^c}) \rightarrow 0.5$ when $c$ is large.

Let $\epsilon \in (0,1/2)$. My questions are:

  • For fixed $c$, is $\limsup_{x \rightarrow \infty } d(x^{2^c})=1$ ? If so, what is the biggest $x_0=x_0(c,\epsilon)$ guaranteeing $d(x^{2^c})\le 1-\epsilon$ for all $2\le x\le x_0$ ?
  • For fixed $N$, is $\lim_{c \rightarrow \infty } \max_{x\le N} d(x^{2^c})=0.5$ (or something little more) ? If so, what is the smallest $c_0=c_0(N,\epsilon)$ such that $\max_{x \le N} d(x^{2^c})\le 1-\epsilon$ for all $c \ge c_0$?
share|improve this question
1  
This is probably harder than the question of whether every sufficiently large power of 2 contains a 7 in its decimal expansion, which is a fairly well-known open question. –  Anthony Quas Apr 3 '13 at 14:15
add comment

2 Answers

up vote 4 down vote accepted

This answer adresses the first of the two questions (and was originally written, except for minor changes, for a slightly vaguer version of the question; thus the material that might not seem completely fitting now, except that it could be helpful for the second question, so I leave it).

It is a result of Lindström (On the Binary Digits of a Power, Journal of Number Theory, 1997) that, using his notation and denoting by $B(\cdot)$ the numer of 1s in the binary expansion in other words the sum of digits, $$ \limsup_{m\to \infty} \frac{B(m^h)}{\log_2 m}= h $$
which means precisely that for fixed $c$ the supremum is indeed $1$; indeed it works for any exponent not just powers of $2$.

I have not studied Lindström's proof in detail, but it seems to be explicit so that one could derive information for the $x_0$; and for squares the paper by Dromota and Rivat contains another explicit construction that could also be used.

Even more generally, the same is true for every polynomial of degree $h$ (with integer coeficients and positive leading coefficient).

Yet, it is true that such numbers, powers with many $1$, are in a certain sense rare.

There are various further (in part recent) results around this question. For example: $$ \frac{1}{N} \# \left\{ n \lt N \colon B(n^2) \le \log_2 N + y \sqrt{\frac{\log_2 N}{2}} \right\} = \Phi(y)+o(1) $$ where $\Phi$ denotes the normal distribution function. In other words, this $B(n^2)$ behaves like the sum of $2 \log_2 N$ independent random variables $0$ and $1$ with equal probability. This result is a special case of a result of Bassily and Kátai (Distribution of the values of q-additive functions on polynomial sequences, Acta Math. Hung. 1995)

For other results related to this, and the above mentioned information in more detail and nice constructions related to the above phonomenon, see for example Drmota and Rivat "The sum of digits function of squares" (Journal LMS, 2005) ; for similar investigations for arbitrary polynomials and q-ary digits see this more recent paper by the same authors and Mauduit

Or, for investiagtions of the ratio of $B(m^h)/B(m)$ see this recent paper by Hare, Laishram, Stoll "Stolarsky's conjecture and the sum of digits of polynomial values"

(Added: I do not know if anything on the second question is known or could be derived from known things; the distribution result seems to support what Aaron Meyerowitz says, it could be worth looking into the results on the ratio I mentioned.)

share|improve this answer
    
Oh I am sorry. I just clarified my question as you suggested and did not notice that you already answered. –  eig Apr 3 '13 at 22:55
    
@eig: no problem, I changed the answer slightly so that it is not confusing with the new version. This answers the first question, except for the $x_0$ but you could have a look at the two papers and extract a value. For the second I do not know an answer but perhaps some of the additional information is useful. –  quid Apr 4 '13 at 0:11
add comment

It look as if quid has given you an answers which is more profound than what I am about to say. However I took the question another way.

The numbers you report suggest that perhaps for any fixed upper bound $N \gt 2$ we have $$ \lim_{c \to \infty}\max_{x \le N}d(x^{2^c}) \rightarrow 0.5.$$ You can restrict attention to odd $x$ since for even $x$ the powers $x^C$ will accumulate a tail of $0$ bits at the end and always have a lower density than that of $\left(\frac{x}{2}\right)^C.$ That the limit (of the max) is $0.5$ seems very plausible to me. Unless I see a reason to think otherwise, I would expect that the binary strings we get will behave like random binary strings of their length (actually we always start and end with a $1$ which increases the density but this effect goes to zero, however it might be more fair to not count those two bits). The chance that a random string will have density over $0.5+\varepsilon$ ( for fixed $\varepsilon \gt 0$) goes to zero as the length increases. If we have $N$ or $\frac{N}{2}$ strings where $N$ is fixed (but the strings are increasing in length together), the probability that any one of them will have density over $0.5+\varepsilon$ will also go to zero. My assumptions here are vague. Say that every time we increase $c$ to $c+1$ we double the lengths of all the strings via random bit generation. I suspect , by the same reasoning, that $$ \lim_{C \to \infty}\max_{x \le N}d(x^{C}) \rightarrow 0.5.$$ And even that the minimum density (for odd $x \gt 1$) goes to $0.5.$ Equivalently, I conjecture that for any fixed odd $x \gt 1:$ $$ \lim_{C \to \infty}d(x^{C}) \rightarrow 0.5.$$


It is interesting to look at what happens for any one given even $x$ (assuming this last conjecture is true for odd $x$.) It is convenient to look instead at the ratio $d'$ of the number of $1's$ to $\log_2(x)$. This will not affect the limit since it changes the denominator by less than $1.$ If $x=2^tz$ where $z$ is odd then $x^C$ and $z^C$ have the same number of bits equal to $1$, so (we speculate, for large enough $C\cdots$ ) about $0.5C\log z.$ But $\log(x^C)=tC+C\log(z)$ so $d'(x)$ would go to $$\frac{0.5C\log z}{tC+C\log z}=\frac{0.5\log z}{t+\log z}.$$ A very few, very small , experiments support the suggestion that this is the correct limit and that the convergence is rapid..


A question I can't easily answer (assuming that the $\max$ does go to $0.5$) is how rapidly does the $\max$ go to $0.5?$ Perhaps it is faster than a random model would suggest. If $y$ had a density $1$ and then we double the length with random bits we would expect a density about $3/4$ (then $5/8$ then $9/16$ etc) but $y^2$ will already have density nearly $1/2.$ That may or may not make any difference if none of our $\frac{N}{2}$ strings have exceptionally high density.

share|improve this answer
    
My first reading (of the original version) was also like yours; but then in the display it asked for bound for density for squares and other powers, so in the end I went with the other reading. But since in the new version both readings appear explicitly the situation seems perfect anyway. –  quid Apr 4 '13 at 0:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.