Son los bits de orden alto de $n^2$ de probabilidades de ser ceros como?

Question

Deje $B_i(n)$ $i$th bits en binario de la expansión de $n$, por lo que el $n=\sum B_i(n)2^i$. Ahora vamos a $n$ al azar y de manera uniforme elegido de algunos de los grandes de la gama, y deje $E(j)$ ser el valor esperado de $B_j\bigl(n^2\bigr)$, $j$th poco en la expansión de $n^2$. Que es:

$$E(j) = \lim_{M\to\infty} \frac1M \sum_{n=0}^{M-1}B_j\bigl(n^2\bigr)$$

si este límite existe. No es difícil ver que debe existir para cualquier fija $j$, ya que la función $B_j\bigl(n^2\bigr)$ está totalmente determinado por el valor de $n\bmod 2^{j+1}$, y así es periódica con período en la mayoría de las $2^{j+1}$. De hecho, podemos deshacernos de el límite:

$$E(j) = \frac1{2^{j+1}} \sum_{n=0}^{2^{j+1}-1}B_j\bigl(n^2\bigr)$$

Por ejemplo, el primer par de valores de$E$$\frac12, 0, \frac14, \frac14$.

Numérico de la evidencia sugiere que:

$$\lim_{j\to\infty} E(j) = \frac12$$

¿Es esto cierto?

Answer 1

De acuerdo a la "Distribución de las cifras 0 y 1 en los diversos órdenes de la representación binaria de kth potencias de números enteros", W. Bruto y R. Vacca (las Matemáticas de la Computación, de abril de 1968, 22, #102, 423-427), la respuesta es sí.

En la página 423 que definir una función $N_k(h)$, que es el número de bits 1 en el $h$th posición de la secuencia $n^k$ más uno de sus períodos, por lo que mi $E(j)$ es exactamente $N_2(j)2^{-(j+1)}$. Luego de diapositivas (página 424) que

$$E(j) = \frac12\left(1 - 2^{-\lfloor j/2\rfloor}\right)$$

a excepción de $j=0$. Un resultado similar se tiene para arbitrario $k$th poderes-la densidad de bits de orden alto enfoques $\frac12$ todos los $k$.

Answer 2

Por Hensel del lema, se puede demostrar que el valor distinto de cero plazas en el $2$-adics $\Bbb Z_{(2)}$ son exactamente los números de la forma $4^n(8k+1)$ : los números cuya binario de expansión termina con "001" y un número par de ceros.

Las plazas mod $2^j$ son de nuevo los números. Por lo tanto, el número de plazas modulo $2^j$$1 + 2^{j-3} + 2^{j-5} + \ldots \approx 2^{j-1}/3$.
Fuera de esos cuadrados, aquellos donde dar la vuelta al $2^{j-1}$ bits, no de nuevo en una plaza cualquiera de las $0$ o $2^{2k}$$j \le 2k+3$, por lo que son en la mayoría de las $3$, que es insignificante en comparación con todas las demás plazas.