Distribución de azar divisor sumas modulo n

Question

Vamos $k$, $n\ge 2$ ser enteros positivos, y elija $\ell$ tal que $0\le \ell \le k-1$. Para cada entero $2\le j \le n$, elija un divisor $d_j$$j$, uniformemente al azar de los divisores de a $j$. Probar si $P(n,k,\ell)$ denota la probabilidad de $$d_2 + d_3 + \cdots + d_n \equiv \ell \pmod{k}$$ then $$\lim_{n\to\infty} P(n,k,\ell) = \frac{1}{k}$$

Soy capaz de mostrar esto para $k$ un primer o potencia de dos, pero no estoy seguro de cómo hacerlo para los otros valores de $k$. Al $k$ es una potencia de dos, en el hecho de $P(n,k,\ell) = 1/k$ para suficientemente grande $n$, y al $k = p$ es primo, tenemos $$|P(n,p,\ell) - 1/p| \le \frac{p+1}{p(p-1)^{J(n)}}$$ where $J(n)$ is the largest integer such that ${a_{J(n)}}^{p-2} \le n$, where $a_k$ is the $k$th prime number that is also a primitive root mod $p$.

Answer 1

Suponiendo que la pregunta tiene la intención de los divisores $d_j$ a ser elegido de forma independiente el uno del otro (por $2\le j\le n$), podemos ver que la probabilidad deseada converge rápidamente a $1/k$. Para ver esto, recordemos que $$ \frac{1}{k} \sum_{un \, (\text{mod} \,k)} e^{-2\pi i \ell a/k} e^{2\pi i a d/k} = \begin{cases} 1 & \text{if } d\equiv \ell\text{ }(\text{mod }k)\\ 0 &\text{otherwise}. \end{casos} $$ Por lo tanto, la probabilidad deseada es $$ \frac{1}{k} \sum_{un\, (\text{mod} \,k)} e^{-2\pi i \ell a/k}\, {\Bbb E}\left(\prod_{j=2}^{n} e^{2\pi i d_j a/k}\right)= \frac{1}{k} \sum_{un\, (\text{mod} \,k)} e^{-2\pi i\ell a/k} \prod_{j=2}^{n} {\Bbb E} e^{2\pi i ad_j/k}). $$ El plazo $a\equiv 0\text{ }(\text{mod }k)$ da el indicado término principal $1/k$.

Considere ahora la contribución de los términos con $a\not\equiv 0\text{ }(\text{mod }k)$. Claramente para cada $j$,$|{\Bbb E}(e^{2\pi i a d_j/k})| \le 1$. El uso de este trivial obligado para todos los compuestos de $j$, vemos que $$ \left| \prod_{j=2}^{n} {\Bbb E} e^{2\pi i ad_j/k}) \right| \le \prod_{p\le n} \left| \frac{1+e^{2\pi i ap/k}}{2}\right| = \prod_{p\le n} \left|\cos (\pi p/k)\right|. $$ Puesto que los números primos están distribuidas de manera uniforme en la reducción de residuos clases de mod $k$ (esto es una consecuencia de la prueba de Dirichlet del Teorema), tenemos que $$ \prod_{p\le n} \left|\cos (\pi p/k)\right| \le \left( \prod_{b=1,\,(b,k)=1}^k \left|\cos (\pi ab/k)\right| \right)^{\frac{1+o(1)}{\varphi(k)} \frac{n}{\log n} } < c_k^{\frac{n}{\log n}}, $$ para algunos puede determinar fácilmente constante $c_k$ que es estrictamente menor que $1$.

Esto completa la prueba de que la probabilidad converge esencialmente exponencialmente rápidamente a $1/k$. Nosotros probablemente puede ser mucho más precisa que no ignora el típico compuesto de números anteriores.