%% slacpub7115: page file slacpub7115004.tcx.
%% section 4 Lattice Paths [slacpub7115004 in slacpub7115004: slacpub7115005]
%%%% latex2techexplorer block:
%% latex2techexplorer page setup:
\iftechexplorer
\setcounter{section}{3}
\fi
\iftechexplorer
\setcounter{secnumdepth}{2}
\setcounter{tocdepth}{2}
\def\thepart#1{}%
\def\thechapter#1{}%
\newcommand{\partLink}[3]{\docLink{#1.tcx}[part::#2]{#3}\\}
\newcommand{\chapterLink}[3]{\docLink{#1.tcx}[chapter::#2]{#3}\\}
\newcommand{\sectionLink}[3]{\docLink{#1.tcx}[section::#2]{#3}\\}
\newcommand{\subsectionLink}[3]{\docLink{#1.tcx}[subsection::#2]{#3}\\}
\newcommand{\subsubsectionLink}[3]{\docLink{#1.tcx}[subsubsection::#2]{#3}\\}
\newcommand{\paragraphLink}[3]{\docLink{#1.tcx}[paragraph::#2]{#3}\\}
\newcommand{\subparagraphLink}[3]{\docLink{#1.tcx}[subparagraph::#2]{#3}\\}
\newcommand{\partInput}{\partLink}
\newcommand{\chapterInput}{\chapterLink}
\newcommand{\sectionInput}{\sectionLink}
\else
\newcommand{\partInput}[3]{\input{#2.tcx}}
\newcommand{\chapterInput}[3]{\input{#2.tcx}}
\newcommand{\sectionInput}[3]{\input{#2.tcx}}
\fi
\newcommand{\subsectionInput}[3]{\input{#2.tcx}}
\newcommand{\subsubsectionInput}[3]{\input{#2.tcx}}
\newcommand{\paragraphInput}[3]{\input{#2.tcx}}
\newcommand{\subparagraphInput}[3]{\input{#2.tcx}}
\aboveTopic{slacpub7115.tcx}%
\previousTopic{slacpub7115003.tcx}%
\nextTopic{slacpub7115005.tcx}%
\bibfile{slacpub7115005u2.tcx}%
\newmenu{slacpub7115::context::slacpub7115004}{
\docLink{slacpub7115.tcx}[::Top]{Top}%
\sectionLink{slacpub7115003}{slacpub7115003}{Previous: 3. Discrete Calculus and Solutions to the Dirac Equation}%
\sectionLink{slacpub7115005}{slacpub7115005}{Next: 5. Epilogue}%
}
%%%% end of latex2techexplorer block.
%%%% code added by add_nav perl script
\docLink{slacpub7115.tcx}[::Top]{Top of Paper}%

\docLink{pseudo:previousTopic}{Previous Section}%
\bigskip%
%%%% end of code added by add_nav
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% author definitions added by nc_fix
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\baselinestretch}{1.4}
\renewcommand{\baselinestretch}{1.4}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% end of definitions added by nc_fix
\section{\usemenu{slacpub7115::context::slacpub7115004}{Lattice Paths}}\label{section::slacpub7115004}
In this section we interpret the discrete solutions of the Dirac
equation given in the previous section in terms of counting lattice
paths. As we have remarked in the previous section, the solutions
are built from the functions $\psi_0$, $\psi_R$ and $\psi_L$. These
functions are finite sums when $r/\Delta$ and $\ell/\Delta$ are
positive integers, and we can rewrite them in the form
\begin{eqnarray}
\psi_R(r,\ell) &=& \Sigma_{k=0}^{\infty}
(1)^k\Delta^{2k+1}C_{k+1}^{r/\Delta}C_k^{\ell/\Delta}\nonumber \\
\psi_L(r,\ell) &=& \Sigma_{k=0}^{\infty}
(1)^k\Delta^{2k+1}C_{k}^{r/\Delta}C_{k+1}^{\ell/\Delta} \\
\psi_0(r,\ell) &=& \Sigma_{k=0}^{\infty}
(1)^k\Delta^{2k+1}C_k^{r/\Delta}C_k^{\ell/\Delta}\nonumber
\end{eqnarray}
where
\begin{equation}
C_n^{z} = \frac{z(z1)\cdot\cdot\cdot(zn+1)}{n!}
\end{equation}
denotes the choice coefficient.
\vspace{.5cm}
\begin{figure}[htb]
\begin{center}
\leavevmode
{\epsfxsize=3.75truein \epsfbox{8131A10.eps}}
\end{center}
\caption{Rectangular lattice in Minkowski spacetime.}
\label{fig1}
\end{figure}
We are thinking of $r$ and $\ell$ as the light cone coordinates
$r=\frac{1}{2}\,(t+x)$, $\ell=\frac{1}{2}\,(tx)$. Hence, in a standard
diagram for Minkowski spacetime, a pair of values $[r,\ell]$
determines a rectangle with sides of length $\ell$ and $r$ on the left
and right pointing light cones. (We take the speed of light $c=1$.)
This is shown in Figure. 1.
Clearly, the simplest way to think about this combinatorics is to
take $\Delta =1$. If we wish to think about the usual continuum
limit, then we shall fix values of $r$ and $\ell$ and choose $\Delta$
small but such that $r/\Delta$ and $\ell/\Delta$ are integers. The
combinatorics of an $r\times \ell$ rectangle with integers $r$ and
$\ell$
is no different in principle than the combinatorics of an
$(r/\Delta)\times (\ell/\Delta)$ rectangle with integers $r/\Delta$ and
$\ell/\Delta$. Accordingly, we shall take $\Delta = 1$ for the rest of
this discussion, and then make occasional comments to connect this
with the general case.
\vspace{.5cm}
\begin{figure}[htb]
\begin{center}
\leavevmode
{\epsfxsize=3.75truein \epsfbox{8131A01.eps}}
\end{center}
\caption{An example of a path in the lightcone
rectangle.}
\label{fig2}
\end{figure}
Finally, for thinking about the combinatorics of the $r\times \ell$
rectangle, it is useful to view it turned by $45^o$ from its
lightcone configuration. This is shown in Fig. 2.
We shall consider lattice paths on the $r\times \ell$
rectangle from $A=[0,0]$ to $B=[r,\ell]$. Each step in such a path
consists in an increment of either the first or the second light
cone coordinate. The ``particle'' makes a series of ``left or
right'' choices to get from A to B. In counting the lattice paths we
shall represent {\it left} and {\it right} by
\bigskip
\hskip2in\vbox{\epsfxsize=.75truein\epsfbox{8131A02.eps}}
\noindent
(Left is vertical in the rotated representation.)
Now notice that a lattice path has two types of corners:
\hskip1.5in\vbox{\epsfxsize=1.75truein \epsfbox{8131A03.eps}}
We can count RL corners by the point on the L axis where the path
increments. We can count LR corners by the point on the R axis where
the path increments. A lattice path is then determined by a choice
of points from the L and R axes. More specifically, there are paths
that begin in R (go right first) and end in L, begin in L and end in
R, begin in L and end in L, begin in R and end in R. We call these
paths of type RL, LR, LL and RR respectively. (Note that a RL corner
is a twostep path of type RL and that an LR corner is a two step
path of type LR.) It is easy to see that an RL path involves $k$
points from the R axis and $k+1$ points from the L axis, an LR path
involves $k+1$ points from the R axis and k points from the L axis,
while an LL or RR path involves the choice of $k$ points from each
axis. See Figure 3 for examples.
\vspace{.5cm}
\begin{figure}[htb]
\begin{center}
\leavevmode
{\epsfxsize=3.5truein \epsfbox{8131A04.eps}}
\end{center}
\caption{Showing by example that $C_k^rC_{k+1}^\ell$ enumerates RL
paths and $C_k^rC_k^\ell$ enumerates RR paths.}
\label{fig3}
\end{figure}
\noindent
As a consequence, we see that if $\Vert XY\Vert$ denotes the number
of paths from A to B of type XY, then
\begin{eqnarray}
\Vert RL\Vert &=& \Sigma_kC_k^rC_{k+1}^\ell \nonumber \\
\Vert LR\Vert &=& \Sigma_kC_{k+1}^rC_k^\ell \\
\Vert RR\Vert &=& \Vert LL\Vert=\Sigma_kC_k^rC_k^\ell\ . \nonumber
\end{eqnarray}
We see, therefore, that our functions $\psi_0$, $\psi_R$ and
$\psi_L$ can be regarded as weighted sums over these different types
of lattice path. In fact, we can reinterpret $()^k$ in terms of
the number of corners (choices) in the paths:
\newpage
\begin{eqnarray*}
RR &\Rightarrow& 2k \ \hbox{corners} \\
LR &\Rightarrow& 2k+1 \ \hbox{corners} \\
RL &\Rightarrow& 2k+1 \ \hbox{corners} \\
LL &\Rightarrow& 2k \ \hbox{corners} \ .
\end{eqnarray*}
Hence if $N_c(XY)$ denotes the number of paths with $c$ corners of
type XY then
\begin{eqnarray}
\psi_0 &=& \Sigma_c (1)^{\frac{c}{2}}N_c(LL) = \Sigma_c (1)
^{\frac{c}{2}}\,N_c(RR)\nonumber \\
\psi_R &=& \Sigma_c (1)^{\frac{c1}{2}}\,N_c(LR) \\
\psi_L &=& \Sigma_c (1)^{\frac{c1}{2}}\,N_c(RL)\ . \nonumber
\end{eqnarray}
From the point of view of the solution to the RI Dirac equation
($\psi_1=\psi_0\psi_L$, $\psi_2=\psi_0+\psi_R$) it is an
interesting puzzle in discrete physics to understand the nature of
the negative case counting that is entailed in the solution. (An
attempt has been made by one of us to interpret this in terms of
spin or particle number conservation in the presence of random
electromagnetic fluctuations producing the paths
\cite{9}.) The signs do not appear to come from local
considerations along the path.
The RII Dirac solution gives a different point of view. Here
$\psi_1=\psi_0i\psi_L$, $\psi_2=\psi_0i\psi_R$. Taken the hint
given by the appearance of $i$, we note that $i^{2k}=()^k$ while
$i^{2k+1} = (1)^ki$. Thus
\[
\psi_1 = \Sigma_c(i)^cN_c(R) \qquad
\psi_2 = \Sigma_c(i)^cN_c(L) \]
where $N_c(R)$ denotes the number of paths that start to the right
and have $c$ crossings, while $N_c(L)$ denotes the number of paths
that start to the left and have $c$ crossings. This shows that our
solution in the RII case is precisely in line with the amplitudes
described by Feynman and Hibbs (Ref. \cite{2}) for their
checkerboard model of the Dirac propagator. See also H. A. Gersch
\cite{10} and Ref. \cite{3} for the relationship of the
Feynman model to the combinatorics of the Ising model in statistical
mechanics.
Returning now to the RI equation, we see that $(i)^cN_c$ gives the
clue to the combinatorics of the signs. In our RI formulation, no
complex numbers appear and none are needed if we take a
combinatorial interpretation of $i$ as an operator on ordered pairs:
$i[a,b] = [b,a]$. Then we can think of a ``prespinor'' in the form
of a labeled $\frac{\pi}{2}$ angle associated to each corner:
\vspace{.5cm}
\begin{figure}[htb]
\begin{center}
\leavevmode
{\epsfxsize=2truein \epsfbox{8131A05.eps}}
\end{center}
\end{figure}
\noindent
As the particle moves from corner to corner its prespinor is
operated on by $i$. There is a combination of one sign change and
one change in order. The total sign change from the beginning of the
path to the end documents the positivity or negativity of the count.
%%%% code added by add_nav perl script
\bigskip%
\docLink{pseudo:nextTopic}{Next Section}%

\docLink{slacpub7115005u2.tcx}[::Bottom]{Bottom of Paper}%
%%%% end of code added by add_nav