Exercise 2.2.16* (A result from Edouard Lucas)

Proof.

a)

Write $f(x)={(1+x)}^{2^r}-(1+x^{2^r})\in \mathbb{Z}[x]$, and $F(x)\in {𝔽}_2[x]$ the reduced polynomial with coefficients in the field ${𝔽}_2=\{0,1\}$.

We have proved by induction in Problem 14 that ${(1+x)}^{p^r}=1+x^{p^r}$ is true in ${𝔽}_p[x]$ for any prime $p$, and any $r\ge 0$, so

$${(1+x)}^{2^r}=1+x^{2^r}\in {𝔽}_2[x].$$

So $F(x)=0$. This is equivalent to the fact that all coefficients of $f(x)={(1+x)}^{2^r}-(1+x^{2^r})\in \mathbb{Z}[x]$ are even.

b)

Write $n=\underset{r\in ℛ}{\sum <!--\; FUNCTION\; APPLICATION\; -->}{2}^r$ in binary. Consider $g(x)={(1+x)}^n-\underset{r\in ℛ}{\prod <!--\; FUNCTION\; APPLICATION\; -->}(1+x^{2^r})$ , and $$G(x)={(1+x)}^n-\underset{r\in ℛ}{\prod }(1+x^{2^r})\in {𝔽}_2[x]$$

the corresponding reduced polynomial with coefficients in ${𝔽}_2$. Then, in ${𝔽}_2[x]$

$$\begin{array}{llll}\hfill {(1+x)}^n& ={(1+x)}^{\underset{r\in ℛ}{\sum }{2}^r}& \hfill & \\ \hfill & =\underset{r\in ℛ}{\prod }{(1+x)}^{2^r}& \hfill & \\ \hfill & =\underset{r\in ℛ}{\prod }(1+x^{2^r}).& \hfill & \end{array}$$

Therefore $G(x)=0$, so all coefficients of the polynomial $g(x)={(1+x)}^n-\underset{r\in ℛ}{\prod <!--\; FUNCTION\; APPLICATION\; -->}(1+x^{2^r})$ are even.

c)

We expand both members of the equality $${(1+x)}^n=\underset{r\in ℛ}{\prod }(1+x^{2^r})\in {𝔽}_2[x].$$

First ${(1+x)}^n=\sum <!--\; FUNCTION\; APPLICATION\; -->\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)x^k$. Next, the expansion of ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{r\in ℛ}(1+x^{2^r})$ contains the products $x^{r_1}{x}^{r_2}\cdots x^{r_k}$, where $\{r_1,r_2,\dots ,r_k\}$ is any subset $𝒯$ among the $2^{|𝒮|}$ subsets of $𝒮$.

$$\begin{array}{llll}\hfill \underset{r\in ℛ}{\prod }(1+x^{2^r})& =\underset{𝒯\subseteq ℛ}{\sum }{x}^{\underset{r\in 𝒯}{\sum }{2}^r}& \hfill & \\ \hfill & =\underset{k=0}{\overset{n}{\sum }}\left(\underset{𝒯\subseteq ℛ,\underset{r\in 𝒯}{\text{∑}}{2}^r=k}{\sum }1\right)x^k.& \hfill & \end{array}$$

The comparison of the coefficient of $x^k$ in these two expansions gives

$$\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)\equiv \underset{𝒯\subseteq ℛ,\underset{r\in 𝒯}{\text{∑}}{2}^r=k}{\sum }1(mod2),$$

where

$$\begin{array}{llll}\hfill \underset{𝒯\subseteq ℛ,\underset{r\in 𝒯}{\text{∑}}{2}^r=k}{\sum }1& =\mathrm{Card}\left\{𝒯\subseteq ℛ\mid \underset{r\in 𝒯}{\sum }{2}^r=k\right\}.& \hfill & \\ \hfill & & \hfill \end{array}$$

Write $k={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{s\in 𝒮}{2}^s$. The uniqueness of the decomposition of an integer in binary shows that there is exactly one subset $𝒮$ such that $k={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{s\in 𝒮}{2}^s$. Therefore

$$\mathrm{Card}\left\{𝒯\subseteq ℛ\mid \underset{r\in 𝒯}{\sum }{2}^r=k\right\}=\{\begin{array}{cc}1\hfill & \text{if }𝒮\subseteq ℛ\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

This shows that

$$\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)\equiv \{\begin{array}{cc}1(\mathit{mod}2)\hfill & \text{if }𝒮\subseteq ℛ\hfill \\ 0(\mathit{mod}2)\hfill & \text{otherwise}.\hfill \end{array}$$

In other words, $\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)$ is odd if and only if $𝒮\subseteq ℛ$.

To give an example, for $n=11=\overline{1011}={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{r\in \{0,1,3\}}{2}^r$,

$$\begin{array}{ccccccccccccc}\hfill k\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill & \hfill 5\hfill & \hfill 6\hfill & \hfill 7\hfill & \hfill 8\hfill & \hfill 9\hfill & \hfill 10\hfill & \hfill 11\hfill \\ \hfill \left(\genfrac{}{}{0.0pt}{}{11}{k}\right)\hfill & \hfill 1\hfill & \hfill 11\hfill & \hfill 55\hfill & \hfill 165\hfill & \hfill 330\hfill & \hfill 462\hfill & \hfill 462\hfill & \hfill 330\hfill & \hfill 165\hfill & \hfill 55\hfill & \hfill 11\hfill & \hfill 1\hfill \end{array}$$

$\left(\genfrac{}{}{0.0pt}{}{11}{k}\right)$, is odd for the eight elements $0=\overline{0000},1=\overline{0001},2=\overline{0010},3=\overline{0011},8=\overline{1000},9=\overline{1001},10=\overline{1010},11=\overline{1011}$.

d)

The integers $k\in [[0,n]]$ such that $\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)$ is odd are the integers $k$ whose unique binary expansion is $k={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{s\in 𝒮}{2}^s$, where $𝒮\subseteq ℛ$. There are $|𝒫(ℛ)|=2^{|ℛ|}=2^{w(n)}$ such subsets $𝒮$.

So $\left(\genfrac{}{}{0.0pt}{}{n}{k}\right)$ is odd for precisely $2^{w(n)}$ values of $k$.