Let $p$ be an odd prime and let $a_1,a_2,\ldots,a_k$ be integers not all equivalent modulo $p$. For each $n>0$, let $c_n$ denote the number of tuples $(b_1,b_2,\ldots,b_n)$ with $1\le b_i \le k$ for each $i$ such that $p|a_{b_1}+a_{b_2}+\cdots+a_{b_n}$. Show that $\displaystyle\lim_{n\to \infty} \dfrac{c_n}{k^n} = \dfrac{1}{p}$.

I thought about using complex numbers here. It seems hard to count the number of tuples directly, so is there a way we can in order to calculate the limit? A roots of unity filter with $\zeta = g^{2n}$ where $g$ is a primitive root modulo $n$ gives $$\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},$$ but I wasn't sure if this helps.


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

If $g_n(x)=f(x)^n$, then $c_n$ is the sum of the coefficients if $g_n(x)$ with exponents divisible by $p$.

That means $$c_n=\frac{1}{p}\sum_{i=0}^{p-1} g_n(\zeta^i)$$ where $\zeta$ is a primitive $p$th root of $1$.


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

Now, when $i\neq 0$, $\left|\frac{f(\zeta^i)}k\right|<1$ because it is the center of mass of $k$ points on the unit circle, not all equal.

So if $i=1,\dots,p-1$ then $\frac{f(\zeta^i)}{k}\to 0$.

Also, $\frac{f(1)}{k}=1$.

Thus $\frac{c_n}{k^n}\to \frac{1}{p}$.

You can likely put together a Markov chain argument, but I'm having a hard time figuring it.

  • $\begingroup$ What if all the $a_i$ are equivalent modulo $p$? $\endgroup$ Dec 28 '16 at 0:54
  • $\begingroup$ Then $\frac{f(\zeta^i)}{k}=\zeta^{ia_1}$. But basically, then $c_n=1$ if $p\mid n$ or if all $a_i\equiv 0\pmod p$, otherwise $c_n=0$. $\endgroup$ Dec 28 '16 at 1:01
  • $\begingroup$ So that is a necessary condition? $\endgroup$ Dec 28 '16 at 1:02
  • $\begingroup$ Sorry, $c_n=k^n$ if $p\mid n$ or if all $a_i\equiv 0$. And yes, the condition is necessary. $\endgroup$ Dec 28 '16 at 1:03
  • $\begingroup$ Where did you use the condition in the solution and also that $p$ is odd? $\endgroup$ Dec 28 '16 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.