Probabilidad de que $x^2-y^2$ es divisible por $k$

Question

Sean dos números $x$ y $y$ ser seleccionado del conjunto de los primeros $n$ números naturales con reemplazo (es decir, los dos números pueden ser iguales).La cuestión es averiguar la probabilidad de que $x^2-y^2$ es divisible por $k\in \mathbb{N}$

---

Para $k=2$

Cualquier número puede expresarse como $2p,2p+1$ .ahora $x^2-y^2=(x-y)(x+y)$ Si ambos números son de la forma $2p+1$ entonces (x-y) sería divisible por $2$ .si dos números son de diferente forma entonces no será divisible por $2$ Así que la probabilidad en este caso es $a^2+(1-a)^2$ donde $a$ es la probabilidad de que el número elegido sea divisible por $2$ que es $\frac{\lfloor \frac{n}{2} \rfloor}{n}$ Sin embargo, esto se complica con $k=3$ En otras palabras, si hay una generalización o una forma de resolver para algunos grandes $k$ Gracias.

Answer 1

Una generalización expresada por un conjunto

Una buena manera de generalizar esto es utilizar la aritmética modular, o esencialmente mirar el resto de $\frac{x}{k}$ y $\frac{y}{k}$ . Como ha señalado en su ejemplo de $k=2$ los números sólo pueden expresarse como $$2*p,2*p+1$$

Esto se puede generalizar en un conjunto de expresiones únicas que definen cada número o cada $x$ y $y$ para un valor $k>1$ y $p≥0$$$ S={kp,kp+1...kp+(k-2),kp+(k-1)}$$

Utilizando la aritmética modular, sabemos que $S\equiv \{0,1,2...k-2,k-1\}\pmod k$

Desde $x$ y $y$ son dos términos cualesquiera del conjunto $S$ para cualquier $p≥0$ sabemos que $x$ y $y$ son realmente iguales a cualquier valor de $\{0,1,2...k-2,k-1\}$ ya que sólo tenemos que mirar el resto cuando se divide por $k$ para determinar la divisibilidad.

Probabilidad mediante mod

Ahora sabemos $x^2-y^2 = (x-y)(x+y)$ lo que significa que $(x-y)$ o $(x+y)$ tienen que ser divisibles por $k$ para cumplir el requisito de que $x^2-y^2$ es divisible por $k$ .

Hay que tener en cuenta que la probabilidad de elegir un número aleatorio expresado por cualquier expresión del conjunto $S$ es uniforme y es igual a $\frac{1}{k}$ . Por ejemplo, la probabilidad de elegir un número es expresable mediante $3p+1$ es $\frac{1}{3}$ . Esto se puede demostrar mostrando cómo cada número expresado por $kp$ siempre se puede emparejar con $kp+1,kp+2,...kp+(k-2),kp+(k-1)$ , mostrando así cómo hay un número igual de números de cada tipo.

A la pregunta ....

$(x-y)$ es divisible por $k$ si $(x-y)\equiv 0\pmod k$ . Esto se simplifica a $(x$ mod $k)-(y \text{ mod}\ k) = 0$ . Por lo tanto, ahora tenemos que encontrar la probabilidad de que $x$ y $y$ son ambos expresables por la misma expresión en el conjunto S.

Ahora esto se reduce a un simple problema de preguntar cuál es la probabilidad de elegir dos de los mismos elementos del conjunto $S$ sin sustitución, que es $\frac{k}{k} *\frac{1}{k} =$ $\frac{k}{k^2}$

$(x+y)$ es divisible por $k$ si $(x+y)\equiv 0\pmod k$ . Esto se simplifica a $(x$ mod $k)+(y \text{ mod}\ k) = 0$ . Por lo tanto, ahora tenemos que encontrar la probabilidad de que $x$ y $y$ se eligen de forma que el $x+y =$ un múltiplo de $k$ .

