Classic Iterated Function Systems

Proof of Lucas's Theorem

Let $p$ be a prime number, and let $r$ and $c$ be written in $p$-ary notation

$$\begin{array}{l} r = {r_k} \cdots {r_2}{r_1}{r_0} = {r_0} + {r_1}p + {r_2}{p^2} + \cdots + {r_k}{p^k} \qquad (0 \le {r_i} \lt p) \\ c = {c_k} \cdots {c_2}{c_1}{c_0} = {c_0} + {c_1}p + {c_2}{p^2} + \cdots + {c_k}{p^k} \qquad (0 \le {c_i} \lt p) \\ \end{array}$$

Then

$$\left( {\begin{array}{c} r \\ c \\ \end{array}} \right) = \left( {\begin{array}{c} {{r_0}} \\ {{c_0}} \\ \end{array}} \right)\left( {\begin{array}{c} {{r_1}} \\ {{c_1}} \\ \end{array}} \right)\left( {\begin{array}{c} {{r_1}} \\ {{c_1}} \\ \end{array}} \right) \cdots \left( {\begin{array}{c} {{r_k}} \\ {{c_k}} \\ \end{array}} \right)(\bmod p)$$

We take here the standard convention that the binomial coefficient $(r,c)=0$ if $c \gt r$.

We first need to show that \( (1 + x)^{p^{\Large{n}}} = 1 + x^{p^{\Large{n}}} \bmod p \) when $p$ is a prime and $n > 0$. If $0 < k < p^n$, then

$$ \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = \frac{{p^n !}}{{k!(p^n - k)!}} = \frac{{p^n }}{k}\left( {\begin{array}{*{20}c} {p^n - 1} \\ {k - 1} \\ \end{array}} \right) $$

In particular, this means that \( k\left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = p^n \left( {\begin{array}{*{20}c} {p^n - 1} \\ {k - 1} \\ \end{array}} \right). \) At least $n$ powers of $p$ divide the right hand side of this equation, but at most $n-1$ powers of $p$ divide $k$ on the left side. Thus $p$ must divide \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) \) and so \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = 0\bmod p. \) But when $k = 0$ or $k = p^n$, then \( \left( {\begin{array}{*{20}c} {p^n } \\ k \\ \end{array}} \right) = 1. \)

These observations show that in the binomial theorem expansion of \( (1 + x)^{p^n }, \) only the first ($k = 0$) and last ($k = p^n$) coefficients are non-zero mod $p$, and our desired result follows.

Suppose $p$ = 5, $r$ = 482, and $c$ = 176. First note that

\[ \begin{array}{l} 482 = 3 \cdot 5^3 + 4 \cdot 5^2 + 1 \cdot 5 + 2 = 3412{\text{ (base }}5) \\ 176 = 1 \cdot 5^3 + 2 \cdot 5^2 + 0 \cdot 5 + 1 = 1201{\text{ (base }}5) \\ \end{array} \]

Then using the lemma allows us to write

\[ \begin{align} (1 + x)^{482} &= (1 + x)^{3(125)} \cdot (1 + x)^{4(25)} \cdot (1 + x)^{1(5)} \cdot (1 + x)^2 \\ &= (1 + x^{125} )^3 \cdot (1 + x^{25} )^4 \cdot (1 + x^5 )^1 \cdot (1 + x)^2 \bmod 5\\ \end{align} \]

On the left side, the coefficient of $x^{176}$ will be \( \left( {\begin{array}{c} {482} \\ {176} \\ \end{array}} \right). \) The only way to get $x^{176}$ in the product on the right side is to use one $x^{125}$ term, two $x^{25}$ terms, no $x^5$ terms, and one $x^1$ term. From the choices available in the product expansion above, we can do this in exactly \( \left( {\begin{array}{c} 3 \\ 1 \\ \end{array}} \right)\left( {\begin{array}{c} 4 \\ 2 \\ \end{array}} \right)\left( {\begin{array}{c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{c} 2 \\ 1 \\ \end{array}} \right) \) ways. Hence

\[ \left( {\begin{array}{c} {482} \\ {176} \\ \end{array}} \right) = \left( {\begin{array}{c} 3 \\ 1 \\ \end{array}} \right)\left( {\begin{array}{c} 4 \\ 2 \\ \end{array}} \right)\left( {\begin{array}{c} 1 \\ 0 \\ \end{array}} \right)\left( {\begin{array}{c} 2 \\ 1 \\ \end{array}} \right)\bmod 5 \]

The proof is based on the Binomial Theorem for the expansion of $(1+x)^r$ as illustrated in the example above.

$$ \begin{align} \sum\limits_{c = 0}^r {\,\left( {\begin{array}{*{20}c} r \\ c \\ \end{array}} \right)\,x^c } &= \left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{{\kern 1pt} r} = \prod\limits_{m = 0}^k {\,\left[ {\left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{p^{\Large{m}} } } \right]^{ r_{ {\Large{m}}} } } \\ \\ &= \prod\limits_{m = 0}^k {\,\left( {1 + x^{{\kern 1pt} p^{ {\Large{m}}} } } \right)^{ r_{ {\Large{m}}} } (\bmod p)} \quad \left[ {{\text{since }}\left( {{\kern 1pt} {\kern 1pt} 1 + x} \right)^{p^{\Large{m}} } \equiv 1 + x^{{\kern 1pt} p^{\Large{m}} } (\bmod p)} \right] \\ \\ &= \prod\limits_{m = 0}^k {\,\left[ {\sum\limits_{s_{\Large{m}} = 0}^{r_{ {\Large{m}}} } {\left( {\begin{array}{*{20}c} {r_{ m} } \\ {s_{ m} } \\ \end{array}} \right)x^{{\kern 1pt} s_{\Large{m}} {\kern 1pt} p^{\Large{m}} } } } \right]} \,\,(\bmod p) \\ \\ &= \sum\limits_{c = 0}^r {\,\left[ {\sum {\prod\limits_{m = 0}^k {\left( {\begin{array}{*{20}c} {r_{ m} } \\ {s_{ m} } \\ \end{array}} \right)} } } \right]\,x^c } \;(\bmod p) \\ \end{align} $$

where for each value of $c$, the inner sum in the last sum is taken over all sets $(s_0, s_1, s_2, \ldots, s_k)$ such that

\[ 0 \le s_m \le c_m \lt p \text{ and } \sum\limits_{m = 0}^k {s_m p^m = c} \]

But there is at most one such set of coefficients, given by $s_m = c_m$ if every $c_m ≤ r_m$ (since there is a unique representation for the $p$-ary form of $c$). If $c_m \gt r_m$ for some $m$, then the inner sum is zero. In either case, the theorem follows by equating coefficients of $x^c$ for each $0 ≤ c ≤ r$.