Demostrar que $\lim_{n\to \infty} \dfrac{c_n}{k^n} = \dfrac{1}{p}$

Question

Dejemos que $p$ sea un primo impar y que $a_1,a_2,\ldots,a_k$ sean números enteros no todos equivalentes módulo $p$ . Para cada $n>0$ , dejemos que $c_n$ denotan el número de tuplas $(b_1,b_2,\ldots,b_n)$ con $1\le b_i \le k$ para cada $i$ tal que $p|a_{b_1}+a_{b_2}+\cdots+a_{b_n}$ . Demostrar que $\displaystyle\lim_{n\to \infty} \dfrac{c_n}{k^n} = \dfrac{1}{p}$ .

Pensé en usar números complejos aquí. Parece difícil contar el número de tuplas directamente, así que ¿hay alguna forma de hacerlo para calcular el límite? Un filtro de raíces de la unidad con $\zeta = g^{2n}$ donde $g$ es una raíz primitiva módulo $n$ da $$\frac{(1 + \zeta^0 x)^{nk} + (1 + \zeta^1 x)^{nk} + \cdots + (1 + \zeta^{k-1} x)^{nk}}{k} \equiv 1+x^k+x^{2k}+\cdots +x^{nk} \pmod{p},$$ pero no estaba seguro si esto ayuda.

Answer 1

Definir $f(x)=\sum x^{a_j}$ .

Si $g_n(x)=f(x)^n$ entonces $c_n$ es la suma de los coeficientes si $g_n(x)$ con exponentes divisibles por $p$ .

Esto significa que $$c_n=\frac{1}{p}\sum_{i=0}^{p-1} g_n(\zeta^i)$$ donde $\zeta$ es una primitiva $p$ raíz de $1$ .

Entonces:

$$\frac{c_n}{k^n}=\frac{1}{p}\sum_{i=0}^{p-1} \left(\frac{f(\zeta^i)}{k}\right)^n$$

Ahora, cuando $i\neq 0$ , $\left|\frac{f(\zeta^i)}k\right|<1$ porque es el centro de masa de $k$ puntos del círculo unitario, no todos iguales.

Así que si $i=1,\dots,p-1$ entonces $\frac{f(\zeta^i)}{k}\to 0$ .

También, $\frac{f(1)}{k}=1$ .

Así, $\frac{c_n}{k^n}\to \frac{1}{p}$ .

---

Es probable que se pueda armar un argumento de cadena de Markov, pero me está costando trabajo entenderlo.