doc.tex

\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{cleveref}
\usepackage{epstopdf}
\usepackage{framed}
\usepackage{array}
\usepackage{comment}
\usepackage{animate}
\usepackage{hyperref}


\epstopdfDeclareGraphicsRule{.gif}{png}{.png}{convert gif:#1 png:\OutputFile}
\AppendGraphicsExtensions{.gif}
\setbeamersize{text margin left=5mm,text margin right=5mm} 
\graphicspath{{figures/}}
\usenavigationsymbolstemplate{} 

\title{Is Pascal's Triangle a Fractal ?}
\author{Ankith A Das}
\institute{The University of Sydney}
\date{\today}

\begin{document}
\frame{\titlepage}

% \begin{frame}
%     \textit{Mathematics is the art of giving the \textcolor{red}{same name} to \textcolor{blue}{different things}}
% \\[5pt]
% \rightline{{\rm --- Henri Ponicar\'e}}
% \end{frame}

\section[Outline]{}
\setbeamercovered{transparent}

\section{Pascal's Triangle}
\begin{frame}
    \frametitle{Pascal's Triangle}
    \begin{equation*}
        \begin{array}{c}
            \begin{array}{c}
             1 \\
            \end{array}
             \\
            \begin{array}{cc}
             1 & 1 \\
            \end{array}
             \\
            \begin{array}{ccc}
             1 & 2 & 1 \\
            \end{array}
             \\
            \begin{array}{cccc}
             1 & 3 & 3 & 1 \\
            \end{array}
             \\
            \begin{array}{ccccc}
             1 & 4 & 6 & 4 & 1 \\
            \end{array}
             \\
            \begin{array}{cccccc}
             1 & 5 & 10 & 10 & 5 & 1 \\
            \end{array}
             \\
            \begin{array}{ccccccc}
             1 & 6 & 15 & 20 & 15 & 6 & 1 \\
            \end{array}
             \\
            \begin{array}{cccccccc}
             1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \\
            \end{array}
        \end{array}
    \end{equation*}
    \begin{itemize}
        % Add an image of pascal Triangle
        \item
        One of the earliest mentions was in a Chinese document at around 1303 AD
        \item
        Looks pretty innocent right?
    \end{itemize}

\end{frame}

\begin{frame}
    \frametitle{Pascal's Triangle}
    %We will look at the patterns when we color Pascal's triangle \\
    \begin{itemize}
        \item It is observed by coloring 
        \begin{enumerate}
            \item all odd numbers black
            \item all even numbers white
        \end{enumerate}
    \end{itemize}
    \begin{figure}
        \centering
        \includegraphics[scale=0.8]{Mod2,7.pdf}
    \end{figure}
    \let\thefootnote\relax\footnotetext{Modified code:https://tex.stackexchange.com/questions/198887/how-can-i-draw-pascals-triangle-with-some-its-properties}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering 
        \includegraphics[scale=0.8]{PascalMod2.pdf}
        \caption{A bigger picture}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{Pascal's Triangle}
    \begin{itemize}
        \item So how can we formulate this pattern ? We can begin by looking at binomial coefficients
        \begin{align*}
            (1+x)^{0} &=\qquad 1 \\
            (1+x)^{1} &=\quad 1+1 x \\
            (1+x)^{2} &= 1+2 x+1 x^{2} \\
            & \vdots \\
            (1+x)^{n} &=a_{0}+a_{1} x+\cdots+a_{n} x^{n} 
        \end{align*}
        where coefficients are given by
        \begin{equation*}
            a_{k}= \binom{n}{k} =\frac{n !}{(n-k) ! k !}, \quad 0 \leq k \leq n
        \end{equation*}
    \end{itemize}
\end{frame}
% Add a picture of skewed pascal triangle, Look into adding numbers to the figure

\begin{frame}
    \frametitle{Pascal's Triangle}
    \begin{itemize}
        \item Checking if a binomial coefficient is odd or even by computing $\frac{n!}{(n-k)!k!}$ is a bad idea
        \begin{align*}
            50! = &3041409320171337804361260816606476884437\\
            &7641568960512000000000000   
        \end{align*}
        \item Even if we use the recursive formula 
        \begin{equation*}
            \binom{n+1}{k}= \binom{n}{k-1} + \binom{n}{k}
        \end{equation*}
        \begin{equation*}
            \binom{40}{20} = 137846528820 > 2^{32}
        \end{equation*}
        which is a big number (computer has fixed precision)
        \item Fortunately, we don't need to compute these large numbers
        \end{itemize}
\end{frame}

\begin{frame}
    \centering 
    \Large
    The Macroscopic view
\end{frame}

% Slide on HOLD!!!
\begin{frame}
    \frametitle{Pascal's Triangle}
    \begin{itemize}
        \item In order to color a row in the triangle, we only need to know the color of the previous row
        %\item In the odd,even coloring case, our problem simplifies to
        %Ex: Divisibility by 2 can be followed from addition rule
        \begin{columns}
            \begin{column}{0.5\textwidth}
                \begin{table}[H]
                    \begin{tabular}{|lll|}
                        \hline
                        $\binom{n+1}{k} = $ & $\binom{n}{k-1} + $& $\binom{n}{k}$\\
                        \hline
                        even & even & even \\
                        odd  & odd  & even \\
                        odd  & even & odd  \\
                        even & odd & odd  \\
                        \hline
                    \end{tabular}
                \end{table}
            \end{column}
            \begin{column}{0.5\textwidth}
                \begin{figure}
                    \centering
                    \includegraphics[scale=0.7]{Mod2,7.pdf}
                \end{figure}
            \end{column}
        \end{columns} 
        \begin{figure}
            \centering
            \includegraphics[scale=0.3]{pascalRule.pdf}
        \end{figure}
        \item The idea of looking at neighbor cells to determine the state of a new cell is the core idea of cellular automata
        %\item Can we extend this idea of divisibility to other numbers ?
        %\item What global patterns do we get? How are they related to binomial coefficient? These are some of the questions that I will try to answer.
        %\item What patterns do we get ? Global pattern? Why? ...IFS
    \end{itemize}
\end{frame}

\section{Cellular Automata}
% \begin{frame}
%     \frametitle{Cellular Automata}
%     \begin{itemize}
%         % \item Prefect feedback machines. They are mathematically finite state machines
%         %\item Each cell has one out of $p$ states. \textit{p-state} automata
%         \item Consists of a grid of cells, each one with a finite number of states, like 1 or 0.
%         \item For each cell, a neighborhood is defined.
%         %\item Can be 1-D, 2-D \dots
%         \item To run cellular automata, we need 2 pieces of information 
%         \begin{enumerate}
%             \item Initial state of cells 
%             %\item Rules to describe new cell state from the states of a group of cells from the previous layer
%             \item Fixed set of rules (rule table) that determine the state of new cell depending upon the states of current and neighborhood cells.
%         \end{enumerate}
%         \item The rules should not depend on the position of the group of cells within the layer.
%         % Under review 
%         % \begin{figure}
%         %     \includegraphics[scale = 0.5]{fig1.png} 
%         % \end{figure}
%     \end{itemize}
% \end{frame}

%% Under Review 
% \begin{frame}
%     \frametitle{Cellular Automata}
%     \begin{itemize}
%         \item More kinds of rules
%         \begin{figure}[H]
%             \includegraphics[scale = 0.37]{fig2}
%             \caption{(a) is a four rule configuration and (b) is a 8 rule configuration}
%         \end{figure}
%     \end{itemize}
% \end{frame}


\subsection{Elementary CA}
\begin{frame}
    \frametitle{Cellular Automata}
    \begin{itemize}
        \item Consists of a grid of cells, each one with a finite number of states, like 1 or 0.
        \begin{figure}
            \centering
            \includegraphics[scale=0.4]{grid.pdf}
        \end{figure}
        \item A set of rules to describe new cell state from the states of a group of cells from the previous layer
        \item Next generation depends on itself,cell to the left and, cell to the right (Neighbors).
        %\item All the rules can be numbered in a nice way using binary
        \begin{figure}[H]
            \includegraphics[scale=0.5]{rulerule30}
            %\caption{Elementary rule 30 = $(00011110)_2$}
        \end{figure}
        \item Ex:
        \begin{figure}
            \centering
            \includegraphics[scale=0.4]{IMG.png}
        \end{figure}
        %\item Total number of rules are $2^{2^3} = 256$
        %\item Mathematica can do this for you very easily using CellularAutomaton[ ]
    \end{itemize}
\end{frame}

\begin{frame}
    \centering
    \animategraphics[loop,width=\linewidth]{2}{figures/gif/frame-}{0}{29}
    \let\thefootnote\relax\footnotetext{https://en.wikipedia.org/wiki/File:One-d-cellular-automaton-rule-110.gif}
\end{frame}

\begin{frame}
    \frametitle{Cellular Automata}
    So lets run some 
    \begin{figure}
        \includegraphics[scale=0.3]{fig3.png}
        \includegraphics[scale=0.5]{rule60.pdf}
        \caption{13 Generations of a 1-D Cellular Automata}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item There $2\times2\times2=8$ binary states for each 3 cells.
        \item So, there are a total of $2^8 = 256$ possible rule sets.
        \item Each rule can be index with 8-bit binary
        \begin{figure}
            \centering
            \includegraphics[scale=0.7]{rule60Num.pdf}
            \caption{Rule $(00111100)_2 = 60$}
        \end{figure}
        \item For the following examples, the initial state is
        \begin{figure}
            \centering 
            \includegraphics[scale=0.6]{initial.pdf}
        \end{figure}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Cellular Automata}
    \begin{figure}
        \centering
        \includegraphics[scale=0.53]{fig4.pdf}
        \caption{Rule 110, this might be special}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{Cellular Automata}
    \begin{figure}
        \includegraphics[scale=0.5]{seir.pdf}
        \includegraphics[scale=0.6]{rule60.pdf}
        \caption{Rule 60. Sierpinski Triangle*}
    \end{figure}
\end{frame}


\begin{frame}
    \begin{figure}
        \includegraphics[scale=0.5]{GlobalMod2.pdf}
        \caption{Sierpinski Triangle}
    \end{figure}
\end{frame}

% \begin{frame}
%     \frametitle{Elementary Cellular Automata}
%     \begin{figure}
%         \includegraphics[scale=0.4]{sier2.pdf}
%         \caption{Rule 90.}
%     \end{figure}
% \end{frame}

\begin{frame}
    \frametitle{Cellular Automata}
    \begin{figure}
        \includegraphics[scale=0.8]{rule30.pdf}
        \caption{Rule 30}
    \end{figure}
    \begin{itemize}
        \item Has been used as a random number generator in Mathematica
        \item Sensitive to initial conditons 
    \end{itemize}
\end{frame}
\subsection{2D CA}

\begin{comment}  
% \begin{frame}
%     \centering \LARGE
%     Let's take it up a notch and see what happens in 2-D...
% \end{frame}

% \begin{frame}
%     \centering \Large
%     Let's play the \textit{Game of Life......}
% \end{frame}

% \begin{frame}
%     \frametitle{2D CA: Game of life...}
%     \begin{itemize}
%         % Maybe I can ger rid of this one 
%         %\item Was very popular through the work of John Horton Conway in 1970's
%         %\item Was made popular through the work of John Horton Conway
%         %\item 2-state CA
%         \item The rules are...
%         \begin{enumerate}
%             \item Cell survives when exactly 2 or 3 of it's 8 neighbors are alive.
%             \item If more than 3 neighbors are alive, the cell dies from over-crowdedness.
%             \item If fewer than 2 neighbors are alive, the cell dies from loneliness.
%             \item Dead cell comes back to life when surrounded by exactly 3 live neighbors.  
%         \end{enumerate}
%         \item Makes some interesting patters and life like behavior 
%         \item \textbf{Note:} The position of the alive and dead cells w.r.t the center does not matter for this rule. Also known as Totalistic CA
%     \end{itemize}
% \end{frame}


% \begin{frame}
%     \frametitle{Cellular Automata}
%     \begin{itemize}
%         \item Another variant of Game of Life: One out of eight rule
%         \begin{enumerate}
%             \item Cell becomes alive if exactly one neighbor is alive.
%             \item Otherwise unchanged.
%         \end{enumerate}
%         \item Has some nice self-similarity
%     \end{itemize}
% \end{frame}

% \begin{frame}
%     \frametitle{Cellular Automata} 
%     \begin{itemize}
%         \item Game of life is just one out of the imaginable set of rules 
%         \item For 2-state 2D automata and a neighborhood of eight cells, there are $2^{2^9} \approx 10^{154}$ different sets of rules!!
%         \item Let's look at another rule: Majority Rule
%         \begin{enumerate}
%             \item If 5 or more of the neighborhood of 9 cells (including itself) are alive, this cell lives or stays alive 
%             \item Otherwise dies or remains dead
%         \end{enumerate}
%         \item Here center cell adjusts to the majority 
%         \item This kind of rule is called Outer Totalistic
%         \item Has some resemblance with percolation
%     \end{itemize}
% \end{frame}

% \begin{frame}
%     \frametitle{Cellular Automata with Different neighbors}
%     \begin{itemize}
%         \item Let's consider only 4 neighbors.
%         \begin{figure}
%             \centering
%             \includegraphics[scale=0.5]{VonNeigh.png}
%         \end{figure}
%         \item C = Center, N = North, E = East, S = South, W = West
%         \item Can number the cell states in binary $(\text{CSWNE})_2$. Ex:$(01100)_2$ means S, W cells are alive, rest are dead
%         \item Total number of sets of rules are $2^{2^5} \approx 4 \cdot 10^9$
%         \item Two interesting examples are shown 
%     \end{itemize}
% \end{frame}

% \begin{frame}
%     \frametitle{Cellular Automata}
%     \begin{table}[H]
%         \begin{tabular}{l|l|l|l|l|l|l|l}
%         CSWNE & C & CSWNE & C & CSWNE & C & CSWNE & C \\
%         \hline
%         00000 & 0 & 01000 & 1 & 10000 & 1 & 11000 & 1 \\
%         00001 & 0 & 01001 & 1 & 10001 & 1 & 11001 & 1 \\
%         00010 & 0 & 01010 & 1 & 10010 & 1 & 11010 & 1 \\
%         00011 & 0 & 01011 & 1 & 10011 & 1 & 11011 & 1 \\
%         00100 & 1 & 01100 & 0 & 10100 & 1 & 11100 & 1 \\
%         00101 & 1 & 01101 & 0 & 10101 & 1 & 11101 & 1 \\
%         00110 & 1 & 01110 & 0 & 10110 & 1 & 11110 & 1 \\
%         00111 & 1 & 01111 & 0 & 10111 & 1 & 11111 & 1
%         \end{tabular}
%     \end{table}
%     \begin{itemize}
%         \item This behaves like a 1D CA
%     \end{itemize}
% \end{frame}

% % Maybe the last point is obvious and need not be stated 
% \begin{frame}
%     \frametitle{Cellular Automata}
%     \begin{itemize}
%         \item Many interesting rules can be given by a simple formula
%         \item Parity Rule:
%         \begin{equation*}
%             C_{new} = C_{old} + N_{old} + E_{old} + S_{old} + W_{old} \mod 2
%         \end{equation*}
%         %\item Again, this is a 2-state CA
%     \end{itemize}
% \end{frame}
\end{comment}

\subsection{Cellular Automata and polynomials}
\begin{frame}
    \frametitle{CA and Polynomials}
    \begin{itemize}
        \item Let's look at the powers of $r(x) = 1 + x$:
        \begin{align*}
            (r(x))^{0} &=1 \\
            (r(x))^{1} &=1+x \\
            (r(x))^{2} &=1+2 x+x^{2} \\
            %(r(x))^{3} &=1+3 x+3 x^{2}+x^{3} \\ 
            & \vdots \\
            (r(x))^{n} &=a_{0}(n)+a_{1}(n) x+a_{2}(n) x^{2}+\cdots+a_{n}(n) x^{n} 
        \end{align*}
        \item By the addition rule of binomial coefficients
        \begin{equation*}
            a_k(n) = a_{k-1}(n-1) + a_k(n-1)
        \end{equation*}
        \item This is a Cellular Automata kind of behavior
    \end{itemize}
\end{frame}

% Maybe add a figure to give better explanation of last point
\begin{frame}
    \frametitle{CA and polynomials}
    %\frametitle{CA, Pascal's Triangle and Polynomial}
    \begin{itemize}
        %\item Looking at the divisibility properties of $a_k(n)$ with 2
        \item To color the triangle, we could look at divisibility of $a_k(n)$ with respect to 2
        \item Now, there are 2 possibilities 
        \begin{align*}
            a_k(n) \equiv 0 \pmod 2  \qquad or&& a_k(n) \equiv 1 \pmod 2
        \end{align*}
        \item The recursive addition rules in mod 2 arithmetic simplifies to
        \begin{table}
            \centering
            \begin{tabular}{|ccc|}
                \hline
                $\binom{n+1}{k} =$ & $\binom{n}{k-1}$& $+ \ \binom{n}{k} \ $\\
                \hline
                0 & 0 & 0 \\
                1 & 1 & 0 \\
                1 & 0 & 1 \\
                0 & 1 & 1 \\
                \hline
            \end{tabular}
        \end{table}
        %\item Exactly same rule set used to color the Pascal Triangle
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item If we set 1 = Black, 0 = White
        \begin{figure}
            \centering
            \includegraphics{addRule.pdf}
        \end{figure}
        \item If we add a right neighbor to the above rule such that it doesn't affect the output
        \begin{figure}
            \centering
            \includegraphics[scale=0.7]{rule60Num.pdf}
        \end{figure}
        \item This is rule $00111100_2 = 60$ Cellular Automata
    \end{itemize}

\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.4]{sierSmall}
        % Add generation axis to this plot 
        \begin{itemize}
            \item Thus, this figure shows the coefficients of the powers of $r(x) = 1+x \mod 2$
        \end{itemize}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \includegraphics[scale=0.5]{seir.pdf}
        \caption{A Bigger picture}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{Generalizations}
    \begin{itemize}
        \item There are 2 ways to generalize,
        \begin{enumerate}
            \item A different integer modulus 
            \item A different polynomial
        \end{enumerate}
        \item Ex: Let $r(x) = 1+2x$
        \begin{align*}
            (r(x))^0 &= 1 \\
            (r(x))^1 &= 1+2x \\
            (r(x))^2 &= 1 + 4x + 4x^2\\
            (r(x))^3 &= 1 + 6x + 12x^2 + 8x^3 \\
            &\vdots \\
            (r(x))^n &= a_0(n) + a_1(n)x + \dots + a_n(n)x^n
        \end{align*}
        \item By observation,
        \begin{equation*}
            a_k(n) = a_{k}(n-1) + 2a_{k-1}(n-1)
        \end{equation*}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item By looking at the remainder with p = 3,i.e $a_k(n)\mod3$ 
        \begin{align*}
            (r(x))^0 &= 1 \\
            (r(x))^1 &= 1 \ 2 \\
            (r(x))^2 &= 1 \ 1 \ 1 \\
            (r(x))^3 &= 1 \ 0 \ 0 \ 2
        \end{align*}
        \item The cellular automaton would be $a_{n,k} = a_{n-1,k} + 2a_{n-1,k-1} \mod 3$
        \begin{figure}
            \centering
            \includegraphics[scale=0.3]{Mod3Poly.pdf}
            \includegraphics[scale=0.6]{genPolyRule.pdf}
            \caption{CA for $r(x) = 1 + 2x \mod 3$ and rule table}
        \end{figure}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{genPolyRuleVertical.pdf}
        \includegraphics[scale=0.6]{Mod3Bigger.pdf}
        \caption{A bigger picture for rule $(02110221)_3 = 5421$}
    \end{figure}
\end{frame}

\begin{frame}
    \frametitle{Generalizations}
    \begin{itemize}
        \item Another quick example: $r(x) = 1 + x \mod 3$
        \begin{figure}
            \centering 
            \includegraphics[scale=0.5]{mod3ployrule.pdf}
            \includegraphics[scale=0.5]{PascalCAMod3.pdf}
        \end{figure}
        \item The CA rule is $a_{n,k} = a_{n-1,k} + a_{n-1,k-1} \mod 3$
    \end{itemize}
\end{frame}
% \begin{frame}
%     \frametitle{Linear Cellular Automata}
%     \begin{itemize}
%         \item We can start with any polynomial $r(x) = a_0 + a_1x+\dots+a_dx^d$
%         \item The coefficients of $(r(x))^n$ modulo some positive integer $p$ is obtained by an addition formula involving $d$ coefficients from              $(r(x))^{n-1}$
%         \item So, there is an associated Cellular Automata which generates coefficients modulo p of the powers of $(r(x))^n$
%         \item A look-up table can be generated by an addition formula
%         \item These are called \textit{Linear Cellular Automata}
%         \item Again, the choice of p determines the number of states.
%         This opens up a lot of interesting problems 
%     \end{itemize}
% \end{frame}

% % This slide needs improvement
% \begin{frame}
%     \begin{itemize}
%         \item Pattern Formation: Given a polynomial, what is the global pattern which evolves when the automaton has run for a long time?
%         \item Colors: What is the relation between the global patterns which are obtained for different choices of p?
%         \item Fractal Dimension: Fractal dimension of the global pattern ?
%         \item Higher Dimension: What if we used polynomial of m variables ? (m-dimensional ?)
%         \item Factorization: If a polynomial $r(x)$ can be factorized to two polynomials $s(x)$ and $t(x)$, how are the patters related ? Is that factorization unique ? \\
%         In general, no, it depends on $p$\\
%         Ex: $1+x$ is irreducible with respect to integers. But in arithmetic modulo $p$, with $p$ not prime, there are non trivial factorization
%         \begin{equation*}
%             1+x \equiv (1+3x)(1+4x) \pmod 6
%         \end{equation*}
%     \end{itemize}
% \end{frame}

\begin{frame}
    \centering
    \Large
    The Microscopic view 
\end{frame}

\section{Binomial Coefficients and Divisibility}

% Under review, be more descriptive 
\begin{frame}
    \frametitle{Binomial Coefficients and Divisibility}
    \begin{itemize}
        %\item Discuss the question of whether a binomial coefficient is divisible by $p$ or not. 
        \item Black and white coloring of the Pascal triangle depending on divisibility with $n$ (mod $n$), where n is an integer
        \item We will also that in order to understand the patterns formed by mod $n$, we should look at the patters formed by the prime factors of $n$ 
        \item We will look at a direct, non-recursive computation of binomial divisibility by p (prime)
        %\item This was solved in an elegant manner by Ernest Eduard Kummer.
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \includegraphics[scale=0.36]{PascalMod3.pdf}
        \caption{Pascal triangle Mod 3}
    \end{figure}
\end{frame}

\begin{frame}
    %\frametitle{Binomial Coefficients and Divisibility}
    \begin{itemize}
        \item We define a new coordinate system such that, at position $(n,k)$ the binomial coefficient is 
        \begin{equation*}
            \binom{n+k}{k} = \frac{(n+k)!}{n!k!}
        \end{equation*}
        \begin{figure}
            \centering
            \includegraphics[scale=0.39]{newCoordinate.png}
            \caption{A new coordinate system}
        \end{figure}
    \end{itemize}
    \let\thefootnote\relax\footnotetext{Fig. from "Chaos and Fractals" Pg 394}
\end{frame}

\subsection{Divisibility Sets}
\begin{frame}
    \frametitle{Divisibility Sets}
    \begin{itemize}
        \item We formally define our problem
        \begin{equation*}
            P(r) = \left\{ (n,k) \left| \binom{n+k}{k} \text{ is not divisible by }r \right. \right\}
        \end{equation*}
        \item Plotting the points in this set gives the same Pascal Triangle pattern
        \begin{figure}
            \centering
            \includegraphics[scale = 0.5]{P(2)}
            \caption{$P(2)$ or Mod 2}
        \end{figure}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Divisibility Sets}
    \begin{itemize}
        \item Observe that if $p$ and $q$ are two different prime numbers and a given integer $r$ is \textbf{not} divisible by $p \cdot q$, then it is \textbf{not} divisible by either $p$ or $q$
        \begin{equation*}
            P(pq) = P(p) \cup P(q) \text{, if $p \neq q$, $p,q$ prime} \tag{$\dagger$}
        \end{equation*}
        \item Eq $(\dagger)$ is the negation of the statement: If $pq$ divides $r$, then $r$ is divisible by both $p$ and $q$.
        \item Ex: $P(6) = P(2) \cup P(3)$ %This generalization can be extended to any integer
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \begin{minipage}[c]{.45\textwidth}
            \includegraphics[width=1\linewidth,clip]{mod6Initalmod2.pdf}
            \centering
            $P(2)$ or Mod 2
        \end{minipage}
        \hfill
        \begin{minipage}[c]{.45\textwidth}
            \includegraphics[width=1\linewidth,clip]{Mod6InitalMod3.pdf}
            \centering
            $P(3)$ Mod 3
        \end{minipage}
        % Add a few more figures, so as to give a more clear description of this union. 
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[width=0.475\textwidth]{Mod6.pdf}
        \hfill
        \includegraphics[width=0.475\textwidth]{mod2,3.jpg}
        \caption{Left shows Mod 6 ($P(6)$) pattern and right shows the union of mod 2 (Red) and mod 3 (Blue)}
        % Add a few more figures, so as to give a more clear description of this union. 
    \end{figure}
\end{frame}


\begin{frame}
    \begin{itemize}
        \item For an integer $r = p_1^{n_1}\dots p_s^{n_s}$ where $p_1,\dots,p_s$ are primes
        \begin{equation*}
            P(r) = P(p_1^{n_1}) \cup ... \cup P(p_s^{n_s})
        \end{equation*}
        \item So to understand the pattern formed by $P(r)$, we just need to understand the pattern of $P(p^n)$
        \item We can construct $P(p)$ in a non-recursive direct method using Kummer's result
    \end{itemize}
\end{frame}

\subsection{Kummer's Result}
\begin{frame}
    \frametitle{Kummer's Result and p-adic numbers}
    \begin{itemize}
        \item To understand Kummer's result, we need to consider numbers with base $p$, where $p$ is prime 
        \item Like the decimal system, p-adic expansion of an integer is given by
        \begin{equation*}
            n = a_0 + a_1p +\dots + a_m p^m
        \end{equation*}
        where $a_i \in \{0,1,\dots,p-1\}$
        \item The p-adic representation would be 
        \begin{equation*}
            n = (a_m a_{m-1} \dots a_0)_p
        \end{equation*} 
        \item Ex: $15_{10} = (1111)_2 = (120)_3 = (30)_5 = (21)_7 = (14)_{11}$ 
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item We define carry function $c_p$
        \begin{equation*}
            c_p(n,k) = \text{number of carries in the p-adic addition of n and k}
        \end{equation*}
        \item Ex: For $n = 15$ and $k=8$
        \begin{equation*}
            k=(08)_{10}=(1000)_{2}=(022)_{3}=(13)_{5}=(11)_{7}=(08)_{11}
        \end{equation*}
        \item If we take the binary addition
        \begin{tabular}{cccccc}
            & $0^1$ & $1$ & $1$ & $1$ & $1$ \\
            + & $0$ & $1$ & $0$ & $0$ & $0$ \\
            \hline
            & $1$ & $0$ & $1$ & $1$ & $1$ 
        \end{tabular}
        \begin{equation*}
            c_2(15,8) = 1
        \end{equation*}
        \item Similarly, we can do the same for $p=3,5,7\dots$
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Kummer's result}
    \begin{itemize}
        \item Kummer's Statement is:
        \begin{quote}
            Let $r = c_p(n,k),$ then $\binom{n+k}{k}$ is divisible by $p^r$ but not $p^{r + 1}$
        \end{quote}
        \item So, prime factorization of $\binom{n+k}{k}$ contains exactly $c_p(n,k)$ factors of $p$
        \item This result is pretty amazing, since it gives a direct method to check if a binomial coefficient is divisible by $p$ or not.
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item For $n=5$ and $k=4$, Kummer's result says
        \begin{equation*}
            n = (101)_2 = (12)_3 = (10)_5 = (5)_7
        \end{equation*}
        \begin{equation*}
            k = (100)_2 = (11)_3 = (4)_5 = (4)_7
        \end{equation*}
        \item In Base 2 addition
        \begin{tabular}{cccccc}
            & $0^1$ & $1$ & $0$ & $1$ \\
            + & $0$ & $1$ & $0$ & $0$ \\
            \hline
            & $1$ & $0$ & $0$ & $1$  
        \end{tabular}
        $\Rightarrow c_2(5,4) = 1$ 
        \item In Base 3 addition 
        \begin{tabular}{cccccc}
            & $0^1$ & $1^1$ & $2$\\
            + & $0$ & $1$ & $1$\\
            \hline
            & $1$ & $0$ & $0$   
        \end{tabular}
        $\Rightarrow c_3(5,4) = 2$
        \item Similar additions can be done for $p = 5,7,11\dots$
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        
        \item Kummer's result says:
        \begin{equation*}
            c_{p}(5,4)=\left\{\begin{array}{l}{1, \text { for } p=2,7} \\
            {2, \text { for } p=3 } \\
        {0 \text{ otherwise }}\end{array}\right.
        \end{equation*}
        \item This implies 
        \begin{equation*}
            \binom{5+4}{4} = \binom{9}{4} = 2^1 \cdot 3^2 \cdot 7^1
        \end{equation*}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Applying Kummer's result to Divisibility Set gives 
        \begin{equation*}
            P(p) = \{(n,k) | \ c_p(n,k) = 0\}
        \end{equation*}
        \item That is, the number of carries $c_p(n,k)$ is only $0$ if and only if 
        \begin{equation*}
            a_i + b_i < p, \quad i = 0,\dots,m
        \end{equation*}
        where $a_i$ and $b_i$ are the p-adic digits of n and k. 
        %\item This is called the \textit{mod-p} condition.
        %\item For prime powers, 
        % Review this equation 
        %\begin{equation*}
        %    P(p^\tau) = \{(n,k)| \ c_p(n,k) < \tau \}
        %\end{equation*}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \includegraphics[width=0.475\textwidth]{P(5)cp.pdf}
        \hfill
        \includegraphics[width=0.475\textwidth]{P(5)Bi.pdf}
        \caption{$P(5)$ generated using carry function (left) vs binomial divisibility (right)}
        % Make them the same size 
        % Put more figures also, define for P(2) P(3)...
    \end{figure}
        
\end{frame}

\begin{frame}
    \centering
    \Large
    The Big Picture
\end{frame}

\section{Iterated Function System}
\begin{frame}
    \frametitle{Iterated Function System}
    \begin{itemize}
        \item A method of constructing fractals using a set of contraction mappings. 
        \item A contraction mapping is an affine linear transformation 
        \begin{equation*}
            f(x, y)=\left[ \begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right] \left[ \begin{array}{l}{x} \\ {y}\end{array}\right]+\left[ \begin{array}{l}{e} \\ {f}\end{array}\right]
        \end{equation*}
        where
        \begin{equation*}
            \text{det}\left(\left[ \begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right]\right) < 1
        \end{equation*}
        \item Union of these contraction mappings gives the Hutchinson equation of the fractal
        %\item If you put a probability factor to these contraction mappings, you get some pretty images. 
    \end{itemize}
\end{frame}

% Some pretty pictures and some details about them 

\begin{frame}
    \begin{itemize}
    \item The Hutchinson operator for Sierpinski Triangle is:
    \begin{equation*}
        S = w_{00}(S) \cup w_{01}(S) \cup w_{10}(S)
    \end{equation*}
    where $w_{ij}$ are contraction mappings of a unit square
    \begin{align*}
        w_{00} &= (x/2,y/2)\\
        w_{01} &= (x/2, y/2+1/2) \\
        w_{10} &= (x/2 + 1/2, y/2) \\
        w_{11} &= (x/2 + 1/2 + y/2 + 1/2)
    \end{align*}
    % \item So how do we know for sure that our Pascal Sierpinski triangle is the same as the Hutchinson operator Sierpinski Triangle?
    % \item Let's construct Mod 2 Pascal triangle in a unit square
    \item Let $Q$ be a unit square  
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.2]{w_00.pdf}
        \includegraphics[scale=0.2]{w_01.pdf}
        \includegraphics[scale=0.2]{w_10.pdf}
    \end{figure}

\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{0.pdf}
        \caption{Initial region, $Q = S^0$}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{1.pdf}
        \caption{$S^1 = S(Q)$}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{2.pdf}
        \caption{$S^2 = S(S(Q))$}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{3.pdf}
        \caption{$S^3 = S(S(S(Q)))$}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{5.pdf}
        \caption{$S^5$}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{GlobalMod2}
        \caption{$S^\infty$}
    \end{figure}
\end{frame}

\begin{frame}
    \centering
    So how do we know for sure that our Pascal Triangle pattern is the Sierpinski Triangle ?
\end{frame}
\begin{frame}
    \begin{itemize}
        \item Let's construct Mod 2 Pascal triangle in a unit square
        \item Let $Q$ be the unit square 
        \begin{equation*}
            Q = \{(x,y) | \ (x,y) \in [0,1] \times [0,1]\}
        \end{equation*}
        \item Expand $x$ and $y$ in base 2 \\
        \begin{minipage}[c]{0.45\textwidth}
            \begin{align*}
                x &= \sum_{i=1}^\infty a_i 2^{-i}, \ a_i \in \{0,1\} \\
                y &= \sum_{i=1}^\infty b_i 2^{-i}, \ b_i \in \{0,1\}
            \end{align*}
        \end{minipage}
        \hfill
        \begin{minipage}[c]{0.45\textwidth}
            \begin{figure}
                \centering
                \includegraphics[scale=0.55]{PascalSq.pdf}
            \end{figure}
        \end{minipage}
        \item From Kummer's result, we know that the coordinates of the points not divisible by 2 are those which have no carries in the binary addition of the coordinates
        \begin{equation*}
            S = \{(x,y) \in Q| \ a_i + b_i \leq 1 \ \forall i\}
        \end{equation*} 
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Proof}
    \begin{itemize}
        \item To show $S$ is the Sierpinski Triangle, $S$ must be invariant under the Hutchinson operator
        \begin{equation*}
            w_{00}(S) \cup w_{01}(S) \cup w_{10}(S) = S 
        \end{equation*}
        \item Take any point $(x,y) \in S$
        \begin{equation*}
            (x,y) = (0.a_1a_2\dots,0.b_1 b_2 \dots)
        \end{equation*}
        where $a_i + b_i \leq 1$
        \item To understand Hutchinson operator in action 
        \begin{gather*}
            \frac{x}{2} = \frac{a_12^{-1} + a_2 2^{-2} + a_3 2^{-3}\dots}{2} = 0 \cdot 2^{-1} a_12^{-2} + a_2 2^{-3} + a_3 2^{-4}\dots \\ = (0.0a_1 a_2 a_3)_2
        \end{gather*}
        \begin{gather*}
            \left(\frac{x}{2}+\frac{1}{2}\right) = \frac{1}{2} + 0 \cdot 2^{-1} a_12^{-2} + a_2 2^{-3} + a_3 2^{-4}\dots \\
            =(0.1a_1 a_2 a_3)_2
        \end{gather*}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Applying the 3 transformations gives 
        \begin{align*}
            w_{00}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.0a_1a_2\dots,0.0b_1 b_2 \dots) \\
            w_{01}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.0a_1a_2\dots,0.1b_1 b_2 \dots) \\
            w_{10}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.1a_1a_2\dots,0.0b_1 b_2 \dots)
        \end{align*}
        \item Clearly, all these points are also in $S$.
        \item Therefore, $S$ is invariant under the Hutchinson operator
        \item So..., $S$ is indeed the Sierpinski Triangle 
    \end{itemize}
\end{frame}

% Section removed from main slides 
% \begin{frame}
%     \frametitle{Proof} %by symbols}
%     \begin{itemize}
%         \item To show both are the same, we need to show
%         \begin{equation*}
%             w_{00}(S) \cup w_{01}(S) \cup w_{10}(S) \subset S 
%         \end{equation*}
%         and, 
%         \begin{equation*}
%             w_{00}(S) \cup w_{01}(S) \cup w_{10}(S) \supset S
%         \end{equation*}
%         \item Take any point $(x,y) \in S$ 
%         \begin{equation*}
%             (x,y) = (0,a_1a_2\dots,0.b_1 b_2 \dots)
%         \end{equation*}
%         where $a_i + b_i \leq 1$
%         \item Applying the 3 transformations gives 
%         \begin{align*}
%             w_{00}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.0a_1a_2\dots,0.0b_1 b_2 \dots) \\
%             w_{01}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.0a_1a_2\dots,0.1b_1 b_2 \dots) \\
%             w_{10}(0.a_1a_2\dots,0.b_1 b_2 \dots) &= (0.1a_1a_2\dots,0.0b_1 b_2 \dots)
%         \end{align*}
%     \end{itemize}
% \end{frame}
% %\end{comment}

% \begin{frame}
%     \begin{itemize}
%         \item Clearly, all these points are also in $S$.
%         \item To show the second relation, we take any point $(x,y) \in S$, and we have to provide another point $(x',y') \in S$ such that $(x,y)$ is one of the images of $w_{00}(x',y'),w_{10}(x',y'),$ or $w_{01}(x',y')$. We choose 
%         \begin{equation*}
%             (x',y') = (0.a_2\dots,0.b_2\dots)
%         \end{equation*}
%         \item We obtain 
%         \begin{equation*}
%             (x, y)=\left\{\begin{array}{l}{w_{00}\left(x^{\prime}, y^{\prime}\right) \text { if } a_{1}=0 \text { and } b_{1}=0 \text { or }} \\ {w_{01}\left(x^{\prime}, y^{\prime}\right) \text { if } a_{1}=0 \text { and } b_{1}=1 \text { or }} \\ {w_{10}\left(x^{\prime}, y^{\prime}\right) \text { if } a_{1}=1 \text { and } b_{1}=0}\end{array}\right.
%         \end{equation*}
%         \item This completes our proof.
%     \end{itemize}
% \end{frame}

\begin{frame}
    \frametitle{Concequences}
    \begin{itemize}
        \item The binary representation allows us to see Hutchinson operator in action applied to a point inside square
        \item If $(x,y)$ is an arbitrary point in $Q$, the applying the map $w_{00},w_{01},w_{10}$ again and again yields points with leading binary decimal points satisfying $a_i + b_i \leq 1$
        \item In symbols,
        \begin{equation*}
            A_0 = Q
        \end{equation*} 
        Then running the IFS gives 
        \begin{equation*}
            A_n = w_{00}(A_{n-1}) \cup w_{01}(A_{n-1}) \cup w_{10}(A_{n-1})
        \end{equation*}
        where the leading $n$ binary digits satisfy $a_i + b_i \leq 1$
        \item Finally, the sequence will lead to Sierpinski triangle
        \begin{equation*}
            \lim_{n \to \infty} A_n = S
        \end{equation*}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{IFS for other primes}
    \begin{itemize}
        %\item Now, we can finally look into the global pattern formation of divisibility of binomial coefficients with primes, i.e the global patterns formed by 
        \item With similar arguments we can construct IFS for any prime p
        % \begin{equation*}
        %     P(r) = \left\{ (n,k) \left| \binom{n+k}{k} \text{is not divisible by }r \right. \right\}
        % \end{equation*}
        \item Divide the unit square $Q$ in $p^2$ congruent square $Q_{a,b}$ with $a,b \in \{0,\dots,p-1\}$. We introduce the contraction mappings 
        \begin{equation*}
            w_{a,b}(x,y) = \left(\frac{x+a}{p}, \frac{y+b}{p}\right)
        \end{equation*} 
        where 
        \begin{equation*}
            w_{a,b}(Q) = Q_{a,b}
        \end{equation*}
        \item Then we set the restriction to define the set of transformation
        \begin{equation*}
            a+b \leq p-1
        \end{equation*}
        
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.25]{IFSp3.pdf}
        \caption{1st Generation of Mod 3 IFS}
    \end{figure}
    \begin{itemize}
        % \item Then we set the restriction to define the set of transformation
        % \begin{equation*}
        %     a+b \leq p-1
        % \end{equation*}
        \item This restriction follows from Kummer's result,i.e $\binom{n+k}{k}$ is indivisible by $p$ when there is no carries in the p-adic addition of $n,k$
        \item The Hutchinson operator for these contractions,
        \begin{equation*}
            W_p(A) = \bigcup_{a+b < p} w_{a,b}(A)
        \end{equation*} 
    \end{itemize}
\end{frame}

%need to improve this section, very less detail about the figures 
% \begin{frame}
%     \begin{figure}
%         \centering
%         \includegraphics[scale=0.5]{GlobalMod2.pdf}
%         \caption{Limit of Mod 2 IFS}
%     \end{figure}
% \end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{GlobalMod3.pdf}
        \caption{Limit of Mod 3 IFS.}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{GlobalMod5}
        \caption{Limit of Mod 5 IFS.}
    \end{figure}
\end{frame}

\begin{frame}
    \begin{figure}
        \centering
        \includegraphics[scale=0.5]{GlobalMod7}
        \caption{Limit of Mod 7 IFS.}
    \end{figure}
\end{frame}

\section*{}
% Fix this issue, Slide should be out of all sections 
\begin{frame}
    \frametitle{Summary}
    \begin{itemize}
        \item We approached the problem of coloring (or divisibility) of pascal's triangle in 3 different ways 
        \begin{enumerate}
            \item First, we looked at the macroscopic nature of divisibility, i.e how the neighbors affected the divisibility of a cell. We then explored the realm of cellular automata and how it extends this idea to general polynomials.
            \item Second, we looked at the microscopic nature of divisibility,i.e how the divisibility of a cell depends on its coordinate (Kummer's Result). We looked how p-adic numbers gave insight about binomial divisibility with primes.
            \item Finally, we looked at the global pattern using Iterated function system. We showed that the limit of Pascal Mod 2 pattern was indeed the Sierpinski triangle. We also explored the global patterns of other primes and their IFS. 
        \end{enumerate}
    \end{itemize}
\end{frame}

\begin{frame}
    \begin{itemize}
        \item Each method gave a different perspective of the same problem.
        \item This entire chapter is trying to solve the jig-saw puzzle that relates fractals, Pascal's triangle, and Cellular Automata. 
        \item Understanding that these 3 very different things are all tied up by one common thread is, honestly, amazing.
    \end{itemize}
\end{frame}

\begin{frame}
    \centering 
    \Huge{Thank You!}
\end{frame}

% 2 figures were taken out from the text book, need to reference them 
% One figure from MathWorld 

% Add references, for code and images 
% Use footnotes 
% Use mesh 
% Mini frames off 

\begin{frame}
    \frametitle{References}
    \begin{itemize}
        \item Most of the content in this presentation is based on "Chaos and Fractals: New Frontiers of Science" by Peitgen, H et al
        2003.
        \item Slide 29: Image was directly taken from the book "Chaos and Fractals" Pg. 394
        \item Slide 3,4,28: Modified Tikz code from \url{https://tex.stackexchange.com/questions/198887/how-can-i-draw-pascals-triangle-with-some-its-properties}
        \item Mathematica was used to generate most of the figures.
        \item Inkscape, an open source image editing software, was used to edit all vector images. \url{https://inkscape.org/}
    \end{itemize}
\end{frame}

\end{document}