La "tasa de cobertura" de los cosets $7 \Bbb{Z} + a$ por algún coset $b \Bbb{Z} +c$ .

Question

La tasa de cobertura de los cosets $7\Bbb{Z} + a$ por el coset $13\Bbb{Z} + 2$ :

$$ 7(0) -4 = 13(-1) + 2 \\ 7(1) -5 = 13(0) + 2 \\ 7(2) + 1 = 13(1) + 2 \\ 7(4) + 0 = 13(2) + 2 \\ 7(6) -1 = 13(3) + 2 \\ 7(8) -2 = 13(4) + 2 \\ 7(10) -3 = 13(5) + 2 \\ 7(12) - 4 = 13(6) + 2 \\ 7(14) -5 = 13(7) + 2 \\ $$

Se necesita como mínimo un desplazamiento de $14$ es decir $7(x + 14) + a = 13y + 2$ antes de que el ciclo comience de nuevo (mira el ciclo de residuos: $-4,-5,1,0,-1,-2,-3,-4,-5, \dots$ el desplazamiento que separa a los dos $-5$ es $14$ .

Es $\dfrac{1}{14}$ o para todos los fijos $x, a \in \Bbb{Z}$ el límite

$$\lim\limits_{y \to \infty} \dfrac{\#(\{7x + a, 7(x+1) + a, \dots, 7(x + y) + a\} \cap (13 \Bbb{Z} + 2))}{y - x} = \dfrac{1}{14}$$ .

La tasa de cobertura de $7\Bbb{Z} + a$ por $19 \Bbb{Z} + 3$ :

$$ 7(3) + 1 = 19(1) + 3\\ 7(5) + 6 = 19(2) + 3 \\ 7(8) + 4 = 19(3) + 3 \\ 7(11) + 2 = 19(4) + 3 \\ 7(14) + 0 = 19(5) + 3 \\ 7(16) + 5 = 19(6) + 3 \\ 7(19) + 3 = 19(7) + 3 \\ 7(22) + 1 = 19(8) + 3 \\ 7(24) + 6 = 19(9) + 3 \\ $$

es por lo tanto $\dfrac{1}{19}$ . ¿Cómo podemos calcular esta tasa sin pasar por el problema de la enumeración?

Answer 1

La densidad natural de un conjunto $S\subseteq\mathbb{N}$ de los naturales se define como

$$ \mu(S)=\lim_{N\to\infty} \frac{|S\cap[1,B]|}{N}. $$

No todos los subconjuntos de $S$ tienen una densidad - de hecho podemos construir $S$ para que $|S\cap[1,N]|$ oscila indefinidamente si queremos. Esta densidad tampoco es contablemente aditiva como lo sería la medida de probabilidad, por lo que, por ejemplo, cada singleton $S=\{n\}$ tiene densidad $0$ pero su unión tiene densidad $\mu(\mathbb{N})=1$ . También vale la pena señalar que es difícil demostrar cosas sobre la densidad natural de ciertos conjuntos, sin embargo se actualiza por algo llamado la densidad de Dirichlet, definida por un límite con series de Dirichlet en $s=1$ En este caso, la densidad de Dirichlet puede existir incluso cuando la densidad natural no existe y, en la práctica, es más fácil trabajar con la densidad de Dirichlet para los conjuntos que se encuentran y se examinan en la teoría analítica de los números.

Debería estar claro cómo ampliar la definición de densidad natural a todos los $\mathbb{Z}$ si queremos un tratamiento más "simétrico" de los cosets. La densidad natural de un coset es simplemente $\mu(a+m\mathbb{Z})=\tfrac{1}{m}$ . Le interesa la densidad relativa $\mu(A\cap B)/\mu(B)$ para dos cosets $A=a+7\mathbb{Z}$ y $B=2+13\mathbb{Z}$ .

Afortunadamente, la intersección de dos cosets es mismo un coset (o vacío). Los elementos de $A\cap B$ donde $A=a+m\mathbb{Z}$ y $B=b+n\mathbb{Z}$ son soluciones del sistema de congruencias

$$ \begin{cases} x \equiv a \mod m \\ x \equiv b \,\mod n \end{cases} $$

El Teorema Chino del Resto dice que esto está vacío si $a\not\equiv b\mod \gcd(m,n)$ o bien es un residuo mod. $\mathrm{lcm}(m,n)$ (que se puede construir explícitamente utilizando una versión de la interpolación de Lagrange y las inversiones modulares, que puedo explicar si quieres). Por tanto, tenemos

$$ \mu\big((a+m\mathbb{Z})\cap(b+n\mathbb{Z})\big) = \begin{cases} \frac{1}{\mathrm{lcm}(m,n)} & \textrm{ if } a\equiv b\mod\gcd(m,n) \\[5pt] ~0 & \textrm{ if } a\not\equiv b \mod \gcd(m,n) \end{cases} $$