Divisibility of Dice Sums by 6 and 7
You roll $n$ fair six-sided dice and let $S_n$ denote their sum.
- What is the probability that $S_n$ is divisible by $6$?
- What is the probability that $S_n$ is divisible by $7$?
Use the roots of unity filter (discrete Fourier analysis on cyclic groups) to derive closed-form expressions for both cases, and explain why the two answers behave so differently.
Hints
- Think about what the distribution of a single die looks like modulo $6$ versus modulo $7$. Is either one already uniform?
- The roots of unity filter extracts the probability of a specific residue: $P(m \mid S_n) = \frac{1}{m}\sum_{k=0}^{m-1}[f(\omega^k)]^n$ where $f$ is the die's pgf and $\omega = e^{2\pi i/m}$.
- For mod $6$, evaluate $\sum_{j=1}^{6} \omega^{jk}$ using the fact that $\omega^6 = 1$. For mod $7$, note that $\gcd(6,7) = 1$ forces $\{1k, 2k, \ldots, 6k\}$ to hit all non-zero residues mod $7$.
Worked Solution
How to Think About It: The core question is: what fraction of the time does the sum of $n$ dice land on a particular residue class? Before doing any math, think about symmetry. Each die takes values
Quick Estimate: For mod $6$: the symmetry argument above immediately gives $P(6 \mid S_n) = 1/6$ for all $n$. For mod $7$: with $n = 1$, the sum is
Approach: Use the probability generating function of each die together with the roots of unity filter to extract the coefficient sum for a given residue class.
Formal Solution:
The pgf of one fair die is:
$f(z) = \frac{1}{6}(z + z^2 + z^3 + z^4 + z^5 + z^6) = \frac{z}{6} \cdot \frac{1 - z^6}{1 - z}$
The pgf of the sum $S_n$ is $[f(z)]^n$. The roots of unity filter extracts the probability that $S_n \equiv 0 \pmod{m}$:
$P(m \mid S_n) = \frac{1}{m} \sum_{k=0}^{m-1} [f(\omega^k)]^n$
where $\omega = e^{2\pi i / m}$.
Part 1: Divisibility by 6
Set $m = 6$ and $\omega = e^{2\pi i / 6}$. We need $f(\omega^k)$ for $k = 0, 1, \ldots, 5$.
- $f(1) = 1$ (trivially).
- For $k = 1, 2, 3, 4, 5$: we compute $f(\omega^k) = \frac{1}{6}\sum_{j=1}^{6} \omega^{jk}$. Since $\omega^6 = 1$, the set $\{\omega^k, \omega^{2k}, \ldots, \omega^{6k}\}$ runs through all sixth roots of unity (or repeats a subgroup), and the key point is that $\sum_{j=1}^{6} \omega^{jk} = \sum_{j=0}^{5} \omega^{jk} = 0$ whenever $6 \nmid k$.
So $f(\omega^k) = 0$ for $k = 1, 2, 3, 4, 5$, and:
$P(6 \mid S_n) = \frac{1}{6}\bigl[1^n + 0 + 0 + 0 + 0 + 0\bigr] = \frac{1}{6}$
for all $n \geq 1$. This is exact, not an approximation.
Part 2: Divisibility by 7
Set $m = 7$ and $\omega = e^{2\pi i / 7}$. For $k \neq 0$:
$f(\omega^k) = \frac{1}{6}\sum_{j=1}^{6} \omega^{jk}$
Since $\gcd(6, 7) = 1$, the map $j \mapsto jk \mod 7$ for $j = 1, \ldots, 6$ hits all non-zero residues mod $7$ exactly once. Therefore:
$\sum_{j=1}^{6} \omega^{jk} = \sum_{r=1}^{6} \omega^r = \left(\sum_{r=0}^{6} \omega^r\right) - 1 = 0 - 1 = -1$
So $f(\omega^k) = -1/6$ for every $k = 1, 2, \ldots, 6$. Plugging in:
$P(7 \mid S_n) = \frac{1}{7}\left[1 + 6 \cdot \left(-\frac{1}{6}\right)^n\right] = \frac{1}{7}\left[1 + \frac{(-1)^n}{6^{n-1}}\right]$
Verification with small cases: - $n = 1$: $P = \frac{1}{7}[1 - 1] = 0$. Correct -- a single die never sums to a multiple of $7$. - $n = 2$: $P = \frac{1}{7}[1 + 1/6] = \frac{1}{7} \cdot \frac{7}{6} = \frac{1}{6}$. Correct -- out of $36$ outcomes, exactly $6$ give $S_2 = 7$. - $n \to \infty$: $P \to 1/7$, as the correction term $(-1/6)^n \to 0$.
Answer:
$P(6 \mid S_n) = \frac{1}{6} \quad \text{(exact, for all } n \geq 1\text{)}$
$P(7 \mid S_n) = \frac{1}{7}\left[1 + \frac{(-1)^n}{6^{n-1}}\right]$
The difference comes down to whether $m$ divides the number of faces on the die. When $m = 6$, each die is already uniform mod $6$, so divisibility is immediate. When $m = 7$, the die cannot hit residue $0$ alone, so uniformity only emerges asymptotically.
Intuition
The roots of unity filter is the workhorse tool for extracting residue-class probabilities from generating functions. The core idea is simple: summing $f(\omega^k)$ over all $m$-th roots of unity $\omega^k$ kills every term in the generating function except those whose exponent is divisible by $m$. It is really just the discrete Fourier transform applied to probability -- and it shows up constantly in combinatorics, number theory, and quant interviews involving dice, cards, or any discrete random variable.
The elegant punch line here is why divisibility by $6$ gives an exact uniform answer while divisibility by $7$ does not. A six-sided die hits each residue mod $6$ exactly once, so its pgf vanishes at every non-trivial sixth root of unity. That makes the filter collapse to a single term. For mod $7$, the die misses residue $0$, and the correction term $(-1/6)^n$ quantifies exactly how much "non-uniformity" is left after $n$ rolls. This exponential convergence to uniformity is a miniature version of mixing in Markov chains -- a pattern that appears everywhere from card shuffling theory to MCMC convergence diagnostics.