Sabiendo que $x$ y $y$ debe proceder del conjunto $S$ podemos ver que hay un emparejamiento específico de elementos de $S$ que hace que la suma del par de elementos sea igual a $2*kp+k$ , un múltiplo de $k$ . Las únicas veces que el par de elementos, que será la expresión que expresa $x$ y $y$ , suman $2*kp$ es cuando uno se expresa por $kp+m$ y el otro es $kp+(k-m)$ para cualquier número entero $m$ . Esto se debe a que $(kp+m)+(kp+(k-m)) = 2*kp$ . Por ejemplo $3p+1$ puede ser emparejado con $3p+2$ ya que su suma es $6p+3$ un múltiplo de 3.

Ahora buscamos la probabilidad de que los dos elementos elegidos de $S$ son pares entre sí (si ambos elementos elegidos son $kp$ El número total de parejas que se pueden elegir es el número total de elementos del conjunto $S$ al cuadrado, que es $k^2$ . El número total de pares que cumplen la divisibilidad por $k$ es igual a $\lfloor\frac{k}{2}\rfloor + 1$ . La función techo se aplica para corregir los errores que se producen cuando $k$ es impar ya que obviamente no se puede tener un número fraccionario de pares. El extra $+1$ es para incluir el caso en que ambos elementos sean iguales.

Por lo tanto, la probabilidad de que $(x+y)$ es divisible por $k$ es $\frac{\lfloor\frac{k}{2}\rfloor + 1}{k^2}$ .

Sin embargo ahora nos encontramos con un problema de solapamiento, que son los casos en los que los dos elementos elegidos de $S$ hacer $(x-y)$ y $(x+y)$ divisible por k. Para deshacernos del sobreconteo tenemos que restar el número de veces que esto ocurre para un conjunto dado $S$ . Sabemos que tenemos que restar una vez para el caso en que ambos elementos sean $kp$ . También hay que restar otro en función de si $k$ es par o no. Esto se debe a que cuando $k$ es par, tenemos el caso en que el elemento $kp+\frac{k}{2}$ puede emparejarse consigo mismo para cumplir con todo. Por lo tanto, la respuesta final es $$\frac{k}{k^2}+\frac{\lfloor\frac{k}{2}\rfloor + 1}{k^2} - \frac{(k+1 \text{ mod }2)+1}{k^2}$$

El $\frac{(k+1 \text{ mod }2)+1}{k^2}$ nos dice que hay que restar uno más y restar otro si $k$ es par, por lo que desplazamos la parte modular en 1 ya que $( \text{ even number mod }2 = 0)$

Answer 2

EDITAR 12.04.17

Después de algunos días de estudio de este interesante problema, proporciono ahora una solución analítica completa del problema recuperando un problema relacionado en OEIS.

Doy valores exactos de las primeras probabilidades, y doy una fórmula general exacta para la probabilidad si el divisor $n$ es primo.

También se presenta una simulación de Monte-Carlo.

Obsérvese que mis hallazgos surgieron en orden temporal opuesto.

Solución analítica del problema

Buscando la secuencia de los primeros términos de

$$s(n) = p(n) n^2 \tag{1}$$

que son

$${1, 2, 5, 8, 9, 10, 13, 24, 21, 18, 21, 40, 25, 26, 45}$$

en la enciclopedia online de secuencias de números enteros https://oeis.org/ nos da la entrada A062803 "Número de soluciones a $x^2 == y^2 mod(n)$ ", creado inicialmente por Ahmed Fares (ahmedfares(AT)my-deja.com), el 19 de julio de 2001. Una fórmula fue ideada por Vladeta Jovovic el 22 de septiembre de 2003: "Multiplicativo con a(2^e)=e*2^e y a(p^e)=((p-1)*e+p)*p^(e-1) para un primo impar p".

Exploremos esto un poco más de cerca. Nuestro problema se transforma en la cuestión del número $s(n)$ de soluciones a la congruencia

$$x^2-y^2 == 0, \; mod(n)\tag{1}$$

Nuestras probabilidades vienen dadas entonces por

$$p(n) = s(n)/n^2\tag{2}$$

Supongamos que el número $n$ tiene la representación

$$n = \prod_{i=1}^{k} p_i^{a_i}\tag{3}$$

donde $p_i$ es el $i$ -número primo que aparece en $n$ en orden ascendente, $a_i$ es la multiplicidad (exponente) y $k$ es el número de factores primos diferentes en $n$ . Obsérvese que en la teoría de los números $k$ se llama tradicionalmente $\omega(n)$ el número de factores primos distintos. Se implementa en Mathematica como PrimeNu[n].

Entonces, la afirmación de ser multiplicativa significa que podemos aplicar la fórmula a cada uno de los factores primos de la potencia por separado, y multiplicar el resultado juntos.

Esto da para $n$ incluso

$$s(n_{even}) = (a_1 2^{a_1}) \prod_{i=2}^{k} ((p_i-1)a_i+p_i) p_i^{a_i-1}\tag{4.1}$$

y para $n$ impar

$$s(n_{odd}) = \prod_{i=1}^{k} ((p_i-1)a_i+p_i) p_i^{a_i-1}\tag{4.2}$$

Es fácil ver que para un primo impar $n$ , $s(n) = 2n-1$ como se ha afirmado anteriormente.

La fórmula se simplifica si $n$ es libre de cuadrados. Entonces todos los no evanescentes $a_i$ son iguales a $1$ y encontramos

$$s(n_{even}) = 2 \prod_{i=2}^{k} (2 p_i-1)\tag{5.1}$$ $$s(n_{odd}) = \prod_{i=1}^{k} (2 p_i-1)\tag{5.2}$$

Para quienes estén interesados en codificar esta fórmula, he aquí un ejemplo en Mathematica

s[n_] := Module[{fi, pi, ai, pout},   
  fi = FactorInteger[n];  
  pi = #[[1]] & /@ fi;  
  ai = #[[2]] & /@ fi;  
  pout = If[OddQ[n],   
    Product[((pi[[i]] - 1) ai[[i]] + pi[[i]]) pi[[i]]^(ai[[i]] - 1), {i, 1, Length[pi]}],    
    ai[[1]] 2^ai[[1]] Product[((pi[[i]] - 1) ai[[i]] + pi[[i]])
       pi[[i]]^(ai[[i]] - 1), {i, 2, Length[pi]}]]]  

La descomposición del factor primo de $n$ se realiza mediante la función FactorInteger[]. De ella extraemos el $p_i$ y $a_i$ y luego aplicar la fórmula de Jovovic.

Valores exactos de las probabilidades

Hacemos la suposición (natural) de que todos los restos posibles de un número elegido al azar $x$ modulo $n$ tienen la misma probabilidad.

Entonces podemos calcular los valores exactos de las probabilidades con el siguiente fragmento de código (escrito aquí en Mathematica)

h[n_] := 1/n^2 Count[Flatten[Table[Mod[x^2 - y^2, n], {x, 0, n - 1}, {y, 0, n - 1}]], 0]

Explicación

Para un divisor dado $n$ la expresión $z = x^2-y^2$ debe considerarse sólo para $x$ y $y$ entre $0$ y $n-1$ . La Tabla[] enumera todos los elementos $x^2-y^2 mod(n)$ y Flatten[] los pone en un array. Ahora Count[.,0] cuenta los ceros en este array. Dividiendo esto por $n^2$ da la probabilidad.

El resultado para $n = 1..30$ en el formato $\{n,p(n)\}$ son

$$h(n)_{tab} = \left( \begin{array}{ccccc} \{1,1\} & \left\{2,\frac{1}{2}\right\} & \left\{3,\frac{5}{9}\right\} & \left\{4,\frac{1}{2}\right\} & \left\{5,\frac{9}{25}\right\} \\ \left\{6,\frac{5}{18}\right\} & \left\{7,\frac{13}{49}\right\} & \left\{8,\frac{3}{8}\right\} & \left\{9,\frac{7}{27}\right\} & \left\{10,\frac{9}{50}\right\} \\ \left\{11,\frac{21}{121}\right\} & \left\{12,\frac{5}{18}\right\} & \left\{13,\frac{25}{169}\right\} & \left\{14,\frac{13}{98}\right\} & \left\{15,\frac{1}{5}\right\} \\ \left\{16,\frac{1}{4}\right\} & \left\{17,\frac{33}{289}\right\} & \left\{18,\frac{7}{54}\right\} & \left\{19,\frac{37}{361}\right\} & \left\{20,\frac{9}{50}\right\} \\ \left\{21,\frac{65}{441}\right\} & \left\{22,\frac{21}{242}\right\} & \left\{23,\frac{45}{529}\right\} & \left\{24,\frac{5}{24}\right\} & \left\{25,\frac{13}{125}\right\} \\ \left\{26,\frac{25}{338}\right\} & \left\{27,\frac{1}{9}\right\} & \left\{28,\frac{13}{98}\right\} & \left\{29,\frac{57}{841}\right\} & \left\{30,\frac{1}{10}\right\} \\ \end{array} \right)$$

Los resultados de la simulación (véase más adelante) concuerdan razonablemente con estos resultados.

Si $n$ es un número primo impar la probabilidad viene dada por

$$p(n)=\frac{2 n-1}{n^2}$$

Si $n$ es compuesto no he encontrado la fórmula exacta. El problema parece estar relacionado con los residuos cuadráticos.

Simulación de Monte-Carlo

EDITAR 11.04.17

Distinguimos dos posibles conjuntos básicos de enteros entre los que seleccionar para la prueba de divisibilidad:

1. Conjunto con repetición

Creamos un conjunto $m$ que consiste en todos los números $z = x^2-y^2$ de enteros donde $1<= x <= n_{max}, 1<= y <= n_{max}$ .

2. Conjunto sin repetición

El conjunto $m_0$ se obtiene eliminando de $m$ todos los duplicados.

Entonces, para un divisor dado $n$ estimamos la probabilidad de divisibilidad por el cociente del número de elementos del conjunto para los que $\frac{z}{n}$ es un número entero relativo a todos los elementos del conjunto.

Las probabilidades resultantes para $m_{max} = 10^3$ y los divisores en el rango $n = 1..30$ son

Caso 1 (con repetición)

Lista de resultados en el formato $(n, p(n))$

$$((1, 1.0), (2, 0.5000005), (3, 0.55533378), (4, 0.5000005), (5, \ 0.35968128), (6, 0.27766739), (7, 0.26530612), (8, 0.37475112), (9, \ 0.25933407), (10, 0.17984114), (11, 0.17355372), (12, 0.27766739), \ (13, 0.14792899), (14, 0.13265356), (15, 0.19973533), (16, \ 0.25000075), (17, 0.11417454), (18, 0.12966754), (19, 0.10246197), \ (20, 0.17984114), (21, 0.14736213), (22, 0.08677736), (23, \ 0.08502487), (24, 0.20808462), (25, 0.10419251), (26, 0.073965), (27, \ 0.11103881), (28, 0.13265356), (29, 0.06774345), (30, 0.09986916))$$

El gráfico

Caso 2 (sin repetición)

Lista de resultados en el formato $(n, p(n))$

$$((1, 0.5125414), (2, 0.19847984), (3, 0.22136804), (4, 0.19847984), \ (5, 0.14290505), (6, 0.08393305), (7, 0.10653981), (8, 0.11713062), \ (9, 0.08960969), (10, 0.05436621), (11, 0.07129035), (12, \ 0.08393305), (13, 0.06139016), (14, 0.04070156), (15, 0.05862769), \ (16, 0.06700892), (17, 0.04836223), (18, 0.03377941), (19, \ 0.04369956), (20, 0.05436621), (21, 0.04403089), (22, 0.02740017), \ (23, 0.03676344), (24, 0.04804486), (25, 0.03682731), (26, \ 0.0236357), (27, 0.03531034), (28, 0.04070156), (29, 0.02972352), \ (30, 0.02204489))$$

El gráfico

Obsérvese la notable peridocidad con un periodo de $4$ en el caso "artificial" 2. Estoy seguro de que hay una explicación sencilla para esto, y que algunos lectores pueden darla.