5
$\begingroup$

Would you please help me solve Problem 7 of Section 4.5, "Combinatorial Number Theory," in An Introduction to the Theory of Numbers, Niven, Zuckerman, Montgomery, 5th ed., Wiley (New York), 1991:

Let $n$ and $k$ be positive, relatively-prime integers with $n > k$. Prove that if $k$ distinct integers are selected at random from $1, 2, \dots, n$, the probability that their sum is divisible by $n$ is $1/n$.

The authors describe three methods for solving combinatorial problems: (1) the pigeonhole principle, (2) the one-to-one correspondence procedure, in which elements in a finite set or between two sets are paired off to determine the number of elements, and (3) the inclusion-exclusion principle. I know that the denominator of the probability fraction is $n \choose k$, so I tried (without success) to use the second method to count the number of desired outcomes to be $(n - 1)!/((n - k)! k!)$.

Because $n$ and $k$ are relatively prime, I know that $n \choose k$ is divisible by $n$ (see Example 10, notwithstanding the mistake/typo in the proof). In that case, numerical evidence suggests that the sum in question is uniformly distributed modulo $n$. If I can prove that conjecture, I am done.

I found similar problems with particular values for $n$ and $k$, but the solutions do not help me solve this general case.

$\endgroup$
4
$\begingroup$

Think of the numbers as integers modulo~$n$. Consider the map $A=\{a_1,a_2,\ldots,a_k\}\mapsto\{a_1+1,a_2+1,\ldots,a_k+1\}$. This adds $k$ modulo $n$ to the sum of the elements of $A$.

$\endgroup$
  • $\begingroup$ Can you explain more? How does this solve the problem? $\endgroup$ – crskhr Jun 2 '18 at 15:32
0
$\begingroup$

The exponential formula tells us that the cycle index $Z(P_k)$ of the unlabeled set operator

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}$$

on $k$ slots has OGF

$$Z(P_k) = [w^k] \exp\left(\sum_{l\ge 1} (-1)^{l-1} a_l \frac{w^l}{l}\right).$$

The desired probability is given by

$${n\choose k}^{-1} \frac{1}{n} \sum_{p=0}^{n-1} \left. Z(P_k) \left(\sum_{q=1}^n z^q\right)\right|_{z=\exp(2\pi ip/n)}.$$

This is

$${n\choose k}^{-1} \frac{1}{n} \sum_{p=0}^{n-1} \left. [w^k] \exp\left(\sum_{l\ge 1} (-1)^{l-1} \left(\sum_{q=1}^n z^{ql}\right) \frac{w^l}{l}\right)\right|_{z=\exp(2\pi ip/n)}.$$

Evaluating the contribution for $p=0$ first we get

$${n\choose k}^{-1} \frac{1}{n} [w^k] \exp\left(\sum_{l\ge 1} (-1)^{l-1} n \frac{w^l}{l}\right) \\ = {n\choose k}^{-1} \frac{1}{n} [w^k] \exp\left(n \log(1+w)\right) \\ = {n\choose k}^{-1} \frac{1}{n} [w^k] (1+w)^n = {n\choose k}^{-1} \frac{1}{n} {n\choose k} = \frac{1}{n}.$$

It remains to evaluate the contribution from $1\le p\le n-1.$ Now for these $p$ if $l$ is a multiple of $m = n/\gcd(p, n)$ we have

$$\sum_{q=1}^n \exp(2\pi ip/n)^{ql} = n.$$

We get zero otherwise. This yields for the remaining terms without the scalar in front

$$\sum_{p=1}^{n-1} [w^k] \exp\left(\sum_{l\ge 1} (-1)^{ml-1} n \frac{w^{ml}}{ml} \right) = \sum_{p=1}^{n-1} [w^k] \exp\left(-\frac{n}{m} \sum_{l\ge 1} \frac{(-w)^{ml}}{l} \right) \\ = \sum_{p=1}^{n-1} [w^k] \exp\left(-\frac{n}{m}\log\frac{1}{1-(-w)^m}\right) = \sum_{p=1}^{n-1} [w^k] (1-(-w)^{n/\gcd(p, n)})^{\gcd(p, n)} \\ = \sum_{p=1}^{n-1} [w^k] (1+(-1)^{1+n/\gcd(p, n)} w^{n/\gcd(p, n)})^{\gcd(p, n)}.$$

Using an Iverson bracket this becomes

$$\sum_{p=1}^{n-1} [[n/\gcd(p,n)|k]] \times {\gcd(p, n)\choose k\gcd(p,n)/n} (-1)^{k\gcd(p,n)/n+k}.$$

Putting it all together we thus obtain

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} + (-1)^k {n\choose k}^{-1} \frac{1}{n} \sum_{p=1}^{n-1} [[n/\gcd(p,n)|k]] \times {\gcd(p, n)\choose k\gcd(p,n)/n} (-1)^{k\gcd(p,n)/n}.}$$

Note that $n/\gcd(p,n)$ is a divisor of $n$ that is at least two (we would need $p=n$ to get $n/\gcd(p,n) = 1$ but $p\lt n$). This means when $\gcd(k, n) = 1$ the Iverson bracket fails for all $p$ and only the first term remains, which is what we wanted to prove.

As a sanity check we evaluate the formula when $k=n.$ The sum of the one subset is $n(n+1)/2$ so we should get for the probability one when $n$ is odd and zero when it is even. We find

$$\frac{1}{n} + (-1)^n {n\choose n}^{-1} \frac{1}{n} \sum_{p=1}^{n-1} {\gcd(p, n)\choose \gcd(p,n)} (-1)^{\gcd(p,n)} \\ = \frac{1}{n} + (-1)^n \frac{1}{n} \sum_{p=1}^{n-1} (-1)^{\gcd(p,n)} = (-1)^n \frac{1}{n} \sum_{p=1}^{n} (-1)^{\gcd(p,n)} \\ = (-1)^n \frac{1}{n} \sum_{d|n} \sum_{\gcd(p,n) = d} (-1)^d = (-1)^n \frac{1}{n} \sum_{d|n} (-1)^d \sum_{\gcd(q,n/d) = 1} 1 \\ = (-1)^n \frac{1}{n} \sum_{d|n} (-1)^d \varphi(n/d).$$

We evaluate this using formal Dirichlet series, starting from $\sum_{d|n} \varphi(d) = n$ which yields

$$\sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$

Furthermore we have

$$\sum_{n\ge 1} \frac{(-1)^n}{n^s} = -\left(1-\frac{2}{2^s}\right)\zeta(s).$$

This means that

$$\sum_{n\ge 1} \frac{1}{n^s} \sum_{d|n} (-1)^d \varphi(n/d) = -\left(1-\frac{2}{2^s}\right) \zeta(s-1).$$

Now we have for $n$ even

$$- (-1)^n \frac{1}{n} [n^{-s}] \left(1-\frac{2}{2^s}\right) \zeta(s-1) = - (-1)^n \frac{1}{n} (n - 2 [(n/2)^{-s}] \zeta(s-1)) \\ = - (-1)^n \frac{1}{n} (n - 2 \times n/2) = 0.$$

We obtain zero as required. On the other hand with $n$ odd we find

$$- (-1)^n \frac{1}{n} [n^{-s}] \left(1-\frac{2}{2^s}\right) \zeta(s-1) = - (-1)^n \frac{1}{n} [n^{-s}] \zeta(s-1) \\ = - (-1)^n \frac{1}{n} \times n = 1,$$

again as required. This concludes the sanity check. and indeed the entire argument.

Remark. Some of this material is duplicate where I have not found the links however.

$\endgroup$

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.