binomial-coefficientscombinatoricsfractals
If Sierpinski Triangles are found in
Pascal's Triangle under modulo 2 what happens when we view Pascal's Triangle under modulo $m$ where $m>2$? Do fractals appear and if so for which numbers?
Related question, can we predict any behaviors if $m$ is prime?
I looked at $m=3$ with about fifty rows and saw a complicated pattern of upwards and downwards facing triangles be highlighted, but was unsure if the patterns were forming a fractal.
The following relations all hold modulo 2 (you can think of them as a special case of Lucas' theorem, or just prove them directly):
$$ {2a \choose 2b} \equiv {a \choose b}, \mbox{ and } {2a \choose 2b+1} \equiv 0\\ {2a+1 \choose 2b} \equiv {2a+1 \choose 2b+1} \equiv {a \choose b} \, . $$
Using these, you can recursively check whether any given bit sequence $B=(b_1,b_2,\dots,b_k)$ could possibly occur:
Each application of one of these rules will approximately halve the length of $B$; if neither rule can be made to apply at any step, we eliminate $B$ from consideration. So eventually, if you don't eliminate $B$ from consideration, you'll end up at the trivial string $1$ (which gets sent to itself by both rules, and clearly appears in the triangle).
Applying this algorithm, we can see that your $1101$ fails immediately; it doesn't consist either of repetitions or of something padded with zeroes. The other specific examples you're asking about will fail for similar reasons. Any sequence with two adjacent $1$s cannot have rule 1. applied to it: that already means it's impossible for every other bit to be a $0$. Moreover, any sequence with an odd-length run of either $1$s or $0$s cannot have rule 2. applied to it, unless the run starts or ends the sequence; it makes it impossible to pair the bits off with each other. Since your sequences end with two $1$s, and have a run of $2^n-1$ $0$s in the middle, neither rule can be applied to them, so they can't possibly be in the triangle.
On the other hand, something like $101000001$ passes, via the sequence of transformations $$ 101000001 \to^1 11001 \to^2 101 \to^1 11 \to^2 1 \, . $$
If you want to enumerate all sequences that appear somewhere, you can apply these two rules in reverse. For a given sequence $B=(b_1,b_2,\dots,b_k)$, how could it have been produced from rules 1. and 2.?
$B$ could have been produced from rule 1. by any of four bit strings: $(0, b_1, 0, b_2, \dots, 0, b_k, 0)$, $(0, b_1, 0, b_2, \dots, 0, b_k)$, $(b_1, 0, b_2, \dots, 0, b_k, 0)$, or $(b_1, 0, b_2, \dots, 0, b_k)$.
$B$ could also have been produced from rule 2. by any of four bit strings: $(b_1, b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_1, b_2, b_2, \dots,b_{k-1}, b_{k-1}, b_k)$, or $(b_1, b_2, b_2, \dots, b_{k-1}, b_{k-1}, b_k)$.
In both cases, there is a longest string that can be produced (the first one listed), and three other strings that can be obtained from the longest string by removing its first or last element, or both.
For example, if we start with the string $1011$, we can run rule 1. backward to get the strings $010001010$, $10001010$, $01000101$, and $1000101$. We can run rule 2. backward to get the strings $11001111$, $1001111$, $1100111$, and $100111$.
We know that, for any string which appears in the triangle, we can repeatedly apply rules 1. and 2. until the string $1$ is obtained. So we must be able to obtain all possible strings by repeatedly applying the backwards versions of rules 1. and 2. to the string $1$. Moreover, each backwards rule goes from a string of length $k$ to a string of length at least $2k-2$. So if we want to find all strings of length $k$, we'll only have to apply the algorithm until the shortest strings being produced at any given stage are of length at least $k$, and this will take about $\log_2 k$ steps.
To be precise, if we start with a string of length $3$, we can get to a string of length up to $2^n+2$ in $n$ steps. Our algorithm starts being a little funkier for shorter strings than that, but you can enumerate all the possibilities and see that every string of length $3$ is obtainable from the string $1$ in at most $2$ steps. So any string of length up to $2^n+2$ can be obtained in at most $n+2$ steps, meaning that any string of length $k$ can be obtained in at most $\left\lceil\log_2(k-2)+2\right\rceil$ steps.
This already gives us a pretty good algorithm for enumerating all possible strings. But we can do better. The implication of everything above is that any sequence comes from a $1$ floating somewhere in the triangle. But no matter which $1$ we start with, we'll end up with the same set of bit strings (as long as we adopt the standard convention that ${a \choose b}=0$ whenever $b<0$ or $b>a$; otherwise, some of the sequences we produce might go out of bounds).
So we might as well imagine that we're starting with the $1$ at the very top of the triangle, in row $0$. By the original Lucas' theorem argument, each step will, at worst, take us from row $n$ of the triangle to row $2n+1$. So, after $t$ steps, we'll be, at worst on row $2^t-1$. Since $\left\lceil\log_2(k-2)+2\right\rceil$ steps are sufficient to produce all strings of length $k$, we see that every string of length $k$ that occurs at all will occur before row $$ 2^\left\lceil\log_2(k-2)+2\right\rceil-1<8k \, , $$ to give a crude upper bound which can probably be improved upon.
In summary, every bit string of length $k$ that appears in the mod 2 version of Pascal's triangle will occur somewhere in the first $8k$ rows. So you can enumerate them all just by computing the first $8k$ rows of Pascal's triangle and looking at all the $k$-element substrings of the result (remembering to pad the triangle on the left and right by sufficiently many zeroes). I think this a much nicer way of doing things than my other algorithm (which basically boiled down to computing bits of Pascal's triangle anyways...)
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.
Best Answer
For prime $m=p$ you have Lucas' theorem. It might not be obvious, but this gives a fractal structure to the binomial coefficients, modulo $p$.
(From here out, $m$ is an arbitrary integer, not $p$, because this is the statement from Wikipedia.)
It says that if $m=\sum_{i=0}^k m_i p^i$ and $n=\sum_{i=0}^k n_ip_i$ are the base $p$ representations (so $0\leq m_i,n_i<p$) then:
$$\binom{m}{n}\equiv \prod_{i=0}^k \binom{m_i}{n_i} \pmod p$$
Specifically, then, this means that if $0\leq a< b<p^k$ and and $M,N$ are any non-negative integers, then:
$$\binom{Mp^k + a}{Np^k+b} \equiv 0\pmod p$$
This gives big blocks where Pascal's triangle is zero, as in Sierpinski.
More generally, we might want to ask about modulo prime powers.
This answer gives some details on Andrew Granville's result for modulo prime powers. Don't know how "fractal" that result is. It seems to be not as "fractal" is the result for primes, but it is hard to tell.
If it is, then modulo any number $M$, Chinese Remainder Theorem says that Pascal's triangle looks like the overlay of the fractals for each of the prime powers in the unique factorization.
Without Granville, if $M$ is square-free, there will be a fractal structure, modulo $M$.