Why does Pascal's Triangle (mod 2) encode the Fermat primes?

Question

I've just finished the recent Numberphile video on Pascal's Triangle and learned about a new-to-me property of the triangle; the Fermat primes $F_0 = 3, F_1 = 5, F_2 = 17, \dots$ are encoded in it somehow!

Take the standard Pascal's Triangle $(\mod 2)$ and read out each row $r_n$ as binary, $x_n = \sum_{i=0}^n 2^{i}r_{n,i}$ then the first few rows read as 1, 3, 5, 15, 17, 51, 85, 255, 257, … These are either Fermat primes or products of Fermat primes!

I wrote a short Python Script to explore a bit. The first few rows present an elegant binary pattern, $x_n = \prod_{i=0}^n F_{i}^{r_{n,i}}$ selecting $3, 5, 3 \times 5, 17, 3 \times 17$, etc. This pattern is striking in its precision.

I wanted to know what happens around row 32/33, when we reach the Fermat non-prime $F_5 = 2^{2^5}+1 = 4294967297 = 641 \times 6700417$. The pattern breaks, and $F_5$ shows up. However, on the next few rows, we have $12884901891 = 3 \times 641 \times 6700417, 21474836485 = 5 \times 641 \times 6700417, \dots$ So this means that Fermat numbers specifically, rather than just some certain primes, are part of this overall correspondence. Additionally, we can see that the binary pattern repeats here, and it goes through all of the same permutations as earlier, but with the two new factors from $F_5$. $F_6$ also adds two more factors and repeats the pattern. I haven't yet explored higher.

I would like to know why this correspondence exists and what it might tell us about Fermat numbers. Personally, I found this jaw-dropping.

Answer 1

It is indeed true that each $x_{n}$ is a product of integers of the form $2^{2^{m}}+1$ (although not of the ones you have stated).

To prove this, we fix an $n\in\mathbb{N}$. Your definition of $x_{n}$ rewrites as $x_{n}=\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}$.

Write $n$ in the form $n=a_{k}2^{k}+a_{k-1}2^{k-1}+\cdots+a_{0}2^{0}$ for some $k\in\mathbb{N}$ and $a_{0},a_{1},\ldots,a_{k}\in\left\{ 0,1\right\} $. (This is just the base-$2$ representation of $n$, possibly with leading zeroes.)

Lucas's theorem tells you that if $i=b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$ for some $b_{0} ,b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $, then

$\dbinom{n}{i}\equiv\dbinom{a_{k}}{b_{k}}\dbinom{a_{k-1}}{b_{k-1}} \cdots\dbinom{a_{0}}{b_{0}}=\prod\limits_{j=0}^{k}\underbrace{\dbinom{a_{j}}{b_{j}} }_{\substack{= \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} \\\text{(since }a_{j}\text{ and }b_{j}\text{ lie in }\left\{ 0,1\right\} \text{)}}}$

$=\prod\limits_{j=0}^{k} \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} = \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\text{ for all }j\text{;}\\ 0, & \text{otherwise} \end{cases} \mod 2$.

Hence, the $i\in\mathbb{N}$ for which $\dbinom{n}{i}$ is odd are precisely the numbers of the form $b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$ for $b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $ satisfying $\left( b_{j}\leq a_{j}\text{ for all }j\right) $. Since all these $i$ satisfy $i \in \left\{ 0,1,\ldots,n\right\}$ (because otherwise, $\dbinom{n}{i}$ would be $0$ and therefore could not be odd), we can rewrite this as follows: The $i \in \left\{ 0,1,\ldots,n\right\}$ for which $\dbinom{n}{i}$ is odd are precisely the numbers of the form $b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$ for $b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $ satisfying $\left( b_{j}\leq a_{j}\text{ for all }j\right) $. Since these numbers are distinct (because the base-$2$ representation of any $i\in\mathbb{N}$ is unique, as long as we fix the number of digits), we thus can substitute $b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$ for $i$ in the sum $\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}2^{i}$. Thus, this sum rewrites as follows:

$\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}2^{i} =\underbrace{\sum\limits_{\substack{b_{0},b_{1} ,\ldots,b_{k}\in\left\{ 0,1\right\} ;\\b_{j}\leq a_{j}\text{ for all }j} }}_{=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_k} }\underbrace{2^{b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}}}_{=\left( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1}}\cdots\left( 2^{2^{0}}\right) ^{b_{0}}}$

$=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_{k} }\left( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\cdots\left( 2^{2^{0}}\right) ^{b_{0}}$

$=\left( \sum\limits_{b_{k}=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b_{k}}\right) \left( \sum\limits_{b_{k-1}=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\right) \cdots\left( \sum\limits_{b_{0}=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b_{0}}\right) $

$=\left( \sum\limits_{b=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b}\right) \left( \sum\limits_{b=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b}\right) \cdots\left( \sum\limits_{b=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b}\right) $

$=\prod\limits_{g=0}^{k}\underbrace{\left( \sum\limits_{b=0}^{a_{g}}\left( 2^{2^{g} }\right) ^{b}\right) }_{\substack{= \begin{cases} 2^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} \\\text{(since }a_{g}\in\left\{ 0,1\right\} \text{)}}}$

$=\prod\limits_{g=0}^{k} \begin{cases} 2^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} $

$=\left( \prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g} =1}}\left( 2^{2^{g}}+1\right) \right) \underbrace{\left( \prod\limits _{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=0}}1\right) }_{=1}$

$=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( 2^{2^{g}}+1\right) $.

Thus, $x_{n}=\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( 2^{2^{g}}+1\right) $. This is clearly a product of Fermat numbers.

EDIT: This result also appears as equation (10) in Andrew Granville, Binomial coefficients modulo prime powers, 1997, where it is ascribed to Larry Roberts.

Answer 2

The claim is an example of the "law of small numbers".

The numbers you are looking at are products of the Fermat numbers $2^{2^n} + 1$, and not the Fermat primes. Since the first few such numbers are Fermat primes, but no larger Fermat primes are known, it is not surprising at all that the pattern holds for the first few $n$ and then fails at 32. It will continue to fail over and over again at larger row numbers.

More specifically, if $n = \sum_{0 \leq i \leq t} a_i 2^i$, the identity is $\sum_{0 \leq i \leq n} ({n \choose i} \bmod 2) 2^i = \prod_{0 \leq j \leq t} (2^{2^j}+1)^{a_j}$. This is indeed a nice identity, but it has virtually nothing to do with primes or Fermat primes.

Answer 3

There is a 1977 article, "A Relationship Between Pascal's Triangle And Fermat's Numbers" (link to PDF), which provides a proof by induction that the number you call $x_n$ is equal to $$F_k^{d_k}\cdots F_0^{d_0}$$ where $n=(d_k\ldots d_0)_2$ is the binary expansion of $n$.