¿Cómo explicar una propiedad particular de los penúltimos bits de los primos?

Question

Suponiendo que $i \geq 0$ , dejemos que $p_i$ denotan un $i$ - el primer lugar: $p_0 = 2, p_1 = 3, \ldots$ Entonces $b_i$ denota el penúltimo bit de $p_i$ es decir $b_i = \left\lfloor p_i/2 \right\rfloor \bmod 2.$

Las secuencias $B_0$ y $B_1$ se construyen mediante el siguiente algoritmo: si $b_i$ es igual a $i \bmod 2$ , añadir $b_i$ a $B_0$ ; en caso contrario (es decir, si $b_i$ no es igual a $i \bmod 2$ ), añadir $b_i$ a $B_1$ . Así, $$\begin{array}{l} B_0 = 1010101101010101010101101010101010011001001111001101001011001010\ldots,\\ B_1 = 1101010101011001011010101100101010101010010101011101010101010101\ldots \end{array}$$

Básicamente, ambas secuencias son $\ldots1010\ldots$ , ligeramente intercalados con tiradas de dos o más trozos idénticos. Por ejemplo, el primer $10^6$ bits de $B_1$ ni siquiera contienen diez ceros consecutivos. ¿Cuál es la explicación de este fenómeno?

Answer 1

No creo que esto sea tan inesperado dado trabajo de Lemke Oliver y Soundararajan en los residuos de los primos consecutivos. (Me doy cuenta de que la primera palabra del título de ese artículo es "Inesperado", pero no me importa). Nótese que el primer enlace de John Omielan en los comentarios apunta (eventualmente) a este artículo.

---

Veamos las estadísticas de ejecución de los primeros 49.981 bits de $B_0$ correspondiente a la mitad de los primeros 100.000 primos. Hay series de bits consecutivos iguales de longitudes 1 a 7, y los recuentos de estas series son, respectivamente, $$(27261, 7710, 1771, 390, 67, 13, 2).$$

Consideremos ahora un proceso de Markov con estados {0,1} y matriz de transición \begin{pmatrix}\frac{1}{2}-d & \frac{1}{2}+d \\ \frac{1}{2}+d & \frac{1}{2}-d\end{pmatrix} para algún parámetro $d \in [-1/2, 1/2]$ . Es de esperar que las carreras sean más cortas en el caso de las grandes $d$ y de mayor duración para los más pequeños $d$ . Si tomamos $d = 0.28$ obtenemos los siguientes recuentos para las ejecuciones de longitud 1 a 11, promediados sobre 100 muestras: $$(30378.2, 6700.82, 1472.6, 324.16, 71.42, 16.01, 3.7, 0.75, 0.15, 0.02, 0.01).$$ Esto parece un ajuste decente a los valores observados, aunque tal vez demasiado bajo en los tramos de longitud media y demasiado alto en otros.

---

No estoy seguro de qué valor de $d$ es realista aquí: Lemke Oliver y Soundararajan tienen expresiones (conjeturalmente) asintóticamente correctas, pero están estudiando un problema ligeramente diferente. Más concretamente, si miramos los residuos mod 4 de la primera $10^6$ primos, sus datos sugieren $d \approx 0.07$ es una estimación razonable para su problema. Para primos más pequeños $d$ debería ser mayor, pero su $B_0$ / $B_1$ es lo suficientemente artificial como para que sus métodos sean significativamente más difíciles de aplicar. ( EDITAR: parece que la mayor parte de esto $d$ término se debe a las definiciones de $B_0$ y $B_1$ (véase la respuesta de Will Sawin).

En términos más generales, el desajuste de la forma de los datos sugiere (como es lógico) que existen efectos de mayor alcance que los captados por la modelización del proceso de Markov. Espero que pasar algún tiempo de calidad con Lemke Oliver y Soundararajan y pensar en la conjetura de las tuplas primarias debería darte mejores explicaciones aquí.

Answer 2

Creo que los fenómenos que observas se explican más por la forma en que construyes $B_0$ y $B_1$ que por las propiedades de los primos (aunque las propiedades de los primos parecen desempeñar un papel). Si en cambio suponemos que $b_i$ fueran aleatorios, obtenidos mediante el lanzamiento de una moneda, es fácil ver que para cada bit de $B_0$ o $B_1$ la probabilidad de que el siguiente bit sea el mismo es $\frac{1}{3}$ y la probabilidad de que el siguiente bit sea diferente es $2/3$ .

En efecto, digamos $b_i \equiv i \mod 2$ para algunos $i$ Así que en el momento $i$ acabamos de añadir $b_i$ a $B_0$ .

Entonces, si el siguiente $k-1$ bits no son congruentes con su posición mod $2$ , seguido por el $k$ a su posición, $i+k$ , mod. $2$ a continuación añadimos el bit $i+k \mod 2$ a $B_0$ . Esto ocurre con probabilidad $\frac{1}{2^k}$ y en cada secuencia esto ocurre exactamente para un valor de $k$ .

Así que tenemos una parte diferente con probabilidad $\frac{1}{2} + \frac{1}{2^3} + \frac{1}{2^5} + \dots = \frac{2}{3}$ y el mismo bit con probabilidad $\frac{1}{2^2} + \frac{1}{2^4} + \frac{1}{2^6} + \dots = \frac{1}{3}$ . El $B_1$ caso es idéntico.

Así que la probabilidad de obtener $10$ ceros consecutivos a partir de un punto cualquiera es $\frac{1}{2} \cdot \frac{1}{3^9}$ . Sin embargo, el tiempo que esperamos que pase antes de ver la primera tirada de $10$ ceros consecutivos es un poco más larga que la inversa, $3^{10}-1=59048$ por un argumento clásico.

Así que esperamos unas 17 veces más de lo que cabría esperar para encontrar una serie de diez ceros. (Pero había que elegir 4 opciones para encontrar una tirada tan larga sin ceros). Eso no es completamente sorprendente, pero es mucho menos extraño que en el modelo aleatorio ingenuo, donde el tiempo de espera esperado es $2^{11}-1$ , por lo que habrías esperado alrededor de $489$ veces más de lo esperado.

---

De forma más general, si sustituimos $b_i$ con una cadena de Markov con probabilidad de tomar el mismo valor en pasos adyacentes $p$ entonces la probabilidad de que $B_0$ toma el mismo valor en pasos adyacentes debe ser $$p^2 + p^2(1-p)^2 + p^2 (1-p)^4 + \dots = \frac{ p^2}{ 1- (1-p)^2} = \frac{p^2 }{ 2p -p^2} = \frac{p}{ 2-p}$$ ya que para obtener dos del mismo bit en $B_0$ , $b_i$ debe ser igual o igual-diferente-diferente-igual o igual-diferente-diferente-diferente-igual.

Para explicar $\frac{ p}{2-p} = \frac{1}{2} - .28 = .22$ como en el análisis de dvitek, necesitamos $p= \frac{2}{ 1/.22 +1} =.361$ es decir, hay una discrepancia de aproximadamente $.14$ para explicar en la estadística más natural la frecuencia con la que dos primos adyacentes tienen penúltimos bits distintos.