Probabilidad de los polinomios coprimos

Question

Dado un número entero positivo $N$ elegimos $m_1, m_2, n_1, n_2$ independientemente y con igual probabilidad de $\{0,1,\ldots,N\}$ y que $f_1 = x^{m_1} + (1+x)^{n_1}$ y $f_2 = x^{m_2} + (1+x)^{n_2}$ como polinomios en la indeterminada $x$ sobre el campo ${\mathbb F}_2$ de dos elementos. Sea $P(N)$ sea la probabilidad de que $f_1$ y $f_2$ son coprimos. ¿Qué se puede decir de $P(N)$ en particular su asintótica como $N \to \infty$ ?

Por enumeración explícita en Maple, los primeros valores son $$\eqalign{P \left( 1 \right) &={\frac {9}{16}},P \left( 2 \right) ={\frac {56}{ 81}},P \left( 3 \right) ={\frac {45}{64}},P \left( 4 \right) ={\frac { 489}{625}},P \left( 5 \right) ={\frac {1019}{1296}},\cr P \left( 6 \right) &={\frac {1895}{2401}},P \left( 7 \right) ={\frac {3299}{4096} },P \left( 8 \right) ={\frac {5308}{6561}},P \left( 9 \right) ={\frac {2023}{2500}},P(10) = \frac{11954}{14641}\cr}$$ El muestreo aleatorio parece indicar $P(100) \approx 0.83$ . La secuencia $(N+1)^4 P(N)$ no parece estar en la OEIS.

EDIT: Esa secuencia está ahora en la OEIS como A245488 . $P(100) = 86648767/101^4 \approx 0.8326776196$ .

Answer 1

(Editado en respuesta a los comentarios de Julian Rosen)

Como $N\to\infty$ se podría adivinar que $P(N)$ se acerca a $$ \prod_{p} \Bigl(1 - \Bigl(\frac{\gcd(a_p,b_p)}{a_p b_p}\Bigr)^2\Bigr), $$ donde el producto es sobre todos los irreducibles $p(x)\in\mathbf{F}_2[x]$ de grado como mínimo $2$ y $a_p$ y $b_p$ denotan los órdenes de $x$ y $x+1$ en el grupo multiplicativo de $\mathbf{F}_2[x]/(f(x))$ respectivamente. Esto se debe a que este grupo es cíclico, por lo que la intersección de subgrupos de órdenes $a_p$ y $b_p$ tiene orden $\gcd(a_p,b_p)$ . Entonces el número de pares $(m,n)$ con $1\le m\le a_p$ y $1\le n\le b_p$ para lo cual $p\mid x^m+(1+x)^n$ es $\gcd(a_p,b_p)$ Así que si $N$ es grande en comparación con $a_p$ y $b_p$ entonces la proporción de los pares $(m,n)$ con $0\le m,n\le N$ para lo cual $p\mid x^m+(1+x)^n$ se acercará $\gcd(a_p,b_p)/(a_pb_p)$ . Por lo tanto, la probabilidad de que $p$ divide ambos $x^{m_1}+(1+x)^{n_1}$ y $x^{m_2}+(1+x)^{n_2}$ se acerca al cuadrado de $\gcd(a_p,b_p)/(a_pb_p)$ , lo que da lugar a la fórmula reivindicada.

Sin embargo, como señala Julian Rosen, estoy asumiendo implícitamente la independencia de la divisibilidad por primos distintos $p$ que no es válido. Así que mi fórmula debe ser modificada de alguna manera. Por otro lado, he calculado el producto mostrado sobre $p$ de grado hasta $15$ , y consiguió $0.8321...$ coincidiendo con los cálculos de Robert Israel. Así que tal vez mi fórmula es una aproximación razonable a la verdad.

Answer 2

Este parece ser un problema difícil e interesante. Aquí hay una heurística sobre la respuesta correcta, pero tengo pocas esperanzas de que pueda convertirse en una prueba. A continuación dejemos $D$ denotan un polinomio en ${\Bbb F}_2[x]$ y que $\mu(D)$ denotan la función de Mobius. Sólo nos interesará $D$ que son coprimos a $x(1+x)$ . Para tales $D$ consideremos el grupo generado por $x$ y $1+x$ en $({\Bbb F}_2[x]/D)^*$ denota esto por $\langle x,1+x\rangle_D$ y su orden por $|\langle x,1+x\rangle_D|$ . La probabilidad conjeturada es $$ \sum_{D, (D,x(1+x))=1} \frac{\mu(D)}{|\langle x, 1+x \rangle_D|^2}. $$

Para ver el por qué de esto, observe que podemos identificar si $(f,g)=1$ mediante la suma $\sum_{D|f, D|g} \mu(D)$ . Por lo tanto, el problema pide $$ \sum_{D, (D,x(1+x))=1} \mu(D) \Big( \frac{1}{(N+1)^2} \sum_{0 \le a, b\le N; D|x^a+(1+x)^b} 1\Big)^2. $$

La probabilidad de que $D$ divide $x^a+(1+x)^b$ es la misma que la probabilidad de que $D$ divide $x^m (1+x)^n +1 = x^m (1+x)^n -1$ . Desde $x^m (1+x)^n$ se extiende uniformemente sobre los elementos de $\langle x,1+x \rangle_D$ esta probabilidad es claramente $1/|\langle x,1+x\rangle_D|$ . Esto justifica heurísticamente la conjetura. El argumento podría precisarse dividiendo $a$ y $b$ en intervalos de tamaño del orden de $x$ en $({\Bbb F}_2[x]/D)^*$ y el orden de $1+x$ allí. El problema es que habrá un error de tamaño $O(1/N)$ al hacerlo, y esto no puede ser controlado como la suma sobre $D$ incluye un número exponencial de términos.

Parece plausible que la suma sobre $D$ en la conjetura converge, pero no veo ninguna forma de demostrarlo. Sería interesante calcularlo numéricamente. Se puede obtener algo riguroso haciendo el análisis anterior sólo con los $D$ cuyos factores irreducibles tienen grado inferior a $\log N$ decir. De este modo se obtiene un límite superior para la probabilidad deseada.